Clustering - K-Means

군집화는 대표적인 비지도학습 주제의 하나로 데이터 $x$에 대한 출력 $y$를 예측하는 지도학습과는 달리 $x$ 자체가 비슷한 것끼리 묶어주는 알고리즘입니다. 비지도학습이니 당연히 $x$에 대한 라벨 $y$가 필요하지 않고 비슷한 특성을 가진 데이터끼리 그룹 (군집)을 구성하는 것으로 간단하게는 문서, 음악, 영화를 여러 주제의 그룹으로 모으는 경우나 스팸 이메일을 판단하는 데이도 사용되는 중요한 분야입니다. 이번 포스트에서는 군집화의 대표적인 알고리즘, K-Means를 살펴보도록 하겠습니다.

K-Means

K-Means 는 군집의 개수 $k$를 설정하고 각 군집에 할당된 데이터 샘플의 평균 중심으로 군집 중심을 이동하는 방법입니다. K-Means는 다음과 같이 4단계로 요약할 수 있습니다.

1) 데이터에서 랜덤하게 $k$개의 센트로이드를 초기 군집 중심으로 설정합니다. 
2) 각 샘플은 가장 가까운 군집 중심 $\mu^k$ 에 할당됩니다. 즉, 해당 샘플에서 가장 가까운 군집 중심이 1번 군집이라면 그 샘플의 군집은 1번이 되는 것이죠.
3) 모든 샘플에 대해 군집 할당이 완료되면 각 군집 별 평균으로 중심점을 이동합니다.
4) 군집 중심이 지정한 임계치보다 적게 변화되거나 최대 반복 횟수에 도달할 때까지 2,3번 과정을 반복합니다.

군집 중심과 샘플의 거리는 두 포인트의 Euclidean distance로 계산합니다. 특히 각 군집 별 Sum of Squares 를 inertia 라고 하며 K-Means는 inertia를 최소화하는 군집 중심을 찾는 알고리즘으로 생각할 수 있습니다.

Inertia

Examples

먼저 sklearn.datasets의 make_blobs 함수를 이용하여 군집화를 위한 가상 데이터를 생성해 보겠습니다. make_blobs 파라미터는 다음과 같고 [n_samples, n_feature] 의 배열 $X$와 군집 번호를 담고 있는 [n_samples] 의 배열 $y$를 생성합니다.

Parameters	Description
n_samples	표본 데이터의 수로 디폴트는 100
n_features	데이터의 feature 개수로 디폴트는 20
centers	생성할 군집의 수
cluster_std	군집의 표준 편차

from sklearn.datasets import make_blobs

import matplotlib.pyplot as plt

X, y = make_blobs(n_samples=150, n_features=2, centers=3, cluster_std=0.5)

plt.figure()
plt.scatter(X[:,0], X[:,1], c='black', marker='o')
plt.show()

sklearn.cluster 모듈의 KMeans 함수를 이용해 K-Means를 수행합니다. 파라미터는 다음과 같습니다. 

Parameters	Description
n_clusters	생성할 군집의 개수
init	{'k-means++', 'random'} 중 하나를 선택합니다. 군집 중심을 초기화할때 랜덤으로 설정하거나  추후 설명할 K-Means++ 로 설정합니다.
n_init	K-Means를 실행하는 횟수입니다. 디폴트는 10으로 설정되며 inertia 관점에서 가장 좋은 결과를 출력합니다.
max_iter	K-Means 알고리즘의 반복 횟수로 디폴트는 300입니다.
tol	직전 군집 중심과 현 군집 중심의 차이가 이 값보다 작아지면 수렴했다고 생각하고 알고리즘을 종료합니다.

KMeans 객체를 선언한 후 fit_predict(입력) 함수를 수행하면 각 데이터 샘플 별로 할당된 군집 번호를 알 수 있습니다. 또한 fit 이후에는 "cluter_centers_" 라는 속성을 통해 각 군집의 중심을 얻을 수 있습니다.

kmeans = KMeans(n_clusters=3, init='random', n_init=10, max_iter=300, tol=1e-4)
y_pred = kmeans.fit_predict(X)

X_0 = X[y==0] # cluster 0
X_1 = X[y==1] # cluster 1
X_2 = X[y==2] # cluster 2

plt.figure()
plt.scatter(X_0[:,0], X_0[:,1], c='green', marker='o', label='cluster 0')
plt.scatter(X_1[:,0], X_1[:,1], c='blue', marker='o', label='cluster 1')
plt.scatter(X_2[:,0], X_2[:,1], c='orange', marker='o', label='cluster 2')

plt.scatter(kmeans.cluster_centers_[:,0], kmeans.cluster_centers_[:,1], marker='+', c='black')

 

K-Means++

KMeans 함수의 "init" 파라미터는 본래 'k-means++'로 설정되어 있습니다. 이는 랜덤하게 군집 중심을 초기화할때 초기값이 나쁠 경우 군집 결과가 좋지 않기 때문에 K-Means 초기화 알고리즘을 개량한 것으로 초기 군집 중심이 최대한 서로 멀리 떨어지도록 위치시킵니다. K-Means++ 의 초기화 과정은

1) 선택한 $k$개의 군집 중심을 저장할 빈 집합 $M$을 설정하고
2) 입력 샘플에서 첫 번째 군집 중심을 랜덤하게 선택하고 $M$의 첫 번째 원소로 삽입합니다.
3) $M$에 있지 않은 각 샘플에 대해 $M$에 있는 군집 중심과의 최소 거리를 계산하고 최소 거리가 가장 큰 샘플을 다음 군집 중심으로 잡아 $M$에 추가합니다.
4) $k$가 다 찰때까지 2,3 과정을 반복합니다.

초기화 과정이 당연히 랜덤하게 초기화할 때보다 더 오래걸리지만 초기화 중심이 각각 최대한 멀리 떨어져 있으므로 군집화 과정 상의 수렴 속도가 훨씬 빨라지게 됩니다. 위에서 언급한대로 "KMeans(init='k-means++')" 를 통해 쉽게 사용할 수 있습니다.

 

참조

• www.geeksforgeeks.org/ml-k-means-algorithm/
• m.blog.naver.com/slykid/221850725829

---

다음 포스트

[Machine Learning/Data Analysis] - Clustering - 군집 개수 정하기