在其他数据框中找到最近的点（有大量数据）

Question

问题很简单我有两个DataFrame：

一个拥有90 000公寓的人和他们的latitude/longitude
和一个拥有 3 000 药房和他们的 latitude/longitude

我想为我所有的公寓创建一个新变量：'distance of the nearest pharmacy'

为此，我尝试了两种方法，这两种方法花费了很多时间：

第一种方法： 我创建了一个矩阵，其中我的公寓在行中，我的药房在列中，它们之间的距离在交叉路口，然后我只取最小值具有 90 000 值的列向量的矩阵

我只是在 numpy 中使用了 double for :

m,n=len(result['latitude']),len(pharma['lat'])
M = np.ones((m,n))
for i in range(m):
     for j in range(n):
        if (result['Code departement'][i]==pharma['departement'][j]):
            M[i,j] =(pharma['lat'][j]-result['latitude'][i])**2+(pharma['lng'][j]-result['longitude'] [i])**2

ps ：我知道 lat/long 的公式错误，但公寓位于同一地区，所以这是一个很好的近似值

第二种方法：我使用这个主题的解决方案（谁是同样的问题，但数据较少） https://gis.stackexchange.com/questions/222315/geopandas-find-nearest-point-in-other-dataframe

我使用了 geopandas 和最近的方法：

from shapely.ops import nearest_points
pts3 = pharma.geometry.unary_union


def near(point, pts=pts3):
     nearest = pharma.geometry == nearest_points(point, pts)[1]
     return pharma[nearest].geometry.get_values()[0]

appart['Nearest'] = appart.apply(lambda row: near(row.geometry), axis=1)

正如我所说，这两种方法都花费了太多时间，在运行 1 小时后，我的 pc/notebook 崩溃并失败了。

我的最后一个问题：你有优化的方法来更快吗？有可能的？如果它已经优化过，我会购买另一台 PC，但是要满足哪些条件，要寻找哪些条件才能让 PC 能够进行如此快速的计算？

Answer 1

我想 Ball Tree 是适合此任务的结构。

您可以使用 scikit-learn 实现，请参阅下面的代码以获取适合您情况的示例：

import numpy as np
import geopandas as gpd
from shapely.geometry import Point
from sklearn.neighbors import BallTree

## Create the two GeoDataFrame to replicate your dataset
appart = gpd.GeoDataFrame({
        'geometry': Point(a, b),
        'x': a,
        'y': b,
    } for a, b in zip(np.random.rand(100000), np.random.rand(100000))
])

pharma = gpd.GeoDataFrame([{
        'geometry': Point(a, b),
        'x': a,
        'y': b,
    } for a, b in zip(np.random.rand(3000), np.random.rand(3000))
])

# Create a BallTree 
tree = BallTree(pharma[['x', 'y']].values, leaf_size=2)

# Query the BallTree on each feature from 'appart' to find the distance
# to the nearest 'pharma' and its id
appart['distance_nearest'], appart['id_nearest'] = tree.query(
    appart[['x', 'y']].values, # The input array for the query
    k=1, # The number of nearest neighbors
)

用这个方法你可以很快解决你的问题（上面的例子，在我的电脑上，在100000点的输入数据集上用了不到一秒的时间找到最近点的索引，在3000个点中).

默认情况下，BallTree 的 query 方法返回到最近邻居的距离及其 ID。如果您愿意，可以通过将 return_distance 参数设置为 False 来禁用返回最近邻居的距离。如果你真的只关心距离，你可以只保存这个值：

appart['distance_nearest'], _ = tree.query(appart[['x', 'y']].values, k=1)

在其他数据框中找到最近的点（有大量数据）

Find nearest point in other dataframe (WITH A LOT OF DATA)

python

optimization

nearest-neighbor

pandas

geopandas