DBSCAN聚类地理坐标超ε范围，求原因分析与替代算法建议

我正在分析一批工作的纬度和经度数据，这类工作通常发生在相似（但不完全相同）的经纬度位置。为了减少展示和分析的数据量，我希望将同一地理区域的工作聚类在一起，因此使用DBSCAN进行聚类，并选取簇中心附近的工作点作为代表点。

实现代码如下：

import pandas as pd, numpy as np
from sklearn.cluster import DBSCAN
from geopy.distance import great_circle
from shapely.geometry import MultiPoint

def cluster_with_dbscan(jobs, radius_km, min_samples):

    # ignore jobs that are missing Lat Long coords for now
    jobs_cluster = jobs[['Job ID', 'Lat', 'Long']].dropna()

    # run dbscan
    kms_per_radian = 6371.0088
    epsilon = radius_km / kms_per_radian
    coords = jobs_cluster[['Lat', 'Long']].values
    db = DBSCAN(eps=epsilon, min_samples=min_samples, algorithm='ball_tree', metric='haversine').fit(np.radians(coords))

    # appending cluster data onto original jobs, preserving jobs that never had location data
    jobs_cluster['Cluster ID'] = db.labels_
    jobs_with_cluster = pd.merge(jobs, jobs_cluster[['Job ID', 'Cluster ID']], how='left', on=['Job ID'])

    # capture cluster data, including centroids
    num_clusters = len(set(db.labels_))
    clusters = pd.Series([coords[db.labels_ == n] for n in range(num_clusters)])

    def get_centermost_point(cluster):
        if len(cluster) == 0:
            return tuple([None,None])
        centroid = (MultiPoint(cluster).centroid.x, MultiPoint(cluster).centroid.y)
        centermost_point = min(cluster, key=lambda point: great_circle(point, centroid).m)
        return tuple(centermost_point)

    centermost_points = clusters.map(get_centermost_point)

    lats, lons = zip(*centermost_points)
    clusters = pd.DataFrame({'Lat':lats, 'Long':lons}).reset_index().rename(columns={'index':'Cluster ID'})

    return jobs_with_cluster,clusters

运行参数：

radius_km = 2
min_samples = 1 # want to keep outliers
jobs,clusters = cluster_with_dbscan(jobs, radius_km , min_samples )

运行后虽得到聚类结果，但部分簇内的工作点相距远超2公里（部分簇跨度达数百公里）。根据我的理解，DBSCAN的簇内点与核心点的距离应不超过2公里。请问是我对DBSCAN的理解有误？簇的覆盖范围可以超过等效ε值吗？如果是这样，有没有更合适的聚类算法？还是我的DBSCAN实现存在缺陷？

1. DBSCAN的簇确实可能超过ε范围 #

你的理解有部分偏差：DBSCAN的簇是通过核心点的链式连接形成的——如果点A是核心点，且点B在A的ε范围内；点B是核心点，点C在B的ε范围内，那么A、B、C会被归为同一簇，哪怕A和C的距离远超ε。这种“链式延伸”会导致簇的整体跨度远大于ε，这是DBSCAN的固有特性，不是算法故障。

2. 参数设置是核心问题 #

你设置了min_samples=1，这会彻底改变DBSCAN的行为：

• DBSCAN中，核心点的定义是：在ε范围内至少包含min_samples个点（包括自身）。当min_samples=1时，每个点都是核心点（因为每个点至少包含自己）。
• 此时，所有能够通过“相邻点距离≤ε”连接起来的点都会被归为同一个簇，哪怕这条链长达数百公里（只要每一步的相邻点都在2公里内）。这就是你看到超大簇的直接原因。

3. 代码中的潜在bug #

除了参数问题，你的get_centermost_point函数存在坐标顺序错误：

• Shapely的MultiPoint默认坐标顺序是**(经度, 纬度)（x对应经度，y对应纬度），但你的coords是[['Lat', 'Long']].values，即(纬度, 经度)**的顺序。
• 这会导致计算的质心坐标顺序颠倒，进而great_circle计算的距离出错，最终选出来的“中心最近点”可能不是真正的中心附近点。
• 修复方法：创建MultiPoint时调整坐标顺序，比如MultiPoint([(p[1], p[0]) for p in cluster])，然后质心的x是经度，y是纬度，再转换回（纬度, 经度）和原point比较。

4. 解决方案 #

（1）调整DBSCAN参数 #

不要设置min_samples=1，根据你的数据密度设置合理值（比如2-5）：

• min_samples至少为2时，核心点需要在ε范围内包含至少1个其他点，能有效避免长链式的超大簇，同时仍可保留孤立点（标记为-1）。

（2）换用严格限制簇内距离的算法 #

如果你需要簇内任意两点距离都不超过ε，DBSCAN不适合，推荐以下两种算法：

• 凝聚层次聚类（Agglomerative Clustering）：使用linkage="complete"（最大距离链接），合并簇的条件是两个簇之间的最大距离≤ε，这样能保证最终簇内所有点的距离都≤ε。示例代码片段：

  from sklearn.cluster import AgglomerativeClustering
  
  # 转换为弧度，使用haversine距离
  coords_rad = np.radians(jobs_cluster[['Lat', 'Long']].values)
  agg_clustering = AgglomerativeClustering(
      n_clusters=None,
      distance_threshold=epsilon,  # 和DBSCAN的epsilon一致（弧度单位）
      linkage='complete',
      metric='haversine'
  ).fit(coords_rad)
  jobs_cluster['Cluster ID'] = agg_clustering.labels_
  

• OPTICS算法：作为DBSCAN的改进版，它可以识别密度变化的簇，同时通过xi参数控制簇的切割，避免长链式结构。

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