[[alternative]]An anti-spam algorithm for handling concept drift

碩士[[abstract]]垃圾郵件氾濫的問題一直沒有得到徹底的解決，各種垃圾郵件防治機制紛紛興起，其中以機器學習為主的垃圾郵件內容分類過濾最為盛行。而這些方法，主要都是基於所有的資料在固定不變的環境下之假設，但是在實際環境中，郵件內容會隨著概念的漂移而不斷變動，使得分類器在模型建立之初，都有不錯的分類效果，但隨著時間的演進與概念的漂移，郵件的分類正確率會逐漸下滑，因此必須有一個學習與調整的機制，針對資料集中新進與舊有郵件做相關的學習與調整。另一個郵件分類的問題是資料的偏斜，由於垃圾郵件的氾濫，垃圾郵件個數通常明顯的比正常郵件來的多，在分類的過程中，雖然垃圾郵件類別都有著較高的召回率，但是正常郵件類別的召回率卻相對不佳。因此本研究提出IFWB（Incremental Forgetting Weighted Bayesian，漸進遺忘權重貝氏）演算法，以貝氏分類為基礎，採用IGICF（Information Gain and Inverse Class Frequency，資訊增益與類別頻率倒數）擷取關鍵字，結合漸進遺忘機制與分類成本架構來解決郵件分類中概念漂移與資料偏斜的問題，最後透過實驗來驗證本研究所提出的郵件分類方法。[[abstract]]The overflow problem of spam has not been solved completely. Many anti-spam techniques have been proposed. Among them, the machine learning techniques are the most popular, but these works are based on a static environment assumption. In the real world application, the email context may change with concept drift. The classification result is usually good at the beginning, but along with time evolution and concept drift, the classification accuracy dropped down gradually. So a mechanism is needed to adjust the classifier according to the new incoming emails and the old emails in the dataset. Another problem of email categorization is data skewedness. Because of the spam overflow, the number of spam emails is far more than that of legitimate ones. In the classification result, the majority class is with good recall rate, but the minority class with poor recall rate. For these reasons, we propose an algorithm, IFWB (Incremental Forgetting Weighted Bayesian), based on Naïve Bayesian and IGICF (Information Gain and Inverse Class Frequency) feature extraction, combined with the gradual forgetting mechanism and cost-sensitive model to tackle concept drift and data skewedness. Finally, we demonstrate the effectiveness of the IFWB algorithm through a series of experiments.[[tableofcontents]]目錄 第1章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的 3 1.3 論文架構 5 第2章 文獻探討 6 2.1 垃圾郵件防治方法 6 2.2 分類演算法 9 2.3 概念漂移 13 2.4 資料偏斜 15 2.5 概念漂移之垃圾郵件過濾方法 16 第3章 IFWB演算法 21 3.1 相關演算法之選擇 21 3.2 IFWB演算法流程 23 3.3 字詞擷取 29 3.4 權重貝氏分類法 31 3.5 分類錯誤成本架構 37 第4章 實驗 39 4.1 郵件資料集與實驗說明 39 4.1.1. 實驗環境與郵件資料集 39 4.1.2. 實驗說明 41 4.2 實驗探討與分析 43 4.2.1. 實驗一 43 4.2.2. 實驗二 45 4.2.3. 實驗三 46 4.2.4. 實驗四 47 4.2.5. 實驗五 49 4.2.6. 實驗六 51 4.2.7. 實驗七 52 第5章 結論 54 參考文獻 58 圖目錄 圖 1：kNN運作原理 10 圖 2：類神經網路運作原理 12 圖 3：SVM運作原理 13 圖 4：字詞與案例間的關聯網 18 圖 5：ICBC調整分群架構機制 19 圖 6：訓練階段流程 23 圖 7：字詞庫於訓練階段建立與關鍵字集產生方法 27 圖 8：郵件資料集之向量矩陣 27 圖 9：分類階段流程 28 圖 10：線性的漸進遺忘方程式，N=100，k=80% 32 圖 11：IFWB在各個資料集下的分類結果 45 圖 12：IG、IGICF關鍵字詞擷取方法之分類結果 46 圖 13：貝氏與IFWB在概念漂移下的分類結果 47 圖 14：IFWB演算法在訓練集為SpamAssassin測試集為LingSpam下之分類結果 49 圖 15：TREC與SpamAssassin在各種遺忘速率k值下的分類結果 50 圖 16：在資料偏斜下，有無分類成本學習架構之正常郵件召回率 51 表目錄 表 1：關鍵字擷取演算法 31 表 2：範例郵件關鍵字資料表 35 表 3：分類成本矩陣 37 表 4：公開郵件資料集 40 表 5：實驗郵件資料集 41 表 6：各種正常郵件分類成本下之分類結果 52[[note]]學號: 696630036, 學年度: 9