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

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

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

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

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

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

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

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

0 引 言

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

1 模糊支持向量分類機(jī)

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

設(shè)訓(xùn)練樣本集為,

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

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

其約束條件為,

2 垃圾郵件過濾預(yù)處理

2.1 郵件信頭和信體分離

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

2.2 中文分詞和去停用詞

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

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

2.3 郵件特征表示

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

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

3 基于FSVM的垃圾郵件分類機(jī)

3.1 FSVM分類機(jī)

設(shè)垃圾郵件的訓(xùn)練樣本集為,

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

其約束條件為,

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

通過構(gòu)造拉格朗日函數(shù)可將(3)式轉(zhuǎn)化為對(duì)偶形式,

對(duì)應(yīng)的約束條件為,

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

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

3.2 核函數(shù)

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

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

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

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

圖1 基于類中心的隸屬度設(shè)計(jì)方法

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

圖2 新的隸屬度設(shè)計(jì)方法

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

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

4 實(shí)驗(yàn)與結(jié)果

4.1 評(píng)價(jià)指標(biāo)

垃圾郵件過濾的性能評(píng)價(jià)常借用文本分類相關(guān)指標(biāo).本文在分類時(shí)選用以下3種評(píng)價(jià)指標(biāo).

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

4.2 實(shí)驗(yàn)系統(tǒng)框圖

實(shí)驗(yàn)系統(tǒng)框圖如圖3所示.訓(xùn)練郵件用于生成FSVM分類機(jī),新郵件則通過FSVM分類器進(jìn)行分類.

圖3 實(shí)驗(yàn)系統(tǒng)框圖

4.3 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)結(jié)果

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

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

表1 實(shí)驗(yàn)結(jié)果

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

5 總 結(jié)

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

[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]潘文峰.基于內(nèi)容的垃圾郵件過濾研究[D].北京：中國(guó)科學(xué)計(jì)算技術(shù)研究所,2004.

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

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

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

[9]杜 吉吉,劉三陽,齊小剛.一種新隸屬度函數(shù)的模糊支持向量機(jī)[J].系統(tǒng)仿真學(xué)報(bào),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.

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

趙海濤(1984—),男,碩士研究生,從事機(jī)器學(xué)習(xí)與智能計(jì)算研究.