k近傍法アルゴリズム

統計学において、k近傍法（k -NN）は、ノンパラメトリックな 教師あり学習法です。1951年にEvelyn FixとJoseph Hodgesによって最初に開発され、 ^[1]後にThomas Coverによって拡張されました。^{[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]

内の値を取るペアがあり、Y はXのクラスラベルであるため、（および確率分布）に対してが成り立つとします。上の何らかのノルムと点が与えられた場合、が となるようにトレーニング データを並べ替えたものとします。 ${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$${\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]多くの場合、距離メトリックがLarge Margin Nearest NeighborやNeighborhood components analysisなどの特殊なアルゴリズムで学習されると、 k -NNの分類精度が大幅に向上します。

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

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

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

バイナリ（2クラス）分類問題では、同票を避けるためにkを奇数に選ぶと良い。この設定で経験的に最適なkを選択する一般的な方法の1つは、ブートストラップ法である。 ^[9]

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

トレーニング データ セットのサイズが無限に近づくと、1 つの最近傍分類器によって、ベイズ エラー率(データの分布を考慮に入れた達成可能な最小エラー率)の 2 倍以下のエラー率が保証されます。

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

重み を持つ重み付き最近接分類器を表すものとします。漸近理論では、正則性条件は、いくつかの基準でパラメータを区別するための仮定を必要とする条件変数です。クラス分布では、過剰リスクは、定数および に対して次の漸近展開を持ちます^[11]。 ここで、および です。${\displaystyle C_{n}^{wnn}}$${\displaystyle \{w_{ni}\}_{i=1}^{n}}$ $${\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\}}$

上記の表示の 2 つの項のバランスをとる最適な重み付けスキームは、次のように与えられます。については、 について は を設定します。 ${\displaystyle \{w_{ni}^{*}\}_{i=1}^{n}}$${\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 -NNは、均一カーネルを持つ可変帯域幅のカーネル密度「バルーン」推定器の特殊なケースです。^{[12] [13]}

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

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

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

k近傍分類器のエラー率については多くの結果が出ている。 ^[16] k近傍分類器は、 が発散して としてゼロに収束することを条件に、強く（つまり 上の任意の結合分布に対して）整合している。 ${\displaystyle (X,Y)}$${\displaystyle k:=k_{n}}$${\displaystyle k_{n}/n}$${\displaystyle n\to \infty }$

を、サイズnのトレーニングセットに基づくk近傍分類器と表記する。一定の規則性条件下では、過剰リスクは、 いくつかの定数およびに対して、次の漸近展開^[11]をもたらす。 ${\displaystyle C_{n}^{knn}}$ $${\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}}$

この選択により、上記の表示の 2 つの項の間でトレードオフが提供され、最近傍誤差は最適 (ミニマックス) レートでベイズ誤差に収束します。 ${\displaystyle k^{*}=\left\lfloor Bn^{\frac {4}{d+4}}\right\rfloor }$${\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アルゴリズムを適用する前に次元削減が行われるのが一般的です。^[17]

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

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

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

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

データの削減は、膨大なデータセットを扱う作業において最も重要な問題の 1 つです。通常、正確な分類には一部のデータ ポイントのみが必要です。これらのデータはプロトタイプと呼ばれ、次の場所にあります。

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

他のクラスの例に囲まれたトレーニング例は、クラス外れ値と呼ばれます。クラス外れ値の原因には次のものがあります。

• ランダムエラー
• このクラスのトレーニング例が不十分です（クラスターではなく孤立した例が表示されます）
• 重要な機能が欠けている（クラスは他の次元で分離されているが、それは不明）
• 他のクラスのトレーニング例が多すぎる（クラスのバランスが取れていない）ため、特定の小さなクラスに対して「敵対的な」背景が作成されます。

k -NNのクラス外れ値はノイズを生成します。これらは検出して、将来の分析のために分離することができます。2 つの自然数、k > r >0 が与えられた場合、トレーニング例のk近傍に他のクラスの例がr 個以上含まれている場合、そのトレーニング例は ( k、r )NN クラス外れ値と呼ばれます。

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

トレーニング セットXが与えられると、CNN は反復的に動作します。

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

分類にはXではなくU を使用します。プロトタイプではない例は「吸収」ポイントと呼ばれます。

訓練例を境界比の降順でスキャンするのが効率的である。^{[23]訓練例}xの境界比は次のように定義される。

ここで、‖ 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アプレットを使用して作成されました。^[23]

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

k -NN 回帰 ( k -NN スムージングとも呼ばれる)では、 k -NN アルゴリズムを使用して連続変数を推定します。^{[引用が必要]このようなアルゴリズムの 1 つは、} k近傍点の加重平均を使用し、距離の逆数で重み付けします。このアルゴリズムは次のように機能します。

1. クエリ例からラベル付き例までのユークリッド距離またはマハラノビス距離を計算します。
2. ラベルの付いた例を距離の昇順に並べます。
3. RMSEに基づいて、発見的に最適な最近傍の数k を見つけます。これは、クロス検証を使用して行われます。
4. k近傍の多変量近傍を使用して逆距離加重平均を計算します。

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

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

• 最近傍重心分類器
• 最も近い点のペアの問題
• 最近傍グラフ
• セグメンテーションベースのオブジェクト分類

• Dasarathy, Belur V.編(1991)。Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques。ISBN 978-0818689307。
• Shakhnarovich, Gregory、Darrell, Trevor、Indyk, Piotr 編 (2005)。学習と視覚における最近傍法。MIT出版。ISBN 978-0262195478。