BIRCH

군집 특징을 이용한 계산

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

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

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

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

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

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

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

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

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

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

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