버치

BIRCH(계층 구조를 사용한 균형 반복 축소 및 클러스터링)는 특히 대규모 데이터 ^[1]집합에 대한 계층적 클러스터링을 수행하는 데 사용되는 비감독 데이터 마이닝 알고리즘입니다.수정을 통해 기대-최대화 알고리즘을 ^[2]사용하여 k-평균 클러스터링 및 가우스 혼합물 모델링을 가속화하는 데도 사용할 수 있다.BIRCH의 장점은 주어진 리소스 세트(메모리 및 시간 제약)에 대해 최상의 품질의 클러스터링을 생성하기 위해 들어오는 다차원 메트릭 데이터 포인트를 증분 및 동적으로 클러스터링할 수 있다는 것입니다.대부분의 경우 BIRCH에서는 데이터베이스 스캔을 1회만 수행하면 됩니다.

개발자들은 BIRCH가 "데이터베이스 영역에서 '노이즈'(기본 패턴의 일부가 아닌 데이터 포인트)를 효과적으로 처리하기 위해 제안된 최초의 클러스터링 알고리즘"^[1]이라고 주장하여 DBSCAN을 2개월 차이로 앞섰습니다.BIRCH 알고리즘은 2006년에 ^[3]SIGMOD 10년 test of time 상을 받았습니다.

이전 방법의 문제

이전의 클러스터링 알고리즘은 매우 큰 데이터베이스에 비해 성능이 떨어졌으며 데이터 세트가 너무 커서 메인 메모리에 맞지 않는 경우를 적절하게 고려하지 않았습니다.그 결과, 높은 클러스터링 품질을 유지하면서 추가 IO(입출력) 작업에 드는 비용을 최소화하면서 많은 오버헤드가 발생하였습니다.또한, 대부분의 BIRCH의 전임자는 각 '클러스터링 결정'에 대해 모든 데이터 포인트(또는 현재 존재하는 모든 클러스터)를 동등하게 검사하고 이러한 데이터 포인트 간의 거리에 기초한 휴리스틱 가중치를 수행하지 않는다.

BIRCH의 이점

모든 데이터 포인트와 현재 존재하는 클러스터를 스캔하지 않고 클러스터링을 결정할 수 있다는 점에서 로컬입니다.데이터 공간이 일반적으로 균일하게 점유되지 않고 모든 데이터 점이 동일한 중요성은 아니라는 관찰을 활용합니다.I/O 비용을 최소화하면서 사용 가능한 메모리를 최대한 활용하여 가능한 최고의 서브 클러스터를 도출합니다.또한 전체 데이터 세트를 미리 필요로 하지 않는 증분 방식입니다.

알고리즘.

BIRCH 알고리즘은 실값 벡터로 표현되는 N개의 $데이터$ 포인트 세트와 원하는 수의 $클러스터$ K를 입력으로 받아들입니다.4단계로 동작하며, 그 중 2단계는 옵션입니다.

첫 번째 단계에서는 다음과 같이 정의된 높이 균형 트리 데이터 구조인 데이터 포인트에서 클러스터링 기능( $C$ F $\displaystyle$ CF $CF$ 을 구축합니다.

N개의 d차원 데이터 포인트 세트가 주어진 경우 세트의 클러스터링 $기능$ C $F$ ${\displaystyle$ $CF=(N,{\overrightarrow {LS}},SS)$ $}$ 는 $CF$ 트리플 $CF=(N,{\overrightarrow {LS}},SS)$ F $CF=(N,{\overrightarrow {LS}},SS)$ ( N $CF=(N,{\overrightarrow {LS}},SS)$ , $CF=(N,{\overrightarrow {LS}},SS)$ $CF=(N,{\overrightarrow {LS}},SS)$ $CF=(N,{\overrightarrow {LS}},SS)$ , $CF=(N,{\overrightarrow {LS}},SS)$ ) $CF=(N,{\overrightarrow {LS}},SS)$ { $displaystyle$ CF = ( N , { \ $overrightarrow {LS$ , $SS$ ) 로 정의됩니다.
- ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ i ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ i $→$ { $displaystyle$ { $overright$ arrow { $LS$ } = \ $sum$ _ { i ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ = $1$ }^{ $N$ } { \ $overright arrow$ { X _ { i ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ $}$ }} l sum sum sum the l l l l l l l 。
- $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ i $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ N ( $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ ) $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ {\ $displaystyle$ SS= $\sum$ _ ${i=1}^{N}({\overrightarrow {X_{i}}}^2}}$ 는 $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ 데이터 포인트의 제곱합이다.
클러스터링은 특징들이 CF나무, 두개의 매개 변수와height-balanced 나무:[해명 필요한]과 threshold T{T\displaystyle}요소 B{B\displaystyle}분지에. 각각의 리프가 아닌 노드는 형태의 대부분의 B{B\displaystyle}항목에서[CF나는, chid나는 l]{\displaystyle[CF_{나는},chi가 조직되어 있다.ld_{나는}해결}, $child_{i}$ i $child_{i}$ $child_{i}$ i { $display$ $style$ $child _$ {i $child_{i}$ }c and and and and and and and노드 $CF_{i}$ C F $CF_{i}$ { $displaystyle CF$ _ { $i$ }의 $CF_{i}$ 클러스터 $i$ 기능에 대한 포인터입니다.리프 노드에는 [ $[CF_{i}]$ $display$ [ $CF_{i}}$ 형식의 각 엔트리가 $최대$ L { $display$ L $}$ 개 $L$ 포함되어 있습니다.또한 모든 리프 노드를 연결하는 데 사용되는2개의 포인터가 있습니다.트리 사이즈는 $파라미터$ T({ $displaystyle$ T $T$ 에 따라 달라집니다. $사이즈$ P({ $displaystyle$ P $P$ 페이지에는 노드가 들어갑니다. $({displaystyle$ B $}$ $L$ L({ $displaystyle$ L $})$ 는 $L$ P({ $displaystyle$ P $P$ 에 의해 결정됩니다. $따라서$ 성능 $튜닝$ 에 따라 P(\ $displaystyle$ P $)$ 를 $P$ 변경할 수 있습니다.리프 노드의 각 엔트리는 단일 데이터 포인트가 아니라 하위 클러스터이기 때문에 데이터셋을 매우 간략하게 나타냅니다.

두 번째 단계에서 알고리즘은 첫 $번째$ $C$ F $트리$ 의 $CF$ 모든 리프 엔트리를 스캔하여 $작은$ C $트리$ 를 $CF$ 재구축하고 특이치를 삭제하고 혼잡한 서브클러스터를 큰 것으로 그룹화합니다.이 순서는, BIRCH 의 최초의 프레젠테이션에서는 옵션으로서 마크 되어 있습니다.

스텝 3에서는 기존의 클러스터링 알고리즘을 사용하여 모든 리프 엔트리를 클러스터링합니다.여기서 집적 계층 클러스터링 알고리즘은 $C$ $(\display$ style $CF$ $CF)$ 벡터로 표현되는 서브클러스터에 직접 적용됩니다.또한 사용자가 클러스터에 대해 원하는 수의 클러스터 또는 원하는 직경 임계값을 지정할 수 있는 유연성을 제공합니다.이 스텝 후에 데이터 내의 주요 분포 패턴을 캡처하는 클러스터 세트가 취득됩니다.다만, 옵션의 순서 4로 처리할 수 있는, 경미하고 현지화된 오차가 있는 경우가 있습니다.4단계에서는 3단계에서 생성된 클러스터의 중심체를 시드로 사용하고 데이터 포인트를 가장 가까운 시드로 재배포하여 새로운 클러스터 세트를 얻는다.4단계에서는 특이치를 삭제하는 옵션도 제공합니다.가장 가까운 씨앗에서 너무 멀리 떨어져 있는 점이 특이치로 취급될 수 있습니다.

클러스터링 기능을 사용한 계산

$CF=[N,{\overrightarrow {LS}},SS]$ $CF=[N,{\overrightarrow {LS}},SS]$ $CF=[N,{\overrightarrow {LS}},SS]$ F $CF=[N,{\overrightarrow {LS}},SS]$ [ $CF=[N,{\overrightarrow {LS}},SS]$ , $CF=[N,{\overrightarrow {LS}},SS]$ S $CF=[N,{\overrightarrow {LS}},SS]$ , $]$ { $display style$ CF = [N , ${\overrightarrow {LS}$ , $SS$ 만 주어진다면 기본 실제 값을 몰라도 동일한 측정값을 계산할 수 있습니다.

중심: ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}$
반지름 : $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}}}$ $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}}}$ i $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}}}$ $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}}}$ ( $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}}}$ i $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}}}$ - $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}}}$ $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}}}$ $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}}}$ + $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}}}$ - $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}}}$ C $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}}}$ l $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}}}$ → $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}}}$ L $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}}}$ $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}}}$ N $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}}}$ = $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}}}$ $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}}}$ - ( $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}}}$ $=$ N ) $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}}}$ (\ $style$ R $→$ 1 N ) _ $sum frcrt .$ $ot {\overright arrow {C}}\cdot {\overright arrow {LS}}{N}={sqrt {\frac {SS}}-({\frac {overright arrow {LS}}}}{2}}}}}$
$CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ C $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ [ $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ 1 , L $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ , $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ 1 $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ ]{ $displaystyle CF$ _ { $1}$ = [ $N$ _ { \ $overright$ arrow { $LS$ _ {1 $}$ } } 。 $SS_{1}]$ 및 $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ F $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ [ $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ , $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ 2 $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ , $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ $]$ { $display$ style $CF _$ ${2} =$ [ $N_{2}$ }, $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}}}}$ ${$ 2} $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ : $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}}}}$ 2 $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}}}}$ $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}}}}$ 1 $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}}}}$ $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}}}}$ $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}}}}$ $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}}}}$ $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}}}}$ $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}}}}$ $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}}}}$ ） $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}}}}$

다차원적인 경우에는 제곱근을 적절한 노름으로 대체해야 합니다.

BIRCH 클러스터링 기능의 수치 문제

안타깝게도 BIRCH에서 $(\displaystyle$ SS $)$ 라는 $SS$ 용어를 사용하는 것과 관련된 수치상의 문제가 있습니다. $D_{2}$ ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ - ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ ( ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ ) ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ ( \ $displaystyle$ { $frac$ { $SS$ } { $N$ } ) - { \ $big$ ( } { \ $frac$ { $LS$ $}$ } { $N$ } } $^{$ $2$ } $D_{2}$ 등 $D_{2}$ 거리에서 치명적인 취소 및 정밀도 저하가 발생할 수 있습니다 $.$ e 음수(그리고 제곱근은 ^[2]정의되지 않음)입니다.이 문제는 BETULA 클러스터 $CF=(N,\mu ,S)$ $CF=(N,\mu ,S)$ F $CF=(N,\mu ,S)$ ( $CF=(N,\mu ,S)$ , $CF=(N,\mu ,S)$ , $CF=(N,\mu ,S)$ S $CF=(N,\mu ,S)$ ) \ $displaystyle$ CF = ( $N$ , \ $mu$ , S ) \ displaystyle CF = ( N , \ mu , S $CF=(N,\mu ,S)$ ) 를 사용하여 $CF=(N,\mu ,S)$ 해결할 수 있습니다. 이 기능은 수치적으로 신뢰할 수 있는 온라인 알고리즘에 기반한 $수치$ N \ $displaystyle N$ $N$ μ, \ $\mu$ $\mu$ 및 편차의 합계를 저장합니다.이러한 특징의 경우 유사한 가감성 정리가 유지됩니다.제곱 편차에 대한 벡터를 각각 저장할 때, 결과 BIRCH CF-트리는 k-평균 클러스터링 및 계층적 응집적 클러스터링 외에 기대-최대화 알고리즘을 사용하여 가우스 혼합물 모델링을 가속화하는 데 사용될 수 있다.

메모들

^ ^a ^b 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. pp. 103–114. doi:10.1145/233269.233324.
^ ^a ^b Lang, Andreas; Schubert, Erich (2020), "BETULA: Numerically Stable CF-Trees for BIRCH Clustering", Similarity Search and Applications, pp. 281–296, arXiv:2006.12881, doi:10.1007/978-3-030-60936-8_22, ISBN 978-3-030-60935-1, S2CID 219980434, retrieved 2021-01-16
^ "2006 SIGMOD Test of Time Award". Archived from the original on 2010-05-23.

[birch-1] 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. pp. 103–114. doi:10.1145/233269.233324.

[:0-2] Lang, Andreas; Schubert, Erich (2020), "BETULA: Numerically Stable CF-Trees for BIRCH Clustering", Similarity Search and Applications, pp. 281–296, arXiv:2006.12881, doi:10.1007/978-3-030-60936-8_22, ISBN 978-3-030-60935-1, S2CID 219980434, retrieved 2021-01-16

[3] "2006 SIGMOD Test of Time Award". Archived from the original on 2010-05-23.

[1]

[2]

[3]

Search

버치

네임스페이스

더

목차

이전 방법의 문제

BIRCH의 이점

알고리즘.

클러스터링 기능을 사용한 계산

BIRCH 클러스터링 기능의 수치 문제

메모들