臺灣博碩士論文加值系統

使用基因演算法來建構分類樹是一項創新的實驗研究。我們使用基因演算法不僅能用於輔助決策樹來決定最佳的屬性，並結合了資訊理論，以其作為分類樹中的分割準則，即最小化熵之概念。我們採用的方式是使用基因演算法，一開始以啟發式的作法來產生初始之演化族群，考量最小化之熵數與即時線上測試誤差為衡量依據，來找出分類樹中之最佳切割點，同時決定其切割屬性與切割值，一步步地以最佳節點將分類樹給推衍出來。在本研究中，我們針對五種具代表性的分類資料進行實驗，將提出的作法與其他決策樹演算法做比較。實驗結果顯示，本研究所提出之混合啟發式基因分類樹演算法能夠有效的降低分類樹中切割方式的複雜度，並能建構出較小的分類樹。此外，本研究亦開發了一套雛形系統，用以輔助分類樹的建構並自動產生一些規則以支援決策者制定決策。我們嘗試採用基因演算法去設計一套知識擷取系統，用以建構分類樹以進一步進行資料探勘之應用。

In this paper, using genetic algorithms to construct classification trees is a novel implement research. The Genetic Algorithm not only assists to get the optimal features as the tree nodes but also combine the information theory as the criterion of the classification trees to minimum the entropy. The splitting method of the subsets of individuals associated to the nodes is the Genetic Algorithm. The stopping criterion of the tree induction is based on a heuristic able to recognize whether the set of the individuals associated to a node of the tree is a sub-population, or not. And considering the information theory combined with Genetic Algorithm-based computing to induct the classification tree. Experimental results for five data mining classification problems are presented and compared with other decision trees algorithms. This Hybrid GA-Heuristic Classification Tree algorithm indicates that a Genetic algorithm reduces the complexity of the used splitting methods to construct a small tree. A prototype was presented to assistant the classification tree construction and produced a set of rules to support decision makers. We try to design a knowledge acquisition system using genetic algorithms to construct the classification trees applying to data mining.

1. Introduction................................................1
2. Literatures Review..........................................4
2.1 Classification...........................................4
2.2 Decision Trees...........................................4
2.3 Information Theory.......................................6
2.4 Genetic Algorithms.......................................7
2.5 Hybrid System with Genetic Algorithms and Decision Trees.8
3. The Proposed Methodology...................................11
3.1 The Proposed Method.....................................11
3.2 The HGCT Process........................................13
3.3 The Design of Optimization Algorithm....................15
4. Experiments and Results....................................17
4.1 Experiments Description.................................17
4.2 The Application Data Sets...............................18
4.3 The Results of Experiments..............................19
5. Conclusions................................................24
5.1 The HGCT Works..........................................24
5.2 Discussion..............................................25
5.3 Further Work............................................25
6. Reference..................................................27

[1] Akeel, A. A., " A Hybrid GA-Heuristic Search Strategy", AI Expert, pp.34-37, September 1994.
[2] Apte, G., Weiss, S., “Data Mining with Decision Trees and Decision Rules”, Future Generation Computer Systems, Vol. 13, pp.197-210, 1997.
[3] Bala, J., De Jong, K., "Using Learning to Facilitate the Evolution of Features for Recognizing Visual Concepts", Evolutionary Computation, Vol. 4, Issue 3, pp.297-312, Fall 1996.
[4] Bala, J., DeJong, K., Huang, J., Vafaie, H., Wechsler, H., "Visual Routine for Eye Detection Using Hybrid Genetic Architectures", Proceedings of the 13th International Conference on Pattern Recognition, Vol. 3, pp.606-610, 1996.
[5] Bala, J., Kenneth, A., Jong, D., Haung, J., Vafaie H., Wechsler, H., “Hybrid Learning Using Genetic Algorithms and Decision Trees for Pattern Classification”, IJCAI conference, Montreal, pp.19-25, August 1995.
[6] Breiman, L., Friedman, J., Olshen, R., Stone, C., Classification and Regression Trees, CRC Press, 1984.
[7] Breslow, L., D.W. Aha, "Simplifying Decision Trees: A Survey," Knowledge Engineering Review, Vol. 12, pp.1-40, 1997.
[8] Brown, D.E., Pittard, C.L., “Classification Trees with Optimal Multi-variate Splits”, Systems, Man and Cybernetics, vol. 3, pp. 475-477, International Conference on ''Systems Engineering in the Service of Humans'', 1993.
[9] Chai, B. B., Huang, T., Zhuang, X., Zhao, Y., Sklansky, J., "Piecewise Linear Classifiers Using Binary Tree Structure and Genetic Algorithm", Pattern Recognition, Vol. 29, No. 11, pp.1905-1917, 1996.
[10] Chai, B. B., Zhuang, X., Zhao, Y., Sklansky, J., “Binary Linear Decision Tree with Genetic Algorithm”, Pattern Recognition, Proceedings of the 13th International Conference, Vol. 3, pp.530-534, 1996.
[11] Christopher R. Westphal , Teresa Blaxton, Data Mining Solutions: Methods and Tools for Solving Real-World Problems, New York, Wiley, 1998.
[12] Dhar, V., Stein, R., Intelligent Decision Support Methods: The Science of Knowledge Work, Prentice-Hall Inc., 1997.
[13] Gelfand, S.B, Ravishankar, C.S, Delp, E.J., “An Iterative Growing and Pruning Algorithm for Classification Tree Design”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 2, pp.163 —174, Feb. 1991.
[14] Goldgerg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Publishing Company, 1989.
[15] Goodman, R.M. , S. Paclhaic, "Decision Design Using Information Theory", Knowledge Acquisition, Vol.2, No.1, pp.1-19, March 1990.
[16] Gray, N.A.B., "Capturing Knowledge Through Top-down Induction of Decision Trees", IEEE Expert [see also IEEE Intelligent Systems], Vol.53, pp.41-50, June 1990.
[17] Groth, R., Data Mining: A Hands-On Approach for Business Professionals, Prentice Hall, 1997.
[18] Hambaba, M.L., “Intelligent Hybrid System for Data Mining”, Computational Intelligence for Financial Engineering, Proceedings of the IEEE/IAFE 1996 Conference, pp.111, 1996.
[19] Holland, J. H., Adaptation In Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Mich, 1975.
[20] Holland, J. H., Holyoak, K. J., Nisbett, R. E., Thagard, P. R., Induction: Processes of Inference, Learning, and Discovery, MIT Press, Cambridge, Massachusetts 1986.
[21] Houben, I., Wehenkel, L., Pavella, M., “Coupling of K-NN with Decision Trees for Power System Transient Stability Assessment”, Control Applications, Proceedings of the 4th IEEE Conference, pp. 825-832, 1995.
[22] Hunt, K. J., "Classification by Induction: Application to Modelling and Control of Non-linear Dynamical Systems", Intelligent Systems Engineering, Vol. 24, pp.231-245, 1993.
[23] Witten, I. H., Frank, E., Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann Publishers, San Francisco, California, 1999.
[24] Holland, J. H., “Genetic Algorithms”, Scientific American, pp.66-72, July 1992.
[25] Kamber, M., Winstone, L., Gong, W., Cheng, S., Han, J., “Generalization and Decision Tree Induction: Efficient Classification in Data Mining”, Research Issues in Data Engineering, Proceedings Seventh International Workshop, pp.111-120, 1997.
[26] Kim, H., Koehler, G.J., "Theory and Practice of Decision Tree Induction", Omega, Vol. 23, Issue.6, pp.587-700, Dec. 1995.
[27] Kim, K. M., Lee, B. J., Lyou K., Park, G. T., “Design of a Binary Decision Tree Using the Genetic Algorithm and K-means Algorithm for Recognition of the Defect Patterns of Cold Mill Strip”, Fuzzy Systems Conference Proceedings, IEEE International, Vol. 2, pp.1081-1085, 1999.
[28] Kostic, T., Germond, A. J., Alba, J. J., “Optimization and Learning of Load Restoration Strategies”, Electrical Power & Energy Systems, Vol. 20, No. 2, pp.131-140, 1998.
[29] Loh, W.Y., Shih, Y.S., “Split Selection Methods for Classification Trees”, Statistica Sinica, Vol. 7, pp. 815-840, 1997.
[30] McSherry, D., “Strategic Induction of Decision Trees”, Knowledge-Based Systems, Vol. 12, pp.269-275, 1999.
[31] Michael, J.A., Gordon, L., Data Mining Techniques: for Marketing, Sales, and Customer Support, Wiley Computer Pub., New York, 1997.
[32] Michie, D., Spiegelhalter, D. J., Taylor, C. C. (Eds.), Machine Learning, Neural and Statistical Classification, Ellis Horwood, London, 1994.
[33] Nakashima, T., Ishibuchi, H., Murata, T., “Evolutionary Algorithms for Constructing Linguistic Rule-based Systems for High-dimensional Pattern Classification Problems”, Evolutionary Computation Proceedings, IEEE World Congress on Computational Intelligence, pp.752-757, 1998.
[34] Ngan, P. S., Wong, M. L., Lam, W., Leung, K. S., Cheng, C.Y., “Medical Data Mining Using Evolutionary Compution”, Artifical Intelligence in Medicine, Vol. 16, pp.73-96, 1999.
[35] Nikolopoulos, C., Duvendack, S., “A Hybrid Machine Learning System and its Application to Insurance Underwriting”, Evolutionary Computation, IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference, Vol.2, pp.692-695, 1994.
[36] Ohno, H., Furuhashi, T., “A Conceptual Framework Consisting of Sensor-motor, Internal Representation, and Evaluation Function Spaces for Construction of Autonomous Systems”, Fuzzy Systems Conference Proceedings, FUZZ-IEEE International, Vol. 2, pp.992-997, 1999.
[37] Pal, S. K., Bandyopadhyay, S., Murthy, C. A., “Genetic Algorithms for Generation of Class Boundaries”, Systems, Man and Cybernetics, Part B, IEEE Transactions, Vol. 28, No.6, pp.816-828, Dec. 1998.
[38] Paul Harmon, “Genetic Algorithms and Evolutionary Programming”, Intelligent Software Strategies, Vol. 5, No.6, June 1994
[39] Peter, C., Discovering Data Mining: from Concept to Implementation, Upper Saddle River, NJ : Prentice Hall , 1997.
[40] Peter, D. T., “Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm”, Journal of Artificial Intelligence Research 2, pp. 369-409, 1995.
[41] Petrowski, A., Genet, M. G., “A Classification Tree for Speciation”, Evolutionary Computation, Vol. 1, pp.204-211, 1999.
[42] Pieter, A., Dolf, Z., Data Mining, Harlow: Addison-Wesley, 1996.
[43] Quinlan, J. R., “Discovering Rules by Induction from Large Collections of Examples”, in Expert Systems in the micro-electronic age, D. Michie (ed.), Edinburgh: Edinburgh University Press, pp.168-201, 1979.
[44] Quinlan, J. R., C4.5: Programs for Machine Learning, Morgan Kaufmann, San Mateo, CA, 1992.
[45] Quinlan, J.R., "Induction of Decision Trees", Machine Learning, Vol.1, No.1, pp.81-106, March 1986.
[46] Selby, R.W., Porter, A.A, “Learning from Examples: Generation and Evaluation of Decision Trees for Software Resource Analysis”, IEEE Transactions on Software Engineering, Vol.14, No. 12, pp.1743 —1757, Dec. 1988.
[47] Shih, Y.S., “Families of Splitting Criteria for Classification Trees”, Statistics and Computing, Vol. 9, pp. 309-315, 1999.
[48] Spangler, W.E., May, J.H., Vargas, L.G., "Choosing Data-Mining Methods for Multiple Classification: Representational and Performance Measurement Implications for Decision Support", Journal of Management Information Systems, Vol. 16, No. 1, pp.37-62, Summer 1999.
[49] Terano, T., Ishino, Y., “Marketing Data Analysis Using Inductive Learning and Genetic Algorithms with Interactive- and Automated-phases”, Evolutionary Computation, IEEE International Conference, Vol. 2, pp.771-776, 1995.
[50] Thomson, P., Miller, J.F., “Symbolic Method for Simplifying AND-EXOR Representations of Boolean Functions Using a Binary-decision Technique and a Genetic Algorithm”, Computers and Digital Techniques, IEE Proceedings, Vol.143, No.2, pp.151-155, March 1996.
[51] Weiss, S. M., Indurkya, N., Predictive Data Mining: A Practical Guide, Morgran Kaufman Publishers, 1997.
[52] Zhang, Z., Zhou Y., Lu Y., Zhang B., “Extracting Rules from a GA-pruned Neural Network”, Systems, Man and Cybernetics, IEEE International Conference, Vol. 3, pp.1682-1685, 1996.