K-Means Clustering

K-means 클러스터링은 데이터를 k개 그룹으로 분할하는 비지도 학습 알고리즘입니다. 각 그룹은 해당 그룹에 할당된 점들의 평균인 중심점으로 표현됩니다. K-means는 클러스터 내 제곱 거리 합이라는 관성(inertia)을 최소화하는 분할을 찾으므로, 클러스터 안의 점들은 중심점에 가깝게 모입니다. 표준 절차는 Lloyd 알고리즘입니다. Stuart Lloyd는 신호 양자화를 위해 1957년 Bell Labs에서 이 알고리즘을 개발했으며, "k-means"라는 이름은 James MacQueen의 1967년 논문에서 유래했습니다. 간단하고 빠르며 수백만 개의 점으로 확장할 수 있으므로, k-means는 데이터 마이닝, 압축 및 레이블이 없는 데이터의 구조 탐색에 기본 도구로 사용됩니다.

알고리즘 작동 방식#

초기 중심점을 선택한 뒤, Lloyd 알고리즘은 클러스터가 더 이상 바뀌지 않을 때까지 할당 단계와 업데이트 단계를 번갈아 수행합니다:

1. 초기화: 시작 중심점 k개를 선택합니다. Scikit-learn의 기본 방식인 k-means++는 첫 번째 중심점을 무작위로 선택하고, 이후 중심점은 이미 선택한 가장 가까운 중심점까지의 제곱 거리에 비례하는 확률로 선택하여 초기 중심점이 서로 멀리 떨어지도록 합니다.
2. 할당: 일반적으로 유클리드 거리를 기준으로 모든 점을 가장 가까운 중심점에 할당합니다.
3. 업데이트: 각 중심점을 현재 해당 중심점에 할당된 점들의 평균으로 이동합니다.
4. 반복: 점이 클러스터를 변경하지 않거나 중심점의 이동량이 허용 오차보다 작아질 때까지 할당 단계를 반복합니다.

두 단계 모두 관성을 높일 수 없으므로 루프는 항상 수렴하지만, 초기 중심점에 따라 달라지는 국소 최솟값에만 도달합니다. 전역 최적해를 찾는 문제는 NP-hard이므로 구현에서는 여러 초기화를 실행하고 관성이 가장 낮은 결과를 선택합니다. scikit-learn의 KMeans에서는 k-means++로 초기화할 때 기본 n_init="auto"이 한 번 실행되고, 무작위 초기화를 사용하면 10번 실행됩니다.

클러스터 수 선택#

K-means에서는 k를 미리 지정해야 합니다. 중심점이 많아질수록 점에 더 가까워지므로 k가 커지면 관성은 항상 감소합니다. 따라서 엘보 방법에서는 k에 따른 관성을 그래프로 표시하고 감소 폭이 완만해지는 지점을 찾습니다. 실루엣 점수는 각 점에서 해당 클러스터까지의 평균 거리와 가장 가까운 다른 클러스터까지의 평균 거리를 비교하며, -1부터 1까지의 값을 가집니다. 값이 높을수록 클러스터가 조밀하고 서로 잘 분리되어 있습니다. 다음 예시에서는 네 중심점 주변에서 생성된 데이터의 k를 2부터 6까지 평가합니다:

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

관성은 k=2일 때 18,363, k=3일 때 5,241, k=4일 때 1,127로 감소한 뒤 k=5일 때 1,039, k=6일 때 922로만 감소하므로 엘보 지점은 k=4입니다. 실루엣 점수도 이에 부합합니다. k=4일 때 0.811로 정점에 도달한 뒤 k=5일 때 0.687로 떨어져, 데이터 생성에 사용된 네 중심점을 찾아냅니다.

가정 및 변형 알고리즘#

K-means는 클러스터가 대략 구형이고 크기가 비슷하며 유클리드 공간에서 서로 분리된 경우 가장 잘 작동합니다. 더 큰 스케일의 특징이 거리를 좌우하므로, 데이터는 보통 먼저 표준화합니다. 모든 점은 어떤 클러스터엔가 할당되며, 일부 극단적인 이상치는 중심점을 해당 그룹에서 멀어지게 할 수 있습니다. 다음과 같은 여러 변형 알고리즘은 이러한 제약을 완화합니다:

• 미니배치 k-means: 작은 무작위 배치로 중심점을 업데이트하며, 대규모 데이터셋의 학습 속도를 크게 높이는 대신 정확도가 조금 낮아집니다.
• K-medoids: 실제 데이터 점을 클러스터 중심으로 사용하므로 이상치에 더 강하며 어떤 거리 측정 방법과도 함께 사용할 수 있습니다.
• 퍼지 c-means: 단일한 확정 할당 대신 퍼지 논리 개념에 따라 각 점이 모든 클러스터에 속하는 정도를 부여합니다.
• 가우시안 혼합 모델: 클러스터마다 확률 분포를 적합해 크기가 서로 다른 타원형 클러스터를 허용하고, 소프트 확률 할당 결과를 반환합니다.

AI 및 컴퓨터 비전 분야의 활용#

• 색상 양자화: 이미지의 픽셀 색상을 클러스터링하고 각 픽셀을 해당 클러스터의 중심점으로 대체하면, 수천 가지 색상이 있는 사진을 k개 색상의 팔레트로 줄일 수 있습니다. 이렇게 하면 이미지를 압축할 수 있을 뿐 아니라 빠르고 대략적인 이미지 분할도 수행할 수 있습니다.
• 코드북과 벡터 양자화: 중심점은 코드북을 구성하며, 각 벡터는 가장 가까운 중심점의 인덱스로 저장됩니다. 고전적인 bag-of-visual-words 이미지 검색에서는 로컬 이미지 디스크립터를 사용해 이런 방식으로 어휘를 구축했습니다.
• 앵커 박스 설계: YOLOv2는 학습 박스의 너비와 높이에 k-means를 적용하고, 거리로 1에서 IoU를 뺀 값을 사용해 앵커 박스를 선택했습니다.
• 가중치 팔레트화: quantize=8을 사용해 YOLO26을 Core ML로 내보내면, 각 대형 가중치 텐서의 값을 k-means로 클러스터링해 중심점 256개로 줄입니다. 따라서 내보낸 모델은 가중치마다 8비트 인덱스와 작은 조회 테이블을 저장합니다.
• 고객 세분화: 소매업체는 구매 빈도, 장바구니 크기, 최근 구매 시점을 기준으로 고객을 그룹화하여 각 세그먼트에 맞는 혜택을 제공합니다.

K-Means와 관련 알고리즘 비교#

• K-최근접 이웃(KNN): 공통으로 쓰이는 "k" 때문에 혼동이 생깁니다. KNN은 레이블이 지정된 가장 가까운 k개 사례를 바탕으로 새 포인트에 레이블을 지정하는 지도 학습 알고리즘인 반면, k-means는 비지도 학습 알고리즘이며 k는 생성할 클러스터의 수입니다.
• DBSCAN: 포인트를 밀도에 따라 그룹화하고 클러스터 수를 자체적으로 찾아내며, 어떤 형태의 클러스터든 처리하고, 밀도가 낮은 포인트는 억지로 클러스터에 넣는 대신 노이즈로 분류합니다.
• 계층적 클러스터링: 가장 가까운 그룹을 반복적으로 병합해 중첩된 클러스터의 트리를 구성합니다. 따라서 트리를 원하는 수준에서 잘라 k를 나중에 선택할 수 있지만, 포인트 수에 따라 비용이 최소 제곱 수준으로 증가합니다.