臺灣博碩士論文加值系統

在案例推理(CBR)研究中，主要應透過案例推理機制找出最符合現行問題需求之結果。在本研究使用機器學習的技術包括基因規劃法(GP)及基因演算法(GA)來產生CBR tree以提升單一CBR案例推理系統之學習能力。基因規劃法用於建立案例切割規則來區隔各子案例庫；基因演算法用以求出各子案例庫下特徵屬性比對相似值的對應權重。本研究乃利用UCI及DELVE資料庫中，包含分類及推估問題共六組實驗資料進行模式建構，同時也應用GA-CBR 、C5.0及CART三種技術進行實驗並比較其學習成效。實驗結果顯示CBR tree效果明顯比其它三種技術優越。

A critical issue must be correctly recognized in case-based reasoning (CBR) that is to retrieve not just a similar historical case but a usefully similar case from case base to the target problem. For this reason, this paper examines application of machine learning techniques, genetic programming (GP) and genetic algorithm (GA) to the integration of domain knowledge into the CBR. We call the integrated system GP-Based CBR tree system in this paper. First, we apply classification problems based on GP for case base and split up into several subcase bases in accordance with some important features from case base. Second, GA would be used to determine weight sets for features similarity degree of several subcase bases, and we call this part GA-CBR. The CBR tree reaps the benefits of three systems. The hybrid approach combined GP and GA both techniques with CBR systems for increasing the overall accuracy. We experimentally assess six datasets and accuracy of generated was comparable to four approaches that were CBR tree, GA-CBR, C5.0 and CART over six datasets.

Contents
1. Introduction 1
2. Literature Review 3
2.1 Classification 3
2.2 Decision Trees 4
2.3 Genetic Programming 4
2.4 Genetic Algorithms 8
2.5 Case-Based Reasoning 10
2.6 K Nearest Neighbor Algorithm 12
3. Methodology 14
3.1 The CBR Implementation 14
3.2 The GA-CBR System Implementation 18
3.3 The GP-Based CBR tree System Implementation 20
4. Experiments 24
4.1 The Datasets 24
4.2 The Parameters for GP-Based CBR tree System 25
5. The Result 27
6. Discussion 31
7. Conclusions 32
8. Future Work 32
9. References 32
10. Appendix 39
10.1 Appendix of Six Datasets 39
10.2 Appendix of Experiment 44

[1] Alan R.A., "Data Mining Introductory and Advanced Topics," Prentice Hall Publish, NJ, ISBN: 0-130-88892-3, 2002.
[2] Alexandrini, F., Krechel, D., Maximini, K. and Von Wangenheim, A., "Integrating CBR into the Health Care Organization," 16th IEEE Symposium on Computer-Based Medical Systems, pp.130-135, 2003.
[3] Aly, W.M., Sheta, A.F. and Abdelaziz, A.R., "Development of Evolutionary Models for Long-Term Load of Power Plant Systems," ACS/IEEE International Conference on Computer Systems and Applications, pp.117, 2003.
[4] Apte, G. and Weiss, S., "Data Mining with Decision Trees and Decision Rules," Future Generation Computer Systems , Vol. 13, pp.197-210, 1997.
[5] Brameier, M. and Banzhaf, W., "A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining,"IEEE Transactions on Evolutionary Computation, Vol. 5, Issue:1, pp.17-26, 2001.
[6] Breiman, L., Friedman, J., Olshen, R. and Stone, C., "Classification and Regression Trees," CRC Press, ISBN: 0-41204-841-8, 1984.
[7] Breslow, L. and D. W. Aha, "Simplifying Decision Trees: A Survey," Knowledge Engineering Review, Vol. 12, pp.1-40, 1997.
[8] Brill, F.Z., Brown, D.E. and Martin, W.N., "Fast Genetic Selection of Features for Neural Network Classifiers," IEEE Transactions on Neural Networks, Vol.3, pp.324-328, 1992.
[9] Brown, C.E. and Gupta, U.G., "Applying Case-Based Reasoning to the Accounting Domain," Intelligent Systems in Accounting Finance and Management, Vol.3, pp.205-221, 1994.
[10] Chen, S.M. and Huang, C.M., "Generating Weighted Fuzzy Rules from Relational Database Systems for Estimating Values using Genetic Algorithms, " IEEE Transactions on Fuzzy Systems, Vol.11, Issue:4, pp.495-506, 2003.
[11] Chi-I Hsu, C. Chiu, and Nan-Hsing Chiu, "Applying Genetic Algorithms to Nested Case-Based Reasoning for The Optimum Information Systems Outsourcing Decision," 4th Asia-Pacific Conference on Simulated Evolution And Learning, pp.816-820, 2002.
[12] Chiu, C. and Chiu, Nan-Hsing, "The Prediction of Airplane Landing Gravity Using Case-Based Reasoning," International Journal of Industrial Engineering, Vol.10, pp.82-89, 2003.
[13] Chiu, C., "A Case-Based Customer Classification Approach for Direct Marketing," Expert Systems with Applications, Vol.22, pp.163-168, 2002.
[14] Chiu, C., Chang, Pei-Chann, and Chiu Nan-Hsing, "A Case-Based Expert Support System for Due-Date Assignment in a Wafer Fabrication Factory," Journal of Intelligent Manufacturing, Vol.14, pp.287-296, 2003.
[15] Chiu, C., Chen, W., and Huang, A., "The Genetic Algorithm Design of Feature Weighting in Case-Based Systems: An Example of Insurance Direct Marketing," Quantitative Management Techniques and Applications, Taiwan, 1998.
[16] Cho, S.B. and Shimohara, K., "Modular Neural Networks Evolved by Genetic Programming," Proceedings of IEEE International Conference on Evolutionary Computation, pp.681-684, 1996.
[17] Davis, L., "Handbook of Genetic Algorithms," Van Nostrand Reinhold Press, NY, ISBN 0-442-00173-8, 1991.
[18] Finnie, G. R., Wittig, G.E. and Desharnais, J.M., "A Comparison of Software Effort Estimation Techniques using Function Points with Neural Networks, Case Based Reasoning and Regression models," Journal of Systems and Software, Vol.39, pp.281-289, 1997.
[19] Fouque, G. and Matwin, S., "CAESAR: a System for Case Based Software Reuse," Proceedings of the Seventh Knowledge-Based Software Engineering Conference, pp. 90-99, 1992.
[20] Gilboa, I. and Schmeidler, D., "Case-Based Knowledge and Induction," IEEE Transactions on Systems, Man and Cybernetics, Vol.30, Issue: 2, pp85-95, 2000.
[21] Goldberg, D. E., "Genetic Algorithms in Search, Optimization and Machine Learning," Addison-Wesley Publish, MA, ISBN: 0-201-15767-5, 1989.
[22] Gray, N. B., "Capturing Knowledge through Top-Down Induction of Decision Trees," IEEE Expert: IEEE Intelligent Systems, Vol. 53, pp. 41-50, June 1990.
[23] Haruyama, S. and Qiangfu Zhao, "Designing Smaller Decision Trees using Multiple Objective Optimization Based GPs Systems," 2002 IEEE International Conference on Man and Cybernetics, Vol.6, pp.5, 2002.
[24] Helm, T.M., Painter, S.W. and Oakes, W.R., "A Comparison of Three Optimization Methods for Scheduling Maintenance of High Cost, Long-Lived Capital Assets," Proceedings of the Winter Simulation Conference, Vol.2 , pp.1880-1884, 2002.
[25] Ho, S.Y., Chen, H.M., Ho, S.J. and Chen, T.K., "Design of Accurate Classifiers with a Compact Fuzzy-Rule Base Using an Evolutionary Scatter Partition of Feature Space," Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics: Accepted for future publication, Vol.1, Issue: 99, pp.1, 2004.
[26] Holland, J. H., “Genetic Algorithms,” Scientific American, pp. 66-72, 1992.
[27] Holland, J.H., "Adaptation in Natural and Artificial Systems," University of Michigan, Cambridge, MIT Press, MA, ISBN: 0-262-58111-6, 1975.
[28] Howard, L.M. and Angelo, D.J., "The GA-P: A Genetic Algorithm and Genetic Programming Hybrid," IEEE Expert: IEEE Intelligent Systems, Vol.10, Issue: 3, pp.11-15, 1995.
[29] Hsu, C., Chiu, C. and Hsu, P. "Predicting Information Systems Outsourcing Success Using A Hierarchical Design of Case-Based Reasoning," Expert Systems with Applications, Vol.26, pp.435-441, 2004.
[30] Iles, M. and Deugo, D., "A Search for Routing Strategies in a Peer-To-Peer Network using Genetic Programming," Proceedings of 21st IEEE Symposium on Reliable Distributed Systems , pp.341-346, 2002.
[31] Jarmulak, J., Craw, S. and Rowe, R., "Self-Optimising CBR Retrieval," Proceedings of 12th IEEE International Conference on Tools with Artificial Intelligence, pp.376-383, 2000.
[32] Jeng, B. C., and Liang, T. P., "Fuzzy Indexing and Retrieval in Case-Based Systems," Expert Systems with Applications, pp.135-142, 1995.
[33] Kelly, J.D. and Davis, L., "A Hybrid Genetic Algorithm for Classification," International Joint Conference on Artificial Intelligence, pp.645-650, 1991.
[34] Khoshgoftaar, T.M., Nguyen, L., Gao, K. and Rajeevalochanam, J., "Application of an Attribute Selection Method to CBR-Based Software Quality Classification," Proceedings. 15th IEEE International Conference on Tools with Artificial Intelligence, pp.47-52, 2003.
[35] Kim S.H. and Shin S.W., "Identifying the Impact of Decision Variables for Nonlinear Classification Tasks," Expert Systems with Application
[36] Kim, B. and Kwangsuk Park, "A Study on the Modeling of Nonlinear System using Genetic Programming," Proceedings of the 18th Annual International Conference of the IEEE on Engineering in Medicine and Biology Society, Bridging Disciplines for Biomedicine, Vol.18, pp.201-214, 2000.
[37] Kim, H. and Koehler, G. J., "Theory and Practice of Decision Tree Induction," International Journal Management Science on Omega, Vol. 23, Issue.6, pp. 587-700, Dec. 1995.
[38] Kinnear, K.E. and Jr., "Fitness Landscapes and Difficulty in Genetic Programming," Proceedings of the 1994 IEEE World Conference on Computational Intelligence, Vol.1, pp.142-147, 1994.
[39] Kishore, J.K., Patnaik, L.M., Mani, V. and Agrawal, V.K., "Application of Genetic Programming for Multicategory Pattern Classification," IEEE Transactions on Evolutionary Computation, Vol.4, Issue: 3, pp.242-258, 2000.
[40] Kohavi, R., Langley, P. and Yun, Y., "Heuristic Search for Feature Weights in Instance-Based Learning," Manuscript Submitted for Publication, 1995.
[41] Kolodner, J., "Case-Based Reasoning," Morgan Kaufmann Publish, CA, ISBN: 1-55860-237-2, 1993.
[42] Kolodner, J., "Improving Human Decision Making through Case-Based Decision Aiding," Magazine on AI, Vol.12, Iissue: 2, pp.52-68, 1991.
[43] Kolonder, J. L., Simpson, R., and Sycara-Cyransky, K., "A Process Model of Case-based Reasoning in Problem Solving," Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pp. 284-290, 1985.
[44] Koza, J.R. and Rice, J.P., "Genetic Generation of Both the Weights and Architecture for a Neural Network," International Joint Conference on Neural Networks, Vol.2, pp.397-404, 1991.
[45] Koza, J.R., "Genetic Programming II," MIT Press, MA, ISBN 0-26211-189-6, 1994.
[46] Koza, J.R., "Genetic Programming: On the Programming of Computers by Means of Natural Selection," MIT Press, MA, ISBN 0-262-11170-5, 1992.
[47] Koza, J.R., "Hierarchical Automatic Function Definition in Genetic Programming, in Foundations of Genetic Algorithms," San Mateo Press, CA, pp. 297-318, 1993.
[48] Koza, J.R., "Survey of Genetic Algorithms and Genetic Programming," IEEE on Neural-Fuzzy Technologies and Its Applications, , pp. 589-594, 1995.
[49] Shin.,K.S., "Case-based Reasoning Supported by Genetic Algorithms for Corporate Bond Rating", Expert Systems with Applications, Vol.16, pp.85-95, 1999.
[50] Langley, P. and Iba, W., "Average-Case Analysis of a Nearest Neighbor Algorithm". Proceedings of the Thirteenth IJCAI, France, Morgan Kaufmann, pp.889-894, 1993.
[51] Leake, D.B., "Case-Based Reasoning: Experiences, Lessons & future Directions," AAAI Press, Menlo Park, CA, ISBN: 0-262-62110-x, 1996.
[52] Li, K. and Liu, Y.S., "Fuzzy case-based reasoning: weather prediction," Proceedings. 2002 International Conference on Machine Learning and Cybernetics, Vol. 1, pp.107-110, 2002.
[53] Lin, Y. and Bhanu, B.,"Discovering operators and features for object detection, Pattern Recognition," Proceedings of 16th International Conference, Vol.3, pp.339-342, 2002.
[54] Liu, N., Abdelrahman, M.A. and Ramaswamy, S., "A Genetic Algorithm for the Single Machine Total Weighted Tardiness Problem," Proceedings of the 35th Southeastern Symposium on System Theory, pp.34-38, 2003.
[55] Loveard, T. and Ciesielski, V., "Representing Classification Problems in Genetic Programming," Proceedings of the 2001 Congress on Evolutionary Computation, Vol.2, pp.1070-1077, 2001.
[56] Lan R.A., "Data Mining Introductory and Advanced Topics," Prentice Hall Publish, NJ, ISBN: 0-130-88892-3, 2002.
[57] Mendes, E., Watson, I., Triggs, C., Mosley, N. and Counsell, S., "A comparison of development effort estimation techniques for Web hypermedia applications," Proceedings. Eighth IEEE Symposium on Software Metrics, pp.131-140, 2002.
[58] Michael, B. A. and Gordon, L., "Data Mining Techniques: for Marketing, Sales, and Customer Support," Wiley Computer Publish, NY, ISBN: 0-471-17980-9, 1997.
[59] Michie, D., Spiegelhalter, D. J. and Taylor, C. C., "Machine Learning, Neural and Statistical Classification," Ellis Horwood Publish, NJ, ISBN: 0-13106-360-x, 1994.
[60] Ngan, P.S., "Medical Data Mining using Evolutionary Computation," Artificial Intelligence in Medicine, Vol.16, Issue: 1, pp.73-96, 1999.
[61] Prasad, M.V.N., Lander, S.E. and Lesser, V.R., "On Retrieval and Reasoning in Distributed Case Bases," Intelligent Systems for the 21st Century IEEE International Conference on Systems, Man and Cybernetics, Vol.1, pp.351-356, 1995.
[62] Petrowski, A. and Genet, M. G., "A Classification Tree for Speciation," Congress on Evolutionary Computation, Vol. 1, pp.204-211, 1999.
[63] Pijun Xia and Ming Rao. "A Hybrid Intelligent System for Process Operations Support," 1997 IEEE International Conference on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation, Vol.3, pp.2097-2102, 1997.
[64] Richardson, M.M. and Warren, J.R., "Induced Decision Trees for Case-Based Reasoning," Australian and New Zealand Conference on Intelligent Information Systems, pp.52-55, 1996.
[65] Riesbeck, C.K., and Schank, R.C., "Inside Case-Based Reasoning," Hillsdale Publish, NJ, ISBN: 0-89859-767-6, 1989.
[66] Schuster, M.G., "A Multi objective Genetic Programming Approach for Pricing and Hedging Derivative Securities," Proceedings of IEEE International Conference on Computational Intelligence for Financial Engineering, pp.77-84, 2003.
[67] Sheta, A.F. and Mahmoud, A., "Forecasting Using Genetic Programming," Proceedings of the 33rd Southeastern Symposium on System Theory, , pp.343-347, 2001.
[68] Siedlecki, W. and Sklansky, J., "A Note on Genetic Algorithms for Large-Scale Feature Selection," Pattern Recognition Letters, Vol.10, pp.335-347, 1989.
[69] Steven, A. V., "Genetic Classification Trees," Evolutionary Algorithms in Management Applications, Springer, pp.227-389, 1995.
[70] Terrio, M.D. and Heywood, M.I., "Directing Crossover for Reduction of Bloat in GP," IEEE Canadian Conference on Electrical and Computer Engineering, Vol.2, pp.1111-1115, 2002.
[71] Tsakonas, A. and Dounias, G., "Hierarchical Classification Trees using Type-Constrained Genetic Programming,", Proceedings of First International IEEE Symposium on Intelligent Systems, Vol.2, pp.50-54, 2002.
[72] Tsang, E.C.C., Shiu, S.C.K., Wang, X.Z.and Ho, K., "Case-Base Reduction using Learned Local Feature Weights," Joint 9th IFSA World Congress and 20th NAFIPS International Conference, , Vol.5, pp.2965-2970, 2001.
[73] Watson I., "Applying Case-Based Reasoning: Techniques for Enterprise Systems," AI-CBR, University of Salford, UK, ISBN: 1-55860-462-6, 1997.
[74] Wettschereck, D., Aha, D.W. and Mohri, T., "A Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms," Artificial Intelligence Review, Vol.11, pp.273-314, 1997.
[75] Wilson, D.R. and Martinez, T.R., "Instance-Based Learning with Genetically Derived Attribute Weights," Proceedings of the International Conference on Artificial Intelligence, Expert Systems, and Neural Networks, pp.11-14, 1996.
[76] Wong, F., and Tan, C., "Hybrid Neural, Genetic and Fuzzy Systems," NY: Wiley Press, 1994.
[77] Yi L. and Khoshgoftaar, T.M., "Genetic Programming Model for Software Quality Classification," Sixth IEEE International Symposium on High Assurance Systems Engineering, pp.127-136, 2001.
[78] Yin, W. J., Liu M. and Wu C., "A genetic Learning Approach with Case-Based Memory for Job-Shop Scheduling Problems," Proceedings of International Conference on Machine Learning and Cybernetics, Vol.3, pp.1683-1687, 2002.
[79] Zhaohao Sun, Finnie, G. and Weber, K., "Integration of Abductive CBR and Deductive CBR," 10th IEEE International Conference on Fuzzy Systems, Vol.3, pp.1432-1435, 2001.
[80] Watson, I., “Case-based Reasoning is a Methodology not a Technology,” Knowledge-based Systems, Vol: 12, Issue: 5-6, pp. 303-308, 1999.
[81] Weiss, S. M. and Indurkya, N., "Predictive Data Mining: A Practical Guide," Morgran Kaufman Publishers, San Francisco, ISBN: 1-55860-403-0, 1997.