# K-means++ 알고리즘 K-means++은 k-means clustering의 초기 중심점 선정(initialization)을 개선하기 위한 확률적(seeding) 방법이다. 초기 중심점을 더 균질하게 선택함으로써 최종 클러스터링 품질과 수렴 속도를 개선하는 것을 목표로 한다. 이 알고리즘은 초기화 단계에서 중심점들을 점진적으로 선택하고, 이후에는 표준 Lloyd의 알고리즘을 이용해 각 클러스터를 구성한다. ## 용어 정의 - X: 데이터 집합, X = {x1, x2, ..., xn} ⊆ R^d - k: 원하는 클러스터 수 - C: 현재까지 선택된 중심점의 집합, C = {c1, c2, ..., cm} (0 ≤ m ≤ k) - D(x): x에 대해 현재 선택된 중심점들 C로부터의 거리 중 최솟값의 제곱, 즉 D(x) = min_{c ∈ C} ||x - c||^2 - p(x): x를 다음 중심점으로 선택할 확률, p(x) = D(x) / ∑_{x' ∈ X} D(x') - Lloyd의 알고리즘: 중심점을 재계산하고 각 데이터 포인트를 가장 가까운 중심점에 할당하는 반복적 프로세스 수식 예시 - D(x) 정의: $D(x) = \min_{c \in C} \|x - c\|^2$ - 확률 정의: $p(x) = \dfrac{D(x)}{\sum_{x' \in X} D(x')}$ - 중심점 업데이트(클러스터 S_j에 속하는 점들의 평균): $c_j = \dfrac{1}{|S_j|} \sum_{x_i \in S_j} x_i$ - 목적 함수(손실): $J = \sum_{i=1}^n \|x_i - \text{assign}(x_i)\|^2$ > 주의: 위의 D는 squared Euclidean distance를 사용한다. 거리 metric으로 Euclidean 거리를 사용하는 것이 일반적이다. ## 알고리즘 개요 K-means++의 전체 흐름은 두 단계로 나뉜다. 첫 번째 단계는 확률적 초기화로, 두 번째 단계는 일반적인 Lloyd의 알고리즘으로 클러스터를 수렴시키는 것이다. 1) 첫 중심점 선택 - 데이터 X에서 임의로 한 점 xᶦ를 첫 중심점 c₁으로 선택한다. 2) 다음 중심점의 확률적 선택 - 각 데이터 포인트 x에 대해 D(x) = min_{c ∈ C} ||x - c||^2를 계산한다. - 다음 중심점 c를 선택할 때 각 x에 대해 확률 p(x) = D(x) / ∑_{x' ∈ X} D(x')를 사용하여 하나의 점을 새로운 중심점으로 추가한다. 3) 반복 - 필요 중심점의 수 k가 될 때까지 2)를 반복한다. 즉, C의 원소 수가 k가 될 때까지 각 단계에서 확률적으로 새로운 중심점을 추가한다. 4) Lloyd의 알고리즘으로 최적화 - 초기화가 완료되면, 선택된 중심점 C를 이용해 표준 Lloyd의 알고리즘을 수행한다. - 할당 단계: 각 포인트를 가장 가까운 중심점에 할당한다. - 업데이트 단계: 각 클러스터의 중심점을 해당 클러스터에 속한 포인트의 평균으로 갱신한다. - 수렴 조건이 만족될 때까지 할당-갱신을 반복한다. Pseudocode - 아래는 직관적 이해를 돕기 위한 간단한 의사코드이다. Algorithm KMeansPlusPlus(X, k) Input: X = {x1, ..., xn}, k Output: centers C = {c1, ..., ck} C ← { 임의의 점 xᵢ1 ∈ X } while |C| < k for each x ∈ X D(x) ← min_{c ∈ C} ||x - c||^2 end for Choose xᵢ ∈ X with probability p(xᵢ) = D(xᵢ) / ∑_{x ∈ X} D(x) C ← C ∪ {xᵢ} end while Run LloydsAlgorithm(X, C) return C - Lloyd의 알고리즘은 일반적인 K-means의 핵심 반복으로, 수렴 시까지 다음을 반복한다. - 할당: 각 x를 가장 가까운 중심점에 할당 - 업데이트: 각 중심점을 속한 클러스터의 산술평균으로 재설정 ## 특징 및 비교 - 초기화 품질: 무작위 초기화에 비해 K-means++는 더 균일하고 분리된 초기 중심점을 선택하므로 초기 수렴 시간과 최종 클러스터의 품질이 개선되는 경향이 있다. - 수렴 속도: 초기화가 더 낫기 때문에 Lloyd의 수렴 속도가 빨라질 수 있다. 다만 데이터 특성에 따라 다를 수 있다. - 재현성: 초기 중심점의 임의성에 의해 결과가 달라질 수 있다. 동일한 시드(seed)를 사용하면 재현 가능. - 거리/모드: 일반적으로 유클리드 거리(Euclidean distance)에서 잘 작동한다. 다른 거리 메트릭을 사용하면 확률 분포가 달라질 수 있다. ## 시간 및 공간 복잡도 - 초기화 비용 - 기본 naive 구현: 초기 시드 k를 선택할 때마다 D(x)를 계산하므로 대략 O(n k^2)의 시간 복잡도가 발생한다. 더 효율적인 구현으로 O(n k)까지 개선 가능하다. - Lloyd의 알고리즘 비용 - 각 반복에서의 할당은 O(n d)이고, 중심점 업데이트는 O(n d)이며, 일반적으로 t회의 반복으로 수렴한다. 따라서 총 시간은 O(t n d) 수준으로 평가된다. - 공간 복잡도 - 중심점 저장: O(k d) - 데이터 저장 및 거리 계산을 위한 중간 변수: O(n d) - 전반적으로 O(n d + k d)이며, 추가적인 최적화 없이도 충분히 관리 가능하다. - 참고로, 대규모 데이터 셋의 경우 초기화 단계의 비효율을 줄이기 위한 k-means++의 확장 기법(k-means|| 등)들이 제안되었다. ## 구현상의 주의점 - 거리 계산의 재사용 - 기존에 계산된 D(x) 값을 재사용하면 초기화 속도를 높일 수 있다. 다만 새로운 중심점이 추가될 때 D(x) 값을 재계산해야 한다는 점을 주의해야 한다. - 중심점의 중복 - 확률적 선택 과정에서 이미 선택된 점이 다시 선택되지 않도록 주의할 필요가 있다. - 데이터 스케일링 - 특징(Feature) 스케일링이 중요하다. 거리 기반 알고리즘이므로 각 차원의 스케일 차이가 결과에 큰 영향을 줄 수 있다. - 이상치 - 극단값(outlier)이 존재하면 초기화 및 이후 클러스터의 위치에 큰 영향을 미칠 수 있다. 필요 시 이상치 제거나 로버스트 방법을 고려한다. ## 변형 및 확장 - k-means++의 일반화 - 다른 거리 메트릭을 사용하는 경우에도 비슷한 확률적 초기화 아이디어를 적용할 수 있다. - 대규모 데이터용 확장 - k-means||와 같은 초기화 기법은 대규모 데이터에 대해 초기화 비용을 대폭 줄여준다. - 초기화 외의 개선 - 초기 중심점 수를 자동으로 결정하는 방법, 또는 실루엣(silhouette) 기반의 후처리 등으로 전체 클러스터링 품질을 향상시키는 연구가 있다. --- 관련 문서: [[K-means 알고리즘]], [[거리 측정 방법]], [[클러스터링 평가 지표]], [[초기화 방법]], [[Lloyd의 알고리즘]]