k近傍法（knn）とは
k近傍法(k-nearest neighbor algorithm, k-nn)は機械学習のアルゴリズムの一つです。簡単に説明すると、データをグループ分けするにあたり、対象とするあるデータがどのグループに含まれるかを周囲のデータの多数決で推測するという手法です。これだけではいまいちイメージがわかないと思いますので、より詳しく見ていきましょう。
k近傍法のアルゴリズム
例えば以下の図のようなデータがあったとします。赤、青、緑の三つのクラスがあるのがわかります。
このデータを我々人間がグループ分けする場合、我々は塊になっているところのデータをだいたい同じグループと分類するでしょう。つまり上図の☆は青に属するのではないかと考えるわけです。
これと同じことをアルゴリズムとして実装したいのです。そこで以下のように、☆に近い点を近い順に任意の数、k個だけ選びます。その選んだ点に最も多く含まれているグループに☆も分類されると考えます。これがk近傍法です。
例えば仮にk=5に設定した場合、図4のように5個取ります。この場合は取った5個のうち青は 4個、緑は1個で最も多いのは青だったため、☆は青に分類されることがわかります。
※ k近傍法において、範囲内のどのクラスの数も同じ場合には多数決で決定できないのではないかと思われたかもしれません。そのような場合、まず距離の大きさで近い方を取り、それでも距離も同じ場合にはデータセットのラベル順によって決定されることが多いようです(scikit-learnのk近傍法ではこの方法を取っています、参考：https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier)。今回の私たちの実装においては、このような場合にはただデータセットのラベル順で先に来る方に分類されるようにします。
なお、このように分類対象のデータをその周りの教師データを用いて分類することから、k近傍法はアルゴリズムとしては教師あり学習に分類されます。
k近傍法の利点、欠点
k近傍法は非常にシンプルな手法であるため、学習を必要としない、外れ値に頑健であるといったメリットがあります。一方、それぞれのデータについて多数決を取らなければならないという性質上、データ数が増えるに伴って計算量も非常に多くなってしまうというデメリットがあります。
k近傍法の実装
irisデータセットの分類
ここまででk近傍法の詳細について理解できたかと思います。では次に、k近傍法アルゴリズムを実装することで動作を確認してみましょう。
まずは分類対象のデータを用意しましょう。今回はscikit-learnのirisデータセットを用いることにします。irisデータセットはアヤメの特徴量のデータセットです。データをロードして、その詳細を見てみましょう。
データの個数は150個あり、その特徴量の数は4つとわかりました。
また、その特徴量の詳細を見てみましょう。
このことから、特徴量4つは具体的にはsepal length(ガクの長さ)、sepal width(ガクの幅)、petal length(花弁の長さ)、petal width(花弁の幅)であるということがわかりました。
また、クラスは何種類なのか見てみます。
クラスは3種類で、アヤメはsetosa, versicolor, virginicaという種類に分類できるようです。
では、データの詳細が分かったので早速k近傍法を実装したいところですが、今回は2次元平面上に描画することをイメージしやすいように、適当に特徴量を4つから2つに限定しましょう(特徴量を減らす場合、データの性質をよく表している特徴量を残すべきですが、今回はその説明は省略しています)。
また、データは訓練用データと試験用データに分割する必要があるのでした。sickit-learnにはデータを訓練用と試験用に分割してくれるtrain_test_splitがあります。
データを訓練用と試験用に分割したことで、現在のデータの形状は以下のようになっていることがわかります。
では、データの準備ができたのでk近傍法の詳細を実装していきましょう。k近傍法ではまず、対象の試験データと周りの訓練データ全てとの距離を計算する必要があります。訓練データは学習する必要はなく、ただモデル内に取り込むだけです。取り込んでおいた訓練データと試験データの距離には、ユークリッド距離を用います。
#距離の計算の実装例(訓練データx_trainはあらかじめモデル内に記憶してあるものとする)
def calc_dist(x_test): #x_testは試験データ、距離の計算結果の配列を返す
#距離を格納する配列
dist = np.zeros([x_test.shape[0], x_train.shape[0]])
for i in range(x_test.shape[0]):
for j in range(x_train.shape[0]):
distance = np.sum((x_test[i] - x_train[j])**2) #距離の計算にはユークリッド距離を用いる
dist[i][j] = distance
return dist距離が計算できたら次に、試験データに最も近いk個の訓練データで多数決を行います。ここでもっとも多かったクラスを所属先のクラスとして設定します。
#クラスの予測の実装例(訓練データのラベルy_trainはあらかじめモデル内に記憶してあるものとする)
def predict(x_test, k): #x_testは試験データ、kはいくつのデータを考慮するか
distance = calc_dist(x_test) #距離の配列を取得
pred = np.zeros(x_test.shape[0]) #予測結果を格納する配列
for i in range(x_test.shape[0]):
sorted_index = np.argsort(distance[i,:]) #距離の配列のインデックスを昇順にソート(並び替え)する
sorted_labels = y_train[sorted_index][:k] #ラベルの配列も距離の配列のインデックスに合わせて並び替え、上からk個を取り出す
u, counts = np.unique(sorted_labels, return_counts=True) #取り出したラベルの頻度(個数)をカウント
pred[i] = u[np.argmax(counts)] #最も頻度が高かったクラスを予測結果とする
return pred
これらを踏まえて、k近傍法モデルの実装は以下のようになります。
import numpy as np
class KNN():
def __init__(self, k):
self.k = k
#訓練はただ訓練データを取り込むだけ
def train(self, x_train, y_train):
self._x_train = x_train
self._y_train = y_train
#予測を行うメソッド
def predict(self, x_test):
distance = self.calc_dist(x_test) #距離の配列を取得
pred = np.zeros(x_test.shape[0]) #予測結果を格納する配列
for i in range(x_test.shape[0]):
sorted_index = np.argsort(distance[i,:]) #距離の配列のインデックスを昇順にソート(並び替え)する
sorted_labels = self._y_train[sorted_index][:self.k] #ラベルの配列も距離の配列のインデックスに合わせて並び替え、上からk個を取り出す
u, counts = np.unique(sorted_labels, return_counts=True) #取り出したラベルの頻度(個数)をカウント
pred[i] = u[np.argmax(counts)] #最も頻度が高かったクラスを予測結果とする
return pred
#距離を計算し、その結果を返すメソッド
def calc_dist(self, x_test):
dist = np.zeros([x_test.shape[0], self._x_train.shape[0]]) #距離を格納する配列
for i in range(x_test.shape[0]):
for j in range(self._x_train.shape[0]):
distance = np.sum((x_test[i]-self._x_train[j])**2) #距離の計算にはユークリッド距離を用いる
dist[i][j] = distance
return distでは、このモデルを用いて実際に試験データを分類してみましょう。また、予測結果がどのくらい正しかったのか、正解率も計算してみましょう。
100%に近く、非常に高い正解率を出せていることがわかります。
MNISTデータセットの分類
さて、k近傍法の実装を理解できたところで、次により難しいデータセットを分類してみます。今度は手書き数字の画像データセットである、MNISTデータセットを分類してみましょう。
MNISTデータセットはどんなデータセットなのか、まずデータをロードしていくつか表示してみましょう。
表示してみてわかる通り、MNISTデータセットは手書き数字の画像データです。また、データのサイズは訓練データが(5000, 28, 28)、テストデータが(800, 28, 28)となっていました。ここで、train_setに関して画像1枚のサイズは縦×横で(28, 28)となっており、それが5000枚あるという意味です。test_setについても画像の枚数が800枚であるというだけで、同じです。
扱いやすくするため、28×28の画像を1次元ベクトルに直してしまいましょう。
先ほどのirisデータセットでは2つしか特徴量がなかった一方、こちらのデータセットの特徴量はなんと784もあります。しかも数字は1~10まであるので10クラス分類です。
大変そうに見えますが理屈は特徴量が2つのときと全く同じなので、今回実装したk近傍法モデルは特徴量やクラス数が多くても問題なく動作するように実装してあります。実際に学習させ、正解率を表示してみましょう。結構時間がかかるかもしれません。
irisデータセットを分類したときとはうってかわって、精度がかなり低いことが分かります。k近傍法は画像データセットのような特徴量が多すぎるデータに対しては効果的でないことがわかりました。
まとめ
今回はk近傍法について解説しました。仕組み自体はそれほど複雑なものではないと思いますが、機械学習における代表的な手法の一つですのでよく理解しておきましょう。次はk平均法について解説しようと思いますので、ぜひそちらも併せてご覧ください。
