Способы кластеризаци на графе

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Способы кластеризаци на графе == Граф состоит из двух типов объектов 1) вершин(узлов)- V 2)ребер (пар ...)
(Способы кластеризаци на графе)
Строка 1: Строка 1:
== Способы кластеризаци на графе ==
== Способы кластеризаци на графе ==
 +
[[Категория:Кластеризация]]
 +
{{Задание|Konstantinov_bionet|Nvm|31 декабря 2018}}
Граф состоит из двух типов объектов 1) вершин(узлов)- V
Граф состоит из двух типов объектов 1) вершин(узлов)- V
Строка 48: Строка 50:
CNM
CNM
-
 
-
 
-
[[Категория:Кластеризация]]
 
-
{{Задание|Konstantinov_bionet|Nvm|31 декабря 2018}}
 

Версия 14:57, 5 ноября 2018

Способы кластеризаци на графе

Данная статья является непроверенным учебным заданием.
Студент: Участник:Konstantinov_bionet
Преподаватель: Участник:Nvm
Срок: 31 декабря 2018

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Граф состоит из двух типов объектов 1) вершин(узлов)- V 
2)ребер (пар вершин соединенных между собой) - E. Более формальная запись G:=(V,E)

Кроме этого каждый граф можно представить в виде матрицы смежности (M) размером V*V. Где Mij= растоянию между узлом i и узлом j.

Графы часто возникают при упрощении сложных систем. К примеру в виде графа удобно отображать:

  1. взамосвязи различных сайтов в интернете
  2. Социальные сети (сети контактов)
  3. Генные сети в молекулярной биологии
  4. порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер).

Spectral SCAN CPM Walktrap Bigclam LPA NewmanGreedy CNM

И в связи с необходимостью распозновать образы и кластера в больших графах необходимы способы кластеризации.

В качестве метрики растояния можно использовать суммы длин ребер (или их количества) между двумя точками, что по сути является евклидовой метрикой.


Парадигма кластеризации графа. Парадигма кластеризации графа постулирует, что «Естественные» группы в графах, обладают следующей характеристикой: При случайном обходе графа и поподании в кластер, мы не выйдем из него пока не обойдем многие вершины в нем.

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

Spectral

SCAN

CPM

Walktrap

Bigclam

LPA

NewmanGreedy

CNM

Личные инструменты