CCH-Based Geometric Algorithms for SVM and the Applications

PENG Xin-jun; WANG Yi-fei

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2009 > 30(1): 90-100

PENG Xin-jun, WANG Yi-fei. CCH-Based Geometric Algorithms for SVM and the Applications[J]. Applied Mathematics and Mechanics, 2009, 30(1): 90-100.

Citation:

PENG Xin-jun, WANG Yi-fei. CCH-Based Geometric Algorithms for SVM and the Applications[J]. Applied Mathematics and Mechanics, 2009, 30(1): 90-100.

Citation:

PENG Xin-jun, WANG Yi-fei. CCH-Based Geometric Algorithms for SVM and the Applications[J]. Applied Mathematics and Mechanics, 2009, 30(1): 90-100.

PDF( 459 KB)

CCH-Based Geometric Algorithms for SVM and the Applications

PENG Xin-jun^1,2,
WANG Yi-fei³

1.
Department of Mathematics, Shanghai Normal University, Shanghai 200234, P. R. China;

Received Date: 2008-08-26
Rev Recd Date: 2008-11-17
Publish Date: 2009-01-15

Abstract

Abstract

The support vector machine (SVM) is a novel machine learning tool in data mining. The geometric approach based on the compressed convex hull (CCH) with a mathematical framework is introduced to solve SVM classification problems. Compared with the reduced convex hull (RCH), CCH preserves the shape of geometric solid for the data set; meanwhile, it is easy to give the necessary and sufficient condition of determining its extreme points. As the practical applications of CCH, spare and probabilistic speed-up geometric algorithms were developed. Results of some numerical experiments show that the proposed algorithms can reduce the kernel evaluation and display nice performances.
- support vector machine,
- compressed convex hull,
- kernel parameter,
- geometric approach,
- probabilistic speed-up

FullText(HTML)

References(26)

References

[1]	Vapnik V.The Natural of Statistical Learning Theory[M].New York:Springer,1995.
[2]	Vapnik V.Statistical Learning Theory[M].New York:Wiley,1998.
[3]	Christianini V,Shawe-Taylor J.An Introduction to Support Vector Machines[M].Cambridge:Cambridge University Press,2002.
[4]	Ripley B D.Pattern Recognition and Neural Networks[M].Cambridge:Cambridge University Press,1996.
[5]	El-Naqa I,Yang Y,Wernik M,et al.A support vector machine approach for detection of microclassification[J].IEEE Trans Med Imag,2002,21(12):1552-1563. doi: 10.1109/TMI.2002.806569
[6]	Joachims T.Text categorization with support vector machines:Learning with many relevant features[A].In:European Conference on Machine Learning No.10[C].1398.Chemnitz,Germany:Springer-Verlag,1998,137-142.
[7]	Osuna E,Freund R,Girosi F.Training support vector machines:an application to face detection[A].In:Proceedings of the 1997 Conference Computer Vision and Pattern Recognition[C].Washinton D C:IEEE Computer Society,1997,130-136.
[8]	Brown M P S,Grundy W N,Lin D,et al.Knowledge-based analysis of microarray gene expression data by using support vector machine[J].Proc Nat Acad Sci USA,2000,97(1):262-267. doi: 10.1073/pnas.97.1.262
[9]	Mukherjee S,Osuna E,Girosi F.Nonliner prediction of chaotic time series using a support vector machine[A].In:Proceedings of the 1997 IEEE Workshop[C].Amelia Island,FL,1997,511-520.
[10]	Jeng J T,Chuang C C,Su S F.Support vector interval regression networks for interval regression analysis[J].Fuzzy Sets and Systems,2003,138(2):283-300. doi: 10.1016/S0165-0114(02)00570-5
[11]	Zhou D,Xiao B,Zhou H,et al.Global geometric of SVM classifiers[R]. Institute of automation,Chinese Academy of Sciences. Tech Rep AI Lab,2002.
[12]	Platt J.Fast training of support vector machines using sequential minimal optimization[A].In:Advances in Kernel Method-Support Vector Learning[C].Cambridge,MA:MIT Press,1999,185-208.
[13]	Bennett K P,Bredensteiner E J.Geometry in learning[A].In:Geometry at Work[C].Washington,DC:Mathematical Association of America,1998,132-145.
[14]	Keerthi S S,Shevade S K,Bhattacharyya C,et al.A fast iterative nearest point algorithm for support vector machine classifier design[J].IEEE Trans Neural Netw,2000,11(1):124-136. doi: 10.1109/72.822516
[15]	Mavroforakis M E,Theodoridis S.A geometric approach to support vector machine (SVM) classification[J].IEEE Trans Neural Netw,2007,17(3):671-682.
[16]	Frigui H,Krishnapuram R.A robust competitives clustering algorithm with applications in computer vision[J].IEEE Trans Pattern Anal Mach Intell,1999,21(5):450-465. doi: 10.1109/34.765656
[17]	Bennett K P,Bredensteiner E J.Duality and Geometry in SVM Classifiers[A].In:Proceedings of the Seventeenth International Conference on Machine Learning[C].San Mateo,CA:Morgan Kaufmann Publishers Inc,2000,57-64.
[18]	Crisp D J,Burges C J C.A geometric interpretation of ν-SVM classifiers[A].In:Advances in Neural Information Processing Systems[C].Cambridge,MA:MIT Press,1999,244-250.
[19]	Franc V,Hlavac V.An iterative algorithm learning the maximal margin classifier[J].Pattern Recognition,2003,36(9):1985-1996. doi: 10.1016/S0031-3203(03)00060-8
[20]	Chapelle O,Vapnik V,Bousquet O,et al.Choosing multiple parameters for support vector machines[J].Mach Learn,2002,46(1):131-159. doi: 10.1023/A:1012450327387
[21]	Ayat N E,Cheriet M,Suen C Y.Automatic model selection for the optimization of the SVM kernels[J].Pattern Recogn Comput Sci,2005,38(10):1733-1745.
[22]	Adankon M M,Cheriet M.Optimizing resources in model selection for support vector machine[J].Pattern Recognition,2007,40(3):953-963. doi: 10.1016/j.patcog.2006.06.012
[23]	Schittkowshi K.Optimal parameter selection in support vector machine[J].J Indust Manag Optimi,2005,1(4):465-476. doi: 10.3934/jimo.2005.1.465
[24]	Chung K M,Kao W C,Wang L L,et al.Radius margin bounds for support vector machines with the RBF kernel[J].Neural Comput,2003,38(10):2643-2681.
[25]	Jones S,Thornton J M.Principles of protein-protein interactions[J].Proc Nat Acad Sci USA,1996,93(1):13-20. doi: 10.1073/pnas.93.1.13
[26]	Glaser F.ConSurf:identification of functional regions in proteins by surface-mapping of phylogenetic information[J].Bioinformatics,2003,19(1):163-164. doi: 10.1093/bioinformatics/19.1.163