Найдите связанные компоненты в графе в MATLAB

У меня есть много точек 3D-данных, и я хочу найти на этом графике «связанные компоненты». Именно здесь формируются кластеры, обладающие следующими свойствами:

  • Каждый кластер содержит точки, каждая из которых находится на максимальном расстоянии от другой точки в кластере.
  • Все точки в двух различных кластерах находятся как минимум на расстоянии друг от друга.

Эта проблема описана в вопросе и ответе здесь.

Есть ли реализация такого алгоритма в MATLAB, встроенная или доступная на FEX? Простые поиски ничего полезного не выдали.


matlab cluster-analysis
person Bill Cheatham    schedule 31.12.2010    source источник
comment
Вы можете взглянуть на JUNG 'Java Universal Network/Graph Framework' jung.sourceforge.net/presentations/JUNG_M2K.pdf с использованием возможностей Java MATLAB.   -  person zellus    schedule 01.01.2011

Ответы (3)


arrow_upward
1
arrow_downward

Возможно, в этом случае можно применить алгоритм кластеризации на основе плотности. См. этот связанный вопрос для описание алгоритма DBscan.

person Amro    schedule 31.12.2010
comment
Спасибо. Это делает именно то, что я хочу. - person Bill Cheatham; 12.01.2011

arrow_upward
0
arrow_downward

Я не думаю, что можно удовлетворить обоим условиям во всех случаях.

Если вы решите сосредоточиться на первом условии, вы можете использовать иерархическую кластеризацию Complete-Linkage, в которой точки или группы точек объединяются на основе максимального расстояния между любыми двумя точками. В Matlab это реализовано в CLUSTERDATA (см. справку для отдельной функции шаги).

Чтобы рассчитать индексы вашего кластера, вы должны запустить

clusterIndex = clusterdata(coordiantes,maxDistance,'criterion','distance','linkage','complete','distance','euclidean')

Если затем вы хотите просто удалить точки разных кластеров, расстояние между которыми меньше minDistance, вы можете запустить pdist между кластерами, чтобы очистить подключенные компоненты.

person Jonas    schedule 01.01.2011

arrow_upward
0
arrow_downward

В этом случае может быть полезен алгоритм k-means или k-medoid.

person mary    schedule 19.08.2011
comment
Привет, Мэри, добро пожаловать в StackOverflow! Вы могли бы сделать свой ответ еще более полезным, предоставив несколько ссылок. Поскольку вопрос конкретно о реализациях MATLAB, знаете ли вы какие-либо для предлагаемого вами алгоритма? - person Jonas Heidelberg; 21.08.2011