基于模糊支持向量機的中文垃圾郵件過濾方法

趙海濤,魏 延,賴 敏,陳守剛

(1.重慶師范大學數(shù)學與計算機科學學院,重慶 400047;2.重慶正大軟件職業(yè)技術學院,重慶 400056)

基于模糊支持向量機的中文垃圾郵件過濾方法

趙海濤1,2,魏 延1,賴 敏1,陳守剛1

(1.重慶師范大學數(shù)學與計算機科學學院,重慶 400047;2.重慶正大軟件職業(yè)技術學院,重慶 400056)

隨著電子郵件的廣泛使用,垃圾郵件問題也日益嚴峻.基于郵件內容的過濾是當前解決垃圾郵件問題的主流技術之一.提出了一種基于帶有模糊隸屬度的模糊支持向量機對中文垃圾郵件過濾的方法,同時,為解決FSVM中隸屬度函數(shù)的確定問題,使用了一種改進的基于類中心的隸屬度函數(shù)設計方法.通過實驗,使用FSVM對垃圾郵件過濾能夠取得較好的效果.

垃圾郵件;支持向量機;模糊支持向量機;模糊隸屬度;隸屬度函數(shù)

0 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展,電子郵件作為一種現(xiàn)代通信手段受到廣泛使用,但同時也受到大量垃圾郵件的騷擾.支持向量機(SVM)是Vapnik[1]提出的一種基于統(tǒng)計學習理論的機器學習方法,它以最大化分類間隔構造最優(yōu)分類超平面來提高分類器的泛化能力,具有訓練樣本小、泛化能力強、全局最優(yōu)等優(yōu)點.本文提出一種基于帶有模糊隸屬度的模糊支持向量機對中文垃圾郵件過濾的方法,通過實驗證實,該方法對垃圾郵件過濾能取得較好的效果.

1 模糊支持向量分類機

標準的或者說傳統(tǒng)的SVM主要是用于解決非模糊的兩類劃分和多類劃分的問題.每個樣本點都被假定屬于一個并且是唯一的一個類.而在許多現(xiàn)實中的問題中,一些訓練樣本點數(shù)據(jù)是以不同的隸屬度屬于不同的類.實際上,一封郵件是否是垃圾郵件,以及在多大程度上是垃圾郵件,不同的用戶有不同的理解.因此,對郵件過濾的處理應被視為不確定信息的處理問題.本文根據(jù)文獻[2,3]中提出的模糊支持向量機(FSVM)方法來對垃圾郵件進行過濾.

設訓練樣本集為,

其中,xi∈Rm,yi∈{+1,-1},核函數(shù)為z=φ(x),則訓練集變?yōu)?φ(xi),yi),分類超平面為w·φ(xi) +b=0.

引入模糊因子si(0＜si≤1,i=1,2,…,n)來表示第i個郵件樣本屬于正類的程度.此時,訓練集就轉化為帶有模糊因子的訓練樣本集(φ(xi),yi, si)),設sζii為帶權松弛因子,C＞0為懲罰參數(shù).模糊支持向量機(FSVM)的最優(yōu)分類超平面的求解轉化成一個二次規(guī)劃問題：

其約束條件為,

2 垃圾郵件過濾預處理

2.1 郵件信頭和信體分離

電子郵件的一般格式包括信頭和信體兩部分.其郵件過濾預處理為：首先分離信頭和信體,有時候僅僅根據(jù)信頭信息就可以判斷一封郵件是否是垃圾郵件;然后分別進行基于信頭和信體的過濾.

2.2 中文分詞和去停用詞

中文電子郵件不同于英文郵件,每個詞條間沒有固定的空格分隔符.為了將中文電子郵件向量化,首先需要進行分詞.本文采用正向最大匹配法和逆向最大匹配法[4]相結合的分詞方案,即先根據(jù)標點對文檔進行粗切分,把文檔分解成若干個句子,然后再對這些句子用正向最大匹配法和逆向最大匹配法進行掃描切分,如果兩種分詞方法得到的匹配結果相同,則認為分詞正確,否則按最小交集處理.

其次,分詞處理完成之后,得到一系列文本單詞所組成的表列,特征辭典是由表列中的單詞所構成的集合.為了縮小文本特征辭典,提高郵件分類器的訓練分類效率,通常需要對辭典進行去停用詞處理.

2.3 郵件特征表示

郵件的特征表示主要采用向量空間模型(Vector Space Model,VSM),在郵件向量空間模型中,一封郵件就是一篇文檔(Document)d,郵件中的每個詞就是一個特征項(Term)t,所有的特征項構成特征詞典(Term List),{tk│1≤k≤n}.這樣,文檔 d則被表示為d(t1,t2,…,tN).對特征辭典中的任意特征項而言,由于它在郵件中出現(xiàn)的位置和出現(xiàn)的頻率不同,對郵件分類結果的影響也不同.故應該給每個特征項賦予一定的權重來表示其重要程度,故文檔 d又被表示成,d(t1,w1;t2,w2;…,tN, wN),可簡記為,d= d(w1;w2;…;wN),其中,ti(i =1,2,…,N)為特征項,wi為ti的權重.權重wi一般被定義為在詞 ti在文檔d中出現(xiàn)頻率tf(t,d)的函數(shù),常見的有布爾函數(shù)、平方根函數(shù)、對數(shù)函數(shù)和TFIDF函數(shù)等.本文采用 TFIDF函數(shù),公式為,

其中,w(t,d)為特征項 t在文檔d中的權重,tf(t, d)為特征項t在文檔d中的詞頻,N為訓練樣本的總數(shù),nt為訓練樣本集中出現(xiàn)特征項t的文本數(shù),分母為歸一化因子.

3 基于FSVM的垃圾郵件分類機

3.1 FSVM分類機

設垃圾郵件的訓練樣本集為,

其中,xi∈Rm,yi∈{+1,-1},(+1即正類,代表合法郵件;-1即負類,代表垃圾郵件),Z=φ(x)表示從Rn到一個特征空間Z的非線性映射,則訓練樣本集變?yōu)?φ(xi),yi),分類超平面為w·φ(xi)+b =0;引入模糊因子si(0＜si≤1,i=1,2,…,n)來表示第i個郵件樣本屬于正類(即合法郵件)的程度.此時,訓練集就轉化為帶有模糊因子的訓練樣本集(φ(xi),yi,si)),又設 siζi為帶有權重的松弛因子,C為懲罰參數(shù)(值大于0)用來控制對錯分樣本懲罰的程度.模糊支持向量機(FSVM)的最優(yōu)分類超平面的求解轉化成一個二次規(guī)劃問題,

其約束條件為,

yi(w·xi+b)≥1-ζi,ζi≥0, i=1,2,…,n

通過構造拉格朗日函數(shù)可將(3)式轉化為對偶形式,

對應的約束條件為,

求解(4)式可得到其最優(yōu)解α＊,同時,利用原始約束可以找到閾值b＊,從而可以把模糊支持向量機最優(yōu)分類函數(shù)轉化為,

在式(4)、(5)中,K(xi,xj))為核函數(shù),表示某特征空間 Z的內積,其值為,

3.2 核函數(shù)

核函數(shù)的基本作用是將非線性可分輸入空間等價映射到線性可分的高維空間.常見核函數(shù)包括：多項式核函數(shù)(Poly),高斯徑向基核函數(shù)(RBF)與 S型核函數(shù)(Sigmoid).

多項式核函數(shù)的優(yōu)點在于計算的復雜度很小,需要存儲的數(shù)據(jù)單元小,缺點是它的運算次數(shù)很難控制.一般來講,多項式的次數(shù)越高對于要處理的問題的精度和推廣能力越好,但是次數(shù)太高的情況下容易出現(xiàn)“過學習”的問題.徑向基函數(shù)的優(yōu)點是其本身是一個對稱的函數(shù),在沒有任何先驗知識的境況下經(jīng)常被采用.而Sigmoid核函數(shù),SVM實現(xiàn)就包含一個隱層的多層感知器,隱層節(jié)點數(shù)由算法自動確定.在實際應用中,常根據(jù)具體問題構造相應的核函數(shù).一般對于文本的非線性可分情況較為常用的核函數(shù)為RBF核函數(shù)和Poly核函數(shù).

3.3 模糊隸屬度的確定和模糊隸屬度函數(shù)

傳統(tǒng)的模糊隸屬度的確定方法[2,3]是一種基于類中心的隸屬度函數(shù)設計方法,使樣本對分類所起的作用隨著樣本遠離類別的幾何中心而逐漸減小,這樣可以弱化噪聲或孤立點的影響,但同時也大大弱化了支持向量對分類超平面的作用,其最終結果將會使所獲得的分類超平面偏離最優(yōu)分類超平面.如圖1所示,從圓心到圓周,訓練樣本的隸屬度依次減小,這樣,支持向量(粗體表示)的隸屬度很小,從而容易導致分類超平面偏離最優(yōu)分類超平面.

圖1 基于類中心的隸屬度設計方法

參照文獻[5,6]中所給出的模糊隸屬度確定方法,同時,分析比較了文獻[7-9]提出的隸屬度函數(shù),本文使用一種簡單快捷有效的隸屬度函數(shù),即改進的基于類中心的隸屬度函數(shù)設計方法：樣本對分類所起的作用隨著樣本遠離類別的幾何中心而逐漸增大,即將樣本到類別幾何中心的距離與該類中離類別幾何中心最遠的樣本到類別幾何中心的距離的比值定義為隸屬度;對于那些離類中心太遠的噪聲和孤立點,設置一個閾值,當樣本與類別幾何中心的距離大于閾值時,就賦一個很小的隸屬度;閾值根據(jù)兩類樣本幾何中心之間的距離和樣本的稠密情況決定,通過調整閾值,就可以使支持向量的隸屬度較大,而噪聲或孤立點的隸屬度很小,即在給噪聲或孤立點賦小隸屬度的同時,保證了支持向量有較大的隸屬度,從而使分類精度較高.如圖2所示,從圓心到內圓周,訓練樣本的隸屬度依次增大,而內圓周與外圓周之間的訓練樣本則賦予很小的隸屬度.這樣,通過給噪聲或孤立點很小隸屬度避免了噪聲或孤立點的干擾,保證了支持向量有較大的隸屬度,從而使分類精度提高.

圖2 新的隸屬度設計方法

在兩類分類中,使用正類樣本的均值作為正類的中心,記為x+,即;負類樣本的均值作為負類的中心,記為x-,即x正類的半徑,,負類的半徑,r-=每個正類樣本到正類中心的距離為,d+;每個負類樣本到負類中心的距離為,,平均距離,m-=.兩類中心的距離為,t=.θ為一個很小的正數(shù),作為噪聲和孤立點的隸屬度.λ＞0為一個控制因子,使 t·λ·m+/(m+m-)＜r+和 t·λ·m-/(m++m-)＜r-成立,則隸屬度函數(shù)定義為：

式(6)中,δ是足夠小的正數(shù),是為了保證si＞0而設置的.

4 實驗與結果

4.1 評價指標

垃圾郵件過濾的性能評價常借用文本分類相關指標.本文在分類時選用以下3種評價指標.

在以上3種評價指標中,Ns→s表示將垃圾郵件判為垃圾郵件的樣例數(shù),Ss→h表示將垃圾郵件判為合法郵件的樣例數(shù),Nh→s表示將合法郵件判為垃圾郵件的樣例數(shù),Ns為垃圾郵件總數(shù).

4.2 實驗系統(tǒng)框圖

實驗系統(tǒng)框圖如圖3所示.訓練郵件用于生成FSVM分類機,新郵件則通過FSVM分類器進行分類.

圖3 實驗系統(tǒng)框圖

4.3 實驗環(huán)境及實驗結果

本實驗環(huán)境為：CPU 2.0 GHz,Windows XP SP2, 80 G硬盤,512 M內存.

實驗所用語料來自于中國教育和科研網(wǎng)緊急響應組(CCERT)于2005年6月公布的電子郵件數(shù)據(jù)集.實驗所采用的電子郵件樣本是從中隨機抽取的一部分,其中垃圾郵件為2 000封,合法郵件為2 000封,共計4 000封電子郵件樣本.實驗共進行了10次,每次實驗都從數(shù)據(jù)集中隨機抽取同等數(shù)量郵件.訓練集共選取2 000封,其中垃圾郵件為1 000封,合法郵件為1 000封.測試集共選取2 000封,其中垃圾郵件為1 000封,合法郵件為1 000封.前5次實驗選取多項式核函數(shù)(Poly)進行郵件過濾,分別得到評價指標 P、R、F的值,并求得5次實驗數(shù)據(jù)的平均值.后5次選取徑向基核函數(shù)(RBF)進行郵件過濾,方法同 Poly核函數(shù)過程.最后與貝葉斯方法和支持向量機方法(使用多項式核函數(shù),訓練測試樣本分布同F(xiàn)SVM,并取3次的平均值)進行了對比.測試結果如表1所示.

表1 實驗結果

由表1數(shù)據(jù)可知,FSVM方法能夠取得更好的分類效果.其R、P和F的測試值均比貝葉斯方法的測試值高出8到10個百分點,比支持向量機方法高2到4個百分點.在所用時間方面,實驗中發(fā)現(xiàn)模糊支持向量機方法比貝葉斯方法較快,與支持向量機方法速度接近或稍快.

5 總 結

本文將模糊支持向量機分類方法引入中文垃圾郵件過濾技術中.針對傳統(tǒng)的模糊隸屬度的確定方法存在因噪聲和孤立點干擾而影響分類效果的缺點,本文使用了一種改進的隸屬度函數(shù)設計方法.通過仿真實驗,使用該方法對垃圾郵件過濾能夠取得較好的效果,具有較高的可行性.

[1]Vapnik V N.The Nature of Statistical Learning Theory[M].New Y ork：Spring-Verlag,1995.

[2]Lin C F,Wang S D.Fuzzy support vector machines[J].IEEE Transaction on Neural Networks,2002,13(2)：464-471.

[3]Lin C F,Wang SD.Fuzzy support vector machines with automatic membership setting[J].Stud Fuzz,2005,177(1)：233-254.

[4]潘文峰.基于內容的垃圾郵件過濾研究[D].北京：中國科學計算技術研究所,2004.

[5]劉 暢,孫德山.模糊支持向量機隸屬度的確定方法[J].計算機工程與應用,2008,44(11)：41-42.

[7]哈明虎.一種新的模糊支持向量機[J].計算機工程與應用,2009,45(25)：151-153.

[8]范婕婷,賴惠成.一種基于SVM算法的垃圾郵件過濾方法[J].計算機工程與應用,2008,44(28)：95-97.

[9]杜 吉吉,劉三陽,齊小剛.一種新隸屬度函數(shù)的模糊支持向量機[J].系統(tǒng)仿真學報,2009,21(7)：1901-1903.

Filter Methods of Chinese Spasm Based on Fuzzy Support Vector Machine

ZHAO Haitao1,2,WEI Yan1,LAI Min1,CHEN Shougang1

(1.School of Mathmatics and Computer Science,Chongqing Normal University,Chongqing 400047,China; 2.Chongqing Zhengda Software Polytechnic College,Chongqing 400047,China)

With the widespread use of e-mail,the issue of spam is also increasingly severe.Content-based filtering is one of the mainstream technologies used so far.In this paper,a method of fuzzy support vector machine with a fuzzy membership degree for Chinese spam filtering was proposed for the decision of membership function of FSVM.A new method of membership function which improves the method based on center of cluster was used.After the experiment,using FSVM,spam filter can achieve better results.

spam;support vector machine;fuzzy support vector machine;fuzzy membership;membership function

TP18

：A

1004-5422(2010)02-0133-04

2010-03-14.

重慶市教委科技計劃基金資助項目(K J090823).

趙海濤(1984—),男,碩士研究生,從事機器學習與智能計算研究.