簡易檢索 / 詳目顯示

回結果列表
研究生： 黃植暄
Chih-Hsuan Huang
論文名稱： 應用蜂群演算法為基礎之屬性選擇及參數最佳化之支撐向量機於規則萃取
Artificial Bee Colony-based Support Vector Machines with Feature Selection and Parameters Optimization for Rule Extraction
指導教授： 郭人介
Ren-Jieh Kuo
口試委員: 喻奉天
Vincent F. Yu
林希偉
Shi-Woei Lin
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2014
畢業學年度： 102
語文別： 英文
論文頁數： 108
中文關鍵詞： 支撐向量機 、蜂群演算法 、決策樹 、分類 、規則萃取 、屬性選擇 、參數最佳化
外文關鍵詞： Support vector machines, Artificial bee colony, Decision tree, Classification, Rule extraction, Feature selection, Parameters optimization
相關次數： 點閱：244  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 分類問題在資料探勘中是一個重要的議題，而支撐向量機(Support Vector Machines, SVMs)靠著解決非線性問題的能力得到較好的分類準確性，在現今解決分類問題上扮演著相當重要的角色，但是它的優點伴隨著一個缺點，就像其它產生非線性模型的方法一樣，被認為是不可理解的黑箱型分類方法，這個缺點是非常嚴重的，因為在許多特定的應用領域上，可理解性是必須的，像是在醫療診斷的應用上。為了解決這個問題，有研究提出了使用主動式學習為基礎之方法(Active Learning-Based Approach, ALBA)，一種藉由決策樹(Decision Tree, DT)從支撐向量機裡萃取決策規則的方法，此方法確實可以從支撐向量機裡得到可理解的分類規則，同時也改善了單純使用決策樹時的分類準確率，但是ALBA在最終階段產出的決策樹，一般來說都非常複雜，因此在本研究我們提出了ABC-SVM-DT演算法來從支撐向量機裡萃取決策規則，其中蜂群演算法(Artificial Bee Colony Algorithm, ABC)在其中扮演著資料在進入SVM-DT前，挑選屬性以及最佳化參數的角色，為了驗證此方法的有效性，我們使用的UCI裡的六個資料集去做驗證，結果顯示本研究提出的ABC-SVM-DT 演算法可以同時改善分類準確率以及最終決策樹之複雜度。

    Classification is an important issue in data mining. Support vector machines (SVMs) are currently state-of-art for the classification task and, generally speaking, exhibit good classification accuracy due to their ability to nonlinearities. However, its strength is also its main weakness, as the generated nonlinear models are typically regarded as incomprehensible black-box models. This inability in explanation of SVMs is a serious problem in those particular applications which require the comprehensibility such as medical diagnosis. In order to overcome this inability, previous research proposed the Active Learning-Based Approach (ALBA) to extract the comprehensible rules from SVMs using decision tree classifier. The result shows ALBA actually can extract rules and improve the classification accuracy from original decision tree. However, the final decision trees generated by ALBA are generally too complicated. Thus, this study proposes a novel artificial bee colony-SVM-decision tree (ABC-SVM-DT) algorithm to extract comprehensible rules from SVMs. The ABC algorithm is applied to implement feature selection and parameters optimization before SVM-DT. For evaluation, six datasets from the UCI Machine Learning Repository are employed to demonstrate the effectiveness of the proposed algorithm. The result shows the classification accuracy and the complexity of final decision tree can be improved simultaneously by the proposed ABC-SVM-DT algorithm.

    摘要 I ABSTRACT II 誌謝 III CONTENTS IV LIST OF TABLES VII LIST OF FIGURES VIII CHAPTER 1 INTRODUCTION 1 1.1 Background 1 1.2 Research Objectives 3 1.3 Research Scope 4 1.4 Thesis Organization 4 CHAPTER 2LITERATURE REVIEW 6 2.1 The Support Vector Machines 6 2.1.1 The Linear SVM (separable data) 6 2.1.2 The Linear Generalized SVM (nonseparable data) 8 2.1.3 Non-Linear SVM 9 2.2 Rule Extraction from SVMs 10 2.2.1 Utilizing SVM as a Black Box 12 2.2.2 Utilizing SVs in SVM only 13 2.2.3 Utilizing SVs and the Separating Hyper-plane in SVM 15 2.2.4 Utilizing SVs, Training Data and Separating Hyper-plane 16 2.3 The Support Vector Machine with Metaheuristics 18 2.3.1 SVM with Genetic Algorithm 19 2.3.2 Particle Swarm Optimization with SVM 20 2.3.3 Artificial Bee Colony with SVM 21 2.4 Decision Tree 22 CHAPTER 3 METHODOLOGY 24 3.1 Preprocessing and Defining Phase 24 3.2 Artificial Bee Colony Phase 26 3.3 Support Vector Machine-Decision Tree Phase 27 CHAPTER 4 NUMERICAL ILLUSTRATION 30 4.1 Datasets 30 4.2 Evaluation Criterion 30 4.3 Experiment Setup 31 4.3.1 Parameter Determination 32 4.4 Experiment result 37 4.4.1 Statistic Test 40 4.4.2 Comparison between Original DT and SVM-DT 48 4.4.3 Comparison among SVM-DT and the Feature Selection and Parameters Optimization based SVM-DT (PSO-SVM-DT, GA-SVM-DT and ABC-SVM-DT) 55 CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH 60 5.1 Conclusions 60 5.2 Contributions 61 5.3 Future Research 61 REFERENCES 63 APPENDIX 72 Appendix I- Experiment results of full factorial design for ABC-SVM-DT. 72 Appendix II- Experiment results of Taguchi method (citation) for GA-SVM-DT. 73 Appendix III- Experiment results of Taguchi method (citation) for PSO-SVM-DT. 76 Appendix IV- Experiment results of Iris dataset using ABC-SVM-DT. 79 Appendix V- Experiment results of Wine dataset using ABC-SVM-DT. 80 Appendix VI- Experiment results of Ionosphere dataset using ABC-SVM-DT. 81 Appendix VII- Experiment results of Sonar dataset using ABC-SVM-DT. 82 Appendix VIII- Experiment results of Cmc dataset using ABC-SVM-DT. 83 Appendix IX- Experiment results of German dataset using ABC-SVM-DT. 84 Appendix X- Experiment results of Iris dataset using GA-SVM-DT. 85 Appendix XI- Experiment results of Wine dataset using GA-SVM-DT. 86 Appendix XII- Experiment results of Ionosphere dataset using GA-SVM-DT. 87 Appendix XIII- Experiment results of Sonar dataset using GA-SVM-DT. 88 Appendix XIV- Experiment results of Cmc dataset using GA-SVM-DT. 89 Appendix XV- Experiment results of German dataset using GA-SVM-DT. 90 Appendix XVI- Experiment results of Iris dataset using PSO-SVM-DT. 91 Appendix XVII- Experiment results of Wine dataset using PSO-SVM-DT. 92 Appendix XVIII- Experiment results of Ionosphere dataset using PSO-SVM-DT. 93 Appendix XIX- Experiment results of Sonar dataset using PSO-SVM-DT. 94 Appendix XX- Experiment results of Cmc dataset using PSO-SVM-DT. 95 Appendix XXI- Experiment results of German dataset using PSO-SVM-DT. 96 Appendix XXII- Experiment results of Iris dataset using SVM-DT. 97 Appendix XXIII- Experiment results of Wine dataset using SVM-DT. 98 Appendix XXIV- Experiment results of Ionosphere dataset using SVM-DT. 99 Appendix XXV- Experiment results of Sonar dataset using SVM-DT. 100 Appendix XXVI- Experiment results of Cmc dataset using SVM-DT. 101 Appendix XXVII- Experiment results of German dataset using SVM-DT. 102 Appendix XXVIII- Experiment results of Iris dataset using DT. 103 Appendix XXIX- Experiment results of Wine dataset using DT. 104 Appendix XXX- Experiment results of Ionosphere dataset using DT. 105 Appendix XXXI- Experiment results of Sonar dataset using DT. 106 Appendix XXXII- Experiment results of Cmc dataset using DT. 107 Appendix XXXIII- Experiment results of German dataset using DT. 108

    Akay, B. & Karaboga, D., "Parameter Tuning for the Artificial Bee Colony Algorithm," in Computational Collective Intelligence. Semantic Web, Social Networks and Multiagent Systems. vol. 5796, N. Nguyen, R. Kowalczyk, and S.-M. Chen, Eds., ed: Springer Berlin Heidelberg, 2009, pp. 608-619.
    Andrews, R., Diederich, J., & Tickle, A. B., "Survey and critique of techniques for extracting rules from trained artificial neural networks," Knowledge-based systems, vol. 8, no. 6, pp. 373-389, 1995.
    Baesens, B., Van Gestel, T., Viaene, S., Stepanova, M., Suykens, J., & Vanthienen, J., "Benchmarking state-of-the-art classification algorithms for credit scoring," Journal of the Operational Research Society, vol. 54, no. 6, pp. 627-635, 2003.
    Barakat, N. & Bradley, A. P., "Rule extraction from support vector machines: a review," Neurocomputing, vol. 74, no. 1, pp. 178-190, 2010.
    Barakat, N. & Diederich, J., "Learning-based rule-extraction from support vector machines," in The 14th International Conference on Computer Theory and applications ICCTA'2004, 2004.
    Barakat, N. & Diederich, J., "Eclectic rule-extraction from support vector machines," International Journal of Computational Intelligence, vol. 2, no. 1, pp. 59-62, 2005.
    Barakat, N. H. & Bradley, A. P., "Rule extraction from support vector machines: a sequential covering approach," Knowledge and Data Engineering, IEEE Transactions on, vol. 19, no. 6, pp. 729-741, 2007.
    Barros, M., Guilherme, J., & Horta, N., "GA-SVM optimization kernel applied to analog IC design automation," in Electronics, Circuits and Systems, 2006. ICECS'06. 13th IEEE International Conference on, 2006, pp. 486-489.
    Ben-Hur, A., Horn, D., Siegelmann, H. T., & Vapnik, V., "Support vector clustering," The Journal of Machine Learning Research, vol. 2, pp. 125-137, 2002.
    Berry, M. J. & Linoff, G., Data mining techniques: for marketing, sales, and customer support: John Wiley & Sons, Inc., 1997.
    Bianchi, L., Dorigo, M., Gambardella, L. M., & Gutjahr, W. J., "A survey on metaheuristics for stochastic combinatorial optimization," Natural Computing: an international journal, vol. 8, no. 2, pp. 239-287, 2009.
    Bishop, C. M., Neural networks for pattern recognition: Oxford university press, 1995.
    Blum, C. & Roli, A., "Metaheuristics in combinatorial optimization: Overview and conceptual comparison," ACM Computing Surveys (CSUR), vol. 35, no. 3, pp. 268-308, 2003.
    Boswell, D., "Introduction to support vector machines," ed: August, 2002.
    Breiman, L., "Classification and regression trees," 1984.
    Brown de Colstoun, E. C., Story, M. H., Thompson, C., Commisso, K., Smith, T. G., & Irons, J. R., "National Park vegetation mapping using multitemporal Landsat 7 data and a decision tree classifier," Remote Sensing of Environment, vol. 85, no. 3, pp. 316-327, 2003.
    Browne, A., Hudson, B. D., Whitley, D. C., Ford, M. G., & Picton, P., "Biological data mining with neural networks: Implementation and application of a flexible decision tree extraction algorithm to genomic problem domains," Neurocomputing, vol. 57, pp. 275-293, 2004.
    Burges, C. J., "A tutorial on support vector machines for pattern recognition," Data mining and knowledge discovery, vol. 2, no. 2, pp. 121-167, 1998.
    Chaves, A. C., Vellasco, M. M. B., & Tanscheit, R., "Fuzzy rule extraction from support vector machines," in Hybrid Intelligent Systems, 2005. HIS'05. Fifth International Conference on, 2005, p. 6 pp.
    Chen, M.-S., Han, J., & Yu, P. S., "Data mining: an overview from a database perspective," Knowledge and data Engineering, IEEE Transactions on, vol. 8, no. 6, pp. 866-883, 1996.
    Chen, Z., Li, J., & Wei, L., "A multiple kernel support vector machine scheme for feature selection and rule extraction from gene expression data of cancer tissue," Artificial Intelligence in Medicine, vol. 41, no. 2, pp. 161-175, 2007.
    Chunhong, Z. & Licheng, J., "Automatic parameters selection for SVM based on GA," in Intelligent Control and Automation, 2004. WCICA 2004. Fifth World Congress on, 2004, pp. 1869-1872.
    Downs, T., Gates, K. E., & Masters, A., "Exact simplification of support vector solutions," The Journal of Machine Learning Research, vol. 2, pp. 293-297, 2002.
    Eiben, A. E., Hinterding, R., & Michalewicz, Z., "Parameter control in evolutionary algorithms," Evolutionary Computation, IEEE Transactions on, vol. 3, no. 2, pp. 124-141, 1999.
    Furnkranz, J. & Flach, P. A., "Roc ‘n’rule learning—towards a better understanding of covering algorithms," Machine Learning, vol. 58, no. 1, pp. 39-77, 2005.
    Fayyad, U. M., Piatetsky-Shapiro, G., Smyth, P., & Uthurusamy, R., "Advances in knowledge discovery and data mining," 1996.
    Frohlich, H., Chapelle, O., & Scholkopf, B., "Feature selection for support vector machines by means of genetic algorithm," in Tools with Artificial Intelligence, 2003. Proceedings. 15th IEEE International Conference on, 2003, pp. 142-148.
    Fu, X., Ong, C., Keerthi, S., Hung, G. G., & Goh, L., "Extracting the knowledge embedded in support vector machines," in Neural Networks, 2004. Proceedings. 2004 IEEE International Joint Conference on, 2004.
    Fung, G., Sandilya, S., & Rao, R. B., "Rule extraction from linear support vector machines," in Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, 2005, pp. 32-40.
    Goldberg, D. E. & Holland, J. H., "Genetic algorithms and machine learning," Machine learning, vol. 3, no. 2, pp. 95-99, 1988.
    Hsu, C.-W., Chang, C.-C., & Lin, C.-J., "A practical guide to support vector classification," ed, 2003.
    Hsu, C.-W. & Lin, C.-J., "A simple decomposition method for support vector machines," Machine Learning, vol. 46, no. 1-3, pp. 291-314, 2002.
    Hu, H., Harrison, R. W., Tai, P. C., & Pan, Y., "Current Methods for Protein Secondary-Structure Prediction Based on Support Vector Machines," Knowledge Discovery in Bioinformatics: Techniques, Methods, and Applications, pp. 1-26, 2007.
    Huang, C.-L. & Dun, J.-F., "A distributed PSO–SVM hybrid system with feature selection and parameter optimization," Applied Soft Computing, vol. 8, no. 4, pp. 1381-1391, 2008.
    Huang, C.-L. & Wang, C.-J., "A GA-based feature selection and parameters optimization for support vector machines," Expert Systems with applications, vol. 31, no. 2, pp. 231-240, 2006.
    Huerta, E. B., Duval, B., & Hao, J.-K., "A hybrid GA/SVM approach for gene selection and classification of microarray data," in Applications of Evolutionary Computing, ed: Springer, 2006, pp. 34-44.
    Huysmans, J., Baesens, B., & Vanthienen, J., "Using rule extraction to improve the comprehensibility of predictive models," DTEW-KBI_0612, pp. 1-55, 2006.
    Im, J. & Jensen, J. R., "A change detection model based on neighborhood correlation image analysis and decision tree classification," Remote Sensing of Environment, vol. 99, no. 3, pp. 326-340, 2005.
    Jiang, M.-H. & Yuan, X.-C., "Construction and application of PSO-SVM model for personal credit scoring," in Computational Science–ICCS 2007, ed: Springer, 2007, pp. 158-161.
    Joachims, T., Text categorization with support vector machines: Learning with many relevant features: Springer, 1998.
    Joachims, T., "A support vector method for multivariate performance measures," in Proceedings of the 22nd international conference on Machine learning, 2005, pp. 377-384.
    Johansson, U., Konig, R., & Niklasson, L., "The Truth is In There-Rule Extraction from Opaque Models Using Genetic Programming," in FLAIRS Conference, 2004, pp. 658-663.
    Kao, Y.-T. & Zahara, E., "A hybrid genetic algorithm and particle swarm optimization for multimodal functions," Applied Soft Computing, vol. 8, no. 2, pp. 849-857, 2008.
    Karaboga, D., "An idea based on honey bee swarm for numerical optimization," Techn. Rep. TR06, Erciyes Univ. Press, Erciyes, 2005.
    Karaboga, D. & Akay, B., "A comparative study of Artificial Bee Colony algorithm," Applied Mathematics and Computation, vol. 214, no. 1, pp. 108-132, 2009.
    Karaboga, D. & Basturk, B., "A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm," Journal of global optimization, vol. 39, no. 3, pp. 459-471, 2007.
    Karaboga, D. & Basturk, B., "On the performance of artificial bee colony (ABC) algorithm," Applied soft computing, vol. 8, no. 1, pp. 687-697, 2008.
    Kecman, V., Learning and soft computing: support vector machines, neural networks, and fuzzy logic models: MIT press, 2001.
    Kennedy, J., "Particle swarm optimization," in Encyclopedia of Machine Learning, ed: Springer, 2010, pp. 760-766.
    Khemchandani, R. & Chandra, S., "Twin support vector machines for pattern classification," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 29, no. 5, pp. 905-910, 2007.
    Kuo, R., Zulvia, F. E., & Suryadi, K., "Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand–A case study on garbage collection system," Applied Mathematics and Computation, vol. 219, no. 5, pp. 2574-2588, 2012.
    LaValle, S. M., Branicky, M. S., & Lindemann, S. R., "On the relationship between classical grid search and probabilistic roadmaps," The International Journal of Robotics Research, vol. 23, no. 7-8, pp. 673-692, 2004.
    Lin, H.-T. & Lin, C.-J., "A study on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods," Technical report, Department of Computer Science, National Taiwan University, 2003.
    Lin, L., "Integration of Particle Swarm K-means Optimization Algorithm and Granular Computing for Imbalanced Data Classification Problem-A Case Study on Prostate Cancer Prognosis," 2013.
    Martens, D., Baesens, B., & Van Gestel, T., "Decompositional rule extraction from support vector machines by active learning," Knowledge and Data Engineering, IEEE Transactions on, vol. 21, no. 2, pp. 178-191, 2009.
    Martens, D., Baesens, B., Van Gestel, T., & Vanthienen, J., "Comprehensible credit scoring models using rule extraction from support vector machines," European journal of operational research, vol. 183, no. 3, pp. 1466-1476, 2007.
    Mitchell, T. M., "Machine learning and data mining," Communications of the ACM, vol. 42, no. 11, pp. 30-36, 1999.
    Moschitti, A., Pighin, D., & Basili, R., "Semantic role labeling via tree kernel joint inference," in Proceedings of the Tenth Conference on Computational Natural Language Learning, 2006, pp. 61-68.
    Nunez, H., Angulo, C., & Catala, A., "Support vector machines with symbolic interpretation," in Neural Networks, 2002. SBRN 2002. Proceedings. VII Brazilian Symposium on, 2002a, pp. 142-147.
    Nunez, H., Angulo, C., & Catala, A., "Rule extraction from support vector machines," in ESANN, 2002b, pp. 107-112.
    Nunez, H., Angulo, C., & Catala, A., "Rule-based learning systems for support vector machines," Neural Processing Letters, vol. 24, no. 1, pp. 1-18, 2006.
    Poli, R., Kennedy, J., & Blackwell, T., "Particle swarm optimization," Swarm intelligence, vol. 1, no. 1, pp. 33-57, 2007.
    Pontil, M. & Verri, A., "Support vector machines for 3D object recognition," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 20, no. 6, pp. 637-646, 1998.
    Quinlan, J. R., "Induction of decision trees," Machine learning, vol. 1, no. 1, pp. 81-106, 1986.
    Quinlan, J. R., C4. 5: programs for machine learning vol. 1: Morgan kaufmann, 1993.
    Ranaee, V., Ebrahimzadeh, A., & Ghaderi, R., "Application of the PSO–SVM model for recognition of control chart patterns," ISA transactions, vol. 49, no. 4, pp. 577-586, 2010.
    Rokach, L., Data mining with decision trees: theory and applications vol. 69: World scientific, 2008.
    Samadzadegan, F. & Saeedi, S., "Clustering Of Lidar Data Using Particle Swarm Optimization Algorithm In Urban Area," Laserscanning09, vol. 38, pp. 334-339, 2009.
    Shi, Y. & Eberhart, R., "Parameter selection in particle swarm optimization," in Evolutionary Programming VII. vol. 1447, V. W. Porto, N. Saravanan, D. Waagen, and A. E. Eiben, Eds., ed: Springer Berlin Heidelberg, 1998, pp. 591-600.
    Smola, A. J., Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond: MIT press, 2002.
    Sugumaran, V., Muralidharan, V., & Ramachandran, K., "Feature selection using decision tree and classification through proximal support vector machine for fault diagnostics of roller bearing," Mechanical Systems and Signal Processing, vol. 21, no. 2, pp. 930-942, 2007.
    Sulaiman, M. H., Mustafa, M. W., Shareef, H., & Abd Khalid, S. N., "An application of artificial bee colony algorithm with least squares support vector machine for real and reactive power tracing in deregulated power system," International Journal of Electrical Power & Energy Systems, vol. 37, no. 1, pp. 67-77, 2012.
    Suykens, J. A. & Vandewalle, J., "Least squares support vector machine classifiers," Neural processing letters, vol. 9, no. 3, pp. 293-300, 1999.
    Taguchi, G., Introduction to quality engineering: designing quality into products and processes, 1986.
    Torres, D. & Rocco, C., "Extracting trees from trained SVM models using a TREPAN based approach," in Hybrid Intelligent Systems, 2005. HIS'05. Fifth International Conference on, 2005, p. 6 pp.
    Van Gestel, T., Suykens, J. A., Baesens, B., Viaene, S., Vanthienen, J., Dedene, G., et al., "Benchmarking least squares support vector machine classifiers," Machine Learning, vol. 54, no. 1, pp. 5-32, 2004.
    Van Gestel, T., Suykens, J. A., Baestaens, D.-E., Lambrechts, A., Lanckriet, G., Vandaele, B., et al., "Financial time series prediction using least squares support vector machines within the evidence framework," Neural Networks, IEEE Transactions on, vol. 12, no. 4, pp. 809-821, 2001.
    Vapnik, V., The nature of statistical learning theory: springer, 1995.
    Vapnik, V., The nature of statistical learning theory: springer, 2000.
    Venter, G. & Sobieszczanski-Sobieski, J., "Particle swarm optimization," AIAA journal, vol. 41, no. 8, pp. 1583-1589, 2003.
    Vose, M. D., The simple genetic algorithm: foundations and theory vol. 12: The MIT Press, 1999.
    Waske, B. & Benediktsson, J. A., "Fusion of support vector machines for classification of multisensor data," Geoscience and Remote Sensing, IEEE Transactions on, vol. 45, no. 12, pp. 3858-3866, 2007.
    Whitley, D., "A genetic algorithm tutorial," Statistics and computing, vol. 4, no. 2, pp. 65-85, 1994.
    Yang, J. & Honavar, V., "Feature subset selection using a genetic algorithm," in Feature extraction, construction and selection, ed: Springer, 1998, pp. 117-136.
    Yu, G.-X., Ostrouchov, G., Geist, A., & Samatova, N. F., "An SVM-based algorithm for identification of photosynthesis-specific genome features," in Bioinformatics Conference, 2003. CSB 2003. Proceedings of the 2003 IEEE, 2003, pp. 235-243.
    Zhang, Y., Su, H., Jia, T., & Chu, J., "Rule extraction from trained support vector machines," in Advances in Knowledge Discovery and Data Mining, ed: Springer, 2005, pp. 61-70.

    QR CODE