K-means Clustering
Clustering (군집) : 기계학습에서 비지도학습의 기법 중 하나이며, 데이터 셋에서 서로 유사한 관찰치들을 그룹으로 묶어 분류하여 몇 가지의 군집(cluster)를 찾아내는 것
※위의 그림은 군집을 설명하기 위한 임의의 그림입니다
K-means Clustering?
K-means 알고리즘은 굉장히 단순한 클러스터링 기법 중에 하나이다. 어떤 데이터 셋(set)이 있고 N개의 클러스터로 분류하겠다고 가정하면, 그 데이터 셋에는 N개의 중심(centroid)이 존재한다. 각 데이터들은 유클리디안 거리를 기반으로 가까운 중심에 할당되고, 같은 중심에 모인 데이터 그룹이 하나의 클러스터가 된다.
학습 방식
기본적으로 K-means Clustering은 EM 알고리즘을 기반으로 한다. E는 Expectation, M은 Maximization을 의미하는 것이다. 아래 그림을 보자.
위와 같이 무작위로 데이터가 있을 때 먼저 클러스터의 수를 2로 정하고, 2개의 클러스터의 중심을 무작위로 잡는다.
그 후에 모든 데이터 셋과 각 중심과의 유클리디안 거리를 구해 가장 가까운 중심에 할당한다. 이를 Expectation 단계라고 한다.
※ 아래부터 나오는 그림들은 정확한 수치계산으로 나눈 것이 아닌, 모두 이해를 돕기 위해 임의로 그린 것임을 밝힙니다.
이렇게 두개로 나눠진 클러스터들에서는, 각 중심이 정말로 중심에 오도록 업데이트 해주는데, 이 단계가 Maximization 단계이다. K-means는 이름에서도 알 수 있듯이 이 중심을 클러스터의 데이터들의 ‘평균값’으로 계산한다.
자, 이제 중심이 바뀌었다. 이 중심에 맞게 또 다시 데이터 셋들을 클러스터링 해야한다. 이렇게 E-M-E-M을 정한 반복수를 채우거나, 더 이상 학습해도 결과가 바뀌지 않을 때까지 반복한다.
아래 그림으로 간략히 보면 이해가 빠를 것이다.
수학적 로직
그렇다면 어떻게 이러한 알고리즘이 가능하게 될까? 우선, 데이터 셋이 다음과 같이 있다고 해보자.
총 N개의 데이터가 있고, 여기서 K개의 클러스터로 나눠야한다. 최종 적으로는 모든 N개의 데이터를 K개의 클러스터에 배정하는 것이다. 이 때, K 값은 미리 지정해주어야 하는 값이다.
이 때, 목적함수를 정의해주게 되는데 이 함수를 왜곡 측정(distortion measure) 함수라고 한다. 수식은 다음과 같다.
클러스터의 각각의 점들로부터 그 클러스터의 평균과의 거리의 합을 제곱하여 구하게 되는데, 우리는 J값이 최소가 될 때 각각의 값을 구해야한다. 벡터가 k번째 클러스터에 속하는 경우 Uk로 표기하고, Uk는 k번째 클러스터의 정중앙에 놓인 벡터(무게중심)라고 가정한다. 따라서 처음에는 이 Uk의 임의의 초기값을 줌으로써 클러스터의 중심을 임의로 잡는 것이다.
그 후에는 Uk의 값을 고정한 채로 J를 최소화하는 rnk의 값을 구한다.
(이 때 rnk는 0 또는 1의 값인데, xn이 k번째 클러스터에 속하는 경우 rnk의 값은 1이 되고 아닌 경우에는 0이 된다. )
rnk의 값이 구해지면, 새롭게 얻어진 rnk의 값을 고정하고 다시 Uk를 구하고 이를 정해진 횟수만큼 반복될 때까지, 혹은 더이상 학습해도 결과가 달라지지 않을 때까지 반복하는 것이다. 이 것이 EM 알고리즘의 로직이다. K-means는 이름에서도 알 수 있듯이 이 중심을 데이터 셋의 ‘평균’값으로 계산하게 된다.
구현
K-means Clustering은 파이썬에서 간단하게 구현할 수 있다. Scikit-Learn 라이브러리를 활용한다.
from sklearn.cluster import KMeans#클러스터의 개수 지정(n개)
num_clusters = n#알맞은 매트릭스 Z 삽입
km = KMeans(n_clusters=num_clusters)
km.fit(Z)
클러스터의 알맞은 개수를 보기 위해서 Scree plot을 그려본다.
from scipy.spatial.distance import cdistdistortions = []
K = range(1,10)
for k in K:
kmeanModel = KMeans(n_clusters=k).fit(Z)
kmeanModel.fit(Z)
distortions.append(sum(np.min(cdist(Z, kmeanModel.cluster_centers_, 'euclidean'), axis=1)) / Z.shape[0])# Plot the elbow
plt.plot(K, distortions, 'bx-')
plt.xlabel('k')
plt.ylabel('Distortion')
plt.title('The Elbow Method showing the optimal k')
plt.show()
Scree Plot에서 꺾이는 부분이 알맞은 클러스터의 개수로, 위의 그림에서는 3이 꺾이는 부분이므로 3개가 알맞은 클러스터의 개수가 된다.
3개의 클러스터로 클러스터링을 한 후 시각화를 하는 코드는 다음과 같다.
df = pd.DataFrame(Z)
df['category'] = km.labels_colormap = { 0: 'red', 1: 'green', 2: 'blue'}
colors = results.apply(lambda row: colormap[row.category], axis=1)
ax = results.plot(kind='scatter', x=0, y=1, alpha=0.1, s=300, c=colors)
<참고 URL>
