基于函数值和接近度的聚类点

Question

我有很多点 X 和它们的函数值 f 存储在 numpy 数组中。我想在 X 中找到 所有点 在距离 r 内没有更好的点（较小的 f 值）。

X 是几十万点，所以我不能预先计算 sp.spatial.distance.pdist(X) 而是求助于以下：

def cluster(X,f,r):
    pts,n = np.shape(X)
    centers = []
    for i in range(0,pts):
        pdist = sp.spatial.distance.cdist(X,[X[i]])
        if not np.any(np.logical_and(pdist <= r, f < f[i])):
            centers.append(i)
    return centers

这需要几分钟。有没有一种方法可以根据接近度和另一个指标快速聚类？

Answer 1

您可以对 space 进行分区，这样您就可以忽略完全超出被测点半径的分区。

你也可以按f排序，这样你就不需要扫描那些值较小的点了。

Answer 2

我认为可以总结为：

使用k近邻构建kdtree。用半径查询树中靠近查询点的点，检查它们的函数值。

x=scipy.random.rand(10000,2) # sample data
f = exp(-x[:,0]**2) # sample function values
K=scipy.spatial.KDTree(x) # generate kdtree of data set
ix = K.query_point_ball(x[0],0.1) # query indices of points within 0.1 of x[0] in euclidean norm
# check f[ix] for your function criterion

感兴趣的可以一次性查询所有点

ix = K.query_point_ball(x,0.04)

Answer 3

您可以通过保留记录显着减少距离计算的次数。例如，如果 j 是中心 i 的邻居并且它具有较大的 f 值，那么 j 永远不会成为中心，因为它的邻居之一是 i 具有较小的 f 值。请检查以下内容，如果您需要说明，请告诉我。

def cluster4(X,f,r):
    pts,n = np.shape(X)
    centers = np.ones((pts,1),dtype=int)
    for i in range(pts):
        if not centers[i]:
            continue
        pdist = sp.spatial.distance.cdist(X,[X[i]])
        inrange = (pdist <= r)
        inrange[i] = False
        lesser = (f < f[i])
        if np.any(inrange & lesser):
            centers[i] = 0
        centers[inrange & np.invert(lesser)] = 0
    return np.where(centers == 1)[0]

基于函数值和接近度的聚类点

Clustering points based on their function values and proximity

python

numpy

scipy

cluster-analysis