王 強，賈銀山

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

1 引言

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

2 支持向量機的基本原理

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

圖1 最優(yōu)分類超平面

2.1 線性支持向量分類機

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

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

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

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

2.2 核函數(shù)

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

(1)線性核函數(shù)

(2)多項式核函數(shù)

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

(3)高斯徑向基函數(shù)

(4)Sigmiod核

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

3 電子郵件的預(yù)處理技術(shù)

3.1 郵件預(yù)處理

電子郵件也有自己的“信封”和“信文”，即郵件的首部和郵件的主體，是一種半結(jié)構(gòu)化的文檔。郵件的首部主要有收件人的電子郵箱地址、發(fā)信人的電子郵箱地址、傳送郵件經(jīng)過的路徑以及信件標題等，其中主體部分就是郵件傳送的內(nèi)容。

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

3.2 郵件的向量化

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

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

其中tfik為項Ti在文本Di中出現(xiàn)的次數(shù)，N為訓(xùn)練樣本總數(shù)，nk為訓(xùn)練文本集中出現(xiàn)Ti的文本頻數(shù)。

3.3 特征向量的降維處理

由于郵件文本的內(nèi)容很多，詞匯量很大，因此轉(zhuǎn)化的向量空間的維數(shù)肯定很大，維數(shù)越大，相應(yīng)分類的精確度也就會降低。學(xué)習(xí)算法的復(fù)雜度和時間也會增加，因此要對特征向量進行降維，也就是減少訓(xùn)練樣本向量空間中特征項的數(shù)量。

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

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

4 實驗分析及結(jié)果

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

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

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

表1 試驗結(jié)果指標值對比

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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