machine-learning - KNN の KD ツリー検索が機能しないのはいつですか?

Question

KNN (K Nearest Neighbors 問題) の KD Trees について調査し、学習してきましたが、いつ検索が機能しないのでしょうか? または、単純な検索を改善する価値があるかどうか。このアプローチの欠点はありますか？

Answer 1

Kd ツリーは、高次元 (非常に多くのツリー ブランチを訪問する必要がある場合) ではうまく機能しません。経験則の 1 つは、データの次元が である場合、kd ツリーは、データ ポイントkが より多い場合にのみ有効になるということです。2^k

高次元では、通常、近似最近傍検索に切り替えることをお勧めします。まだ実行していない場合は、FLANN ( github ) が非常に便利なライブラリです (C、C++、python、および matlab API を使用)。kd ツリー、総当たり検索、およびいくつかの近似手法の適切な実装があり、それらのパラメーターを自動的に調整してそれらを簡単に切り替えるのに役立ちます。

Answer 2

それはあなたの距離関数に依存します。

任意の距離関数で kd-trees を使用することはできません。ただし、ミンコフスキーの基準は問題ないはずです。しかし、多くのアプリケーションでは、より高度な距離関数を使用する必要があります。

さらに、次元数が増えると、kd-trees はあまりうまく機能しなくなります。

理由は簡単です。kd-tree は、境界までの 1 次元距離が既に目的のしきい値よりも大きい点、つまりユークリッド距離 (z は最も近い境界、y は既知の点を閉じる) よりも大きい点を見ないようにします。

(x_j - z_j)      <=>   sqrt(sum_i((x_i - y_i)^2))
equivalently, but cheaper:
(x_j - z_j)^2    <=>   sum_i((x_i - y_i)^2)

この剪定規則が保持される可能性は、次元数とともに大幅に減少することが想像できます。100 次元の場合、1 次元の差の 2 乗が差の 2 乗の合計よりも大きくなる可能性はほとんどありません。