安利 柳泉 張晗

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

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

中圖分類(lèi)號(hào)：G202 ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

1、實(shí)驗(yàn)思想

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

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

2、實(shí)驗(yàn)指導(dǎo)

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

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

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

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

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

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

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

3、實(shí)驗(yàn)方案

1）實(shí)驗(yàn)數(shù)據(jù)

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

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

2）K最近鄰計(jì)算模型

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

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

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

5）結(jié)果分析

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

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

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

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

最后，統(tǒng)計(jì)識(shí)別的正確率，并思考對(duì)算法的改進(jìn)。算法的改進(jìn)可從兩個(gè)方面考慮：一是性能問(wèn)題：KNN構(gòu)造模型很簡(jiǎn)單，但在對(duì)測(cè)試樣本分類(lèi)地的系統(tǒng)開(kāi)銷(xiāo)大，因?yàn)橐獟呙枞坑?xùn)練樣本并計(jì)算距離。二是訓(xùn)練的時(shí)間：能否大幅減少訓(xùn)練樣本量，同時(shí)又保持分類(lèi)精度。4、實(shí)驗(yàn)考核

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

5、結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

[9]. 電子文獻(xiàn)： https：//www.kaggle.com/datasets[OL]

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