基于改進貝葉斯決策的郵件過濾

薛正元

基于改進貝葉斯決策的郵件過濾

薛正元

探討了基于概率閾值的貝葉斯郵件過濾模型的局限性：由于很少考慮所設(shè)定閾值的適用性和實用性，損失了一定的召回率。改進貝葉斯決策，提出了基于隨機變量的較小錯誤分類決策方法；針對郵件處理的特殊性，進一步提出了基于隨機變量的較小風(fēng)險分類決策方法。實驗結(jié)果表明，處理普通文本分類問題時，前者的分類決策效果更好；而后者在處理郵件問題時性能更優(yōu)，能夠在保持較小誤判風(fēng)險的同時，提高貝葉斯郵件過濾器的召回率以及F值。

垃圾郵件；郵件過濾；概率；閾值；分類決策

垃圾郵件不僅困擾人們的日常生活，更威脅到網(wǎng)絡(luò)的效率和安全。據(jù)中國互聯(lián)網(wǎng)協(xié)會反垃圾郵件中心[1]公布的《2010年第四季度中國反垃圾郵件狀況調(diào)查報告》，中國網(wǎng)民平均每周收到13.5封垃圾郵件，處理垃圾郵件耗時9.4 min，并有進一步增長的趨勢。當(dāng)前有多種反垃圾郵件技術(shù)[2]，包括黑白名單技術(shù)、基于規(guī)則的過濾技術(shù)、行為識別技術(shù)、基于內(nèi)容的過濾技術(shù)等。然而，垃圾郵件的日新月異給當(dāng)前技術(shù)帶來了新的難題。單純利用這些過濾技術(shù)，都很難達到令人滿意的效果。表1總結(jié)了這些主流技術(shù)的優(yōu)缺點。

表1 傳統(tǒng)反垃圾郵件技術(shù)的優(yōu)缺點分析

本文重點關(guān)注基于內(nèi)容的過濾技術(shù)[3]：首先由用戶對現(xiàn)有的大量郵件進行分類——垃圾郵件或正常郵件，然后系統(tǒng)通過對郵件集進行不斷地總結(jié)與學(xué)習(xí)，進而根據(jù)新郵件內(nèi)容進行分析和判斷。著名的“貝葉斯過濾技術(shù)”[3-5]便是基于該思想的一種有效技術(shù)。貝葉斯郵件過濾器是一種基于概率的分類器，一般根據(jù)計算得到郵件后驗概率，采用人為設(shè)定閾值的方法進行分類決策。貝葉斯分類器具有優(yōu)秀的分類表現(xiàn)，但在郵件分類決策時采用概率閾值的方法具有較大主觀性，因此難以實現(xiàn)誤判風(fēng)險和垃圾郵件召回率之間的平衡。

1 相關(guān)研究

目前已有多位學(xué)者將貝葉斯方法應(yīng)用于文本分類，并取得了較好的效果[6]。但郵件過濾不同于一般的文本分類：通常認為，用戶寧愿接收更多的垃圾郵件，也不能接受將合法郵件錯判為垃圾郵件[3]。

為解決上述問題，文獻[7]提出垃圾郵件的代價因子指標(biāo)，指出如果簡單地追求高的郵件正確率則可能產(chǎn)生很大的代價。自從代價問題被研究人員普遍認識到之后，許多研究者不再盲目地追求所謂的正確率，而對誤判垃圾郵件所帶來的風(fēng)險越來越重視。文獻[8]提出一種最小風(fēng)險的貝葉斯決策，即根據(jù)誤判與漏判之間的代價比來設(shè)定閾值從而進行分類決策。這是目前研究人員普遍采用的一種方法，即根據(jù)計算得到郵件的后驗概率，采用人為設(shè)定概率閾值的方法進行分類決策。文獻[9]提出一種新的最小風(fēng)險的貝葉斯決策，從直線幾何分割的角度改進了貝葉斯郵件分類決策模型，并定義了新的風(fēng)險因子。但實質(zhì)上，該文提出的最小風(fēng)險的貝葉斯決策仍然是一種基于概率閾值的分類決策。

上述文獻[7-9]普遍存在以下問題：它們雖認識到?jīng)Q策風(fēng)險的存在，甚至采取了設(shè)定閾值等措施，卻未考慮所設(shè)定的閾值是否最優(yōu)、是否合適，甚至是否有必要設(shè)定閾值。對于該問題，文獻[10-11]通過貝葉斯過濾方法對垃圾郵件語料進行實驗測試，依據(jù)實驗結(jié)果進一步給出了閾值等參數(shù)和過濾效果間的關(guān)系，并得出了較優(yōu)的參數(shù)設(shè)定。但該文仍存在以下問題：盡管人們可能在一個或者若干個訓(xùn)練樣本集上進行反復(fù)測試和實驗驗證，得到一個所謂“最佳”閾值，但由于有限的訓(xùn)練樣本集不可能具有良好的“數(shù)據(jù)完備性”，因此對于現(xiàn)實中的郵件來說，這種閾值的適用性非常有限。而要找到一個具有普適性的“最佳”閾值，尚存在一定難度。

因此，本文從一般模型的探討著手，討論了基于概率閾值的貝葉斯分類模型存在的問題，進而提出了一種基于隨機變量的分類決策方法。通過理論分析和實驗驗證了本文方法的有效性。

2 理論模型

2.1 后驗概率的計算

設(shè)D1，D2，…，Dm為樣本空間S的一個劃分，P(Di)表示事件Di發(fā)生的概率，且 P(Di)＞0(i=1，2，…，m)。對于任一事件x，P(x)＞0，則有貝葉斯公式：

貝葉斯決策就是根據(jù)先驗概率，利用貝葉斯公式轉(zhuǎn)換成后驗概率，再根據(jù)后驗概率大小進行決策分類。對于垃圾郵件問題，運用貝葉斯公式對郵件內(nèi)容進行分析，過濾器根據(jù)概率進行郵件分類：垃圾郵件類Spam或正常郵件類Ham。首先在訓(xùn)練過程中收集大量郵件，建立Spam類和Ham類。然后對其中的每一封郵件，提取獨立字符串w1，w2，…，wn作為特征分詞，并統(tǒng)計相應(yīng)詞頻 f1，f2，…，fn。進一步假設(shè)文本郵件d中的各特征詞之間相互獨立，結(jié)合貝葉斯公式，求出待分類郵件d屬于Spam類的概率（后驗概率）如式（2）：

n表示待分類郵件d中所含不同特征詞總個數(shù)；P(d)表示任意情況下文本郵件d出現(xiàn)的概率；P(Spam)表示垃圾郵件類先驗概率，等于訓(xùn)練樣本集中垃圾郵件比例；P(wi|Spam)表示在垃圾郵件類條件下特征詞wi出現(xiàn)的條件概率，等于垃圾郵件類中特征詞wi的詞頻 fi與垃圾郵件類中特征詞總數(shù)之比；式中與Ham相關(guān)的變量含義與上述變量類似。

2.2 基于隨機變量的分類決策

對一封待分類郵件di，由2.1節(jié)計算得到郵件的后驗概率（記該值為Pi）之后，基于概率閾值的貝葉斯過濾器根據(jù)Pi值是否達到事先設(shè)定的閾值P0進行分類決策。達到P0的就必須歸為垃圾郵件，否則必須歸為正常郵件，十分不靈活；進一步講，由于概率問題從根本上來說就是不確定性問題，因此，僅根據(jù)不確定的、概率意義上的數(shù)值大小就給出問題的確定結(jié)果，這種做法顯然不太合適。

為此，本文提出一種基于隨機變量的分類決策方法。該方法首先利用貝葉斯分類法求出各待分類郵件的后驗概率，然后在此基礎(chǔ)上進行改進。

2.2.1 基于隨機變量的較小錯誤分類決策

與基于概率閾值的貝葉斯過濾不同的是，本文提出的基于隨機變量的分類決策未設(shè)定閾值，而使用隨機變量的思想：對一封待分類郵件di，后驗概率Pi表示的是該郵件屬于垃圾郵件的概率，因此，對于后驗概率超過1/2的郵件di，可以依概率Pi將其歸為垃圾郵件類；未歸為垃圾郵件類的，以及后驗概率小于1/2的郵件，歸為正常郵件類。

采用基于隨機變量的分類決策后，貝葉斯過濾垃圾郵件分類決策部分的流程如圖1所示。

圖1 基于隨機變量的分類決策流程圖

這種基于隨機變量的分類決策方法具有的優(yōu)點：不會由于人為設(shè)定閾值的不當(dāng)（過大或過?。┒鴮?dǎo)致決策失誤帶來較大分類損失；同時，引進該方法后，考慮后驗概率超過1/2的那部分郵件，其分類決策的整體結(jié)果與其數(shù)學(xué)期望相符；另外，不難發(fā)現(xiàn)該決策方法可使郵件分類結(jié)果具有較大的郵件判對率T。

（1）采用基于概率閾值的貝葉斯分類算法，設(shè)定閾值P0，則判定結(jié)果正確的概率為：

（2）采用基于隨機變量的較小錯誤分類決策方法，則判定結(jié)果正確的概率為：

將兩種方法作比較，式（1）中取閾值P0為0.9，則兩方法的決策性能（郵件判對率理論值）對比如圖2（a）所示。由圖可以看出，與傳統(tǒng)基于概率閾值的貝葉斯決策相比，通常情況下后者在全部郵件判對率方面具有較為明顯的優(yōu)勢。

進一步分析，不難發(fā)現(xiàn)本節(jié)提出的決策方法的性能非常接近于基于最小錯誤的貝葉斯決策（見圖2（b））。稱這種決策方法為基于隨機變量的較小錯誤分類決策。

圖2 與貝葉斯決策法性能對比圖

由圖2可知，從理論上講，較之傳統(tǒng)基于概率閾值的貝葉斯分類決策，本節(jié)基于隨機變量的較小錯誤分類決策除了可使郵件分類的整體結(jié)果與數(shù)學(xué)期望相符，在決策分類正確率方面同樣具有優(yōu)勢。

2.2.2 基于隨機變量的較小風(fēng)險分類決策

考慮到郵件分類決策的特殊性：如將一封正常郵件誤判為垃圾郵件比漏判一封垃圾郵件代價更高。為降低分類決策風(fēng)險，進一步改進2.2.1小節(jié)提出的基于隨機變量的分類決策。

假設(shè)誤判1封垃圾郵件的代價等同于漏判9封垃圾郵件的代價，則傳統(tǒng)貝葉斯決策中設(shè)定閾值P0=0.9[8]。而在基于隨機變量的分類決策中，將該閾值對應(yīng)到值1/2，其目的是：如果郵件后驗概率達到P0，則歸為垃圾郵件的可能性大；否則歸為正常郵件的可能性大。通過對郵件分類特性的思考，當(dāng)后驗概率小于等于1/2時，可直接將其歸為正常郵件（即 f(Pi)=0，其中Pi≤1/2）。針對后驗概率大于1/2時的情況，提出一種采用冪函數(shù)形式的決策函數(shù) f(Pi)=Pri。其中Pi＞1/2為郵件di對應(yīng)的后驗概率，r為待定常數(shù)。設(shè)

將P0=0.9代入式（5），得r=log0.90.5≈6.58，故

顯然式（6）滿足 f(0)=0及 f(1)=1。同時對于后驗概率為1/2的較特殊郵件，有 f(1/2)=0.56.58≈0.01，即只有約1%的可能被判為垃圾郵件，這也符合對于后驗概率小于1/2的郵件的處理情況。

由上，得到基于隨機變量的分類決策函數(shù) f(Pi)圖像，如圖3所示。

圖3 基于隨機變量的分類決策函數(shù)f（Pi）圖像

得到?jīng)Q策函數(shù) f(Pi)后，就可以在進行分類決策時將郵件依概率 f(Pi)歸為Spam類，這與依概率Pi歸為Spam類，以及依Pi是否達到閾值歸為Spam類相比，具有更低的決策風(fēng)險。稱這種決策方法為基于隨機變量的較小風(fēng)險分類決策。

3 實驗驗證

3.1 實驗安排

實驗采取兩組對比：實驗A采用當(dāng)今主流的貝葉斯郵件訓(xùn)練方法對郵件集進行訓(xùn)練，然后采用基于概率閾值的分類法進行分類決策。假設(shè)誤判1封垃圾郵件相當(dāng)于漏判9封正常郵件，選取0.9作為閾值使錯誤風(fēng)險最小[8]。實驗B采用同樣的貝葉斯郵件訓(xùn)練方法對郵件集進行訓(xùn)練，然后分別采用本文提出的基于隨機變量的較小錯誤決策方法和基于隨機變量的較小風(fēng)險決策方法進行分類（分別記為實驗B-1和B-2）。

實驗數(shù)據(jù)源有兩個：（1）CCERT[12]，包含9 272封正常郵件和25 088封垃圾郵件，從中隨機抽取正常郵件和垃圾郵件各4 500封作為實驗數(shù)據(jù)源；（2）CNLP-Platform[13]，包含正常郵件和垃圾郵件各1 500封，從中隨機抽取正常郵件和垃圾郵件各1 200封作為實驗數(shù)據(jù)源。兩個數(shù)據(jù)源獨立進行實驗：將兩個數(shù)據(jù)源分別平均分成5份，4份用于訓(xùn)練，1份用于測試，進行5重交叉實驗，最后取5次實驗平均值作為實驗結(jié)果。

表2 實驗A與實驗B性能指標(biāo)比較

3.2 實驗結(jié)果與評價

采用4個評價指標(biāo)：垃圾郵件查準(zhǔn)率P、垃圾郵件召回率R和F值、全部郵件判對率T。其中，查準(zhǔn)率P等于判為垃圾郵件的郵件中實為垃圾郵件的比例，反映識別垃圾郵件的準(zhǔn)確性；召回率R等于實為垃圾郵件的郵件中判為垃圾郵件的比例，反映識別垃圾郵件的完整性；F值=2PR/（P+R）兼顧了查準(zhǔn)率和召回率問題，是以上兩個指標(biāo)的綜合；判對率T等于所有待分類郵件被正確歸類的郵件的比例，反映正確歸類郵件的能力。

實驗得出采用基于隨機變量的分類決策方法（實驗A）與采用基于隨機變量的分類決策方法（實驗B）性能指標(biāo)，如表2所示；圖表形式如圖4所示。

圖4 實驗A與實驗B性能指標(biāo)比較圖

由圖4可知，本文提出的基于隨機變量的分類決策方法相對于當(dāng)今主流的貝葉斯決策有了一定程度的性能提升：實驗A中雖具有稍高的查準(zhǔn)率P，但召回率指標(biāo)R不佳；實驗B-1具有較高的判對率T，因此對于普通的文本分類問題，利用這種基于隨機變量的較小錯誤分類決策方法將可能是個更好的選擇；實驗B-2中查準(zhǔn)率P稍低，但其召回率R、判對率T和綜合指標(biāo)F值均較好，同時不難驗證其在誤判風(fēng)險方面顯著優(yōu)于實驗B-1，而與設(shè)定閾值P0=0.9的當(dāng)今主流的貝葉斯決策風(fēng)險相差無幾。

將本文基于隨機變量的較小風(fēng)險分類決策結(jié)果與文獻[11]提出的最小風(fēng)險貝葉斯算法結(jié)果作比較，可見本文各指標(biāo)均略高于文獻[11]中各指標(biāo)約2至3個百分點，如表3。因此，本文方法優(yōu)于文獻[11]中的方法。從郵件分類的特殊性考慮，本文基于隨機變量的較小風(fēng)險分類決策方法更適合于進行郵件分類決策。

表3 本文實驗結(jié)果與文獻[11]結(jié)果對比

4 結(jié)束語

隨機變量的思想已經(jīng)日趨成熟，但將隨機變量應(yīng)用于分類決策的相關(guān)研究還比較罕見。本文通過對基于概率閾值的貝葉斯垃圾郵件過濾模型進行理論探討，提出用隨機變量的思想代替概率閾值的思想，并通過一定的性能指標(biāo)進行實驗驗證。實驗結(jié)果表明，較之當(dāng)今基于概率閾值的貝葉斯郵件過濾技術(shù)，在分類決策時引入“隨機變量”的思想將會在一定程度上提高貝葉斯過濾器的分類性能。

考慮到郵件分類的特殊性，本文提出的基于隨機變量的較小風(fēng)險分類決策方法更適合于進行郵件分類決策；而對于普通的文本二分類問題，利用本文提出的基于隨機變量的較小錯誤分類決策方法將可能是個更好的選擇。同時，考慮到有限的實驗郵件集難以具有良好的數(shù)據(jù)完備性，本文基于隨機變量的分類決策思想在“普適性”方面還有待進行更深入的研究。相信隨著研究的深入，基于隨機變量的分類決策思想將有更廣闊的應(yīng)用前景。

[1]中國互聯(lián)網(wǎng)協(xié)會反垃圾郵件中心[EB/OL].[2011-05-18].http：//www.anti-spam.cn/.

[2]Cormack G.Email spam filtering：a systematic review[M]// Foundations and Trends in Information Retrieval.[S.l.]：Now Publishers Inc，2008.

[3]王斌，潘文鋒.基于內(nèi)容的垃圾郵件過濾技術(shù)綜述[J].中文信息學(xué)報，2005，19（5）：1-10.

[4]陳志賢.垃圾郵件過濾技術(shù)研究綜述[J].計算機應(yīng)用研究，2009，26（5）：1612-1615.

[5]Metsis V，Androutsopoulos I，Paliouras G.Spam filtering with naive Bayes-which naive Bayes?[C]//Proc of the 3rd CEAS，Mountain View，CA，USA，2006.

[6]樊興華，孫茂松.一種高性能的兩類中文文本分類方法[J].計算機學(xué)報，2006，29（1）：124-131.

[7]Androuts Opoulos I，Koutsias J，Chandrinos K V，et al.An evaluation of naive Bayesian anti-spam filtering[C]//Proc of the Workshop on Machine Learning in the New Information Age，the 11th European Conference on Machine Learning （ECML 2000），May 2000：9-17.

[8]李維杰，徐勇.簡體中文垃圾郵件分類的實驗設(shè)計及對比研究[J].計算機工程與應(yīng)用，2007，43（25）：128-132.

[9]王濤，裘國永，何聚厚.新的基于最小風(fēng)險的貝葉斯郵件過濾模型[J].計算機應(yīng)用研究，2008，25（4）：1147-1148.

[10]張學(xué)農(nóng)，張立成.基于簡單貝葉斯的中英文垃圾郵件過濾的比較分析[J].計算機應(yīng)用與軟件，2008，25（8）：178-180.

[11]王美珍，李芝棠，吳漢濤.改進的貝葉斯垃圾郵件過濾算法[J].華中科技大學(xué)學(xué)報，2009，37（8）：27-30.

[12]中國教育和科研計算機網(wǎng)緊急響應(yīng)組（CCERT）[EB/OL]. [2011-06-27].http：//www.ccert.edu.cn/spam/sa/datasets.htm.

[13]中文自然語言處理開放平臺（CNLP-Platform）[EB/OL]. [2011-06-27].http：//www.nlp.org.cn/docs/download.php?doc_id= 1207.

XUE Zhengyuan

鄭州大學(xué) 信息工程學(xué)院，鄭州 450001

School of Information Engineering,Zhengzhou University,Zhengzhou 450001,China

This paper confers in depth to the limitations of the traditional Bayesian anti-spam mechanism.It seldom thinks about whether the threshold is suitable or not,so the recalling is reduced.Aiming at this question,the paper proposes a lower-error policy decision based on chance variable;and considering the particularity of email classification,a lower-risk policy decision based on chance variable is proposed.The experimental results show that the former one maybe a better way to classify the common text; and the latter one makes better performance on recalling and F value when dealing with emails,at the same time it keeps a lower risk of error judging.

spam email;email filter;probability;threshold;classify decision

A

TP302.1

10.3778/j.issn.1002-8331.1109-0044

XUE Zhengyuan.Improved probability-based Bayesian anti-spam mechanism.Computer Engineering and Applications, 2013,49（7）：98-101.

薛正元（1989—），男，碩士研究生，主要研究領(lǐng)域為Web數(shù)據(jù)挖掘，網(wǎng)絡(luò)信息技術(shù)。E-mail：xuezhengyuan@163.com

2011-09-05修回日期：2011-11-21

1002-8331（2013）07-0098-04

CNKI出版日期：2012-01-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120116.0928.067.html