《機器學習實戰》學習總結（一）——k近鄰演算法(kNN)

最近在學習機器學習相關知識，在學習的過程中有一些自己的心得體會，在此做了個學習總結，方便查閱，也給想了解機器學習或者Python的同學提供一點點幫助。

科普

機器學習(Machine Learning)專門研究計算機怎樣模擬或實現人類的學習行為，以獲取新的知識或技能，重新組織已有的知識結構使之不斷改善自身的性能。它是人工智慧的核心，是使計算機具有智能的根本途徑，其應用遍及人工智慧的各個領域，它主要使用歸納、綜合。

——來自 百度百科

簡單的講，機器學習就是一門讓機器能夠進行自我學習並不斷優化功能的學科。

本篇分演算法原理和代碼實現來介紹k-近鄰演算法。（下文會涉及演算法解析和部分專業術語，需要一定的Python語言和演算法基礎）

演算法原理

k-近鄰（k-Nearest Neighbour，簡稱KNN），常用於有監督學習。

KNN的工作原理很簡單：存在一個訓練樣本集合A，在給定測試樣本b時，基於某種距離度量，找出訓練集A中與測試樣本b最靠近的k個訓練樣本（通常k≤20且為整數），之後，基於這k個訓練樣本的信息來預測種類或值。

其中，在分類問題中，KNN用來預測種類。一般使用「投票法」，選擇這k個樣本中出現最多的類別來作為測試樣本的類別。

在回歸問題中，KNN預測一個值。使用「平均法」，將k個樣本的實值輸出的平均值作為測試樣本的輸出。一般情況下，距離度量選擇歐式距離：

三維的歐式距離公式為：

其他維度以此類推。

舉個例子

假設：評價一個人的長相用 [「好看」，「中等」，「難看」]來衡量。評價人的特徵用：身高、體重、年齡。我們已有一個200*4的數據集合矩陣作為訓練樣本，矩陣的4列分別為：身高、體重、年齡、長相。

現得到一個測試樣本，包括身高、體重、年齡三個評價特徵，這時我們用KNN對這個人的長相進行分類。

偽代碼如下：

對測試樣本點進行以下操作：

(1)計算已知類別數據集中的點與當前點之間的距離；

(2)按照距離遞增次序排序；

(3)選取與當前點距離最小的k個點；

(4)確定前k個點所在類別的出現頻率；

(5)返回前k個點出現頻率最高的類別作為當前點的預測分類。

1.演算法的泛化誤差

KNN演算法雖然很簡單，但是其泛化誤差(演算法推廣後，機器對於未知數據的學習錯誤率)卻是可以接受，以1NN問題(即k=1)為例,推導過程如下：

給定測試樣本x,若其最近鄰樣本為z，1NN出錯率就是x與z類別標記不同的概率，即：

假設樣本獨立同分布，且對任意x和任意小正數d，在x附近d距離範圍內總能找到一個訓練樣本z，令

表示貝葉斯最優分類器（以最小化總體風險為目標，對於樣本的分類。通俗講就是樣本最好的分類方式，具體推導見周志華老師《機器學習》的P147頁）的結果。

此時有：

以上得出，1NN的結構不僅簡單，而且1NN的泛化錯誤率≤2倍的貝葉斯最優分類器錯誤率。

2.演算法的不足

KNN演算法作為一種較簡單的演算法，它的不足之處在於：

(1)沒有明顯的訓練過程，它是「懶惰學習」的典型代表，它在訓練階段所做的僅僅是將樣本保存起來，如果訓練集很大，必須使用大量的存儲空間，訓練時間開銷為零；

(2)必須對數據集中每個數據計算距離值，實際中可能非常耗時。

3.kd樹

由於上述的不足，為了提高KNN搜索的速度，可以利用特殊的數據存儲形式來減少計算距離的次數。kd樹就是一種以二叉樹的形式存儲數據的方法。

kd樹就是對k維空間的一個劃分。構造kd樹相當於不斷用垂直於坐標軸的超平面將k維空間切分，構成一系列k維超矩陣區域。kd樹的每一個節點對應一個超矩陣區域。（想要深入了解的同學可以參看李航老師的《統計機器學習》P41頁）

舉個例子

給定一個二維空間的數據集：

請構造一個平衡kd樹(平衡kd樹就是以中位數作為劃分標準)。

解：根據點對應包含數據集T的矩陣，選擇x1軸，6個數據點的x1坐標的中位數是7，以平面x1=7將空間分為左、右兩個子矩陣(子節點)。

接著，左矩陣形以x2=4分為兩個子矩陣，右矩陣形以x2=6分為兩個子矩陣。

如此遞歸，最後得到如下圖所示的特徵空間劃分。

形成kd樹，並利用kd樹進行KNN搜索。搜索時從葉子節點往根節點搜索，具體搜索過程不展開贅述。

代碼實現與解讀

現在機器學習的很多基礎演算法都能調用scikit-learn中的包來實現，可能只需要一行命令。但我還是希望我們能夠自己動手實現一遍裡面的演算法，會加深自己對於演算法的理解。

下面的代碼部分主要源於《機器學習實戰》，書中對於代碼部分並未做太多解釋，對於Python初學者來說不太很友好，所以我加上了更詳細的解釋，方便初學者學習。

1. k-近鄰演算法

這是演算法比較核心的地方，也是上述偽代碼具體的實現。

程序清單：

2. 將文本數據轉換為矩陣

我們在本地存儲的訓練集樣本多為CSV格式或TXT格式，而若要在計算機中對它們進行處理，首先得將它們轉換為矩陣形式。

下面的代碼段就是編寫了file2matrix()函數，將文本文件轉換為矩陣。

程序清單：

3. 歸一化數值

當度量標準不一樣時，如果沒有將數據歸一化，可能導致數值大的特徵在評價中起較大作用，而實際這幾個特徵的重要性是一樣的。

所以為了特徵重要性的評判，我們要進行數據歸一化。歸一化方式有很多，我們一般用：

程序清單：

4. 分類器的測試代碼

用測試數據集來測試演算法的分類準確度，這裡會用到剛才創建的幾個函數。

程序清單：

以上構建的函數是KNN演算法實現的主要框架，我們現在調用的很多演算法包很多也是按照上述方式構建出來的。

當然，scikit-learn中的KNN演算法肯定是優化版，速度會快很多，但核心思想卻是一樣的。

至此，我們完成了KNN演算法原理和主要代碼的學習。KNN演算法是分類數據最簡單最實用的方法，有廣泛的應用。本篇寫的比較概括，目的在於拋磚引玉，希望大家可以挖掘出KNN演算法更多的東西來交流探討。

下一節我們將進行決策樹演算法的學習。

聲明

以上均為本人自學整理所得，如有錯誤，歡迎指正，有任何建議也歡迎交流，讓我們共同進步！轉載請註明作者與出處。

原理部分主要來自於《機器學習》—周志華，《統計學習方法》—李航，《機器學習實戰》—Peter Harrington。代碼部分主要來自於《機器學習實戰》。代碼部分用Python3實現。

推薦閱讀：