コサインの類似性を持つKDTreeを使用できますか？

Question

例えば、sklearn KDTreeでこの類似性メトリックを使用することはできませんが、私は測定ワードの類似性を使用しているので必要です。このケースでは、高速で堅牢なカスタマイズアルゴリズムとは何ですか？私はLocal Sensitivity Hashingについて知っていますが、調整して&がparamsを見つけるために多くのテストを行う必要があります。

Answer 1

コサインの類似性で得られるランキングは、すべてのデータ点を最初に正規化したときのユークリッド距離の順位と同じです。だからKDTreesを持つk最近傍にKDツリーを使うことができますが、コサインの類似性を再計算する必要があります。

コサイン類似度は、通常提示される距離メトリックではありませんが、1に変換できます。完了した場合、Ball Treeのような他の構造を使用して、コサインの類似性を使ってnnを高速化することができます。私はあなたがJavaの実装に興味があったなら、JSATライブラリでこれを実装しました。

Answer 2

table at the end of this pageによれば、コサインサポートはk-d-treeが可能でなければなりません。ELKIはR-treeで余弦をサポートし、k-d-treeの境界矩形も導出できます。 k-d-treeはそのテーブルの少なくとも5つのメトリックをサポートしています。だから私はなぜそれがうまくいかないのか分からない。 sklearnでのインデックス作成サポートは、残念ながら非常に完全ではありません（改善されていますが）。それを参考にしないでください。

kdツリーは、理論的コサインバウンディングボックスにバウンディングボックスと最小角度で作業

ユークリッド距離となるようにデータを変換

• によってコサイン変換をサポートすることができるが（すなわち、であるように見えます

kd-treeは、高次元のデータではうまく動作しません。コサインは、非常に高次元のデータでよく使われます。 k-d-treeは常に1つの次元のみを調べます。すべてのd次元を一度使用するには、O（2^d）のデータポイントが必要です。高いdの場合、すべての属性が使用される方法はありません。 バウンディングボックスを使用しているため、Rツリーの方がやや優れています。これらはすべてのディメンションの分割ごとに縮小されるので、プルーニングは改善されます。しかし、これはまた、そのようなデータのために多くのメモリを必要とすることを意味し、木構造は同じ問題を抱えている可能性があります。 本質的に、高次元のデータにはどちらも使用しないでください。

しかし、Cosineが魔法のように結果を向上させるとは思わない、特にhigh-dデータの場合。それは非常に過大評価されています。上記の変換が示すように、はがユークリッド上のコサインの系統的な利点ではありません。コサインはユークリッドの特別なケースです。

sparseデータの場合、反転リスト（Lucene、Xapian、Solr、...）は余弦のインデックス方法です。