淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-3006200513513100
中文論文名稱 決策樹法在垃圾郵件過濾之應用
英文論文名稱 Application of Decision Tree Methods on Spam Filtering
校院名稱 淡江大學
系所名稱(中) 統計學系碩士班
系所名稱(英) Department of Statistics
學年度 93
學期 2
出版年 94
研究生中文姓名 蔡孟娟
研究生英文姓名 Meng-Chuan, Tsai
學號 692460560
學位類別 碩士
語文別 中文
口試日期 2005-06-13
論文頁數 63頁
口試委員 指導教授-陳景祥
委員-歐士田
委員-張春桃
中文關鍵字 垃圾信  決策樹  C4.5  分類迴歸樹  QUEST  貝氏分類器 
英文關鍵字 Spam  Decision Tree  C4.5  C&RT  QUEST  Bayes Classifier 
學科別分類 學科別自然科學統計
中文摘要 由於電腦科技的進步與網際網路的發達,電子郵件已成為現代人日常生活中溝通交流的重要媒介。電子郵件方便寄送,成為商品廣告的最佳行銷管道,因此產生垃圾郵件的問題。垃圾信成長速度很快,不只佔用網路資源、造成系統負擔,也浪費收件者的時間。因此,近年來過濾垃圾信的技術已成為一項熱門的研究領域。本研究根據電子郵件的14個特徵,透過資料採礦技術中的三種決策樹方法,將電子郵件分類為垃圾信與正常信,並與時下最常被用來過濾垃圾信的貝氏分類器方法做比較。我們的研究發現,在考慮分類結果與風險成本的情況下,C4.5決策樹的結果最好,其分類時間也比其他二種決策樹方法快。本研究並發現,在做分類前若先使用白名單,可以降低正常信被誤判的機率。
英文摘要 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.
論文目次 目  錄

目錄 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
參考文獻 參考文獻
[1] Dent KD,林長毅譯,Postfix技術手冊,美商歐萊禮股份有限公司台灣分公司,2004。
[2] 毛慶禎,寫信與收信,http://www.lins.fju.edu.tw/~mao/internet/firstmail.htm。
[3] 吳文峰,中文郵件分類器之設計及實作,私立逢甲大學資訊工程學系碩士論文,2002。
[4] 李先育,垃圾郵件防治篩選之研究,私立中國文化大學資訊管理學系研究所碩士論文,2004。
[5] 李啟鑫,資料探勘與統計技術的自由軟體整合介面,私立淡江大學統計學系應用統計研究所碩士論文,2004。
[6] 葉怡威,類神經網路模式應用與實作,儒林圖書公司,2004。
[7] 趙銘森,林志忠,PHP之戀,上奇科技股份有限公司,2003。
[8] 劉容生,天涯@比鄰,科學人, 1, 2002。
[9] 蔡瓊輝,使用倒傳遞類神經網路學習垃圾郵件行為的類型,私立樹德科技大學資訊管理系碩士論文,2004。
[10] 鍾在豐,中文垃圾郵件之偵測及實作,私立中華大學資訊工程學系碩士論文,2004。
[11] 謝邦昌,資料採礦入門及應用-從統計技術看資料採礦,資商訊息顧問股份有限公司,2001。
[12] A Plan for Spam. http://www.paulgraham.com/spam.html.
[13] Androutsopoulos I, Koutsias J, Chandrinos KV and Spyropoulos CD. An Experimental Comparison of Naïve Bayesian and Keyword-Based Anti-Spam Filtering with Personal E-mail Messages. In Proc. of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Athens, Greece, pp. 160-167, 2000.
[14] Bogofilter. http://bogofilter.sourceforge.net/.
[15] Borgelt C. A Navie Bayes Classifier Plug-In for DataEngine. In Proc. of the 3rd Data Analysis Symposium, pp.87-90, 1999
[16] Breiman L, Friedman JH, Olshen RA and Stone CJ. Classification and Regression Trees, Wadsworth, Pacific Grove, 1984.
[17] Carreras X and Màrquez L. Boosting Trees for Anti-Spam Email Filtering. In Proc. of RANLP-01, 4th International Conference on Recent Advances in Natural Language Processing, Tzigov Chark, BG, 2001.
[18] Chen D, Chen T and Ming H. Spam Email Filter-Using Naïve Bayesian, Decision Tree, Neural Network and AdaBoost. http://www.cs.iastate.edu/~tongjie/spamfilter/paper.pdf.
[19] Cohen WW. Learning Rules that Classify E-Mail, In Proc. of the 1996 AAAI Spring Symposium on Machine Learning in Information Access, 1996
[20] Crawford E, Kay K and McCreath E. Automatic Induction of Rules for e-mail Classification. In Proc. of the Sixth Australasian Document Computing Symposium, Coffs Harbour, Australia, 2001.
[21] Drucker H, Wu D and Vapnik VN. Support Vector Machines for Spam. IEEE Trans. on Neural Networks, 10(5): 1048-1054, 1999.
[22] Hird S. Technical Solutions for Controlling Spam. In Proc. of AUUG2002, Melboume, 2002.
[23] Johnson DE, Oles FJ, Zhang T and Goetz T. A decision-tree-based symbolic rule induction system for text categorization. IBM Systems Journal, 41(3): 428-437, 2002.
[24] Loh WY and Shih YS. Split Selection Methods for Classification Trees. Statistica Sinica, 7(4): 815-840, 1997.
[25] MailShell Anti-Spam. http://www.mailshell.com/.
[26] MailWasher Pro. http://www.mailwasher.net/.
[27] Manco G, Masciari E, Ruffolo M and Tagarelli A. Towards an Adaptive Mail classifier. In Proc. Conference of the Italian Association of Artificial Intelligence (AIIA 2002), 2002.
[28] Quinlan JR. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
[29] Sahami M, Dumais S, Heckerman D and Horvite E. A Bayesian Approach to Filtering Junk E-Mail. In Learning for Text Categorization-Papers from the AAAI Workshop, pp. 55-62, 1998.
[30] Shih YS. QUEST User Manual. http://www.stat.wisc.edu/~loh/quest.html.
[31] Spam Bouncer. http://www.spambouncer.com/.
[32] SpamKiller Guide. http://www.mcafee.com/tw/.
[33] Spam Prevention Solution. http://www.trendmicro.com/.
[34] Thunderbird. http://www.mozilla.org/.
[35] Wang JH and Chien LF. Toward Automated E-mail Filtering-An Investigation of Commercial and Academic Approaches. In Proc. of TANET, pp. 687-692, 2003.
[36] Wood P. A Spammer in the Works. MessageLabs Ltd., 2004.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2005-07-11公開。
  • 同意授權瀏覽/列印電子全文服務,於2005-07-11起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信