[군집] HDBSCAN

◈  '군집' 목차 ◈

1. K-평균

2. DBSCAN

3. HDBSCAN

     HDBSCAN 알고리즘에 대해 알아보자.

4. 병합 군집

5. 평균-이동

6. BIRCH

7. 유사도 전파

8. 스펙트럼 군집

9. 가우시안 혼합 모델

10. 베이즈 가우시안 혼합 모델

---

1. HDBSCAN 알고리즘

DBSCAN과 비교했을 때, epsilon은 필요 없다. Minpst 만 존재한다. 

 

step1. Transform the space

데이터 셋의 값들을 density/sparcity 의미를 포함한 값으로 변환한다. (muutal reachability distance 값)

 

<mutual reachability distance>

 

 

step2. MST 생성

밀집도가 높은 cluster 찾기 위해, 모든 point 간의 d_m_reach-k(p,q) 값 관련 데이터 셋을 얻었다. data point를 꼭지점으로 d_m_reach-k(p,q) 를 선으로 하여 weighted graph를 구성한다. graph의 모든 노드들을 순회하며 가장 낮은 weight 순으로 선을 추가하며 weighted graph를 그린다. 

 

 

 

step3. cluster hierarchy 구축

MST가 주어지면, 이를 connected components 들의 계층 구조로 변환한다. MST에서 distance가 작은 선부터 순회하면 새로운 클러스터에 합쳐준다. 

 

 

 

step4. Condense the cluster tree

노드로부터 갈라진 left와 right 리프 갯수가 모두 Minpst 이상이면 각각 새로운 cluster에 할당하고, 그게 아니면 모두 부모 cluster에 넣는다. 복잡한 cluster tree를 단순하게 압축한다. 

 

 

step5. Extract the clusters

좀 더 stable한 cluster 를 선택해야 한다. 

 

모든 리프 component를 독립된 클러스터로 선택하고 connected component의 계층 tree를 DFS로 순회한다. 

두 자식(left, right) 클러스터 stability 합 > 부모 stability 라면, 부모 노드와 자식 노드를 합쳐 하나의 클러스터로 생성한다.  

두 자식(left, right) 클러스터 stability 합 < 부모 stability 라면, 자식 노드는 제외하고 부모 노드만 선택해 클러스터로 생성한다. 

 

<stability 를 고려한 클러스터 선택 과정>

 

<클러스터의 stability 계산 공식>