基于組合算法的中文反垃圾郵件分類系統(tǒng)的研究

摘要：論述了一種采用組合算法實(shí)現(xiàn)的垃圾郵件分類系統(tǒng)，并在Windows平臺(tái)下用Visual Basic 6.0實(shí)現(xiàn)。本系統(tǒng)工作在郵件客戶端，基于郵件內(nèi)容的解析，相對(duì)于只使用基于分類器的垃圾郵件分類系統(tǒng)，不僅能有效快速地分類郵件，同時(shí)提高了分類的精度、降低誤判率。

關(guān)鍵詞：垃圾郵件； 向量空間算法； 貝葉斯算法； 組合算法

中圖分類號(hào)：TP309.2

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)06－1825－03

0引言

目前，隨著互聯(lián)網(wǎng)在全球的普及和應(yīng)用的不斷發(fā)展，電子郵件系統(tǒng)已經(jīng)成為人們最常用的通信手段之一。然而，近年來大量垃圾郵件的泛濫，違背了早期設(shè)計(jì)郵件系統(tǒng)的初衷，令互聯(lián)網(wǎng)用戶措手不及，嚴(yán)重影響了用戶使用郵箱的效率。各種種類的垃圾郵件的存在，在不同程度上對(duì)用戶和網(wǎng)絡(luò)環(huán)境造成了負(fù)面影響，目前這一問題已經(jīng)引起了全球范圍內(nèi)的熱切關(guān)注。據(jù)統(tǒng)計(jì)，2001年垃圾郵件僅占電子郵件總量的7%，2002年即達(dá)到29%至2003年7月就超過了51%， 2004年1月高達(dá)60%。2005年7月，中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC)發(fā)布的《第十六次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示，我國(guó)網(wǎng)民平均每周收到14.5封電子郵件。其中：正常電子郵件為5.2封；垃圾郵件卻達(dá)到9.3封。網(wǎng)民每周收到的垃圾郵件數(shù)是非垃圾郵件數(shù)的近兩倍!據(jù)Spamhaus數(shù)據(jù)顯示，截止到2006年11月17日，中國(guó)位居第二是垃圾郵件最多的國(guó)家，已發(fā)現(xiàn)的垃圾郵件形式為305種。因此，在我國(guó)如何全面防范垃圾郵件已成為互聯(lián)網(wǎng)的重點(diǎn)研究課題，具有廣泛的實(shí)際應(yīng)用價(jià)值。

近年來，有關(guān)反垃圾郵件技術(shù)的研究開始逐步興起，相關(guān)的投入也越來越大。目前為止，常用的解決垃圾郵件的方法有[1]：反向域名驗(yàn)證、黑白名單、關(guān)鍵詞過濾、基于規(guī)則方法的過濾和基于統(tǒng)計(jì)的過濾等。

在所有反垃圾郵件技術(shù)中，基于向量空間算法的垃圾郵件分類器具有簡(jiǎn)單、快速的特點(diǎn)，但是它的查全率和查準(zhǔn)率都相對(duì)差一點(diǎn)[2]；基于樸素貝葉斯算法的垃圾郵件分類器是最常用的一種方法，它具有分類算法容易理解，分類精度高的等優(yōu)點(diǎn)，所以在實(shí)際運(yùn)用中都顯示了良好的穩(wěn)定性和精確度[3]。但是，由于樸素貝葉斯算法中假定不同的詞在郵件中的出現(xiàn)是相互獨(dú)立的，此假定在實(shí)際的郵件中是不成立的，詞之間的相互依賴將導(dǎo)致樸素貝葉斯算法作出不恰當(dāng)?shù)墓烙?jì)，使得判斷郵件是否屬于某類郵件出現(xiàn)錯(cuò)誤。郵件分類器的最終目的是不僅要分類速度夠快，還要分類精度夠高并盡可能地將誤判率降到最低。為了實(shí)現(xiàn)這個(gè)想法，本文組合了向量空間分類算法和貝葉斯分類算法的優(yōu)點(diǎn)，提出了經(jīng)過組合后的新算法，目標(biāo)是對(duì)于發(fā)來的一封新郵件，根據(jù)新郵件與訓(xùn)練集中合法郵件集的質(zhì)心和垃圾郵件集的質(zhì)心相似度來判定使用具體的分類算法。從而利用較少的時(shí)間獲得較好的分類效果。

1相關(guān)工作

1．1基于向量空間分類算法的郵件分類

基于向量空間分類郵件算法的基本思想是[4]：用同一類電子郵件的質(zhì)心代表它們的共同特征，需要被分類的郵件與質(zhì)心比較，如果該郵件與質(zhì)心的相似程度滿足分類要求，則該郵件就可以被劃分成質(zhì)心所代表的這一類電子郵件。在向量空間算法中，每封郵件由空間向量模型表示，即用token（可以理解為字或詞，但不僅限于字或詞）出現(xiàn)頻率表示的向量：mi=(wi1，wi2，…，win )。其中：mi表示第i封郵件；n表示郵件空間的維數(shù)；wij表示每一個(gè)token的權(quán)重，它代表了該token相對(duì)于郵件來說的重要程度。表示token權(quán)重的方法有[5]TF－IDF、詞頻、互信息、信息熵等。本文采用TF－IDF的方法。

質(zhì)心向量C可以看做是具有某種特征的一組向量的平均值，在郵件分類中，它用來表示郵件集合{m}的共同特征。設(shè)整個(gè)訓(xùn)練集的郵件數(shù)為N封，則訓(xùn)練階段的時(shí)間復(fù)雜度為O(N)。

一封新郵件通過比較與垃圾郵件集和合法郵件集的質(zhì)心向量的相似度，就可以把它劃分到最相似的質(zhì)心向量所代表的郵件類中。在分類階段，對(duì)于每一封待分類的郵件，由于要計(jì)算兩個(gè)相似度的值，時(shí)間復(fù)雜度為O(2)。可見，基于向量空間法的郵件分類是十分快速的。其在分類階段基于向量空間法的郵件分類算法如下：



1．2基于樸素貝葉斯分類算法的郵件分類

樸素貝葉斯分類算法是目前在郵件分類中廣泛使用的一種方法，其主要思想是[5]：

給定一個(gè)訓(xùn)練集（由垃圾郵件集Cs和合法郵件集組成Ch），算法首先通過計(jì)算垃圾郵件和合法郵件在訓(xùn)練數(shù)據(jù)中發(fā)生的次數(shù)來估計(jì)每個(gè)類別的先驗(yàn)概率P(Cs)和P(Ch)。對(duì)于每封郵件獨(dú)立的token串{t1，t2，…，tn}，根據(jù)它發(fā)生的次數(shù)可以計(jì)算P(ti)。類似地，通過計(jì)算在訓(xùn)練數(shù)據(jù)中每個(gè)token串在垃圾郵件和合法郵件中發(fā)生的次數(shù)可以估計(jì)概率P(xi/Cs)和P(xi/Ch)。當(dāng)一封郵件需要被分類時(shí)，則使用這些導(dǎo)出的概率值對(duì)其進(jìn)行預(yù)測(cè)分類。在這里假設(shè)所有的token串所起的作用是獨(dú)立的，并且對(duì)于分類問題每個(gè)token串所起的作用是相等的。由于垃圾郵件的標(biāo)題和正文的各個(gè)詞語之間的依賴性在絕大多數(shù)場(chǎng)合下都非常弱，可以采用樸素貝葉斯分類器作為垃圾郵件的分類方法是可取的。

貝葉斯定理就是通過對(duì)某一事件過去發(fā)生的概率情況的考察，大致可以推斷出當(dāng)前這一事件發(fā)生的概率。貝葉斯定理是基于貝葉斯算法郵件分類的基石。在訓(xùn)練階段，對(duì)已知的垃圾郵件集合和合法郵件集合樣本進(jìn)行分析，建立兩張哈希表spam－h(huán)ash和ham－h(huán)ash，把一封郵件中的token作為哈希表的key，它出現(xiàn)的次數(shù)作為哈希表的value。最后利用這兩張哈希表來建立第三張哈希表probability－h(huán)ash。計(jì)算方法是：設(shè)

向量空間算法和樸素貝葉斯算法是在郵件分類算法中實(shí)際使用很廣泛的兩種方法，因?yàn)樗鼈兌既菀讓?shí)現(xiàn)，在不同的方面都體現(xiàn)了不同的獨(dú)特性能，所以有關(guān)這兩個(gè)算法探索的腳步一直沒有停過。

對(duì)于向量空間算法的主要工作集中在對(duì)郵件token串權(quán)重的選擇和抽取方面的改進(jìn)，來提高算法的性能。例如由武漢大學(xué)的張滬寅、吳產(chǎn)樂、邢建兵[6]設(shè)計(jì)的基于內(nèi)容分析的電子郵件過濾模型，就是通過token串對(duì)郵件文本內(nèi)容過濾上作了改進(jìn)，取得了良好的性能。

對(duì)于樸素貝葉斯算法的主要工作集中在對(duì)放松變量獨(dú)立假設(shè)這一限制方面的改進(jìn)來提高郵件分類的性能。產(chǎn)生了樸素貝葉斯算法的幾個(gè)變種[7]：TAN是一種樹狀貝葉斯網(wǎng)絡(luò)，它放松了樸素貝葉斯算法中的獨(dú)立假設(shè)條件，擴(kuò)展了樸素貝葉斯的結(jié)構(gòu)。TAN允許除了類別變量外，其他變量具有樹結(jié)構(gòu)。這樣，就允許分類變量間存在依賴關(guān)系，即每個(gè)分類變量最多可以依賴于另外一個(gè)分類變量。BAN對(duì)樸素貝葉斯作了進(jìn)一步擴(kuò)展，它允許分類變量間形成任意的有向圖，能表示依賴關(guān)系的增強(qiáng)。GBN進(jìn)一步擴(kuò)展了BAN。在GBN中類別變量節(jié)點(diǎn)被認(rèn)為是一個(gè)普通的節(jié)點(diǎn)，可以存在不以類別變量為父節(jié)點(diǎn)的節(jié)點(diǎn)。經(jīng)改進(jìn)的貝葉斯算法都比樸素貝葉斯算法具有較好的綜合性能，在小幅度犧牲了效率的情況下明顯改進(jìn)了分類精度。

與上述的想法不同，本文另辟蹊徑，考慮到基于向量空間算法的郵件分類器的優(yōu)點(diǎn)是分類速度快，在計(jì)算單個(gè)郵件與一類郵件的相似程度上，向量空間算法比樸素貝葉斯算法有更好的性能，但精度不高。基于樸素貝葉斯算法的郵件分類器的優(yōu)點(diǎn)是分類精度高，且能達(dá)到比向量空間算法較高的分類精度和較好的魯棒性，但是當(dāng)詞之間的依賴性較高時(shí)，分類器的誤判率也會(huì)隨之升高。所以將這兩種算法結(jié)合在一起，讓兩者之間各自發(fā)揮所長(zhǎng)，得到一個(gè)經(jīng)組合后全新的郵件分類算法。

2向量空間和樸素貝葉斯的組合算法（hybrid of VSMand Bayesian）

基于向量空間算法的郵件分類速度快，但是有一個(gè)缺點(diǎn)：有一種郵件，在遇到一種與合法郵件的質(zhì)心（或垃圾郵件的質(zhì)心）很相似，實(shí)際上卻屬于垃圾郵件（或合法郵件）的郵件時(shí)，向量空間法往往返回錯(cuò)誤的結(jié)果；而樸素貝葉斯算法則考慮郵件整體概率情況判斷其類別，與質(zhì)心相似度無關(guān)，所以最后可以得到較好的分類結(jié)果。但是這是在忽略分類屬性相關(guān)性的前提下可以達(dá)到的效果，一旦分類屬性的依賴性較大時(shí)，基于樸素貝葉斯算法的郵件分類器的分類精度就會(huì)下降。

根據(jù)上述的想法，可以構(gòu)造在不同的情況下使用不同算法的反垃圾郵件分類器。經(jīng)組合后的新算法，既可以保持分類速度快的優(yōu)點(diǎn)，又具有較高的精確度和較低的誤判率。

這樣就可以將已知的郵件樣本空間劃分成三個(gè)區(qū)域，即合法郵件球和垃圾郵件球以及剩下的區(qū)域。

對(duì)于一封新郵件，首先判定它在樣本空間中所處的位置，如果在兩球區(qū)域里就可以直接使用向量空間法判斷其類別，由于合法郵件實(shí)際上非常重要，不希望把合法郵件錯(cuò)誤地劃分成垃圾郵件。因此VSM制定的分類規(guī)則要使得合法郵件被劃分成垃圾郵件的概率盡可能小，則分類規(guī)則為:若新郵件m落入Ballh中時(shí)，則m直接被判定為合法郵件；若新郵件m落入Balls中時(shí)，滿足條件sim(m， Cs)>K的郵件劃分為垃圾郵件，其中臨界值K為

3實(shí)驗(yàn)及結(jié)果

3．1郵件樣本

本文選用CCERT標(biāo)準(zhǔn)中文郵件樣本集對(duì)上述算法的性能進(jìn)行測(cè)試。其中，垃圾郵件樣本由CCERT垃圾郵件蜜罐系統(tǒng)所捕獲，正常郵件來自公開的中文論壇。本文共選取1 000封中文郵件樣本（垃圾郵件500封，合法郵件500封）。其中：600封（垃圾郵件與合法郵件各300封）作為訓(xùn)練集；400封（垃圾郵件與合法郵件各200封）作為測(cè)試集。另外，本文不刪除重復(fù)的垃圾郵件，因?yàn)猷]件的重復(fù)信息能體現(xiàn)出垃圾郵件的統(tǒng)計(jì)行為。

3．2郵件預(yù)處理

在郵件預(yù)處理過程中，首先去掉出現(xiàn)的非中文漢字和郵件文本中的停用詞，然后建立動(dòng)態(tài)鏈接庫調(diào)用已調(diào)試好的ICTCLAS源代碼程序?qū)︵]件進(jìn)行分詞處理；對(duì)分詞后的郵件，利用TF－IDF法計(jì)算每個(gè)詞條在郵件向量中的權(quán)重，本文只選擇權(quán)重排在質(zhì)心向量前3 000（這是本系統(tǒng)調(diào)試的一個(gè)較佳數(shù)值）的詞條作為訓(xùn)練集的詞匯列表。這里需要注意的是：算法中是使用質(zhì)心向量的值來排序從而取出對(duì)應(yīng)的前3 000哈希表的值用來計(jì)算，而不是直接用哈希值來排序。這樣做的目的是考慮到質(zhì)心向量反映了郵件間的整體關(guān)聯(lián)性，放大了該類郵件的特征，能選取更恰當(dāng)?shù)脑~匯來進(jìn)行運(yùn)算，進(jìn)而提高了貝葉斯算法的分類精度。

3．3實(shí)驗(yàn)方法

本文在上述的郵件測(cè)試集上比較向量空間法(VSM)，貝葉斯算法（Bayesian）和組合算法(hybrid)的性能。

3．4評(píng)價(jià)指標(biāo)[ 8 ]

對(duì)中文垃圾郵件過濾方案測(cè)評(píng)需要定義一些指標(biāo)，在本文中借鑒了文本分類和信息檢索領(lǐng)域的一些指標(biāo)。

設(shè)測(cè)試集中有N封郵件，先定義幾個(gè)變量。A：系統(tǒng)判定為SPAM且正確為SPAM;B：系統(tǒng)判定為SPAM且正確為HAM;C：系統(tǒng)判定為HAM且正確為SPAM;D：系統(tǒng)判定為HAM且正確為HAM。可見，N=A+B+C+D。定義如下指標(biāo)：

a)回率（recall）。recall=A/A+C×100℅，即垃圾郵件檢出率。

b)精確率(accuracy)。accuracy=A+D/N×100℅，即對(duì)所有郵件的判對(duì)率。

c)誤判率(error)。error=B+C/N×100℅=1-accuracy。

如果召回率和精確率均為1，則達(dá)到最理想的系統(tǒng)，但是在實(shí)際上這是不可能的。從本系統(tǒng)在實(shí)際運(yùn)行中所得到的數(shù)據(jù)可以看出，本郵件過濾系統(tǒng)取得了較理想的結(jié)果。

3．5實(shí)驗(yàn)結(jié)果分析

表1給出了三個(gè)算法在兩個(gè)數(shù)據(jù)集上的測(cè)試結(jié)果。從表1中可以看出組合算法的分類效果明顯優(yōu)于向量空間法，比貝葉斯算法的分類效果略高出1~2個(gè)百分點(diǎn)；同時(shí)組合后的算法的時(shí)間復(fù)雜度為O（N），這說明組合算法在較少的時(shí)間損耗下，獲得了很好的分類效果，這與先前的設(shè)想是完全一致的。

4結(jié)束語

本文通過結(jié)合向量空間法和樸素貝葉斯算法的長(zhǎng)處，提出了一種新的組合算法(hybrid of VSM and Bayesian)。分析和實(shí)驗(yàn)表明，新算法在較少的時(shí)間損耗下，達(dá)到了與貝葉斯算法相似甚至更好的分類效果，在一定程度上彌補(bǔ)了兩種算法的不足，盡可能地發(fā)揮各自的優(yōu)勢(shì)。與單使用向量空間算法相比較，組合算法是在向量空間算法的基礎(chǔ)上，對(duì)于那些處在類交界處的屬于不同類的郵件很容易產(chǎn)生錯(cuò)誤的區(qū)域，利用樸素貝葉斯的精確性進(jìn)行劃分，從而可以使分類結(jié)果更加準(zhǔn)確。與單使用樸素貝葉斯方法相比，組合算法是在向量空間算法的基礎(chǔ)上，只取出其中的一個(gè)區(qū)域的郵件運(yùn)用樸素貝葉斯算法，而不是將所有的郵件全部運(yùn)用樸素貝葉斯算法，這樣可以在一定程度上減少計(jì)算量，從而可以節(jié)省一定的時(shí)間。另外，組合算法縮小了運(yùn)用樸素貝葉斯算法范圍，限制了條件獨(dú)立性的范圍，這在一定程度上克服了由于樸素貝葉斯的條件獨(dú)立性而帶來的負(fù)面效應(yīng)，使分類的準(zhǔn)確性更高。

可見，組合算法體現(xiàn)了因地制宜、分而治之的觀點(diǎn)，將整個(gè)訓(xùn)練實(shí)例空間劃分成不同的區(qū)域，再以每個(gè)區(qū)域?yàn)橹贮c(diǎn)，選擇適合的算法，這比在整個(gè)空間上單一只使用某一種算法要具有更好的分類精度，同時(shí)也降低了誤判率，實(shí)驗(yàn)證明了組合算法的可行性。

參考文獻(xiàn)：

[1]黃淑華. 反垃圾電子郵件技術(shù)綜述[J].福建商業(yè)高等專科學(xué)校學(xué)報(bào)， 2006， 4(2):37－40.

[2]DUMAIS S T， PLATT J，HECKERMAN D， et al. Inductive learning algorithms and representations for text categorization[C] //Proc of Pmc ACMa－Conf Information and Knowledge Management. 1998:148－ 155.

[3]LANGLEY P， IBA W， THOMPSON K. An analysis of Bayesian classifiers[C] //Proc of the 10th National Conference on Artificial Intelligence. Menlo Park:AAAI Press， 1992:223－228.

[4]HAN E H， KARYPIS G. Centroid－based document classification algorithms:analysis experimental results， Technical Report TR－00－017. Minneapolis: Department of Computer Science，University of Minnesota， 2000.

[5]管建和，鄧剛. 用貝葉斯算法實(shí)現(xiàn)垃圾郵件過濾[J]. 網(wǎng)絡(luò)與通信，2006(6):53－56.

[6]張滬寅，吳產(chǎn)樂，邢建兵. 基于內(nèi)容分析的電子郵件過濾模型的設(shè)計(jì)[J]. 計(jì)算機(jī)工程， 2005， 8(15):39－41.

[7]趙志國(guó)，譚敏生，李志敏. 基于改進(jìn)貝葉斯的垃圾郵件過濾算法的綜述[J]. 南華大學(xué)學(xué)報(bào)，2006， 3(1):33－37.

[8]ANDROUTSOPOULOS I， KOUTSIAS J， CHANDRINOS K V， et al.An evaluation of nave Bayesian anti－spam filtering[C] //Proc of the 11th Workshop on Machine Learning in the New Information Age， European Conference on Machine Learning. 2000:9－17.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文