Pythonでk-NNをフルスクラッチで実装してみた

Scikit-learnを始めとしたパッケージが充実してきているおかげで、データ分析に関わる人もスクラッチから機械学習モデルを実装する機会が少なくなっています。

しかし、機械学習モデルを理解するためにはそのモデルを実装してみるのが一番早いと言われています。たとえパラメータをいじるだけの作業であったとしても、モデルの理解が深い人とそうでない人では、問題解決の質が変わってきます。

本記事では、最も基本的な分類モデルである k-NN (k-Nearest Neighbor) 法をフルスクラッチで実装したのでご紹介します。

目次

k-Nearest Neighbor法

k-Nearest Neighbor 法 (k-NN) は k近傍法とも呼ばれ、分類モデルの中でももっともシンプルに実装できるものとして広く知られています。

k-NNとは、特徴量空間にデータをプロットしたときに、プロットと距離が近い学習データを近いものから順にk個選び出し、それらの学習データのクラスを多数決することでデータのクラスを決定する分類モデルです。

図のように、青四角クラスと赤丸クラスの学習データが配置された特徴量空間を考えます。

k-NNのkは、テストデータ（星型）から何個の近傍点をクラス予測時に考慮するかということを決定するパラメータです。この例の場合、k=3のときは赤い学習データのほうが多いため赤クラスに分類されます。一方で、k=5のときは青のほうが多数となるため、テストデータは青クラスに分類されます。

k-NNをPythonで実装する

k-NNの概要については理解していただけたと思います。実にシンプルなモデルであるため、スクラッチから実装することはさほど難しくないです。それどころか、データサイエンティストであればこれくらいは実装できるのが最低要件だと思います。

シンプルである一方で、テストデータと複数の学習データとの距離をそれぞれ計算する必要があるため、計算量が多いという欠点があります。

こちらが実装したコードです。

import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import f1_score
import time


def load_data():
    iris = load_iris()
    return train_test_split(iris.data, iris.target, test_size=0.3)

def predict(k, test_plot, X_train,  y_train):
    dist_dict = {}

    for i, train_plot in enumerate(X_train):
        dist = np.linalg.norm(train_plot - test_plot)

        if len(dist_dict) <  k:
            dist_dict[dist] = y_train[i]    
        elif dist < np.max(list(dist_dict)) and len(dist_dict) == k:
            dist_dict.pop(np.max(list(dist_dict)))
            dist_dict[dist] = y_train[i]     

    count = np.bincount(list(dist_dict.values()))
    pred = np.argmax(count)
    return pred

def predict_test_data(k, X_train, X_test, y_train, y_test):
    pred_list = []
    
    for test_plot in X_test:
        pred = predict(k, test_plot, X_train, y_train)
        pred_list.append(pred)
    return f1_score(y_test, pred_list, average='macro')

if __name__ == '__main__':
    X_train, X_test, y_train, y_test = load_data()
    start_time = time.time()
    fscore = predict_test_data(3, X_train, X_test, y_train, y_test)
    process_time = time.time() - start_time
    print('F-score: {:.3f}'.format(fscore))
    print('Process time: {:.3f} sec'.format(process_time))

実装したモデルをirisデータセットを用いてF値で評価すると、次のような結果となりました。

F-score: 0.978
Process time: 0.118 sec

クラスの分類がうまくいっていることを確認することができました。

k-NNの特徴としてすべての点との距離を求める処理が必要となることから計算量が大きくなってしまうということがあります。そのため、プログラムの実行時間を計測できるような処理を実装しています。今回は何も考えずに最も単純な方法で実装したため計算量がかなり大きくなってしまっています。

Scikit-learnなどで実装されているk-NNは、この問題をできるだけ解決するように実装の工夫がなされています。実装を工夫した際のコードについてはまた別の機会にご紹介できればと思います。

まとめ

k-Nearest Neighbor法をフルスクラッチで実装してみました。まずは計算量などを考慮せずに最低限の精度が出るモデルの実装ができたので、次のステップとして高速化を考えていきたいです。k-NNは最も単純な機械学習モデルのひとつです。この記事を参考にしつつ、一から実装してみてはいかがでしょうか。

関連記事
決定木分類器をフルスクラッチで実装した際の記事です。
hktech.hatenablog.com