薛正元

基于改進(jìn)貝葉斯決策的郵件過濾

薛正元

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

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

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

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

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

1 相關(guān)研究

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

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

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

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

2 理論模型

2.1 后驗(yàn)概率的計(jì)算

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

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

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

2.2 基于隨機(jī)變量的分類決策

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

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

2.2.1 基于隨機(jī)變量的較小錯(cuò)誤分類決策

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

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

圖1 基于隨機(jī)變量的分類決策流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)安排

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

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

表2 實(shí)驗(yàn)A與實(shí)驗(yàn)B性能指標(biāo)比較

3.2 實(shí)驗(yàn)結(jié)果與評價(jià)

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

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

圖4 實(shí)驗(yàn)A與實(shí)驗(yàn)B性能指標(biāo)比較圖

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

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

表3 本文實(shí)驗(yàn)結(jié)果與文獻(xiàn)[11]結(jié)果對比

4 結(jié)束語

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

考慮到郵件分類的特殊性，本文提出的基于隨機(jī)變量的較小風(fēng)險(xiǎn)分類決策方法更適合于進(jìn)行郵件分類決策；而對于普通的文本二分類問題，利用本文提出的基于隨機(jī)變量的較小錯(cuò)誤分類決策方法將可能是個(gè)更好的選擇。同時(shí)，考慮到有限的實(shí)驗(yàn)郵件集難以具有良好的數(shù)據(jù)完備性，本文基于隨機(jī)變量的分類決策思想在“普適性”方面還有待進(jìn)行更深入的研究。相信隨著研究的深入，基于隨機(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é)報(bào)，2005，19（5）：1-10.

[4]陳志賢.垃圾郵件過濾技術(shù)研究綜述[J].計(jì)算機(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].計(jì)算機(jī)學(xué)報(bào)，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í)驗(yàn)設(shè)計(jì)及對比研究[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（25）：128-132.

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

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

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

[12]中國教育和科研計(jì)算機(jī)網(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)域?yàn)閃eb數(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