k近傍法(k-NN)の簡単なPython実装

# k近傍法の概要
k近傍法(k-NearistNeighbor)は機械学習のアルゴリズムで教師あり学習で、分類問題などに使います。とても似た名前にk平均法(k-means)があるりますが、k-meansは教師なし学習でクラスタリングに使います。
k近傍法のアルゴリズム自体はとても単純です。分類したいデータと、既存のデータとの距離を計算し、距離が近いk点のデータの多数決でクラスを決定します。
例えばk=1のときは距離が一番近いデータの仲間である、とするだけです。
図を見たほうがわかりやすいですね。
![220px-KnnClassification.svg.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/188904/2b0cd9fb-1e86-5e94-7227-ba974100f443.png)
>k近傍法の例。標本（緑の丸）は、第一のクラス（青の四角）と第二のクラス（赤の三角）のいずれかに分類される。k = 3 なら、内側の円内にあるオブジェクトが近傍となるので、第二のクラスに分類される（赤の三角の方が多い）。しかし、k = 5 なら、それが逆転する。
引用:[wikipedia](https://ja.wikipedia.org/wiki/K%E8%BF%91%E5%82%8D%E6%B3%95)

以上からk近傍法の特徴として以下が挙げられます。

* 最も単純な教師なし学習である
* 事前に識別のための学習を必要としない
* 判別時に全データとの距離を計算するため、判別に時間がかかる
* 次元が大きくなると、計算コスト的にも精度的にも問題がある(いわゆる次元の呪いにハマりやすい性質がある)

# k近傍法の実装(Python)

簡単な実装

```python
import numpy as np
import scipy.spatial.distance as distance
import scipy.stats as stats


import numpy as np
import scipy.spatial.distance as distance
import scipy.stats as stats


class knn:
    def __init__(self,k):
        self.k = k
        self._fit_X = None  # 既存データを格納 
        self.classes = None  #
        self._y = None
    def fit(self, X, label):
        # Xは元のデータ点で、shape(data_num, feature_num)
        print("original data:\n", X)
        print("label:\n", label)
        self._fit_X = X
        # ラベルデータからクラスを抽出、またラベルをindexとした配列を作成
        # self.classes[self.label_indices] == label のように復元できるのでreturn_inverseという
        self.classes, self.label_indices = np.unique(label, return_inverse=True)
        print("classes:\n", self.classes)
        print("label_indices:\n", self.label_indices)
        print("classes[label_indices]で復元されるか確認:\n", self.classes[self.label_indices])
    def neighbors(self, Y):
        # Yは予測対象のデータ点(複数可)で, shape(test_num, feature_num) 
        # 予測対象の点とデータ点の距離を求めるので、test_num * data_num だけ距離を計算する
        dist = distance.cdist(Y, self._fit_X)
        print("テストデータと元データとの距離:\n", dist)
        # distはshape(test_num, data_num) となる
        # [[1.41421356 1.11803399 2.6925824  2.23606798]   テスト点1と元データ各点との距離
        #  [3.         2.6925824  1.80277564 1.41421356]   テスト点2と元データ各点との距離
        #  [3.31662479 3.20156212 1.11803399 1.41421356]]  テスト点3と元データ各点との距離
        
        # 距離を測定したらk番目までに含まれるindexをもとめる
        # argpartitionはk番目までと、それ以降にデータを分ける関数
        # argsortだと距離の順位もわかるが、素のk-nnでは距離順位の情報はいらないので、argpartitionを使う
        neigh_ind = np.argpartition(dist, self.k)
        # neigh_indのshapeは(test_num, feature_num)となる
        # 上のdistでk=2でargpartitionしたときの結果
        # 例えば1行目だと index 2,1 が上位2要素になっている。上の距離をみると、0.5と1.5が相当する
        # 2行目だと index 3, 2 が上位2要素で、1.73と1.80が相当する
        #[[1 0 3 2]
        # [3 2 1 0]
        # [2 3 1 0]]
        # k番目までの情報だけを取り出す
        neigh_ind = neigh_ind[:, :self.k]
        # neigh_indのshapeは(test_num, self.k)となる
        #[[1 0]   テスト点1に近い元データ点のindexのリスト
        # [3 2]   テスト点2に近い元データ点のindexのリスト
        # [2 3]]  テスト点3に近い元データ点のindexのリスト
        return neigh_ind
    def predict(self, Y):
        # k番目までのindexを求める shape(test_num, self.k)となる
        print("test data:\n",Y)
        neigh_ind = self.neighbors(Y)
        # stats.modeでその最頻値を求める. shape(test_num, 1) . _は最頻値のカウント数
        # self.label_indices は [0 0 1 1] で、元データの各点のラベルを表す
        # neigh_indは各テスト点に近い元データのindexのリストで shape(est_num, k)となる
        # self.label_indices[neigh_ind] で、以下のような各テスト点に近いラベルのリストを取得できる
        # [[0 0]  テスト点1に近い元データ点のラベルのリスト
        #  [1 1]  テスト点2に近い元データ点のラベルのリスト
        #  [1 1]] テスト点3に近い元データ点のラベルのリスト
        # 上記データの行方向(axis=1)に対してmode(最頻値)をとり、各テスト点が属するラベルとする
        # _はカウント数
        mode, _ = stats.mode(self.label_indices[neigh_ind], axis=1)
        # modeはaxis=1で集計しているのでshape(test_num, 1)となるので、ravel(=flatten)してやる
        # [[0]
        #  [1]
        #  [1]]
        # なおnp.intpはindexに使うデータ型
        mode = np.asarray(mode.ravel(), dtype=np.intp)
        print("test dataの各ラベルindexの最頻値:\n",mode)
        # index表記からラベル名表記にする. self.classes[mode] と同じ
        result = self.classes.take(mode)
        return result
```

予測してみる

```python
K = knn(k=2)
# 元のデータとラベルをセット
samples = [[0., 0., 0.], [0., .5, 0.], [1., 2., -2.5],[1., 2., -2.]]
label = ['a','a','b', 'b']
K.fit(samples, label)
# 予測したいデータ
Y = [[1., 1., 0.],[2, 2, -1],[1, 1, -3]]
p = K.predict(Y)
print("result:\n", p)
```
実行結果

```
>>result
original data:
 [[0.0, 0.0, 0.0], [0.0, 0.5, 0.0], [1.0, 2.0, -2.5], [1.0, 2.0, -2.0]]
label:
 ['a', 'a', 'b', 'b']
classes:
 ['a' 'b']
label_indices:
 [0 0 1 1]
classes[label_indices]で復元されるか確認:
 ['a' 'a' 'b' 'b']
test data:
 [[1.0, 1.0, 0.0], [2, 2, -1], [1, 1, -3]]
テストデータと元データとの距離:
 [[1.41421356 1.11803399 2.6925824  2.23606798]
 [3.         2.6925824  1.80277564 1.41421356]
 [3.31662479 3.20156212 1.11803399 1.41421356]]
test dataの各ラベルindexの最頻値:
 [0 1 1]
result:
 ['a' 'b' 'b']
```

# 参考文献
* [データ解析第十回「k-近傍法」 by 鈴木大慈](http://ibis.t.u-tokyo.ac.jp/suzuki/lecture/2015/dataanalysis/L10.pdf)
* [k最近傍法\(k\-Nearest Neighbor, k\-NN\)でクラス分類・回帰分析・モデルの適用範囲\(適用領域\)の設定をしよう！ \- Speaker Deck](https://speakerdeck.com/hkaneko/kzui-jin-bang-fa-k-nearest-neighbor-k-nn-dekurasufen-lei-hui-gui-fen-xi-moderufalseshi-yong-fan-wei-shi-yong-ling-yu-falseshe-ding-wosiyou)
* [k近傍法\(k\-Nearest Neighbor\)の理解 — OpenCV\-Python Tutorials 1 documentation](http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/html/py_tutorials/py_ml/py_knn/py_knn_understanding/py_knn_understanding.html)
* [機械学習\_k近傍法\_理論編 ｜ Developers\.IO](https://dev.classmethod.jp/machine-learning/2017ad_20171218_knn/)