[ 영상 처리 ] Ch8. Clustering and Segmentation(1)

본 영상 처리 개념과 기법들에 대한 공부를 진행하면서 배운 내용들을 중심으로 정리한 포스팅입니다. 

책은 Computer Vision: Algorithms and Applications를 기반으로 공부하였습니다.

또한, 인하대학교 박인규 교수님의 디지털 영상 처리 과목을 기반으로 제작된 포스팅입니다.

---

Before This Episode

https://jinwoo-jung.tistory.com/80

[ 영상 처리 ] Ch7. Color Image Processing

---

Clustering

 

 

• Clustering
  • 군집화
  • 무작위한 데이터들을 상호간의 관계 혹은 기준에 따라 비슷한 것들끼리 하나의 집합으로 묶는 과정
  • 비지도 학습
  • K-Means, MeanShift, etc

 

K-Means Clustering

Clustering을 다시한번 정의하면, Data를 최적 개수의 군집으로 나누는 과정이라고 할 수 잇다. 그 중, K-Means Clustering의 목표는 주어진 데이터의 분산을 최소화 하면서 Clustering을 수행하는 것이다. 앞의 $K$가 의미하는 바는, 군집화의 개수가 "K"개로 정해져 있음을 의미한다.

 

 

수식에 대한 이해가 필요한데, $d$는 Cluster Center($c_i$)와 data($x_j$)의 distance(차이)를 의미한다. 그리고 $\delta_{ij}$는 Cluster Assignment로, distance에 따라서 $x_j$가 $c_i$를 Cluster Center로 하는 Cluster에 속하는지를 판단한다. 만약 속한다면 1, 속하지 않으면 0을 할당한다. 이를 모든 Data, Cluster Center에 반복하고 $N$으로 나눠 평균을 취한다. 

 

 

 

수식 중 일부만 가져와 다시 생각 해 보면, $\delta$(군집관계)를 고려하여 $x_j$로 부터 거리가 가장 가까운 $c_i$를 의마하고, 해당 수식을 최소로 하는 $c,\delta$를 찾는 것이 우리의 목적이다. $K$개의 Cluster라고 고정되어 있기 때문에, 결국 Cluster Center $c$의 개수도 정해져 있다. 따라서 전체 데이터에 대하여 정해진 $c$와의 거리가 최소가 되는 군집을 형성시키는 것이 $K$ Means Clustering이다. 그 과정에서 $c_i$ 역시 해당 Cluster에 속하는 $x_j$들에 영향을 받게 되어 변화 될 것이다. 

 

 

그림으로 $K = 2$인 $K$ Means Clustering 과정을 살펴보자. 주어진 데이터(초록색)에 대하여 $K=2$이기 때문에, Random Cluster Center(파란색, 빨간색)을 선택하였다. 이후 데이터와 Cluster Center에 대하여 거리를 비교해 더 가까운 Cluster Center로 해당 데이터들을 Clustering 한다. 

 

Decision Boundary는 보라색으로 표현된 경계로, 두 Cluster Center의 수직으로 형성된다. 이는 해당 경계를 기준으로 Clustering이 이루어 짐을 의미한다. 

 

 

 

이후 각 Cluster에 속하는 데이터 들의 무게중심(평균)으로 Cluster Center를 Update 한다. 

 

Cluster Center가 변화 되었으므로, 다시 모든 데이터에 대하여 Clustering 과정을 반복한다. Update 된 Cluster Center를 기준으로 데이터들의 거리가 최소로 되도록 Clustering이 이루어진다. 이 과정을 계속 반복한다.

 

 

이 과정을 반복하게 된다면, Cluster Center는 일정한 Threshold 범위 이상 변화되지 않고 해당 위치 주변을 맴돌게 된다. 이때, Clustering을 종료하면 K-Means Clustering이 완료 된다. 그 결과 아래와 같다.

 

 

K-Means Clustering Process

 

그림으로 설명한 과정을 수식화 한 것이 위 Process이다. 처음에 무작위로 Cluster Centers를 설정한다. 이후 모든 포인트에 대하여 Cluster Center와 Data의 Distance를 기준으로 최적의 군집관계를 형성한다. 이후 형성된 군집관계를 기반으로 Cluster Center를 Update한다. 앞서서는 무게중심을 구한다고 했는데, 수식을 보면 군집관계를 기반으로 Cluster Center와 해당 Cluster에 속하는 Data들의 차이(거리)를 최소로 하는 Cluster Center로 Update 된다. 위 과정을 데이터의 군집관계가 변화되지 않을 때 까지 즉, Cluster Center의 Update가 매우 적을 때 까지 반복한다.

 

그렇기에 $K$-Means Clustering은 초기 Cluster Center의 위치가 매우 중요하다. 또한, Cluster Center와 Data의 Distance를 구할 때 사용되는 측정 방법이 달라질 수 있다. 기본적으론 Uclidean을 쓰지만 다양한 방법들이 있다.

 

K-Means Clustering : Pros

K-Means Clustering의 장점은 구현이 쉽고 빠르다. 또한, Cluster Center는 데이터의 분산을 최소로 하기 때문에, 데이터를 표현하는 좋은 지표가 될 수 있다.

 

K-Means Clustering : Cons

동작 속도가 빠를수도 있지만, 이는 차원에 따라 달라질 수 있다. 각 Iteration 즉, 반복 과정은 $O(KNd)$에 동작하는데, $K$는 Clustering 수, $N$은 데이터 갯수, $d$는 차원이다. 따라서 차원이 커지면 속도가 느려질 수 있다.

 

또한, 사전에 $K$를 정해놔야 하고, Outlier에 민감하다.

 

위 상황과 같이 Outlier에 의해서 오른쪽 Cluster Center가 왜곡됨을 확인할 수 있다.

 

마지막으로, 앞서 언급한 것 처럼 초기 Cluster Center가 잘못 잡히면 Local Minima에 빠질 수 있다.

 

 

왼쪽의 경우 초기 Cluster Center에 의하여 Local Minima에 빠져 Clustering이 이상적으로 수행되지 않음을 확인할 수 있다.  $d_1$이 $d_2$보다 가깝기 때문에 어떻게 보면 자연스러운 결과라고 생각이 될 수 있지만, 오른쪽 이상적인 Global Minimum의 결과를 보면 확실히 초기 Cluster Center에 영향을 받아 Clustering 결과가 잘못 되었음을 확인할 수 있다.

 

또한, Data의 분포(밀도)를 고려하지 않고, 모든 클러스터에서 같은 Parameter(Distnace Measurement, etc...)가 사용되기 때문에 부정확한 결과를 초래할 수 있다.