K-means 클러스터링의 전역탐색은 NP-hard 문제이다.
그러므로 EM(Expectation Maximization)과 Hill Climbing 기법을 사용하여 K-means 클러스터링의 지역최소값을 구해내는 것이 일반적이다.
Hill Climbing기법의 최대 약점은 Non-convex 공간에서 탐색 시작위치에 매우 민감하다는 점이다.
이를 해결하기 위한 방법으로는 크게 두 가지가 있는 것 같다.
첫째는 Climbing의 이동 폭이나 방향을 조정하는 것이다.
일부러 눈앞에 보이는 가장 좋은 길을 포기하고 다른 길을 찾아 모험을 떠나는 것이다. (Exploration)
예를 들어 SA(Stochastic Annealing)는 여기저기 방황하다가 점차 한 방향으로만 탐색하는 알고리즘이다.
이러한 방법의 최대 약점은 역시 얼마나 방황할지에 대한 일반식이 없다는 점이다.
여러 실험을 통해 문제별로 최적화된 인자를 찾아주어야 한다.
둘째는 Random Walk이다.
이 방법은 초기 시작점을 무작위로 배정하여 알고리즘을 여러번 수행하고, 그 중 가장 좋은 값을 선택하는 것이다.
좋은 점은 별도의 인자가 필요없다는 점이지만, Optima에 얼마나 빠르게 수렴하는지가 관건이다.
이 두 가지 방법은 단독으로 사용되기도 하고 혼용되기도 한다.
예를 들어 극단적인 SA나 GA(Genetic Algorithm)의 경우 초기 수행은 Random Walk와 다를 것이 없으나 점차 Random Walk가 줄어들며 Climbing의 효과가 커진다.
서론이 길었다.
Lloyd K-means가 무작위로 시작점을 설정하는 것과 달리, K-means++ 알고리즘은 시작점을 휴리스틱하게 설정한다.
그 결과, 기존 알고리즘보다 훨씬 빠르게 지역최적해로 수렴하게 된다.
다른 연구들에서도 보이듯이 K-means의 가장 큰 약점이 초반에 center를 잘 못잡는다는 점인데, K-means++는 시작점을 잘 설정해줌으로써 그러한 약점을 극복했다.
알고리즘 자체는 단순하다.
초기 중심을 선정할 때, 중심으로 선택되지 않은 모든 점들 가운데서 랜덤하게 중심을 선택하되
가장 가까운 중심과의 거리의 제곱을 바탕으로 한 편중 확률분포를 사용한다.
어렵게 말한 기분이지만, 식으로보면 단순하다.
각 샘플별로 아래의 확률을 부여하고, 새 중심값을 무작위로 선출한다.
식은 k-means++ 논문에서 가져왔다.
물론 새로 중심을 뽑을 때마다 모든 샘플들에 대한 선출 확률을 재계산해야한다는 단점은 있다.
아래는 numpy에 내장된 weighted random 모듈을 이용한 초기값 선정 예시 코드이다.
# First Choice
seed = np.append(seed, np.random.choice(node, 1))
# Later Choice
for i in range(k-1):
dist_vector = np.array([np.min([dist[node_index][center_index] for center_index in seed]) for node_index in node]) ** 2
weighted_probability = (dist_vector / np.sum(dist_vector))
while True:
chosen_value = np.random.choice(node, 1, weighted_probability.tolist())
if len(np.where(seed == chosen_value)[0]) == 0:
break
seed = np.append(seed, chosen_value)
나는 K-means++의 초기값 설정의 가장 큰 특징은 휴리스틱 그 자체도 있지만, Random Walk를 차용했다는 점이라고 생각한다.
이를 통해 어느 정도 지역최적해에 빠지는 문제를 해결할 수 있지 않을까 생각했었다.
그러나 간단한 실험 결과, K-means++의 Random Walk는 매우 약하다는 것을 확인했다.
10k번의 반복 수행에도 불구하고 동일한 에너지값에 수렴하였다.
K-means는 초기값만 잘 설정하면 지역최적해로 매우 빠르게 수렴한다.
이 정설을 실험을 해보고서야 깨닫게 됐다.
머리가 나쁘면 몸이 고생이다.