Hierarchical Clustering이란? (Agglomerative Hierarchical Clustering, Divisive Hierarchical Clustering)

 Hierarchcical Clustering(Hierarchical cluster analysis, HCA), 즉 계층적 군집 분석은 말 그대로 데이터 하나하나를 계층에 따라 순차적으로 클러스터링 하는 기법이다. 이번 포스팅에서는 Hierarchical Clustering이 무엇인지에 대해 알아보겠다. 

 

알고리즘

우선, Agglomerative Hierarchical Clustering의 알고리즘에 대해 설명하도록 하겠다. 이 알고리즘은 각 데이터가 모두 나눠져있는 상태에서, 작은 단위로부터 클러스터링을 시작하여 모든 데이터를 묶을 때까지 반복하는 Bottom Up 방식으로 클러스터링을 진행한다. 다음과 같은 예시 데이터가 있다고 하자. 각 원은 하나의 데이터를 말한다. 우리는 이 6개의 데이터에 대해 클러스터링을 진행할 것이다.

 

Clustering의 대상이 되는 예시 데이터

1. 가장 거리가 가까운 데이터를 찾고, 이들을 묶는다.

우선, 가장 거리가 가까운 데이터를 찾는다. 우리의 예시에서는 2와 5가 될 것이다. (각 데이터 사이의 거리를 어떻게 구하는지 궁금하다면, 다음 포스팅을 참고한다.) 이 2와 5 데이터를 다음 그림과 같이 하나의 클러스터로 묶어준다.

2와 5 데이터가 하나의 클러스터가 된 모습

2. 1을 모든 데이터가 하나의 클러스터로 묶일 때까지 반복한다.

이제 1에서 했던 데이터 사이의 거리가 가장 가까운 데이터를 하나의 클러스터로 묶어주는 작업을 반복하기만 하면 된다. 다음으로 거리가 가까운 데이터는 3과 6일 것이다. 이들을 묶어준다.

3과 6 데이터가 하나의 클러스터가 된 모습

이제 다음으로 묶을 데이터를 살펴 본다. 3 6 클러스터와 4 데이터가 가장 거리가 가까워 보이므로 이들을 하나의 클러스터로 묶어야할 것 같다. (클러스터와 데이터, 클러스터와 클러스터 사이의 거리 측정 방법은 아래에서 추가적으로 설명한다.) 이들을 묶어준다. 

3, 4, 6 데이터가 하나의 클러스터가 된 모습

이런 식으로 모든 데이터가 하나의 클러스터로 묶일 때까지 알고리즘을 반복하면 다음과 같은 결과가 된다.

알고리즘 종료 시 클러스터의 모습

이 종료된 클러스터를 덴드로그램(Dendrogram)으로 표현하면 다음과 같다. 이 때, 각 덴드로그램의 수평선 높이는 클러스터가 만들어진 순서대로 정해진다. 우리의 예시에서는 2 5가 가장 먼저 하나의 클러스터로 묶이고, 다음으로 36, 436이 묶였기 때문에 25 클러스터의 가로선이 가장 아래, 36이 그 위, 346이 그 위 순서가 된다. 

클러스터를 덴드로그램으로 표현한 모습

3. 클러스터를 나눈다.

 이제 원하는 개수로 클러스터를 나누면 된다. 예를 들어, 두 개의 클러스터를 원한다면 다음과 같이 덴드로그램을 자르면 된다. 그러면 364 클러스터가 하나, 152 클러스터가 하나 만들어질 것이다.

두 개의 클러스터로 자른 모습

 만약 3개의 클러스터를 원한다면 어떻게 해야할까? 다음 그림과 같이 덴드로그램을 자르면 될 것이다. 그러면 364, 1, 52가 각 클러스터가 될 것이다.

세 개의 클러스터로 자른 모습

이렇게 우리는 Agglomerative Hierarchical Clustering에 대해 알아보았다. 이와 반대되는 개념으로는 Divisive Hierarchical Clustering이 있다. 이는 전체 데이터를 하나의 클러스터로 묶고 시작하는 Top down 방식으로 클러스터링을 진행한다. 

 

Cluster의 거리 측정

 우리는 데이터와 데이터 사이의 거리를 측정하는 방법에 대해 알고있다. 하지만 클러스터와 클러스터 사이의 거리는 어떻게 측정할 수 있을까? (데이터와 클러스터의 거리는 데이터를 원소가 하나인 클러스터로 취급하여 계산한다.) 이에는 여러 가지 방법이 있는데, 이번 포스팅에서는 네 가지 방법을 소개하려고 한다.

클러스터의 거리 측정 방법

Maximum (Complete Linkage Clustering)

각 클러스터 내 데이터 사이의 가장 긴 거리를 두 클러스터 사이의 거리로 생각한다. 즉, 가장 비슷하지 않은 두 데이터의 거리를 두 클러스터 사이의 거리로 정의한다.

Minimum (Single Linkage Clustering)

각 클러스터 내 데이터 사이의 가장 짧은 거리를 두 클러스터 사이의 거리로 생각한다. 즉, 가장 비슷한 두 데이터의 거리를 두 클러스터 사이의 거리로 정의한다.

Mean

각 클러스터 내 모든 데이터의 거리의 평균을 두 클러스터 사이의 거리로 생각한다.

Centroid Linkage

각 클러스터의 중앙값 사이의 거리를 두 클러스터 사이의 거리로 생각한다.

 

이러한 거리 측정 방법 중 적절한 방법을 이용해 Hierarchical Clustering 알고리즘이 진행된다.

 

 이번 포스팅에서는 Hierarchical Clustering이 무엇인지에 대해 알아보았다. Hierarchical Clustering은 K-means Clustering과는 달리 알고리즘이 시작되기 전에 클러스터의 개수를 미리 정의해주지 않아도 된다는 장점을 가진다. 상황에 따른 적절한 Clustering 방법을 활용하면 좋을 것이다.