BIRCH는 계층을 사용하여 균형 잡힌 반복 감소 및 클러스터링을 나타냅니다. 계층적 클러스터링 및 반복적 분할을 포함한 기타 클러스터링 방법을 통합하여 방대한 양의 숫자 레코드를 클러스터링하도록 설계되었습니다.
BIRCH는 클러스터링 기능과 클러스터링 기능 트리(CF 트리)의 두 가지 개념을 제공하며, 이는 클러스터 설명을 요약하는 데 사용됩니다. 이러한 구조는 클러스터링 방법을 촉진하여 거대한 데이터베이스에서 최고의 속도와 확장성을 달성하고 들어오는 개체의 증분 및 동적 클러스터링에 효과적입니다.
클러스터에서 n개의 d차원 데이터 개체 또는 점이 주어지면 중심 x0를 나타낼 수 있습니다. , 반경 R 및 클러스터의 직경 D는 다음과 같습니다. -
$$x_{0}=\frac{\sum_{i=1}^{n}x_{i}}{n}$$
$$R=\sqrt{\frac{\sum_{i=1}^{n}(x_{i}-x_{0})^{2}}{n}}$$
$$D=\sqrt{\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}(x_{i}-x_{j})^{2}}{n (n-1)}}$$
여기서 R은 구성원 요소에서 중심까지의 평균 거리이고 D는 클러스터 내부의 평균 쌍별 거리입니다. R과 D는 모두 중심 주위에 있는 클러스터의 견고함을 반대로 합니다. 클러스터링 기능(CF)은 개체 클러스터에 대한 데이터를 요약하는 3차원 벡터입니다. 클러스터에서 n개의 d차원 객체 또는 점이 주어지면 {xi }, 클러스터의 CF는 다음과 같이 표현됩니다.
CF=(n,LL,SS)
여기서 n은 클러스터의 포인트 수, LS는 n포인트의 선형 합 $\sum_{i=1}^{n}(x_{i})$, SS는 데이터 포인트의 제곱합입니다. (즉,$\sum_{i=1}^{n}x_{i}^{2}$)
클러스터링 기능은 주어진 클러스터에 대한 통계 요약입니다. 통계적 관점에서 클러스터의 0번째, 첫 번째 및 두 번째 순간입니다. 클러스터링 기능은 추가 기능입니다. 예를 들어, 일반적으로 클러스터링 기능인 CF1 및 CF2를 보유하는 두 개의 분리된 클러스터 C1 및 C2가 있다고 가정합니다. C1과 C2를 결합하여 형성되는 클러스터의 클러스터링 기능은 단순히 CF1 + CF2입니다.
클러스터링 기능은 BIRCH에서 클러스터링 결정을 개발하는 데 필요한 모든 측정값을 계산하는 데 충분합니다. BIRCH는 클러스터링 기능을 사용하여 개체 클러스터에 대한 데이터를 요약함으로써 스토리지를 효율적으로 사용하므로 모든 개체를 저장해야 하는 요구 사항을 우회합니다.
CF 트리는 계층적 클러스터링을 위해 클러스터링 기능을 저장하는 높이 균형 트리입니다. 트리의 리프가 아닌 노드에는 하위 항목 또는 "자식"이 있습니다. 리프가 아닌 노드는 자식의 CF 합계를 저장하므로 자식에 대한 클러스터링 데이터를 요약합니다.
CF 트리에는 분기 요소 B와 임계값 T를 포함하는 두 개의 매개변수가 있습니다. 분기 요소는 잎이 아닌 노드당 최대 자식 수를 정의합니다. 임계값 매개변수는 트리의 리프 노드에 저장된 하위 클러스터의 최대 지름을 정의합니다. 이 두 매개변수는 결과 트리의 크기를 유지합니다.