進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2007201616294700
論文名稱(中文) 平行化共軛梯度演算法於單調性限制支援向量機之研究
論文名稱(英文) A Parallelized Conjugate Gradient Algorithm for Monotonicity Constrained Support Vector Machines
校院名稱 成功大學
系所名稱(中) 資訊管理研究所
系所名稱(英) Institute of Information Management
學年度 104
學期 2
出版年 105
研究生(中文) 周琦
研究生(英文) CHI CHOU
電子信箱 cycle-zz@hotmail.com
學號 R76031121
學位類別 碩士
語文別 英文
論文頁數 55頁
口試委員 指導教授-李昇暾
口試委員-林清河
口試委員-耿伯文
口試委員-陳志全
中文關鍵字 支援向量機  單調性先驗知識  共軛梯度演算法  平行化策略 
英文關鍵字 Support Vector Machines  Monotonic Prior knowledge  Conjugate Gradient Algorithm  Parallel Strategy 
學科別分類
中文摘要 資料探勘為一種資料庫知識探索的工具,其計算過程能從資料中找出潛藏價值,而分類更是其中最重要且常被使用的資料探勘技術。許多分類技術,包含支援向量機(SVMs)在內,已經有多年的發展。近年來,支援向量機因為在解決問題上有優異的表現而成為指標性的分類演算法,然而支援向量機(SVMs)是一種高運算成本以及易受雜訊資料影響的機器學習演算法,為提升支援向量機的效能,對於不同實際問題的情境亦投入多方努力在改善,舉例而言,加以考量專家知識已被證實能幫助支援向量機處理雜訊資料得到更有用的結果,此種支援向量機則被稱為知識導向的支援向量機,加入單調性限制後的支援向量機透過使用二次規劃的方法計算矩陣產生相當大的運算成本。
在大數據的時代裡,資訊無所不在,電腦硬體的進步已經追不上資訊成長的速度,隨著資料增加,支援向量機的效率明顯下降,因此本研究利用數值分析方法中的共軛梯度演算法對支援向量機的二次規劃問題進行求解,由於共軛梯度演算法的特性可使資料分解成較小集合再使用電腦平行化處理的技術將支援向量機的問題進行平行式處理,針對大型及高複雜資料經過切割後求解,大幅降低訓練時間,增加支援向量機處理大量資料的可行性。
英文摘要 Data mining, also known as knowledge discovery in database (KDD), is the computational process of discovering patterns from observed data, for which classification is one of the most important tasks in data mining. Many classification techniques, including Support Vector Machines (SVMs), have been developed over the years. Recently, SVMs have become state-of-art classifiers due to their excellent ability in solving classification problems. However, SVMs also have drawbacks, such as high computing cost with large amounts of data and high susceptibility to noisy data. Various efforts have been made to improve SVMs based on different scenarios of real world problems. Among them, taking into account experts' knowledge has been confirmed to help SVMs deal with noisy data to gain more useful results. For example, SVMs with monotonicity constraints and with the Tikhonov regularization method, also known as Regularized Monotonic SVM (RMC-SVM) incorporates inequality constraints into SVMs based on the monotonic property of real-world problems and use the Tikhonov regularization method is further applied to ensure that the solution is unique and bounded. These kinds of SVMs are also referred to as knowledge-oriented SVMs. However, solving SVMs with monotonicity constraints will require even more computational time than SVMs.
In the era of big data, information is ubiquitous. The progress of data processing and analyzing the ability of computer hardware has fallen behind the growth of information. With the size of dataset becoming larger and larger, the efficiency of SVMs decreased gradually. Therefore, in this research, a parallelized Conjugate Gradient (CG) strategy is proposed to solve the regularized monotonicity constrained SVMs. Due to the characteristics of the CG method, the dataset can be divided into n parts for parallel computing at different times. This study proposed an RMC-SVMs with a parallel strategy to reduce the required training time and to increase the feasibility of using RMC-SVMs in real world applications.
論文目次 摘要 I
ABSTRACT II
誌謝 IV
CONTENTS V
List of Tables VII
List of Figures VIII
Chapter 1 Introduction 1
1.1 Background and motivation 1
1.2 Research Objectives 4
1.3 Organization of Research 5
Chapter2 Literature Review 7
2.1 Support Vector Machines (SVMs) 7
2.1.1 Evolution of SVMs 7
2.1.2 Applications of SVMs 9
2.2 Classification with Monotonicity Constraints 10
2.3 Conjugate Gradient Algorithm with SVM 12
2.4 Parallel Strategy of SVM 12
Chapter 3 Research Methodology 14
3.1 Concept of Monotonicity 14
3.1.1 Definition of Monotonicity 14
3.1.2 Constructing the Monotonicity Constraints 15
3.2 Construct of the Regularized Monotonic SVM Model 19
3.3 Conjugate Gradient Method to Solve RMC-SVM 23
3.3.1 Concept of Conjugate Gradient Method 23
3.3.2 Conjugate Gradient Method to Solve RMC-SVM 25
3.4 Parallel Strategy to Solve RMC-SVM 27
Chapter 4 Experimental Results and Analysis 29
4.1 Experimental Design 29
4.2 Data Collection 32
4.3 Performance Measures 34
4.4 Experimental Result 36
4.4.1 Comparison of RMC-SVM and Mixture RMC-SVM 37
4.4.2 Comparison of Mixture SVM and Mixture RMC-SVM 40
4.4.3 Impacts of Different Surfaces 45
Chapter 5 Conclusions and Suggestions 48
5.1 Contributions 48
5.2 Managerial Implications 49
5.3 Recommendations of Future Works 49
REFERENCES 51

參考文獻 Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. Paper presented at the Proceedings of the fifth annual workshop on Computational learning theory.
Burges, C. J. (1998). A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2(2), 121-167.
Chang, C.-C., & Lin, C.-J. (2011). LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3), 27.
Chattratichat, J., Darlington, J., Ghanem, M., Guo, Y., Hüning, H., Koehler, M., . . . Yang, D. (1997). Large Scale Data Mining: Challenges and Responses. Paper presented at the KDD.
Chen, C.-C., & Li, S.-T. (2014). Credit rating with a monotonicity-constrained support vector machine model. Expert Systems with Applications, 41(16), 7235-7247.
Collobert, R., Bengio, S., & Bengio, Y. (2002). A parallel mixture of SVMs for very large scale problems. Neural computation, 14(5), 1105-1114.
Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine learning, 20(3), 273-297.
Dai, Y.-H., & Fletcher, R. (2006). New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Mathematical Programming, 106(3), 403-421.
Decherchi, S., Ridella, S., Zunino, R., Gastaldo, P., & Anguita, D. (2010). Using unsupervised analysis to constrain generalization bounds for support vector classifiers. Neural Networks, IEEE Transactions on, 21(3), 424-438.
Dembczyński, K., Kotłowski, W., & Słowiński, R. (2008). Ensemble of decision rules for ordinal classification with monotonicity constraints Rough Sets and Knowledge Technology (pp. 260-267): Springer.
Dong, J.-x., Krzyżak, A., & Suen, C. Y. (2003). A fast parallel optimization for training support vector machine Machine Learning and Data Mining in Pattern Recognition (pp. 96-105): Springer.
Doumpos, M., & Zopounidis, C. (2009). Monotonic support vector machines for credit risk rating. New Mathematics and Natural Computation, 5(03), 557-570.
Graf, H. P., Cosatto, E., Bottou, L., Dourdanovic, I., & Vapnik, V. (2004). Parallel support vector machines: The cascade svm. Paper presented at the Advances in neural information processing systems.
Greco, S., Matarazzo, B., & Slowinski, R. (1998). A new rough set approach to evaluation of bankruptcy risk Operational tools in the management of financial risks (pp. 121-136): Springer.
Grinblat, G. L., Uzal, L. C., & Granitto, P. M. (2013). Abrupt change detection with one-class time-adaptive support vector machines. Expert Systems with Applications, 40(18), 7242-7249.
Gruber, C., Gruber, T., Krinninger, S., & Sick, B. (2010). Online signature verification with support vector machines based on LCSS kernel functions. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 40(4), 1088-1100.
Hestenes, M. R., & Stiefel, E. (1952). Methods of conjugate gradients for solving linear systems.
Hu, Q., Che, X., Zhang, L., Zhang, D., Guo, M., & Yu, D. (2012). Rank entropy-based decision trees for monotonic classification. Knowledge and Data Engineering, IEEE Transactions on, 24(11), 2052-2064.
Huang, Z., Chen, H., Hsu, C.-J., Chen, W.-H., & Wu, S. (2004). Credit rating analysis with support vector machines and neural networks: a market comparative study. Decision support systems, 37(4), 543-558.
Kaytez, F., Taplamacioglu, M. C., Cam, E., & Hardalac, F. (2015). Forecasting electricity consumption: a comparison of regression analysis, neural networks and least squares support vector machines. International Journal of Electrical Power & Energy Systems, 67, 431-438.
Kim, H. S., & Sohn, S. Y. (2010). Support vector machines for default prediction of SMEs based on technology credit. European Journal of Operational Research, 201(3), 838-846.
Kramer, K., Hall, L. O., Goldgof, D. B., Remsen, A., & Luo, T. (2009). Fast support vector machines for continuous data. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 39(4), 989-1001.
Li, S.-T., & Chen, C.-C. (2014). A Regularized Monotonic Fuzzy Support Vector Machine Model for Data Mining with Prior Knowledge.
Maes, C. M. (2010). A regularized active-set method for sparse convex quadratic programming. Citeseer.
Menon, A. K. (2009). Large-scale support vector machines: algorithms and theory. Research Exam, University of California, San Diego, 1-17.
Mukkamala, S., Janoski, G., & Sung, A. (2002). Intrusion detection using neural networks and support vector machines. Paper presented at the Neural Networks, 2002. IJCNN'02. Proceedings of the 2002 International Joint Conference on.
Na, M. G., Park, W. S., & Lim, D. H. (2008). Detection and diagnostics of loss of coolant accidents using support vector machines. Nuclear Science, IEEE Transactions on, 55(1), 628-636.
Pazzani, M. J., Mani, S., & Shankle, W. R. (2001). Acceptance of rules generated by machine learning among medical experts. Methods of information in medicine, 40(5), 380-385.
Platt, J. C. (1999). 12 fast training of support vector machines using sequential minimal optimization. Advances in kernel methods, 185-208.
Potharst, R., & Feelders, A. J. (2002). Classification trees for problems with monotonicity constraints. ACM SIGKDD Explorations Newsletter, 4(1), 1-10.
Ravikumar, B., Thukaram, D., & Khincha, H. (2009). An approach using support vector machines for distance relay coordination in transmission system. Power Delivery, IEEE Transactions on, 24(1), 79-88.
SchiilkopP, B., Burgest, C., & Vapnik, V. (1995). Extracting support data for a given task. no. x.
Serafini, T., Zanghirati, G., & Zanni, L. (2005). Gradient projection methods for quadratic programs and applications in training support vector machines. Optimization Methods and Software, 20(2-3), 353-378.
Serafini, T., & Zanni, L. (2005). On the working set selection in gradient projection-based decomposition techniques for support vector machines. Optimization Methods and Software, 20(4-5), 583-596.
Shilton, A., Palaniswami, M., Ralph, D., & Tsoi, A. C. (2005). Incremental training of support vector machines. Neural Networks, IEEE Transactions on, 16(1), 114-131.
Shin, K.-S., Lee, T. S., & Kim, H.-j. (2005). An application of support vector machines in bankruptcy prediction model. Expert Systems with Applications, 28(1), 127-135.
Suykens, J., Lukas, L., Van Dooren, P., De Moor, B., & Vandewalle, J. (1999). Least squares support vector machine classifiers: a large scale algorithm. Paper presented at the European Conference on Circuit Theory and Design, ECCTD.
Tikhonov, A. N., & Arsenin, V. I. A. k. (1977). Solutions of ill-posed problems: Vh Winston.
Vapnik. (1995). The Nature of Statistical Learning Theory.
Vapnik. (1998). Statistical learning theory (Vol. 1): Wiley New York.
Yan, X., & Chowdhury, N. A. (2014). Mid-term electricity market clearing price forecasting utilizing hybrid support vector machine and auto-regressive moving average with external input. International Journal of Electrical Power & Energy Systems, 63, 64-70.
Yu, H.-F., Hsieh, C.-J., Chang, K.-W., & Lin, C.-J. (2012). Large linear classification when data cannot fit in memory. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(4), 23.
Zanghirati, G., & Zanni, L. (2003). A parallel solver for large quadratic programs in training support vector machines. Parallel computing, 29(4), 535-551.
Zanni, L., Serafini, T., & Zanghirati, G. (2006). Parallel software for training large scale support vector machines on multiprocessor systems. The Journal of Machine Learning Research, 7, 1467-1492.
Zhang, J.-P., Li, Z.-W., & Yang, J. (2005). A parallel SVM training algorithm on large-scale classification problems. Paper presented at the Machine Learning and Cybernetics, 2005. Proceedings of 2005 International Conference on.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2021-12-31起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw