Навігація
Головна
ПОСЛУГИ
Авторизація/Реєстрація
Реклама на сайті
 
Головна arrow Інформатика arrow Моделирование сложных сетей
< Попередня   ЗМІСТ   Наступна >

Метод k-means

Итеративный алгоритм кластерного анализа к- means (к-средних) группировки документов по фиксированному количеству кластеров заключается в следующем: случайным образом выбирается к векторов, которые определяются как центроиды (наиболее типичные представители) кластеров.

Затем к кластеров

наполняются - для каждого из векторов, которые остались, некоторым образом определяется близость к центроиду соответствующего кластера. Близость может определяться разными способами, в частности, как нормированное скалярное произведение:

где х — документ, центроид кластера N — размерность пространства термов.

После этого вектор приписывается к тому кластеру, к которому он наиболее близок. Далее векторы группируются и перенумеровываются соответственно принадлежности к кластерам. Потом для каждого из новых кластеров заново определяется центроид — вектор, наиболее

близкий ко всем векторам из данного кластера, координаты которого определяются, например, следующим образом:

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

Алгоритм к-means максимизирует функцию качества кластеризации Q:

В отличие от метода LSI, k-means может использоваться для группирования динамических информационных потоков благодаря своей вычислительной простоте - O(kn), где n -количество объектов группирования (документов). Недостатком метода является то, что каждый документ может попасть всего лишь в один кластер.

Иерархическое группирование-объединение

Иерархическое группирование-объединение (Hierarchical Agglomerative Clustering, HAC) начинается с того, что каждому объекту в соответствие ставится отдельный кластер, а затем происходит объединение кластеров, которые наиболее близки друг к другу, в соответствии с выбранным критерием. Алгоритм завершается, когда все объекты объединяются в единый кластер. История объединений образует бинарное дерево иерархии кластеров.

Разновидности алгоритма HAC различаются выбором критериев близости (подобия) между кластерами. Например, близость между двумя кластерами может вычисляться как максимальная близость между объектами из этих кластеров.

Иерархическая кластеризация очень часто применяется при социологическом анализе, в биологии, экономике и т.д. Главным образом там, где заранее неизвестно количество кластеров.

Для иерархической кластеризации необходимо каким-либо образом определить расстояние между узлами нашего графа (сети). Т.е. нам необходимо получить количественную оценку близости узлов, аналогичную расстоянию в обычном евклидовом пространстве. Рассмотрим два наиболее используемых определения. Первое это Евклидово расстояние (Euclidean distance), определяется следующим образом:

здесь N - число узлов в сети. Евклидово расстояние точно равно нулю для полностью структурно - эквивалентных узлов и увеличивается для узлов, которые не имеют общих соседей. Второе определение базируется на корреляции Пирсона между строками (столбцами) матрицы инцидентности.

где

Здесь структурно эквивалентные узлы те, которые имеют большой коэффициент корреляции.

После того как мы любым способом определили матрицу расстояний можно приступать непосредственно к иерархической кластеризации. Остановимся подробнее на англомеративном алгоритме. Вначале опишем идею алгоритма. Пусть у нас есть точки xl,x2...xNи матрица относительных расстояний xtj. На первом шаге каждую точку считаем отдельным кластером. Затем ближайшие (в смысле расстояния) точки объединяем и считаем одним кластером, и так далее пока не задействуются все точки. На выходе мы получим дерево (дендограмму). При подсчете расстояний между кластерами наиболее часто используют один из двух следующих алгоритмов. Single-link алгоритм считает минимум из возможных расстояний между парами узлов, находящихся в кластере, Complete-link алгоритм считает максимум из этих расстояний.

Приведем пошаговый пример для Single-link алгоритма. Пусть есть граф, показанный на рис. 2.5.1.

Пример графа

Рис. 2.5.1 - Пример графа

Записав матрицу Евклидовых расстояний (1), видим, что минимальное расстояние равное нулю соответствует узлам 1 и 5. Поэтому на первом шаге объединяем эти узлы в один кластер.

На втором шаге снова записываем матрицу расстояний, используя алгоритм Single-link. Следующее расстояние после нулевого расстояния равно единице. И на этом шаге мы получаем два кластера, которые суммарно включают все узлы сети.

Если разрезать дендограмму вдоль пунктирной линии 1 - то мы получим два кластера содержащие узлы (1, 5, 2) и (3, 4, 6) соответственно. Что соответствует и интуитивному разбитию на кластера, см. рис. 1. Если резать вдоль второй пунктирной линии, то получаем три кластера (1, 5), (2) и (3, 4, 6).

На рис. 2.5.2 показана окончательная дендограмма

сети.

Использован алгоритм Single-link

Рис. 2.5.2 - Использован алгоритм Single-link

Если при иерархической кластеризации использовать алгоритм Complete-link, то получим немного другую дендограмму, см рис. 2.5.3.

Отличие в алгоритмах проявится на втором шаге построения. При использовании алгоритма Single-link в один кластер к узлам (4, 6) добавляется узел 3, поскольку он связан с узлом 6 единичным расстоянием, таким же, как и внутрекластерное расстояние. А при использовании Complete-link алгоритма, узел 3 присоединяется на следующем шаге т.к. здесь необходимо смотреть по максимальному расстоянию, т.е. по расстоянию от узла 3 до узла 4, которое больше внутрикластерного расстояния между узлами 4 и 6.

Использован алгоритм Complete-link

Рис. 2.5.3 - Использован алгоритм Complete-link

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Банківська справа
БЖД
Бухоблік та Аудит
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Нерухомість
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
РПС
Соціологія
Статистика
Страхова справа
Техніка
Товарознавство
Туризм
Філософія
Фінанси
Інші