雷俊杰 張偉池 余榮 張浩川

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

關(guān)鍵詞：機器學(xué)習(xí)；決策樹；選項識別；特征提??；答題卡

1 相關(guān)概述

1.1研究背景

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

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

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

1.2.1計算占空比方法

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

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

1.2.2支持向量機識別

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

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

1.3決策樹簡介

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

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

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

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

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

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

（1）構(gòu)造訓(xùn)練樣本和測試樣本。

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

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

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

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

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

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

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

（7）將所有的訓(xùn)練樣本的特征向量構(gòu)造成特征矩陣的形式。

（8）將特征矩陣數(shù)據(jù)輸入決策樹訓(xùn)練算法中，構(gòu)造用于識別選項的決策樹模型。 在上面的步驟中，有兩個參數(shù)是至關(guān)重要的，一個是選項區(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)驗，我們可以知道，當Ⅳ越大的時候，填涂的空間信息就會保存得越好，越能夠表征選項的填涂特征，識別的準確率會越高，但計算的復(fù)雜度會增加，效率下降并有可能導(dǎo)致決策樹的過擬合；而當閾值T越大的時候，識別的嚴格程度就會越高，這樣一來導(dǎo)致的情況就是，對于填涂的識別會越來越準確，但對于未填涂的識別錯誤也會越來越高，反之亦然。也就是說，若n固定，將閾值作為橫軸，識別正確率作為縱軸畫出來的圖形，應(yīng)該是一個類似小山坡的形狀；而當n增加的時候，由于表征性能更好，畫出來的圖形應(yīng)該是比前者的形狀更“高”。那么，應(yīng)該大約會在n=3，4，也就是選項分成9個或16個矩形，閾值T為0.6左右的時候，構(gòu)造出來的決策樹識別性能會是最好的，因為在這個區(qū)間內(nèi)，小矩形具有足夠好的表征性能，而閾值的也是靠近中間的值，兩者達到了對正樣本和負樣本都不偏不倚的平衡狀態(tài)。下面我們通過仿真實驗來驗證猜想。

3仿真實驗

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

3.1構(gòu)造訓(xùn)練樣本集和測試樣本集

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

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

3.2結(jié)果分析

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

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

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

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

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

3.3識別效率

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

4結(jié)語

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

[參考文獻]

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

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

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

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

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

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

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

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

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

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

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

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