基于自適應性分類器的垃圾郵件檢測

陳 龍,梁意文,譚成予

(武漢大學 計算機學院,武漢 430072)

0 概述

近年來,垃圾郵件泛濫給人們的通信造成很大的困擾和不便,其不僅消耗通信帶寬和網絡資源,且浪費人們的處理時間,因此,對垃圾郵件進行檢測很有實際意義,但是,垃圾郵件越來越容易偽裝成正常郵件而繞過檢測,其中新型垃圾郵件的檢測更是成為一大難題。

目前,垃圾郵件檢測技術分為2類:基于知識工程的方法和基于機器學習的方法[1]。基于知識工程的方法主要包括黑名單白名單[2]、灰名單[3]等,其利用已知規(guī)則鑒別垃圾郵件。該方法主要依賴于對當前發(fā)件人身份的識別[4],優(yōu)點是鑒別準確率高,缺點是需要人為頻繁更新規(guī)則,不易于維護?；跈C器學習的方法興起于20世紀90年代末期,主要包括樸素貝葉斯[5]、支持向量機(Support Vector Machine,SVM)[6]、人工神經網絡[7],該方法通過樣本訓練集生成分類器以對垃圾郵件進行識別,優(yōu)點是其獨立于知識庫,無需經常更新,缺點是效果優(yōu)劣完全依賴于訓練集,只有測試郵件跟訓練集的正常郵件和垃圾郵件訓練樣本形式匹配時才能正確分類。但是,目前垃圾郵件的偽裝技術愈加成熟,因此,分類器對偽裝郵件的正確識別成為影響垃圾郵件檢測準確率的重要因素。

本文受生物免疫系統(tǒng)多層防御機制、自適應性強的啟示,結合反向選擇算法(Negative Selection Algorithm,NSA)和SVM,設計一種新的自適應性分類器,將其應用于垃圾郵件檢測。該分類器對郵件進行預檢驗并快速區(qū)別出能匹配檢測模型的“正常郵件”和垃圾郵件,然后結合反向選擇的自適應性對該“正常郵件”進行二次檢測,得到最終的正常郵件和新型垃圾郵件,同時計算出最初最優(yōu)超平面模型得到的垃圾郵件檢測率和正常郵件準確率,最后根據(jù)正常郵件和垃圾郵件集合去自適應調整初始化的最優(yōu)超平面方程,直至垃圾郵件的檢測率和正常郵件的準確率趨于穩(wěn)定,此時,分類器對當前的郵件分類達到最優(yōu)。

1 垃圾郵件檢測方法

文獻[8]將計算機系統(tǒng)的安全保護比喻成學習鑒別“自我”“非我”的問題,其基于生物免疫系統(tǒng)的T細胞生成機制,提出一種變化檢測的NSA,并且闡明該方法在計算機病毒檢測方面的可行性。

文獻[9]首次將計算機免疫應用于垃圾郵件檢測,將“自我”當成正常郵件,“非我”比喻成垃圾郵件,借鑒抗體匹配抗原的思想隨機生成垃圾郵件檢測器,且在系統(tǒng)運行過程中建立權值和閾值的評價體系,其中匹配次數(shù)多的檢測器其權值較大,通過將檢測器的權值和與閾值進行比較來判斷郵件類別。

文獻[10]針對垃圾郵件重復性(每個郵件服務器的眾多用戶都會收到相同的垃圾郵件)和迷惑性(不斷改變垃圾郵件的特征關鍵詞來繞過垃圾郵件過濾器,但是該改變不會偏差太大)的共性,無需先驗信息,僅借鑒NSA來進行垃圾郵件檢測。該算法包含隨機檢測器生成、檢測器成熟、抗原匹配和檢測器老化4個并行的工作模塊,以及自我?guī)旌蜋z測器庫2個庫。在系統(tǒng)學習垃圾郵件模式的1/3階段,垃圾郵件檢測率就超過80%,該方法大多情況下檢測率都超過70%。

文獻[11]結合神經網絡與NSA對垃圾郵件進行區(qū)分。先將已去重的檢測集劃分為“自我”和“非我”,然后將由“自我”和“非我”濃度向量生成的特征向量作為神經網絡分類器的輸入,分類找出程序的“自我”“非我”特征向量。神經網絡和人工免疫的結合,提高了垃圾郵件檢測率,且使得該兩種不同的檢測器在統(tǒng)一的平臺上獲得高效的運行性能。

文獻[12]受NSA的啟發(fā),改進差分優(yōu)化方法(NSA-DE),將其用于垃圾郵件檢測。該算法在隨機檢測器的生成階段使用局部差分進化,將局部離群系數(shù)作為適應函數(shù),求解檢測器和非垃圾郵件在空間上的最大距離。理論分析和實驗結果均表明,相比標準的NSA,NSA-DE性能較高。

文獻[13]基于增量SVM和人工免疫(克隆選擇)的思想,針對郵件流的垃圾郵件檢測提出不間斷檢測的方法。該方法使用滑動窗口標注郵件,追蹤郵件內容和用戶興趣的動態(tài)變化,其中一封新郵件的最終標簽由多數(shù)表決判定。滑動窗口被用來清除過時信息,其包含的分類器動態(tài)更新采用超邊際分析技術。在其不間斷的檢測過程中,使用8種不同的方法,本文選取3個基準數(shù)據(jù)集對該8種方法分別就正確率、精確率、召回率、失誤率和速度5個指標進行比較,結果表明該8種方法在垃圾郵件檢測的實際應用中具有良好的性能。

目前,由于自身的局限性,單一檢測方法不能很好應對垃圾郵件內容形式多變的特性,因此越來越多的混合方法被提出以解決垃圾郵件檢測問題[14]。混合方法綜合了多種單一方法的優(yōu)勢,規(guī)避其不足,在性能方面有明顯的提升。本文正是將NSA和SVM進行結合,提出一種基于自適應性分類器的垃圾郵件檢測方法。

2 自適應性檢測模型

2.1 反向選擇算法

NSA最初在1994年被提出,該算法模仿人工免疫的反向選擇過程,隨機產生檢測器,將檢測到“自我”的檢測器清除,保留能正確檢測“非我”的檢測器。該算法包含數(shù)據(jù)表示、訓練階段和測試階段。數(shù)據(jù)一般用二進制或實值表示,訓練階段(也稱探測器生成階段)利用既定的訓練算法隨機生成探測器,測試階段通過評估探測器是否會匹配正常郵件來確認探測器是否成熟,如果能匹配正常郵件,則丟棄該探測器,反之,說明該探測器已成熟,可以投入使用。圖1和圖2分別展示了NSA應用在垃圾郵件檢測中的訓練過程和測試評估過程。

圖1 NSA訓練過程

圖2 NSA測試過程

NSA能夠根據(jù)“自我”來辨別“非我”,如果正常郵件樣本足夠多,該算法就能根據(jù)外來郵件與成熟檢測器是否匹配來判斷郵件是否為垃圾郵件。

2.2 支持向量機

SVM于1995年首次被提出,其建立在統(tǒng)計學習理論的VC維理論和結構風險最小原理的基礎上,根據(jù)有限的樣本信息,在模型的復雜性(即對特定訓練樣本的學習精度)和學習能力(即無錯誤地識別任意樣本的能力)之間尋求最佳平衡,以獲得最好的推廣能力(或稱泛化能力)。

如圖3所示,SVM利用已知的正常郵件和垃圾郵件樣本,用其訓練出檢測模型并使用該模型去鑒別其他郵件。

圖3 SVM垃圾郵件檢測模型

SVM垃圾郵件檢測方法的缺陷在于垃圾郵件形式多變,而檢測模型卻固定不變,因此,該方法只能檢測出與模型相匹配的垃圾郵件。

2.3 自適應性垃圾郵件檢測模型

本文借鑒上述2個算法的思想,建立如圖4所示的自適應性垃圾郵件檢測模型。對準備好的公有實驗數(shù)據(jù)集進行特征降維,利用現(xiàn)有的數(shù)據(jù)抽樣分別生成基于SVM的最優(yōu)超平面方程和基于NSA的成熟檢測器模型。輸入的測試郵件先經過最優(yōu)超平面以判定其是否為垃圾郵件,若是,則將該郵件放入垃圾郵件集合;若不是,則開始第二輪成熟檢測器的判定,如果不能匹配成熟檢測器,則將該郵件放入正常郵件集合;反之,將其放入垃圾郵件集合。最后結合2輪得到的垃圾郵件和正常郵件集合,更新初始的郵件樣本,動態(tài)調整最優(yōu)超平面方程以適應新型垃圾郵件的檢測,直至該檢測器的正常郵件準確率和垃圾郵件檢測率都趨于穩(wěn)定,停止更新。

圖4 自適應性垃圾郵件檢測模型

自適應性檢測模型第1層使用檢測精度高、高維模式識別效果佳的SVM分類超平面進行過濾,該層的目標是盡最大可能將與樣本集特征匹配的正常郵件和垃圾郵件區(qū)分到其應屬的集合,存在的問題是機器學習算法具有無法有效檢測新型垃圾郵件的固有缺陷,因此,在該層中,會有較多的新型垃圾郵件被錯誤歸類在模型所輸出的“正常郵件”集合中;第2層使用NSA對第1層的“正常郵件”進行二次過濾,這是一個自適應的過程,開始時可能由于樣本數(shù)量少,檢測的新型垃圾郵件不多,但是隨著樣本數(shù)量的補充,“自我”集合(正常郵件集合)越來越豐富完備,檢測出的新型垃圾郵件會越來越多。通過上述2次檢測,能夠有效減少垃圾郵件漏報率,提升整體分類效果。下文還提出運用NSA檢測的新型垃圾郵件增量,更新原有的樣本訓練集從而更新SVM的分類超平面,通過優(yōu)化SVM模型以提升該方法的檢測效果。

2.3.1 郵件預處理

郵件預處理階段是對數(shù)據(jù)集中的郵件進行初步加工,將郵件內容轉化為后續(xù)模型易處理的標準形式,一般是將每封郵件處理成一個固定維數(shù)的郵件向量。該階段主要包括文本分詞、去除停用詞和詞匯還原3個步驟。

1)文本分詞。數(shù)據(jù)集是英文郵件,文本分詞將每封郵件的內容分解成一個包含很多單詞的數(shù)組(允許數(shù)組有多個相同單詞),其主要方法是根據(jù)單詞分隔符(包括空格、符號、段落)將每封郵件的文本內容分割成各個獨立的單詞。

2)去除停用詞。停用詞是一些高頻出現(xiàn)但是不重要的詞,如“a”“an”“and”等。因為停用詞會對郵件關鍵詞的特征選取造成影響,所以需根據(jù)已收錄的停用詞表將郵件中出現(xiàn)的停用詞進行去除。

3)詞匯還原。也稱詞干提取,是針對英文單詞的特有處理。有些單詞在單復數(shù)、時態(tài)間進行轉變,但是在計算相關性時,其應該當作同一個單詞來處理。如“creat”“created”“creating”都應該還原成同一個單詞“creat”來處理。詞匯還原的目的是將該不同類型的詞還原為同一個單詞。

2.3.2 郵件表示

當數(shù)據(jù)集里的郵件經過預處理后,每封郵件都可以看成是一個單詞列表,其主要包含主題、正文內容和收發(fā)件人等關鍵信息。本文將郵件數(shù)據(jù)集中出現(xiàn)的每個單詞都當成郵件的一個特征,因此,每封郵件都可以由一個包含多個單詞的特征向量來表示。

常用的特征提取方法包括二進制表示、TF-IDF(Term Frequency-Inverse Document Frequency)[15]、TF(Term Frequency)、DF(Document Frequency)[16]等。本文采用二進制的方法表示郵件的特征向量。如果Wi表示郵件的任意一個單詞,則郵件可以表示為Mail=(W1,W2,…,Wm)(m表示特征向量的個數(shù),即單詞的總個數(shù))。Wi的取值為0或1,1代表該單詞出現(xiàn)在郵件中,0則反之。

2.3.3 特征降維

當數(shù)據(jù)集中的郵件經過文本處理后,每封郵件都可以看成一個單詞列表,不同郵件同一單詞的頻率、位置、區(qū)分性大不相同,該單詞根據(jù)不同的特征選擇機制,分別計算其對文本的影響強度值,并進行排名,強度值大于閾值的詞匯被選取為特征詞,反之,則丟棄。該過程根據(jù)單詞的重要程度(垃圾郵件和正常郵件的可區(qū)分度)將所有的單詞進行排序,選取重要程度高的單詞作為郵件特征關鍵詞,并開始特征表示階段。如果沒有詞篩選這一階段,單詞數(shù)量過多,特征不明顯且雜亂的情況下,不僅會因為特征維度高而造成維度災難,且無法選取有效的特征準確區(qū)分正常郵件和垃圾郵件,從而影響后續(xù)分類效果。通過詞篩選這一階段,一方面可以減少區(qū)分度較差的單詞,降低其帶來的不良影響,另一方面可以降低特征維度,減小計算復雜度。

在大多數(shù)文檔中經常出現(xiàn)的特征,無法區(qū)分文檔,而很少出現(xiàn)的單詞,在分類過程中不能給予人們足夠多信息[17],因此,本文采用的方法是丟棄在郵件數(shù)據(jù)集中出現(xiàn)頻率達95%以上和5%以下的特征[18]。

2.3.4 自適應性分類器

分類器的設計主要涉及SVM的分類平面和NSA的檢測器2個模塊。圖5所示為SVM求解線性可分問題的最優(yōu)分類線示意圖。

圖5 SVM最優(yōu)分類線示意圖

NSA模塊中,初始化隨機生成的檢測器與“自我”集合(本文指正常郵件)進行匹配,如果能匹配,則刪除該檢測器進行重新生成,如果未能匹配,則將其進化為成熟檢測器。本文選取的是簡單通用的r連續(xù)位匹配規(guī)則[20],具體步驟為:首先初始化隨機生成二進制形式的未成熟檢測器d,然后將該檢測器與“自我”集合S的所有個體逐一匹配,如果存在至少一個個體Sk與檢測器連續(xù)對應的r位相同,則認為該檢測器與樣本匹配,刪除該檢測器;否則,將該檢測器加入成熟檢測器集合D中[21]。

圖6所示為自適應性分類器結構框架,從郵件數(shù)據(jù)集中抽樣的樣本經過SVM[22]和NSA[23]的并行計算,分別生成最優(yōu)超平面和成熟檢測器,經過最優(yōu)超平面篩選出正常郵件,將其與成熟檢測器進行匹配,如果能匹配,說明該郵件是最優(yōu)超平面檢測漏報的垃圾郵件;反之,則為正常郵件。最后將這些郵件檢測結果重新反饋到樣本集中,調整生成新的最優(yōu)超平面。循環(huán)上述過程,直至最優(yōu)超平面的分類效果趨于穩(wěn)定,此時得到的最優(yōu)超平面方程則是根據(jù)當前的測試輸入郵件得到的最佳分類選擇。

圖6 自適應性分類器結構框架

3 實驗結果與分析

3.1 實驗設計

本文實驗數(shù)據(jù)集是Ling-Spam,其中包含2 893封電子郵件,分別存儲在10個文件夾中,垃圾郵件總計481封[24]。所有郵件都去除了Html標簽,只剩下主題和正文,內容全是文本類型,無圖片和附件。該數(shù)據(jù)集有4種不同的類型,每種類型的郵件總數(shù)和垃圾郵件數(shù)量一樣,本文選取的是已經進行詞匯還原和停用詞去除的集合,其中選取任意9個文件夾的郵件數(shù)據(jù)作為訓練集,另一個作為測試集。

對實驗數(shù)據(jù)進行分析,隨機抽取文件夾中的垃圾郵件進行抽樣觀察,發(fā)現(xiàn)文件夾1～文件夾9中垃圾郵件樣本的形式大多類似,如圖7所示,這些垃圾郵件常常包含call、percent、profit、www、discount等關鍵詞。

圖7 文件夾1～文件夾9垃圾郵件樣本

文件夾10的垃圾郵件如圖8所示,其比較隱蔽,如正文中很少提到的“商品”和“折扣”等信息,但其會通過將free擴展為freedom、將Web替換為W-e-b等方式來逃避關鍵詞過濾。

圖8 文件夾10垃圾郵件樣本

本文選取的實驗指標包括垃圾郵件召回率、精確率和正常郵件的召回率、精確率以及準確率。最終,本文將文件夾1～文件夾9的垃圾郵件視為舊垃圾郵件,文件夾10的垃圾郵件看成新型垃圾郵件。

3.2 結果分析

本文實驗分為3組,每次選取Ling-Spam數(shù)據(jù)集中的一個文件夾數(shù)據(jù)作為測試集,其他數(shù)據(jù)作為訓練集。第1組用原始的SVM方法測試該數(shù)據(jù)集;第2組用原始的NSA方法測試該數(shù)據(jù)集;第3組用本文自適應性分類模型來進行實驗。每組實驗重復10次,取平均值作為參考依據(jù)。

第1組實驗結果如表1所示,其中第10次實驗以文件夾1～文件夾9的郵件為訓練集,文件夾10的郵件為測試集。

表1 SVM垃圾郵件檢測結果 %

由表1可以看出,在10次實驗中,正常郵件的召回率和精確率普遍較高,基本都在95%以上,這是因為正常郵件的形式比較固定,所以經過樣本訓練出來的檢測模型能較為準確地識別出正常郵件。而第10次實驗數(shù)據(jù)比較異常,其原因是文件夾10中的郵件(如圖8所示的樣例)沒有預先抽取樣本參與到檢測模型的生成中,因此,檢測模型不能很好地模擬新型垃圾郵件的特征,導致在實驗中垃圾郵件的召回率和精確率普遍較低,甚至出現(xiàn)無法識別該類郵件的極端情況。實驗結果還表明,SVM對現(xiàn)有垃圾郵件的識別率較高,但是對新型垃圾郵件的識別率較低。

第2組實驗結果如表2所示。由表2可以看出,NSA檢測正常郵件的精確率不如SVM,而檢測垃圾郵件的精確率普遍較高,平均值達到90%以上。這是因為NSA依靠“自我”來識別“非我”,檢測器能根據(jù)正常樣本集提取出正常郵件的特征,無需記憶垃圾郵件特征,所以即使出現(xiàn)新型垃圾郵件,其也能根據(jù)正常郵件來識別剔除該新型垃圾郵件。

表2 NSA垃圾郵件檢測結果 %

第3組實驗結果如表3所示。由表3可以看出,自適應性分類模型在保證郵件的準確率和正常郵件的召回率、精確率的基礎上,還能有效提高垃圾郵件的召回率和精確率,這也驗證了本文自適應性分類器的高效性,其不僅能保證正常郵件的高識別率,也能高效地檢測出新型垃圾郵件。

表3 自適應性垃圾郵件檢測結果 %

4 結束語

本文設計垃圾郵件自適應性分類器,依據(jù)該分類器建立垃圾郵件的自適應性檢測模型。實驗結果表明,與單一的NSA和SVM算法相比,該方法有效地提高了識別垃圾郵件和正常郵件的精確率、召回率以及準確率。針對日益增多的附件和圖片嵌入等形式的垃圾郵件,下一步將抽象出這些郵件的共性,結合本文針對文本型垃圾郵件的研究,進一步提升垃圾郵件的識別率。

[1] IDRIS I,SELAMAT A,NGUYEN N T,et al.A combined negative selection algorithm-particle swarm optimization for an email spam detection system[J].Engineering Applications of Artificial Intelligence,2015,39(39):33- 44.

[2] BLANZIERI E,BRYL A.A survey of learning-based techniques of email spam filtering[J].Artificial Intelligence Review,2008,29(1):63-92.

[3] HARRIS E.The next step in the spam control war:greylisting[EB/OL].[2017-02-25].http://projects.puremagic.com/greylisting/whitepaper.html.

[4] 譚 營,朱元春.反垃圾電子郵件方法研究進展[J].智能系統(tǒng)學報,2010,5(3):189-201.

[5] SAHAMI M,DUMAIS S,HECKERMAN D,et al.A bayesian approach to filtering junk e-mail[EB/OL].[2017-02-25].https://www.researchgate.net/publication/2788064_A_Bayesian_Approach_to_Filtering_Junk_E-Mail.

[6] CORTES C,VAPNIK V.Support-vector networks[J].Machine Learning,1995,20(3):273-297.

[7] CLARK J,KOPRINSKA I,POON J.A neural network based approach to automated e-mail classification[C]//Proceedings of 2003 IEEE/WIC International Conference on Web Intelligence.Washington D.C.,USA:IEEE Computer Society,2003:702-705.

[8] FORREST S,PERELSON A S,ALLEN L,et al.Self-nonself discrimination in a computer[C]//Proceedings of 1994 IEEE Symposium on Security and Privacy.Washington D.C.,USA:IEEE Computer Society,1994:202-212.

[9] ODA T,WHITE T.Spam detection using an artificial immune system[EB/OL].[2017-02-26].http://terri.zone12.com/doc/academic/crossroads/.

[10] MA W,TRAN D,SHARMA D.A novel spam email detection system based on negative selection[C]//Proceedings of the 4th International Conference on Computer Sciences and Convergence Information Technology.Washington D.C.,USA:IEEE Press,2009:987-992.

[11] MOHAMMAD A H,ZITAR R A.Application of genetic optimized artificial immune system and neural networks in spam detection[J].Applied Soft Computing,2011,11(4):3827-3845.

[12] IDRIS I,SELAMAT A.Email spam detection using differential evolution negative selection algorithm[J].International Journal of Digital Content Technology and Its Applications,2013,7(15):15-20.

[13] TAN Y,RUAN G.Uninterrupted approaches for spam detection based on SVM and AIS[J].International Journal of Computational Intelligence and Pattern Recog-nition,2014,1(1):1-26.

[14] SIRISANYALAK B,SOMIT O.An artificial immunity-based spam detection system[C]//Proceedings of 2007 IEEE Congress on Evolutionary Computation.Washington D.C.,USA:IEEE Press,2007:3392-3398.

[15] SALTON G,BUCKLEY C.Term-weighting approaches in automatic text retrieval[J].Information Processing and Management,1988,24(5):513-523.

[16] SPARCK J K.A statistical interpretation of term specificity and its application in retrieval[J].Journal of Documentation,1972,28(1):11-21.

[17] ZUCHINI M H.Aplica??es de mapas auto-organizaveis em minera??o de dados e recupera??o de informa??o[EB/OL].[2017-02-25].http://viacodigo.com.br/pos/Zuchini,MarcioHenrique.pdf.

[18] BEZERRA G B,BARRA T V,FERREIRA H M.An immunological filter for spam[C]//Proceedings of International Conference on Artificial Immune Systems.Berlin,Germany:Springer,2006:446-458.

[19] DRUCKER H,WU D,VAPNIK V N.Support vector machines for spam categorization[J].IEEE Transactions on Neural Networks,1999,10(5):1048-1054.

[20] JI Z,DASGUPTA D.Revisiting negative selection algori-thms[J].Evolutionary Computation,2007,15(2):223-251.

[21] 金章贊,廖明宏,肖 剛.否定選擇算法綜述[J].通信學報,2013,34(1):159-170.

[22] 劉菊新,徐從富.基于多分類器組合模型的垃圾郵件過濾[J].計算機工程,2010,36(18):194-196.

[23] 王祖輝,姜 維.基于支持向量機的垃圾郵件過濾方法[J].計算機工程,2009,35(13):188-189.

[24] ANDROUTSOPOULOS I,KOUTSIAS J,CHANDRINOS K V,et al.An experimental comparison of naive bayesian and keyword-based anti-spam filtering with personal e-mail messages[C]//Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,2000:160-167.