胡恩博，余臘生

（1.中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙 410083；2.湖南第一師范學(xué)院信息科學(xué)與工程學(xué)院，湖南長沙 410205）

一種基于中文分詞的主觀題自動(dòng)評(píng)分優(yōu)化算法研究*

胡恩博1，2，余臘生1

（1.中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙 410083；2.湖南第一師范學(xué)院信息科學(xué)與工程學(xué)院，湖南長沙 410205）

論述了一種基于中文分詞的主觀題自動(dòng)評(píng)分優(yōu)化算法的設(shè)計(jì)與實(shí)現(xiàn)，詳細(xì)介紹了中文分詞技術(shù)及實(shí)現(xiàn)方法，對(duì)單詞串匹配度從單詞長度、單詞詞形、單詞順序及影響因子四個(gè)方面進(jìn)行算法設(shè)計(jì)與分析，最后進(jìn)行實(shí)驗(yàn)測試，測試結(jié)果表明采用此優(yōu)化算法進(jìn)行的自動(dòng)評(píng)分準(zhǔn)確率有顯著提升.

中文分詞；自動(dòng)評(píng)分；相似度

考試是高校教育中的一個(gè)重要環(huán)節(jié)，考試后的閱卷評(píng)分工作，特別是涉及到全校性質(zhì)的基礎(chǔ)課程的閱卷評(píng)分工作給教師帶來沉重負(fù)擔(dān)的同時(shí)，還會(huì)帶來效率低下，以及人為因素影響的公平公正問題.

現(xiàn)今社會(huì)的考試系統(tǒng)對(duì)于客觀題的評(píng)分技術(shù)已經(jīng)相當(dāng)成熟，但在主觀題的評(píng)分上由于受到很多因素，如算法復(fù)雜度、人類自然語言等的影響，還存在很多缺陷.現(xiàn)有研究基于最優(yōu)指派問題的匈牙利算法［1］能較好地解決主觀題評(píng)分的準(zhǔn)確率問題，但運(yùn)算速度有待提高；基于LSA（Latent Semantic Analysis，用于文本語義分析的潛在語義分析算法）的算法又過于繁瑣，難于實(shí)現(xiàn).

基于此，本文設(shè)計(jì)了一種易實(shí)現(xiàn)、且運(yùn)算效率佳的基于中文分詞的主觀題自動(dòng)評(píng)分優(yōu)化算法，其原理圖如圖1所示，經(jīng)測驗(yàn)，該算法能滿足一般通用課程的主觀題評(píng)分準(zhǔn)確與效率可行的要求.

圖1 算法原理圖

1 中文分詞技術(shù)

隨著國內(nèi)計(jì)算機(jī)的發(fā)展與應(yīng)用的普及，中文分詞的發(fā)展與應(yīng)用也突飛猛進(jìn)，衍生出了很多不同的算法，歸納其特點(diǎn)可分為：字符串匹配分詞算法、理解分詞算法、統(tǒng)計(jì)分詞算法及語義分詞算法四類［2］.

其基本原理是將答案文件先做去標(biāo)點(diǎn)、表格及圖形的初始預(yù)處理，從《知網(wǎng)》知識(shí)庫中獲取各詞的概念定義［3］，然后利用分詞技術(shù)，對(duì)其進(jìn)行分詞處理，得到單詞串文件.其原理如下圖2所示.

圖2 分詞處理流程

預(yù)處理與分詞技術(shù)已經(jīng)比較成熟，以分詞技術(shù)為例，目前網(wǎng)絡(luò)上有很多開源的分詞軟件，如跨平臺(tái)的IKAnalyzer、Paoding和LibMMSeg等，以及基于Windows平臺(tái)的FreeICTCLAS和CRF等，圖3為利用基于跨平臺(tái)的Paoding開源分詞技術(shù)對(duì)“中華人民共和國萬歲”這一語句進(jìn)行分詞計(jì)算的結(jié)果示例.

圖3 分詞示例

2 單詞串匹配度計(jì)算

單詞匹配度是衡量單詞串A與單詞串B相似程度的標(biāo)準(zhǔn).匹配度越高表明兩個(gè)單詞串的意思越相近.單詞串匹配度是用來判斷考生答案文件和標(biāo)準(zhǔn)答案文件的相近程度.

單詞串匹配中語義相似度的算法一般分為兩類：基于語義詞典的詞語相似度算法和基于語料庫的詞語語義相似度算法［4］.這兩種方法共同的問題是過于依賴各自的詞典以及語料庫.

基于人工智能的理論思想，本文設(shè)計(jì)了一種從單詞串長度、順序和形狀三者相結(jié)合的多層次比較算法，在提升了單詞串匹配度計(jì)算的性能的同時(shí)，對(duì)主觀題評(píng)分的準(zhǔn)確率有明顯改善.

3 算法實(shí)現(xiàn)

對(duì)于主觀題的閱卷，教師一般先觀察答案的字?jǐn)?shù)夠不夠，有沒有足夠的篇幅，這一問題可描述為單詞串的長度相似計(jì)算.其次是看有沒有關(guān)鍵點(diǎn)，把這一問可分解描述為單詞串的詞形相似、詞序相似及詞點(diǎn)相似問題.將這三者綜合，便是人工閱卷評(píng)分的思想.

以上四點(diǎn)可用四個(gè)算法解決，四個(gè)算法彼此約束，綜合評(píng)分，現(xiàn)將算法實(shí)現(xiàn)如下：

3.1 單詞串A長度與單詞串B長度相似計(jì)算算法

式（1）中用Length（StringA）來表示標(biāo)準(zhǔn)答案文件經(jīng)過預(yù)處理和分詞技術(shù)分詞后得到的單詞串A，Length（StringB）表示考生答案文件經(jīng)過同樣處理后得到的單詞串B，String-LengthSimila表示兩者的長度相似度.

例1：Question：中國的全稱是？

A1：中華人民（不完全得分答案）

A2：中華人民共和國（標(biāo)準(zhǔn)答案）

A3：北京人民大會(huì)堂（不得分答案）

以上標(biāo)準(zhǔn)答案A2經(jīng)過分詞處理后得到的分詞結(jié)果見圖3，則可知Length（StringA）＝5，假設(shè)考生答案文件為A1，則Length（StringB）＝3，若考生答案文件為A2，則Length（StringB）＝5，由此得到StringLengthSimila分別為0.75和1.

由此可見，StringLengthSimila值越大，考生答案就與標(biāo)準(zhǔn)答案越相近.當(dāng)然，如果僅憑這一項(xiàng)來評(píng)分就有可能出現(xiàn)完全錯(cuò)誤的評(píng)分結(jié)果，例如如果考生答案是A3，分詞后的結(jié)果為：北京｜北京人｜人民｜大會(huì)｜大會(huì)堂，得到的長度為5，如果僅憑長度評(píng)分的話，這個(gè)完全錯(cuò)誤的答案會(huì)得到滿分.

3.2 單詞串A與單詞串B詞形相似計(jì)算算法

式（2）中用CharSimila表示單詞串A與單詞串B的詞形相似度，SimilaChar表示兩者相似詞形的個(gè)數(shù)，MaxLength表示兩者最大的單詞個(gè)數(shù).同樣以例1為例，由此算法可知A1的詞形相似度約為0.6，A2的詞形相度為1，A3的詞形相似度約為0.2.

由此可見，CharSimila的值越大，兩個(gè)單詞串就越相似，這樣考生答案就越接近標(biāo)準(zhǔn)答案.

3.3 單詞串A與單詞串B的詞序相似計(jì)算算法

式（3）中用SortSimila表示單詞串A與單詞串B的詞序相似度，COUNT用來統(tǒng)計(jì)兩個(gè)單詞串的逆序數(shù)，Only1用來計(jì)算單詞串A與單詞串B中都出現(xiàn)并且僅出現(xiàn)1次的單詞的集合.以例1為例，

由此算法可知A1、A2及A3的SortSimila均為1，顯然SortSimila針對(duì)此一類答案的評(píng)分是有很大偏差的，但是否就該完全無視SortSimila呢，顯然不能，比如學(xué)生的答案是A4（美利堅(jiān)合眾國），則Only1＜1，故SortSimila＝0，針對(duì)這一類答案，SortSimila的評(píng)判就尤為準(zhǔn)確與重要.

3.4 字符串A與字符串B的綜合相似計(jì)算算法

式（4）中α、β、γ分別為字符串長度、詞形及詞序相似度的影響因子，可根據(jù)不同的考試科目特點(diǎn)自定義，最后綜合三者評(píng)分.

4 測試結(jié)果

依據(jù)以上算法，在點(diǎn)上對(duì)本文提及的四個(gè)答案進(jìn)行綜合相似度計(jì)算，對(duì)α、β、γ分別賦值0.2、0.7、0.1，則計(jì)算到的四個(gè)答案的綜合相似度A1＝0.67、A2＝1、A3＝0.42、A4＝0.07.

在面上，通過4個(gè)實(shí)驗(yàn)進(jìn)行測試，試卷題目分別為4個(gè)Office簡答題，標(biāo)準(zhǔn)答案控制在100字內(nèi)，每個(gè)實(shí)驗(yàn)回收電子試卷50份，與使用原算法的實(shí)驗(yàn)結(jié)果進(jìn)行比對(duì)，結(jié)果如表1所示：

表1 原算法與優(yōu)化算法準(zhǔn)確率測試比對(duì)

通過以上測試結(jié)果可知，優(yōu)化后的算法準(zhǔn)確率在實(shí)驗(yàn)1、2和4上有明顯提高，但在實(shí)驗(yàn)3上提高百分點(diǎn)不大.究其原因，在人工查看實(shí)驗(yàn)3的每個(gè)答案后，發(fā)現(xiàn)是由于實(shí)驗(yàn)3的答案在SortSimila度上已經(jīng)很接近標(biāo)準(zhǔn)答案，故評(píng)分差距不大.

5 結(jié)語

本文算法由3個(gè)小算法綜合而成，評(píng)分在綜合考慮長度、詞形與詞序相似度的同時(shí)，還要根據(jù)考試科目的特性相對(duì)設(shè)置影響因子α、β、γ的值.一般而言，影響因子β的值所占比重要遠(yuǎn)遠(yuǎn)高于α、γ，即詞形相似度的比重應(yīng)充分考慮.本文在詞形相似度較高的情況下的評(píng)分效果與原算法差距不大，依然有改進(jìn)的空間.

［1］張旭輝，朱宏輝.最優(yōu)指派問題匈牙利算法的探討與C＋＋實(shí)現(xiàn)［J］.技術(shù)交流，2004，（5）：67－69.

［2］張啟宇，朱玲，張雅萍.中文分詞算法研究綜述［J］.情報(bào)探索，2008，（11）：53－56.

［3］張以利.匈牙利算法在主觀題自動(dòng)批閱中的應(yīng)用研究［J］.南京工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2007，（2）：73－75.

［4］李玉紅，柴林燕，張琪.結(jié)合分詞技術(shù)與語句相似度的主觀題自動(dòng)判分算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，（11）：251－254.

（責(zé)任編校：晴川）

An Optim ization Algorithm of Automatic Grading for Subjective Questions Based on Chinese W ords Segmentation

HU Enbo1，2，YU Lasheng1
（1.School of Information Science and Engineering，Central South University，Changsha Hunan 410083，China；2.School of Information Science and Engineering，Hunan First Normal University，Changsha Hunan 410205，China）

The paper discusses the design and implementation ofan optimization algorithm ofautomatic grading for subjective questions based on Chinese words segmentation，introduces the Chinese segmentation technology and implementation method in detail，designs and analyses the word stringmatching algorithm from four aspects of the word length，word formation，word order and influencing factors，and finally the experiment is tested.The test results show that automatic grading accuracy is significantly improved with this optimization algorithm.

Chinese words segmentation；automatic grading；similarity

TP301

A

1008－4681（2014）05－0059－03

2014－06－11

胡恩博（1980－），男，湖北咸寧人，湖南第一師范學(xué)院信息科學(xué)與工程學(xué)院講師，中南大學(xué)信息科學(xué)與工程學(xué)院碩士生.研究方向：軟件工程.