Hierarchical Clustering 알고리즘 개념

/*

 * http://sosal.kr/

 * made by so_Sal

 */

 

 

 

 

계층적 클러스터링의 종류

 

1) Single (nearest-neighbour) : 두 클러스터간 거리를 두 클러스터의 멤버간 거리 중 가장 짧은 것으로 봅니다.

2) Complete (furthest neighbour) : 두 클러스터간 거리를 두 클러스터의 멤버간 거리 중 가장 긴 것으로 봅니다.

3) Centroid : 두 클러스터간 거리를 각 클러스터의 Multivariate mean간의 거리로 봅니다.

4) Average : 두 클러스터간 거리를 두 클러스터의 모든 멤버간 거리의 평균(average)으로 봅니다.

5) Median : 두 클러스터간 거리를 두 클러스터의 모든 멤버간 거리의 중앙값(median)으로 봅니다.

6) Ward : 두 클러스터간 거리를 두 클러스터의 모든 멤버간 거리의 평균(median)으로 보는데, 단, 공분산을 고려한 보정을 해줍니다.

출처: http://blog.daum.net/etineye/20

계층적 클러스터링에서 Single (nearest-neighbour) 의 예제입니다.

그림으로 최대한 이해하기 쉽게 그리려고 노력했습니다 ^^.

Distance Matrix에서 거리가 짧은 두개의 Data를 먼저 묶는다.

A와 D의 거리는 2이고, 가장 가깝기 때문에 A와 D를 하나의 그룹으로 선정한다. 

 

A와 D가 가장 가까운 Distance를 가지기 때문에 A-D 2개의 데이터를 묶는다.

A와 D가 묶였기 떄문에, A-D는 하나의 군집으로 처리되며,

Single(nearest-neighbour) 알고리즘에서는 A-D 군집과 B의 거리는 A-B, D-B의 거리 중 작은 값으로 처리한다.

A-D 군집과 B의 거리 측정 -

A-B의 거리(20)  <  D-B의 거리(25)

Single 알고리즘에서는 가장 작은값로 처리하기 때문에, AD와 B의 거리는 20이 된다.

마찬가지로 A-C(7) > D-C(3) 이므로

A-D 군집과 C의 거리는 3이 된다.

AD를 군집으로 묶었을 때, distance matrix의 결과이다.

이런식으로 Matrix의 Row와 Column을 한칸씩 줄여나가면서 그룹화 한다.

이제 Row, Column은 3개가 남았으며 3개의 노드를 이용하여 다시 Hierarchical clustering을 재현한다.

 

 

노드간의 연결을 계속 반복하면 결국 마지막 2개의 노드만이 남는 순간이 오는데

이땐 그냥 바로 연결해주면 끝.

 

결과입니다.

Hierarchical clustering의 결과는 (((AD)C)B) 이런 모양이 되겠네요.

물론 단순히 괄호로 묶는건 그룹간의 distance를 알 수 없으니, 위와같이 그래프로 표시해주면 좋겠습니다.