基于多粒度数据压缩的支持向量机

PDF(881180 KB)

南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (5) : 637-643.

基于多粒度数据压缩的支持向量机

包文颖1，胡清华2，王长忠1**

作者信息 +

Support vector machine based on multi-granulations

Bao Wen-Ying1, Hu Qing-Hua2, Wang Chang-Zhong1

Author information +

文章历史 +

摘要

support vector machine based on multi-granulations, MG-SVM）。首先，利用多粒度理论对数据进行粒化与压缩；然后，对压缩后的数据利用支持向量机寻找最优超平面并进行分类；最后利用UCI中一些标准数据进行数据压缩与分类试验。与传统的支持向量机分类方法相比，MG-SVM算法在保持或提高经典支持向量机的分类和泛化能力的同时，有效地降低了时间复杂度。

Abstract

In reality we are always faced with a large number of large-scale data. Multi-granulations theory is a good tool to deal with it. Support vector machine (SVM) is a powerful instrument for solving classification problems, but it is not suitable for large-scale data. It comes into being a new idea By compromising the merits of multi-granulations theory and SVM. In this work, by introducing multi-granulations theory into SVM, a new algorithm, called support vector machine based on multi-granulations (MG-SVM), is proposed to deal with classification of large-scale data. First, multi-granulations theory is employed to granulate data and compress data granules. Then, remove the consistent information granule to compress the data. At the last, the compressed data is used to train support vectors to find the optimal hyperplane. The experiments on some benchmark datasets show that MG-SVM algorithm not only make computational complexities decreased, but also make classification power of traditional SVM invariant.

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用

包文颖1，胡清华2，王长忠1**. 基于多粒度数据压缩的支持向量机[J]. 南京大学学报(自然科学版), 2013, 49(5): 637-643

Bao Wen-Ying1, Hu Qing-Hua2, Wang Chang-Zhong1. Support vector machine based on multi-granulations[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(5): 637-643

参考文献

[1] Corts C, Vapnik V N. Support vector networks. Machine Learning, 1995, 20: 273~297.

[2] Burges C. A turtorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1998, 2(2): 121~167.

[3] Cortes C, Vapnik V N. Support vector networks. Machine Learning, 1995, 20: 273~297.

[4] Vapnik V N. The nature of statistical learning theory. New York: Springer-Verlag, 1995, 314.

[5] Scholkopf B, Burges C, Smola A. Advances in kernel methods: Support vector learning. Cambridge, MA: MIT Press, 1999, 314.

[6] Wang L P, Fu X. Data mining with computational intelligence. Berlin: Springer, 2005, 356.

[7] Wang L P. Support vector machines: Theory and applications. Berlin: Springer, 2005, 431.

[8] Bai J W, Wang W J, Guo H S. A novel support vector machine active learning strategy. Journal of Nanjing University (Natural Sciences), 2012, 48(2): 182~189.( 白龙飞 , 王文剑 , 郭虎升 . 一种新的支持向量机主动学习策略 . 南京大学学报 ( 自然科学 ),2012,48(2):182~189)

[9] Burges C J C. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1998, 2: 121~167.

[10] Osuna E, Frenud R, Girosi F. An improved training algorithm for support vector machines. Proceedings of IEEE Workshop on Neural Networks for Signal Processing. New York, USA, 1997: 276~285.

[11] Tang Y C, Jin B, Zhang Y Q. Granular support vector machines for medical binary classification problems. Fogl G B. Proceedings of the IEEE CIBIB. Piscataway, IEEE Computational Intelligence Society, 2004: 73~78.

[12] Cortes C, Vapnik V. Support vector networks. Machine Learning, 1995, 20: 273~297.

[13] Shin H, Cho S. Fast pattern selection for support vector classifiers. Lecture Notes in Artificial Intelligence, 2003, 2637: 376~387.

[14] Shin H, Cho S. Invariance of neighborhood relation under input space to feature space mapping. Pattern Recognition Letters, 2005, 26: 707~718.

[15] Boser B, Guyon I, Vapnik V. A training algorithm for optimal margin classifiers. Proceedings of the 5^th Annual ACM Work shop on Computational Learning Theory. New York: ACM Press, 1992: 144~152.

[16] Lee Y J, Mangasarian L. RSVM: Reduced support vector machines. Proceedings of the 1^st SIAM International Conference on Data Mining, 2001:5~7.

[17] Zheng S, Lu X, Zheng N, et al. Unsupervised clustering based reduced support vector machines. Proceedings of the IEEE Conference on Acoustics, Speech, and Signal Processing, 2003: 821~824.

[18] Hu Q H, Yu D R, Xie Z X. Selecting samples and features for SVM based on neighborhood model. The 11^th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing. Toronto, 2007:508~517.

[19] Shin H, Cho S. Fast pattern selection for support vector classifiers. Lecture Notes in Artificial Intelligence, 2003, 2637: 376~387.

[20] Hu Q H, Yu D R, Liu J F, et al. Neighborhood rough set based heterogeneous feature subset selection. Information Sciences, 2008, 178: 3577~3594.