[解決済み] 高次元データにおけるニアレストネイバー？

質問

という質問をしたことがあります。 質問 数日前に、与えられたベクトルに対する最近傍を見つける方法について書きました。私のベクトルは現在21次元ですが、私は機械学習や数学の分野ではないので、先に進む前に、いくつかの基本的な質問を自分自身に投げかけはじめています。

• ユークリッド距離は、そもそも最近傍を見つけるのに適した指標なのか？そうでない場合、どのような選択肢があるのか？
• また、k-neighborsを決定するための適切な閾値はどのように決定すればよいのでしょうか？この値を決定するために、何か解析ができるのでしょうか？
• 以前、kd-Treeを使うことを提案されましたが、Wikipediaのページには、高次元の場合、kd-Treeはほとんど総当たり検索と同じだとはっきり書かれています。この場合、100万点のデータセットから効率的に最近傍を見つけるには、どのような方法があるのでしょうか？

どなたか、上記の質問の一部（または全部）を明らかにしていただけませんか？

どのように解決するのですか？

私は現在、音楽情報検索のための分類や最近傍探索などの問題を研究しています。

こんなことに興味がありませんか？ 近似最近傍 ( ANN )のアルゴリズムです。このアイデアは、アルゴリズムが十分に 近傍 (そうすることで、複雑さを軽減することができます。あなたは kd-ツリー これはその一例です。しかし、あなたが言ったように kd-ツリー は高次元ではうまく機能しません。実際 すべて 現在のインデックス作成技術（空間分割に基づく）は、十分に高い次元では線形探索に劣化する[1][2][3]。

うち ANN というアルゴリズムが提案されていますが、おそらく最も人気があるのは 位置感応型ハッシュ ( LSH 高次元空間の点の集合をビンの集合、すなわちハッシュテーブルに写像するものである[1][3]。しかし、従来のハッシュとは異なり ローカリティセンシティブ ハッシュは 近く を同じビンに入れる。

LSH には、いくつかの大きな利点があります。まず、シンプルであること。データベース内のすべての点のハッシュを計算し、そこからハッシュテーブルを作るだけである。クエリを実行するには、クエリポイントのハッシュを計算し、ハッシュテーブルから同じビンにあるすべてのポイントを取得するだけでよい。

2つ目は、その性能を裏付ける厳密な理論があることです。それは、クエリー時間が サブリニア であり、線形探索よりも高速である。どの程度速くなるかは、どの程度の近似が許容されるかによる。

最後に LSH は任意のLpノルムと互換性があり 0 < p <= 2 . したがって，最初の質問に答えるには，次のようにすればよいでしょう． LSH は、ユークリッド距離測定法と併用してもよいし、マンハッタン（L1）距離測定法と併用してもよい。また、ハミング距離やコサイン類似度にも対応するものがあります。

2008年のIEEE Signal Processing MagazineにMalcolm SlaneyとMichael Caseyがまともな概要を書いています[4]。

LSH は、一見どこにでも適用されているように見えます。試してみるのもいいかもしれませんね。

[1] Datar, Indyk, Immorlica, Mirrokni, "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions," 2004.

[2] Weber, Schek, Blott, "A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces," 1998.「高次元空間における類似性探索手法の定量的分析と性能研究」.

[3] Gionis, Indyk, Motwani, "Similarity search in high dimensions via hashing," 1999.

[4] Slaney, Casey, "Locality-sensitive hashing for finding nearest neighbors", 2008.