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

Question

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

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

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