由於電腦科技的進步與網際網路的發達，電子郵件已成為現代人日常生活中溝通交流的重要媒介。電子郵件方便寄送，成為商品廣告的最佳行銷管道，因此產生垃圾郵件的問題。垃圾信成長速度很快，不只佔用網路資源、造成系統負擔，也浪費收件者的時間。因此，近年來過濾垃圾信的技術已成為一項熱門的研究領域。本研究根據電子郵件的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.