不完全樸素貝葉斯分類模型在垃圾郵件過濾中的研究

董 萍

(三門峽職業(yè)技術(shù)學(xué)院信息工程系,河南三門峽 472000)

伴隨著網(wǎng)絡(luò)的發(fā)展和電子郵件的廣泛應(yīng)用,令用戶煩惱的垃圾郵件大量產(chǎn)生,它嚴(yán)重占用網(wǎng)絡(luò)帶寬,影響網(wǎng)絡(luò)服務(wù)的正常進(jìn)行;侵犯收件人的隱私權(quán),耗費網(wǎng)絡(luò)存儲空間;附件中帶有的病毒或木馬,給個人計算機(jī)安全帶來極大危害[1]。鑒于這些危害,過濾垃圾郵件也就隨之成為人們的重要工作之一。垃圾郵件分類是對在網(wǎng)絡(luò)上傳遞的郵件進(jìn)行判別分類,阻塞非法郵件的傳遞。本文引入 N平均 1-依賴郵件過濾模型的新的郵件過濾分類模型,在一定程度上考慮了屬性之間的語義關(guān)聯(lián),對垃圾郵件的過濾更有效。

1 N平均 1-依賴郵件過濾模型

樸素貝葉斯分類模型[2]是對貝葉斯分類模型的簡化,它因簡單、高效在郵件過濾應(yīng)用的研究中扮演著重要的角色。x-依賴的貝葉斯分類模型既有NB分類模型的高效性,又能保留部分的屬性之間的關(guān)聯(lián)以便能獲得更好的分類效果。

該分類的條件獨立假設(shè)割裂了屬性之間的關(guān)系,影響了分類的準(zhǔn)確性,放松樸素貝葉斯分類模型關(guān)于屬性之間條件獨立假設(shè)。該分類模型放松了NB分類模型對屬性之間條件獨立假設(shè)的約束,允許每一個屬性和最多 x個屬性條件依賴,即該屬性有x個父屬性。

基于上述思想,本文提出了一種新的郵件分類模型,N平均 1-依賴郵件過濾模型[3]。該模型依據(jù)屬性之間的互信息大小挑選出 N個屬性作為父屬性,依次按照 1-依賴分類模型計算各個類別標(biāo)簽的后驗概率,最后取 N個 1-依賴后驗概率的平均值作為分類概率。

N平均 1-依賴郵件過濾模型如式 (1)。

式 (1)給出了樸素貝葉斯分類模型,其中的 Pr(cy)為各個類標(biāo)簽的先驗概率該模型的關(guān)鍵就是選取哪些屬性來作為父屬性,模型使用平均互信息來選取 N個屬性。

x-依賴的貝葉斯分類模型放松了 NB分類模型對屬性之間條件獨立的假設(shè),允許屬性和最多 x個屬性條件依賴。NB分類模型就是一個 0-依賴的貝葉斯分類模型?？紤]到計算的復(fù)雜性問題,構(gòu)建一個 1-依賴貝葉斯分類模型是一個較好的選擇。由于這種分類模型放松了 NB的條件獨立假設(shè),所以稱做不完全樸素貝葉斯分類模型。

基于不完全的樸素貝葉斯分類模型,提出一種新的郵件分類模型,N平均 1-依賴郵件過濾模型[4]。該模型使用屬性所攜帶的平均互信息的大小衡量屬性的權(quán)值的高低,并對其進(jìn)行排序。具有較高權(quán)值的屬性對分類效果的影響較大,所以權(quán)值高的屬性應(yīng)該優(yōu)先被選擇為父屬性。最后,模型選取排在最前面的N個屬性作為候選的父屬性。

2 算法描述

對于每一封測試郵件,具有 m個屬性和 2個類別標(biāo)簽 (垃圾郵件類別標(biāo)簽 Cspam與合法郵件類別標(biāo)簽Clegit)。

Step 1：確定 N值;

Step 2：計算屬性 attri與其他屬性 ＜attrl,attr2,…,attri-1,attri+1,…,attrm＞之間的互信息量;

Step 3：挑選出互信息量最高的 N個屬性構(gòu)成super-parent集合;

Step 4：依次從候選的父屬性集合中取出屬性按照 One-Dependance-Estimate進(jìn)行類別概率計算;

Step 5：計算 N個 ODE概率的平均值作為最終的分類概率;

Step 6：輸出郵件的類別估計,結(jié)束算法。

3 實驗與分析

3.1 實驗設(shè)計

實驗環(huán)境：實驗的硬件平臺為一臺 IBM Pc計算機(jī),配置為雙核 3.0GHz Pentium CPU、2G內(nèi)存,操作系統(tǒng)為 Windows XP sp2。實驗環(huán)境依然是在 eclipse3.2上運行Weka機(jī)器學(xué)習(xí)實驗環(huán)境。

實驗數(shù)據(jù)：垃圾郵件數(shù)據(jù)集 Spambase有 57個屬性,1個類別標(biāo)簽屬性含有兩個類別標(biāo)簽 (合法郵件和垃圾郵件)。Spambase數(shù)據(jù)集總共包含有 4601封郵件,其中有 2788封郵件為合法郵件 (Legit),有1813封郵件為垃圾郵件 (Spam)。垃圾郵件的數(shù)量占郵件數(shù)目總體的 39.4%。

在實驗的過程中,數(shù)據(jù)集被近似平均地劃分為10個子集進(jìn)行 10次交叉驗證,取其平均值為最終的測試結(jié)果。每一次交叉驗證,都使用一個不同的子集來作為測試數(shù)據(jù)集,其他的子集作為訓(xùn)練數(shù)據(jù)集。這樣,每一個子集都會被作為測試數(shù)據(jù)進(jìn)行分類計算。

3.2 實驗結(jié)果與分析

圖1顯示了基于 N平均 1-依賴郵件過濾模型的 0-1損失分類錯誤率曲線。圖中的 X軸表示測試郵件的數(shù)量,實驗測試了從 2000封郵件到 4500封郵件的分類準(zhǔn)確率,其中的間隔為 500。Y軸表示不完全樸素貝葉斯分類模型對郵件分類的 0-1損失錯誤率。不同的曲線表示了分類模型在取不同的 N值的分類結(jié)果。錯誤率越小,模型的分類準(zhǔn)確率越高,分類性能越好。

圖1 spambase數(shù)據(jù)集在 N平均 1-依賴郵件過濾模型中的結(jié)果

從圖1中可以看到,NB分類模型 (即當(dāng) N=0的時候)達(dá)到較高的郵件分類準(zhǔn)確率 (89%—91.5%),但是 N平均 l-依賴分類模型達(dá)到了更佳的分類結(jié)果。圖1顯示了 N=10,20,30,40,50和 60的時候的分類錯誤率曲線,除了 N=10的曲線在郵件數(shù)目為 2500封郵件時的分類錯誤率略高于 NB分類模型外,其他的曲線都顯示了 N平均 1-依賴郵件過濾模型的分類錯誤率低于 NB分類模型。同時,雖然添加依賴屬性能降低分類的錯誤率,但是添加更多的父屬性數(shù)目需要有更多的計算時間,另一方面從實驗結(jié)果中可以看到并不是 N值越高越好。N=20的曲線,雖然在 2000到 3500的實驗結(jié)果不如N=30,40,50和 60的實驗結(jié)果,但是在郵件數(shù)量增多后,在 4000封及以上的時候,N=20達(dá)到了最好的分類效果 (最低的錯誤率)。當(dāng)郵件數(shù)目很多的時候,實驗顯示N值取 20是一個較好的選擇。

當(dāng)郵件總數(shù)從 4000增加到 4500的時候,分類錯誤率有一個較大幅度的上升。出現(xiàn)這個現(xiàn)象的原因可能是因為新增加的 500封郵件中有部分郵件特征向量導(dǎo)致了分類錯誤率的突變。雖然如此該實驗的目的是比較不同的 N值條件下分類模型在不同郵件數(shù)目下的分類效果,該突變對實驗的最終結(jié)果沒有太多的影響。該實驗的結(jié)果顯示了實驗達(dá)到了預(yù)先的目的。

4 結(jié)束語

在不完全樸素貝葉斯分類模型的基礎(chǔ)上提出了一種基于不完全樸素貝葉斯的垃圾郵件分類模型：N-平均 1-依賴郵件過濾模型。該模型放松樸素分類模型條件獨立假設(shè),利用 N個 1-依賴貝葉斯分類的平均概率估計值來對郵件的類別進(jìn)行判別。經(jīng)過實驗證明,該模型到達(dá)了更好的分類效果,得到了更低的分類錯誤率。同時,實驗驗證了 N的取值并不是越大越好,當(dāng)郵件數(shù)在 4000封以上的時候,N取20是不錯的選擇。

[1] 劉震.垃圾郵件過濾理論和關(guān)鍵技術(shù)研究[D].成都：電子科技大學(xué),2007.

[2] 衣治安,毛巖.垃圾郵件過濾技術(shù)概述[J].長江大學(xué)學(xué)報 (自然科學(xué)版),2010,3(7)：256-258.

[3] 謝建偉,魏曉寧.基于內(nèi)容的垃圾郵件過濾技術(shù)綜述[J].黑龍江科技信息,2008,36(94)：95-96.

[4] 時紅梅,高茂庭.垃圾郵件過濾技術(shù)及發(fā)展[J].計算機(jī)與數(shù)字工程 [J],2008,36(6)：128-132.