为什么 KNN 的余弦距离比欧几里得距离快得多？

Question

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

如此大的差异背后的原因是什么？我知道 scikit learn 使用球树或 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 台式机上复制了效果。

Answer 1

正如 @igrinis 所指出的，这在最新稳定版本的 scikit-learn (0.24.1) 中不再是问题。无论如何，我认为我即将写的内容可能是一个促成因素。

根据文档：

1. metric=euclidean使用测量距离sqrt(sum((x - y)^2))
2. metric=cosine使用此公式测量距离。

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

如果您想进一步加快速度，可以考虑使用线性内核，它可能会产生与 相同的结果cosine，但拟合速度会更快，因为不涉及分母（意味着没有除法）。