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

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