Методы инкрементной кластеризации документов

Метод B⁺ – tree

B⁺ - tree – это дерево отвечающее следующим условиям [35]:

- корневая вершина имеет более одного потомка;

- промежуточные узлы имеют m/2 или более потомков, где m – коэффициент ветвления;

- все листья находятся на одинаковом расстоянии от корневой вершины.

В приближении к задаче кластерного анализа документов, листья B+ – дерева – это документы, а промежуточные узлы – кластеры, их содержащие.

Предположим, в такое дерево добавляется документ. Тогда, начиная с самого корня и вниз по дереву, вектор данного документа сравнивается с каждым кластером и, если величина сходства превышает некий заданный критерий, то документ добавляет в данный кластер, то есть становиться потомком некоего узла, представляющего кластер. Если данный узел уже содержит m потомков, то требуется разделение узла. Если разделение происходит на всех уровнях выше, вплоть до корневой вершины, то глубина дерева увеличивается на 1.