人工智能算法與實(shí)踐-第6章 KNN算法

6.4算法案例26.1算法概述6.2算法原理6.3算法案例1目錄第六章K近鄰算法人工智能算法與實(shí)踐—1

—

6.5算法總結(jié)01算法概述PartONE—2

—

K近鄰算法K近鄰算法（k-NearestNeighbor）又稱KNN算法，是機(jī)器學(xué)習(xí)中的一個(gè)經(jīng)典的算法。K-近鄰算法原理如下：給定一個(gè)訓(xùn)練數(shù)據(jù)集，并且每個(gè)數(shù)據(jù)都存有一個(gè)標(biāo)簽。對(duì)于新輸入的實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最為鄰近的K個(gè)實(shí)例，這K個(gè)實(shí)例的多數(shù)存在哪個(gè)類中，就把新的輸入實(shí)例分類到這個(gè)類中。打個(gè)比方：假設(shè)你們想了解我是個(gè)怎樣的人，然后你發(fā)現(xiàn)我身邊關(guān)系最密切的朋友是一群學(xué)霸，那么你可以推測(cè)出我也是一個(gè)學(xué)霸。假設(shè)有兩類不同的樣本數(shù)據(jù)，分別用三角形和正方形表示，如圖所示。圖正中間的五角星表示的是待分類的數(shù)據(jù)。那么，如何給這個(gè)五角星分類呢？6.1算法概述—3

—

02算法原理PartTWO—4

—

做分類找鄰居算距離給定測(cè)試對(duì)象，計(jì)算它與訓(xùn)練集中的每個(gè)對(duì)象的距離。圈定距離最近的K個(gè)訓(xùn)練對(duì)象，作為測(cè)試對(duì)象的近鄰。根據(jù)這K個(gè)近鄰歸屬的主要類別，來對(duì)測(cè)試對(duì)象分類。6.2.1算法計(jì)算步驟—5

—

K折交叉驗(yàn)證的基本思路如下：（1）不重復(fù)地將原訓(xùn)練集隨機(jī)分為m份；（2）挑選其中1份作為驗(yàn)證集，剩余K-1份作為訓(xùn)練集用于模型訓(xùn)練，在訓(xùn)練集上訓(xùn)練后得到一個(gè)模型，用這個(gè)模型在驗(yàn)證集上測(cè)試，保存模型的評(píng)估指標(biāo)；（3）重復(fù)第二步K次（確保每個(gè)子集都有一次機(jī)會(huì)作為驗(yàn)證集）；（4）計(jì)算K組測(cè)試指標(biāo)的平均值作為模型精度的估計(jì)，并作為當(dāng)前K折交叉驗(yàn)證下模型的性能指標(biāo)。假設(shè)K=5時(shí)，其交叉驗(yàn)證方法如左圖所示。KNN中的K值選取對(duì)分類的結(jié)果影響至關(guān)重要。如果K值選取的太小，即選用較小的鄰域中的樣本進(jìn)行預(yù)測(cè)，容易受到異常點(diǎn)的影響，波動(dòng)較大，模型整體會(huì)很復(fù)雜，容易發(fā)生過擬合。6.2.2K值的選取—6

—

010203歐氏距離曼哈頓距離明考斯基距離6.2.3確定距離函數(shù)—7

—

03算法案例PartTHREE約會(huì)網(wǎng)站配對(duì)數(shù)據(jù)—8

—

6.3.1讀取數(shù)據(jù)集—9

—

數(shù)據(jù)集介紹：海倫女士一直使用在線約會(huì)網(wǎng)站尋找適合自己的約會(huì)對(duì)象。盡管約會(huì)網(wǎng)站會(huì)推薦不同的人選，但她并不是喜歡每一個(gè)人。經(jīng)過一番總結(jié)，她發(fā)現(xiàn)自己交往過的人可以進(jìn)行如下分類：不喜歡，即didntlike；魅力一般，即smallDoes；極具魅力，即largeDoes。代碼輸出結(jié)果如下：根據(jù)數(shù)據(jù)集的第一列和第三列數(shù)據(jù)創(chuàng)建散點(diǎn)圖，橫軸表示特征值“每年出行的里程數(shù)”，縱軸表示特征值“每周吃冰淇淋的公升數(shù)”根據(jù)數(shù)據(jù)集的第一列和第二列數(shù)據(jù)創(chuàng)建散點(diǎn)圖，橫軸表示特征值“每年出行的里程數(shù)”，縱軸表示特征值“玩游戲的時(shí)間占比”根據(jù)數(shù)據(jù)集的第二列和第三列數(shù)據(jù)創(chuàng)建散點(diǎn)圖，橫軸表示特征值“玩游戲的時(shí)間占比”，縱軸表示特征值“每周吃冰淇淋的公升數(shù)”6.3.2創(chuàng)建散點(diǎn)圖分類數(shù)據(jù)—10

—

6.3.3數(shù)據(jù)歸一化處理—11

—

提取了四組樣本數(shù)據(jù)，計(jì)算樣本1和樣本2之間的距離，這里我們選用歐氏距離，因此樣本1與樣本2之間的距離計(jì)算方法如下：每年出行里程數(shù)對(duì)于計(jì)算結(jié)果的影響遠(yuǎn)遠(yuǎn)大于表中其他兩個(gè)特征。在處理這種數(shù)字差值范圍大的特征值時(shí)，我們通常采用歸一化的方法將取值范圍處理為0到1或者?1到1之間，利用下面公式，可以實(shí)現(xiàn)將特征值轉(zhuǎn)化為[0,1]區(qū)間內(nèi)的值：輸出結(jié)果如下所示6.3.4測(cè)試KNN分類器模型—12

—

左邊為KNN模型的代碼實(shí)現(xiàn)，這里將訓(xùn)練集和測(cè)試集按照7：3劃分。設(shè)置k=4，遍歷測(cè)試集的每一行，knn()函數(shù)會(huì)返回該行數(shù)據(jù)的分類標(biāo)簽結(jié)果，與實(shí)際分類標(biāo)簽結(jié)果進(jìn)行比較，若不一致，則error加1，最后計(jì)算整個(gè)測(cè)試集的錯(cuò)誤率。

輸出結(jié)果如下所示：由此看出，KNN處理約會(huì)數(shù)據(jù)集的錯(cuò)誤率最終為4.3%，效果還不錯(cuò)。6.3.5模型預(yù)測(cè)—13

—

輸出結(jié)果如下所示：classifyPerson()函數(shù)的作用是輸入一名用戶的玩游戲時(shí)間比，一年飛行里程，消費(fèi)冰淇淋數(shù)預(yù)測(cè)海倫與改名用戶的匹配程度。04算法案例PartFOUR預(yù)測(cè)簽到位置—14

—

預(yù)測(cè)簽到位置Facebook創(chuàng)建了一個(gè)虛擬世界，其中包括10公里*10公里共100平方公里的約10萬個(gè)地方。對(duì)于給定的坐標(biāo)集，您的任務(wù)將根據(jù)用戶的位置、準(zhǔn)確性和時(shí)間戳等預(yù)測(cè)用戶下一次的簽到位置，從而使商家在用戶簽到次數(shù)多的地方更精準(zhǔn)的投放廣告，如上圖所示。6.4.1項(xiàng)目介紹—15

—

簽到事件的id用戶簽到位置定位準(zhǔn)確度時(shí)間戳業(yè)務(wù)id，預(yù)測(cè)的目標(biāo)值12345數(shù)據(jù)集介紹6.4.2數(shù)據(jù)集介紹—16

—

row_id

xyaccuarcy

time

place_id

6.4.3算法流程分析—17

—

首先獲取數(shù)據(jù)，然后對(duì)數(shù)據(jù)進(jìn)行處理，主要是處理時(shí)間特征，將時(shí)間戳成立成比較有意義的時(shí)間，還需過濾掉年和月以及簽到次數(shù)少的地點(diǎn)。數(shù)據(jù)處理完后篩選特征值和目標(biāo)值，接著進(jìn)行數(shù)據(jù)集劃分，使用特征工程進(jìn)行標(biāo)準(zhǔn)化，接著使用KNN算法預(yù)估器進(jìn)行模型訓(xùn)練，同時(shí)加入網(wǎng)格搜索與交叉驗(yàn)證，最后進(jìn)行模型評(píng)估。6.4.4代碼實(shí)現(xiàn)—18

—

實(shí)驗(yàn)代碼運(yùn)行后，實(shí)驗(yàn)結(jié)果如下：05算法總結(jié)PartFIVE—19

—

算法總結(jié)優(yōu)點(diǎn)缺點(diǎn)1優(yōu)點(diǎn)1）算法簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)。2）不需要顯示的訓(xùn)練過程，模型就是訓(xùn)練數(shù)據(jù)集本身。3）特別適用于多分類問題。2缺點(diǎn)1）它是一種懶惰算法，對(duì)測(cè)試樣本分類時(shí)的計(jì)算量大，內(nèi)存開銷大，評(píng)分