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

k-近鄰算法通過測(cè)量不同特征值之間的距離方法進(jìn)行分類。

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

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

假定存在訓(xùn)練樣本集 X_train（X_train.shape=(10, 2)），對(duì)應(yīng)的標(biāo)記 y_train（y_train.shape=(10,)，包含0、1)，使用 matplotlib.pyplot 作圖表示如下（綠色的點(diǎn)表示標(biāo)記0，紅色的點(diǎn)表示標(biāo)記1）：

現(xiàn)有一個(gè)新的數(shù)據(jù)：x（x = np.array([3.18557125, 6.03119673])），作圖表示如下（藍(lán)色的點(diǎn)）：

首先，使用歐拉距離公式計(jì)算 x 到 X_train 中每個(gè)樣本的距離：

import math

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

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

import numpy as np

nearest = np.argsort(distances)

第三，取 k 個(gè)距離最近的樣本對(duì)應(yīng)的標(biāo)記：

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

最后，對(duì)這 k 個(gè)距離最近的樣本對(duì)應(yīng)的標(biāo)記進(jìn)行統(tǒng)計(jì)，找出占比最多標(biāo)記即為 x 的預(yù)測(cè)分類，此例的預(yù)測(cè)分類為0：

from collections import Counter

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

將上面的代碼封裝到一個(gè)方法中：

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]

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

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

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

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)

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

kNN_classifier.fit(X_train, y_train)

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

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

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

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

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

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

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

predict() 方法對(duì)待測(cè)數(shù)據(jù)集進(jìn)行預(yù)測(cè)，參數(shù) X_predict 類型為矩陣。該方法使用列表解析式對(duì) X_predict 進(jìn)行了遍歷，對(duì)每個(gè)待測(cè)數(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]

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

如果模型很壞，預(yù)測(cè)的結(jié)果就不是我們想要的。同時(shí)實(shí)際情況中，很難拿到真實(shí)的標(biāo)記（label），無(wú)法對(duì)模型進(jìn)行檢驗(yàn)。

訓(xùn)練模型時(shí)訓(xùn)練樣本沒有包含所有的標(biāo)記。

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

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

import numpy as np
from sklearn import datasets

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

現(xiàn)在將樣本分為20%示例測(cè)試數(shù)據(jù)和80%比例訓(xùn)練數(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 作為訓(xùn)練數(shù)據(jù)用于訓(xùn)練模型，X_test 和 y_test 作為測(cè)試數(shù)據(jù)驗(yàn)證模型準(zhǔn)確性。

對(duì)于第二個(gè)問題，還是以 Scikit Learn 中提供的鳶尾花數(shù)據(jù)為例，其標(biāo)記 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是以順序存儲(chǔ)的，在將樣本劃分為訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)過程中，如果訓(xùn)練數(shù)據(jù)中才對(duì)標(biāo)記只包含0、1，這樣的訓(xùn)練數(shù)據(jù)對(duì)于模型的訓(xùn)練將是致命的。以此，應(yīng)將樣本數(shù)據(jù)先進(jìn)行隨機(jī)處理。

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

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

將隨機(jī)化的索引數(shù)組分為訓(xùn)練數(shù)據(jù)的索引與測(cè)試數(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ù)分為訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)：

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

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

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

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

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

調(diào)用該方法，返回一個(gè)小于等于1的浮點(diǎn)數(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 中有一個(gè) score()?方法，里面就調(diào)用了 accuracy_score() 方法，將測(cè)試數(shù)據(jù) X_test 和 y_test 作為參數(shù)傳入該方法中，可以直接計(jì)算出算法正確率。

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ù)是在算法運(yùn)行前需要決定的參數(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-近鄰算法是一個(gè)比較簡(jiǎn)單的算法，有其優(yōu)點(diǎn)但也有缺點(diǎn)。

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

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

Github | ML-Algorithms-Action