Способы кластеризаци на графе
Материал из MachineLearning.
(→Способы кластеризаци на графе) |
(→Способы кластеризаци на графе) |
||
| Строка 15: | Строка 15: | ||
#порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер). | #порты, аэропорты, города (в качестве узлов графа)и пути их соединяюющие (в качестве ребер). | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
И в связи с необходимостью распозновать образы и кластера в больших графах необходимы способы кластеризации. | И в связи с необходимостью распозновать образы и кластера в больших графах необходимы способы кластеризации. | ||
| Строка 34: | Строка 26: | ||
[[Марковский алгоритм кластеризации]] | [[Марковский алгоритм кластеризации]] | ||
| + | |||
| + | [[Кластеризация графов без использования метрик (пример)]] | ||
Spectral | Spectral | ||
Версия 15:24, 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
