k-近傍法（k-nearest neighbor algorithm、k-NN）についてメモ。
同じような名前の「k-means法」とは異なるので注意。

【目次】

k-近傍法とは

特徴空間において、距離が近い既知データから未知データのクラスを予測する方法である。分類問題の「教師あり学習」である。
k-近傍法は教師データから学習（モデル作成）する訳でなく、単にデータ間の距離で分類する単純なアルゴリズムであり「怠惰学習」とも呼ばれる。

例えば、校庭（特徴空間）の様々な遊具（座標）の中で、すべり台付近に集まっている子たちが10人いて、そのうち７人はＡ組、２人はＢ組の生徒だと分かっているとする（既知の情報）。この情報から残り１名（未知の情報）を予測すると、Ａ組の生徒の可能性が高いと予測される。

k-近傍法は、このようなアルゴリズムで周囲の既知データ（訓練データ）を多数決して、未知データのクラスを予測する。
なお、k-近傍法の「k」は周囲のいくつの既知データで予測するかを指定するハイパーパラメータである。多数決で予測を出すため奇数にするのが一般的である。
パラメータ k の値の違いで予測結果が変わることがある。

f:id:cochineal19:20210523124358p:plain:w450

なお、k=1 の場合を「最近傍法」と呼び、一番近くの既知データのクラスをそのまま採用する。

ミンコフスキー距離

ここで、近さの尺度として、特徴空間上の距離を表す「ミンコフスキー距離（Lpノルム）」に触れたい。
ミンコフスキー距離は「マンハッタン距離（L1ノルム）」や「ユーグリッド距離（L2ノルム）」を一般化したもので次の形をとる。

ミンコフスキー距離（Lpノルム）

$\quad d\left( x,y\right) =\left( \sum ^{n}_{i=1}\left| x_{i}-y_{i}\right| ^{p}\right) ^{1/p}$

パラメータ p=1 にてマンハッタン距離（L1ノルム）

$\quad d\left( x,y\right) =\left( \sum ^{n}_{i=1}\left| x_{i}-y_{i}\right| ^{1}\right) ^{1/1} = \sum ^{n}_{i=1}\left| x_{i}-y_{i}\right|$

パラメータ p=2 にてユーグリッド距離（L2ノルム）

$\quad d\left( x,y\right) =\left( \sum ^{n}_{i=1}\left| x_{i}-y_{i}\right| ^{2}\right) ^{1/2} = \sqrt{ \sum ^{n}_{i=1}\left( x_{i}-y_{i}\right)^{2}}$

k-近傍法では、このパラメータ p を設定することでマンハッタン距離やユーグリッド距離など複数の距離を扱える。一般的にはユーグリッド距離を使うことが多い。

pythonコード

sklearn の neighbors の KNeighbors にてk-近傍法を実装できる。
予測に用いる周囲の既知データ数（ハイパーパラメータ k ）は、n_neighbors で指定する。デフォルトは n_neighbors=5 。
ミンコフスキー距離（Lpノルム）は p で指定する。デフォルトは p=2（ユーグリッド距離、L2ノルム）。

from sklearn import model_selection, neighbors, metrics
import seaborn as sns
import matplotlib.pyplot as plt

#-- データ取得・分割
iris = sns.load_dataset("iris")
X_train, X_test, y_train, y_test = train_test_split(iris.iloc[:,:4], iris.iloc[:,4], test_size=0.2, random_state=99)

#-- k-近傍法
kn = neighbors.KNeighborsClassifier(n_neighbors=5)
kn.fit(X_train, y_train)    #-- 学習
y_pred1 = kn.predict(X_test) #-- 予測

#-- 評価
print(metrics.confusion_matrix(y_test, y_pred1))
print(metrics.classification_report(y_test, y_pred1))