はじめに

最初は機械学習に対し、何かよく分からないマシーンが人間の様に学習しているイメージを持っていましたが、最近は学習という操作は単なる写像操作ではないかと思う様になってきました。

パーセプトロン系であれば、トレーニングサンプルという数字の羅列を、重みという数字の羅列に変換しているだけですし、決定木においても、ノード数分の分割特徴量と閾値という数字の羅列に変換しているだけです。

つまり学習という操作は、大量にある数字の羅列を、そこに含まれる情報をある程度保ったまま、それよりも少ない数字の羅列に変換する写像であると考えることができます。

もっというと学習とはトレーニングサンプルというデータを、不必要な情報を圧縮して小さくする操作とも言えます。

k近傍法のアルゴリズム

k近傍法は、怠惰学習と呼ばれており、この様な写像操作によるトレーニングサンプルの圧縮を行いません。要するに学習せずに、トレーニングサンプルを丸暗記する形になります。

あるテストサンプルがあったとし、そのクラスラベルを予想する場合を考えます。

テストサンプルと特徴量空間上の距離が近い物から順番に ${k}$ 個のトレーニングサンプルを抜き出し、多数決でテストサンプルのクラスラベルを決定します。

つまりテストサンプルの周りに、クラスラベルが1のトレーニングサンプルがいっぱいあるとそのテストサンプルのクラスラベルは1になるということです。

テストサンプル毎にトレーニングサンプルとの距離を計算し、更にそれをソートする操作が入りますので、効率は非常に悪く時間がかかりますが、かなり複雑な決定領域を表現することができ、予測精度も一般的に中々高いみたいです。

距離というと中学校で習った三平方の定理を思い出します。三平方の定理から導かれる距離をユークリッド距離と言いい、 ${n}$ 次元空間上の2つの位置ベクトル ${\mathbf{x}^i}$ 、 ${\mathbf{x}^j}$ の距離 ${d}$ は以下の式で表せます。

${\displaystyle d = \left[ \sum_{k=1}^{n} \left( x_{k}^{i} - x_{k}^{j} \right)^{2} \right]^{\frac{1}{2} }\tag{1} }$

(1)式の ${2}$ の表記を ${1}$ にしたものは、マンハッタン距離と呼ばれています。

${\displaystyle d = \sum_{k=1}^{n} \left| x_{k}^{i} - x_{k}^{j} \right| \tag{2} }$

これを一般化した形式では以下の様に表し、

${\displaystyle d = \left[ \sum_{k=1}^{n} \left( | x_{k}^{i} - x_{k}^{j} | \right)^{p} \right]^{\frac{1}{p} }\tag{3} }$

ミンコフスキー距離と呼ぶみたいです。

scikit-learnのk近傍法では、デフォルトの距離指標はユークリット距離になっています。

どういう時に他の距離指標を使うか分からないですが、、取り敢えずはユークリット距離を使っておけばいいでしょうかね。

例によってアヤメデータを使い、自作版とscikit-learn版でk近傍法の結果を比較しています。

注意点ですが、k近傍法を使うときは、特徴量空間の距離を揃えるためにサンプルデータを標準化する必要があるので注意してください。

--------------------------------------------------
my k-nearest neighbors score:0.933333333333
sklearn k-nearest neighbors score:0.933333333333

まあ合いますよね。

f:id:darden:20170128155702p:plain:w600

f:id:darden:20170128155735p:plain:w600

決定領域も完全一致ですね。

ただソートが入るので自作版はかなり遅いです。それに比べてscikit-learnのk近傍法は異様に速いですね。

今回はソースコードは見てないですが、Cythonだけでなくソートを速くするアルゴリズムも何か使って入るかもしれませんね。

取り敢えずはk近傍法のアルゴリズムは理解できたので良しとしましょう。

ただ虚しいのは、自分で頑張ってスクリプトを書きましたが、scikit-learnにはかなわないですね。やはり自作するよりも既にあるものを使った方がはるかに効率はいいでしょうね。