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

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

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

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

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

---

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

Алгоритм основан на двух функциях expansion и inflation.

1) expansion - разширяем поток из вершины на потенциальных участников кластера. 2) inflation - уменьшаем переходы между кластерами и увеличиваем внутри кластера.

---

итог по алгоритму

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

---

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

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.