一種基于ECVM的Tri-training半監督垃圾郵件檢測算法

卜華龍，夏 靜，鄭尚志

巢湖學院信息工程學院，安徽巢湖，238000

一種基于ECVM的Tri-training半監督垃圾郵件檢測算法

卜華龍，夏 靜，鄭尚志

巢湖學院信息工程學院，安徽巢湖，238000

為提高垃圾郵件檢測精度，提出一種基于ECVM的Tri-training半監督垃圾郵件檢測算法，兼顧了Tri-training算法的準確性和ECVM算法處理大規模數據的高效性特點，可以降低算法的時間和空間復雜度，提高未標記數據的利用率，適應垃圾郵件數據的規模大、標記數據少、稀疏性強等特點。Matlab實驗表明Tri-training+ECVM比傳統的Tri-training+SVM在準確率和時間復雜度指標上都有大幅度的提升。

Tri-training；ECVM；垃圾郵件檢測；半監督學習

垃圾郵件檢測是網絡安全的典型應用之一。通常根據郵件的內容，采用相應的分類學習算法將郵件歸至某類別[1]。基于內容的文本分類方法可以分成數據預處理、維數約簡和分類建模三個主要步驟[2]。其數據預處理的方式是根據郵件格式，剔除無關結構信息，保留核心內容，如郵件標題、郵件發送人和正文，并將其記錄成一條特征向量；維數約簡用于實現壓縮此特征向量維數的目的；分類建模主要實現分類器的建模過程。傳統的分類學習可分成監督、無監督學習和半監督學習[3]。其中半監督學習結合了監督和無監督學習的優點，同時利用標記和無標記數據，已經成為當前數據挖掘、機器學習等領域的主要研究方向[4]。

作為文本分類等領域的主流學習算法，支持向量機(support vectors machine，SVM)具有其他多數算法不具有的檢測精度，因此，被廣泛改造成半監督環境下的學習算法并取得了很好的效果，在文本、生物信息挖掘等領域中得到了廣泛使用[5]。

然而，在現實環境下，垃圾郵件檢測數據集規模龐大、標記樣本少、特征稀疏等，具體表現為數據點數量極大，樣本標簽大部分未標記，特征空間維度高且很多特征值為0。由于SVM算法時間復雜度為o(n3)，n是訓練樣本個數，導致SVM處理大規模垃圾郵件檢測數據集時效率不夠[6]，給傳統SVM分類學習器帶來嚴重挑戰。

本文提出基于Tri-training和ECVM的半監督垃圾郵件檢測算法，試圖運用Tri-training算法解決標記樣本過少問題，并運用基于廣泛內核CVM算法(extensive kernel core vector machine ，ECVM)來大幅縮減數據集規模的影響，節約SVM的求解時間。在仿真實驗中，安排Tri-training和Co-training、CVM和ECVM算法比較等多個方案，探討本文算法在垃圾郵件檢測中的優勢。

1 算法必要性分析

1.1 Tri-training算法分析

協同訓練(Co-training)算法是基于已標記訓練樣本有限前提下的一類半監督學習算法，它強調利用易獲取的未標記樣本信息提高學習精度[7]。Co-training假設數據含有兩個相異充分冗余視圖，且每個視圖的特征集都具有訓練出足夠精度分類學習器[8]的能力。Co-training具有較強的模型限制，當數據不滿足充分冗余視圖假設時，算法存在可用性缺陷。

對此，周志華等人提出Tri-training算法。該算法不需要充分冗余視圖假設，利用三個分類器進行協同訓練，既保留了Co-training的協同優勢又避免了驗證時間長、分類算法要求苛刻等問題[9]。Tri-training算法雖然比Co-training算法多了一個分類器，但不再需要交叉驗證，降低了算法的時間復雜度。另外，增加一個分類器也會提高集成效果。該算法雖然對單個分類器的精度要求不高，但算法的結構決定其對分類器的時間復雜度要求很高，如前所述，支持向量機SVM在實際處理大規模數據集時，時間復雜度和空間復雜度較高，導致分類器因支持向量多而變慢[10](傳統的SVM算法時間復雜度為o(n3)，n是訓練樣本個數)，造成SVM處理大規模垃圾郵件檢測數據集時效率不夠，對此，本文引入ECVM，以解決高維和數據稀疏問題。

1.2 支持向量機與基于廣泛內核的CVM算法分析

SVM算法核心是將訓練數據表示為S={(x,y)}?{Rn×(-1,1)}l，并定義分類判別超平面y=sgn(+b)，w是權重向量，b為偏差，然后利用Mercer定理將原始數據集投影(非線性映射)至高維甚至是無窮維特征空間上，再用線性學習機分解此特征空間,以解決具有高度非線性的原始樣本集分類與回歸等問題，常用核函數有高斯核函數K(x,z)=exp(-‖x-z‖2/σ2)等[11]。

作為一種主要的SVM計算方法，基于最小閉包球的CVM算法采用近似最優解的概念來求解SVM，大幅提高了支持向量機的學習精度，然而CVM算法要求核函數滿足k(x,y)=K(‖x-y‖)的各方同性假設，從而限制了可用性，且時間復雜度較高[12-13]。王奇安等人提出基于最小閉包球的改進算法ECVM。該算法同樣采用求解SVM的近似最優解，且消除了同向性核方法假設，簡化了新球心的計算，不再需要解決每次迭代工程中的QP問題，ECVM的時間復雜度與樣本集大小n呈線性關系，空間復雜度與樣本大小無關[14]。

2 基于Tri-training和ECVM的垃圾郵件檢測算法

垃圾郵件檢測通過分類器判斷正常郵件和垃圾郵件，數據的采集、分析和處理具有以下特點和困難：

(1)規模龐大，數據集規模經常達到上萬級別；

(2)標記樣本少，大部分樣本沒有事先標記過；

(3)特征空間維度高且稀疏性強。

本文利用ECVM解決規模龐大和特征稀疏問題，提高算法效率；通過Tri-training算法解決標記樣本過少問題。主要框架如圖1所示。

具體工作如下：

(1)數據規范和歸一化，以防止數據特征間的數量級不一。首先采用Z_Score類方法規范化(公式1)樣本特征，再設計歸一化函數(公式2)將各特征值歸一化至[0,1]區間:

(1)

xi=(xi-xmin)/(xmax-xmin)

(2)

圖1 算法框架圖

(2)初始化標記數據集U和未標記數據集L，將U分成標記訓練數據集SLtrain和測試集SVtrain，令SLtrain=L。

(3)協同訓練，該過程主要基于Tri-training協同訓練三個ECVM分類器，為體現分類器差異，這里的分類器核函數分別采用Gauss、Poly和Rbf，具體過程如下表1所示。

表1 算法步驟

(4)垃圾郵件檢測，分別使用訓練好的C1、C2和C3分類器對新未標記數據進行預測，采用少數服從多數的原則進行協同投票，以決定最終標簽。

3 實驗與分析

實驗數據集采用2005-Jul，包含20308個垃圾郵件和9042個正常郵件[15]。為模擬半監督學習環境，首先合并這29400個樣本，并打亂分布結構得到數據集C，再將C的1/10作為標記訓練集SUtrain，剩余部分4/5作為未標記數據集SLtrain，1/5用作測試分類器的SVtrain。

檢測評價準則采用最常用的召回率R和準確率P[16]，垃圾郵件檢測只有表2中4種結果。

表2 系統檢測分類表

本文主要研究算法相對Co-training算法和CVM算法的效果，因此，限定參數為Matlab工具箱中的默認參數，實驗環境為Matlab。Tri-training算法中的迭代次數K=10，β=5%，ECVM中參數ε值(半徑選取)=10-7。

首先，對比Co-training+ECVM與Tri-training+ECVM的檢測準確率，表3所示為平均值，共重復3次。從分類檢測的召回率和準確率兩個指標都可以看出Tri-training+ECVM能提高精度2%～3.4%。

表3 Co-training與Tri-training(召回率與準確率)

其次，對比了ECVM與CVM的檢測準確率，共分成Co-training+ECVM，Co-training+CVM，Tri-training+ECVM和Tri-training+CVM四種情況，表4所示為召回率和準確率的平均結果。從分類檢測的召回率和準確率兩個指標反映出ECVM至少比CVM提高精度1.4%以上。

表4 CVM與ECVM對比(召回率與準確率)

最后，雖然理論研究已證明了ECVM和傳統的SVM的時間效果，但此處還是統計了實驗的時間復雜度(表5)。通過對比CVM和ECVM的CPU使用時間，可以明顯發現ECVM比CVM消耗時間要低，考慮到ECVM的時間復雜度是樣本規模的線性函數，這個現象是非常正常的。

表5 CVM與ECVM對比(CPU時間，單位s)

4 結束語

針對垃圾郵件數據集規模大、標記數據少和稀疏性強等問題，本文提出使用Tri-training算法的協同訓練方法提高未標記數據的利用率，并結合ECVM算法處理大規模數據的高效性來處理半監督垃圾郵件檢測問題，試圖通過Tri-training算法解決標記樣本過少問題，并通過基于廣泛內核CVM算法以大幅縮減數據集規模的影響，節約SVM的求解時間。基于Matlab的多個實驗對比說明準確率和降低時間復雜度都有所提高，驗證了算法的有效性。

[1]陳凱.反垃圾郵件技術的研究與實踐[D].北京:北京郵電大學軟件學院，2006:2-19

[2]蘇金樹，張博鋒，徐昕.基于機器學習的文本分類技術研究進展[J].軟件學報，2006，17(9):1848-1859

[3]林冬茂.數據挖掘技術在垃圾郵件檢測中的應用[J].計算機仿真，2012，29(2):120-125

[4]牛罡，羅愛寶， 商琳.半監督文本分類綜述[J].計算機科學與探索，2011，5(4)：313-321

[5]李紅蓮，王春花，袁保宗，等.針對大規模訓練集的支持向量機的學習策略[J].計算機學報，2004，27(5):715-719

[6]袁鼎榮，鐘寧，張師超.文本信息處理研究述評[J].計算機科學，2011，38(12):9-13

[7]周志華.機器學習及其應用[M].北京：清華大學出版社，2006：1-201

[8]鄔書躍，余杰，樊曉平.基于Tri-training的入侵檢測算法[J].計算機工程， 2012，38(6):158-160[9]Zhou Zhihua，Li Ming.Tri-training:Exploiting Unlabeled Data Using Three Classifiers[J].IEEE Transactions on Knowledge and Data Engineering，2005，17(11):1529-1541

[10]李昆侖，張偉，代運娜.基于Tri-training的半監督SVM[J].計算機工程與應用，2009，45(22):103-106

[11]Cristianini N.支持向量機導論[M].李國正，王猛，曾華軍，譯.北京:電子工業出版社，2004：1-189

[12]龐雄昌，王吉吉，韓鯤.基于CVM的入侵檢測[J].微計算機信息，2008，24(18):45-46

[13]Tsang I W，Andras K，James T，et al.Simpler core vector machines with enclosing balls[C]//New York:Proc of the Twenty-Fourth International Conference on Machine Learning(ICML)，2007:911-918

[14]王奇安，陳兵.基于廣泛內核的CVM算法的入侵檢測[J].計算機研究與發展，2012，49(5):974-981

[15]Quang-Anh Tran.2005-Jul dataset[DB/OL].[2016-02-03].http://www.ccert.edu.cn/spam/sa/datasets.htm

[16]秦玉平，耿姝，孫宗寶.基于C-SVM和KPCA的垃圾郵件檢測研究[J].計算機工程與應用，2010，46(19):94-96

(責任編輯：汪材印)

10.3969/j.issn.1673-2006.2016.08.029

2016-03-18

安徽省教育廳自然科學研究重點項目“基于deepweb 數據集成的企業情報個性化推送系統”(KJ2012A205)；安徽省教育廳自然科學研究重點項目“半監督冗余特征檢測技術”(KJ2016A502)；巢湖學院“計算機圖形學”課程開發項目(ch15yykc05)。

卜華龍(1980-)，安徽巢湖人，碩士，講師，主要研究方向：機器學習。

TP181

A

1673-2006(2016)08-0105-04