Материал: Алгоритм нахождения кластеров

Алгоритм нахождения кластеров

Введение

Нахождение сообществ или кластеров является достаточно популярной темой для изучения, широко обсуждаемой и изучаемой последние годы. Такой интерес обусловлен возрастающим объемом данных, используемых при моделировании систем. Методы анализа графов и алгоритмы поиска сообществ используются во многих сферах, таких как: социология, биология, физика и информатика. Одним словом, в тех областях, где информация может быть представлена в виде графа, в котором вершины соответствуют неким объектам, а ребра - связям между этими объектами. Например, в качестве объектов могут выступать интернет ресурсы, а связью между ними будут пользователи, использующие эти ресурсы или url ссылки с одного ресурса на другой. Особый интерес в последние годы представляет анализ моделей социальных сетей. Описанная структуру можно отнести к типу графов, называемыми социальными, они обладают неким набором свойств, специфичных только для такого типа графов.

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

Обзор существующих методов кластеризации

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

Сообщество

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

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

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

Минимальное сечение

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

Самым знаменитым алгоритмом из этого класса можно считать алгоритм Кернигана-Лина, первоначально разработанный для оптимизации схем размещения экектронных компонент на печатных платах. [1]

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

кластер граф спектр модулярность

Иерархическая кластеризация

В случаях, когда невозможно сразу определить структуру графа, количество сообществ в нем или вообще их наличие можно прибегнуть к использованию алгоритмов иерархической кластеризации. Алгоритмы, относящиеся к этому типу также позволяют выделить графы, имеющие иерархическую структуру. Основная идея алгоритмов из этого класса заключается в использовании меры схожести между вершинами, такими как коэфициент Отиаи [2], коэфициент Жаккара [3] или расстояние Хемминга [4] для матрицы смежности. На основании этих показателей вершины графа распределяются по кластерам, а после алгоритм повторяется для образовавшихся подграфов. Такой процесс называют процессом таксономии, результатом которого является иерархическая древообразная структура. Такие процессы нередко встречаются в области биологии при систематизации и классификации живых организмов.

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

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

Частичная кластеризация

Данный класс алгоритмов предполагает отображение вершин графа в евклидовом пространстве, так чтобы расстояние между ними отражало некую меру несходства между вершинами. Таким образом, вершины, соответствующие точкам, находящимся ближе друг к другу, вероятнее будут находиться в одном кластере. Часто меру несхожести или функцию схожести (cost function) выражают с использованием центральной точки (centroid point), обнаруживаемой в каждом кластере. Самые популярные алгоритмы частичной кластеризации:

·    Mинимальная k-кластеризация. Необходимым критерием этого алгоритма является нахождение такого разбиения, при котором наибольший диаметр (максимальное расстояние между двумя точками из этого кластера) найденных кластеров был минимально возможным.

·    K-сумма. Имеет тот же принцип, что и минимальная k-кластеризация, только вместо диаметра сообщества используется среднее расстояние между всеми парами вершин в кластере.

·    K-центр. Для каждого кластера находится центральная точка и разбиение выбирается таким образом, чтобы минимизировать максимальное расстояние между центральной точкой и другими точками в кластере, соответствующем этой точке.

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

·    Метод k-средних. Наиболее популярный и часто используемый из методов частичной кластеризации, описанный в 1950 г. математиками Гуго Штейнгаузом и Стюартом Ллойдом [5][6]. Он схож с другими рассмотренными методами, но при нахождении разбиения минимизируется суммарное квадратичное отклонение точек кластеров от центров этих кластеров, равное

где k - число кластеров,  - найденные кластеры, i = 1,2, …, k и- центры масс векторов .

Метод Гирвана-Ньюмана

Алгоритм, предложенный Гирваном и Ньюманом [7], относящийся к классу алгоритмов деления. Идея метода состоит в том, чтобы последовательно убирать связи между вершинами, предположительно находящимися в разных сообществах, до тех пор, пока не образуется множество несвязных компонент изначального графа, равное заданному числу кластеров. Выбор ребра, которое необходимо удалить осуществляется, основываясь на идеи центральности по посредничеству (далее центральность), предложенной Фриманом в 1977 г [8].

Центральность - характеристика, приписываемая каждому ребру в графе, являющаяся неотрицательной величиной, численно равной количеству кратчайших путей, проходящих через данное ребро. Если между вершинами n кратчайщих путей, то каждый из путей учитывается с коэфициентом 1/n при подсчете модулярности. Кратчайшим путем между двумя вершинами называется последовательность ребер, соединяющая эти вершины и обладающая наименьшей суммой весов.

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

В итоге алгоритм нахождения сообществ выглядит следующим образом:

1.   Находится центральность для всех ребер в графе.

2.   Ребро с наибольшим значением центральности удаляется.

.     Центральность для всех ребер пересчитывается заново.

.     При изменении количества компонент связности рассчитывается модулярность текущего разбиения.

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

К сожалению, данный метод имеет высокую сложность O(m^2n) и его использование на графах с большим количеством вершин нецелесообразно. Однако время работы алгоритма можно сильно сократить, если заранее знать количество кластеров в оптимальном разбиении.

Спектральный метод

Основная идея спектрального метода нахождения сообществ в графах заключается в анализе собственных векторов и собственных значений матриц, связанных с графом, таких, как матрица смежности или Лапласиан[9]. Множество собственных значений таких матриц называют спектром графа.

Спектральная теория графов возникла в 1950-60 годах. Кроме теоретических исследований графов <https://ru.wikipedia.org/wiki/Теория_графов> о связи структурных и спектральных свойств графов, другим источником стали исследования в кантовой химии <https://ru.wikipedia.org/wiki/Квантовая_химия>. Монография 1980 года «Спектры графов» (Spectra of Graphs) Цветковича, Дооба и Сакса (Cvetković, Michael Doob, Sachs) [10] обобщила почти все исследования в этой области, известные к тому моменту. В 1988 году вышло обновлённое обозрение «Последние исследования в теории спектра графа» [11]. Третье издание книги «Спектры графов» (1995) содержит итоги дальнейших вкладов в этой области [12].

В данной работе производилось изучение спектрального метода с использованием матрицы смежности, однако сейчас ведутся разработки методов определения кластеров по спектру матриц, составленных различными способами, например, нормированная матрица Лапласа [13] и Non-backtracking-матрица [14].

Другие методы

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

1.   Fastgreedy - метод, основанный на жадной оптимизации функции модулярности. [15]

2.   Multilevel - метод, основанный на многоуровневой оптимизации функции модулярности. [16]

.     LabelPropogation - метод, основанный на присвоении меток к каждой вершине. Каждый раз выбирается метка с максимальной встречаемостью среди смежных вершин. [17]

.     Walktrap - подход, основанный на случайном блуждании. Использует идею о том, что короткие случайные блуждания не приводят к выходу из текущего сообщества. [18]

.     Infomap - метод случайного блуждания, основанный на понятии информаци- онных потоков в сетях, кодирования и сжатия информации. [19]

Анализ и сравнение выбранных методов

Анализируемые модели графов.

Для тестирования и анализа реализованных алгоритмов были использованы два готовых набора данных и два разных алгоритма генерации случайных графов.

Наборы данных Фортунато и Кастеллиано

Данный граф был описан Фортунато и Кастеллиано в книге «Encyclopedia of Complexity and Systems Science» [21]. Граф содержит 14 вершин и 25 ребер. Оптимальное разбиение, содержащее два кластера изображено на рисунке.

Карате клуб Захария

Данная социальная сеть изучалась Уэйном Захарием с 1970 по 1972 г.

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