這篇論文研究如何解決資料探勘中法則萃取的問題，其中包括了數值關聯法則探勘 (numeric association rule mining)以及分類法則探勘 (classification rule mnining)。這兩類的問題存在著多個目標需要同時被最佳化，而這些目標時常互相抵觸。我們提出了兩個多目標演化式演算法來分別解決這兩種問題。我們採納了MOEA/D中透過布置均勻的權重向量來達成配對選擇 (mating selection)和物競天擇 (environmental selection)的概念來維持探索及開發間的平衡。為了保留那些具有相同適應度 (fitness)但卻不相同的解，MOEA/D中對於子問題的解從限制一個解被修改成可以是一個解集合。我們遵循一般關聯法則探勘的架構，透過尋找頻繁項目集 (frequent itemset)來進行數值關聯法則探勘。而對於分類法則探勘，我們提出了一個結合密西根 (Michigan)和匹茲堡 (Pittsburgh)兩種方法的兩階段演化式演算法。透過第一階段先找出所有柏拉圖最佳 (Pareto-optimal)法則，在第二階段則利用這些法則組合成柏拉圖最佳法則集合。當法則互相起衝突時，每個法則集合會根據各自的喜好選擇對應方針。我們提出的數值關聯法則探勘演算法透過實驗在人造的資料集中可顯示出他的正確性和有效性。我們也把這個方法用在一些公開的實際生活上產生的資料集上，可當成外來比較的依據。對於分類法則探勘，我們在一些公開的資料集上和一些現存基於法則 (rule-based)或是非基於法則 (non-rule based)的分類器進行比較，實驗結果顯示我們的方法是有效的。

In this thesis, the problem of rule extraction in data mining including numeric association rule mining and classification rule mining is addressed. Both tasks involve many objectives to be optimized simultaneously, where the objectives frequently contradict with each other. Two Pareto-based multiobjective evolutionary algorithms are proposed to solve these problems. By incorporating the concept of MOEA/D, the mating restriction and environmental selection enhance the exploitation and exportation ability through setting the uniform weight vectors. And the solution of subproblem defined in MOEA/D is modified to a set of solutions to obtain solutions with same fitness. For numerical association rule mining, the proposed algorithm follows the common framework to obtain frequent itemsets. For classification, a two-phase multiobjective evolutionary algorithm is proposed which combines both Michigan and Pittsburgh approach to find Pareto-optimal rules first and then to form the Pareto-optimal rule set. The policy for each rule set is different according to its preference when conflict between rules occurred. Through experiments upon synthetic datasets, the proposed algorithm for numeric association rule mining shows its correctness and efficiency. The proposed algorithm is also applied upon several public real life datasets for future comparison. And for classification, the experimental results show it’s competitive against existing rule-based and non-rule based classifiers upon several public datasets.

口試委員會審定書 #
誌謝 i
中文摘要 ii
ABSTRACT iii
CONTENTS iv
LIST OF FIGURES vii
LIST OF TABLES viii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Literature Review 4
1.2.1 Rule-based Data Mining 4
1.2.2 Multiobjective Evolutionary Algorithm 6
1.2.3 Evolutionary Algorithm for Rule-based Data Mining 8
1.2.4 Multiobjective Evolutionary Algorithm for Rule-based Data Mining 12
1.3 Contribution 13
1.4 Organization 14
Chapter 2 Preliminaries 16
2.1 Multiobjective Optimization 16
2.1.1 Multiobjective Optimization Problems (MOPs) 16
2.1.2 Existing Approaches to MOPs 17
2.2 Multiobjective Evolutionary Algorithm 20
2.2.1 Overview of Evolutionary Algorithm 20
2.2.2 Multiobjective Evolutionary Algorithm 24
2.3 Differential Evolution Algorithm 27
Chapter 3 Multiobjective Evolutionary Algorithm (MOEA) for Numeric Association Rule Mining (NARM) 30
3.1 Overview 30
3.2 Chromosome Encoding and Decoding 33
3.3 Genetic Algorithm Components 35
3.4 Summary 42
Chapter 4 Two-Phase Multiobjective Evolutionary Algorithm (MOEA) for Classification Rule Mining (CRM) 43
4.1 Overview 43
4.2 First Phase: Rule Evolver 48
4.2.1 Chromosome Encoding and Decoding 49
4.2.2 Genetic Algorithm Components 51
4.2.3 Rule Pruning Stage 54
4.2.4 Termination of Phase 1 54
4.3 Second Phase: Rule Set Evolver 55
4.3.1 Chromosome Encoding and Decoding 56
4.3.2 Genetic Algorithm Components 58
4.3.3 Rule Set Pruning Stage 59
4.3.4 Default Class Deciding Stage 60
4.3.5 Termination of Phase 2 60
4.4 Summary 60
Chapter 5 Experiments and Results 62
5.1 Problem datasets 62
5.1.1 Datasets for numeric association rule mining 62
5.1.2 Datasets for classification rule mining 63
5.2 Benchmark Algorithms 65
5.3 Parameter Setting 65
5.4 Performance of Proposed MOEA for NARM 68
5.4.1 Synthetic dataset 68
5.4.2 Real life dataset 69
5.5 Performance of Proposed Two-Phase MOEA for CRM 70
5.6 Discussions 72
Chapter 6 Conclusions and Future Work 75
REFERENCE 78

[1]U. M. Fayyad, G. Piatetsky-Shapiro, and P. Smyth, “From data mining to knowledge discovery: An overview,” Advances in Knowledge Discovery and Data Mining, American Association for Artificial Intelligence, pp. 1-34, 1996.
[2]D. Pyle , Data Preparation for Data Mining, Morgan Kaufmann, 1999.
[3]R. Agrawal, T. Imielinski, and A. Swami, “Mining association rules between sets of items in large databases,” in Proceedings of ACM SIGMOD International Conference on Management of Data, Washington, D.C., USA, 1993, pp. 207-216.
[4]K. Ke, J. Cheng, and W. Ng, “MIC framework: An information-theoretic approach to quantitative association rule mining,” in Proceedings of the 22th International Conference on Data Engineering, Atlanta, GA, USA, 2006, pp. 112–114.
[5]D. Michie, D. J. Spiegelhalter and C. C. Taylor, Machine Learning, Neural and Statistical Classification. Ellis Horwood Series in Artificial Intelligence, 1994.
[6]V. Dhar, D. Chou, and F. Provost, “Discovering interesting patterns for investment ,decision making with GLOWER – a Genetic Learner Overlaid with Entropy Reduction,” Data Mining and Knowledge Discovery, vol. 4, no. 4, pp. 251-280, 2000.
[7]A. A. Freitas and S. H. Lavington, Mining Very Large Databases with Parallel Processing. Kluwer Academic Publishers, 1997.
[8]R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” in Proceedings of the 20th Very Large Data Bases Conference, Santiago de Chile, Chile, 1994, pp.487-499.
[9]J. Han and J. Pei, “Mining frequent patterns by pattern-growth: Methodology and implications,” ACM SIGKDD Explorations Newsletter 2, vol. 2, pp. 14-20, 2000.
[10]D. Lin and Z. M. Kedem, “Pincer-search: A new algorithm for discovering the maximum frequent set,” in Proceedings of the 6th International Conference on Extending Database Technology, Valencia, Spain, 1998, pp. 105-119.
[11]S. Orlando, P. Palmerini, and R. Perego, “Enhancing the Apriori algorithm for frequent set counting,” in Proceedings of the 3rd International Conference on Data Warehousing and Knowledge Discovery, Munich, Germany, 2001, pp. 71-82.
[12]R. Srikant and R. Agrawal, “Mining quantitative association rules in large relational tables,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Montreal, Canada, 1996, pp. 1–12.
[13]R. J. Miller and Y. Yang, “Association rules over interval data,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Tucson, Arizona , USA, 1997, pp. 452–461.
[14]T. Fukuda, M. Yasuhiko, M. Sinichi, and T. Tokuyama, “Mining optimized association rules for numeric attributes,” in Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Montreal, Canada, 1996, pp. 182–191.
[15]J. R. Quinlan, C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
[16]W. W. Cohen, “Fast effective rule induction,” in Proceedings of the 12th International Conference on Machine Learning, Tahoe City, California, USA, 1995, pp. 115-123.
[17]E. Frank and I. H. Witten, “Generating accurate rule sets without global optimization,” in Proceedings of the 15th International Conference on Machine Learning, Madison, Wisconsin, USA, 1998, pp. 144–151.
[18]R. Kohavi, “The power of decision tables,” in Proceedings of the 8th European Conference on Machine Learning, Heraclion, Crete, Greece, 1995, pp. 174–189.
[19]L. I. Kuncheva, Fuzzy Classifier Design. Physica-Verlag, 2000.
[20]W. Zhang, “Mining fuzzy quantitative association rules,” in Proceedings of International Conference on Tools with Artificial Intelligence, Chicago, Illinois, USA , 1999, pp 99–102.
[21]M. Delgado, N. Marin, D. Sanchez, and MA.Vila, “Fuzzy association rules: General model and applications,” IEEE Transactions on Fuzzy Systems, vol. 11, no. 2, pp. 214–225, 2003.
[22]W. Pedrycz and V. de Oliveira, “Optimization of fuzzy models,” IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, vol. 26, no. 4, pp. 627-637, 1996.
[23]Y. Jin, “Fuzzy modeling of high-dimensional systems: Complexity reduction and interpretability improvement,” IEEE Transactions on Fuzzy Systems, vol. 8, no. 2, pp. 212-221, 2000.
[24]D. F. Jones, S. K. Mirrazavi, and M. Tamiz, “Multi-objective meta-heuristics: An overview of the current state-of-the-art,” European Journal of Operational Research, vol. 137, no. 1, pp. 1–9, 2002.
[25]J. D. Schaffer, “Multiple objective optimization with vector evaluated genetic algorithms,” in Proceedings of the International Conference on Genetic Algorithms, Pittsburgh, PA, USA, 1985, pp. 93–100.
[26]C. M. Fonseca and P. J. Fleming, “Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization,” in Proceedings of the International Conference on Genetic Algorithms, Urbana-Champaign, IL, USA, 1993, pp. 416–423.
[27]J. Horn, N. Nafpliotis, and D. E. Goldberg, “A niched Pareto genetic algorithm for multiobjective optimization,” in Proceedings of the IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Orlando, FL, USA, 1994, pp. 82–87.
[28]J. D. Knowles and D.W. Corne, “Approximating the nondominated front using the Pareto archived evolution strategy,” Evolutionary Computation, vol. 8, pp. 149–172, 2000.
[29]D.W. Corne, N. R. Jerram, J. D. Knowles, and M. J. Oates, “PESA-II: Regionbased selection in evolutionary multiobjective optimization,” in Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, CA,USA, 2001, pp. 283–290.
[30]E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, Tech. Rep. 103, 2001.
[31]K. C. Tan, T. H. Lee, and E. F. Khor, “Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 565–588, 2001.
[32]K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
[33]A. Toffolo and E. Benini, “Genetic diversity as an objective in multi-objective evolutionary algorithms,” Evolutionary Computation, vol. 11, no. 2, pp. 151–167, 2003.
[34]Q. Zhang and H. Li, “MOEA/D: A multi-objective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712–731, Dec. 2007.
[35]K. C. Tan, C. K. Goh, A. A. Mamun, and E. Z. Ei, “An evolutionary artificial immune system for multi-objective optimization,” European Journal of Operational Research, vol. 187, no. 2, pp. 371-392, 2008.
[36]P. G. Espejo, S. Ventura, and F. Herrera, “A Survey on the Application of Genetic Programming to Classification,” IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews, vol. 40, no. 2, 2010.
[37]A. Ghosh and B. Nath, “Multi-objective rule mining using genetic algorithms,” Information Sciences, vol. 163, no. 1–3, pp. 123–133, 2004.
[38]J. Mata, J. L. Alvarez, and J. C. Riquelme, “Discovering numeric association rules via evolutionary algorithm,” in Proceedings of the 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Taipei, Taiwan, 2002, pp. 40–51.
[39]M. Kaya, “Multi-objective genetic algorithm based approaches for mining optimized fuzzy association rules,” Soft Computing, vol. 10, pp. 578–586, 2006.
[40]B. Alatas, E. Akin, and A. Karci, “MODENAR: Multi-objective differential evolution algorithm for mining numeric association rules,” Applied Soft Computing, vol. 8, pp. 646–656, 2008.
[41]A. Salleb-Aouissi, C. Vrain, and C. Nortet, “QuantMiner: A genetic algorithm for mining quantitative association rules,” in Proceedings of the 20th International Conference on Artificial Intelligence, Hyderabad, India, 2007, pp. 1035-1040.
[42]E. Noda, A. A. Freitas, and H. S. Lopes, “Discovering interesting prediction rules with a genetic algorithm,” in Proceedings of the Conference on Evolutionary Computation, Orlando, Florida, USA, 1999, pp. 1322-1329.
[43]S. W. Wilson, “Classifier fitness based on accuracy,” Evolutionary Computation, vol. 3, no. 2, pp. 149–175, 1995.
[44]S. W. Wilson, “ZCS: A zeroth level classifier system,” Evolutionary Computation, vol. 2, no. 1, pp. 1–18, 1994.
[45]T. D. Do, S. C. Hui, A. C. M. Fong, and B. Fong, “Associative classification with artificial immune system,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 2, 2009.
[46]K. A. D. Jong, W. M. Spears, and D. F. Gordon, “Using genetic algorithms for concept learning,” Machine Learning, vol. 13, pp. 161-188, 1993.
[47]J. Bacardit, “Pittsburgh genetics-based machine learning in the data mining era: Representations, generalization, and run-time,” Ph.D. thesis, Ramon Llull University, Barcelona, Catalonia, Spain, 2004.
[48]J. Bacardit and N. Krasnogor, “Performance and efficiency of memetic Pittsburgh learning classifier systems,” Evolutionary Computation, vol. 17, no. 3, pp. 307-342, 2009.
[49]J. Bacardit and M. Butz, “Data mining in learning classifier systems: Comparing XCS with GAssist, ” in 7th International Workshop on Learning Classifier Systems, Seattle, USA , 2004.
[50]G. Venturini, “SIA: A supervised inductive algorithm with genetic search for learning attributes based concepts, ” in Proceedings of the European Conference on Machine Learning, Vienna, Austria, 1993, pp. 280–296.
[51]J. S. Aguilar-Ruiz, J. C. Riquelme, and M. Toro, “Evolutionary learning of hierarchical decision rules,” IEEE Transactions on Systems, Man, and Cybernetics,Part B: Cybernetics, vol. 33, no. 2, pp. 324–331, 2003.
[52]R. J. Bayardo and R. Agrawal, “Mining the most interesting rules,” in Proceedings of 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, 1999, pp. 145–153.
[53]B. de la Iglesia, G. Richards, M. S. Philpott, and V. J. Rayward-Smith, “The application and effectiveness of a multi-objective metaheuristic algorithm for partial classification,” European Journal of Operational Research, vol. 169, issue 3, pp. 898-917, 2006.
[54]H. Ishibuchi and S. Namba, “Evolutionary multiobjective knowledge extraction for high-dimensional pattern classification problems,” Lecture Notes in Computer Science, vol. 3242: Parallel Problem Solving from Nature - PPSN, pp. 1123–1132, 2004.
[55]H. Ishibuchi, K. Isao, and N. Yusuke, “Evolutionary multi-objective rule selection for classification rule mining,” Studies in Computational Intelligence, vol. 98, pp. 47–70, 2008.
[56]K. C. Tan, Q. Yu, and J. H. Ang, “A dual-objective evolutionary algorithm for rules extraction in data mining,” Computational Optimization and Applications, vol. 34, pp. 273-294, 2006.
[57]C. A. C. Coello, G. B. Lamont, and D. A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems. Springer-Verlag New York Inc, 2007.
[58]D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman, 1989.
[59]H. Beyer and H. Schwefel, “Evolution strategies–A comprehensive introduction,” Natural Computing, vol. 1, no. 1, pp. 3–52, 2002.
[60]M. Dorigo and T. Stützle, Ant Colony Optimization. The MIT press, 2004.
[61]J. Kennedy and R. C. Eberhart, Swarm Intelligence. Morgan Kaufmann, 2001.
[62]D. Dasgupta, Artificial Immune Systems and Their Applications, Springer-Verlag, 1999.
[63]M. Mitchell, An Introduction to Genetic Algorithms. Bradford Books, 1996.
[64]J. Holland, Adaptation in Natural and Artificial Systems. The MIT Press, 1975.
[65]L. Booker, “Intelligent behavior as an adaptation to the task environment,” Ph.D. dissertation, University of Michigan Ann Arbor, 1982.
[66]J. Baker, “Reducing bias and inefficiency in the selection algorithm,” in Proceedings of the International Conference on Genetic Algorithms and Their Application, Cambridge, MA, USA, 1987, pp. 14–21.
[67]H. Li and Q. Zhang, “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 2, pp. 284-302, 2009.
[68]K. Miettinen, Nonlinear Multiobjective Optimization. Norwell, MA: Kluwer, 1999.
[69]I. Das and J. E. Dennis, “Normal-boundary intersection: A new method for generating Pareto optimal points in multicriteria optimization problems,” SIAM Journal on Optimization, vol. 8, no. 3, pp. 631–657, 1998.
[70]R. Storn and K. Price, “Differential evolution a simple and efficient heuristic for global optimization over continuous spaces,” Global Optimization, vol. 11, no. 4, pp. 341–359, 1997.
[71]K. Deb, A. Sinha, and S. Kukkonen, “Multi-objective test problems, linkages, and evolutionary methodologies,” in Proceedings of Genetic and Evolutionary Computation Conference, Seattle, WA, USA, 2006, pp. 1141–1148.
[72]A. W. Iorio and X. Li, “Solving rotated multi-objective optimization problems using differential evolution,” in Proceedings of Joint Australian Conference Artificial Intelligence, Cairns, Australia, 2004, pp. 861–872.
[73]K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Chichester, U.K.: Wiley, 2001.
[74]P. Clark and R. Boswell, “Rule induction with CN2: Some recent improvements,” in Proceedings of the European Working Session on Learning, Porto, Portugal, 1991, pp. 151-163.
[75]T. Soule and J. A. Foster, “Effects of code growth and parsimony pressure on populations in genetic programming,” Evolutionary Computation, vol. 6, no. 4, pp. 293–309, 1998.
[76]H. A. Guvenir and I. Uysal, Bilkent University Function Approximation Repository, 2000. [http://funapp.cs.bilkent.edu.tr]
[77]C. L. Blake and C. J. Merz, UCI Repository of machine learning databases, Irvine, CA: University of California, Department of Information and Computer Science, 1998. [http://www.ics.uci.edu/~mlearn/MLRepository.html]
[78]G. H. John and P. Langley, “Estimating continuous distributions in Bayesian classifiers,” in Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence, Montreal, Canada, 1995, pp. 338–345.
[79]I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann Publishers: CA, 1999.
[80]J. Alcala-Fdez, L. Sanchez, S. Garcia, M. J. del Jesus, S. Ventura, J. M. Garrell, J. Otero, C. Romero, J. Bacardit, V.M. Rivas, J. C. Fernandez, and F. Herrera, “KEEL: A Software Tool to Assess Evolutionary Algorithms to Data Mining Problems,” Soft Computing, vol. 13, no. 3, pp. 307-318, 2009.
[81]M. Matsumoto and T. Nishimura, “Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator,” ACM Transactions on Modeling and Computer Simulation, vol. 8, no. 1, pp. 3–30, 1998.