군집분석의 의미 및 종류(2)

4. 계층적 군집분석

1) 계층적 군집분석의 절차

계층적 군집분석의 절차는 다음과 같은 형태입니다.

 

계층적 군집분석 절차

 

1. 각 관측치를 군집으로 정의하여 데이터 수만큼의 군집을 지정합니다.

2. 각 군집과 군집 간 거리들을 모두 계산합니다.

3. 가장 작은 거리를 갖는 두 개의 군집을 찾아 이를 하나의 군집으로 결합합니다.

4. 모든 관측치를 포함하는 하나의 군집이 형성될 때까지 앞의 두 단계를 계속 반복합니다.

 

2) 계층적 군집분석 예시

예시를 통해서 계층적 군집분석 알고리즘을 다시 한번 살펴보겠습니다. 

 

다음과 같이 5쌍의 x, y 데이터가 있을 때, 이를 그래프로 나타내면 아래와 같은 형태입니다.

 

 

각각의 데이터끼리의 거리를 구해보면 아래와 같습니다. 

이때, 가장 거리가 가까운 점은 P1과 P2이므로 이 두 점을 하나의 군집으로 묶어주게 됩니다.

 

 

군집 간의 거리를 구하는 방법은 크게 4가지로 나눌 수 있습니다.

 

군집간의 거리를 구하는 방법

 

첫 번째 그림은 최단연결방법(Single-link)으로 한 군집의 데이터와 다른 군집의 데이터 간의 길이 중 가장 짧은 거리를 기준으로 하는 방법입니다.

 

두 번째 그림은 최장 연결방법(Complete-link)으로 한 군집의 데이터와 다른 군집의 데이터 간의 길이 중 가장 긴 거리를 기준으로 하는 방법입니다.

 

세 번째 그림은, 평균 연결방법(Average-link)으로 한 군집의 각 데이터와 다른 군집의 각 데이터 간의 평균 거리를 이용한 방법입니다.

 

마지막 그림은 중심 연결방법(Centroid distance)으로 두 군집들의 centroids 간의 거리를 기준으로 하는 방법입니다.

 

 

이 네가지 방법 중에서 우리는 단일 연결법(Single-link)을 이용한 거리 행렬을 구해보겠습니다.

 

앞서, p1과 p2를 하나의 군집으로 묶었기 때문에

각 데이터와 이 군집의 거리는 각 데이터와 군집의 데이터들 간의 거리 중 더 작은 값을 선택하게 됩니다. 

 

 

거리 행렬을 구해보면 아래와 같은 결과가 나와 p4와 p5를 하나의 군집으로 만들어 주게 됩니다.

 

 

이와 같은 방법을 반복하다 보면 아래와 같이 결국, 하나의 군집으로 만들어 지게 됩니다. 

 

 

여기서 우리가 원하는 수만큼의 군집으로 나누고 싶으면, 

덴드로그램을 원하는 수의 군집 부분에서 잘라서 구해주면 됩니다.