[Hierarchical Clustering] BIRCH - with 1 DB Scan

BIRCH

Balanced Interative Reducing and Clustering using Hiearhcies

 

방법

BIRCH는 CF(Clustering Feature) tree를 통해 1 DB scan만으로 대략적인 cluster 구조를 파악한다.

 

1. (1 DB scan) DB를 scan하면서 in-memory CF tree를 구성한다.
2. (optional) CF-tree의 leaf nodes에 임의의 clustering algorithm을 적용해서 clustering 결과를 보완할 수 있다.

 

장단점

• 장점 : scales linearly
  • 1 scan 만으로 괜찮은 clustering 결과를 찾고 추가적인 scan을 통해 quality를 개선한다.
  • 때문에 linear한 cost를 가진다.
• 단점
  • numeric data에 대해서만 적용이 가능하다.
  • data records의 순서에 민감하다.
    • 같은 데이터이더라도 data records 순서에 따라 결과가 달라질 수 있다.

 

---

Clustering Feature

메모리를 많이 차지하지 않고도 cluster의 형태를 관리할 수 있는 자료구조이다.

모든 objects를 기억하지 않아도 된다.

 

Cluster의 statistic 정보를 담고 있다.

 

 

예시

 

---

CF-Tree

특징

• height-balanced tree : root부터 모든 leaf 까지의 height이 동일하다.
• leaf node : clustering feature를 가진다.
• non-leaf node
  • non-leaf node는 children을 가진다.
  • 각 non-leaf node에는 children의 clustering feature의 합을 저장한다.
• 두 개의 parameter를 가진다. → 적절히 선택해야 한다.
  
  • branching factor
    • 최대 children 수
    • 한 노드는 몇 개의 children을 가질 것인가
  • threshold
    • leaf node에 저장될 cluster의 최대 diameter
    • 어디까지를 cluster로 보고 어느 범위 밖을 다른 cluster로 볼 것인가
• 각 level은 전체 데이터에 대한 clustering strucutre를 의미한다.

 

구성 방법

1. initial state : null root node
2. DB에서 object를 꺼낸다.
3. 어느 node에 더 가까운지 비교하면서 삽입한다. → cf 각 요소의 값을 갱신한다.
4. 지름이 threshold를 넘으면 새로운 cluster를 형성한다.
5. node를 split할 때는
   • 중심이 가까운 것 끼리 모아서 나누고
   • 나눠진 것들의 parent를 형성한다.
6. DB의 모든 object에 대해 2-5 과정을 반복한다.