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

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

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

中圖分類號：TP309.2

文獻標志碼：A

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

0引言

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

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

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

1相關工作

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

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

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

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



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

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

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

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

向量空間算法和樸素貝葉斯算法是在郵件分類算法中實際使用很廣泛的兩種方法，因為它們都容易實現，在不同的方面都體現了不同的獨特性能，所以有關這兩個算法探索的腳步一直沒有停過。

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

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

與上述的想法不同，本文另辟蹊徑，考慮到基于向量空間算法的郵件分類器的優點是分類速度快，在計算單個郵件與一類郵件的相似程度上，向量空間算法比樸素貝葉斯算法有更好的性能，但精度不高?；跇闼刎惾~斯算法的郵件分類器的優點是分類精度高，且能達到比向量空間算法較高的分類精度和較好的魯棒性，但是當詞之間的依賴性較高時，分類器的誤判率也會隨之升高。所以將這兩種算法結合在一起，讓兩者之間各自發揮所長，得到一個經組合后全新的郵件分類算法。

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

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

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

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

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

3實驗及結果

3．1郵件樣本

本文選用CCERT標準中文郵件樣本集對上述算法的性能進行測試。其中，垃圾郵件樣本由CCERT垃圾郵件蜜罐系統所捕獲，正常郵件來自公開的中文論壇。本文共選取1 000封中文郵件樣本（垃圾郵件500封，合法郵件500封）。其中：600封（垃圾郵件與合法郵件各300封）作為訓練集；400封（垃圾郵件與合法郵件各200封）作為測試集。另外，本文不刪除重復的垃圾郵件，因為郵件的重復信息能體現出垃圾郵件的統計行為。

3．2郵件預處理

在郵件預處理過程中，首先去掉出現的非中文漢字和郵件文本中的停用詞，然后建立動態鏈接庫調用已調試好的ICTCLAS源代碼程序對郵件進行分詞處理；對分詞后的郵件，利用TF－IDF法計算每個詞條在郵件向量中的權重，本文只選擇權重排在質心向量前3 000（這是本系統調試的一個較佳數值）的詞條作為訓練集的詞匯列表。這里需要注意的是：算法中是使用質心向量的值來排序從而取出對應的前3 000哈希表的值用來計算，而不是直接用哈希值來排序。這樣做的目的是考慮到質心向量反映了郵件間的整體關聯性，放大了該類郵件的特征，能選取更恰當的詞匯來進行運算，進而提高了貝葉斯算法的分類精度。

3．3實驗方法

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

3．4評價指標[ 8 ]

對中文垃圾郵件過濾方案測評需要定義一些指標，在本文中借鑒了文本分類和信息檢索領域的一些指標。

設測試集中有N封郵件，先定義幾個變量。A：系統判定為SPAM且正確為SPAM;B：系統判定為SPAM且正確為HAM;C：系統判定為HAM且正確為SPAM;D：系統判定為HAM且正確為HAM。可見，N=A+B+C+D。定義如下指標：

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

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

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

如果召回率和精確率均為1，則達到最理想的系統，但是在實際上這是不可能的。從本系統在實際運行中所得到的數據可以看出，本郵件過濾系統取得了較理想的結果。

3．5實驗結果分析

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

4結束語

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

可見，組合算法體現了因地制宜、分而治之的觀點，將整個訓練實例空間劃分成不同的區域，再以每個區域為著手點，選擇適合的算法，這比在整個空間上單一只使用某一種算法要具有更好的分類精度，同時也降低了誤判率，實驗證明了組合算法的可行性。

參考文獻：

[1]黃淑華. 反垃圾電子郵件技術綜述[J].福建商業高等專科學校學報， 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]管建和，鄧剛. 用貝葉斯算法實現垃圾郵件過濾[J]. 網絡與通信，2006(6):53－56.

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

[7]趙志國，譚敏生，李志敏. 基于改進貝葉斯的垃圾郵件過濾算法的綜述[J]. 南華大學學報，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.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文