k近鄰理論與實(shí)踐

保留初心，砥礪前行

k-nearest neighbor, k-NN是一種可以用于多分類和回歸的方法。knn是一個(gè)很簡單的分類方法。

k近鄰法的輸入是實(shí)例的特征向量，也就是特征空間中的點(diǎn)；
k近鄰法的輸出是實(shí)例的類別，可以是多個(gè)類。

接下來本文將從：

  • k近鄰算法
  • k近鄰法的模型
  • kd樹

三個(gè)方面進(jìn)行闡述。

1. k近鄰算法

本文的第一句話，就已經(jīng)非常明確地告訴了你，k-NN是用來做什么的。機(jī)器學(xué)習(xí)無非就是做這幾件事而已，k-NN一下子就可以分類和回歸，是不是很牛。

然后介紹了它的輸入輸出，這個(gè)時(shí)候你可能就一頭霧水了——等等，我連它是什么都不清楚，怎么就輸入輸出了呢。別急，接下來我就開始介紹k近鄰算法。

k近鄰算法簡單、直觀：給定一個(gè)訓(xùn)練數(shù)據(jù)集（其中的實(shí)例類別已定），對新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最接近的k個(gè)實(shí)例，這k個(gè)實(shí)例的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例分為這個(gè)類。

通過以上的話已經(jīng)足夠理解k近鄰，如果說的再具象一些：

  1. 我們需要輸入一個(gè)這樣的數(shù)據(jù)集
    T = {(x1,y1),(x2,y2),(x3,y3),···,(xN,yN)}
    其中xi是實(shí)例的特征向量，yi是xi這個(gè)實(shí)例對應(yīng)的類別，有可能是c1，c2，c3，··· ， cK。
    然后我們要再輸入一個(gè)需要被分類的實(shí)例的特征向量x。

  2. 根據(jù)給定的某種距離度量，在 T 中找到與x最接近的k個(gè)點(diǎn)。

  3. 在k個(gè)點(diǎn)中根據(jù)某種分類的決策規(guī)則（例如，哪個(gè)類別多就是哪個(gè)類別）決定x的類別y。

  4. 輸出x的類別y。

從以上的敘述可以看出， k近鄰是沒有顯式的學(xué)習(xí)過程的。

當(dāng) k近鄰的k = 1時(shí)，成為最近鄰算法。顧名思義，相信聰明的你肯定知道是什么意思了。

2. k近鄰法的模型

在前邊的介紹中的第2個(gè)步驟中，可以看到“某種距離度量”；第3步中有“某種決策規(guī)則”；還有k近鄰的k究竟是多少。
以上這些都是在了解了 k近鄰算法后我們會產(chǎn)生的問題。

沒錯(cuò)，這三個(gè)問題就是k近鄰法的3個(gè)基本要素。
下面，我們就從這3個(gè)基本要素，探究k近鄰法的模型。

2.1. 距離度量

根據(jù)k近鄰法的思路，我們輸入的x與數(shù)據(jù)集中的某個(gè)xi的相似程度，需要通過兩個(gè)點(diǎn)的距離來反應(yīng)。

一般使用的是歐氏距離，推廣到更一般的情況是Lp距離。

Lp距離的定義是：

Lp(xi,xj) = (∑l=1n|xi(l) - xj(l)|p)1/p

其中xi,xj為特征空間中的兩個(gè)點(diǎn)。上式就代表了xi和xj間的Lp距離。

當(dāng)p = 2時(shí)Lp距離就稱為歐氏距離。
歐氏距離簡單說就是兩點(diǎn)的每一個(gè)維度的元素分別做差，再求平方和，最后開根號，是不是很容易。

2.2. k值的選擇

算法名叫 k近鄰，因此顯而易見k值對于該算法的重要性。

先說結(jié)論： K值一般取一個(gè)較小的值，通常采用交叉驗(yàn)證法來選取最優(yōu)的k值。

K值的選擇會對k近鄰法的結(jié)果產(chǎn)生較大的影響。

  • 當(dāng)k較小時(shí)：
    優(yōu)點(diǎn)：學(xué)習(xí)的近似誤差會減小。
    缺點(diǎn)：預(yù)測結(jié)果會對近鄰的實(shí)例點(diǎn)非常敏感（我個(gè)人的理解是：例如，如果k = 2， 鄰近的2個(gè)點(diǎn)恰好的不同類的情況下， 預(yù)測結(jié)果就會出錯(cuò)），k值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合。

  • 當(dāng)k較大時(shí)：
    優(yōu)點(diǎn)：減小學(xué)習(xí)的估計(jì)誤差。
    缺點(diǎn)：學(xué)習(xí)的近似誤差會增大，k值的增大意味著整體的模型變得簡單，過于簡單會完全忽略訓(xùn)練實(shí)例中的大量有用信息。


從上圖可以看出，k = 3 與 k = 5 時(shí)的分類結(jié)果是不同的。然而k值并不會在學(xué)習(xí)過程中自動優(yōu)化，而是在模型初始化是人為約定好的。因此k值對于k近鄰至關(guān)重要，需要給予更多的關(guān)注。

2.3. 分類決策規(guī)則

一般是多數(shù)表決，就是說k個(gè)實(shí)例中哪個(gè)類別多，輸入的x就是哪一類。

3. kd樹

重頭戲來了，在實(shí)現(xiàn) k近鄰時(shí)，需要計(jì)算輸入x與數(shù)據(jù)集中的每一個(gè)xi的距離，從而選擇距離最小的k個(gè)。當(dāng)訓(xùn)練集很大或維數(shù)很大時(shí)，計(jì)算會非常耗時(shí)。
因此為了提高 k近鄰的效率，下面介紹kd樹方法來存儲訓(xùn)練數(shù)據(jù)，減少計(jì)算次數(shù)。

kd樹是對k維空間中的實(shí)例點(diǎn)進(jìn)行存儲以便對其快速檢索的二叉樹數(shù)據(jù)結(jié)構(gòu)，表示對k維空間的一種劃分。

對構(gòu)造kd樹的語言描述晦澀難懂，因此直接上算法，再加上一個(gè)低維空間的例子，就可以搞懂它到底是怎么回事。

（以下算法描述只為了清晰易懂，并不是嚴(yán)禁的說法）

  • 構(gòu)造算法：
    輸入：k維空間數(shù)據(jù)集T = {x1, x2, ..., xN},
    其中xi = (xi(1), xi(2), ..., xi(k)), i = 1, 2, 3, ..., N
    輸出： kd樹
  1. 將所有實(shí)例點(diǎn)視作根節(jié)點(diǎn)。也就是說現(xiàn)在的根節(jié)點(diǎn)（為了敘述方便，起個(gè)別名叫做節(jié)點(diǎn)A）包含了整個(gè)k維空間。
  2. 選擇一條坐標(biāo)軸x(1)，l = j mod k + 1，其中j為節(jié)點(diǎn)的深度，k為空間的維度。
    將節(jié)點(diǎn)A中的所有的點(diǎn)的 x(1)軸的中位數(shù)找出來，給它起個(gè)名字叫做切分點(diǎn)（選擇中位數(shù)作為切分點(diǎn)叫做平衡kd樹）。并且通過切分點(diǎn)畫一個(gè)與x(1)軸垂直的超平面，將節(jié)點(diǎn)A所表示的那個(gè)k維空間1分為2。
  3. 把那些被劃分到兩個(gè)子空間的實(shí)例點(diǎn)放在2個(gè)子節(jié)點(diǎn)（節(jié)點(diǎn)B和節(jié)點(diǎn)C）上（坐標(biāo)x(1)小于切分點(diǎn)的點(diǎn)放在左子節(jié)點(diǎn)，大于的放在右子節(jié)點(diǎn)），那些恰巧落在切分超平面上的點(diǎn)，還保留在節(jié)點(diǎn)A中。
  4. 上述的2和3步驟，也就是選擇坐標(biāo)軸，選擇切分點(diǎn)，劃分超平面的動作循環(huán)執(zhí)行下去... ...
    直到，某次劃分的兩個(gè)子區(qū)域沒有實(shí)例點(diǎn)存在，就停止算法。至此，kd樹形成。
  • 例題：
    這個(gè)例題從低維出發(fā)，便于讀者想象思考，高維同理。
    使用如下2維空間數(shù)據(jù)集：
    T = {(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)}
    和上述算法構(gòu)造一個(gè)平衡kd樹。

對應(yīng)上述算法的第1步


圖-1 對應(yīng)上述算法的第1步

將根節(jié)點(diǎn)1分為2，恰好落在超平面上的點(diǎn)保留在根節(jié)點(diǎn)，剩下的點(diǎn)按照劃分進(jìn)入左右子節(jié)點(diǎn)


圖-2 將根節(jié)點(diǎn)1分為2，恰好落在超平面上的點(diǎn)保留在根節(jié)點(diǎn)，剩下的點(diǎn)按照劃分進(jìn)入左右子節(jié)點(diǎn)

繼續(xù)上圖的劃分，在左右兩個(gè)子節(jié)點(diǎn)的基礎(chǔ)上繼續(xù)劃分，落在超平面上的點(diǎn)留下，分到兩邊的點(diǎn)進(jìn)入下一層的左右子節(jié)點(diǎn)


圖-3 繼續(xù)上圖的劃分，在左右兩個(gè)子節(jié)點(diǎn)的基礎(chǔ)上繼續(xù)劃分，落在超平面上的點(diǎn)留下，分到兩邊的點(diǎn)進(jìn)入下一層的左右子節(jié)點(diǎn)

最后一次劃分，左右子節(jié)點(diǎn)已經(jīng)沒有實(shí)例點(diǎn)的存在了，算法結(jié)束


圖-4 最后一次劃分，左右子節(jié)點(diǎn)已經(jīng)沒有實(shí)例點(diǎn)的存在了，算法結(jié)束
圖-5 kd樹
  • 搜索算法
    輸入：經(jīng)過上邊的構(gòu)造算法構(gòu)造出來的kd樹，目標(biāo)點(diǎn)x
    輸出：x的最近鄰點(diǎn)
圖-6 圖解搜索算法

上圖是構(gòu)造kd樹算法的輸出結(jié)果，紅點(diǎn)代表目標(biāo)點(diǎn)x。也就是說我們要尋找紅色目標(biāo)點(diǎn)的最近鄰。
首先在kd樹中找到紅色園點(diǎn)所在的子節(jié)點(diǎn)，也就是（4,7）那個(gè)點(diǎn)所在的葉子節(jié)點(diǎn)。
因此把（4,7）作為最鄰近。并且以紅色目標(biāo)點(diǎn)為圓心，經(jīng)過（4,7）畫圓。從圖中可以看出的是，真正的最近鄰一定在這個(gè)圓的內(nèi)部。
你可能會說，從這個(gè)圖一下不就看出來內(nèi)部有一個(gè)點(diǎn)嗎。等等等等，這是你從上帝視角看的圖，而真實(shí)的數(shù)據(jù)結(jié)構(gòu)是一棵二叉樹，并不是這張圖，因此從樹上是無法做出這種判斷的。
接下來我們就要尋找比（4,7）距離紅點(diǎn)更近的點(diǎn)。
根據(jù)kd樹找到（4,7）父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)，如果這個(gè)子節(jié)點(diǎn)的區(qū)域與圓不相交，這個(gè)子節(jié)點(diǎn)的區(qū)域就不會存在最近鄰點(diǎn)，這種情況下就退回（4,7）父節(jié)點(diǎn)的父節(jié)點(diǎn)，繼續(xù)以上的步驟。而從圖-5可以看出（4,7）的兄弟節(jié)點(diǎn)是（2,3），就在圓內(nèi)，因此最近鄰節(jié)點(diǎn)由（4,7）變成（2,3）。因此就可以得到紅色圓點(diǎn)的最近鄰為（2,3）。
這是低維，少量數(shù)據(jù)的情況，只是為了清楚地解釋搜索算法?？梢酝茝V到高維大量數(shù)據(jù)的情況，實(shí)相同的道理。

OK，理論結(jié)束，開始實(shí)踐。
經(jīng)過上述的講解，我們已經(jīng)知道，k近鄰算法是沒有顯示的學(xué)習(xí)過程的，整個(gè)分類過程就是構(gòu)建kd樹和搜索kd樹的過程。

k近鄰實(shí)驗(yàn)，我們使用sklearn中內(nèi)置的Iris數(shù)據(jù)集。它由150個(gè)實(shí)例組成，平均分為3個(gè)種類，每個(gè)種類50個(gè)實(shí)例。每個(gè)實(shí)例分別有4個(gè)屬性描述。
下面從sklearn中導(dǎo)入Iris數(shù)據(jù)集的下載器，使用下載器下載數(shù)據(jù)存入變量iris中。


from sklearn.datasets import load_iris

iris = load_iris()

print iris.data.shape

(150, 4)

print iris.data   #打印數(shù)據(jù)集中的數(shù)據(jù)
print iris.target  #打印實(shí)例對應(yīng)的類別

[[ 5.1  3.5  1.4  0.2]
 [ 4.9  3.   1.4  0.2]
 [ 4.7  3.2  1.3  0.2]
 [ 4.6  3.1  1.5  0.2]
... ...
... ...
篇幅原因，中間省略
一共150個(gè)實(shí)例
... ...
... ...
 [ 6.8  3.2  5.9  2.3]
 [ 6.7  3.3  5.7  2.5]
 [ 6.7  3.   5.2  2.3]
 [ 6.3  2.5  5.   1.9]
 [ 6.5  3.   5.2  2. ]
 [ 6.2  3.4  5.4  2.3]
 [ 5.9  3.   5.1  1.8]]
[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]

接下來對數(shù)據(jù)集進(jìn)行分割，需要強(qiáng)調(diào)的一點(diǎn)是，無論什么數(shù)據(jù)集，在分割訓(xùn)練集和測試集的時(shí)候一定要做到隨機(jī)采樣，避免相同特征的數(shù)據(jù)聚在一起的情況。

from sklearn.cross_validation import train_test_split

X_train, X_test, Y_train, Y_test = train_test_split(iris.data, iris.target, test_size=0.25, random_state=33)

print 'X_train: ', X_train
print 'X_test: ', X_test
print 'Y_train: ', Y_train
print 'Y_test: ', Y_test

X_train:  [[ 5.   2.3  3.3  1. ]
 [ 4.9  3.1  1.5  0.1]
 [ 6.3  2.3  4.4  1.3]
 [ 5.8  2.6  4.   1.2]
... ...
... ...
... ...
 [ 5.6  3.   4.5  1.5]
 [ 7.7  3.   6.1  2.3]
 [ 5.4  3.4  1.7  0.2]]
X_test:  [[ 5.7  2.9  4.2  1.3]
 [ 6.7  3.1  4.4  1.4]
 [ 4.7  3.2  1.6  0.2]
 [ 6.5  2.8  4.6  1.5]
... ...
 [ 5.8  2.7  5.1  1.9]
 [ 5.7  3.   4.2  1.2]]
Y_train:  [1 0 1 1 1 0 0 1 0 2 0 0 1 2 0 1 2 2 1 1 0 0 2 0 0 2 1 1 2 2 2 2 0 0 1 1 0
 1 2 1 2 0 2 0 1 0 2 1 0 2 2 0 0 2 0 0 0 2 2 0 1 0 1 0 1 1 1 1 1 0 1 0 1 2
 0 0 0 0 2 2 0 1 1 2 1 0 0 1 1 1 0 1 1 0 2 2 2 1 2 0 1 0 0 0 2 1 2 1 2 1 2
 0]
Y_test:  [1 1 0 1 2 2 0 0 2 2 2 0 2 1 2 1 2 0 1 2 0 0 2 0 2 2 1 1 2 2 1 1 2 2 2 2 2
 1]

最后就是使用sklearn的k近鄰分類器，對測試集進(jìn)行分類測試：
KNeighborsClassifier函數(shù)默認(rèn)k為5，經(jīng)過測試，對于這個(gè)數(shù)據(jù)集，當(dāng)k=7時(shí)效果最好。

# 導(dǎo)入數(shù)據(jù)標(biāo)準(zhǔn)化模塊
from sklearn.preprocessing import StandardScaler
# 導(dǎo)入k近鄰分類器
from sklearn.neighbors import KNeighborsClassifier
# 標(biāo)準(zhǔn)化訓(xùn)練集
ss = StandardScaler()
X_train = ss.fit_transform(X_train)
# 標(biāo)準(zhǔn)化測試集
X_test = ss.fit_transform(X_test)
# 將knn分類器賦給變量knn，并且參數(shù)中選擇上文中講的kd樹
knn = KNeighborsClassifier(algorithm='kd_tree')
#knn = KNeighborsClassifier(n_neighbors=7, algorithm='kd_tree')
# Fit the model using X as training data and y as target values
knn.fit(X_train, Y_train)
# 輸入測試集進(jìn)行預(yù)測
y_predict = knn.predict(X_test)

print Y_test
print y_predict

第一行打印的是正確的結(jié)果
第二行打印的是knn模型預(yù)測的結(jié)果

[1 1 0 1 2 2 0 0 2 2 2 0 2 1 2 1 2 0 1 2 0 0 2 0 2 2 1 1 2 2 1 1 2 2 2 2 2 1]
[1 1 0 1 1 2 0 0 1 2 2 0 2 1 2 1 1 0 1 1 0 0 2 0 1 1 1 1 1 1 1 1 1 1 2 2 1 1]

錯(cuò)誤率：e = 1/m ∑i=1mI(f(xi)≠yi)
由以上結(jié)果可以算出e = 10 / 36
模型精度1 - e

如果你也喜歡機(jī)器學(xué)習(xí)，并且也像我一樣在ML之路上努力，請關(guān)注我，我會進(jìn)行不定期更新，總有一些可以幫到你。

所有圖片均來自網(wǎng)絡(luò)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容