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

徐丹+韓艷杰+寇曼曼

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

關鍵詞： 垃圾郵件過濾； 粗糙集理論； 增量學習； ILRS算法

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

0 引 言

隨著Internet技術的快速發展，電子郵件在人們的生活中扮演著越來越重要的角色。人們之間大量的交流都通過電子郵件來進行，但是垃圾郵件的日益增多也成為困擾人們日常工作生活的一個難題，電子郵件過濾技術由此產生并成為阻止垃圾郵件的重要手段之一。有很多學者對電子郵件過濾方法進行了研究，常見的有以下三種：

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

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

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

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

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

1 相關基本概念

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

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

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

定義 4（條件分類對決策分類的確定性程度）：設決策表為[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]即為控制規則產生的閾值[11]。

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

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

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

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

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

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

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

輸出：更新后的規則集[M′]。

Step1：根據原郵件規則集中的規則對新增對象[x]進行匹配，匹配結果分為2種情況。

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

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

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

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

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

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

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

圖1 ILRS算法流程圖

3 實驗仿真

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

3.1 增量前后的實驗對比

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

具體實驗步驟如下：

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

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

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

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

表1 算法有效性測試

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

圖2 正確識別率的測試

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

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

表2 ILRS算法與ID4算法比較

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

圖3 正確識別率的比較

圖4 規則個數對比圖

4 結 論

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

參考文獻

[1] 楊峰，曹麒麟，段海新.基于DNS Blocklist的反垃圾郵件系統的設計與實現[J].計算機工程與應用，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] 于洪，李志君，唐宏，等.電子郵件過濾系統的粗糙集分析模型[J].計算機工程與應用，2003（15）：47?48.

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

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

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

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

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

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