一種基于決策樹的選項識別方法

雷俊杰 張偉池 余榮 張浩川

摘要：文章將機器學習中的決策樹算法和圖像處理技術相結合，提出了一種基于決策樹的選項識別方法，該方法首先需要通過人工標注的方式從答題卡中抽取選項構造訓練集和測試集，訓練集和測試集都包括填涂的選項和未填涂的選項兩類，接著將訓練集中的答題卡選項切割成n個大小相同的小矩形，通過計算這些小矩形的占空比并通過設定閾值的方式將其離散化成{0，l}中的其中一個值，這些值將作為選項的填涂空間信息特征，然后將n個小矩形的離散后的值相加作為表征選項整體填涂信息特征，再將這n+l個特征構成特征向量的形式，去構造選項識別的決策樹，最后，用測試集測試決策樹的準確率和速度。經(jīng)過仿真測試，在權衡識別準確率和識別效率之后，得出選項切割的最佳個數(shù)和最佳離散化閾值，在該參數(shù)的設置下，決策樹的識別性能具有滿意的結果。該方法實現(xiàn)方便、簡單、易于理解，并具有很高的準確率和很快的識別速度。

關鍵詞：機器學習；決策樹；選項識別；特征提?。淮痤}卡

1 相關概述

1.1研究背景

隨著科學技術的日益發(fā)展，傳統(tǒng)的教育行業(yè)也發(fā)生著巨大的變革，從以前的客觀題需要人工手動批改，到后來使用光學標記閱讀機去識別選項答案，效率得到了大大的提升。但光學標記閱讀機雖然速度快，準確性高，但也存在著一些問題[1-3]：（1）設備成本高，一臺普通的光學標記閱讀機需要好幾萬的成本。（2）答題卡需要定制。（3）光學標記閱讀機不能保存數(shù)字圖像。基于上面的原因，出現(xiàn)了數(shù)碼閱卷的方式，該方式只需要將試卷掃描到電腦上，通過一定的算法就可實現(xiàn)識別，通用性更好并且不需要額外的識別硬件。

1.2答題卡客觀題選項識別的缺點和不足

雖然數(shù)碼閱卷取得了長足的進展，但在客觀題選項識別上仍然存在著一些不盡人意的地方。當前選項識別方法一般分為兩種，一是簡單通過計算占空比的方法，二是使用支持向量機（SVM）識別[4-5]。下面分別簡單介紹兩種方法的實現(xiàn)。

1.2.1計算占空比方法

該方法步驟為[67]：（1）判斷像素是否為黑色像素，若是的話，則累加。（2）求得該選項的占空比，公式為：占空比=黑色像素總和/選項矩形面積。（3）判斷計算出來的古空比是否大于某一設定閾值，若大于，則輸出為填涂，否則，輸出為未填涂。

這種方法實現(xiàn)簡單，識別速度快，但由于需要設置固定的閾值，因此對一些填涂不全的選項會出現(xiàn)誤識的結果，整體準確率不是太高。

1.2.2支持向量機識別

在王勝春的論文《基于SVM的信息識別系統(tǒng)》中，提出了用支持向量機識別選項的方法，該方法步驟為[8]（1）定義各識別塊與水平定位塊的相對坐標模板。（2）對水平定位區(qū)域進行圖像分割。（3）獲取各水平定位塊重心。（4）根據(jù)各信息識別塊與水平定位塊的相對坐標模塊，獲取各信息識別塊初步識別范圍。（5）根據(jù)各信息識別塊初步識別范圍及所定義的環(huán)境因子構建輸入向量集。（6）采用SVM對輸入向量集進行訓練與識別，獲取識別結果。

該方法使用了較多的參數(shù)，使得實現(xiàn)起來具有一定的困難性，并且論文中提出的識別方法和論文中的識別系統(tǒng)耦合度過高。

1.3決策樹簡介

決策樹是一種簡單、高效的機器學習分類算法，它通俗易懂，跟人的思考方式很像，構建出來的樹圖形清晰明了，同時它也是其他復雜的機器學習算法，如boost、隨機森林的基礎。

從技術上講，一個決策樹由一系列節(jié)點和分支組成，而節(jié)點和子節(jié)點之間形成分支，節(jié)點代表著決策過程中所考慮的屬性，而不同屬性值形成不同分支。為了利用決策樹對某一事例作出決策，可以利用這一事例的屬性值并由樹根向下搜索直至葉節(jié)點，葉節(jié)點上即包含著決策結果[9-10]。

決策樹的構造包含以下4步[11]： （l）選擇度量集合分類不純度的計算方法，一般有熵、吉尼不純度、錯分類不純度3種可選擇。（2）遍歷集合的每個特征，根據(jù)度量選擇分類效果最好的屬性對集合進行劃分。（3）遞歸地構造整棵決策樹。（4）使用剪枝策略修建決策樹，防止其過擬合。2算法介紹

決策樹具有良好的數(shù)學理論支持，方便調(diào)試，構造的模型易于理解，因此很適合用于答題卡選項的識別[12]。

構造決策樹需要對象的特征，之前的論文中，選項的特征提取做法是[1]：對選項分割后計算各個小矩形的占空比，并以此為特征；這種做法是比較適合的，因為只有一個總體的占空比的做法，會丟失了填涂的空間信息。這就好比，在一個房間里，有許許多多本書，如果我們只知道房間內(nèi)有多少本書，那么當我們要找一本書的時候就非常麻煩，但如果我們將這些書分門別類，分成一塊區(qū)域一塊區(qū)域去管理，那樣就既可以保留了書本的數(shù)量信息，又可以保留書本的空間信息，尋找起來就會快很多。而將選項劃分為多個小區(qū)域的做法，就做到了既保留了填涂的總體信息，又保留了填涂的空間信息。但決策樹不適用于連續(xù)的數(shù)據(jù)，因此在這里我們需要將占空比離散化，離散化的方法也非常簡單，就是設置一閾值，若占空比高于該閾值則將特征值置為l，否則為0。這個離散化的過程，其實很像我們?nèi)讼冉虝嬎銠C怎么樣才算填涂的選項，但填涂的選項有太多的情況，不可能一一給計算機詳細地羅列出來，既然如此，那我們就先教會計算機一個狹小的區(qū)域怎么樣才算填涂，而一個狹小的區(qū)域往往是容易判斷的，然后計算機再通過統(tǒng)計每個狹小區(qū)域的特征來判斷整個選項區(qū)域是否填涂。于是，一個復雜的問題就變成了一個個小的問題。以往的占空比閾值判斷方法往往會丟失選項填涂的空間信息，它只能夠得到選項大致填涂了多少，而不會知道這些填涂是分散的還是集中的；現(xiàn)在通過將選項分割成一個個小的區(qū)域，其特征值代表了區(qū)域的填涂信息，能夠在整體上保留填涂的空間信息。不過，由于特征值只會代表單個區(qū)域信息，我們還需要一個特征來表征整個區(qū)域的填涂信息，這個特征可以通過對所有小區(qū)域的特征求和來得到。

于是，基于決策樹的選項識別算法步驟如下。

（1）構造訓練樣本和測試樣本。

（2）設定劃分個數(shù)Ⅳ和離散化閾值T。

（3）將訓練樣本中的選項圖像分為NAI大小相同的小區(qū)域，逐一計算每個區(qū)域黑色像素的占空比。

（4）根據(jù)離散化閾值將占空比離散化，方法為：占空比大于閾值，特征值置為l；否則，特征值置為0。

（5）對該選項所有區(qū)域的特征值求和。

（6）根據(jù)上面的特征信息構造該選項圖像的特征值向量，最后輸出的特征值向量大概會是這樣的形式：

Vector=[1，1，1，0，0，1，0，1，…，ll，l]

其中，II為前面的1的個數(shù)之和，最后的1是該選項的類別（這里1代表“填涂”，0代表“未填涂”）。

（7）將所有的訓練樣本的特征向量構造成特征矩陣的形式。

（8）將特征矩陣數(shù)據(jù)輸入決策樹訓練算法中，構造用于識別選項的決策樹模型。 在上面的步驟中，有兩個參數(shù)是至關重要的，一個是選項區(qū)域劃分成的矩形個數(shù)Ⅳ，一個是閾值To -般的選項圖像大小長度在40像素內(nèi)，高度在20像素內(nèi)，為了方便計算，在這里使得n=m，即選項區(qū)域劃分為nXn個大小相同的小矩形，n=2，3，4，5，玎若再大的話，會使到分割后區(qū)域過小而失去表征的作用。而根據(jù)經(jīng)驗，閾值可選擇0.4-0.8的值。根據(jù)直觀的經(jīng)驗，我們可以知道，當Ⅳ越大的時候，填涂的空間信息就會保存得越好，越能夠表征選項的填涂特征，識別的準確率會越高，但計算的復雜度會增加，效率下降并有可能導致決策樹的過擬合；而當閾值T越大的時候，識別的嚴格程度就會越高，這樣一來導致的情況就是，對于填涂的識別會越來越準確，但對于未填涂的識別錯誤也會越來越高，反之亦然。也就是說，若n固定，將閾值作為橫軸，識別正確率作為縱軸畫出來的圖形，應該是一個類似小山坡的形狀；而當n增加的時候，由于表征性能更好，畫出來的圖形應該是比前者的形狀更“高”。那么，應該大約會在n=3，4，也就是選項分成9個或16個矩形，閾值T為0.6左右的時候，構造出來的決策樹識別性能會是最好的，因為在這個區(qū)間內(nèi)，小矩形具有足夠好的表征性能，而閾值的也是靠近中間的值，兩者達到了對正樣本和負樣本都不偏不倚的平衡狀態(tài)。下面我們通過仿真實驗來驗證猜想。

3仿真實驗

本論文實現(xiàn)算法所用到的操作系統(tǒng)是Win7專業(yè)版，cpu為AMD A8 PRO，數(shù)據(jù)仿真的平臺為vs20lO+opencv2.4.10，論文中關于效率的數(shù)據(jù)皆基于此，不同平臺得到的結果會有所不同。在opencv中，已經(jīng)有實現(xiàn)決策樹的開源算法[5]而本論文也是在該算法的基礎上進行調(diào)試和改進的。

3.1構造訓練樣本集和測試樣本集

訓練樣本集的構造對決策樹的生成非常重要。構造的訓練樣本集需要包含兩部分，一是正樣本集（填涂的選項圖像集），二是負樣本集（未填涂的選項圖像集）。本論文從十多份不同的試卷中抽取了具有代表性的7 259張選項圖像，其中正樣本集共3 674張，負樣本集共3 621張。

測試樣本集中共有15 236張，其中正樣本為7 590張，負樣本為7 646張。

3.2結果分析

當設置n=2（即選項分為大小相等的4個小矩形），閾值為0.4-0.64時，通過上面的方法提取特征，構造決策樹，并對測試集進行測試，結果統(tǒng)計如表1所示。

從上面的表格可以看出，在測試樣本中，當閾值較低時，正樣本的錯誤個數(shù)也較少，而負樣本的錯誤個數(shù)則很多，因此總正確率不是很高；隨著閾值增加，負樣本識別正確率上升；而后面由于閾值過高導致了正樣本識別正確率降低，這跟前面的推測是一樣的。

同樣地，增大n的值，記錄識別結果。n=3，4，5時的閾值與準確率關系如圖1所示。

可以看到，當n=3時總體的準確率要比n=2時高，而n=4時總體準確率又比n=3時高，并且當n=4，閾值為0.62時準確率達到最高值，為9 9.7%。而當n再增加的時候，會使得切割的矩形過小，增加決策樹的復雜度，并增加額外的時間，但跟前面的性能所差無幾，因此，在n=4時所提取的特征已經(jīng)能夠很好地表征填涂的信息，也具有很好的識別率。測試樣本在n=4，離散化閾值為0.62時構造出來的決策樹識別結果的詳細準確率如表2所示。

從上面的數(shù)據(jù)可以看到，正樣本和負樣本都達到了較高的正確率。因此，將選項分割為4X4的小矩形，求出其占空比，并根據(jù)閾值為0.62將占空比離散化作為特征，構造決策樹進行識別的方法是有效可行的。

3.3識別效率

本次測試共15 236份測試樣本，識別耗費時間為8 237 ms，平均0.54 ms識別一道選項，可以說，決策樹的識別效率是非常高的。

4結語

科技的發(fā)展日新月異，傳統(tǒng)的紙質(zhì)考試，人工批改的方式也在科技發(fā)展的潮流下發(fā)生著深刻的變革，越來越多的學校、考試都采用了數(shù)碼自動化的批改方式；同時，圖像識別，機器學習等算法也成為當下流行的研究熱點；機器學習中的決策樹算法具有方便、簡潔、易于理解準確度高等特點。本文在決策樹的基礎上，結合改進的特征提取方法，提出一種答題卡選項識別算法，并通過仿真試驗得出了特征提取中的最佳參數(shù)：n=4，T=0.62；在該參數(shù)組合下，構造出來的決策樹具有良好的識別準確率和識別效率。該算法兼容性高，能夠很方便地移植到當前的答題卡選項識別系統(tǒng)上。

[參考文獻]

[1]楊燕青，彭延軍基于灰度圖像的答題卡識別技術[J]山東科技大學學報（自然科學版），2009（3）：99-102

[2]高育鵬，楊俊，何廣軍.基于圖像識別的自動閱卷系統(tǒng)研究[J]現(xiàn)代電子技術，2006（ 22）：119-120.

[3]周萬珍，鄭廣，王健霞.數(shù)字圖像處理技術在客觀中的應用[J]數(shù)學的實踐與認識，2006 （8）：243-246

[4]鄭廣，秦敏基于圖像識別的客觀題閱卷研究[J]儀器儀表學報，2006 （6）：273-274，791

[5]阮秋琦數(shù)字圖像處理學[M]北京：電子工業(yè)出版社，2001.

[6]劉洪濤，孫天澤嵌入式系統(tǒng)技術與設計[M].北京：人民郵電出版社，2011

[7]蘇錦秀基于圖像識別的答題卡研究[J].現(xiàn)代技術，2008 （22）：119-120

[8]王勝春.基于SVM的信息卡識別系統(tǒng)[D].長沙：湖南師范大學，2008

[9]周海濤，韓曉軍.基于數(shù)字圖像處理的答題卡識別方法研究[J].電腦知識與技術，2008 （10）：197-199

[lO]JohnD，蔡競峰，蔡自興.決策樹技術及其當前研究方向[J]控制工程，2005 （1）：15-18

[11]彼得哈靈頓機器學習實戰(zhàn)[M]李銳，李鵬，曲亞東，等，譯北京：人民郵電出版社，2013.

[12]加里布拉德斯基，阿德里安.學習Opencv[M]._于-仕琪，劉瑞禎，譯北京：清華大學出版社，2016