朱 軍，饒 元，傅雷揚(yáng) (安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院，安徽 合肥 230036)

張 寧，劉 鍇 (安徽農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)中心，安徽 合肥 230036)

基于文本分類的中文垃圾郵件過濾技術(shù)研究

朱 軍，饒 元，傅雷揚(yáng) (安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院，安徽 合肥 230036)

張 寧，劉 鍇 (安徽農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)中心，安徽 合肥 230036)

由于語言上的差異，中文垃圾郵件過濾與英文郵件在信息處理技術(shù)上差別較大。針對(duì)中文垃圾郵件過濾的郵件訓(xùn)練集、過濾規(guī)則和分類器特征庫更新不及時(shí)，經(jīng)常出現(xiàn)誤判和漏判等問題，以文本分類技術(shù)為基礎(chǔ)，將基于規(guī)則方法和Bayes分類方法相結(jié)合，設(shè)計(jì)了一種中文垃圾郵件過濾方法，詳細(xì)闡述了中文郵件過濾的郵件預(yù)處理、中文分詞、特征選取等技術(shù)。試驗(yàn)結(jié)果表明，該方法可以明顯改善中文垃圾郵件過濾效果。

中文垃圾郵件；過濾；文本分類；Bayes分類；特征選取

從文本分類技術(shù)角度看，過濾垃圾郵件即將郵件分為垃圾類和非垃圾類。根據(jù)電子郵件的半結(jié)構(gòu)化特性，可以先采用郵件預(yù)處理技術(shù)提取郵件主題和正文內(nèi)容的文本，然后使用文本分類算法將垃圾郵件過濾[1]。文本分類有訓(xùn)練過程和分類過程2個(gè)階段(見圖1)。在訓(xùn)練過程階段，系統(tǒng)需要一定數(shù)量的已分類好的訓(xùn)練文本指導(dǎo)，經(jīng)過預(yù)處理后提取必要的特征信息來構(gòu)造分類器，目前在垃圾郵件內(nèi)容過濾領(lǐng)域常用的分類技術(shù)有Bayes分類、決策樹、支持向量機(jī)、遺傳算法(Genetic Algorithm)、粗糙集等[2]。這些技術(shù)分為基于規(guī)則的方法和基于統(tǒng)計(jì)的方法，基于規(guī)則的方法從訓(xùn)練文本中學(xué)習(xí)得到分類規(guī)則，如決策樹、粗糙集等；基于統(tǒng)計(jì)的方法通過統(tǒng)計(jì)學(xué)習(xí)的方法構(gòu)造相應(yīng)的分類器，如Bayes分類、支持向量機(jī)等。上述分類方法對(duì)英文郵件過濾效果較好，但對(duì)中文郵件過濾效果較差。因?yàn)橹形泥]件和英文郵件在信息處理上有很大差別，若郵件訓(xùn)練集、中文過濾規(guī)則和分類器特征庫更新不及時(shí)，經(jīng)常出現(xiàn)誤判和漏判現(xiàn)象。筆者從郵件預(yù)處理入手，結(jié)合中文分詞和特征選取技術(shù)，提出了一種基于規(guī)則和Bayes分類方法相結(jié)合的中文垃圾郵件過濾方法，通過機(jī)器學(xué)習(xí)來解決郵件訓(xùn)練集、中文過濾規(guī)則和分類器特征庫的自動(dòng)更新問題。

圖1 文本分類的2個(gè)階段

1 Bayes分類原理

Bayes分類算法是一種基于概率分析的可能性推理，Paul Graham在2002年提出一種用該算法過濾垃圾郵件的方法[3]。由于一些單詞在垃圾郵件中出現(xiàn)頻率較高，而另一些單詞在合法郵件中出現(xiàn)頻率較高，因而對(duì)上述單詞進(jìn)行概率統(tǒng)計(jì)后可以得到其“垃圾郵件指示性概率”，進(jìn)而根據(jù)郵件中包含的一些單詞來確定該郵件的“垃圾郵件概率”。垃圾郵件所含有特殊單詞和代碼的概率是其內(nèi)容的特征，根據(jù)這些特征可以建立Bayes概率模型，通過Bayes公式計(jì)算得出其是垃圾郵件的概率，從而判斷該郵件是否為垃圾郵件。

設(shè)文本dx屬于某類文本的概率為P(cj|dx)，計(jì)算P(cj|dx)時(shí)可以利用Bayes公式：

(1)

設(shè)dx為n個(gè)特征的集合(t1,t2,…,tn)，假設(shè)特征之間是相互獨(dú)立的，根據(jù)文本中出現(xiàn)的特征的文本分類條件概率可以求得：

(2)

將其應(yīng)用到郵件過濾中，只考慮垃圾郵件和正常郵件2個(gè)類別。設(shè)c=1為垃圾郵件類，c=0為正常郵件類，對(duì)郵件dx可以用式(3)計(jì)算該郵件是垃圾郵件的概率：

(3)

在垃圾郵件過濾技術(shù)中，基于統(tǒng)計(jì)的方法比基于規(guī)則的方法檢測新垃圾郵件的能力強(qiáng)，但是準(zhǔn)確性不高，易將正常郵件誤判為垃圾郵件。另外，Bayes分類通過已知的郵件訓(xùn)練集進(jìn)行概率計(jì)算，其過濾準(zhǔn)確性需要依賴大量歷史數(shù)據(jù)，郵件訓(xùn)練集如何及時(shí)自動(dòng)地更新也是需要解決的問題。

2 中文垃圾郵件綜合過濾方法

圖2 中文垃圾郵件過濾流程圖

綜合運(yùn)用Bayes概率模型和基于規(guī)則方法的過濾技術(shù)，設(shè)計(jì)一種中文垃圾郵件綜合過濾方法。首先收集大量的垃圾郵件和正常郵件，經(jīng)過郵件預(yù)處理和中文分詞后，進(jìn)行特征選取，生成SA(SpamAssassin)中文規(guī)則和特征詞庫。通過一次機(jī)器學(xué)習(xí)，同時(shí)得到Bayes過濾器的特征詞庫和SA中文規(guī)則庫，第1層過濾時(shí)使用SA中文規(guī)則庫過濾，第2層過濾使用Bayes過濾，雙層過濾不僅提高垃圾郵件過濾效果，并且可以自動(dòng)更新郵件訓(xùn)練集、SA中文規(guī)則和特征詞庫，中文垃圾郵件過濾流程圖如圖2所示。

2.1郵件過濾模塊設(shè)計(jì)

圖3 中文垃圾郵件過濾模塊設(shè)計(jì)圖

在使用SA中文規(guī)則庫進(jìn)行第1層過濾時(shí)，將SA的閾值盡量提高，在誤判率盡可能小的情況下過濾垃圾郵件，然后將過濾出來的垃圾郵件送到垃圾郵件集，及時(shí)更新Bayes過濾器郵件訓(xùn)練集。通過SA中文規(guī)則過濾的郵件進(jìn)入第2層進(jìn)行Bayes過濾，Bayes過濾器結(jié)合特征詞庫對(duì)郵件計(jì)算其垃圾郵件概率，如果超過設(shè)定閾值則判為垃圾郵件，低于設(shè)定閾值則判為正常郵件，發(fā)送給用戶的同時(shí)抄送到系統(tǒng)設(shè)定的郵箱，作為機(jī)器學(xué)習(xí)的新的正常郵件訓(xùn)練集，而使用新的郵件訓(xùn)練集學(xué)習(xí)后得到的特征詞庫又會(huì)自動(dòng)更新SA中文規(guī)則，從而形成良性循環(huán)，這樣系統(tǒng)運(yùn)行時(shí)間越長，過濾垃圾郵件的準(zhǔn)確性越高。郵件過濾模塊如圖3所示。

2.2郵件預(yù)處理

郵件預(yù)處理包括郵件解碼、漢字編碼識(shí)別和郵件元素分離等步驟[4]。

1)郵件解碼 郵件解碼實(shí)際上就是編碼的逆過程。在郵件解碼之前必須先判斷郵件采用的是何種編碼，然后才能使用相應(yīng)的解碼算法。目前的中文郵件系統(tǒng)基本都使用RFC2045等定義的MIME協(xié)議，MIME定義2種編碼方式：Base64與QP(Quote-Printable)。在編碼后的郵件源碼中，以“=?charset?B?xxxxxxxx?=”表示xxxxxxxx是Base64編碼，且原文的字符集是charset；以“=?charset?Q? xxxxxxxx?=”表示xxxxxxxx是Quoted-printable編碼，且原文的字符集是charset。根據(jù)該特征，使用perl的正則表達(dá)式設(shè)計(jì)編碼判斷算法對(duì)郵件進(jìn)行解碼[5]。

2)漢字編碼識(shí)別 漢字有不少編碼標(biāo)準(zhǔn)，目前常用的漢字編碼有GB碼、BIG5碼和Unicode碼。若郵件內(nèi)容采用不同的編碼會(huì)對(duì)規(guī)則匹配產(chǎn)生很大影響，所以在規(guī)則生成中必須對(duì)不同編碼的郵件進(jìn)行識(shí)別。筆者主要根據(jù)郵件的主題或信體中的字符的編碼范圍來識(shí)別郵件的GB2312編碼格式。

3)郵件元素分離 電子郵件是一種半結(jié)構(gòu)化的文本數(shù)據(jù)，郵件元素分離主要是提取信頭中的主題信息和信體數(shù)據(jù)。

2.3中文分詞

漢語是基于單字的文本，漢字(詞)不僅是中文書面表達(dá)的最小單位，也是自然語言中最小的構(gòu)成單位。由于詞與詞之間沒有邊界標(biāo)志，在對(duì)郵件文本進(jìn)行特征提取時(shí)，為了讓計(jì)算機(jī)能識(shí)別處理，必須使用分詞方法將郵件文本中的詞劃定邊界。中文分詞通常的方法主要分為3類：第1類是基于詞典的字符串匹配分詞方法；第2類是基于詞的頻度統(tǒng)計(jì)分詞方法，上述方法比較容易實(shí)現(xiàn)；第3類方法主要基于句法、語法分析，并結(jié)合語義分析，通過對(duì)上下文內(nèi)容所提供信息的分析對(duì)詞進(jìn)行定界，該類方法試圖讓機(jī)器具有人類的理解能力，其原理較為晦澀，一般不易實(shí)現(xiàn)。

2.4特征選取

圖4 特征選取流程圖

郵件訓(xùn)練集經(jīng)過預(yù)處理和分詞后得到大量詞匯，如果將上述詞匯都作為特征，不僅計(jì)算壓力大，而且分類算法代價(jià)高，系統(tǒng)提取的文檔類別信息也不準(zhǔn)確，因而需要通過特征選取選出適當(dāng)數(shù)量的詞作為垃圾郵件特征詞[5]。特征選取的任務(wù)是從分詞處理后得到的大量詞匯中選出適量的垃圾郵件特征詞。特征選取之前需要對(duì)郵件進(jìn)行預(yù)處理和中文分詞過程，在此基礎(chǔ)上進(jìn)行特征選取(見圖4)，其具體過程如下：①首先對(duì)垃圾郵件集和正常郵件集分別進(jìn)行郵件解碼、漢字編碼識(shí)別和郵件元素分離等預(yù)處理，建立垃圾郵件表(spam)和正常郵件表(ham)。②對(duì)spam表和ham表中的主題字段和信體字段進(jìn)行中文分詞處理后，建立subject_spam、body_spam、subject_ham、body_ham 4個(gè)特征項(xiàng)表。③在特征項(xiàng)表subject_spam和subject_ham中進(jìn)行特征選取，建立垃圾郵件主題特征詞表(subject)，在特征項(xiàng)表body_spam和body_ham中進(jìn)行特征選取，建立垃圾郵件信體特征詞表(body)。④在垃圾郵件主題特征詞表和垃圾郵件信體特征詞表中進(jìn)行權(quán)值計(jì)算，建立SA規(guī)則庫和Bayes特征詞庫。

3 試驗(yàn)結(jié)果與分析

表1 變量定義表

3.1評(píng)價(jià)指標(biāo)的定義

圖5 使用SA中文規(guī)則過濾的試驗(yàn)結(jié)果

依據(jù)文獻(xiàn)[6]定義相關(guān)變量(見表1)，設(shè)測試集中郵件總數(shù)為N(為A、B、C、D4個(gè)變量之和)，另外定義2個(gè)常用的評(píng)價(jià)指標(biāo)[7]：①召回率Recall=[A/(A+C)]×100%，即系統(tǒng)發(fā)現(xiàn)垃圾郵件的能力。②誤判率Error=[(B+C)/N]×100%。

3.2試驗(yàn)結(jié)果分析

僅使用SA中文規(guī)則測試時(shí)，將閾值由0.5～5.0設(shè)置10個(gè)等級(jí)，試驗(yàn)結(jié)果如圖5所示。從圖5可以看出，隨著閾值增高，召回率和誤判率都減小，雖然閾值增高后漏檢了部分垃圾郵件，但是判斷準(zhǔn)確性有所提高。當(dāng)閾值為4.0時(shí)，在誤判率為0時(shí)可以檢測出近60%的垃圾郵件，說明如果僅使用SA中文規(guī)則方法來過濾，召回率和誤判率的關(guān)系表現(xiàn)不均衡，這表明基于規(guī)則的過濾方法在靈活性方面還有待提高。

根據(jù)上述試驗(yàn)結(jié)果，將SA的閾值設(shè)定為4.0，確保第1層過濾時(shí)為零誤判，第2層過濾采用Bayes過濾器對(duì)通過第1層過濾的郵件再次過濾，根據(jù)最小風(fēng)險(xiǎn)的Bayes決策[8]，將Bayes過濾器的閾值分別設(shè)定為0.5、0.9和0.99，試驗(yàn)結(jié)果如表2所示。由表2可知，綜合使用2種過濾方法后，召回率和誤判率相對(duì)均衡，說明郵件經(jīng)過預(yù)處理、中文分詞和特征選取后構(gòu)造的Bayes過濾器對(duì)中文垃圾郵件過濾效果明顯改善。

表2 綜合使用2種過濾方法試驗(yàn)結(jié)果

[1]潘文鋒.基于內(nèi)容的垃圾郵件過濾研究[D]. 北京：中國科學(xué)院計(jì)算技術(shù)研究所，2004.

[2]Han J W，Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰 譯.北京：機(jī)械工業(yè)出版社，2001.

[3]Graham P. A Plan for Spam[EB/OL]. http://www.paulgraham.com/spam.html，2002-08-18.

[4]朱軍.中文垃圾郵件過濾技術(shù)研究及應(yīng)用[D].合肥：合肥工業(yè)大學(xué)，2005.

[5]盧揚(yáng)竹，張新有，祁玉.郵件過濾中特征選擇算法的研究及改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2009，29(10) : 2812-2815．

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

[7]潘潔.基于Linux的中文垃圾郵件過濾系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].安徽農(nóng)業(yè)大學(xué)學(xué)報(bào)，2011，38(2): 309-314．

[8]邊肇祺，張學(xué)工.模式識(shí)別[M].北京：清華大學(xué)出版社，1999.

[編輯] 李啟棟

10.3969/j.issn.1673-1409.2012.01.033

TP391

A

1673-1409(2012)01-N102-04