一種基于貝葉斯的垃圾郵件過濾系統(tǒng).doc

精品論文推薦一種基于貝葉斯的垃圾郵件過濾系統(tǒng)裘敬功，張闖，肖波，藺志青 北京郵電大學信息與通信工程學院，北京 (100876) e-mail: 摘要：本文提出了一種基于貝葉斯的智能垃圾郵件過濾系統(tǒng)的設計與實現(xiàn)方案。首先，基于貝葉斯的智能垃圾郵件過濾系統(tǒng)會通過訓練一定數(shù)量的樣本郵件，來提取區(qū)分度高的特征 值；然后對新郵件進行向量化，并利用貝葉斯公式結合訓練結果對新郵件進行評分；最后，通過設定的閾值來判斷該郵件是否屬于垃圾郵件。 關鍵詞：垃圾郵件；貝葉斯理論；分類器 中圖分類號：tp3111.引言電子郵件在 internet 中的廣泛應用極大地滿足了大量存在的人與人通信的需求，也使人 們的交流方式得到了極大的改變。但是隨之而來的垃圾郵件也越來越泛濫，占用了有限的存 儲、計算和網(wǎng)絡資源，耗費了用戶大量的處理時間，影響和干擾了用戶的正常工作，生活和 學習。垃圾郵件可以說是因特網(wǎng)帶給人類最具爭議性的副產(chǎn)品，它的泛濫已經(jīng)使整個因特網(wǎng) 不堪重負。當前一些技術已經(jīng)應用到反垃圾郵件系統(tǒng)中，如基于驗證查詢的技術（包括 dns 反向 查詢、mx 查詢、dkim 技術和 sendid 技術等），基于密碼術的技術(包括 amtp、mtp、 s/mime 等)、基于挑戰(zhàn)的技術（包括挑戰(zhàn)-響應方式和計算性挑戰(zhàn)等）以及基本的垃圾郵件 過濾技術。過濾是反垃圾郵件的一種重要的方法，也是應用范圍最廣的技術。過濾技術實現(xiàn) 起來相對簡單，并且主要用于接收系統(tǒng)來辨別和處理垃圾郵件，比如很多郵件服務器上的反 垃圾郵件插件、反垃圾郵件網(wǎng)關、客戶端上的反垃圾郵件功能等，都是采用的過濾技術?？傮w來說，目前的過濾技術從過濾的依據(jù)來分，可以分為基于 ip 地址過濾、基于信頭 的過濾和基于內(nèi)容的過濾三種。對于從自身服務器發(fā)出的垃圾郵件可以采取 ip 地址過濾的 方法。這種方法通過維護一個發(fā)送或轉(zhuǎn)發(fā)垃圾郵件的 ip 數(shù)據(jù)庫進行垃圾郵件過濾，可以用 于那些長期轉(zhuǎn)發(fā)垃圾郵件的服務器。這種方法的優(yōu)點是有效便捷，但缺點同樣很明顯，從該 ip 地址發(fā)出的正常郵件也將被過濾掉。基于信頭的過濾技術根據(jù)信頭中的某些域來進行過 濾，如發(fā)送或轉(zhuǎn)發(fā)的郵件地址。常用的過濾方法是基于內(nèi)容過濾，通過對郵件內(nèi)容的識別， 來判斷郵件是垃圾郵件還非垃圾郵件?；趦?nèi)容的過濾方法結合人工智能、概率論等方法對 郵件進行判別，有著較高的識別率，有著廣泛的應用。在基于內(nèi)容的過濾方法中，貝葉斯過 濾方法訓練以及分類的速度較快，而且從本質(zhì)上講是基于統(tǒng)計信息的，有著很高的識別率， 因此本系統(tǒng)采用基于貝葉斯的思想對垃圾郵件進行過濾處理。2. 貝葉斯決策理論2.1 貝葉斯公式貝葉斯決策理論的基礎是貝葉斯公式，貝葉斯公式定義如下：若 b1 , b2 是一系列u互不相容的事件，且bi = ，且 p(bi ) 0 ，i=1,2， 則對任一事件 a 有:i =1- 7 -p(bi | a) =p(bi )p( a | bi ) p( a | bi )p(bi )i =1i=1,2， 貝葉斯公式又稱逆概率公式，反映的是由已知事件的先驗概率來獲得事件發(fā)生的后驗概 率。先驗概率指的是事件發(fā)生的概率，即事件沒有發(fā)生，求事件發(fā)生的可能性大小。而后驗 概率則是指事件發(fā)生之后，這件事件發(fā)生的原因是由某個原因引起的可能性的大小，是一種 條件概率。但條件概率卻不一定是后驗概率。后驗概率是由先驗概率通過貝葉斯公式計算出 來的?？梢姡闰灨怕适恰耙颉?，而后驗概率是“果”。2.2 利用貝葉斯理論進行垃圾郵件過濾通過對大量郵件的單詞進行分析，可以認為郵件中的單詞是符合貝葉斯概率模型的。利 用貝葉斯理論進行垃圾郵件過濾的基本思想如下：1某些單詞在已知的垃圾郵件中出現(xiàn)的概 率比較大，而另外一些單詞在正常郵件中出現(xiàn)的概率比較大。因此，一封新郵件到達后，對 其中的每個單詞可以求出其在垃圾郵件中出現(xiàn)的概率，也就是這封郵件根據(jù)這個單詞可以判 別為是垃圾郵件的概率。通過加權求和可以得到一個分數(shù)，也就是把這封郵件判決為垃圾郵 件得到的分數(shù)。同理，也可以得到把這封郵件判決為正常郵件的分數(shù)。通過求差或求積就可 以得到這個郵件的最終得分，然后再利用一定的閾值就可以得到判決結果。因此，可以根據(jù)郵件的內(nèi)容來建立貝葉斯模型，將貝葉斯公式中的事件與垃圾郵件、 正常郵件對應起來，然后利用貝葉斯公式得到這封郵件的分數(shù)，再根據(jù)一定的判別規(guī)則進行 郵件類型的判別。垃圾郵件的貝葉斯模型簡歷以后，貝葉斯公式就成為如下形式：p(c j ) p(dx c j )p(c jd x ) =p(d x ), j = 0,1其中， p(c j ) ， j = 0,1 即為經(jīng)訓練集統(tǒng)計出來的先驗概率分布，其值公式表示如下：訓練中屬于cj類的文本數(shù)量p(c j ) =訓練集中文本數(shù)量p(d x c j )c文本的類條件概率是貝葉斯計算的關鍵，由待測郵件 dx 的向量和訓練集對 jv的統(tǒng)計信息求得。我們在向量表示中提到 dx 可以用向量 e = w1 ,l, wn 表示，但是如果向量的各個元素間相關聯(lián)，模型計算相當復雜，因而研究者們提出了樸素貝葉斯模型，并且該 模型完全勝任了該模型在分類領域的運用。2樸素貝葉斯模型又稱簡單貝葉斯模型(navie bayes)，假設構成待測文本向量的各個特 征項彼此獨立，該模型如下圖所示：圖 1 樸素貝葉斯結構圖模型假設成樸素貝葉斯模型后，p(d x c j )的求解方式如下：np(d xc j ) = p(tii =1c j )p(d xc j )目前為止，計算方法已經(jīng)比較清楚，不過還不能完全求出，因為表達式中涉及待測文本的特征項，而特征項的分布模型還不清楚。常見的特征項分布模型有多變量貝 努力分布和多項式分布模型，它們屬于樸素貝葉斯模型的一個變異，也就是說他們具有樸素 貝葉斯模型的性質(zhì)。3智能垃圾郵件過濾系統(tǒng)的設計與實現(xiàn)總體來說，基于貝葉斯模型的垃圾郵件系統(tǒng)分為三個模塊：郵件預處理模塊、分類器訓 練模塊和郵件分類模塊。其中，郵件預處理模塊主要實現(xiàn)了郵件的解析、郵件的分詞(即向 量化)；分類器訓練模塊實現(xiàn)了詞頻、文檔頻率的統(tǒng)計、特征向量的降維處理、用戶反饋的 處理；郵件分類模塊實現(xiàn)了新郵件的向量化、特征項提取、郵件評分并分類的功能。系統(tǒng)整 體設計框圖如下圖所示：圖 2 系統(tǒng)整體框架在處理過程中，無論是訓練樣本、測試樣本還是反饋回來的判斷錯誤的郵件，都要首先 經(jīng)過預處理模塊，進行郵件解析，從郵件頭和郵件體中提取內(nèi)容信息，并進行分詞處理，并 將郵件解析結果以向量形式保存；如果進行樣本的訓練，則進入分類器訓練模塊，統(tǒng)計出每 個單詞的詞頻(tf)、文檔頻率(df)，然后利用 tf-idf 方法計算出每個單詞在向量空間中的權 重，然后通過設定權重閾值提取權重比較大的特征值，從而實現(xiàn)了特征向量的降維處理，最 后將得到兩個向量：spam 向量和 ham 向量，分別保存降維后特征向量中特征值在垃圾郵件 中和非垃圾郵件中的詞頻，也就是分類器訓練得到的特征項；當一封新的郵件進入到系統(tǒng)后， 首先也會被解析成一個特征值向量，然后利用分類器訓練得到的特征項進行降維處理，并通 過查詢特征項以及結合分類決策，也就是規(guī)定的評分規(guī)則，進行對郵件的評分，最后根據(jù)評 分閾值判定郵件是否為垃圾郵件；如果在分類過程中判斷錯誤，可以將錯誤的郵件進行反饋， 重新進行訓練并更新關鍵詞庫。4.系統(tǒng)模塊設計4.1 郵件預處理模塊由于電子郵件是半結構化文本，語義不是很確定，需要采用一定策略從電子郵件中提取 重要的文本信息。預處理的目的是通過對郵件進行解析，從郵件頭和郵件體中提取出目標文 本信息、進行分詞處理，最后將結果保存到分詞向量中以供分類器訓練和郵件分類使用。郵 件的預處理是分類器訓練和郵件分類的重要前提，預處理結果的好壞和分詞的精準直接影響 到后序的處理結果。郵件的預處理主要完成了郵件的解析和文本的分詞兩個功能。下面將分別介紹。 目前的電子郵件一般都采用 mime(multipurpose internet mail extensions)標準，即多用途互聯(lián)網(wǎng)郵件擴展，它定義郵件內(nèi)容傳輸?shù)母袷揭约熬幋a方式等，郵件解析要按照 mime標準進行。一個 mime 郵件分為 mime 信息頭和 mime 郵件體兩部分。mime 信息頭也就 是郵件頭，包含了郵件的基本信息，如收件人、發(fā)件人等。此外，還包含兩個重要字段： content-type 和 content-transfer-encoding。其中 content-type 定義了數(shù)據(jù)的類型，如文本、 音頻、視頻等類型，以便數(shù)據(jù)能被適當?shù)奶幚?；content-transfer-encoding 定義了數(shù)據(jù)的編 碼方式，以便客戶端對數(shù)據(jù)進行解碼處理。如果 mime 信息頭中 content-type 定義郵件體 為多部分消息(multipart)，那么每個部分還會有 mime 段頭，用來指定子段的數(shù)據(jù)類型和編 碼方式。下圖是郵件解析的主要流程。圖 3 郵件解析的基本流程解析郵件時首先獲取郵件頭信息，主要包括主題(subject:)、內(nèi)容類型(content-type)以及內(nèi)容傳輸編碼(content-transfer-encoding)字段的內(nèi)容，然后根據(jù)內(nèi)容類型進行判斷，如果 是文本類型就進行處理，根據(jù)編碼方式讀取郵件體中的文本信息；如果郵件體是多個子段組 成的，那么分別讀取各個子段中文本信息，然后將文本信息匯總并保存起來。最后將郵件頭 的主題和郵件體中的文本信息保存起來以便進行分詞處理。在進行文本分類處理之前，要進行文本的分詞。由于英文語句在書寫上的特殊性，在分 詞處理上相對漢語要容易的多。中文分詞，也稱為切詞?，F(xiàn)有的分詞方法可分為三大類:基 于詞典的字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計的分詞方法。分詞處理過 后的文本以單詞的形式保存在向量中等待后序模塊進行處理。4.2 分類器訓練模塊3經(jīng)過分詞處理后向量中存放大量不同的單詞，如果將每個單詞都表示成特征項的話， 那特征向量的維數(shù)將會非常龐大，而且大量不同的單詞中真正能對郵件類別起到區(qū)分作用的 又占少數(shù)，因此需要通過特征選擇來篩選特征項，實現(xiàn)特征向量的降維處理。目前特征子集 的選取算法一般是構造一個評價函數(shù)，對特征集中的每個特征進行獨立的評估。本模塊采用 了 tf-idf(term frequency-inverse document frequency)即詞頻-逆向文檔頻率方法來對每個 特征進行評估，以決定該特征是否作為用來分類的特征項。特征向量經(jīng)過降維處理后，就可以對從訓練樣本提取的特征向量進行分類處理。分類器 會根據(jù)已知的郵件類別將特征項保存到指定的 spam 向量和 ham 向量。這兩個向量分別保 存了垃圾郵件和非垃圾郵件中出現(xiàn)的特征項以及特征項的詞頻。4.2.1 特征向量降維特征向量的降維處理采用 tf-idf（詞頻-逆向文檔頻率）方法，該方法是一種統(tǒng)計方法， 用于評估一字詞對一個文件集或一個語料庫中某一個文件的重要程度。字詞的重要性隨它在 文件中出現(xiàn)的次數(shù)成正比，隨它在語料庫中出現(xiàn)的頻率成反比。具體做法是：將每一封郵件d 表示成訓練樣本向量空間中的一個向量，向量中的每一維由郵件中的一個單詞 wi 和其權重 組成。每個單詞的權重值 di 由下式計算：r miss=num(s h)num(s h) + num(s)其中，tf (wi , d ) 為詞頻， d 為文檔總數(shù)， df (wi ) 為文檔頻率。 求出每個單詞的權重值后，就可以將權重值低于門限值的單詞，也就是對郵件類別區(qū)分度較小的單詞排除在特征項之外，最后得到精簡后的特征向量。4.2.2 文本分類訓練 文本的分類采用貝葉斯分類方法，貝葉斯方法基于如下的假定：待考查的數(shù)據(jù)變量遵循某概率分布，且可根據(jù)這些概率及已觀察到的數(shù)據(jù)進行推理，以做出最優(yōu)的決策。具體的實現(xiàn)方法：訓練樣本經(jīng)過解析向量化并進行降維處理后，統(tǒng)計每個單詞在垃圾郵 件和非垃圾郵件中出現(xiàn)的次數(shù)，分別保存到兩個向量中作為訓練的結果集。兩個向量 spam 向量和 ham 向量分別保存了在訓練樣本向量空間中垃圾郵件和非垃圾郵件出現(xiàn)的單詞以及 詞頻。在這個過程中統(tǒng)計出類先驗概率和類條件概率，從而得到貝葉斯分類器。郵件分類時需要再次查詢 spam 向量和 ham 向量，以獲取某關鍵詞在垃圾郵件和非垃圾郵件中的詞頻來進行評分處理。為了加快查詢速度，利用哈希函數(shù)將表示單詞的字符串映 射為散列值，實際上 spam 向量和 ham 向量保存的是特征項的散列值。這樣就加快了在郵 件分類時對已分類文本的查詢速度，也加快了系統(tǒng)處理的速度。n下圖是分類器訓練模塊的流程圖。4.3 郵件分類模塊圖 4 分類器訓練模塊工作流程4基于貝葉斯分類方法來對一封新的郵件進行分類，首先要經(jīng)過郵件的預處理、特征向 量的降維處理，然后再結合特征項庫的先驗概率進行組合計算獲得這封郵件為垃圾郵件的后 驗概率。將計算結果和設定的閾值進行比較來判定郵件是否為垃圾郵件。根據(jù)判定的郵件類型，可以進行反饋學習來更新分類器，反饋學習采用增量式學習，在 學習過程不斷更新原有的各種統(tǒng)計量。通過貝葉斯分類器的反饋學習，該系統(tǒng)可以隨著垃圾 郵件的變化而不斷的進行更新。由于分類模塊依賴于訓練模塊得到 spam 向量和 ham 向量，因此訓練模塊包括預處理 模塊的分詞功能處理結果的準確度直接影響到郵件的判別結果。下圖是郵件分類的基本流 程。5實驗結果圖 5 郵件分類基本流程為了評價此過濾系統(tǒng)的性能，引入兩個性能指標：誤報率 r err 和漏報率 r miss 。其中誤num(h s)報率的定義如下:r err=num(h s) + num(h)，其中 num(h s) 是將合法郵件判為垃圾郵件的概率， num(h) 為實際的合法郵件的數(shù)量。漏報率的定義如下：r miss=num(s h)num(s h) + num(s)其中 num(s h) 是將垃圾郵件判為合法郵件的數(shù)量，而 num(s) 為實際垃圾郵件的數(shù) 量。實驗共使用樣本郵件 37822 封，其中垃圾郵件有 24232 封，正常郵件 12611 封。其中， 正確判斷出郵件類型的郵件共 36318 封，將正常郵件判為垃圾郵件共 66 封，垃圾郵件漏判 為正常郵件的共 459 封。通過計算可以得知，郵件的正確識別率為 98.575%，誤判率為 0.52%， 漏判率為 1.86%。實驗證明，基于貝葉斯的智能垃圾郵件過濾系統(tǒng)有著良好的系統(tǒng)性能。6. 結束語本文給出了一種基于貝葉斯的智能垃圾郵件過濾的解決方案。通過對大量樣本郵件進行 測試，該系統(tǒng)對垃圾郵件的正確識別率在 98%以上。在貝葉斯過濾器的設計過程中有幾個 難點。一是預處理模塊的分詞部分，切詞的準確與否直接影響到樣本的訓練結果、郵件的分 類結果。另外一點就是特征向量降維和郵件評分閾值的選取。對于郵件特征向量降維，選取 特征項過多或過少都會對影響判決結果。而評分閾值的選擇更是直接影響到郵件的分類結 果。因此，在設計過程中一定要注意對這幾個細節(jié)的處理。參考文獻1 劉明川，彭長生. 基于貝葉斯概率模型的郵件過濾算法探討. 重慶郵電學院學報（自然科學版）, 第17卷, 第5期2 張銘鋒，李云春，李巍. 垃圾郵件過濾的貝葉斯方法綜述. 計算機應用研究 20053 邵必林，馬維平，邊根慶. 基于貝葉斯理論的中文垃圾郵件過濾