Адекватность методов объединения кластеров задаче кластерного анализа документов

Далеко не все существующие методы объединения кластеров, непременно использующиеся в агломеративных иерархических методах кластеризации, подходят для задачи анализа объектов в многомерном пространстве. Поэтому, многие из иерархических методов кластеризации, использующие неадекватные методы объединения кластеров, становятся практически бесполезны в условиях нашей задачи. Так, методы объединения, основанные на средних векторах, центроидах, дают почти всегда неудовлетворительные результаты. Дело в том, что, поскольку пространство многомерно, эти средние вектора мало отличаются от друг друга, что приводит к разбиению плохого качества [23]. Так, например, может случиться ситуация, когда объединяемые кластеры ближе друг другу, чем какие-то объединенные на предыдущем шаге.

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

Из остальных, с проблемой различной формы и размера кластеров наилучшим образом справляются методы попарного среднего. Особенно, те из них, которые основаны не на локальной, а на глобальной близости через понятия взаимной связности, связи, соседства и т.д.

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

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

Метод дальнего соседа работает эффективно только на коллекциях документов с непересекающейся тематикой и формирует сферические кластеры.

Метод Варда более эффективен, но, в основном, за счет стремления создавать на начальном этапе кластеры небольших размеров, форму он не учитывает также. К тому же метод Варда чрезвычайно требователен к ресурсам.

Методы попарного среднего, а особенно взвешенного попарного среднего располагают гораздо большими возможностями для определения формы кластеров. Более того, иерархический кластерный анализ, основанный на этих методах, дает наилучшие результаты еще и потому, что, вместе с возможностью применения различных схем взвешивания, позволяет добиваться большей гибкости в определении качества получаемых кластеров, как в плане формы, так и плотности. Наиболее перспективные алгоритмы, такие как ROCK, CHAMELEON, используют тот же принцип объединения попарного среднего, существенно изменяя саму формулу, включая в нее новые факторы, учет которых приносит большую эффективность. При объединении используются количественные и качественные характеристики объектов и их связей (близости) в кластерах, что гораздо эффективнее исключает случайные объединения и способствует получению более качественной структуры набора данных (коллекции документов).