1、基于K近鄰的手寫數字識別作者：日期：威繆名予律故土考暑期生產實習報告題 目 基于K-近鄰算法的手寫數字識別學院 電子工程學院專業智能科學與技術學生姓名 學 號指導老師提交日期摘要基于k -近鄰算法對經典的手寫數字集 mni st中的測試數據進行分類。用M A TL AB語言編寫代碼，將原始數據讀入,形成三維矩陣,再通過k近鄰算法計算 出待測數據周圍最近的k個數據，將待測數據分為k個數據中最多的類。本次實 驗只是用mnist數據中訓練圖像前6 0 00張，測試圖像前1000張。關鍵詞：k-近鄰算法，數據分類，手寫數字集，mn ist數據集目錄一緒論 51.1 k-近鄰算法的基本概念 51.2 m

2、ni st 數據集 5?二k-近鄰算法6?1.3 1 k近鄰算法的工作原理 62 .2 k 近鄰算法的算法步驟6?2. 3 k-近鄰算法的優缺點 6三k-近鄰算法分類m ni st的具體方法錯誤!未定義書簽。四實驗結果與分析7?4.1 待測圖像 74.2 實驗結果9?4.3 3結果分析？1 1五實驗代碼 17六總結與展望 166. 1總結1?66. 2展望 16參考文獻17?一、緒論1.1手寫數字識別的基本概念手寫數字識別是圖像識別的一個分支，它研究的對象是：如何利用電子計算機自動辨認人手寫的阿拉伯數字。在整個OCR領域中，最為困難的就是脫機手寫字符的識別。到目前為止， 盡管人們在脫機手寫英文

3、、漢字識別的研究中已取得很多可喜成就，但距實用還有一定距離。而在手寫數字識別這個方向上，經過多年研究，研究工作者已經開始 把它向各種實際應用推廣，為手寫數據的高速自動輸入提供了一種解決方案。1. 2手寫數字識別的實際背景字符識別處理的信息可分為兩大類：一類是文字信息，處理的主要是 用各國家、各民族的文字(如：漢字、英文等)書寫或印刷的文本信息，目前在印 刷體和聯機手寫方面技術已趨向成熟，并推出了很多應用系統；另一類是數據信 息，主要是由阿拉伯數字及少量特殊符號組成的各種編號和統計數據，如：郵政編碼、統計報表、財務報表、銀行票據等等，處理這類信息的核心技術是手寫數 字識別。這幾年來我國開始大力推

4、廣的“三金”工程在很大程度上要依賴數據信 息的輸入，如果能通過手寫數字識別技術實現信息的自動錄入，無疑會促進這一事 業的進展。因此，手寫數字的識別研究有著重大的現實意義，一旦研究成功并投 入應用，將產生巨大的社會和經濟效益。1.3手寫數字識別的理論意義手寫數字識別作為模式識別領域的一個重要問題，也有著重要的理論價值：(1)阿拉伯數字是唯一的被世界各國通用的符號，對手寫數字識別的研究基 本上與文化背景無關，這樣就為各國、各地區的研究工作者提供了一個施展才智 的大舞臺。在這一領域大家可以探討，比較各種研究方法。(2)由于數字識別的類別數較小，有助于做深入分析及驗證一些新的理論。 這方面最明顯的例子

5、就是人工神經網絡，相當一部分的人工神經網絡模型都以手 寫數字識別作為具體的實驗平臺，驗證理論的有效性，評價各種方法的優缺點。(3)盡管人們對手寫數字的識別已從事了很長時間的研究 ，并已取得了很多 成果，但到目前為止機器的識別本領還無法與人的認知能力相比，這仍是一個有難度的開放問題。(4 )手寫數字的識別方法很容易推廣到其它一些相關問題，一個直接的應 用是對英文這樣的拼音文字的識別。事實上，很多學者就是把數字和英文字母的 識別放在一塊兒研究的。1.4基于手寫數字識別的典型應用手寫數字識別有著極為廣泛的應用前景， 這也正是它受到世界各國的研究工 作者重視的一個主要原因。下面我們將介紹基于手寫數字識

6、別的應用系統的特殊 要求，以及一些以手寫數字識別技術為基礎的典型應用。(1)手寫數字識別在大規模數據統計中的應用在大規模的數據統計(如:行業年鑒、人口普查等)中，需要輸入大量的數據， 以前完全要手工輸入，則需要耗費大量的人力和物力。近年來在這類工作中采用 O CR技術已成為一種趨勢。因為在這種應用中，數據的錄入是集中組織的，所以往往可以通過專門設計 表格和對書寫施加限制以便于機器的自動識別。 目前國內的大多數實用系統都要 求用戶按指定規范在方格內填寫。另外，這些系統往往采用合適的用戶界面對識 別結果做全面的檢查，最終保證結果正確無誤?？梢钥闯?，這是一類相對容易的 應用，對識別核心算法的要求比

7、較低，是目前國內很多單位應用開發的熱點。(2)手寫數字識別在財務、稅務、金融領域中的應用財務、稅務、金融是手寫數字識別大有可為的又一領域。隨著我國經濟的迅速發展，每天等待處理的財務、稅務報表、支票、付款單等越來越多。如果能把 它們用計算機自動處理，無疑可以節約大量的時間、金錢和勞力。與上面提到的 統計報表處理相比，在這個領域的應用難度更大，原因有:1、對識別的精度要求更 高；2、處理的表格往往不止一種，一個系統應能智能地同時處理若干種表格；3、由于處理貫穿于整個日常工作之中，書寫應盡量按一般習慣(如：不對書寫者 的寫法做限定，書寫時允許寫連續的字串，而不是在固定的方格內書寫)，這樣對識別及預處

8、理的核心算法要求也提高了。(3 )手寫數字識別在郵件分揀中的應用隨著人們生活水平的提高，經濟活動的發展，通信聯系的需求使信函的互換 量大幅度增加，我國函件業務量也在不斷增長 ，預計到2 0 0 0年，一些大城市的 中心郵局每天處理量將高達幾百萬件，業務量的急劇上升使得郵件的分揀自動化 成為大勢所趨。在郵件的自動分揀中，手寫數字識別( OCR)往往與光學條碼識 別、人工輔助識別等手段相結合，完成郵政編碼的閱讀。目前使用量最大的OVC S分揀機的性能指標：OCR拒分率30%, O CR分揀差錯率1.1%。1 . 5手寫數字識別技術展望隨著國家信息化進程的加快，手寫數字識別的應用需求將越來越廣泛，因

9、此 應當加強這方面的研究工作。作者認為，應用系統的性能的關鍵與瓶頸仍然在于 手寫數字識別核心算法性能上，最終目標是研究零誤識率和低拒識率的高速識別 算法。此外，盡早建立反映中國人書寫習慣的、具有國家標準性質的手寫數字樣 本庫也是當務之急。二、k近鄰算法2.1 k 近鄰算法的基本概念k-近鄰算法，即是給定一個訓練數據集，對新的輸入實例，在訓練數據集中 找到與該實例最鄰近的k個數據，這k個數據的多數屬于某個類，就把該輸入實例分類到這個類中。k-近鄰算法中，所選擇的鄰居都是已經正確分類的對象。該 方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所 屬的類別。k-近鄰方法雖然從原理上

10、也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由于 k-近鄰方法主要靠周圍有限的鄰近的樣本，而不是 靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣 本集來說，k-近鄰方法較其他方法更為適合。？k-近鄰算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的 k個最近鄰居，將這些鄰居的屬性的 平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰 居對該樣本產生的影響給予不同的權值（weight）,如權值與距離成正比（組合函 數）。該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很 大，而其他類樣本容量很小時，有可能導致當輸

11、入一個新樣本時，該樣本的K個鄰 居中大容量類的樣本占多數。該算法只計算“最近的”鄰居樣本，某一類的樣本數量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量并不能影響運行結果?？梢圆捎脵嘀档姆椒ǎê驮摌颖揪嚯x小的鄰居權值大）來改進。該方法的另一個不足之處是計算量較大，因為對每一 個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰 點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。2 .2 k近鄰算法的工作原理存在一

12、個樣本數據集合（即訓練樣本集），并且樣本集中每個數據都存在標 簽（即每個數據與所屬分類的對應關系）o輸入沒有標簽的新數據之后，將新數 據的每個特征與樣本集中數據對應的特征進行比較 ，算法將提取出樣本集中特征 最相似數據（最近鄰）的分類標簽。一般選擇樣本數據集中前 K個最相似的數據，k 一般不大于20的整數。2 . 3 k近鄰算法的算法步驟S tep.1計算已知類別數據集中的點與當前點之間的距離;d(xi X2)2 (yi y2)2St ep.2按照距離遞增次序排序；Step.3選取與當前點距離最小的k個點；St e p . 4確定前k個點所在類別的出現頻率；?Ste p .5返回前k個點出現頻

13、 率最高的類別作為當前點的預測分類。2 .4k-近鄰算法的優缺點k-近鄰算法擁有以下優點：精度高、對異常值不敏感、無輸入數據假定？ k-近鄰算法擁有以下缺點：時間復雜度和空間復雜度都很高三 k近鄰算法分類m n i s t的具體方法數據先預處理，將下載的初始圖像數據讀入MA TLAB，并儲存為三維的矩陣 再讀入標簽文件，儲存為二維矩陣，以便后面的使用。手寫數字圖像都為28像素*28像素，對于每一個數字圖像，計算其與每一張 訓練圖像的距離，對于一張待測圖像與訓練圖像，計算每一個像素的差值，如果差 值大于參數4 5 ,則這兩站圖的距離加一，直到 784個像素點全部計算完畢，得 到兩張圖的距離。再用

14、排序找到與該張數字圖像最近的 k張圖像，對距離最近的 k張圖像根據訓練數據標簽進行分類，找到 k張圖像中最多的數字,該張測試數 字圖像即劃分為該數字類。四實驗結果與分析4. 1待測圖像圖4.1 待測第1張圖Q Figure 1 修raj圖4.4待測第4張圖文嘉直播工更圜朗奧圖4. 2待測第2張圖圖4.3待測第3張圖4 .2實驗結果圖4. 5待測第5張圖Figure 1圖4. 6 待測第6張圖| trairJMAGE 3 I 28x2x60000 double無詼顯示具有52428S個以上元素的交里摘要。 -s- - -/LEG 28x28:(10000 double藕顯示具有5242舐個正蔡素

15、的我里摘要.圖4.8測試樣本三維矩陣圖4. 9距離矩陣圖4 .10測試圖像分類結果工柞區(?名稱，m占上b71 biggti colum?jj distance1 HDB RD2JJ IT1JE k i 1 rridgicnum yj numberP值1000600025473,L895J0234;961000x6000 double65661000100100【。5Q.43.20.QZ1ALn10最小值10006000196兀塞656610001001000010導K值1000600010234UTE奈5566 LOOO10010003610出田q righrt10720101072S728

16、right_ra1e0.7280 |072&0 67280row59;。00ske84iasortd_dkt.H1000x6000 double曖k U J Llj-co rt&d_nu.0.0.33A5, M.15.2-036sortedpos.1 OOOjc&OQO doublyVjV JFtestJMAGE2Sx28xl 州緲 doubz.k 京/“test label10)00x1 doubleo gtested rru”， 1x1000 doubfe 09trainJMAGE23x28x60000 曲曲*曖k K 7匚 -train label60000x1 doub/eog丁工，工

17、_1_L7-_1_，_I_圖4.12工作區4.3 結果分析因為所使用的電腦限制，只選取了部分數據集進行實驗，所以準確性會有所 下降，訓練樣本數據的增加在一定程度上可以提升正確率。其次參數的選擇對于實驗結果的影響比較巨大，本次實驗中用到了兩個參數 即計算距離時的參數4 5,以及參數k,兩個參數需要多次實驗以選取最佳參數來 得到最優分類結果。4.4 min i s t數據集Google實驗室的 Corinna Co r te s和紐約大學柯朗研究所的Y an n L eCun建有一個手寫數字數據庫，含有 0- 9的60000張訓練圖像和0 9的1 0 0 0 0測試圖像兩種，每張圖片灰度級都是 8

18、,且每張圖片可以使用一個784大 小的向量表征。下載網址五實驗代碼1主程序C l Ccl e ark=100;%k 距離a=1000; %待測數據個數b=60 0 0; %訓練數據個數lo a d(te s t _IMAG E .mat);%載入待測圖像矩陣lo a d(/ m ni s t_t ra in.ma t ) ;%載入訓練圖像矩陣dist a nce=z e r os (a,b);num b er= z e r os(1, 1 0);tested_n umber= z ero s ( 1 ,a);FID = fopcn ( t10k-la b els. id x 1-u b y t

19、 e，,rz圖像標簽magicnumb e r= f re a d (FID, 2);s i ze=frea d ( FID,2);row s =fr e a d(FI D , 2);c o 1 ums=f r ea d (F I D, 2 );testa b el= f a e ad(F ID);F I D2 = fope n (train- 1 a bel s . i dx1- u b y te , r圖像標簽mag icnumber = fread (FID 2 ,2);s i ze=frea d (F I D2, 2 );rows=fread(F I D2,2);c o 1 u ms=

20、 f read(FID2,2););%載人待測);%載入訓練t ra i n_ label=f r ea d (F I D 2);for i=1 ： afo r j = 1: bfo r p= 1:28fo r q=1:28if (test_ I MAGE(p, q , i )-tr a in_IMAGE (p, q, j )4 5distance( i ,j)= d i s t ance(i ,j)+1;enden dende ndE nd%計算距離矩陣s o rted_dis t ance,s orted _p o si t i on= sort(d i st anc e,2) ;%距離矩

21、陣排序f or i = 1 ： af or q = 1: 10n umber (q)=0;endf orj=1: kfor p= 1 :10if tr a i n _labe 1 (so rted_position ( i , j)=( p -1)number (p) =number (p)+1;ende ndend%計算k距離內數據個類數目s orted _ number ,biggest = s ort(number,2);tested _ num b er( 1 , i) =biggest(10) -1; % 給待測圖像分類e nd r i ght=0;f or i=1 : aif t e sted_n umbe r( i )=tes t _ lab e l(i)ri g h t=right+1;endend righ t _ r ate=right/a;%計算正確率讀取原始數據程序cl cc 1 ear tes t_I MA GE= zero s (28,2 8,1000 0 );FID = f ope n ( t 1 0 k-ima g es. i d x 3- u b y te, r );m a gi c n u mb c r=f r ead (FID,4 );s i ze= f rea