이번 포스팅에서는 클러스터링(Clustering, 군집화)의 대표적인 알고리즘 중에 하나로 K-Means 클러스터링에 대해서 알아보려고 한다. 여기서 다루는 내용은 다음과 같다.
1. K-Means 클러스터링(Clustering, 군집화)이란?
2. K-Means 클러스터링(Clustering, 군집화) 알고리즘
3. K-Means 클러스터링(Clustering, 군집화) 장단점
4. K-Means 클러스터링(Clustering, 군집화) 파이썬 구현
본 포스팅에서는 수식을 포함하고 있습니다.
티스토리 피드에서는 수식이 제대로 표시되지 않을 수 있으니
PC 웹 브라우저 또는 모바일 웹 브라우저에서 보시기 바랍니다.
1. K-Means 클러스터링(Clustering, 군집화)이란?
- 정의 -
K-Means 클러스터링은 비지도 학습 알고리즘으로 사전에 클러스터 개수 $k$와 초기값을 입력하면 각 데이터의 그룹을 할당해 나가는 Hard Clustering 알고리즘이다.
이 말의 뜻을 하나씩 살펴보자.
a. K-Means 클러스터링은 비지도 학습이다.
K-Means 클러스터링 알고리즘은 데이터에 라벨(Label)이 없고 데이터의 유사도를 바탕으로 개별 데이터를 그룹에 할당하는(라벨을 만들어내는) 비지도 학습이다.
b. K-Means 클러스터링 알고리즘은 사전에 클러스터 개수와 초기값을 지정해야 한다.
K-Means 클러스터링 알고리즘이 데이터를 보고 자동으로 클러스터 개수를 파악하여 그룹화해주는 것은 아니다. 반드시 클러스터 개수를 지정해줘야 한다.
클러스터 개수를 지정했으면 그 개수만큼의 값을 초기값으로 선정해야 한다. 아래 그림과 같이 클러스터 개수를 3으로 정했다면 초기값도 적절하게 3개값을 정한다. 이때 초기값은 직접 지정해도 되고 랜덤 샘플링을 통하여 지정할 수도 있다.
c. K-Means 클러스터링은 그룹을 할당해 나가는 알고리즘이다.
앞에서 얘기한 초기값은 각 그룹의 초기 중심점이라는 의미이다. 이때 각 중심점은 그룹을 결정하며 개별 데이터는 자기와 가까운 중심점과 같은 그룹으로 할당된다. 이때 한 번에 종료되는 것은 아니고(물론 데이터 형태에 따라 또는 운이 좋으면 한번에 끝날 수 있다) 그룹의 중심점을 업데이트하고 다시 개별 데이터의 그룹을 할당하는 과정을 반복하게 된다.
d. K-Means 클러스터링은 Hard Clustering 알고리즘이다.
Hard Clustering이란 데이터 포인트들의 그룹이 중심에 가까운 점에 무조건적으로 할당하는 군집화라는 뜻이다. 어찌보면 그럴듯하지만 논란이 있다. 왜 그럴까?
아래 2 그림에서 검은점을 빨간 그룹과 파란 그룹 중에서 어느 그룹에 할당해야할지를 생각해보자.
왼쪽의 경우 검은점은 빨간 그룹이라고 아주 강하게 말할 수 있을 것이다. 따라서 검은점을 빨간 그룹에 할당시키는 것이 당연할 것이다. 하지만 오른쪽의 경우는 어떤가? 빨간쪽에 가깝다고 하지만 파란쪽 중심으로 부터 생성된 데이터가 아니라고 하기엔 무리가 있다. 이때에는 검은점이 빨간쪽에서 60%, 파란쪽에서 40%정도의 가능성을 갖고 나왔다고 얘기하는 것이 더 합리적일 것이다. 하지만 K-Means 클러스터링은 이러한 가능성은 생각하지 않고 무조건 가까운 쪽으로 그룹을 할당하는 Hard Clustering 알고리즘이다.
- 궁금 사항 -
여기서 궁금한 사항이 생길 수 있다.
클러스터 개수는 어떻게 정하면 좋을까?
클러스터링이 얼마나 잘되었는지를 정량화한 지표를 이용한다. 그러고 나서 클러스터 개수 후보를 정하고 각 클러스터 개수에 대하여 클러스터링을 수행한 뒤 지표를 계산한다.
이때 지표값을 최적화하는 클러스터링 개수를 최적 클러스터 개수로 선정한다.
자주 활용되는 지표로 Dunn Index, 실루엣(Silhouette) Index 등이 있는데 이에 대해선 다음 포스팅에서 소개하겠다.
2. K-Means 클러스터링(Clustering, 군집화) 알고리즘
이번엔 K-Means 클러스터링(군집화) 알고리즘은 다음과 같다.
K-Means 클러스터링 알고리즘
(1) 클러스터 개수 $K$, $\epsilon > 0$ 그리고 최대 반복수 $L$을 설정한다.
(2) 초기값(초기 중심값) $\mu_j^{(0)}, j=1, \ldots, K$을 계산한다. 초기값은 직접 설정해주거나 데이터 포인트에서 클러스터 개수만큼 비 복원 추출할 수도 있다.
(3) $t$번째 스텝에서의 중심값을 $\mu_j^{(t)}, j=1, \ldots, K$라 하자. 이제 개별 데이터에 그룹을 할당한다. 이때 개별 데이터와 각 중심값과의 거리를 계산하고 최소 거리를 갖는 중심값을 그룹으로 정한다. 이때 거리는 유클리디안 거리(Euclidean Distance)를 사용한다. 즉,
$$ \DeclareMathOperator*{\argminA}{argmin} k = \argminA_{j=1, \ldots, K}\|x_n-\mu_j^{(t)} \|$$라 한다면 개별 데이터 $x_n$의 그룹은 $k$가 되는 것이다.
(4) 중심값을 업데이트한다. $r_{nk}$를 $x_n$의 그룹이 $k$라면 1, 아닌 경우 0의 값을 갖는다고 하자. 이때 $t+1$번째 중심값은 다음과 같이 업데이트된다.
$$\mu_k^{(t+1)} = \frac{\sum_{i=1}^nr_{ik}x_i}{\sum_{i=1}^nr_{ik}}$$
위식은 결국 각 그룹에서의 평균값을 다음 스텝의 중심값으로 업데이트됨을 의미한다.
(5) 만약 $t>L$ 또는 $\|\mu_k^{(t+1)}-\mu_k^{(t)} \|<\epsilon$이면 알고리즘을 종료하고 아닌 경우에는 (3)으로 돌아간다.
3. K-Means 클러스터링(Clustering, 군집화) 알고리즘의 장단점
- 장점 -
(1) 직관적이고 구현이 쉽다.
알고리즘이 돌아가는 과정이 직관적이고 이해가 쉽다.
(2) 구현이 굉장히 쉽다.
알고리즘이 단순하여 구현하기가 쉽다.
(3) 대용량 데이터에 적용 가능하다.
복잡한 계산이 필요하지 않아 대용량 데이터에도 적용 가능하다.
(4) 수렴성이 보장된다.
K-Means 알고리즘은 수렴성이 보장된다.
- 단점 -
(1) 초기값에 민감하다.
초기값에 따라서 결과가 매우 달라질 수 있다.
(2) 이상치에 영향을 받는다.
거리를 Euclidean Distance를 기반으로 하기 때문에 중심값을 업데이트하는 과정에서 이상치에 영향을 받을 수 있다.
(3) 그룹 내 분산 구조를 반영할 수 없다.
거리를 Euclidean Distance를 기반으로 하기 때문에 그룹 내 분산 구조를 제대로 반영할 수 없다. 아래 왼쪽 그림은 세개의 분산 구조를 갖는 클러스터를 나타낸 것이다. 우리가 원하는 것은 이러한 분산 구조를 반영한 타원 형태의 클러스터링(군집화) 결과이다. 하지만 K-Means를 실제로 돌려보면 Euclidean Distance의 영향으로 타원 구조가 아닌 원형 구조의 클러스터링 결과를 얻게 된다.
(4) 차원의 저주에 걸릴 수 있다.
고차원으로 갈수록 개별 데이터 간 거리가 가까워져 클러스터링 효과가 없을 수 있다. 이는 군집간에는 거리를 최대한 떨어뜨려놔야 클러스터링을 하는 의미가 있는데 고차원으로 갈 수록 개별 데이터간 거리가 가까워져 이러한 효과를 볼 수 없다는 뜻이다.
(5) 클러스터의 개수를 정해야 한다.
K-Means 클러스터링은 클러스터 개수를 자동으로 잡아주지 않고 사전에 정해줘야 한다. 하지만 Dunn Index, 실루엣(Silhouette) Index과 같은 지표를 이용하여 최적 클러스터 개수를 정할 수 있다.
(6) 범주형 변수가 있다면 K-Means 클러스터링을 할 수 없다.
K-Means 클러스터링(군집화) 알고리즘은 Euclidean Distance를 사용하기 때문에 범주형 변수가 있다면 적용할 수 없다. 이때에는 K-Means 클러스터링(군집화) 알고리즘을 확장한 K-Modes Clustering 알고리즘을 이용하면 클러스터링(군집화)가 가능하다고 한다. 이와 관련된 내용도 추후에 포스팅 해봐야겠다.
4. K-Means 클러스터링(Clustering, 군집 분석) 파이썬 구현
먼저 샘플용 데이터를 만들어보자.
import numpy as np
import random
import matplotlib.pyplot as plt
np.random.seed(100)
num_data = 50
x11 = np.linspace(0.3,0.7,20)
x12 = np.linspace(1.3,1.8,15)
x13 = np.linspace(2.4,3,15)
x1 = np.concatenate((x11,x12,x13),axis=None)
error = np.random.normal(1,0.5,num_data)
x2 = 1.5*x1+2+errorfig = plt.figure(figsize=(7,7))
fig.set_facecolor('white')
plt.scatter(x1, x2, color='k')
plt.show()
딱 봐도 그룹이 3개로 나뉘는 데이터이다.
1) 직접 구현
클러스터링(군집화) 알고리즘을 직접 구현해보자. 아래 코드가 K-Means 클러스터링을 수행하는 함수이다. 이 함수는 데이터(X), 클러스터 개수(n_clusters), 초기 중심값(init_center), 최대 반복수(max_iter). 오차한계(epsilon) 마지막으로 random_state를 인자로 받는다.
이 함수는 초기 중심값을 세팅하고 각 스텝마다 라벨과 중심값을 업데이트한다. 최대 반복수만큼 반복되었거나 이전 스텝의 중심값과 다음 스텝 중심값의 차이가 오차 한계보다 작다면 알고리즘은 종료되며 최종 라벨(labels), 반복 스텝 수(iteration), 라벨 업데이트 과정(labels_history), 중심값 업데이트 과정(center_history)을 출력한다.
def kmeans_clustering(X, n_clusters, init_center=None, max_iter=10, epsilon=1e-4, random_state=100):
# inititalize centeroids
if init_center is None:
random.seed(random_state)
idx = random.sample(range(X.shape[0]), n_clusters)
center = X[idx,:]
else:
center = init_center
iteration = 1
labels_history = [] # label history
center_history = [] # centeroid history
while(iteration<=max_iter):
## assign label
labels = []
for i in range(X.shape[0]):
data = X[i, :]
labels.append(np.argmin([np.linalg.norm(data-x) for x in center]))
labels = np.array(labels)
## update centeroids
next_center = []
for i in range(n_clusters):
target_idx = np.where(labels==i)[0]
center_val = np.mean(X[target_idx,:], axis=0)
next_center.append(center_val)
next_center = np.array(next_center)
if epsilon:
if np.linalg.norm(next_center-center) <= epsilon:
break
center = next_center
labels_history.append(labels)
center_history.append(center)
iteration += 1
return (labels, iteration, labels_history, center_history)
이제 이 함수를 이용하여 K-Means 클러스터링을 수행해보자. 클러스터 개수를 3개로 설정하고 초기 중심값을 지정해주었다.
X = np.stack([x1, x2], axis=1)
init_center= np.array([[2,4],[1,5],[2.5,6]])
max_iter=50
epsilon=1e-10
random_state=101
n_clusters=3
results = kmeans_clustering(X, n_clusters, init_center, max_iter, epsilon=1e-4,
random_state=100)
labels = results[0]
이제 군집화가 잘되었는지 확인해보자.
fig = plt.figure(figsize=(7,7))
fig.set_facecolor('white')
for i, label in enumerate(labels):
if label == 0:
color = 'blue'
elif label ==1:
color = 'red'
else:
color = 'green'
plt.scatter(X[i,0],X[i,1], color=color)
plt.xlabel('x1')
plt.ylabel('x2')
plt.show()
클러스터링(군집화)이 아주 잘되었다. 이번엔 업데이트 진행과정을 살펴보자.
labels_history = results[2]
for j, labels in enumerate(labels_history):
fig = plt.figure(figsize=(7,7))
fig.set_facecolor('white')
for i, label in enumerate(labels):
if label == 0:
color = 'blue'
elif label ==1:
color = 'red'
else:
color = 'green'
plt.scatter(X[i,0],X[i,1], color=color)
plt.title(f'Iteration : {j+1}')
plt.xlabel('x1')
plt.ylabel('x2')
plt.show()
알고리즘 4 스텝만에 클러스터링이 완료된 것을 알 수 있다.
2) Scikit-Learn 이용
이번에는 Scikit-Learn 패키지를 이용하여 K-Means 클러스터링을 해보자. Scikit-Learn에서는 KMeans 클래스를 이용하여 클러스터링(군집화)을 수행한다.
이때 n_clusters는 3, init에는 초기 중심값 init_center를 넣고 KMeans 인스턴스를 생성한다. 그러고 나서 fit 함수에 클러스터링(군집화)하려고 하는 데이터(X)를 넣어주면 클러스터링(군집화)이 수행된다.
그리고 최종 라벨은 labels_ 필드를 이용하여 얻을 수 있다.
import warnings
warnings.filterwarnings('ignore')
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=3, init=init_center)
kmeans.fit(X)
labels = kmeans.labels_
클러스터링(군집화)를 시각화해보자.
fig = plt.figure(figsize=(7,7))
fig.set_facecolor('white')
for i, label in enumerate(labels):
if label == 0:
color = 'blue'
elif label ==1:
color = 'red'
else:
color = 'green'
plt.scatter(X[i,0],X[i,1], color=color)
plt.xlabel('x1')
plt.ylabel('x2')
plt.show()
이번 포스팅에서는 클러스터링(군집화)의 대표적인 알고리즘 K-Means 클러스터링을 알아보았다. 다음 포스팅에서는 클러스터링이 잘되었는지를 정량적으로 알아볼 수 있는 여러가지 지표들에 대해서 알아보려고 한다.
참고자료
문일철 - 인공지능 및 기계학습 개론2
'통계 > 머신러닝' 카테고리의 다른 글
| 12. Gaussian Mixture Model(가우시안 혼합 모형) 클러스터링(군집 분석)에 대해서 알아보자 with Python (0) | 2022.04.25 |
|---|---|
| 12. 클러스터링(군집화) 평가 지표 Dunn Index with Python (1) | 2022.04.22 |
| 10. 가지치기(Pruning)에 대해서 알아보자 with Python (4) | 2021.07.05 |
| 9. 의사결정나무(Decision Tree) 에 대해서 알아보자 with Python (3) | 2021.06.10 |
| 8. 연관 규칙 분석(Association Rule Analysis) with Python (0) | 2021.05.23 |
댓글