Марковский алгоритм кластеризации
Материал из 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.
