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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Марковский алгоритм кластеризации)
Текущая версия (02:23, 13 декабря 2018) (править) (отменить)
(Марковский алгоритм кластеризации)
 
(11 промежуточных версий не показаны.)
Строка 6: Строка 6:
-
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — алкоритм кластерного анализа основанный на потоке (случайном блуждании) в графе. Изначально разработан для выделения кластеров в графе, однако может быть применен к любым объектам для которых задана матрица сходства/различия.
+
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — алкоритм кластерного анализа основанный на потоке (случайном блуждании) в графе. Изначально разработан для выделения кластеров в простом графе, однако может быть применен к любым объектам для которых задана матрица сходства/различия. Данный алгоритм является быстрый и масштабируемым алгоритмом кластеризации.
-
Марковский алгоритм кластеризации — быстрый и масштабируемый алгоритм кластеризации, основанный на моделировании потока в графе.
 
-
 
-
Данный алгоритм был разработан в рамках PhD работы Van Dongen в 2000 году в центре математических и компьютерных наук в Нидерландах.
 
----
----
Строка 24: Строка 21:
Случайный обход графа - такой обход вершин граф, при котором выбор следующей вершины зависит только от
Случайный обход графа - такой обход вершин граф, при котором выбор следующей вершины зависит только от
текущего положения на графе, а вероятность перейти к любой вершинне расчитывется исходя из матрицы
текущего положения на графе, а вероятность перейти к любой вершинне расчитывется исходя из матрицы
-
смежности. Следует отметить что при таком обходе одна вершина может быть посещена неограниченное число раз. Случайное блуждание в графе - это цепь Маркова.
+
смежности. Следует отметить что при таком обходе одна вершина может быть посещена неограниченное число раз.
 +
Случайное блуждание в графе представляет собой цепь Маркова.
-
Строго определить что такое кластер в графе, не представляется возможном, однако можно дать два близких определения:
+
Строго определить что такое кластер в графе, не представляется возможном, однако можно сделать следующие замечания:
-
#Длинна пути между узлами одного кластера мало по сравнению с длинно пути между точками пренадлежажащими
+
-
одному кластеру.
+
-
#При случайном обходе графа, прежде чем покинуть кластер будут посещены многоие из его вершин
+
 +
-длинна пути между узлами одного кластера мало по сравнению с длинно пути между точками пренадлежажащими
 +
разным кластерам
 +
-при случайном обходе графа, прежде чем покинуть кластер будут посещены многоие из его вершин.
 +
 +
Метод MCL опирается на второе заечание -
 +
расстояние между узлами графа относящихся к одному кластеру, меньше чем растояние между узлами относящимся к различным кластерам. т.е. верояность перехода (поток) между узлами внутри одного кластера много больше чем между узлами относящимися к разным кластерам. Таким образом если усиливать поток там где он силен и ослаблять его там где он слаб то согласно парадигме кластеризации графа границы между различными кластерами будут исчезать. Таким образом будет выявлена кластерная структура графа.
----
----
Строка 37: Строка 38:
==== Общее описание метода ====
==== Общее описание метода ====
-
Метод опирается на следующе допущение -
 
-
расстояния между узлами графа относящихся к одному кластеру, меньше чем растояние между узлами относящимся к различным кластерам. т.е. верояность перехода (поток) между узлами внутри одного кластера много больше чем между
 
-
узлами относящимися к разным кластерам.
 
-
таким образом если усиливать поток там где он силен и ослаблять его там где он слаб то согласно парадигме кластеризации графа границы между различными кластерами будут исчезать. Таким образом будет выявлена кластерная структура графа.
 
Моделирование потока в графе осуществляется путем преобразования его в марковский граф (см. рисуйнок 1).
Моделирование потока в графе осуществляется путем преобразования его в марковский граф (см. рисуйнок 1).
Строка 52: Строка 49:
-
1) распространение - представляет собой обычное умножение матрицы самой на себя. Данная операция усиливает поток из вершины на потенциальных участников кластера.
+
1) распространение (N) - представляет собой возведение матрицы в степень N. Данная операция усиливает поток из вершины на потенциальных участников кластера.
-
2) накачивание - обычное умножение матрицы самой на себя. уменьшаем переходы между кластерами и увеличиваем внутри кластера.
+
2) накачивание (K) - представляет собой применение произведения Адамара матрицы самой на себя. (произведение Адамара - бинарная операция над двумя матрицами одинаковой размерности, результатом которой является матрица той же размерности, в которой каждый элемент с индексами i, j — это произведение элементов с индексами i, j исходных матриц). Данная операция уменьшает вероятности переходов между кластерами быстрее чем вероятности переходов внутри одного кластера. Так же на этом шаге выполняеца нормирование каждого столбца матрицы.
-
расширение (expansion) - представляет собой произведение Адамара (бинарная операция над двумя матрицами одинаковой размерности, результатом которой является матрица той же размерности, в которой каждый элемент с индексами i, j — это произведение элементов с индексами i, j исходных матриц). Данная операция объединяет кластера, остабляет сильный ток и усиливает слабый.
+
-
+
 +
В данном алгоритме необходимо подбирать степь распространения и накачивании (так как это непосредственно вляйет на разбиение). Увеличение степени распространении - увеличивает средний размер кластера, в то время как увеличение степени накачивания - приводит к увеличению количества кластеров.
 +
 +
В ходе выполнения алгоритма выделяются узлы которые являются "центрами" кластеров. Наглядная визуализация алгоритма приведена на рисунки 3. Как можно заметить в ходе работы алгоритма граф становится все менее и менее связным пока не будет разделен на кластеры.
Строка 65: Строка 63:
----
----
 +
==== Примеры способов кластеризации ====
-
Примеры способов кластеризации
 
-
[[Изображение:MCL1.jpeg|200px|thumb| Рисунок 4 кластеризации простого графа методом MCL. Слева грав до кластеризации, справо после кластеризации]]
+
[[Изображение:MCL1.jpeg|200px|thumb| Рисунок 4 кластеризации простого графа методом MCL. Слева грав до кластеризации, справа после кластеризации]]
Расмотрим работу данного метода на примере кластеризации простого графа и его смежной матрицы.
Расмотрим работу данного метода на примере кластеризации простого графа и его смежной матрицы.
-
Возмем граф состоящий из 12 вершин и составим для него матрицу вероятностей переходов между узлами. Так как граф является не взвешенны вероятности перехода между соседними узлами и вероятность остаться в этом узле будет равна 1/(количество ребер смежных с вершиной + 1). Матрица представленна на рисунке 5.
+
Возьмем граф состоящий из 12 вершин и составим для него матрицу вероятностей переходов между узлами. Так как граф является не взвешенным вероятности перехода между соседними узлами и вероятность остаться в этом узле будет равна 1/(количество ребер смежных с вершиной + 1). Матрица вероятностей переходов между узлами представленна вверху рисунка 5. Кроме этого на рисунке 5 представлен результат выполнения функции распространения без регулярной инфляции. Как не сложно заметить в результате этого получается полносвязный граф. Однако при выполнении инфляции в каждом цикле алгоритма приводит к выделению кластерной структуры алгоритма, это можно наблюдать на рисунке 6.
-
Таким образом мы получим матрицу.
+
-
Процес MCL представлен на рисунке 5
+
 +
[[Изображение:MCL2.png|200px|thumb| Рисунок 5 экспансия без инфляции]]
-
 
+
[[Изображение:MCL3.jpeg|200px|thumb| Рисунок 6 экспансия с инфляцией]]
-
[[Изображение:MCL3.jpeg|200px|thumb| Рисунок 5 экспансия с инфляцией]]
+
----
----
-
итог по алгоритму
+
==== Плюсы и минусы алгоритма ====
 +
 
 +
#Плюсы алгоритма
#Плюсы алгоритма
##Работает как с взвешенными, так и с невзвешенными графами
##Работает как с взвешенными, так и с невзвешенными графами
Строка 94: Строка 92:
##Не подходит для кластеров большого размера
##Не подходит для кластеров большого размера
##Часто кластеры получаются разного размера
##Часто кластеры получаются разного размера
-
##Время работы алгоритма в наихудшем случае Ο(V^3)
+
##Время работы алгоритма в наихудшем случае Ο(V^3), однаков слкчае разряженной матрицы время расчета может уменьшаться до Ο(V) и расчет может быть распаралален на несколько процессоров.
-
 
+
----
-
Дальнейшее развитие ,в 2012 году, метод получил как
+
Данный алгоритм был разработан в рамках PhD работы Van Dongen в 2000 году в центре математических и компьютерных наук в Нидерландах. В 2012 году были разработанны такие вариации алгоритма как MLR-MCL и
-
MLR-MCL
+
R-MCL которые облдали меньшим количеством недостатков.
-
R-MCL
+
[Satuluri V. M. Scalable clustering of modern networks : дис. – The Ohio State University, 2012.]
[Satuluri V. M. Scalable clustering of modern networks : дис. – The Ohio State University, 2012.]
-
----
 
-
 
-
 
-
[[Изображение:MCL2.png|200px|thumb| Рисунок 5 экспансия без инфляции]]
 
-
 
-
 
-
В этих двух статьях двугой подход к кластеризации на графе:
 
-
 
-
 
-
L. Hagen and A. B. Kahng, A new approach to effective circuit clustering, in IEEE [91],
 
-
pp. 422–427.
 
-
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.
 
-
 
-
Графы часто возникают при упрощении сложных систем. К примеру в виде графа удобно отображать:
 
-
#взамосвязи различных сайтов в интернете
 
-
#Социальные сети (сети контактов)
 
-
#Генные сети в молекулярной биологии
 
-
#порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер).
 
-
3.2.1 Приложения
 
-
#умножение разреженных матриц (распределения строк по разным процессора), параллельные вычисления, численное решение уравнений в частных производных .
 
-
Разреженное матричное умножение требует м.
 
-
Минимизация объема связи между процессорами - это разбиение графа
 
-
проблема. [A. Gupta, Fast and effective algorithms for graph partitioning and sparsematrix ordering, IBM Journal of Research & Development, 41 (1997). http://www.research.ibm.com/journal/rd/411/gupta.html].
 
-
Решатели PDE действуют на сетке или сетке, и параллельное вычисление такого решателя требует
 
-
разделение сетки, опять же, чтобы минимизировать связь между процессами
 
-
сорс [53].
 
-
планирование и размещение микросхем [C. J. Alpert and A. B. Kahng, Recent directions in netlist partitioning: a survey, Integration: the VLSI Journal, 19 (1995), pp. 1–81.]
 
-
• Оценка требований к проводке и производительности системы в синтезаторе высокого уровня.
 
-
Сис и поэтажное планирование.
 
#На сегодняшний день данный алгоритм применяется для данных в молекулярной биологии (выделение групп генов) [S. Brohee and J. van Helden. Evaluation of clustering algorithms for protein-
#На сегодняшний день данный алгоритм применяется для данных в молекулярной биологии (выделение групп генов) [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.]
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.