吳欣遠(yuǎn)，林建輝

（西南交通大學(xué) 牽引動力國家重點實驗室，四川 成都 610031）

0 引言

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

1 粗糙集基本理論

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

1.2 約簡

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

1.3 可變精度粗糙集模型

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

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

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

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

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

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

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

表1 實驗用數(shù)據(jù)集分布

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

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

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

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

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

4 實驗驗證

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

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

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

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

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

本實驗中決策表的構(gòu)造以采用信息增益方法的特征選擇為基礎(chǔ)。由信息增益的方法保留了對分類比較重要的1 000個特征項，然后構(gòu)造決策表。決策表的論域為每類中所有Web文本的集合，論域中的對象則為每篇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)記中同時出現(xiàn)，則該特征詞對應(yīng)此Web文本對象上的屬性值為4。綜上所述，經(jīng)過特征選擇，重要的特征詞被保留下來，這時再由Web文本的結(jié)構(gòu)特征確定其所對應(yīng)的屬性值，得到了規(guī)模較小、離散型的決策表，同時不會影響分類的質(zhì)量。

4.3 決策表的約簡

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

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

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

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

表2 實驗過程中采用的方法

表3 采用方法①和方法②（標(biāo)記加權(quán)前后）的分類器性能

表4 采用方法②和方法③（約簡前后）的分類器訓(xùn)練時間

表5 采用方法③和方法④的分類器性能

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

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

5 結(jié)論

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

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

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

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

[4]YeMingquan，WuXindong，HuXuegang，etal.Anonymizing classification data using rough set theory[J].Knowledge-Based Systems，2013，43（1）：82-94.

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

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

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

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