[[alternative]]Application of decision tree methods on spam filtering

碩士[[abstract]]由於電腦科技的進步與網際網路的發達，電子郵件已成為現代人日常生活中溝通交流的重要媒介。電子郵件方便寄送，成為商品廣告的最佳行銷管道，因此產生垃圾郵件的問題。垃圾信成長速度很快，不只佔用網路資源、造成系統負擔，也浪費收件者的時間。因此，近年來過濾垃圾信的技術已成為一項熱門的研究領域。本研究根據電子郵件的14個特徵，透過資料採礦技術中的三種決策樹方法，將電子郵件分類為垃圾信與正常信，並與時下最常被用來過濾垃圾信的貝氏分類器方法做比較。我們的研究發現，在考慮分類結果與風險成本的情況下，C4.5決策樹的結果最好，其分類時間也比其他二種決策樹方法快。本研究並發現，在做分類前若先使用白名單，可以降低正常信被誤判的機率。[[abstract]]As a result of the progress on computer science and the development of Internet, Email has been the important communication medium in daily life. Email Advertising becomes the most efficient technique in marketing, and therefore arises the problem about spam. The amounts of spam increase quickly. It not only takes the network resources and makes the burden on system, but also wastes the receiver’s time. Spam filtering becomes a popular research issue in recent years. In this study, we use three decision tree methods of data mining technology to classify Emails into “spam” and “legitimate” based on fourteen characteristics of Email. The three decision tree methods are compared with bayes classifier, which is most often used in spam filtering at present. When the efficiency of classification and misclassification costs are considered, C4.5 method has the best outcome in our case study of spam mails. It takes the shortest test time among the three decision tree methods. Our study also shows that we can avoid misclassifying legitimate by using the white list before we apply the classification.[[tableofcontents]]目 錄 目錄 I 圖目錄 III 表目錄 IV 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機與目的 2 1.3 論文結構 3 第二章 文獻回顧與相關研究 5 2.1 垃圾信過濾技術 5 2.2 反制垃圾信(Anti-spam)工具 8 2.3 其他相關研究 9 第三章 電子郵件系統的基本架構 10 3.1 電子郵件的簡介 10 3.2 郵務系統的組成 11 3.3 電子郵件的基本架構 12 3.4 垃圾信的問題 15 3.5 電子郵件特徴之擷取 18 第四章 研究方法 22 4.1 決策樹簡介 22 4.2 C4.5決策樹 24 4.2.1 Gain準則 24 4.2.2 Gain ratio準則 26 4.2.3 C4.5分類器 28 4.3 C&RT演算法 30 4.4 QUEST演算法 32 4.5 貝氏分類器 33 4.6 PHP 35 4.6.1 PHP的優點 35 4.6.2 Multi-byte String 35 4.6.3 使用mailparse函數擷取郵件特徵 36 第五章 實作與評估 38 5.1 測試方法 38 5.1.1 資料來源與測試過程 38 5.1.2 測試環境與測試時間 39 5.1.3 測試結果的評估 40 5.2 C4.5、C&RT、QUEST與貝氏分類器之測試結果 42 5.3 風險成本分析 44 5.4 增加使用關鍵字的分析 48 5.4.1 建立白名單 50 5.4.2 建立黑白名單 51 5.4.3 討論 52 第六章 結論與建議 54 6.1 結論 54 6.2 後續研究 56 參考文獻 57 圖 目 錄 圖3.1 電子郵件的傳遞流程 11 圖3.2 電子郵件範例 13 圖4.1 決策樹的例子 23 圖4.2 C4.5產生的決策樹 28 圖4.3 C4.5產生的決策樹規則 29 圖4.4 以mailparse擷取電子郵件的程式範例 37 圖4.5 以mailparse擷取電子郵件的結果範例 37 圖5.1 垃圾信的精確率與檢出率 42 圖5.2 正常信的精確率與檢出率 43 圖5.3 錯誤率 44 圖5.4 風險成本 47 圖5.5 正常信的檢出率 52 表 目 錄 表2.1 分類郵件或過濾垃圾信的研究 7 表2.2 反制垃圾信的軟體 8 表3.1 變數說明 21 表4.1 高爾夫球賽的資料 25 表4.2 常用的mailparse函數 36 表5.1 測試環境 39 表5.2 測試時間 39 表5.3 分類結果列聯表 40 表5.5 風險成本表 45 表5.6 錯誤分類的風險成本比( ) 46 表5.8 降低正常信被誤判的情形 49 表5.10 建立白名單後的比較 50 表5.12 建立黑白名單後的比較 51 表6.1 測試結果整理與比較 54 表5.4 使用14個郵件特徵的分類結果 60 表5.7 使用14個郵件特徵的風險成本 61 表5.9 使用白名單與14個郵件特徵的分類結果 62 表5.11 使用黑白名單與14個郵件特徵的分類結果 63[[note]]學號: 692460560, 學年度: 9