基于增量式貝葉斯模型的中文問句分類研究

王小林,鎮麗華,楊思春,邰偉鵬,鄭 嘯

(安徽工業大學計算機科學與技術學院,安徽馬鞍山243002)

基于增量式貝葉斯模型的中文問句分類研究

王小林,鎮麗華,楊思春,邰偉鵬,鄭 嘯

(安徽工業大學計算機科學與技術學院,安徽馬鞍山243002)

固定訓練集生成的分類器性能不理想且不能跟蹤用戶需求,為此,提出一種將增量式貝葉斯思想用于問句分類的方法。采用遺傳算法選取最優特征子集優化分類器,從而避免訓練集特征過分冗余,使分類器在學習過程中動態地擴大訓練集并修改分類器參數。在對問句進行分類時,提取問句的疑問詞、句法結構、疑問意向詞和疑問意向詞在知網的首項義原作為分類特征。為了驗證增量式貝葉斯方法的有效性,從語料庫中隨機抽取不同規模的問句構成增量集,基于不同的增量集對同一測試集中的問句進行分類。實驗結果表明,增量式貝葉斯分類器較樸素貝葉斯分類器有更高的分類精度,大類和小類的準確率分別達到90.2%和76.3%,在提高準確率的同時優化了運行效率。

問句分類;問答系統;增量式貝葉斯;樸素貝葉斯;改進貝葉斯;遺傳算法

1 概述

自動問答系統一般包括3個主要部分:問句分析,信息檢索和答案抽取[1]。幾乎所有的問答系統在問句分析階段都有問句分類這個過程,問句分類就是根據問句答案的類型將問句分到相應的語義類別中去。問句分類作為問答系統的一個重要子模塊,它的重要性不言而喻,可以說問句分類的準確性直接影響了整個問答系統的性能。

問句分類方法大致分為2種:基于規則的方法和基于統計的方法?；谝巹t的方法簡單、準確率高,但存在的主要問題是建立規則庫的工作量大,人工負擔重,而且靈活性也不高[2]。因此,當前基于統計的方法占主導地位,分類算法也層出不窮,具有代表性的有樸素貝葉斯、K-近鄰、最大熵和支持向量機等。樸素貝葉斯分類器以其結構簡單、效率高、抗干擾能力強已成為分類研究的重要方法。

在中文問句分類研究上,貝葉斯分類器受到廣泛應用并且效果顯著,但大多數仍是基于固定訓練集訓練,這顯然不能滿足現在爆炸式增長的信息需求。針對這一情況,本文提出將增量式學習[3]的思想用于中文問句分類研究,并用遺傳算法[4]選取最優特征子集優化分類器的方法。

2 樸素貝葉斯問句分類模型

對問句分類的研究大多還是借鑒文本分類的思想,假設問句中的詞與詞之間相互獨立,將句中的詞作為特征并進行符號化表示,使用樸素貝葉斯公式找到問句所屬的語義類別其數學模型簡化表示為:

其中,Ci表示問句類別變量;q1,q2,…,qn為問句經過分詞、去除停用詞后的特征項;n為特征項個數,式中:

樸素貝葉斯分類是根據訓練樣本的類先驗概率和特征的類條件概率計算后驗概率,從而預測測試問句的類別。如果訓練樣本沒有很好的完備性,那得出的準確率就可能很低。事實上,有限大小的訓練集不可能有很完備的數據,很多領域的自動問答系統也是分批獲取數據的。

3 增量貝葉斯相關理論

3.1 貝葉斯增量學習模型

Bayes概率是測量某個個體對某一未知事件發生的置信度,測量個體根據先驗信息和現有的統計數據,用概率的方法預測未知事件發生的可能性,正是這種充分利用先驗信息的特性使之成為增量學習的最佳模型。

3.2 增量分類思想

有限的訓練集不能完全表示所有問句的分布情況,因此,需要找到一種方法使得訓練集更加完備,從而優化分類效果。增量學習的思想就是將測試集中未標注類別的問句用現有分類器進行分類,對分類結果運用某種嚴格的選擇策略進行判斷,符合加入條件的問句實例加入到訓練集擴充訓練數據。用新加入的問句實例修正當前分類器參數,使得各類別的類先驗概率和各特征項的類條件概率更加精確,從而使分類器的分類效果更好。

4 特征提取

問句分類和文本分類類似,都是通過文本中包含的特征信息來確定文本所屬類別,但也有所區別[6]。問句一般都較短,所包含的信息比較少,沒有足夠的上下文環境,這就使得問句分類比文本分類更加復雜。因此,通過提取更優特征信息來提高問句分類準確率就顯得尤為重要。本文共選取了4種分類特征:問句疑問詞,句法結構,疑問意向詞以及疑問意向詞在知網中的首項義原。下面以問句“迪克·克拉克的生日是什么時候?”為例對本文的特征抽取方法進行說明。

4.1 疑問詞

疑問詞對于問句有很好的區分作用[7],是最重要的分類特征。對問句進行分詞和詞性標注后得到“迪克·克拉克|nh;的|u;生日|n;是|v;什么|r;時候|n”,選取詞性標記為“|r”的詞作為疑問詞。該問句的疑問詞特征為{什么}。

4.2 句法結構

句法分析是分析問句中詞與詞之間的關系,若2個詞之間有弧相連,說明他們之間有依存關系,弧發起的詞依存于弧指向的詞。利用句法分析的結果找出問句的主干,可以減少修飾性詞匯對問句分類的干擾。本文采用哈爾濱工業大學社會計算與信息檢索研究中心的句法分析器對示例問句進行句法分析,結果如圖1所示,提取出的問句主干為“生日 是什么時候”,該問句的句法結構特征為{生日,是,什么,時候}。

圖1 句法分析結果

4.3 疑問意向詞

疑問意向詞是個能說明“問句到底要問什么”這一含義的概念。按照漢語問句的表達習慣,疑問詞附近的名詞最能表達整個問句的語義信息,并且疑問詞右邊的名詞信息比疑問詞左邊的名詞信息更加豐富和有效。采用以下步驟提取疑問意向詞:

(1)把詞性為“n、nd、nh、ni”等各類名詞統一標注為“n”;

(2)從疑問詞開始往右搜索,把第一個搜索到的標記為“n”的詞作為疑問意向詞,若疑問詞右邊沒有標記為“n”的詞,則轉步驟(3);

(3)從疑問詞開始往左搜索,把第一個搜索到的標記為“n”的詞作為疑問意向詞,若沒有搜索到,則該問句沒有疑問意向詞。

示例問句疑問詞后面第一個標記為“n”的是“時候”,該問句的疑問意向詞特征為{時候}。

4.4 疑問意向詞在知網中的首項義原

提取疑問意向詞在知網中的首項義原作為分類特征,能夠使問句的特征更具一般性,從而能更容易更準確地得到問句分類。疑問意向詞“時候”在知網中的首項義原是“時間”,所以該問句的疑問意向詞在知網中的首項義原特征為{時間}。

5 結合遺傳算法的貝葉斯增量學習方法

其中,m表示訓練集中與類別Ci相關的問句數;Qj表示訓練集中與類別Ci相關的問句。

5.1 遺傳算法

遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法[11],它向高一級搜索的過程中不斷發現新的最優解領域從而找到全局最優點,避免算法陷入局部最優解領域。由于遺傳算法是對特征子集進行優劣評估,而不是對某個特征進行評價,使得在獲取最優特征子集的同時無需考慮特征之間的關聯性。用遺傳

絕大部分文本增量學習都是從未標注類別的增量集中選擇類別相關度大的文本加到訓練集中,文本含有的特征信息可以更新分類器參數,從而影響分類器的分類性能。但并不是文本的每個特征都能表現出明顯的類別信息,冗余或不相關的特征總會降低分類器或分類算法的性能和預測準確度,所以特征選擇是分類問題中非常關鍵的一步[8]。本文先通過設置閾值將問句屬于某一類別的概率大于閾值的問句視為類別相關問句加入到反饋集[9-10],再使用基于遺傳算法的搜索技術從反饋集中選擇最優特征子集,以下為閾值計算公式:算法對反饋集特征選擇的關鍵步驟如下:

(1)遺傳個體表示。編碼問題的關鍵在于要使得所得編碼能夠代表所給特征集的所有可能子集的解空間。本文采用一個二進制位表示所選特征子集里的一個特征,二進制位為1時表示該特征項包含于所選特征子集,相反,如果二進制位為0表示排除該特征。

(2)初始種群的選擇。遺傳算法總是代表問題可能潛在解集的一個種群,種群由若干遺傳個體組成,每個個體就是一個可能解。本文針對反饋集生成初始種群T,每個個體的每一位基因位按等概率在{0,1}中選擇。

(3)適應度函數的定義。適應度函數的選擇是否合適是遺傳算法能否成功解決問題的關鍵。本文在選擇適應度函數的時候主要考慮3個因素:1)選出的特征子集在訓練集中應有較大比重;2)選出的特征子集對類別區分有較大貢獻;3)特征子集包含的特征盡可能地少。綜合這3個因素,選擇的適應度函數如下:

其中,xi代表一個特征項,等于1時表示該特征被選入特征子集,否則等于0;M表示壓縮后的訓練集中的特征總數;N(xi)表示特征xi在訓練集出現的頻次;(logn–logm)表示所選特征子集對類別的貢獻度;n表示總的類別數;m表示用原始訓練集對刪除了特征子集中未出現特征項的壓縮訓練集進行分類能正確分出的類別數。

(4)遺傳算子設計。在遺傳算法中通過選擇算子、交叉算子和變異算子來決定后代。選擇算子使用排序選擇,對群體中的所有個體按其適應度大小進行排序,根據排序來決定個體被選中的概率;交叉算子選擇單點交叉操作,在個體編碼串中隨機設定交叉點,對該點后的2個個體部分結構進行互換;變異算子選擇基因位變異操作,對個體編碼串以變異概率隨機指定某一位或某幾位進行變異操作。

(5)終止條件的選擇。設置最大進化代數,進化結束后選取適應度最大的個體進行解碼后就得到所需要的最優特征子集。

5.2 本文算法描述

基于以上描述,將算法思想整理并描述如下:

輸入 初始訓練集D={d1,d2,…,dn},增量集S={s1,s2,…,sm},測試集T={t1,t2,…,tk},反饋集R=?

輸出 分類器C

Step 1 利用訓練集D,學習初始分類器C;

Step 2 WhileS!=?,對S中的每一元素,重復:

Step 2.1 利用現有分類器C分類si,獲得最大后驗概率Pmax和類別C′i;

Step 2.2 IfPmax＞λ(λ為相應類別閾值)thenR=R+{＜si,C′i＞},else go on;

Step 2.3S=S-{si};

Step 3 對于反饋集用遺傳算法(種群大小為100,遺傳代數為1 000,交叉概率為0.5,變異概率為0.1)生成最優特征子集;

Step 4 根據反饋集修正分類器參數。

算法主要是利用樣本中的有用信息修正分類器參數得到更精確的分類器。假設實例sp經過最優特征提取后為,將其加入到訓練集中,根據Dirichlet先驗分布特性和拉普拉斯概率估計[5],調整式(2)的類別先驗概率和式(3)的特征項的類條件概率如下:

6 實驗結果及分析

6.1 實驗數據

本文采用的哈爾濱工業大學信息檢索研究室提供的中文問句集,該問句集被分為7個大類,包括詢問描述類(DES)、人物類(HUM)、地點(LOC)、數字(NUM)、實體(OBJ)、時間(TIME)和未知類(unknown),每個大類又包含一些不重復的小類,共77個小類。問句集共有6 266個問句(其中,4 966個作為訓練樣本;1 300個作為測試樣本)。將測試樣本隨機分成2個部分,容量分別為700和600,容量為700的作為測試集T,容量為600的樣本隨機抽取200,400,600條問句作為增量集A,B,C。

6.2 評價標準

一般采用分類準確率對系統進行評價,定義如下:

6.3 實驗結果

首先給出測試語料和增量前后訓練語料各類別上的問句分布,如表1所示。

表1 測試語料和訓練語料中的問句分布

為了驗證本文設計的增量式貝葉斯學習方法在問句分類應用上的有效性及分類器增量學習后的性能,設計了3種不同的分類器模型,即傳統樸素貝葉斯分類器、文獻[12]中改進的貝葉斯分類器,以及增量式貝葉斯分類器。針對不同的增量集,設計的增量式貝葉斯分類器也不一樣。在問句分類時選取疑問詞、句法結構、疑問意向詞和疑問意向詞在知網的首項義原作為問句分類特征。不同分類器模型在大類和小類上的準確率如表2所示,在各類別上的準確率如表3所示。

表2 不同分類器模型的分類準確率 %

表3 不同分類器模型在各類別上的分類準確率 %

6.4 結果分析

由表2可以看出,改進貝葉斯分類器無論在大類還是小類上準確率都比樸素貝葉斯高。為了測試本文增量式的可行性,重點比較改進貝葉斯和增量式貝葉斯這幾組實驗,發現3種增量貝葉斯模型的準確率都比改進貝葉斯的準確率高,不同增量集對應的增量式貝葉斯分類器分類效果比較表明,增量集的問句數越多分類效果越好,說明本文提出的增量式貝葉斯方法是有效的。

觀察表3中的數據發現:(1)HUM、LOC和TIME這3個類別使用改進貝葉斯分類方法時效果并不理想,其主要原因是因為訓練集不充分導致初始分類器不準確。動態加入最優特征優化分類器后準確率提高尤其顯著,增量集為C時分別提高了15.1,10.6,13.6個百分點。具體到小類發現,HUM_ORGANIZATION的正確率由27.8%提高到61.1%,LOC_COUNTRY的正確率由67.5%提高到90.0%,TIME_OTHER的正確率由72.7%提高到86.4%,這說明了增量學習方法對于訓練不充分的類別優化效果更加有效,使得分類器從訓練初期的不充分階段逐步向充分階段轉移。(2)DES和NUM使用3種增量式貝葉斯分類器準確率提升幅度都比較小,這是因為經遺傳算法篩選后加入的特征在這2個類別的訓練集里本來就已經較完備,而且這些特征比較能反映問句的類別(如“簡稱”、“如何”、“多少”),所以用改進貝葉斯分類器分類時準確率就已經比較高。(3)OBJ類訓練集規模比較大,但準確率比較低,這是由于包含疑問詞“什么”的問句在訓練集中在DES類別中出現的比例要比在OBJ中出現的比例大,所以很多包含“什么”的問句都被標記為DES類。

除準確率提高以外,增量式貝葉斯分類模型也大大優化了運行效率。分析知增量式貝葉斯模型主要時間消耗在初始參數的確定上,后面每一次對參數的調整都建立在上一個模型的基礎上,進行分類時只要在已有的參數上計算,而改進貝葉斯模型對測試問句中的每個特征的概率計算都需要對訓練集從頭至尾統計詞頻,這必然會耗費大量時間。

7 結束語

本文提出將增量式貝葉斯思想用于問句分類的方法,結合遺傳算法選取最優特征集優化分類器,強化了較完備數據對分類的積極影響而弱化了噪音數據的消極影響。實驗結果表明,該方法在消除過多冗余特征、縮小增量規模的同時仍然有效地改善了分類器性能,并且在訓練集不充分的情況下效果尤為突出,可見訓練集的完備性對問句分類有較大影響。

在使用增量式完善訓練集時也存在問題:用遺傳算法提取最優特征時選取的是對分類系統最優而不是類別最優,會給某些類別帶來干擾特征項;另外,選取最優特征只停留在詞語表層,沒有涉及語義。所以該增量學習方法還有待改進,下一步的研究重點是結合知網庫對問句進行語義擴展,這樣在選擇適應度函數時特征子集的選擇就延伸到語義層,而且語義擴展后得到的特征子集對類別貢獻度也會有所提高。

[1] 鄭實福,劉 挺,秦 兵,等.自動問答綜述[J].中文信息學報,2002,16(6):46-52.

[2] 楊思春,高 超,秦 鋒,等.融合基本特征和詞袋綁定特征的問句特征模型[J].中文信息學報,2012,26 (5):46-52.

[3] 陳 文,晏 立,周 亮.一種具有增量學習能力的PU主動學習算法[J].計算機工程,2011,37(4): 214-215.

[4] Sarkar B K,Sana S S,Chaudhuri K.Selecting Informative Rules with Parallel Genetic Algorithm in Classification Problem[J].Applied Mathematics and Computation, 2011,218(7):3247-3264.

[5] 宮秀軍,劉少輝,史忠植.一種增量貝葉斯分類模型[J].計算機學報,2002,25(6):645-650.

[6] 李 鑫,黃萱菁,吳立德.基于錯誤驅動算法組合分類器及其在問題分類中的應用[J].計算機研究與發展, 2008,45(3):535-541.

[7] 許 莉,王大玲,夏秀峰.基于句法和語義信息的問句特征提取方法[J].計算機工程,2010,36(21):65-66.

[8] 洪智勇,王天擎,劉燦濤.一種新的互信息特征子集評價函數[J].計算機工程與應用,2011,47(22): 130-132.

[9] Lee J H.Combining the Evidence of Different Relevance Feedback MethodsforInformation Retrieval[J]. Information Processing and Management,1998,34(6): 681-691.

[10] Tao Dacheng,Tang Xiaoou,Li Xuelong.Direct Kernel Biased Discriminant Analysis:A New Content-based Image Retrieval Relevance Feedback Algorithm[J]. IEEE Transactions on Multimedia,2006,8(4):716-727.

[11] 周 明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業出版社,1999.

[12] 張 宇,劉 挺,文 勖.基于改進貝葉斯模型的問題分類[J].中文信息學報,2005,19(2):100-105.

編輯 顧逸斐

Chinese Question Classification Research Based on Incremental Bayes Model

WANG Xiao-lin,ZHEN Li-hua,YANG Si-chun,TAI Wei-peng,ZHENG Xiao
(School of Computer Science&Technology,Anhui University of Technology,Maanshan 243002,China)

Since the performance of the classifier generated by the fixed training set is not satisfactory and can hardly track the users'needs dynamically,in this paper,the incremental Bayes idea is introduced in question classification.In order to eliminate the feature redundancy in the training set,Genetic Algorithm(GA)is used to select the optimal features to amend the classifier.In the process of classifier learning,the parameters are modified dynamically while the training set is expanded.The interrogative word,syntax structure,question focus words,and their first sememes are chosen as classification features.To verify the effectiveness of the proposed method,in the experiment,questions of different size at random are extracted from the corpus to build the incremental sets.Then classify the questions from the same test set based on different incremental sets.Experimental results show that the incremental Bayes classifier achieves better result. The classification accuracy of coarse classes and fine classes achieves 90.2%and 76.3%respectively.At the same time, it significantly optimizes the efficiency to some degree.

question classification;question answering system;incremental Bayes;naive Bayes;modified Bayes; Genetic Algorithm(GA)

1000-3428(2014)09-0238-05

A

TP319

10.3969/j.issn.1000-3428.2014.09.048

國家自然科學基金資助項目(61003311);安徽高校省級自然科學基金資助項目(KJ2011A040)。

王小林(1964-),男,教授,主研方向:人工智能,中文信息處理;鎮麗華,碩士研究生;楊思春,副教授、博士研究生;邰偉鵬,講師、博士研究生;鄭 嘯,教授、博士。

2013-09-09

2013-11-01E-mail:wxl@ahut.edu.cn