k평균 클러스터링의 수행절차(과정)

 

 

 

k평균 클러스터링의 수행절차(과정)

 

단계	설명
1 Step   클러스터링의 수 k 값를 정의	·       초기 (군집의) 중심으로 k개의 객체를 임의로 선택합니다.
2 Step   각 측정값을 클러스터에 할당	·       각 자료를 가장 가까운 군집 중심에 할당합니다. ·       데이터가 분포된 공간상에 '클러스터 중심'으로 가정할 임의의 지점 k개를 선택합니다. 각 데이터는 근처에 있는 '클러스터 중심'에 할당됩니다.
3 Step   새로운 클러스터의 중심 계산	·       각 군집 내의 자료들의 평균을 계산하여 군집의 중심을 갱신(update)합니다. ·       각 '클러스터 중심'을 해당 클러스터에 속한 데이터들이 평균으로 조정합니다.
4 Step   클러스터 재분류	·       군집 중심의 변화가 거의 없을 때(또는 최대 반복수)까지 단계2와 단계3를 반복합니다. ·       더 이상 '클러스터의 중심'이 변하지 않을 때까지 2~3단계를 반복합니다.

 

위의 단계2는 자료들의 군집의 중심점(평균)으로부터의 오차제곱합이 최소가 되도록 각 자료를 할당하는 과정입니다.

 

 

 

 

k-평균군집에서 군집의 수(k)는 미리 정해 주어야 하며, k-개의 초기 중심값은 임의로 선택될 수 있으나, 자료값 중에서 무작위로 선택하는 것이 보다 편리합니다.

초기 중심점들은 서로 멀리 떨어져 있는 것이 바람직하며, 초기값에 따라 군집 결과가 크게 달라질 수 있습니다.

k-평균군집은 군집의 매 단계마다 군집 중심으로부터의 오차제곱합을 최소화하는 방향으로 군집을 형성해나가는(부분 최적화를 수행하는) 탐욕적(gredy) 알고리즘으로

간주될 수 있으며, 안정된 군집은 보장하나 전체적으로 최적이라는 것은 보장하지 못합니다.

 

 

 

Step 1: 클러스터링의 수 k를 정의

초기 k개 클러스터

 

 

 

초기 k개 클러스터의 가상의 중심점들을 지정 후 선택합니다.

초기 k "평균값" (위의 경우 k=3) 은 데이터 오브젝트 중에서 무작위로 뽑습니다. (색칠된 동그라미로 표시됨)

 

 

 

 

 

Step 2: 각 측정값을 클러스터에 할당

각 측정값을 가장 가까운 중심점의 클러스터에 할당합니다.

k 각 데이터 오브젝트들은 가장 가까이 있는 평균값을 기준으로 묶인다. 평균값을 기준으로 분할된 영역은 보로노이 다이어그램(Voronoi diagram) 으로 표시됩니다.

 

 

 

 

 

 

Step 3: 새로운 클러스터의 중심 계산

새로운 클러스터의 중심점을 다시 계산합니다.

k개의 클러스터의 중심점을 기준으로 평균값이 재조정됩니다.

 

 

 

 

 

 

 

Step 4: 클러스터 재분류

재정의 된 중심값 기준으로 다시 거리기반으로 클러스터링합니다.

수렴할 때 까지 2), 3) 과정을 반복하고 경계가 변경되지 않으면 종료합니다.