王友衛(wèi) 劉元寧 鳳麗洲 朱曉冬

(吉林大學 計算機科學與技術(shù)學院，吉林 長春 130012)

隨著網(wǎng)絡技術(shù)的迅速發(fā)展，電子郵件已成為人們?nèi)粘Ｉ钪兄匾耐ㄐ攀侄沃?日益增長的垃圾郵件常常附載大量虛假甚至危害社會穩(wěn)定與安全的信息.垃圾郵件在線識別具有區(qū)別于傳統(tǒng)文本分類的特點［1-2］:①識別過程需根據(jù)用戶興趣進行，同一封郵件在不同用戶甚至處于不同階段的相同用戶眼中可能得到不同的分類結(jié)果;②郵件識別屬于在線應用，因此對處理速度要求比較高;③在線郵件數(shù)量眾多、種類復雜，難以通過傳統(tǒng)人工標注形成通用的訓練樣本集.因此，如何有效解決以上問題成為垃圾郵件在線識別的首要任務.

增量學習方法已被廣泛應用于垃圾郵件在線識別［3］.與傳統(tǒng)方法相比，增量學習可以充分利用歷史學習結(jié)果，在不顯著降低樣本識別精度的前提下，減少訓練時間及傳統(tǒng)人工標注工作量.Syed 等［4］結(jié)合支持向量機(SVM)提出了Batch SVM 方法，該方法將增量樣本集與訓練集中支持向量集合并形成新的訓練集，對訓練集中的冗余樣本處理過于簡單，導致識別精度不高.王學軍等［5］將SVM 和主動學習結(jié)合起來，通過在增量學習過程中選擇正類樣本構(gòu)造新的最優(yōu)超平面;該算法能準確識別正類樣本，但針對負類樣本的識別精度較低.劉伍穎等［2］根據(jù)用戶反饋構(gòu)建個性化的用戶興趣模型，通過組合郵件模型分類器與興趣模型分類器結(jié)果實現(xiàn)對郵件的準確分類;該方法通過SVM 集成學習有效降低了特征向量空間維數(shù)，算法執(zhí)行速度較快.陳榮等［6］結(jié)合基于最優(yōu)標號和次優(yōu)標號(BvSB)的主動學習去挖掘那些對當前分類器模型最有價值的樣本進行人工標注，并借助帶約束條件的自學習(CST)方法進一步選擇待標注樣本，使得當標注代價較小時仍能夠獲得良好的分類性能.

現(xiàn)有增量學習方法普遍存在下面問題:①待標注樣本選擇過程往往需要訓練集中所有樣本參與，故計算復雜度較高;②傳統(tǒng)主動學習要求用戶對待標注樣本進行類別標注，忽略了用戶對樣本被正確分類的感興趣程度.針對這些問題，文中對傳統(tǒng)Batch SVM 方法做出改進，引入用戶興趣度的概念，實現(xiàn)了一種在線垃圾郵件識別新方法.

1 相關理論

1.1 Batch SVM 增量學習

Batch SVM 由Syed 等［4］提出，現(xiàn)已成為機器學習中一種典型的增量學習方法.如圖1 所示，該方法實現(xiàn)的具體步驟如下.

輸入:初始訓練樣本集合A0、增量樣本集合S1，S2，…，Sn;

(1)使用SVM 對A0進行訓練，獲得支持向量集合V0;

(2)將S1加入V0生成訓練集A1，對A1進行SVM 訓練繼而得到支持向量集合V1;

(3)重復類似步驟(2)的過程直到所有的增量樣本集合都已參加訓練.

輸出:以An為訓練集的分類器.

圖1 Batch SVM 增量學習方法Fig.1 Incremental learning method of Batch SVM

1.2 主動學習模型

主動學習目的是在增量訓練過程中有選擇地擴大有標記樣例集合和循環(huán)訓練的方法，使分類器獲得了更強的泛化能力.主動學習模型一般分為學習引擎和采樣引擎兩個部分［7］，如圖2 所示.

圖2 主動學習模型Fig.2 Active learning model

其中，學習引擎先在初始樣本集合上構(gòu)造初始分類器，接著對增量樣本進行分類;采樣引擎則使用不同的采樣算法從增量樣本集合中選擇樣本推薦給領域?qū)＜疫M行標注，并使用標注后樣本更新訓練集以進行迭代訓練.根據(jù)采樣算法不同，可將主動學習算法分為基于流的主動學習和基于池的主動學習.理論研究表明，相對于監(jiān)督學習而言，主動學習可以帶來指數(shù)級的樣本復雜度改善［8］.

2 垃圾郵件在線識別新方法

結(jié)合傳統(tǒng)Batch SVM 和主動學習理論實現(xiàn)了一種在線垃圾郵件識別新方法.給定訓練樣本集Ai及增量郵件集合Si(i=1，2，…，ns，ns為增量集數(shù)目)，文中方法的執(zhí)行過程如圖3 所示.

圖3 文中方法的執(zhí)行過程Fig.3 Executing process of the proposed method

2.1 特征提取、樣本訓練及識別

為了更好地兼顧算法執(zhí)行速度及特征提取效果，使用類間-類內(nèi)綜合測量特征提取方法(CMFS)進行特征提取［9］.將郵件訓練集Ai中不同單詞對應的CMFS 值按照從大到小的順序排列，選取前nf個單詞構(gòu)成特征詞集合Sfi.

序列最小優(yōu)化算法(SMO)由Microsoft Research的Platt［10］在1998年提出，它能快速地解決SVM 分類過程面臨的二次規(guī)劃問題.基于SMO 在處理稀疏矩陣方面的優(yōu)異表現(xiàn)，文中使用該算法對Ai進行訓練，接著使用所得分類器Oi對Si中每封郵件進行識別.SMO 相關參數(shù)設置如下:懲罰因子ζ=1.0，容忍極限值=0.001，核函數(shù)為RBF Kernal，核函數(shù)參數(shù)γ=0.5.

2.2 分類確定性評價

Joshi 等［11］通過在主動學習過程中統(tǒng)計未標注樣本屬于各個類別的概率大小來尋找那些分類結(jié)果最不確定的樣本，將其推薦給專家進行標注.該方法將Si中增量樣本sij與Ai中每個樣本進行比較，因此計算量較大.為此，文中考慮使用代表樣本，即從包含個已標注樣本的訓練集Ai中隨機選取/2個代表樣本(記為Ari)與sij進行比較.若Ari中垃圾郵件、合法郵件集合分別為Arsi、Arhi，則郵件sij(j=1，2，…，)分類確定性u(sij)計算如下:

式中，Sim ( sij，yk)、Sim ( sij，gl)分別表示郵件sij與郵件yk、gl之間的相似度，使用歐式距離表示.將Si中所有郵件對應u(sij)按照從小到大的順序排列，選擇前Nt(文中取Nt=10)封郵件(記為Sri)推薦給用戶.

2.3 樣本標注

文中主動學習方法中領域?qū)＜壹礊猷]件接收者(用戶).傳統(tǒng)主動學習方法強制用戶對待標注樣本的類別進行標注，而實際上，用戶未必對所有類型樣本都關心，且他們針對不同類型樣本的感興趣程度也不盡相同.文中提出了一種新的郵件樣本標注模型，特點有:①用戶可根據(jù)郵件內(nèi)容決定是否對其進行標注;②引入了用戶興趣度的概念來區(qū)分用戶對不同類型樣本的感興趣程度.

定義 用戶U 對郵件E 能被正確分類的感興趣程度，定義為U 對E 的用戶興趣度.

文中樣本標注模型將任意待標注郵件E 表示為具有以下4 個域的結(jié)構(gòu)形式，如圖4(a)所示.

(1)索引.郵件的唯一標識.

(2)內(nèi)容.郵件的文本內(nèi)容包括郵件主題，正文等信息.

(3)類別.E 為合法郵件還是垃圾郵件，記為C(E)，該部分由用戶進行手工標注.

(4)用戶興趣度.U 對E 的用戶興趣度記為I(E)，該部分由用戶進行手工標注.

給定Sri中郵件sij，則樣本標注過程如下:

(1)用戶查看sij內(nèi)容決定其對此類型樣本是否感興趣，若不，則丟棄sij(如圖4(b)所示)，否則，轉(zhuǎn)至步驟(2);

(2)用戶標注sij的類別C(sij)及用戶對sij被正確分類的興趣度I(sij)(默認為1).I(sij)由用戶根據(jù)經(jīng)驗給出，如:若用戶對sij內(nèi)容特別感興趣，說明他對sij分類結(jié)果正確與否特別關注，故可標記I(sij)=1.0，如圖4(c)所示.同理，若用戶對sij內(nèi)容感興趣程度一般，則可標記I(sij)=0.5，如圖4(d)所示;若用戶對sij內(nèi)容有一點感興趣，則可標記I(sij)=0.3，依此類推.

(3)重復執(zhí)行步驟(1)、(2)直至遍歷完Sri中的所有郵件，至此便生成了標注郵件集合Sdi對應的標注模型實例集合S'di.

圖4 文中方法的郵件標注模型及實例Fig.4 Email labeling model and examples of the proposed method

2.4 訓練樣本集更新

傳統(tǒng)主動學習訓練樣本集更新時將用戶標注后所有樣本直接加入原始訓練集，一方面使得訓練集樣本數(shù)量增長較快;另一方面無法有效區(qū)分不同類型樣本分類正確與否對用戶造成的影響(例如:相對于垃圾郵件而言，用戶對合法郵件被正確分類的需求更高).文中提出了一種基于“輪盤賭”［12］的樣本加入方法，針對已標注的郵件集合Sdi處理步驟如下.

1)為保證合法郵件優(yōu)先于垃圾郵件被加入訓練集，設置權(quán)值μ(0 ＜μ ＜1，文中取μ=0.9).

2)根據(jù)2.3 節(jié)樣本標注結(jié)果，獲得Sdi對應的標注模型實例集合S'di;

3)針對Sdi中每封郵件sij，先從S'di中獲得與之對應的用戶興趣度I(sij)，接著計算sij加入Ai的概率Pij:

(1)if C(sij)=ham，then Pij=I(sij)

(2)else Pij=I(sij)* μ(0 ＜μ ＜1)

(3)endif

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集與評價方法

將常用于在線仿真的非加密英文郵件TREC2007(包含50 199 封垃圾郵件、25 220 封合法郵件)作為實驗數(shù)據(jù)集［13］.去除郵件附件、標簽、郵件頭、停用詞等信息，并使用Porter Stemming 算法進行詞形還原［14］.設置特征提取的對應特征向量維數(shù)nf=600，測試集數(shù)目nt=5.為仿真在線學習過程，保證算法針對初始訓練集A0的訓練時間、針對增量樣本集Si(0 ＜i≤ns)的學習時間、針對測試集Tj(0 ＜j≤nt)的測試時間滿足圖5 所示的先后關系.進一步地，在對Tj(0 ＜j≤nt)進行仿真測試之前，先由用戶按照文中郵件標注模型對Tj中每封郵件進行標注，生成標注模型實例集合T'j.

圖5 初始訓練集A0、增量樣本集Si 及測試集Tj 的時間關系Fig.5 Time relationship among initial training corpus A0，incremental corpus Si and testing corpus Tj

基于傳統(tǒng)垃圾郵件識別算法性能評價標準［15］，文中提出了一種結(jié)合用戶興趣度的垃圾郵件識別召回率(r)、準確率(p)評價新方法.針對標注模型實例集合T'j(0 ＜j≤nt)，若T'j中屬垃圾郵件的模型實例集合記為T'js，屬合法郵件的模型實例集合記為T'jh，則r、p 定義如下:

式中，α 為用戶對某郵件的興趣度，Φs為T'js中所有郵件對應的用戶興趣度集合，Φss為T'js中被正確分類的郵件對應的用戶興趣度集合，hs為T'jh中被錯分的郵件對應的用戶興趣度集合，ns(α)為T'js中對應興趣度為α 的郵件數(shù)目，nss(α)為T'js中對應興趣度為α 且被正確分類的郵件數(shù)目，nhs(α)為T'jh中對應興趣度為α 且被錯分的郵件數(shù)目.由式(2)知，r 越大，系統(tǒng)發(fā)現(xiàn)垃圾郵件的能力就越強;p 越大，合法郵件被漏讀的可能性就越小.

3.2 耗時分析

假設當前郵件訓練集Ai樣本數(shù)為，增量集Si樣本數(shù)為，對Ai進行SVM 訓練的耗時為tT(Ai)、從Si中選擇待標注樣本的耗時為tS(Si).表1 評估了不同主動學習方法對應的tT(Ai)、tS(Si)值.其中，Sdi為用戶標注后樣本集，Spdi為文中實際加入訓練集的樣本集，tV(A)表示對樣本集A 進行SVM 訓練所需時間，tC()表示計算樣本集合Ai-1中所有樣本的分類確定性所需時間，tO()表示對個元素排序所需時間，δ表示CST 樣本選擇過程所需時間.可見，由于存在SpdiSdi，文中方法的tT(Ai)值不大于Joshi 方法、Chen 方法;進一步知，由于tC()過程耗時依賴于大小，故文中方法所得tS(Ai)值將小于另外兩種方法.

表1 不同主動學習方法對應的tT(Ai)、tS(Si)值Table 1 tT(Ai)and tS(Si)values corresponding to different active learning methods

3.3 性能測試

圖6 10 個用戶在不同ns 值下對應的ra、pa 值Fig.6 ra and pa values of 10 users with different ns values

3.3.1 多用戶情況下的性能測試

表2 不同方法所得及值Table 2 andvalues obtained by different methods

表2 不同方法所得及值Table 2 andvalues obtained by different methods

方法 r t p t r p Batch SVM 0.933 0.929 0.934 0.933 Wang 方法 0.971 0.934 0.978 0.937 Joshi 方法 0.969 0.966 0.968 0.971 Chen 方法 0.964 0.967 0.966 0.967文中方法0.966 0.971 0.974 0.976

3.3.2 單用戶情況下的性能測試

單用戶仿真實驗時應考慮用戶興趣遷移對學習效果的影響［16］.先從S1-S100中挑選5 個典型郵件內(nèi)容主題，接著給出某一用戶在不同增量學習階段針對這些主題的興趣度變化過程，如表3 所示.在增量學習不同階段由用戶自行對Tj(1 ＜j≤nt)進行標注，先使用傳統(tǒng)評價方法計算垃圾郵件識別召回率均值、準確率均值，再使用文中新評價方法計算召回率均值、準確率均值，結(jié)果如表4 所示.可見，相對于傳統(tǒng)評價方法，新評價方法下文中方法的召回率均值、準確率均值提升明顯;文中方法所得值雖低于Wang 方法，但明顯高于其他方法;文中方法所得值為0.979，比全局次高值大0.010.綜上說明:新評價方法反映了用戶興趣度對分類結(jié)果的影響;文中方法在增量學習不同階段區(qū)分了用戶興趣度，有效降低了用戶興趣遷移對算法識別效果的影響.

表3 不同增量學習階段用戶興趣度變化Table 3 Changes of user interest degree at different incremental learning stages

表4 不同方法所得 及值Table 4 andvalues obtained by different methods

表4 不同方法所得 及值Table 4 andvalues obtained by different methods

方法 r t p t r p Batch SVM 0.921 0.909 0.913 0.897 Wang 方法 0.972 0.933 0.976 0.936 Joshi 方法 0.969 0.965 0.962 0.969 Chen 方法 0.956 0.958 0.955 0.961文中方法0.962 0.959 0.971 0.979

3.3.3 不同算法耗時對比實驗

定義樣本訓練平均耗時w 及待標注樣本選擇平均耗時z 如下:

式中，θ(Ai)為對Ai進行SVM 訓練的耗時，?(Si)為主動學習過程中從Si中選擇待標注樣本的耗時.使用不同方法分別計算相應z 的值及當ns=20，40，60，80，100 時對應的w 值，結(jié)果如圖7(a)-7(d)所示.可見，Batch SVM 方法所得w 值受取值影響較大，與關系不大;而其他方法w 取值與關系密切，=200 時所得w 值較=50 時普遍偏高.由于使用了“輪盤賭”方法抑制訓練集規(guī)模的快速增長，故相對于Wang 方法、Joshi 方法、Chen 方法而言，文中方法的樣本訓練時間較短，且當增量集樣本數(shù)目較大時，在一定程度內(nèi)(ns≤40)優(yōu)于Batch SVM.對比結(jié)合主動學習的Joshi 方法、Chen方法及文中方法對應的z 值發(fā)現(xiàn)，文中方法的結(jié)果明顯偏小，進一步驗證了該方法在降低待標注樣本選擇耗時方面的有效性.

4 結(jié)語

提出了一種基于SVM 增量學習的垃圾郵件識別新方法，主要內(nèi)容如下:①為降低尋找待標注郵件耗時，通過從已標注訓練集中隨機選擇代表樣本計算郵件的分類確定性;②提出了用戶興趣度的概念和新樣本標注模型，將用戶針對郵件被正確分類的感興趣程度融入模型中;③結(jié)合用戶興趣度，使用“輪盤賭”方法更新郵件訓練集;④提出了結(jié)合用戶興趣度的分類器性能評價新標準.實驗結(jié)果證明:新樣本標注模型有效融合了用戶對郵件被正確分類的感興趣程度，“輪盤賭”訓練集更新方式在降低訓練集規(guī)模增長速度的同時保證了用戶感興趣郵件被優(yōu)先加入;新方法針對垃圾郵件識別效果好，樣本訓練及待標注樣本選擇速度快，具有較高的實用價值.

圖7 ns 取不同值時不同方法所得w、z 值Fig.7 w and z values obtained by different methods with different ns values

［1］Liu W Y，Wang T.Active learning for online spam filtering［J］.Information Retrieval Technology，2008，4993:555-560.

［2］劉伍穎，王挺.集成學習和主動學習相結(jié)合的個性化垃圾郵件過濾［J］.計算機工程與科學，2011，33(9):34-41.Liu Wu-ying，Wang Ting.Ensemble learning and active learning based personal spam email filtering［J］.Computer Engineering ＆ Science，2011，33(9):34-41.

［3］Bouchachia A，Gabrys B，Sahel Z.Overview of some incremental learning algorithms［C］∥Proceedings of IEEE International Conference on Fuzzy Systems.London:IEEE，2007:1-6.

［4］Syed N，Liu H，Sung K.Handling concept drifts in incremental learning with support vector machines［C］∥Proceedings of the Workshop on Support Vector Machines at the International Joint Conference on Articial Intelligence(IJCAI-99).Stockholm:IJCAII and the Scandinavian AI Societies，1999:317-321.

［5］王學軍，趙琳琳，王爽.基于主動學習的視頻對象提取方法［J］.吉林大學學報:工學版，2013，43(3):51-54.Wang Xue-jun，Zhao Lin-lin，Wang Shuang.Video object extraction method based on active learning SVM ［J］.Journal of Jilin University:Engineering and Technology Edition，2013，43(3):51-54.

［6］陳榮，曹永鋒，孫洪.基于主動學習和半監(jiān)督學習的多類圖像分類［J］.自動化學報，2011，37(8):954-962.Chen Rong，Cao Yong-feng，Sun Hong.Multi-class image classification with active learning and semi-supervised learning［J］.Acta Automatica Sinica，2011，37(8):954-962.

［7］Wu Y，Kozintsev I，Bouguet J Y，et al.Sampling strategies for active learning in personal photo retrieval［C］∥Proceedings of ICME 2006.Piscataway:IEEE，2006:529-532.

［8］吳偉寧，劉揚，郭茂祖，等.基于采樣策略的主動學習算法研究進展［J］.計算機研究與發(fā)展，2012，49(6):1162-1173.Wu Wei-ning，Liu Yang，Guo Mao-zu，et al.Advances inactive learning algorithms based on sampling strategy［J］.Journal of Computer Research and Development，2012，49(6):1162-1173.

［9］Yang J M，Liu Y N，Zhu X D，et al.A new feature selection based on comprehensive measurement both in inter-category and intra-category for text categorization［J］.Information Processing ＆ Management，2012，48(4):741-754.

［10］Platt John.Sequential minimal optimization:a fast algorithm for training support vector machines［R］.［S.l.］:Microsoft Research，1998.

［11］Joshi A J，Porikli F，Papanikolopoulos N.Multi-class active learning for image classification［C］∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Miami:IEEE，2009:2372-2379.

［12］夏桂梅，曾建潮.一種基于輪盤賭選擇遺傳算法的隨機微粒群算法［J］.計算機工程與科學，2007，29(6):51-54.Xia Gui-mei，Zeng Jian-chao.A stochastic partical swarm optimization algorithm based on the genetic algorithm of roulette wheel selection ［J］.Computer Engineering ＆Science，2007，29(6):51-54.

［13］Cormack G V.TREC 2007 spam track overview［C］∥Proceedings of the 16th Text Retrieval Conference.Gaithersburg:National Institute of Standards and Technology，2007:500-274.

［14］Porter M F.An algorithm for suffix stripping［J］.Program:Electronic Library and Information Systems，1980，14(3):130-137.

［15］Yang J M，Liu Y N，Liu Z，et al.A new feature selection algorithm based on binomial hypothesis testing for spam filtering［J］.Knowledge-Based Systems，2011，24(6):904-914.

［16］Bouneffouf D，Bouzeghoub A，Gan?arski A L.Following the user's interests in mobile context-aware recommender systems:the hybrid-ε-greedy algorithm［C］∥Proceedings of 26th International Conference on Advanced Information Networking and Applications Workshops.Fukuoka:IEEE，2012:657-662.