K-평균 알고리즘이란?
K-평균(k-means) 알고리즘은 입력 매개변수 k를 받아 n개의 객체를 k개의 클러스터로 분할하는 대표적인 군집화 기법입니다. 이때 클러스터 내부의 유사도(intracluster similarity)는 최대한 높아지고, 서로 다른 클러스터 간의 유사도(intercluster similarity)는 최대한 낮아지도록 분할합니다.
클러스터 유사도는 해당 클러스터에 속한 객체들의 평균값을 기준으로 계산됩니다. 이 평균값은 클러스터의 중심(centroid) 또는 무게중심(center of gravity)으로 해석할 수 있습니다.
K-평균 알고리즘의 진행 과정
알고리즘은 다음 순서로 진행됩니다. 먼저 전체 객체 중에서 임의로 k개를 선택하며, 선택된 각 객체가 하나의 클러스터 평균(중심)을 정의합니다. 이후 남은 객체들은 객체와 클러스터 평균 사이의 거리를 기준으로 가장 가까운 클러스터에 배정됩니다.
그다음 각 클러스터의 새로운 평균을 계산하고, 이 과정을 목적 함수가 수렴할 때까지 반복합니다. 일반적으로 제곱 오차(squared-error) 기준이 사용되며, 다음과 같이 표현됩니다.
$$\mathrm{E=\displaystyle\sum\limits_{i=1}^k\displaystyle\sum\limits_{p\epsilon C_{i}}|p-m_{i}|^2}$$
여기서 E는 데이터셋에 포함된 모든 객체에 대한 제곱 오차의 총합입니다. p는 주어진 객체를 나타내는 공간상의 점이며, mi는 클러스터 Ci의 평균입니다(p와 mi는 모두 다차원 값입니다). 즉, 각 클러스터에 속한 모든 객체에 대해 객체와 클러스터 중심 사이의 거리를 제곱한 뒤 이를 합산합니다. 이 기준은 결과적으로 만들어지는 k개의 클러스터가 최대한 조밀(compact)하고 서로 독립적(independent)이 되도록 만드는 역할을 합니다.
알고리즘: K-평균
k-means — 각 클러스터의 중심을 클러스터 내 객체들의 평균값으로 정의하는 분할(partitioning) 알고리즘입니다.
입력(Input):
k: 클러스터의 개수,
D: n개의 객체를 포함하는 데이터셋
출력(Output):
k개의 클러스터 집합
방법(Method):
D에서 임의로 k개의 객체를 선택하여 초기 클러스터 중심으로 지정합니다.
반복(repeat):
클러스터 내 객체들의 평균값을 기준으로, 각 객체를 가장 유사한 클러스터에 (재)배정합니다.
클러스터 평균을 갱신합니다. 즉, 각 클러스터에 속한 객체들의 평균값을 다시 계산합니다.
더 이상 변화가 없을 때까지(until no change) 반복합니다.
반복적 재배치(Iterative Relocation) 과정
예를 들어 세 개의 객체를 임의로 선택하여 세 개의 초기 클러스터 중심으로 삼을 수 있으며, 클러스터 중심은 “+” 기호로 표시됩니다. 각 객체는 자신에게 가장 적합한 클러스터 중심을 기준으로 해당 클러스터에 배정됩니다.
다음으로 클러스터 중심이 갱신됩니다. 각 클러스터의 평균값은 현재 클러스터에 속한 객체들을 바탕으로 다시 계산되며, 새로운 클러스터 중심을 이용해 객체들이 가장 인접한 클러스터 중심을 기준으로 재배분됩니다. 이러한 재배분 과정은 점선 곡선으로 표시된 새로운 실루엣(new silhouettes)을 형성합니다.
이처럼 객체들을 클러스터에 반복적으로 재배정하여 분할 품질을 점진적으로 향상시키는 과정을 반복적 재배치(iterative relocation)라고 합니다. 어떤 클러스터에서도 객체의 재배분이 더 이상 발생하지 않으면 프로세스가 종료되며, 최종적으로 얻어진 클러스터들이 군집화 단계의 결과물로 반환됩니다.