題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 高性能中文垃圾郵件過濾系統(tǒng)
- 小類：
- 信息技術(shù)
- 簡介：
- 隨著電子郵件的廣泛應(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è)在線二值分類問題，即將郵件區(qū)分為Spam(垃圾郵件) 或Ham(正常郵件)。近幾年，基于機(jī)器學(xué)習(xí)的文本分類法在垃圾郵件過濾中發(fā)揮了巨大的作用，典型的方法包括貝葉斯方法、支持向量機(jī)（SVM，Support Vector Machine）方法、最大熵方法、PPM(Prediction by Partial Match)壓縮算法等。由于這些方法過濾正確率高、成本低，因此機(jī)器學(xué)習(xí)方法稱為當(dāng)前的主流方法。應(yīng)用機(jī)器學(xué)習(xí)方法對垃圾郵件進(jìn)行過濾時(shí)涉及到3個(gè)問題：模型選擇、特征抽?。ㄠ]件表示）以及訓(xùn)練方法。 從模型上看，機(jī)器學(xué)習(xí)技術(shù)可以粗略分為生成模型（如貝葉斯模型）和判別模型（如SVM、最大熵模型）。在相關(guān)領(lǐng)域——文本分類中，判別模型的分類效果比生成模型的分類效果要好，特別在沒有足夠多的訓(xùn)練數(shù)據(jù)的時(shí)候，這種現(xiàn)象更明顯。在生成模型方面，著名的Bogo系統(tǒng)就是基于貝葉斯模型的，在TREC評測中作為基準(zhǔn)（Baseline）系統(tǒng)。用于數(shù)據(jù)壓縮的CTW(context tree weight)和PPM(Prediction by Partial Match)等壓縮算法被引入到了垃圾郵件過濾。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)，證明了在郵件過濾上，判別模型的分類效果比生成模型的分類效果要好。不嚴(yán)格的在線支持向量機(jī)（Relaxed Online SVM）克服了支持向量機(jī)計(jì)算量大的問題被用于解決垃圾郵件過濾的問題，并在TREC 2007評測中取得了很好效果。Goodman和Yih提出使用在線邏輯回歸模型，避免了SVM、最大熵模型的大量計(jì)算，并取了與上一年度（2005年）最好結(jié)果可比的結(jié)果。 在特征抽?。脆]件表示）上，郵件的文本內(nèi)容是當(dāng)前過濾器處理的重點(diǎn)。大多數(shù)英文過濾器以詞作為過濾單元，中文過濾器則是以詞作為過濾單元。由于垃圾郵件對文本的內(nèi)容進(jìn)行了變形，使得上述方法存在缺陷。非精確的字符串匹配被用于解決這個(gè)問題，但該方法只對英文垃圾郵件過濾有效，無法直接用于中文垃圾郵件過濾。在信息檢索領(lǐng)域的字符級n元文法被引入垃圾郵件過濾，并在TREC評測中取得優(yōu)于詞袋（Bag of word）假設(shè)的結(jié)果。鑒于大量垃圾郵件將文本內(nèi)容轉(zhuǎn)換為圖像，基于圖像分析(Image Analysis)的過濾技術(shù)近年來得到重視。 在訓(xùn)練方法上，最簡單也是最常用的訓(xùn)練方法就是對每一封郵件都進(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è)方向走過了頭，僅對誤判的郵件進(jìn)行訓(xùn)練導(dǎo)致過濾器訓(xùn)練數(shù)據(jù)不足，其對準(zhǔn)確率仍有影響。TONE（Train On/Near Error）在TOE基礎(chǔ)上加以改進(jìn)，預(yù)設(shè)一個(gè)分?jǐn)?shù)界限，當(dāng)郵件得分與判斷閥值之差的絕對值在界限之內(nèi)時(shí)，即使正確判斷也進(jìn)行訓(xùn)練。 本文采用邏輯回歸模型、字節(jié)級n元文法和TONE訓(xùn)練方法進(jìn)行中文垃圾郵件過濾。本文描述的系統(tǒng)參加了中國計(jì)算機(jī)學(xué)會(huì)主辦的SEWM（Search Engine and Web Mining）2008垃圾郵件過濾評測，獲立即反饋、主動(dòng)學(xué)習(xí)、延遲反饋全部在線評測項(xiàng)目的第一，性能優(yōu)于第二名100倍左右；在另外兩個(gè)中文測試集（SEWM 2007和TREC05c）上也顯著優(yōu)于當(dāng)年評測的最好結(jié)果。
- 詳細(xì)介紹：
- 1 邏輯回歸模型 邏輯回歸（Logistic Regression，LR)模型，和SVM一樣，是一種判別學(xué)習(xí)模型。判別學(xué)習(xí)模型與以貝葉斯為代表的生成模型有本質(zhì)差異。傳統(tǒng)生成模型認(rèn)為數(shù)據(jù)都是某種分布生成的，并試圖根據(jù)這種分布建模。采用最大似然估計(jì)(maximum likelihood estimation，簡稱MLE)來求解模型參數(shù)，并用平滑算法來解決數(shù)據(jù)稀疏問題。這種方法僅當(dāng)以下兩個(gè)條件都滿足時(shí)才是最優(yōu)的：第一，數(shù)據(jù)的概率分布形式是已知的；第二，存在足夠大的訓(xùn)練數(shù)據(jù)時(shí)才能采用最大似然估計(jì)(maximum likelihood estimation，簡稱MLE)來求解模型參數(shù)。但在實(shí)際應(yīng)用中，這兩個(gè)條件很多時(shí)候無法滿足。判別學(xué)習(xí)模型是與生成模型相對應(yīng)的一類建模方法。其假設(shè)條件比MLE弱得多，只要求訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)來自同一個(gè)分布即可。而且，判別學(xué)習(xí)算法的目標(biāo)往往與實(shí)際應(yīng)用的評價(jià)標(biāo)準(zhǔn)密切相關(guān)(如使模型在訓(xùn)練數(shù)據(jù)上的錯(cuò)誤率最小化)。因此判別學(xué)習(xí)模型的性能往往要優(yōu)于生成模型。邏輯回歸模型和SVM本質(zhì)上是一致的，都是在尋找具有最大間隔的超平面，不同的是損失函數(shù)（經(jīng)驗(yàn)風(fēng)險(xiǎn)）的定義不同。但從計(jì)算復(fù)雜度上看，邏輯回歸模型的計(jì)算復(fù)雜要明顯低于SVM，其分類速度要也比SVM快得多。 在基于內(nèi)容的郵件過濾系統(tǒng)中，影響一封郵件是垃圾郵件還是非垃圾郵件的因素是該郵件中的特征。 應(yīng)用邏輯回歸模型，可以根據(jù)郵件的特征判斷該郵件是垃圾郵件的概率(公式如picture1所示)。 2 基于字節(jié)級n元文法的特征提取 郵件過濾的依據(jù)是郵件的特征，特征項(xiàng)的定義，是影響分類性能的關(guān)鍵因素。和文本分類問題相比，郵件過濾有其特殊之處。反垃圾郵件技術(shù)在進(jìn)步，發(fā)送垃圾郵件的技術(shù)也在不斷地提高。由于巨大的利益驅(qū)動(dòng)，狡猾的垃圾郵件發(fā)送者對其電子郵件信息進(jìn)行多方面的偽裝，通過各種手段將垃圾郵件偽裝為正常郵件。同時(shí)，大量垃圾郵件以圖像的形式出現(xiàn)，導(dǎo)致傳統(tǒng)方法失效；單純的依賴郵件的文本內(nèi)容對含有病毒的垃圾郵件無能為力。 針對垃圾郵件特征提取面臨的問題，提出了基于字節(jié)級n元文法的特征提取方法。字節(jié)級n元文法在處理郵件文本內(nèi)容時(shí)，提取了郵件的文本內(nèi)容，在處理郵件的附件、所包含的圖片等組成成分時(shí)，提取了它們的二進(jìn)制特征，因此能夠在一個(gè)簡單的框架下處理以往很難處理問題。采用字節(jié)級n元文法提取郵件特征，避免了繁雜的郵件解析、漢字編碼轉(zhuǎn)換等工作，并使系統(tǒng)具有處理圖像、病毒郵件的能力。 字節(jié)級n元文法，將郵件按字節(jié)流進(jìn)行大小為n的滑動(dòng)窗口操作，形成長度為n 的字節(jié)片斷序列，每個(gè)字節(jié)片斷稱為gram。n元文法 按字節(jié)流進(jìn)行采用長度為n 的窗口切分，如：hellowolrd，按照n=4時(shí)進(jìn)行滑動(dòng)窗口切分為：hell、ello、llow、lowo、owol、wolr、olrd這樣7個(gè)4-gram。采用n元文法信息作為郵件特征具有以下特點(diǎn)：無需任何詞典支持，無需進(jìn)行分詞處理；無需語言學(xué)先驗(yàn)知識；無需對郵件進(jìn)行預(yù)處理，將郵件當(dāng)作無差別的字節(jié)流對待，不用考慮文字編碼的問題，同時(shí)具有處理復(fù)雜文件的能力，如HTML格式郵件、圖像文件、壓縮文件。與以詞字、詞組等為特征元素相比，這樣定義特征元素能有效防止了垃圾郵件信息的可能被繞過的情況。如product進(jìn)行文字變形，變換為p!roduct，pro_duct，prod-uct等等，基于詞字、詞組的過濾器就可能識別不出該特征，而基于字節(jié)的n元文法仍可以有效識別出該特征。例如，當(dāng)n=4時(shí)，product進(jìn)行特征抽取如下：prod、rodu、oduc、duct；當(dāng)product文字變形后變?yōu)閜rod-uct時(shí)進(jìn)行特征抽取如下：prod、rod-、od-u、d-uct、-uct；兩者共有的特征是prod。當(dāng)出現(xiàn)特征prod時(shí)，則該完整的單詞為product的概率比只捕捉到特征prod時(shí)的概率要大得多。 中文使用至少2個(gè)字節(jié)表示一個(gè)字(如GB2312使用兩個(gè)字節(jié)表示1個(gè)漢字，GB18030使用兩個(gè)字節(jié)或四個(gè)字節(jié)表示1個(gè)漢字)，不使用空格作為詞的分隔符，因此，如果對漢字進(jìn)行文字變換程度太大的話，是很難讓人讀懂的，如“胡錦濤”，常見的變形文字是“胡.錦.濤”、“hu錦濤”等，這種文字變形使得典型的以詞為過濾單元的方法失效。但在n元文法下，能夠提取有效特征，表明了該郵件的性質(zhì)。以詞作為過濾單元，詞作為最小的能自由運(yùn)用的語言單位，將有助于過濾性能的提高，需要進(jìn)行編碼識別和分詞，但分詞的準(zhǔn)確度難以保證，尤其是未登錄詞的識別性能難以得到保證，同時(shí)難以處理文字變形；若以字作為過濾單元，不需要進(jìn)行分詞，實(shí)現(xiàn)起來比較容易，但如字的語義表達(dá)能力較弱，上下文信息太少。 在實(shí)驗(yàn)中使用了字節(jié)級4-gram，并且每一封郵件僅取前3000個(gè)4-gram。郵件的特征值為布爾值，即郵件包含某個(gè)4-gram，其值為1，否則為0。 3 TONE訓(xùn)練方法 TONE（Train On or Near Error）方法也被稱之為Thick Threshold方法，該方法是在TOE基礎(chǔ)上加以改進(jìn)，預(yù)設(shè)一個(gè)分?jǐn)?shù)界限，當(dāng)郵件得分與判斷閥值之差的絕對值在界限之內(nèi)時(shí)，即使正確判斷也進(jìn)行訓(xùn)練。 現(xiàn)在說明該方法的應(yīng)用。對于本文采用的邏輯回歸模型，當(dāng)郵件的得分大于等于0.5時(shí)，就判斷成垃圾郵件；反之，當(dāng)當(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)練方法只對分類面附近的樣本進(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)如picture2所示。 垃圾郵件的在線過濾模式如picture3所示。 評估結(jié)果如picture4所示。 評測結(jié)果的(1-ROCA)%圖如pricture5所示。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 隨著電子郵件廣泛應(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ì)損失。2007年第四季度中國網(wǎng)民平均每周收到的垃圾郵件比例為55.65%，迫切需要有效的技術(shù)解決垃圾郵件泛濫的問題。 故設(shè)計(jì)此系統(tǒng)通過一定的技術(shù)手段對郵件內(nèi)容進(jìn)行分析，進(jìn)而判斷郵件是否為垃圾郵件。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 1.采用邏輯回歸模型。計(jì)算復(fù)雜度低，分類速度快。 2.基于字節(jié)級n元文法的特征提取。有效解決了垃圾郵件特征獲取的問題，應(yīng)用該特征不僅簡化了特征提取，還使得過濾器能夠處理圖像、病毒郵件的能力，為大幅提高垃圾郵件過濾器的性能奠定了基礎(chǔ)。 3.采用TONE訓(xùn)練方法。減輕了系統(tǒng)對訓(xùn)練數(shù)據(jù)的需求，提高了系統(tǒng)的效率，同時(shí)還提高了系統(tǒng)的魯棒性。
應(yīng)用價(jià)值和現(xiàn)實(shí)意義
- 該方法的性能極佳，能有效地對郵件的內(nèi)容進(jìn)行分析，進(jìn)而判斷一封郵件是否為垃圾郵件。 該系統(tǒng)可做為網(wǎng)站、個(gè)人用戶及有過濾郵件需要的機(jī)構(gòu)的郵件過濾工具，從一定程度上解決相關(guān)人員在垃圾郵件方面的困擾，節(jié)省人力、物力。 如果此系統(tǒng)得到推廣，將能從一定程度上解決垃圾郵件泛濫的現(xiàn)狀，節(jié)省網(wǎng)絡(luò)資源、用戶的寶貴時(shí)間和上網(wǎng)費(fèi)用，減少由垃圾郵件帶來的經(jīng)濟(jì)損失。
學(xué)術(shù)論文摘要
- 設(shè)計(jì)并實(shí)現(xiàn)了基于在線過濾模式高性能中文垃圾郵件過濾系統(tǒng)，能夠較好地好識別不斷變化的垃圾郵件。以邏輯回歸模型為基礎(chǔ)，本文提出了字節(jié)級n元文法提取郵件特征，并采用TONE（Train On or Near Error）方法訓(xùn)練建立過濾器。在多個(gè)中文垃圾郵件過濾評測數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，本文過濾器的性能在TREC 06數(shù)據(jù)上優(yōu)于由于當(dāng)年評測的最好成績，在SEWM 07立即反饋上1-ROCA值達(dá)到了0.0000%，并以絕對優(yōu)勢獲得了SEWM 08評測的所有在線過濾任務(wù)的第一名。
獲獎(jiǎng)情況
- 此系統(tǒng)參加了中國計(jì)算機(jī)學(xué)會(huì)主辦的SEWM（Search Engine and Web Mining）2008垃圾郵件過濾評測，獲立即反饋、主動(dòng)學(xué)習(xí)、延遲反饋全部在線評測項(xiàng)目的第一，性能優(yōu)于第二名100倍左右；在另外兩個(gè)中文測試集（SEWM 2007和TREC05c）上也顯著優(yōu)于當(dāng)年評測的最好結(jié)果。
鑒定結(jié)果
- 附加材料中的“SEWM2008-task3-overview.ppt”中的“測評相關(guān)說明”和“測評結(jié)果分析”兩部分有詳細(xì)說明。
參考文獻(xiàn)
- [1]V. N. Vapnik. Statistical Learning Theory[M]. New York, USA: John Wiley & Sons, Inc. 1998:1-18. [2]A. Bratko, B. Filipi?, G.V. Cormack et al. Spam Filtering Using Statistical Data Compression Models[J]. The Journal of Machine Learning Research archive, 2006,7:2673-2698 [3]G. Hulten and J. Goodman. Tutorial on junk e-mail filtering[C]. The Twenty-First International Conference on Machine Learning (ICML 2004). 2004: (Invited Talk, icmltutorialannounce.htm) [4]D. Sculley, G. M. Wachman. Relaxed Online SVMs for Spam Filtering[C]. The 30th Annual International ACM SIGIR Conference (SIGIR’07). New York, NY, USA:ACM, 2007:415-422 [5]J. Goodman and W. Yih. Online Discriminative Spam Filter Training[C]. Third Conference on Email and Anti-Spam (CEAS 2006). 2006:113-115. ( [6]D. Sculley. Advances in Online Learning-based Spam Filtering [D]. Medford, MA, USA: Tufts University.
同類課題研究水平概述
- 郵件過濾任務(wù)本質(zhì)上可以看作是一個(gè)在線二值分類問題，即將郵件區(qū)分為Spam(垃圾郵件) 或Ham(正常郵件)。近幾年，基于機(jī)器學(xué)習(xí)的文本分類法在垃圾郵件過濾中發(fā)揮了巨大的作用，典型的方法包括貝葉斯方法、支持向量機(jī)（SVM，Support Vector Machine）方法、最大熵方法、PPM(Prediction by Partial Match)壓縮算法等。由于這些方法過濾正確率高、成本低，因此機(jī)器學(xué)習(xí)方法稱為當(dāng)前的主流方法。應(yīng)用機(jī)器學(xué)習(xí)方法對垃圾郵件進(jìn)行過濾時(shí)涉及到3個(gè)問題：模型選擇、特征抽?。ㄠ]件表示）以及訓(xùn)練方法。 從模型上看，機(jī)器學(xué)習(xí)技術(shù)可以粗略分為生成模型（如貝葉斯模型）和判別模型（如SVM、最大熵模型）。在相關(guān)領(lǐng)域——文本分類中，判別模型的分類效果比生成模型的分類效果要好，特別在沒有足夠多的訓(xùn)練數(shù)據(jù)的時(shí)候，這種現(xiàn)象更明顯。在生成模型方面，著名的Bogo系統(tǒng)就是基于貝葉斯模型的，在TREC評測中作為基準(zhǔn)（Baseline）系統(tǒng)。用于數(shù)據(jù)壓縮的CTW(context tree weight)和PPM(Prediction by Partial Match)等壓縮算法被引入到了垃圾郵件過濾。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)，證明了在郵件過濾上，判別模型的分類效果比生成模型的分類效果要好。不嚴(yán)格的在線支持向量機(jī)（Relaxed Online SVM）克服了支持向量機(jī)計(jì)算量大的問題被用于解決垃圾郵件過濾的問題，并在TREC 2007評測中取得了很好效果。Goodman和Yih提出使用在線邏輯回歸模型，避免了SVM、最大熵模型的大量計(jì)算，并取了與上一年度（2005年）最好結(jié)果可比的結(jié)果。
