臺灣博碩士論文加值系統

在很多領域裡，屬性選擇 (feature selection) 是一件很重要的事。做屬性選擇有很多好處，例如增快執行速度、提高測試的準確度等等。本論文探討利用支向機 (Support Vector Machine) 在不同的屬性選擇策略下分類的效果。論文的前半部分主要在討論目前已有的屬性選擇方法，以及利用這些方法來參與比賽所得的經驗。後半部份則對更多的方法作深入的研究。

Feature selection is an important issue in many research areas. There are some reasons for selecting important features such as reducing the learning time, improving
the accuracy, etc. This thesis investigates the performance of combining support vector machines (SVM) and various feature selection strategies. The first part of the
thesis mainly describes the existing feature selection methods and our experience on using those methods to attend a competition. The second part studies more feature selection strategies using the SVM.

CHAPTER
I. Introduction 1
II. Basic Concepts of SVM 4
2.1 Linear Separating Hyperplane with Maximal Margin 4
2.2 Mapping Data to Higher Dimensional Spaces 6
2.3 The Dual Problem 9
2.4 Kernel and Decision Functions 10
2.5 Multi-class SVM 13
2.5.1 One-against-all Multi-class SVM 13
2.5.2 One-against-one Multi-class SVM 14
2.6 Parameter Selection 15
III. Existing Feature Selection Methods 17
3.1 Feature Ranking 17
3.1.1 Statistical Score 17
3.1.2 Random Shuffle on Features 20
3.1.3 Separating Hyperplane in SVM 21
3.2 Feature Selection 22
3.2.1 Forward/Backward Selection 22
3.2.2 Feature Ranking and Feature Number Estimation 23
3.3 Feature Scaling 25
3.3.1 Radius-Margin Bound SVM 25
3.3.2 Bayesian SVM 27
IV. Experience on NIPS Competition 29
4.1 Introduction of the Competition 29
4.2 Performance Measures 30
4.2.1 Balanced Error Rate (BER) 30
4.2.2 Area Under Curve (AUC) 31
4.2.3 Fraction of Features 31
4.2.4 Fraction of Probes 31
4.3 Data Sets Information 32
4.3.1 Source of Data Sets 32
4.4 Strategies in Competition 33
4.4.1 No Selection: Direct Use of SVM 33
4.4.2 F-score for Feature Selection: F-score + SVM 33
4.4.3 F-score and Random Forest for Feature Selection: F-score + RF + SVM 35
4.4.4 Random Forest and RM-bound SVM for Feature Selection 36
4.5 Experimental Results 36
4.6 Competition Results 38
4.7 Discussion and Conclusions from the Competition 38
V. Other Feature Ranking Methods by SVM 42
5.1 Normal Vector of the Decision Boundary in Nonlinear SVM 42
5.2 Change of Decision Value in Nonlinear SVM 43
5.2.1 Instances from Underlying Distribution 44
5.2.2 Instances from Decision Boundary 48
5.3 Random Shuffle on Features using Probability SVM 49
5.3.1 SVM with Probability Output 49
5.3.2 Random Shuffle on Validation Data Features 50
VI. Experiments 52
6.1 Experiment Procedures 52
6.1.1 Feature Selection by Ranking 52
6.1.2 Feature Scaling using RM-bound SVM 54
6.2 Data Sets 54
6.3 Experimental Results 56
6.4 Analysis 57
VII. Discussion and Conclusions 65
BIBLIOGRAPHY 67

[1] R. R. Bailey, E. J. Pettit, R. T. Borochoff, M. T. Manry, and X. Jiang. Automatic recognition of usgs land use/cover categories using statistical and neural networks classifiers. In SPIE OE/Aerospace and Remote Sensing, Bellingham, WA, 1993. SPIE.
[2] C. L. Blake and C. J. Merz. UCI repository of machine learning databases. Technical report, University of California, Department of Information and Computer Science, Irvine, CA, 1998. Available at http://www.ics.uci.edu/~mlearn/MLRepository.html.
[3] B. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 144-152. ACM Press, 1992.
[4] L. Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
[5] C.-C. Chang and C.-J. Lin. IJCNN 2001 challenge: Generalization ability and text decoding. In Proceedings of IJCNN. IEEE, 2001.
[6] C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
[7] O. Chapelle, V. Vapnik, O. Bousquet, and S. Mukherjee. Choosing multiple parameters for support vector machines. Machine Learning, 46:131-159, 2002.
[8] Y.-W. Chen and C.-J. Lin. Combining svms with various feature selection strategies. In I. Guyon, S. Gunn, M. Nikravesh, and L. Zadeh, editors, Feature extraction, foundations and Applications. Springer, 2004.
[9] W. Chu, S. Keerthi, and C. Ong. Bayesian trigonometric support vector classifier. Neural Computation, 15(9):2227-2254, 2003.
[10] K.-M. Chung, W.-C. Kao, C.-L. Sun, L.-L. Wang, and C.-J. Lin. Radius margin bounds for support vector machines with the RBF kernel. Neural Computation, 15:2643-2681, 2003.
[11] R. Collobert, S. Bengio, and Y. Bengio. A parallel mixture of SVMs for very large scale problems. Neural Computation, 14(05):1105-1114, 2002.
[12] C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 20:273-297, 1995.
[13] R. A. Fisher. The use of multiple measurements in taxonomic problem. Annals of Eugenics, 7:179-188, 1936.
[14] I. Guyon and A. Elisseeff. An introduction to variable and feature selection. J. Mach. Learn. Res., 3:1157-1182, 2003.
[15] I. Guyon, J. Weston, S. Barnhill, and V. Vapnik. Gene selection for cancer classification using support vector machines. Machine Learning, 46:389-422, 2002.
[16] M. Heiler, D. Cremers, and C. Schnorr. Efficient feature subset selection for support vector machines. Technical Report 21, University of Mannheim, Germany, Department of Mathematics and Computer Science, Computer Vision, Graphics, and Pattern Recognition Group, D-68131 Mannheim, Germany, 2001.
[17] C.-W. Hsu, C.-C. Chang, and C.-J. Lin. A practical guide to support vector classification. Technical report, 2003.
[18] T. Joachims. Transductive inference for text classification using support vector machines. In Proceedings of International Conference on Machine Learning, 1999.
[19] G. H. John, R. Kohavi, and K. Pfleger. Irrelevant features and the subset selection problem. In International Conference on Machine Learning, pages 121-129, 1994. Journal version in AIJ, available at http://citeseer.nj.nec.com/13663.html.
[20] S. S. Keerthi and C.-J. Lin. Asymptotic behaviors of support vector machines with Gaussian kernel. Neural Computation, 15(7):1667-1689, 2003.
[21] R. Kohovi and G. H. John. Wrappers for feature subset selection. Artificial Intellgence, 97(1-2):273-324, 1997.
[22] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2324, November 1998. MNIST database available at http://yann.lecun.com/exdb/mnist/.
[23] A. Liaw and M. Wiener. Classification and regression by randomForest. R News, 2/3:18-22, December 2002.
[24] C.-J. Lin. A Guide to Support Vector Machines.
[25] C.-J. Lin. Formulations of support vector machines: a note from an optimization point of view. Neural Computation, 13(2):307-317, 2001. 69
[26] H.-T. Lin and C.-J. Lin. A study on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods. Technical report, Department of Computer Science and Information Engineering, National Taiwan University, 2003.
[27] A. K. McCallum, R. Rosenfeld, T. M. Mitchell, and A. Y. Ng. Improving text classification by shrinkage in a hierarchy of classes. In J. W. Shavlik, editor, Proceedings of ICML-98, 15th International Conference on Machine Learning, pages 359-367, Madison, US, 1998. Morgan Kaufmann Publishers, San Francisco, US.
[28] G. J. McLachlan. Discriminant Analysis and Statistical Pattern Recognition. Wiley, New York, 1992.
[29] D. Michie, D. J. Spiegelhalter, and C. C. Taylor. Machine Learning, Neural and Statistical Classification. Prentice Hall, Englewood Cliffs, N.J., 1994. Data available at http://www.ncc.up.pt/liacc/ML/statlog/datasets.html.
[30] S. Perkins, K. Lacker, and J. Theiler. Grafting: Fast, incremental feature selection by gradient descent in function space. Journal of Machine Learning Research, 3:1333-1356, 2003.
[31] J. Platt. Probabilistic outputs for support vector machines and comparison to regularized likelihood methods. In A. Smola, P. Bartlett, B. Scholkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, Cambridge, MA, 2000. MIT Press.
[32] D. Prokhorov. IJCNN 2001 neural network competition. Slide presentation in IJCNN''01, Ford Research Laboratory, 2001. http://www.geocities.com/ijcnn/nnc_ijcnn01.pdf .
[33] G. Ratsch. Benchmark data sets, 1999. Available at http://ida.first.gmd.de/~raetsch/data/benchmarks.htm.
[34] V. Svetnik, A. Liaw, C. Tong, and T. Wang. Application of Breiman''s random forest to modeling structure-activity relationships of pharmaceutical molecules. In F. Roli, J. Kittler, and T. Windeatt, editors, Proceedings of the 5th International Workshopon Multiple Classifier Systems, Lecture Notes in Computer Science vol. 3077., pages 334-343. Springer, 2004.
[35] V. Svetnik, A. Liaw, C. Tong, and T. Wang. Application of breiman''s random forest to modeling structure-activity relationships of pharmaceutical molecules. In Multiple Classifier Systems, pages 334-343, 2004.
[36] V. Vapnik. Statistical Learning Theory. Wiley, New York, NY, 1998.
[37] V. Vapnik and O. Chapelle. Bounds on error expectation for support vector machines. Neural Computation, 12(9):2013-2036, 2000.
[38] J.-Y. Wang. Application of support vector machines in bioinformatics. Master''s thesis, Department of Computer Science and Information Engineering, National Taiwan University, 2002.
[39] J. Weston, S. Mukherjee, O. Chapelle, M. Pontil, T. Poggio, and V. Vapnik. Feature selection for SVMs. In Advances in Neural Information Processing Systems, volume 12, pages 668-674, 2000.
[40] T.-F. Wu, C.-J. Lin, and R. C. Weng. Probability estimates for multi-class classification by pairwise coupling. Journal of Machine Learning Research, 5:975-1005, 2004.
[41] J. Zhu, S. Rosset, T. Hastie, and R. Tibshirani. 1-norm support vector machines. Technical report, 2003.