为什么KNN算法使用余弦距离比欧几里得距离更快？

Question

我正在使用scikit learn拟合k最近邻分类器，并注意到当使用两个向量之间的余弦相似度时，拟合速度更快，通常比使用欧几里得相似度快一个数量级或更多。请注意，这两种方法都是sklearn内置的；我没有使用任何自定义实现。

为什么会有如此大的差异？我知道scikit learn使用Ball树或KD树来计算邻居图，但我不确定度量形式为什么会影响算法的运行时间。

为了量化效果，我进行了一次模拟实验，其中我使用欧几里得或余弦度量对随机数据进行了KNN拟合，并记录了每种情况下的运行时间。每种情况下的平均运行时间如下所示：

import numpy as np
import time
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
res=[]
n_trials=10
for trial_id in range(n_trials):
    for n_pts in [100,300,1000,3000,10000,30000,100000]:
        for metric in ['cosine','euclidean']:
            knn=KNeighborsClassifier(n_neighbors=20,metric=metric)
            X=np.random.randn(n_pts,100)
            labs=np.random.choice(2,n_pts)
            starttime=time.time()
            knn.fit(X,labs)
            elapsed=time.time()-starttime
            res.append([elapsed,n_pts,metric,trial_id])

res=pd.DataFrame(res,columns=['time','size','metric','trial'])
av_times=pd.pivot_table(res,index='size',columns='metric',values='time')
print(av_times)

编辑：这些结果来自于一台安装了 sklearn 版本为 0.21.3 的 MacBook。我也在一台安装了 sklearn 版本为 0.23.2 的 Ubuntu 台式机上复制了相同的效果。

- Simon Segert

---

我刚在replit上多次运行了你的代码，使用sklearn==0.24.2，没有发现任何显著差异。如果你正在使用相同版本的话，可能与你的本地机器有关。 - amin_nejad

@amin_nejad，非常有趣。我也尝试了一个不同的机器，使用版本23.2，得到了与我的问题类似的效果。查看更改日志，自版本23.2以来，KNN类进行了一些更改，但似乎没有明显相关的内容：https://scikit-learn.org/stable/whats_new/v0.24.html#version-0-24-0 - Simon Segert

我浪费了几分钟追寻"S-Euclidean"，但在scipy.spatial.distance中似乎有sqeuclidean - 没有稀疏矩阵，并且我不确定它是否可以用于KNeighborsClassifier()。另一个想法是为了时间分析目的修复算法，从brute开始。 - greybeard

尽管“欧几里得距离”和“余弦相似度”没有明确提到，但它们一定与“sklearn.neighbors”下的变更清单中列出的更改有关。 - amin_nejad

Answer 1

根据评论，尝试在KNN中使用algorithm='brute'，欧几里得时间加快，与余弦距离时间相匹配。但是尝试使用algorithm='kd_tree'和algorithm='ball_tree'都会出现错误，因为这些算法显然不接受余弦距离。所以看起来当分类器适合于algorithm='auto'模式时，它默认使用暴力算法来计算余弦度量，而对于欧几里得距离，它使用其他算法之一。查看变更日志，版本0.23.2和0.24.2之间的差异可能归结为以下内容：

neighbors.NeighborsBase 受益于改进的 algorithm = 'auto' 启发式方法。除了以前的一套规则外，现在当特征数超过15个时，选择brute，假设数据固有维数过高，无法使用基于树的方法。

因此，看起来两者之间的区别与度量无关，而是与高维情况下基于树的搜索和暴力搜索的性能有关。对于足够高的维数，树状搜索可能无法优于线性搜索，因此由于需要构造数据结构而产生的额外开销，整体运行时间会更慢。在这种情况下，由于基于树的算法不适用于余弦距离，所以实现被迫在余弦情况下使用更快的暴力搜索，但它（次优地）在欧几里得情况下选择了基于树的算法。看起来这种行为已经被注意并在最新版本中进行了纠正。

- Simon Segert

---

如果您引用了文档（或其他任何在线可用的资源），请同时包含相关的链接（编辑以添加）。 - desertnaut

Answer 2

正如@igrinis指出的那样，在scikit-learn的最新稳定版本（0.24.1）中，这已不再是一个问题。不管怎样，我认为我即将写的内容可能会成为一个贡献因素。

根据文档：

1. metric=euclidean使用sqrt(sum((x - y)^2))测量距离。 2. metric=cosine使用this formula来测量距离。

正如你所看到的，metric=cosine中没有平方根，这可能是第一个选项拟合时间更长的原因。

如果你想进一步加快速度，你可以考虑使用线性核函数，它可能会产生与余弦相似度相同的结果，但会更快地适应，因为分母不参与计算（意味着没有除法）。

- Arturo Sbr

---

此公式缺失。除此之外，现代处理器上计算平方根应该非常快（例如，在基于Skylake的处理器上可以每6个周期计算一个平方根，并且使用AVX SIMD指令每12个周期可以计算4个）。这几乎无法解释x55的减速，特别是这种减速随着输入大小的增加而增加...我猜测两个度量标准的算法不同（但可能是基于数学技巧的原因）。 - Jérôme Richard

我的错！我更新了答案。链接在代码片段里面。是的，算法可能完全不同。 - Arturo Sbr

有趣的假设，但我不认为这是原因。我刚刚重新运行了我的实验，包括“曼哈顿”距离选项，而那里的运行时间基本与欧几里德距离相同。请注意，曼哈顿距离的定义不包括平方根。 - Simon Segert

没有平方根在余弦度量中，这可能是为什么没有平方和度量的原因？单个值的单调函数不会改变顺序。（呃 - “总是复数”只适用于诗歌吗？英语...） - greybeard

Answer 3

我在Mac上运行了您的代码片段，使用的是sklearn 0.24.1版本，结果如下：

metric    cosine  euclidean
size                       
100     0.000322   0.000165
300     0.000205   0.000186
1000    0.000273   0.000271
3000    0.000503   0.000531
10000   0.001459   0.001326
30000   0.002919   0.002784
100000  0.008977   0.008872

所以很可能是实现问题，在v0.24中得到了修复。

- igrinis

Answer 4

简而言之，欧几里得距离中涉及到计算平方根，需要进行多次数学运算，而余弦距离可以直接计算，仅需4次运算。这就是为什么余弦距离比欧几里得距离更高效的原因。

- Pedro Kaneto Suzuki

---

计算机需要进行一个数学级数求和，这将导致许多操作。坦率地说：没有。 - greybeard

这个想法已经在Arturo Sbr的回答中提出过了（并且在该回答的评论中被驳斥了）。 - Simon Segert