基于多層grams的在線支持向量機的中文垃圾郵件過濾

沈元輔，沈躍伍

(1. 哈爾濱理工大學 圖書館，黑龍江 哈爾濱 150080；2. 哈爾濱理工大學 計算機科學與技術學院，黑龍江 哈爾濱 150080)

?

基于多層grams的在線支持向量機的中文垃圾郵件過濾

沈元輔1，沈躍伍2

(1. 哈爾濱理工大學 圖書館，黑龍江 哈爾濱 150080；2. 哈爾濱理工大學 計算機科學與技術學院，黑龍江 哈爾濱 150080)

該文提出一種多層grams特征抽取方法來提升基于在線支持向量模型的垃圾郵件過濾器。基于在線支持向量機模型的垃圾郵件過濾器在大規模垃圾郵件數據集已取得了很好的過濾效果，但與邏輯回歸模型相比，計算性能的耗時是巨大的，很難被工業界所運用。該文提出的多層grams特征抽取方法能夠有效減少特征數，抽取更精準有效的特征，大幅降低模型的運行時間，同時提升過濾器的過濾效果。實驗表明，該方法使得在線支持向量機模型的運行時間從10337s減少到3784s，同時模型(1-ROCA)%降低了一半。

特征抽取；支持向量機；垃圾郵件過濾。

1 引言

近年來，垃圾郵件給電子郵件行業帶來了很多問題，給人們生活造成了影響，個人和公司由于接收垃圾郵件和區分垃圾郵件而占用大量網絡資源和時間。同時垃圾郵件也是一個有利可圖的商業模式，因為垃圾郵件發送者只需要付出很小的代價就能得到豐厚的回報。由于垃圾郵件導致了經濟上的損失，有些國家制定相關法律來制裁垃圾郵件發送者。然而，由于技術上的限制，無法跟蹤某些垃圾郵件的來源(如國家或某個地點)，從而無法對垃圾郵件發送者進行法律制裁。

很多研究人員提出了多種解決垃圾郵件的方法。較早的技術是基于黑白名單的過濾技術[1]。該方法實現簡單，運行速度快，但準確率較低。隨著垃圾郵件發送技術的發展，垃圾郵件的特性大部分體現在郵件的內容上，所以垃圾郵件發送者發送的郵件很容易躲避基于黑白名單過濾技術的檢測。為了解決此類問題，研究人員通過分析郵件的內容和附件來判別垃圾郵件。例如，建立一個垃圾郵件詞庫，將郵件內容與庫中詞進行匹配，若匹配成功，判斷為垃圾郵件。我們將這種技術稱為基于規則或匹配的垃圾郵件過濾技術。該技術針對性很強，詞庫也便于更改。但隨著電子郵件的發展，垃圾郵件的數量非常龐大，規則庫或詞庫也將變得非常龐大，從而導致系統匹配速度變慢[2]。

為了更好地解決基于內容的郵件過濾問題，基于機器學習理論的垃圾郵件過濾技術成為當前最常用的方法。該方法針對郵件內容進行過濾，從郵件的內容獲取特征，并通過這些特征以及對應的標注來訓練和優化過濾器。該方法準確率高、成本較低，已成為當前解決垃圾郵件過濾問題普遍采用的方法[3]。

基于內容的垃圾郵件過濾是一個機器學習過程，機器學習技術通常分為生成模型(如樸素貝葉斯模型)和判別模型(如支持向量機模型、邏輯回歸模型)。Goodman and Hulten[4]在PU-1數據集上測試發現，判別模型的效果要好于生成模型。通過TREC和CEAS會議的垃圾郵件評測競賽發現，取得最好效果的模型都是采用判別模型[5-7]。在2007年TREC垃圾郵件評測中取得最好的成績是采用在線支持向量模型(online SVM)[7]。然而，在線支持向量模型消耗時間與樣本數量成平方關系，即時間復雜度為O(n2)，邏輯回歸模型和樸素貝葉斯模型時間復雜度僅為O(n)。在2007年Sculley and Watchman[8]提出了松弛在線向量機(Relaxed Online SVM，簡稱ROSVM)算法，大幅的降低了online SVM模型的運行時間。盡管ROSVM模型的運行時間被大幅降低，但與邏輯回歸模型相比，消耗時間仍然是巨大的。例如，ROSVM運行完TREC06p數據需要18 541s，而邏輯回歸模型僅需238s，運行效率是ROSVM的78倍。

本文我們提出多層grams特征抽取方法來提升在線支持向量模型。目前，常用的特征抽取方法是基于詞和基于n-grams的特征抽取方法。實驗發現基于n-grams的特征抽取方法效果更好，但該方法抽取特征數據較多，例如，一封郵件的字符串長度為3 000個字符，則抽取的特征接近3 000。大量特征數目是導致模型分類器高耗時的關鍵因素。因此本文提出了多層grams特征抽取方法提升在線支持向量機模型。實驗結果表明，該方法不僅能大幅降低系統的運行時間，同時還大幅提升過濾器的過濾效果。

本文第2節介紹在線支持向量機；第3節介紹本文提出的多層grams特征抽取方法；第4節是本文實驗和數據分析部分；第5節為結論。

2 在線支持向量機分類器

2.1 支持向量機

f(x)=w·x+b

(1)

其中w表示超平面向量，b是偏移項，x是郵件的特征向量。當f(x)=0時，w為超平面，距超平面最近兩個不同樣本符合f(x)=±1。因此距超平面最近的兩個不同類型的樣本的距離為1/‖w‖2。所以最大間隔的優化問題如式(2)所示。

subject_to:yi(w·xi+b)≥1-ξi,?i,ξi≥0

(2)

其中，xi表示第i個訓練樣本，yi表示此樣本的所屬類型。

然而并不是所有的樣本都是線性可分的，即不能找到線性超平面，當訓練樣本不是線性可分的情況，我們引入松弛變量ξi。當最大分類間隔變大時，最少錯分樣本個數會增加，當最小錯分個數減少時，最大分類間隔變小。最大分類間隔和最少錯分個數之間是矛盾的，所以引入平衡參數C，調節兩者之間的個數。優化形式如式(3)所示。

subject_to:yi(w·xi+b)≥1-ξi,?i,ξi≥0

(3)

其中，ξi是松弛變量，C是平衡因子。參數C的選擇很重要，它決定了過濾器的分類性能和消耗的時間。

2.2 在線支持向量機

通常，SVM采用批量學習(batch learning)的方式進行訓練，批量學習就是事先使用一部分訓練數據對SVM進行訓練，之后再采用另一部分數據作為測試集對訓練好的模型進行測試。在測試的過程中模型不再進行學習。

由于垃圾郵件過濾通常采用在線的方式進行，訓練數據隨著時間源源不斷的到來，當模型遇到新的訓練郵件后，必須將該訓練郵件加入訓練數據集，重新對模型進行學習。

對于一封新的郵件，過濾器首先對郵件進行分類，分類后等待用戶給予的反饋，即用戶會告訴過濾器這封郵件是垃圾郵件還是正常郵件，過濾器獲得用戶的反饋后，根據反饋結果調整模型的參數。由于不停地有新郵件添加到訓練集中，一個加快訓練速度的簡單方法是，每次訓練時候，都以前一次訓練得到的參數作為本次訓練的初始參數。

本文的在線支持向量機分類器使用Platt的SMO算法作為求解器[9]，因為SMO方法對線性支持向量機來說是最快的方法。

在線學習算法的訓練樣本是源源不斷的到來的，隨著時間的推移，訓練樣本集合會達到很大的規模，當訓練規模很大時，在線支持向量機模型的訓練速度就會急劇下降，從而導致模型不可用。因此，應該采取相應的算法提升模型的訓練速度，使用三個簡化措施。

1) 減少訓練集合大小

在線支持向量機訓練時，將訓練之前出現的所有郵件。郵件數量很大時，訓練時間將是非常昂貴的。本文提出只訓練最新的n封郵件，減少過濾器訓練時間，同時，新的郵件訓練時并不需要訓練之前的數據。每次訓練完之后保存當前的權重向量，下次訓練時只需要在此向量進行訓練。

2) 減少訓練的次數

根據KKT(Karush-Kuhn-Tucker)條件，當yif(xi)>1時，xi被認為是一個很容易正確分類的樣本。所以當樣本xi滿足yif(xi)≤1時，該樣本需要重新訓練。現在我們放寬條件來降低重復訓練的更新數量，當樣本滿足yif(xi)≤M，(0≤M≤1)時，該樣本進行重新訓練。這樣就降低了訓練樣本的次數。

3) 減少迭代次數

減少學習過程的迭代次數。SVM模型中最優分類面通過多次迭代獲得，迭代次數的多少直接影響到模型的運行速度，如果次數過大，模型訓練將很慢。然而在垃圾郵件過濾中，該模型并不需要過多的訓練。所以，通過降低SVM模型的迭代次數能提升模型的運行速率，從而提升過濾器整體性能。

3 多層grams特征抽取方法

本節我們將介紹基于多層grams的特征抽取方法，在介紹該方法之前將介紹基于分詞和基于n-grams的特征抽取方法，并分析存在的問題。

3.1 基于詞和n-grams的特征抽取方法

基于詞的特征提取方法是將一封郵件的內容以詞的形式分開，每個詞作為一個特征建立特征空間向量。即在建立特征空間之前，需要對郵件進行分詞。中英文分詞有所不同，不同的系統也有不同的分詞形式。對郵件內容為英文的郵件，有多種分詞形式，例如，一個連續且含非空白字符的字符串為一個特征，即以空格形式分詞，也有的是一個連續且只含字母的字符串為一個特征，即以非字母形式分詞等。中文郵件的分詞，并不像英文分詞那么簡單，因為中文每個詞與詞之間是連續的，并沒有用空格分開，需要根據一定的規范將中文句子拆分成每個詞。所以中文分詞要比英文分詞復雜得多，困難得多。目前中文分詞方法主要分為3類： 基于詞典的方法、基于統計的方法和基于理解的方法[10]。這3類分詞方法之間哪種方法準確率更高，目前尚無定論。對目前常用的分詞系統來說，大部分都是混合使用這三類分詞方法。例如，海量科技的分詞算法就是采用基于詞典和基于統計的分詞方法。目前比較成熟的分詞系統有： SCWS分詞系統、FudanNLP分詞系統、ICTCLAS分詞系統、CC-CEDICT分詞系統、IKAnalyzer分詞系統、庖丁解牛(Paoding)分詞系統和JE分詞系統等。本文實驗使用JE分詞系統。

隨著反垃圾郵件技術的發展，發送垃圾郵件技術也在提高，垃圾郵件發送者通過故意拼寫錯誤、字符替換和插入空白等形式對垃圾郵件特征的單詞進行變體，從而逃避檢測系統的檢測。圖1給出了“Viagra”這個單詞在TREC05p數據集上出現次數最多的25種變體。正常情況下，用戶都能知道這些變體和“Viagra”單詞是同一個含義。然而在基于詞的特征提取方法下，每一個變體的出現都代表一個新的特征，不能識別出是“Viagra”這個單詞，從而導致過濾器失效。基于字節的n-grams方法能夠克服這些問題。

圖1 “Viagra”這個單詞在TREC05p-1數據集上出現次數最多的25中變體

基于n-grams的特征提取方法是將郵件按照字節流進行大小為n字節的切分(其中，n取值為1，2，3，4…)，每次向后滑動一個字符，得到長度為n個字節的若干個串，每個串稱為gram。例如，information，按照n=4時進行滑動窗口切分為： info、nfor、form、orma、rmat、mati、atio和tion這8個4-grams的特征。

基于字節級n-grams特征提取方法使用非常方便，對句子進行分詞，不需要任何詞典的支持；在使用之前也不需要語料庫進行訓練。在對郵件提取特征時，不需要對郵件進行預處理，也不用考慮郵件編碼問題，直接將郵件作為無差別的字節流。同時該方法能夠處理復雜的文檔，例如，HTML格式的郵件、郵件中的圖像文件以及附件等內容。該方法與基于詞的特征提取方法相比，能夠有效防止信息偽裝等問題。如圖1所示的文字變形。基于詞的特征提取方法可能就識別不了這些特征，而n-grams方法能有效地識別出該特征。例如，Viagra使用4-grams方法提出的特征為： Viag、iagr、agra；當Viagra變形后變成Viiagra時提取的特征為： Viia、iiag、iagr、agra；兩者共同特征是iagr和agra。過濾器能夠識別這兩個特征。

中文的一個字由兩個字節或四個字節組成，每個字之間都是連續的。對于中文的n-grams特征提取方法如圖2所示。圖2中，“10月29日”在計算機中存儲的形式轉化為十六進制： 31 30 D4 C2 32 39 C8 D5。使用基于字節級的4-grams特征提取方法提取的特征如圖2所示。

圖2 使用n-grams方法提取特征實例

雖然基于n-grams的特征抽取方法已經在垃圾郵件過濾中取得了非常好的效果，但仍存在以下兩個問題：

1) 基于n-grams的特征抽取方法抽取的特征數目較多，特征數接近郵件內容的字符數，對大規模系統來說，耗時非常久。

2) 基于n-grams的特征抽取方法抽取中文郵件特征時，會出現半個漢字情況，半個漢字和其他字符會組成新的漢字，改變特征原有的含義。

3.2 多層grams特征抽取方法

雖然基于n-grams的特征抽取方法已取得很好的效果，但由于該方法抽取的特征數目較多，導致Online SVM消耗的時間仍然過大，無法在工業界使用。本文提出了多層n-grams特征抽取方法。該方法處理流程如圖2，處理過程如算法1。

多層grams特征抽取方法相比n-grams方法有兩大優點： 1)能夠大幅降低特征的數據，從而大幅降低online SVM模型的運行時間。2)能夠抽取更為精準、更為有效的特征，減少無用和具有噪聲的特征，從而提升模型過濾效果。

算法1： 多層n-grams特征抽取方法處理過程

Input： 一封郵件內容

Step1： 將郵件內容按照中英文字符分隔成若干個字符串，每個字符串為全部中文字符或全部非中文字符，并將其分成全部中文字符串集合和全部非中文字符串集合。例如，郵件內容為： “12月12日 10個人在Hilton Hotel花費1234567元人民幣”，被分成若干個字符串，其中，中文字符串集合為： “月,日, 個人在,花費,元人民幣”，非中文字符串集合為： “12,12,10, Hilton Hotel,1234567”。

Step2： 對中文字符串集合中每個字符串使用n-grams特征抽取方法抽取特征，但滑動窗口每次往后移動兩個字符。例如，字符串“元人民幣”一共為8個字符，通過n-grams方法抽取的特征為： “元人，人民，民幣”。

Step3： 對非中文字符串集合中每個字符串也使用n-grams方法抽取特征，但滑動窗口每次往后移動1個字符。

Step4： 將兩個集合中抽取的特征組成特征空間向量。

圖3 基于多層grams特征抽取框架

4 實驗

本節我們將在大規模數據集上測試本文所提出的多層grams特征抽取方法，本節的實驗結果表明，該方法大幅降低了基于在線支持向量機的中文垃圾郵件過濾器的運行時間，顯著提升了過濾器的過濾性能。

4.1 實驗數據集及評價指標

本文中所用的數據集TREC06c是TREC會議于2006年舉行的中文垃圾郵件評測數據，其數據集由清華大學提供。TREC06c數據集的郵件數為64 620封，其中垃圾郵件為21 766封，正常郵件為42 854封。

本文使用(1-ROCA)%和lam%作為過濾器的評估指標[5]。hm%為正常郵件的誤判率，sm%為垃圾郵件的誤判率。由于hm%值很小時，并不能保證sm%的值也很小，所以本文使用(1-ROCA)%和lam%做過濾器評價指標。

lam%為邏輯平均誤判率，其定義為式(4)。

以hm%為橫坐標，以sm%為縱坐標，組成ROC曲線，(1-ROCA)%的值為取不同閾值時的ROC曲線上方面積。該值的范圍為0到1之間。(1-ROCA)%和lam%的值越小表示過濾器性能越好。

4.2 實驗設置

本節所有實驗所測試郵件都只提取每封郵件的前3 000個字符，涉及的n-grams特征抽取方法的n均為4。在線支持向量機模型中，正則化參數C=100，回看樣本的參數n=10 000，即只訓練最新出現的10 000封郵件，KKT條件中，M的參數為0.8，優化迭代次數設為1。

4.3 基于詞和n-grams特征抽取方法比較

我們分別測試基于詞和基于n-grams的特征抽取方法在online SVM模型上的效果，實驗結果為表1，實驗結果表明基于n-grams方法的過濾效果要遠好于基于分詞的方法，(1-ROCA)%由0.007提升到0.004，降低近一半。

表1 基于詞和基于n-grams的特征抽取方法在Online SVM模型上指標對比

在時間消耗方面，雖然基于分詞的方法抽取特征數目明顯小于n-grams，但消耗的時間基本接近，主要原因是中文分詞花費時間較大，導致整體消耗的時間過大。

因此，基于n-grams特征抽取方法在online SVM模型處理中文垃圾郵件過濾時要明顯優于基于分詞的特征抽取方法。

4.4 多層grams和n-grams特征抽取方法比較

我們將基于多層grams的特征抽取方法和最優的n-grams方法進行比較，實驗結果如表2，通過表2可以發現，多層grams特征抽取方法相比n-grams方法，郵件的平均特征特征由1 625減少到835，減少一半，同時系統運行時間由10 337減少到3 784，僅為原來的1/3。且模型的(1-ROCA)%由原來的0.004降低到了0.002，效果顯著。

表2 基于多層grams和n-grams的特征抽取方法在Online SVM模型上指標對比

4.5 與目前最新的垃圾郵件過濾比較

目前研究中比較常用的是基于邏輯回歸的垃圾過濾器(LR Model)[11]，該方法不僅過濾效果好，而且運行速度快，普遍被工業界運用。同時，在2013年孫廣路、齊浩亮等提出了基于在線排序邏輯回歸的垃圾郵件過濾器(Ranking LR Model)[12]，該方法極大提升了過濾器過濾效果。本文將這兩種方法與本文提出的方法進行比較，實驗結果如表3。從實驗結果可以看出，本文提出的方法的過濾效果是LR Model的5倍，是Ranking LR Model的3倍，效果非常顯著。上述數據再次證明了本文提出的方法能被廣泛使用。

表3 與目前最新模型的比較

4.6 討論

從表3可以看出，文本提出的基于多層grams特征抽取方法，不僅降低了模型的特征數目，同時抽取特征能夠更精準、更有效地反映垃圾郵件和正常郵件的特性，減少噪聲特征，從而提升模型過濾性能。

5 結論

在線支持向量機模型過濾器在TREC 2007垃圾郵件評測競賽中取得非常好的效果，但與邏輯回歸模型過濾器相比，消耗的計算代價是巨大的。目前，很多研究人員更傾向于通過改變在線支持向量機模型的訓練方法來減少模型的耗時，很少有研究者從特征抽取的角度來提升模型的效率。然而，事實上特征的優化對模型的影響也是至關重要的，影響機器學習模型的計算速度不僅僅是樣本的數量，還有特征維度，通過抽取能夠反映數據特性的特征，可以提升過濾器的性能。因此，我們提出了基于多層grams的特征抽取方法來提升基于在線支持向量模型的中文垃圾郵件過濾器。實驗表明，該方法不僅能大幅減少系統的運行時間，而且還能大幅提升系統的過濾效果。

[1] G Hulten， J Goodman. Tutorial on Junk Mail Filtering[C]//Proceedings of the Twenty-First International Conference on Machine Learning Tutorial, 2004.

[2] T Nathan, S Timothy, C Brad, et al. Deterministic Memory-efficient String Matching Algorithms for Intrusion Detection[C]//Proceedings of IEEE INFOCOM, 2004: 2628-2639.

[3] Hongyu Gao, Yan Chen, Kathy Lee. Towards Online Spam Filtering in Social Network[C]//Proceedings of the 19th Annual Network & Distributed System Security Symposium.2012.

[4] G Hulten, J Goodman. Tutorial on junk e-mail filtering. In ICML 2004, 2004.

[5] G V Cormack, T R Lynam. TREC 2005 spam track overview[C]//Proceedings of The Fourteenth Text REtrieval Conference (TREC 2005), 2005.

[6] G V Cormack. TREC 2006 spam track overview[C]//Proceedings of The Fifteenth Text REtrieval Conference, 2006.

[7] G V Cormack. TREC 2007 spam track overview[C]//Proceedings of The Sixteenth Text REtrieval Conference, 2007.

[8] D Sculley， G Wachman. Relaxed online SVMs for spam filtering[C]//Proceedings of The Thirtieth Annual ACM SIGIR Conference Proceedings, 2007.

[9] J Platt. Sequential minimal optimization: A fast algorithm for training support vector machines[M]. In B Scholkopf, C Burges, A Smola, editors, Advancesin Kernel Methods—Support Vector Learning. MIT Press, 1998: 158-208.

[10] 孫鐵利, 劉延吉. 中文分詞技術的研究現狀與困難[J]. 信息技術，2009, 7: 187-192.

[11] 沈躍伍. 基于在線學習的垃圾郵件過濾技術研究[D]. 哈爾濱理工大學, 2012.

[12] 孫廣路, 齊浩亮. 基于在線排序邏輯回歸的垃圾郵件過濾[J]. 清華大學學報： 自然科學版, 2013, 5: 734-740.

Typed N-gram for Online SVM Based Chinese Spam Filtering

SHEN Yuanfu1, SHEN Yuewu2

(1. Library, Harbin University of Science and Technology, Harbin, Heilongjiang 150080, China; 2. School of Computer Science and Technology, Harbin University of Science and Technology, Harbin, Heilongjiang 150080, China)

In this paper, we propose Mix-grams method to improve online SVM filter for spam filtering. Though online SVM classifier brings high performance on online spam filtering, its computational cost is remarkable compared to other methods such as Logistic Regression. In this paper, we propose a type based n-gram extraction method to reduce the feature dimension of online SVM filter. Experimental results demonstrate that the method improves the filter performance and reduces the computational cost of online SVM filter.

Feature Extraction; Support Vector Machine (SVM); Spam filtering

沈元輔(1960—)，副教授，主要研究領域為信息檢索、信息過濾。E?mail：yuanfu．shen@gmail．com沈躍伍(1986—)，碩士研究生，主要研究領域為機器學習、數據挖掘、特征抽取。E?mail：yuewu．shen@qq．com

1003-0077(2015)01-0126-07

2014-06-15 定稿日期： 2014-07-27

TP391

A