摘  要： 針對(duì)Web中文文本分類中現(xiàn)有權(quán)重計(jì)算方法的不足和SVM算法對(duì)大數(shù)據(jù)量模式分類的低效性，提出了基于粗糙集約簡并且加權(quán)的SVM分類方法。粗糙集作為SVM分類的前期預(yù)處理器，應(yīng)用粗糙集的約簡理論和基于Web中文文本的可變精度粗糙集加權(quán)方法對(duì)分類前的數(shù)據(jù)分別進(jìn)行簡化并計(jì)算權(quán)重，從而提高SVM后期分類的效率和精度。實(shí)驗(yàn)結(jié)果表明，SVM對(duì)約簡并加權(quán)后的數(shù)據(jù)進(jìn)行分類，分類性能得到了進(jìn)一步保證。

　　關(guān)鍵詞： SVM；粗糙集；約簡；加權(quán)

0 引言

　　支持向量機(jī)（Support Vector Machine，SVM）方法在模式分類中應(yīng)用廣泛[1-2]。它以VC維和結(jié)構(gòu)風(fēng)險(xiǎn)最小化為基礎(chǔ)，根據(jù)有限的信息在模型對(duì)特定樣本的學(xué)習(xí)精度和學(xué)習(xí)能力之間得到問題的最優(yōu)解。SVM使用內(nèi)積函數(shù)將輸入空間變換到一個(gè)高維空間，從中求廣義最優(yōu)分類面，較好地解決了過學(xué)習(xí)、高維數(shù)等實(shí)際問題，且具有較好的魯棒性。但由于SVM最終將分類轉(zhuǎn)換成二次規(guī)劃問題，其計(jì)算量隨著變量的增加而呈指數(shù)增長。在Web文本分類中，文本類別和數(shù)目多、噪音多，文本向量稀疏性大、維數(shù)高，中文文本的特征向量可能存在冗余且具有較大的相關(guān)性，這將導(dǎo)致SVM網(wǎng)絡(luò)結(jié)構(gòu)和核函數(shù)計(jì)算復(fù)雜[3]。如何減少SVM的分類訓(xùn)練時(shí)間，進(jìn)一步提高分類精度，是當(dāng)前需要解決的熱點(diǎn)問題。由此，本文提出了基于粗糙集約簡并加權(quán)的SVM分類算法。

1 粗糙集基本理論

　　1.1 知識(shí)表示系統(tǒng)和知識(shí)

　　粗糙集理論認(rèn)為，知識(shí)就是一種對(duì)對(duì)象進(jìn)行分類的能力。一個(gè)知識(shí)庫可以表達(dá)為四元組S=<U，A，V，f>，其中U（U≠空集）為全域，即所討論對(duì)象的全體；A和V分別為屬性集合和屬性值集合，V=Va，其中Va表示屬性a∈A的屬性值范圍；f∶U×A→V是一個(gè)映射關(guān)系，表示對(duì)?坌x∈U，a∈A有f（x，a）∈V。若A由條件屬性集合C和決策屬性集合D組成，且A=C∪D，C∩D=?椎，則稱S為決策表。

　　1.2 約簡

　　設(shè)U為論域，R為U上的不可分辨關(guān)系。如果ind（R）=ind（R-{r}），r∈R，則稱r在R之中是可省的，否則就是不可省的；若任一r∈R都是不可省的，則稱R是獨(dú)立的，否則R是相關(guān)的，即R中存在可約去的屬性；若P?哿R是獨(dú)立的，且ind（P）=ind（R），則稱P是R的一個(gè)約簡[4-5]。在R中所有不可省的關(guān)系的集合稱為R的核，以core（R）來表示。

　　1.3 可變精度粗糙集模型

　　可變精度粗糙集模型是粗糙集模型的擴(kuò)展，該模型可以通過設(shè)定近似包含閾值?琢，更精細(xì)地對(duì)邊界上的樣本進(jìn)行劃分，從而放松了經(jīng)典粗糙集嚴(yán)格的邊界定義，使其能夠更好地處理不一致的信息，具有一定的抗噪聲能力[6]。可變精度?琢-下、上近似集定義分別為：

　　關(guān)系R形成的x的等價(jià)類被集合X包含的程度由C（[x]R，X）描述；-下近似和上近似分別為關(guān)系R下的等價(jià)類以大于包含度以及U中的等價(jià)類以大于1-包含度包含在X中的元素集合；VPRS模型退化為傳統(tǒng)的粗糙集模型。

　　2 基于Web中文文本的可變精度粗糙集權(quán)重計(jì)算方法

　　基于可變精度粗糙集模型，將n類Web文本集按照文本所屬類別劃分為U={D1，D2，…，Dn}的等價(jià)類，不同的特征詞形成的等價(jià)關(guān)系為R，可以定義-上、下近似集分別為：

　　其中，集合Di在等價(jià)關(guān)系R下?琢-上、下近似集分別由R?琢Di和R?琢Di表示；R對(duì)U劃分的等價(jià)類可能或一定包含在決策屬性劃分的等價(jià)類的元素集合分別由R?琢U和R?琢U描述；由于Web文本分類中特征詞分布具有隨機(jī)性，因此可以引入式（6）中的分類近似質(zhì)量?酌R（U）來度量關(guān)系R對(duì)論域劃分的等價(jià)類被確切分到?jīng)Q策屬性劃分的等價(jià)類的比率[8]，近似質(zhì)量越高，則特征詞對(duì)分類的貢獻(xiàn)就越大，并將其替代逆文本頻率對(duì)特征詞頻率進(jìn)行加權(quán)，以提高樣本的可分性。

　　由此，本文提出了基于Web中文文本的可變精度粗糙集加權(quán)方法（WVPRS），如式（7）所示：

　　其中，Hwij為第j個(gè)特征詞在第i篇Web文本中的權(quán)重；n為Web文本樣本集的類別個(gè)數(shù)；tfij為第j個(gè)特征詞在第i篇Web文本中出現(xiàn)的次數(shù)；max（λij）為特征詞j所在網(wǎng)頁標(biāo)記（Web文本i中）對(duì)應(yīng)的最大加權(quán)系數(shù)（參照表1），S={TITLE，H1，H2，H3，H4，H5，H6，B，U，I}。例如，若特征詞j在文本i<TITLE>和<U>中同時(shí)出現(xiàn)，則max（λij）=7；如果j只出現(xiàn)在Web文本i的正文中，則取max（λij）=1。

　　該權(quán)重計(jì)算方法既考慮到Web文本不同于純文本的結(jié)構(gòu)特點(diǎn)，應(yīng)用特征詞在Web文本中出現(xiàn)的位置信息對(duì)特征詞頻率進(jìn)行加權(quán)，又考慮到已有的分類決策信息，分別計(jì)算特征詞與各類決策以及整體決策劃分的一致程度，由特征詞對(duì)Web文本各類別的分類重要程度集中體現(xiàn)整體權(quán)重?；赪eb文本的可變精度粗糙集加權(quán)方法對(duì)Web文本中特征詞出現(xiàn)頻率同時(shí)進(jìn)行標(biāo)記加權(quán)和近似質(zhì)量加權(quán)，更充分地刻畫了特征詞對(duì)Web文本分類的重要程度。

3 基于粗糙集約簡并加權(quán)的SVM分類算法

　　本文將粗糙集理論與SVM相結(jié)合，提出了一種優(yōu)勢互補(bǔ)的混合分類模型。該模型由粗糙集的前期數(shù)據(jù)過濾、中期加權(quán)計(jì)算和SVM的后期分類三部分構(gòu)成。

　　在模型的訓(xùn)練部分，首先對(duì)訓(xùn)練集進(jìn)行分詞等預(yù)處理和特征選擇，并由得到的特征子集構(gòu)造離散型的決策表。然后將粗糙集作為分類模型的前期數(shù)據(jù)過濾器，應(yīng)用其約簡理論，以不損失有效信息為前提，過濾掉決策表中的冗余特征，從而簡化SVM的輸入數(shù)據(jù)集，減小SVM算法訓(xùn)練復(fù)雜度，最終達(dá)到節(jié)省訓(xùn)練時(shí)間的目的。接著，訓(xùn)練模型轉(zhuǎn)向中期權(quán)重計(jì)算階段，將粗糙集作為加權(quán)計(jì)算器，應(yīng)用式（7）的加權(quán)算法進(jìn)行權(quán)重計(jì)算，得到Web文本中間表示形式。最后，訓(xùn)練模型轉(zhuǎn)向后期分類階段，利用SVM算法的優(yōu)勢對(duì)粗糙集約簡并加權(quán)后的數(shù)據(jù)進(jìn)行分類訓(xùn)練，最終得到分類性能較高的分類器。

　　模型的測試部分則應(yīng)用訓(xùn)練部分得到的決策表約簡結(jié)果對(duì)Web文本測試集直接進(jìn)行特征提取，之后轉(zhuǎn)向粗糙集的中期加權(quán)計(jì)算和SVM的后期分類階段，得到分類結(jié)果。

4 實(shí)驗(yàn)驗(yàn)證

　　實(shí)驗(yàn)中Web文本訓(xùn)練集和測試集使用軟件Webdup 0.93 Beta獲取，將臺(tái)灣大學(xué)林智仁開發(fā)的LIBSVM作為本實(shí)驗(yàn)中的SVM模型，ROSETTA用來做粗糙集的約簡及加權(quán)等相關(guān)計(jì)算。

　　4.1 Web文本的獲取以及預(yù)處理

　　用于Web中文文本分類的訓(xùn)練集和測試集包括房產(chǎn)、財(cái)經(jīng)、娛樂、教育、軍事、汽車、旅游、科技和體育9個(gè)類別，共3 141個(gè)文本。這9個(gè)類別在所抓取的各網(wǎng)站上都已經(jīng)進(jìn)行了很好的分類。數(shù)據(jù)集分布如表1所示。

　　掃描Web樣本集中的HTML文檔源代碼，對(duì)表1中的標(biāo)記所修飾內(nèi)容進(jìn)行識(shí)別并加權(quán)，只在正文中出現(xiàn)的內(nèi)容則不需要加權(quán)，默認(rèn)加權(quán)系數(shù)為1。本實(shí)驗(yàn)采用中科院軟研所的ICTCLAS分詞程序進(jìn)行分詞，并進(jìn)行去停用詞等預(yù)處理。

　　4.2 特征選擇以及構(gòu)造決策表

　　本實(shí)驗(yàn)中決策表的構(gòu)造以采用信息增益方法的特征選擇為基礎(chǔ)。由信息增益的方法保留了對(duì)分類比較重要的1 000個(gè)特征項(xiàng)，然后構(gòu)造決策表。決策表的論域?yàn)槊款愔兴蠾eb文本的集合，論域中的對(duì)象則為每篇Web文本，Web文本的類別為決策屬性，決策屬性值即為某文本所屬具體的類別，特征選擇后保留的各特征詞作為決策表的條件屬性；接著通過測定特征詞在某Web文本中出現(xiàn)的位置來確定其在該Web文本對(duì)象上所對(duì)應(yīng)的條件屬性值。

　　由此算法得到的條件屬性值即為特征詞所在Web文本標(biāo)記對(duì)應(yīng)權(quán)值系數(shù)的最大值（若特征詞僅在正文中出現(xiàn)或者未在Web文本中的任何位置出現(xiàn)，那么該特征詞的權(quán)值系數(shù)分別設(shè)為1和0）。例如，如果特征詞在某Web文本的正文、<H3>標(biāo)記中同時(shí)出現(xiàn)，則該特征詞對(duì)應(yīng)此Web文本對(duì)象上的屬性值為4。綜上所述，經(jīng)過特征選擇，重要的特征詞被保留下來，這時(shí)再由Web文本的結(jié)構(gòu)特征確定其所對(duì)應(yīng)的屬性值，得到了規(guī)模較小、離散型的決策表，同時(shí)不會(huì)影響分類的質(zhì)量。

　　4.3 決策表的約簡

　　常用的屬性約簡算法有屬性逐步刪除、屬性逐步增加、基于可辨識(shí)矩陣和邏輯運(yùn)算等方法。本實(shí)驗(yàn)中采用可辨識(shí)矩陣和邏輯運(yùn)算進(jìn)行決策表的約簡，約簡后保留了673個(gè)特征項(xiàng)，“屬性蒸發(fā)”了32.7%?？梢?，粗糙集的約簡算法有效地縮減了特征維數(shù)并對(duì)數(shù)據(jù)進(jìn)行了“濃縮”。

　　4.4 WVPRS權(quán)值計(jì)算和SVM分類

　　對(duì)上一步驟中經(jīng)過粗糙集約簡后保留的特征項(xiàng)應(yīng)用前文提出的基于Web中文文本的可變精度粗糙集加權(quán)方法進(jìn)行權(quán)值計(jì)算，得到文本向量，然后轉(zhuǎn)向SVM進(jìn)行分類訓(xùn)練，并將訓(xùn)練得到的分類器分別與約簡前、未考慮Web文本標(biāo)記加權(quán)、采用逆文本頻率加權(quán)的各SVM分類器性能進(jìn)行比較。為了方便描述實(shí)驗(yàn)結(jié)果，特做如表2所示的標(biāo)號(hào)。

　　實(shí)驗(yàn)過程中，SVM分類器采用線性核函數(shù)，選用查準(zhǔn)率、查全率以及F1值來衡量分類效果，分別對(duì)表中不同方法的分類效果進(jìn)行比較并分析，實(shí)驗(yàn)結(jié)果如表3~5所示。

　　通過表3可以看出：在相同的實(shí)驗(yàn)環(huán)境下，使用相同的數(shù)據(jù)集并采用未經(jīng)過粗糙集前期數(shù)據(jù)約簡和加權(quán)的SVM分類算法，方法②對(duì)Web文本中的特殊結(jié)構(gòu)標(biāo)記進(jìn)行加權(quán)后，分類器的查準(zhǔn)率、查全率、F1值較方法①分別提高了2.11%、2.50%、2.40%，方法②分類的平均性能比方法①要好?？梢?，對(duì)能夠體現(xiàn)Web文本結(jié)構(gòu)的特殊標(biāo)記進(jìn)行適當(dāng)加權(quán)有利于改善分類器的性能。

　　表5中的方法③和方法④均考慮了Web文本中特殊標(biāo)記和粗糙集約簡對(duì)分類的作用，而方法④在特征詞權(quán)重計(jì)算過程中引入了分類決策信息，將逆頻率替代為近似質(zhì)量對(duì)特征詞在當(dāng)前文本中出現(xiàn)的頻率進(jìn)行雙重加權(quán)，進(jìn)一步提高了SVM的分類精度，查準(zhǔn)率、查全率和F1值分別提高了3.23%、2.67%和2.96%。結(jié)果表明，權(quán)重計(jì)算過程中考慮標(biāo)記和已有分類決策信息的作用，能夠有效地提高分類精度。

5 結(jié)論

　　SVM在分類問題中能夠表現(xiàn)出非線性、高維輸入空間等優(yōu)勢，而面對(duì)Web文本分類中噪音多、文本稀疏性大、特征詞存在冗余等問題使SVM呈現(xiàn)出訓(xùn)練時(shí)間長、分類速度慢等不足。對(duì)此，本文闡述了粗糙集的約簡理論和可變精度粗糙集模型，分析了HTML標(biāo)記對(duì)網(wǎng)頁內(nèi)容的修飾作用并設(shè)計(jì)了特殊標(biāo)記加權(quán)方案，提出了基于Web中文文本的可變精度粗糙集加權(quán)方法，最后設(shè)計(jì)了以粗糙集約簡和權(quán)重計(jì)算作為前端預(yù)處理器，以SVM作為后端分類器的混合算法。實(shí)驗(yàn)證明，該算法從分類效率和分類精度兩個(gè)方面對(duì)經(jīng)典的SVM模型進(jìn)行了優(yōu)化，使其分類性能得到進(jìn)一步保證。

參考文獻(xiàn)

　　[1] 木林.基于SVM算法和其他算法在文本分類中的性能比較[J].內(nèi)蒙古大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，42（6）：703-707.

　　[2] 姜春茂，張國印，李志聰.基于遺傳算法優(yōu)化SVM的嵌入式網(wǎng)絡(luò)系統(tǒng)異常入侵檢測[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（2），287-289.

　　[3] 胡志軍，王鴻斌，張惠斌.基于距離排序的快速SVM分類算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（4），85-87.

　　[4] Ye Mingquan， Wu Xindong， Hu Xuegang， et al. Anonymizing classification data using rough set theory[J]. Knowledge-Based Systems， 2013，43（1）：82-94.

　　[5] 趙東紅，王來生，張峰.遺傳算法的粗糙集理論在文本降維上的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（36），125-128.

　　[6] 蘭均，施化吉，李星毅，等.基于特征詞復(fù)合權(quán)重的關(guān)聯(lián)網(wǎng)頁分類[J].計(jì)算機(jī)科學(xué)，2011，38（3）：187-190.

　　[7] 胡清華，謝宗霞，于達(dá)仁.基于粗糙集加權(quán)的文本分類方法研究[J]，情報(bào)學(xué)報(bào)，2005，24（1）：59-63.

　　[8] 楊淑棉.粗糙集在文本分類系統(tǒng)中的應(yīng)用研究[D].濟(jì)南：山東師范大學(xué)，2007.