이전 포스팅에서 K-Means 클러스터링의 개념이나 원리를 다뤘다.
K-Means 클러스터링 알고리즘은 소개된지 거의 반세기가 지났지만, 여전히 머신러닝에 가장 널리 사용되는 클러스터링 알고리즘 중 하나이다.
그러나 K-Means 알고리즘의 가장 큰 단점은 처음에 지정하는 중심점(centroid)의 위치를 무작위로 결정하기 때문에 최적의 클러스터로 묶어주는 데에는 한계가 있다는 것이다.
그래서 이번에는 K-Means의 새로운 버전이라고 할 수 있는 K-Means++ 알고리즘에 대해 살펴보려고 한다. K-Means++는 전통적인 K-Means의 문제, 즉 중심점 무작위 선정의 문제를 해결하기 위해 생겨난 거라고 보면 되겠다.
K-Means++ 클러스터링의 원리
전통적인 K-Means는 아래와 같은 원리로 진행된다.
-
일단 K개의 임의의 중심점(centroid)을 배치하고
-
각 데이터들을 가장 가까운 중심점으로 할당한다. (일종의 군집을 형성한다.)
-
군집으로 지정된 데이터들을 기반으로 해당 군집의 중심점을 업데이트한다.
-
2번, 3번 단계를 수렴이 될 때까지, 즉 더이상 중심점이 업데이트 되지 않을 때까지 반복한다.
그러나 K-Means++는 좀 다르다. K-Means에서 가장 첫번째 단계, 즉 중심점을 배치하는 걸 그냥 임의로 하는 대신 좀 더 신중하게(?) 하는 것이다.
-
(일단 아무 공간에나 중심점을 k개 찍고 시작하는게 아니라) 가지고 있는 데이터 포인트 중에서 무작위로 1개를 선택하여 그 녀석을 중심점으로 지정한다.
-
나머지 데이터 포인트들에 대해 그 첫번째 중심점까지의 거리를 계산한다.
-
두번째 중심점은 각 점들로부터 거리비례 확률에 따라 선택한다. 즉, 이미 지정된 중심점으로부터 최대한 먼 곳에 배치된 데이터 포인트를 그 다음 중심점으로 지정한다는 뜻이다.
-
중심점이 k개가 될 때까지 2,3번을 반복한다.
scikit-learn 사용법
파이썬 라이브러리 scikit-learn을 사용하면 K-Means++를 매우 쉽게 적용할 수 있다.
K-Means를 사용할 때와 똑같고, 그냥 모델을 불러올 때 init = 'k-means++만 넣어주면 되는거다.
from sklearn.cluster import KMeans
model = KMeans(n_cluster = k, init = 'k-means++)사실 기본값이 'k-means++'이라 따로 지정 안해주면 알아서 ++로 돌린다. 만약 전통적인 k-means로 중심점을 랜덤하게 지정하고 싶으면 init='random'을 써줘야 한다.
K-Means에 비해 가진 장점
-
초기 중심점을 더욱 전략적으로 배치하기 때문에 전통적인 K-Means보다 더 최적의 군집화를 할 수 있다.
-
K-Means보다 알고리즘이 수렴하는 속도가 빠르다. 전통적인 K-Means를 사용하면 초기 중심점이 (재수없게) 잘못 지정되는 경우 알고리즘이 수렴하는 데 시간이 오래 걸릴 수 있기 때문이다.
