Pythonのscipyを使ったk近傍法(K-Nearest Neighbors)の実装方法を解説する

2023.01.18 2022.10.21

今回は、PythonでK-Nearest Neighborsをスクラッチで実装する方法を学びます。

KNNは教師ありアルゴリズムであり、分類と回帰の両方のタスクに使用することができます。

KNNは非常に簡単に実装することができます。

この記事では、分類タスクを実行するために、KNNアルゴリズムをゼロから実装します。

この記事もチェック：Python(sklearn)を使ってKNN(k近傍法アルゴリズム)の機械学習を実装する方法

K-最近傍アルゴリズムを支える直観力
PythonでK-Nearest Neighborsをゼロから実装する
K-Nearest Neighbors の完全な Python コード
1. 虹彩データセットを用いたゼロからのK-Nearest Neighborsの構築
まとめ

K-最近傍アルゴリズムを支える直観力

K-最近傍モデルでは、データセット全体を保存し、それに類似する点に基づいてデータ点を分類するため、学習は不要です。

学習データのみに基づいて予測を行います。

#Importing the required modules

import numpy as np

from scipy.stats import mode
 
#Euclidean Distance

def eucledian(p1,p2):

    dist = np.sqrt(np.sum((p1-p2)**2))

    return dist
 
#Function to calculate KNN

def predict(x_train, y , x_input, k):

    op_labels = []

    #Loop through the Datapoints to be classified

    for item in x_input: 

        #Array to store distances

        point_dist = []

        #Loop through each training Data

        for j in range(len(x_train)): 

            distances = eucledian(np.array(x_train[j,:]) , item) 

            #Calculating the distance

            point_dist.append(distances) 

        point_dist = np.array(point_dist) 

        #Sorting the array while preserving the index

        #Keeping the first K datapoints

        dist = np.argsort(point_dist)[:k] 

        #Labels of the K datapoints from above

        labels = y[dist]

        #Majority voting

        lab = mode(labels) 

        lab = lab.mode[0]

        op_labels.append(lab)
 
    return op_labels

上の図を考えてみましょう。

赤と緑の2つのクラスがあり、新しいデータ点（黒）が与えられ、この新しいデータ点がどちらのクラスに属するかを指定するよう求められています。

KNNは、似たような項目はより近いグループになる傾向があるという考えに基づいています。

従って、この新しいデータポイントは赤のグループに近いことが明らかであり、アルゴリズムはこのポイントを赤に分類することになります。

このアルゴリズムの詳細については、Wikiのページを参照してください。

KNNにおける距離の計算方法。

マンハッタン法
ユークリッド法
ミンコフスキー法
マハラノビス距離
etc..

今回は、ユークリッド距離を使って、学習データセットの各点から新しいデータ点の近さを計算することにします。

この記事もチェック：半教師付き学習(SSL)を用いてラベルのないデータから分類器モデルを学習するための初心者向けチュートリアルです。

PythonでK-Nearest Neighborsをゼロから実装する

まず、K-Nearest NeighborsをScratchで実装するための手順を把握します。

ステップ1. データ点間の距離を計算するために、適切な距離メトリックを把握します。

ステップ2. 距離を配列に格納し、その距離の昇順でソートする（インデックスを保持する、つまりNumPyのargsortメソッドを使用することができる）。

ステップ3. ソートされたリストの最初のK個の要素を選択します。

ステップ4. 多数決を行い、出現回数が最大のクラスを、分類されるデータポイントの新しいクラスとして割り当てます。

K-Nearest Neighbors の完全な Python コード

上記の手順をコードに変換して、K-Nearest Neighborsをゼロから実装してみましょう。

#Importing the required modules
#Importing required modules

from sklearn.metrics import accuracy_score

from sklearn.datasets import load_iris

from numpy.random import randint
 
#Loading the Data

iris= load_iris()
 
# Store features matrix in X

X= iris.data
#Store target vector in 

y= iris.target
 
#Creating the training Data

train_idx = xxx = randint(0,150,100)

X_train = X[train_idx]

y_train = y[train_idx]
 
#Creating the testing Data

test_idx = xxx = randint(0,150,50) #taking 50 random samples

X_test = X[test_idx]

y_test = y[test_idx]
 
#Applying our function 

y_pred = predict(X_train,y_train,X_test , 7)
 
#Checking the accuracy
accuracy_score(y_test, y_pred)

predict関数の入力引数には、Training dataset、True Labels、Datapoints to classify、そして最近傍の数(K)が必要です。

虹彩データセットを用いたゼロからのK-Nearest Neighborsの構築

さて、いよいよ実装をいくつかのデータでテストしてみましょう。

0.98

結果は以下の通りです。

K-Nearest Neighbors from Scratch Illustration — KNN Illustration

Kを7にすると、我々の実装したモデルは与えられたデータに対して非常に良い性能を発揮するようです。

この記事もチェック：Pythonでsklearnを使ってデータをトレーニングセットとテストセットに分割する方法

まとめ

この記事では、独自の K-Nearest Neighbors をスクラッチから実装し、分類問題に適用しました。

KNN アルゴリズムの内部動作を決定し、アルゴリズムの作成に関わるステップを調べました。

KNNは非常にシンプルであるため、機械学習において非常に強力で有用なアルゴリズムです。

もし、関連するゼロからの実装に興味があれば、以下の記事をご覧ください。

ゼロから始めるロジスティック回帰
Pythonでゼロから始めるK-Meansクラスタリングアルゴリズム
PythonでゼロからBag of Wordsモデルを作成する
PythonでゼロからTF-IDFモデルを作る
ゼロから始める線形回帰

次回お会いできる日まで。

この記事もチェック：知っておきたいPythonの機械学習アルゴリズムTOP5