k近傍法

統計学において、k近傍法（k -NN）は、非パラメトリックな教師あり学習法です。これは、1951年にEvelyn FixとJoseph Hodgesによって初めて開発され^{[ 1 ]} 、後にThomas Coverによって拡張されました^{[ 2 ]}。分類では、新しい例には、 k個の最も近い訓練例のラベルに基づいてラベルが割り当てられます。回帰では、予測はこれらの近傍の値から計算されます^{[ 1 ] [ 2 ]} 。 最もよく使用されるのは、 k -NN分類器として分類に使用され、その出力はクラスメンバーシップです。オブジェクトは、その近傍の多数決によって分類され、オブジェクトはk個の最も近い近傍の中で最も一般的なクラスに割り当てられます（kは正の整数で、通常は小さい値です）。k = 1の場合、オブジェクトは単純にその単一の最も近い近傍のクラスに割り当てられます。  

k -NNアルゴリズムは回帰にも一般化できます。k-NN回帰（最近傍平滑化とも呼ばれる）では、出力はオブジェクトのプロパティ値です。この値はk個の最近傍の値の平均です。k=1の場合、出力はその単一の最近傍の値に単純に割り当てられます。これは最近傍補間 とも呼ばれます。

分類と回帰の両方において、近傍の寄与に重みを割り当てることは有用な手法であり、これにより、近い近傍は遠い近傍よりも平均に大きく寄与するようになります。たとえば、一般的な重み付けスキームでは、各近傍に 1/ dの重みを与えます。ここでdは近傍までの距離です。^{[ 3 ]}

入力は、データセット内の最も近いk個の訓練例で構成されます。近傍は、クラス（k -NN分類の場合）またはオブジェクトプロパティ値（k -NN回帰の場合）が既知のオブジェクトのセットから取得されます。これはアルゴリズムの訓練セットと考えることができますが、明示的な訓練ステップは必要ありません。

k -NNアルゴリズムの特異性（場合によっては欠点）は、データの局所構造に対する感度です。k-NN分類では、関数は局所的に近似されるだけで、すべての計算は関数評価まで延期されます。このアルゴリズムは距離に依存するため、特徴が異なる物理単位を表している場合、またはスケールが大きく異なる場合は、トレーニングデータの特徴ごとの正規化によって精度が大幅に向上する可能性があります。^{[ 4 ]}

ペアがあると仮定します${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$値を取る$\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$ここで、YはXのクラスラベルであり、${\displaystyle X|Y=r\sim P_{r}}$のために${\displaystyle r=1,2}$（そして確率分布）${\displaystyle P_{r}}$) ある規範が与えられた場合${\displaystyle \|\cdot \|}$の上$\displaystyle \mathbb {R} ^{d}}$そしてポイント${\displaystyle x\in \mathbb {R} ^{d}}$、 させて${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$トレーニングデータの並べ替えによって、${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$。

学習データは、多次元特徴空間におけるベクトルであり、それぞれにクラスラベルが付与されている。アルゴリズムの学習フェーズは、学習データの特徴ベクトルとクラスラベルを保存することのみで構成される。

分類フェーズでは、kはユーザー定義の定数であり、ラベルなしベクトル（クエリまたはテストポイント）は、そのクエリポイントに最も近いk個のトレーニングサンプルの中で最も頻繁に出現するラベルを割り当てることによって分類されます。

連続変数によく使われる距離尺度はユークリッド距離です。テキスト分類などの離散変数には、オーバーラップ尺度（またはハミング距離）などの別の尺度を使用できます。たとえば、遺伝子発現マイクロアレイデータのコンテキストでは、ピアソンやスピアマンなどの相関係数を尺度としてk -NNが使用されています。 ^{[ 5 ]}多くの場合、距離尺度をラージマージン最近傍法や近傍成分分析などの特殊なアルゴリズムで学習すると、k -NNの分類精度が大幅に向上します。

基本的な「多数決」分類の欠点は、クラス分布が偏っている場合に発生します。つまり、より頻繁に出現するクラスの例が、その数が多いためk近傍に共通する傾向があるため、新しい例の予測を支配する傾向があります。^{[ 7 ]}この問題を克服する 1 つの方法は、テスト ポイントからk近傍のそれぞれまでの距離を考慮して分類に重み付けすることです。 k近傍のそれぞれのクラス (または回帰問題では値) は、その点からテスト ポイントまでの距離の逆数に比例する重みで乗算されます。偏りを克服するもう 1 つの方法は、データ表現の抽象化です。たとえば、自己組織化マップ(SOM) では、各ノードは、元のトレーニング データでの密度に関係なく、類似した点のクラスターの代表 (中心) です。k -NNは、SOM に適用できます。

kの最適な選択はデータに依存します。一般的に、kの値が大きいほど分類に対するノイズの影響は軽減されますが、^{[ 8 ]}クラス間の境界は不明瞭になります。適切なkは、さまざまなヒューリスティック手法によって選択できます(ハイパーパラメータ最適化を参照)。クラスが最も近いトレーニング サンプルのクラスであると予測される特殊なケース (つまり、k = 1 の場合) は、最近傍アルゴリズムと呼ばれます。

k -NN アルゴリズムの精度は、ノイズの多い特徴や無関係な特徴が存在する場合、または特徴のスケールがその重要性と一致しない場合に、著しく低下する可能性があります。分類を改善するために特徴を選択またはスケーリングすることに多くの研究努力が注がれてきました。特に一般的なアプローチは、進化アルゴリズムを使用して特徴のスケーリングを最適化することです。^{[ 9 ]}もう 1 つの一般的なアプローチは、トレーニング データとトレーニング クラスの相互情報によって特徴をスケーリングすることです。

二値分類問題では、同票を避けるため、 k を奇数に選択することが有効です。この設定で経験的に最適なk を選択する一般的な方法の 1 つは、ブートストラップ法です。 ^{[ 10 ]}

最も直感的な最近傍型分類器は、特徴空間で点xをその最近傍のクラスに割り当てる最近傍分類器です。${\displaystyle C_{n}^{1nn}(x)=Y_{(1)}}$。

訓練データセットのサイズが無限大に近づくにつれて、最近傍分類器は、ベイズ誤差率の2倍以下（データの分布を考慮した場合に達成可能な最小誤差率）の誤差率を保証します。

k近傍分類器は、k個の最近傍に重みを割り当てるものと見なすことができる。${\displaystyle 1/k}$そしてその他すべてに0の重みが割り当てられます。これは重み付き最近傍分類器に一般化できます。つまり、i番目の最近傍に重みが割り当てられます。${\displaystyle w_{ni}}$、 と${\textstyle \sum _{i=1}^{n}w_{ni}=1}$重み付き最近傍分類器の強い一貫性に関する同様の結果も成り立つ。 ^{[ 11 ]}

させて${\displaystyle C_{n}^{wnn}}$重み付き最近傍分類器を重みで表す${\displaystyle \{w_{ni}\}_{i=1}^{n}}$漸近理論における条件変数である正則条件に従うと、パラメータを何らかの基準で区別するために仮定が必要となる。クラス分布では、超過リスクは次の漸近展開を持つ^{[ 12 ]。}$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$$ 定数の場合${\displaystyle B_{1}}$そして${\displaystyle B_{2}}$どこ${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$そして${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\left\{i^{1+2/d}-(i-1)^{1+2/d}\right\}}$。

最適な重み付け方式${\displaystyle \{w_{ni}^{*}\}_{i=1}^{n}}$上記の表示にある2つの項のバランスをとる式は、次のように表されます。${\displaystyle k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$、 $${\displaystyle w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$$のために${\displaystyle i=1,2,\dots ,k^{*}}$そして $${\displaystyle w_{ni}^{*}=0}$$のために${\displaystyle i=k^{*}+1,\dots ,n}$。

最適な重み付けでは、超過リスクの漸近展開における支配的な項は次のようになります。${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$同様の結果は、バギングされた最近傍分類器を使用した場合にも当てはまります。

最近傍アプローチの変形では、最も近い近傍ではなく、最も遠いk個の近傍を使用します。この設定では、類似性ではなく、最大の非類似性に基づいて近傍が選択されます。このアプローチは、レコメンデーションシステムで「逆近傍」モデルとして提案されており、最も類似性の低いユーザーが特定され、そのユーザーの嗜好が逆向きに使用されてレコメンデーションが生成されます。^{[ 13 ]}目標は通常、推奨アイテムの多様性または新規性を高めることです。これは、従来の最近傍法では、人気のあるアイテムや明白なアイテムが優先される可能性があるためです。経験的評価では、最も遠い近傍アプローチは、標準的な k 最近傍法より​​も予測精度が低いことが一般的にわかっていますが、ユーザーが認識する有用性は、場合によっては同等かそれ以上になることがあります。

k -NNは、一様カーネルを持つ可変帯域幅カーネル密度「バルーン」推定量の特殊なケースである。^{[ 14 ] [ 15 ]}

このアルゴリズムの単純なバージョンは、テスト例から保存されているすべての例までの距離を計算することで簡単に実装できますが、大規模なトレーニングセットでは計算負荷が高くなります。近似最近傍探索アルゴリズムを使用することで、 k- NNは大規模なデータセットでも計算処理が容易になります。長年にわたり、多くの最近傍探索アルゴリズムが提案されてきました。これらのアルゴリズムは一般的に、実際に実行される距離評価の回数を減らすことを目的としています。

k- NNにはいくつかの強力な一貫性結果があります。データの量が無限に近づくにつれて、2クラスk -NNアルゴリズムは、ベイズエラー率の2倍（データの分布が与えられた場合に達成可能な最小エラー率）よりも悪いエラー率にならないことが保証されます。 ^{[ 2 ]}近接グラフを使用することで、 k -NNの速度をさまざまな面で改善できます。^{[ 16 ]}

多クラスk- NN分類の場合、CoverとHart（1967）は、エラー率の上限を証明している。 $$\displaystyle R^{*}\ \leq \ R_{k\mathrm {NN} }\ \leq \ R^{*}\left(2-{\frac {MR^{*}}{M-1}}\right)}$$ どこ${\displaystyle R^{*}}$ベイズエラー率（可能な最小エラー率）は、${\displaystyle R_{kNN}}$は漸近的なk- NN 誤差率であり、Mは問題におけるクラス数である。この境界は、下限と上限の両方が何らかの分布によって達成可能であるという意味でタイトである。^{[ 17 ]}の場合${\displaystyle M=2}$ベイズ誤差率${\displaystyle R^{*}}$がゼロに近づくと、この制限は「ベイズ誤差率の2倍以下」に縮小します。

k近傍分類器のエラー率に関する結果は多数存在する。 ^{[ 18 ]} k近傍分類器は強く（つまり、任意の同時分布に対して）${\displaystyle (X,Y)}$)一貫性のある提供${\displaystyle k:=k_{n}}$分岐して${\displaystyle k_{n}/n}$ゼロに収束する${\displaystyle n\to \infty }$。

させて${\displaystyle C_{n}^{knn}}$nサイズのトレーニング セットに基づくk近傍分類器を表します。特定の正則条件の下では、過剰リスクは次の漸近展開をもたらします^{[ 12 ]}$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left\{B_{1}{\frac {1}{k}}+B_{2}\left({\frac {k}{n}}\right)^{4/d}\right\}\{1+o(1)\},}$$ いくつかの定数に対して${\displaystyle B_{1}}$そして${\displaystyle B_{2}}$。

選択${\displaystyle k^{*}=\left\lfloor Bn^{\frac {4}{d+4}}\right\rfloor }$上記の表示にある 2 つの用語間のトレードオフを提供します。${\displaystyle k^{*}}$-最近傍誤差は最適な（ミニマックス）収束率でベイズ誤差に収束する${\displaystyle {\mathcal {O}}\left(n^{-{\frac {4}{d+4}}}\right)}$。

K近傍法による分類性能は、（教師あり）メトリック学習によって大幅に向上することがよくあります。よく用いられるアルゴリズムとしては、近傍成分分析や大マージン最近傍法などがあります。教師ありメトリック学習アルゴリズムは、ラベル情報を用いて新しいメトリックまたは擬似メトリックを学習します。

アルゴリズムへの入力データが大きすぎて処理できない場合、また冗長であると思われる場合（例えば、フィートとメートルの両方で同じ測定値がある場合）、入力データは縮小された表現の特徴セット（特徴ベクトルとも呼ばれる）に変換されます。入力データを特徴セットに変換することを特徴抽出と呼びます。抽出された特徴が慎重に選択されていれば、特徴セットは入力データから関連情報を抽出し、フルサイズの入力ではなくこの縮小された表現を使用して目的のタスクを実行できると期待されます。特徴抽出は、特徴空間で変換されたデータにk -NN アルゴリズムを適用する前に、生データに対して実行されます。

k -NNを用いた顔認識のための典型的なコンピュータビジョン計算パイプラインの例（特徴抽出と次元削減の前処理ステップを含む）（通常はOpenCVで実装される）：

1. Haar顔検出
2. 平均シフト追跡分析
3. PCAまたはFisher LDAによる特徴空間への射影、それに続くk -NN分類

高次元データ（例えば、次元数が10を超えるデータ）の場合、次元の呪いの影響を避けるために、通常はk -NNアルゴリズムを適用する前に次元削減が行われます。^{[ 19 ]}

k -NNの文脈における次元の呪いとは、基本的に、すべてのベクトルが検索クエリベクトルからほぼ等距離にあるため、高次元ではユークリッド距離が役に立たないことを意味します（クエリ点を中心とする円上に複数の点がほぼ配置されていると想像してください。クエリから検索空間内のすべてのデータ点までの距離はほぼ同じです）。

特徴抽出と次元削減は、前処理ステップとして主成分分析（PCA）、 線形判別分析（LDA）、または正準相関分析（CCA）の手法を使用し、その後、次元削減された空間の特徴ベクトルに対してk -NNによるクラスタリングを行うことで、1つのステップで組み合わせることができます。このプロセスは低次元埋め込みとも呼ばれます。^{[ 20 ]}

非常に高次元のデータセット (たとえば、ライブ ビデオ ストリーム、DNA データ、または高次元時系列で類似性検索を実行する場合)の場合、局所性に敏感なハッシュ、「ランダム投影」、^「スケッチ」^{[ 21 ] 、}または VLDB ツール ボックスのその他の高次元類似性検索技術を使用して高速近似k -NN 検索を実行することが^、唯一実行可能なオプションとなる可能性があります。

最近傍ルールは、事実上、決定境界を暗黙的に計算します。決定境界を明示的に、かつ効率的に計算することも可能であり、その場合、計算複雑度は境界の複雑度の関数となります。^{[ 23 ]}

データ削減は、膨大なデータセットを扱う上で最も重要な課題の一つです。通常、正確な分類にはデータポイントの一部のみが必要です。これらのデータはプロトタイプと呼ばれ、以下のように見つけることができます。

1. クラス外れ値、つまりk -NN（指定されたkに対して）によって誤って分類されたトレーニングデータを選択します。
2. 残りのデータを2つのセットに分けます。(i) 分類決定に使用されるプロトタイプと、(ii)プロトタイプを使用してk -NNで正しく分類できる吸収点です。吸収点はトレーニングセットから削除できます。

データ削減のための圧縮型最近傍法

圧縮最近傍法（CNN、ハートアルゴリズム）は、 k -NN分類のデータセットを削減するように設計されたアルゴリズムです。 ^{[ 24 ]}トレーニングデータからプロトタイプのセットUを選択することで、 Uを使用した1NNは、データセット全体を使用した1NNとほぼ同じ精度で例を分類できます。

訓練データセットXが与えられた場合、CNNは反復的に動作します。

1. Xのすべての要素をスキャンし、 Uの最も近いプロトタイプがxとは異なるラベルを持つ要素xを探します。
2. Xからxを取り除き、 Uに加える
3. Uにプロトタイプが追加されなくなるまでスキャンを繰り返します。

分類にはXの代わりにUを使用してください。プロトタイプではない例は「吸収点」と呼ばれます。

境界比率の降順でトレーニング例をスキャンするのが効率的です。^{[ 25 ]}トレーニング例xの境界比率は次のように定義されます。

a ( x ) = ‖ x' -y ‖ / ‖ xy ‖ ⁠

ここで、‖ xy ‖はxとは異なる色を持つ最も近い例yまでの距離であり、‖ x'-y ‖はyからxと同じラベルを持つ最も近い例x'までの距離です。

境界比は区間 [0,1] にあります。これは、‖ x'-y ‖ が‖ xy ‖を超えることがないためです。この順序付けにより、プロトタイプのセットUに含めるクラスの境界が優先されます。x とは異なるラベルの点は、xの外部にあると呼ばれます。境界比の計算は、右の図で示されています。データポイントは色でラベル付けされています。初期ポイントはxで、そのラベルは赤です。外部ポイントは青と緑です。x に最も近い外部ポイントはyです。y に最も近い赤いポイントはx'です。境界比a ( x ) = ‖ x'-y ‖ / ‖ xy ‖は、初期ポイントxの属性です。

以下は、一連の図で CNN を説明したものです。クラスは 3 つ (赤、緑、青) あります。図 1: 最初は各クラスに 60 個の点があります。図 2 は 1NN 分類マップを示しています。各ピクセルは、すべてのデータを使用して 1NN によって分類されます。図 3 は 5NN 分類マップを示しています。白い領域は、5NN 投票が同数になった未分類領域に対応します (たとえば、5 つの最近傍点の中に緑が 2 つ、赤が 2 つ、青が 1 つある場合)。図 4 は、縮小されたデータセットを示しています。十字は (3,2)NN ルールによって選択されたクラス外れ値です (これらのインスタンスの 3 つの最近傍点はすべて他のクラスに属しています)。四角はプロトタイプ、空の円は吸収点です。左下隅には、3 つのクラスすべてについて、クラス外れ値、プロトタイプ、吸収点の数が表示されています。この例では、プロトタイプの数はクラスによって 15% から 20% まで変化します。図5は、プロトタイプを用いた1NN分類マップが初期データセットを用いたものと非常によく似ていることを示している。これらの図はMirkesアプレットを使用して作成された。^{[ 25 ]}

• k-NN分類器のためのCNNモデル縮小
• 
  図1．データセット。
• 
  図2．1NN分類マップ。
• 
  図3．5NN分類マップ。
• 
  図4．CNNによる縮小データセット。
• 
  図5．CNNで抽出されたプロトタイプに基づく1NN分類マップ。

k -NN回帰（k -NN平滑化とも呼ばれる）では、 k -NNアルゴリズムを用いて連続変数を推定します。このようなアルゴリズムの一つとして、 k個の最近傍点の加重平均を用いる方法があります。加重平均の重みは、それぞれの近傍点間の距離の逆数で表されます。このアルゴリズムは次のように動作します。

1. クエリ例からラベル付き例までのユークリッド距離またはマハラノビス距離を計算します。
2. ラベル付けされた例を、距離が短い順に並べ替えてください。
3. RMSEに基づいて、ヒューリスティックに最適な最近傍点の数kを見つける。これは交差検証を用いて行う。
4. k個の最近傍多変量データを用いて、逆距離加重平均を計算します。

k番目の最近傍までの距離は、局所的な密度推定値と見なすこともできるため、異常検出における一般的な外れ値スコアでもあります。k - NNまでの距離が大きいほど、局所的な密度は低くなり、クエリポイントが外れ値である可能性が高くなります。^{[ 26 ]}この外れ値モデルは非常に単純ですが、大規模な実験分析によると、別の古典的なデータマイニング手法である局所外れ値係数とともに、より最近のより複雑なアプローチと比較しても非常にうまく機能します。^{[ 27 ]}

混同行列、または「マッチング行列」は、 k -NN分類の精度を検証するためのツールとしてよく用いられます。尤度比検定などのより堅牢な統計的手法も適用可能です。

• 最近傍重心分類器
• 最近接点ペア問題
• 最近傍グラフ
• セグメンテーションに基づくオブジェクト分類

• Dasarathy, Belur V.編 (1991).最近傍 (NN) ノルム: NN パターン分類技術. IEEE Computer Society Press. ISBN 978-0818689307。
• Shakhnarovich, Gregory; Darrell, Trevor; Indyk, Piotr 編 (2005).学習と視覚における最近傍法. MIT Press . ISBN 978-0262195478。