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

1、暑期生產(chǎn)實習(xí)報告 題 目 基于K-近鄰算法的手寫數(shù)字識別 學(xué) 院 電子工程學(xué)院 專 業(yè) 智能科學(xué)與技術(shù) 學(xué)生姓名 學(xué) 號 指導(dǎo)老師 提交日期 摘要基于k-近鄰算法對經(jīng)典的手寫數(shù)字集mnist中的測試數(shù)據(jù)進行分類。用MATLAB語言編寫代碼，將原始數(shù)據(jù)讀入，形成三維矩陣，再通過k近鄰算法計算出待測數(shù)據(jù)周圍最近的k個數(shù)據(jù)，將待測數(shù)據(jù)分為k個數(shù)據(jù)中最多的類。本次實驗只是用mnist數(shù)據(jù)中訓(xùn)練圖像前6000張，測試圖像前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)缺點6三 k-近鄰算法分類mnist的具體方法6四 實驗結(jié)果與分析74.1 待測圖像74.2 實驗結(jié)果94.3結(jié)果分析11五 實驗代碼11六 總結(jié)與展望166.1 總結(jié)166.2 展望16參考文獻171、 緒論 1.1 手寫數(shù)字識別的基本概念手寫數(shù)字識別是圖像識別的一個分支，它研究的對象是：如何利用電子計算機自動辨認(rèn)人手寫的阿拉伯?dāng)?shù)字。在整個OCR領(lǐng)域中，最為困難的就是脫機手寫字符的識別。到目前為止，盡管人們在脫機手寫英文、漢字識別的研究中已取得很多可喜成就，但距實用還有一定距離。而在手寫數(shù)字識別這個方向上，經(jīng)過多年研究，研究工

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

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

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

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

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

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

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

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

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

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

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

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

15、張訓(xùn)練圖像和0-9的10000測試圖像兩種，每張圖片灰度級都是8，且每張圖片可以使用一個784大小的向量表征。五 實驗代碼1主程序clccleark=100;%k距離a=1000;%待測數(shù)據(jù)個數(shù)b=6000;%訓(xùn)練數(shù)據(jù)個數(shù)load('test_IMAGE.mat');%載入待測圖像矩陣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'

16、,'r');%載入待測圖像標(biāo)簽magicnumber=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(

17、FID2);for i=1:a for j=1:b for p=1:28 for q=1:28 if (test_IMAGE(p,q,i)-train_IMAGE(p,q,j)>45 distance(i,j)=distance(i,j)+1; end end end endEnd%計算距離矩陣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

18、,j)=(p-1) number(p)=number(p)+1; end endend%計算k距離內(nèi)數(shù)據(jù)個類數(shù)目 sorted_number,biggest=sort(number,2); tested_number(1,i)=biggest(10)-1;%給待測圖像分類endright=0;for i=1:a if tested_number(i)=test_label(i) right=right+1; endendright_rate=right/a;%計算正確率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