根据空间接近度对几何点进行分组

Question

我在3D空间中有以下几点：

根据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 clustering模块，看起来非常适合这类问题。但是，正如@Paul指出的那样，他们缺少与我的D_max参数相关的群集最大大小的选项。我不确定如何为DBSCAN和HDBSCAN群集添加最大群集大小功能。

---

感谢@ Anony-Mousse，我观看了Agglomerative Clustering: how it works和Hierarchical Clustering 3: single-link vs. complete-link，我正在研究Comparing Python Clustering Algorithms，我觉得这些算法的运作方式越来越清晰。

Answer 1

根据要求，我的评论作为答案：

您可以使用DBSCAN（http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html）或HDBSCAN。

这两种算法都允许根据d_max（同一数据集的2个点之间的最大距离）对每个点进行分组，但它们不采用最大簇大小。限制群集最大大小的唯一方法是减少epsparameter，它控制同一群集的2个点之间的最大距离。

Answer 2

使用分层凝聚聚类。

如果使用完整链接，则可以控制簇的最大直径。完整链接是最大距离。

DBSCAN的epsilon参数不是最大距离，因为可以传递多个步骤。集群可以变得比epsilon大得多！

Answer 3

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)