Способы кластеризаци на графе
Материал из MachineLearning.
(Новая: == Способы кластеризаци на графе == Граф состоит из двух типов объектов 1) вершин(узлов)- V 2)ребер (пар ...) |
(→Способы кластеризаци на графе) |
||
Строка 1: | Строка 1: | ||
== Способы кластеризаци на графе == | == Способы кластеризаци на графе == | ||
+ | [[Категория:Кластеризация]] | ||
+ | {{Задание|Konstantinov_bionet|Nvm|31 декабря 2018}} | ||
Граф состоит из двух типов объектов 1) вершин(узлов)- V | Граф состоит из двух типов объектов 1) вершин(узлов)- V | ||
Строка 48: | Строка 50: | ||
CNM | CNM | ||
- | |||
- | |||
- | |||
- |
Версия 14:57, 5 ноября 2018
Способы кластеризаци на графе
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Граф состоит из двух типов объектов 1) вершин(узлов)- V 2)ребер (пар вершин соединенных между собой) - E. Более формальная запись G:=(V,E)
Кроме этого каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij= растоянию между узлом i и узлом j.
Графы часто возникают при упрощении сложных систем. К примеру в виде графа удобно отображать:
- взамосвязи различных сайтов в интернете
- Социальные сети (сети контактов)
- Генные сети в молекулярной биологии
- порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер).
Spectral SCAN CPM Walktrap Bigclam LPA NewmanGreedy CNM
И в связи с необходимостью распозновать образы и кластера в больших графах необходимы способы кластеризации.
В качестве метрики растояния можно использовать суммы длин ребер (или их количества) между двумя точками, что по сути является евклидовой метрикой.
Парадигма кластеризации графа. Парадигма кластеризации графа постулирует, что
«Естественные» группы в графах, обладают следующей характеристикой:
При случайном обходе графа и поподании в кластер, мы не выйдем из него пока не обойдем многие вершины в нем.
Марковский алгоритм кластеризации
Spectral
SCAN
CPM
Walktrap
Bigclam
LPA
NewmanGreedy
CNM