Clustering using Centroid-based approach. What is k-Means Algorithm

Centroid-based Approach는 k-Means 알고리즘을 사용한다. 이 접근 방식은 기존의 Hierachical한 방식이 Time과 Space가 너무 많이 소요된다는 점에 착안하여 등장한다. 좀 더 효율적인 알고리즘을 사용한 Clustering 방식이 필요하다.

 

k-Means의 장점은 이해하고 구현하기 쉽다는 것이지만 오직 local minimun만이 얻어진다는 것이 단점이다. 또한 초기화하기 힘들고 outlier에 민감하다는 것이다.

 

k-Means 알고리즘의 아이디어에 대해 알아보자. 각각의 데이터들이 각각의 Cluster로 독립적으로 할당시킨다. Dissimilariy 방식으로 거리 측정 방식을 정의하고, within cluster의 표준편차를 최소화할 수 있는 Cluster로 결정된다.

 

k-Means 알고리즘의 절차를 보자. 처음에 Cluster의 개수를 k개로 설정하고 시작한다. 각각의 Point를 하나의 Cluster로 초기화한다. 각각의 Data point에 대해서 cluster의 중심과 가장 가까운 주변 Data 들을 결정하게 된다. 이후 다시 Cluster의 중심을 계산한다. 해당 방식을 Centroid가 수렴할 때까지 반복적으로 수행한다.

 

Optimization Problem으로 Sum of squared Error가 존재한다. 각각의 Data point과 Cluster의 Centroid 간의 차이를 제곱하여 더한 것의 최솟값을 계산하게 된다. 이를 SSE라고 부른다. 최솟값을 갖는 S가 정해졌을 때, centroid의 편차를 0으로 두어 다음 Centroid의 지점을 최신화시킨다.

 

 

k-Means 알고리즘에는 어떤 문제점이 있을까? Distance Metric 문제가 발생한다. Metric이 정의되지 않았을 때와 Cluster가 non-convex한 경우 Distance를 구하는 것이 적합하지 않을 수 있다는 점이다.

 

Data Normalization 개념이 등장한다. Euclidean 거리를 측정했을 때 절대적 차이가 더 큰 Data instance에 대해서 더 큰 오차의 값을 넣게 되면 Cluster하는데 있어서 상대적으로 계산이 안되는 문제가 발생한다.

 

그렇기 때문에 각각의 Data 속성들을 비교 가능하도록 Mean-Std Normalization을 시킨다. Min-max scaling이라고 불리기도 한다.

 

그렇다면 k의 값을 어떻게 설정하는가? K에 따라 결과를 도출해야 어느 K가 더 적합한지를 알 수 있다. Elbow Method를 사용하는데 이는 계산할 수 있는 범위의 k를 모두 계산하는 것이다. 그 중에 within variance가 가장 작은 값이 나오게 하는 k를 사용하는 방식이다.

 

K의 값을 1부터 올려서 SSE가 줄어드는 양상을 확인한다. 이때 주의할 것은 Elbow Method는 SSE의 최소점을 찾는 것이 아니다. 정체가 시작되는 구간을 찾는다고 생각하면 된다.

 

k-Means 알고리즘의 ISSUE로 outlier에 민감하다고 했다. 이에 대안책으로는 Sotf assignment 방식이 있다. Mixture of Gaussian의 방식으로 클러스터를 가질 확률에 대한 접근을 하는 것이다. 그리고 k-means가 아닌 k-medoids 방식으로 Cluster의 평균이 아닌 Median을 사용하는 것이다.

 

다음으로 어떻게 Clusterdml centroid를 초기화할 것인가? Random하게 하는 방식, Heuristic하게 하는 방식이 존재한다. k-Mean++ 방식도 있는데 이는 Initial Point로부터 하나하나 지점을 잡는 것이다.

 

그렇다면 어떤 Clutser가 좋은 Cluster인가? Intra-cluster의 Similarity가 높을 때, 즉 군집 내의 유사도가 높고 군집 간의 유사도가 낮을 때이다. (Inter-cluster similarity is low)

 

Internal Criterion 예시로 Silhouette coefficient 가 있다. SSE대신 Silhouette를 사용하는 경우도 있음을 알고있자.

 

External Criterion의 경우 Clustering의 결과물을 이미 결정된 답안과 비교를 하여 성능을 측정하는 것이다. 이는 Labeled Data가 필요하다.