MathClustering

계층적 클러스터링

Clustering, Math, 계층적 클러스터링

계층적 클러스터링은 하나의 데이터 샘플을 하나의 클러스터로 보고 가장 유사도가 높은 클러스터를 합치면서 클러스터 갯수를 줄여 가는 방법을 말한다.

클러스터간의 거리 측정

클러스터간의 비유사도(dissimilarity) 혹은 거리(distance)를 측정하는 방법에는 다음과 같은 것이 있다.

비귀납적 방법

centroid

두 클러스터의 중심점(centroid)를 정의한 다음 두 중심점의 거리를 클러스터간의 거리로 정의한다.

여기에서 $c_u$ 와 $c_v$ 각각 두 클러스터 $u$ 와 $v$ 의 중심점이다.

single

클러스터 $u$ 의 모든 데이터 $i$ 와 클러스터 $v$ 의 모든 데이터 $j$ 의 모든 조합에 대해 거리를 측정해서 최소값을 구한다. 최소 거리(Nearest Point) 방법이라고도 한다.

complete

클러스터 $u$ 의 모든 데이터 $i$ 와 클러스터 $v$ 의 모든 데이터 $j$ 의 모든 조합에 대해 거리를 측정한 후 가장 큰 값을 구한다. Farthest Point Algorithm 또는 Voor Hees Algorithm 이라고 한다.

average

클러스터 $u$ 의 모든 데이터 $i$ 와 클러스터 $v$ 의 모든 데이터 $j$ 의 모든 조합에 대해 거리를 측정한 후 평균을 구한다. $|u|$ 와 $|v|$ 는 각각 두 클러스터의 원소의 갯수를 뜻한다.

귀납적 방법

median

이 방법은 Agglomerative Clustering에서 사용할 수 있는 귀납적 방법으로 centroid 방법의 변형이다. 만약 클러스터 $u$가 클러스터 $s$ 와 클러스터 $t$ 가 결합하여 생겼다면 클러스터 $u$ 의 중심점은 새로 계산하지 않고 원래 클러스터의 두 클러스터의 중심점의 평균을 사용한다.

weighted

이 방법은 Agglomeratice Clustering 에서 사용할 수 있는 귀납적 방법이다. 만약 클러스터 $u$ 가 클러스터 $s$ 와 클러스터 $t$ 가 결합하여 생겼다면 다음과 같이 원래 클러스터까지의 두 거리의 평균을 사용한다.

Ward

이 방법은 Agglomerative Clustering 에서 사용할 수 있는 귀납적 방법이다. 만약 클러스터 $u$ 가 클러스터 $s$ 와 클러스터 $t$ 가 결합하여 생겼다면 다음과 같이 두 클러스터 거리의 가중 평균에서 원래의 두 클러스터 사이의 거리를 보정한 값을 사용한다.

이 식에서 $|\cdot|$ 기호는 클러스터의 원소의 갯수를 말한다.

SciPy의 계층적 클러스터링

파이썬으로 계층적 클러스터링을 하려면 SciPy 패키지의 linkage 명령을 사용하거나 scikit-learn 패키지의 AgglomerativeClustering 클래스를 사용한다. 각각 장단점이 있는데 SciPy 패키지는 tree 형태로 시각화해주는 dendrogram 명령도 지원한다.

MNIST digit 이미지 중 20개의 이미지를 무작위로 골라 계층적 클러스터링을 적용해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from sklearn.datasets import load_digits

digits = load_digits()
n_image = 20
np.random.seed(0)
idx = np.random.choice(range(len(digits.images)), n_image)
X = digits.data[idx]
images = digits.images[idx]

plt.figure(figsize=(12, 1))
for i in range(n_image):
    plt.subplot(1, n_image, i + 1)
    plt.imshow(images[i], cmap=plt.cm.bone)
    plt.grid(False)
    plt.xticks(())
    plt.yticks(())
    plt.title(i)

1
2
3
4
from scipy.cluster.hierarchy import linkage, dendrogram

Z = linkage(X, 'ward')
Z

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from matplotlib.offsetbox import OffsetImage, AnnotationBbox

plt.figure(figsize=(10, 4))
ax = plt.subplot()

ddata = dendrogram(Z)

dcoord = np.array(ddata["dcoord"])
icoord = np.array(ddata["icoord"])
leaves = np.array(ddata["leaves"])
idx = np.argsort(dcoord[:, 2])
dcoord = dcoord[idx, :]
icoord = icoord[idx, :]
idx = np.argsort(Z[:, :2].ravel())
label_pos = icoord[:, 1:3].ravel()[idx][:20]

for i in range(20):
    imagebox = OffsetImage(images[i], cmap=plt.cm.bone_r, interpolation="bilinear", zoom=3)
    ab = AnnotationBbox(imagebox, (label_pos[i], 0),  box_alignment=(0.5, -0.1), 
                        bboxprops={"edgecolor" : "none"})
    ax.add_artist(ab)

plt.show()

Share