K-Means 클러스터링 알고리즘은 가장 단순하고 빠른 클러스터링 알고리즘의 하나이다. 다음과 같은 목적함수 값이 최소화될 때까지 클러스터의 중심(centroid) 위치와 각 데이터가 소속될 클러스터를 반복해서 찾는다. 이 값을 inertia라고도 한다.
$$ J = \sum_{k=1}^K \sum_{i \in C_k} d(x_i, \mu_k) $$이 식에서 $K$는 클러스터의 갯수이고 $C_k$는 $k$번째 클러스터에 속하는 데이터의 집합, $\mu_k$는 $k$번째 클러스터의 중심위치, $d$는 $x_i, \mu_k$ 두 데이터사이의 거리(distance) 혹은 비유사도(dissimilarity)로 정의한다. 만약 유클리드 거리를 사용한다면 다음과 같다.
$$ d(x_i, \mu_k) = || x_i - \mu_k ||^2 $$세부 알고리즘은 다음과 같다.
scikit-learn의 cluster 서브패키지는 KMeans 클러스터링을 위한 KMeans
클래스를 제공한다. 다음과 같은 인수를 받을 수 있다.
n_clusters
: 클러스터의 갯수init
: 초기화 방법. "random"
이면 무작위, "k-means++"
이면 K-Means++ 방법. 또는 각 데이터의 클러스터 라벨. n_init
: 초기 중심값 시도 횟수. 디폴트는 10이고 10개의 무작위 중심값 목록 중 가장 좋은 값을 선택한다.max_iter
: 최대 반복 횟수.random_state
: 시드값.다음은 make_blobs
명령으로 만든 데이터를 2개로 K-means 클러스터링하는 과정을 나타낸 것이다. 마커(marker)의 모양은 클러스터를 나타내고 크기가 큰 마커가 중심값 위치이다. 각 단계에서 중심값은 전단계의 클러스터의 평균으로 다시 계산된다.
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
X, _ = make_blobs(n_samples=20, random_state=4)
def plot_KMeans(n):
model = KMeans(n_clusters=2, init="random", n_init=1, max_iter=n, random_state=8).fit(X)
c0, c1 = model.cluster_centers_
plt.scatter(X[model.labels_ == 0, 0], X[model.labels_ == 0, 1], marker='v', facecolor='r', edgecolors='k')
plt.scatter(X[model.labels_ == 1, 0], X[model.labels_ == 1, 1], marker='^', facecolor='y', edgecolors='k')
plt.scatter(c0[0], c0[1], marker='v', c="r", s=200)
plt.scatter(c1[0], c1[1], marker='^', c="y", s=200)
plt.grid(False)
plt.title("iteration={}, score={:5.2f}".format(n, model.score(X)))
plt.figure(figsize=(8, 8))
plt.subplot(321)
plot_KMeans(1)
plt.subplot(322)
plot_KMeans(2)
plt.subplot(323)
plot_KMeans(3)
plt.subplot(324)
plot_KMeans(4)
plt.tight_layout()
plt.show()
K-Means++ 알고리즘은 초기 중심값을 설정하기 위한 알고리즘이다. 다음과 같은 방법을 통해 되도록 멀리 떨어진 중심값 집합을 찾아낸다.
다음은 KMean 방법을 사용하여 MNIST Digit 이미지 데이터를 클러스터링한 결과이다. 각 클러스터에서 10개씩의 데이터만 표시하였다.
from sklearn.datasets import load_digits
digits = load_digits()
model = KMeans(init="k-means++", n_clusters=10, random_state=0)
model.fit(digits.data)
y_pred = model.labels_
def show_digits(images, labels):
f = plt.figure(figsize=(8, 2))
i = 0
while (i < 10 and i < images.shape[0]):
ax = f.add_subplot(1, 10, i + 1)
ax.imshow(images[i], cmap=plt.cm.bone)
ax.grid(False)
ax.set_title(labels[i])
ax.xaxis.set_ticks([])
ax.yaxis.set_ticks([])
plt.tight_layout()
i += 1
def show_cluster(images, y_pred, cluster_number):
images = images[y_pred == cluster_number]
y_pred = y_pred[y_pred == cluster_number]
show_digits(images, y_pred)
for i in range(10):
show_cluster(digits.images, y_pred, i)
이미지의 제목에 있는 숫자는 클러스터 번호에 지나지 않으므로 원래 숫자의 번호와 일치하지 않는다. 하지만 이를 예측문제라고 가정하고 분류결과행렬을 만들면 다음과 같다.
from sklearn.metrics import confusion_matrix
confusion_matrix(digits.target, y_pred)
이 클러스터링 결과의 ARI, AMI, 실루엣 계수값은 다음과 같다.
from sklearn.metrics.cluster import adjusted_mutual_info_score, adjusted_rand_score, silhouette_score
print("ARI:", adjusted_rand_score(digits.target, y_pred))
print("AMI:", adjusted_mutual_info_score(digits.target, y_pred))
print("Silhouette Score:", silhouette_score(digits.data, y_pred))
연습 문제 14.2.1¶붓꽃 데이터를 K=3인 K-Means 클러스터링하여 adjusted Rand index, adjusted mutual information, 실루엣 계수를 각각 계산하라. |
"bj : X 클러스터링에서는 다른 클러스터였는데 Y 클러스터링에서도 다른 클러스터 Yj 인 데이터 쌍의 수" 라고 되어있는데 Y 클러스터링에서는 같은 클러스터 Yj 인 데이터 쌍의 수가 되어야하는 것이 아닌가요??
Adjusted Rand Index의 설명이 잘못되어 있었습니다. 수정하였습니다.