Как идентифицировать кластеры узлов в сети - PullRequest
1 голос
/ 22 мая 2011

У меня есть таблица, описывающая несколько наборов связанных узлов:

node
origin_node REFERENCES node
start_time
end_time

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

A, B, 10:00, 11:00
B, C, 9:00, 9:15
D, E, 10:00, 10:15
B, A, 13:00, 13:30
E, B, 12:00, 13:20
F, G, 9:00, 9:15

... тогда у меня было бы 2 кластера {A, B, C, D, E} и {F, G}

(времена в значительной степени не имеют значения - просто нужно продемонстрировать этот узел +origin_node не обязательно уникален / упорядочен).

Но я немного застрял в разработке алгоритма, который идентифицирует кластеры из нескольких тысяч строк.

Я работаю с MySQL 5.0.22 - поэтому у меня нет CONNECT BY, и у меня есть доступ к PHP и awk, хотя мне было бы легче понять алгоритм, а не кодированное решение.И поскольку анализ данных занимает не более пары часов, я склоняюсь к простоте, а не к порядку.

Кстати: это реальная проблема, а не домашняя работа (я перестал быть студентом,давным-давно - возможно, слишком рано;)

TIA

Ответы [ 2 ]

0 голосов
/ 17 июня 2011

Пошёл с обходом сети и пометкой посещенных узлов (аналогично алгоритмам сборки мусора).Это достаточно эффективно, но нужно немного кода.

0 голосов
/ 22 мая 2011

мне было бы легче понять алгоритм, а не кодированное решение

пробовал эти ссылки?

http://en.wikipedia.org/wiki/Cluster_analysis

http://en.wikipedia.org/wiki/Category:Data_clustering_algorithms

Кроме того, хотя и не MySQL, на сайте Microsoft также есть кое-что:

http://msdn.microsoft.com/en-us/library/ms174879.aspx


Редактировать, за ваш комментарий:

В вашем конкретном случае может сработать что-то похожее на создание таблицы закрытия.

Использование временной таблицы ...

Начните с произвольного узла. Назначьте его новому кластеру.

Следующий узел. Есть ли ссылка на узел из идентифицированного в данный момент кластера?

  • Если нет, назначьте его новому кластеру.

  • Если да, назначьте его этому кластеру. Затем для каждой ссылки убедитесь, что уже обработанный узел находится в том же кластере. Если нет, переназначьте их на этот кластер.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...