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

卜華龍，夏 靜，鄭尚志

巢湖學(xué)院信息工程學(xué)院，安徽巢湖，238000

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

卜華龍，夏 靜，鄭尚志

巢湖學(xué)院信息工程學(xué)院，安徽巢湖，238000

為提高垃圾郵件檢測精度，提出一種基于ECVM的Tri-training半監(jiān)督垃圾郵件檢測算法，兼顧了Tri-training算法的準(zhǔn)確性和ECVM算法處理大規(guī)模數(shù)據(jù)的高效性特點(diǎn)，可以降低算法的時(shí)間和空間復(fù)雜度，提高未標(biāo)記數(shù)據(jù)的利用率，適應(yīng)垃圾郵件數(shù)據(jù)的規(guī)模大、標(biāo)記數(shù)據(jù)少、稀疏性強(qiáng)等特點(diǎn)。Matlab實(shí)驗(yàn)表明Tri-training+ECVM比傳統(tǒng)的Tri-training+SVM在準(zhǔn)確率和時(shí)間復(fù)雜度指標(biāo)上都有大幅度的提升。

Tri-training；ECVM；垃圾郵件檢測；半監(jiān)督學(xué)習(xí)

垃圾郵件檢測是網(wǎng)絡(luò)安全的典型應(yīng)用之一。通常根據(jù)郵件的內(nèi)容，采用相應(yīng)的分類學(xué)習(xí)算法將郵件歸至某類別[1]?；趦?nèi)容的文本分類方法可以分成數(shù)據(jù)預(yù)處理、維數(shù)約簡和分類建模三個(gè)主要步驟[2]。其數(shù)據(jù)預(yù)處理的方式是根據(jù)郵件格式，剔除無關(guān)結(jié)構(gòu)信息，保留核心內(nèi)容，如郵件標(biāo)題、郵件發(fā)送人和正文，并將其記錄成一條特征向量；維數(shù)約簡用于實(shí)現(xiàn)壓縮此特征向量維數(shù)的目的；分類建模主要實(shí)現(xiàn)分類器的建模過程。傳統(tǒng)的分類學(xué)習(xí)可分成監(jiān)督、無監(jiān)督學(xué)習(xí)和半監(jiān)督學(xué)習(xí)[3]。其中半監(jiān)督學(xué)習(xí)結(jié)合了監(jiān)督和無監(jiān)督學(xué)習(xí)的優(yōu)點(diǎn)，同時(shí)利用標(biāo)記和無標(biāo)記數(shù)據(jù)，已經(jīng)成為當(dāng)前數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域的主要研究方向[4]。

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

然而，在現(xiàn)實(shí)環(huán)境下，垃圾郵件檢測數(shù)據(jù)集規(guī)模龐大、標(biāo)記樣本少、特征稀疏等，具體表現(xiàn)為數(shù)據(jù)點(diǎn)數(shù)量極大，樣本標(biāo)簽大部分未標(biāo)記，特征空間維度高且很多特征值為0。由于SVM算法時(shí)間復(fù)雜度為o(n3)，n是訓(xùn)練樣本個(gè)數(shù)，導(dǎo)致SVM處理大規(guī)模垃圾郵件檢測數(shù)據(jù)集時(shí)效率不夠[6]，給傳統(tǒng)SVM分類學(xué)習(xí)器帶來嚴(yán)重挑戰(zhàn)。

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

1 算法必要性分析

1.1 Tri-training算法分析

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

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

1.2 支持向量機(jī)與基于廣泛內(nèi)核的CVM算法分析

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

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

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

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

(1)規(guī)模龐大，數(shù)據(jù)集規(guī)模經(jīng)常達(dá)到上萬級別；

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

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

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

具體工作如下：

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

(1)

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

(2)

圖1 算法框架圖

(2)初始化標(biāo)記數(shù)據(jù)集U和未標(biāo)記數(shù)據(jù)集L，將U分成標(biāo)記訓(xùn)練數(shù)據(jù)集SLtrain和測試集SVtrain，令SLtrain=L。

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

表1 算法步驟

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

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)數(shù)據(jù)集采用2005-Jul，包含20308個(gè)垃圾郵件和9042個(gè)正常郵件[15]。為模擬半監(jiān)督學(xué)習(xí)環(huán)境，首先合并這29400個(gè)樣本，并打亂分布結(jié)構(gòu)得到數(shù)據(jù)集C，再將C的1/10作為標(biāo)記訓(xùn)練集SUtrain，剩余部分4/5作為未標(biāo)記數(shù)據(jù)集SLtrain，1/5用作測試分類器的SVtrain。

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

表2 系統(tǒng)檢測分類表

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

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

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

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

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

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

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

4 結(jié)束語

針對垃圾郵件數(shù)據(jù)集規(guī)模大、標(biāo)記數(shù)據(jù)少和稀疏性強(qiáng)等問題，本文提出使用Tri-training算法的協(xié)同訓(xùn)練方法提高未標(biāo)記數(shù)據(jù)的利用率，并結(jié)合ECVM算法處理大規(guī)模數(shù)據(jù)的高效性來處理半監(jiān)督垃圾郵件檢測問題，試圖通過Tri-training算法解決標(biāo)記樣本過少問題，并通過基于廣泛內(nèi)核CVM算法以大幅縮減數(shù)據(jù)集規(guī)模的影響，節(jié)約SVM的求解時(shí)間?；贛atlab的多個(gè)實(shí)驗(yàn)對比說明準(zhǔn)確率和降低時(shí)間復(fù)雜度都有所提高，驗(yàn)證了算法的有效性。

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

[2]蘇金樹，張博鋒，徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào)，2006，17(9):1848-1859

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

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

[5]李紅蓮，王春花，袁保宗，等.針對大規(guī)模訓(xùn)練集的支持向量機(jī)的學(xué)習(xí)策略[J].計(jì)算機(jī)學(xué)報(bào)，2004，27(5):715-719

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

[7]周志華.機(jī)器學(xué)習(xí)及其應(yīng)用[M].北京：清華大學(xué)出版社，2006：1-201

[8]鄔書躍，余杰，樊曉平.基于Tri-training的入侵檢測算法[J].計(jì)算機(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]李昆侖，張偉，代運(yùn)娜.基于Tri-training的半監(jiān)督SVM[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(22):103-106

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

[12]龐雄昌，王吉吉，韓鯤.基于CVM的入侵檢測[J].微計(jì)算機(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]王奇安，陳兵.基于廣泛內(nèi)核的CVM算法的入侵檢測[J].計(jì)算機(jī)研究與發(fā)展，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].計(jì)算機(jī)工程與應(yīng)用，2010，46(19):94-96

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2016.08.029

2016-03-18

安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目“基于deepweb 數(shù)據(jù)集成的企業(yè)情報(bào)個(gè)性化推送系統(tǒng)”(KJ2012A205)；安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目“半監(jiān)督冗余特征檢測技術(shù)”(KJ2016A502)；巢湖學(xué)院“計(jì)算機(jī)圖形學(xué)”課程開發(fā)項(xiàng)目(ch15yykc05)。

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

TP181

A

1673-2006(2016)08-0105-04