陳鐵軍，靖豐年，段誼海

（鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州450001）

0 引 言

基于內(nèi)容的垃圾郵件過濾法比一般白名單與黑名單技術(shù)、規(guī)則過濾以及基于關(guān)鍵詞匹配的內(nèi)容掃描等智能化程度高，可采用屬于有監(jiān)督學(xué)習(xí)的樸素貝葉斯分類器，實(shí)踐結(jié)果表明分類效果佳。其中，貝葉斯過濾器是基于文本的過濾技術(shù)，準(zhǔn)確率較高，但是，現(xiàn)有樸素貝葉斯分類器基于一個(gè)假設(shè)：從郵件中提取的文本特征是相互獨(dú)立的。這是一個(gè)很強(qiáng)的假設(shè)，因?yàn)槲谋咎卣魇窍嗷リP(guān)聯(lián)的，所以現(xiàn)有貝葉斯算法過多的簡(jiǎn)化文本特征的相關(guān)性，導(dǎo)致判別垃圾郵件的召回率減低。在早期基于貝葉斯分類器的算法中，特征值被簡(jiǎn)化為0和1，沒有體現(xiàn)特征出現(xiàn)的概率，為更多利用文本特征的相關(guān)性，提出基于多項(xiàng)式模型的貝葉斯分類器［2］。與伯努利模型相對(duì)比，多項(xiàng)式模型更精確地描述了特征的重要性，然而，算法時(shí)間代價(jià)卻激增由O（n）上升到O（n2）。另外，對(duì)于那些出現(xiàn)次數(shù)較少的對(duì)判斷會(huì)造成較大的誤差。針對(duì)以上情況，本文提出基于RSSI特征選擇器的貝葉斯垃圾郵件過濾算法，剔除無(wú)關(guān)特征和不穩(wěn)定特征，有效減少過擬合，提高算法效率。與現(xiàn)有樸素貝葉斯算法 （nave Bayes）和支持向量機(jī) （support vector machine，SVM）等算法相比，RSSI算法能顯著減少分類時(shí)間，降低合法郵件被誤判的概率。

1 樸素貝葉斯分類器的構(gòu)建

樸素貝葉斯分類器是有監(jiān)督學(xué)習(xí)的一種，分類器對(duì)郵件進(jìn)行分類時(shí)，考慮到時(shí)間開支本文選擇文檔頻數(shù)［3］（document frequency，DF）作為特征來(lái)進(jìn)行建模。通過郵件解析和中文分詞［4］預(yù)處理，對(duì)出現(xiàn)的詞語(yǔ)生成一個(gè)詞典，設(shè)郵件的特征向量為X ＝（x1，x2，…，xi，…，xn）［5］，xi表示每一封郵件的特征項(xiàng)。郵件共有兩類：正常的郵件集合G和垃圾郵件集合B，其中G ＝（G1，G2，…，Gi，…，Gn），B ＝（B1，B2，…，Bi，…，Bn）。設(shè)郵件E 的特征向量為XE＝（，，…，…），根據(jù)貝葉斯公式，則郵件E 屬于垃圾郵件的概率為

就伯努利模型而言，xi取1或0，設(shè)參數(shù)＝P（xi＝1｜B）＝P（xi＝1｜G）＝P（B），給定一個(gè)訓(xùn)練集合可以得出參數(shù)的似然函數(shù)

y（i）＝1表示第i個(gè)訓(xùn)練樣本屬于B 集合，1 ｛｝表示指示符號(hào)，規(guī)定1｛true｝＝1，1｛fault｝＝0，進(jìn)而可以得出給定測(cè)試郵件屬于垃圾郵件的概率

2 貝葉斯多項(xiàng)式模型

伯努利模型貝葉斯分類器可根據(jù)特征項(xiàng)的出現(xiàn)與否計(jì)算給定測(cè)試郵件與正常郵件和垃圾郵件的匹配程度，對(duì)郵件分類。由于伯努利模型xi只能取兩個(gè)值1和0，為表達(dá)更多的特征信息，提出了多項(xiàng)式模型［6］，此時(shí)對(duì)X ＝（X1，X2，…，Xi，…，Xn），Xi表示郵件經(jīng)中文分詞后第i 個(gè)字符的標(biāo)識(shí)，n表示郵件的長(zhǎng)度。給定參數(shù)＝P（xj＝i｜B），＝P（xj＝i｜G）＝P（B），給定訓(xùn)練集合｛（x（i），y（i））；i＝1，…，m｝，這里x（i）＝，…，），ni是第i個(gè)訓(xùn)練樣本的郵件長(zhǎng)度，可以得到參數(shù)，的似然函數(shù)

求得參數(shù)的極大似然估計(jì)

ti取1或0，以上就是多項(xiàng)式模型貝葉斯分類器的數(shù)學(xué)模型。比較式 （6）和式 （11），發(fā)現(xiàn)在計(jì)算判別X 屬于垃圾郵件的概率時(shí)，計(jì)算量差別在上 （注意兩式中｜B不同），比較式 （3）和式 （8）發(fā)現(xiàn)多項(xiàng)式模型的計(jì)算量是O（n2），而伯努利模型中的計(jì)算量?jī)H為O（n）。對(duì)計(jì)算機(jī)來(lái)說O（n2）的運(yùn)算量尚可接受，精簡(jiǎn)算法結(jié)構(gòu)將大幅減少運(yùn)算時(shí)間，下面將對(duì)生成的特征向量X 簡(jiǎn)化。

3 RSSI算法過程

對(duì)式 （11）剖析發(fā)現(xiàn)計(jì)算了大量的無(wú)關(guān)特征項(xiàng)［9］，如字典中收納的量詞、語(yǔ)氣詞等，對(duì)正常郵件和垃圾郵件建模過程中發(fā)現(xiàn)，這些詞的在正常郵件和垃圾郵件出現(xiàn)概率和大致相同，固可以利用這個(gè)特征來(lái)對(duì)生成的字典進(jìn)行合理的 “瘦身”。

設(shè)閾值為T ＝5%，如果超過了這個(gè)范圍，認(rèn)為此為相關(guān)特征項(xiàng)，如果在這個(gè)范圍內(nèi)，則認(rèn)為是無(wú)關(guān)特征項(xiàng)，在生成字典中刪除此特征項(xiàng)

在對(duì)一些錯(cuò)誤分類的郵件研究發(fā)現(xiàn)，有些出現(xiàn)頻次很小的特征項(xiàng)是導(dǎo)致分類錯(cuò)誤的主因，比如特征項(xiàng)xi在集合G 中出現(xiàn)一次，而沒有在集合B 中出現(xiàn)，顯然這存在很大的偶然因素，然而貝葉斯分類器通過對(duì)特征項(xiàng)xi的計(jì)算后將有極大的傾向把郵件X 分給集合G 。為了克服這個(gè)缺點(diǎn)，我們?cè)O(shè)閾值Tf＝5，有關(guān)計(jì)算公式如下

到此，我們降低了X 維數(shù)，降低了算法的運(yùn)算量，減少了內(nèi)存空間的消耗，并提高了分類正確率。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

在上述基于多項(xiàng)式模型的貝葉斯垃圾郵件分類算法中，采用RSSI方法降低特征維數(shù)，本文仿真基于matlab平臺(tái)，WEKA Java API和Eclipse開發(fā)環(huán)境，選用PU 系列英文語(yǔ)料庫(kù)和ZH1 中文語(yǔ)料庫(kù)，實(shí)驗(yàn)方法采用 “十字交叉驗(yàn)證法”［10］，將每一個(gè)語(yǔ)料庫(kù)中平均分10份，9份作為訓(xùn)練集，1份作為測(cè)試集，采用原始處理訓(xùn)練集和測(cè)試集txt文本集為一個(gè)m×n維的矩陣［11］，m 為集合中元素的個(gè)數(shù)，n為幾何元素的權(quán)值，1表示對(duì)應(yīng)特征項(xiàng)出現(xiàn)，0表示不出現(xiàn)。

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

為了評(píng)價(jià)算法的好壞，引入正確率 （RPrecision）和召回率 （RRecall）兩個(gè)概念

式中：A——垃圾郵件被正確分類的數(shù)量，B——被錯(cuò)誤判定為垃圾郵件的數(shù)量。正確率越高，正確分類垃圾郵件和正常郵件的數(shù)量越多

式中：A——正確區(qū)分垃圾郵件的數(shù)量，C——漏掉的垃圾郵件的數(shù)量。召回率越高，檢測(cè)到的垃圾郵件越多，漏掉的垃圾郵件越少。

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

實(shí)驗(yàn)中，首先對(duì)傳統(tǒng)貝葉斯算法和本文改進(jìn)算法對(duì)郵件的分類正確率進(jìn)行測(cè)試，采用 “十字交叉驗(yàn)證法”，首先選取集合中的70%作為樣本集，利用Weka軟件對(duì)其進(jìn)行訓(xùn)練，建立特征集。然后對(duì)集合中剩下的30%提取特征，進(jìn)行分類測(cè)試，隨著特征數(shù)目的不算增加，對(duì)分類正確率的影響如圖1所示。

圖1 兩種算法下選擇特征個(gè)數(shù)對(duì)郵件正確率的影響

從圖1可以看出，當(dāng)特征個(gè)數(shù)較少時(shí)，分類準(zhǔn)確率較低，是因?yàn)樘卣黜?xiàng)不能完全反映文本特征，導(dǎo)致文本區(qū)分度不高，當(dāng)特征數(shù)量大于等于200時(shí)，分類準(zhǔn)確率趨于穩(wěn)定，此時(shí)出現(xiàn)了大量冗余的特征項(xiàng)。觀察到改進(jìn)后的方法在特征個(gè)數(shù)較少時(shí)仍有很高的準(zhǔn)確率，趨于穩(wěn)定時(shí)特征個(gè)數(shù)比改進(jìn)前少，這是因?yàn)楦倪M(jìn)算法剔除了大量的無(wú)關(guān)特征性，使算法在僅有少量特征個(gè)數(shù)下就能充分反映文本特征。

研究特征數(shù)目對(duì)召回率的影響，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 兩種算法下選擇特征個(gè)數(shù)對(duì)郵件召回率的影響

從上圖中可以看出，在特征項(xiàng)個(gè)數(shù)較少時(shí)，郵件召回率較低，這是因?yàn)樘卣鱾€(gè)數(shù)不能充分描述垃圾郵件文本，導(dǎo)致漏掉的垃圾郵件過多，隨著特征數(shù)量的增加，召回率出現(xiàn)極大值，其原因是特征項(xiàng)正好反映文本特征，不同類型的郵件區(qū)分度高。隨著特征數(shù)量的增多，算法召回率下降趨于平穩(wěn)，這是因?yàn)閾诫s與分類無(wú)關(guān)的特征項(xiàng)，產(chǎn)生分類干擾，使分類效果變壞。兩條曲線比較發(fā)現(xiàn)，改進(jìn)前的極值出現(xiàn)在300左右，而改進(jìn)后的極值在200 左右，這是因?yàn)樘蕹藷o(wú)關(guān)特征項(xiàng)使極值提前，因?yàn)樘蕹艘徊糠址诸惛蓴_，所以提高了召回率。

測(cè)試改進(jìn)算法的時(shí)間代價(jià)，對(duì)分類器進(jìn)行訓(xùn)練后，隨機(jī)選取測(cè)試集中100份郵件進(jìn)行測(cè)試，得出結(jié)果見表1。

表1 傳統(tǒng)貝葉斯算法和本文算法的分類時(shí)間

分類時(shí)，對(duì)測(cè)試郵件的特征向量X 分別與垃圾郵件模型和正常郵件模型相匹配，看哪種模型匹配度高。改進(jìn)后算法分類時(shí)間短的原因是去除了無(wú)關(guān)特征項(xiàng)，在最后計(jì)算P（B｜X）時(shí)特征項(xiàng)數(shù)比改進(jìn)前少，固節(jié)省了計(jì)算時(shí)間。

4.4 與其它垃圾郵件算法的比較

對(duì)于時(shí)下流行的K 最鄰近算法、支持向量機(jī)算法用于垃圾郵件分類，實(shí)驗(yàn)選取了共1089封郵件的實(shí)驗(yàn)集，對(duì)比了KNN 算法、SVM 算法和RSSI算法，實(shí)驗(yàn)結(jié)果見表2。

表2 RSSI算法、KNN 算法、SVM 算法性能對(duì)比

從表2 中可以看出：①?gòu)泥]件過濾性能上看，基于RSSI的貝葉斯垃圾郵件過濾算法的正確率和召回率與SVM 算法相當(dāng)，但比KNN 算法要好；②從郵件過濾速度上看，基于RSSI的貝葉斯垃圾郵件過濾算法要比KNN 算法和SVM 算法快一倍以上，這是因RSSI算法有效減少特征項(xiàng)，降低了計(jì)算機(jī)的工作量。

5 結(jié)束語(yǔ)

貝葉斯垃圾郵件分類模型是廣泛使用的一種垃圾郵件分類模型，但是需要使用大量的訓(xùn)練集合訓(xùn)練，占用大量網(wǎng)絡(luò)資源和系統(tǒng)資源見下方［12］。本文提出了基于RSSI的貝葉斯垃圾郵件過濾算法，與傳統(tǒng)貝葉斯垃圾郵件分類機(jī)制相比：①本文算法能去除無(wú)關(guān)特征，使召回率極大值提前，準(zhǔn)確率在取較小值即達(dá)到平穩(wěn)，改進(jìn)了算法性能；②本文算法由于去除了無(wú)關(guān)特征的干擾，提高了準(zhǔn)確率和召回率，減少了計(jì)算時(shí)間，提高了效率。

與KNN 算法和SVM 算法相比，性能相當(dāng)，但由于簡(jiǎn)化了算法，執(zhí)行效率得到了大幅提升。

［1］ZHENG Dongdong，SONG Shunlin.Survey of image spam filtering technology ［J］.Computer Engineering and Design，2010，31（1）：41－44（in Chinese）.［鄭冬冬，宋順林.圖片垃圾郵件過濾技術(shù)綜述［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31 （1）：41－44.］

［2］EP Sanz JGHJ.Email spam filtering ［J］.Advances in Computers，2008，74：45－114.

［3］LI Xiao，LUO Junyong，YIN Meijuan.Email filtering based on structural feature analysis and text classification ［J］.Computer Engineering and Design，2010，31 （21）：4555－4558 （in Chinese）.［李瀟，羅軍勇，尹美娟.基于結(jié)構(gòu)特征分析與文本分類的郵件篩選 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31 （21）：4555－4558.］

［4］YANG Kaifeng，ZHANG Yikun，LI Yan.Feature selection method based on document frequency ［J］.Computer Engineering，2010，36 （17）：33－35 （in Chinese）. ［楊凱峰，張毅坤，李燕.基于文檔頻率的特征選擇方法 ［J］.計(jì)算機(jī)工程，2010，36 （17）：33－35.］

［5］LIU Hongzhi.Research on Chinese word segmentation techniques［J］.Computer Development ＆Applications，2010，23（3）：1－3 （in Chinese）.［劉紅芝.中文分詞技術(shù)的研究 ［J］.電腦開發(fā)與應(yīng)用，2010，23 （3）：1－3.］

［6］LIANG Zhiwen，YANG Jinmin，LI Yuanqi.A Bayesian spam filtering algorithm based on polynomial model and low risk［J］.Journal of Central South University （Science and Technology），2013，44（7）：2787－2792（in Chinese）. ［梁志文，楊金民，李元旗.基于多項(xiàng)式模型和低風(fēng)險(xiǎn)的貝葉斯垃圾郵件過濾算法 ［J］.中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，44 （7）：2787－2792.］

［7］ZHAO Jing.Research on spam filtering technologies based on content characteristics analysis［D］.Shandon：Shandong Normal University，2012：7－15 （in Chinese）. ［趙靜.基于內(nèi)容特征分析的垃圾郵件過濾關(guān)鍵技術(shù)研究 ［D］.山東：山東師范大學(xué)，2012：7－15.］

［8］ZHENG Wei，SHEN Wenzhang，YING Peng.Implementing spam filter by improving naive Bayesian algorithm ［J］.Journal of Northwestern Polytechnical University，2010，28 （4）：623－627 （in Chinese）.［鄭煒，沈文張，英鵬.基于改進(jìn)樸素貝葉斯算法的垃圾郵件過濾器的研究 ［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2010，28 （4）：623－627.］

［9］FU Huitao，Kamil Moydin.Study and design of an improved text feature selection method ［J］.Computer Applications and Software，2011，28 （4）：238－241 （in Chinese）. ［符會(huì)濤，木衣丁·卡米力.一種改進(jìn)的文本特征選擇方法的研究與設(shè)計(jì)［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28 （4）：238－241.］

［10］Blanzieri E，Bryl A.A survey of learning－based techniques of email spam filtering ［J］.Artif Intell Rev，2008，29：63－92.

［11］LUO Qin，LIU Bing，YAN Junhua，et al.Research of a spam filtering algorithm based on naive Bayes and AIS ［C］／／International Conference on Computational and Information－Sciences.Washington：IEEE，2010：152－155.

［12］Kosmopoulos A，Paliouras G，Androutsopoulos I.Adaptive spam filtering using only naive bayes text classifiers ［C］／／Fifth Conference on Email and Anti－Spam，2008.