계층적 군집화

계층적 군집(Hierarchical Clustering)은 n개의 군집으로 시작해 점차 군집의 개수를 줄여 나가는 방법입니다.

 

유클리디안 거리를 사용해서 계층적 군집분석을 시행해 보겠습니다.

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

X = np.array([[1, 4], [2, 1], [4, 6], [4, 3], [5, 1]])
labels = ['a', 'b', 'c', 'd', 'e']

plt.figure(figsize=(7, 7))
plt.xlim(0, 7)
plt.ylim(0, 7)
plt.scatter(X[:, 0], X[:, 1])
for label, x, y in zip(labels, X[:, 0], X[:, 1]):
    plt.annotate(
        label,
        xy=(x, y), xytext=(-3, 3),
        textcoords='offset points', ha='right', va='bottom')
plt.show()

 

 

 

 

 

 

최단연결법 (single linkage)

군집간 거리를 측정할 때, 가장 가까운 데이터 포인트끼리 거리를 측정하여 병합합니다.

	x	y
a	1	4
b	2	1
c	4	6
d	4	3
e	5	1

위와 같은 데이터셋이 있을 때 거리행렬을 계산하면

	a	b	c	d
a
b	\(\sqrt{10}\)
c	\(\sqrt{13}\)	\(\sqrt{29}\)
d	\(\sqrt{10}\)	\(\sqrt{8}\)	\(\sqrt{9}\)
e	\(\sqrt{25}\)	\(\sqrt{9}\)	\(\sqrt{26}\)	\(\sqrt{5}\)

이 때 거리가 가장 짧은 d와 e가 군집을 형성합니다.

 

{d, e}를 하나의 군집으로 보고 다음 거리행렬을 재계산하면

	a	b	c
a
b	\(\sqrt{10}\)
c	\(\sqrt{13}\)	\(\sqrt{29}\)
{d, e}	\(\sqrt{10}\)	\(\sqrt{8}\)	\(\sqrt{9}\)

{d, e}라는 군집과 {a}라는 군집간의 거리를 계산할 때

a와 가장 가까운 d와의 거리가 군집간의 거리가 됩니다.

 

최종적으로 덴드로그램을 그리면 다음과 같습니다.

plt.figure(figsize=(7, 7))
dendrogram(linkage(X, 'single'),
           orientation='top',
           distance_sort='descending',
           labels=labels,
           show_leaf_counts=True)
plt.show()

군집을 4개 형성하려면 {d, e}, {a}, {b}, {c}

3개 형성하려면 {d, e, b}, {a}, {c}

2개 형성하려면 {d, e, b, c}, {a} 가 됩니다.

 

파이썬에서는 scipy.cluster.hierarchy 클래스의 linkage 함수를 이용합니다.

linkage(X, 'single')

>>>
array([[3.        , 4.        , 2.23606798, 2.        ],
       [1.        , 5.        , 2.82842712, 3.        ],
       [2.        , 6.        , 3.        , 4.        ],
       [0.        , 7.        , 3.16227766, 5.        ]])

해석하면 다음과 같습니다.

 

1행 : 3번포인트와 4번포인트 (d와 e)가 거리 2.24로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 5번포인트가 됩니다.

 

2행 : 1번포인트와 5번포인트(b와 군집{d, e})가 거리 2.83으로 가장 짧아 군집을 형성합니다. 이 때 크기는 3입니다.

여기서 만들어진 군집은 6번 포인트가 됩니다.

 

3행 : 2번 포인트와 6번포인트(c와 군집{b, d, e})가 거리 3으로 가장 짧아 군집을 형성합니다. 이 때 크기는 4입니다.

여기서 만들어진 군집은 7번 포인트가 됩니다.

 

4행 : 0번 포인트와 7번포인트(a와 군집{b, c, d, e})가 거리 3.16으로 가장 짧아 군집을 형성합니다. 이 때 크기는 5입니다.

거리 3.16은 최단연결법이므로 군집{b, c, d, e}와 가장 가까운 점인 a와의 거리 \(\sqrt{10}\)입니다.

 

 

 

 

 

 

 

 

최장연결법(complete linkage)

군집간 거리를 측정할 때, 가장 먼 데이터 포인트끼리 거리를 측정하여 병합합니다.

	a	b	c
a
b	\(\sqrt{10}\)
c	\(\sqrt{13}\)	\(\sqrt{29}\)
{d, e}	\(\sqrt{25}\)	\(\sqrt{9}\)	\(\sqrt{26}\)

군집 {d, e}와 {a} 사이의 거리를 측정할 때 {a}와 가장 먼 e포인트와 거리를 측정합니다.

linkage(X, 'complete')

>>>
array([[3.        , 4.        , 2.23606798, 2.        ],
       [1.        , 5.        , 3.        , 3.        ],
       [0.        , 2.        , 3.60555128, 2.        ],
       [6.        , 7.        , 5.38516481, 5.        ]])

1행 : 3번포인트와 4번포인트 (d와 e)가 거리 2.24로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 5번포인트가 됩니다.

 

2행 : 1번포인트와 5번포인트(b와 군집{d, e})가 거리 3으로 가장 짧아 군집을 형성합니다. 이 때 크기는 3입니다.

여기서 만들어진 군집은 6번 포인트가 됩니다.

 

3행 : 0번 포인트와 2번포인트(a와 c)가 거리 3.61로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 7번 포인트가 됩니다.

 

4행 : 6번 포인트와 7번포인트(군집{a, c}와 군집{b, d, e})가 거리 5.39로 가장 짧아 군집을 형성합니다. 이 때 크기는 5입니다.

거리 5.39는 최장연결법이므로 군집{a, c}와 군집{b, d, e}중 가장 먼 점 사이의 거리인 b와 c 사이의 거리 \(\sqrt{29}\)입니다.

 

 

 

 

 

 

 

평균연결법(avearge linkage)

군집간 모든 포인터들의 거리의 평균으로 거리를 측정하여 병합합니다.

	a	b	c
a
b	\(\sqrt{10}\)
c	\(\sqrt{13}\)	\(\sqrt{29}\)
{d, e}	\(\frac{\sqrt{10} + \sqrt{25}}{2}\)	\(\frac{\sqrt{8} + \sqrt{9}}{2}\)	\(\frac{\sqrt{9} + \sqrt{26}}{2}\)

linkage(X, 'average')

>>>
array([[3.        , 4.        , 2.23606798, 2.        ],
       [1.        , 5.        , 2.91421356, 3.        ],
       [0.        , 2.        , 3.60555128, 2.        ],
       [6.        , 7.        , 4.13478994, 5.        ]])

1행 : 3번포인트와 4번포인트 (d와 e)가 거리 2.24로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 5번포인트가 됩니다.

 

2행 : 1번포인트와 5번포인트(b와 군집{d, e})가 거리 2.91으로 가장 짧아 군집을 형성합니다. 이 때 크기는 3입니다.

여기서 만들어진 군집은 6번 포인트가 됩니다.

 

3행 : 0번 포인트와 2번포인트(a와 c)가 거리 3.61로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 7번 포인트가 됩니다.

 

4행 : 6번 포인트와 7번포인트(군집{a, c}와 군집{b, d, e})가 거리 4.13으로 가장 짧아 군집을 형성합니다. 이 때 크기는 5입니다.

거리 4.13은 평균연결법이므로 군집{a, c}와 군집{b, d, e} 사이의 모든 데이터들의 거리의 평균입니다.

\(\frac{\sqrt{10}+\sqrt{10}+\sqrt{25}+\sqrt{29}+\sqrt{9}+\sqrt{26}}{6}=4.13\)

	a	b	c	d
a
b	\(\sqrt{10}\)
c	\(\sqrt{13}\)	\(\sqrt{29}\)
d	\(\sqrt{10}\)	\(\sqrt{8}\)	\(\sqrt{9}\)
e	\(\sqrt{25}\)	\(\sqrt{9}\)	\(\sqrt{26}\)	\(\sqrt{5}\)

 

 

 

 

중심연결법(centroid linkage)

군집 내 모든 포인터들의 중심을 기준으로 군집간 거리를 측정하여 병합합니다.

	a	b	c
a
b	\(\sqrt{10}\)
c	\(\sqrt{13}\)	\(\sqrt{29}\)
{d, e}	\(\sqrt{16.25}\)	\(\sqrt{7.25}\)	\(\sqrt{16.25}\)

linkage(X, 'centroid')

>>>
array([[3.        , 4.        , 2.23606798, 2.        ],
       [1.        , 5.        , 2.6925824 , 3.        ],
       [0.        , 6.        , 3.54338194, 4.        ],
       [2.        , 7.        , 3.88104367, 5.        ]])

1행 : 3번포인트와 4번포인트 (d와 e)가 거리 2.24로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 5번포인트가 됩니다.

 

2행 : 1번포인트와 5번포인트(b와 군집{d, e})가 거리 2.69로 가장 짧아 군집을 형성합니다. 이 때 크기는 3입니다.

여기서 만들어진 군집은 6번 포인트가 됩니다.

 

3행 : 0번 포인트와 6번포인트(a와 군집{b, d, e})가 거리 3.54로 가장 짧아 군집을 형성합니다. 이 때 크기는 4입니다.

여기서 만들어진 군집은 7번 포인트가 됩니다.

 

4행 : 2번 포인트와 7번포인트(c와 군집{a, b, d, e})가 거리 3.88로 가장 짧아 군집을 형성합니다. 이 때 크기는 5입니다.

거리 3.88은 중심연결법이므로 c(1, 4)와 군집{a, b, d, e}의 중심(3, 2.25)사이의 거리 \(\sqrt{15.0625}=3.88\)입니다.

 

 

 

 

 

 

 

 

와드연결법(ward linkage)

군집내 편차들의 제곱합을 고려한 방법입니다.

그렇기 때문에 이상치에 둔감하지만 수식도 복잡하고, 계산량이 매우 많습니다.

특히 수식의 경우 대부분의 블로그들이 잘못 안내하고 있어 올바른 수식을 구하는데 애를 먹었습니다.

 

계산식은 다음과 같습니다.

해석하면 두 군집 사이의 거리는 두 군집내의 모든 데이터들과 그 중심과의 거리의 제곱합에서

각 군집내의 모든 데이터들과 그 중심사이의 거리의 제곱합을 빼주고 2를 곱해서 루트를 씌우면 됩니다.

linkage(X, 'ward')

>>>
array([[3.        , 4.        , 2.23606798, 2.        ],
       [1.        , 5.        , 3.10912635, 3.        ],
       [0.        , 2.        , 3.60555128, 2.        ],
       [6.        , 7.        , 5.47113638, 5.        ]])

1행 : 3번포인트와 4번포인트 (d와 e)가 거리 2.24로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 5번포인트가 됩니다.

 

2행 : 1번포인트와 5번포인트(b와 군집{d, e})가 거리 3.11로 가장 짧아 군집을 형성합니다. 이 때 크기는 3입니다.

여기서 만들어진 군집은 6번 포인트가 됩니다.

 

두 군집내 모든 데이터들과 그 중심사이의 거리의 제곱합은

\(dist(b, (b + d + e) / 3)^2+dist(d, (b + d + e) / 3)^2+dist(e, (b + d + e) / 3)^2 = 7.33\)

군집 b는 데이터가 하나이므로 제곱합은0

군집 {d, e}는 \(dist(d, (d + e) / 2)^2 + dist(e, (d + e) / 2)^2 = 2.5\)

따라서 b와 군집{d, e}사이의 와드거리는

\(\sqrt{2 \times (7.33 - 0 - 2.5)} = 3.11\)

(여기서 dist(a, b)는 두 점 사이의 거리)

 

3행 : 0번 포인트와 2번포인트(a와 c)가 거리 3.61로 가장 짧아 군집을 형성합니다. 이 때 크기는 2입니다.

여기서 만들어진 군집은 7번 포인트가 됩니다.

 

4행 : 6번 포인트와 7번포인트(군집{a, c}와 군집{b, d, e})가 거리 5.47로 가장 짧아 군집을 형성합니다. 이 때 크기는 5입니다.

 

두 군집내 모든 데이터들과 그 중심사이의 거리의 제곱합은

\(dist(a, (a + b + c + d + e) / 5)^2 + dist(b, (a + b + c + d + e) / 5)^2 + dist(c, (a + b + c + d + e) / 5)^2 + \)

\(dist(d, (a + b + c + d + e) / 5)^2 +  dist(e, (a + b + c + d + e) / 5)^2 = 28.8\)

군집 {a, c}는 \(dist(a, (a + c) / 2)^2 + dist(c, (a + c) / 2)^2 = 6.5\)

군집 {b, d, e}는 \(dist(b, (b + d + e) / 3)^2 + dist(d, (b + d + e) / 3)^2 + dist(e, (b + d + e) / 3)^2 = 7.33\)

따라서 군집{a, c}와 군집{b, d, e}사이의 와드거리는

\(\sqrt{2 \times (28.8 - 6.5 - 7.33)} = 5.47\)

(여기서 dist(a, b)는 두 점 사이의 거리)

 

 

 

이상으로 계층적 군집화 방법에 대해 알아보았습니다.

 

 

github

MachineLearning/계층적 군집분석.ipynb at main · Tripleler/MachineLearning (github.com)