K-means
K-means는 데이터를 K개의 클러스터로 분할하는 비지도 학습 알고리즘이다. 각 클러스터의 중심(centroid)과 데이터 포인트 간의 거리를 반복적으로 최소화한다.
- K개의 초기 중심점을 선택한다
- 각 데이터 포인트를 가장 가까운 중심점의 클러스터에 할당한다
- 각 클러스터의 중심점을 소속 포인트들의 평균으로 갱신한다
- 중심점이 더 이상 변하지 않거나 최대 반복 횟수에 도달할 때까지 2~3을 반복한다
import numpy as np
def kmeans(data, k, max_iter=20): # 초기 중심점 선택 centroids = data[np.random.choice(len(data), k, replace=False)]
for _ in range(max_iter): # 각 포인트를 가장 가까운 중심점에 할당 distances = np.linalg.norm(data[:, None] - centroids, axis=2) labels = distances.argmin(axis=1)
# 중심점 갱신 new_centroids = np.array( [ data[labels == i].mean(axis=0) if np.any(labels == i) else centroids[i] for i in range(k) ] )
if np.allclose(centroids, new_centroids): break centroids = new_centroids
return labels, centroids시간복잡도는 반복당 O(n·k·d)이다. n은 데이터 수, k는 클러스터 수, d는 차원 수이다.
초기화 문제
Section titled “초기화 문제”초기 중심점 선택에 따라 결과가 크게 달라진다. 운이 나쁘면 지역 최적해에 빠진다.
**K-means++**는 이 문제를 완화하는 초기화 방법이다. 첫 중심점은 랜덤으로, 이후 중심점은 기존 중심점과의 거리에 비례하는 확률로 선택한다. 멀리 있는 포인트가 다음 중심점이 될 확률이 높아져서, 초기 중심점이 데이터 전체에 골고루 퍼진다. scikit-learn의 KMeans는 기본값으로 K-means++를 쓴다.
적절한 K를 모르는 경우가 많다.
Elbow method: K를 1부터 늘려가며 각 K에 대한 SSE(Sum of Squared Errors, 각 포인트와 소속 중심점 간 거리 제곱의 합)를 그래프로 그린다. SSE가 급격히 꺾이는 지점(elbow)의 K를 선택한다.
Silhouette score: 각 포인트에 대해 “같은 클러스터 내 평균 거리”와 “가장 가까운 다른 클러스터까지의 평균 거리”를 비교한다. -1~1 범위이며, 1에 가까울수록 클러스터링이 잘 된 것이다.
활용 예시: 이미지 색상 분석
Section titled “활용 예시: 이미지 색상 분석”이미지의 지배적인 색상을 추출할 때 K-means를 쓸 수 있다. 각 픽셀의 RGB 값을 데이터 포인트로, K=2로 클러스터링하면 배경색과 전경색(텍스트 색)을 분리할 수 있다.
pixels = image.reshape(-1, 3) # (H*W, 3)labels, centroids = kmeans(pixels, k=2)
# 큰 클러스터 = 배경, 작은 클러스터 = 전경counts = np.bincount(labels)bg_color = centroids[counts.argmax()]fg_color = centroids[counts.argmin()]두 색상의 유클리드 거리가 너무 작으면(대비 부족) 흑백으로 폴백하는 식으로 처리한다.
- 클러스터가 구형(spherical)이 아니면 잘 안 맞는다. 길쭉하거나 비정형 분포에는 DBSCAN이나 GMM이 낫다.
- K를 미리 정해야 한다.
- 이상치에 민감하다. 하나의 극단값이 중심점을 크게 끌어당긴다.
- 고차원 데이터에서는 거리 의미가 희석된다(curse of dimensionality).
참고