使用 DBSCAN 找到最密集的集群？

Question

我一直在查看 Geoff Boeing 在 DBSCAN 上的优秀博文。我最感兴趣的页面是 -

http://geoffboeing.com/2014/08/clustering-to-reduce-spatial-data-set-size/

如何将此方法修改为 return 最大簇的中心（被最多 lat/lng 点包围的簇中心）？每个集群的中心点是否有密度等级？

核心 dbscan -

db = DBSCAN(eps=.01, min_samples=1).fit(coordinates)
labels = db.labels_
num_clusters = len(set(labels)) - (1 if -1 in labels else 0)
clusters = pd.Series([coordinates[labels == i] for i in xrange(num_clusters)])
print('Number of clusters: %d' % num_clusters)

Answer 1

不幸的是，该博客 post 在一些关键点上是错误的。

从不将 DBSCAN 与 min_samples=1 一起使用。那就是单链接聚类。 如果要单联，就用单联，不要DBSCAN。在这里，Leader 集群可能也是一个不错的选择。
明智地选择eps。在他的例子中，他选择的 eps 太小了，他大部分删除了（接近）重复项...
DBSCAN 集群没有有意义的 center。因为它们可以是非 convex.In 特定的，所以中心需要考虑半正弦距离，而他没有。第一个版本使用均值，新版本使用最接近均值的点（但可能仍然失真，因为均值没有考虑地球）。
关于纬度、经度，您应该在聚类期间 使用大圆距离，而不仅仅是之后。（目前已在博客中修复）。

上面的第 3 点也回答了您的问题：DBSCAN 聚类 可能没有有意义的中心 。中心可以在集群之外。

自 original post 以来，改进了一些要点（尤其是第 4 点）。 DBSCAN 现在实际上使用了 haversine 和球树索引。

Answer 2

如果您有兴趣将最大的簇表示为 'central' 点（例如，降维），我会执行以下操作：

找到分类点数最多的簇：

# Assumes coordinates is a DataFrame
db = DBSCAN(eps=eps, min_samples=min_samples).fit(coordinates)
df = pd.DataFrame([coordinates.x, coordinates.y, db.labels_]).T # Add other attributes of coordinates if needed
df.columns = ['x', 'y','label']; # Add column names
max_label = df.label.mode()[0];

max_cluster = df[df['label']==max_label];

您可以取每一列的平均值

max_cluster_array = max_cluster[['x','y']].as_matrix()
print max_cluster_array.mean(axis=0) # what you are looking for

如果您有兴趣估计更可靠的 'central' 点，您还可以研究 multivariate kernel density estimation 函数。

Answer 3

我也在做一个类似的项目，并使用他的博客 post 作为指导。 return 最大簇中心的逻辑（但请注意，中心本身对于 DBSCAN 可能毫无意义）：按大小对簇进行排序，取最大的，计算质心（使用该博客中提供的逻辑post)。然后你有一个选择。您可以将计算出的质心保留为 "center point"，也可以在簇中找到最接近该质心的点（正如该博客 post 的作者所做的那样）。

与另一位回复者相反，该博客 post 在很多方面 并没有错：

单链接聚类在许多情况下都非常好用，包括博客 post 的作者正在使用的情况。
他的 eps 适合并适合他的用例，他解释说这明确意味着要删除近似重复项。
博客 post 关于聚类中心没有错 - 事实上它明确提到了非凸性，代码 return 是来自集群而不是集群的中心点本身。
博客中的代码 post 确实在 DBSCAN 聚类期间通过 haversine 度量使用大圆距离。

最重要的是，结果完全符合博客中的预期 post。

使用 DBSCAN 找到最密集的集群？

Using DBSCAN to find the most dense cluster?

python

cluster-analysis

dbscan

scikit-learn