2015-04-01
658
Существует множество методов кластерного анализа. Основные из них появились еще в 60-е годы. Различные алгоритмы кластеризации были разработаны в основном для нужд числового анализа. Некоторые из этих методов были адаптированы для систем информационного поиска, в том, числе и для решения проблем кластеризации документов.
Многократные попытки классификации методов кластерного анализа приводят к десяткам, а то и сотням разнообразных классов. Такое многообразие порождается большим количеством возможных способов вычисления расстояния между отдельными наблюдениями, не меньшим количеством методов вычисления расстояния между отдельными кластерами в процессе кластеризации и многообразными оценками оптимальности конечной кластерной структуры.
Выделяются основные два класса методов кластеризации: разделяющие и иерархические. Основное их различие в структуре получаемых кластеров. Разделяющие на выходе предлагают набор выделенных в коллекции документов классов, причем, как правило, число классов должно быть задано заранее. Иерархические не имеют такого ограничения и строят вложенную иерархию кластеров.
|
|
|
Выбор класса методов ограничивается направленностью нашей задачи, поскольку она включает в себя не только цель получения тематических групп документов, но и создание иерархической структуры коллекции. Можно сделать вывод, что для задачи кластерного анализа документов наилучшим образом подходят иерархические методы, поскольку они могут получить таксономию корпуса документов. Однако, большинство таких методов имеет как серьезные ограничения в адекватности получаемых разбиений, так и в производительности.
Основными проблемами большинства кластерных методов, причем не только иерархических, которые необходимо преодолевать для успешного выполнения нашей задачи являются:
- большая размерность пространства;
- большой объем анализируемых данных;
- зависимость от вводимых параметров, определяющих результат анализа.
Часто неспособность обойти вышеперечисленные проблемы заключается в недостатках метода объединения кластеров, если речь идет об агломеративных методах. Иногда, методы становятся бесполезными из-за своей низкой производительности на фоне большой размерности и объема данных.
Тем не менее, не так давно, появились алгоритмы, серьезно улучшающие характеристики иерархической кластеризации и при этом обладающие приемлемой производительностью.
Иерархические методы дают на выходе вложенную последовательность с единственным, включающим все остальные, кластером на вершине и простыми кластерами, не включающими в себя другие на самом низком уровне иерархии. Результат действия по такому алгоритму можно представить графически как дерево, именуемое дендрограммой (от греческого dendron - дерево), отражающее процесс агломерации, слияния отдельных наблюдений в единый окончательный кластер. На нем (Рисунок 5) наглядно представляется процесс «склеивания» кластеров и получения промежуточных уровней дерева [3].
|
|
|
Рисунок 5 – Дендрограмма иерархического кластерного анализа
Такое представление является серьезным преимуществом данного метода, поскольку помимо непосредственного объединения документов в классы, происходит разбиение документов на иерархически связанные классы, то есть сохраняется систематика набора документов.
Выделяют два основных подхода к созданию такой системы кластеров.
Агломеративный (накапливающий) подход. Начиная с элементарных сущностей (документов), происходит их последовательное объединение в кластеры. Для этого подхода важно понятие сходства кластеров и расстояния между кластерами. В основном все предлагаемые алгоритмы отличаются именно стратегией объединения.
Дивизивный (делимый) подход. Начиная с одного, включающего в себя все сущности (документы) кластера, происходит последовательное разбиение кластеров, вплоть до получения элементарных сущностей (документов). На каждом шаге необходимо принимать решение: какой кластер разделить и как произвести разделение. Дивизивными является большинство графо-ориентированных методов, построенных на последовательном разделении графа.
