Способы кластеризаци на графе
Материал из MachineLearning.
Способы кластеризаци на графе
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Граф состоит из двух типов объектов 1) вершин(узлов)- V 2)ребер (пар вершин соединенных между собой) - E. Более формальная запись G:=(V,E)
Кроме этого каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij= растоянию между узлом i и узлом j.
Что такое естественные группы? В общем, это сложная проблема, но в рамках графиков существует единое понятие, которое управляет многими предложениями. Это понятие может быть сформулировано по-разному. Пусть G - граф, обладающий кластерной структурой, тогда альтернативные формулировки следующие: а) Число путей большой длины в G велико для пар вершин, лежащих в одном плотном кластере, и мало для пар вершин, принадлежащих разным кластерам. б) Случайное блуждание в G, которое посещает плотное скопление, скорее всего, не покинет скопление, пока не будут посещены многие его вершины.
c) Учитывая все кратчайшие пути между всеми парами вершин G, связи между различными плотными кластерами, вероятно, будут во многих кратчайших путях. Эти три понятия тесно связаны друг с другом
Графы часто возникают при упрощении сложных систем. К примеру в виде графа удобно отображать:
- взамосвязи различных сайтов в интернете
- Социальные сети (сети контактов)
- Генные сети в молекулярной биологии
- порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер).
Вероятностные кластерные алгоритмы. В сообществе разбиения графов было предложено несколько рандомизированных кластерных алгоритмов. Я следую за обзорной статьей [8] Альперта и Канга, написанной в 1995 году. Каргер [99] предложил эвристику, в которой каждая вершина начинается как одноэлементное скопление. Ребра итеративно выбираются случайным образом, и каждый раз, когда кластеры, падающие на выбранное в данный момент ребро, сжимаются в один кластер. Соответствующий подход был предложен Bui et al. В [29, 159].
Хаген и Канг выбирают случайные блуждания для циклов в [75]; Основная установка состоит в том, что если два узла встречаются достаточно часто в цикле, то они объединяются в кластере. Наконец, Yeh et al. [174] предлагают метод, в котором вычисляются кратчайшие пути между случайно выбранными парами вершин.
И в связи с необходимостью распозновать образы и кластера в больших графах необходимы способы кластеризации. С каждым ребром связана стоимость, которая корректируется каждый раз, когда ребро включается в кратчайший путь. В плотных кластерах альтернативные пути легко найти; это не относится к вершинам в разных кластерах, ребра между ними неизбежно приобретут более высокую проверку. Основная идея, лежащая в основе алгоритма MCL, укладывается в одну и ту же парадигму, но два важных различия заключаются в том, что случайные блуждания вычисляются детерминистически и одновременно. Суть алгоритма в том, что он включает в себя усиление случайных прогулок.
Стандартный способ определения случайного блуждания на простом графе - позволить юному Уокеру взлететь на произвольную вершину. После этого он последовательно посещает новые вершины, выбирая произвольно одно из исходящих ребер. 3 Это будет отправной точкой для алгоритма MCL. Отличный обзор случайных графов [114] Ловаша. Важное наблюдение, цитируемое из этой статьи, заключается в следующем: случайное блуждание - это конечная цепь Маркова, обратимая во времени (см. Ниже
В качестве метрики растояния можно использовать суммы длин ребер (или их количества) между двумя точками, что по сути является евклидовой метрикой.
Парадигма кластеризации графа. Парадигма кластеризации графа постулирует, что
«Естественные» группы в графах, обладают следующей характеристикой:
При случайном обходе графа и поподании в кластер, мы не выйдем из него пока не обойдем многие вершины в нем.
Марковский алгоритм кластеризации
Кластеризация графов без использования метрик (пример)
Spectral
SCAN
CPM
Walktrap
Bigclam
LPA
NewmanGreedy
CNM
