DBSCAN 聚类地理位置超出 epsilon 值

Question

我正在尝试分析一些工作的纬度和经度数据。工作的性质意味着它们往往发生在相似（尽管不相同）的纬度/经度位置

为了减少要显示和分析的数据点数量，我想将类似地理区域的工作聚集在一起。为此，我使用 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的理解有误吗？簇可以覆盖大于等效 epsilon 值的区域吗？如果有的话有没有更合适的聚类算法？

或者我的 DBSCAN 实现是否存在某种缺陷？

Answer 1

你对DBSCAN的理解是错误的

DBSCAN 将通过将项目链接在一起形成一个更大的连续组来进行聚类，其中至少有

min_samples

个点

radius_km

远。请注意，并非簇中的所有点都需要远离质心

radius_km

因此，在您的示例中，来自同一集群的两个点可以相距 100 公里，只要它们之间存在至少 50 个点的链，每个点最多相距 2 公里

更符合您要求的算法是

Canopy Clustering。不幸的是，它没有包含在大多数库中，但可以在https://gist.github.com/gdbassett/528d816d035f2deaaca1找到一个简单的实现。如果您希望项目仅属于单个集群，请设置 T1=T2=2km