基于KNN的手寫體數字識別實驗案例設計

安利 柳泉 張晗

摘要：本文以規范設計、夯實基礎、科學考核、激勵創新為宗旨精心設計了基于KNN的手寫體識別的實驗案例。試驗過程中，首先逐步引導學生理解KNN算法的基本思想與原理，然后基于Python語言實現手寫體數字的識別，最后通過科學完善的考核標準總結學生獨立實驗的能力。整個實驗以理解算法設計為核心、代碼實現與調試為重點、考核與總結為評價，提高了學生理論聯系實際、分析與研究、變革與創新的能力，取得了良好的教學效果。

關鍵詞： KNN算法 ?數字識別 ?Python語言 實驗案例

中圖分類號：G202 ? ? ? ? ? 文獻標識碼：A

隨著信息時代的到來，人們對于信息處理的要求更加嚴格，不僅要有非常高的準確率，還要有非常快的處理速度。手寫體數字識別一直是多年來的研究熱點，也是圖像處理和模式識別領域中的研究內容[1]，手寫體數字識別被應用在大規模數據統計中。例如，人口普查、成績單錄入、行業年檢、財務報表錄入等應用中。手寫數字識別是利用機器或計算機自動辨認手寫體阿拉伯數字的一種技術，是光學字符識別技術的一個分支。由于阿拉伯數字通用，并且數字識別和處理也常是一些自動化系統的核心和關鍵，所以對手寫體數字識別的研究通用性強，且意義重大。

本文通過實驗過程[2-6]，引導學生逐步熟悉KNN算法的設計方法。并通過Python語言中程序調試實現基于KNN算法，利用計算機自動辨認人手寫在紙張上的阿拉伯數字的過程，以培養學生積極思考、精益求精的科學態度和創新意識，提高學生獨立實驗能力、分析與研究能力、理論聯系實際能力和創新能力，最終達到培養學生基于算法和程序設計問題的求解基本方法和能力的目的。具體實驗過程如圖1：

1、實驗思想

k最鄰近算法（k-Nearest Neighbor， KNN）是一種分類算法[7-8]，也是最簡單易懂的機器學習算法。1968年由 Cover 和 Hart 提出，應用場景有字符識別、文本分類、圖像識別等領域。該算法的思想是：一個樣本與數據集中的k個樣本最相似，如果這k個樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。KNN算法是由你的鄰居來推斷出你的類別。

如圖2所示，綠色三角形要被決定賦予哪個類，是紅色五角星還是藍色四方形？如果K=4，由于紅色五角星所占比例為3/4，綠色三角將被賦予紅色五角星那個類，如果K=7，由于藍色四方形比例為4/7，因此綠色三角被賦予藍色四方形類。由此也說明了KNN算法的結果很大程度取決于K的選擇。

2、實驗指導

手寫體數字識別是一個比較完整的工程實踐過程，需要經歷學習研究、方案論證、系統設計、實現調試、測試標定、設計總結等過程。因此在實驗過程中需加強對學生的引導：

1）學習矩陣以及向量在Python環境中的表示，了解圖像數據轉換為矩陣的過程。

2）熟悉距離計算模型，了解各模型的特點。本實驗中，在鄰居距離的模型選擇中，我們選擇相對簡單的歐式距離模型，但此模型在低維度計算時準確度較高，而在高維度對距離衡量，歐式距離的區分能力就越差。

3）對庫函數以及參數的理解，如tile（A，n）就是將A重復n次，argsort（）是排序函數等

4）注意k值的選擇，k值通常是采用交叉檢驗來確定（以k=1為基準）經驗規則：k一般低于訓練樣本數的平方根。

5）理解類別的判斷方法。本實驗初始選擇投票決定：少數服從多數，近鄰中哪個類別的點最多就分為該類。后面對算法改進可采用加權投票法：根據距離的遠近，對近鄰的投票進行加權，距離越近則權重越大（權重為距離平方的倒數）

6）在實驗完成后，可以組織學生以項目演講、答辯、評講的形式進行交流，了解不同解決方案及其特點，拓寬知識面。

3、實驗方案

1）實驗數據

本次實驗的數據集由學生在網站[9]下載。數據集包括數字0-9的手寫體。每個數字大約有200個樣本。每個樣本保存在一個txt文件中。手寫體圖像本身的大小是32x32的二值圖，轉換到txt文件保存后，內容也是32x32個數字，0或者1，數據集解壓后有兩個目錄，目錄trainingDigits存放的是大約2000個訓練數據，testDigits存放大約900個測試數據。一共1934個文件，最后構建的矩陣是1934x1024的矩陣，如圖3所示。

這里我們還新建一個KNN.py腳本文件，文件里面包含四個函數，一個用來生成將每個樣本的txt文件轉換為對應的一個向量，一個用來加載整個數據庫，一個實現kNN分類算法。最后就是實現這個加載，測試的函數。

2）K最近鄰計算模型

KNN是采用測量不同特征值之間的距離方法進行分類，也就是說對于每個樣本數據，需要和訓練集中的所有數據進行歐氏距離計算。

3）KNN算法流程圖（圖4）

4）核心分類函數[10]，使用Python語言實現（圖5）

5）結果分析

首先分析問題，將每一個手寫體處理為一個向量，在本實驗中處理為將32x32的二進制圖像文本矩陣轉換成1x1024的向量。循環讀出文件的前32行，存儲在向量中。

將訓練數據中的數據進行分類訓練，即給每個圖像追加標簽。標簽是通過截取文件名的首數字字符得到。文件名的保存方式，如圖1所示。

然后，通過歐式距離計算樣本與訓練集的距離（代碼如上分類函數所示），并將得到的距離按從小到大排序。

接著，選擇前K個作鄰居，通過投票法，決定當前樣本的標簽，即分類。具體過程是，統計k個鄰居的各分類標簽訓練圖像個數，哪個分類標簽里的鄰居個數最多，那么當前樣本即為該分類。

最后，統計識別的正確率，并思考對算法的改進。算法的改進可從兩個方面考慮：一是性能問題：KNN構造模型很簡單，但在對測試樣本分類地的系統開銷大，因為要掃描全部訓練樣本并計算距離。二是訓練的時間：能否大幅減少訓練樣本量，同時又保持分類精度。4、實驗考核

實驗考核是實驗過程中不可或缺的環節，是對實驗所達到的效果和學生學習實踐效果的有效檢驗，要求單人單組，詢問學生是否單獨完成程序的運行、確保每個同學都能夠了解KNN算法以及程序運行的過程，根據完成質量進行打分。為體現考核的公正性、合理性和準確性以及強調實驗結果的同時，注重實驗的整個過程，不能僅憑實驗結果和實驗報告給出成績，因此制定實驗考核指標，見表1：

5、結束語

此案例是機器學習的入門案例，熟練掌握該案例的實現過程為后續實驗的完成奠定了良好的基礎。從實驗教學效果上看，此案例貼近生活、應用廣泛，學生比較容易接受，興趣也更濃厚，特別在獨立實驗完成的過程中，學生從中獲得巨大的成就感，實驗的主動性明顯增強。不足之處，算法優化方面學生還不夠主動，后期將鼓勵學生在前人的基礎上進行創新，設計更好的解決方案，最終實現層次式的發展。

參考文獻

[1]. 期刊：任美麗，孟亮，基于原型生成技術的手寫體識別[J].計算機工程與設計，2015年，第36卷第8期：2211-2216

[2]. 期刊：劉福泉，案例+實驗教學法在計算機網絡教學中的應用—以一次教學活動為例[J].計算機時代，2015年，第8期：57-60

[3]. 期刊：賈翼婷，計算機實驗教學淺談[J].西安郵電學院學報，2006年，第11卷第4期：136-138

[4]. 期刊：胡旺，鄭莉華，陳安龍 ，一種進階式數據庫課程實驗方案設計[J]. 計算機教育，2012年，第1期：39-42

[5]. 期刊：汪志華，計算機組成原理實驗教學的改革與實踐[J].集美大學學報，2016年，第17卷第2期：83-87

[6]. 期刊：鐘元生，曹權，APP開發教學案例設計[J].軟件工程師，2015年，18卷第8期：65-68

[7]. 期刊：熊志斌，朱劍峰，尹國城等，基于KNN算法的文本分類器的設計與實現[J].軟件研發與應用，2016年，第八期：11-13

[8]. 期刊：劉卓，K-最鄰近算法在文本分類中的應用[J].蘇州市職業大學學報，2010年，第21卷第2期：58-60

[9]. 電子文獻： https：//www.kaggle.com/datasets[OL]

[10]. 期刊：趙明洪，張太紅，王正敏，Python程序代碼相似度檢測[J].現代計算機，2014年12月上：30-32 59