地理空间点对相似度与距离计算的高效算法优化需求

问题背景 #

需要计算GeoDataFrame中所有点对的地理距离、基于Value列的曼哈顿相似度，同时关联Name等字段。但原始循环+apply的方案在大数据集下速度极慢，且itertools.combinations会因大量重复地理点产生冗余计算，因此需要更高效的实现思路。

示例数据与原始低效代码 #

示例GeoDataFrame

import geopandas as gpd
from shapely.geometry import Point

data = {
    'Name': ['A', 'B', 'C', 'D', 'E'],
    'Value': [10, 20, 10, 30, 20],
    'geometry': [Point(0,0), Point(1,1), Point(0,0), Point(2,2), Point(1,1)]
}
gdf = gpd.GeoDataFrame(data, crs="EPSG:4326")

原始低效代码（循环+apply）

import pandas as pd

results = []
for i in range(len(gdf)):
    for j in range(i+1, len(gdf)):
        row_i = gdf.iloc[i]
        row_j = gdf.iloc[j]
        geo_dist = row_i.geometry.distance(row_j.geometry)
        manhattan_sim = abs(row_i.Value - row_j.Value)
        results.append({
            'Name1': row_i.Name,
            'Name2': row_j.Name,
            'GeoDistance': geo_dist,
            'ManhattanSimilarity': manhattan_sim
        })
result_df = pd.DataFrame(results)

高效优化方案 #

核心思路：先聚合唯一地理点，减少重复计算；再通过向量化运算+批量展开得到最终结果

方案1：基于唯一点ID的关联计算

适合中等规模重复点的场景：

1. 给唯一地理点分配ID，标记原始行对应的点ID

# 给每个唯一geometry分配唯一ID
gdf['point_id'] = gdf['geometry'].astype('category').cat.codes
# 提取唯一点集合
unique_points = gdf[['point_id', 'geometry']].drop_duplicates().set_index('point_id')

2. 向量化计算唯一点间的距离矩阵

# 生成唯一点的距离矩阵（向量化运算，比循环快10-100倍）
distance_matrix = unique_points.geometry.apply(lambda x: unique_points.geometry.distance(x)).unstack()
# 转换为长格式的点对距离数据，仅保留point_id1 < point_id2的非重复对
unique_distances = distance_matrix.stack().reset_index()
unique_distances.columns = ['point_id1', 'point_id2', 'GeoDistance']
unique_distances = unique_distances[unique_distances['point_id1'] < unique_distances['point_id2']]

3. 生成原始行点对并关联距离、计算相似度

import numpy as np
from itertools import combinations

# 提取原始行的索引、point_id、Name、Value信息
index_info = gdf.reset_index()[['index', 'point_id', 'Name', 'Value']]
# 生成所有i<j的原始行索引对
index_pairs = list(combinations(index_info['index'], 2))
pair_df = pd.DataFrame(index_pairs, columns=['idx1', 'idx2'])

# 关联两边的Name、Value、point_id
pair_df = pair_df.merge(index_info, left_on='idx1', right_on='index').drop('index', axis=1)
pair_df = pair_df.merge(index_info, left_on='idx2', right_on='index', suffixes=('_1', '_2')).drop('index', axis=1)

# 匹配唯一点的距离（处理point_id1 > point_id2的反向情况）
pair_df = pair_df.merge(unique_distances, left_on=['point_id_1', 'point_id_2'], right_on=['point_id1', 'point_id2'], how='left')
mask = pair_df['point_id_1'] > pair_df['point_id_2']
pair_df.loc[mask, 'GeoDistance'] = pair_df.loc[mask].apply(lambda x: distance_matrix.loc[x['point_id_2'], x['point_id_1']], axis=1)

# 计算曼哈顿相似度
pair_df['ManhattanSimilarity'] = abs(pair_df['Value_1'] - pair_df['Value_2'])

# 整理最终结果
final_result = pair_df[['Name_1', 'Name_2', 'GeoDistance', 'ManhattanSimilarity']].rename(columns={'Name_1':'Name1', 'Name_2':'Name2'})

方案2：分组聚合+批量展开（适合大量重复点场景）

当同一地理点对应成百上千条数据时，此方案效率更高：

1. 按地理点分组，收集每组的Name和Value列表

grouped = gdf.groupby('geometry').agg({
    'Name': list,
    'Value': list
}).reset_index()

2. 计算组间点对的距离并展开所有Name组合

from itertools import combinations, product

# 生成组间的非重复对
group_pairs = list(combinations(grouped.index, 2))
group_pair_df = pd.DataFrame(group_pairs, columns=['g1', 'g2'])

# 关联组信息并计算地理距离
group_pair_df = group_pair_df.merge(grouped, left_on='g1', right_index=True)
group_pair_df = group_pair_df.merge(grouped, left_on='g2', right_index=True, suffixes=('_1', '_2'))
group_pair_df['GeoDistance'] = group_pair_df['geometry_1'].distance(group_pair_df['geometry_2'])

# 展开组间的所有Name/Value对
def expand_group_pairs(row):
    name_pairs = product(row['Name_1'], row['Name_2'])
    value_pairs = product(row['Value_1'], row['Value_2'])
    return pd.DataFrame({
        'Name1': [n1 for n1, n2 in name_pairs],
        'Name2': [n2 for n1, n2 in name_pairs],
        'GeoDistance': row['GeoDistance'],
        'ManhattanSimilarity': [abs(v1-v2) for v1, v2 in value_pairs]
    })

group_result = pd.concat([expand_group_pairs(row) for _, row in group_pair_df.iterrows()], ignore_index=True)

3. 补充组内的点对（同一地理点的不同Name）

inner_pairs = []
for _, row in grouped.iterrows():
    if len(row['Name']) < 2:
        continue
    # 生成组内的非重复Name对
    for (n1, v1), (n2, v2) in combinations(zip(row['Name'], row['Value']), 2):
        inner_pairs.append({
            'Name1': n1,
            'Name2': n2,
            'GeoDistance': 0.0,
            'ManhattanSimilarity': abs(v1-v2)
        })
inner_result = pd.DataFrame(inner_pairs)

# 合并组间和组内结果
final_result = pd.concat([group_result, inner_result], ignore_index=True)

预期输出 #

两种方案最终都会得到与原始代码一致的结果：

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