从随机样本(python)构建一个近似均匀的网格

Question

我想从采样数据构建网格.我可以使用机器学习 - 聚类算法,如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)

    #This method is very slow even before doing any 'pruning'

方法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)) # where dist is a cython compiled function
        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 = 50000
r = 0.1
x1 = np.random.rand(N)
x2 = np.random.rand(N)
X = np.vstack([x1, x2]).T

tic = 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.840130090714
Method 1: 2.23365592957
Method 2: 0.774812936783

Answer 1

从这个问题中我不确定你到底想做什么。您提到想要创建一个“近似网格”或“均匀分布”，而您提供的代码选择点的子集，使得没有成对距离大于r。

一些可能的建议：

• 如果你想要的是一个近似网格，我会构造你想要近似的网格，然后查询每个网格点的最近邻居。根据您的应用程序，您可以进一步将这些结果修剪为距网格点的距离大于对您有用的点。

• 如果您想要的是从点之间得出的近似均匀分布sklearn.neighbors.KernelDensity，我将在每个点处进行核密度估计（ ），并从数据集中进行随机子选择，并按每个点处的局部密度的倒数进行加权。

• 如果您想要的是点的子集，使得没有成对距离大于 r，我将首先构造一个radius_neighbors_graph半径r，它将一次性为您提供所有距离太近的点的列表。然后，您可以使用类似于上面编写的修剪算法来根据这些稀疏图距离删除点。

我希望这有帮助！

Answer 2

我想出了一个非常简单的方法，比我以前的尝试要有效得多。

这个只是循环数据集，并且仅当当前点到所有现有中心的距离大于 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 = 40000
r = 0.1
x1 = 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]).T

tic = 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.219595909119
Method 2: 0.191949129105
Method 3: 0.0127329826355