给定距离内的点分组算法

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可能是更好的选择。

Answer 2

调整路径搜索算法，例如Dijkstra或A *，或者调整图的广度优先或深度优先搜索。从一组未访问点中的任何一点开始，然后继续使用您选择的任何算法，并注意一点被认为仅连接到距离小于阈值的所有点。当您完成一个类（即，当您无法发现新节点时）时，从未访问的节点集中选择任何节点并重复。

Answer 3

我最终做了什么

在完成了你的评论的所有建议之后，来自cs.stackexchange的帮助并做了一些研究，我能够写下两种不同的方法来解决这个问题。如果有人可能感兴趣，我决定在这里分享。同样，问题是编写一个程序，它接受一组坐标元组并将它们分组成簇。如果存在元素序列x = x_1，...，y = x_N，则d（x_i，x_i + 1），两个点x，y属于同一簇。

---

DBSCAN：通过修正欧几里德度量，minPts = 2并且分组距离epsilon = r。 scikit-learn提供了这种算法的一个很好的实现。该任务的最小代码段将是：

from sklearn.cluster import DBSCAN
from sklearn.datasets.samples_generator import make_blobs
import networkx as nx
import scipy.spatial as sp

def cluster(data, epsilon,N): #DBSCAN, euclidean distance
    db     = DBSCAN(eps=epsilon, min_samples=N).fit(data)
    labels = db.labels_ #labels of the found clusters
    n_clusters = len(set(labels)) - (1 if -1 in labels else 0) #number of clusters
    clusters   = [data[labels == i] for i in range(n_clusters)] #list of clusters
    return clusters, n_clusters

centers = [[1, 1,1], [-1, -1,1], [1, -1,1]]
X,_ = make_blobs(n_samples=N, centers=centers, cluster_std=0.4,
                            random_state=0)
cluster(X,epsilon,N)

在我的机器上，对于这种聚类变化，N = 20000，epsilon = 0.1的epsilon只需要290ms，所以这对我来说似乎很快。

---

图形组件：人们可以将此问题想象如下：坐标定义图形的节点，如果它们的距离小于epsilon / r，则两个节点相邻。然后给出一个簇作为该图的连通分量。起初我在实现此图时遇到了问题，但是有很多方法可以编写线性时间算法来执行此操作。然而，对我来说，最简单和最快捷的方法是使用scipy.spatial的cKDTree数据结构和相应的query_pairs（）方法，该方法返回给定距离内的点的indice元组列表。例如，可以这样写：

class IGraph:
    def __init__(self, nodelst=[], radius = 1):
        self.igraph = nx.Graph()
        self.radii  = radius
        self.nodelst = nodelst #nodelst is array of coordinate tuples, graph contains indices as nodes
        self.__make_edges__()

    def __make_edges__(self):
        self.igraph.add_edges_from( sp.cKDTree(self.nodelst).query_pairs(r=self.radii) )

    def get_conn_comp(self):
        ind = [list(x) for x in nx.connected_components(self.igraph) if len(x)>1]
        return [self.nodelst[indlist] for indlist in ind]


def graph_cluster(data, epsilon):
    graph = IGraph(nodelst = data, radius = epsilon)
    clusters = graph.get_conn_comp() 
    return clusters, len(clusters)

对于上面提到的相同数据集，此方法需要420毫秒才能找到连接的组件。但是，对于较小的集群，例如N = 700，此代码段运行得更快。它似乎也有一个优势，可以找到更小的聚类（给出更小的epsilon值）和另一个方向的巨大缺点（当然所有这些都在这个特定的数据集上）。我认为，根据具体情况，两种方法都值得考虑。

希望这对某人有用。

编辑：从理论上讲，DBSCAN在正确实现时具有计算复杂度O（n log n）（根据维基百科...），同时构建图形以及查找其连接的组件在时间上线性运行。我不确定这些语句对于给定的实现有多好。