03. 군집화(1) - K 평균 알고리즘

군집화-Clustering

군집화는 주어진 데이터들을 비슷하거나 유사한 데이터끼리 그룹으로 묶는 비지도학습의 일종이다. 

K 평균 알고리즘 ( K-Means Algorithm )

 군집화의 방법 중 가장 일반적이고, 간편하며 빠른 알고리즘은 K-평균 알고리즘이다. k-평균 알고리즘은 주어진 데이터세트를 중심 K 개로 군집화하며, 이 K 값은 임의로 정해진다.    

(그림 : K 평균 알고리즘 군집화의 예시)

K 평균 알고리즘의 동작

 K 평균 알고리즘의 오차함수를 작성하려면, 너무 많이 복잡하고, 오랜 시간이 소요되기 때문에 이 군집화 방법에 있어선 휴리스틱한 접근 방법을 요구한다. 따라서, 중심의 초깃값을 어떻게 설정하느냐에 따라 결과에 영향을 미친다.

 먼저, 데이터를 n차원 좌표계에 나타낼 수 있도록 가공하고, 아래와 같은 방법을 통해 k개의 그룹으로 군집화한다.

1) 초기 중심의 좌표를 설정한다[각주:1] 2) 모든 데이터(벡터)에 대해 가장 가까운 중심을 구하여 k개의 그룹으로 군집화한다. 3) 다시 그룹의 좌표의 평균값을 계산하고 그것을 새로운 중심으로 설정한다 4) 새로운 중심과 이전 중심의 차이가 허용치보다 작을 때까지 2~3을 반복한다

K 평균 알고리즘의 특징과 한계

 휴리스틱하게 접근하는 이 알고리즘의 특성상, 계산이 복잡하지 않고 빠르게 결과를 도출해낼 수 있다는 것이 장점이다. 하지만, 초기 중심의 좌표에 따라 결과값이 영향을 받고, 지역 최소값에 빠지는 경우도 있으며 노이즈에 대응하는 것이 강건하지 않기 때문에 k-medoids 등의 알고리즘을 사용하는 경우도 많다(다음 포스팅에서 자세히 다룬다) 하지만, K 평균은 굉장히 계산이 간단하고( O(n)의 복잡도를 가진다 ) 볼록한 데이터 형태에 대해 굉장히 효율적인 군집화 방법이기 때문에 군집화를 배울 때 빠지지 않고 등장하는 기법 중 하나이다.^[각주:2]

1. 이 설정 방법에 대해서는 다음 포스팅에서 알아본다, 가장 대표적으로 랜덤하게 설정하는 방법이 있다. [본문으로]
2. 다만 반대로 생각하면 오목한 데이터 분포에서는 굉장히 좋지 않은 모습을 보인다. [본문으로]