一種基于決策樹(shù)的選項(xiàng)識(shí)別方法

雷俊杰 張偉池 余榮 張浩川

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

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

1 相關(guān)概述

1.1研究背景

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

1.2答題卡客觀題選項(xiàng)識(shí)別的缺點(diǎn)和不足

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

1.2.1計(jì)算占空比方法

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

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

1.2.2支持向量機(jī)識(shí)別

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

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

1.3決策樹(shù)簡(jiǎn)介

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

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

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

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

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

于是，基于決策樹(shù)的選項(xiàng)識(shí)別算法步驟如下。

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

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

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

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

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

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

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

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

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

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

3仿真實(shí)驗(yàn)

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

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

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

測(cè)試樣本集中共有15 236張，其中正樣本為7 590張，負(fù)樣本為7 646張。

3.2結(jié)果分析

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

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

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

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

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

3.3識(shí)別效率

本次測(cè)試共15 236份測(cè)試樣本，識(shí)別耗費(fèi)時(shí)間為8 237 ms，平均0.54 ms識(shí)別一道選項(xiàng)，可以說(shuō)，決策樹(shù)的識(shí)別效率是非常高的。

4結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

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

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

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

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

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

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

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

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

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