董 萍

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

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

1 N平均 1-依賴(lài)郵件過(guò)濾模型

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

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

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

N平均 1-依賴(lài)郵件過(guò)濾模型如式 (1)。

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

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

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

2 算法描述

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

Step 1：確定 N值;

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

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

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

Step 5：計(jì)算 N個(gè) ODE概率的平均值作為最終的分類(lèi)概率;

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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