基于Chi-quare檢驗與詞義分析的試題重復檢測算法

雷虎，任佳

（西安翻譯學院 陜西 西安710105）

基于Chi-quare檢驗與詞義分析的試題重復檢測算法

雷虎，任佳

（西安翻譯學院 陜西 西安710105）

針對無紙化考試系統入庫試題重復檢測問題；提出基于卡方檢驗與詞義分析的試題重復檢測算法，首先自動提取試題的特征信息詞項，利用卡方檢驗改進公式進行特征詞分析并刪除冗余詞；其次，結合中文WordNet詞典對特征詞進行詞義分析，并利用Tf-Idf方法計算入庫試題的特征詞向量與不同題型特征詞的余弦相似度；最后，根據所得相似度值判別該試題是否與題庫試題重復。實驗結果表明，在重復度閥值選取0.8時，算法耗時少、準確性高。

卡方檢驗；特征詞；語義；余弦相似度；試題重復度

基于信息技術的快速發展，無紙化考試系統已經成為傳統考試改革的趨勢和方向。試題的質量和題庫的試題量是無紙化考試系統高質量高效率運行的關鍵；為了適應無紙化考試題庫中試題的數量和質量要求，試題入庫時，由于命題者之間的協調不周，題庫中試題重復時有發生，如入庫試題與試題庫中原有題目重復或組卷后一套測試試卷中因考點相同題型不同導致一試題題目包含另一試題答案等，都將影響無紙化考試系統的運行效果。為了降低題庫中的試題重復度，命題老師在錄入試題時，系統需要自動檢測錄入試題與題庫中試題重復度，根據給定閥值判斷錄入試題在題庫中是否存在重復的試題？而算法的好壞直接影響到入庫試題是否與題庫中試題重復的準確性，因此，對于無紙化考試系統的試題重復度檢測算法的研究至關重要。

試題重復度算法通常分為基于詞頻的相似度算法和基于語義分析相似度算法，邱云飛等人提出的基于詞頻的試題重復度算法沒有將同義特征詞進行比較分析，算法效果不明顯，余弦相似性計算往往與預先給定的閾值有很大關系，而且穩定性不好，當閾值確定不準確將嚴重影響最終結果，因此基于詞頻的相似度檢測算法不能很好進行試題重復度地區分［1-3］；基于語義的相似度算法從試題中抽取TF-IDF值較大的特征詞，然后進行特征詞的位置和詞義分析，從而計算出基于語義和詞頻的試題重復度。此方法對試題重復度檢測的精度較高，但因建立特征詞的語義庫比較困難，黃承慧、李明濤等人結合語義特性進行文本相似度計算，盡管對詞語的語義關系進行了分析，但卻沒有將詞語本身的特性（如詞頻、冗余等）進行分析計算，所得相似度算法復雜，而且效率不高不高［4-7］。

文中提出的基于卡方檢驗的語義相似度算法：預先自動提取出入庫試題的特征信息詞項，利用卡方檢驗進行驗證并刪除冗余詞，結合中文WordNet詞典進行詞義分析和入庫試題與題庫中試題的余弦相似度計算，根據給定閥值，即可得到入庫試題與題庫試題是否存在重復，以此方法計算出試題重復度更加準確。

1　相關技術

1.1Tf-Idf方法

TF-IDF方法是基于特征詞之間相互獨立的一種試題特征詞提取方法，運算效率高。在提取特征詞時，將試題的文本信息按照一定的邏輯次序劃分成一組特征詞序列，再根據所得特征詞分解成相同詞義的候選特征詞序列，利用余弦定理計算候選特征詞序列的相似度，確定候選特征詞構成試題特征詞的概率，提高提取特征詞的準確度。要實現試題文本的重復度檢測，就需要對試題文檔進行向量表示，向量空間模型（Vector Space Model，VSM）是一種經典的文檔向量化表示方法，常用來進行相似度計算的數據模型。任一試題都能提取出一組特征詞，按照特征詞在試題中的重要程度進行權重分配，然后進行規范化正交特征詞向量組成向量空間。所有要錄入的試題文檔都可表示為向量（T1,Q1,T2,Q2,…,Tn,Qn），Ti為特征向量；Qi為特征詞Ti的權重值，通常需要構造一個關于特征詞的權重計算函數用來判斷試題文檔的重復度。

詞頻（Term Frequency，TF），表示一個詞語在一文檔中出現的頻率。TF主要思想：一個詞語w1在文本D中出現的頻率較高而在文本E中出現的頻率較低，w1詞語就具有很好的區分能力，也稱為該詞語貢獻度較大。反文檔頻率（Inverse Document Frequency，IDF）的主要思想是：IDF越大，包含詞語w1的文檔越少，w1具有很好的區分能力。文檔d1和文檔d2的關鍵詞語的TF/IDF分別是w11，w12,...w1n和w21,w22,...,w2n。

1.2Chi-quare檢驗

Chi-quare檢驗是以檢驗統計量χ2分布為基礎一種非參數檢驗：設入庫試題的特征詞行向量為x=（x1,…..,xn），題庫中試題的特征詞列向量y=（y1，。..yp），其中n、p分別是入庫試題和庫中試題所含特征詞的數目。x和y為文檔中含有相同特征詞（或同義特征詞）的相似度。Oi表示觀察頻數，Ei表示期望頻數，n為總頻數，pi為i水平的期望頻率。統計量χ2值越大，表示觀察頻數和期望頻數差額越大；統計量χ2值越小，說明觀察頻數和期望頻數越接近［9］。

當某一試題特征詞t和試題類別k之間的相關程度滿足卡方分布時，m1表示類別k中包含t的文檔頻數，m2表示不在類別k中包含t的文檔頻數，m3表示類別k中不含t的文檔頻數，m4表示不在k中不含t的文檔頻數，則卡方檢驗中χ2的統計量可以表示為：

χ2值越高表明特征詞t與類別k的相關性就越大,式（2）計算時當m1×m4-m2×m3>0時，所得值越大表示特征詞t與試題類別ck中特征詞相關性就越大，特征詞在試題類別k中出現的次數就越多，即特征詞屬于的類別k的概率越大；當值為零時表示試題類別k與特征詞t無關，即特征詞t與試題類別特征詞相互獨立。對于試題的所有試題類型計算特征詞χ2值，并按式（3）進行排序后刪除所有類別的低于閥值的試題特征詞。

當m1×m4-m2×m3<0時，表示特征詞t與屬于類別k的概率較小，但在其他試題類別中出現的概率較大，這時χ2（kt）也較大，表明卡方檢驗的統計量χ2（kt）增大了試題特征詞與類別k的相關性較小而與其他類別相關性較大的特征詞的權重值，而且題庫中同種類別試題數量較大，特征詞構成復雜，入庫試題特征詞與題庫試題特征詞進行卡方驗證時算法運算量較大，不僅提高了算法的復雜度而且影響了算法的準確性。這也是卡方檢驗進行特征詞類別相關性驗證時的不足之處。

特征詞的提取算法直接影響試題重復度檢測的準確度，通過上述的卡方檢驗的不足分析，在提取入庫試題的特征詞時減少題庫類別和綜合考慮特征詞與其他類別試題特征詞的集中度和分散度改進Chi-quare檢驗的χ2計算。

1）建立同類試題模板，確定題庫中各類試題的關鍵特征詞和候選特征詞庫。針對無紙化考試系統的試題類型較少，試題內容較少的特點，在開始構建題庫之前建立各種題型（如選擇、操作、計算題型）模板，并將模板的詞匯構成題庫類別關鍵特征詞向量Ki=｛t1,t2,……tn｝,i為試題的種類，題庫中每道試題除關鍵特征詞外的其他貢獻度較大的詞匯組成候選特征詞Li=｛tf1,tf2,……tfn｝。這樣不僅減小了命題的難度而且大大縮小了題庫試題的特征詞范圍，減少了進行特征詞卡方驗證時的算法復雜度。

2）集中度。集中度表示試題特征詞ti在所屬題型中，同時也存在其他題型中，f（tm）表示入庫試題特征詞t在試題類別km中出現的文檔個數，集中度?計算公式為：

3）分散度。分散度表示試題特征詞ti在所屬題型中，同時也在其他題型中，f（tm）表示入庫試題特征詞t在試題類別km中出現的文檔個數，分散度為f（tm）。

改進Chi-quare檢驗的χ2計算公式如下：

卡方統計量計算的改進公式引入了集中度和分散度兩個因子，并對相同試題類型建立試題模板，形成特定類的特征詞庫，使公式（2）增大了特征詞在某一題型類中出現頻率低而在其他類中出現次數較多的的權值問題得到了解決。

1.3同義特征詞相似度計算

傳統試題重復度算法，特征詞權重采用TF-IDF計算得出，特征詞的同義詞沒有被考慮，導致試題的重復度檢測僅限于字面意思，遺漏了試題同義特征詞的重復度檢測。利用專業工具詞典對試題特征詞加權檢測，算法準確性高，但特征詞典與同義詞典的建立困難；對于試題文本中的任意兩個特征詞，如果在試題中的相同位置可以互相替換而試題表達的意思一致，則認為這兩個特征詞的相似度大，否則相似度小。對詞義是影響特征詞相似度的關鍵因素，特征詞相似程度可以用特征詞的詞義相似度來衡量。

入庫試題的同義特征詞向量Sa=｛（ta1）,f（ta2）,…f（tai）｝和題庫試題的特征詞向量Sb=｛tb1,tb2,……,tbj｝，其中f（t1）表示入庫試題特征詞ta1的所有同義詞向量，同義特征詞向量有中文WordNet詞典提取出來；Sa和Sb中特征詞及同義特征詞向量的相似度能夠確定Sa和Sb分別對應的試題的重復度，基于同義詞的特征詞相似計算中的權值Q由特征詞的TF-IDF值計算，公式如下：

其中，Tfidf（tjk）=Tf（tjk）×Idf（tjk）×γ，Idf（tjk）=log，γ為特征詞的權重值；Tf（tjk）可由特征詞tjk在試題中出現的次數除以題庫試題總數計算。由此可見，TfIdf值與特征詞tjk在試題中的出現次數成正比，與特征詞tjk在題庫中的出現次數成反比。兩個特征詞向量的余弦相似度公式為：

試題特征詞的詞義相似度可用特征詞的同義詞向量的相似度計算，公式如下：

試題的重復度可以由試題同義特征詞向量與題庫中試題特征詞向量的相似度計算，而試題同義特征詞向量與題庫中試題特征詞向量的相似度計算通過同義特征詞向量的相似度Fv和特征詞的余弦相似度Cs進行運算，公式為：

2　算法設計

2.1特征詞提取

首先，試題特征信息預處理。通過詞性標注、語義標注的方法進行特征詞分詞，用特征詞表示試題信息，并完成提取特征詞和刪除停用詞（如的、和、在等詞）。題庫中的試題信息提取特征詞后形成試題的特征詞向量，每個特征詞在試題中的貢獻不同。為了建立特征詞空間向量模型，需要從含有大量特征詞的試題信息中選取貢獻較大的特征詞。

其次，特征詞權重計算。向量空間模型將試題文本信息表示為數字形式，但特征向量維數較大。因此需要對特征詞進行權重排序，選取權重較大的特征詞，將那些高度冗余的或者對試題重復率區分貢獻不大的特征項刪除。選取詞頻高的同義詞為候選特征詞，并對每個同義詞根據詞語相似度加權，給同義詞加權時，如無同義詞，則Sim（ti,tj）值為0。

最后，相似度計算：將優化得到的特征詞及候選特征詞，形成特征詞向量。用卡方檢驗計算ti與其同義詞之間的相似度，將所得Sim值與β比較，若Sim值大于β，則給ti加權并刪除ti同義詞；若Sim值小于β，表示該同義詞無關緊要，可以直接刪除該同義詞；計算完所有詞語的權重后，找出權重最大的前N個詞語作為試題信息的特征詞。

2.2基于卡方檢驗與詞義分析的試題重復檢測算法

卡方檢驗與詞義分析的試題重復檢測算法設計如下:

1）在無紙化考試系統中的試題入庫時，需要對入庫試題預先利用工具軟件NLPIR分詞系統提取試題的特征信息詞項，然后對特征信息詞項與題庫中試題的特征詞進行卡方（χ2）統計量改進公式（5）進行檢驗，刪除冗余詞項，構成試題的同義特征詞行向量Sa=｛ta1,ta2,…tai｝，題庫中所有試題的特征詞樣本向量Sb構成列向量，利用中文WordNet詞典找出行向量中的特征詞Ta1在列向量Sb中的同義特征詞Tbk，形成Sa的同義特征詞向量Sf（a）=｛（ta1）,f（ta2）,…f（tai）｝。

2）將行向量Sa中每個特征詞與列向量Sb的相似度之和除以Sa中特征詞的個數K作為向量Sa與Sb的詞義相似度，用Fv（Sa,Sb）表示。

3）特征詞的TF-IDF權值由公式（7）計算，向量Sa和向量Sb的余弦相似度Cs（Sa,Sb）由公式（7）得出,由公式（6）計算集合Sa和Sb中的元素加權因子Q。

4）由公式（9）計算得到的同義特征詞向量的相似度，即為Sf（a）和Sb代表的試題之間的重復度。

5）以此類推，得出行向量Sa與所有列向量Sb的試題重復度，如存在一個大于給定的試題重復閥值時，則此試題與題庫中試題存在重復，不能入庫；如所有值都在限定的重復度閥值范圍之內，則表明入庫試題與題庫中現有試題沒有重復，可以入庫。

3　算法實現

算法中因試題特征詞在提取和確認時會受試題文本的長度影響，因此，實驗時選擇Access計算機等級考試二級題庫作為實驗數據，題庫中已有1 560道試題?，F有450道試題準備入庫，首先將準備入庫的試題1利用工具軟件NLPIR進行分詞，然后利用卡方檢驗進行特征詞詞義相似度計算，刪除冗余詞。其次利用TF-IDF算法對特征詞進行權值計算，并利用中文WordNet詞典進行語義相似度計算，最后計算出試題文本特征詞與題庫中試題2的相似度，即可得到入庫試題與題庫試題的文本相似度。

表1　試題信息表

入庫試題經過工具軟件NLPIR分詞系統預處理后，得到試題的特征信息詞項格式如表2所示。

在卡方進行特征詞檢驗時，用類別數的倒數、某特征項在某類中文檔覆蓋率的大小、某特征項在某類文本中出現的頻率對檢測試題的特征詞進行降維處理，再利用手工方法進行特征詞重復度準確度評估。實驗過程中，特征詞閥值分別選取試題文本的60%、70%、80%進行特征詞提取，實驗結果表明，當選取試題文本長度的60%的特征詞時，試題特征詞的重復度計算效果最好；當閥值為80%時，因為特征詞較多，增加了算法的復雜度。表3為3種算法在試題重復度閥值取0.6,、0.8、0.9值時認為試題重復的準確率和耗費時間的對比分析表。

表2　預處理后的試題特征信息表

表3　3種算法的重復度檢測結果比較

圖1為3種算法在試題量為450，試題余弦重復度閥值分別取0.6,、0.8、0.9時的算法準確性比較圖，圖2為3種算法在試題量為450，試題余弦重復度閥值分別取0.6,、0.8、0.9時的算法耗費時間比較圖。

圖1　3種算法在不同閥值的準確性分析圖

實驗時，對入庫的450道試題分別運用3種算法進行比較，算法A表示基于詞頻的余弦相似算法，算法B表示基于詞頻和語義相結合的余弦相似算法，算法C表示基于卡方檢驗的試題語義重復度余弦算法；由實驗結果發現：當算法C的特征詞閥值選取試題文本長度的60%，特征詞余弦相似度閥值取0.8時，計算試題重復度準確性最高、耗費時間較短。

圖2　3種算法在不同閥值的耗費時間分析圖

4　結束語

本文利用卡方統計量對試題的特征詞進行了修正，使得特征詞同時兼顧詞頻和詞義要素，為試題的重復度檢測提供重要依據。實驗結果表明根據本文算法計算得出的試題重復度能夠有效減少題庫中試題的重復率，減少了運算的復雜度，并大大提高了運算準確性。目前，無紙化考試系統正處于不斷完善與發展中，文中算法的語義相似度僅從中文WordNet詞典進行語義分析，因涉及同義詞范圍較大導致算法效率不高，后期的研究可根據不同的考試科目建立專業詞典，并根據不同的試題類型設置試題模板，以此為基礎設計更加合理的試題重復度算法。

［1］邱云飛，王 威，劉大有，等．一種詞頻與方差相結合的特征加權方法［J］.計算機應用研究,2012,29（6）:2132-2134.

［2］謝 華，王 健，林鴻飛，等．基于特征選擇的質心向量構建方法［J］.計算機工程,2012,38（1）:195-210.

［3］Selvi P,Gopalan N P.Sentence similarity computation based on WordNet and corpus statistics［C］//roceedings of International Conference on Computational Intelligence and Multimedia Applica-tions．Washington，DC:IEEE Computer Society，2007:9-14．

［4］李明濤,羅軍勇，尹美娟，等．結合詞義的文本特征詞權重計算方法［J］.計算機應用，2012，32（5）:1355－1358.

［5］Guan Hu,Zhou Jingyu,Guo Minyi.A Class-feature-centroid Classifier for Text Categorization［C］//Proc.of 2009 www Conference.Madrid,Spain:IEEE Press,2009:201-210.

［6］黃承慧，印鑒，侯昉．一種結合詞項語義信息和TF-IDF方法的文本相似度量方法［J］.計算機學報,2011,34（5）:856-864.

［7］任姚鵬，陳立潮，張英俊，等．結合語義的特征權重計算方法研究［J］．計算機工程與設計，2010，31（10）:2381-2387．

Algorithm of feature terms semantic similarity based on chi-square test

LEI Hu，REN Jia
（Xi'an Fan Yi university，Xi'an 710105,China）

According to the question repeatability problem of paperless examination.The algorithm of Feature semantic similarity is proposed based on Chi square test.First,automatic extraction of words features information from the question,delete the redundant words by test,Second,analysis feature words semantic under the Chinese WordNet Dictionary,and calculate the cosine similarity of feature vectors by using the TF-IDF method,Finally,according to the result to determine whether the question is put into question database.The experimental result shows that the algorithm is good robustness,high accuracy,high efficiency under the threshold selection 0.8.

chi-square test；feature terms；semantic；cosine similarity；question redundancy

TN919

A

1674－6236（2016）13-0026-04

2015-07-03稿件編號：201507038

陜西省高等教育教學改革研究重點項目（13BZ69）；陜西省教育廳專項科學研究項目（16JK2078）

雷 虎（1976—），男，陜西西安人，碩士。研究方向：數據挖掘與圖像處理。