Hierarchical Clustering

khsfun0312·2021년 2월 18일
0

Machine Learning

목록 보기
6/10

Hierarchical Clustering의 정의

Hierarchical Clustering(계층적 군집화)는 계층적 트리 모형을 이용해 개별 개체들을 순차적, 계층적으로 유사한 그룹으로 군집화하는 알고리즘이다.
지난 글에서 K-평균 군집화를 다루었는데, 군집화라는 점에서 같지만 K-평균 군집화와 달리 군집의 수(K)를 사전에 정하지 않아도 학습을 할 수 있다. 이는 Dendrogram(덴드로그램)을 생성하여 가능하다. 대신 계산복잡도는 K-평균 군집화보다 크다.

덴드로그램은 개체들이 결합되는 순서를 나타내는 트리형태의 구조이다. 이를 통해 데이터를 몇 개의 군집으로 분류할 수 있게 된다.

계층적 군집화의 과정

계층적 군집화를 수행하기 위해서는 distance(거리)와 similarity(유사도)가 계산되어야 한다. 거리 측정법은 KNN을 다룬 글에 있다. 유사도를 측정하는 방법은 https://ratsgo.github.io/from%20frequency%20to%20semantics/2017/04/20/docsim/ 이 블로그에 자세히 설명되어 있으니 참고하면 좋다.

  1. 모든 개체들 사이의 거리에 대한 유사도 행렬을 계산한다.
  2. 거리가 가까운 데이터들끼리 군집을 형성한다.
  3. 유사도 행렬을 업데이트한다.

ex)

위와 같이 거리 행렬이 주어졌을 때 거리가 가장 가까운 것은 A와 D이므로 이들이 하나의 군집으로 묶이게 된다.

A와 D가 군집으로 묶이면서 행렬은 위와 같이 업데이트가 된다. AD와 C 사이의 거리가 가장 가까우므로 이들이 또다시 하나의 군집으로 형성될 것이다. 이 때 군집과 개체 사이의 거리 또는 군집간의 거리는
위와 같이 여러 방법으로 계산할 수 있다.

크게 두 부류밖에 남지 않았기에 이들이 군집을 형성할 것이다.

분석 대상 관측치가 없으면 학습이 종료된다. 왼쪽이 이 데이터셋에서의 덴드로그램이다.

실습

Dendrogram 그리기

from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

# Calculate the linkage: mergings
mergings = linkage(data,method='complete')

# Plot the dendrogram, using varieties as labels
plt.figure(figsize=(40,20))
dendrogram(mergings,
           labels = labels.as_matrix(columns=['labels']),
           leaf_rotation=90,
           leaf_font_size=20,
)
plt.show()

linkage에는 크게 세가지 방식이 있는데, Complete linkage는 두 군집의 가장 먼 거리를 측정하는 방식이고, Single linkage는 가장 가까운 거리, Average linkage는 평균 거리를 측정하는 방식이다.

  • Ward linkage도 많이 쓰이는데, 이는 연결될 수 있는 군집 조합을 만들고, 군집 내 편차들의 제곱합을 기준으로 (군집의 평균과 데이터들 사이의 오차 제곱합(SSE)을 측정해) 최소 제곱합을 가지게 되는 군집끼리 연결하는 방식이다.

AgglomerativeClustering(병합군집)

from sklearn.cluster import AgglomerativeClustering

cluster = AgglomerativeClustering(n_clusters=5, affinity='euclidean', linkage='ward')
cluster.fit_predict(data)

병합군집은 계층적 군집을 만들어가며 모든 포인트들이 하나의 포인트를 가진 군집에서 마지막 군집까지 이동하며 최종군집이 형성되는 방식이다. 이 때 한 군집에 속한 개체는 다른 군집으로 이동할 수 없는게 특징이다.

from sklearn.cluster import AgglomerativeClustering

model = AgglomerativeClustering(n_clusters = 3, affinity='euclidean', linkage='complete')
#model.fit(X_train, y_train)
y_predict = model.fit_predict(X_test)

print("계층적 군집화 정확도: {0:.4f}".format(accuracy_score(y_predict, y_test)))

scikitlearn의 유방암 데이터에 적용해서 위의 코드로 정확도 0.69가 나왔다.

출처

profile
똘멩이

0개의 댓글