房愛東，凌 軍，李雪竹

宿州學(xué)院信息工程學(xué)院，宿州，234000

最大熵原理在垃圾郵件分類中的應(yīng)用研究

房愛東，凌 軍，李雪竹

宿州學(xué)院信息工程學(xué)院，宿州，234000

垃圾郵件具有初始樣本小和多變性的特點(diǎn)，為了從大量的郵件中將其識(shí)別出來，采用平滑技術(shù)處理特征詞的稀疏特性，進(jìn)行概率統(tǒng)計(jì)分析，引入最大熵原理，并結(jié)合增量學(xué)習(xí)方法提高分類效果。通過對(duì)標(biāo)準(zhǔn)數(shù)據(jù)集的測(cè)試，測(cè)試結(jié)果證明所提出算法具有良好的垃圾郵件識(shí)別能力，能提高郵箱業(yè)務(wù)對(duì)垃圾郵件的識(shí)別能力。

最大熵原理; 增量學(xué)習(xí); 機(jī)器學(xué)習(xí)

1 相關(guān)研究與問題提出

隨著互聯(lián)網(wǎng)的發(fā)展，電子郵件已經(jīng)逐步替代了傳統(tǒng)的通信手段成為人們溝通的橋梁，但垃圾郵件的泛濫嚴(yán)重影響了人們正常的工作和學(xué)習(xí)。據(jù)《中國反垃圾郵件狀況調(diào)查報(bào)告》顯示，中國電子郵箱用戶平均每周收到的垃圾郵件為13.8封，電子郵箱用戶平均每周收到的郵件中垃圾郵件所占比例為40.1%。

目前，反垃圾郵件的方法主要有以下幾種：SMTP層的反垃圾郵件技術(shù)、IP層的反垃圾郵件技術(shù)、基于規(guī)則的垃圾郵件過濾方法以及結(jié)合機(jī)器學(xué)習(xí)的概率統(tǒng)計(jì)方法[1]。但是，以上方法都有其特有的局限性，如IP層的反垃圾郵件技術(shù)有延遲，速度慢；SMTP層的反垃圾技術(shù)對(duì)網(wǎng)絡(luò)資源要求過大；基于規(guī)則的過濾方法準(zhǔn)確性和時(shí)間開銷存在矛盾，而基于機(jī)器學(xué)習(xí)的概率統(tǒng)計(jì)方法[2]過程較為復(fù)雜，需要用戶干預(yù)，也不易于大規(guī)模應(yīng)用。人們?cè)趯?shí)際應(yīng)用中往往將幾種方法相結(jié)合對(duì)郵件進(jìn)行分類，但效果依然不佳。由于垃圾郵件具有初始樣本小、變化多樣等特點(diǎn)，而最大熵理論在小樣本訓(xùn)練下分類效果好以及對(duì)初始樣本依賴小，故本文提出一種基于最大熵方法并通過增量學(xué)習(xí)的方法對(duì)郵件進(jìn)行分類的反垃圾郵件方法。

2 基于最大熵方法的反垃圾郵件系統(tǒng)的搭建

2.1 最大熵理論模型

最大熵的基本思想是，選擇一個(gè)模型使某個(gè)事物的分布盡可能均勻，使得該系統(tǒng)的熵達(dá)到最大。而更加現(xiàn)實(shí)的問題是，如果對(duì)某個(gè)事物已經(jīng)有所了解，選擇一個(gè)什么樣的模型預(yù)測(cè)該事物可能發(fā)生的事件。最大熵模型擬合所有已知事實(shí)，保持對(duì)未知事件的未知狀態(tài)，而要對(duì)未知事件盡可能使其分布均勻，需要選擇一種模型與現(xiàn)有事實(shí)一致。

20世紀(jì)90年代，大規(guī)模真實(shí)文本的處理開始使用最大熵方法[3]，通過實(shí)驗(yàn)和綜合觀察，對(duì)許多問題的處理結(jié)果超過了使用其他方法的最好結(jié)果。最近幾年，最大熵模型被廣泛應(yīng)用于包括詞義排歧、詞性標(biāo)注、機(jī)器翻譯、短語識(shí)別、分詞等[4-6]。

(1)

(2)

(3)

若存在k個(gè)特征fi(i=1,2,…，k)，則有k組約束：

(4)

滿足上述約束條件的模型很多，這里需要在約束條件下具有均勻分布的概率，若用條件熵為條件概率p(x|y)均勻性的一種數(shù)學(xué)測(cè)量方法，則熵的計(jì)算公式如下：

(5)

其中，0≤H(p)≤log|y|則一組約束p被滿足的最優(yōu)解為：

p*=argmaxH(p)

(6)

使用拉格朗日乘數(shù)法即可求得最優(yōu)解：

(7)

(8)

其中，參數(shù)λi是對(duì)應(yīng)特征函數(shù)fi的權(quán)重，z(x)是歸一化因子。若通過訓(xùn)練樣本進(jìn)行學(xué)習(xí)，就可以求得λi值，得到所求的概率分布，最大熵模型的構(gòu)造得到滿足。最大熵模型的參數(shù)求解就是帶約束條件的非線性規(guī)劃問題，屬于凸優(yōu)化問題，可獲得最優(yōu)解。

2.2 基于最大嫡模型的郵件分類

用X表示郵件的類別，即正常郵件和垃圾郵件，用Y表示郵件樣本特征，于是可利用公式(7)來求得任意一篇郵件yi∈Y屬于任意類別xj∈X的條件概率p(xj|yi)?？紤]用各種不同的方法作為判定條件，如對(duì)于Y不兼容分類集合的情況(垃圾郵件或正常郵件)，可比較樣本在不同集合出現(xiàn)的概率，并把此樣本劃分到出現(xiàn)概率最大的集合中。還考慮到郵件分類誤報(bào)問題，若一封垃圾郵件被錯(cuò)分為正常郵件，對(duì)用戶造成的損失相對(duì)來說不是很大；而一旦一封重要的郵件被錯(cuò)誤分類為垃圾郵件，可能會(huì)給用戶帶來難以預(yù)料的損失。因此，可考慮Y中存在兼容分類的情況，根據(jù)當(dāng)前郵件特征設(shè)定一個(gè)閾值ε，如果樣本特征在正常郵件集中出現(xiàn)的概率p(x|y)>ε，則該郵件就被認(rèn)定為正常郵件。當(dāng)出現(xiàn)稀疏事件的時(shí)候，最大熵模型可以使未知事件的概率分布盡可能均勻，即傾向于得到最大熵。

對(duì)于文本分類，文檔中的特征詞具有稀疏特征，表現(xiàn)在相當(dāng)多的特征詞在訓(xùn)練樣本中出現(xiàn)，而在待分類文檔中沒有出現(xiàn)，同樣也有相當(dāng)多的特征詞在待分類文檔中出現(xiàn)，卻沒有在訓(xùn)練樣本中出現(xiàn)?？刹捎闷交夹g(shù)(smoothing)來處理此種情況，即對(duì)所有在待分類文檔中出現(xiàn)而沒有在訓(xùn)練文檔出現(xiàn)的特征詞賦予一個(gè)值。針對(duì)文本中的分類問題，絕對(duì)折扣(Absolute-Discounting)技術(shù)[8]是目前使用最多的。絕對(duì)折扣平滑技術(shù)是指在減掉一個(gè)固定值的前提下對(duì)模型中觀察到的事件進(jìn)行折扣，然后把折扣后的概率分?jǐn)偟剿形船F(xiàn)事件中。因?yàn)樘卣骱瘮?shù)的值是詞頻，對(duì)特征出現(xiàn)次數(shù)進(jìn)行折扣時(shí)不涉及到保持概率和為1的問題，所以只需直接給所有出現(xiàn)次數(shù)為0的特征一個(gè)值即可。

2.3 增量學(xué)習(xí)調(diào)整標(biāo)記

增量學(xué)習(xí)是改善機(jī)器學(xué)習(xí)和概率統(tǒng)計(jì)方法的一個(gè)重要而且十分有效的途徑，本文采用增量學(xué)習(xí)方法來提高垃圾郵件分類的性能。在增量學(xué)習(xí)之前，通過一個(gè)初始模型對(duì)郵件進(jìn)行分類判斷，之后對(duì)錯(cuò)檢和漏檢的郵件進(jìn)行內(nèi)部調(diào)整。

本文采取對(duì)郵件的主體部分插入標(biāo)簽，標(biāo)簽隱含了對(duì)應(yīng)郵件的唯一標(biāo)識(shí)信息。對(duì)于調(diào)整錯(cuò)誤的郵件，用戶只要點(diǎn)擊標(biāo)簽，相應(yīng)信息就會(huì)返還進(jìn)行增量學(xué)習(xí)處理，增量過程通過對(duì)該數(shù)據(jù)文件的分析來進(jìn)行模型的改善。當(dāng)訓(xùn)練模式啟動(dòng)時(shí)，使用者可以根據(jù)所服務(wù)的用戶的實(shí)際郵件情況重新訓(xùn)練一個(gè)或者多個(gè)新的模型來供分類使用。在增量效果不滿意的情況下，訓(xùn)練模式還可以把模型狀態(tài)回滾，重置到初始狀態(tài)，重新進(jìn)行增量訓(xùn)練。

3 分類效果測(cè)試

使用加入訓(xùn)練標(biāo)記的最大熵方法，對(duì)郵件樣本進(jìn)行測(cè)試。所有的郵件樣本來源于國際上Benchmark標(biāo)準(zhǔn)數(shù)據(jù)集SpamAssassin Corpus (RFC822)和ZH1 Chinese Corpus，郵件分類效果根據(jù)錯(cuò)檢率和漏檢率判斷。對(duì)標(biāo)準(zhǔn)數(shù)據(jù)集SpamAssassin Corpus (RFC822)的測(cè)試結(jié)果如表1和表2所示。

表1 SpamAssassin Corpus (RFC822)的測(cè)試結(jié)果1

注：(1)表中數(shù)據(jù)格式：特征選擇數(shù)為2000，特征選擇數(shù)為10 000未進(jìn)行特征選擇。(2)S-S 垃圾郵件檢測(cè)為垃圾郵件數(shù)量，S-H垃圾郵件檢測(cè)為正常郵件數(shù)量H-H，正常郵件檢測(cè)為正常郵件數(shù)量，H-S 正常郵件檢測(cè)為垃圾郵件數(shù)量。

表2 SpamAssassin Corpus (RFC822)的測(cè)試結(jié)果2

對(duì)ZH1 Chinese Corpus的測(cè)試結(jié)果如表3和表4所示。

表3 ZH1 Chinese Corpus的測(cè)試結(jié)果1

注：表中數(shù)據(jù)格式為：特征選擇數(shù)為2000，特征選擇數(shù)為10 000未進(jìn)行特征選擇。

表4 ZH1 Chinese Corpus的測(cè)試結(jié)果2

4 數(shù)據(jù)分析

通過郵件分類結(jié)果可以看出，本文方法對(duì)MIME測(cè)試數(shù)據(jù)具有良好的分類效果，在標(biāo)準(zhǔn)測(cè)試集上的漏檢率和錯(cuò)檢率隨訓(xùn)練集的增大而減少；而不隨訓(xùn)練集合增大的數(shù)據(jù)又說明有少數(shù)郵件在初始分類是始終不能被正確分類的，這就體現(xiàn)了增量學(xué)習(xí)的必要性。特征選擇數(shù)增加，意味著郵件越來越全面地被郵件樣本代表，因此可以判斷的依據(jù)也就更多，特征數(shù)的增加會(huì)使計(jì)算結(jié)果準(zhǔn)確性的提高，使漏檢率和錯(cuò)檢率降低。

5 結(jié)束語

本文研究了最大熵方法在垃圾郵件分類中的應(yīng)用，并通過引入增量學(xué)習(xí)的方法對(duì)其進(jìn)行了加強(qiáng)，實(shí)驗(yàn)表明，在原有的最大熵理論基礎(chǔ)上，加入增量學(xué)習(xí)可以很好地提升垃圾郵件的分類效果。

［1］徐松浦．反垃圾郵件中貝葉斯方法的應(yīng)用研究［D］．成都:成都理工大學(xué)信息科學(xué)與技術(shù)學(xué)院，2005:5-8

［2］靳小波．基于機(jī)器學(xué)習(xí)算法的文本分類系統(tǒng)［D］．西安:西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，2005:12-13

［3］張樂．機(jī)器學(xué)習(xí)方法在基于內(nèi)容的垃圾郵件過濾中的研究［D］．沈陽:東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，2004: 10-14

［4］R Adwait．Maximum entropymodels for natural language ambiguity resolution［D］．Pennsylvania:University of Pennsylvania Computer Science College，1998:15-20

［5］R Adwait．A maximum entropymodel for Part－of－Speech tagging［C］//Proceedings of the Empirical Methods in Natural Language Processing Conference．Philadelphia，USA，1996:31-33

［6］Adam L Berger，Stephen A Della Pietra，Vincent JDella Pietra．A maximum entropy approach to natural language processing［J］．Computational Linguistics，1996，22(1):38-73

［7］陳文慶．基于最大熵模型郵件過濾系統(tǒng)的研究與實(shí)現(xiàn)［D］．廣州:華南理工大學(xué)電子信息學(xué)院，2004:35-42

［8］M Sven，N Hermann，Z Jrg．Smoothing methods in maximum entropy language modeling［C］//IEEE International Conference on Acoustics，Speech and Signal Processing．Phoenix，AR，1999:60-71

10.3969/j.issn.1673-2006.2017.12.025

TP393.08

A

1673-2006(2017)12-0094-04

2017-08-24

安徽省高等學(xué)校教學(xué)研究重大項(xiàng)目(2016jyxm1026)；安徽省科技廳軟科學(xué)研究計(jì)劃資助項(xiàng)目(1502052053)；宿州學(xué)院教學(xué)研究項(xiàng)目(szxy2015jy12);宿州區(qū)域發(fā)展協(xié)同創(chuàng)新中心課題資助(2016szxt06)。

房愛東(1966-)，安徽宿州人,副教授，研究方向：模式識(shí)別、網(wǎng)絡(luò)與信息安全。

(責(zé)任編輯:劉小陽)