7

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

方法二：

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
4

4 回答 4

4

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

几个可能的建议：

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

  • 如果您想要的是从点中提取的近似均匀分布，我会sklearn.neighbors.KernelDensity在每个点进行核密度估计 ( )，并从数据集中进行随机子选择，该数据集由每个点的局部密度的倒数加权。

  • 如果你想要的是一个点的子集，使得没有成对的距离大于 r，我会从构造一个radius_neighbors_graphwith radius开始r，它会一次性给你一个所有太靠近的点的列表。然后，您可以使用类似于您上面编写的修剪算法来根据这些稀疏图距离删除点。

我希望这会有所帮助！

于 2013-10-30T15:13:57.390 回答
4

我想出了一个非常简单的方法，它比我以前的尝试更有效率。

这只是简单地循环数据集并将当前点添加到网格点列表中，前提是它与所有现有中心的距离大于 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
于 2013-11-01T02:11:34.420 回答
1

也许您只能在nearest每 k << N 次删除中重新拟合对象以加快处理速度。大多数时候邻里结构不应该有太大变化。

于 2013-10-30T10:00:09.027 回答
0

听起来您正在尝试重新发明以下内容之一：

  • 集群特征（参见 BIRCH）
  • 数据气泡（请参阅“数据气泡：层次聚类的质量保持性能提升”）
  • 冠层预聚类

即这个概念已经被发明了至少三次，只是有很小的变化。

从技术上讲，它不是集群。K-means 也不是真正的聚类。

它被更恰当地描述为矢量量化。

于 2013-10-31T07:50:57.477 回答