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

Question

我在3D中有以下几点space：

我需要根据D_max和d_max分组点：

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

像这样：

上图中组的形状看起来像一个盒子，但形状可以是 grouping 算法输出的任何形状。

我正在使用 Python 并使用 Blender 可视化结果。我正在考虑使用 scipy.spatial.KDTree and calling its query API，但是，我不确定这是否适合手头的工作。我担心可能有一个我不知道的更好的工具。我很想知道是否还有其他 tool/library/algorithm 可以帮助我。

正如@CoMartel 所指出的，DBSCAN and also HDBSCAN clustering 模块看起来很适合解决此类问题。但是，正如@Paul 所指出的，他们缺少与我的 D_max 参数相关的集群最大大小的选项。我不确定如何向 DBSCAN 和 HDBSCAN 集群添加最大集群大小功能。

感谢@Anony-Mousse 我看了Agglomerative Clustering: how it works and Hierarchical Clustering 3: single-link vs. complete-link and I'm studying Comparing Python Clustering Algorithms，我觉得这些算法是如何工作的越来越清楚了。

Answer 1

应要求，我的评论作为回答：

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

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

Answer 2

使用层次凝聚聚类。

如果你使用complete linkage你可以控制簇的最大直径。完整的link是最大距离。

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)

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

Group geometry points according to spatial proximity

python

cluster-analysis

dbscan

scikit-learn