K-평균 알고리즘

K-평균 알고리즘(K-means algorithm)은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다.

이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다.

역사

"K-평균"에 대한 개념은 1957년 Hugo Steinhaus에 의해 소개되었으나, 용어 자체는 1967년에 James MacQueen에 의해 처음 사용되었다. 현재 사용되고 있는 표준 알고리즘은 1957년에 Stuart Lloyd가 펄스 부호 변조(PCM)를 목적으로 처음으로 고안 하였으나 1982년이 되어서야 컴퓨터 과학 매거진에 처음 공개되었다. 알고리즘이 공개되기 이전인 1965년에 E. W. Forgy 또한 같은 알고리즘을 제안하였다. 차후 1975년과 1979년에 Hartigan과 Wong에 의해 거리 계산이 필요하지 않은 좀 더 효율적인 방법이 소개 되었다.

알고리즘

표준 알고리즘

$i$번째 클러스터의 중심을 $\mu _{i}$, 클러스터에 속하는 점의 집합을 $S_{i}$라고 할 때, 전체 분산은 다음과 같이 계산된다.

$V=\sum _{i=1}^{k}\sum _{j\in S_{i}}|x_{j}-\mu _{i}|^{2}$

이 값을 최소화하는 $S_{i}$을 찾는 것이 알고리즘의 목표가 된다.

알고리즘은 우선 초기의 $\mu _{i}$를 설정하는 것으로 시작한다. 이후 다음의 두 단계를 반복한다.

• 클러스터 설정: 각 데이터로부터 각 클러스터들의 $\mu _{i}$까지의 유클리드 거리를 계산하여, 해당 데이터에서 가장 가까운 클러스터를 찾아 데이터를 배당한다.

$S_{i}^{(t)}=\{x_{p}:|x_{p}-\mu _{i}^{(t)}|^{2}\leq |x_{p}-\mu _{j}^{(t)}|^{2}\forall j,1\leq j\leq k\}$

• 클러스터 중심 재조정: $\mu _{i}$를 각 클러스터에 있는 데이터들의 무게중심 값으로 재설정해준다.

$\mu _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum \limits _{x_{j}\in S_{i}^{(t)}}x_{j}$

만약 클러스터가 변하지 않는다면 반복을 중지한다.

맨 처음, 각 점들을 $k$개 집합으로 나눈다. 이때 임의로 나누거나, 어떤 휴리스틱 기법을 사용할 수도 있다. 그 다음 각 집합의 무게 중심을 구한다. 그 다음, 각각의 점들을 방금 구한 무게중심 가운데 제일 가까운 것에 연결지음으로써 새로이 집합을 나눌 수 있다. 이 작업을 반복하면 점들이 소속된 집합을 바꾸지 않거나, 무게중심이 변하지 않는 상태로 수렴될 수 있다.

초기화 기법

무작위 분할 (Random Partition)

무작위 분할 알고리즘은 가장 많이 쓰이는 초기화 기법으로, 각 데이터들을 임의의 클러스터에 배당한 후, 각 클러스터에 배당된 점들의 평균 값을 초기 $\mu _{i}$로 설정한다. 무작위 분할 기법의 경우 다른 기법들과는 달리 데이터 순서에 대해 독립적이다. 무작위 분할의 경우 초기 클러스터가 각 데이터들에 대해 고르게 분포되기 때문에 각 초기 클러스터의 무게중심들이 데이터 집합의 중심에 가깝게 위치하는 경향을 띈다. 이러한 특성 때문에 K-조화 평균이나 퍼지 K-평균에서는 무작위 분할이 선호된다.

Forgy

Forgy 알고리즘은 1965년 Forgy에 의해 고안되었으며 현재 주로 쓰이는 초기화 기법 중 하나로, 데이터 집합으로부터 임의의 $k$개의 데이터를 선택하여 각 클러스터의 초기 $\mu _{i}$로 설정한다. 무작위 분할 기법과 마찬가지로 Forgy 알고리즘은 데이터 순서에 대해 독립적이다. Forgy 알고리즘의 경우 초기 클러스터가 임의의 $k$개의 점들에 의해 설정되기 때문에 각 클러스터의 무게중심이 중심으로부터 퍼져있는 경향을 띈다. 이러한 특성 때문에 EM 알고리즘이나 표준 K-평균 알고리즘에서는 Forgy 알고리즘이 선호된다.

MacQueen

1967년 MacQueen에 의해 고안된 MacQueen 알고리즘은 Forgy 알고리즘과 마찬가지로 데이터 집합으로 부터 임의의 $k$개의 데이터를 선택하여 각 클러스터의 초기 $\mu _{i}$로 설정한다. 이후 선택되지 않은 각 데이터들에 대해, 해당 점으로부터 가장 가까운 클러스터를 찾아 데이터를 배당한다. 모든 데이터들이 클러스터에 배당되고 나면 각 클러스터의 무게중심을 다시 계산하여 초기 $\mu _{i}$로 다시 설정한다. MacQueen 알고리즘의 경우 최종 수렴에 가까운 클러스터를 찾는 것은 비교적 빠르나, 최종 수렴에 해당하는 클러스터를 찾는 것은 매우 느리다.

Kaufman

1990년에 Kaufman과 Rousseeuw에 의해 고안된 Kaufman 알고리즘은 전체 데이터 집합 중 가장 중심에 위치한 데이터를 첫번째 $\mu _{i}$로 설정한다. 이후 선택되지 않은 각 데이터들에 대해, 가장 가까운 무게중심 보다 선택되지 않은 데이터 집합에 더 근접하게 위치한 데이터를 또 다른 $\mu _{i}$로 설정하는 것을 총 $k$개의 $\mu _{i}$가 설정될 때 까지 반복한다. 무작위 분할과 마찬가지로, Kaufman 알고리즘은 초기 클러스터링과 데이터 순서에 대해 비교적 독립적이기 때문에 해당 요소들에 의존적인 다른 알고리즘들 보다 월등한 성능을 보인다.

복잡도

K-평균 알고리즘의 계산 복잡도에 크게 영향을 미치는 요소 두가지는 유클리드 공간 $d$와 클러스터의 수 $k$이다. 클러스터의 수가 작더라도, 일반적인 유클리드 공간 $d$에서 K-평균 알고리즘의 최적 해를 찾는 것은 NP-난해이다. 반대로 낮은 차원의 유클리드 공간일지라도, $k$개의 클러스터에 대해 최적 해를 찾는 것 또한 NP-난해이다.

이러한 이유로 K-평균 알고리즘에서는 위와 같은 휴리스틱 기법을 주로 사용한다. Lloyd 알고리즘의 경우, 시간 복잡도는 클러스터의 수, 데이터 벡터의 차원, 데이터 벡터의 수에 각각 비례한다. 또한 알고리즘이 해가 수렴하기까지 반복되므로, 알고리즘이 반복된 횟수에도 비례한다. 즉, $n$개의 $d$-차원 데이터 벡터들을 $i$번의 반복을 통해 $k$개의 클러스터로 묶는데 걸리는 시간은 $O(nkdi)$이다. K-평균 알고리즘은 많은 환경에서 빠르게 수렴하기 때문에 (보통은 처음 주어진 데이터의 개수보다 훨씬 적은 반복만 필요하다) 널리 사용된다.

• Smoothed analysis 경우의 복잡도는 다항 시간이다. $[0,1]^{d}$내의 임의의 $n$개의 점들의 집합에 대해, 집합 내의 각 점들이 평균$0$, 분산$\sigma ^{2}$의 정규분포를 이룬다면, 해당 집합을 $k$개의 클러스터로 묶는데 걸리는 시간이 $O(n^{34}k^{34}d^{8}log^{4}(n)/\sigma ^{2})$임이 증명된 바 있다.
• 다항을 넘는(superpolynomial) 시간($2^{\Omega ({\sqrt {n}})}$)이 걸리는 경우도 존재한다.
• 공간 복잡도의 경우, 알고리즘은 각 클러스터의 무게중심 벡터들에 대한 정보를 추가로 저장해야 하고, 이 무게중심 벡터들은 매 반복마다 독립적이기 때문에, K-평균 알고리즘은 $O((n+k)d)$의 공간 복잡도를 가진다.

한계점

이 알고리즘은 전역 최적값을 보장해 주지 않는다. 맨 처음 나눈 방법에 상당히 의존한 결과가 나오므로 초기 클러스터 설정에 따라서는 실제 최적값보다 꽤 나쁜 값을 얻을 수도 있다. 이를 방지하기 위해서는, 서로 다른 초기값으로 여러 번 시도하여 가장 좋은 결과를 사용하는 기법 등을 사용할 수 있다.

또한, 이 알고리즘은 구하려는 클러스터의 갯수를 미리 정해 두어야 한다. 클러스터 갯수를 너무 많이 설정하면 큰 클러스터가 여러 개로 나뉘는 결과를 얻을 수도 있다.

바깥 고리

• Numerical Example of K means clustering
• Application example which uses K means clustering to reduce the number of colors in images
• K-means Java code
• K-means C++ STL code
• K-means Python library

참고 문헌

• D. Arthur, S. Vassilvitskii (2006): "How Slow is the k-means Method?," Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
• H.-H. Bock (2007) : " Clutering Methods: A History of k-Means Algorithms", Proceedings of Selected Contributions in Data Analysis and Classification, 2:161-172