Марковский алгоритм кластеризации
Материал из MachineLearning.
Строка 2: | Строка 2: | ||
{{Задание|Konstantinov_bionet|Nvm|31 декабря 2018}} | {{Задание|Konstantinov_bionet|Nvm|31 декабря 2018}} | ||
- | + | ||
- | кластеризации, основанный на моделировании потока в графе. Он был создан в 2000 году | + | == Марковский алгоритм кластеризации == |
- | в Центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм имеет широкий спектр применений, например, для данных в | + | Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — быстрый и масштабируемый алгоритм кластеризации, основанный на моделировании потока в графе. Он был создан в 2000 году в Центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм имеет широкий спектр применений, например, для данных в |
молекулярной биологии. | молекулярной биологии. | ||
+ | |||
+ | |||
[[Изображение:Марковский_алгоритм_кластеризации.jpeg|thumb]] | [[Изображение:Марковский_алгоритм_кластеризации.jpeg|thumb]] | ||
+ | |||
+ | ---- | ||
+ | общее описание метода | ||
+ | |||
+ | Алгоритм основан на двух функциях expansion и inflation. | ||
+ | |||
+ | 1) expansion - разширяем поток из вершины на потенциальных участников кластера. | ||
+ | 2) inflation - уменьшаем переходы между кластерами и увеличиваем внутри кластера. | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | итог по алгоритму | ||
+ | #Плюсы алгоритма | ||
+ | ##Работает как с взвешенными, так и с невзвешенными графами | ||
+ | ##Устойчив к шуму в данных | ||
+ | ##Количество кластеров не указано заранее, но можно настроить степень детализации кластера с параметрами | ||
+ | #Минусы алгоритма | ||
+ | ##Не удается найти перекрывающиеся кластеры (*) | ||
+ | ##Не подходит для кластеров большого размера | ||
+ | ##Часто кластеры получаются разного размера | ||
+ | |||
+ | |||
+ | |||
+ | ---- | ||
Список используемой литературы | Список используемой литературы |
Версия 14:16, 28 октября 2018
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Марковский алгоритм кластеризации
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — быстрый и масштабируемый алгоритм кластеризации, основанный на моделировании потока в графе. Он был создан в 2000 году в Центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм имеет широкий спектр применений, например, для данных в молекулярной биологии.
общее описание метода
Алгоритм основан на двух функциях expansion и inflation.
1) expansion - разширяем поток из вершины на потенциальных участников кластера. 2) 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.