基于KNN的手寫體數(shù)字識別實驗案例設(shè)計

安利 柳泉 張晗

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

關(guān)鍵詞： KNN算法 ?數(shù)字識別 ?Python語言 實驗案例

中圖分類號：G202 ? ? ? ? ? 文獻標(biāo)識碼：A

隨著信息時代的到來，人們對于信息處理的要求更加嚴格，不僅要有非常高的準(zhǔn)確率，還要有非?？斓奶幚硭俣取Ｊ謱戵w數(shù)字識別一直是多年來的研究熱點，也是圖像處理和模式識別領(lǐng)域中的研究內(nèi)容[1]，手寫體數(shù)字識別被應(yīng)用在大規(guī)模數(shù)據(jù)統(tǒng)計中。例如，人口普查、成績單錄入、行業(yè)年檢、財務(wù)報表錄入等應(yīng)用中。手寫數(shù)字識別是利用機器或計算機自動辨認手寫體阿拉伯?dāng)?shù)字的一種技術(shù)，是光學(xué)字符識別技術(shù)的一個分支。由于阿拉伯?dāng)?shù)字通用，并且數(shù)字識別和處理也常是一些自動化系統(tǒng)的核心和關(guān)鍵，所以對手寫體數(shù)字識別的研究通用性強，且意義重大。

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

1、實驗思想

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

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

2、實驗指導(dǎo)

手寫體數(shù)字識別是一個比較完整的工程實踐過程，需要經(jīng)歷學(xué)習(xí)研究、方案論證、系統(tǒng)設(shè)計、實現(xiàn)調(diào)試、測試標(biāo)定、設(shè)計總結(jié)等過程。因此在實驗過程中需加強對學(xué)生的引導(dǎo)：

1）學(xué)習(xí)矩陣以及向量在Python環(huán)境中的表示，了解圖像數(shù)據(jù)轉(zhuǎn)換為矩陣的過程。

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

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

4）注意k值的選擇，k值通常是采用交叉檢驗來確定（以k=1為基準(zhǔn)）經(jīng)驗規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根。

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

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

3、實驗方案

1）實驗數(shù)據(jù)

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

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

2）K最近鄰計算模型

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

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

4）核心分類函數(shù)[10]，使用Python語言實現(xiàn)（圖5）

5）結(jié)果分析

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

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

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

接著，選擇前K個作鄰居，通過投票法，決定當(dāng)前樣本的標(biāo)簽，即分類。具體過程是，統(tǒng)計k個鄰居的各分類標(biāo)簽訓(xùn)練圖像個數(shù)，哪個分類標(biāo)簽里的鄰居個數(shù)最多，那么當(dāng)前樣本即為該分類。

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

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

5、結(jié)束語

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

參考文獻

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

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

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

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

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

[6]. 期刊：鐘元生，曹權(quán)，APP開發(fā)教學(xué)案例設(shè)計[J].軟件工程師，2015年，18卷第8期：65-68

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

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

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

[10]. 期刊：趙明洪，張?zhí)t，王正敏，Python程序代碼相似度檢測[J].現(xiàn)代計算機，2014年12月上：30-32 59