出品：Python數據之道（ID：PyDataLab）

作者：Peter，來自讀者投稿

編輯：Lemon

圖解超經典的KNN算法

本文中介紹的機器學習算法中的一種監督學習的算法：KNN 算法，全稱是 K-Nearest Neighbor，中文稱之為 K 近鄰算法。

它是機器學習可以說是最簡單的分類算法之一，同時也是最常用的分類算法之一。在接下來的內容中，將通過以下的幾個方面的內容對該算法進行詳細的講解：

1、算法思想

思想

首先對 KNN 算法的思想進行簡單的描述：

KNN 算法是一個基本的分類和回歸的算法，它是屬于監督學習中分類方法的一種。其大致思想表述為：

給定一個訓練集合 M 和一個測試對象 n ，其中該對象是由一個屬性值和未知的類別標簽組成的向量。

計算對象 m 和訓練集中每個對象之間的距離（一般是歐式距離）或者相似度（一般是余弦相似度），確定最近鄰的列表

將最近鄰列表中數量占據最多的類別判給測試對象 z 。

一般來說，我們只選擇訓練樣本中前 K 個最相似的數據，這便是 k-近鄰算法中 k 的出處。

用一句俗語來總結 KNN 算法的思想：物以類聚，人以群分

說明

• 所謂的監督學習和非監督學習，指的是訓練數據是否有類別標簽，如果有則是監督學習，否則是非監督學習

• 在監督學習中，輸入變量和輸出變量可以連續或者離散的。如果輸入輸出變量都是連續型變量，則稱為回歸問題（房價預測）；如果輸出是離散型變量，則稱之為分類問題（判斷患者是否屬于患病）

• 在無監督學習中，數據是沒有任何標簽的，主要是各種聚類算法（以后學習）

2、算法步驟

KNN 算法的步驟非常簡單：

計算未知實例到所有已知實例的距離；

選擇參數 K（下面會具體講解K值的相關問題）

根據多數表決( Majority-Voting )規則，將未知實例歸類為樣本中最多數的類別

3、圖解 KNN 算法

K 值影響

下面通過一組圖形來解釋下 KNN 算法的思想。我們的目的是：判斷藍色的點屬于哪個類別

我們通過變化 K 的取值來進行判斷。在該算法中K的取值一般是奇數，防止兩個類別的個數相同，無法判斷對象的類別

K=1、3、5、7…….

首先如果 K=1：會是什么的情況？

根據圖形判斷：藍色圖形應該是屬于三角形

K=3 的情形

從圖中可以看出來：藍色部分還是屬于三角形

K=5 的情形：

此時我們觀察到藍色部分屬于正方形了

K=7 的情形：

這個時候藍色部分又變成了三角形

小結

當 K 取值不同的時候，判別的結果是不同的。所以該算法中K值如何選擇將非常重要，因為它會影響到我們最終的結果。

4、K 值選取

交叉驗證

上面的一系列圖形中已經說明了該算法中K值對結果的影響。那么 K 值到底該如何選擇呢？謎底揭曉：交叉驗證

K 值一般是通過交叉驗證來確定的；經驗規則來說，一般 k 是低于訓練樣本數的平方根。

所謂交叉驗證就是通過將原始數據按照一定的比例，比如 6/4 ，拆分成訓練數據集和測試數據集，K 值從一個較小的值開始選取，逐漸增大，然后計算整個集合的方差，從而確定一個合適的 K 值。

經過使用交叉驗證，我們會得到類似如下的圖形，從圖形中可以明顯的：

當 K 先不斷增大的時候，誤差率會先進行降低。因為數據會包含更多的樣本可以使用，從而分類效果會更好；

當 K=10 的附近，出現誤差率的變化，建議 K=9 或者 11 ；

當 K 不斷增大的時候，誤差率將會不斷增加。此時，KNN 算法將會變得沒有意義。比如有 50 個樣本，當 K 增加到 45 的時候，算法沒有意義，幾乎使用了全部樣本數據，沒有體現出最近鄰的思想。

K 值過小

k值太小：容易受到噪聲點的影響

• 用較小的鄰域中的實例進行預測；

• 近似誤差減小，估計誤差增大；

• 預測結果對近鄰的實例點非常敏感；如果近鄰點恰好是噪聲，預測出錯。

K 值過大

k 值太大：分類太多，太細，導致包含太多其他類別的點

• 用較大的鄰域中的實例點進行預測；

• 減少學習的估計誤差，但是近似誤差增大；

• 與輸入實例較遠的點的訓練實例也會起預測作用；

• k 值增大意味著整個模型變得簡單。

5、距離問題

常見距離

在上面的算法原理中提到，需要計算測試對象和訓練集合中每個對象距離。在機器學習中，兩個對象之間的距離包含：

常用的距離有以下幾種：

• 歐式距離

• 曼哈頓距離

• 切比雪夫距離

• 閔可夫斯基距離

• 標準歐式距離

• 馬氏距離

• 漢明距離

• 夾角余弦

• 杰卡德相似系數

在 KNN 算法中我們一般采用的是歐式距離（常用）或者曼哈頓距離

歐式距離

N維空間的距離：

當 n=2 時候，稱之為歐式距離：

其中 X 稱之為到原點的歐式距離

曼哈頓距離

曼哈頓距離是閔可夫斯基距離的一種特殊情形。閔可夫斯基距離指的是：

當 p=2，變成歐式距離；

當 p=1，變成曼哈頓距離；

當 p 區域無窮，變成切比雪夫距離；

6、算法優缺點

優點

簡單易用，而且非常容易弄懂基本原理，KNN 算法可以說是機器算法中最簡單易懂的算法。即使初學者沒有太多的基礎，相信也能明白它的原理。

算法是惰性的，模型訓練時間快。KNN 算法沒有明確的數據訓練過程，或者說它根本不需要進行數據的訓練，直接可以對測試對象進行判斷。

適合用于多分類問題（對象具有多個標簽）。

缺點

對計算機的內存要求高：因為它存儲了整個訓練數據，性能較低

算法的可解釋差，對結果不能給出一定的解釋規則

什么時候使用 KNN 算法？scikit-learn 官方中的一張圖給出了一個答案：

7、KNN算法實現

下面通過一個簡單的算法來實現 KNN 算法，主要步驟為：

創建數據集合和標簽

利用歐式距離，使用 KNN 算法進行分類

計算歐式距離

距離的排序（從大到小）

統計 K 個樣本中出現次數多的，歸屬于該類別

作者簡介

Peter，碩士畢業僧一枚，從電子專業自學Python入門數據行業，擅長數據分析及可視化。喜歡數據，堅持跑步，熱愛閱讀，樂觀生活。個人格言：不浮于世，不負于己

個人站點：www.renpeter.cn，歡迎常來小屋逛逛

本文來自公眾號讀者投稿，歡迎各位童鞋向公號投稿，點擊下面圖片了解詳情！

---------End---------

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯

獲取一折本站知識星球優惠券，復制鏈接直接打開：

https://t.zsxq.com/y7uvZF6

本站qq群704220115。

加入微信群請掃碼：

總結

以上是生活随笔為你收集整理的【机器学习入门】图解超经典的KNN算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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