總第77篇

本篇介紹機器學習眾多算法里面最基礎也是最“懶惰”的算法——KNN（k-nearest neighbor）。你知道為什么是最懶的嗎？

01|算法簡介：

KNN是英文k-nearest neighbor的縮寫，表示K個最接近的點。該算法常用來解決分類問題，具體的算法原理就是先找到與待分類值A距離最近的K個值，然后判斷這K個值中大部分都屬于哪一類，那么待分類值A就屬于哪一類。

這其實和我們生活中對人的評價方式一致，你想知道一個人是什么樣的人，你只需要找到跟他關系最近（好）的K個人，然后看這K個人都是什么人，就可以判斷出他是什么樣的人了。

02|算法三要素：

通過該算法的原理，我們可以把該算法分解為3部分,第一部分就是要決定K值，也就是要找他周圍的幾個值；第二部分是距離的計算，即找出距離他最近的K個值；第三部分是分類規則的確定，就是以哪種標準去評判他是哪一類。

1、K值的選取

K值的選取將會對KNN算法的結果產生重大的影響，下面通過一個簡單的例子說明一下：如下圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。

圖2.1——來源于網絡

大家可以看到k值的選取會直接影響到評測結果，如果k值選取過大，相當于用較大領域中的訓練實例進行預測，這樣看起來是覺得數據越多可能越準確，但實際上并不然，如果要想獲得較多個k值，這樣你就需要把距離進一步擴大，預測準確率自然會下降。

還是拿那個我們判斷一個人是什么樣子的人為例，如果選擇較大的k值比如一個班的人，然后根據這一個班所有人的情況去預測這個班里面的某一個人是什么樣子的，這樣很明顯是不準確的。

如果k值選取過小，則這些很有可能是特例，也會影響預測的結果。

過大也不好，過小也不好，那么我們該怎么辦？最笨的也是最有效的方法就是試，我們在上一篇推文說模型選擇有一種方法是交叉驗證，機器學習開篇。我們在k值選擇的時候也可以用交叉驗證這種方法。

2、距離的度量

我們在評判人與人之間的關系遠近的時候沒有一個量化的關系，只會用一些詞去形容兩個人之間關系的遠近，比如閨蜜（發小）》舍友》同學。

但在統計學習中我們評判兩者的遠近關系的時候是有一個可以量化的東西，這里我們用的是歐式距離。

歐式距離又稱歐幾里得距離，是指在m維空間中，兩個點之間的真實距離。

• 二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：

?

• 三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：

?

• 兩個n維向量a(x11,x12,…,x1n)與?b(x21,x22,…,x2n)間的歐氏距離：

? ?

　 也可以用表示成向量運算的形式：

?

當然我們還可以使用其他距離來度量兩者的遠近關系，比如曼哈頓距離（是不是覺得名字很高大上），更多詳情點擊：https://wenku.baidu.com/view/ebde5d0e763231126edb1113.html

3、分類規則的確定：

這里我們目前就使用多數表決的分類規則，即這距離最近的k個值中的大部分值的類別就是待預測值的類別。

04|算法步驟：

收集數據：找尋待訓練的文本數據。

準備數據：利用python解析文本文件。

分析數據：對數據進行一些統計分析，有個基本的認識。

訓練算法：KNN沒有這一步，這也是為何被稱為最懶算法的原因。

測試算法：將提供的數據利用交叉驗證的方式進行算法的測試。

使用算法：將測試得到的準確率較高的算法直接應用到實際中。

05|利用python對未知電影進行分類：

1、背景：

假設愛情電影和動作電影之間的區別可以用打斗次數和接吻次數這兩個特征來決定，下面提供了一些電影的類別以及其對應的接吻和打斗次數(訓練數據集)。

表6-1:來源于網絡

現在有一電影A，已知其打斗次數為18，接吻次數為90，需要利用knn算法去預測該電影屬于哪一類別。

2、準備數據

3、分析數據

4、測試算法

通過測試最后得出，如果一部電影中含有18次打斗次數，90次接吻次數，那么可以判定為該電影是愛情片。

5、應用算法：

通過修改inX的值，就可以直接得出該電影的類型。

06|最后：

上面python實現過程中涉及的一些知識點：

pandas數據轉換成numpy，df.matrix()

matplotlib中文顯示亂碼問題

列表生成式

np.tile()函數

np.sum()函數

np.argsort()函數

dict.get()方法

dict.items()方法

operator.itemgetter()函數

總結

以上是生活随笔為你收集整理的最懒惰的算法—KNN的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。