貝葉斯網絡在過濾垃圾郵件算法中的應用研究

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

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

貝葉斯網絡在過濾垃圾郵件算法中的應用研究

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

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

為在用戶數據流中刪除垃圾郵件，研究了具有自我學習能力的自適應郵件過濾系統.在對正常和垃圾2類郵件誤分類成本分析的基礎上，利用概率性的學習方法創建滿足過濾任務需要的過濾器，且討論使用郵件域名特征變量進行特定郵件過濾并設計了過濾器，最后對實際郵件組進行操作，驗證了算法的可靠性.

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

早期對郵件的過濾只是對郵件正文進行過濾，邏輯過濾規則只是機械地使用二進制決策來決定取舍，而這種規則是有局限性的.研究能根據過濾環境特征變量［1］變化進行自我調整，并能進行自我學習的郵件過濾系統是一種解決辦法.由于垃圾郵件特征變化的多樣性和實時性，邏輯過濾規則的優化對系統提出了更高的要求.理想的過濾系統應具備隨過濾目標對象的特征變化而自動調整過濾規則的能力，對郵件進行分析，能直接從系統郵件緩沖區讀取數據并進行學習，個性化地為每個用戶架構有自身特征的過濾系統，過濾系統完成對目標的操作.依據貝葉斯定理設計的分類器，本文設計一個功能模塊，并制訂了一個可行的過濾方案，并對郵件錯誤成本進行定量分析，完成垃圾郵件過濾［2］.

1 貝葉斯模型

采用貝葉斯定理的分類器，在自動生成概率性的文本分類模型的過程中，將貝葉斯定理應用到分類技術的算法中，利用貝葉斯定理建模，既能解決傳統文本過濾問題，又可以在貝葉斯過濾器中引入具體的特征變量，將郵件域名信息同要完成的指定任務結合起來，聯合使用研究模型和系統損失模型，對目標文件作出是否為垃圾郵件的判定.

1.1 貝葉斯網絡

為完成垃圾郵件的檢測需要建立一個概率性的分類器，利用貝葉斯定理的網絡形式和其直接的、非循環形式的對應圖表達一個緊密的幾率分布，圖1中任一個隨機變量xi都用一個節點來表示，兩節點間的線段表示由父、子節點分別確定的兩變量間概率相關性.網絡結構表明網絡中每一個節點xi都有條件地獨立于由其父節點給出的其他節點.為描述幾率分布，將網絡中的節點xi組成一個條件幾率圖，圖1用來說明對應的概率分布.

對每個過濾任務，一個貝葉斯過濾器就是一個貝葉斯網絡，網絡中的節點C表示級別，每個節點xi用于表示一個特征變量［3］，將一個指定的范例X(將xi(i=1，2，3，…))的值分配給對應的特征變量，網絡允許為每一個級別CK計算幾率P(C=cK|X=x)為

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

為降低貝葉斯過濾器對特征變量xi的限制，過濾方法允許特征變量xi間有限形式的相關.圖1(a)展示了貝葉斯過濾器在具有同其他過濾器相同的上述特征變量xi間有限形式時的系統結構;圖1(b)則表現了特征變量間具備有限相關性的復雜貝葉斯分類器的系統結構.

圖1 同貝葉斯過濾器相對應的貝葉斯網絡

1.2 變量空間模型

采用貝葉斯定理的垃圾郵件過濾系統在對郵件文本進行分類時，要依據相應的郵件信息形成特征變量.用一個變量空間模型將變量空間維數的定義同整個郵件庫中給定的詞對應起來，每個具體的單詞用一個二進制變量表示，表明單詞出現與否.

2 郵件域名的作用

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

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

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

首先完成對郵件外部表述文字有無特定短語匹配的檢測，如“免費”、“只是為了money”等，在實驗中引入了一個有40個特征短語變量的集合，使用概率性的過濾方案，在當前規則限定下，利用用戶手動建立起來的，由短語組成的特征變量，快速完成對當前郵件的過濾.

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

圖2 垃圾郵件和正常郵件標題中包含非字母和數字的百分率變化曲線

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

3 垃圾郵件總體劃分和實驗室測試

為確認研究結果，對垃圾郵件進行過濾實驗，以信件正文和特征變量為對象進行基本分類操作，對性能進行了測定，同時對過濾器在操作環境設定領域的學習效率進行了評估.

3.1 建立實驗用樣本分類器

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

盡管實驗中50個變量不是最佳值，開始階段的多個實驗還是表明了由50個特征變量提供的實驗結果是可靠的.

3.2 添加域名特征變量

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

3.3 郵件分類敏感成本理論和實際測試結果

設郵件為垃圾郵件可能性＞98%時，只能被劃分為垃圾郵件.實驗中得到的一組數值顯示了98%的基本值是滿足實驗任務要求的，根據變量結構的變化對垃圾和正常郵件進行再調用和分類的有關數據統計如表1所示.

表1 采用不同變量組的分類結果 %

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

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

圖3 垃圾郵件準確率和重調率曲線

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

3.4 實際垃圾郵件的分類

垃圾郵件常分為包含黃色信息和所謂“目標信息”2類，根據實驗要求，用合法郵件、黃色郵件和其他垃圾郵件為匹配模型，創建郵件過濾器.

利用2類不同的垃圾郵件可使學習型分類器有更多的自由度，為實驗需要建立一個由972個垃圾郵件，211個合法郵件組成的一個郵件組，并暫時將其分成一個有916個信息組成的訓練組，267個信息組成的測試組.為測試不同垃圾郵件分類的效率，用2種不同的方法來標識郵件組，首先完成對每個郵件是否為垃圾郵件的標記，然后再對分類出的垃圾郵件進行內部劃分.

表2 依據垃圾郵件內部類型劃分的郵件分類結果 %

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

由表2可以發現，垃圾郵件內部種類的劃分不提高郵件分類效率，反而使精度降低，在給定的準確率和重調率的范圍內，圖4曲線也反映了這點.

圖4 垃圾郵件準確率和重調率曲線

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

4 仿真過濾

為測試實驗過濾器的最終效率，提供一個由2 600個郵件組成的集合，并已完成它的垃圾郵件的劃分，過濾近10 d某用戶所收到的224信件，依據測試結果，其中有46封為垃圾郵件，用表1中的變量結構來構建學習型過濾器，以98%作為垃圾郵件劃分精度的極限.實驗結果如表3所示.

表3 采用最新訓練組過濾效率表

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

圖5 仿真過濾效果曲線圖

5 結語

一個具備自我學習能力的過濾系統能夠排除絕大部分垃圾郵件，郵件正文、人工短語尤其是域名變量，在具體郵件過濾中對準確性的提高作用很大，用學習型分類模式去完善貝葉斯網絡，對于建立高集成度、有域名變量特點的過濾器有指導意義，實際應用中的曲線圖(圖4)證明了系統的可用性.

［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］段宏斌，張健.改進的Naive Bayes技術在反垃圾郵件系統中的應用［J］.西北大學學報(自然科學版)，2006，36(5):737-740.

［5］王寧，張建忠.基于改進貝葉斯模型的中文郵件分類算法［J］.計算機工程與應用，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］.北京:機械工業出版社，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—)，男，教授.

(編輯 張 紅)