数日前に、特定のベクトルの最近傍を見つける方法について質問しました。私のベクトルは21次元になりました。先に進む前に、私は機械学習や数学の領域から来ていないため、いくつかの基本的な質問をし始めています。
上記の質問の一部（またはすべて）を明確にしていただけますか？
私は現在、音楽情報検索のためにそのような問題（分類、最近傍探索）を研究しています。
近似最近傍（ANN）アルゴリズムに興味があるかもしれません。アイデアは、アルゴリズムが十分に近い近傍（おそらく最近傍ではない）を返すことを許可することです。そうすることで、複雑さを軽減できます。あなたはkd-treeについて言及しました; それは一例です。しかし、あなたが言ったように、kd-treeは高次元ではうまく機能しません。実際、現在のすべてのインデックス作成手法（スペース分割に基づく）は、十分に高い次元の線形検索に低下します[1][2][3]。
最近提案されたANNアルゴリズムの中で、おそらく最も人気のあるものは、局所性鋭敏型ハッシュ（LSH）です。これは、高次元空間内のポイントのセットをビンのセット、つまりハッシュテーブルにマッピングします[1][3]。ただし、従来のハッシュとは異なり、局所性鋭敏型ハッシュは近くのポイントを同じビンに配置します。
LSHにはいくつかの大きな利点があります。まず、それは簡単です。データベース内のすべてのポイントのハッシュを計算し、それらからハッシュテーブルを作成するだけです。クエリを実行するには、クエリポイントのハッシュを計算してから、ハッシュテーブルから同じビン内のすべてのポイントを取得します。
第二に、そのパフォーマンスをサポートする厳密な理論があります。クエリ時間はデータベースのサイズで劣線形である、つまり線形検索よりも速いことを示すことができます。どれだけ速くなるかは、許容できる近似の量によって異なります。
最後に、LSHはの任意のLpノルムと互換性があります0 < p <= 2。したがって、最初の質問に答えるには、LSHをユークリッド距離メトリックで使用するか、マンハッタン（L1）距離メトリックで使用できます。ハミング距離とコサイン類似度のバリエーションもあります。
まともな概要は、2008年にIEEE SignalProcessingMagazineのMalcolmSlaneyとMichaelCaseyによって書かれました[4]。
LSHはどこにでも適用されているようです。あなたはそれを試してみたいかもしれません。
[1] Datar、Indyk、Immorlica、Mirrokni、「p-Stable分布に基づく局所性鋭敏型ハッシュスキーム」、2004年。
[2] Weber、Schek、Blott、「高次元空間における類似性検索方法の定量分析とパフォーマンス研究」、1998年。
[3] Gionis、Indyk、Motwani、「ハッシュによる高次元での類似性検索」、1999年。
[4] Slaney、Casey、「最近傍を見つけるための局所性鋭敏型ハッシュ」、2008年。
I.距離メトリック
まず、データセット内の特徴（列）の数は、kNNで使用する距離メトリックを選択する際の要因ではありません。正確にこの質問に向けられたかなりの数の公開された研究があり、比較のための通常の根拠は次のとおりです。
データの基礎となる統計的分布。
データを構成する特徴間の関係（それらは独立していますか？つまり、共分散行列はどのように見えますか）。と
データが取得された座標空間。
データがサンプリングされた分布についての予備知識がない場合、少なくとも1つの（十分に文書化された徹底的な）調査で、ユークリッド距離が最良の選択であると結論付けられます。
メガスケールのWeb推奨エンジンおよび現在の学術研究で使用されているYEuclideanメトリック。ユークリッド距離は直感的な意味を持ち、計算スケールがあります。つまり、ユークリッド距離は、2つの点が2次元であろうと、22次元空間であろうと、同じ方法で計算されます。
私にとっては数回しか失敗しませんでした。基礎となる（デカルト）座標系が不適切な選択であったため、これらの各ケースでユークリッド距離が失敗しました。たとえば、パスの長さ（距離）が加算されなくなったため、通常はこれを認識します。たとえば、距離空間がチェスボードの場合、マンハッタンの距離はユークリッドよりも優れています。同様に、距離空間が地球で距離がトランスの場合も同様です。 -大陸便、極座標系に適した距離メトリックは良い考えです（たとえば、ロンドンからウィーンまでは2.5時間、ウィーンからサンクトペテルブルクまではさらに3時間、ほぼ同じ方向ですが、ロンドンからセント。ピーターズバーグは5.5時間ではなく、3時間強です。）
ただし、データが非デカルト座標系に属している場合を除いて、距離メトリックの選択は通常重要ではありません。（CS学生からのこのブログ投稿を参照して、kNN分類器への影響を調べることによっていくつかの距離メトリックを比較します-chi squareは最良の結果をもたらしますが、違いは大きくありません;より包括的な研究は学術論文のComparative Study of最近傍の距離関数-マハラノビス（本質的に、次元共分散を説明するために正規化されたユークリッド）は、この研究で最高でした。
重要な条件の1つ：距離メトリックの計算を意味のあるものにするには、再スケーリングする必要がありますデータ-これを行わずに正確な予測を生成するためにkNNモデルを構築することはめったにありません。たとえば、運動能力を予測するためにkNNモデルを構築していて、期待変数が身長（cm）、体重（kg）、体脂肪（％）、および安静時脈拍（1分あたりの心拍数）である場合、一般的なデータポイントは次のようになります。次のようになります：[180.4、66.1、11.3、71]。明らかに、距離の計算は身長によって支配されますが、体脂肪率による寄与はほとんど無視できます。言い換えると、代わりにデータが異なる方法で報告され、体重がキログラムではなくグラムであった場合、元の値86.1は86,100になり、結果に大きな影響を与えます。これはまさにあなたが行うことです。したくない。
X_new = (X_old - mu) / sigma
II。データ構造
kd-tree構造のパフォーマンスが心配な場合、A Voronoi Tessellationは概念的に単純なコンテナーですが、kd-Treeよりもパフォーマンスとスケーリングが大幅に向上します。
これは、kNNトレーニングデータを永続化するための最も一般的な方法ではありませんが、この目的でのVTの適用、およびその結果としてのパフォーマンス上の利点は、十分に文書化されています（たとえば、このMicrosoft Researchレポートを参照）。これの実際的な重要性は、「主流」言語を使用している場合（たとえば、TIOBEインデックス）、VTを実行するためのライブラリを見つける必要があるということです。PythonとRには、言語ごとに複数のオプションがあることを知っています（たとえば、CRANで利用可能なRのボロノイパッケージ）
kNNにVTを使用すると、次のように機能します。
データからランダムにwポイントを選択します。これらはボロノイ中心です。ボロノイセルは、各中心に最も近いすべての隣接点をカプセル化します。ボロノイ中心のそれぞれに異なる色を割り当てて、特定の中心に割り当てられた各点がその色でペイントされるようにすると想像してみてください。十分な密度がある限り、これを行うと、各ボロノイ中心の境界が（2つの色を分離する境界として）うまく表示されます。
ボロノイセンターの選択方法は？私は2つの直交するガイドラインを使用します。wポイントをランダムに選択した後、トレーニングデータのVTを計算します。次に、各ボロノイ中心に割り当てられたデータポイントの数を確認します。これらの値はほぼ同じである必要があります（データ空間全体でポイント密度が均一である場合）。2次元では、これにより同じサイズのタイルを持つVTが発生します。これが最初のルールであり、これが2番目のルールです。反復ごとにwを選択します。変数パラメーターとしてwを使用してkNNアルゴリズムを実行し、パフォーマンス（VTにクエリを実行して予測を返すために必要な時間）を測定します。
したがって、100万のデータポイントがあると想像してください.....ポイントが通常の2Dデータ構造またはkdツリーで永続化されている場合、それぞれに対して平均で数百万の距離計算を実行します。応答変数を予測する新しいデータポイント。もちろん、これらの計算は単一のデータセットに対して実行されます。V / Tを使用すると、2つの異なるデータ母集団に対して、2つのステップで最近傍探索が実行されます。最初はボロノイ中心に対して、次に最も近い中心が見つかると、セル内のポイントはに対応します。その中心を検索して、実際の最近傍を見つけます（連続した距離計算によって）これらの2つのルックアップを組み合わせると、単一のブルートフォースルックアップよりもはるかに高速になります。これは簡単にわかります。100万個のデータポイントの場合、データスペースをテッセレートするために250個のボロノイセンターを選択するとします。平均して、各ボロノイセルには4,000個のデータポイントがあります。したがって、平均500,000の距離計算（ブルートフォース）を実行する代わりに、実行する距離ははるかに少なく、平均で125+2,000になります。
III。結果の計算（予測された応答変数）
kNNトレーニングデータのセットから予測値を計算するには、2つのステップがあります。1つ目は、n、つまりこの計算に使用する最近傍の数を特定することです。2つ目は、予測値への寄与をどのように重み付けするかです。
最初のコンポーネントでは、最適化問題を解くことでnの最適値を決定できます（最小二乗最適化と非常によく似ています）。それが理論です。実際には、ほとんどの人はn=3を使用します。いずれにせよ、n = 1、n = 2、n = 3などの一連のテストインスタンス（予測値を計算するため）に対してkNNアルゴリズムを実行し、nの関数としてエラーをプロットするのは簡単です。nのもっともらしい値を開始したいだけの場合は、ここでもn=3を使用します。
2番目のコンポーネントは、各ネイバーの寄与をどのように重み付けするかです（n> 1と仮定）。
最も単純な重み付け手法は、各ネイバーに重み付け係数を掛けるだけです。これは、1 /（dist * K）、またはそのネイバーからテストインスタンスまでの距離の逆数に、経験的に導き出された定数Kを掛けたものです。この手法は、最も近い隣人を過大評価することが多いため（同時に、より遠い隣人を過小評価するため）、この手法のファンではありません。これの重要性は、与えられた予測がほぼ完全に単一のネイバーに依存する可能性があることです。これにより、アルゴリズムのノイズに対する感度が向上します。
この制限を実質的に回避する、より優れた重み関数は、Pythonでは次のように見えるガウス関数です。
def weight_gauss(dist, sig=2.0) :
return math.e**(-dist**2/(2*sig**2))
kNNコードを使用して予測値を計算するには、応答変数を予測するデータポイント（「テストインスタンス」）に最も近いn個の近傍を特定し、次に、n個の近傍ごとに1回、weight_gauss関数を呼び出します。この関数は、各近傍の重みを返します。これは、加重平均計算でその近傍の係数として使用されます。
あなたが直面しているのは、次元の呪いとして知られています。PCAやICAなどのアルゴリズムを実行して、 21次元すべてが本当に必要であることを確認し、ほぼ同じ結果品質で21未満を使用できる線形変換を見つけると便利な場合があります。
更新：
RangayyanによるBiomedical Signal Processingという本でそれらに遭遇しました（正しく覚えているといいのですが）。ICAは簡単な手法ではありませんが、フィンランドの研究者によって開発されたものであり、そのためのMatlabコードは一般にダウンロード可能であると思います。PCAはより広く使用されている手法であり、Rまたは他のソフトウェア実装を見つけることができるはずです。PCAは、線形方程式を繰り返し解くことによって実行されます。私はそれをずっと前にやったので、その方法を思い出せません。=）
アイデアは、信号を独立した固有ベクトル（実際には離散固有関数）とそれらの固有値（この場合は21）に分割することです。各固有値は、各固有関数が各測定に提供する寄与の量を示します。固有値が小さい場合は、対応する固有関数をまったく使用せずに信号を非常に厳密に表すことができます。これにより、次元を取り除くことができます。
トップアンサーは良いですが古いので、 2016年のアンサーを合計したいと思います。
すでに述べたように、高次元の空間では、次元の呪いが角を曲がったところに潜んでおり、人気のあるkdツリーなどの従来のアプローチはブルートフォースアプローチと同じくらい遅くなります。その結果、私たちは近似最近傍探索（ANNS）に関心を向けます。これは、ある程度の精度を優先して、プロセスを高速化します。正確なNNの適切な近似が得られ、適切な傾向が得られます。
価値があるかもしれないホットトピック：
私の関連する答えを確認することもできます：
質問に1つずつ答えるには：
これはあなたが正しい方向に始めるための素晴らしい論文です。「最も近い隣人にいるときは意味がありますか？」Beyer他による。
20K以上のサイズのテキストデータを使用しています。テキスト関連のアドバイスが必要な場合は、私がお手伝いできるかもしれません。
コサイン類似性は、高次元ベクトルを比較するための一般的な方法です。これは距離ではなく類似性であるため、最小化するのではなく最大化する必要があることに注意してください。ドメイン固有の方法を使用してデータを比較することもできます。たとえば、データがDNA配列の場合、変異の確率などを考慮した配列類似性を使用できます。
使用する最近傍の数は、データのタイプ、ノイズの量などによって異なります。一般的な規則はありません。範囲内のすべての値を試して、特定のデータと問題に最適なものを見つける必要があります。 。人々は、データが多ければ多いほど、必要なネイバーが少なくなることを直感的に理解しています。考えられるすべてのデータがあるという仮定の状況では、分類するために必要なのは1つの最近傍を探すことだけです。
k最近傍法は、計算コストが高いことが知られています。これは、サポートベクターマシンのような他のアルゴリズムに人々が目を向ける主な理由の1つです。
kd-treesは、実際、高次元データではうまく機能しません。剪定ステップはもはやあまり役に立たないため、最も近いエッジ（1次元の偏差）は、ほとんどの場合、既知の最近傍に対する完全な次元の偏差よりも小さくなります。
しかしさらに、kdツリーは私が知っているすべてのLpノルムでのみうまく機能し、距離ベースのアルゴリズムが次元の増加とともに低下する距離集中効果があります。
詳細については、次元の呪いとそのさまざまな変形について調べてください（これには複数の側面があります！）
たとえば、LSHやランダム射影を使用して、ユークリッド最近傍を盲目的に近似することに多くの用途があるとは思いません。そもそも、はるかに微調整された距離関数を使用する必要があるかもしれません！
多くは、あなたが最も近い隣人を知りたい理由に依存します。データセットのモードを見つけることが本当に必要な場合は、平均シフトアルゴリズムhttp://en.wikipedia.org/wiki/Mean-shiftを調べることができます。
ブール機能のtf-idfのコサインは、ほとんどの問題でうまく機能すると思います。これは、Luceneのような多くの検索エンジンで使用されている実績のあるヒューリスティックのためです。私の経験では、ユークリッド距離は、テキストのようなデータに対して悪い結果を示しています。さまざまな重みとk-exampleの選択は、トレーニングデータとブルートフォースパラメーターの選択を使用して実行できます。
KDツリーは、すべてのポイントの5％を確認した後、早期に終了した場合、21次元で正常に機能します。 FLANNは、128次元のSIFTベクトルに一致するようにこれ（およびその他の高速化）を実行します。（残念ながら、FLANNはユークリッド距離のみを実行し、高速で堅実な scipy.spatial.cKDTree はLp距離のみを実行します。これらはデータに適している場合とそうでない場合があります。）もちろん、ここには速度と精度のトレードオフがあります。
（Ndata、Nquery、データ分散について説明できれば、同様のデータを試すのに役立つ可能性があります。）
4月26日、私の古いMac PPCでカットオフを使用したcKDTreeの実行時間を追加し、実現可能性の非常に大まかなアイデアを提供します。
kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 %
3.5 sec to query 1000 points
distances to 2 nearest: av 0.131 max 0.253
kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 %
15 sec to query 1000 points
distances to 2 nearest: av 0.131 max 0.245
iDistanceは、高次元データでの正確なknn検索におそらく最適です。おおよそのボロノイ図として見ることができます。
私は同じ問題を経験しました、そして次のように言うことができます。
あなたはaz順序曲線を試すことができます。3次元で簡単です。
しばらく前に同じような質問がありました。高速な近似最近傍検索については、spotifyの迷惑ライブラリを使用できます：https ：//github.com/spotify/annoy
これは、C++で最適化されたPythonAPIのサンプルコードです。
from annoy import AnnoyIndex
import random
f = 40
t = AnnoyIndex(f, 'angular') # Length of item vector that will be indexed
for i in range(1000):
v = [random.gauss(0, 1) for z in range(f)]
t.add_item(i, v)
t.build(10) # 10 trees
t.save('test.ann')
# ...
u = AnnoyIndex(f, 'angular')
u.load('test.ann') # super fast, will just mmap the file
print(u.get_nns_by_item(0, 1000)) # will find the 1000 nearest neighbors
それらは異なる距離測定を提供します。どの距離測定を適用するかは、個々の問題によって大きく異なります。また、最初に重要性のために特定のディメンションを事前スケーリング（重み付けを意味する）することを検討してください。これらの次元または特徴重要度の重みは、エントロピー損失などによって計算される場合があります。教師あり学習の問題がある場合は、この次元の値をスクランブルすると、機械学習モデルのパフォーマンスがどれだけ悪化するかを確認します。
多くの場合、ベクトルの方向は絶対値よりも重要です。たとえば、テキストドキュメントのセマンティック分析では、長さではなく、セマンティクスが類似している場合にドキュメントベクトルを近くに配置する必要があります。したがって、これらのベクトルを単位長に正規化するか、距離測定として角距離（つまりコサイン類似度）を使用することができます。
これがお役に立てば幸いです。
ユークリッド距離は、そもそも最近傍を見つけるための良い指標ですか？そうでない場合、私のオプションは何ですか？
ソフト部分空間クラスタリングをお勧めします。これは、今日ではかなり一般的なアプローチであり、最も関連性の高い次元を見つけるために特徴の重みが計算されます。たとえば、ユークリッド距離を使用する場合は、これらの重みを使用できます。一般的な問題については次元の呪いを参照してください。また、この記事は何らかの形であなたを啓発することができます。
数値データセットとカテゴリデータセットが混在する部分空間クラスタリングのためのk-means型クラスタリングアルゴリズム