DBSCAN在sklearn中很慢

Question

我正在尝试对一个包含超过100万个数据点的数据集进行聚类。其中一列是文本，另一列是与之对应的数值。我面临的问题是程序会卡住并永远无法完成。我尝试使用大约10万个数据点的较小数据集，可以快速运行，但随着数据点数量的增加，它开始变慢，对于100万个数据点，它永远无法完成。最初，我认为可能是因为我的tfidf文本矩阵有100个维度，所以需要很长时间。然后我尝试基于每个数据点的单个数值进行聚类，但仍未能完成。以下是代码片段。您是否知道我可能做错了什么？我看到其他人处理更大的数据集，并没有出现问题。

Y=data['amount'].values
Y=Y.reshape(-1,1)
dbscan = DBSCAN(eps=0.3, min_samples= 10, algorithm='kd_tree')
dbscan.fit_predict(Y)
labels = dbscan.labels_
print(labels.size)
clusters = labels.tolist()
#printing the value and its label
for a, b in zip(labels, Y):
    print(a, b)

- Anshul Tripathi

---

你实际上等了多久才完成？ - Dr. Snoopy

“基于每个数据点仅有一个单一值的聚类”是什么意思？你是否对“eps”和“min_samples”进行了超参数调整？DBScan对这些参数非常敏感。即使是eps的微小变化也可能改变模型的行为。 - Kalsi

@MatiasValdenegro 我让它跑了一整晚，它还在运行。可能已经8个小时了。 - Anshul Tripathi

@Kalsi 我的意思是说，amount只是一个单一的特征，所以我的数据集是一个1百万行1列的矩阵，与文本相比，将其转换为tfidf矩阵后生成了100个特征。所以是一个1百万行100列的矩阵。 - Anshul Tripathi

虽然不是直接回答问题，但是open3d DBSCAN实现比sklearn快大约2倍（在我的Intel i7上对于10000个点的计算，open3d为34ms，而sklearn为62ms）。 - tiberius

Answer 1

很可能你的 epsilon 值太大了。

如果大多数点之间的距离都在 epsilon 范围内，那么运行时间将会是二次的 O(n²)。因此，请从 小 的值开始尝试！

你不能只是添加/删除特性而不改变 epsilon 值。

- Has QUIT--Anony-Mousse

---

为什么epsilon/点密度会改变运行时复杂度？无论如何都必须计算成对距离。 - Daniel

Answer 2

使用更多核心。

使用n_jobs参数。在DBSCAN类中定义为：n_jobs=-1

示例：

Y=data['amount'].values
Y=Y.reshape(-1,1)
dbscan = DBSCAN(eps=0.3, min_samples= 10, algorithm='kd_tree', n_jobs=-1)
dbscan.fit_predict(Y)
labels = dbscan.labels_
print(labels.size)
clusters = labels.tolist()
#printing the value and its label
for a, b in zip(labels, Y):
    print(a, b)

- seralouk