BIRCH

BIRCH는 특히 대규모 자료 집합에 대해 계층적 군집화를 수행하는 데 사용되는 비지도 데이터 마이닝 알고리즘이다.^[1] 수정을 거치면 K-평균 알고리즘 및 기댓값 최대화 알고리즘을 사용하는 가우시안 혼합 모델링을 가속하는 데에도 사용할 수 있다.^[2] BIRCH의 장점은 들어오는 다차원 메트릭 데이터 포인트를 점진적이고 동적으로 군집화하여 주어진 자원(메모리 및 시간 제약) 내에서 최상의 품질의 군집화를 생성하려 한다는 점이다. 대부분의 경우 BIRCH는 데이터베이스를 단 한 번만 스캔하면 된다.

개발자들은 BIRCH가 "데이터베이스 영역에서 '노이즈'(기본 패턴의 일부가 아닌 데이터 포인트)를 효과적으로 처리하도록 제안된 최초의 군집화 알고리즘"이라고 주장하며,^[1] DBSCAN보다 두 달 앞서 발표되었다. BIRCH 알고리즘은 2006년 SIGMOD 10년 테스트 오브 타임 어워드(Test of Time Award)를 수상했다.^[3]

이전 방식의 문제점

이전의 군집화 알고리즘들은 매우 큰 데이터베이스에서 성능이 떨어졌으며, 메인 메모리에 담기에 데이터 집합이 너무 클 경우를 충분히 고려하지 못했다. 결과적으로, 추가적인 입출력(IO) 작업 비용을 최소화하면서 높은 군집화 품질을 유지하는 데 많은 오버헤드가 발생했다. 게다가 BIRCH의 이전 알고리즘들은 대부분 '군집화 결정'을 내릴 때마다 모든 데이터 포인트(또는 현재 존재하는 모든 군집)를 동일하게 검사하며, 데이터 포인트 간의 거리에 기반한 휴리스틱 가중치를 수행하지 않는다.

BIRCH의 장점

각 군집화 결정이 모든 데이터 포인트와 현재 존재하는 군집을 스캔하지 않고도 이루어지므로 지역적(local)이다.
데이터 공간이 일반적으로 균일하게 채워져 있지 않으며 모든 데이터 포인트가 똑같이 중요하지는 않다는 관찰을 활용한다.
사용 가능한 메모리를 최대한 활용하여 가능한 가장 정밀한 하위 군집을 도출하는 동시에 I/O 비용을 최소화한다.
전체 자료 집합을 미리 필요로 하지 않는 점진적인 방법이기도 하다.

알고리즘

BIRCH 알고리즘은 입력값으로 $N$ 개의 데이터 포인트 집합(실수 벡터로 표현됨)과 원하는 군집의 수 $K$ 를 받는다. 이 알고리즘은 네 가지 단계로 작동하며, 두 번째 단계는 선택 사항이다.

첫 번째 단계에서는 데이터 포인트로부터 군집 특징( $CF$ ) 트리를 구축하는데, 이는 다음과 같이 정의되는 높이 균형 트리 자료 구조이다.

N개의 d차원 데이터 포인트 집합이 주어졌을 때, 해당 집합의 군집 특징 $CF$ $CF$ 는 세 쌍 $CF=(N,{\overrightarrow {LS}},SS)$ $CF=(N,{\overrightarrow {LS}},SS)$ 로 정의된다. 여기서
- ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ 는 선형 합이다.
- $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ 는 데이터 포인트의 제곱 합이다.
군집 특징은 분기 계수 $B$ 와 임계값 $T$ 라는 두 개의 매개변수를 가진 높이 균형 트리인 CF 트리에 구성된다. 각 비단말 노드는 최대 $B$ 개의 $[CF_{i},child_{i}]$ 형태의 엔트리를 포함하며, 여기서 $child_{i}$ 는 $i$ 번째 자식 노드에 대한 포인터이고 $CF_{i}$ 는 연관된 하위 군집을 나타내는 군집 특징이다. 단말 노드는 각각 $[CF_{i}]$ 형태의 최대 $L$ 개 엔트리를 포함한다. 또한 모든 단말 노드를 연결하는 이전 및 다음 포인터도 있다. 트리의 크기는 매개변수 $T$ 에 따라 달라진다. 노드는 크기 $P$ 인 페이지에 맞아야 한다. $B$ 와 $L$ 은 $P$ 에 의해 결정된다. 따라서 $P$ 를 조정하여 성능 튜닝을 할 수 있다. 단말 노드의 각 엔트리가 단일 데이터 포인트가 아니라 하위 군집이기 때문에 매우 압축된 데이터 집합 표현이 가능하다.

두 번째 단계에서 알고리즘은 초기 $CF$ 트리의 모든 단말 노드 엔트리를 스캔하여 더 작은 $CF$ 트리를 재구성하며, 이 과정에서 이상치를 제거하고 밀집된 하위 군집들을 더 큰 군집으로 묶는다. 이 단계는 BIRCH의 원래 제안에서 선택 사항으로 표시되어 있다.

세 번째 단계에서는 기존의 군집화 알고리즘을 사용하여 모든 단말 노드 엔트리를 군집화한다. 여기서는 응집형 계층적 군집화 알고리즘을 $CF$ 벡터로 표현된 하위 군집들에 직접 적용한다. 또한 사용자가 원하는 군집 수나 군집에 대한 원하는 지름 임계값을 지정할 수 있는 유연성을 제공한다. 이 단계를 거치면 데이터의 주요 분포 패턴을 포착하는 군집 집합을 얻을 수 있다. 그러나 사소하고 국소적인 부정확성이 존재할 수 있으며, 이는 선택적인 4단계에서 처리될 수 있다. 4단계에서는 3단계에서 생성된 군집의 중심을 시드로 사용하고 데이터 포인트를 가장 가까운 시드로 재분배하여 새로운 군집 집합을 얻는다. 4단계에서는 이상치를 버리는 옵션도 제공한다. 즉, 가장 가까운 시드에서 너무 멀리 떨어진 포인트는 이상치로 취급할 수 있다.

군집 특징을 이용한 계산

군집 특징 $CF=[N,{\overrightarrow {LS}},SS]$ 만 주어지면, 실제 기반 값을 알지 못해도 동일한 척도를 계산할 수 있다.

중심(Centroid): ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}$
반지름(Radius): $R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}$
군집 $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ 과 $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ 사이의 평균 연계 거리(Average Linkage Distance): $D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1}}\sum _{j=1}^{N_{2}}({\overrightarrow {X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\cdot SS_{2}+N_{2}\cdot SS_{1}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}$

다차원 사례에서는 제곱근을 적절한 노름(norm)으로 대체해야 한다.

BIRCH는 거리 D0에서 D3까지를 사용하여 가장 가까운 단말 노드를 찾고, 반지름 R 또는 지름 D를 사용하여 데이터를 기존 단말 노드에 흡수할지 아니면 새 단말 노드를 추가할지 결정한다.

BIRCH 군집 특징의 수치적 문제

안타깝게도 BIRCH에서 $SS$ 항을 사용하는 것과 관련된 수치적 문제가 있다. ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ 을 계산하거나 $D_{2}$ 와 같은 다른 거리 계산에서 유사한 식을 뺄 때, 심각한 취소가 발생하여 정밀도가 떨어질 수 있으며, 경우에 따라 결과가 음수가 되어 제곱근이 정의되지 않는 문제가 발생할 수 있다.^[2] 이는 대신 BETULA 군집 특징 $CF=(N,\mu ,S)$ 을 사용하여 해결할 수 있는데, 이는 개수 $N$ , 평균 $\mu$ , 그리고 분산 계산을 위한 더 신뢰할 수 있는 온라인 알고리즘에 기반한 제곱 편차의 합을 저장한다. 이러한 특징에 대해서도 유사한 가법 정리(additivity theorem)가 성립한다. 제곱 편차에 대해 벡터나 행렬을 저장할 때, 결과적으로 생성되는 BIRCH CF-트리는 K-평균 알고리즘 및 계층적 군집화 외에도 기댓값 최대화 알고리즘을 사용한 가우시안 혼합 모델링을 가속하는 데 사용될 수 있다.

선형 합과 제곱 합을 저장하는 대신, 각 군집 특징 $CF'=(N,\mu ,S)$ 에 평균 및 평균으로부터의 제곱 편차를 저장할 수 있다.^[4] 여기서

$n$ 은 노드 가중치(포인트 수)이다.
$\mu$ 는 노드 중심 벡터(산술 평균, 중심)이다.
$S$ 는 평균으로부터의 제곱 편차의 합(응용 프로그램에 따라 벡터 또는 메모리 절약을 위한 합)이다.

여기서 주요 차이점은 $S$ 가 원점이 아닌 중심을 기준으로 계산된다는 것이다.

단일 포인트 $x$ 는 군집 특징 $CF_{x}=(1,x,0)$ 으로 변환될 수 있다. 두 군집 특징 $CF_{AB}=CF_{A}+CF_{B}$ 를 결합하기 위해 다음을 사용한다.

$N_{AB}=N_{A}+N_{B}$
$\mu _{AB}=\mu _{A}+{\frac {N_{B}}{N_{AB}}}(\mu _{B}-\mu _{A})$ (평균의 점진적 업데이트)
$S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})\circ (\mu _{B}-\mu _{AB})$ (아다마르 곱을 사용한 벡터 형태)
$S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})^{T}(\mu _{B}-\mu _{AB})$ (제곱 편차의 스칼라 합 업데이트)

이 계산들은 유사한 제곱값들의 뺄셈을 피하는 수치적으로 더 신뢰할 수 있는 계산(분산의 온라인 계산 참조)을 사용한다. 중심은 단순히 노드 중심 벡터 $\mu$ 이며, 유클리드 거리나 맨해튼 거리 등을 사용한 거리 계산에 직접 사용할 수 있다. 반지름은 $R={\sqrt {{\frac {1}{N}}S}}$ 로, 지름은 $D={\sqrt {{\frac {2}{N-1}}S}}$ 로 간소화된다.

이제 BIRCH 알고리즘에서 사용되는 D0에서 D4까지의 다양한 거리를 다음과 같이 계산할 수 있다.^[4]

유클리드 거리 $D_{0}=\|\mu _{A}-\mu _{B}\|$ 와 맨해튼 거리 $D_{1}=\|\mu _{A}-\mu _{B}\|_{1}$ 은 CF 중심 $\mu$ 를 사용하여 계산된다.
군집 간 거리 $D_{2}={\sqrt {{\frac {1}{N_{A}}}S_{A}+{\frac {1}{N_{B}}}S_{B}+{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}$
군집 내 거리 $D_{3}={\sqrt {{\frac {2}{N_{AB}(N_{AB}-1)}}\left(N_{AB}(S_{A}+S_{B})+N_{A}N_{B}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}\right)}}$
분산 증가 거리 $D_{4}={\sqrt {{\frac {N_{A}N_{B}}{N_{AB}}}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}$

이 거리들은 선택한 연계(linkage)에 따라 계층적 군집화를 위한 거리 행렬을 초기화하는 데에도 사용할 수 있다. 정확한 계층적 군집화 및 K-평균 알고리즘을 위해서는 노드 가중치 $N$ 도 사용해야 한다.

군집화 단계

CF-트리는 데이터 집합에 대한 압축된 요약을 제공하지만, 단말 노드 자체는 매우 낮은 품질의 데이터 군집화만 제공한다. 두 번째 단계에서 단말 노드들은 다음과 같은 방법을 사용하여 군집화될 수 있다.

K-평균 알고리즘: 단말 노드들에 포인트 수 N만큼 가중치를 부여한다.
K-평균++: $(N,\mu ,S)$ 가 BETULA 군집 특징일 때, 이전 선택 중심을 $c_{i}$ 라 하면 $S+N\min _{i}||\mu -c_{i}||$ 에 비례하여 군집 특징을 샘플링한다.
가우시안 혼합 모델링: 분산 S도 고려할 수 있으며, 단말 노드가 공분산을 저장하는 경우 공분산도 고려된다.
계층적 군집화: 다음의 BIRCH 거리와 연계 간의 등가성을 사용하여 연계를 초기화할 수 있다.^[5]

HAC 연계와 BIRCH 거리 간의 대응 관계^[5]
HAC 연계	BIRCH 거리
UPGMA	D2²
WPGMA	D0²
워드법	2 D4²

가용성

ELKI에는 BIRCH와 BETULA가 포함되어 있다.
Scikit-learn에는 제한된 버전의 BIRCH가 포함되어 있는데, 이는 D0 거리와 정적 임계값만 지원하며 군집화 단계에서 단말 노드의 중심만을 사용한다.^[6]

각주

1 2 Zhang, T.; Ramakrishnan, R.; Livny, M. (1996). 〈BIRCH: an efficient data clustering method for very large databases〉. 《Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96》. 103–114쪽. doi:10.1145/233269.233324.
1 2 Lang, Andreas; Schubert, Erich (2020), “BETULA: Numerically Stable CF-Trees for BIRCH Clustering” (영어), 《Similarity Search and Applications》, 281–296쪽, arXiv:2006.12881, doi:10.1007/978-3-030-60936-8_22, ISBN 978-3-030-60935-1, S2CID 219980434, 2021년 1월 16일에 확인함
↑ “2006 SIGMOD Test of Time Award”. 2010년 5월 23일에 원본 문서에서 보존된 문서.
1 2 Lang, Andreas; Schubert, Erich (2022). “BETULA: Fast clustering of large data with improved BIRCH CF-Trees” (영어). 《Information Systems》 108. doi:10.1016/j.is.2021.101918.
1 2 Schubert, Erich; Lang, Andreas (2022년 12월 31일), “5 Cluster Analysis” (영어), 《Machine Learning under Resource Constraints - Fundamentals》 (De Gruyter), 215–226쪽, arXiv:2309.02552, doi:10.1515/9783110785944-005, ISBN 978-3-11-078594-4
↑ as discussed in

[birch-1] 1 2 Zhang, T.; Ramakrishnan, R.; Livny, M. (1996). 〈BIRCH: an efficient data clustering method for very large databases〉. 《Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96》. 103–114쪽. doi:10.1145/233269.233324.

[:0-2] 1 2 Lang, Andreas; Schubert, Erich (2020), “BETULA: Numerically Stable CF-Trees for BIRCH Clustering” (영어), 《Similarity Search and Applications》, 281–296쪽, arXiv:2006.12881, doi:10.1007/978-3-030-60936-8_22, ISBN 978-3-030-60935-1, S2CID 219980434, 2021년 1월 16일에 확인함

[3] “2006 SIGMOD Test of Time Award”. 2010년 5월 23일에 원본 문서에서 보존된 문서.

[:1-4] 1 2 Lang, Andreas; Schubert, Erich (2022). “BETULA: Fast clustering of large data with improved BIRCH CF-Trees” (영어). 《Information Systems》 108. doi:10.1016/j.is.2021.101918.

[corr-5] 1 2 Schubert, Erich; Lang, Andreas (2022년 12월 31일), “5 Cluster Analysis” (영어), 《Machine Learning under Resource Constraints - Fundamentals》 (De Gruyter), 215–226쪽, arXiv:2309.02552, doi:10.1515/9783110785944-005, ISBN 978-3-11-078594-4

[6] s discussed in

[1]

[2]

[3]

[4]

[5]

[6]