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

張巖 李洋 博柳姍 等

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

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

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

1 前言

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

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

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

對所有樣本數(shù)據(jù)中的每個目標(biāo)變量出現(xiàn)的次數(shù)進行統(tǒng)計分析可以得出，每個目標(biāo)變量出現(xiàn)的次數(shù)大致相同且每個目標(biāo)變量均呈現(xiàn)正態(tài)分布趨勢，說明分布較好;對所有樣本數(shù)據(jù)的同一目標(biāo)變量的自變量的出現(xiàn)次數(shù)進行統(tǒng)計分析可以得均呈現(xiàn)正態(tài)分布趨勢，進一步說明數(shù)據(jù)分布比較好;通過Excel表進行缺失值查找，并未發(fā)現(xiàn)缺失值，說明該數(shù)據(jù)完整;通過Excel表篩選，共發(fā)現(xiàn)1332個自變量相同并且結(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ù)

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

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

計算并分析所有自變量的信息增益率可得出結(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 對數(shù)據(jù)進行分類

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

3.3 分別對每類樣本進行預(yù)測

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

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

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

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

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

3.3.3 混合預(yù)測

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

3.4 對未識別樣本的進一步預(yù)測

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

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

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

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

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

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

5 結(jié)論

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

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

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

參考文獻(xiàn)：

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

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

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

〔4〕戴健，丁治明.基于MapReduce快速kNN Join方法[J].計算機學(xué)報，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.