基于K近鄰的手寫數(shù)字識(shí)別

1、暑期生產(chǎn)實(shí)習(xí)報(bào)告 題 目 基于K-近鄰算法的手寫數(shù)字識(shí)別 學(xué) 院 電子工程學(xué)院 專 業(yè) 智能科學(xué)與技術(shù) 學(xué)生姓名 學(xué) 號(hào) 指導(dǎo)老師 提交日期 摘要基于k-近鄰算法對(duì)經(jīng)典的手寫數(shù)字集mnist中的測(cè)試數(shù)據(jù)進(jìn)行分類。用MATLAB語(yǔ)言編寫代碼，將原始數(shù)據(jù)讀入，形成三維矩陣，再通過(guò)k近鄰算法計(jì)算出待測(cè)數(shù)據(jù)周圍最近的k個(gè)數(shù)據(jù)，將待測(cè)數(shù)據(jù)分為k個(gè)數(shù)據(jù)中最多的類。本次實(shí)驗(yàn)只是用mnist數(shù)據(jù)中訓(xùn)練圖像前6000張，測(cè)試圖像前1000張。關(guān)鍵詞：k-近鄰算法，數(shù)據(jù)分類，手寫數(shù)字集，mnist數(shù)據(jù)集目錄一 緒論51.1 k-近鄰算法的基本概念51.2 mnist數(shù)據(jù)集5二 k-近鄰算法62.1 k-近鄰算法的

2、工作原理62.2 k-近鄰算法的算法步驟62.3 k-近鄰算法的優(yōu)缺點(diǎn)6三 k-近鄰算法分類mnist的具體方法6四 實(shí)驗(yàn)結(jié)果與分析74.1 待測(cè)圖像74.2 實(shí)驗(yàn)結(jié)果94.3結(jié)果分析11五 實(shí)驗(yàn)代碼11六 總結(jié)與展望166.1 總結(jié)166.2 展望16參考文獻(xiàn)171、 緒論 1.1 手寫數(shù)字識(shí)別的基本概念手寫數(shù)字識(shí)別是圖像識(shí)別的一個(gè)分支，它研究的對(duì)象是：如何利用電子計(jì)算機(jī)自動(dòng)辨認(rèn)人手寫的阿拉伯?dāng)?shù)字。在整個(gè)OCR領(lǐng)域中，最為困難的就是脫機(jī)手寫字符的識(shí)別。到目前為止，盡管人們?cè)诿摍C(jī)手寫英文、漢字識(shí)別的研究中已取得很多可喜成就，但距實(shí)用還有一定距離。而在手寫數(shù)字識(shí)別這個(gè)方向上，經(jīng)過(guò)多年研究，研究工

3、作者已經(jīng)開(kāi)始把它向各種實(shí)際應(yīng)用推廣，為手寫數(shù)據(jù)的高速自動(dòng)輸入提供了一種解決方案。1.2 手寫數(shù)字識(shí)別的實(shí)際背景 字符識(shí)別處理的信息可分為兩大類：一類是文字信息，處理的主要是用各國(guó)家、各民族的文字（如：漢字、英文等）書(shū)寫或印刷的文本信息，目前在印刷體和聯(lián)機(jī)手寫方面技術(shù)已趨向成熟，并推出了很多應(yīng)用系統(tǒng)；另一類是數(shù)據(jù)信息，主要是由阿拉伯?dāng)?shù)字及少量特殊符號(hào)組成的各種編號(hào)和統(tǒng)計(jì)數(shù)據(jù)，如：郵政編碼、統(tǒng)計(jì)報(bào)表、財(cái)務(wù)報(bào)表、銀行票據(jù)等等，處理這類信息的核心技術(shù)是手寫數(shù)字識(shí)別。這幾年來(lái)我國(guó)開(kāi)始大力推廣的“三金”工程在很大程度上要依賴數(shù)據(jù)信息的輸入，如果能通過(guò)手寫數(shù)字識(shí)別技術(shù)實(shí)現(xiàn)信息的自動(dòng)錄入，無(wú)疑會(huì)促進(jìn)這一事業(yè)的

4、進(jìn)展。因此，手寫數(shù)字的識(shí)別研究有著重大的現(xiàn)實(shí)意義，一旦研究成功并投入應(yīng)用，將產(chǎn)生巨大的社會(huì)和經(jīng)濟(jì)效益。1.3 手寫數(shù)字識(shí)別的理論意義手寫數(shù)字識(shí)別作為模式識(shí)別領(lǐng)域的一個(gè)重要問(wèn)題，也有著重要的理論價(jià)值：（1）阿拉伯?dāng)?shù)字是唯一的被世界各國(guó)通用的符號(hào)，對(duì)手寫數(shù)字識(shí)別的研究基本上與文化背景無(wú)關(guān)，這樣就為各國(guó)、各地區(qū)的研究工作者提供了一個(gè)施展才智的大舞臺(tái)。在這一領(lǐng)域大家可以探討，比較各種研究方法。（2）由于數(shù)字識(shí)別的類別數(shù)較小，有助于做深入分析及驗(yàn)證一些新的理論。這方面最明顯的例子就是人工神經(jīng)網(wǎng)絡(luò)，相當(dāng)一部分的人工神經(jīng)網(wǎng)絡(luò)模型都以手寫數(shù)字識(shí)別作為具體的實(shí)驗(yàn)平臺(tái)，驗(yàn)證理論的有效性，評(píng)價(jià)各種方法的優(yōu)缺點(diǎn)。（3

5、）盡管人們對(duì)手寫數(shù)字的識(shí)別已從事了很長(zhǎng)時(shí)間的研究，并已取得了很多成果，但到目前為止機(jī)器的識(shí)別本領(lǐng)還無(wú)法與人的認(rèn)知能力相比，這仍是一個(gè)有難度的開(kāi)放問(wèn)題。 （4）手寫數(shù)字的識(shí)別方法很容易推廣到其它一些相關(guān)問(wèn)題，一個(gè)直接的應(yīng)用是對(duì)英文這樣的拼音文字的識(shí)別。事實(shí)上，很多學(xué)者就是把數(shù)字和英文字母的識(shí)別放在一塊兒研究的。1.4 基于手寫數(shù)字識(shí)別的典型應(yīng)用手寫數(shù)字識(shí)別有著極為廣泛的應(yīng)用前景，這也正是它受到世界各國(guó)的研究工作者重視的一個(gè)主要原因。下面我們將介紹基于手寫數(shù)字識(shí)別的應(yīng)用系統(tǒng)的特殊要求，以及一些以手寫數(shù)字識(shí)別技術(shù)為基礎(chǔ)的典型應(yīng)用。（1） 手寫數(shù)字識(shí)別在大規(guī)模數(shù)據(jù)統(tǒng)計(jì)中的應(yīng)用在大規(guī)模的數(shù)據(jù)統(tǒng)計(jì)（如：行

6、業(yè)年鑒、人口普查等）中，需要輸入大量的數(shù)據(jù)，以前完全要手工輸入，則需要耗費(fèi)大量的人力和物力。近年來(lái)在這類工作中采用OCR技術(shù)已成為一種趨勢(shì)。因?yàn)樵谶@種應(yīng)用中，數(shù)據(jù)的錄入是集中組織的，所以往往可以通過(guò)專門設(shè)計(jì)表格和對(duì)書(shū)寫施加限制以便于機(jī)器的自動(dòng)識(shí)別。目前國(guó)內(nèi)的大多數(shù)實(shí)用系統(tǒng)都要求用戶按指定規(guī)范在方格內(nèi)填寫。另外，這些系統(tǒng)往往采用合適的用戶界面對(duì)識(shí)別結(jié)果做全面的檢查，最終保證結(jié)果正確無(wú)誤?？梢钥闯?，這是一類相對(duì)容易的應(yīng)用，對(duì)識(shí)別核心算法的要求比較低，是目前國(guó)內(nèi)很多單位應(yīng)用開(kāi)發(fā)的熱點(diǎn)。（2） 手寫數(shù)字識(shí)別在財(cái)務(wù)、稅務(wù)、金融領(lǐng)域中的應(yīng)用財(cái)務(wù)、稅務(wù)、金融是手寫數(shù)字識(shí)別大有可為的又一領(lǐng)域。隨著我國(guó)經(jīng)濟(jì)的迅

7、速發(fā)展，每天等待處理的財(cái)務(wù)、稅務(wù)報(bào)表、支票、付款單等越來(lái)越多。如果能把它們用計(jì)算機(jī)自動(dòng)處理，無(wú)疑可以節(jié)約大量的時(shí)間、金錢和勞力。與上面提到的統(tǒng)計(jì)報(bào)表處理相比，在這個(gè)領(lǐng)域的應(yīng)用難度更大，原因有：1、對(duì)識(shí)別的精度要求更高；2、處理的表格往往不止一種，一個(gè)系統(tǒng)應(yīng)能智能地同時(shí)處理若干種表格；3、由于處理貫穿于整個(gè)日常工作之中，書(shū)寫應(yīng)盡量按一般習(xí)慣（如：不對(duì)書(shū)寫者的寫法做限定，書(shū)寫時(shí)允許寫連續(xù)的字串，而不是在固定的方格內(nèi)書(shū)寫），這樣對(duì)識(shí)別及預(yù)處理的核心算法要求也提高了。（3） 手寫數(shù)字識(shí)別在郵件分揀中的應(yīng)用隨著人們生活水平的提高，經(jīng)濟(jì)活動(dòng)的發(fā)展，通信聯(lián)系的需求使信函的互換量大幅度增加，我國(guó)函件業(yè)務(wù)量也在

8、不斷增長(zhǎng)，預(yù)計(jì)到2000年，一些大城市的中心郵局每天處理量將高達(dá)幾百萬(wàn)件，業(yè)務(wù)量的急劇上升使得郵件的分揀自動(dòng)化成為大勢(shì)所趨。在郵件的自動(dòng)分揀中，手寫數(shù)字識(shí)別（OCR）往往與光學(xué)條碼識(shí)別、人工輔助識(shí)別等手段相結(jié)合，完成郵政編碼的閱讀。目前使用量最大的OVCS分揀機(jī)的性能指標(biāo)：OCR拒分率30%，OCR分揀差錯(cuò)率1.1%。1.5 手寫數(shù)字識(shí)別技術(shù)展望隨著國(guó)家信息化進(jìn)程的加快，手寫數(shù)字識(shí)別的應(yīng)用需求將越來(lái)越廣泛，因此應(yīng)當(dāng)加強(qiáng)這方面的研究工作。作者認(rèn)為，應(yīng)用系統(tǒng)的性能的關(guān)鍵與瓶頸仍然在于手寫數(shù)字識(shí)別核心算法性能上，最終目標(biāo)是研究零誤識(shí)率和低拒識(shí)率的高速識(shí)別算法。此外，盡早建立反映中國(guó)人書(shū)寫習(xí)慣的、具有

9、國(guó)家標(biāo)準(zhǔn)性質(zhì)的手寫數(shù)字樣本庫(kù)也是當(dāng)務(wù)之急。2、 k近鄰算法2.1 k-近鄰算法的基本概念k-近鄰算法，即是給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的k個(gè)數(shù)據(jù)， 這k個(gè)數(shù)據(jù)的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例分類到這個(gè)類中。k-近鄰算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。 k-近鄰方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于k-近鄰方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，k-近

10、鄰方法較其他方法更為適合。k-近鄰算法不僅可以用于分類，還可以用于回歸。通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比（組合函數(shù)）。該算法在分類時(shí)有個(gè)主要的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。 該算法只計(jì)算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本，或者這類樣本很靠近目標(biāo)樣本。無(wú)論怎樣，數(shù)量并不能影響運(yùn)行結(jié)果?？梢圆?/p>

11、用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(jìn)。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。2.2 k近鄰算法的工作原理存在一個(gè)樣本數(shù)據(jù)集合（即訓(xùn)練樣本集），并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽（即每個(gè)數(shù)據(jù)與所屬分類的對(duì)應(yīng)關(guān)系）。輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)之后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，算法將提取出樣本集中特征最相似數(shù)據(jù)（最近鄰）

12、的分類標(biāo)簽。一般選擇樣本數(shù)據(jù)集中前K個(gè)最相似的數(shù)據(jù)，k一般不大于20的整數(shù)。2.3 k近鄰算法的算法步驟Step.1 計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離；Step.2 按照距離遞增次序排序；Step.3 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)；Step.4 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率；Step.5 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類。2.4 k-近鄰算法的優(yōu)缺點(diǎn)k-近鄰算法擁有以下優(yōu)點(diǎn):精度高、對(duì)異常值不敏感、無(wú)輸入數(shù)據(jù)假定 k-近鄰算法擁有以下缺點(diǎn)：時(shí)間復(fù)雜度和空間復(fù)雜度都很高三 k近鄰算法分類mnist的具體方法數(shù)據(jù)先預(yù)處理，將下載的初始圖像數(shù)據(jù)讀入MATLAB，并儲(chǔ)存為

13、三維的矩陣，再讀入標(biāo)簽文件，儲(chǔ)存為二維矩陣，以便后面的使用。手寫數(shù)字圖像都為28像素*28像素,對(duì)于每一個(gè)數(shù)字圖像，計(jì)算其與每一張訓(xùn)練圖像的距離，對(duì)于一張待測(cè)圖像與訓(xùn)練圖像，計(jì)算每一個(gè)像素的差值，如果差值大于參數(shù)45，則這兩站圖的距離加一，直到784個(gè)像素點(diǎn)全部計(jì)算完畢，得到兩張圖的距離。再用排序找到與該張數(shù)字圖像最近的k張圖像，對(duì)距離最近的k張圖像根據(jù)訓(xùn)練數(shù)據(jù)標(biāo)簽進(jìn)行分類，找到k張圖像中最多的數(shù)字，該張測(cè)試數(shù)字圖像即劃分為該數(shù)字類。四 實(shí)驗(yàn)結(jié)果與分析4.1 待測(cè)圖像圖4.1 待測(cè)第1張圖圖4.2待測(cè)第2張圖圖4.3 待測(cè)第3張圖圖4.4 待測(cè)第4張圖圖4.5 待測(cè)第5張圖圖4.6 待測(cè)第6張

14、圖4.2 實(shí)驗(yàn)結(jié)果圖4.7 訓(xùn)練樣本三維矩陣圖4.8測(cè)試樣本三維矩陣圖4.9 距離矩陣圖4.10 測(cè)試圖像分類結(jié)果圖4.11 正確率圖4.12 工作區(qū)4.3結(jié)果分析因?yàn)樗褂玫碾娔X限制，只選取了部分?jǐn)?shù)據(jù)集進(jìn)行實(shí)驗(yàn)，所以準(zhǔn)確性會(huì)有所下降，訓(xùn)練樣本數(shù)據(jù)的增加在一定程度上可以提升正確率。其次參數(shù)的選擇對(duì)于實(shí)驗(yàn)結(jié)果的影響比較巨大，本次實(shí)驗(yàn)中用到了兩個(gè)參數(shù)，即計(jì)算距離時(shí)的參數(shù)45，以及參數(shù)k，兩個(gè)參數(shù)需要多次實(shí)驗(yàn)以選取最佳參數(shù)來(lái)得到最優(yōu)分類結(jié)果。4.4 mnist數(shù)據(jù)集Google實(shí)驗(yàn)室的Corinna Cortes和紐約大學(xué)柯朗研究所的Yann LeCun建有一個(gè)手寫數(shù)字?jǐn)?shù)據(jù)庫(kù)，含有0-9的60000

15、張訓(xùn)練圖像和0-9的10000測(cè)試圖像兩種，每張圖片灰度級(jí)都是8，且每張圖片可以使用一個(gè)784大小的向量表征。下載網(wǎng)址 五 實(shí)驗(yàn)代碼1主程序clccleark=100;%k距離a=1000;%待測(cè)數(shù)據(jù)個(gè)數(shù)b=6000;%訓(xùn)練數(shù)據(jù)個(gè)數(shù)load(test_IMAGE.mat);%載入待測(cè)圖像矩陣load(mnist_train.mat);%載入訓(xùn)練圖像矩陣distance=zeros(a,b);number=zeros(1,10);tested_number=zeros(1,a);FID = fopen(t10k-labels.idx1-ubyte,r);%載入待測(cè)圖像標(biāo)簽magicnumber=

16、fread(FID,2);size=fread(FID,2);rows=fread(FID,2); colums=fread(FID,2);test_label=fread(FID);FID2 = fopen(train-labels.idx1-ubyte,r);%載入訓(xùn)練圖像標(biāo)簽magicnumber=fread(FID2,2);size=fread(FID2,2);rows=fread(FID2,2); colums=fread(FID2,2);train_label=fread(FID2);for i=1:a for j=1:b for p=1:28 for q=1:28 if (tes

17、t_IMAGE(p,q,i)-train_IMAGE(p,q,j)45 distance(i,j)=distance(i,j)+1; end end end endEnd%計(jì)算距離矩陣sorted_distance,sorted_position = sort(distance,2);%距離矩陣排序for i=1:a for q=1:10 number(q)=0; end for j=1:k for p=1:10 if train_label(sorted_position(i,j)=(p-1) number(p)=number(p)+1; end endend%計(jì)算k距離內(nèi)數(shù)據(jù)個(gè)類數(shù)目 so

18、rted_number,biggest=sort(number,2); tested_number(1,i)=biggest(10)-1;%給待測(cè)圖像分類endright=0;for i=1:a if tested_number(i)=test_label(i) right=right+1; endendright_rate=right/a;%計(jì)算正確率2讀取原始數(shù)據(jù)程序clccleartest_IMAGE=zeros(28,28,10000);FID = fopen(t10k-images.idx3-ubyte,r);magicnumber=fread(FID,4);size=fread(FID,4);rows=fread(FID,4); colums=fread(FID,4);