2.5万门店匹配7.6万六边形区域：K近邻算法优化求助

问题描述 #

我需要解决以下场景的近邻匹配问题：

• 拥有约25000个带经纬度坐标的门店地址列表
• 拥有约76000个分属不同配送城市的六边形区域列表，每个区域包含质心坐标和多边形边界
• 核心需求：快速判定每个门店所属的六边形区域，暴力解法耗时约2天，因配送范围频繁变更，需要可高频运行的高效方案

门店数据示例 #

INDIRIZZO_COMPLETO  latitude    longitude   COORDINATE_EXTRACTION_DETAIL
0   LUNGOMARE LUIGI RIZZO 1, 92010 LAMPEDUSA E LIN...   35.497965   12.607482   from original address
1   VIA TERRANOVA 71, 92010 LAMPEDUSA E LINOSA (AG...   35.506421   12.610504   from original address
2   VIALE PAPA PIO XII 107/109, 00036 PALESTRINA (...   35.551062   12.320357   from zipcode: 36 Italy
3   VIA ROMA 82, 96010 PORTOPALO DI CAPO PASSERO (...   36.682967   15.133651   from original address
4   CONTRADA PIANETTI SNC, 96018 PACHINO (SR), SIC...   36.700497   15.073600   from zipcode: 96018 Italy

六边形区域数据示例 #

city_code   Polygon latitude    longitude
0   SCN POLYGON ((10.63303663611384 44.59771368472511,...   44.597003   10.635361
1   SCN POLYGON ((10.706225086720105 44.58751732975397...   44.586805   10.708550
2   BAR POLYGON ((16.939176495419776 41.09659615583256...   41.095711   16.941403
3   BAR POLYGON ((16.925717571722554 41.10755391076213...   41.106669   16.927944
4   BAR POLYGON ((16.89992580762363 41.067339007464646...   41.066454   16.902151

现有实现方案 #

tree = BallTree(np.deg2rad(df[['latitude', 'longitude']].values), metric='haversine')

distances, indices = tree.query(np.deg2rad(np.c_[query_lats, query_lons]), k = 5)

r_km = 6371 # multiplier to convert to km (from unit distance)
for name, d, ind in zip(df_other['INDIRIZZO_COMPLETO'], distances, indices):
  print(f"INDIRIZZO_COMPLETO {name} closest matches:")
  for i, index in enumerate(ind):
    print(f"\t{df['city_code'][index]} with distance {d[i]*r_km:.4f} km")
    list_data = (name, df['city_code'][index], d[i]*r_km)
    append_list_as_row(file_name_2, list_data)

现有方案仅在部分区域匹配正确，大量匹配结果错误，需要优化建议。

优化建议 #

1. 替换核心匹配逻辑：从质心距离转为多边形点-in-面判断 #

现有方案的核心问题是质心最近不代表门店实际在六边形内部——尤其是六边形密集分布、形状不规则或门店位于区域边界时，误差会极大。必须基于多边形边界做精确的点-in-面验证，这是保证匹配正确性的基础。

2. 用空间索引缩小候选范围，提升效率 #

直接暴力遍历所有六边形做点-in-面判断效率太低，可通过空间索引先筛选候选集合：

• 使用geopandas的sjoin方法，先通过内置的R树空间索引，快速筛选出门店可能归属的六边形（比如直接用predicate='within'做精确匹配，或用intersects先获取邻接区域）。
• 示例代码思路：

  import geopandas as gpd
  from shapely.geometry import Point
  
  # 转换门店数据为GeoDataFrame
  shops_gdf = gpd.GeoDataFrame(
      df_other,
      geometry=gpd.points_from_xy(df_other.longitude, df_other.latitude),
      crs="EPSG:4326"
  )
  
  # 转换六边形数据为GeoDataFrame（解析Polygon字段）
  hex_gdf = gpd.GeoDataFrame(
      df,
      geometry=gpd.GeoSeries.from_wkt(df['Polygon']),
      crs="EPSG:4326"
  )
  
  # 批量执行精确的点-in-面匹配
  matched_result = gpd.sjoin(shops_gdf, hex_gdf, how='left', predicate='within')
  
  # 处理未匹配的门店（比如位于所有六边形外的情况）
  unmatched_shops = matched_result[matched_result['city_code'].isna()]
  # 对未匹配门店，可再用近邻质心筛选候选后做二次验证
  

3. 优化坐标系与索引类型 #

• 将经纬度转换为平面坐标系（比如根据数据所在区域选择对应UTM投影的EPSG编码），用欧氏距离替代haversine距离，计算速度更快，小范围区域内精度足够。
• 优先使用R树索引（geopandas默认实现），相比BallTree更适合多边形的空间查询场景，能更高效地处理边界邻接、包含等关系。

4. 批量处理替代循环，减少开销 #

现有代码逐行遍历门店的方式效率低下，改用geopandas的批量空间操作，利用底层C扩展加速计算，避免Python循环的性能损耗。

5. 验证与调优匹配结果 #

• 随机抽取一定比例的匹配结果手动核对，确认错误类型（是边界判断遗漏，还是索引筛选错误）。
• 对边界附近的门店，可增加候选六边形的数量（比如将k值从5提升到10），确保不遗漏正确的归属区域。

内容的提问来源于stack exchange，提问作者michele