[Cluster Analysis] Hierarchical Clustering

Hierarchical Clustering

Clustering을 하는 기준으로 distance matrix를 이용한다.

 

몇 개의 cluster로 나눌 지 결정할 필요 없다.

단, 몇 개로 나뉘었을 때 중단할지나 cluster 내 최대 distance 등 termination condition을 정해주어야 한다.

 

계층을 구성하는 방법에 따라 agglomerative나 divisive로 나눌 수 있다.

• bottom-up : agglomerative
  
  • leaf부터 root까지 구성해나간다.
  • 가장 가까운 것 끼리 묶어 나간다.
  • 예 : AGNES
• top-down : divisive
  
  • root부터 leaf까지 구성해나간다.
  • 가장 가까운 것들끼리 분리해 나간다.
  • 예 : DIANA

 

Advanced Hierarchical Clustering Method

AGNES나 DIANA는 cost가 $O(n^2)$에 비례하기 때문에 scalability가 낮다.

때문에 large datacost에 적용하기 힘들다.

 

이를 극복한 방법은 아래와 같이 있다.

• BIRCH : CF-tree를 이용함으로써 sub-cluster의 quality를 높인다.
• ROCK : neighbor와 link analysis를 통해 categorical data clustering을 한다.
• CHAMELEON : dynamic modeling을 통해 clustering을 수행한다.