3
.docx3.2. Рассмотрение отдельных алгоритмов
3.2.1. Метод k - средних и его разновидности
Метод к-средних (k-means) или метод динамических ядер — один из самых простых в реализации методов. Данный метод предполагает предварительное задание числа кластеров. В начале работы алгоритма выбираются центральные точки кластеров. На каждой итерации такая точка приписывается к тому кластеру, к центральной точке которого он ближе всего расположен. После этого рассчитывается среднее значение координат всех точек, которые вошли в определенный кластер, и это среднее значение и становится центральной точкой данного кластера. Итерации повторяются до тех пор, пока алгоритм не сойдется. Разновидности данного алгоритма можно классифицировать по следующим признакам:
• в зависимости от того, как вычисляются центры кластеров: k-means (средние значения), k-median (медианы);
• в зависимости от того, как вычисляются начальные значения: случайно, алгоритмом k-means++;
• в зависимости от того, может ли документ входить в несколько кластеров одновременно: четкие и нечеткие.
3.2.2. Алгоритм ЕМ
Метод k-средних является частным случаем алгоритма ЕМ (ехресtanсу–maximisation), который основывается на предположении, что множество можно описать как линейную комбинацию нормальных распределений. Задача алгоритма состоит в нахождении таких параметров (математического ожидания и дисперсии) [2].
3.2.3. Иерархические алгоритмы
Алгоритмы данного типа предполагают на каждой итерации производить объединение двух документов, расположенных ближе всего друг к другу, в одну группу. После этого производится перерасчет расстояний между документами, причем группа уже считается неделимым объектом.
3.2. 4 . Алгоритмы на основе графов
Документы можно представить как вершины графа, и в таком случае задача кластеризации документов сводится к удалению определенных ребер графа. По такому принципу работают следующие алгоритмы:
• Минимального покрывающего дерева
• Выделения связных компонент (в частности МаjorClust)
Иерархические методы кластерного анализа
Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.
Иерархические агломеративные методы (Agglomerative Nesting, AGNES)
Эта группа методов характеризуется последовательным объединением исходных элементов и соответс твующим уменьшением числа кластеров.
В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут с оставлять один кластер .
Иерархические дивизимные ( делимые ) методы (DIvisive ANAlysis, DIANA)
Эти методы являются логической противоположностью агломеративным методам.
В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп.
Принцип работы описанных выше групп методов в виде дендрограммы показан на рис . 3.