基于粗糙集約簡并加權的SVM分類算法

吳欣遠，林建輝

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

0 引言

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

1 粗糙集基本理論

1.1 知識表示系統和知識

1.2 約簡

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

1.3 可變精度粗糙集模型

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

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

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

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

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

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

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

表1 實驗用數據集分布

該權重計算方法既考慮到Web文本不同于純文本的結構特點，應用特征詞在Web文本中出現的位置信息對特征詞頻率進行加權，又考慮到已有的分類決策信息，分別計算特征詞與各類決策以及整體決策劃分的一致程度，由特征詞對Web文本各類別的分類重要程度集中體現整體權重。基于Web文本的可變精度粗糙集加權方法對Web文本中特征詞出現頻率同時進行標記加權和近似質量加權，更充分地刻畫了特征詞對Web文本分類的重要程度。

3 基于粗糙集約簡并加權的SVM分類算法

本文將粗糙集理論與SVM 相結合，提出了一種優勢互補的混合分類模型。該模型由粗糙集的前期數據過濾、中期加權計算和SVM的后期分類三部分構成。

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

模型的測試部分則應用訓練部分得到的決策表約簡結果對Web文本測試集直接進行特征提取，之后轉向粗糙集的中期加權計算和SVM的后期分類階段，得到分類結果。

4 實驗驗證

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

4.1 Web文本的獲取以及預處理

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

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

4.2 特征選擇以及構造決策表

本實驗中決策表的構造以采用信息增益方法的特征選擇為基礎。由信息增益的方法保留了對分類比較重要的1 000個特征項，然后構造決策表。決策表的論域為每類中所有Web文本的集合，論域中的對象則為每篇Web文本，Web文本的類別為決策屬性，決策屬性值即為某文本所屬具體的類別，特征選擇后保留的各特征詞作為決策表的條件屬性；接著通過測定特征詞在某Web文本中出現的位置來確定其在該Web文本對象上所對應的條件屬性值。

由此算法得到的條件屬性值即為特征詞所在Web文本標記對應權值系數的最大值（若特征詞僅在正文中出現或者未在Web文本中的任何位置出現，那么該特征詞的權值系數分別設為1和0）。例如，如果特征詞在某Web文本的正文、＜H3＞標記中同時出現，則該特征詞對應此Web文本對象上的屬性值為4。綜上所述，經過特征選擇，重要的特征詞被保留下來，這時再由Web文本的結構特征確定其所對應的屬性值，得到了規模較小、離散型的決策表，同時不會影響分類的質量。

4.3 決策表的約簡

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

4.4 WVPRS權值計算和SVM分類

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

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

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

表3 采用方法①和方法②（標記加權前后）的分類器性能

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

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

通過表3可以看出：在相同的實驗環境下，使用相同的數據集并采用未經過粗糙集前期數據約簡和加權的SVM分類算法，方法②對Web文本中的特殊結構標記進行加權后，分類器的查準率、查全率、F1值較方法①分別提高了2.11%、2.50%、2.40%，方法②分類的平均性能比方法①要好。可見，對能夠體現Web文本結構的特殊標記進行適當加權有利于改善分類器的性能。

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

5 結論

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

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

[2]姜春茂，張國印，李志聰.基于遺傳算法優化SVM的嵌入式網絡系統異常入侵檢測[J].計算機應用與軟件，2011，28（2），287-289.

[3]胡志軍，王鴻斌，張惠斌.基于距離排序的快速SVM分類算法[J].計算機應用與軟件，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]趙東紅，王來生，張峰.遺傳算法的粗糙集理論在文本降維上的應用[J].計算機工程與應用，2012，48（36），125-128.

[6]蘭均，施化吉，李星毅，等.基于特征詞復合權重的關聯網頁分類[J].計算機科學，2011，38（3）：187-190.

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

[8]楊淑棉.粗糙集在文本分類系統中的應用研究[D].濟南：山東師范大學，2007.