ScipyのKd-tree関数を使用してK-Nearest Neighbors（KNN）をスピードアップする方法

Question

Scipy's Kd-treeを使用してKNN検索を高速化する方法を検討していますが、ツリーを作成し、2）ツリーを使用して検索をスピードアップします。

私はNetflixトレーニングデータのパンダデータフレームを持っています。このデータフレームは、ユーザーの列、評価された各ムービーアイテム、および与えられた評価で構成されています（下記参照）。このトレーニングデータを使用して、テストユーザーの最近隣（KNN）を計算して、テストユーザーの評価を予測します。最近隣は、ユークリッド距離ではなくピアソンの相関係数を使用して計算されます。一番近いネイバーが計算されると、最も近いネイバーを使ってテストユーザーの評価を予測/推測したいと思います。

しかし、私のユーザーと映画のリストは大きく（ネットフリックスデータ）、何千もの映画の中の何千人ものユーザーに最も近いネイバーを計算するのが計算上不可能になります。 K最近傍を高速化する方法として、Kdツリーアプローチが提案されている。

ScipyのKdツリーを使用してこのアプローチを高速化する方法はありますか？もしそうなら、Kdツリーアプローチを利用するためには、データをどのような形式にする必要がありますか？この正確な質問のためにSki-kit学習機能が組み込まれていることはわかっていますが、これを個別に実装できる必要があります。

Goal: predict user 1 rating on movie 10 by finding most similar users 

Training data 
user movie rating 
2   7  5.0 
3  10  3.0 
4   4  1.0 
50  3363  2.0 
50  7  3.0 
83  50  4.0 
83  7  5.0 
etc 

Answer 1

ScipyのKDツリーは、p標準メトリック（p = 2が標準ユークリッド距離）をサポートしています。より一般的なメトリクスが必要な場合は、scikit-learnのBallTreeがさまざまなメトリックをサポートしています。特に、correlation metricはPearson相関係数に関連しているため、このメトリックを使用して効率的な検索を行うアルゴリズムをベースにすることができます。

つまり、数千のディメンションがある場合、ツリーベースのアプローチは、ブルートフォースよりも優れているとは限りません。相関距離のために設計されたハッシュ関数を用いて、Locality Sensitive Hashingのようなある種の近似アルゴリズムを使用する方が良いでしょう。