用于垃圾郵件的貝葉斯過濾算法研究

曹翠玲，王媛媛，袁野，趙國冬

（1. 哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001；2. 東北林業大學機電工程學院，黑龍江 哈爾濱 150040）

用于垃圾郵件的貝葉斯過濾算法研究

曹翠玲1，王媛媛2，袁野1，趙國冬1

（1. 哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001；2. 東北林業大學機電工程學院，黑龍江 哈爾濱 150040）

研究了基于改進的支持向量機（SVM，support vector machine）算法結合樸素貝葉斯算法在垃圾郵件過濾中的應用。首先，SVM 對訓練集樣本空間中兩類交界處的集合構造一個最優分類超平面；然后，每個樣本根據與其最近鄰的類型是否相同進行取舍，從而降低樣本空間也提高了每個樣本類別的獨立性；最后，利用樸素貝葉斯算法對郵件分類。仿真實驗結果表明，該算法降低了樣本空間復雜度，快速得到最優分類特征子集，有效地提高了垃圾郵件過濾的分類速度、準確率和召回率。

樸素貝葉斯；支持向量機；修剪；垃圾郵件

1 引言

目前的垃圾郵件過濾技術主要有以下幾種。

1) 黑白名單過濾[1,2]，其原理是將發送方的郵箱或者IP放入黑名單列表中，但當對方采用IP代理、動態IP、地址隱藏、偽造等方式發送郵件時，該方法就失效了。

2) 基于規則的過濾技術，該技術的代表是決策樹。最早的決策樹學習系統要追溯到 Hunt于1966年研制的一個概念學習系統（CLS, concept learning system），該系統第一次提出使用決策樹進行概念學習，是許多決策樹學習算法的基礎。隨后，Quinlan提出了迭代分類算法 ID3，1993年又提出C4.5算法[3,4]，旨在克服ID3算法在應用中的不足。C4.5算法對于ID3算法的重要改進是使用信息增益率來選擇屬性。2002年，Ruggieri提出了EC4.5算法[5]，EC4.5算法采用二分搜索取代線性搜索，還提出幾種不同的尋找連續屬性的局部閉值的改進策略。實驗表明，在生成同樣一棵決策樹時，與C4.5算法相比，EC4.5算法可將效率提高5倍，但EC4.5算法占用內存比C4.5算法多。

3) 基于統計的智能學習技術，支持向量機（SVM）、樸素貝葉斯（NB，native Bayes）等都是智能學習技術。比較SVM和NB及其改進算法，實驗結果表明，在召回率和準確率上，SVM算法有較大優勢，但是在分類速度和訓練集、測試集大小上，樸素貝葉斯算法有明顯優勢。馬小龍[6]提出了SVM-EM樸素貝葉斯算法，該算法先利用SVM算法將數據集分成完整集和缺失集，計算缺失屬性數據項與完整屬性數據項的相關度，利用EM 算法對數據不完整屬性進行修補處理，最后利用樸素貝葉斯算法分類。SVM-EM算法主要是根據修補不完整屬性來分類的，缺點是隨著郵件數量的增多，屬性也隨著增多，其中的冗余屬性也相應增加，該算法并沒有處理冗余屬性，隨著郵件數量和樣本集的增加，分類速度和吞吐量就會降低。本文提出的改進的樸素貝葉斯（TSVM-NB）算法有效地解決了冗余屬性，提高了分類速度、準確率和召回率。該算法首先利用SVM 對訓練集樣本空間中兩類交界處的集合構造一個最優分類超平面，明確每個樣本根據與其最近鄰的類型是否相同進行取舍，舍去冗余屬性，從而降低樣本空間也提高了每個樣本類別的獨立性，最后利用樸素貝葉斯算法對郵件分類，在分類速度和準確率上都有所提高。

2 樸素貝葉斯算法及其改進

2.1 垃圾郵件過濾流程

電子郵件是基于文本形式的，而且本身是一種無結構的文本，為了使計算機能夠對郵件進行學習和處理，一般采用空間向量模型，將電子郵件集用向量集合表示，所以需要對郵件預處理。預處理包括文本分詞、文本標注、特征選擇、特征詞權重計算等。

預處理完成后就是郵件分類，現有的主流文本分類方法是樸素貝葉斯算法和支持向量機算法，兩者的分類原理、使用場合、效率等各方面都有所不同。圖1為垃圾郵件過濾的簡單流程。

圖1 垃圾郵件過濾的簡單流程

1) 文本分詞是將一段連續的中文句子按照一定的規則拆分成具有一定語義的詞，想要對一句中文進行處理，必須要將這句中文拆分成不同的詞來進行處理，這是對中文信息處理的基礎。

2) 文本標注是對分詞詞性標注，以便后續的特征選擇，即要確定每個詞是名詞、動詞、形容詞或其他詞性，除此之外，還需要在集合中使用停用詞表刪除助詞、虛詞等無意義或者貢獻不大的詞語。

3) 電子郵件內容經過分詞處理后，形成一個代表電子郵件內容的特征向量，這個特征向量包含了郵件內容所有被劃分的詞，特征項提取是指從分詞結果集中選擇具有代表文章內容信息的分詞。

4) 對于不同的特征選擇方法，其特征向量權重的計算方法不同，權重代表的意義也不一樣。比如，TF-IDF[7]是根據一篇文檔詞如果出現頻率高，但是在其他文檔出現頻率低，則說明該詞具有很好的區分文檔的能力，詞頻方法是根據某個詞出現的頻率，將出現頻率小的刪除。

5) 本文的重點就是分類，下文詳細介紹分類方法以及在傳統的分類方法上的改進算法。

2.2 樸素貝葉斯算法模型

樸素貝葉斯文本分類原理[8～10]是求解向量X (x1, x2,… ,xn)屬于類別 C (c1, c2,…, cj)的概率值(P1, P2,… ,Pn)，其中，Pn為 X (x1, x2,… ,xn)屬于cj的概率，則 max(P1, P2,… ,Pn)所對應的類別就是文本X所屬的類別，因此，分類問題被描述為求解方程式(1)的最大值。

其中

1) P( cj)是訓練文本中，文本屬于類別 cj的概率。

3) P( c1,c2,… ,cn)是給定所有類別的聯合概率。

顯然，對于給定的所有類別，分母 P( c1, c2,…,cn)是一個已知的常數，所以，將式(1)簡化為求解式(2)的最大值。

又根據樸素貝葉斯假設，文本特征向量屬性x1,x2,… ,xn獨立同分布，其聯合概率分布等于各個屬性特征概率分布的乘積，即

所以

4) 在前文提到的樸素貝葉斯算法及其改進算法利用的都是樸素貝葉斯的基本原理，只是放松了獨立性假設條件，但是那些實際上相互不獨立的屬性都還是存在于訓練樣本集中。從式(4)中可以看出，最后計算文本類別概率時，用到的還是條件獨立的假設，那么實際上相互不獨立的屬性還是限制了算法的性能，特別是在準確率和召回率方面，這些算法都遇到了一定的瓶頸。那么，有沒有一種算法，可以將獨立性假設條件應用到現實世界中？如果某個算法將所有參與到計算中的樣本集屬性根據其是否相關聯處理，即如果 2個屬性之間是有關系、不獨立的，就能確定這 2個屬性所屬類別是否相同，然后根據算法來處理這2個屬性，這就是本文提出的改進的樸素貝葉斯算法TSVM-NB。

2.3 基于SVM算法的改進樸素貝葉斯算法

2.3.1 支持向量機

支持向量機[11,12]因為顯著的泛化能力而倍受人們的青睞，原理是在特征空間內構造出一個超平面，使兩類之間的寬度達到最大，即距離構造的超平面最遠，但還必須使類別的錯分懲罰達到最小，所以SVM的本質就是二次尋優問題。

在訓練集可分的情況下，SVM構造一個最優超平面

使樣本集(xi, yi)( i =1,2,… ,n;{+1 ,?1 })，滿足約束條件

并且邊界平面最優化，即最小化倒數，

當訓練集線性不可分時，引進松弛因子εi≥ 0及懲罰參數C，在約束條件1 ? εi( i =1,…, n)下最小化函數分類規則只需取

核函數的引入是SVM算法的一大特點，低維空間向量集往往很難劃分，那就自然想到將低維空間映射到高維空間，但隨之就會增加計算復雜度，而核函數很巧妙地解決了這個問題。

K (x, y) =φ( x )φ(y)，其中，φ表示某種映射，只要適當選擇核函數，就可以得到對應的高維空間的分類函數

其中， φ( x)是比x高維的向量（無需知道φ的具體形式），由于 K (x, y) =φ(x )? φ(y)只涉及x、y，并沒有涉及高維運算，所以沒有增加計算復雜度。

2.3.2 改進的樸素貝葉斯TSVM-NB

前文提到，樸素貝葉斯算法的使用前提條件是訓練集樣本中的屬性是相互獨立的，利用支持向量機中的原理，可以找到完美的一個超平面，將兩類之間的距離達到最大即兩類邊界處的混疊情況不會出現，但是在實際應用中，這種獨立性假設條件是不成立的，這就嚴重影響了樸素貝葉斯算法分類的召回率與正確率，本文利用支持向量機修剪技術[13]降低屬性之間的交叉重疊，增強其獨立性，并結合樸素貝葉算法分類速度快的優點提出了一種改進的樸素貝葉斯算法TSVM-NB。

首先對訓練集利用樸素貝葉斯算法進行初次訓練，得到訓練集合中的每個向量的類別及初次訓練類別結合，然后用下面算法對訓練集合進行修剪。

找出每一個向量點的最近鄰，然后對每一向量點做如下操作，如果該點與其最近鄰屬于同類，則保留此點；如果該點與其最近鄰屬于異類，將該點刪除。

什么是最近鄰，怎么找到最近鄰？采用歐式距離作為2個向量之間的距離，即設2個向量為x (x1, x2,… ,xn)， x (x1,x2,… ,xn)，則x與 x之

i ii i j jj jij間的距離定義為

一個向量的最近鄰就是與其距離最近的向量。

上述方法的實現方法如下：給定一個已經被樸素貝葉算法初次訓練過的訓練集 (x1, y1),(x2, y2),…, (x ,y )(x ∈ Rn,y ∈{?1 ,1},i= 1,2,3,…, m)，將訓

mmi i練集表示為矩陣

輸入： X (x1, x2,…, xm)，Y (y1, y2,… ,ym)為樣本訓練集向量。

輸出：經過TSVM訓練之后的樣本類別向量V (v1, v2,…, vm)。

1) 計算每2個向量的距離，自身距離為無窮

2) 找到每個向量的最近鄰

3) 判斷每個向量的類標與其最近鄰是否一致，類標不一致，則刪除該向量

修剪后的訓練集用NB算法對郵件分類。

3 算法在郵件過濾中的實現

郵件分類的具體實現方式，如圖2所示。

1) 以大量的正常郵件和垃圾郵件作為訓練集，訓練集分詞并標注，采用中國科學院計算技術研究所研發的 ICTCLAS漢語分詞系統實現自動分詞和文本標注。

圖2 垃圾郵件過濾流程

2) 特征選擇采用信息增益的方法，在不區分垃圾郵件與正常郵件的全域范圍內，計算每個特征X的IG值，然后按照IG值大小排序，依次選擇所需數量作為特征。選擇完成之后構成特征向量，特征向量代表該郵件。

3) 特征向量構成之后先用樸素貝葉斯算法對特征向量初次訓練，得到初始的特征向量訓練集合及其類別。

4) 用TSVM對3)中的特征向量修剪，修剪的目的是降低特征屬性之間的獨立性約束，即降低維度，使特征向量集合減少冗余。修剪之后得到修剪后的訓練集。

5) 樸素貝葉斯算法根據修剪后的訓練集對郵件分類。

4 實驗結果分析

本文所有實驗都是在普通PC（Intel CORE 7i，2.60 GHz CPU，8.0 GB RAM），軟件為MyEclipse 8.5，算法語言為 Java和 Matlab實現提出的TSVM-NB算法，實驗數據來自數據堂DATAMALL的5 000封正常郵件和5 000封垃圾郵件，其中，4 000封垃圾郵件和4 000封正常郵件作為訓練集，其余的作為測試集。表1是對數據集的基本描述。

表1 數據集描述

垃圾郵件和正常郵件都來自不同的領域，并且涉及的垃圾類別也不一樣。例如，垃圾廣告中就包含很多不正常營銷、推銷、培訓等垃圾信息；特殊亂碼字符類垃圾郵件往往是在一些亂碼字符中夾雜一些上述垃圾廣告或者黃色暴力廣告；特殊言論是包含一些敏感詞匯，宣傳不正當宗教，威脅國家安全等的一些言論信息。正常的工作和交流郵件就是人與人之間基本溝通的郵件，當然這些郵件當中可能也包含正常廣告、營銷類等內容。

最后從召回率、正確率以及在不同訓練集數量下的運行速度等指標來評估比較樸素貝葉斯算法、支持向量機算法以及利用SVM改進的樸素貝葉斯算法。

本文實驗特征選擇采用信息增益（IG）方法，多維度分析算法在不同的過濾閾值、不同樣本集數量實驗結果，并從召回率、正確率、分類速度、支持向量個數等方面比較3種算法。

如圖3所示，越多的訓練樣本集結果越精確，但是過多的訓練樣本集使向量個數增加，而且過多樣本集使代表性向量增加的同時，冗余向量、無用向量也增加，這使計算量跟著增加，大大降低了分類速度，利用TSVM-NB算法修剪向量，減掉冗余和無用向量，降低向量個數從而增加計算速度（圖4與圖3類似）。圖5是3種算法在不同的樣本集下支持向量個數比較。改進的算法支持向量個數減少，計算速度就會明顯提高，3種算法的速度比較如圖6所示。

圖3 3種算法正確率對比

圖4 3種算法召回率對比

圖5 3種算法支持向量個數對比

圖6 3種算法分類耗時比較

從圖6中可以看出，在樣本集數量較小的情況下，3種算法的分類速度沒有太大的區別，但是隨著樣本集的增加，SVM算法和NB算法的分類所用時間上升很快。利用SVM算法改進的樸素貝葉斯算法耗時雖然增加（隨著樣本集數量的增加，耗時增加這是必然的），但是耗時增加比較慢，所以相對來說，該算法一定程度上降低了耗時增長的速率，從而提高了分類速度。

將訓練集分為1 000封、2 000封、3 000封、4 000封、5 000封、6 000封、7 000封、8 000封等8個階段，每個階段分別用SVM算法、NB算法計算TSVM-NB的正確率和召回率，從圖3和圖4可以看出，在訓練集比較大的情況下，SVM算法不管是正確率還是召回率都不如其他 2種算法，并且達到一定量之后 2種指標反而下降，這是因為SVM算法不適合在大量郵件集下應用，樸素貝葉斯算法比SVM效果好，但實驗中當郵件訓練集超過 4 000封時，召回率和正確率也有所下降，改進的樸素貝葉斯算法TSVM-NB算法不管是正確率還是召回率在一定程度上都有所提高。

5 結束語

本文在支持向量機算法和樸素貝葉斯算法的基礎上，針對樸素貝葉斯算法的限制——屬性相互條件獨立，用 SVM尋找最優平面，修剪重疊屬性，增強屬性獨立，提出了改進的樸素貝葉斯算法 TSVM-NB，并根據垃圾郵件系統的評價指標正確率和召回率評估該算法，經過大量實驗，證明該算法可以在一定程度上提高垃圾郵件處理的正確率、召回率以及分類速度。

該算法主要是適用于屬性向量之間的交錯重疊特別嚴重的數據集中，即類別劃分不是特別容易的情況，如果數據集之間混疊性較弱，該算法的優勢就體現不出來。

隨著科技的發展，垃圾郵件不僅局限于文本形式，還存在垃圾圖片、垃圾視頻、垃圾音頻等各種形式，本文研究算法只是針對文本形式的垃圾郵件，如何高效過濾圖片、視頻、音頻將會在下一步工作中進行研究。

[1] [EB/OL].http://www.anti-spam.org.cn/.

[2] JI W Y, KIM H, HUH J H. Hybrid spam filtering for mobile communication[J]. Computers & Security, 2009, 29(4):446-459.

[3] HAIBO H,GARCIA E A. Learning form imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9): 1263-1284.

[4] WU X, KUMAR V, ROSS QUINLAN J, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1-37.

[5] RUGGIERI S. Efficient C4.5[J]. IEEE Transactions on Knowledge & Data Engineering, 2002, 14(2):438-444.

[6] 馬小龍. 一種改進的貝葉斯算法在垃圾郵件過濾中的研究[J].計算機應用研究, 2012, 29(3):1091-1094. MA X L. Research of spam-filtering based on optimized native Bayesian algorithm[J]. Alication Research of Computer, 2012, 29(3): 1091-1094.

[7] SCHOLKOPF B, MIKA S, BURGES C, et al. Input space versus feature space in kernel-based methods[J]. IEEE Transactions on Neural Network,1999,10(5):1000-1017.

[8] FRIEDMAN N, GEIGER D, GOLDSZMIDT M. Bayesian network classifiers[J].Machine Learning,1997,29(2/3):131-163.

[9] 石洪波, 王志海, 黃厚寬, 等.一種限定性的雙層貝葉斯分類模型[J]. 軟件學報 ,2004,15(2):193-199. SHI H B, WANG Z H, HUANG H K, et al. A restricted double-level Bayesian classification model[J]. Journal of Software, 2004, 15(2): 193-199.

[10] 王雙成, 杜瑞杰, 劉穎. 連續屬性完全貝葉斯分類器的學習與優化[J]. 計算機學報,2012,35(10):2129-2138. WANG S C, DU R J, LIU Y. The learning and optimization of full Bayes classifiers with continuous attributes[J]. Chinese Journal of Computer, 2012, 35(10):2129-2138.

[11] 曾志強, 高濟. 基于向量集簡約的精簡支持向量機[J]. 軟件學報, 2007, 18(11): 2719-2727. ZENG Z Q, GAO J. Simplified support vector machine based on reduced vector set method[J]. Journal of Software, 2007, 18(11): 2719-2727.

[12] 李曉黎, 劉繼敏, 史忠植. 基于支持向量機和無監督聚類相結合的中文網頁分類器[J]. 計算機學報, 2001,24(1):62-68. LI X L, LIU J M, SHI Z Z. A Chinese Web page classifier based on support vector machine and unsupervised clustering[J]. Chinese Journal of Computer, 2001, 24(1): 62-68.

[13] 李紅蓮, 王春華, 袁保宗.一種改進的支持向量機: NN-SVM[J].計算機學報, 2003, 26(8): 1015-1020. LI H L, WANG C H, YUAN Z B. A improved SVM: NN-SVM[J]. Chinese Journal of Computer,2003, 26(8): 1015-1020.

趙國冬（1978-），黑龍江大慶人，博士，哈爾濱工程大學講師，主要研究方向為機器人、信息安全。

Research of a spam filter based on improved naive Bayes algorithm

CAO Cui-ling1, WANG Yuan-yuan2, YUAN Ye1, ZHAO Guo-dong1
(1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China; 2. College of Mechanical and Electrical Engineering, Northeast Forestry University, Harbin 150040, China)

In spam filtering filed, naive Bayes algorithm is one of the most popular algorithm, a modified using support vector machine(SVM) of the native Bayes algorithm :SVM-NB was proposed. Firstly, SVM constructs an optimal separating hyperplane for training set in the sample space at the junction two types of collection, Secondly, according to its similarities and differences between the neighboring class mark for each sample to reduce the sample space also increase the independence of classes of each samples. Finally, using naive Bayesian classification algorithm for mails. The simulation results show that the algorithm reduces the sample space complexity, get the optimal classification feature subset fast, improve the classification speed and accuracy of spam filtering effectively.

naive Bayes, SVM, trim, spam mail

TP319

A

10.11959/j.issn.2096-109x.2017.00119

曹翠玲（1990-），女，河北邯鄲人，哈爾濱工程大學碩士生，主要研究方向為網絡信息安全、嵌入式系統。

王媛媛（1995-），女，黑龍江哈爾濱人，東北林業大學本科生，主要研究方向為信息安全。

袁野（1995-），男，黑龍江北安人，哈爾濱工程大學本科生，主要研究方向為嵌入式系統。

2016-10-27；

2016-11-25。通信作者：曹翠玲，caocuiling0927@163.com