Группировка геометрических точек по пространственной близости

Question

У меня есть следующие точки в трехмерном пространстве:

Мне нужно группировать точек, согласно D_max и d_max:

D_max = max dimension of each group
d_max = max distance of points inside each group

Примерно так:

Форма группы на изображении выше выглядит следующим образомполе, но форма может быть любой, что будет выводом алгоритма группировки .

---

Я использую Python и визуализирую результаты с помощью Blender.Я рассматриваю возможность использования scipy.spatial.KDTree и вызова его query API, однако я не уверен, что это правильный инструмент для работы под рукой.Я беспокоюсь, что может быть лучший инструмент, о котором я не знаю.Мне любопытно узнать, есть ли какой-нибудь другой инструмент / библиотека / алгоритм, который может мне помочь.

---

Как указывал @CoMartel, существует DBSCAN , а также Модули кластеризации HDBSCAN , которые хорошо подходят для такого рода задач.Однако, как отмечает @Paul, у них нет опции для максимального размера кластера, который соответствует моему параметру D_max.Я не уверен, как добавить функцию максимального размера кластера к кластеризации DBSCAN и HDBSCAN.

---

Благодаря @ Anony-Mousse я наблюдал Агломерационная кластеризация: как она работает и Иерархическая кластеризация 3: одиночная ссылка против полной ссылки и я изучаю Сравнение алгоритмов кластеризации Python , я чувствую, что становится все яснее, как работают эти алгоритмы.

Answer 1

Используйте иерархическую агломерационную кластеризацию .

Если вы используете полная связь , вы можете контролировать максимальный диаметр кластеров.Полная ссылка - это максимальное расстояние.

Параметр epsilon DBSCAN равен , а не максимальному расстоянию, поскольку несколько шагов соединяются транзитивно.Кластеры могут стать намного больше, чем эпсилон!

Answer 2

Алгоритм кластеризации DBSCAN с максимальным расстоянием точек внутри каждой группы расширений

Вы можете использовать алгоритм DBSCAN рекурсивно.

def DBSCAN_with_max_size(myData, eps = E, max_size = S):
     clusters = DBSCAN(myData, eps = E)
     Big_Clusters = find_big_clusters(clusters)
     for big_cluster in Big_Clusters:
         DBSCAN_with_max_size(big_cluster ,eps = E/2 ,max_size = S) //eps is something lower than E (e.g. E/2)

Answer 3

По запросу мой комментарий в качестве ответа:

Вы можете использовать DBSCAN (http://scikit -learn.org / stable / modules / generate / sklearn.cluster.DBSCAN.html ) или HDBSCAN.

Оба этих алгоритма позволяют группировать каждую точку в соответствии с d_max (максимальное расстояние между двумя точками одного и того же набора данных), но они не принимают максимальный размер кластера.Единственный способ ограничить максимальный размер кластера - это уменьшить параметр eps, который контролирует максимальное расстояние между двумя точками одного кластера.