根据每个点的最近邻距离,在最佳网格上插入非结构化的X,Y,Z数据

Question

在我使用的show final solution的答案之后编辑了这个问题

我有来自不同来源的非结构化2D数据集,例如: 这些数据集是3 numpy.ndarray(X,Y坐标和Z值).

我的最终目标是在网格上插入这些数据以转换为图像/矩阵.所以,我需要找到插入这些数据的"最佳网格".而且,为此,我需要在该网格的像素之间找到最佳的X和Y步长.

根据点之间的欧氏距离确定步骤:

使用每个点与其最近邻居之间的欧几里德距离的平均值.

• 使用KDTree/ cKDTree来自scipy.spacial用于X,Y数据的构建树.
• 使用query方法k=2获取距离(如果k=1,距离仅为零,因为查询每个点找到自己).

    # Generate KD Tree
    xy = np.c_[x, y]  # X,Y data converted for use with KDTree
    tree = scipy.spacial.cKDTree(xy)  # Create KDtree for X,Y coordinates.

    # Calculate step
    distances, points = tree.query(xy, k=2)  # Query distances for X,Y points
    distances = distances[:, 1:]  # Remove k=1 zero distances
    step = numpy.mean(distances)  # Result

性能调整:

• 使用scipy.spatial.cKDTree而不是scipy.spatial.KDTree因为它真的更快.
• 使用balanced_tree=False带scipy.spatial.cKDTree:在我的情况极大的提升速度,但对于所有的数据可能不是真的.
• 使用n_jobs=-1与cKDTree.query使用多线程.
• 使用p=1与cKDTree.query用于曼哈顿距离代替欧氏距离的(p=2):快,但可能不太准确.
• 仅查询点的随机子样本的距离:大型数据集加速,但可能不太准确且重复性较差.

在网格上插入点:

使用计算的步骤在网格上插入数据集点.

    # Generate grid
    def interval(axe):
        '''Return numpy.linspace Interval for specified axe'''
        cent = axe.min() + axe.ptp() / 2  # Interval center
        nbs = np.ceil(axe.ptp() / step)  # Number of step in interval
        hwid = nbs * step / 2  # Half interval width 
        return np.linspace(cent - hwid, cent + hwid, nbs)  # linspace

    xg, yg = np.meshgrid(interval(x), interval(y))  # Generate grid

    # Interpolate X,Y,Z datas on grid
    zg = scipy.interpolate.griddata((x, y), z, (xg, yg))

如果像素距离首字母点太远,则设置NaN:

将NaN设置为距离初始X,Y,Z数据的点太远(距离>步长)的网格像素.使用先前生成的KDTree.

    # Calculate pixel to X,Y,Z data distances
    dist, _ = tree.query(np.c_[xg.ravel(), yg.ravel()])
    dist = dist.reshape(xg.shape)

    # Set NaN value for too far pixels
    zg[dist > step] = np.nan

Answer 1

我建议你一起去KDTree.query。

您正在搜索一个特征距离来缩放您的分箱：我建议您仅采用点的随机子集，并使用曼哈顿距离，因为KDTree.query它非常慢（但它是 *log(n) 复杂性）。

这是我的代码：

# CreateTree
tree=scipy.spatial.KDTree(numpy.array(points)) # better give it a copy?
# Create random subsample of points
n_repr=1000
shuffled_points=numpy.array(points)
numpy.random.shuffle(shuffled_points)
shuffled_points=shuffled_points[:n_repr]
# Query the tree
(dists,points)=tree.query(shuffled_points,k=2,p=1)
# Get _extimate_ of average distance:
avg_dists=numpy.average(dists)
print('average distance Manhattan with nearest neighbour is:',avg_dists)

我建议您使用曼哈顿距离（https://en.wikipedia.org/wiki/Taxicab_geometry），因为它的计算速度比欧几里德距离更快。由于您只需要平均距离的估计器，因此应该足够了。