基于Spark的地理定位点聚类：识别100米内邻近兴趣点集群

嘿，针对你这个从POI数据集里找出距离小于100米的点集群的需求，我刚好有个实用的解决方案，结合地理距离计算和简单的聚类逻辑就能实现，直接看具体步骤吧：

因为是经纬度坐标，不能直接用平面欧氏距离计算，得用Haversine公式计算地球表面的球面距离，然后筛选出间距小于100米的点对，最后整理成集群。

步骤1：实现经纬度转球面距离的函数 #

先写个计算两点间距离（单位：米）的工具函数：

import math

def haversine_distance(lat1, lon1, lat2, lon2):
    # 把经纬度转换成弧度（三角函数需要弧度输入）
    lat1_rad = math.radians(lat1)
    lon1_rad = math.radians(lon1)
    lat2_rad = math.radians(lat2)
    lon2_rad = math.radians(lon2)
    
    # Haversine核心公式
    dlat = lat2_rad - lat1_rad
    dlon = lon2_rad - lon1_rad
    a = math.sin(dlat/2)**2 + math.cos(lat1_rad) * math.cos(lat2_rad) * math.sin(dlon/2)**2
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    # 地球平均半径约6371公里，转换成米
    distance_m = 6371000 * c
    return distance_m

步骤2：加载数据并筛选符合条件的点对 #

假设你的数据可以用列表存储，我们遍历所有点对（避免重复计算，只处理i<j的情况），找出距离小于100米的点：

# 替换成你的实际数据集
poi_data = [
    (1, 48.860294, 2.338629),
    (2, 48.858093, 2.294694),
    (3, 48.8581965, 2.2937403),
    (4, 48.8529717, 2.3477134)
]

clusters = []
# 双重循环遍历点对，跳过重复的组合
for i in range(len(poi_data)):
    id1, lat1, lon1 = poi_data[i]
    for j in range(i + 1, len(poi_data)):
        id2, lat2, lon2 = poi_data[j]
        dist = haversine_distance(lat1, lon1, lat2, lon2)
        if dist < 100:
            clusters.append((id1, id2))

print("距离小于100米的点集群：", clusters)

运行这段代码后，输出正好是你预期的[(2, 3)]，完美匹配需求。

大数据量场景的优化方案 #

如果你的数据集有几千甚至上万个点，双重循环的效率会很低，这时候可以用KD-Tree空间索引来加速邻近点查询，Python的scipy库已经帮我们实现好了：

from scipy.spatial import KDTree
import numpy as np

# 提取经纬度并转成弧度（KDTree适合处理欧氏距离，转弧度后近似球面距离）
coords = np.radians([(lat, lon) for _, lat, lon in poi_data])
tree = KDTree(coords)

# 100米对应的弧度差：100米 / 地球半径（6371000米）≈ 1.57e-5弧度
radius = 100 / 6371000
clusters = []

for i in range(len(coords)):
    # 查询当前点周围radius范围内的所有点索引，排除自身
    nearby_indices = tree.query_ball_point(coords[i], radius)
    for j in nearby_indices:
        if j > i:  # 避免重复添加相同点对
            clusters.append((poi_data[i][0], poi_data[j][0]))

print("距离小于100米的点集群：", clusters)

这种方法能把时间复杂度从O(n²)降到O(n log n)，处理大数据量时速度提升非常明显。

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