可能是關於 kNN 算法最詳細的入門總結

【從零開始學機器學習第 10 篇】

摘要：機器學習最簡單算法——kNN 算法總結。

對於不少想學機器學習的初學者來說，可能聽到「機器學習」四個字就有點發怵，覺得難學門檻高，既要會編程數學還要好，那些科班出身的研究生才幹得了。

這話也對也不對，要說它對是因為要學的內容的確不少也不簡單，遠不像數據分析、爬蟲看著好學。其次，學習路徑一定程度地被魔化了：很多人說學機器學習要先去啃《西瓜書》、《統計學習方法》這些大篇幅的數學公式算法書，很容易讓新手放棄。

要說它不對也有道理。一是可能你並沒有真正想去學它，沒發現它有用或者至少有趣的地方；二是機器學習真的沒有那麼難入門，前提是找到合適自己的方法。所以想清楚為什麼學和從哪兒開始學很重要。

看了很多教程後，找到了合適自己的機器學習入門方法，也覺得適合很多人，接下來會一點點分享出來。

作為入門的第一課，kNN 算法是最好的選擇，因為它是機器學習中最簡單的算法，學會它幾乎沒有難度只需要會兩點：高中數學和一點 Python 編程基礎（遠沒有爬蟲那麼難）。

雖然是最簡單的算法，但我們還是花了大量篇幅（9 篇文章）來介紹它，為的是打好基礎，今天這一篇做個總結。

kNN 算法（K-Nearest Neighbor），也叫 K 近鄰算法，在具體介紹它之前，記住它的兩個特點。

它有什麼用途？主要有兩種。

一是可以解決分類問題，比如預測紅酒屬於哪一類，花屬於哪一種，是良性腫瘤還是惡性腫瘤等。除了二分類，它還可以解決多分類問題。

二是可以解決回歸問題，比如預測房價多少、學生成績多高等。

kNN 算法是少數能同時解決分類和回歸問題的算法，很實用。

它的算法思想和實現難麼？非常簡單。

kNN 算法思想可以用「近朱者赤近墨者黑」形容，誰離待預測值近，待預測值就屬於哪一類，就這麼簡單。判斷遠近可以用中學學過的歐拉距離公式計算。

知道特點後，我們通過一個酒吧猜酒的例子引入了 kNN算法：桌上倒的紅酒屬於兩類，需要根據它們的顏色深度、酒精濃度值去預測新倒的酒屬於哪一類：

【機器學習01】Python 手寫機器學習最簡單的 kNN 算法（可點擊）

具體如何預測呢？很簡單，只需要兩步：先把場景抽象為數學問題，然後將數學問題寫成 Python 代碼得到預測結果。

抽象為數學問題就是把酒映射到坐標軸中，接著根據歐拉公式計算待預測酒（黃色點）同每杯樣本酒（紅綠色點）之間的距離，然後排序並取前 k 杯酒（k 個點），哪一類酒佔比多，則新倒的酒就歸屬哪一類。

理清數學思路後就可以手寫代碼，手寫代碼可以加深對算法的理解，同時也能搞懂 Sklearn 調包背後的真正含義。

在這第一篇文章中，我們就手寫了 kNN  算法，預測出新倒的酒（黃色點）屬於綠色的赤霞珠。

接下來為了作對比，我們又調用了 Sklearn 中的 kNN 算法包，僅 5 行代碼就得到了相同的結果。

初次接觸 sklearn 的話，可能並不清楚代碼背後的 fit、predict 做了什麼，於是我們仿寫了 Sklearn 的 kNN 算法包，加深了對 Sklearn 調包的理解：

【機器學習02】sklearn 中的 kNN 封裝算法實現

通過以上兩篇我們就初步學會了 kNN 算法。不過在對算法做預測時，使用了全部數據作為訓練集，這樣一來算法的預測準確率如何並不清楚。

所以我們做了改進，將數據集拆成一大一小兩部分，大的作為訓練集，小的作為測試集。在訓練集上訓練好 kNN 模型後，把測試集餵給它得到預測結果，接著和測試集本身的真實標籤值作比較，得到了模型的準確率。

這一過程用到了 sklearn 的 train_test_split 方法，最終將一份有 178 個樣本的葡萄酒數據集，按照 7:3 的比例隨機劃分出了 124 個訓練樣本和 54 個測試樣本。

【機器學習03】手寫 Sklearn 的 train_test_split 函數

具體如何計算模型的分類準確率呢？我們又用到了 sklearn 的 accuracy_score 方法，在葡萄酒數據集上達到了 76% 的準確率 。（54 個測試樣本中，預測對了 41 個）

【機器學習04】Sklearn 的 model.score 和 accuracy_score 函數

為了鞏固之前 4 節內容，我們又以兩個機器學習中常見的數據集為例：鳶尾花和手寫數字識別，初步走了一遍 kNN 分類算法。

【機器學習05】kNN小結：解決鳶尾花和手寫數字識別分類

最後，模型在鳶尾花數據集上的準確率達到 97.8%（45 個花樣本僅預測錯 1 個），在手寫數字數據集上的預測準確率達到了 98.7%。這是在使用默認參數而未調參的情況下得到的結果，可見 kNN 算法雖簡單但效果很好。

不過，我們又發現存在一個問題：kNN 模型有很多參數（叫超參數），我們使用的都是默認參數，這樣建立得到的模型不一定是最好的，而我們期望找到最好的模型。

如何做到呢？這就需要調參，於是我們了解了 kNN 算法幾個重要的超參數，手動搭配組合之後找到了更好的模型，分類準確率進一步提升：

【機器學習06】調參——得到更好的 kNN 模型

但手動調整超參數很不方便，為此我們想到了 Sklearn 中專門實現調參功能的網格搜索方法（GridSearchCV），只需要指定超參數範圍，它就會運行所有超參數組合建立模型，最後返回其中效果最好的一組，這比我們自己手寫的方法方便地多。

【機器學習07】使用網格搜索（GridSearchCV）快速找到 kNN 模型最佳超參數

通過網格搜索我們進一步優化了 kNN 模型，這並沒有完，還有很重要的一點工作：對數據做歸一化處理。因為 kNN 模型跟樣本距離有密切關係，如果特徵之間的數量級相差很大的話，在計算距離時就容易產生偏差影響分類效果，所以最好建模前先去除數據量綱。

原始特徵最值歸一化後均值方差歸一化後

常用的數據歸一化方式有最值歸一化和均值方差歸一化，詳細對比了兩種方法的特點，最終建議使用均值方差歸一化：

【機器學習08】數據歸一化 Feature Scaling

歸一化處理後，之前葡萄酒模型的分類準確率從最初的 0.76 飆升到了 0.96。（54 個測試樣本中，正確分類的樣本數從 41 個上升到 52 個），可見數據歸一化對 kNN 算法的重要性。

以上我們主要介紹的是 kNN 算法解決分類問題，它還可以解決回歸問題，方法大同小異。為了加深理解，我們以常見的回歸數據集波士頓房價為例，運用 kNN 回歸模型預測了房價，效果不錯。

【機器學習09】kNN 解決回歸問題：以波士頓房價為例

以上就是 kNN 算法的主要內容，最後總結一下 kNN 算法的特點：

優點：

缺點：

kNN 算法在計算樣本距離時，每個樣本都要遍歷計算一篇全部訓練樣本，當數據量很大時，會很耗時，雖然可以用 KD 樹、球樹等改進方法但效率依然不高。

kNN 算法預測結果依賴最近的 K 個點，一旦 K 個點之中有異常值，很可能會分類錯誤。

對於預測的結果，並不能解釋預測值為什麼屬於這個類別。不像線性回歸算法具有可解釋性。

隨著維度的增加，「看似相近」的兩個點，它們之間的距離會隨著特徵維數的增多而越來越大。比如有 2 個特徵的數據集，兩個點之間的距離是1.4，一旦特徵數量增大到 10000 維時，距離就變成了 100。

相信看完這十篇文章，應該就可以搞明白 kNN 算法了，也能看得懂李航《統計學習方法》第 3 章的 kNN 算法。

到這兒，你就邁出了機器學習的第一步。接下來一起學習第二個算法吧：線性回歸。

最後以上所有文章代碼，可以在下方公眾號中回覆：knn 得到。