클러스터링과 계층적 군집 분석(Hierarchical Clustering)

지금까지 알아본 K-Means와 DBSCAN은 비지도학습 + 분할 군집(Partition Clustering)이었다. 이번엔 계층적 군집 분석에 대해 자세히 알아보자.

■ 덴드로그램(Dendrogram)과 2가지 접근방식(응집형 / 분리형)

트리 구조를 갖는 다이어그램을 덴드로그램이라고 한다. y축은 군집과의 거리를 보여준다.

덴드로그램은 응집형(Agglomerative)과 분리형(Divisive)으로 표현할 수 있다. 응집형은 bottom-up 접근 방식인데 처음 시작할 때 모든 데이터가 각각의 군집으로 시작해서 주변과 병합해나가는 방식이다. 분리형은 top-down 접근으로, 시작할 때 모든 데이터가 하나의 군집으로 시작해서 분리해나가는 방식이다. 자세한 이미지는 다음 블로그에 잘 나와있다.

■ 덴드로그램의 장점: 클러스터 개수를 내 맘대로!

덴드로그램의 장점은 클러스터의 개수를 지정하지 않아도 된다는 점이다. 결과를 보고, 덴드로그램을 잘라서(첫 번째 이미지에서 그래프를 점선으로 자르는 행위) 원하는 수준의 군집을 나눌 수 있다.

덴드로그램은 생물학의 분류나 고객군의 분류에서 많이 사용한다.

■ 군집과 군집의 거리를 측정하는 방법

그동안 우리가 구한 ‘거리’는 모두 하나의 데이터 포인트와 또 다른 데이터 포인트의 거리였다. 덴드로그램에서 관심있는 것은 하나의 데이터 포인트와 군집과의 거리 또는 군집과 군집간의 거리이다.

먼저 개별 데이터 포인트에서 시작하여 Proximity matrix을 그린다. proximity matrix는 하나의 데이터 포인트와 다른 데이터 포인트 간의 유클리드 거리를 행렬로 표시한 것이다.

그 뒤, 거리가 가까운 데이터 포인트끼리 병합을 하여 군집으로 만든다. 이제 두 개의 군집 간의 거리를 계산해야한다. 군집을 어떻게 나누는지에 따라 4개의 접근 방식- 최단연결법(Single Link), 최장연결법(Complete Link), 평균연결법(Group Average), 중심연결법(Distance Between Centroids)-이 있다.

■ 최단연결법과 최장연결법

최단연결법은 두 개의 군집에서 가장 가까운 데이터 포인트끼리의 거리를 구하는 방식이다. 그림으로 살펴보자.

데이터포인트 3,6이 1번 군집이고, 2,5가 2번 군집이고, 4와 1은 개별 군집이라고 가정해보자. 이제 군집의 병합을 위해 군집 간의 거리를 구하려고 한다. 현재 데이터 포인트 2와 3 사이의 거리가 4나 1보다 더 가까우니까 2가 속한 군집과 병합한다. 즉, 3번 군집은 데이터 포인트 2, 3, 5, 6를 가진 군집이 된다.

최장연결법은 그 반대다. 두 개의 군집 내에 있는 모든 데이터 포인트끼리 쌍을 지어 그 거리가 가장 먼 데이터 포인트를 구한다.

1번 군집과 2번 군집이 있을 때부터 살펴보자(가장 가까운 거리에 있는 데이터끼리 군집을 이루는 것은 최장연결법에서도 동일하게 이뤄진다). 데이터 포인트 6과 4의 거리, 6과 5의 거리, 6과 1의 거리를 구하면 6과 5의 거리가 가장 멀다는 것을 알 수 있다. 따라서 군집 3으로 병합되는 것은 4이다.

이제 1의 관점에서 가장 먼 거리를 구하면 1과 4이다. 따라서 군집 4로 병합되는 것은 1, 2, 5이다. 위의 최단연결법으로 군집을 나눈 것과 상당히 다름을 알 수 있다.

정리해보자면 최단연결법은 타원형이 아닌 모양에도 쓸 수 있지만 아웃라이어에 취약하다. 최장연결법은 노이즈나 아웃라이어에는 강하나 원형으로 군집을 생성하려는 경향이 강하고, 큰 군집을 쪼개려는 경향을 가진다.

■ 평균연결법

최단연결법과 최장연결법을 합친 것이 평균연결법이다. 평균연결법은 두 개의 군집 내 데이터 포인트 쌍의 거리를 평균낸다. 최단연결법과 최장연결법의 트레이드 오프적인 관계를 중화하나 계산 비용이 높다는 단점이 있다. 위의 예제를 평균연결법으로 계산하면 다음과 같다.

평균연결법은 노이즈와 아웃라이어에 강하나 클러스터의 모양이 원형이 된다는 한계점을 가진다.

즉, 데이터의 형태와 분석하려는 목적을 고려해서 적절히 어떤 접근 방식을 취할 것인지 선택하는 것이 중요하겠다.

■ 계층적 클러스터링의 문제점

계층적 클러스터링의 최대 문제점은 greedy algorithm이라는 점이다. 한 번 병합이 되거나 분리된 군집은 다시 되돌릴 수 없다.

또한 앞서 알아본 것처럼 군집 간의 거리를 어떻게 계산하는지에 따라 노이즈와 아웃라이어에 취약하거나, 복잡한 군집을 다루지 못하는 등의 한계를 갖게 된다.

게다가 계층적 클러스터링은 상대적으로 계산 비용이 더 높다. Proximity matrix를 사용하기 때문에 데이터 포인트가 천개라면 그 제곱인 백만번을 계산해야한다.