基于雙隸屬度模糊支持向量機(jī)的郵件過濾

1、ComputerEngineeringandApplications計(jì)算機(jī)工程與應(yīng)用2010，46（2）93基于雙隸屬度模糊支持向量機(jī)的郵件過濾孫名松，高慶國，王宣丹SUNMing-song，GAOQing-guo，WANGXuan-dan哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150080CollegeofComputerScience&Technology，HarbinUniversityofScienceandTechnology，Harbin150080，ChinaE-mail：gaoqingguoSUNMing-song，GAOQing-guo，WANGXuan-dan.Mailf

2、ilteringbydualmembershipfuzzysupportvectormachine.（2）：ComputerEngineeringandApplications，2010，4693-95.Abstract：Basedonfuzzyofinformationcontainedinmailandasymmetryoflegitimatemailsandspamatthemisjudgmentprice，amailfilteringmethodisproposed.Itmakesuseofdualmembershipfuzzysupportvectormachine.Accordin

3、gtoprovideadifferentpairofmembershipforeachsample，theoptimalclassifierisderived.Itimprovestheaccuracyofmailfiltering.Thesimulationresultsshowthatthemethodisabletoeffectivelyreducethemisjudgmentoflegitimatemessagesasspam.Inadditional，ithasahighaccuracyandsoon.Keywords：spamfiltering；fuzzysupportvector

4、machine；membership；dualmembershipfuzzysupportvectormachine摘要：針對郵件所含信息的模糊性和合法郵件與垃圾郵件錯(cuò)分代價(jià)的不對稱性提出了基于雙隸屬度模糊支持向量機(jī)的郵件過濾方法，通過對每個(gè)樣本賦予不同的雙隸屬度，得到最優(yōu)分類器，提高了郵件過濾的正確率。經(jīng)仿真實(shí)驗(yàn)證明，該方法能夠有效降低將合法郵件誤判為垃圾郵件，而且有很高的正確率等特點(diǎn)。關(guān)鍵詞：垃圾郵件過濾；模糊支持向量機(jī)；隸屬度；雙隸屬度模糊支持向量機(jī)DOI：10.3778/j.issn.1002-8331.2010.02.029文章編號(hào)：（2010）1002833102-0093-03文

5、獻(xiàn)標(biāo)識(shí)碼：A中圖分類號(hào)：TP393.0981引言近年來，垃圾郵件在全球的泛濫影響和制約了電子郵件服務(wù)的健康、持續(xù)發(fā)展，對互聯(lián)網(wǎng)的安全和信息安全構(gòu)成了直接威脅。中國互聯(lián)網(wǎng)協(xié)會(huì)反垃圾郵件中心（www.anti-）最新發(fā)布的2008年第一季度反垃圾郵件狀況調(diào)查報(bào)告中調(diào)查顯示，中國網(wǎng)民每周收到垃圾郵件的比例為56.70%，垃圾郵件不僅浪費(fèi)網(wǎng)絡(luò)傳輸帶寬，增加了互聯(lián)網(wǎng)使用成本，而且也影響到人們的日常工作和生活。郵件過濾是一個(gè)在線二值分類問題，與普通的分過濾器需要將郵件區(qū)分為垃圾郵件或者正常郵件。類問題相比，郵件過濾有很多自身的特性：）實(shí)時(shí)性。郵件過濾要求過濾器必須具備較高的速度來（1處理所收到的郵件。而且

6、電子郵件的各種特征會(huì)隨時(shí)間不斷發(fā)生變化，為了使過濾器隨時(shí)間具有很好的泛化性，自學(xué)習(xí)功能也是郵件過濾的關(guān)鍵。（2）結(jié)構(gòu)性。日常所收發(fā)的郵件是一種半結(jié)構(gòu)化的數(shù)據(jù)，通收件人、正文、發(fā)送地址、附件等多個(gè)域。郵件的這常包含主題、種結(jié)構(gòu)性方便了對郵件特征的分析和提取，另一方面郵件的這種半結(jié)構(gòu)化使其具有更多的分類特征可供選擇。這些特征包括語言文本特征和郵件的各種行為特征。（3）模糊性。一封郵件的內(nèi)容針對于不同的收件人來說可能會(huì)有不同的看法，同一封郵件對于客戶甲來說可能是合法郵件，而同樣對于客戶乙來說可能就會(huì)被認(rèn)為是垃圾郵件，所以在郵件的過濾中應(yīng)該考慮郵件的這種模糊性的特性。（4）非對稱性。待過濾的郵件分布非

7、常不均勻，其中垃圾郵件占絕對多數(shù)。因此不能簡單的用分類問題的準(zhǔn)確率來評判郵件過濾方法的性能。對于郵件過濾來說，將合法郵件錯(cuò)判為垃圾郵件造成的不良后果遠(yuǎn)比將垃圾郵件誤判為是合法郵件要大得多。另一方面郵件正文長度也是很不均勻的，有的郵件正文很長，有的郵件正文可能會(huì)很短，判定那些正文很短、信息量很少的郵件更加困難?？傊?，以上郵件過濾的4種特性不同于一般文本分類，在研究垃圾郵件過濾時(shí)應(yīng)加以重點(diǎn)考慮。重點(diǎn)考慮郵件內(nèi)容的模糊性和非對稱性，應(yīng)用雙隸屬度模糊支持向量機(jī)進(jìn)行對垃圾郵件過濾，利用模糊隸屬度對每封郵件屬于合法郵件或垃圾郵件的程度做綜合評價(jià)。2模糊支持向量機(jī)1支持向量機(jī)（SupportVectorMa

8、chine，）是由VapnikSVM等人提出的一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理的新穎機(jī)器學(xué)習(xí)方法，它具有小樣本、良好的推廣性能、全局最優(yōu)等特點(diǎn)，已被成作者簡介：孫名松（1963-），男，教授，主要研究方向網(wǎng)絡(luò)應(yīng)用、網(wǎng)絡(luò)安全；高慶國（1980-），男，碩士研究生，主要研究方向網(wǎng)絡(luò)應(yīng)用、網(wǎng)絡(luò)安全；王宣丹（1983-），男，碩士研究生，主要研究方向網(wǎng)絡(luò)應(yīng)用、網(wǎng)絡(luò)安全。收稿日期：2008-07-25修回日期：2008-10-13942010，46（2）ComputerEngineeringandApplications計(jì)算機(jī)工程與應(yīng)用功地運(yùn)用于許多分類問題的研究。Lin等學(xué)者提出了模糊支持向量機(jī)方法（Fuz

9、zySupportVectorMachine，F(xiàn)SVM）2，將模糊技術(shù)應(yīng)用于支持向量機(jī)中，對不同的樣本采用不同的懲罰權(quán)系數(shù)，使得在構(gòu)造目標(biāo)函數(shù)時(shí)，不同的樣本有不同的貢獻(xiàn)，對含有噪聲或野值的樣本賦予較小的權(quán)值，從而達(dá)到消除噪聲與野值樣本影響的目的。在支持向量機(jī)的郵件分類方法中，一封郵件樣本均被明確的標(biāo)記為垃圾郵件或者是合法郵件。而在模糊支持向量機(jī)的郵件分類中，一封郵件訓(xùn)練樣本被賦予一個(gè)模糊隸屬度，當(dāng)采用模糊支持向量機(jī)作為郵件分類器時(shí)的原理如下：假設(shè)有郵件訓(xùn)練樣本集：D=（x1，y1，s）1，（xn，yn，s）n其中，xNiR表示訓(xùn)練集中第i個(gè)樣本郵件；yi-1，1代表郵件所屬類（垃圾郵件或合法郵

10、件）；si，1表示第i個(gè)郵件樣本屬于類的隸屬度，0為足夠小的數(shù)。假設(shè)Z=（x）為訓(xùn)練樣本從原始模式空間Rn映射到高維特征空間Z之間的映射關(guān)系，i是支持向量機(jī)目標(biāo)函數(shù)中的分類誤差項(xiàng)，sii為帶權(quán)的誤差項(xiàng)，得到最優(yōu)分類平面為下面的目標(biāo)函數(shù)的最優(yōu)解：n準(zhǔn)（，）=1T+C（si）ii=1約束條件為：yTi（zi+b）-1+i0，i=1，2，li0，i=1，2，l其中懲罰因子C為常數(shù)，表示線性可分函數(shù)yi的權(quán)系數(shù)。從而相應(yīng)的最優(yōu)分類面的判別函數(shù)為n（fx）=sgn（aiyiK（xi，x）+b）i=1其中K（xi，x）為核函數(shù)，K（xi，x）將高維特征空間中內(nèi)積運(yùn)算轉(zhuǎn)化為低維模式空間上的一個(gè)簡單的函數(shù)計(jì)算

11、。ai的條件式為：0aisiC，i=1，2，l，ai0相應(yīng)的樣本xi為支持向量，這里有兩種類型的支持向量，一種滿足0ai0，使TR+和TT+D-i-s-=，DiTi-，D-iT上面公式中：是一很小的正數(shù)，為了保證si0。4雙隸屬度模糊支持向量機(jī)首先郵件本身所含信息具有模糊性，另外對于一封正常郵件被誤判為垃圾郵件所造成的后果遠(yuǎn)比垃圾郵件被誤判為正常郵件的危害大的多，充分考慮到以上兩點(diǎn)，在郵件過濾的過程中采用雙隸屬度模糊支持向量機(jī)分類器進(jìn)行郵件過濾。在傳孫名松，高慶國，王宣丹：基于雙隸屬度模糊支持向量機(jī)的郵件過濾2010，46（2）95統(tǒng)的模糊支持向量機(jī)模型中，每一個(gè)訓(xùn)練樣本的隸屬函數(shù)中只有一個(gè)隸

12、屬度，而在雙隸屬度模糊支持向量機(jī)5模型中，每一個(gè)郵件訓(xùn)練樣本擁有兩個(gè)隸屬度，即屬于正常郵件的隸屬度和垃圾郵件的隸屬度。應(yīng)用雙隸屬度模糊支持向量機(jī)尋找最優(yōu)類超平面的問題描述為：lwmin，（a，k，w，a，i，）i=1kwTw+cmii+（1-m）iii=1約束條件為：wT準(zhǔn)（xk）+b1-ii0，i=1，2，lwT準(zhǔn)（xk）+b-1+ii0，i=1，2，l其對偶形式為：llmax，i+i-1ll（-）（-）準(zhǔn)（x）Tiijji準(zhǔn)（x）jiii=1i=1i=1j=1約束條件為：lli=i，0iCmii=1i=10iC（1-m）i，i=1，2，l轉(zhuǎn)化為二次規(guī)劃問題為，令i=i-i，所以上面的式子變

13、為llllmax，i+2i-1ijKii=1i=1（x，x）iii=12j=1約束條件為：li=0，0i+iCmii=10iC（1-m）i，i=1，2，l最終郵件的分類器變?yōu)椋海╢x）=sgn（wTl準(zhǔn)（x）+b）=sgn（i-i）K（xi，x）+b）i=1其中mi為郵件訓(xùn)練樣本的隸屬度。5仿真實(shí)驗(yàn)與結(jié)果分析5.1郵件過濾器性能指標(biāo)LR是合法郵件的查全率（LegitimateRecall）LR=n；lLP是合法郵件的準(zhǔn)確率（LegitimatePrecision）LR=n。slll準(zhǔn)確率與查全率反應(yīng)分類質(zhì)量的不同方面，兩者統(tǒng)一考慮組成新的指標(biāo)F1測試值：F1=2LPLR引入權(quán)重，把一個(gè)合法郵件

14、誤判的重要性要高于垃圾郵件誤判的倍，則精確率和錯(cuò)誤率分別為：WA=nll+nsslsWErr=nls+nslls同時(shí)假設(shè)沒有過濾器時(shí)，合法郵件能被正確識(shí)別，垃圾郵件全部被識(shí)別為合法郵件，定義基準(zhǔn)的精確率和基準(zhǔn)的錯(cuò)誤率為：WAb=NllsWErrb=Nls則可得到TCR測試值，TCR的值越大，說明郵件過濾器的性能越好。bTCR=WErrWErr=Nnls+nsl5.2實(shí)驗(yàn)結(jié)果及分析采用CCERT提供的2005年6月份中文語料集，其中包括合法郵件9042封，垃圾郵件樣本為20308封，垃圾郵件的比例為69.2%。從中隨機(jī)取出正常郵件1752封，垃圾郵件1024封。將這2776封分為4組，每次取3組

15、做為訓(xùn)練集，另一份為測試集。分別采取應(yīng)用支持向量機(jī)，模糊支持向量機(jī)和雙隸屬度支持向量機(jī)對數(shù)據(jù)進(jìn)行實(shí)驗(yàn)得到結(jié)果如表1。表1三種方法的對比結(jié)果LR（/%）LP（/%）F1/（%）WA（/%）TCRSVM85.6989.5587.5886.130.72FSVM94.3591.0092.6493.941.66DMFSVM95.5893.2694.4198.681.89通過對比實(shí)驗(yàn)，可以看出，對于合法郵件的正確率，前兩種方法的差別不大，但是所提出的方法就明顯高于前兩種方法，而且就合法郵件的查全率來說，基于雙隸屬度模糊支持向量機(jī)的方法就要明顯好于標(biāo)準(zhǔn)的支持向量機(jī)和模糊支持向量機(jī)方法。從后面三個(gè)綜合性的評價(jià)

16、指標(biāo)也可以看出基于雙隸屬度模糊支持向量機(jī)的郵件過濾性能都優(yōu)于其他兩種方法。6總結(jié)針對郵件內(nèi)容的模糊性和誤判郵件代價(jià)的非對稱性，提出了基于雙隸屬度模糊支持向量機(jī)的郵件過濾方法，并對該方法中隸屬度的確定進(jìn)行了分析和研究，并對隸屬度函數(shù)進(jìn)行了改進(jìn)，而且把該方法應(yīng)用到雙隸屬度模糊支持向量機(jī)中，最后得到了雙隸屬度模糊支持向量機(jī)的分類器模型，并進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該方法的性能優(yōu)于基于支持向量機(jī)的郵件過濾方法和基于模糊支持向量機(jī)的郵件過濾方法。參考文獻(xiàn)：1VapnikVN.EstimationsofdependencebasedonempiricaldataM.NewYork：SpringerVerlag，1982.2LinCF，WangSD.FuzzysupportvectormachinesJ.IEEETransactionsonNeuralNetworks，2002，13（2）：464-471.3ChangJH，HaoPY.A