Метод BIRCH (balanced iterative reducing and clustering using hierarchies) или CF – tree

Как и все методы инкрементной кластеризации, данный метод использует древесную структуру данных CF – tree (Clustering Feature tree). Собственно, каждый кластер представляется некоторым вектором CF (Clustering Feature), являющимся тройкой:

, (50)

где N – количество точек в кластере, – линейная сумма этих точек (векторов), SS – сумма квадратов этих точек (векторов). Соответственно объединение кластеров представляется опять же вектором CF, полученным простой линейной суммой векторов CF объединяемых кластеров.

CF – tree – это дерево, характеризующееся двумя параметрами: коэффициентом ветвления B и пороговым значением T. B является значением максимально возможно числа потомков для узла. T определяется как минимальное общее внутреннее сходство кластера.

Объекты в такое дерево поступают последовательно и проходят по направлению от корневой вершины к листьям, пока не находят наиболее близкий лист. По достижении уровня листьев, объект добавляется в наиболее близкий лист, если при этом не происходит нарушения порогового значения T. Или же добавляется как лист, если есть для него еще место у родителя в соответствии с B.

Если эти условия не выполняются, то необходимо разделить листья, то есть разбить их родителя на два узла и распределить листья по ним. Разделение происходит разнесением листьев из наиболее удаленной пары по разным родителям и распределении остальных листьев по принципу близости первым двум.

После добавления объекта в качестве листа, необходимо обновить узлы на пути к данному листу. Если после разделения листьев, их количество потомков на уровне родителей перестало удовлетворять B, то всех потомков уровня родителей листьев необходимо разделить по аналогии с листьями и далее, вплоть до корневой вершины, если необходимо.