Метод DC – tree
Метод DC-tree (Document-Cluster Tree – «Дерево Кластеров Документов») [6] во многом аналогичен методу B+ - tree и BIRCH.
DC-tree – это дерево, имеющее четыре основных параметра: коэффициент ветвления B (максимальное число потомков); два критерия сходства S1 и S2, где 0 £ S1 и S2 £ 1; минимальное число потомков узла M.
Так же как и в методах иерархической кластеризации, в узлах этого дерева содержатся кластеры документов, листья являются самими документами. Более того, каждый лист может содержать не один документ, а несколько.
Критерий S1. Для повышения производительности алгоритма применяется этот критерий. Новый документ (или некий набор документов), продвигаясь по дереву, сначала на каждом уровне проверяется на близость каждому узлу. Если значение близости превышает значение критерия, то документ спускается на уровень ниже и сравнивается уже с потомками наиболее близкого ему узла на предыдущем уровне. Если не превышает, то он сам становиться потомком этого узла и, фактически, листом.
Критерий S2. Необязательно, чтобы каждый лист содержал отдельный документ. Таким образом, проверяется, не превышает ли значение близости вновь пришедшего документа к листьям дерева значения этого критерия и, если превышает, данный документ добавляется к этому листу. Таким образом, экономятся ресурсы и время.
Очевидно, что размер дерева зависит от этих двух критериев. А именно, глубина дерева прямо зависит от S1, а размер дерева от S2. Если установить S1 = 0, а S2 > 1, то DC-tree будет эквивалентно B+ - tree.
Опишем алгоритм добавления документа в такое дерево.
Шаг 1. Начиная с вершины дерева, документ рекурсивно спускается по дереву, выбирая на каждом уровне наиболее близкого, похожего ему потомка со значением сходства выше S1. Если такого потомка на каком-то уровне не находиться, то документ вставляется как новый лист дерева в свободное место для потомков соответствующего узла (действует коэффициент B). Если нет свободного места, то требуется деление потомков (см. ниже) узла.
Шаг 2. По достижении последнего уровня ищется самый близкий, сходный лист и проверяется, не превышает ли значение сходства критерия S2. Если превышает, то документ добавляется к этому листу. Иначе, добавляется как отдельный лист, если еще есть место у родителя. Иначе, опять же требуется деление листьев (см. ниже).
Шаг 3. Если произошло добавление документа в качестве листа к дереву, требуется обновить все узлы-предки на пути от этого листа до вершины дерева. При отсутствии деления, требуется просто просуммировать данный документ (вектор) вверх по дереву (пересчитать кластеры, то есть, фактически результирующие, средние вектора). При делении листьев, фактически происходит разделение их родителя и увеличение потомков на родительском уровне. Если их число превышает B, то требуется уже их деление и так далее до корневой вершины. Если вершина делиться, то глубина дерева увеличивается на 1 и образуется новая вершина.
Деление узлов.
Вместо того, чтобы добавлять нового потомка к узлу, уже содержащему B потомков, необходимо распределить набор B + 1 кластеров между двумя узлами. Разделение должно произойти таким образом, чтобы сходство между двумя новыми узлами было бы минимальным, а сходство между их потомками максимальным. Самый прямолинейное решение – простой перебор для нахождения оптимального деления. Однако количество вариантов слишком велико – 2B-1. Поэтому применяется следующий алгоритм.
Шаг 1. Для каждой пары кластеров подсчитывается значение их сходства. Выбирается пара с наименьшим сходством. Эти кластеры, образующие пару, считаются первыми элементами в своих группах.
Шаг 2. Если все кластеры были сгруппированы, то конец. Если нет, но какая-то группа имеет настолько мало кластеров, что все несгруппированные кластеры должны быть отнесены к ней, чтобы достичь минимального числа потомков M, то сделать это.
Шаг 3. Для каждого несгруппированного кластера подсчитать его сходство с кластерами, распределенными на шаге один и сгруппировать их на основе значения этого сходства.
Удаление и объединение узлов.
Если удаление какого-либо документа, как потомка какого-либо узла, не привело к тому, что число потомков стало меньше M для этого узла, то операция удаления считается завершенной. Иначе должна выполниться операция объединения узлов. Узел-родитель удаленного потомка объединяется с потомком своего родителя. Если операция объединения привела к тому, что условие минимального числа потомков перестало выполняться для узла-родителя объединенных узлов, то следует провести объединение и для него. Так, если данный процесс достигнет корневой вершины, глубина дерева уменьшается на 1.