基于決策樹和加權(quán)KNN混合算法的光學(xué)符號(hào)識(shí)別技術(shù)

張巖 李洋 博柳姍 等

摘要：光學(xué)字符識(shí)別是針對(duì)印刷體字符，采用光學(xué)的方式將紙質(zhì)文檔中的文字轉(zhuǎn)換成為黑白點(diǎn)陣的圖像文件，并且通過字符識(shí)別模型將圖像中的文字處理成可編輯的文本格式.本文首先對(duì)樣本數(shù)據(jù)進(jìn)行預(yù)處理，采用局部離群因子法剔除無效數(shù)據(jù)，通過信息增益率計(jì)算各個(gè)自變量相關(guān)性的強(qiáng)弱來找出恰當(dāng)?shù)奶卣?，并將樣本分為五類，建立決策樹法和加權(quán)KNN算法相結(jié)合的混合算法，預(yù)測(cè)每類數(shù)據(jù)的結(jié)果并給出準(zhǔn)確率，將結(jié)果中未識(shí)別的樣本放在所有訓(xùn)練集下再次通過混合算法進(jìn)行訓(xùn)練預(yù)測(cè)，最終總預(yù)測(cè)正確率達(dá)到了96.406%.最后通過混淆矩陣來評(píng)價(jià)模型，結(jié)果表明其拒識(shí)率較低，準(zhǔn)確率較高，訓(xùn)練預(yù)測(cè)時(shí)間較短，具有可行性.

關(guān)鍵詞：決策樹法;加權(quán)KNN算法;局部離群因子法;信息增益率;混淆矩陣

中圖分類號(hào)：TP391.43? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2019）02-0026-04

1 前言

光學(xué)字符識(shí)別是光學(xué)符號(hào)識(shí)別的核心，但是對(duì)于許多類型的機(jī)器學(xué)習(xí)算法來說，將像素模式連接到更高概念的關(guān)系是非常復(fù)雜的，而且用嚴(yán)格的規(guī)則來定義這些模式是很困難的.本文的數(shù)據(jù)來源于公開的UCI的光學(xué)字符識(shí)別數(shù)據(jù)集（數(shù)據(jù)來源：http：//archive.ics.uci.edu/ml/index.php），該數(shù)據(jù)集包含了26個(gè)英文大寫字母的20000個(gè)樣本，每一個(gè)樣本代表光學(xué)圖像中的一個(gè)矩形區(qū)域，該區(qū)域只包含單一字符，每一個(gè)樣本包含16個(gè)自變量和letter目標(biāo)變量，letter指示當(dāng)前樣本是哪一個(gè)字母，我們對(duì)圖像數(shù)據(jù)運(yùn)用一定的統(tǒng)計(jì)方法進(jìn)行初步的統(tǒng)計(jì)描述，分析所給圖像數(shù)據(jù)集，選取恰當(dāng)?shù)奶卣?，通過恰當(dāng)?shù)臄?shù)學(xué)模型來準(zhǔn)確判斷識(shí)別每個(gè)字符，由于每一個(gè)模型不會(huì)是100%最優(yōu)，所以應(yīng)當(dāng)建立適合的評(píng)價(jià)模型對(duì)建立的數(shù)學(xué)模型進(jìn)行性能評(píng)估，主要包括正確率率、拒識(shí)率的評(píng)價(jià)，最后提出模型的性能提升方案，即將所給數(shù)據(jù)中的70%用上述數(shù)學(xué)模型來驗(yàn)證剩下的30%的樣本數(shù)據(jù)，測(cè)試出正確率，分析錯(cuò)誤原因.

2 數(shù)據(jù)預(yù)處理

2.1 數(shù)據(jù)整體分析

對(duì)所有樣本數(shù)據(jù)中的每個(gè)目標(biāo)變量出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)分析可以得出，每個(gè)目標(biāo)變量出現(xiàn)的次數(shù)大致相同且每個(gè)目標(biāo)變量均呈現(xiàn)正態(tài)分布趨勢(shì)，說明分布較好;對(duì)所有樣本數(shù)據(jù)的同一目標(biāo)變量的自變量的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)分析可以得均呈現(xiàn)正態(tài)分布趨勢(shì)，進(jìn)一步說明數(shù)據(jù)分布比較好;通過Excel表進(jìn)行缺失值查找，并未發(fā)現(xiàn)缺失值，說明該數(shù)據(jù)完整;通過Excel表篩選，共發(fā)現(xiàn)1332個(gè)自變量相同并且結(jié)果也相同的樣本，但考慮到該樣本經(jīng)歸一化處理，已經(jīng)被縮放到從0到15的整數(shù)值范圍內(nèi)，所以此處重復(fù)并不代表原數(shù)據(jù)重復(fù)，因而不刪除此處重復(fù)值;通過Excel表篩選，并未發(fā)現(xiàn)自變量相同但目標(biāo)變量不同的樣本，即沒有不一致的數(shù)據(jù).

2.2 局部離群因子法[1]剔除離群數(shù)據(jù)

離群點(diǎn)可分為全局離群點(diǎn)和局部離群點(diǎn)，在很多情況下，局部離群點(diǎn)的挖掘比全局離群點(diǎn)的挖掘更有意義[2].通過計(jì)算每個(gè)樣本的局部離群因子來定量分析某個(gè)樣本的離群程度，有效地剔除離群數(shù)據(jù).具體步驟如下：

Step1：找到離各個(gè)樣本xi距離最近的k個(gè)樣本，其中樣本xij表示距離樣本xi最近的第j個(gè)樣本，樣本xijj表示距離樣本xij最近的第j個(gè)樣本，d（xi，xij）為xi與xij之間的歐氏距離，d（xij，xijj）表示xij與其距離最近的第m個(gè)樣本之間的歐式距離，k取5，i=1，2…20000， j=1，2…k，

計(jì)算并分析所有自變量的信息增益率可得出結(jié)果：a7，a8，a9，a10，a11，a12，a13，a14，a15，a16等屬性取值數(shù)目所帶來的影響大;a2，a3，a4，a5，a6等屬性取值數(shù)目所帶來的影響小.綜上，得出特征變量是：a7，a8，a9，a10，a11，a12，a13，a14，a15，a16.

3.2 對(duì)數(shù)據(jù)進(jìn)行分類

根據(jù)上述分類依據(jù)，運(yùn)用決策樹法將上述十個(gè)特征變量分為2類處理，分類結(jié)果如圖1所示：

3.3 分別對(duì)每類樣本進(jìn)行預(yù)測(cè)

分別用加權(quán)KNN算法及決策樹法來對(duì)每類樣本進(jìn)行預(yù)測(cè)，每類70%的樣本作為訓(xùn)練，30%的樣本作為預(yù)測(cè).以第一類樣本集合為例.

3.3.1 用加權(quán)KNN算法對(duì)第一類樣本進(jìn)行訓(xùn)練預(yù)測(cè)（a14≤1）

KNN算法最早是由Cover和Hart提出的[5]，其核心思想是一個(gè)樣本與離它最近的k個(gè)樣本同屬一個(gè)類別，具有相似的特征.在傳統(tǒng)的KNN算法中，當(dāng)相近的樣本過于密集且每類樣本容量差別過大時(shí)，k值的選取就很重要，有可能導(dǎo)致預(yù)測(cè)新樣本時(shí)，這一區(qū)域內(nèi)容量大的類別起決定性作用[6，7].為避免傳統(tǒng)KNN算法的不足，本文采用加權(quán)KNN算法對(duì)樣本進(jìn)行預(yù)測(cè)，利用高斯函數(shù)來把距離轉(zhuǎn)換為權(quán)值[4].具體步驟如下.

3.3.2 用決策樹算法對(duì)第一類樣本進(jìn)行訓(xùn)練預(yù)測(cè)

利用3.3.1挑選的70%的樣本進(jìn)行訓(xùn)練，并計(jì)算信息增益率，從中選擇信息增益率高的屬性標(biāo)記節(jié)點(diǎn)，最后對(duì)其進(jìn)行剪枝，經(jīng)過反復(fù)調(diào)試參數(shù)、優(yōu)化，得出最佳樹結(jié)構(gòu)（置信度閾為0.20，分枝數(shù)為100）.對(duì)剩余30%的樣本進(jìn)行預(yù)測(cè)，對(duì)于a14≤1所在分支，共有樣本1435個(gè)，預(yù)測(cè)錯(cuò)誤39個(gè)，預(yù)測(cè)正確率為97.282%.

3.3.3 混合預(yù)測(cè)

將上述兩種方法預(yù)測(cè)的結(jié)果進(jìn)行比較，若預(yù)測(cè)結(jié)果相同，則輸出預(yù)測(cè)結(jié)果，若預(yù)測(cè)結(jié)果不同，則劃入未識(shí)別集，進(jìn)行下一步預(yù)測(cè).預(yù)測(cè)結(jié)果如表1：

3.4 對(duì)未識(shí)別樣本的進(jìn)一步預(yù)測(cè)

進(jìn)一步預(yù)測(cè)經(jīng)3.3處理得到801個(gè)未識(shí)別集，為提高識(shí)別正確率降低拒識(shí)率，選取原訓(xùn)練集和集合Sw作為未識(shí)別集的訓(xùn)練集，其中集合Sw為原訓(xùn)練集經(jīng)訓(xùn)練好的決策樹算法、加權(quán)KNN算法進(jìn)行預(yù)測(cè)而得出的未識(shí)別數(shù)據(jù)組成的集合，重復(fù)上述步驟，預(yù)測(cè)結(jié)果如表2所示：

從表2可看出訓(xùn)練集為集合Sw時(shí)預(yù)測(cè)結(jié)果要優(yōu)于訓(xùn)練集為原訓(xùn)練集的預(yù)測(cè)結(jié)果，故選擇集合Sw作為未識(shí)別集的訓(xùn)練集.

4 預(yù)測(cè)結(jié)果分析

隨機(jī)挑選70%的數(shù)據(jù)作為已知數(shù)據(jù)進(jìn)行學(xué)習(xí)和訓(xùn)練，將剩下的30%隨機(jī)數(shù)進(jìn)行預(yù)測(cè)驗(yàn)證.調(diào)用本文提出的混合預(yù)測(cè)模型對(duì)其預(yù)測(cè)，預(yù)測(cè)結(jié)果如下表3.

該模型識(shí)別光學(xué)字符錯(cuò)誤率僅為1.525%，正確率達(dá)到96.406%，拒識(shí)率為2.07%，通過混淆矩陣計(jì)算出Kappa系數(shù)為0.97396，也表明此模型具有很好的一致性.

該模型中將策樹算法和加權(quán)KNN算法預(yù)測(cè)不一致的數(shù)據(jù)計(jì)入未識(shí)別集中，但對(duì)于未別集的預(yù)測(cè)的正確率較低，而且拒識(shí)率過高，所以未識(shí)別集的預(yù)測(cè)屬于此模型的短板，可通過降低未識(shí)別集的拒識(shí)率來對(duì)此模型進(jìn)行改進(jìn).通過統(tǒng)計(jì)得出預(yù)測(cè)錯(cuò)誤和拒絕識(shí)別主要出現(xiàn)在B，D，E，F(xiàn)，H，N，O，Q，R，S，U，X等12個(gè)字母中，也可從這些字母入手，來降低拒識(shí)率和提高正確率.

5 結(jié)論

5.1 對(duì)初始數(shù)據(jù)進(jìn)行預(yù)處理，通過計(jì)算信息增益率的計(jì)算找出恰當(dāng)?shù)奶卣髯兞?，并利用決策樹法和加權(quán)KNN算法建立混合預(yù)測(cè)的數(shù)學(xué)模型.

5.2 對(duì)數(shù)據(jù)進(jìn)行分類預(yù)測(cè)，不僅避免了相近數(shù)據(jù)的影響，還大大減少了運(yùn)算次數(shù)，節(jié)約了時(shí)間;在預(yù)測(cè)之后，將全部樣本分成識(shí)別集和未識(shí)別集，并分別給出來兩個(gè)集合的識(shí)別正確率和拒識(shí)率，避免了過模擬現(xiàn)象，該計(jì)算結(jié)果更為精確，訓(xùn)練時(shí)間更短.

5.3 通過混淆矩陣來評(píng)價(jià)模型，模型拒識(shí)率較低，準(zhǔn)確率較高，訓(xùn)練預(yù)測(cè)時(shí)間較短，具有可行性.

參考文獻(xiàn)：

〔1〕Breuning M M.LOF： Identifying density-based local outliers [J].ACM SIGMOD Record，2000，29（2）：93-104.

〔2〕胡彩平，秦小麟.一種基于密度的局部離群點(diǎn)檢測(cè)算法DLOF[J].計(jì)算機(jī)研究與發(fā)展，2010，47（12）：2110-2116.

〔3〕袁梅宇.數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2014.

〔4〕戴健，丁治明.基于MapReduce快速kNN Join方法[J].計(jì)算機(jī)學(xué)報(bào)，2015，38（1）：99-108.

〔5〕Cover T M， Hart P E. Nearest neighbor pattern classification. IEEE Trans Inf Theory IT-13（1）：21-27[J]. IEEE Transactions on Information Theory， 1967， 13（1）：21-27.

〔6〕Sun S， Huang R. An adaptive k-nearest neighbor algorithm[C]// Seventh International Conference on Fuzzy Systems and Knowledge Discovery. IEEE， 2010：91-94.

〔7〕Ghosh A K， Azen S P. On optimum choice of k in nearest neighbor classification[J]. Computational Statistics & Data Analysis， 2006， 50（11）：3113-3123.