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

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

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

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

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

現(xiàn)有一個新的數(shù)據(jù)：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() 方法返回排序后的索引，而不會對原數(shù)據(jù)的順序有任何影響：

import numpy as np

nearest = np.argsort(distances)

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

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

最后，對這 k 個距離最近的樣本對應的標記進行統(tǒng)計，找出占比最多標記即為 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]

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

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

Scikit Learn 中 k-鄰近算法在 neighbors 模塊中，初始化時傳入?yún)?shù) n_neighbors 為 6，即為上面的 k：

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)

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

kNN_classifier.fit(X_train, y_train)

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

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

y_predict 值為0，與前面實現(xiàn)的 kNN 方法結(jié)果一致。

定義一個 KNNClassifier 類，其構(gòu)造器方法傳入?yún)?shù) k，表示預測時選取的最相似數(shù)據(jù)的個數(shù)：

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() 方法對待測數(shù)據(jù)集進行預測，參數(shù) X_predict 類型為矩陣。該方法使用列表解析式對 X_predict 進行了遍歷，對每個待測數(shù)據(jù)調(diào)用了一次 _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]

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

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

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

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

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

import numpy as np
from sklearn import datasets

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

現(xiàn)在將樣本分為20%示例測試數(shù)據(jù)和80%比例訓練數(shù)據(jù)：

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 作為訓練數(shù)據(jù)用于訓練模型，X_test 和 y_test 作為測試數(shù)據(jù)驗證模型準確性。

對于第二個問題，還是以 Scikit Learn 中提供的鳶尾花數(shù)據(jù)為例，其標記 y 的內(nèi)容為：

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])

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

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

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

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

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

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

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

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

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

可以將兩個問題的解決方案封裝到一個方法中，seed 表示隨機數(shù)種子，作用在 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() 方法對樣本數(shù)據(jù)進行了預處理后，開始訓練模型，并且對測試數(shù)據(jù)進行驗證：

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 是對測試數(shù)據(jù) X_test 的預測結(jié)果，其中與 y_test 相等的個數(shù)除以 y_test 的個數(shù)就是該模型的正確率，將其和 y_test 進行比較可以算出模型的正確率：

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

調(diào)用該方法，返回一個小于等于1的浮點數(shù)：

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()?方法，里面就調(diào)用了 accuracy_score() 方法，將測試數(shù)據(jù) X_test 和 y_test 作為參數(shù)傳入該方法中，可以直接計算出算法正確率。

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 是一種超參數(shù)，超參數(shù)是在算法運行前需要決定的參數(shù)。 Scikit Learn 中 k-近鄰算法包含了許多超參數(shù)，在初始化構(gòu)造函數(shù)中都有指定：

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

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

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

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

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

Github | ML-Algorithms-Action