人工智能算法與實踐-第6章 KNN算法

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

—

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

—

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

—

02算法原理PartTWO—4

—

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

—

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

—

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

—

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

—

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

—

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

—

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

—

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

—

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

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

—

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

—

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

—

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

—

row_id

xyaccuarcy

time

place_id

6.4.3算法流程分析—17

—

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

—

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

—

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