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

比較のためだけに必要な場合は、平方距離を使用できます（math.sqrt - 遅い操作を削除してください）。

可能な最適化 - Pythonの操作((train[0] - test[0]) ** 2は、指数による給電を使用している場合、（1）Pythonのループは非常に遅いです

def squared_euc_dist(self, train, test): 
    x = train[0] - test[0] 
    y = train[1] - test[1] 
    return x * x + y * y 

Answer 2

単純な乗算に変更する価値があります。配列計算を使用する方法を学ぶ。 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）すべての場合、試して測定（プロファイル）してください。実行時パフォーマンスの最適化に対処する際に直感に頼らないでください。

P.S.上記のコードスニペットは、（意図的に）あなたのコードに正確にマッピングされません。それをどのように適応させるかは、あなた次第です。ヒント：2D配列;）