[클러스터링] K-Means 알고리즘

1. 정의

K-Means 알고리즘은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. (출처:위키피디아)

 

수행 과정은 아래와 같다.

1) 임의의 군집 중심점(centroid)를 설정
2) 각 데이터는 가장 가까운 중심점에 소속됨
3) 중심점에 할당된 데이터들의 평균 중심으로 중심점 이동
4) 이동된 중심점으로 각 데이터 소속 변경
5) 4번에서 소속변경이 없다면 멈추고 계속 있다면 소속변경이 없을 때까지 3~4번을 반복

---

2. 특징

2-1. 장점

• 일반적으로 많이 사용되는 알고리즘으로 쉽고 간결하다.

2-2. 단점

• 거리 기반 알고리즘으로 속성의 개수가 많다면 정확도가 떨어진다.
• 반복을 수행하는데, 반복 횟수가 많을 경우 수행 시간이 느리다.
• 몇 개의 군집을 선택할지 가이드하기 어렵다.

---

3. 사이킷런 KMeans 클래스 소개

사이킷런 KMeans 클래스를 통해 해당 알고리즘을 사용할 수 있는데, 초기화 파라미터는 다음과 같다.

class sklearn.cluster.KMeans(n_clusters=8, init='k-means++', n_init=10, 
max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd')

3-1. n_clusters

n_clusters는 몇개의 클러스터로 묶을지에 관한 변수이다. 즉, 군집 중심점(centroid)의 개수를 의미한다.

3-2. init

init은 군짐 중심점(centroid)의 초기 좌표의 설정에 관련된 부분이다. k-means++과 random이 있다.

• k-means++: 특별한 알고리즘에 의해서 설정
• random: 주어진 데이터중에서 랜덤하게 골라서 설정한다.

KMeans 알고리즘의 경우, initial points로 비슷한 점이 여러 개 선택되면 학습 결과가 좋지 못하다. 따라서, k-means++를 활용하면, 이 부분을 해결할 수 있고 보통 이 방식을 사용한다고 한다.

3-3. n_init

초기 중심점 시도 횟수. 10번이라면 10개의 중심점 목록중 가장 좋은 값을 선택한다.

3-4. max_iter

최대 반복 횟수이며, 이 횟수 이전에 모든 데이터의 중심점 이동이 없으면 종료한다.

3-5. tol

tol은 early stop 역할으로 inertia가 지정해준 tol만큼 줄어들지 않으면 조기에 종료시키는 것이다.

inertia
군집 중심점과 데이터간의 거리의 제곱 합

---

4. 사용법

sklearn에서 기본으로 제공해주는 iris 데이터셋을 통해 사용법을 알아보자.

# 라이브러리 임포트
from sklearn.preprocessing import scale
from sklearn.datasets import load_iris
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
%matplotlib inline

# 데이터 로드 및 프레임으로 변환
iris = load_iris()
irisDF = pd.DataFrame(iris.data, columns=['sepal_length', 'sepal_width', 'petal_length', 'petal_width'])
irisDF.head()

Out:

	sepal_length	sepal_width	petal_length	petal_width
0	5.1	3.5	1.4	0.2
1	4.9	3.0	1.4	0.2
2	4.7	3.2	1.3	0.2
3	4.6	3.1	1.5	0.2
4	5.0	3.6	1.4	0.2

 

 

# Kmeans 실행
kmeans = KMeans(n_clusters=3, init='k-means++', max_iter=300, random_state=100)
kmeans.fit(irisDF)

print(kmeans.labels_)

Out:

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 2 2 1 2 2 2 2
 2 2 1 1 2 2 2 2 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2
 2 1]

 

# 칼럼 변경 및 수행 결과 확인
irisDF['target'] = iris.target
irisDF['cluster'] = kmeans.labels_
irisDF['target'] = irisDF['target'].map({0: iris.target_names[0], 1: iris.target_names[1], 2: iris.target_names[2]})
irisDF['cluster'] = irisDF['cluster'].map({0: iris.target_names[0], 1: iris.target_names[1], 2: iris.target_names[2]})
iris_result = irisDF.groupby(['target', 'cluster'])['sepal_length'].count()

iris_result

Out:

target      cluster   
setosa      setosa        50
versicolor  versicolor    48
            virginica      2
virginica   versicolor    14
            virginica     36
Name: sepal_length, dtype: int64

 

# PCA를 활용한 시각화
from sklearn.decomposition import PCA

pca = PCA(n_components=2)
pca = pca.fit_transform(iris.data)
irisDF['pca_x'] = pca[:, 0]
irisDF['pca_y'] = pca[:, 1]
irisDF.head()

Out:

	sepal_length	sepal_width	petal_length	petal_width	target	cluster	pca_x	pca_y
0	5.1	3.5	1.4	0.2	setosa	setosa	-2.684126	0.319397
1	4.9	3.0	1.4	0.2	setosa	setosa	-2.714142	-0.177001
2	4.7	3.2	1.3	0.2	setosa	setosa	-2.888991	-0.144949
3	4.6	3.1	1.5	0.2	setosa	setosa	-2.745343	-0.318299
4	5.0	3.6	1.4	0.2	setosa	setosa	-2.728717	0.326755

 

plt.subplots(figsize=(15, 5))

plt.subplot(1, 2, 1)
sns.scatterplot(data=irisDF, x='pca_x', y='pca_y', hue='target')
plt.title('target')

plt.subplot(1, 2, 2)
sns.scatterplot(data=irisDF, x='pca_x', y='pca_y', hue='cluster')
plt.title('cluster')

 

실제 레이블인 target과 KMeans를 활용한 cluster간에 조금의 오차를 확인할 수 있다.

---

5. K 값 구하는 방법

실제 상황에서는 변수가 매우 많기 떄문에 적절한 K값을 찾는 데 한계가 있다. 이에 대한 방법으로 2가지 방법이 있다.

5-1. 엘보우 기법 (elbow method)

앞에서 잠깐 언급했던, 이너셔(inertia)를 활용한다. 이너셔값은 클러스터의 중심점과 데이터 간의 거리이므로 작을수록 클러스터링이 잘된 것이라고 할 수 있다. 다만, K값이 커지면 필연적으로 작아질 수 밖에 없다. 조금 생각해보면 K가 커지면 클러스터가 그만큼 많아지게 되고, 각 클러스터별 데이터의 수는 줄어들면서 거리는 가까워질 수 밖에 없다.

 

그래서 엘보우 기법은 무엇이냐. 방법은 다음과 같다.

1) 적당한 K값의 범위를 설정하여 이너셔값을 구하고 위처럼 그래프로 나타낸다.
2) 이너셔값이 급격히 줄어드는 K값을 정한다.

팔꿈치처럼 꺾이는 부분을 선택한다고 해서, 엘보우 기법이다.

5-1-1. 예시

iris 데이터셋을 활용한 예시이다. 범위를 2~9로 설정하고 그만큼 for문을 돌려서 이너셔값을 구한 뒤, 그래프를 그렸다. (재학습을 위해 앞서 칼럼들을 drop하여 진행)

inertias = []
for k in range(2, 10):
    kmeans = KMeans(n_clusters=k, init='k-means++', max_iter=300, random_state=100)
    kmeans.fit(irisDF.drop(columns = {'target', 'cluster', 'pca_x', 'pca_y'}))
    inertias.append(kmeans.inertia_)

data = np.array([range(2, 10), inertias])
newdf = pd.DataFrame(data.T, columns=['X', 'inertia'])
plt.figure(figsize=(7,5))
sns.set_style('whitegrid')
sns.lineplot(data = newdf, x='X', y='inertia')

X=3 지점에서 급격히 줄어드는 것을 알 수 있고 적절한 클러스터의 수는 3이 된다.

5-2. 실루엣 계수

실제로는 어느 한 지점에서 크게 떨어지지 않고 비교적 그래프가 완만한 경우가 많다. 그에 대한 대안으로 실루엣 계수를 사용할 수 있다. 보통 엘보우 기법에서 최적의 값을 찾지 못했을 때 쓰인다.

 

실루엣 계수는 클러스터 내부에서의 평균 거리와, 최근접한 다른 클러스터 데이터와의 평균 거리도 점수에 반영한다. 따라서 실루엣 계수가 클수록 다른 클러스터 데이터와의 거리가 멀게 되고 이는 분류가 잘되었다는 뜻이다.

 

5-2-1. 예시

위와 마찬가지로 iris 데이터셋을 활용한 예시이다. 코드는 아래와 같다.

from sklearn.metrics import silhouette_score

silhouette = []
for k in range(2, 10):
    kmeans = KMeans(n_clusters=k, init='k-means++', max_iter=300, random_state=100)
    kmeans.fit(irisDF.drop(columns = {'target', 'cluster', 'pca_x', 'pca_y'}))
    labels = kmeans.predict(irisDF.drop(columns = {'target', 'cluster', 'pca_x', 'pca_y'}))
    silhouette.append(silhouette_score(irisDF.drop(columns = {'target', 'cluster', 'pca_x', 'pca_y'}), labels))
data = np.array([range(2, 10), silhouette])
newdf = pd.DataFrame(data.T, columns=['X', 'silhouette'])
plt.figure(figsize=(7,5))
sns.set_style('whitegrid')
sns.lineplot(data = newdf, x='X', y='silhouette')

X가 2일 때가 가장 크게 나왔다. 아무래도 이는 virsicolor와 virginica가 근처에 있고 setosa가 멀리 있어서 이렇게 수치가 나온듯 하다.

 

한편, 실루엣 계수 평균값만 높다고 최적일 수는 없다. 특정 클러스터의 실루엣 계수가 높고 다른 클러스터의 실루엣 계수가 낮다면 좋지 않을 것이다. 따라서, 개별 클러스터별 실루엣 계수도 함께 고려하면 좋을 것이다.

---

6. Reference

• https://ko.wikipedia.org/wiki/K-%ED%8F%89%EA%B7%A0_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

k-평균 알고리즘 - 위키백과, 우리 모두의 백과사전

• https://lovit.github.io/nlp/machine%20learning/2018/03/19/kmeans_initializer/

 

k-means initial points 선택 방법

• https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html?highlight=kmeans#sklearn.cluster.KMeans

sklearn.cluster.KMeans

• http://www.yes24.com/product/goods/69752484

파이썬 머신러닝 완벽 가이드 - YES24

• http://www.yes24.com/Product/Goods/110511505

데싸노트의 실전에서 통하는 머신러닝 - YES24