簡易檢索 / 詳目顯示

回結果列表
研究生： 詹盈芳
Chan, Ying-fang
論文名稱： 粒子群演算法於具理解性分類知識發現之研究
Comprehensible Knowledge Discovery using Particle Swarm Optimization for Classification Tasks
指導教授： 李昇暾
Li, Sheng-Tun
學位類別： 碩士
Master
系所名稱： 管理學院 - 資訊管理研究所
Institute of Information Management
論文出版年： 2008
畢業學年度： 96
語文別： 英文
論文頁數： 64
外文關鍵詞： Constraints, Monotonicity, Rules extraction, Particle Swarm Optimization, Data Mining
相關次數： 點閱：114  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • Data mining techniques enable us to discover hidden patterns and extract valuable knowledge from databases. Although most proposed methods indeed have good performance e.g. high accuracy, rules resulted from data mining process sometimes contradict expert knowledge even common sense due to data quality. Knowledge discovery in databases (KDD) should require not only accurate predictions but also comprehensible rules.
    This study focuses on classification problems and emphasizes comprehensibility of extracting knowledge. Owing to Particle Swarm Optimization (PSO) is a suitable candidate for optimization tasks, and is competitive with other optimization algorithms. This study exploits constraints and monotonicity for the purpose of satisfying rules comprehensibility and combines PSO with these characteristics. Therefore, constraints-based PSO classifier is a useful model with comprehensibility and justifiability.

    ABSTRACT I ACKNOWLEDGEMENT II TABLE OF CONTENETS III LIST OF TABLES V LIST OF FIGURES VI CHAPER 1 Introduction 1 1.1 Background and motivation 1 1.2 Objectives 2 1.3Thesis Organization 3 CHAPTER 2 Literature Review 5 2.1 Particle Swam Optimization 5 2.1.1 Evolution of PSO 5 2.1.2 Application of PSO 10 2.2 Decision rules in classification 11 2.2.1 Rule representation 11 2.2.2 Fitness functions for rule discovery 13 2.2.3 Classification rules mining 16 2.3 Constraints 17 2.3.1 Constraints satisfaction 17 2.3.2 Monotonicity Constraints 18 CHAPTER 3 A two-phase classifier based on PSO 20 3.1 Phase one: Constraint-based PSO 21 3.1.1 Setting constraints and parameters 22 3.1.2 Swarm initialization 24 3.1.3 Particle evaluating and replacement 26 3.1.4 Position update and constraints checking 31 3.1.5 Position update and constraints checking 32 3.2 Phase two: The interesting rule set evolver 33 3.2.1 Swarm initialization 34 3.2.2 Evaluate rule set fitness: interestingness measure 34 3.2.3 Evaluate rule set accuracy 37 3.2.4 Post-processing of rule set 38 CHAPTER 4 Experiment and results analysis 39 4.1 Data collection 39 4.2 Experiment setup 41 4.2.1 Parameter settings 42 4.3 Experiments results and comparisons against other classification techniques 50 CHAPTER 5 Conclusions and future work 59 5.1 Conclusions 59 5.2 Future work 60 REFERENCES 61

    Chiu, C., & Hsu, P.-L. A constraint-based genetic algorithm approach for mining classification rules. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PARTC: Application and reviews, 35(2), 205-220, 2005.
    Clerc, M., & Kennedy, J. The particle swarm-explosion, stability and convergence in a multi-dimentional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73, 2002.
    David, M., Manu, D. B., Raf, H., Bart, B., Christophe, M., & Jan, V. Ant-based approach to the knowledge fusion problem. Ant Colony Optimization and Swarm Intelligence, 2006.
    Eberhart, R. C., & Shi, Y. Comparison between genetic algorithms and particle swarm optimization. 1998 Annual Conference on Evolutionary Programming, 1998a.
    Eberhart, R. C., & Shi, Y. Evolving artificial neural networks. Proceedings of the 1998 International Conference on Neural Networks and Brain, Beijing, China, 1998b.
    Eberhart, R. C., & Shi, Y. Comparing inertia weights and constriction factors in particle swarm optimization. Proceeding of 2002 IEEE CEC, 2000.
    Eberhart, R. C., & Shi, Y. Particle swarm optimization: developments, application and resources. Congress on Evolutionary Computation, Seoul, South Korea, 2001.
    Falco, I. D., Cioppa, A. D., & Tarantino, E. Facing classification problems with particle swarm optimization. Applied Soft Computing, 7(3), 652-658, 2007.
    Freitas, A. A survey of evolutionary algorithms for data mining and knowledge discovery. Advances in evolutionary computation, 2002.
    Gago, P., & Bentos, C. A metric for selection of the most promising rules. Principles of data mining and knowledge discovery, Nantes, France, 1998.
    Garofalakis, M., & Rastogi, R. Scalable data mining with model constraints. SIGKDD Explorations, 2(2), 39-48, 2000.
    Hilderman, R., & Hamilton, H. Measuring the interestingness of discovered knowledge: a principled approach. Intelligent Data Analysis, 7(4), 347-382, 2003.
    Hu, X., Eberhart, R. C., & Shi, Y. Swarm intelligence for permutation optimization: a case study of n-queens problem. Proceedings of the 2003 IEEE Swarm Intelligence Symposium (SIS '03), Indianapolis, Indiana USA
    2003.
    Hu, X., Shi, Y., & Eberhart, R. C. Recent advances in particle swarm. Proceedings of IEEE Congress on Evolutionary Computation 2004 (CEC 2004), 1, 90-97, 2004.
    Kamber, M., & Shinghal, R. Evaluating the interestingness of characteristic rules. Proceeding of the second International Conference on Knowledge Discovery and Data Mining, Portland Oregon, 1996.
    Kennedy, J., & Eberhart, R. Particle swarm optimization. Proceedings of the 1995 IEEE International Conference on Neural Networks, Piscataway, NJ, 1995.
    Liu, B., Hsu, W., Mun, L.-F., & Lee, H.-Y. Finding interesting patterns using user expectations. IEEE Transactions on Knowledge and Data Engineering, 11(6), 817-832, 1999.
    McGarry, K. A survey of interestingness measures for knowledge discovery. The Knowledge Engineering Review, 20(1), 39-61, 2005.
    Mendes, R., Kennedy, J., & Neves, J. The fully informed particle swarm: simpler, maybe better. IEEE Transactions on Evolutionary Computation, 8(3), 204-210, 2004.
    Noda, E., Freitas, A. A., & Lopes, H. S. Discovering Interesting Prediction rules with a Genetic Algorithm. Conference on Evolutionary Computation, Washington D.C., USA, 1999.
    Padmanabhan, B., & Tuzhilin, A. Unexpectedness as a measure of interestingness in knowledge discovery. Decision Support Systems, 27, 303-318, 1999.
    Padmanabhan, B., & Tuzhilin, A. Knowledge refinement based on the discovery of unexpected patterns in data mining. Decision Support Systems, 33, 309-321, 2002.
    Parsopoulos, K. E., & Vrahatis, M. N. Particle swarm optimization method in multi-objective problems. Proceedings of the 2002 ACM symposium on Applied computing, Madrid, Spain 2002.
    Parsopoulos, K. E., & Vrahatis, M. N. UPSO: A unified particle swarm optimization scheme. Proceedings of the International Conference of Computational Methods in Sciences and Engineering (ICCMSE 2004), Zeist, The Netherlands, 2004.
    Parsopoulos, K. E., & Vrahatis, M. N. Parameter selection and adaptation in Unified Particle Swarm Optimization. Mathematical and Computer Modeling, 46, 198-213, 2007.
    Reyes-Sierra, M., & Coello, C. A. Multi-objective particle swarm optimizers: a survey of the state-of-the-art. International Journal of Computational Intelligence Research, 2(3), 287-308, 2006.
    Romão, W., Freitas, A. A., & Gimenes, I. M. d. S. Discovering interesting knowledge from a science and technology database with a genetic algorithm. Aplied soft computing, 4(2), 121-137, 2004.
    Salerno, J. Using the particle swarm optimization technique to train a recurrent neural model. Proceedings of the Ninth IEEE International Conference on Tools with Artificial Intelligence Newport Beach, CA, USA, 1997.
    Shi, Y., & Eberhart, R. A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, NJ, 1998.
    Sousa, T., Silva, A., & Neves, A. Particle swarm based data mining algorithms for classification tasks. Parallel Computing, 30(5-6), 767-783, 2004.
    Taguchi, G. Introduction to Quality Engineering. Tokyo: Asian Productivity Organization, 1986.
    Tan, K. C., Yu, Q., & Ang, J. H. A dual-objective evolutionary algorithm for rules extraction in data mining. Computational optimization and applications, 34, 273-294, 2006.
    Tan, K. C., Yu, Q., Heng, C. M., & Lee, T. H. Evolutionary computing for knowledge discovery in medical diagnosis. Artificial Intelligence in Medicine, 27, 129-154, 2003.
    Trelea, I. C. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters, 85, 317-325, 2003.
    Tripathi, P. K., Bandyopadhyay, S., & Pal, S. K. Multi-Objective Particle Swarm Optimization with time variant inertia and acceleration coefficients. Information Sciences, 177, 5033-5049, 2007.
    Wang, K. P., Huang, L., Zhou, C. G., & Pang, W. Particle swarm optimization for traveling salesman problem. Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi'an, China, 2003.
    Wang, X., Yang, J., Teng, X., Xia, W., & Jensen, R. Feature selection based on rough sets and particle swarm optimization. Pattern Recognition Letters, 28, 459-471, 2007.
    Witten, I. H., & Frank, E. Data Mining: Practical Machine Learning Tools and Techniques. San Francisco: Morgan Kaufmann, 2000.

    下載圖示 校內：2013-06-20公開
    校外：2013-06-20公開
    QR CODE