齊浩亮,程曉龍,楊沐昀,何曉寧,李生,雷國華

(1.黑龍江工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系,黑龍江哈爾濱150050;2.哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱150001;3.哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱150080)

1 前言

隨著電子郵件的廣泛應(yīng)用,伴隨而來的垃圾郵件問題日益嚴(yán)重。它不僅消耗網(wǎng)絡(luò)資源、占用網(wǎng)絡(luò)帶寬、浪費(fèi)用戶的寶貴時(shí)間和上網(wǎng)費(fèi)用,而且嚴(yán)重威脅網(wǎng)絡(luò)安全,已成為網(wǎng)絡(luò)公害,帶來了嚴(yán)重的經(jīng)濟(jì)損失。中國互聯(lián)網(wǎng)協(xié)會(huì)反垃圾郵件中心發(fā)布的2007年第四季度反垃圾郵件調(diào)查報(bào)告顯示,垃圾郵件在規(guī)模上不斷增長,2007年第四季度中國網(wǎng)民平均每周收到的垃圾郵件比例為55.65%。迫切需要有效的技術(shù)解決垃圾郵件泛濫的問題。

郵件過濾任務(wù)本質(zhì)上可以看作是一個(gè)在線二值分類問題[1-2],即將郵件區(qū)分為Spam(垃圾郵件)或Ham(正常郵件)。近幾年,基于機(jī)器學(xué)習(xí)的文本分類法在垃圾郵件過濾中發(fā)揮了巨大的作用,典型的方法包括貝葉斯方法、支持向量機(jī)(SVM,Support Vector M achine)方法、最大熵方法、PPM(Prediction by Partial Match)壓縮算法等。由于這些方法過濾正確率高、成本低,因此機(jī)器學(xué)習(xí)方法稱為當(dāng)前的主流方法。應(yīng)用機(jī)器學(xué)習(xí)方法對(duì)垃圾郵件進(jìn)行過濾時(shí)涉及到3個(gè)問題：模型選擇、特征抽取(郵件表示)以及訓(xùn)練方法。

從模型上看,機(jī)器學(xué)習(xí)技術(shù)可以粗略分為生成模型(如貝葉斯模型)和判別模型(如SVM、最大熵模型)。在相關(guān)領(lǐng)域——文本分類中,判別模型的分類效果比生成模型的分類效果要好,特別在沒有足夠多的訓(xùn)練數(shù)據(jù)的時(shí)候,這種現(xiàn)象更明顯[1]。在生成模型方面,著名的Bogo系統(tǒng)就是基于貝葉斯模型的,在 TREC評(píng)測中作為基準(zhǔn)(Baseline)系統(tǒng)。用于數(shù)據(jù)壓縮的CTW(Context Tree Weight)和PPM(Prediction by PartialMatch)等壓縮算法被引入到了垃圾郵件過濾[2]。CTW 和PPM是數(shù)據(jù)壓縮中使用的動(dòng)態(tài)壓縮算法,其原理是根據(jù)已經(jīng)出現(xiàn)的數(shù)據(jù)流預(yù)測后面要出現(xiàn)的數(shù)據(jù)流,預(yù)測的越準(zhǔn),所需的編碼也就越少,并據(jù)此進(jìn)行分類。2004年,Hulten和Goodman在PU-1垃圾郵件集上做實(shí)驗(yàn),證明了在郵件過濾上,判別模型的分類效果比生成模型的分類效果要好[3]。不嚴(yán)格的在線支持向量機(jī)(Relaxed On line SVM)克服了支持向量機(jī)計(jì)算量大的問題被用于解決垃圾郵件過濾的問題[4],并在TREC 2007評(píng)測中取得了很好效果。Goodm an和Y ih提出使用在線邏輯回歸模型,避免了SVM、最大熵模型的大量計(jì)算,并取了與上一年度(2005年)最好結(jié)果可比的結(jié)果[5]。

在特征抽取(即郵件表示)上,郵件的文本內(nèi)容是當(dāng)前過濾器處理的重點(diǎn)。大多數(shù)過濾器以詞作為過濾單元。由于垃圾郵件對(duì)文本的內(nèi)容進(jìn)行了變形,使得上述方法存在缺陷。非精確的字符串匹配被用于解決這個(gè)問題[6],但該方法只對(duì)英文垃圾郵件過濾有效,無法直接用于中文垃圾郵件過濾。在信息檢索領(lǐng)域的字符級(jí)n元文法被引入垃圾郵件過濾,并在TREC評(píng)測中取得優(yōu)于詞袋(Bag o f w ord)假設(shè)的結(jié)果[4]。字符語言模型也被應(yīng)用于垃圾郵件過濾,取得了比較好的效果[7]。鑒于大量垃圾郵件將文本內(nèi)容轉(zhuǎn)換為圖像,基于圖像分析(Image Analysis)的過濾技術(shù)近年來得到重視[8]。

在訓(xùn)練方法上,最簡單也是最常用的訓(xùn)練方法就是對(duì)每一封郵件都進(jìn)行訓(xùn)練。這種方法在實(shí)際應(yīng)用中已經(jīng)獲得了很好的效果,但是有兩個(gè)問題。第一個(gè)問題是內(nèi)容相近的郵件可能被多次訓(xùn)練,增加資源的耗費(fèi)。第二個(gè)問題是會(huì)出現(xiàn)過度訓(xùn)練的問題,當(dāng)某些特征在特征庫中已經(jīng)有足夠多的計(jì)數(shù)時(shí),再過多的進(jìn)行訓(xùn)練會(huì)導(dǎo)致準(zhǔn)確率的下降。改用TOE(Train On Error)方法后,僅當(dāng)郵件被誤判時(shí)才進(jìn)行訓(xùn)練,這種方法只能用于判別學(xué)習(xí)模型。這樣可防止過度訓(xùn)練、減小空間占用并提高速度。盡管過度訓(xùn)練會(huì)極大的影響過濾器的準(zhǔn)確率,但TOE訓(xùn)練法在另一個(gè)方向走過了頭,僅對(duì)誤判的郵件進(jìn)行訓(xùn)練導(dǎo)致過濾器訓(xùn)練數(shù)據(jù)不足,其對(duì)準(zhǔn)確率仍有影響。TONE(Train On or Near Error)在 TOE基礎(chǔ)上加以改進(jìn),預(yù)設(shè)一個(gè)分?jǐn)?shù)界限,當(dāng)郵件得分與判斷閥值之差的絕對(duì)值在界限之內(nèi)時(shí),即使正確判斷也進(jìn)行訓(xùn)練[4]。

本文采用邏輯回歸模型、字節(jié)級(jí)n元文法和TONE訓(xùn)練方法進(jìn)行中文垃圾郵件過濾。本文描述的系統(tǒng)參加了中國計(jì)算機(jī)學(xué)會(huì)主辦的SEWM(Search Engine and Web Mining)2008垃圾郵件過濾評(píng)測,獲立即反饋、主動(dòng)學(xué)習(xí)、延遲反饋全部在線評(píng)測項(xiàng)目的第一,性能優(yōu)于第二名100倍左右;在SEWM 2007上 1-ROCA達(dá)到了0.000 0%;在TREC06c上也顯著優(yōu)于當(dāng)年評(píng)測的最好結(jié)果。

本文的隨后部分安排如下。第二節(jié)介紹了垃圾郵件的在線過濾模式,第三節(jié)介紹了垃圾郵件過濾器的設(shè)計(jì),包括過濾模型、特征提取和訓(xùn)練方法,第四節(jié)是實(shí)驗(yàn)結(jié)果,最后給出了本文的結(jié)論。

2 垃圾郵件的在線過濾模式

過濾器(分類器)的學(xué)習(xí)方式可以分為在線學(xué)習(xí)(Online Learning)和批量學(xué)習(xí)/離線學(xué)習(xí)(Batch Learning/Offline Learning)。在離線學(xué)習(xí)方式下,通過訓(xùn)練樣本調(diào)整分類器的參數(shù)。在實(shí)際應(yīng)用時(shí),不再調(diào)整分類器的參數(shù)。在在線學(xué)習(xí)方式下,分類器根據(jù)用戶的反饋不斷調(diào)整系統(tǒng)參數(shù),使系統(tǒng)能夠適應(yīng)不斷變化的應(yīng)用環(huán)境。在線學(xué)習(xí)適用于需要快速更新的環(huán)境。受制于在線更新學(xué)習(xí)器,其參數(shù)更新算法的復(fù)雜度要低,以適應(yīng)實(shí)際應(yīng)用的需求。為了避免垃圾郵件被過濾器過濾,垃圾郵件發(fā)送者不斷改進(jìn)垃圾郵件發(fā)送技術(shù)。這就要求垃圾郵件過濾器具有良好的適應(yīng)能力,因而在線學(xué)習(xí)方式適用于垃圾郵件過濾[9-10]。SEWM 08中文垃圾郵件過濾評(píng)測也表明,在線學(xué)習(xí)方式的性能優(yōu)于批量學(xué)習(xí)方式(http ：//www 2.scut.edu.cn/antispam/ppt.htm l)。在線學(xué)習(xí)方式能夠滿足過濾不斷變化的垃圾郵件的要求,這也是TREC(Text REtrieval Conference)公開評(píng)測采用在線學(xué)習(xí)方式的原因。

本文采用在線學(xué)習(xí)方式,這也是國內(nèi)外垃圾郵件過濾評(píng)測采用的方式。所用的郵件在線過濾模式如圖1所示,以過濾器和訓(xùn)練器為中心分為過濾和訓(xùn)練(即學(xué)習(xí))兩部分。過濾器根據(jù)在線更新的特征庫,過濾按實(shí)際順序輸入的郵件流,判斷每個(gè)郵件的屬性。訓(xùn)練器根據(jù)用戶的反饋對(duì)郵件的過濾結(jié)果進(jìn)行學(xué)習(xí),并進(jìn)一步調(diào)整特征權(quán)重庫中相應(yīng)特征及其權(quán)重,提高過濾器的適應(yīng)能力與性能。

圖1 垃圾郵件過濾在線模式

3 基于邏輯回歸模型的垃圾郵件過濾器

模型是影響垃圾郵件過濾效果的核心因素,恰當(dāng)選擇過濾模型是系統(tǒng)成功的關(guān)鍵。邏輯回歸(Logistic Regression,LR)模型,和SVM 一樣,是一種判別學(xué)習(xí)模型,具有良好的性能;邏輯回歸模型的時(shí)間復(fù)雜度和空間復(fù)雜度都低于SVM,更重要的是,邏輯回歸模型可以很容易地以在線學(xué)習(xí)方式調(diào)整模型的參數(shù),使模型能夠適應(yīng)不斷演進(jìn)的垃圾郵件,因此,邏輯回歸模型成為當(dāng)前垃圾郵件過濾中的主流模型之一[11]。特征選擇是與過濾模型關(guān)系緊密,是影響分類性能的關(guān)鍵因素。本文提出了字節(jié)級(jí)n元文法的郵件特征提取方法,將郵件視為二進(jìn)制流,簡化了特征提取,保證了過濾器的性能。在訓(xùn)練時(shí),采用TONE方法,該方法可以與邏輯回歸模型等判別學(xué)習(xí)模型配合使用,降低訓(xùn)練量,并提升系統(tǒng)性能。

3.1 邏輯回歸模型

邏輯回歸(Logistic Regression,LR)模型,和SVM一樣,是一種判別學(xué)習(xí)模型。判別學(xué)習(xí)模型與以貝葉斯為代表的生成模型有本質(zhì)差異。傳統(tǒng)生成模型認(rèn)為數(shù)據(jù)都是某種分布生成的,并試圖根據(jù)這種分布建模。采用最大似然估計(jì)(Maxim um Likelihood Estimation,簡稱M LE)來求解模型參數(shù),并用平滑算法來解決數(shù)據(jù)稀疏問題。這種方法僅當(dāng)以下兩個(gè)條件都滿足時(shí)才是最優(yōu)的：第一,數(shù)據(jù)的概率分布形式是已知的;第二,存在足夠大的訓(xùn)練數(shù)據(jù)時(shí)才能采用最大似然估計(jì)來求解模型參數(shù)。但在實(shí)際應(yīng)用中,這兩個(gè)條件很多時(shí)候無法滿足。判別學(xué)習(xí)模型是與生成模型相對(duì)應(yīng)的一類建模方法。其假設(shè)條件比M LE弱得多,只要求訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)來自同一個(gè)分布即可。而且,判別學(xué)習(xí)算法的目標(biāo)往往與實(shí)際應(yīng)用的評(píng)價(jià)標(biāo)準(zhǔn)密切相關(guān)(如使模型在訓(xùn)練數(shù)據(jù)上的錯(cuò)誤率最小化)。因此判別學(xué)習(xí)模型的性能往往要優(yōu)于生成模型。從計(jì)算復(fù)雜度上看,邏輯回歸模型的計(jì)算復(fù)雜要明顯低于SVM,其分類速度要也比SVM快得多。

在基于內(nèi)容的郵件過濾系統(tǒng)中,影響一封郵件是垃圾郵件還是非垃圾郵件的因素是該郵件中的特征。應(yīng)用邏輯回歸模型,可以根據(jù)郵件的特征判斷該郵件是垃圾郵件的概率：

其中：x?是該封郵件的所有特征組成的向量,是該封郵件的所有特征相對(duì)應(yīng)的特征權(quán)重向量。

定義一個(gè)分界值,通常設(shè)為0.5。比較P(y)和分界值,若P(y)大于等于分界值,就判斷為垃圾郵件;否則就判斷為正常郵件。

3.2 基于字節(jié)級(jí)n元文法的特征提取

郵件過濾的依據(jù)是郵件的特征,特征項(xiàng)的定義,是影響分類性能的關(guān)鍵因素。和文本分類問題相比,郵件過濾有其特殊之處。反垃圾郵件技術(shù)在進(jìn)步,發(fā)送垃圾郵件的技術(shù)也在不斷地提高。由于巨大的利益驅(qū)動(dòng),狡猾的垃圾郵件發(fā)送者對(duì)其電子郵件信息進(jìn)行多方面的偽裝,通過各種手段將垃圾郵件偽裝為正常郵件。同時(shí),大量垃圾郵件以圖像的形式出現(xiàn),導(dǎo)致傳統(tǒng)方法失效;單純的依賴郵件的文本內(nèi)容對(duì)含有病毒的垃圾郵件無能為力。

針對(duì)垃圾郵件特征提取面臨的問題,提出了基于字節(jié)級(jí)n元文法的特征提取方法。字節(jié)級(jí)n元文法在處理郵件文本內(nèi)容時(shí),提取了郵件的文本內(nèi)容,在處理郵件的附件、所包含的圖片等組成成分時(shí),提取了它們的二進(jìn)制特征,因此能夠在一個(gè)簡單的框架下處理以往很難處理問題。采用字節(jié)級(jí)n元文法提取郵件特征,避免了繁雜的郵件解析、漢字編碼轉(zhuǎn)換等工作,并使系統(tǒng)具有處理圖像、病毒郵件的能力。

字節(jié)級(jí)n元文法,將郵件按字節(jié)流進(jìn)行大小為n的滑動(dòng)窗口操作,形成長度為n的字節(jié)片斷序列,每個(gè)字節(jié)片斷稱為gram。n元文法 按字節(jié)流進(jìn)行采用長度為n的窗口切分,如：abcd,按照n=2時(shí)進(jìn)行滑動(dòng)窗口切分為：ab、bc、cd這樣 3個(gè)2-gram。采用n元文法信息作為郵件特征具有以下特點(diǎn)：無需任何詞典支持,無需進(jìn)行分詞處理;無需語言學(xué)先驗(yàn)知識(shí);無需對(duì)郵件進(jìn)行預(yù)處理,將郵件當(dāng)作無差別的字節(jié)流對(duì)待;不用考慮文字編碼的問題;同時(shí)具有處理復(fù)雜文件的能力,如 HTM L格式郵件、圖像文件、壓縮文件。與以詞字、詞組等為特征元素相比,這樣定義特征元素能有效防止了垃圾郵件信息的可能被繞過的情況。如product進(jìn)行文字變形,變換為p!roduct,pro_duct,prod-uct等等,基于詞字、詞組的過濾器就可能識(shí)別不出該特征,而基于字節(jié)的n元文法仍可以有效識(shí)別出該特征。例如,當(dāng)n=4時(shí),product進(jìn)行特征抽取如下：prod、rodu、oduc、duct;當(dāng)p roduct文字變形后變?yōu)閜 rod-uct時(shí)進(jìn)行特征抽取如下：prod 、rod-、od-u 、d-uct、-uct;兩者共有的特征是prod。當(dāng)出現(xiàn)特征prod時(shí),則該完整的單詞為product的概率比只捕捉到特征prod時(shí)的概率要大得多。同時(shí),變形后的字符串往往較多地出現(xiàn)在垃圾郵件中,表明了郵件的性質(zhì)。

中文使用至少2個(gè)字節(jié)表示一個(gè)字(如GB 2312使用兩個(gè)字節(jié)表示1個(gè)漢字,GB 18030使用兩個(gè)字節(jié)或四個(gè)字節(jié)表示1個(gè)漢字),不使用空格作為詞的分隔符,因此,如果對(duì)漢字進(jìn)行文字變換程度太大的話,是很難讓人讀懂的,如“辦證”,常見的變形文字是“辦.證”、“辦證”等,由于無法進(jìn)行正確的分詞,這種文字變形使得典型的以詞為過濾單元的方法失效。由于字節(jié)級(jí)n元文法提取連續(xù)的n個(gè)字節(jié)作為特征,字符變形后n元文法依然能夠提取有效特征。由于“辦.證”、“辦證”等大量出現(xiàn)在垃圾郵件中,正常郵件中較少出現(xiàn)。在n元文法下,變形后的文字反而表明了它是垃圾郵件,表明了該郵件的性質(zhì)。

以詞作為過濾單元,詞作為最小的能自由運(yùn)用的語言單位,將有助于過濾性能的提高,需要進(jìn)行編碼識(shí)別和分詞,但分詞的準(zhǔn)確度難以保證,尤其是未登錄詞的識(shí)別性能難以得到保證,同時(shí)難以處理文字變形;若以字作為過濾單元,不需要進(jìn)行分詞,實(shí)現(xiàn)起來比較容易,但字的語義表達(dá)能力較弱,上下文信息太少。

在實(shí)驗(yàn)中使用了字節(jié)級(jí)4-gram,并且每一封郵件僅取前3 000個(gè)4-gram。郵件的特征值為布爾值,即郵件包含某個(gè)4-gram,其值為1,否則為 0。

3.3 TONE訓(xùn)練方法

TONE(Train On or Near Error)方法也被稱之為Thick Threshold方法,該方法是在TOE基礎(chǔ)上加以改進(jìn),預(yù)設(shè)一個(gè)分?jǐn)?shù)界限,當(dāng)郵件得分與判斷閥值之差的絕對(duì)值在界限之內(nèi)時(shí),即使正確判斷也進(jìn)行訓(xùn)練。

現(xiàn)在說明該方法的應(yīng)用。對(duì)于本文采用的邏輯回歸模型,當(dāng)郵件的得分大于等于0.5時(shí),就判斷成垃圾郵件;反之,當(dāng)郵件的得分小于0.5時(shí),就判斷成正常郵件。采用TONE訓(xùn)練方法,在下述兩種情況下進(jìn)行訓(xùn)練：(1)過濾器分類錯(cuò)誤;(2)如果設(shè)定閾值為0.1,則得分介于0.4到0.6之間的郵件都需要進(jìn)行訓(xùn)練。

TONE訓(xùn)練方法只對(duì)分類面附近的樣本進(jìn)行訓(xùn)練,通過算法1將分類錯(cuò)誤和在分類面附近的樣本向“安全區(qū)域”調(diào)整。直觀上,這個(gè)過程與支持向量機(jī)模型有異曲同工之妙。支持向量機(jī)模型在尋找最大化最近距離的分類面(即最優(yōu)分類面);在TONE方法中,恰當(dāng)?shù)卦O(shè)置閥值,可以起到相同的作用。據(jù)我們所知,尚未有討論TONE方法和最優(yōu)分類面關(guān)系的文獻(xiàn)。

本文采用梯度下降的方法更新特征庫中特征的權(quán)重。使用梯度下降方法時(shí),選取合適的特征學(xué)習(xí)速率以保證適當(dāng)?shù)膶W(xué)習(xí)速率。

具體實(shí)現(xiàn)如算法1所示。

算法1：分類及權(quán)重更新算法

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

4.1 實(shí)驗(yàn)環(huán)境

4.1.1 測試數(shù)據(jù)

中文垃圾郵件過濾的評(píng)測數(shù)據(jù)主要來自國際文本信息檢索會(huì)議(TREC,Text RE trieval Conference)和全國搜索引擎和網(wǎng)上信息挖掘?qū)W術(shù)研討會(huì)(SEWM,Search Engine and Web M ining)。TREC評(píng)測由美國國防部高級(jí)研究規(guī)劃局(DARPA,Defense Advanced Research Projects Agency和美國國家標(biāo)準(zhǔn)技術(shù)研究院(NIST,National Institute of Standards and Technology)主辦,每年都吸引大批知名大學(xué)和企業(yè)研究機(jī)構(gòu)參與,是信息檢索領(lǐng)域最重要的評(píng)測。TREC會(huì)議于2005年開始舉辦垃圾郵件過濾測評(píng),并在2006年進(jìn)行了中文垃圾郵件過濾評(píng)測。SEWM由中國計(jì)算機(jī)學(xué)會(huì)主辦。國內(nèi)于2007年在SEWM上首次增加了垃圾郵件過濾評(píng)測項(xiàng)目,2008年有6所大學(xué)參加了評(píng)測。SEWM評(píng)測的目標(biāo)是通過提供一個(gè)以中文為主并反映最新垃圾郵件特征的大規(guī)模郵件數(shù)據(jù)集,并以此檢驗(yàn)各種過濾技術(shù)在實(shí)際垃圾郵件過濾中的有效性。該評(píng)測由華南理工大學(xué)廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室主持。

過濾器的性能在目前已有的全部公開中文垃圾郵件公有測試集(TREC06c、SEWM 07和 SEWM 08)上驗(yàn)證,表1是測試數(shù)據(jù)的情況。TREC06c是TREC 06年中文垃圾郵件評(píng)測的公開數(shù)據(jù),SEWM 07和SEWM 08分別是SEWM 07年和SEWM 08年評(píng)測的公開數(shù)據(jù),由華南理工大學(xué)提供。

表1 垃圾郵件過濾測試集

4.1.2 評(píng)估指標(biāo)

實(shí)驗(yàn)使用(1-ROCA)%作為過濾器的評(píng)估指標(biāo),lam%也被使用,用于參考。文獻(xiàn)[13]給出了垃圾郵件過濾采用(1-ROCA)%和lam%而不是正確率/錯(cuò)誤率作為評(píng)價(jià)指標(biāo)的原因。

lam%(logistic average misclassification percentage)：邏輯平均誤判率,定義為lam%=logit-1(logit(ham%)/2+logit(spam%)/2),其中l(wèi)ogit(x)=log(x/(1-x)),logit-1(x)=ex/(1+ex),ham%為正常郵件錯(cuò)誤判斷為垃圾郵件的比率,spam%為垃圾郵件錯(cuò)誤判斷為正常郵件的比率。

ROC曲線是接受者操作特性曲線(receiver operating characteristic curve)的簡稱。以ham%為橫坐標(biāo),以spam%為縱坐標(biāo),取不同的 T值時(shí),可以得到ROC曲線(實(shí)際表達(dá)recall-fallout)。1-ROCA(area above the ROC curve)表明了過濾器的累積失效情況。該值介于0和1之間,該值越小,表示過濾器效能越好。

本文采用 TREC提供的評(píng)估工具(下文稱為TREC工具)。SEWM 07、08垃圾郵件過濾評(píng)測由中國計(jì)算機(jī)學(xué)會(huì)主辦,華南理工大學(xué)承辦并為評(píng)測提供了評(píng)估工具。在SEWM 08評(píng)測中,該工具與TREC工具在立即反饋和主動(dòng)學(xué)習(xí)測試中,1-ROCA時(shí)的最后一位(百萬分之一)略有不同,可能是由于舍入誤差引起的。

4.1.3 測試任務(wù)

實(shí)驗(yàn)在所有的中文垃圾郵件過濾測試集上進(jìn)行,測試 包括 TREC06c、SEWM 07 、SEWM 08 的公開語料。這些測試語料涉及到的測試任務(wù)有立即反饋(Immediate Feedback)、延遲反饋(Delayed Feedback)、主動(dòng)學(xué)習(xí)(Active Learning)。在立即反饋測試中,過濾器按接收到的郵件次序?qū)⑧]件分成正常郵件或垃圾郵件,并計(jì)算每一封郵件分值。過濾器在對(duì)郵件進(jìn)行分類之后可以立即得到該郵件是否分類正確(即該郵件的答案。立即反饋假定用戶在接收到郵件后立即作出判斷。然而,真實(shí)用戶不可能立即向過濾器返回正確的類別。用戶經(jīng)常一次讀多封郵件,這導(dǎo)致過濾器不可能馬上獲得郵件的正確分類。延遲反饋模擬了這種情況。在延遲反饋中,過濾器需要等待一定數(shù)據(jù)郵件之后才能獲得某一封郵件的分類。主動(dòng)學(xué)習(xí)任務(wù)測試過濾器如何有效的利用反饋信息,降低系統(tǒng)的訓(xùn)練次數(shù)和對(duì)標(biāo)注數(shù)據(jù)的依賴。在主動(dòng)學(xué)習(xí)測試中,給定一定的配額(quota),過濾器在配額消耗完后測試系統(tǒng)不再提供反饋。

在實(shí)驗(yàn)中,所有的測試任務(wù)都使用了相同的過濾器。

4.2 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中,首先比較了n元文法、TONE值對(duì)過濾器性能的影響,然后給出了實(shí)驗(yàn)的主要結(jié)果。表2至表3中的“active1000”表示在主動(dòng)學(xué)習(xí)中最多使用1 000個(gè)學(xué)習(xí)樣本。

表2比較了使用3-gram、4-gram和5-gram時(shí),過濾器在不同的測試集合、測試任務(wù)的性能。表中所有實(shí)驗(yàn)使用了相同的參數(shù),學(xué)習(xí)速率 rate(算法1中)為0.004,TONE為0.32。通過實(shí)驗(yàn)結(jié)果可以看出,以4-gram提取特征,過濾器的性能較優(yōu)。

表2 n元文法結(jié)果比較

表3比較了TONE對(duì)過濾器的影響。實(shí)驗(yàn)中采用四元文法、學(xué)習(xí)速率rate設(shè)為 0.004。通過實(shí)驗(yàn)結(jié)果可以看出,TONE=0.32時(shí),過濾器的性能較優(yōu)。

表3 TONE對(duì)過濾器的影響

表4是實(shí)驗(yàn)的主要結(jié)果,分別給出了過濾器在立即反饋、延遲反饋和主動(dòng)學(xué)習(xí)上與其他系統(tǒng)的性能比較。在立即反饋、延遲反饋和主動(dòng)學(xué)習(xí)的測試上,系統(tǒng)參數(shù)設(shè)置為：四元文法,學(xué)習(xí)速率rate為0.004,TONE為0.32。由于SEWM 07評(píng)測沒有參賽隊(duì)進(jìn)行了在線學(xué)習(xí)任務(wù),只進(jìn)行了批處理(離線)任務(wù),因此沒有在線任務(wù)的最佳系統(tǒng)。SEWM 07沒有進(jìn)行延遲反饋測試,TREC06C和SEWM 07沒有進(jìn)行主動(dòng)反饋測試,沒有相關(guān)實(shí)驗(yàn)數(shù)據(jù)。表中“最佳系統(tǒng)/第二名系統(tǒng)”表示評(píng)測中最佳系統(tǒng)或第二名系統(tǒng),“/”在后表示最佳系統(tǒng),“/”在前表示第二名系統(tǒng)。如“0.002 3%/”表示最佳系統(tǒng)的性能,“/0.0094%”表示第二名系統(tǒng)的性能。本文的方法參加了SEWM 08評(píng)測,包攬了SEWM 08所有在線任務(wù)的第一,在表中SEWM 08下的“最佳系統(tǒng)/第二名系統(tǒng)”標(biāo)識(shí)了第二名系統(tǒng)的性能。

表4 與其他系統(tǒng)結(jié)果比較

在SEWM 08的評(píng)測中,本文描述的系統(tǒng)取得了較好的效果。除了本文所描述的系統(tǒng)采用n元文法外,其他參評(píng)單位均提取字或詞作為特征,所使用的模型包括PPM(Prediction by PartialM atching)、基于SVM的過濾器、基于樸素貝葉斯分過濾器、基于語言模型的過濾器。這表明,對(duì)于垃圾郵件過濾,字節(jié)級(jí)n元文法能夠更有效地提取過濾器所需的特征。

從實(shí)驗(yàn)結(jié)果可以看出,本文提出的方法性能優(yōu)異,要么遠(yuǎn)遠(yuǎn)優(yōu)于當(dāng)年評(píng)測的最佳系統(tǒng),要么在評(píng)測中獲得第一,并遠(yuǎn)遠(yuǎn)領(lǐng)先第二名。

圖2 過濾器的學(xué)習(xí)曲線

圖2給出了過濾器在不同的測試集合上立即反饋的學(xué)習(xí)曲線。過濾器在SEWM 07立即反饋上的表現(xiàn)極其出色,垃圾郵件誤判率=0.00%,正常郵件誤判率=0.00%,邏輯誤判率=0.00%,1-ROCA=0.000 0%,因此出現(xiàn)了其對(duì)應(yīng)的學(xué)習(xí)曲線與X軸重回的現(xiàn)象。從圖2可以看出,過濾器的學(xué)習(xí)性能極好,在經(jīng)歷了一定數(shù)量的學(xué)習(xí)后(對(duì)應(yīng)于一段時(shí)間的實(shí)際應(yīng)用),過濾器幾乎不再出現(xiàn)錯(cuò)誤。

5 結(jié)論

垃圾郵件與垃圾郵件過濾是電子郵件應(yīng)用中矛和盾。垃圾郵件的發(fā)送者不斷改進(jìn)垃圾郵件的發(fā)送技術(shù),以便使垃圾郵件不被過濾。在這種情況下,需要垃圾郵件過濾器能夠適應(yīng)不斷演進(jìn)的垃圾郵件,因此采用在線學(xué)習(xí),使得過濾器能夠以增量學(xué)習(xí)的方式調(diào)整過濾器的參數(shù),保證過濾器的性能。本文針對(duì)垃圾郵件過濾過濾問題,采用在線學(xué)習(xí)方式,使過濾器具備處理不斷變化的垃圾郵件能力,這是本文描述的過濾器能夠取得成功的基礎(chǔ)。

高性能中文垃圾郵件過濾器的設(shè)計(jì)是一個(gè)整體工作,涉及到模型的學(xué)習(xí)方式、模型的選擇、特征抽取等多個(gè)方面,不能單純地強(qiáng)調(diào)某一方面而忽略其他方面,要尋求整體最優(yōu)解決方案。本文采用在線邏輯回歸模型這一典型的判別學(xué)習(xí)模型,該模型具有處理速度快、適應(yīng)于在線學(xué)習(xí)的特點(diǎn),奠定了高性能過濾器的基礎(chǔ);提出了字節(jié)級(jí)n元文法獲取郵件特征,簡化了特征提取,提高了特征提取的速度,該方法與語言無關(guān),并使得過濾器具備處理圖像、病毒等復(fù)雜對(duì)象的能力,提高了過濾器的性能;采用TONE方法進(jìn)行訓(xùn)練,減輕了系統(tǒng)對(duì)訓(xùn)練數(shù)據(jù)的需求,提高了系統(tǒng)的效率,同時(shí)還提高了系統(tǒng)的魯棒性。實(shí)驗(yàn)結(jié)果表明,本文的方法的性能極佳,本文描述的過濾器是當(dāng)前性能最好的中文垃圾郵件過濾器之一。

[1] V.N.Vapnik.Statistical Learning Theory[M].New York,USA：JohnW iley&Sons,Inc.1998：1-18.

[2] A.Bratko,B.Filipi?,G.V.Cormack et al.Spam Filtering Using Statistical Data Comp ression Models[J].The Journal o f Machine Learning Research archive,2006,7：2673-2698.

[3] G.H ulten and J.Goodman.Tutorial on Junk E-mail Filtering[C]//The Twenty-First International Conference on M achine Learning(ICML 2004).2004：(Invited Talk,http：//research.m icrosoft.com/en-us/um/peop le/joshuago/icm ltutoria lannounce.htm).

[4] D.Sculley,G.M.Wachman.Relaxed Online SVM s for Spam Filtering[C]//The 30th Annual International ACM SIGIR Con ference(SIGIR'07).New York,NY,USA ：ACM,2007 ：415-422.

[5] J.Goodman and W.Yih.On line Discrim inative Spam Filter Training[C]//Third Conference on Email and Anti-Spam(CEAS 2006).Mountain V iew,California,USA.2006：113-115.(http ：//www.ceas.cc/2006/22.pd f).

[6] D.Scu lley.Advances in Online Learning-based Spam Filtering[D].Medford,M A,USA：Tufts University.2008.

[7] 蘇綏,林鴻飛,葉正.基于字符語言模型的垃圾郵件過濾[J].中文信息學(xué)報(bào),2009,23(2)：41-47.

[8] P.Hayati,V.Potdar.Evaluation of spam detection and prevention framew orks for email and image spam：a state of art[C]//International Conference on Information Integration and web-based Applications and Services(iiWAS 2008)workshops：Proceedings o f the 10th Internationa l Conference on In formation Integration and Web-based App lications&Services(A IIDE 2008).New York,NY,USA：ACM.2008：520-527.

[9] G.V.Cormack,A.Bratko.Batch and On line Spam Filter Comparison.[C]//Third Conference on Email and Anti-Spam(CEAS 2006).Mountain View,California,USA.2006.

[10] J.M.M.Cruz,G.V.Cormack.Using old Spam and H am Samp les to Train Email Filters[C]//6th Conference on Email and Anti-Spam.in Mountain V iew,California,USA,2009.

[11] G.V.Cormack.University o f Waterloo Participation in the TREC 2007 Spam T rack[C]//The Six teenth Text REtrieval Con ference(TREC 2007)Proceedings.Gaithersburg,Mary land,USA.2007.

[12] 劉伍穎,王挺.基于多過濾器集成學(xué)習(xí)的在線垃圾郵件過濾[J].中文信息學(xué)報(bào),2008,22(1)：67-73.

[13] G.Cormack,T.Lynam.TREC 2005 Spam Track Overview[C]//The Fourteenth Tex t REtrieval Conference(TREC 2005)Proceedings.Gaithersburg,M D,USA.2005.