k-평균 클러스터링이란 무엇인가요?

앞서 언급한 바와 같이 많은 클러스터링 알고리즘은 수백만 개의 예시가 있는 머신러닝에 사용되는 데이터 세트로 확장되지 않습니다. 예를 들어 집계형 또는 분할형 계층적 클러스터링 알고리즘은 모든 점 쌍을 살펴보고 각각 $O(n^2 log(n))$ 및 $O(n^2)$의 복잡도를 갖습니다.

이 과정에서는 k-means에 중점을 둡니다. k-means는 $O(nk)$(여기서 $k$는 사용자가 선택한 클러스터 수)로 확장되기 때문입니다. 이 알고리즘은 각 점과 클러스터의 중심점 사이의 거리를 최소화하여 점을$k$ 클러스터로 그룹화합니다 (그림 1 참고).

따라서 k-평균은 데이터를 대략 원형인 여러 개의 분포로 구성된 것으로 효과적으로 처리하고 이러한 분포에 해당하는 클러스터를 찾으려고 시도합니다. 하지만 실제 데이터에는 외부값과 밀도 기반 클러스터가 포함되어 있으며 k-means의 기본 가정과 일치하지 않을 수 있습니다.

k-평균 클러스터링 알고리즘

알고리즘은 다음 단계를 따릅니다.

1. 나중에 수정할 수 있는 $k$의 초깃값을 제공합니다. 이 예에서는 $k = 3$를 선택합니다.

2. $k$ 중심을 무작위로 선택합니다.

   

   그림 1: 초기화 시 k-평균

3. 각 점을 가장 가까운 중심에 할당하여 $k$ 초기 클러스터를 가져옵니다.

   

   그림 2: 초기 클러스터.

4. 각 클러스터의 경우 클러스터에 있는 모든 지점의 평균 위치를 사용하여 새 중심을 계산합니다. 그림 4의 화살표는 중심점 위치의 변화를 보여줍니다.

   

   그림 3: 다시 계산된 중심점.

5. 각 점을 가장 가까운 새 중심에 다시 할당합니다.

   

   그림 4: 재할당 후 클러스터

6. 점이 더 이상 클러스터를 변경하지 않을 때까지 4단계와 5단계를 반복하여 중심점과 클러스터 멤버십을 다시 계산합니다. 대규모 데이터 세트의 경우 다른 기준에 따라 수렴하기 전에 알고리즘을 중지할 수 있습니다.

중앙점 위치는 처음에 무작위로 선택되므로 k-means는 연속 실행에서 상당히 다른 결과를 반환할 수 있습니다. 이 문제를 해결하려면 k-means를 여러 번 실행하고 품질 측정항목이 가장 우수한 결과를 선택합니다. 품질 측정항목은 이 과정의 뒷부분에서 설명합니다. 더 나은 초기 중심점 위치를 선택하려면 고급 버전의 k-means가 필요합니다.

수학에 대한 심층적인 이해는 필요하지 않지만 궁금한 분들을 위해 k-means는 기대 최대화 알고리즘의 특수 사례입니다. UPenn의 이 주제에 관한 강의 노트를 참고하세요.