一、實驗介紹
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。1k-近鄰演算法概述
簡單地說，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近鄰演算法的一般流程
收集資料：可以使用任何方法。
準備資料：距離計算所需要的數值，最好是結構化的資料格式。
分析資料：可以使用任何方法。
訓練演算法：此步驟不適用於k近鄰演算法。
測試演算法：計算錯誤率。
使用演算法：首先需要輸入樣本資料和結構化的輸出結果，然後執行k近鄰演算法判定輸入資料分別屬於哪個分類，最後應用對計算出的分類執行後續的處理。
2。2準備：使用Python匯入資料
首先，建立名為kNN。py的Python模組，本章使用的所有程式碼都在這個檔案中。讀者可以按照自己的習慣學習程式碼，既可以按照本書學習的進度，在自己建立的Python檔案中編寫程式碼，也可以直接從本書的原始碼中複製kNN。py檔案。我推薦讀者從頭開始建立模組，按照學習的進度編寫程式碼。
我們開啟 Xfce 終端，建立實驗資料夾KNN
cd Code
mkdir KNN
cd KNN
touch 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-近鄰演算法實現手寫數字識別系統
本課程源自 圖靈教育 的 《機器學習實戰》，如需系統學習本書，請購買《機器學習實戰》。
更多經典的程式設計練手專案：全部課程，微信關注公眾號
[實驗樓]
，手機檢視海量專案教程。
