はじめに

こんばんは．僕は大学院で機械学習を研究しています．僕としては非常におもしろいのですが，研究にならないようなアイデア（ゴミ）をここに投下していきます．笑

k-Nearest Neighbor (kNN)は非常にシンプルで，非線形な分離平面を実現できることから広く用いられている分類器である．Qiitaでも記事が書かれてた．

http://qiita.com/kenmatsu4/items/c91f5740808022decaae

kNNは新しい入力に対して，その入力の近傍のラベルの多数決でそのラベルを予測をするが，これは全ラベルの適応的重み付きの多数決として解釈できる．そして，オリジナルkNNの重みは滑らかな関数ではない．場合によってはkは入力に応じて変化すべきであり，事前に固定すると柔軟性を失う可能性がある．例えば，ある入力に対してはk=3が望ましいが，別の入力に対してはk=5が望ましい，といった場合に，kを一意に決めていてはk=4とする他ない．ここでは，kNNの重みを滑らかにし，入力に応じてkを変化させることができるように定式化してみる．そして，実験により，性能が改善されるかどうかを確認する．

kNN

kNNを確率的に解釈する（本当はnormalizeしないといけないが省いています）．入力空間を$\mathcal{X}(=\mathbb{R}^d)$, 出力空間を$\mathcal{Y}=\{1,\ldots,c \}$とし，入力$\boldsymbol{x}$がクラス$y$に属する確率を以下で定義する．

p(y|x) = \frac{1}{k}\sum_{i \in N_k(\boldsymbol{x})} I[y_i=y]

ここで，$N_k(\boldsymbol{x})$は$\boldsymbol{x}$のk個のNeighborsのインデックスである．そして，新しい入力$\boldsymbol{x}$に対して，そのラベル$\hat{y}$を以下のように予測する．

\hat{y} = \arg\max_{\mathcal{Y}} \ p(y|\boldsymbol{x})

kNNではいわゆる「学習」は行わない．トレーニングデータをストアするのみで，すぐ予測が行える．次の章では，これを全ラベルの適応的重み付き多数決として解釈する．

Weighted NN

kNNは，新しい入力点の近傍を求め，その近傍に属するサンプルのラベルの多数決でラベルを予測する．これはすなわち，その近傍以外の重みをゼロにしていると解釈できる．つまり，以下と等価である（本質的に）．

\begin{align*}
p(y|\boldsymbol{x}) &= \frac{1}{n}\sum_{i=1}^n w_i(x) I[y_i=y] \\
w_i(x) &= \left\{
\begin{array}{lcr}
1 & if & x_i \in N_k(x) \\
0 & otherwise & 
\end{array}
\right.
\end{align*}

今回はこの重みをもう少しソフトにしてみようと思う．
具体的には，ガウシアンカーネルなどを用いて，

w_i(x) = \exp\left(-\frac{\|\boldsymbol{x}-\boldsymbol{x}_i\|^2}{2\sigma^2}\right)

と定義する．これにより，重みが滑らかになる．
重みを滑らかにしたことによって性能が改善されるか，実験を通して確認してみる．

実験

実験してみる．データの生成にはsklearn.datasetsの中にあるcircle,moon,blobを使い，高次元データは適当にGaussianで作る．データの概観はこんな感じ．
　　

さて，今回特に観察したいのは，

サンプルが少ない時の性能
ノイズが多い時の性能
高次元データに対する性能
の3つ．重みを滑らかにしたので，サンプルが少ない時でも少し性能が上がることが期待される．また，kを適応的に決めることができるのでノイズが多いときにも性能の改善が期待される．さらに，高次元空間で性能が上がるかも検証してみる．以下の表に結果を示す．数値は精度（標準偏差）であり，試行回数は100回である．few sampleではサンプル数を100とし，noisyではサンプル数は1000で，データにノイズをのせたものである．高次元データとしてGaussianは高次元データを表し，次元数dをいろいろ変えて実験してみた．今回使ったkNNはscikit-learnで実装してあるもので，パラメータはweights="uniform"，n_neighborsはcross-validationで決めた．

datasets	kNN	wNN
circle (few sample)	0.627 (0.099)	0.635 (0.115)
circle (noisy)	0.716 (0.028)	0.723 (0.026)
moon (few sample)	1 (0)	1 (0)
moon (noisy)	0.738 (0.022)	0.752 (0.022)
blob (few sample)	0.97 (0.064)	0.971 (0.063)
blob (noisy)	0.970 (0.052)	0.972 (0.049)
Gaussian (d=100)	0.986 (0.008)	0.993 (0.005)
Gaussian (d=500)	0.947 (0.013)	0.984 (0.009)
Gaussian (d=1000)	0.9 (0.019)	0.972 (0.016)

結果は悪くはなかった．サンプルが少ない時，ノイズが乗っているとき，それぞれで少し性能の改善が見られた．特に高次元データに対してはまぁまぁ性能の改善が見られた．検定はしていない...．

Code

Gist: https://gist.github.com/nkt1546789/be1e02e715d3bc462fcc

まとめ

weighted Nearest Neighborsという概念を考えてみた．実験の結果，そんなに悪いアイデアでもないのかな，という印象．でも多分もう提案されているよね．ということで”紹介した”ということにしておく．読んでくれてありがとうございました．

参考

http://scikit-learn.org/stable/auto_examples/neighbors/plot_classification.html