Марковский алгоритм кластеризации

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Марковский алгоритм кластеризации)
Текущая версия (02:23, 13 декабря 2018) (править) (отменить)
(Марковский алгоритм кластеризации)
 
(27 промежуточных версий не показаны.)
Строка 5: Строка 5:
== Марковский алгоритм кластеризации ==
== Марковский алгоритм кластеризации ==
-
План работы над статьей
 
-
* расписать общую постановку задачи (до 2018.11.04)
+
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — алкоритм кластерного анализа основанный на потоке (случайном блуждании) в графе. Изначально разработан для выделения кластеров в простом графе, однако может быть применен к любым объектам для которых задана матрица сходства/различия. Данный алгоритм является быстрый и масштабируемым алгоритмом кластеризации.
-
* расписать общий принцип алгоритма (до 2018.11.10)
+
-
* своровать/нарисовать нужные картинки (до 2018.11.17)
+
-
* разобраться с влиянием expansion и inflation на качество кластеризации (до 2018.11.24)
+
-
* разобраться с ortoMCL и написать пунк о практическом применении метода в биологии (до 2018.12.04)
+
-
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — быстрый и масштабируемый алгоритм кластеризации, основанный на моделировании потока в графе. Он был создан в 2000 году в Центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм имеет широкий спектр применений, например, для данных в
 
-
молекулярной биологии.
 
-
Здесь или ввести понятие графа или дать ссылку на другую статью.
+
----
-
Граф состоит из двух типов объектов 1) вершин(узлов) - V 2)ребер (пар вершин соединенных между собой) - E. Более формальная запись G:=(V,E)
+
==== Термины и определения ====
-
Графы помимо теоритической математики часто возникают при упрощении сложных систем.
 
-
К примеру в виде графа удобно отображать порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер).
 
-
Кластеры в графе возникают в силу необходимости распознания образов и подгруппы в больших графах.
 
-
В качестве метрики растояния можно использовать суммы длин ребер (или их количества) между двумя точками, что по сути является евклидовой метрикой.
+
Граф состоит из двух типов объектов 1) вершин(узлов)- V
 +
2)ребер (пар вершин соединенных между собой) - E. Формально это можно записать как G:=(V,E)
 +
Кроме этого, каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij равен растоянию между узлом i и узлом j.
-
The graph clustering paradigm postulates that
+
Случайный обход графа - такой обход вершин граф, при котором выбор следующей вершины зависит только от
-
‘natural’ groups in graphs, the groups that are sought and not known, have the following
+
текущего положения на графе, а вероятность перейти к любой вершинне расчитывется исходя из матрицы
-
property:
+
смежности. Следует отметить что при таком обходе одна вершина может быть посещена неограниченное число раз.
-
A random walk in G that visits a dense cluster will likely not leave the cluster until many
+
Случайное блуждание в графе представляет собой цепь Маркова.
-
of its vertices have been visited.
+
 +
Строго определить что такое кластер в графе, не представляется возможном, однако можно сделать следующие замечания:
 +
-длинна пути между узлами одного кластера мало по сравнению с длинно пути между точками пренадлежажащими
 +
разным кластерам
 +
-при случайном обходе графа, прежде чем покинуть кластер будут посещены многоие из его вершин.
-
Парадигма кластеризации графа. Парадигма кластеризации графа постулирует, что
+
Метод MCL опирается на второе заечание -
-
«Естественные» группы в графах, обладают следующей характеристикой:
+
расстояние между узлами графа относящихся к одному кластеру, меньше чем растояние между узлами относящимся к различным кластерам. т.е. верояность перехода (поток) между узлами внутри одного кластера много больше чем между узлами относящимися к разным кластерам. Таким образом если усиливать поток там где он силен и ослаблять его там где он слаб то согласно парадигме кластеризации графа границы между различными кластерами будут исчезать. Таким образом будет выявлена кластерная структура графа.
-
При случайном обходе графа и поподании в кластер, мы не выйдем из него пока не обойдем многие вершины в нем.
+
-
В основе алгоритма MCL лежит идея моделирования потока (случайного блуждания) внутри графа.
+
----
-
т.е. если усиливать поток там где он силен и ослаблять его там где он слаб то согласно парадигме кластеризации графа границы между различными кластерами будут исчезать. Таким образом будет выявлена кластерная структура в графе.
+
-
+
-
Моделирование потока через граф легко осуществляется путем преобразования его в марковский граф.
+
-
где ток силен, и уменьшать поток, когда ток слабый. Если
+
==== Общее описание метода ====
-
естественные группы присутствуют на графике, то согласно парадигме тока через
+
-
границы между различными группами будут отмирать, тем самым выявив кластерную структуру в
+
-
график.
+
-
2,
 
-
т. е. график, где для всех узлов веса исходящих дуг суммируются с одним. Поток может
 
-
быть расширена за счет вычислительных степеней связанной стохастической (марковской) матрицы, которая
 
-
составляет обычный дискретный марковский процесс. Это само по себе недостаточно, поскольку
 
-
Марковский процесс не показывает структуру кластера в своем базовом графе.
 
-
Парадигма обеспечивается введением нового оператора в марковский процесс, называемый
 
-
инфляция. В то время как расширение потока представлено обычным матричным продуктом,
 
-
представляет собой входной продукт Адамара-Шура в сочетании с диагональю
 
-
масштабирование. Оператор инфляции несет ответственность за укрепление и ослабление
 
-
ток. Оператор расширения отвечает за то, что поток позволяет подключать разные
 
-
областей графика.
 
-
Полученный алгебраический процесс называется кластерным процессом Маркова или процессом MCL.
 
-
процесс сходится квадратично в окрестности так называемого двудомного идемпотента
 
-
матрицы (идемпотент как при расширении, так и в инфляции).
 
 +
Моделирование потока в графе осуществляется путем преобразования его в марковский граф (см. рисуйнок 1).
 +
[[Изображение:Graph_to_Markov_Graph.jpg|300px|thumb|Рисуйнок 1. Преобразование графа в марковский граф]]
-
В этих двух статьях двугой подход к кластеризации на графе:
+
На первом шаге граф преобразуется в матрицу растояний между узлами (смежную матрицу). В слуае если граф является не взвешенным можно считать что вес всех ребер равен единице. На втором шаге происходит преобразование смежной матрицы в матрицу вероятностей переходов между узлами (стохастическую матрицу). Для этого как правило нормируют значения в каждом отдельном столбце матрицы рассотяний, однако может быть применен любой другой алгоритм.
-
L. Hagen and A. B. Kahng, A new approach to effective circuit clustering, in IEEE [91],
+
После того как стохастическую матрица получена, к ней поочердно применяют две функции (распространение и накачивание) до тех пор пока матрица изменяется (см. рисуйнок 2).
-
pp. 422–427.
+
[[Изображение:MCL_algor.jpg|200px|thumb|Рисуйнок 2. Блок-схема алгоритма MCL]]
-
C.-W. Yeh, C.-K. Cheng, and T.-T. Y. Lin, Circuit clustering using a stochastic flow injection
+
-
method, IEEE Transactions on Computer–Aided Design of Integrated Circuits and Systems,
+
-
14 (1995), pp. 154–162.
+
-
Кластерный анализ и кластеры в графе
+
1) распространение (N) - представляет собой возведение матрицы в степень N. Данная операция усиливает поток из вершины на потенциальных участников кластера.
 +
2) накачивание (K) - представляет собой применение произведения Адамара матрицы самой на себя. (произведение Адамара - бинарная операция над двумя матрицами одинаковой размерности, результатом которой является матрица той же размерности, в которой каждый элемент с индексами i, j — это произведение элементов с индексами i, j исходных матриц). Данная операция уменьшает вероятности переходов между кластерами быстрее чем вероятности переходов внутри одного кластера. Так же на этом шаге выполняеца нормирование каждого столбца матрицы.
-
Предпологается что кластера в графе образуют сгущения, в то время как между кластерми есть пустоты(??)
 
 +
В данном алгоритме необходимо подбирать степь распространения и накачивании (так как это непосредственно вляйет на разбиение). Увеличение степени распространении - увеличивает средний размер кластера, в то время как увеличение степени накачивания - приводит к увеличению количества кластеров.
-
Марковский процес кластеризации
+
В ходе выполнения алгоритма выделяются узлы которые являются "центрами" кластеров. Наглядная визуализация алгоритма приведена на рисунки 3. Как можно заметить в ходе работы алгоритма граф становится все менее и менее связным пока не будет разделен на кластеры.
 +
[[Изображение:Markov_Clustering_Algorithm.jpeg|200px|thumb| Рисунок 3 Визуализация метода]]
-
Эксперименты и практическое применение MCL
+
----
 +
==== Примеры способов кластеризации ====
 +
[[Изображение:MCL1.jpeg|200px|thumb| Рисунок 4 кластеризации простого графа методом MCL. Слева грав до кластеризации, справа после кластеризации]]
-
[[Изображение:Markov_Clustering_Algorithm.jpeg|thumb]]
+
Расмотрим работу данного метода на примере кластеризации простого графа и его смежной матрицы.
-
----
+
Возьмем граф состоящий из 12 вершин и составим для него матрицу вероятностей переходов между узлами. Так как граф является не взвешенным вероятности перехода между соседними узлами и вероятность остаться в этом узле будет равна 1/(количество ребер смежных с вершиной + 1). Матрица вероятностей переходов между узлами представленна вверху рисунка 5. Кроме этого на рисунке 5 представлен результат выполнения функции распространения без регулярной инфляции. Как не сложно заметить в результате этого получается полносвязный граф. Однако при выполнении инфляции в каждом цикле алгоритма приводит к выделению кластерной структуры алгоритма, это можно наблюдать на рисунке 6.
-
общее описание метода
+
-
Алгоритм основан на двух функциях expansion и inflation.
+
[[Изображение:MCL2.png|200px|thumb| Рисунок 5 экспансия без инфляции]]
-
1) expansion - разширяем поток из вершины на потенциальных участников кластера.
 
-
2) inflation - уменьшаем переходы между кластерами и увеличиваем внутри кластера.
 
-
расширение (expansion) - объединяет кластера, остабляет сильный ток и усиливает слабый.
 
-
инфляция (inflation) - сжимает кластера, усиливает сильный поток и ослабляет слабый.
 
-
 
 +
[[Изображение:MCL3.jpeg|200px|thumb| Рисунок 6 экспансия с инфляцией]]
----
----
-
итог по алгоритму
+
==== Плюсы и минусы алгоритма ====
 +
 
 +
#Плюсы алгоритма
#Плюсы алгоритма
##Работает как с взвешенными, так и с невзвешенными графами
##Работает как с взвешенными, так и с невзвешенными графами
##Устойчив к шуму в данных
##Устойчив к шуму в данных
-
##Количество кластеров не указано заранее, но можно настроить степень детализации кластера с параметрами
+
##Количество кластеров не указано заранее, но можно настроить степень детализации кластера
 +
##Может находить кластера произвольной формы
#Минусы алгоритма
#Минусы алгоритма
-
##Не удается найти перекрывающиеся кластеры (*)
+
##Не нацелен находить перекрывающиеся кластеры (*)
##Не подходит для кластеров большого размера
##Не подходит для кластеров большого размера
##Часто кластеры получаются разного размера
##Часто кластеры получаются разного размера
-
 
+
##Время работы алгоритма в наихудшем случае Ο(V^3), однаков слкчае разряженной матрицы время расчета может уменьшаться до Ο(V) и расчет может быть распаралален на несколько процессоров.
----
----
 +
Данный алгоритм был разработан в рамках PhD работы Van Dongen в 2000 году в центре математических и компьютерных наук в Нидерландах. В 2012 году были разработанны такие вариации алгоритма как MLR-MCL и
 +
R-MCL которые облдали меньшим количеством недостатков.
 +
[Satuluri V. M. Scalable clustering of modern networks : дис. – The Ohio State University, 2012.]
 +
 +
 +
 +
#На сегодняшний день данный алгоритм применяется для данных в молекулярной биологии (выделение групп генов) [S. Brohee and J. van Helden. Evaluation of clustering algorithms for protein-
 +
protein interaction networks. BMC Bioinformatics, 7, 2006.][J. Vlasblom and S.J. Wodak. Markov clustering versus affinity propagation for the partitioning of protein interaction graphs. BMC bioinformatics, 10(1):99, 2009.]
 +
#анализе изображений
 +
#проектировании плат и расположении микросхем.
Список используемой литературы
Список используемой литературы

Текущая версия


Данная статья является непроверенным учебным заданием.
Студент: Участник:Konstantinov_bionet
Преподаватель: Участник:Nvm
Срок: 31 декабря 2018

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.



Содержание

Марковский алгоритм кластеризации

Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — алкоритм кластерного анализа основанный на потоке (случайном блуждании) в графе. Изначально разработан для выделения кластеров в простом графе, однако может быть применен к любым объектам для которых задана матрица сходства/различия. Данный алгоритм является быстрый и масштабируемым алгоритмом кластеризации.




Термины и определения

Граф состоит из двух типов объектов 1) вершин(узлов)- V 
2)ребер (пар вершин соединенных между собой) - E. Формально это можно записать как G:=(V,E)
Кроме этого, каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij равен растоянию между узлом i и узлом j.
Случайный обход графа -  такой обход вершин граф, при котором выбор следующей вершины зависит только от 
текущего положения на графе, а вероятность перейти к любой вершинне расчитывется исходя из матрицы 
смежности. Следует отметить что при таком обходе одна вершина может быть посещена неограниченное число раз. 
Случайное блуждание в графе представляет собой цепь Маркова.

Строго определить что такое кластер в графе, не представляется возможном, однако можно сделать следующие замечания:

-длинна пути между узлами одного кластера мало по сравнению с длинно пути между точками пренадлежажащими разным кластерам

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

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


Общее описание метода

Моделирование потока в графе осуществляется путем преобразования его в марковский граф (см. рисуйнок 1).

Рисуйнок 1. Преобразование графа в марковский граф
Рисуйнок 1. Преобразование графа в марковский граф

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


После того как стохастическую матрица получена, к ней поочердно применяют две функции (распространение и накачивание) до тех пор пока матрица изменяется (см. рисуйнок 2).

Рисуйнок 2. Блок-схема алгоритма MCL
Рисуйнок 2. Блок-схема алгоритма MCL


1) распространение (N) - представляет собой возведение матрицы в степень N. Данная операция усиливает поток из вершины на потенциальных участников кластера. 2) накачивание (K) - представляет собой применение произведения Адамара матрицы самой на себя. (произведение Адамара - бинарная операция над двумя матрицами одинаковой размерности, результатом которой является матрица той же размерности, в которой каждый элемент с индексами i, j — это произведение элементов с индексами i, j исходных матриц). Данная операция уменьшает вероятности переходов между кластерами быстрее чем вероятности переходов внутри одного кластера. Так же на этом шаге выполняеца нормирование каждого столбца матрицы.


В данном алгоритме необходимо подбирать степь распространения и накачивании (так как это непосредственно вляйет на разбиение). Увеличение степени распространении - увеличивает средний размер кластера, в то время как увеличение степени накачивания - приводит к увеличению количества кластеров.

В ходе выполнения алгоритма выделяются узлы которые являются "центрами" кластеров. Наглядная визуализация алгоритма приведена на рисунки 3. Как можно заметить в ходе работы алгоритма граф становится все менее и менее связным пока не будет разделен на кластеры.


Рисунок 3 Визуализация метода
Рисунок 3 Визуализация метода



Примеры способов кластеризации

Рисунок 4 кластеризации простого графа методом MCL. Слева грав до кластеризации, справа после кластеризации
Рисунок 4 кластеризации простого графа методом MCL. Слева грав до кластеризации, справа после кластеризации


Расмотрим работу данного метода на примере кластеризации простого графа и его смежной матрицы.

Возьмем граф состоящий из 12 вершин и составим для него матрицу вероятностей переходов между узлами. Так как граф является не взвешенным вероятности перехода между соседними узлами и вероятность остаться в этом узле будет равна 1/(количество ребер смежных с вершиной + 1). Матрица вероятностей переходов между узлами представленна вверху рисунка 5. Кроме этого на рисунке 5 представлен результат выполнения функции распространения без регулярной инфляции. Как не сложно заметить в результате этого получается полносвязный граф. Однако при выполнении инфляции в каждом цикле алгоритма приводит к выделению кластерной структуры алгоритма, это можно наблюдать на рисунке 6.

Рисунок 5 экспансия без инфляции
Рисунок 5 экспансия без инфляции


Рисунок 6 экспансия с инфляцией
Рисунок 6 экспансия с инфляцией

Плюсы и минусы алгоритма

  1. Плюсы алгоритма
    1. Работает как с взвешенными, так и с невзвешенными графами
    2. Устойчив к шуму в данных
    3. Количество кластеров не указано заранее, но можно настроить степень детализации кластера
    4. Может находить кластера произвольной формы
  2. Минусы алгоритма
    1. Не нацелен находить перекрывающиеся кластеры (*)
    2. Не подходит для кластеров большого размера
    3. Часто кластеры получаются разного размера
    4. Время работы алгоритма в наихудшем случае Ο(V^3), однаков слкчае разряженной матрицы время расчета может уменьшаться до Ο(V) и расчет может быть распаралален на несколько процессоров.



Данный алгоритм был разработан в рамках PhD работы Van Dongen в 2000 году в центре математических и компьютерных наук в Нидерландах. В 2012 году были разработанны такие вариации алгоритма как MLR-MCL и R-MCL которые облдали меньшим количеством недостатков. [Satuluri V. M. Scalable clustering of modern networks : дис. – The Ohio State University, 2012.]


  1. На сегодняшний день данный алгоритм применяется для данных в молекулярной биологии (выделение групп генов) [S. Brohee and J. van Helden. Evaluation of clustering algorithms for protein-

protein interaction networks. BMC Bioinformatics, 7, 2006.][J. Vlasblom and S.J. Wodak. Markov clustering versus affinity propagation for the partitioning of protein interaction graphs. BMC bioinformatics, 10(1):99, 2009.]

  1. анализе изображений
  2. проектировании плат и расположении микросхем.

Список используемой литературы


1) Van Dongen, S. 2000. “Graph clustering by flow simulation.” Ph.D. thesis, University of Utrecht, The Netherlands

2) https://www.micans.org/mcl/index.html

3) Li, Li, Christian J. Stoeckert, and David S. Roos. "OrthoMCL: identification of ortholog groups for eukaryotic genomes." Genome research 13.9 (2003): 2178-2189.

4)Satuluri, Venu, Srinivasan Parthasarathy, and Duygu Ucar. "Markov clustering of protein interaction networks with improved balance and scalability." Proceedings of the first ACM international conference on bioinformatics and computational biology. ACM, 2010.