[군집] BIRCH

◈  '군집' 목차 ◈

1. K-평균

2. DBSCAN

3. HDBSCAN

4. 병합군집

5. 평균-이동

6. BIRCH

     BIRCH 군집 알고리즘에 대해 알아보자.

7. 유사도 전파

8. 스펙트럼 군집

9. 가우시안 혼합 모델

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

---

1. BIRCH

BIRCH는 특별히 대규모 데이터 셋을 위해 고안되었다.

BIRCH는 한 번만 데이터에 대해 검사하여 클러스터를 만들며

새로운 데이터에 대해 클러스터링할 때, 모든 데이터나 클러스터를 스캔하지 않고도 클러스터링할 수 있다.

 

훈련 과정에서 새로운 샘플을 클러스터에 빠르게 할당할 수 있는 정보를 담은 트리 구조 CF-tree 를 만든다.

특성 개수가 너무 많지 않다면(20개 이하) 배치 k-평균보다 빠르고 비슷한 결과를 만든다.

 

설정한 일정 반경 내 존재하는 데이터에 대한 정보를 CF 에 담는다.

CF에 담기는 구체적인 정보는 다음과 같다.

 

CF-tree는 CF에 대해  인접 클러스터끼리 묶으며 계층적 트리 구조를 생성한다.

이때 트리 구조의 가장 아래 노드를 leaf Node 라 하고, 가장 위 노드를 Root 라 한다.

leaf Node 도 아니고 root 도 아닌 노드를 Non-leaf Node 라 한다.

 

 

CF-tree 바탕으로 진행되는 BIRCH 알고리즘은 다음과 같다. 

 

step1

모든 데이터를 스캔하고 초기 메모리에 CF-tree 를 만든다.

 

step2 

옵션으로 리프 항목을 검색하여 아웃라이어를 탐색하고 서브 클러스터를 통합하며 CF-tree를 바람직한 길이로 압축한다.

 

step3

모든 리프 노드 엔트리를 CF 값 기준으로 글로벌 클러스터링을 한다. 

 

 

 

기존 데이터로 만들어진 CF-tree 바탕으로 새로운 엔트리가 들어왔을 경우 다음과 같이 진행된다. 

 

 step1

Root 노드부터 거리에 따라 가까운 자식 노드를 선택하면 CF-tree 를 타고 내려간다.

다시 말해 거리가 가장 가까운 leaf 노드를 찾는다.

 

 

 

step2

leaf 노드 도달 시, 가장 가까운 leaf 엔트리가 임계 조건을 위반하지 않고 새로운 엔트리를 흡수할 수 있는 지 확인한다.

만약 흡수 가능하다면 업데이트 되지만, sub cluster 가 지닐 수 있는 최대 엔트리 갯수를 초과한다면 쪼개서 저장해야 하고 수정된 leaf 노드에 맞춰서 non leaf 노드의 CF 및 경로를 업데이트 한다. 

 

 

 

step3

가까운 노드를 찾아서 병합하기도 한다.

 

 

 

2. Birch 클래스

◎ from sklearn.cluster import Birch

사이킷런에서 Birch 클래스를 통해 구현할 수 있다.

 

Birch 클래스의 몇 가지 매개 변수를 살펴보자.

˙threshold : 샘플로부터 subcluster 생성하기 위한 적정 반경

˙branching_factor : 각 노드 내에 존재할 수 있는 최대 CF subcluster 갯수

 

from sklearn.cluster import Birch
brc = Birch(n_clusters=None)
brc.fit(X)
brc.Predict(X)

 

▶ BIRCH 클래스 구현에 대해 더 자세히 알고 싶다면 >>  참고 URL -  Birch