孔 穎

(浙江科技學(xué)院信息與電子工程學(xué)院,杭州310023)

電子郵件作為一種高效、經(jīng)濟(jì)的現(xiàn)代通信技術(shù)手段,已成為互聯(lián)網(wǎng)最大的應(yīng)用項(xiàng)目之一。然而,隨之產(chǎn)生的垃圾郵件像瘟疫一樣蔓延,污染網(wǎng)絡(luò)環(huán)境,占用大量傳輸、存儲和運(yùn)算資源,影響了網(wǎng)絡(luò)的正常運(yùn)行,嚴(yán)重干擾了人們的正常生活,浪費(fèi)用戶的時間、精力,甚至造成很多額外的經(jīng)濟(jì)支出和信息安全隱患。垃圾郵件的判定和郵件的接收者有很大關(guān)系,不同用戶對同一郵件的判斷結(jié)果可能會存在差異。在《中國互聯(lián)網(wǎng)協(xié)會反垃圾郵件規(guī)范》中,將垃圾郵件定義為具備如下部分或全部特征的電子郵件:

1)收件人事先沒有提出要求或同意接收的廣告、電子刊物、各種形式的宣傳品等宣傳性的電子郵件;

2)收件人無法拒收的電子郵件;

3)隱藏發(fā)件人身份、地址、標(biāo)題等信息的電子郵件;

4)含有虛假的信息源、發(fā)件人、路由等信息的電子郵件;

5)含有病毒、惡意代碼、色情、反動等不良信息或有害信息的電子郵件。

基于內(nèi)容的機(jī)器學(xué)習(xí)判別方法是當(dāng)前解決垃圾郵件問題的主流技術(shù)之一,包括Ripper、決策樹方法、Rough Set方法等基于規(guī)則的方法,和 Bayes、SVM、動態(tài)馬爾可夫建模(Dynamic Markov Modeling,DMM)、Winnow等基于概率統(tǒng)計(jì)的方法[1-2]。這些方法的基本思路是:將垃圾郵件過濾看成一個兩類問題,研究從樣本郵件出發(fā)尋找規(guī)律(或分類器),利用規(guī)律(或分類器)對未知郵件進(jìn)行預(yù)測。隨著人工智能、計(jì)算機(jī)技術(shù)的創(chuàng)新和發(fā)展,這種將機(jī)器學(xué)習(xí)方法應(yīng)用于郵件分類領(lǐng)域一直成為當(dāng)前研究的熱點(diǎn)和重點(diǎn)。

本文在簡要介紹基于HTML的卡方特征提取算法的基礎(chǔ)上,將卡方特征提取和HTML標(biāo)簽相結(jié)合,通過神經(jīng)網(wǎng)絡(luò)建立模型,對郵件進(jìn)行預(yù)測,得到了較好的實(shí)驗(yàn)結(jié)果。

1 郵件特征提取

1.1 HTML標(biāo)簽分類

首先需要將收集到的郵件轉(zhuǎn)換為H TML形式,這樣可以將郵件特征使用標(biāo)簽來表示。由圖1可以看到一封瀏覽器接收到的郵件示例。

將圖1所示的郵件轉(zhuǎn)換為HTML格式,由于文本文件的通用性,所有的郵件均可轉(zhuǎn)換為HTML代碼。而HTML為各類標(biāo)簽所組成,對于不同的標(biāo)簽而言,其所代表的含義各不相同,當(dāng)然,處于標(biāo)簽中的內(nèi)容所代表的含義也不同,表1大致給出了基本標(biāo)簽所代表的含義。

圖1 郵件示例圖Fig.1 An example of an e-mail

表1 基本標(biāo)簽含義表Table 1 Meanings of basic tags

當(dāng)然,標(biāo)簽中許多都是用于格式控制的,對于文本內(nèi)容沒有任何影響,不會使文本特征丟失。將郵件轉(zhuǎn)換格式后為了便于進(jìn)一步進(jìn)行特征提取,需要對某些細(xì)節(jié)進(jìn)行一些處理,其中主要的方式為:去除含有圖片的標(biāo)簽;去除超鏈接的標(biāo)簽;不考慮標(biāo)簽中與附件有關(guān)的內(nèi)容;將特殊符號轉(zhuǎn)化為特殊的標(biāo)簽。

完成了細(xì)節(jié)處理后,需要對各種標(biāo)簽進(jìn)行分類,以便于對不同標(biāo)簽內(nèi)的內(nèi)容賦予不同的權(quán)值,達(dá)到最終的特征提取目的。根據(jù)HTML語言的特點(diǎn),在標(biāo)簽分類時使用如表2所示的方式。

特征提取將標(biāo)簽中最為相關(guān)的特征集中在一個數(shù)據(jù)集中,考慮到整個數(shù)據(jù)集包含所有郵件的特征,如郵件中的單詞、圖片和它們在預(yù)處理時所產(chǎn)生的標(biāo)簽等[3]。由于特征提取廣泛用于文本的分類,通常這些分類方法也可以用于處理垃圾郵件,在本實(shí)驗(yàn)中采用了2種提取法:TF-IDF算法和卡方分布算法。

1.2 卡方特征提取

卡方分布處理的是某個特征的度與整個數(shù)據(jù)集之間的關(guān)系[4]。如w是數(shù)據(jù)集C(由兩部分構(gòu)成)中的一個特征,則w的卡方值可用式(1)給出

式(1)中P(spam)和P(ham)分別表示垃圾郵件和正常郵件在數(shù)據(jù)集中出現(xiàn)的概率,這樣就可以給出特征w在整個數(shù)據(jù)集中的卡方分布,如式(2)所示:

式(2)中:k為正常郵件數(shù)據(jù)集中包含特征w的郵件數(shù)量;l為垃圾郵件中包含特征w的郵件數(shù)量;m為正常郵件數(shù)據(jù)集中不包含特征w的郵件數(shù)量;n為垃圾郵件數(shù)據(jù)集中不包含特征w的郵件數(shù)量;N為正常郵件數(shù)據(jù)集中所有郵件的數(shù)量。同樣的,所有的特征的卡方值均取其最高值,最終這些值均作為神經(jīng)網(wǎng)絡(luò)中的一個節(jié)點(diǎn)。

1.3 TF-IDF加權(quán)算法

目前加權(quán)使用最廣泛的算法 ——TF-IDF加權(quán)算法[5-6]:

式(3)中,W(t,d)為特征項(xiàng)t在郵件d中的權(quán)重;tf(t,d)為特征項(xiàng)t在郵件內(nèi)容中的詞頻;N為訓(xùn)練文本的總數(shù);nt為訓(xùn)練郵件集中出現(xiàn)特征項(xiàng)t的郵件數(shù)。用TF-IDF算法來計(jì)算特征詞的權(quán)重值是表示當(dāng)一個詞在這篇郵件中出現(xiàn)的頻率越高,同時在其他文檔中出現(xiàn)的次數(shù)越少,則表明該詞對于表示這篇文檔的區(qū)分能力越強(qiáng),所以其權(quán)重值就應(yīng)該越大[7]。將所有詞的權(quán)值排序,根據(jù)需要選擇特征項(xiàng)。

為消除文檔長度不一對文本表示方式的可能影響,往往需要對加權(quán)后的向量進(jìn)行規(guī)范化處理,使得權(quán)值落在[0,1]中。即:

表2 標(biāo)簽相關(guān)特征Table 2 Characteristics of tags

1.4 基于LVQ神經(jīng)網(wǎng)絡(luò)的郵件分類器設(shè)計(jì)

LVQ神經(jīng)網(wǎng)絡(luò)是一類混合神經(jīng)網(wǎng)絡(luò),它分為有人值守和無人值守[7]。本實(shí)驗(yàn)中將模型分為兩層,第一層是競爭層,該層中每個節(jié)點(diǎn)表示一個子集;而第二層為輸出層,每一個節(jié)點(diǎn)均為一個集。每個集可以劃分為若干個子集。由于LVQ神經(jīng)網(wǎng)絡(luò)可以通過結(jié)合不同的子集創(chuàng)造復(fù)雜的界限,故適合于將垃圾郵件從若干不同的子集中分辨出來。以下為篩選算法:

1)初始化向量權(quán)重W={W1,W2,…,Wn},學(xué)習(xí)率α∈[0,1]。

2)從訓(xùn)練郵件集中選取一個示例,計(jì)算它各個向量之間的距離,分別取歐幾里德距離和余弦距離,這些可以表示不同文本之間的相似性[8]。其中余弦距離可用式(5)表示:

3)比較不同權(quán)向量之間的距離,在結(jié)果中,神經(jīng)元之間最為相似的取值1,其余隱藏層的輸出層取值0。

4)調(diào)整距離,如果一個輸入示例屬于數(shù)據(jù)集r,那么在數(shù)據(jù)集s中神經(jīng)元c擁有最大的權(quán)值,然后根據(jù)式(7)調(diào)整各個權(quán)值:

5)修改學(xué)習(xí)率U(t),當(dāng)重復(fù)增加時降低U(t)。

6)檢查停止?fàn)顩r,并確認(rèn)重復(fù)的次數(shù)足夠多。

使用上述方法提取特征之后代入LVQ神經(jīng)網(wǎng)絡(luò)進(jìn)行計(jì)算,使用MATLAB可以模擬出如圖2的LVQ神經(jīng)網(wǎng)絡(luò)。

1.5 過濾原理

郵件預(yù)處理是建立在訓(xùn)練模型的基礎(chǔ)上的,因?yàn)橛肔VQ神經(jīng)網(wǎng)絡(luò)建立的模型是建立在許多學(xué)習(xí)樣本郵件基礎(chǔ)上的,需要巨大的計(jì)算資源。因此,用于建模的郵件如何進(jìn)行預(yù)處理十分關(guān)鍵。

圖2 LVQ神經(jīng)網(wǎng)絡(luò)Fig.2 LVQ neural network

在特征提取過程中,通過把普通的郵件轉(zhuǎn)化成HTML標(biāo)簽形式,減少分類過程中產(chǎn)生的特征向量數(shù),把每個特征所出現(xiàn)的概率用到卡方算法中,最后再通過LVQ神經(jīng)網(wǎng)絡(luò)建立模型,進(jìn)行郵件分類。電子郵件過濾模型如圖3所示。

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

評價一個解決分類問題的模型是否適用的一個直接手段就是看它的錯分率,即錯誤分類數(shù)與總記錄數(shù)的比值。所示必須測量用來建立模型和在建立模型過程中沒有用到的記錄組成的測試樣本,選擇最具有普遍意義的而不是最適合訓(xùn)練樣本的模型。

考慮N封待測試郵件(Ns封垃圾郵件和N b封垃圾郵件,N=Ns+Nb),在算法郵件分類模型中,垃圾郵件被分類器正確判定的有A封,誤判的有B封;正常郵件被分類器正確判定的有C封,誤判的有D封,顯然Ns=A+B,Nb=C+D。根據(jù)定義,有下列各式成立:

圖3 電子郵件過濾模型Fig.3 Filtering model of an e-mail

垃圾郵件過濾應(yīng)用模型采用ham%、spam%和Accuracy等傳統(tǒng)分類指標(biāo),來分析特征提取和特征值計(jì)算方法、訓(xùn)練模型的選擇對郵件分類模型的影響。

本次實(shí)驗(yàn)使用的是SEWM2008比賽中的數(shù)據(jù)集作為評測數(shù)據(jù)集郵件樣本。抽取樣本中的4 000封,其中正常郵件有3 120封,垃圾郵件有880封。分別用基于HTML的卡方和TF-IDF兩種不同的特征提取方法,把得到的郵件特征向量通過LVQ神經(jīng)網(wǎng)絡(luò)模型進(jìn)行過濾,從而得到的實(shí)驗(yàn)結(jié)果,如表3所示。

表3 各實(shí)驗(yàn)結(jié)果比較Table 3 Comparison of experimental results

從表3實(shí)驗(yàn)結(jié)果的比較可以看出,在數(shù)據(jù)集足夠大時,采用LVQ神經(jīng)網(wǎng)絡(luò)的分類器對于不同方法提取的數(shù)據(jù)集均有較好的結(jié)果,其中采用卡方分布法提取的數(shù)據(jù)集在處理結(jié)果方面略微優(yōu)于傳統(tǒng)的TFIDF提取的數(shù)據(jù)集。實(shí)驗(yàn)還表明,不管是正常郵件分類、垃圾郵件分類還是整體分類,都具有較高的準(zhǔn)確率。

3 結(jié) 語

從基于HTML的卡方特征提取方法和LVQ神經(jīng)網(wǎng)絡(luò)分類器結(jié)果可以看出,該模型是一種較好的垃圾郵件處理系統(tǒng)。通過轉(zhuǎn)換郵件文本為HTML代碼,便于處理其中內(nèi)容,而使用LVQ神經(jīng)網(wǎng)絡(luò)的分類器,在數(shù)據(jù)集足夠大時所得結(jié)果往往優(yōu)于同等情況下的其他分類器,這在實(shí)際應(yīng)用時具有一定的參考價值。

[1] YIH W T,MCCANN R,KOLCZ A.Improving spam filtering by detecting gray mail[C]//Fourth Conference on Email and Anti-Sparn.Mountain View,CA:CEAS,2007.

[2] CLEARY J G,WRITTEN I H.Data compressing using adaptive coding and partial string matching[J].IEEE Transaction on Communications,1984,32(4):396-402.

[3] ZEITOUN I K,YEH L.Join indices as atool for spatial datamining[C]//International Workshop on Temporal,Spatial and Spatio-Temporal Data Mining,Lecture Notes in Artificial Intelligence.Paris:Springer Press,2007:102-114.

[4] 劉洋,杜孝平,羅平,等.垃圾郵件的智能分析、過濾及Rough集討論[R].武漢:第十二屆中國計(jì)算機(jī)學(xué)會網(wǎng)絡(luò)與數(shù)據(jù)通信學(xué)術(shù)會議,2002.

[5] 王斌,潘文鋒.基于內(nèi)容的垃圾郵件過濾技術(shù)綜述[J].中文信息學(xué)報(bào),2005,19(5):1-10.

[6] 程紅蓉,秦志光,萬明成,等.圖像垃圾郵件中文本區(qū)域的自動提取方法[J].解放軍理工大學(xué)學(xué)報(bào):自然科學(xué)版,2009,10(3):258-261.

[7] 王龍,李曉光,鐘紹春.基于K-近鄰法及移動AGENT技術(shù)的垃圾郵件檢測系統(tǒng)研究[J].計(jì)算機(jī)應(yīng)用研究,2009,26(7):2630-2632.

[8] 萬明成,耿技,程紅蓉,等.圖像型垃圾郵件過濾技術(shù)綜述[J].計(jì)算機(jī)應(yīng)用研究,2008,25(9):2579-2582.