Марковский алгоритм кластеризации
Материал из MachineLearning.
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Марковский алгоритм кластеризации
План работы над статьей
- расписать общую постановку задачи (до 2018.11.04)
- расписать общий принцип алгоритма (до 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)
Графы помимо теоритической математики часто возникают при упрощении сложных систем. К примеру в виде графа удобно отображать порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер). Кластеры в графе возникают в силу необходимости распознания образов и подгруппы в больших графах.
В качестве метрики растояния можно использовать суммы длин ребер (или их количества) между двумя точками, что по сути является евклидовой метрикой.
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 лежит идея моделирования потока (случайного блуждания) внутри графа. т.е. если усиливать поток там где он силен и ослаблять его там где он слаб то согласно парадигме кластеризации графа границы между различными кластерами будут исчезать. Таким образом будет выявлена кластерная структура в графе.
Моделирование потока через граф легко осуществляется путем преобразования его в марковский граф.
где ток силен, и уменьшать поток, когда ток слабый. Если естественные группы присутствуют на графике, то согласно парадигме тока через границы между различными группами будут отмирать, тем самым выявив кластерную структуру в график.
2,
т. е. график, где для всех узлов веса исходящих дуг суммируются с одним. Поток может быть расширена за счет вычислительных степеней связанной стохастической (марковской) матрицы, которая составляет обычный дискретный марковский процесс. Это само по себе недостаточно, поскольку Марковский процесс не показывает структуру кластера в своем базовом графе. Парадигма обеспечивается введением нового оператора в марковский процесс, называемый инфляция. В то время как расширение потока представлено обычным матричным продуктом, представляет собой входной продукт Адамара-Шура в сочетании с диагональю масштабирование. Оператор инфляции несет ответственность за укрепление и ослабление ток. Оператор расширения отвечает за то, что поток позволяет подключать разные областей графика. Полученный алгебраический процесс называется кластерным процессом Маркова или процессом MCL. процесс сходится квадратично в окрестности так называемого двудомного идемпотента матрицы (идемпотент как при расширении, так и в инфляции).
В этих двух статьях двугой подход к кластеризации на графе:
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.
Кластерный анализ и кластеры в графе
Предпологается что кластера в графе образуют сгущения, в то время как между кластерми есть пустоты(??)
Марковский процес кластеризации
Эксперименты и практическое применение MCL
общее описание метода
Алгоритм основан на двух функциях expansion и inflation.
1) expansion - разширяем поток из вершины на потенциальных участников кластера. 2) inflation - уменьшаем переходы между кластерами и увеличиваем внутри кластера. расширение (expansion) - объединяет кластера, остабляет сильный ток и усиливает слабый. инфляция (inflation) - сжимает кластера, усиливает сильный поток и ослабляет слабый.
итог по алгоритму
- Плюсы алгоритма
- Работает как с взвешенными, так и с невзвешенными графами
- Устойчив к шуму в данных
- Количество кластеров не указано заранее, но можно настроить степень детализации кластера с параметрами
- Минусы алгоритма
- Не удается найти перекрывающиеся кластеры (*)
- Не подходит для кластеров большого размера
- Часто кластеры получаются разного размера
Список используемой литературы
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.
