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

徐丹+韓艷杰+寇曼曼

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

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

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

0 引 言

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

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

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

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

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

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

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

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

定義2（不分明關(guān)系）：假設(shè)屬性集[P∈R]，對象[X，Y∈U]，對于每個[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）]是一個等價關(guān)系。這樣，屬性集P可以認(rèn)為是用等價關(guān)系（在該屬性集上的取值相等）表示的一個知識的名稱[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í)識別后反饋的錯判和未識別信息作為新樣本進行再訓(xùn)練，原始的非增量式學(xué)習(xí)方法是將錯判和未識別樣本放入原始信息決策表，進行重新訓(xùn)練。這種方法比較簡單，但在樣本集非常大的時候，重新訓(xùn)練的周期較長，且規(guī)則更新速度非常慢，影響學(xué)習(xí)的效率，不能滿足實時郵件過濾要求。本文提出的增量式郵件過濾方法針對錯判和未識別樣本的情況，能從矛盾的郵件決策信息表中提取帶有置信度的決策規(guī)則，從而實現(xiàn)郵件規(guī)則集的動態(tài)更新。

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

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

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

對于步驟（1）如何獲得原始規(guī)則的過程，文獻[10]中已做詳盡表述。對于步驟（2），具體描述如下：設(shè)[S=U，C?D，V，f]為一郵件決策信息表，[R]是屬性約簡，[M]是最小規(guī)則集，對于[y∈U]，假設(shè)其對應(yīng)的規(guī)則為[θy→ψy]，新樣本為錯判和未識別的郵件樣本[x：θx→ψx]加入[U]中，其樣本數(shù)量為[r]。若[x]的某些條件屬性特征[θx]與[y]中的條件屬性特征[θy]相同，而決策屬性特征出現(xiàn)不一致時，重新計算原始規(guī)則的置信度，將原始規(guī)則的置信度由[αy=X?YX]（見定義2，3）更新為[αy=X?YX+r]，同時計算決策表局部最小確定性[αc]，將其作為閾值，對原始規(guī)則和矛盾樣本的置信度進行比較，若原始規(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]進行匹配，匹配結(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 實驗仿真

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

3.1 增量前后的實驗對比

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

具體實驗步驟如下：

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

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

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

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

表1 算法有效性測試

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

圖2 正確識別率的測試

3.2 ILRS算法與ID4方法的實驗對比

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

表2 ILRS算法與ID4算法比較

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

圖3 正確識別率的比較

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

4 結(jié) 論

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

參考文獻

[1] 楊峰，曹麒麟，段海新.基于DNS Blocklist的反垃圾郵件系統(tǒng)的設(shè)計與實現(xiàn)[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].計算機工程與應(yīng)用，2003（15）：47?48.

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

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

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

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

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

[11] 王國胤，何曉.一種不確定性條件下的自主式知識學(xué)習(xí)模型[J].軟件學(xué)報，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.