基于粗糙集的增量式垃圾郵件過濾方法研究

徐丹+韓艷杰+寇曼曼

摘 要： 在粗糙集理論基礎(chǔ)上，提出一種增量式的垃圾郵件過濾方法。該方法將郵件樣本的局部最小確定性作為閾值來控制規(guī)則產(chǎn)生，并在郵件識(shí)別過濾過程中增加了反饋環(huán)節(jié)，將錯(cuò)判和未識(shí)別樣本作為增量樣本進(jìn)行再學(xué)習(xí)，動(dòng)態(tài)調(diào)整郵件規(guī)則的置信度。根據(jù)閾值選擇可信度較高的規(guī)則進(jìn)行更新，從而減少了規(guī)則的個(gè)數(shù)，提高了樣本的正確識(shí)別率，最后用實(shí)驗(yàn)證明了該方法的有效性。

關(guān)鍵詞： 垃圾郵件過濾； 粗糙集理論； 增量學(xué)習(xí)； ILRS算法

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）14?0024?04

0 引 言

隨著Internet技術(shù)的快速發(fā)展，電子郵件在人們的生活中扮演著越來越重要的角色。人們之間大量的交流都通過電子郵件來進(jìn)行，但是垃圾郵件的日益增多也成為困擾人們?nèi)粘９ぷ魃畹囊粋€(gè)難題，電子郵件過濾技術(shù)由此產(chǎn)生并成為阻止垃圾郵件的重要手段之一。有很多學(xué)者對電子郵件過濾方法進(jìn)行了研究，常見的有以下三種：

（1） 基于黑名單?白名單的識(shí)別方法，即利用郵件地址、IP地址或域名的屬性進(jìn)行的郵件識(shí)別，這種方法的正確識(shí)別率低，容易造成誤判，典型的應(yīng)用有結(jié)合DNS（Domain Name Server）的RBL（Real?time Block List）識(shí)別[1]等。

（2） 基于數(shù)據(jù)挖掘技術(shù)，利用文本分類和統(tǒng)計(jì)算法的識(shí)別，比如Bayes[2]、SVM[3]、人工神經(jīng)網(wǎng)絡(luò)[4]等，識(shí)別準(zhǔn)確率較高，但速度慢，不適用于郵件規(guī)模較大的情況；同時(shí)，它們大都沒有考慮交互的問題，對錯(cuò)判郵件的處理不夠完善。

（3） 基于規(guī)則匹配的識(shí)別方法。文獻(xiàn)[5]結(jié)合粗糙集理論的數(shù)據(jù)分析技術(shù)研究了郵件過濾系統(tǒng)的建模和特征發(fā)現(xiàn)等問題，并用經(jīng)驗(yàn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，得到了較好的結(jié)果。劉洋等基于粗糙集理論將郵件向量同規(guī)則向量統(tǒng)一定義，有選擇的進(jìn)行二次過濾，得到了80%左右的正確率[6]。

以上所介紹的方法都只能靜態(tài)的對電子郵件進(jìn)行分類過濾，如何對郵件信息進(jìn)行動(dòng)態(tài)的增量式學(xué)習(xí)將是未來研究的熱點(diǎn)。文獻(xiàn)[7]在擴(kuò)展決策矩陣的定義的基礎(chǔ)上提出一種能夠增量的從樣本數(shù)據(jù)中提取確定性和可能性規(guī)則的方法，該方法對缺乏領(lǐng)域知識(shí)時(shí)的規(guī)則獲取有重要意義；文獻(xiàn)[8]首先根據(jù)粗糙集方法提取規(guī)則，然后在自定義的歸納分配表上利用概率論的思想提取可以覆蓋新樣本的規(guī)則強(qiáng)度高的規(guī)則，并用實(shí)驗(yàn)證明了它的有效性，如何將連續(xù)屬性進(jìn)一步離散化是該方法的下一步需要考慮的問題之一。文獻(xiàn)[9]提出了一種基于概率粗糙集模型的增量式規(guī)則學(xué)習(xí)算法，該算法能夠有效地從不一致和含有噪聲的決策表中提取帶有確定性因子和支持?jǐn)?shù)的決策規(guī)則，提取的規(guī)則具有很好的抗噪聲能力，但是在數(shù)據(jù)量較大的情況下，該方法未能得到有效驗(yàn)證。

本文提出的增量式電子郵件過濾方法是在基于粗糙集的電子郵件過濾模型的基礎(chǔ)上增加反饋環(huán)節(jié)，將識(shí)別過程中錯(cuò)誤識(shí)別和未識(shí)別的郵件信息作為新增的矛盾樣本進(jìn)行再學(xué)習(xí)，通過郵件決策信息表的局部最小確定性與矛盾規(guī)則和樣本可信度的比較，對規(guī)則集進(jìn)行更新，有效地提高了郵件的正確識(shí)別率。本文介紹了基于粗糙集理論的郵件分類模型的相關(guān)基本概念，在此基礎(chǔ)上提出了一種基于粗糙集的增量式電子郵件過濾方法，并利用UCI中的Spam Database數(shù)據(jù)集對該方法進(jìn)行了實(shí)驗(yàn)，并分別與增量前的學(xué)習(xí)效果和ID4算法進(jìn)行比較，從而驗(yàn)證了該方法的有效性。

1 相關(guān)基本概念

定義1（電子郵件決策表信息系統(tǒng)）：電子郵件決策表信息系統(tǒng)是一個(gè)四元組[S=U，R=C?D，V，f]。其中：[U]是郵件的集合；[R]為屬性的集合；[C]為郵件條件屬性的集合；[D]表示決策屬性集合；[V]是屬性值的集合；[f]是信息函數(shù)，它指定[U]中每個(gè)對象[x]的屬性值[10]。

定義2（不分明關(guān)系）：假設(shè)屬性集[P∈R]，對象[X，Y∈U]，對于每個(gè)[Q∈P]，當(dāng)且僅當(dāng)[f（X，a）=f（Y，a）]，[X]和[Y]是不可分辨的，即：[IND（P）={（X，Y）∈][U：?a∈P，f（X，a）=f（Y，a）}。]顯然[IND（P）]是一個(gè)等價(jià)關(guān)系。這樣，屬性集P可以認(rèn)為是用等價(jià)關(guān)系（在該屬性集上的取值相等）表示的一個(gè)知識(shí)的名稱[10]。

定義3（置信度）：對于郵件信息決策表[S=U，R=C?D，V，f]，規(guī)則[A→B]的置信度為：[α=X?YX]，則規(guī)則可表示為如下形式：[A→Bα]，其中：集合[X]是條件屬性值滿足公式[A]的樣本集合，集合[Y]是滿足決策屬性值滿足公式[B]的樣本集合[10]。

定義 4（條件分類對決策分類的確定性程度）：設(shè)決策表為[S=U，A，V，f]，[A=C?D] ，[C]為條件屬性集，[D]為決策屬性集，[Ei∈UINDC，i=1，2，...，m]為條件分類，[Xj∈UINDD，j=1，2，...，n]為分類決策，則任意條件分類[Ei∈UINDC]對決策屬性分類的確定性程度定義[11]為： [kEi=maxEi?XjEiXj∈UINDD]。

定義5（決策表局部最小確定性）：給定決策表[S=U，R，V，f]，[kE1，…，kEi，…，kEm]是條件分類對決策分類的確定性程度，則決策表最小確定性定義為：[αc=minkE1，…，kEi，…，kEm]，[αc]即為控制規(guī)則產(chǎn)生的閾值[11]。

2 基于粗糙集的增量式郵件過濾方法

為了更有效地獲得郵件規(guī)則，需要將學(xué)習(xí)識(shí)別后反饋的錯(cuò)判和未識(shí)別信息作為新樣本進(jìn)行再訓(xùn)練，原始的非增量式學(xué)習(xí)方法是將錯(cuò)判和未識(shí)別樣本放入原始信息決策表，進(jìn)行重新訓(xùn)練。這種方法比較簡單，但在樣本集非常大的時(shí)候，重新訓(xùn)練的周期較長，且規(guī)則更新速度非常慢，影響學(xué)習(xí)的效率，不能滿足實(shí)時(shí)郵件過濾要求。本文提出的增量式郵件過濾方法針對錯(cuò)判和未識(shí)別樣本的情況，能從矛盾的郵件決策信息表中提取帶有置信度的決策規(guī)則，從而實(shí)現(xiàn)郵件規(guī)則集的動(dòng)態(tài)更新。

基于粗糙集的自主式增量郵件過濾方法需要經(jīng)過以下兩個(gè)步驟：

（1） 根據(jù)粗糙集的方法：郵件決策信息表[→]數(shù)據(jù)預(yù)處理[→]屬性約簡[→]值約簡[→]規(guī)則集，抽取數(shù)據(jù)集進(jìn)行匹配，記錄匹配過程中出現(xiàn)的錯(cuò)判和未識(shí)別樣本。

（2） 將上述反饋的錯(cuò)判、未識(shí)別樣本加入新增樣本訓(xùn)練集中，將計(jì)算樣本的置信度加入到原始規(guī)則集中。

對于步驟（1）如何獲得原始規(guī)則的過程，文獻(xiàn)[10]中已做詳盡表述。對于步驟（2），具體描述如下：設(shè)[S=U，C?D，V，f]為一郵件決策信息表，[R]是屬性約簡，[M]是最小規(guī)則集，對于[y∈U]，假設(shè)其對應(yīng)的規(guī)則為[θy→ψy]，新樣本為錯(cuò)判和未識(shí)別的郵件樣本[x：θx→ψx]加入[U]中，其樣本數(shù)量為[r]。若[x]的某些條件屬性特征[θx]與[y]中的條件屬性特征[θy]相同，而決策屬性特征出現(xiàn)不一致時(shí)，重新計(jì)算原始規(guī)則的置信度，將原始規(guī)則的置信度由[αy=X?YX]（見定義2，3）更新為[αy=X?YX+r]，同時(shí)計(jì)算決策表局部最小確定性[αc]，將其作為閾值，對原始規(guī)則和矛盾樣本的置信度進(jìn)行比較，若原始規(guī)則的置信度小于閾值，則矛盾樣本的決策屬性特征值經(jīng)約簡后替換原始規(guī)則的決策屬性特征值。若[x]的某些條件屬性特征與[y]中的條件屬性特征不同且決策屬性特征也不一致，將[x]屬性約簡后加入到規(guī)則集中。具體算法ILRS（Incremental Learning Algorithm Based on Rough Set）表示如下：

輸入：郵件規(guī)則集[M]，新增樣本[x]。

輸出：更新后的規(guī)則集[M′]。

Step1：根據(jù)原郵件規(guī)則集中的規(guī)則對新增對象[x]進(jìn)行匹配，匹配結(jié)果分為2種情況。

（1） 若[x：θx→ψx]的條件屬性特征和已有規(guī)則[θy→ψy]匹配，而決策屬性特征不匹配，即[?y∈U，θx≡θy，ψx≠ψy]出現(xiàn)矛盾樣本，轉(zhuǎn)向Step2。

（2） 若[x]的條件屬性特征和已有規(guī)則[y]不匹配，且決策屬性也不匹配，即[?y∈U，θx≠θy，ψx≠ψy]，則轉(zhuǎn)到Step3。

Step2：新增反饋樣本[x]的置信度為：[αx=rX+r]，已有規(guī)則[y]的置信度更新為[αy=X?Y+rX+r]，比較置信度[αy]、[αx]與局部最小確定性[αc]的大小。

（1） 若[αx>αc≥αy]，則將已有郵件規(guī)則的決策屬性值取反（Spam date語料中垃圾郵件的決策屬性為0，非垃圾郵件的決策屬性為1），且其對應(yīng)的郵件置信度更新為[α∧=rX+r]。

（2） 若[αy>αx≥αc]，則原規(guī)則集M不變。

Step3：將新增樣本屬性約簡后加入到規(guī)則集M中。

ILRS算法流程圖如圖1所示。

圖1 ILRS算法流程圖

3 實(shí)驗(yàn)仿真

本文抽取UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的垃圾郵件數(shù)據(jù)集Spambase[12]進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)集包含4 601個(gè)實(shí)例，其中包括1 813封垃圾郵件，2 788封非垃圾郵件，每個(gè)實(shí)例分別用58個(gè)特征屬性來描述（包括57個(gè)條件屬性特征和1個(gè)決策屬性特征），用0，1對垃圾郵件和非垃圾郵件分別進(jìn)行標(biāo)識(shí)。以下實(shí)驗(yàn)分為兩個(gè)部分：測試1為增量前后的對比實(shí)驗(yàn)，測試2為ILRS算法與決策樹ID4算法的增量式電子郵件學(xué)習(xí)效果的比較。

3.1 增量前后的實(shí)驗(yàn)對比

從Spambase的4 601條實(shí)例中隨機(jī)抽取含有500，1 000，1 500，2 000，2 500，3 000，3 500，4 000，4 500個(gè)樣本的9個(gè)數(shù)據(jù)集，進(jìn)行對比實(shí)驗(yàn)。

具體實(shí)驗(yàn)步驟如下：

Step1：將原始數(shù)據(jù)集中隨機(jī)抽取50%郵件樣本用粗糙集方法進(jìn)行屬性約簡、值約簡得到規(guī)則集；

Step2：用Step1中得到的規(guī)則集對剩下的50%郵件樣本進(jìn)行識(shí)別，記錄反饋的錯(cuò)誤識(shí)別和未識(shí)別的樣本；

Step3：對Step2中錯(cuò)判和未識(shí)別的郵件樣本進(jìn)行增量式學(xué)習(xí)，得到更新后的規(guī)則集；

Step4：在Spambase數(shù)據(jù)集中重新提取與訓(xùn)練集數(shù)量相同的樣本作為測試集，將第3步得到的更新后的規(guī)則集用測試集進(jìn)行測試，得到正確識(shí)別率、未識(shí)別率和規(guī)則個(gè)數(shù)。表1中，各個(gè)符號(hào)的含義如下：N#為郵件樣本數(shù)量；RR（%）為郵件樣本正確識(shí)別率；NR（%）為未識(shí)別率；GR為規(guī)則個(gè)數(shù)。

表1 算法有效性測試

圖2顯示增量學(xué)習(xí)后的正確識(shí)別率有較大提高，表1中的未識(shí)別率也較學(xué)習(xí)前明顯降低。

圖2 正確識(shí)別率的測試

3.2 ILRS算法與ID4方法的實(shí)驗(yàn)對比

為了進(jìn)一步驗(yàn)證算法的有效性，將ILRS算法和決策樹ID4算法作對比測試。實(shí)驗(yàn)步驟同實(shí)驗(yàn)3.1，原始數(shù)據(jù)樣本為測試集，記錄運(yùn)算時(shí)間T（s）、正確識(shí)別率RR（%）、錯(cuò)誤識(shí)別率WR（%）及規(guī)則個(gè)數(shù)GR。實(shí)驗(yàn)結(jié)果如表2所示。

表2 ILRS算法與ID4算法比較

從圖3、圖4可見，在進(jìn)行增量式學(xué)習(xí)時(shí)粗糙集方法ILRS在規(guī)則個(gè)數(shù)較少的情況下，對郵件樣本的正確識(shí)別率高于ID4算法。

圖3 正確識(shí)別率的比較

圖4 規(guī)則個(gè)數(shù)對比圖

4 結(jié) 論

本文在粗糙集理論的基礎(chǔ)上，提出了一種增量式的郵件過濾方法，即將學(xué)習(xí)后反饋的錯(cuò)判和未識(shí)別郵件信息作為新增樣本進(jìn)行再學(xué)習(xí)，把郵件決策信息表局部最小確定性作為閾值與矛盾規(guī)則的置信度進(jìn)行比較，從而更新規(guī)則。實(shí)驗(yàn)表明，增量學(xué)習(xí)后對郵件樣本的正確識(shí)別率明顯提高，錯(cuò)誤識(shí)別率有所降低，并且經(jīng)過實(shí)驗(yàn)對比可以看出，本文提出的ILRS算法比ID4算法提取的規(guī)則數(shù)量少近3倍，對郵件的正確識(shí)別率卻高出10%～20%，從而證明了該方法的有效性。

參考文獻(xiàn)

[1] 楊峰，曹麒麟，段海新.基于DNS Blocklist的反垃圾郵件系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2003（7）：11?12.

[2] PROVOST J. Naive?Bayes vs rule?learning in classification of email [D]. Austin， USA： Department of Computer Sciences， University of Texas， 1999.

[3] DRUCKER H， WU D， VAPNIK V N. Support vector machines for spam categorization [J]. IEEE Transactions on Neural Networks， 1999， 10： 1048?1054.

[4] TRETYAKOV Konstantin. Machine learning techniques in spam filtering data mining problem?oriented seminar [J]. MTAT， 2004， 177： 60?79.

[5] 于洪，李志君，唐宏，等.電子郵件過濾系統(tǒng)的粗糙集分析模型[J].計(jì)算機(jī)工程與應(yīng)用，2003（15）：47?48.

[6] 劉洋，杜孝平，羅平，等.垃圾郵件的智能分析、過濾及Rough集討論[C]//2002年第十二屆中國計(jì)算機(jī)學(xué)會(huì)網(wǎng)絡(luò)與數(shù)據(jù)通信學(xué)術(shù)會(huì)議.武漢：中國計(jì)算機(jī)學(xué)會(huì)，2002：515?521.

[7] 於東軍，王士同，楊靜宇.一種增量式規(guī)則提取算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2004，25（1）：79?81.

[8] 邱兆雷，王愛云，陳傳臻.基于變精度粗集和搜索樹的增量式規(guī)則獲取算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（14）：163?165.

[9] 付長龍，杜旭輝，姚全珠.一種基于概率粗糙集模型的增量式規(guī)則學(xué)習(xí)算法[J].計(jì)算機(jī)科學(xué)，2008，35（5）：143?146.

[10] 王國胤.Rough集理論與知識(shí)獲取[M].西安：西安交通大學(xué)出版社，2001.

[11] 王國胤，何曉.一種不確定性條件下的自主式知識(shí)學(xué)習(xí)模型[J].軟件學(xué)報(bào)，2003，14（6）：1096?1102.

[12] ZHENG Z， WANG G Y. RRIA： a rough set and rule tree based incremental knowledge Algorithm [J].Fundamental Information，2004， 59（2/3）： 299?313.