具有附加功能的 DBSCAN 聚类

Question

我可以将 DBSCAN 与定位以外的其他功能一起使用吗？如果可用，如何通过 R 或 Spark 完成？

我尝试准备一个 R table 的 3 列，其中一列用于纬度、经度和分数（除了 space 特征之外我还想聚类的特征）并且在尝试时运行使用以下 R 代码的 DBSCAN，我得到以下图表，该图表表明该算法在每对列 (long, lat), (long, score), (lat, score), ...

我的 R 代码：

df = read.table("/home/ahmedelgamal/Desktop/preparedData")
var = dbscan(df, eps = .013)
plot(x = var, data = df)

和我得到的情节：

Answer 1

您需要扩展数据。 V3 的范围比 V1 和 V2 的范围大得多，因此 DBSCAN 目前主要忽略 V3。

Answer 2

你误解了情节。

您不会在每个图上获得一个结果，但所有图都显示相同的聚类，只是属性不同。

但你也有一个问题，即 R 版本（据我所知）仅在 Euclidean 距离内快速。

在您当前的代码中，如果 (lat[i]-lat[j])^2+(lon[i]-lon[j])^2+(score[i]-score[j])^2 <= eps^2，点就是邻居。这很糟糕，因为：1. 纬度和经度不是欧几里德，您应该改用半正弦函数，并且 2. 您的附加属性具有 更大的比例，因此您几乎只有得分接近零的聚类点 ，以及 3) 你的分数属性有偏差。

对于这个问题，您可能应该使用广义 DBSCAN。如果它们的 haversine 距离小于例如点，则点是相似的。 1 英里（你想在这里测量地理距离，而不是坐标，因为失真）并且如果他们的分数相差 factor 最多 1.1（即比较 score[y] / score[x] 或工作在日志空间？）。由于您希望 both 条件成立，通常的 Euclidean DBSCAN 实现还不够，但您需要一个允许 多个条件 的广义 DBSCAN。寻找通用 DBSCAN 的实现（我相信 ELKI 中有一个您可以从 Spark 访问的），或者自己实现。做起来并不难。

如果二次运行时间适合您，您可以使用任何基于距离矩阵的 DBSCAN，并且只需 "hack" 二进制距离矩阵：

计算 Haversine 距离
计算分数差异
distance = 0 if haversine < distance-threshold and score-dissimilarity < score-threshold, otherwise 1.
运行具有预先计算的距离矩阵和 eps=0.5 的 DBSCAN（因为它是二进制矩阵，请不要更改 eps！）

速度相当快，但需要 O(n^2) 内存。根据我的经验，如果你有更大的数据，ELKI 的索引会产生很好的加速，如果你运行内存或时间不足，则值得一试。

具有附加功能的 DBSCAN 聚类

DBSCAN Clustering with additional features

r

cluster-analysis

dbscan

apache-spark