K最近隣アルゴリズム: 基礎と応用

By Fouad Sabry

K 最近傍アルゴリズムとは

k-NN としても知られる k 近傍手法は、最初に作成されたノンパラメトリック教師あり学習手法です。 1951年、統計学の分野でエブリン・フィックスとジョセフ・ホッジスによって発表。 トーマス・カバーは後に元のコンセプトを拡張しました。 回帰と分類の両方に応用できます。 どちらのシナリオでも、入力はデータ コレクション内の互いに最も近い k 個のトレーニング インスタンスで構成されます。 k-NN が分類または回帰に使用されたかどうかに関係なく、結果は次のようになります。k 最近傍分類の出力はクラス メンバーシップです。 複数のアイテムの近傍がオブジェクトをどのように分類するかについて投票し、オブジェクトはその k 個の最近傍の中で最も人気のあるクラスに割り当てられます (k は正の数で、多くの場合非常に小さいです)。 k が 1 に等しい場合、オブジェクトはその単一の最近傍のカテゴリに属するものとして単純に分類されます。k-NN 回帰の結果は、オブジェクトに関連付けられた特定のプロパティの値です。 この値は、現在の位置に最も近い k 個の近傍の値の平均です。 k が 1 に等しい場合、出力の値は 1 つの最近傍の値から単純に取得されます。

メリット

(I) 次のトピックに関する洞察と検証:

第 1 章: K 最近傍アルゴリズム

第 2 章: 教師あり学習

第 3 章: パターン 認識

第 4 章: 次元の呪い

第 5 章: 最近傍探索

第 6 章: クラスター分析

第 7 章: カーネル 方法

第 8 章: 大マージン最近傍法

第 9 章: 構造化 kNN

第 10 章: 弱い監視

(II) 応答 k 最近傍アルゴリズムに関する公開トップの質問。

(III) 多くの分野での k 最近傍アルゴリズムの使用例の実例。

(IV) 説明する 17 の付録。 簡単に説明すると、k 最近傍アルゴリズムのテクノロジを 360 度完全に理解できるよう、各業界の 266 の新興テクノロジが紹介されています。

本書の対象者

プロフェッショナル 大学生、大学院生、愛好家、愛好家、およびあらゆる種類の k 最近傍アルゴリズムに関する基本的な知識や情報を超えたいと考えている人。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 23, 2023

Book preview

第 1 章: k 最近傍アルゴリズム

Evelyn FixとJoseph Hodgesは、1951年にノンパラメトリック教師あり学習手法として、統計学でk最近傍アルゴリズム(k-NN)を作成しました。回帰と分類は、その2つの用途です。どちらの状況でも、データ セットの k 個の最も近いトレーニング サンプルの入力で構成されます。k-NN を分類に適用するか回帰に適用するかによって、結果が決まります。

k-NN 分類の結果は、クラス メンバーシップです。オブジェクトが k 個の最近傍の多数決に基づいて割り当てられるクラスは、アイテムの近傍によって決定されます (k は正の整数で、通常は小さいです)。オブジェクトは、k = 1の場合、その1つの最近傍のクラスに割り当てられます。

k-NN 回帰の出力は、オブジェクトのプロパティ値です。k 個の最近傍の値の平均がこの数を構成します。出力は、k = 1の場合、1つの最近傍の値に割り当てられます。

k-NNでは、関数が評価され、関数が局所的に近似されるまで、すべての計算が延期されます。トレーニング データを正規化すると、フィーチャがさまざまな物理単位を反映している場合やサイズが大きく異なる場合に、分類の距離に依存するこの手法の精度を大幅に向上させることができます。

k-NN 分類または回帰を使用する場合、近傍は、クラスまたはオブジェクトのプロパティ値がわかっているオブジェクトのセットから選択されます。明示的なトレーニング フェーズは必要ありませんが、これはアルゴリズムのトレーニング セットと見なすことができます。

k-NNアルゴリズムには、データのローカル構造に敏感であるという特徴があります。

で値を取る

{\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}

ペアがあり {\mathbb {R}}^{d}\times \{1,2\} 、YはXのクラスラベルであるため、 X|Y=r\sim P_{r} r=1,2 (および確率分布)。 P_{r}

あるノルム \|\cdot \| \mathbb {R} ^{d} と 点 x\in {\mathbb {R}}^{d} が

(X_{{(1)}},Y_{{(1)}}),\dots ,(X_{{(n)}},Y_{{(n)}})

与えられたとき、 をトレーニングデータの並べ替えとします

\|X_{{(1)}}-x\|\leq \dots \leq \|X_{{(n)}}-x\|

。

トレーニングの例は、多次元特徴空間内のクラス ラベルを持つベクターです。アルゴリズムのトレーニングフェーズは、トレーニングサンプルの特徴ベクトルとクラスラベルの格納のみで構成されます。

ラベルなしベクトル (クエリまたはテスト ポイント) に最も近い k 個のトレーニング サンプルの中で最も普及しているラベルは、分類フェーズ中に割り当てられます (k はユーザー定義定数)。

ユークリッド距離は、連続変数の一般的な距離メトリックです。オーバーラップ メトリックなどの別のメトリックは、テキストの分類 (またはハミング距離) などの不連続変数に使用できます。たとえば、k-NNは、ピアソンやスピアマンなどの相関係数とともに、遺伝子発現マイクロアレイデータのコンテキストでのメトリックとして使用されています。多くの場合、大マージン最近傍分析や近傍コンポーネント分析などの特定のアルゴリズムを使用して距離メトリックを学習すると、k-NNの分類精度が大幅に向上します。

クラスの分布が歪んでいる場合、基本的な「多数決」の分類には不利があります。つまり、それらは膨大な数のためにk個の最近傍の間で共通する傾向があるため、より頻繁なクラスの例が新しい例の予測を支配する傾向があります。この問題を解決するための 1 つの解決策は、テスト位置とその k 個の最近傍のそれぞれとの間の距離を考慮して分類に重みを付けることです。k 個の最も近いポイントのクラス (回帰問題では値) のそれぞれに、テスト ポイントからの距離の逆数に比例する重みが乗算されます。データ表現の抽象化は、スキューを処理するための別の戦略です。初期トレーニング データの密度に応じて、自己組織化マップ (SOM) の各ノードは、比較可能なポイントのクラスターの代表 (中心) になります。その後、SOM を K-NN で使用できます。

kの理想的な数はデータによって異なります。一般に、K の値を高くすると、分類に対するノイズの影響は軽減されますが、クラス間の境界も曖昧になります。適切な k は、さまざまなヒューリスティック手法を使用して選択できます (「ハイパーパラメータの最適化」を参照)。最近傍アプローチは、クラスが最も近いトレーニングサンプルのクラスであると予測される特定の状況で使用されます(つまり、k = 1の場合)。

ノイズの多い特徴や無関係な特徴が存在する場合、または特徴の縮尺がそれらの関連性と矛盾している場合、k-NN 法の精度が大幅に低下する可能性があります。分類を強化するために、特性の選択やスケーリングについて多くの研究が行われてきました。進化的アルゴリズムは、機能のスケーラビリティを強化するための特に好まれる方法です。

特徴空間内の最も近い近傍のクラスに点 x を割り当てる最近傍分類子は、最も論理的な最近傍分類子、つまり C_{n}^{{1nn}}(x)=Y_{{(1)}} です。

1 つの最近傍分類器は、トレーニング データセットのサイズが無限大 (データの分布が与えられた場合に達成可能な最小エラー率) に近づくにつれて、エラー率がベイズ エラー率の 2 倍より悪くならないことを保証します。

k-最近傍分類器は、k個の最近傍に重み 1/k を割り当て、他のすべての人に0の重みを割り当てると見なすことができます。

これは、重み付き最近傍の分類子に適用されます。

つまり、ここで、i番目に近い近傍には重みが割り当てられます w_{{ni}} {\textstyle \sum _{i=1}^{n}w_{ni}=1} 。

重み付き最近傍分類器の高い一貫性に関する同様の発見も当てはまります。