k-means 알고리즘은 입력 매개변수 k를 생성하고 n개의 개체 그룹을 k개의 클러스터로 나누어 결과적으로 클러스터 내 유사성은 크지만 클러스터 간 유추는 낮습니다. 클러스터 유사도는 클러스터의 중심 또는 무게 중심으로 볼 수 있는 클러스터에 있는 개체의 평균값을 기준으로 계산됩니다.
k-means 알고리즘은 다음과 같이 진행됩니다. 첫째, 각 개체는 원래 클러스터 평균 또는 중심을 정의하는 k개의 개체를 무작위로 선택할 수 있습니다. 나머지 객체 각각에 대해 객체 간의 거리와 클러스터 평균에 따라 동일한 클러스터에 객체가 생성됩니다.
각 클러스터에 대한 새로운 평균을 계산할 수 있습니다. 이 단계는 원리 함수가 수렴할 때까지 반복됩니다. 일반적으로 제곱 오차 기준은 -
로 표시됩니다.$$\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 클러스터를 최대한 간결하고 독립적으로 생성하려고 합니다.
알고리즘: k-평균 − 모든 클러스터의 중심이 클러스터에 있는 객체의 평균값으로 정의되는 파티셔닝을 위한 k-means 알고리즘입니다.
입력 -
k: the number of clusters, D: a data set including n objects.
출력 -
A set of k clusters.
방법 -
-
D에서 원래 클러스터 중심으로 k개 개체를 임의로 선택합니다.
-
반복
-
(재) 각 개체를 개체가 동일한 클러스터에 할당합니다. 클러스터에 있는 개체의 평균 값에 따라 다릅니다.
-
클러스터 수단 업데이트, 즉 각 클러스터에 대한 개체의 평균 값을 계산합니다.
-
변경되지 않을 때까지
3개의 개체를 3개의 원래 클러스터 중심으로 임의로 선택하는 데 사용되며, 여기서 클러스터 중심은 "+"로 표시됩니다. 각 개체는 클러스터에 배포되는 것이 편리한 클러스터 센터에 따라 다릅니다.
다음으로 클러스터 센터가 업데이트됩니다. 각 클러스터의 평균 값은 클러스터의 일반적인 개체를 기반으로 다시 계산됩니다. 새로운 클러스터 중심을 활용하여 객체는 인접한 클러스터 중심에 따라 클러스터에 재분배됩니다. 이러한 재분배 구조는 점선으로 둘러싸인 새로운 실루엣입니다.
파티셔닝을 향상시키기 위해 클러스터에 객체를 반복적으로 재할당하는 단계는 반복 재배치로 정의됩니다. 클러스터에서 개체의 재배포가 나타나지 않으므로 프로세스가 제거됩니다. 결과 클러스터는 클러스터링 단계에서 복원됩니다.