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

沈元輔，沈躍伍

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

?

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

沈元輔1，沈躍伍2

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

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

特征抽??；支持向量機(jī)；垃圾郵件過濾。

1 引言

近年來，垃圾郵件給電子郵件行業(yè)帶來了很多問題，給人們生活造成了影響，個(gè)人和公司由于接收垃圾郵件和區(qū)分垃圾郵件而占用大量網(wǎng)絡(luò)資源和時(shí)間。同時(shí)垃圾郵件也是一個(gè)有利可圖的商業(yè)模式，因?yàn)槔]件發(fā)送者只需要付出很小的代價(jià)就能得到豐厚的回報(bào)。由于垃圾郵件導(dǎo)致了經(jīng)濟(jì)上的損失，有些國家制定相關(guān)法律來制裁垃圾郵件發(fā)送者。然而，由于技術(shù)上的限制，無法跟蹤某些垃圾郵件的來源(如國家或某個(gè)地點(diǎn))，從而無法對(duì)垃圾郵件發(fā)送者進(jìn)行法律制裁。

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

為了更好地解決基于內(nèi)容的郵件過濾問題，基于機(jī)器學(xué)習(xí)理論的垃圾郵件過濾技術(shù)成為當(dāng)前最常用的方法。該方法針對(duì)郵件內(nèi)容進(jìn)行過濾，從郵件的內(nèi)容獲取特征，并通過這些特征以及對(duì)應(yīng)的標(biāo)注來訓(xùn)練和優(yōu)化過濾器。該方法準(zhǔn)確率高、成本較低，已成為當(dāng)前解決垃圾郵件過濾問題普遍采用的方法[3]。

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

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

本文第2節(jié)介紹在線支持向量機(jī)；第3節(jié)介紹本文提出的多層grams特征抽取方法；第4節(jié)是本文實(shí)驗(yàn)和數(shù)據(jù)分析部分；第5節(jié)為結(jié)論。

2 在線支持向量機(jī)分類器

2.1 支持向量機(jī)

f(x)=w·x+b

(1)

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

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

(2)

其中，xi表示第i個(gè)訓(xùn)練樣本，yi表示此樣本的所屬類型。

然而并不是所有的樣本都是線性可分的，即不能找到線性超平面，當(dāng)訓(xùn)練樣本不是線性可分的情況，我們引入松弛變量ξi。當(dāng)最大分類間隔變大時(shí)，最少錯(cuò)分樣本個(gè)數(shù)會(huì)增加，當(dāng)最小錯(cuò)分個(gè)數(shù)減少時(shí)，最大分類間隔變小。最大分類間隔和最少錯(cuò)分個(gè)數(shù)之間是矛盾的，所以引入平衡參數(shù)C，調(diào)節(jié)兩者之間的個(gè)數(shù)。優(yōu)化形式如式(3)所示。

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

(3)

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

2.2 在線支持向量機(jī)

通常，SVM采用批量學(xué)習(xí)(batch learning)的方式進(jìn)行訓(xùn)練，批量學(xué)習(xí)就是事先使用一部分訓(xùn)練數(shù)據(jù)對(duì)SVM進(jìn)行訓(xùn)練，之后再采用另一部分?jǐn)?shù)據(jù)作為測(cè)試集對(duì)訓(xùn)練好的模型進(jìn)行測(cè)試。在測(cè)試的過程中模型不再進(jìn)行學(xué)習(xí)。

由于垃圾郵件過濾通常采用在線的方式進(jìn)行，訓(xùn)練數(shù)據(jù)隨著時(shí)間源源不斷的到來，當(dāng)模型遇到新的訓(xùn)練郵件后，必須將該訓(xùn)練郵件加入訓(xùn)練數(shù)據(jù)集，重新對(duì)模型進(jìn)行學(xué)習(xí)。

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

本文的在線支持向量機(jī)分類器使用Platt的SMO算法作為求解器[9]，因?yàn)镾MO方法對(duì)線性支持向量機(jī)來說是最快的方法。

在線學(xué)習(xí)算法的訓(xùn)練樣本是源源不斷的到來的，隨著時(shí)間的推移，訓(xùn)練樣本集合會(huì)達(dá)到很大的規(guī)模，當(dāng)訓(xùn)練規(guī)模很大時(shí)，在線支持向量機(jī)模型的訓(xùn)練速度就會(huì)急劇下降，從而導(dǎo)致模型不可用。因此，應(yīng)該采取相應(yīng)的算法提升模型的訓(xùn)練速度，使用三個(gè)簡化措施。

1) 減少訓(xùn)練集合大小

在線支持向量機(jī)訓(xùn)練時(shí)，將訓(xùn)練之前出現(xiàn)的所有郵件。郵件數(shù)量很大時(shí)，訓(xùn)練時(shí)間將是非常昂貴的。本文提出只訓(xùn)練最新的n封郵件，減少過濾器訓(xùn)練時(shí)間，同時(shí)，新的郵件訓(xùn)練時(shí)并不需要訓(xùn)練之前的數(shù)據(jù)。每次訓(xùn)練完之后保存當(dāng)前的權(quán)重向量，下次訓(xùn)練時(shí)只需要在此向量進(jìn)行訓(xùn)練。

2) 減少訓(xùn)練的次數(shù)

根據(jù)KKT(Karush-Kuhn-Tucker)條件，當(dāng)yif(xi)>1時(shí)，xi被認(rèn)為是一個(gè)很容易正確分類的樣本。所以當(dāng)樣本xi滿足yif(xi)≤1時(shí)，該樣本需要重新訓(xùn)練?，F(xiàn)在我們放寬條件來降低重復(fù)訓(xùn)練的更新數(shù)量，當(dāng)樣本滿足yif(xi)≤M，(0≤M≤1)時(shí)，該樣本進(jìn)行重新訓(xùn)練。這樣就降低了訓(xùn)練樣本的次數(shù)。

3) 減少迭代次數(shù)

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

3 多層grams特征抽取方法

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

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

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

隨著反垃圾郵件技術(shù)的發(fā)展，發(fā)送垃圾郵件技術(shù)也在提高，垃圾郵件發(fā)送者通過故意拼寫錯(cuò)誤、字符替換和插入空白等形式對(duì)垃圾郵件特征的單詞進(jìn)行變體，從而逃避檢測(cè)系統(tǒng)的檢測(cè)。圖1給出了“Viagra”這個(gè)單詞在TREC05p數(shù)據(jù)集上出現(xiàn)次數(shù)最多的25種變體。正常情況下，用戶都能知道這些變體和“Viagra”單詞是同一個(gè)含義。然而在基于詞的特征提取方法下，每一個(gè)變體的出現(xiàn)都代表一個(gè)新的特征，不能識(shí)別出是“Viagra”這個(gè)單詞，從而導(dǎo)致過濾器失效?；谧止?jié)的n-grams方法能夠克服這些問題。

圖1 “Viagra”這個(gè)單詞在TREC05p-1數(shù)據(jù)集上出現(xiàn)次數(shù)最多的25中變體

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

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

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

圖2 使用n-grams方法提取特征實(shí)例

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

1) 基于n-grams的特征抽取方法抽取的特征數(shù)目較多，特征數(shù)接近郵件內(nèi)容的字符數(shù)，對(duì)大規(guī)模系統(tǒng)來說，耗時(shí)非常久。

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

3.2 多層grams特征抽取方法

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

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

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

Input： 一封郵件內(nèi)容

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

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

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

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

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

4 實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

本文中所用的數(shù)據(jù)集TREC06c是TREC會(huì)議于2006年舉行的中文垃圾郵件評(píng)測(cè)數(shù)據(jù)，其數(shù)據(jù)集由清華大學(xué)提供。TREC06c數(shù)據(jù)集的郵件數(shù)為64 620封，其中垃圾郵件為21 766封，正常郵件為42 854封。

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

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

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

4.2 實(shí)驗(yàn)設(shè)置

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

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

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

表1 基于詞和基于n-grams的特征抽取方法在Online SVM模型上指標(biāo)對(duì)比

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

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

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

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

表2 基于多層grams和n-grams的特征抽取方法在Online SVM模型上指標(biāo)對(duì)比

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

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

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

4.6 討論

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

5 結(jié)論

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

[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] 孫鐵利, 劉延吉. 中文分詞技術(shù)的研究現(xiàn)狀與困難[J]. 信息技術(shù)，2009, 7: 187-192.

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

[12] 孫廣路, 齊浩亮. 基于在線排序邏輯回歸的垃圾郵件過濾[J]. 清華大學(xué)學(xué)報(bào)： 自然科學(xué)版, 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—)，副教授，主要研究領(lǐng)域?yàn)樾畔z索、信息過濾。E?mail：yuanfu．shen@gmail．com沈躍伍(1986—)，碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、特征抽取。E?mail：yuewu．shen@qq．com

1003-0077(2015)01-0126-07

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

TP391

A