Марковский алгоритм кластеризации
Материал из MachineLearning.
Строка 4: | Строка 4: | ||
== Марковский алгоритм кластеризации == | == Марковский алгоритм кластеризации == | ||
+ | |||
+ | План работы над статьей | ||
+ | |||
+ | * расписать общую постановку задачи (до 2018.11.04) | ||
+ | * расписать общий принцип алгоритма (до 2018.11.10) | ||
+ | * своровать/нарисовать нужные картинки (до 2018.11.17) | ||
+ | * разобраться с влиянием expansion и inflation на качество кластеризации (до 2018.11.24) | ||
+ | * разобраться с ortoMCL и написать пунк о практическом применении метода в биологии (до 2018.12.04) | ||
+ | |||
+ | |||
+ | |||
Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — быстрый и масштабируемый алгоритм кластеризации, основанный на моделировании потока в графе. Он был создан в 2000 году в Центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм имеет широкий спектр применений, например, для данных в | Марковский алгоритм кластеризации (MCL, Markov Clustering Algorithm) — быстрый и масштабируемый алгоритм кластеризации, основанный на моделировании потока в графе. Он был создан в 2000 году в Центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм имеет широкий спектр применений, например, для данных в | ||
молекулярной биологии. | молекулярной биологии. | ||
- | [[Изображение: | + | [[Изображение:Markov_Clustering_Algorithm.jpeg|thumb]] |
---- | ---- |
Версия 14:26, 28 октября 2018
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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 году в Центре математических и компьютерных наук в Нидерландах. На сегодняшний день данный алгоритм имеет широкий спектр применений, например, для данных в молекулярной биологии.
общее описание метода
Алгоритм основан на двух функциях 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.