支持向量機及其在郵件過濾中的應用

王 強，賈銀山

(遼寧石油化工大學計算機與通信工程學院，撫順113001)

1 引言

隨著互聯網的快速發展和普及，電子郵件以其方便、快捷等特點受到網民的青睞。與此同時垃圾郵件也在網絡上大量傳輸，不僅占據了郵件服務器大量的存儲空間和網絡帶寬，而且也帶來了嚴重的社會問題。垃圾郵件泛濫造成的危害越來越嚴重，已經成為一個全球性問題。因此，研究反垃圾郵件的方法有著深遠的社會意義和巨大的經濟價值。

2 支持向量機的基本原理

支持向量機的基本思想是:首先把訓練數據集非線性地映射到一個高維空間，這個非線性映射的目的是把在輸入空間中的線性不可分數據集映射到高維特征空間后變為線性可分的數據集，隨后在特征空間建立一個具有最大隔離距離的最優分類超平面，這也相當于在輸入空間產生一個最優非線性決策邊界。這里應該注意的是，在特征空間中支持向量機的分離超平面是最優的分離超平面。有很多個分類超平面都可以把兩個類分離開，但是只有一個是最優的，就是圖中的實線所表示的。它與兩個類之間最近向量的距離最大。最優超平面可由被這個超平面錯分和處在間隔帶中的向量表示，如圖1樣本中的兩個黑方塊和幾個黑圓，它們就是所說的支持向量，所以這種學習機叫支持向量機(SVM)。實際上SVM最吸引人的地方不是支持向量思想，而是結構風險最小化思想，也就是上述的最優分類超平面不但使學習機的經驗風險很小，同時泛化誤差也很小，即結構風險最小。

圖1 最優分類超平面

2.1 線性支持向量分類機

假設有訓練集 T={(x1y1)，(x2y2)，…，(xnyn)}∈(Xn，Yn)n表示一組訓練樣本，xi∈X=Rn，yi∈Y={1，－1}，其中 yi= ±1 表示 xi屬于類別A，yi=－1表示xi屬于類別B，在線性可分的情況下就會有一個超平面使得這兩個類樣本完全分開。該超平面為:(w ”是向量點積。w是超平面的法線方向，w/‖w‖為位單位法向量。‖w‖是表示范數。在二維的兩類線性可分情況下，有很多可能的線性分類器可以把這組數據分隔開，但是只有一個使兩類的分類間隔最大，這個線性分類器就是最優分類超平面(如圖1)。

引進松弛變量 ξi≥0，可得“松弛”了的條件:yi(w·xi+b)+ξi≥0，i=0，1，2…l，并把目標函數表示為:其中 C 為懲罰參數，ξi為松弛項。由此又把線性不可分問題轉化為二次規劃問題，如下表示:

ξi≥0，i=1，2，...l，其中 C 為懲罰參數且 C ＞0。其對偶問題是:

0≤ai≤C，i=1，...，l，此時引進 lagrange 函數［6］為:

2.2 核函數

核函數的引入有效地解決了在高維空間中復雜的計算問題，在解決非線性問題時K(.;.)起著直接的作用，在實際中甚至不需要知道具體的映射是什么，只要選定核函數 K(.;.)就足夠了。由于不同的K(.;.)又可以產生不同的支持向量機，核函數K(.;.)的選擇要滿足Mercer條件。目前使用最多的核函數［6－7］如下。

(1)線性核函數

(2)多項式核函數

其中c≥0 是正定核，當c ＞ 0 時，稱為非奇次多x’)+c)d為奇次多項式核。

(3)高斯徑向基函數

(4)Sigmiod核

其中ρ是尺度值，θ為偏移值。支持向量機對立于感知機的第一層，lagrange乘子對應于感知機的權重。

3 電子郵件的預處理技術

3.1 郵件預處理

電子郵件也有自己的“信封”和“信文”，即郵件的首部和郵件的主體，是一種半結構化的文檔。郵件的首部主要有收件人的電子郵箱地址、發信人的電子郵箱地址、傳送郵件經過的路徑以及信件標題等，其中主體部分就是郵件傳送的內容。

首先對郵件抽取的主體內容進行分詞處理。對于英文郵件而言，可以非常簡單的實現分詞，因為每個英文單詞就是一個詞組。對于中文郵件就必須進行分詞處理。把中文的漢字序列切分成有意義的詞，就是中文分詞，也稱之為切詞。采用基于字典的字符串匹配的分詞方法中的最大正向匹配算法進行中文分詞。此方法能達到最好的分詞效果。

3.2 郵件的向量化

為了能用支持向量機的方法處理郵件，就必須對郵件的內容進行處理。在機器學習與文本分類領域中，廣泛采用向量空間模型來表示文本信息，文檔被轉換成具有高維空間的向量。用向量空間模型來表征電子郵件，這樣郵件的內容就轉化成高維向量空間中的一個點，對郵件內容的處理問題就轉化成了向量的運算問題，實現了文檔的可計算性和可操作性。

在此模型中，每個文檔表示為一個特征向量V(d)=(T1，W1;T2，W2;…Tn，Wn)∈(T × W)n，其中Ti為詞條項，通常為單字、詞、詞組、成語、短語等，詞條項相當于郵件的特征。Wi表示詞條項的權重，是該項在文檔中的重要程度，反映文檔的主題。由于Ti在訓練和測試過程中其值固定不變，所以可以看成特征向量的下標，因此特征向量可以簡化為V(d)=(W1，W2;…Wn)，Wi采用如下的方法計算。TF －IDF公式［4］如下:

其中tfik為項Ti在文本Di中出現的次數，N為訓練樣本總數，nk為訓練文本集中出現Ti的文本頻數。

3.3 特征向量的降維處理

由于郵件文本的內容很多，詞匯量很大，因此轉化的向量空間的維數肯定很大，維數越大，相應分類的精確度也就會降低。學習算法的復雜度和時間也會增加，因此要對特征向量進行降維，也就是減少訓練樣本向量空間中特征項的數量。

一般先對文檔中詞條做禁用詞處理，去掉一些沒有實際意義的虛詞，然后對文檔的特征進行選擇。采用評估函數的方法進行選擇，評估函數對特征集中的每個特征進行評分，把分數大小進行排序，最后選取預定數目的最佳特征作為結果的特征子集。常用的評估函數很多，采用信息增益。其公式如下:

其中P(Ci)表示Ci類文檔在訓練集中的出現概率，P(ti)表示訓練集中出現詞條ti的文檔概率，P(Ci|ti)表示包含詞條ti的文檔屬于Ci類的條件概率，P(Ci︱ti)表示文檔不包含詞條ti時屬于Ci類的條件概率，m表示類別數。最終只保留信息增益值最大的2000個特征項。

4 實驗分析及結果

實驗采用libsvm開源軟件包，libsvm提供了四個核函數，在本實驗中采用默認的徑向基函數，懲罰參數C取10。對垃圾郵件過濾的性能評價通常借用文本分類的相關指標。設測試集合中共有N(N=a+b+c+d)封郵件:a表示在測試集中實際為垃圾郵件且被svm分類器判斷為垃圾郵件的個數;b表示在測試集中實際為正常郵件(ham)且被svm分類器判斷為垃圾郵件的個數;c表示在測試集中實際為垃圾郵件且被svm分類器判斷為正常郵件的個數;d表示在測試集中實際為正常郵件且被svm分類器判斷為正常郵件的個數。因此，實際垃圾數目為a+c，實際正常郵件為b+d，以下幾個評價指標用來衡量垃圾郵件過濾系統的性能。

F1測試值:，實際上是查全率和正確率的綜合指標。

實驗采用的中文語料集是從ccert［8］網站下載的，從中選取了800封郵件，其中包括665封正常郵件，135封垃圾郵件。又從個人及同學的郵箱收集了300封郵件，其中包括200封正常郵件，100封垃圾郵件。這樣總郵件為1100封，正常郵件為865封，垃圾郵件為235封。隨機選取正常郵件500封，垃圾郵件140封作為訓練集，剩余的365封正常郵件和95封垃圾郵件作為測試集，這樣訓練集和測試集沒有交叉。支持向量機的方法與Bayse［5］方法和K－NN［5］方法實驗數據效果比較如表1所示:

表1 試驗結果指標值對比

可以看出支持向量機方法比Bayse方法和KNN方法性能要好，所以用支持向量機進行垃圾郵件過濾具有較好的效果，各項指標都達到93%以上，符合當前郵件過濾器的要求。

5 結束語

在分析支持向量機的基礎之上，根據文本分類思想提出了基于SVM的垃圾郵件過濾方法，通過實驗證明了該方法的可行性和高效性。同時也應注意到SVM方法的一些不足，如何根據具體問題選擇適合的內積函數還沒有理論依據，在核函數的選擇問題上也沒有很好的方法去指導針對具體問題的核函數選擇，SVM對訓練集和測試集的速度和規模的影響也是值得進一步研究的。

［1］Drucker H，Wu D，Vapnik V.Support Vector Machines for spam categorization［J］.IEEE Transactions on Neural Networks，1999，10:1048 －1054.

［2］金展，范晶，陳峰，等.基于樸素貝葉斯和支持向量機的自適應垃圾短信過濾系統［J］.計算機應用，2008，28(3):714－718.

［3］王祖輝，姜維.基于支持向量機的垃圾郵件過濾方法［J］.計算機工程，2009，35(13):188 －189.

［4］秦誼，裴崢，楊霽琳.改進的一分類支持向量機的郵件過濾研究［J］.計算機工程與應用，2009，45(20):151－153.

［5］張羽.基于支持向量機理論的垃圾郵件過濾模型［D］.成都:電子科技大學，2006.

［6］鄧乃揚，田英杰.數據挖掘中的新方法一一支持向量機［M］.北京:科學出版社，2004.

［7］安金龍，王正歐.一種新的支持向量機多類分類方法［J］.信息與控制，2004，6(3):262 －267.

［8］中國教育和科研網緊急響應組(CCERT)［Z］.http://www.ccert.edu.cn/spam/sa/datasets.htm，2010，2.