Skip to content
検索結果に戻る

K近傍法

提唱者
Cover, T.M. & Hart, P.E.
年
1967
種類
Instance-based (non-parametric) learning

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

K近傍法(K-Nearest Neighbors, KNN)は、CoverとHartによって1967年に形式化された、ノンパラメトリックなインスタンスベースの手法であり、訓練データ中のk個の最も近い例を参照して、新しい観測値を分類または予測します。分類の場合はそれらの近傍の間で多数決を取り、回帰の場合はそれらの値の平均を取ります。

手法の背後にある直感

その考え方は単純です。類似した入力は類似した出力を傾向として持ちます。新しい点をラベル付けするために、KNNは特徴空間においてそれに最も近い訓練例のいくつかを見つけ、それらに決定させます。事前に適合される方程式はなく、訓練データ自体がモデルであり、予測は新しい点が到着したときにのみ行われます。

歴史学

最近傍パターン分類は、1967年にIEEE Transactions on Information Theoryに掲載されたThomas CoverとPeter Hartの論文によって、その形式的な統計的基盤が与えられ、最近傍ルールの誤り率を分析しました。KNNは、最も初期で最も永続的なインスタンスベース学習手法の1つとなり、標準的なベースライン分類器であり続けています。

使うべき場面

連続値、二値、または順序特徴量を持つ表形式データで、少なくとも約30個の観測値がある場合に、分類または予測にKNNを使用します。特定の分布を仮定しませんが、特徴量が正規化されていること、および特徴量の数がサンプルサイズに対して小さいままであること(pがnよりはるかに小さいことが望ましい)が必要です。小規模または高次元のサンプルでは、次元の呪いが支配的になり、近傍距離は情報を持たなくなります。そのため、ロジスティック回帰やナイーブベイズのようなパラメトリックモデルの方が良い選択となります。

限界と注意点

  • 特徴量のスケーリングに敏感です。標準化がない場合、大規模な特徴量が距離を支配します。
  • 高次元では急速に劣化します(次元の呪い)。近傍距離の意味が失われます。
  • 予測ごとに訓練セット全体をスキャンする必要があり、大規模データでの予測時には遅くなります。
  • 少なくとも中程度のサンプルサイズが必要です。小規模サンプルでは、最近傍の距離は意味を持ちません。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 概念的に単純で説明しやすい:訓練時の数式はなく、データがモデルです。
  • ノンパラメトリック — 基盤となる分布について仮定をしません。
  • 多クラス問題と複雑な非線形決定境界を自然に扱います。
  • 同じ基本的な考え方で、分類と回帰の両方に機能します。

応用

  • 表形式データを2つ以上のカテゴリに分類すること。
  • 最近傍の例の平均による数値予測(回帰)。
  • より複雑なモデルを試す前の、単純で解釈可能なベースライン。
  • 類似性が既知の例からの決定を駆動するパターン認識。

使い方

使い方

1

新しい観測値に対して、KNNは通常、特徴量全体にわたるユークリッド距離を使用して、それが各訓練例からどれだけ離れているかを測定します。距離はスケールに敏感であるため、特徴量は最初に標準化される必要があります。そうでなければ、大きな数値スケールで測定された変数が計算を支配し、どの近傍が最も近いと見なされるかを歪めてしまいます。

数式
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}
2

新しい観測値への距離が最も小さいk個の訓練点が、その近傍として選択されます。kの値は、決定がどれほど局所的かを制御します。小さいkはデータを密接に追跡しますがノイズに敏感であり、大きいkは境界を平滑化します。kは推測するのではなく、交差検証(例えば、エルボー法)によって選択されるべきです。

3

近傍が予測を決定します。分類の場合は、新しい点はk個の近傍の中で最も一般的なクラス(多数決)を取り、回帰の場合はそれらの値の平均を取ります。これにより、手法は理解しやすくなりますが、すべての予測で訓練セットをスキャンする必要があります。

数式
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}

よくある落とし穴

  • 特徴量の標準化をスキップすること。これにより、1つの大規模変数が静かに距離を制御します。
  • 交差検証ではなく、手動でkを選択すること。
  • 多くの特徴量と少ない観測値でKNNを適用すること。次元/サンプル比率がそれを壊します。
  • 精度、リコール、F1、および混同行列の代わりに、精度のみを報告すること。

よくある質問

kの値の選択方法

kは推測するのではなく、交差検証で選択されるべきです。例えば、さまざまな値を試してみて、エラーの改善が止まる場所を見つけるためにエルボー法を使用します。小さいkはデータを密接に追跡しますがノイズに敏感であり、大きいkは決定境界を平滑化します。

なぜ特徴量を標準化する必要があるのですか?

KNNは距離を使用して「最も近い」を決定しますが、これはスケールに敏感です。1つの特徴量が他の特徴量よりもはるかに大きな数値スケールにある場合、それは距離を支配し、近傍セットを歪めます。各特徴量が公平に貢献するように、特徴量の標準化(例えば、StandardScalerを使用)が必要です。

なぜKNNは多くの特徴量で苦労するのですか?

高次元空間では、すべての点がほぼ等距離になります(次元の呪い)。そのため、「最も近い」近傍はもはや意味のある近さではなくなります。KNNのパフォーマンスは急速に低下し、通常はナイーブベイズやロジスティック回帰のようなパラメトリックモデルが好まれます。pをnよりはるかに小さく保つことが役立ちます。

トレーニングステップはありますか?

通常の意味ではありません。KNNはインスタンスベース(遅延)です。単に訓練データを格納し、予測時にすべての作業を行い、新しい点の最近傍を見つけるために距離を計算します。

関連する手法

参考文献

  1. Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.

    DOI 文献を開く
    コピーしました。