[ML] Clustering: K-Means ++

[#1]

■ Random Initialization Trap

Random Initialization Trap 은 랜덤 초기화 함정이라고 하며, k - means 알고리즘에서 초기 중심점 (Centroid)를 무작위로 선택할 때 발생할 수 있는 문제를 의미합니다.

임의로 중심점을 설정해서 발생하는 문제로 데이터들과 중심점이 너무 가깝게 설정되면 클러스터릴ㅇ이 균일하게 되기 힘들 수 있습니다.

■ K-Means ++

Random Initialization Trap 은 클러스터링 결과가 최적화 되지 않거나 클러스터링이 일관되지 않을 수 있습니다. 이 문제를 해결하기 위해서 K-Means ++ 이란 알고리즘을 사용합니다.

K-Means ++ 의 작동방법은 다음과 같습니다.

​ 

1. 데이터 중에서 1개를 중심점으로 선택합니다.

2. 임의로 선택한 데이터 (1번의 중심점)을 제외하고 나머지 데이터로부터 중심점까지의 거리를 계산합니다.

3. 중심점과 가장 먼 지점의 데이터를 다음 중심점으로 선택합니다.

4. 중심점이 K개가 될 때까지 반복합니다.

■ Optimal K - 최적의 K 판단.

 

참조: https://medium.com/@zalarushirajsinh07/the-elbow-method-finding-the-optimal-number-of-clusters-d297f... 

- Elbow Method

위 그림을 보면 X축은 K개의 갯수를 의미하고, Y축은 중심점까지의 평균 거리를 의미합니다.

1. K개 (Cluster 그룹)를 증가시키면서 평균 거리를 비교합니다.

2. 경사가 완만해지는 지점의 K를 특정합니다.

위에 그림을 보면 4지점부터 중심점 까지의 평균 거리가 급격히 줄어들고 있습니다.