Hierarchical Clustering

이전 포스팅에서 Partitioning Clustering Method 들 몇가지에 대해 다뤘다.

Hierarchical Clustering도 Distance를 기준으로 클러스터링을 수행한다는 점은 partitioning method와 일관적이다.

아래의 Hierarchical Clustering Method의 특징을 살펴보며 그 개념을 이해해보자.

 

특징

1. k (클러스터의 수)를 미리 정하지 않아도 된다. 단, 종료조건 (termination condition)

 

2. Top Down 방식과 Bottom Up 방식이 있다.

Top Down 방식은 DIANA, Bottom Up 방식은 AGNES가 대표적이다.

아래 그림을 통해 두 방식의 차이를 대략적으로 이해할 수 있다.

 

3. Dendrogram을 이용해 Termination Condition을 정한다.

여기서 Dendrogram은 클러스터의 Hierarchy를 표현하는 Tree로 이해할 수 있다.

(아래 그림 참고)

---

 

AGNES (AGglomerative NESting)

AGNES는 대표적인 Bottom Up 방식의 클러스터링 기법이다.

아래 특징과 작동방식을 간단히 살펴보자.

 

# Distance

클러스터 간 거리를 계산할 때, single-link method를 사용한다.

 

# 개쉬운 Steps

1) 가장 dissimilarity가 적은 (가장 가까운.) 노드를 Merge한다.

2) 모든 node가 같은 클러스터가 될 때까지 반복

---

 

DIANA(DIvisive ANAlysis)

AGNES의 inverse 버전이다.

작동방식 또한 비슷하다. 아래 step을 확인하자.

 

# Steps

1) 모든 object들로 구성된, 하나의 큰 클러스터에서 시작

2) 가능한 가장 큰 두 개의 클러스터로 split

3) 모든 클러스터가 single object로 구성될 때까지 반복 (총 n-1 step)

 

# Complexity in the First Step

AGNES처럼 간단하게 끝나면 가장 좋겠지만, 첫 단계의 시간복잡도가 크다는 점에서 개선이 필요하다.

가장 큰 두 개의 클러스터를 찾기 위해서는 아래 경우의 수 만큼의 조합을 테스트해보아야 한다.

$$2^{n-1}-1$$

 

# Detailed Steps to Avoid All Possibilities

위처럼 처음 단계에서 모든 조합의 경우의 수를 구하는 것이 불가능하기 때문에, 아래와 같은 추가적인 단계들이 더 필요하다.

 

1)  평균 dissimilarity가 가장 큰, 수장 object를 찾아 splinter group 형성

수장 object를 찾았을 기점에서는, splinter group은 해당 object 하나만 속해있을 것이다.

 

2) splinter group에 없는 object 'i' 각각에 대해 D를 계산

D는, 모든 i에 대해, splinter group으로 옮겨가는 것이 cost가 적은지, 아니면 원래 그룹에 남아있는 것이 cost가 적은지 결정하는 역할을 한다.

 $$D_{i} = [average \ d(i, j) \ for\ splinter \ group] - [average \ d(i, j) \ for\ non-splinter \ group]$$

 

3) D가 가장 큰 object h를 찾기 & splinter group 변경

h를 찾은 후에, h의 D가 음수라면 (splinter group으로 h를 옮기는 것이 나은 상태) h를 splinter group에 추가한다.

 

4) 모든 D가 음수일 때까지 step 2와 3을 반복

모든 반복이 끝난 시점에는, 데이터가 두 개의 그룹으로 split된 상태일 것이다. (splinter group / rest)

 

5) 다음 split cluster 정하기

다음으로 split될 cluster는, diameter가 가장 큰 그룹이 선택된다.

(선택 이후에는, 처음부터 반복.)

 

6) 하나의 object만 남을 때까지 모든 단계를 반복