scikit-learn機械学習⑳k近傍アルゴリズム

前回は、勾配ブースティングによる分類の実験を行いました。

これまでブースティング、バギング、ランダム・フォレスト、決定木などを扱ってきましたが、これらは全てノンパラメトリックな手法です。

ノンパラメトリックの意味は後で解説しますが、今回紹介するk近傍アルゴリズム（k近傍法、k-Nearest Neighbors、k-NN）もノンパラメトリックな手法になります。

k-近傍アルゴリズム（以下、k-NN）の基本的な仕組みは単純です。以下、分類を例として解説します。

下図を見て下さい。色分けされた丸はデータポイントとそのクラス（ターゲット）を表示しています。ここでのクラスは、A（緑色）、B（赤色）、C（黄色）の３つがあります。さて、青色のデータポイントはどのクラスに属するでしょうか。

なんとなく、周りに黄色のデータポイントが多いのでクラスCだと予想は出来ます。これがk-NNの基本的な考え方です。

なお、k-NNの「k」は整数の値です。例えば、$${k=3}$$としましょう。この$${k=3}$$の値は、入力データ（上図の青色のポイント）に最も近い（近傍にある）３つのデータポイントを選んで、多数決でクラスを決めるために使います。

見てわかるとおり、最も近くにある３つのクラスは黄色が大多数（この場合は全てですが）を占めているので、入力データ（青色のポイント）はクラスCに属すると予測します。

次に、$${k}$$近傍内に、それぞれのクラスが同数個あるケース（上図とは異なります）を考えます。その場合は、下図に示すように距離によって重み付をして判断したりすることが可能です。

上記のケースでは、クラスA、B、Cのデータポイントが近傍内に一つずつありますが、入力データ（青色のポイント）からの距離を考慮するとクラスA（緑色）が予測値となります。

よって、k-NNではデータポイントの距離や重み付けという概念が含まれます。

次に$${k}$$の値を大きくしたケース（上図とは異なります）を考えましょう。

下図は、$${k=6}$$による近傍を表示しています。近傍にあるクラスの数がどれも同じですが、距離による重み付けがされているので、この場合もクラスA（緑色）が予測されるでしょう。

なお、k-NNを分類ではなく数値予測に使う場合は、近傍の$${k}$$データポイントからの平均値を計算します。重みがあるならば、加重平均を計算します。

k-NNの基本的な仕組みは以上です。本文ではさらに、k-NNの数式による定義とデータ構造について解説します。