我想从采样数据中构建一个网格。我可以使用机器学习的聚类算法，比如k-means，但我想限制中心点大致均匀分布。
我已经想出了一种使用scikit-learn最近邻搜索的方法：随机选择一个点，删除半径r内的所有点，然后重复。这个方法效果不错，但我想知道是否有人有更好的（更快的）方法来做这件事。
根据评论，我尝试了两种替代方法，其中一种速度明显变慢，另一种速度大致相同…
方法0（我的第一次尝试）：
def get_centers0(X, r): N = X.shape[0] D = X.shape[1] grid = np.zeros([0,D]) nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') while N > 0: nearest.fit(X) x = X[int(random()*N), :] _, del_x = nearest.radius_neighbors(x) X = np.delete(X, del_x[0], axis = 0) grid = np.vstack([grid, x]) N = X.shape[0] return grid方法1（使用预计算图）：
def get_centers1(X, r): N = X.shape[0] D = X.shape[1] grid = np.zeros([0,D]) nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') nearest.fit(X) graph = nearest.radius_neighbors_graph(X) #这种方法在进行任何“修剪”之前就已经非常慢方法2：
def get_centers2(X, r, k): N = X.shape[0] D = X.shape[1] k = k grid = np.zeros([0,D]) nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') while N > 0: nearest.fit(X) x = X[np.random.randint(0,N,k), :] #min_dist = near.NearestNeighbors().fit(x).kneighbors(x, n_neighbors = 1, return_distance = True) min_dist = dist(x, k, 2, np.ones(k)) # 其中dist是一个用cython编译的函数 x = x[min_dist < 0.1,:] _, del_x = nearest.radius_neighbors(x) X = np.delete(X, del_x[0], axis = 0) grid = np.vstack([grid, x]) N = X.shape[0] return grid运行这些方法如下：
N = 50000r = 0.1x1 = np.random.rand(N)x2 = np.random.rand(N)X = np.vstack([x1, x2]).Ttic = time.time()grid0 = get_centers0(X, r)toc = time.time()print 'Method 0: ' + str(toc - tic)tic = time.time()get_centers1(X, r)toc = time.time()print 'Method 1: ' + str(toc - tic)tic = time.time()grid2 = get_centers2(X, r)toc = time.time()print 'Method 1: ' + str(toc - tic)方法0和方法2的速度大致相同…
Method 0: 0.840130090714Method 1: 2.23365592957Method 2: 0.774812936783回答：
我提出了一种非常简单的方法，比我之前的尝试效率高得多。
这个方法只是简单地遍历数据集，只有当当前点与所有现有中心点的距离大于r时，才将其添加到网格点列表中。这种方法比我之前的尝试快了大约20倍。因为没有涉及外部库，我可以全部在cython中运行…
@cython.boundscheck(False)@cython.wraparound(False)@cython.nonecheck(False)def get_centers_fast(np.ndarray[DTYPE_t, ndim = 2] x, double radius): cdef int N = x.shape[0] cdef int D = x.shape[1] cdef int m = 1 cdef np.ndarray[DTYPE_t, ndim = 2] xc = np.zeros([10000, D]) cdef double r = 0 cdef double r_min = 10 cdef int i, j, k for k in range(D): xc[0,k] = x[0,k] for i in range(1, N): r_min = 10 for j in range(m): r = 0 for k in range(D): r += (x[i, k] - xc[j, k])**2 r = r**0.5 if r < r_min: r_min = r if r_min > radius: m = m + 1 for k in range(D): xc[m - 1,k] = x[i,k] nonzero = np.nonzero(xc[:,0])[0] xc = xc[nonzero,:] return xc运行这些方法如下：
N = 40000r = 0.1x1 = np.random.normal(size = N)x1 = (x1 - min(x1)) / (max(x1)-min(x1))x2 = np.random.normal(size = N)x2 = (x2 - min(x2)) / (max(x2)-min(x2))X = np.vstack([x1, x2]).Ttic = time.time()grid0 = gt.get_centers0(X, r)toc = time.time()print 'Method 0: ' + str(toc - tic)tic = time.time()grid2 = gt.get_centers2(X, r, 10)toc = time.time()print 'Method 2: ' + str(toc - tic)tic = time.time()grid3 = gt.get_centers_fast(X, r)toc = time.time()print 'Method 3: ' + str(toc - tic)新方法的速度提高了大约20倍。如果我提前停止循环（例如，如果连续k次迭代未能产生新的中心点），它可能会变得更快。
Method 0: 0.219595909119Method 2: 0.191949129105Method 3: 0.0127329826355