一、實驗介紹

1.1 實驗內容

本實驗將會從電影題材分類的例子入手，詳細講述k-近鄰演算法的原理。在這之後，我們將會使用該演算法實現手寫數字識別系統。

完整教程及在線練習地址：k-近鄰演算法實現手寫數字識別系統

1.2 實驗來源

本實驗源自《機器學習實戰》 書籍第2章，由 圖靈教育 授權實驗樓發布。如需系統的學習本書，請購買《機器學習實戰》。

為了保證可以在實驗樓環境中完成本次實驗，我們補充了一系列的實驗指導，比如實驗截圖，代碼注釋，幫助您更好得實戰。

1.3 實驗知識點

• k近鄰分類演算法
• 從文本文件中解析和導入數據
• 使用Matplotlib創建擴散圖
• 歸一化數值

1.4 實驗環境

• python 2.7
• numpy 模塊
• Xfce 終端

1.5 適合人群

本課程屬於中等難度級別，適合具有 Python 基礎的用戶，如果對 numpy 了解能夠更好的上手本課程。

1.6 代碼獲取

你可以在實驗樓中獲取本項目代碼，作為參照對比進行學習。

二、實驗原理

眾所周知，電影可以按照題材分類，然而題材本身是如何定義的?由誰來判定某部電影屬於哪個題材?也就是說同一題材的電影具有哪些公共特徵?這些都是在進行電影分類時必須要考慮的問題。沒有哪個電影人會說自己製作的電影和以前的某部電影類似，但我們確實知道每部電影在風格上的確有可能會和同題材的電影相近。那麼動作片具有哪些共有特徵，使得動作片之間非常類似，而與愛情片存在著明顯的差別呢？動作片中也會存在接吻鏡頭，愛情片中也會存在打鬥場景，我們不能單純依靠是否存在打鬥或者親吻來判斷影片的類型。但是愛情片中的親吻鏡頭更多，動作片中的打鬥場景也更頻繁，基於此類場景在某部電影中出現的次數可以用來進行電影分類。本章第一節基於電影中出現的親吻、打鬥出現的次數，使用k近鄰演算法構造程序，自動劃分電影的題材類型。我們首先使用電影分類講解k近鄰演算法的基本概念，然後學習如何在其他系統上使用k近鄰演算法。

本章介紹第一個機器學習演算法：k近鄰演算法，它非常有效而且易於掌握。首先，我們將探討k近鄰演算法的基本理論，以及如何使用距離測量的方法分類物品；接著，我們將使用Python從文本文件中導入並解析數據；然後，本書討論了當存在許多數據來源時，如何避免計算距離時可能碰到的一些常見錯誤；最後，利用實際的例子講解如何使用k近鄰演算法完成手寫數字識別系統。

2.1　k-近鄰演算法概述

簡單地說，k近鄰演算法採用測量不同特徵值之間的距離方法進行分類。

k-近鄰演算法

• 優點：精度高、對異常值不敏感、無數據輸入假定。
• 缺點：計算複雜度高、空間複雜度高。 適用數據範圍：數值型和標稱型。

本書講解的第一個機器學習演算法是k-近鄰演算法（kNN)，它的工作原理是：存在一個樣本數據集合，也稱作訓練樣本集，並且樣本集中每個數據都存在標籤，即我們知道樣本集中每一數據與所屬分類的對應關係。輸入沒有標籤的新數據後，將新數據的每個特徵與樣本集中數據對應的特徵進行比較，然後演算法提取樣本集中特徵最相似數據（最近鄰）的分類標籤。一般來說，我們只選擇樣本數據集中前k個最相似的數據，這就是k-近鄰演算法中k的出處，通常k是不大於20的整數。最後，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。

現在我們回到前面電影分類的例子，使用k近鄰演算法分類愛情片和動作片。有人曾經統計過很多電影的打鬥鏡頭和接吻鏡頭，圖2-1顯示了6部電影的打鬥和接吻鏡頭數。假如有一部未看過的電影，如何確定它是愛情片還是動作片呢？我們可以使用kNN來解決這個問題。

首先我們需要知道這個未知電影存在多少個打鬥鏡頭和接吻鏡頭，圖2-1中問號位置是該未知電影出現的鏡頭數圖形化展示，具體數字參見表2-1。

即使不知道未知電影屬於哪種類型，我們也可以通過某種方法計算出來。首先計算未知電影與樣本集中其他電影的距離，如表2-2所示。此處暫時不要關心如何計算得到這些距離值，使用Python實現電影分類應用時，會提供具體的計算方法。

現在我們得到了樣本集中所有電影與未知電影的距離，按照距離遞增排序，可以找到k個距離最近的電影。假定k=3，則三個最靠近的電影依次是He』s Not Really into Dudes、Beautiful Woman和California Man。k近鄰演算法按照距離最近的三部電影的類型，決定未知電影的類型，而這三部電影全是愛情片，因此我們判定未知電影是愛情片。

本章主要講解如何在實際環境中應用k近鄰演算法，同時涉及如何使用Python工具和相關的機器學習術語。按照1.5節開發機器學習應用的通用步驟，我們使用Python語言開發k近鄰演算法的簡單應用，以檢驗演算法使用的正確性。

k近鄰演算法的一般流程

1. 收集數據：可以使用任何方法。
2. 準備數據：距離計算所需要的數值，最好是結構化的數據格式。
3. 分析數據：可以使用任何方法。
4. 訓練演算法：此步驟不適用於k近鄰演算法。
5. 測試演算法：計算錯誤率。
6. 使用演算法：首先需要輸入樣本數據和結構化的輸出結果，然後運行k近鄰演算法判定輸入數據分別屬於哪個分類，最後應用對計算出的分類執行後續的處理。

2.2　準備：使用Python導入數據

首先，創建名為kNN.py的Python模塊，本章使用的所有代碼都在這個文件中。讀者可以按照自己的習慣學習代碼，既可以按照本書學習的進度，在自己創建的Python文件中編寫代碼，也可以直接從本書的源代碼中複製kNN.py文件。我推薦讀者從頭開始創建模塊，按照學習的進度編寫代碼。

我們打開 Xfce 終端，創建實驗文件夾KNN

cd Codemkdir KNNcd KNNtouch kNN.py

然後我們先來安裝 NumPy 模塊。

sudo pip install numpy

隨後我們就可以使用 vim 或者 sublime 對我們的 kNN.py文件進行編輯。在kNN.py文件中增加下面的代碼：

from numpy import * import operator def createDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ["A","A","B","B"] return group, labels

在上面的代碼中，我們導入了兩個模塊：第一個是科學計算包NumPy；第二個是運算符模塊，k近鄰演算法執行排序操作時將使用這個模塊提供的函數，後面我們將進一步介紹。

然後保存kNN.py文件，確保我們在 kNN.py 文件的路徑下（/home/shiyanlou/Code/KNN），在 Xfce 終端內輸入ipython，進入Python互動式開發環境。

進入Python開發環境之後，輸入下列命令導入上面編輯的程序模塊：

>>> import kNN

上述命令導入kNN模塊。為了確保輸入相同的數據集，kNN模塊中定義了函數createDataSet，在Python命令提示符下輸入下列命令：

>>> group,labels = kNN.createDataSet()

上述命令創建了變數group和labels，在Python命令提示符下輸入下列命令，輸入變數的名字以檢驗是否正確地定義變數：

>>> group array([[ 1. , 1.1], [ 1. , 1. ], [ 0. , 0. ], [ 0. , 0.1]]) >>> labels ["A", "A", "B", "B"]

這裡有4組數據，每組數據有兩個我們已知的屬性或者特徵值。上面的group矩陣每行包含一個不同的數據，我們可以把它想像為某個日誌文件中不同的測量點或者入口。由於人類大腦的限制，我們通常只能可視化處理三維以下的事務。因此為了簡單地實現數據可視化，對於每個數據點我們通常只使用兩個特徵。

向量labels包含了每個數據點的標籤信息，labels包含的元素個數等於group矩陣行數。這裡我們將數據點(1, 1.1)定義為類A，數據點(0, 0.1)定義為類B。為了說明方便，例子中的數值是任意選擇的，並沒有給出軸標籤，圖2-2是帶有類標籤信息的四個數據點。

現在我們已經知道Python如何解析數據，如何載入數據，以及kNN演算法的工作原理，接下來我們將使用這些方法完成分類任務。

2.3　如何測試分類器

在上文中我們提到使用 kNN 演算法能夠判斷出一個電影是動作片還是愛情片，即我們使用 kNN 演算法能夠實現一個分類器。我們需要檢驗分類器給出的答案是否符合我們的預期。讀者可能會問：「分類器何種情況下會出錯？」或者「答案是否總是正確的？」答案是否定的，分類器並不會得到百分百正確的結果，我們可以使用多種方法檢測分類器的正確率。此外分類器的性能也會受到多種因素的影響，如分類器設置和數據集等。不同的演算法在不同數據集上的表現可能完全不同，這也是本部分的6章都在討論分類演算法的原因所在。

為了測試分類器的效果，我們可以使用已知答案的數據，當然答案不能告訴分類器，檢驗分類器給出的結果是否符合預期結果。通過大量的測試數據，我們可以得到分類器的錯誤率——分類器給出錯誤結果的次數除以測試執行的總數。錯誤率是常用的評估方法，主要用於評估分類器在某個數據集上的執行效果。完美分類器的錯誤率為0，最差分類器的錯誤率是1.0，在這種情況下，分類器根本就無法找到一個正確答案。讀者可以在後面章節看到實際的數據例子。

上一節介紹的例子已經可以正常運轉了，但是並沒有太大的實際用處。接下來本書將使用手寫識別系統的測試程序檢測k近鄰演算法的效果。

三、實驗步驟

本項目的詳細步驟可在實驗樓查看並在線完成：k-近鄰演算法實現手寫數字識別系統

主要實現步驟：

1. 準備數據：將圖像轉換為測試向量

2. 分析數據

3. 測試演算法：使用k近鄰演算法識別手寫數字

四、實驗總結

k-近鄰演算法是分類數據最簡單有效的演算法。k-近鄰演算法是基於實例的學習，使用演算法時我們必須有接近實際數據的訓練樣本數據。k-近鄰演算法必須保存全部數據集，如果訓練數據集很大，必須使用大量的存儲空間。此外，由於必須對數據集中的每個數據計算距離值實際使用是可能非常耗時。是否存在一種演算法減少存儲空間和計算時間的開銷呢？k決策樹就是k近鄰演算法的優化版，可以節省大量的計算開銷。

五、擴展閱讀

查看本項目教程及全部代碼：k-近鄰演算法實現手寫數字識別系統

本課程源自 圖靈教育 的 《機器學習實戰》，如需系統學習本書，請購買《機器學習實戰》。

更多經典的編程練手項目：全部課程，微信關注公眾號[實驗樓]，手機查看海量項目教程。

推薦閱讀：