时间戳

首页 > 解决方案 > 如何在保持精度的同时找到数据集中每个点的最近点？

python - 如何在保持精度的同时找到数据集中每个点的最近点？

问题描述

这是我的数据集： https ://pastebin.com/SsuKP2eH

我试图找到数据集中所有点的最近点。这些点是地球表面的纬度和经度。当然，最近的点不可能是同一个点。

我尝试了KDTree这篇文章中列出的解决方案：https ://stackoverflow.com/a/45128643并将海报的随机点（由 生成np.random.uniform）更改为我自己的数据集。

我希望得到一个充满距离的数组，但相反，我得到了一个充满零的数组，其中包含一些数字，例如 2.87722e-06 和 0.616582。这不是我想要的。NearestNeighbours我在我的数据集上尝试了另一种解决方案，得到了相同的结果。于是，我做了一些调试，缩小了他使用的随机数的范围，使其更接近我自己的数据集。

import numpy as np
import scipy.spatial as spatial
import pandas as pd

R = 6367

def using_kdtree(data):
    "Based on https://stackoverflow.com/q/43020919/190597"
    def dist_to_arclength(chord_length):
        """
        https://en.wikipedia.org/wiki/Great-circle_distance
        Convert Euclidean chord length to great circle arc length
        """
        central_angle = 2*np.arcsin(chord_length/(2.0*R)) 
        arclength = R*central_angle
        return arclength

    phi = np.deg2rad(data['Latitude'])
    theta = np.deg2rad(data['Longitude'])
    data['x'] = R * np.cos(phi) * np.cos(theta)
    data['y'] = R * np.cos(phi) * np.sin(theta)
    data['z'] = R * np.sin(phi)
    tree = spatial.KDTree(data[['x', 'y','z']])
    distance, index = tree.query(data[['x', 'y','z']], k=2)
    return dist_to_arclength(distance[:, 1])
    #return distance, index


np.random.seed(2017)
N = 1000
#data = pd.DataFrame({'Latitude':np.random.uniform(-90,90,size=N), 'Longitude':np.random.uniform(0, 360,size=N)})
data = pd.DataFrame({'Latitude':np.random.uniform(-49.19,49.32,size=N), 'Longitude':np.random.uniform(-123.02, -123.23,size=N)})

result = using_kdtree(data)

我发现结果距离数组的值很小，接近 0。这让我相信我的数据集的结果数组充满零的原因是因为点之间的差异非常小。在某个地方，KD 树/最近邻会丢失精度并输出垃圾。有没有办法让他们保持我的花车精度？蛮力方法可以保持精度，但迭代速度太慢，需要 7200 个点。

标签： pythonnumpyloops

解决方案

我认为正在发生的事情 k=2是

    distance, index = tree.query(data[['x', 'y','z']], k=2)

告诉KDTree你想要最接近一点的两点。所以最接近的显然是点本身，与自身的距离为零。此外，如果您打印index，您会看到一个 Nx2 数组，并且每一行都以行号开头。这KDTree就是说离第 i 个点最近的点就是第 i 个点本身。

显然这没有用，您可能只需要第二个最近点。幸运的是，我在k参数的文档中找到了这一点query

要返回的最近邻的数量，或者要返回的第 k 个最近邻的列表，从 1 开始。 https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree。 query.html#scipy.spatial.KDTree.query

所以

    distance, index = tree.query(data[['x', 'y','z']], k=[2])

仅给出第二个到最近点的距离和索引。

推荐阅读