python - 在 knn 算法中计算距离而不是欧氏距离的替代有效方法

Question

我已经实现了 knn 算法，这是我计算欧几里得距离的函数。

def euc_dist(self, train, test):
    return math.sqrt(((train[0] - test[0]) ** 2) + ((test[1] - train[1]) ** 2))

#
def euc_distance(self, test):
    eu_dist = []
    for i in range(len(test)):
        distance = [self.euc_dist(self.X_train[j], test[i]) for j in range(len(self.X_train))]
        eu_dist.insert(i, distance)


    return eu_dist

有没有更有效的方法来执行距离计算？？

Answer 1

(1) Python 循环非常慢。学习使用数组计算，例如numpy :

import numpy as np

x = np.array(...)
y = np.array(...)
distances = np.sqrt(np.sum((x-y)**2)) 

批处理计算可以实现高效的矢量化甚至并行实现。

(2) 如果您不需要绝对距离值(例如，您只比较它们的幅度或平均值或以某种方式对结果进行归一化)，则省略平方根运算，它非常慢。省略是可能的，因为 sqrt 是单调函数(即省略它会保留总顺序)。

squared_distances = np.sum((x-y)**2)

(3) 除了欧几里得之外，可能还有其他距离定义可能对您的特定问题有意义。您可以尝试找到更简单和更快的定义，例如一个简单的减法或绝对错误。

error = x-y
absolute_error = np.abs(x-y)

(4) 在所有情况下，尝试测量(profile)。在处理运行时性能优化时，不要依赖直觉。

附言上面的代码片段并没有完全(有意)映射到您的代码。学习如何适应它们取决于您。提示:二维数组 ;)