为什么余弦距离比在 scikitlearn 中使用带有 DBSCAN 算法的欧氏距离慢得多

Question

我将为包 scikit-learn.

中的 DBSCAN 算法使用两个指标（欧氏距离和余弦相似度）

关键是使用欧氏距离比使用余弦相似度快得多。

代码：

// using euclidean distance    
DBSCAN(eps=0.02, min_samples=5, metric="euclidean").fit(data)

// using cosine similarity
DBSCAN(eps=0.02, min_samples=5, metric=cosine_distance).fit(data)

有谁知道造成速度与余弦相似度差异的原因吗？

Answer 1

我对scikit-learn一无所知，但我可以从数学的角度猜出为什么它可能更慢。

定义

假设您有两个维度为 n 的向量（A 和 B）。

Euclidean distance of two vectors计算为

Sqrt((A_1 - B_1)^2 + (A_2 - B_2)^2 + ... + (A_N - B_N)^2)

其中 A_m 是 A 中的第 m^th 元素。要计算它，你需要计算n个差值，n个乘积，1个平方根。

Cosine of two vectors定义为

cos(x) = A.B / |A||B|

哪里

A.B = A_1 * B_1 + A_2 * B_2 + ...  A_n * B_n
|A| = Sqrt((A_1)^2 + (A_2)^2 + ... + (A_N)^2)

所以 n 乘法 A.B 和 2.n 乘法得到 |A| 和 |B|.

比较

欧氏距离需要n次减法和n次乘法；余弦相似度需要 3.n 次乘法。

假设减法是计算密集型的（它几乎肯定会不那么密集），它是 2.n 对于欧几里得和3.n 用于余弦。

换句话说，与欧几里德距离相比，获得余弦差值至少要慢 50%。我不知道 scikit-learn 如何使用这些指标，或者你的 n 有多大，但这可能是你看到差异的原因。

Answer 2

假设 cosine_distance 是一个 Python 函数：

虽然 sklearn 允许您指定自定义距离函数，但性能并不是特别好。对于每个距离，它都需要设置一个回调到 Python interpreter。这自然比内置函数使用的编译本机代码慢得多。

Python 似乎不会很快解决此开销。可能需要修改 sklearn 源代码（以添加新的内置插件）或使用类似 Java 的东西和良好的 JIT（例如，ELKI 可以通过这种方式扩展，并且自定义距离更快）。

Jython 听起来很酷（Python 在 JVM 上），但据我所知不支持 numpy，因此也不支持 sklearn。而且我不知道它是否可以将Python编译成字节码，或者它是否只是一个解释器。

为什么余弦距离比在 scikitlearn 中使用带有 DBSCAN 算法的欧氏距离慢得多

Why cosine distance is much slower than using euclidean distance with DBSCAN algo in scikitlearn

python

scikit-learn