在機器學習的世界裡打怪升級——KNN算法篇

「全文約2000字，閱讀時間約6分鐘」

來自機器學習世界裡的勇士，你剛走出新手村，還沒完全武裝自己，就碰到了旅途中第一個小boss——KNN算法。

不過也別害怕，這是入門機器學習zui簡單、也zui容易理解的一個算法。

boss技能綜述

先來看看該boss的整體技能（原理）綜述：

要想預測一個新數據，只需把它放到訓練數據集中（「舊數據」），看它離哪些數據近，就把它預測為這些數據的類別（分類）；或者把它預測為這些數據的均值（回歸）。

所以k近鄰算法既可以做分類，又可以做回歸（限於篇幅，本文只介紹分類）。

我們說，機器學習可以看做是一個函數，輸入訓練數據集，輸出預測值。在k近鄰算法中，給定一個數據集D：

其中，x為n維向量，代表每一個樣本的特徵數量；y代表有p個類別；右上角的角標從1到N，代表有N個樣本。

我們的目標是：

當給定一個新的實例x，模型通過學習數據集D，輸出實例x對應的類別y。

boss詳細攻略

該算法的步驟很簡單，主要有以下兩步：

1.找到與x距離最近（如何衡量最近？下文會有介紹）的k個點，k近鄰算法中的k就是這個含義。

2.根據「少數服從多數」的原則，決定x的類別y。換句話說，這k個點中最多的那個類別，就是新的實例x的類別。用公式表示為：

那這公式是啥意思呢？

我們從括號內部開始看起。

首先，y[i]表示k個點所對應的類別，a[j]就表示數據集D中的所有類別，j的取值為1到p（上文介紹過，一共有p個類別）。

其次，I()叫做指示函數。

它的含義是，當括號內的條件為真（True）時，函數返回的值是1；當括號內的條件為假（False）時，函數返回0。

在公式（1）中，當y[i]=a[j]時，返回1。

我們來看下公式（1）運行的過程：

首先取第1個類別a[1]，讓k個點對應的y[i]都跟a[1]比較，計算指示函數並求和。

接下來從第2個類別a[2]開始循環上面的步驟，直到第p個類別a[p]。

由於每次循環返回一個值，我們需要找出其中的最大值，那麼這個最大值對應的類別，就是我們要求的實例x對應的類別y。

距離的衡量

k近鄰算法中，向量和向量之間的距離，我們一般用L2範數來衡量。即

a[i]就表示a中的第i個維度（特徵），總共有n個維度（特徵）。

分類的規則

最後我們來看下為什麼「少數服從多數」的規則是可行的。

我們做一個分類問題的目標是什麼？

當然是分錯的數量越少越好了。

假設我們預測的類別為y'，實際的類別為y，顯然，我們分錯的概率為

當我們找到離x最近的k個點之後，分錯的概率就是

我們希望分錯的概率越小越好，那麼就意味著（3）式中的

越大越好，而這正是我們公式（1）所表示的內容。

因此，多數「投票」的規則就等價於分錯概率最小化。

boss技能介紹

Python在機器學習領域有著得天獨厚的優勢，下面我們就來看看KNN算法在Python中是如何被調用的（調包俠）。

分類

我們來看下它的參數。

1.algorithm

該參數指在尋找最近鄰時所採用的算法，默認為auto，意為自動進行選擇。可供選擇的算法主要有下面三種：kd_tree，ball_tree，brute。

2.leaf_size

指葉子節點的數目，默認為30。

3.metric

指採用何種方式進行距離度量，默認為minkowski（閔可夫斯基距離），也就是我們之前介紹過的範數。

4.metric_params

指距離度量的相關參數，一般無需進行設置。

5.n_neighbors

指最近鄰點的個數，默認為5個。

6.p

當p=1時，即L1範數，採用曼哈頓距離；當p=2時，意為L2範數，採用歐氏距離。

7.weights

指分類時的權重類型，默認是uniform，即k個近鄰點的權重相等；還可以選擇distance，意為近鄰點的權重與預測點之間的距離有關，一般是反比的關係。

回歸

在scikit-learn中可以按如下方式實現：

可以看到，回歸模型的參數與分類模型的一模一樣，大家可以進行參考，這裡就不再贅述了。

boss戰

終於，我們要直面KNN算法這個小boss了。

Python的scikit-learn庫中自帶了很多公開的數據集，這裡用乳腺癌數據集來說明k近鄰算法。

首先，加載該數據集

然後，把該數據集分成兩部分。一部分用來訓練我們的模型，另一部分用來測試模型的精度。

其中，train_test_split可以將數據按25%的比例分成訓練集和測試集。X_train、y_train為訓練樣本和標籤，佔75%；X_test、y_test為測試樣本和標籤，佔比25%。

接著，加載我們的模型

這裡的n_neighbors和k的含義一樣，都是指鄰居的個數。也就是說，我們要找到最近的3個鄰居，來對預測做出判斷。

然後，把數據「餵」給我們的模型，讓模型得到訓練。

訓練完成後，我們測試一下模型的精度

也就是說，模型的精度達到了91.6%。

呼，boss終於倒下了，但剛才的過程有點驚險，我們還需要做一些任務來補充實力。

任務1：模型的泛化能力

我們用數據訓練模型的目的，就是希望它在未知的新數據集中有很好的表現，我們把這種能力就叫做泛化。

我們總是希望泛化精度儘可能高，但有時候，你對舊數據進行過度訓練，模型在訓練集中表現的非常好，以至於將一些無關的噪聲點都擬合了進來。

這時，模型的泛化能力反而會降低，我們稱之為過擬合。

與此同時，假如你沒有對數據進行有效的訓練，產生的模型也比較粗糙，那麼對於新的數據集，模型同樣不會有好的結果。我們稱之為欠擬合。

在模型訓練過程中，既不能訓練過少，也不能過度訓練。過擬合和欠擬合都是需要我們避免的。

任務2：模型的優缺點

優點：模型易於理解，不需要什麼數學基礎。參數也不多，調參很容易。

缺點：如果訓練數據的特徵很多，而且樣本也很大，那麼k近鄰算法的預測速度和精度都會有大幅下降。

恭喜你，勇士！經過這一場戰鬥，你獲得了以下屬性提升：

武力+1%，技能熟練度+1%，智慧+1%

前方還有更多未知的冒險在等著你，繼續前進吧，勇士！