基于RST和SVM的中文問題分類方法

董云耀,陳小翠,黃 煒

(杭州電子科技大學(xué)計算機學(xué)院,浙江杭州310018)

0 引 言

所謂問題分類就是在中文問答系統(tǒng)(Chinese Question Answering System,CQAS)中按預(yù)定的分類規(guī)則確定問題的類型[1,2]。支持向量機(Support Vector Machine,SVM)是一種針對數(shù)據(jù)分類和回歸問題的統(tǒng)計學(xué)習(xí)理論,但是它不能處理冗余數(shù)據(jù),而且當(dāng)訓(xùn)練樣本數(shù)量過大、空間維數(shù)過高時會導(dǎo)致訓(xùn)練時間過長、處理速度過慢,降低分類的效率[3,4]。粗糙集理論(Rough Set Theory,RST)[5]中的屬性約簡可以刪除信息系統(tǒng)中的冗余屬性,降低數(shù)據(jù)空間維數(shù),但是它只能處理量化數(shù)據(jù),而且它的容錯能力和泛化能力也比較弱,這正是支持向量機的優(yōu)勢所在。因此,本文利用RST和SVM的優(yōu)點及兩者之間的互補性,提出了一種新的問題分類方法CRV(The Chinese question classification based on RST-SVM),利用RST中屬性約簡方法消除冗余的屬性,降低了樣本維數(shù),將約簡后的數(shù)據(jù)利用SVM進行分類,從而得到了較高的分類精度。并將該方法應(yīng)用于計算機網(wǎng)絡(luò)課程的自動問答系統(tǒng)中,以驗證該方法的可行性。

1 相關(guān)理論

1.1 RST的屬性約簡

粗糙集理論的屬性約簡就是在保持分類能力不變的情況下,刪除其中不必要或者不重要的屬性[6]。其相關(guān)定義如下:

定義1 信息系統(tǒng)S=(U,R,V,f)。其中:U={x1,x2,…,xn}為論域;R是屬性的非空有限集合,R=C∪D且C∩D=?,其中C稱為條件屬性集,D稱為決策屬性集;V為屬性值的集合;f:U×R→V是一個信息函數(shù),它指定U中每一個對象x的屬性值;

定義2 設(shè)R是U上的等價關(guān)系,r∈R,若ind(R)=ind(R-{r}),則稱關(guān)系r在R中是不必要的,否則是必要的。若每一個r∈R在R中是必要的,則稱r是獨立的,否則稱r是依賴的或非獨立的。設(shè)Q?R并且Q是獨立的,且ind(Q)=ind(R),則稱Q是R的一個絕對約簡,通常R有多個約簡,可以將所有約簡的交集成為核,記作core(R);

定義3 設(shè)P和Q是U中的等價關(guān)系,Q的P正區(qū)域是U中所有根據(jù)分類U/P的信息可以準(zhǔn)確劃分到關(guān)系Q的等價類中去的對象集合,即則稱r為P中Q不必要,否則r為P中Q必要的。若P的Q獨立子集S,S?P有POSS(Q)=POSp(Q),稱S為P的Q相對約簡。P的所有Q約簡的交集稱為P的Q核,記為coreQ(P)。P的Q核是P中所有Q必要的原始關(guān)系構(gòu)成的集合;

定義4 令決策表S=(U,R,V,f)中,P,Q?R,當(dāng)且僅當(dāng)ind(P)=ind(Q)時,Q依賴于P(記作P?Q),而當(dāng)k=γP(Q)=|POSp(Q)|/|U|稱Q是k(0 k 1)度依賴P(記作P?kQ),γP(Q)是Q與P之間的依賴度;

定義5 在已知條件屬性B的前提下,一個屬性c∈C-B關(guān)于決策屬性D的屬性重要性定義為:EB(D)=γB∪{c}(D)-γB(D)。

1.2 支持向量機

SVM就是通過用內(nèi)積函數(shù)定義的非線性映射將輸入向量映射到一個高維空間,然后在這個高維空間中構(gòu)造最優(yōu)超平面作為分類判別平面,使得兩類數(shù)據(jù)樣本之間的間隔最大。

假設(shè)給定數(shù)據(jù)樣本(x1,y1),…,(xi,yi),xi∈Rn,yi∈{-1,+1},其中i=1,2,…,n,分類面方程為ω?x+b=0,要使分類間隔最大,就要求2/||ω||最大,而要求分類面對所有樣本正確分類,就要求滿足:yi(ω×xi+b)≥1,i=1,2,…,n,。根據(jù)拉格朗日函數(shù)和最優(yōu)化條件,得到最優(yōu)分類函數(shù)為:f(x)=

常用的核函數(shù)有:q次多項式函數(shù)、徑向基函數(shù)和Sigmoid函數(shù)。本文采用徑向基函數(shù)作為SVM的

2 CRV分類方法

本文提出的CRV分類方法首先利用RST決策表中的屬性約簡,刪除問句中那些不重要屬性以便降低數(shù)據(jù)的維數(shù),然后利用SVM分類器對約簡后數(shù)據(jù)進行訓(xùn)練和分類測試,并給出最終的分類結(jié)果,其流程圖如圖1所示。

圖1 CRV分類流程圖

由圖1可以給出CRV方法的具體步驟:

(1)問句訓(xùn)練集和問句測試集。從問題庫中抽取問句樣本集,以大約2∶1的比例將其分為問句訓(xùn)練集和問句測試集,并對問句訓(xùn)練集人工預(yù)先分類;

(2)問句預(yù)處理。對問句集進行分詞、詞性標(biāo)注、去掉停用詞、句法分析等預(yù)處理;

(3)特征選取和權(quán)值計算。由于問句包含的特征信息也較少,因此需要從問句中盡可能多的選取對分類有幫助的特征詞,以便于正確的對問題分類。本文選擇疑問詞、主要謂語動詞、中心名詞及其之間的依存關(guān)系作為問句的特征項,利用TF-IDF方法計算特征項的權(quán)值;

(4)特征向量空間。將問句訓(xùn)練集和測試集表示成計算機可以處理的問句向量形式;

(5)屬性離散化和創(chuàng)建決策表。由于問句集的屬性值是連續(xù)的,而粗糙集只能處理離散屬性值,因此需要要對問句集進行離散化處理。本文采用等頻率離散劃分法,根據(jù)權(quán)值的大小進行排序,將其平均劃分成6段,每段用0,1,…,5表示。根據(jù)離散化后的屬性創(chuàng)建決策表,將每一個問句作為決策表中的一行,特征項構(gòu)成決策表的條件屬性,離散化后的屬性值作為條件屬性的取值,問句所屬的類別為決策屬性,對其中的每一個類別賦予特定的數(shù)值;

(6)屬性約簡。刪除決策表中對決策屬性不重要的或者不必要的條件屬性,本文采用的是基于屬性重要性的屬性約簡算法,以下為它的主要步驟。

輸入決策表S=(U,C∪D,V,f),其中U={x1,x2,…,xn},C={C1,C2,…,Cn};

輸出約簡后的屬性集Reduct(簡稱Red);

1)令core(C)=?;

2)計算相對正域POSC(D),對于任意的一個Ci,若POS(C-{Ci})(D)≠POSC(D),則core(C)=core(C)+{Ci},從而得出屬性約簡集合Red=core(C);

3)計算γRed(D),γC(D),若γRed(D)=γC(D),轉(zhuǎn)向5),否則轉(zhuǎn)向4);

4)計算剩余屬性中屬性重要性ECi(D),找出max(ECi(D)),并將其加入Red中,即Red=Red+{Ci},轉(zhuǎn)向3);

5)輸出屬性約簡集Red。

(7)構(gòu)造SVM分類器。將屬性約簡后的訓(xùn)練數(shù)據(jù)作為SVM的輸入量,通過訓(xùn)練問句訓(xùn)練集構(gòu)造最小誤差分類器,并以該分類器對問句測試集進行測試;

(8)分類效果評價。將CRV所得到的分類結(jié)果與直接進行SVM分類的結(jié)果進行比較,若分類效果比較明顯則轉(zhuǎn)步驟9,若分類效果不理想,則需要返回步驟3進行重新處理;

(9)分類結(jié)果。

3 實驗及結(jié)果分析

為驗證CRV方法的對與問題分類的可行性和有效性,本文通過計算機網(wǎng)絡(luò)課程的自動問答系統(tǒng)中對學(xué)生提出的問題進行分類,從問題庫中提取問句集樣本,并將其擴展為1 200個問句,包括796個訓(xùn)練問句,404個問句測試,將其分為8類,各類的訓(xùn)練集數(shù)目和測試集數(shù)目如表1所示。

對問句集樣本進行屬性約簡,將約簡后的樣本數(shù)據(jù)作為SVM的輸入量,使用LIBSVM 2.89在Matlab6.5上實現(xiàn)問題分類。將該方法與直接進行SVM分類進行比較,實驗結(jié)果如表2所示,通過屬性約簡,將數(shù)據(jù)空間維數(shù)由1 200降低到923,其平均分類準(zhǔn)確率由85.39%提高到了86.06%?？梢钥闯?本文提出的方法優(yōu)于直接進行SVM分類方法。

表2 CRV和SVM方法的比較

4 結(jié)束語

本文研究的CRV方法利用RST對樣本數(shù)據(jù)進行預(yù)處理,提高了SVM的分類效率,與直接進行SVM分類相比,減少了數(shù)據(jù)的空間維數(shù),提高了分類的準(zhǔn)確率。但是在該分類過程中有不少的人工干預(yù),而且若特征項的選擇不好,都會影響分類的準(zhǔn)確率,因此在今后的研究中,減少不必要的人工干預(yù),考慮從更深層的語義來選取特征項。

[1] 蔡剛山.中文自動問答系統(tǒng)研究[D].武漢:華中科技大學(xué),2007.

[2] 李鑫.問答系統(tǒng)中的問題分類研究[D].上海:復(fù)旦大學(xué),2007.

[3] Vapnik V.The Nature of Statistical Theory[M].New York:Sp ringer-Verlag,1995:2-57.

[4] 鄧乃楊,甜英杰.支持向量機:理論、算法和拓展[M].北京:科學(xué)出版社,2009:1-125.

[5] Pawlak Z.Rough Sets Theoretical Aspects of Reasoning about Data[M].Boston:Kluwer Academ ic Publishers,1991:1-150.

[6] 史軍.基于粗糙集理論的屬性約簡算法研究[D].青島:青島大學(xué),2009.