摘要：近鄰算法通過測量不同特征值之間的距離方法進行分類。對于近鄰算法來說，它是一個特殊的沒有模型的算法，但是我們將其訓練數據集看作是模型。算法優缺點近鄰算法是一個比較簡單的算法，有其優點但也有缺點。

k-近鄰算法通過測量不同特征值之間的距離方法進行分類。

對于一個存在標簽的訓練樣本集，輸入沒有標簽的新數據后，將新數據的每個特征與樣本集中數據對應的特征進行比較，根據算法選擇樣本數據集中前k個最相似的數據，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。

這里只是對單個新數據的預測，對同時多個新數據的預測放在后文中。

假定存在訓練樣本集 X_train（X_train.shape=(10, 2)），對應的標記 y_train（y_train.shape=(10,)，包含0、1)，使用 matplotlib.pyplot 作圖表示如下（綠色的點表示標記0，紅色的點表示標記1）：

現有一個新的數據：x（x = np.array([3.18557125, 6.03119673])），作圖表示如下（藍色的點）：

首先，使用歐拉距離公式計算 x 到 X_train 中每個樣本的距離：

import math

distances = [math.sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]

第二，對 distances 進行升序操作，使用 np.argsort() 方法返回排序后的索引，而不會對原數據的順序有任何影響：

import numpy as np

nearest = np.argsort(distances)

第三，取 k 個距離最近的樣本對應的標記：

topK_y = [y_train[i] for i in nearest[:k]]

最后，對這 k 個距離最近的樣本對應的標記進行統計，找出占比最多標記即為 x 的預測分類，此例的預測分類為0：

from collections import Counter

votes = Counter(topK_y)
votes.most_common(1)[0][0]

將上面的代碼封裝到一個方法中：

import numpy as np
import math

from collections import Counter


def kNN(k, X_train, y_train, x):
    distances = [math.sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
    nearest = np.argsort(distances)

    topK_y = [y_train[i] for i in nearest[:k]]
    votes = Counter(topK_y)
    return votes.most_common(1)[0][0]

一個典型的機器學習算法流程是將訓練數據集通過機器學習算法訓練（fit）出模型，通過這個模型來預測輸入樣例的結果。

對于 k-近鄰算法來說，它是一個特殊的沒有模型的算法，但是我們將其訓練數據集看作是模型。Scikit Learn 中就是怎么處理的。

Scikit Learn 中 k-鄰近算法在 neighbors 模塊中，初始化時傳入參數 n_neighbors 為 6，即為上面的 k：

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)

fit() 方法根據訓練數據集“訓練”分類器，該方法會返回分類器本身：

kNN_classifier.fit(X_train, y_train)

predict() 方法預測輸入的結果，該方法要求傳入的參數類型為矩陣。因此，這里先對 x 進行 reshape 操作：

X_predict = x.reshape(1, -1)
y_predict = kNN_classifier.predict(X_predict)

y_predict 值為0，與前面實現的 kNN 方法結果一致。

定義一個 KNNClassifier 類，其構造器方法傳入參數 k，表示預測時選取的最相似數據的個數：

class KNNClassifier:
    def __init__(self, k):
        self.k = k
        self._X_train = None
        self._y_train = None

fit() 方法訓練分類器，并且返回分類器本身：

def fit(self, X_train, y_train):
    self._X_train = X_train
    self._y_train = y_train
    return self

predict() 方法對待測數據集進行預測，參數 X_predict 類型為矩陣。該方法使用列表解析式對 X_predict 進行了遍歷，對每個待測數據調用了一次 _predict() 方法。

def predict(self, X_predict):
    y_predict = [self._predict(x) for x in X_predict]
    return np.array(y_predict)

def _predict(self, x):
    distances = [math.sqrt(np.sum((x_train - x) ** 2))
                 for x_train in self._X_train]
    nearest = np.argsort(distances)

    topK_y = [self._y_train[i] for i in nearest[:self.k]]
    votes = Counter(topK_y)

    return votes.most_common(1)[0][0]

上面通過訓練樣本集訓練出了模型，但是并不知道這個模型的好壞，還存在兩個問題。

如果模型很壞，預測的結果就不是我們想要的。同時實際情況中，很難拿到真實的標記（label），無法對模型進行檢驗。

訓練模型時訓練樣本沒有包含所有的標記。

對于第一個問題，通常將樣本集中一定比例（如20%）的數據作為測試數據，其余數據作為訓練數據。

以 Scikit Learn 中提供的鳶尾花數據為例，其包含了150個樣本。

import numpy as np
from sklearn import datasets

iris = datasets.load_iris()
X = iris.data
y = iris.target

現在將樣本分為20%示例測試數據和80%比例訓練數據：

test_ratio = 0.2
test_size = int(len(X) * test_ratio)

X_train = X[test_size:]
y_train = y[test_size:]

X_test = X[:test_size]
y_test = y[:test_size]

將 X_train 和 y_train 作為訓練數據用于訓練模型，X_test 和 y_test 作為測試數據驗證模型準確性。

對于第二個問題，還是以 Scikit Learn 中提供的鳶尾花數據為例，其標記 y 的內容為：

array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])

發現0、1、2是以順序存儲的，在將樣本劃分為訓練數據和測試數據過程中，如果訓練數據中才對標記只包含0、1，這樣的訓練數據對于模型的訓練將是致命的。以此，應將樣本數據先進行隨機處理。

np.random.permutation() 方法傳入一個整數 n，會返回一個區間在 [0, n) 且隨機排序的一維數組。將 X 的長度作為參數傳入，返回 X 索引的隨機數組：

shuffle_indexes = np.random.permutation(len(X))

將隨機化的索引數組分為訓練數據的索引與測試數據的索引兩部分：

test_ratio = 0.2
test_size = int(len(X) * test_ratio)

test_indexes = shuffle_indexes[:test_size]
train_indexes = shuffle_indexes[test_size:]

再通過兩部分的索引將樣本數據分為訓練數據和測試數據：

X_train = X[train_indexes]
y_train = y[train_indexes]

X_test = X[test_indexes]
y_test = y[test_indexes]

可以將兩個問題的解決方案封裝到一個方法中，seed 表示隨機數種子，作用在 np.random 中：

import numpy as np

def train_test_split(X, y, test_ratio=0.2, seed=None):
    if seed:
        np.random.seed(seed)
    shuffle_indexes = np.random.permutation(len(X))

    test_size = int(len(X) * test_ratio)
    test_indexes = shuffle_indexes[:test_size]
    train_indexes = shuffle_indexes[test_size:]

    X_train = X[train_indexes]
    y_train = y[train_indexes]

    X_test = X[test_indexes]
    y_test = y[test_indexes]

    return X_train, X_test, y_train, y_test

Scikit Learn 中封裝了 train_test_split() 方法，放在了 model_selection 模塊中：

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

通過 train_test_split() 方法對樣本數據進行了預處理后，開始訓練模型，并且對測試數據進行驗證：

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)
kNN_classifier.fit(X_train, y_train)
y_predict = kNN_classifier.predict(X_test)

y_predict 是對測試數據 X_test 的預測結果，其中與 y_test 相等的個數除以 y_test 的個數就是該模型的正確率，將其和 y_test 進行比較可以算出模型的正確率：

def accuracy_score(y_true, y_predict):
    return sum(y_predict == y_true) / len(y_true)

調用該方法，返回一個小于等于1的浮點數：

accuracy_score(y_test, y_predict)

同樣在 Scikit Learn 的 metrics 模塊中封裝了 accuracy_score() 方法：

from sklearn.metrics import accuracy_score

accuracy_score(y_test, y_predict)

Scikit Learn 中的 KNeighborsClassifier 類的父類 ClassifierMixin 中有一個 score()?方法，里面就調用了 accuracy_score() 方法，將測試數據 X_test 和 y_test 作為參數傳入該方法中，可以直接計算出算法正確率。

class ClassifierMixin(object):
    def score(self, X, y, sample_weight=None):
        from .metrics import accuracy_score
        return accuracy_score(y, self.predict(X), sample_weight=sample_weight)

前文中提到的 k 是一種超參數，超參數是在算法運行前需要決定的參數。 Scikit Learn 中 k-近鄰算法包含了許多超參數，在初始化構造函數中都有指定：

def __init__(self, n_neighbors=5,
             weights="uniform", algorithm="auto", leaf_size=30,
             p=2, metric="minkowski", metric_params=None, n_jobs=None,
             **kwargs):
    # code here

這些超參數的含義在源代碼和官方文檔[scikit-learn.org]中都有說明。

k-近鄰算法是一個比較簡單的算法，有其優點但也有缺點。

優點是思想簡單，但效果強大， 天然的適合多分類問題。

缺點是效率低下，比如一個訓練集有 m 個樣本，n 個特征，則預測一個新的數據的算法復雜度為 O(m*n)；同時該算法可能產生維數災難，當維數很大時，兩個點之間的距離可能也很大，如 (0,0,0,...,0) 和 (1,1,1,...,1)（10000維）之間的距離為100。

Github | ML-Algorithms-Action