我将对包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)
有谁知道余弦相似性的速度差异的原因？
我对scikit-learn一无所知，但我可以从数学角度猜测为什么它可能会变慢。
定义
假设您有两个具有 n 维的向量(A 和 B(。
两个向量的欧几里得距离计算公式为
Sqrt((A_1 - B_1)^2 + (A_2 - B_2)^2 + ... + (A_N - B_N)^2)
其中A_m是 A 中的第 m 个元素。要计算它，您需要计算 n 个差值、n 个乘积和 1 个平方根。
两个向量的余弦定义为
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有多大，但这可能是你看到差异的一个原因。
假设cosine_distance是一个 Python 函数：
虽然 sklearn 允许您指定自定义距离函数，但性能并不是特别好。对于每个距离，它都需要在 Python 解释器中设置一个回调。这自然比内置函数使用的编译本机代码慢得多。
这种开销似乎不会很快在Python上得到解决。可能需要修改 sklearn 源代码(以添加新的内置函数(或使用像 Java 这样具有良好 JIT 的东西(例如，ELKI 可以通过这种方式扩展，并且对于自定义距离要快得多(。
Jython听起来很酷(JVM上的Python(，但据我所知不支持numpy，因此也不支持sklearn。而且我不知道它是否可以将Python编译成字节码，或者它只是一个解释器。