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