K-Nearest Neighbor

作為一種沒有顯式訓(xùn)練和學(xué)習(xí)過程的分類和回歸算法封豪，k 近鄰在眾多有監(jiān)督機器學(xué)習(xí)算法中算是一種比較獨特的方法谴轮。說它獨特，是因為 k 近鄰不像其他模型有損失函數(shù)吹埠、有優(yōu)化算法第步、有訓(xùn)練過程。

原理

給定一個訓(xùn)練數(shù)據(jù)集缘琅，對于新的輸入實例粘都，根據(jù)這個實例最近的 k 個實例所屬的類別來決定其屬于哪一類。所以相對于其它機器學(xué)習(xí)模型和算法刷袍，k 近鄰總體上而言是一種非常簡單的方法翩隧。

距離的度量方式

找到與該實例最近鄰的實例，這里就涉及到如何找到做个，即在特征向量空間中鸽心，我們要采取何種方式來對距離進行度量。

距離的度量用在 k 近鄰中我們也可以稱之為相似性度量居暖，即特征空間中兩個實例點相似程度的反映顽频。在機器學(xué)習(xí)中，常用的距離度量方式包括歐式距離太闺、曼哈頓距離糯景、余弦距離以及切比雪夫距離等。在 k 近鄰算法中常用的距離度量方式是歐式距離省骂，也即 L2 距離蟀淮，L2 距離計算公式如下：

k 值的大小如何選擇

一般而言，k 值的大小對分類結(jié)果有著重大的影響钞澳。當(dāng)選擇的 k 值較小的情況下怠惶，就相當(dāng)于用較小的鄰域中的訓(xùn)練實例進行預(yù)測，只有當(dāng)與輸入實例較近的訓(xùn)練實例才會對預(yù)測結(jié)果起作用轧粟。但與此同時預(yù)測結(jié)果會對實例點非常敏感策治，分類器抗噪能力較差脓魏，因而容易產(chǎn)生過擬合，所以一般而言通惫，k 值的選擇不宜過小茂翔。但如果選擇較大的 k 值，就相當(dāng)于在用較大鄰域中的訓(xùn)練實例進行預(yù)測履腋，但相應(yīng)的分類誤差也會增大珊燎，模型整體變得簡單，會產(chǎn)生一定程度的欠擬合遵湖。所以一般而言悔政，我們需要采用交叉驗證的方式來選擇合適的 k 值。

交叉驗證的思路就是延旧，把樣本集中的大部分樣本作為訓(xùn)練集卓箫，剩余的小部分樣本用于預(yù)測，來驗證分類模型的準(zhǔn)確性垄潮。所以在 KNN 算法中，我們一般會把 K 值選取在較小的范圍內(nèi)闷盔，同時在驗證集上準(zhǔn)確率最高的那一個最終確定作為 K 值弯洗。

分類決策規(guī)則

k 個實例的多數(shù)屬于哪個類，明顯是多數(shù)表決的歸類規(guī)則逢勾。當(dāng)然還可能使用其他規(guī)則牡整，所以第三個關(guān)鍵就是分類決策規(guī)則。

回歸：k個實例該屬性值的平均值

KD樹

它是一個二叉樹的數(shù)據(jù)結(jié)構(gòu)溺拱，方便存儲 K 維空間的數(shù)據(jù)

KNN 的計算過程是大量計算樣本點之間的距離逃贝。為了減少計算距離次數(shù)，提升 KNN 的搜索效率迫摔，人們提出了 KD 樹（K-Dimensional 的縮寫）沐扳。KD 樹是對數(shù)據(jù)點在 K 維空間中劃分的一種數(shù)據(jù)結(jié)構(gòu)。在 KD 樹的構(gòu)造中句占，每個節(jié)點都是 k 維數(shù)值點的二叉樹沪摄。既然是二叉樹，就可以采用二叉樹的增刪改查操作纱烘，這樣就大大提升了搜索效率杨拐。

技巧

所有的特征應(yīng)該被放縮到相同的量級
為了免平票的出現(xiàn)，K應(yīng)該選擇奇數(shù)
投票的結(jié)果會被到近鄰樣本的距離歸一化擂啥，這樣更近的樣本的投票價值更大
嘗試各種不同的距離度量方法
k值小哄陶，低偏差，高方差
K值大哺壶，高偏差屋吨，低方差

sklearn

如果是做分類蜒谤，你需要引用：from sklearn.neihbors import KNeighborsClassifier
如果是回歸，需要引用：from sklearn.neighbors import KNeighborsRegressor

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None, **kwargs)

weights：預(yù)測中使用權(quán)重函數(shù)离赫。

uniform芭逝，代表所有鄰居的權(quán)重相同；distance渊胸，代表權(quán)重是距離的倒數(shù)旬盯，即與距離成反比；

algorithm：計算最近鄰居的算法

auto翎猛，根據(jù)數(shù)據(jù)的情況自動選擇適合的算法胖翰，默認情況選擇 auto；
kd_tree切厘，也叫作 KD 樹萨咳，是多維空間的數(shù)據(jù)結(jié)構(gòu)，方便對關(guān)鍵數(shù)據(jù)進行檢索疫稿，不過 KD 樹適用于維度少的情況培他，一般維數(shù)不超過 20，如果維數(shù)大于 20 之后遗座，效率反而會下降舀凛；
ball_tree，也叫作球樹途蒋，它和 KD 樹一樣都是多維空間的數(shù)據(jù)結(jié)果猛遍，不同于 KD 樹，球樹更適用于維度大的情況号坡；
brute懊烤，也叫作暴力搜索，它和 KD 樹不同的地方是在于采用的是線性掃描宽堆，而不是通過構(gòu)造樹結(jié)構(gòu)進行快速檢索腌紧。當(dāng)訓(xùn)練集大的時候，效率很低日麸。

leaf_size：構(gòu)造 KD 樹或球樹時的葉子數(shù)寄啼，默認是 30，調(diào)整 leaf_size 會影響到樹的構(gòu)造和搜索速度代箭。
p：Minkowski度量的Power參數(shù)
metric：樹使用的距離度量
n_jobsint：為鄰居搜索運行的并行作業(yè)數(shù)墩划。

from sklearn.neighbors import KNeighborsClassifier 
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from math import sqrt
from collections import Counter

iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.1, random_state=42)

kNN_classifier = KNeighborsClassifier(n_neighbors=3)
kNN_classifier.fit(X_train,y_train)
predict_y = kNN_classifier.predict(X_test)

print(predict_y,y_test)

numpy

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from math import sqrt
from collections import Counter

iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.1, random_state=42)

for x_t, y_t in zip(X_test, y_test):
    # 算出和X_train中每個點的距離
    distances = [sqrt(np.sum((x - x_t)**2)) for x in X_train] 
    # 對到每個點的距離從小到大排序，返回排序前的索引
    near_index = np.argsort(distances)
    # 選取前三個最靠近的點
    K = 3 
    # 根據(jù)索引得到值
    topK = [y_train[i] for i in near_index[:K]]
    # 投票
    votes = Counter(topK)
    predict_y = votes.most_common(1)[0][0]
    print(predict_y,y_t)

K-近鄰算法（K-NN）