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

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

Перейти к: навигация, поиск


Данная статья является непроверенным учебным заданием.
Студент: Участник:Konstantinov_bionet
Преподаватель: Участник:Nvm
Срок: 31 декабря 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. Плюсы алгоритма
    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.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8»
Личные инструменты