一、KNN回顧

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

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

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

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

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

二、KNN三要素

1、K值的選擇

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

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

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

2、距離度量

一般使用歐幾里德距離

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

3、決策規(guī)則

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

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

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

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

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

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

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

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

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

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

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

1、平均值法

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

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

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

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

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

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

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

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

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

三、手寫 k 近鄰算法

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

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

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

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

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

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

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

歐氏距離公式：

例如求點(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)之間的距離：

檢測(cè)分類器效果：

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

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

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

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

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

樣本包括3種特征：

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

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

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

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

不喜歡的人

魅力一般的人

極具魅力的人

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

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

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

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

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

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

如下是0的一種表示：

100000000000001100000000000000000 200000000000011111100000000000000 300000000000111111111000000000000 400000000011111111111000000000000 500000001111111111111100000000000 600000000111111100011110000000000 700000001111110000001110000000000 800000001111110000001110000000000 90000001111110000000111000000000010000000111111000000011110000000001100000011111100000000011100000000120000001111110000000001110000000013000000111110000000000011100000001400000011111000000000001110000000150000000111110000000000011100000016000000011111000000000001110000001700000001111100000000000111000000180000001111100000000000011100000019000000111110000000000001110000002000000000111100000000000011100000210000000011110000000000011110000022000000001111000000000001111000002300000000111100000000001111100000240000000001111000000000011111000025000000000111110000000011111000002600000000011111000000011111100000270000000001111100000011111100000028000000000111111000111111110000002900000000000111111111111110000000300000000000011111111111110000000031000000000000111111111100000000003200000000000000111110000000000000

預(yù)測(cè)錯(cuò)誤的總數(shù)為：10

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

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

五、KD樹

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

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

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

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

2、KD樹(KD_Tree)

KD_Tree算法中，首先是對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行建模，構(gòu)建KD樹，然后再根據(jù)構(gòu)建好的模型來(lái)獲取鄰近樣本數(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來(lái)快速的計(jì)算。

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

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

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

1、計(jì)算每個(gè)特征的方差，取方差最大的作為根節(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來(lái)劃分，小于該值的放在左子樹，大于該值的放在右子樹

3、特征空間劃分：

（2）KD tree查找最近鄰

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

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

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

然后返回葉子節(jié)點(diǎn)的父節(jié)點(diǎn)，檢查另一個(gè)子節(jié)點(diǎn)包含的超矩形體是否和超球體相交，如果相交就到這個(gè)子節(jié)點(diǎn)尋找是否有更加近的近鄰，有點(diǎn)話就更新最近鄰；如果不相交那就直接返回父節(jié)點(diǎn)的父節(jié)點(diǎn)，在另一個(gè)子樹繼續(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算法對(duì)鳶尾花數(shù)據(jù)進(jìn)行分類，比較結(jié)果；

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

畫出下面兩張圖，需要將代碼整合起來(lái)，才能畫出來(lá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é)

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

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

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