出品：Python數(shù)據(jù)之道（ID：PyDataLab）

作者：Peter，來自讀者投稿

編輯：Lemon

圖解超經(jīng)典的KNN算法

本文中介紹的機器學(xué)習(xí)算法中的一種監(jiān)督學(xué)習(xí)的算法：KNN 算法，全稱是 K-Nearest Neighbor，中文稱之為 K 近鄰算法。

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

1、算法思想

思想

首先對 KNN 算法的思想進(jìn)行簡單的描述：

KNN 算法是一個基本的分類和回歸的算法，它是屬于監(jiān)督學(xué)習(xí)中分類方法的一種。其大致思想表述為：

1. 給定一個訓(xùn)練集合 M 和一個測試對象 n ，其中該對象是由一個屬性值和未知的類別標(biāo)簽組成的向量。
2. 計算對象 m 和訓(xùn)練集中每個對象之間的距離（一般是歐式距離）或者相似度（一般是余弦相似度），確定最近鄰的列表
3. 將最近鄰列表中數(shù)量占據(jù)最多的類別判給測試對象 z 。
4. 一般來說，我們只選擇訓(xùn)練樣本中前 K 個最相似的數(shù)據(jù)，這便是 k-近鄰算法中 k 的出處。

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

說明

• 所謂的監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)，指的是訓(xùn)練數(shù)據(jù)是否有類別標(biāo)簽，如果有則是監(jiān)督學(xué)習(xí)，否則是非監(jiān)督學(xué)習(xí)
• 在監(jiān)督學(xué)習(xí)中，輸入變量和輸出變量可以連續(xù)或者離散的。如果輸入輸出變量都是連續(xù)型變量，則稱為回歸問題（房價預(yù)測）；如果輸出是離散型變量，則稱之為分類問題（判斷患者是否屬于患?。?/section>
• 在無監(jiān)督學(xué)習(xí)中，數(shù)據(jù)是沒有任何標(biāo)簽的，主要是各種聚類算法（以后學(xué)習(xí)）

2、算法步驟

KNN 算法的步驟非常簡單：

1. 計算未知實例到所有已知實例的距離；
2. 選擇參數(shù) K（下面會具體講解K值的相關(guān)問題）
3. 根據(jù)多數(shù)表決( Majority-Voting )規(guī)則，將未知實例歸類為樣本中最多數(shù)的類別

3、圖解 KNN 算法

K 值影響

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

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

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

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

根據(jù)圖形判斷：藍(lán)色圖形應(yīng)該是屬于三角形

2. K=3 的情形

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

3. K=5 的情形：

此時我們觀察到藍(lán)色部分屬于正方形了

4. K=7 的情形：

這個時候藍(lán)色部分又變成了三角形

小結(jié)

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

4、K 值選取

交叉驗證

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

K 值一般是通過交叉驗證來確定的；經(jīng)驗規(guī)則來說，一般 k 是低于訓(xùn)練樣本數(shù)的平方根。

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

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

1. 當(dāng) K 先不斷增大的時候，誤差率會先進(jìn)行降低。因為數(shù)據(jù)會包含更多的樣本可以使用，從而分類效果會更好；
2. 當(dāng) K=10 的附近，出現(xiàn)誤差率的變化，建議 K=9 或者 11 ；
3. 當(dāng) K 不斷增大的時候，誤差率將會不斷增加。此時，KNN 算法將會變得沒有意義。比如有 50 個樣本，當(dāng) K 增加到 45 的時候，算法沒有意義，幾乎使用了全部樣本數(shù)據(jù)，沒有體現(xiàn)出最近鄰的思想。

K 值過小

k值太?。喝菀资艿皆肼朁c的影響

• 用較小的鄰域中的實例進(jìn)行預(yù)測；
• 近似誤差減小，估計誤差增大；
• 預(yù)測結(jié)果對近鄰的實例點非常敏感；如果近鄰點恰好是噪聲，預(yù)測出錯。

K 值過大

k 值太大：分類太多，太細(xì)，導(dǎo)致包含太多其他類別的點

• 用較大的鄰域中的實例點進(jìn)行預(yù)測；
• 減少學(xué)習(xí)的估計誤差，但是近似誤差增大；
• 與輸入實例較遠(yuǎn)的點的訓(xùn)練實例也會起預(yù)測作用；
• k 值增大意味著整個模型變得簡單。

5、距離問題

常見距離

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

常用的距離有以下幾種：

• 歐式距離
• 曼哈頓距離
• 切比雪夫距離
• 閔可夫斯基距離
• 標(biāo)準(zhǔn)歐式距離
• 馬氏距離
• 漢明距離
• 夾角余弦
• 杰卡德相似系數(shù)

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

歐式距離

N維空間的距離：

當(dāng) n=2 時候，稱之為歐式距離：

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

曼哈頓距離

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

當(dāng) p=2，變成歐式距離；

當(dāng) p=1，變成曼哈頓距離；

當(dāng) p 區(qū)域無窮，變成切比雪夫距離；

6、算法優(yōu)缺點

優(yōu)點

1. 簡單易用，而且非常容易弄懂基本原理，KNN 算法可以說是機器算法中最簡單易懂的算法。即使初學(xué)者沒有太多的基礎(chǔ)，相信也能明白它的原理。
2. 算法是惰性的，模型訓(xùn)練時間快。KNN 算法沒有明確的數(shù)據(jù)訓(xùn)練過程，或者說它根本不需要進(jìn)行數(shù)據(jù)的訓(xùn)練，直接可以對測試對象進(jìn)行判斷。
3. 適合用于多分類問題（對象具有多個標(biāo)簽）。

缺點

1. 對計算機的內(nèi)存要求高：因為它存儲了整個訓(xùn)練數(shù)據(jù)，性能較低
2. 算法的可解釋差，對結(jié)果不能給出一定的解釋規(guī)則

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

7、KNN算法實現(xiàn)

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

1. 創(chuàng)建數(shù)據(jù)集合和標(biāo)簽
2. 利用歐式距離，使用 KNN 算法進(jìn)行分類
1. 計算歐式距離
2. 距離的排序（從大到?。?/section>
3. 統(tǒng)計 K 個樣本中出現(xiàn)次數(shù)多的，歸屬于該類別

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