機器學習演算法學習01：利用Numpy撰寫KNN演算法解決手寫體數字識別問題

前言

在深度學習未徹底被大眾接受前，人們對人工智能的研究是企圖研究出一系列巧妙的演算法解決相關計算機視覺問題，這里面涌現了無數令人嘆為觀止的演算法（隨機森林，遺傳演算法，SVM，馬爾科夫鏈，KNN等）即使在深度學習逐漸占據解決計算機視覺人工智能問題的演算法的今天，不可否認，依舊有許多深度學習演算法吸收了這些傳統演算法的思想，從而來進行改進，所以學習這些傳統演算法也是非常有必要的🖖🖖🖖，本次我們介紹的是如何利用numpy庫來構造KNN演算法解決手寫體數字識別問題，

本篇博客的代碼也已上傳到github倉庫，不麻煩的話可以點顆星🥰🥰🥰🥰🥰：

liujiawen-jpg/KNN-Alogorith: The KNN algorithm is implemented by numpy (github.com)

1.演算法介紹

KNN演算法全稱（K-NearestNeighbor）直譯為K個最近的鄰居，是一種聚類演算法，該演算法認為我們在判斷一個物體的類別可以根據與他非常相似的K個物體的類別（這K個物體的類別是已知的）來決定，

舉個例子，假設我們需要鑒別某個水果的類別，我們通過比對發現他和我們擁有的水果中7個物品非常相似，我們發現這七個物品其中6個是西瓜，一個是菠蘿，所以我們自然的認為這個物品是西瓜，這就是一個7NN演算法，

直觀一點，我們可以觀察上圖，該圖之中存在三個類別ω1，ω2 ω3，我們使用5NN尋找五個與X相鄰最近的點發現其中四個屬于ω1那么我們就可以推斷出X屬于ω1類別，

看了上面兩個例子，相信你應該對KNN演算法有了基礎的認識了吧，那么我們這里可以先總結出他的流程：

輸入：資料x 已知類別的樣本z 輸出：x的類別y

開始

1. 計算資料x與z中每個樣本的距離d

2. 利用距離d獲取與x距離前K小的索引index

3. 利用index從樣本z中選取出k個樣本

4. 統計這k個樣本的類別，類別數統計最多的作為x的類別

   結束

2.資料集介紹

這里我們使用的是sklearn庫提供的手寫體資料集，該資料集包括了1797張手寫的0-10的圖片

import sklearn.datasets as datasets  
import matplotlib.pyplot as plt
import random
x, y = datasets.load_digits(return_X_y=True) #獲取訓練集和樣本
# 這里我們可以可視化圖片來進行查看
x1 = random.choice(x) # 隨機取出x中的資料
x1 = np.array(x1)
x1 = np.reshape(x1, (8,8)) # 取出來的向量被壓縮成了64的序列，而要顯示成圖片我們需要將他改成二維的形狀
plt.imshow(x1)
plt.show()

通過以上的代碼我們可以查看圖片的內容，我們看出來這些其實就是一系列0-10的圖片（如下兩張就是0和2）（由于設定的是隨機取出，所以可以多運行幾次，每次運行的結果都不一樣）

3.先決條件：安裝numpy,sklearn庫

python由于他的方便簡單，前人開發了無數的易于使用的庫，但是這些并不會隨著你的安裝而自動安裝（sklearn庫好像會自動安裝），所以我們需要自己輸入命令來安裝，不過也是非常簡單的這里如果遇到不知道使用什么命令可以查看這個網站：

Search results · PyPI

利用這個網站查詢結果如下，我們復制命令 pip install numpy即可

然后我們如果是在windows系統上直接，同時按下win鍵和R鍵，在彈出的視窗中輸入cmd并執行，最后在彈出的命令列界面中輸入查詢到的命令：

pip install numpy

等待下載完成即可，如果遇到下載速度非常慢的話可以使用這個博客的方法（解決 ERROR: Could not find a version that satisfies the requirement xxx 的問題_JMU-HZH的博客-CSDN博客）

安裝sklearn庫也同理，

4.演算法代碼撰寫

在此次手動實作KNN演算法中，我一共寫了兩個py檔案，KNN.py和run.py，其中KNN.py實作了kNN演算法，而run.py則為程式啟動腳本，讓我們來一一介紹吧🕵??♂?🕵??♂?🕵??♂?：

KNN.py

import numpy as np
class KNN():
    def __init__(self, x_test, x_train, k):
        
        self.neighbor_distance = np.zeros((len(x_test), len(x_train)))
        #neighbor_distance陣列記錄測驗資料與已知樣本資料的距離
        self.pred = np.zeros(len(x_test,))
        # pred陣列記錄所有樣本的預測值
        self.neighbors = k
        # 記錄需要找出多少個近鄰

    def knn(self, x_test, x_train, y_train):
        for i in range(len(x_test)):
            for j in range(len(x_train)):
                self.neighbor_distance[i][j] = self.compute_distance(
                    x_test[i], x_train[j]) #計算所有的測驗資料和樣本資料的距離
            self.pred[i] = self.compute_pred(
                self.neighbor_distance[i], y_train) #獲得所有樣本資料的預測值
        return self.pred

    def compute_distance(self, x, y):
        # 這里使用mae來進行計算距離
        distance = np.sum(np.abs(x - y))
        # 也可以使用mse來進行計算兩者的距離
        # distance = np.sum(np.square(x - y))
        return distance

    def compute_pred(self, distance, y_train):
        k_pred_index = distance.argsort()[:self.neighbors] #利用numpy的argsort方法獲取前K小樣本的索引
        k_pred = [y_train[index] for index in k_pred_index]#獲取與測驗資料最接近K個物體的類別
        pred = np.argmax(np.bincount(k_pred)) #計算哪個類別出現的最多作為測驗資料的類別
        return pred

run.py:

import numpy as np
import sklearn.datasets as datasets  # 資料集模塊
from sklearn.model_selection import train_test_split  # 劃分訓練集和驗證集
import matplotlib.pyplot as plt
import random
from KNN import KNN
# 讀取資料集
x, y = datasets.load_digits(return_X_y=True)

# 使用sklearn中的方法劃分我們的測驗資料和訓練資料
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.2)

# KNN最近鄰進行分類，這里的K數字可以任意改變
k = 7
knn = KNN(x_test, x_train, k) #初始化我們的knn類別
pred = knn.knn(x_test, x_train, y_train) #獲取預測值

# 利用numpy提供的函式計算分類準確率
accuracy = np.mean(pred == y_test)
print(accuracy)

5.實驗結果分析

在本次實驗中存在三個可供我們調整的變數，分別是測驗資料與訓練資料的比值，計算距離的方法，選取的近鄰個數K，接下來我們使用控制變數法來修改他們觀察正確率的變化，

先給定我們的baseline，當測驗資料與訓練資料數量比為 1 ：4，計算距離采用mae平均絕對誤差時準確率為0.986

5.1 保持其他變數不變，修改計算距離方式

1.計算距離采用mse(均方絕對誤差)：

多次實驗正確率為0.994到0.97，取二者平均值計算約為0.986

2 計算距離采用RMSE(均方根誤差)方式:

多次實驗正確率穩定在0.978左右

5.2 保持其他變數不變，修改k的個數

k = 3, accuracy = 0.983

k=4, accuracy = 0.986

k = 5 accuracy = 0.986

k=6, accuracy = 0.972

k=7,accuracy = 0.985

k=8,accuracy = 0.978

k=9,accuracy=0.980

k=10, accuracy=0.971

5.3 保持其他變數不變，修改測驗資料與訓練樣本的比值

比值為 3:7 , accuracy=0.976

比值為4:6，accuracy = 0.976

比值為1:1, accuracy = 0.971

比值為6:4，accuracy= 0.967

比值為7:3，accuracy=0.965

比值為8:2，accuracy=0.949

比值為9:1，accuracy=0.869

通過以上三個控制變數實驗，我們可以發現

• 修改計算資料與資料之間距離方式對提升正確率并無太大作用，其中使用mae和mse效果最好，RMSE效果較差
• 可以看出來當K的值越發上升時正確率開始逐漸下降，可能是由于當決定資料類別的“近鄰”太多時噪聲過多影響了精度
• 而調整測驗資料與訓練樣本的比值則會影響正確率，可以看到當測驗資料越來越多訓練樣本越來越少模型正確率越來越低嗎，我們可以看出使用KNN我們的訓練樣本必須盡可能地多，以保證我們的準確率，

結語

在本次實驗中，我完成了獨立撰寫kNN演算法的任務，并通過控制變數法完成了對于kNN中各個變數影響性能的研究，同時我也認識到傳統機器學習演算法的設計巧妙，即使在深度學習一統江湖的今天，它對我們這些人工智能的后來者依舊具有非常好的啟示意義，值得我們去認真學習，