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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Марковский алгоритм кластеризации)
Текущая версия (02:23, 13 декабря 2018) (править) (отменить)
(Марковский алгоритм кластеризации)
 
(17 промежуточных версий не показаны.)
Строка 6: Строка 6:
 +
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — алкоритм кластерного анализа основанный на потоке (случайном блуждании) в графе. Изначально разработан для выделения кластеров в простом графе, однако может быть применен к любым объектам для которых задана матрица сходства/различия. Данный алгоритм является быстрый и масштабируемым алгоритмом кластеризации.
-
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — алкоритм кластерного анализа основанный на потоке (случайном блуждании) в графе. Изначально разработан для выделения кластеров в графе, однако может быть применен к любым объектам для которых задана матрица сходства/различия.
 
-
Данный алгоритм был разработан в рамках PhD работы Van Dongen в 2000 году в центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм применяется для данных в молекулярной биологии (выделение групп генов) и анилизе изображений.
+
----
 +
==== Термины и определения ====
-
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.]
 
-
• Оценка требований к проводке и производительности системы в синтезаторе высокого уровня.
 
-
Сис и поэтажное планирование.
 
-
----
+
Граф состоит из двух типов объектов 1) вершин(узлов)- V
-
общее описание метода
+
2)ребер (пар вершин соединенных между собой) - E. Формально это можно записать как G:=(V,E)
 +
Кроме этого, каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij равен растоянию между узлом i и узлом j.
 +
Случайный обход графа - такой обход вершин граф, при котором выбор следующей вершины зависит только от
 +
текущего положения на графе, а вероятность перейти к любой вершинне расчитывется исходя из матрицы
 +
смежности. Следует отметить что при таком обходе одна вершина может быть посещена неограниченное число раз.
 +
Случайное блуждание в графе представляет собой цепь Маркова.
 +
 +
Строго определить что такое кластер в графе, не представляется возможном, однако можно сделать следующие замечания:
-
Метод опирается на следующе допущение -
+
-длинна пути между узлами одного кластера мало по сравнению с длинно пути между точками пренадлежажащими
-
расстояния между узлами графа относящихся к одному кластеру, меньше чем растояние между узлами относящимся к различным кластерам. т.е. поток внутри одного кластера много больше чем между кластерами.
+
разным кластерам
-
т.е. если усиливать поток там где он силен и ослаблять его там где он слаб то согласно парадигме кластеризации графа границы между различными кластерами будут исчезать. Таким образом будет выявлена кластерная структура графа.
+
 +
-при случайном обходе графа, прежде чем покинуть кластер будут посещены многоие из его вершин.
 +
 +
Метод MCL опирается на второе заечание -
 +
расстояние между узлами графа относящихся к одному кластеру, меньше чем растояние между узлами относящимся к различным кластерам. т.е. верояность перехода (поток) между узлами внутри одного кластера много больше чем между узлами относящимися к разным кластерам. Таким образом если усиливать поток там где он силен и ослаблять его там где он слаб то согласно парадигме кластеризации графа границы между различными кластерами будут исчезать. Таким образом будет выявлена кластерная структура графа.
 +
 +
----
 +
 +
==== Общее описание метода ====
Строка 38: Строка 42:
[[Изображение:Graph_to_Markov_Graph.jpg|300px|thumb|Рисуйнок 1. Преобразование графа в марковский граф]]
[[Изображение:Graph_to_Markov_Graph.jpg|300px|thumb|Рисуйнок 1. Преобразование графа в марковский граф]]
-
На первом шаге граф преобразуется в матрицу растояний между узлами (иное представления графа). На втором шаге происходит преобразование матрицы растояний в матрицу стохастических переходов между узлами. В примере используется нормирование значений в столбце однако может быть применен любой другой алгоритм.
+
На первом шаге граф преобразуется в матрицу растояний между узлами (смежную матрицу). В слуае если граф является не взвешенным можно считать что вес всех ребер равен единице. На втором шаге происходит преобразование смежной матрицы в матрицу вероятностей переходов между узлами (стохастическую матрицу). Для этого как правило нормируют значения в каждом отдельном столбце матрицы рассотяний, однако может быть применен любой другой алгоритм.
-
После того как стохастическая матрица (марковский граф) получена, к ней последовательно применяются применяются две функции (Expansion, распространение) и (Inflation, накачивание) до тех пор пока матррица не перестанет менятся (см. рисуйнок 2).
+
После того как стохастическую матрица получена, к ней поочердно применяют две функции (распространение и накачивание) до тех пор пока матрица изменяется (см. рисуйнок 2).
[[Изображение:MCL_algor.jpg|200px|thumb|Рисуйнок 2. Блок-схема алгоритма MCL]]
[[Изображение:MCL_algor.jpg|200px|thumb|Рисуйнок 2. Блок-схема алгоритма MCL]]
-
1) expansion - разширяем поток из вершины на потенциальных участников кластера.
+
1) распространение (N) - представляет собой возведение матрицы в степень N. Данная операция усиливает поток из вершины на потенциальных участников кластера.
-
2) inflation - уменьшаем переходы между кластерами и увеличиваем внутри кластера.
+
2) накачивание (K) - представляет собой применение произведения Адамара матрицы самой на себя. (произведение Адамара - бинарная операция над двумя матрицами одинаковой размерности, результатом которой является матрица той же размерности, в которой каждый элемент с индексами i, j — это произведение элементов с индексами i, j исходных матриц). Данная операция уменьшает вероятности переходов между кластерами быстрее чем вероятности переходов внутри одного кластера. Так же на этом шаге выполняеца нормирование каждого столбца матрицы.
-
расширение (expansion) - объединяет кластера, остабляет сильный ток и усиливает слабый.
+
-
инфляция (inflation) - сжимает кластера, усиливает сильный поток и ослабляет слабый.
+
-
+
-
Марковский алгоритм кластеризации — быстрый и масштабируемый алгоритм кластеризации, основанный на моделировании потока в графе.
+
В данном алгоритме необходимо подбирать степь распространения и накачивании (так как это непосредственно вляйет на разбиение). Увеличение степени распространении - увеличивает средний размер кластера, в то время как увеличение степени накачивания - приводит к увеличению количества кластеров.
 +
В ходе выполнения алгоритма выделяются узлы которые являются "центрами" кластеров. Наглядная визуализация алгоритма приведена на рисунки 3. Как можно заметить в ходе работы алгоритма граф становится все менее и менее связным пока не будет разделен на кластеры.
-
[[Изображение:Markov_Clustering_Algorithm.jpeg|200px|thumb| Визуализация метода]]
+
[[Изображение:Markov_Clustering_Algorithm.jpeg|200px|thumb| Рисунок 3 Визуализация метода]]
 +
 
 +
 
 +
----
 +
==== Примеры способов кластеризации ====
 +
 
 +
 
 +
[[Изображение:MCL1.jpeg|200px|thumb| Рисунок 4 кластеризации простого графа методом MCL. Слева грав до кластеризации, справа после кластеризации]]
 +
 
 +
 
 +
Расмотрим работу данного метода на примере кластеризации простого графа и его смежной матрицы.
 +
 
 +
Возьмем граф состоящий из 12 вершин и составим для него матрицу вероятностей переходов между узлами. Так как граф является не взвешенным вероятности перехода между соседними узлами и вероятность остаться в этом узле будет равна 1/(количество ребер смежных с вершиной + 1). Матрица вероятностей переходов между узлами представленна вверху рисунка 5. Кроме этого на рисунке 5 представлен результат выполнения функции распространения без регулярной инфляции. Как не сложно заметить в результате этого получается полносвязный граф. Однако при выполнении инфляции в каждом цикле алгоритма приводит к выделению кластерной структуры алгоритма, это можно наблюдать на рисунке 6.
 +
 
 +
[[Изображение:MCL2.png|200px|thumb| Рисунок 5 экспансия без инфляции]]
 +
[[Изображение:MCL3.jpeg|200px|thumb| Рисунок 6 экспансия с инфляцией]]
----
----
-
итог по алгоритму
+
==== Плюсы и минусы алгоритма ====
 +
 
 +
#Плюсы алгоритма
#Плюсы алгоритма
##Работает как с взвешенными, так и с невзвешенными графами
##Работает как с взвешенными, так и с невзвешенными графами
Строка 73: Строка 92:
##Не подходит для кластеров большого размера
##Не подходит для кластеров большого размера
##Часто кластеры получаются разного размера
##Часто кластеры получаются разного размера
-
##Время работы алгоритма в наихудшем случае О(V^3)
+
##Время работы алгоритма в наихудшем случае Ο(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.]
-
 
+
#анализе изображений
-
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.
+
-
 
+
Список используемой литературы
Список используемой литературы

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


Данная статья является непроверенным учебным заданием.
Студент: Участник: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.

Личные инструменты