Hierarchical Clustering의 정의
Hierarchical Clustering(계층적 군집화)는 계층적 트리 모형을 이용해 개별 개체들을 순차적, 계층적으로 유사한 그룹으로 군집화하는 알고리즘이다.
지난 글에서 K-평균 군집화를 다루었는데, 군집화라는 점에서 같지만 K-평균 군집화와 달리 군집의 수(K)를 사전에 정하지 않아도 학습을 할 수 있다. 이는 Dendrogram(덴드로그램)을 생성하여 가능하다. 대신 계산복잡도는 K-평균 군집화보다 크다.
덴드로그램은 개체들이 결합되는 순서를 나타내는 트리형태의 구조이다. 이를 통해 데이터를 몇 개의 군집으로 분류할 수 있게 된다.
계층적 군집화의 과정
계층적 군집화를 수행하기 위해서는 distance(거리)와 similarity(유사도)가 계산되어야 한다. 거리 측정법은 KNN을 다룬 글에 있다. 유사도를 측정하는 방법은 https://ratsgo.github.io/from%20frequency%20to%20semantics/2017/04/20/docsim/ 이 블로그에 자세히 설명되어 있으니 참고하면 좋다.
- 모든 개체들 사이의 거리에 대한 유사도 행렬을 계산한다.
- 거리가 가까운 데이터들끼리 군집을 형성한다.
- 유사도 행렬을 업데이트한다.
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가 나왔다.
출처
