一、KNN回顧

k 近鄰學(xué)習(xí)是一種常用的監(jiān)督學(xué)習(xí)方法，比如：判斷一個人的人品，只需要觀察與他來往最密切的幾個人的人品好壞就可以得出，即“近朱者赤，近墨者黑”。

理論/原理：“物以類聚，人以群分”

相同/近似樣本在樣本空間中是比較接近的，所以可以使用和當(dāng)前樣本比較近的其他樣本的目標(biāo)屬性值作為當(dāng)前樣本的預(yù)測值。

k 近鄰法的工作機(jī)制很簡單：

給定測試樣本，基于某種距離度量（一般使用歐幾里德距離）找出訓(xùn)練集中與其最靠近的k個訓(xùn)練樣本，然后基于這k個“鄰居”的信息來進(jìn)行預(yù)測。

二、KNN三要素

1、K值的選擇

對于K值的選擇，一般根據(jù)樣本分布選擇一個較小的值，然后通過交叉驗(yàn)證來選擇一個比較合適的最終值；

當(dāng)選擇比較小的K值的時(shí)候，表示使用較小領(lǐng)域中的樣本進(jìn)行預(yù)測，訓(xùn)練誤差會減小，但是會導(dǎo)致模型變得復(fù)雜，容易導(dǎo)致過擬合；

當(dāng)選擇較大的K值的時(shí)候，表示使用較大領(lǐng)域中的樣本進(jìn)行預(yù)測，訓(xùn)練誤差會增大，同時(shí)會使模型變得簡單，容易導(dǎo)致欠擬合；

2、距離度量

一般使用歐幾里德距離

關(guān)于距離度量，還有其他方式

3、決策規(guī)則

KNN在做回歸和分類的主要區(qū)別在于最后做預(yù)測時(shí)的決策方式不同：

（1）分類預(yù)測規(guī)則：一般采用多數(shù)表決法或者加權(quán)多數(shù)表決法

假設(shè)圖中 “？”表示待預(yù)測樣本，紅色圓表示一類，藍(lán)色方塊表示一類，2和3表示到待預(yù)測樣本的距離

1. 多數(shù)表決法：

每個鄰近樣本的權(quán)重是一樣的，也就是說最終預(yù)測的結(jié)果為出現(xiàn)類別最多的那個類；

如圖，待預(yù)測樣本被預(yù)測為紅色圓

2. 加權(quán)多數(shù)表決法：

每個鄰近樣本的權(quán)重是不一樣的，一般情況下采用權(quán)重和距離成反比的方式來計(jì)算，也就是說最終預(yù)測結(jié)果是出現(xiàn)權(quán)重最大的那個類別；

如圖，紅色圓到待預(yù)測樣本的距離為3，藍(lán)色方塊到待預(yù)測樣本的距離為2，權(quán)重與距離成反比，所以藍(lán)色的權(quán)重比較大，待預(yù)測樣本被預(yù)測為藍(lán)色方塊。

（2）回歸預(yù)測規(guī)則：一般采用平均值法或者加權(quán)平均值法

假設(shè)上圖中的2和3表示鄰近樣本的目標(biāo)屬性值（標(biāo)簽值），此時(shí)沒有類別，只有屬性值

1、平均值法

每個鄰近樣本的權(quán)重是一樣的，也就是說最終預(yù)測的結(jié)果為所有鄰近樣本的目標(biāo)屬性值的均值；

如圖，均值為(3+3+3+2+2)/5=2.6

2、加權(quán)平均值法

圖中，雙箭頭線上的數(shù)表示到待預(yù)測樣本的距離

每個鄰近樣本的權(quán)重是不一樣的，一般情況下采用權(quán)重和距離成反比的方式來計(jì)算，也就是說在計(jì)算均值的時(shí)候進(jìn)行加權(quán)操作；

如圖，權(quán)重分別為（各自距離反比占距離反比總和的比例）:

屬性值為3的權(quán)重：

屬性值為2的權(quán)重：

待預(yù)測樣本的加權(quán)平均值為：

三、手寫 k 近鄰算法

實(shí)現(xiàn)kNN分類算法的偽代碼：

對未知類別屬性的數(shù)據(jù)集中的每個點(diǎn)依次執(zhí)行一下操作：

（1）計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離

（2）按照距離遞增次序排序

（3）選取與當(dāng)前點(diǎn)距離最小的k個點(diǎn)

（4）確定前k個點(diǎn)所在類別的出現(xiàn)頻數(shù)

（5）返回當(dāng)前k個點(diǎn)出現(xiàn)頻數(shù)最高的類別作為當(dāng)前點(diǎn)的預(yù)測分類

歐氏距離公式：

例如求點(diǎn)(1,0,0,1) (1,0,0,1)(1,0,0,1)和(7,6,9,4) (7,6,9,4)(7,6,9,4)之間的距離：

檢測分類器效果：

可以使用已知類別的數(shù)據(jù)（當(dāng)然不告訴分類器），檢驗(yàn)分類器給出的結(jié)果是否與已知類別相同，通過大量的測試數(shù)據(jù)，我們可以計(jì)算出分類器的錯誤率。

以上算法的實(shí)現(xiàn)是用于分類的，決策規(guī)則使用了多數(shù)表決法；此算法通過改變決策規(guī)則，同樣可以用于回歸。

源代碼可見：https://github.com/Daycym/Machine_Learning/tree/master/03_KNN；01_k近鄰算法.py

四、使用手寫k kk 近鄰算法的案例

1、案例1：約會網(wǎng)站的配對效果

樣本包括3種特征：

每年獲得的飛行常客里程數(shù)

玩視頻游戲所耗時(shí)間百分比

每周消費(fèi)的冰淇淋公升數(shù)

樣本包括3種標(biāo)簽：

不喜歡的人

魅力一般的人

極具魅力的人

部分?jǐn)?shù)據(jù)格式為：

代碼可見：02_約會網(wǎng)站的配對效果.py

2、案例2：手寫數(shù)字識別系統(tǒng)

數(shù)據(jù)集包括訓(xùn)練集和測試集

數(shù)據(jù)是32*32的二進(jìn)制文本文件

需要將文本數(shù)據(jù)轉(zhuǎn)換為Numpy數(shù)組

如下是0的一種表示：

100000000000001100000000000000000 200000000000011111100000000000000 300000000000111111111000000000000 400000000011111111111000000000000 500000001111111111111100000000000 600000000111111100011110000000000 700000001111110000001110000000000 800000001111110000001110000000000 90000001111110000000111000000000010000000111111000000011110000000001100000011111100000000011100000000120000001111110000000001110000000013000000111110000000000011100000001400000011111000000000001110000000150000000111110000000000011100000016000000011111000000000001110000001700000001111100000000000111000000180000001111100000000000011100000019000000111110000000000001110000002000000000111100000000000011100000210000000011110000000000011110000022000000001111000000000001111000002300000000111100000000001111100000240000000001111000000000011111000025000000000111110000000011111000002600000000011111000000011111100000270000000001111100000011111100000028000000000111111000111111110000002900000000000111111111111110000000300000000000011111111111110000000031000000000000111111111100000000003200000000000000111110000000000000

預(yù)測錯誤的總數(shù)為：10

手寫數(shù)字識別系統(tǒng)的錯誤率為：0.010571

代碼可見：03_手寫數(shù)字識別系統(tǒng).py

五、KD樹

KNN算法的重點(diǎn)在于找出K個最鄰近的點(diǎn)，主要方法如下：

1、蠻力實(shí)現(xiàn)(brute)

計(jì)算出待預(yù)測樣本到所有訓(xùn)練樣本的訓(xùn)練數(shù)據(jù)，然后選擇最小的K個距離即可得到K個最鄰近點(diǎn)；

當(dāng)特征數(shù)比較多，樣本數(shù)比較多的時(shí)候，算法的執(zhí)行效率比較低。

2、KD樹(KD_Tree)

KD_Tree算法中，首先是對訓(xùn)練數(shù)據(jù)進(jìn)行建模，構(gòu)建KD樹，然后再根據(jù)構(gòu)建好的模型來獲取鄰近樣本數(shù)據(jù)

KD_Tree是KNN算法中用于計(jì)算最近鄰的快速、便捷構(gòu)建方式

除此之外，還有一些從KD_Tree修改后的求解最鄰近點(diǎn)的算法，比如：Ball Tree、BBF Tree、MVP Tree等

當(dāng)樣本數(shù)據(jù)量少的時(shí)候，我們可以使用brute這種暴力的方式進(jìn)行求解最近鄰，即計(jì)算到所有樣本的距離。

當(dāng)樣本量比較大的時(shí)候，直接計(jì)算所有樣本的距離，工作量有點(diǎn)大，所以在這種情況下，我們可以使用kd tree來快速的計(jì)算。

（1）KD數(shù)的構(gòu)建

KD樹采用從m個樣本的n維特征中，分別計(jì)算n個特征取值的方差，用方差最大的第 k 維特征作為根節(jié)點(diǎn)。對于這個特征，選擇取值的中位數(shù)作為樣本的劃分點(diǎn)，對于小于該值的樣本劃分到左子樹，對于大于等于該值的樣本劃分到右子樹，對左右子樹采用同樣的方式找方差最大的特征作為根節(jié)點(diǎn)，遞歸即可產(chǎn)生KD樹。

假設(shè)二維樣本為：{(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)}，下面我們來構(gòu)建KD樹：

1、計(jì)算每個特征的方差，取方差最大的作為根節(jié)點(diǎn)

方差表示數(shù)據(jù)的離散程度，離散程度越大，值越大。因此，選擇第1維特征x1作為根節(jié)點(diǎn)。

2、選取中位數(shù)作為劃分點(diǎn)

x1取值為2,4,5,7,8,9 2,4,5,7,8,92,4,5,7,8,9中位數(shù)取7來劃分，小于該值的放在左子樹，大于該值的放在右子樹

3、特征空間劃分：

（2）KD tree查找最近鄰

當(dāng)我們生成KD樹以后，就可以取預(yù)測測試集里面的樣本目標(biāo)點(diǎn)了。

對于一個目標(biāo)點(diǎn)，我們首先在KD樹里面尋找包含目標(biāo)點(diǎn)的葉子節(jié)點(diǎn)；

以目標(biāo)點(diǎn)為圓心，以目標(biāo)點(diǎn)到葉子節(jié)點(diǎn)樣本實(shí)例的距離為半徑，得到一個超球體，最近鄰的點(diǎn)一定在這個超球體內(nèi)部；

然后返回葉子節(jié)點(diǎn)的父節(jié)點(diǎn)，檢查另一個子節(jié)點(diǎn)包含的超矩形體是否和超球體相交，如果相交就到這個子節(jié)點(diǎn)尋找是否有更加近的近鄰，有點(diǎn)話就更新最近鄰；如果不相交那就直接返回父節(jié)點(diǎn)的父節(jié)點(diǎn)，在另一個子樹繼續(xù)搜索最近鄰；

當(dāng)回溯到根節(jié)點(diǎn)時(shí)，算法就結(jié)束了，保存最近鄰節(jié)點(diǎn)就是最終的最近鄰。

假設(shè)要尋找點(diǎn)(2,2.5) (2,2.5)(2,2.5)的最近鄰點(diǎn)：

六、KNN案例

1、鳶尾花數(shù)據(jù)分類

使用Logistic算法和KNN算法對鳶尾花數(shù)據(jù)進(jìn)行分類，比較結(jié)果；

具體內(nèi)容在代碼的注釋中有介紹；

畫出下面兩張圖，需要將代碼整合起來，才能畫出來。

代碼可見：https://github.com/Daycym/Machine_Learning；02_Logistic回歸下05_鳶尾花數(shù)據(jù)分類.py，以及03_KNN目錄下04_鳶尾花數(shù)據(jù)分類.py。

2、信貸審批

具體內(nèi)容將在代碼中介紹

代碼可見：https://github.com/Daycym/Machine_Learning；02_Logistic回歸下03_信貸審批.py，以及03_KNN目錄下05_信貸審批.py。

七、總結(jié)

本篇主要通過簡單的暴力求解的方式實(shí)現(xiàn)KNN算法，有助于理解KNN算法

后面又介紹了KD樹找K個最近鄰，此算法是最快捷的

最后通過sklearn庫下的KNeighborsClassifier實(shí)現(xiàn)了兩個案例，來屬性KNN模型的構(gòu)建