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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、,'r');%載入待測圖像標簽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');%載入訓練圖像標簽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