K-평균 클러스터링이란?
K-평균 클러스터링(K-Means Clustering)은 데이터 마이닝에서 가장 널리 사용되는 분할 기반(partitioning) 군집화 알고리즘입니다. K-평균은 데이터셋에 있는 각 데이터를 새롭게 형성된 여러 클러스터 중 하나에만 배정하며, 레코드나 데이터 포인트는 거리(distance) 또는 유사도(similarity) 측정 기준을 바탕으로 가장 가까운 클러스터에 할당됩니다.
k-평균 알고리즘은 입력 매개변수 k를 받아 n개의 객체로 이루어진 집합을 k개의 클러스터로 나눕니다. 이때 목표는 클러스터 내부 유사도(intracluster similarity)는 최대화하고, 클러스터 간 유사도(intercluster similarity)는 최소화하는 것입니다. 클러스터 유사도는 클러스터에 속한 객체들의 평균값을 기준으로 계산되며, 이 평균값은 클러스터의 중심점(centroid), 즉 무게중심(center of gravity)으로 해석할 수 있습니다.
K-평균 클러스터링의 주요 단계
- K개의 초기 클러스터 중심 c1, c2, c3… ck를 선택합니다.
- 각 인스턴스 x를, 중심이 x와 가장 가까운 클러스터에 할당합니다.
- 각 클러스터에 대해, 해당 클러스터에 포함된 요소들을 기반으로 중심을 다시 계산합니다.
- 수렴이 완료될 때까지 위의 할당 단계로 되돌아가 반복합니다.
- 객체(데이터 포인트)를 최종적으로 K개의 클러스터로 분리합니다.
- 클러스터 중심(centroid)은 해당 클러스터 내 모든 데이터 포인트의 평균값으로 정의됩니다.
- 거리 함수를 사용하여 각 점을 중심이 가장 가까운 클러스터에 배정합니다.
초기값 설정과 종료 조건
평균값의 초기값은 임의로 지정할 수 있습니다. 무작위로 선택하거나, 입력 데이터 중 처음 k개 항목의 값을 그대로 사용하는 방식도 가능합니다. 수렴 판정 기준은 일반적으로 제곱 오차(squared error)를 사용하지만, 반드시 이것만 사용해야 하는 것은 아닙니다. 예를 들어, 특정 객체가 다른 클러스터로 재배정되는지 여부를 종료 조건으로 삼을 수도 있습니다. 또 다른 종료 기법으로는 단순히 고정된 반복 횟수만 확인하는 방법이 있으며, 수렴하지 않는 경우에도 프로세스가 확실히 끝나도록 최대 반복 횟수를 설정하기도 합니다.
K-평균 알고리즘
입력(Input) −
D = {t1, t2, …, tn} // 요소 집합
k // 원하는 클러스터의 개수출력(Output) −
K // 클러스터 집합
K-평균 알고리즘 의사 코드(Pseudo-code) −
assign initial values for means m1, m2, …, mk
repeat
assign each item ti to the cluster which has the closest mean
calculate the new mean for each cluster
until convergence criteria are met
반복적 재배치(R repetitive Relocation) 과정
먼저 세 개의 객체를 세 개의 초기 클러스터 중심으로 임의로 선택하며, 클러스터 중심은 보통 “+” 기호로 표시합니다. 각 객체는 자신과 가장 가까운 클러스터 중심을 기준으로 해당 클러스터에 배분됩니다.
다음 단계에서는 클러스터 중심이 업데이트됩니다. 각 클러스터의 평균값은 현재 그 클러스터에 속한 객체들을 기준으로 다시 계산됩니다. 새로운 클러스터 중심이 결정되면, 객체들은 다시 어느 중심점이 가장 가까운지에 따라 클러스터에 재배분됩니다. 이러한 재배분 결과는 점선 곡선으로 둘러싸인 새로운 클러스터 경계(실루엣)로 나타납니다.
이처럼 객체들을 클러스터에 반복적으로 재배치하면서 분할 품질을 점진적으로 개선하는 과정을 반복적 재배치(repetitive relocation)라고 합니다. 더 이상 어떤 클러스터에서도 객체의 재배분이 발생하지 않으면 프로세스가 종료되며, 최종적으로 생성된 클러스터들이 군집화 결과로 반환됩니다.