使用NumPy從頭開始進行K最近鄰分類

在這篇文章中，我將實現K最近鄰（KNN），這是一種機器學習算法，可用於分類和迴歸，它屬於監督學習算法的範疇。它對標記的數據集進行操作，並預測測試數據的類別（分類）或數值（迴歸）。

我將使用NumPy實現它，並將使用其他庫來實現數據可視化。

<code>import numpy as np
from sklearn.datasets import make_classification/<code>

我們首先導入庫和函數：

• numpy：它將被用於多維數組的數值計算，因為我們正在處理高維向量。
• make_classification：我們將使用它來創建我們的分類數據集。我們可以決定所需的類和特徵的數量，是否要對樣本進行聚類等。

<code>def euclidian_distance(a, b):
    return np.sqrt(np.sum((a-b)**2, axis=1))/<code>

在KNN算法中，我們需要一個函數來計算訓練數據點與我們想要分類的數據之間的距離。在這裡，我選擇了歐氏距離，因為它在機器學習應用中被廣泛使用。可以嘗試使用其他距離度量，如曼哈頓距離、Chebychev距離等。

<code>def kneighbors(X_test, return_distance=False):
       
        n_neighbors = 5
        dist = []
        neigh_ind = []
        
        point_dist = [euclidian_distance(x_test, X_train) for x_test in X_test]

        for row in point_dist:
            enum_neigh = enumerate(row)
            sorted_neigh = sorted(enum_neigh, key=lambda x: x[1])[:n_neighbors]
    
            ind_list = [tup[0] for tup in sorted_neigh]
            dist_list = [tup[1] for tup in sorted_neigh]
    
            dist.append(dist_list)
            neigh_ind.append(ind_list)
        
        if return_distance:
            return np.array(dist), np.array(neigh_ind)
        
        return np.array(neigh_ind)/<code>

數據點是否接近由上面實現的歐幾里得距離函數確定。在這裡，數據點之間距離的實際值並不重要，我們感興趣的是這些距離的順序。

在訓練過程之前，我們選擇一個數字作為我們的超參數（k）。因此，例如，當k=5時，我們指的是前5個最近的數據點。

在上面的kneighbors函數中，我們找到測試數據集(我們要分類的數據點)中的每個點與數據集其餘部分(即訓練數據)之間的距離。我們將這些距離存儲在point_dist中，其中每一行對應一個測試數據點到所有訓練數據之間的距離列表。我們遍歷每一行，對其進行枚舉，然後根據距離對它排序。我們枚舉每一行的原因是，我們不想丟失用來計算距離的訓練數據點的索引，因為我們將在以後引用它們。

sorted_neigh包含測試數據點的前k個最近鄰，並且根據其歐氏距離對它們進行排序。然後，我們從sorted_neigh中提取索引和距離值並返回它們。

<code>def predict(X_test, weights='uniform'):
        
        class_num = 3
        
        if weights=='uniform':
            neighbors = kneighbors(X_test)
            y_pred = np.array([np.argmax(np.bincount(y_train[neighbor])) for neighbor in neighbors])
        
            return y_pred 
    
        if weights=='distance':
        
            dist, neigh_ind = kneighbors(X_test, return_distance=True)
        
            inv_dist = 1/dist
            
            mean_inv_dist = inv_dist / np.sum(inv_dist, axis=1)[:, np.newaxis]
            
            proba = []
            
            for i, row in enumerate(mean_inv_dist):
                
                row_pred = self.y_train[neigh_ind[i]]
                
                for k in range(class_num):
                    indices = np.where(row_pred==k)
                    prob_ind = np.sum(row[indices])
                    proba.append(np.array(prob_ind))
        
            predict_proba = np.array(proba).reshape(X_test.shape[0], class_num)
            
            y_pred = np.array([np.argmax(item) for item in predict_proba])
            
            return y_pred/<code>

找到k個最近鄰後，我們嘗試預測我們的測試數據點所屬的類。在這裡，我們有k個neighbors，每個neighbor在決定類別標籤時都有投票權。但是，投票機制可能會根據所選標準而有所不同。在上面的

predict函數中，如果權重被選擇為一致的，則意味著每個neighbor在決定類別標籤時都具有相等的投票權重，而與他們的距離無關。

假設我們的測試數據點有5個最近鄰，其中3個屬於A類，其中2個屬於B類。我們不考慮neighbors之間的距離，因為大部分neighbors都是A類的，所以我們認為測試數據點屬於A類。但是，如果選擇權重作為距離，那麼這意味著neighbors的距離確實很重要。因此，最接近測試數據點的任何neighbor都具有與其距離的倒數成比例的最大權重（投票）。因此，對於前面的例子，如果屬於類A的那2個點比其他3個點更接近測試數據點，那麼，這個事實本身可能會在決定數據點的類標籤時起到很大的作用。

在predict函數中，如果權重是一致的，則很容易預測數據點的標籤。首先，我們獲得neighbors的索引，然後使用這些索引從訓練數據集中獲取其相應的類標籤。neighbors中的每一行對應於每個測試數據點具有的neighbors集合。然後，我們使用numpy的 bincount函數查找類標籤的出現次數，並獲取與預測的類標籤對應的最大出現次數的索引。

這裡，我們找到neighbors距離的均值倒數，併為每個測試數據點計算類概率。

<code>def score(X_test, y_test):
    y_pred = predict(X_test)
        
    return float(sum(y_pred == y_test))/ float(len(y_test))/<code>

score函數作為一個非常簡單的準確度指標廣泛用於分類問題。我們只是返回正確分類標籤的百分比。這很簡單!

<code>from sklearn.datasets import make_classification
X, y = make_classification(n_samples = 1000, n_features=2, n_redundant=0, n_informative=2,
                             n_clusters_per_class=1, n_classes=3, random_state=21)

mu = np.mean(X, 0)
sigma = np.std(X, 0)

X = (X - mu ) / sigma/<code>

我們利用sklearn.dataset的make_classification函數填充數據集。然後，我們通過減去平均值然後除以標準差來對每個數據點進行歸一化。

<code>data = np.hstack((X, y[:, np.newaxis]))
        
np.random.shuffle(data)

split_rate = 0.7

train, test = np.split(data, [int(split_rate*(data.shape[0]))])

X_train = train[:,:-1]
y_train = train[:, -1]

X_test = test[:,:-1]
y_test = test[:, -1]

y_train = y_train.astype(int)
y_test = y_test.astype(int)/<code>

創建數據集後，我們在訓練階段實現了隨機拆分，從而獲得了訓練和測試集。

<code>kneighbors(X_test)/<code>

現在該測試我們的knn實現了。

<code>predict(X_test)/<code>

正如預期的那樣，predict函數輸出測試數據的預測類標籤。

<code>score(X_test, y_test)
#0.99/<code>

看起來我們的實現做得還可以，因為它的精確度很高。

K最近鄰的類實現

<code>import numpy as np

class KNearestNeighbors():
    def __init__(self, X_train, y_train, n_neighbors=5, weights='uniform'):

        self.X_train = X_train
        self.y_train = y_train

        self.n_neighbors = n_neighbors
        self.weights = weights

        self.n_classes = 3

    def euclidian_distance(self, a, b):
        return np.sqrt(np.sum((a - b)**2, axis=1))

    def kneighbors(self, X_test, return_distance=False):

        dist = []
        neigh_ind = []

        point_dist = [self.euclidian_distance(x_test, self.X_train) for x_test in X_test]

        for row in point_dist:
            enum_neigh = enumerate(row)
            sorted_neigh = sorted(enum_neigh,
                                  key=lambda x: x[1])[:self.n_neighbors]

            ind_list = [tup[0] for tup in sorted_neigh]
            dist_list = [tup[1] for tup in sorted_neigh]

            dist.append(dist_list)
            neigh_ind.append(ind_list)

        if return_distance:
            return np.array(dist), np.array(neigh_ind)

        return np.array(neigh_ind)

    def predict(self, X_test):

        if self.weights == 'uniform':
            neighbors = self.kneighbors(X_test)
            y_pred = np.array([
                np.argmax(np.bincount(self.y_train[neighbor]))
                for neighbor in neighbors
            ])

            return y_pred

        if self.weights == 'distance':

            dist, neigh_ind = self.kneighbors(X_test, return_distance=True)

            inv_dist = 1 / dist

            mean_inv_dist = inv_dist / np.sum(inv_dist, axis=1)[:, np.newaxis]

            proba = []

            for i, row in enumerate(mean_inv_dist):

                row_pred = self.y_train[neigh_ind[i]]

                for k in range(self.n_classes):
                    indices = np.where(row_pred == k)
                    prob_ind = np.sum(row[indices])
                    proba.append(np.array(prob_ind))

            predict_proba = np.array(proba).reshape(X_test.shape[0],
                                                    self.n_classes)

            y_pred = np.array([np.argmax(item) for item in predict_proba])

            return y_pred

    def score(self, X_test, y_test):
        y_pred = self.predict(X_test)

        return float(sum(y_pred == y_test)) / float(len(y_test))/<code> 

在實現所有必要的函數之後，很容易創建knn的類實現。這裡只有新添加的_init__函數。

將我們的實現與Sklearn的KNeighborsClassifier進行比較

<code>from sklearn.datasets import load_iris
from KNearestNeighbors import KNearestNeighbors
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import pandas as pd


dataset = load_iris()

X = dataset.data
y = dataset.target

mu = np.mean(X, 0)
sigma = np.std(X, 0)
X = (X - mu ) / sigma

X_train, X_test, y_train, y_test = train_test_split(\
                X, y, test_size=0.3, random_state=45)

our_classifier = KNearestNeighbors(X_train, y_train, n_neighbors=3)
sklearn_classifier = KNeighborsClassifier(n_neighbors=3).fit(X_train, y_train)

our_accuracy = our_classifier.score(X_test, y_test)
sklearn_accuracy = sklearn_classifier.score(X_test, y_test)

pd.DataFrame([[our_accuracy, sklearn_accuracy]],
             ['Accuracy'],    
             ['Our Implementation', 'Sklearn\'s Implementation'])/<code>

我們自己的實現和sklearn的實現的準確性看起來是基本相同的。