摘  要： 針對Web中文文本分類中現(xiàn)有權(quán)重計(jì)算方法的不足和SVM算法對大數(shù)據(jù)量模式分類的低效性，提出了基于粗糙集約簡并且加權(quán)的SVM分類方法,。粗糙集作為SVM分類的前期預(yù)處理器,，應(yīng)用粗糙集的約簡理論和基于Web中文文本的可變精度粗糙集加權(quán)方法對分類前的數(shù)據(jù)分別進(jìn)行簡化并計(jì)算權(quán)重，從而提高SVM后期分類的效率和精度,。實(shí)驗(yàn)結(jié)果表明,，SVM對約簡并加權(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ù)有限的信息在模型對特定樣本的學(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í)就是一種對對象進(jìn)行分類的能力,。一個(gè)知識(shí)庫可以表達(dá)為四元組S=<U,，A,，V,，f>，其中U（U≠空集）為全域,，即所討論對象的全體,；A和V分別為屬性集合和屬性值集合，V=Va,，其中Va表示屬性a∈A的屬性值范圍,；f∶U×A→V是一個(gè)映射關(guān)系，表示對?坌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ì)地對邊界上的樣本進(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對U劃分的等價(jià)類可能或一定包含在決策屬性劃分的等價(jià)類的元素集合分別由R?琢U和R?琢U描述,；由于Web文本分類中特征詞分布具有隨機(jī)性，因此可以引入式（6）中的分類近似質(zhì)量?酌R（U）來度量關(guān)系R對論域劃分的等價(jià)類被確切分到?jīng)Q策屬性劃分的等價(jià)類的比率[8],，近似質(zhì)量越高,，則特征詞對分類的貢獻(xiàn)就越大，并將其替代逆文本頻率對特征詞頻率進(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中）對應(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)的位置信息對特征詞頻率進(jìn)行加權(quán),，又考慮到已有的分類決策信息,，分別計(jì)算特征詞與各類決策以及整體決策劃分的一致程度，由特征詞對Web文本各類別的分類重要程度集中體現(xiàn)整體權(quán)重,。基于Web文本的可變精度粗糙集加權(quán)方法對Web文本中特征詞出現(xiàn)頻率同時(shí)進(jìn)行標(biāo)記加權(quán)和近似質(zhì)量加權(quán),，更充分地刻畫了特征詞對Web文本分類的重要程度,。

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

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

　　在模型的訓(xùn)練部分,，首先對訓(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)勢對粗糙集約簡并加權(quán)后的數(shù)據(jù)進(jìn)行分類訓(xùn)練,，最終得到分類性能較高的分類器。

　　模型的測試部分則應(yīng)用訓(xùn)練部分得到的決策表約簡結(jié)果對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文檔源代碼，對表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ǔ)。由信息增益的方法保留了對分類比較重要的1 000個(gè)特征項(xiàng),，然后構(gòu)造決策表,。決策表的論域?yàn)槊款愔兴蠾eb文本的集合，論域中的對象則為每篇Web文本,，Web文本的類別為決策屬性,，決策屬性值即為某文本所屬具體的類別,，特征選擇后保留的各特征詞作為決策表的條件屬性；接著通過測定特征詞在某Web文本中出現(xiàn)的位置來確定其在該Web文本對象上所對應(yīng)的條件屬性值,。

　　由此算法得到的條件屬性值即為特征詞所在Web文本標(biāo)記對應(yīng)權(quán)值系數(shù)的最大值（若特征詞僅在正文中出現(xiàn)或者未在Web文本中的任何位置出現(xiàn),，那么該特征詞的權(quán)值系數(shù)分別設(shè)為1和0）。例如,，如果特征詞在某Web文本的正文,、<H3>標(biāo)記中同時(shí)出現(xiàn)，則該特征詞對應(yīng)此Web文本對象上的屬性值為4,。綜上所述,，經(jīng)過特征選擇，重要的特征詞被保留下來,，這時(shí)再由Web文本的結(jié)構(gòu)特征確定其所對應(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ù)并對數(shù)據(jù)進(jìn)行了“濃縮”,。

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

　　對上一步驟中經(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值來衡量分類效果，分別對表中不同方法的分類效果進(jìn)行比較并分析,，實(shí)驗(yàn)結(jié)果如表3~5所示,。

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

　　表5中的方法③和方法④均考慮了Web文本中特殊標(biāo)記和粗糙集約簡對分類的作用,，而方法④在特征詞權(quán)重計(jì)算過程中引入了分類決策信息，將逆頻率替代為近似質(zhì)量對特征詞在當(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)勢,，而面對Web文本分類中噪音多,、文本稀疏性大、特征詞存在冗余等問題使SVM呈現(xiàn)出訓(xùn)練時(shí)間長,、分類速度慢等不足,。對此，本文闡述了粗糙集的約簡理論和可變精度粗糙集模型,，分析了HTML標(biāo)記對網(wǎng)頁內(nèi)容的修飾作用并設(shè)計(jì)了特殊標(biāo)記加權(quán)方案,，提出了基于Web中文文本的可變精度粗糙集加權(quán)方法，最后設(shè)計(jì)了以粗糙集約簡和權(quán)重計(jì)算作為前端預(yù)處理器,，以SVM作為后端分類器的混合算法,。實(shí)驗(yàn)證明，該算法從分類效率和分類精度兩個(gè)方面對經(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.