Метод B+ – tree
B+ - tree – это дерево отвечающее следующим условиям [35]:
- корневая вершина имеет более одного потомка;
- промежуточные узлы имеют m/2 или более потомков, где m – коэффициент ветвления;
- все листья находятся на одинаковом расстоянии от корневой вершины.
В приближении к задаче кластерного анализа документов, листья B+ – дерева – это документы, а промежуточные узлы – кластеры, их содержащие.
Предположим, в такое дерево добавляется документ. Тогда, начиная с самого корня и вниз по дереву, вектор данного документа сравнивается с каждым кластером и, если величина сходства превышает некий заданный критерий, то документ добавляет в данный кластер, то есть становиться потомком некоего узла, представляющего кластер. Если данный узел уже содержит m потомков, то требуется разделение узла. Если разделение происходит на всех уровнях выше, вплоть до корневой вершины, то глубина дерева увеличивается на 1.