貝葉斯網(wǎng)絡(luò)在過濾垃圾郵件算法中的應(yīng)用研究

崔 超，楊 威，張憲忠，張志軍

(1.齊齊哈爾大學(xué)應(yīng)用技術(shù)學(xué)院，161006 黑龍江齊齊哈爾，cv63@163.com;2.齊齊哈爾市信息中心，161006 黑龍江齊齊哈爾;3.齊齊哈爾市信息技術(shù)研究所 161006 黑龍江齊齊哈爾)

貝葉斯網(wǎng)絡(luò)在過濾垃圾郵件算法中的應(yīng)用研究

崔 超1，楊 威2，張憲忠1，張志軍3

(1.齊齊哈爾大學(xué)應(yīng)用技術(shù)學(xué)院，161006 黑龍江齊齊哈爾，cv63@163.com;2.齊齊哈爾市信息中心，161006 黑龍江齊齊哈爾;3.齊齊哈爾市信息技術(shù)研究所 161006 黑龍江齊齊哈爾)

為在用戶數(shù)據(jù)流中刪除垃圾郵件，研究了具有自我學(xué)習(xí)能力的自適應(yīng)郵件過濾系統(tǒng).在對(duì)正常和垃圾2類郵件誤分類成本分析的基礎(chǔ)上，利用概率性的學(xué)習(xí)方法創(chuàng)建滿足過濾任務(wù)需要的過濾器，且討論使用郵件域名特征變量進(jìn)行特定郵件過濾并設(shè)計(jì)了過濾器，最后對(duì)實(shí)際郵件組進(jìn)行操作，驗(yàn)證了算法的可靠性.

貝葉斯理論方法;概率;特征變量;郵件過濾

早期對(duì)郵件的過濾只是對(duì)郵件正文進(jìn)行過濾，邏輯過濾規(guī)則只是機(jī)械地使用二進(jìn)制決策來(lái)決定取舍，而這種規(guī)則是有局限性的.研究能根據(jù)過濾環(huán)境特征變量［1］變化進(jìn)行自我調(diào)整，并能進(jìn)行自我學(xué)習(xí)的郵件過濾系統(tǒng)是一種解決辦法.由于垃圾郵件特征變化的多樣性和實(shí)時(shí)性，邏輯過濾規(guī)則的優(yōu)化對(duì)系統(tǒng)提出了更高的要求.理想的過濾系統(tǒng)應(yīng)具備隨過濾目標(biāo)對(duì)象的特征變化而自動(dòng)調(diào)整過濾規(guī)則的能力，對(duì)郵件進(jìn)行分析，能直接從系統(tǒng)郵件緩沖區(qū)讀取數(shù)據(jù)并進(jìn)行學(xué)習(xí)，個(gè)性化地為每個(gè)用戶架構(gòu)有自身特征的過濾系統(tǒng)，過濾系統(tǒng)完成對(duì)目標(biāo)的操作.依據(jù)貝葉斯定理設(shè)計(jì)的分類器，本文設(shè)計(jì)一個(gè)功能模塊，并制訂了一個(gè)可行的過濾方案，并對(duì)郵件錯(cuò)誤成本進(jìn)行定量分析，完成垃圾郵件過濾［2］.

1 貝葉斯模型

采用貝葉斯定理的分類器，在自動(dòng)生成概率性的文本分類模型的過程中，將貝葉斯定理應(yīng)用到分類技術(shù)的算法中，利用貝葉斯定理建模，既能解決傳統(tǒng)文本過濾問題，又可以在貝葉斯過濾器中引入具體的特征變量，將郵件域名信息同要完成的指定任務(wù)結(jié)合起來(lái)，聯(lián)合使用研究模型和系統(tǒng)損失模型，對(duì)目標(biāo)文件作出是否為垃圾郵件的判定.

1.1 貝葉斯網(wǎng)絡(luò)

為完成垃圾郵件的檢測(cè)需要建立一個(gè)概率性的分類器，利用貝葉斯定理的網(wǎng)絡(luò)形式和其直接的、非循環(huán)形式的對(duì)應(yīng)圖表達(dá)一個(gè)緊密的幾率分布，圖1中任一個(gè)隨機(jī)變量xi都用一個(gè)節(jié)點(diǎn)來(lái)表示，兩節(jié)點(diǎn)間的線段表示由父、子節(jié)點(diǎn)分別確定的兩變量間概率相關(guān)性.網(wǎng)絡(luò)結(jié)構(gòu)表明網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)xi都有條件地獨(dú)立于由其父節(jié)點(diǎn)給出的其他節(jié)點(diǎn).為描述幾率分布，將網(wǎng)絡(luò)中的節(jié)點(diǎn)xi組成一個(gè)條件幾率圖，圖1用來(lái)說明對(duì)應(yīng)的概率分布.

對(duì)每個(gè)過濾任務(wù)，一個(gè)貝葉斯過濾器就是一個(gè)貝葉斯網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)C表示級(jí)別，每個(gè)節(jié)點(diǎn)xi用于表示一個(gè)特征變量［3］，將一個(gè)指定的范例X(將xi(i=1，2，3，…))的值分配給對(duì)應(yīng)的特征變量，網(wǎng)絡(luò)允許為每一個(gè)級(jí)別CK計(jì)算幾率P(C=cK|X=x)為

式中:變量P(C=ck|X=x)在未加上域名變量前無(wú)實(shí)際意義，式(1)中的每一個(gè)特征變量xi都有條件地獨(dú)立于其他任一特征變量，在給定級(jí)別變量C后，計(jì)算為

為降低貝葉斯過濾器對(duì)特征變量xi的限制，過濾方法允許特征變量xi間有限形式的相關(guān).圖1(a)展示了貝葉斯過濾器在具有同其他過濾器相同的上述特征變量xi間有限形式時(shí)的系統(tǒng)結(jié)構(gòu);圖1(b)則表現(xiàn)了特征變量間具備有限相關(guān)性的復(fù)雜貝葉斯分類器的系統(tǒng)結(jié)構(gòu).

圖1 同貝葉斯過濾器相對(duì)應(yīng)的貝葉斯網(wǎng)絡(luò)

1.2 變量空間模型

采用貝葉斯定理的垃圾郵件過濾系統(tǒng)在對(duì)郵件文本進(jìn)行分類時(shí)，要依據(jù)相應(yīng)的郵件信息形成特征變量.用一個(gè)變量空間模型將變量空間維數(shù)的定義同整個(gè)郵件庫(kù)中給定的詞對(duì)應(yīng)起來(lái)，每個(gè)具體的單詞用一個(gè)二進(jìn)制變量表示，表明單詞出現(xiàn)與否.

2 郵件域名的作用

具體郵件過濾時(shí)，首先要考慮郵件正文內(nèi)容在判定本文是否為垃圾時(shí)所起的作用，同時(shí)還要考慮郵件的其他特征變量，例如一些有誘惑性的短語(yǔ)或特殊符號(hào)的非常規(guī)使用，如“快速致富絕招”、“!!!!”等，此外，郵件中還經(jīng)常包含許多非正文屬性的特征，如郵件域名信息等，對(duì)垃圾郵件判定也非常有用.

2.1 使用特征變量的貝葉斯過濾器

將有具體郵件特點(diǎn)的特征變量引入到貝葉斯過濾器中是很簡(jiǎn)單的，把郵件提供的各種原始信息一律無(wú)變化地引入到分類模型中，不需要對(duì)算式做任何修改，但需要對(duì)在分類模型中使用的具體變量的表達(dá)形式進(jìn)行分析.

首先完成對(duì)郵件外部表述文字有無(wú)特定短語(yǔ)匹配的檢測(cè)，如“免費(fèi)”、“只是為了money”等，在實(shí)驗(yàn)中引入了一個(gè)有40個(gè)特征短語(yǔ)變量的集合，使用概率性的過濾方案，在當(dāng)前規(guī)則限定下，利用用戶手動(dòng)建立起來(lái)的，由短語(yǔ)組成的特征變量，快速完成對(duì)當(dāng)前郵件的過濾.

其次再考慮郵件域名類型等有關(guān)域的特征變量，常見的垃圾郵件經(jīng)常隱藏本身域名，如郵件是一個(gè)具體用戶發(fā)出的，對(duì)一封垃圾郵件非文本特征標(biāo)識(shí)的判定是很容易實(shí)現(xiàn)的.一般垃圾郵件是不帶附件的，接收的時(shí)間也常在夜間，標(biāo)題中出現(xiàn)非字母和數(shù)字的字符所占的百分比也是判定垃圾郵件的重要標(biāo)識(shí)之一，如“￥￥￥人民幣￥￥￥”等，類似上述判定依據(jù)在概率性的分類器中效果良好，而在基于規(guī)則的系統(tǒng)中誤差率則較高，如圖2所示，在垃圾郵件和正常郵件的標(biāo)題中所含的非字母和數(shù)字的分布有明顯的差異［4］.

圖2 垃圾郵件和正常郵件標(biāo)題中包含非字母和數(shù)字的百分率變化曲線

利用標(biāo)題中包含的字母和數(shù)字占標(biāo)題的百分率和域名方面其他一些特征變量對(duì)郵件的判定經(jīng)常是有效的，在對(duì)郵件信息進(jìn)行垃圾判定時(shí)，概率性的分類器可以使用上述特征變量作為依據(jù)對(duì)目標(biāo)郵件作出判定，在實(shí)驗(yàn)中引入了40個(gè)特征變量，包括域和編輯的非短語(yǔ)等.

3 垃圾郵件總體劃分和實(shí)驗(yàn)室測(cè)試

為確認(rèn)研究結(jié)果，對(duì)垃圾郵件進(jìn)行過濾實(shí)驗(yàn)，以信件正文和特征變量為對(duì)象進(jìn)行基本分類操作，對(duì)性能進(jìn)行了測(cè)定，同時(shí)對(duì)過濾器在操作環(huán)境設(shè)定領(lǐng)域的學(xué)習(xí)效率進(jìn)行了評(píng)估.

3.1 建立實(shí)驗(yàn)用樣本分類器

由于特征變量空間廣闊，要進(jìn)行變量的選擇，減少維數(shù)可以實(shí)現(xiàn)對(duì)評(píng)估系統(tǒng)參數(shù)模型變化結(jié)果進(jìn)行精確的控制，降低過濾器對(duì)獨(dú)立變量的干擾.實(shí)驗(yàn)首先選擇50個(gè)特征變量組成一個(gè)特征變量組來(lái)建立分類器，它包括了以單詞、編輯組成的短語(yǔ)和具體域變量，排除文中出現(xiàn)次數(shù) ＜4次的單詞，再計(jì)算每個(gè)特征變量xi和級(jí)別變量C間的信息影響因子MI為

盡管實(shí)驗(yàn)中50個(gè)變量不是最佳值，開始階段的多個(gè)實(shí)驗(yàn)還是表明了由50個(gè)特征變量提供的實(shí)驗(yàn)結(jié)果是可靠的.

3.2 添加域名特征變量

為判定使用特征變量的效率，利用為郵件過濾而編輯建立的特征變量，以一個(gè)有1 578封垃圾郵件，211封合法郵件的郵件庫(kù)為樣本，將郵件庫(kù)分成包括1 538封郵件組成的訓(xùn)練組和由251封郵件組成的測(cè)試組，以郵件標(biāo)題、郵件體為實(shí)驗(yàn)對(duì)象，采用基于單詞的標(biāo)記作為特征變量，然后用35個(gè)特征變量(為完成這項(xiàng)任務(wù)而專門收集的)去增加特征變量的數(shù)量，再用20個(gè)非文本、有具體域特點(diǎn)的變量來(lái)擴(kuò)大變量組，將測(cè)試組同變量組相聯(lián)，完成變量選擇和貝葉斯分類器的建立，最后實(shí)現(xiàn)對(duì)測(cè)試組垃圾的分類.

3.3 郵件分類敏感成本理論和實(shí)際測(cè)試結(jié)果

設(shè)郵件為垃圾郵件可能性＞98%時(shí)，只能被劃分為垃圾郵件.實(shí)驗(yàn)中得到的一組數(shù)值顯示了98%的基本值是滿足實(shí)驗(yàn)任務(wù)要求的，根據(jù)變量結(jié)構(gòu)的變化對(duì)垃圾和正常郵件進(jìn)行再調(diào)用和分類的有關(guān)數(shù)據(jù)統(tǒng)計(jì)如表1所示.

表1 采用不同變量組的分類結(jié)果 %

垃圾郵件準(zhǔn)確度是真實(shí)垃圾郵件數(shù)和本組郵件數(shù)量的比值［5］;垃圾郵件重調(diào)率表示在經(jīng)過測(cè)試分類器分類以后的測(cè)試組中包含垃圾郵件數(shù)量和本組郵件數(shù)量的比例，合法郵件的重調(diào)率算法亦同此.為避免將合法郵件誤判為垃圾郵件，在只采用單詞類變量進(jìn)行過濾的基礎(chǔ)上，短語(yǔ)類信息增加對(duì)過濾精度有較小提高，而域變量的微小增加都會(huì)對(duì)過濾效果產(chǎn)生重大的影響，如表1所示.

在采用不同變量組的情況下，圖3給出了垃圾郵件準(zhǔn)確率和重調(diào)率曲線，為更清晰地表示曲線的變化，重調(diào)率取0.85 ～1.0，通過曲線可以看出，隨著變量組合種類的增加，整個(gè)曲線不斷上移，同只采用單詞模式的過濾手段相比，包括域變量的過濾精度最高.

圖3 垃圾郵件準(zhǔn)確率和重調(diào)率曲線

表明對(duì)于指定文本過濾問題，域名信息在過濾過程中對(duì)提高過濾效果有非常大的幫助.

3.4 實(shí)際垃圾郵件的分類

垃圾郵件常分為包含黃色信息和所謂“目標(biāo)信息”2類，根據(jù)實(shí)驗(yàn)要求，用合法郵件、黃色郵件和其他垃圾郵件為匹配模型，創(chuàng)建郵件過濾器.

利用2類不同的垃圾郵件可使學(xué)習(xí)型分類器有更多的自由度，為實(shí)驗(yàn)需要建立一個(gè)由972個(gè)垃圾郵件，211個(gè)合法郵件組成的一個(gè)郵件組，并暫時(shí)將其分成一個(gè)有916個(gè)信息組成的訓(xùn)練組，267個(gè)信息組成的測(cè)試組.為測(cè)試不同垃圾郵件分類的效率，用2種不同的方法來(lái)標(biāo)識(shí)郵件組，首先完成對(duì)每個(gè)郵件是否為垃圾郵件的標(biāo)記，然后再對(duì)分類出的垃圾郵件進(jìn)行內(nèi)部劃分.

表2 依據(jù)垃圾郵件內(nèi)部類型劃分的郵件分類結(jié)果 %

根據(jù)研究分類器的需要，在實(shí)驗(yàn)中將短語(yǔ)和域名類變量引入變量組，通過變量選擇生成50個(gè)變量，再設(shè)定98%為垃圾郵件分類極限，以反映實(shí)驗(yàn)中出現(xiàn)錯(cuò)誤的不對(duì)稱成本.為過濾出垃圾郵件，可將測(cè)試組分成黃色和其他垃圾郵件2類，完成了對(duì)“垃圾”郵件初步的操作，數(shù)據(jù)顯示基于3種選擇的垃圾郵件分類的效果要優(yōu)于2種的.

由表2可以發(fā)現(xiàn)，垃圾郵件內(nèi)部種類的劃分不提高郵件分類效率，反而使精度降低，在給定的準(zhǔn)確率和重調(diào)率的范圍內(nèi)，圖4曲線也反映了這點(diǎn).

圖4 垃圾郵件準(zhǔn)確率和重調(diào)率曲線

圖3垃圾郵件內(nèi)部種類劃分精度原因之一是同3種分類結(jié)果的方案相比較，在2種分類結(jié)果的方案中有明顯指示效應(yīng)的變量在前者的指示作用非常有限，更重要的一點(diǎn)是隨著自由度的增加，同每類結(jié)果對(duì)應(yīng)的、基于分類的變化度在增大，所以同2種分類結(jié)果的方案相比，3種分類結(jié)果的方案在操作中要完成更多的變量匹配，所以設(shè)定參數(shù)的變化對(duì)成熟的分類器性能的影響非常大.

4 仿真過濾

為測(cè)試實(shí)驗(yàn)過濾器的最終效率，提供一個(gè)由2 600個(gè)郵件組成的集合，并已完成它的垃圾郵件的劃分，過濾近10 d某用戶所收到的224信件，依據(jù)測(cè)試結(jié)果，其中有46封為垃圾郵件，用表1中的變量結(jié)構(gòu)來(lái)構(gòu)建學(xué)習(xí)型過濾器，以98%作為垃圾郵件劃分精度的極限.實(shí)驗(yàn)結(jié)果如表3所示.

表3 采用最新訓(xùn)練組過濾效率表

在3封被誤判的垃圾郵件中，有1封包含有部分主觀的內(nèi)容，其余內(nèi)容均為垃圾內(nèi)容，在進(jìn)一步的研究中可劃定為垃圾郵件;其他2封郵件包含來(lái)自服務(wù)器匿名投遞的產(chǎn)品信息，非用戶所需要的，所以從根本上來(lái)講，表3中的劃分結(jié)果對(duì)郵件用戶無(wú)損失，且有比較高的精度的精度，基于上述研究中的結(jié)果繪制了效果曲線圖，如圖4所示.

圖5 仿真過濾效果曲線圖

5 結(jié)語(yǔ)

一個(gè)具備自我學(xué)習(xí)能力的過濾系統(tǒng)能夠排除絕大部分垃圾郵件，郵件正文、人工短語(yǔ)尤其是域名變量，在具體郵件過濾中對(duì)準(zhǔn)確性的提高作用很大，用學(xué)習(xí)型分類模式去完善貝葉斯網(wǎng)絡(luò)，對(duì)于建立高集成度、有域名變量特點(diǎn)的過濾器有指導(dǎo)意義，實(shí)際應(yīng)用中的曲線圖(圖4)證明了系統(tǒng)的可用性.

［1］COHE W W.Learning rule that classify E-Mail［C］//Proceedings of the AAAI Spring Symposium on Machine Learning in Information Access.California:AAAI Press，1996:18-25.

［2］HALL R J.How to avoid unwanted email［J］.Communication of ACM，1998:41(3):88-95.

［3］KUSHMERICK N.Learning to remove internet advertisements［C］//Proceedings of the 3rdAnnual Conference on Autonomous Agents.New York，NY:ACM，1999:175-181.

［4］段宏斌，張健.改進(jìn)的Naive Bayes技術(shù)在反垃圾郵件系統(tǒng)中的應(yīng)用［J］.西北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2006，36(5):737-740.

［5］王寧，張建忠.基于改進(jìn)貝葉斯模型的中文郵件分類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42(31):97-100.

［6］GRAHAM P.Better Bayesian Filtering［EB/OL］.［2003-01-10］.http://http://paulgraham.com/better.html.

［7］RICHARD O D.貝葉斯決策論模式分類［M］.北京:機(jī)械工業(yè)出版社，2003.

Bayesian application study on arithmetic for filtering junk e-mail

CUI Chao1，YANG Wei2，ZHANG Xian-zhong1，ZHANG Zhi-jun3

(1.College of Applied Technology，Qiqihar University，161006 Qiqihar，China，cv63@163.com;2.Qiqihar Information Center，161006 Qiqihar，China;3.Qiqihar information Technology Institute，161006 Qiqihar，China)

To delete spams from User data stream，an adaptive self-learning spam filtering system has been studied and presented.On the basis of cost analysis mistakenly classified of normal and spam e-mail，a filter to meet the requirements of filtering tasks with learning methods of probabilistic is created，and the use of mail domain name characteristic variables for a particular e-mail filtering is studied.Finally，experiments verify the reliability of the algorithm.

bayesian theory;probability;feature-variable;filtering e-mail

TP391

A

0367-6234(2011)11-0145-04

2010-11-10.

崔 超(1961—)，男，教授.

(編輯 張 紅)