臺灣博碩士論文加值系統

資料探勘分類學中，在資料類別分配不平衡(imbalanced class distribution)或類別誤判成本(misclassification cost)差異很大時，成本應列入考量且績效標準應由極大化正確率轉為極小化錯誤分類成本，也就是所謂的成本敏感性分類(cost-sensitive classification)。要使機器學習具有成本敏感性，最常用的方法就是以具有成本敏感性類別分配的訓練資料來取代傳統自然比例分配(natural distribution)的訓練資料來進行資料分類，也就是將誤判成本較高的類別資料以較高訓練樣本比率來訓練分類器，以降低總誤判成本。本研究以決策樹，約略集合，倒傳遞類神經網路，與支援向量機四種分類器，配合四個UCI資料集，在類別誤判成本已知且訓練樣本量固定條件下，調整訓練樣本的類別比例分配，訓練出不同的分類器，再以自然比例之測試樣本進行測試，獲得不同類別比例分配之總誤判成本，並深入探討不同的分類器對訓練樣本的類別比例分配之成本敏感性。結果顯示：(1)超抽少數類別訓練樣本數(1:10,1:9,…,1:2)所訓練出來的分類器，會使誤判成本穩定維持在最低點，而且超抽2倍至10倍少數類別訓練樣本數，對總誤判成本並無顯著影響。反之，減抽少數類別訓練樣本數(2:1,3:1,…,10:1)所訓練出來的分類器，會使總誤判成本逐漸增加。(2)改變不同類別分配所得到不同分類器對誤判成本曲線斜率高低之影響決定於少數類別誤判增加筆數對多數類別誤判減少筆數之比( )。(3)相較於決策樹、約略集合、與倒傳遞類神經網路，支援向量機對於改變不同類別分配訓練樣本之成本敏感性較大，在微超抽改變至微減抽少數類別訓練樣本(1:2 to 2:1)時，誤判成本會急速增加。

關鍵詞：成本敏感性分類，類別分配不平衡

In the environment of imbalanced class distribution or misclassification cost diverseness, misclassification cost should be emphasized and the performance measure should be switched from maximizing accurate rate to minimizing misclassification cost. To build a cost-sensitive classifier, the most common way is to replace training data set of traditional natural class distribution by one of over-sampling train data of higher misclassification cost.
In this paper, we train classifiers with various combinations of class distribution training data and then test by natural class distribution testing data. The accumulated misclassification cost cures along with different class distributions training data are then plotted and analyzed to explore the cause-effect relationship. Four types of classifier: decision tree, rough set, back-propagation neural network, and support vector machine, and four UCI data sets with imbalanced class distribution are included in this experiment. Assuming the minority of four UCI data set is actual positive, the misclassified minority belongs to false positive (FP) while the misclassified majority belongs to false negative (FN).
Results showed that: First, classifiers trained by over-sampling minority class maintain minimum accumulated misclassification cost in wide ratio range, 1:10, 1:9, …, 1:2, of majority to minority while under-sampling minority increase accumulated misclassification cost dramatically. Secondly, the slope of accumulated misclassification cost curves is determined by the ratio of the derivative of fault positive (FP) to the derivative of fault negative (FN) rate. Eventually, support vector machine is most sensitive to the class distribution training data. The accumulated misclassification cost will dramatically increase from transition of slight over-sampling of majority to minority (1:2) to slight under-sampling minority (2:1).

keywords：Cost-sensitive classification; imbalanced class distribution

摘要 I
ABSTRACT III
目錄 V
表目錄 VII
圖目錄 VIII
第一章 緒論 1
1.1. 研究背景 1
1.2. 研究目的 2
1.3. 研究架構 3
第二章 文獻探討 5
2.1. 決策樹 5
2.2. 倒傳遞類神經網路 8
2.3. 支援向量機 15
2.3.1 線性支援向量機 16
2.3.2 非線性支援向量機 20
2.4. 約略集合理論 22
2.4.1 資訊系統(information system) 23
2.4.2 不可區分的關係（indiscernibility relation） 24
2.4.3 近似集 25
2.4.4 屬性刪減與核心 25
2.4.5 決策規則 26
第三章 研究方法 28
3.1 資料集 29
3.2 訓練與測試樣本設計 30
3.3 分類器 32
3.4 誤判成本計算與分析 33
第四章 結果分析 36
4.1 FP-FN增減關係 36
4.2 誤判成本曲線 39
4.3 FP增量與FN減量之分析 40
4.3.1 FP增量分析 40
4.3.2 FN減量分析 42
4.3.3 分析 44
第五章 結論 46
參考文獻 48

[1] 姚志成，「運用資料探勘技術建構脂肪肝預測模式」，中原大學資訊管理研究所碩士論文，民國九十三年。
[2] 廖介銘，「決策樹應用於糖尿病之探勘」，華梵大學資訊管理研究所碩士論文，民國九十二年六月。
[3] 吳國禎，「資料探索在醫學資料庫之應用」，中原大學醫學工程研究所碩士論文，民國八十八年。
[4] 蕭方智，「應用階層式粒子群方法於模糊決策樹之研究」，元智大學工業工程與管理研究所碩士論文，民國九十四 年七 月。
[5] 陳麗君，「應用資料探勘技術於信用卡黃金級客戶之顧客關係管理」，元智大學工業工程與管理研究所碩士論文，民國九十二年六月。
[6] 林芝儀 ，「應用資料探勘於信用卡授信決策模式之實證研究」，元智大學工業工程與管理研究所碩士論文，民國九十一年。
[7] 葉怡成，類神經網路模式應用與實作，儒林出版社，民國九十二年。
[8] 陳昭蓉，「以倒傳遞類神經網路作為規劃震災後災民疏散系統之應用」，國立台北科技大學建築與都市設計研究所碩士論文，民國九十三年七月。
[9] 施怡如，「虛擬智慧型顧客服務模式在電子商務之應用---以襯衫為例」，東海大學工業工程研究所碩士論文，民國八十九年六月。
[10]李文智，「以總體經濟變數與存託憑證探討對標的股股價預測模式影響之研究-以台積電為例」，大葉大學國際企業管理研究所碩士論文，民國九十五年二月。
[11]王進德、蕭大全，類神經網路與模糊控制理論入門，全華科技圖書，民國九十三年九月，第23-58頁。
[12]賴威利，「利用約略集合理論預測燒燙傷患者死亡率」，南台科技大學國際企業研究所碩士論文，民國九十四年七月。
[13]李慧慈，「利用約略集合理論預測網路銀行使用意願」，南台科技大學國際企業研究所碩士論文，中華民國九十三年六月。
[14]Weiss G. M., and Provost F., 「The Effect of Class Distribution on Classifier Learning, 」 Technical Report ML-TR-43, Department of Computer Science, Rutgers University, 2001.
[15]Zhou Zhi-Hua, and Liu Xu-Ying, 「Training Cost-Sensitive Neural Network with Methods Addressing the Class Imbalance Problem」 IEEE Transactions on Knowledge and Data Engineering, Vol. 18, NO. 1, 2006.
[16]Li Jin, Li Xiaoli, and Yao Xin, 「Cost-Sensitive Classification with Genetic Programming,」 Proceedings of the 2005 IEEE Congress on Evolutionary Computation, Vol.3, pp. 2114-2121.
[17]Ling C., and Li C., 「Data mining for direct marketing: Problems and solutions,」 Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, Menlo Park, CA: AAAI Press, 1998, pp. 73-79.
[18]Kubat M., and Matwin S., 」Addressing the curse of imbalanced training sets: One-sided selection,」 Pro-ceedings of the Fourteenth International Conference on Machine Learning., San Francisco, CA: Morgan Kaufmann, 1997, pp. 179-186.
[19]Chawla N. V., Bowyer K. W., Hall L. O., and Kegelmeyer W. P., 「SMOTE: Synthetic Minority Over-sampling Technique,」 Journal of Articial Intelligence Research, 16, 2002, pp.321-357.
[20]Quinlan J. R., 「Improved Use of Continuous Attributes in C4.5,」 Journal of Artificial Intelligence Research, 4, 1996, pp. 77-90.
[21]Quinlan J. R., 「Induction of Decision Trees」, Machine Learning, 1, 1986, pp. 81-106.
[22]Quinlan J. R., C4.5: Programs for Machine Learning, Morgan Maufman, San Francisco, CA, USA, 1993.
[23]Vapnik V. N., 「The Nature of Statistical Learning Theory,」 Springer Verlag, NY, USA, 1995.
[24]Burges C. J. C., 「A Tutorial on Support Vector Machines for Pattern Recognition,」 Data Mining and Knowledge Discovery, Vol.2, No.2, 1998, pp. 955-974.
[25]Scholkopf B., Burges C. J. C., Smola A. J., 」Introduction to Support Vector Learning,」 Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, USA, 1999, pp.1-15.
[26] Fletcher R., Practical Methods of Optimization, John Wiley and Sons Inc., 2nd edition, 1987.
[27]Gunn S. R., 「Support Vector Machines for Classification and Regression,」 University of Southampton Technical Report, 1998.
[28]Hsu Chih-Wei, Chang Chih-Chung, and Lin Chih-Jen, 「A Practical Guide to Support Vector Classification,」 Available: http://www.csie.ntu. edu.tw/~cjlin/papers/guide/guide.pdf,2003.
[29]Pawlak Zdzislaw, Rough Sets – Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, 1991.
[30]Pawlak Zdzislaw, 「Rough sets and intelligent data analysis,」 Information Sciences, Vol. 147, 2002, pp.1-12.
[31]Walczak B., and Massart D. L., 「Tutorial Rough Sets Theory,」 Chemometrics and Intelligent Laboratory Systems, Vol. 47, 1999, pp.1-16.
[32]Slowinski R., Zopounidis C., and Dimitras A.I., 「Prediction of Company acquisition in Greece by means of the rough set approach,」 European Journal of Operation Research, Vol. 100, 1997, pp. 1-15.