python - 在给定距离内对点进行分组的算法

Question

我目前正在寻找一种高效算法，该算法从三维空间中获取一组点并将它们分组到类中(可能由一个列表表示)。如果一个点靠近该类中的一个或多个其他点，则该点应属于该类。如果两个类共享任何点，则它们是相同的。因为我正在处理大型数据集，所以我不想使用递归方法。此外，我尽量避免使用类似具有 O(n^2) 性能的距离矩阵。

我试图在线检查一些算法，但大多数算法都没有针对这个特定目的(例如 k-d 树或其他聚类算法)。我考虑过将空间分成更小的部分，但这(可能)会导致结果不准确。

我试图自己写点东西，但结果是有缺陷的。我会根据距离对我的点进行排序，并将距离附加为第四个坐标，然后重复以下代码段:

def grouping_presorted(lst, distance):
    positions = [0]
    x = []
    while positions:
        curr_el = lst[ positions[-1] ]
        nn_i = HasNeighbor(lst, distance, positions[-1])

        if nn_i is None:
            x.append(lst.pop(positions[-1]) )
            positions.pop(-1)
        else:
            positions.append(nn_i)
    return x

def HasNeighbor(lst,distance,index):
    i =  index+1
    while lst[i][3]- lst[index][3] < distance:
        dist = (lst[i][0]-lst[index][0])**2 + (lst[i][1]-lst[index][1])**2 + (lst[i][2]-lst[index][2])**2
        if dist < distance:
            return i
        i+=1
    return None

除了一个(可能很容易修复的)溢出错误之外，链接点的逻辑还有一个更大的缺陷。如果您认为我的点描述空间中的线，则该算法仅适用于严格指向原点外的线，但不适用于圆或类似结构。

有人知道为此预先编写的代码或知道我可以尝试什么吗？

提前致谢。

编辑: 看来我的拼写和一些术语的混淆引发了一些误解。我希望这个(制作糟糕的)草图能有所帮助。在这个例子中，我将我的引用距离标记为 d 并用红色圈出了我不想结束的两个容器。

Answer 1

你可以试试 https://en.wikipedia.org/wiki/OPTICS_algorithm .当您首先索引点时(例如，使用 R 树)，这应该可以在 O(n log n) 中实现。

编辑:

如果您已经知道您的 epsilon 以及一个簇中最少有多少个点 (minpoints)，那么 DBSCAN 可能是更好的选择。