[데이터 분석] 22. 클러스터링 Ⅱ : 계층적 군집

1. 계층적 군집

이번 장에서 다룰 계층적 군집은 프로토타입 기반의 군집 기법으로 이진 트리 형태의 덴드로그램을 그려서 군집화를 표현한다. 뿐만 아니라 K-Means 처럼 군집의 개수를 사전에 정의할 필요도 없다. 
계층적 군집은 다시 군집화 방식에 따라, 병합 계층적 군집방식과 분할 계층적 군집방식으로 나눌 수 있다. 이 후에 자세히 설명하겠지만, 간단하게 설명을 하자면, 병합 계층적 군집방식은 각 샘플이 독립적인 클러스터라고 가정한 상태로 시작해, 하나의 클러스터가 남을 때까지 가장 가까운 클러스터를 합치는 방식이다. 반면 분할 계층적 군집방식은 하나의 큰 클러스터로 시작해서 하나의 샘플이 남을 때까지 계속 분할하면서 군집을 만드는 방식이다. 

2. 병합 계층적 군집 방식

보통 병합 계층적 군집 방식을 사용하게 되면, 단일 연결과 완전 연결 중 하나의 방식을 사용해 각 샘플을 병합하게 된다. 여기서 말한 단일 연결이라 함은 클러스터 쌍에서 가장 비슷한 샘플 간의 거리를 계산해, 거리가 가장 가까운 두 샘플이 하나의 클러스터를 구성하는 방식이다. 이와 달리 완전 연결은 클러스터 쌍에서 가장 많이 다른 샘플간의 거리를 비교해 병합을 수행하는 방식이라고 할 수 있다. 

위의 두 방식 중 이번 장에서는 완전 연결 방식을 채택했다고 가정하고, 알고리즘의 과정을 살명하겠다. 구체적인 알고리즘 진행은 아래와 같이 반복된다. 

① 모든 샘플간의 거리를 계산한다. 
② 모든 데이터 포인트를 단일 클러스터로 표현한다. 
③ 가장 많이 다른 샘플 간의 거리를 기록하여 가장 가까운 2개의 클러스터를 병합한다. 
④ 유사도 행렬을 업데이트 한다. 
⑤ 하나의 클러스터가 될 때까지 ① ~ ④ 까지의 과정을 반복한다.

위의 알고리즘 과정을 코드로 표현하면 아래와 같이 작성할 수 있다. 

import pandas as pd
import numpy as np

from scipy.spatial.distance import pdist, squareform
from scipy.cluster.hierarchy import linkage

np.random.seed(12)
variables = ['x', 'y', 'z']
labels = ['ID_0', 'ID_1', 'ID_2', 'ID_3', 'ID_4']

x = np.random.random_sample([5, 3])*10
df = pd.DataFrame(x, columns=variables, index=labels)

print(df)

# pdist(): 입력에 사용할 거리 행렬에 대한 계산
# squareform(): 샘플 간 거리 대칭 행렬을 생성
row_dist = pd.DataFrame(squareform(pdist(df, metric='euclidean')), columns=labels, index=labels)
row_dist

row_clusters = linkage(df, method='complete', metric='euclidean')

pd.DataFrame( \
	row_clusters, \
    columns=['row label 1', 'row label 2', 'distance', 'item no.'], \
    index=['cluster %d' %(i+1) for i in range(row_clusters.shape[0])] \
)

library(stats)
library(tibble)

set.seed(12)
variables <- c('x', 'y', 'z')
labels <- c('ID_0', 'ID_1', 'ID_2', 'ID_3', 'ID_4')

x <- matrix(runif(15, min = 0, max = 10), nrow = 5, ncol = 3)
df <- as.data.frame(x)
colnames(df) <- variables
rownames(df) <- labels

print(df)

row_dist <- as.matrix(dist(df, method = "euclidean"))
colnames(row_dist) <- labels
rownames(row_dist) <- labels

print(as.data.frame(row_dist))

row_clusters <- hclust(dist(df, method = "euclidean"), method = "complete")

row_clusters_df <- as_tibble(cbind(row_clusters$merge, row_clusters$height, row_clusters$order))
colnames(row_clusters_df) <- c('row label 1', 'row label 2', 'distance', 'item no.')

row_clusters_df

추가적으로 위의 결과에 대해 덴드로그램을 그려볼 수 있다. 코드는 다음과 같다. 

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

row_dendrogram = dendrogram(row_clusters, labels=labels)
plt.tight_layout()
plt.ylabel('Euclidean Distance')
plt.show()

library(ggplot2)  # 시각화
library(dendextend)  # 덴드로그램 그리기

# 이전 단계에서 생성한 row_clusters를 덴드로그램으로 시각화
plot(as.dendrogram(row_clusters), main = "Dendrogram", ylab = "Euclidean Distance")

par(mar = c(5, 4, 2, 2))  # 여백 설정

위의 그림에서처럼 덴드로그램은 병합 계층적 군집이 수행되는 동안에 만들어지는 클러스터들을 요약해준다. 위의 그림에서는 ID_1 과 ID_2, ID_4 와 ID_0 그리고 ID_3 가 서로 유클리디안 거리가 가까운 군집이라고 할 수 있다. 

위의 과정은 알고리즘 과정을 순차적으로 작성한 코드였다. 하지만, 위의 내용을 쉽게 사용하기 위한 함수들이 존재하며, 구체적인 내용은 다음과 같다. 

from sklearn.cluster import AgglomerativeClustering

ac = AgglomerativeClustering(n_clusters=2, affinity='euclidean', linkage='complete')
labels = ac.fit_predict(x)
print("클러스터 레이블 : %s" % labels)

[실행 결과]
클러스터 레이블 : 클래스 레이블 : [0 1 1 0 0]

# 필요한 라이브러리 로드
library(stats)

# 유클리드 거리 계산
dist_matrix <- dist(x, method = "euclidean")

# 계층적 군집화 수행 (완전 연결, 유클리드 거리)
hclust_result <- hclust(dist_matrix, method = "complete")

# 클러스터 레이블 생성 (2개의 클러스터로 자르기)
labels <- cutree(hclust_result, k = 2)

# 클러스터 레이블 출력
cat("클러스터 레이블 : ", labels, "\n")

앞서 설명한 것처럼 ID_0과 ID_4 는 같은 클러스터로, ID_1, ID_2 가 같은 클러스터로 배정 받았다. 또한 ID_3의 경우는 ID_1, ID_2 보다는 ID_0, ID_4와 유사한 클러스터로 배정 받았다는 것을 알 수 있다.