[모델 알고리즘][군집] HDBSCAN

[모델 알고리즘][군집] HDBSCAN

◈ '군집' 목차 ◈

1. K-평균

2. DBSCAN

3. HDBSCAN

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

4. 평균-이동

5. 병합 군집

6. BIRCH, 유사도 전파, 스펙트럼 군집

1. HDBSCAN 알고리즘

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

step1 . Transform the space

데이터 셋의 값들을 density/sparcity 의미를 포함한 값으로 변환한다. (muutal 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 계산 공식>

from http://lets-start-data.tistory.com/56 by ccl(A) rewrite - 2021-08-13 23:00:37