具有同步化特征选择的迭代紧凑非平行支持向量聚类算法

doi:10.3969/j.issn.0372-2112.2020.01.006

电子学报 ›› 2020, Vol. 48 ›› Issue (1): 44-58.DOI: 10.3969/j.issn.0372-2112.2020.01.006

所属专题：机器学习—特征选择

具有同步化特征选择的迭代紧凑非平行支持向量聚类算法

方佳艳^1,2, 刘峤^1,2

1. 电子科技大学信息与软件工程学院, 四川成都 611731;
2. 中电科大数据研究院有限公司, 贵州贵阳 550022

收稿日期:2018-04-09 修回日期:2019-04-18 出版日期:2020-01-25
- 作者简介:
- 方佳艳 女,1997年出生,安徽池州人.电子科技大学信息与软件工程学院本科生,主要研究方向为机器学习、人工智能、计算复杂性理论.E-mail:fyk80@163.com
- 基金资助:
- 国家自然科学基金 (No.61772117）; "十三五"装备预研领域基金 (No.6140312010203）; 军委科技委前沿探索项目 (No.1816321TS00105301）; 四川省科技服务业示范项目 (No.2018GFW0150）; 中电集团公司第五十四研究所开放课题 (No.185686）

Iterative Tighter Nonparallel Hyperplane Support Vector Clustering with Simultaneous Feature Selection

FANG Jia-yan^1,2, LIU Qiao^1,2

1. School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China;
2. CETC Big Data Research Institute Co., Ltd., Guiyang, Guizhou 550022, China

Received:2018-04-09 Revised:2019-04-18 Online:2020-01-25 Published:2020-01-25
- Supported by:
- National Natural Science Foundation of China (No.61772117); Equipment Pre-research Field Fund during the 13th Five-year Plan (No.6140312010203); Frontier Exploration Program of Science and Technology Commission of PRC Central Military Commission (No.1816321TS00105301); Sichuan Science and Technology Service Demonstration Project (No.2018GFW0150); Open Project of The 54th Research Insititute of CETC (No.185686)

摘要/Abstract

摘要： 本文提出了一种新的带有同步化特征选择的聚类算法，称为"具有同步化特征选择的迭代紧凑非平行支持向量聚类算法"（IT-NHSVC-SFS）.在具有两个非平行超平面的学习模型中使用迭代（交替）优化算法完成聚类，同时引入两种类型的正则项，分别是欧几里得范数和无穷范数，欧几里得范数用于提升聚类模型的泛化能力，无穷范数实际上是对两个非平行超平面进行同步化地隐式特征抽取，从而降低来自于不相关特征的聚类噪音，保证了模型的聚类精度，并引入一组束缚变量（bounding variables）避免无穷范数的最大化操作，将非凸优化问题转化成二次凸优化问题.同时，由于新提出的模型体现着"最大间隔"的思想，因此具有良好的泛化能力.为了方便实现两个非平行超平面同步化的特征选择过程，文中将非平行超平面SVM（Nonparallel Hyperplane SVM，NHSVM）作为IT-NHSVC-SFS算法的基础模型，因此和TWSVM以及它的变体模型不同的是：只需要求解一个二次规划问题（QP问题）就可以同时得到两个最优超平面.同时，新算法在原有的NHSVM模型的约束条件集合中新添加了两组等式约束条件，从而无需进行原有模型中的两个大矩阵的求逆操作，降低了计算复杂度.此外，在IT-NHSVC-SFS模型中，用拉普拉斯损失函数（Laplacian loss measure）代替了NHSVM模型原有的铰链损失函数（hinge loss function），避免了算法早熟收敛（premature convergence）.在一组标准数据集上的数值实验结果表明，相对于其他已有的聚类算法，IT-NHSVC-SFS算法在聚类精度方面具有更好的表现.

关键词: 聚类, 特征选择, 非平行超平面支持向量机, 无穷范数

Abstract: In this paper, a new clustering algorithm with simultaneous feature selection is proposed, which is called iterative tighter nonparallel support vector clustering with simultaneous feature selection (IT-NHSVC-SFS). In learning with two nonparallel hyperplanes model,we use the iterative (alternating) optimization algorithm to achieve clustering, and at the same time introduce two types of regularizes,the Euclidean norm and the infinite norm, respectively. Euclidean norm clustering model is used to improve the generalization ability and the infinite norm actually fulfills implicit feature extraction for the two nonparallel hyperplanes in order to reduce data noises from irrelevant features, and the clustering precision of the model is guaranteed. We also introduce a set of bounding variables to avoid maximization operation of the infinite norm, converting the non-convex optimization problem into a quadratic convex optimization problem. Meanwhile, because the new model embodies the idea of "maximum margin", it has good generalization ability. IT-NHSVC-SFS chooses nonparallel hyperplanes SVM (NHSVM) as the basis of the algorithm model. Unlike TWSVM and its variant models, only a quadratic programming problem (QP problem) needs to be solved to get the two optimal hyperplane simultaneously. This property is helpful to design a synchronous feature selection process for two nonparallel hyperplanes. The new algorithm adds two sets of equality constraints in the constraint set of the original NHSVM model, which can avoid the inverse operation of two large matrices and reduce the computational complexity. In addition, in the IT-NHSVC-SFS model, the Laplacian loss function replaces the original hinge loss function in NHSVM to avoid premature convergence. Numerical experiments on a set of benchmark data sets show that IT-NHSVC-SFS algorithm performs better in terms of clustering accuracy than other existing clustering algorithms.

Key words: clustering, feature selection, nonparallel hyperplane support vector machine, L-infinite norm

中图分类号:

TP181

方佳艳, 刘峤. 具有同步化特征选择的迭代紧凑非平行支持向量聚类算法[J]. 电子学报, 2020, 48(1): 44-58.

FANG Jia-yan, LIU Qiao . Iterative Tighter Nonparallel Hyperplane Support Vector Clustering with Simultaneous Feature Selection[J]. Acta Electronica Sinica, 2020, 48(1): 44-58.

参考文献

[1] 杭文龙,蒋亦樟,刘解放,等.迁移近邻传播聚类算法[J].软件学报,2016,27(11):2796-2813. HANG Wen-long,JIANG Yi-zhang,LIU Jie-fang,et al.Transfer affinity propagation clustering algorithm[J].Journal of Software,2016,27(11):2796-2813.(in Chinese)
[2] 王岩,彭涛,韩佳育,等.一种基于密度的分布式聚类方法[J].软件学报,2017,28(11):2836-2850. WANG Yan,PENG Tao,HAN Jian-yu,et al.Density-based distributed clustering method[J].Journal of Software,2017,28(11):2836-2850.(in Chinese)
[3] 王卫卫,李小平,冯象初,等.稀疏子空间聚类综述[J].自动化学报,2015,41(8):1373-1384. WANG Wei-wei,LI Xiao-ping,FENG Xiang-chu,et al.A survey on sparse subspace clustering[J].Acta Automatica Sinica,2015,41(8):1373-1384.(in Chinese)
[4] 李向丽,曹晓锋,邱保志.基于矩阵模型的高维聚类边界模式发现[J].自动化学报,2017(11):1962-1972. LI Xiang-li,CAO Xiao-feng,QIU Bao-zhi.Clustering boundary pattern discovery for high dimensional space based on matrix model[J].Acta Automatica Sinica,2017,43(11):1962-1972.(in Chinese)
[5] HARTIGAN J A,WONG M A.A K-means clustering algorithm[J].Applied Statistics,1979,28(1):100-108.
[6] SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2000,22(8):888-905.
[7] REDNER R A,WALKER H F.Mixture densities,maximum likelihood and the EM algorithm[J].Siam Review,1984,26(2):195-239.
[8] NG A Y,JORDAN M I,WEISS Y.On spectral clustering:analysis and an algorithm[A].International Conference on Neural Information Processing Systems:Natural and Synthetic[C].US:MIT Press,2001.849-856.
[9] WANG Y X,XU H.Noisy sparse subspace clustering[A].International Conference on Machine Learning[C].US:JMLR,2013.I-89.
[10] HERSHEY J R,CHEN Z,ROUX J L,et al.Deep clustering:Discriminative embeddings for segmentation and separation[A].IEEE International Conference on Acoustics,Speech and Signal Processing[C].US:IEEE,2016.31-35.
[11] ZHANG X,ZHANG X,LIU H.Self-adapted multi-task clustering[A].International Joint Conference on Artificial Intelligence[C].US:AAAI Press,2016.2357-2363.
[12] ZHANG L,ZHANG Q,DU B,et al.Adaptive manifold regularized matrix factorization for data clustering[A].Twenty-Sixth International Joint Conference on Artificial Intelligence[C].Berlin:Springer,2017.3399-3405.
[13] VAPNIK V N.Statistical learning theory[J].Encyclopedia of the Sciences of Learning,2008,41(4):3185-3185.
[14] 田中大,张超,李树江,等.基于相空间重构与最小二乘支持向量机的时延预测[J].电子学报,2017,45(5):1044-1051. TIAN Zhong-da,ZHANG Chao,LI Shu-jiang,et al.Time-delay prediction based on phase space reconstruction and least squares support vector machine[J].Acta Electronica Sinica,2017,45(5):1044-1051.(in Chinese)
[15] 陈素根,吴小俊.改进的投影孪生支持向量机[J].电子学报,2017,45(2):408-416. CHEN Su-gen,WU Xiao-jun.Improved projection twin support vector machine[J].Acta Electronica Sinica,2017,45(2):408-416.(in Chinese)
[16] 高雷阜,赵世杰,于冬梅,等.耦合负类样本裁剪与非对称错分惩罚的非均衡SVM算法[J].电子学报,2017,45(12):2978-2986. GAO Lei-fu,ZHAO Shi-jie,YU Dong-mei,et al.Unbalanced support vector machine coupling negative-samples cutting with asymmetric misclassification cost[J].Acta Electronica Sinica,2017,45(12):2978-2986.(in Chinese)
[17] 白海钏,鲍长春,刘鑫.基于局部最小二乘支持向量机的音频频带扩展方法[J].电子学报,2016,44(9):2203-2210. BAI Hai-chuan,BAO Chang-chun,LIU Xin.Audio bandwidth extension method based on local least square support vector machine[J].Acta Electronica Sinica,2016,44(9):2203-2210.(in Chinese)
[18] 储茂祥,王安娜,巩荣芬.一种改进的最小二乘孪生支持向量机分类算法[J].电子学报,2014,42(5):998-1003. CHU Mao-xiang,WANG An-na,GONG Rong-fen.Improvement on least squares twin support vector machine for pattern classification[J].Acta Electronica Sinica,2014,42(5):998-1003.(in Chinese)
[19] XU L,NEUFELD J,LARSON B,et al.Maximum margin clustering[J].Advances in Neural Information Processing Systems,2004,17:1537-1544.
[20] JAYADEVA,KHEMCHANDANI R,CHANDRA S.Twin support vector machines for pattern classification[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2007,29(5):905-910.
[21] WANG Z,SHAO Y H,BAI L,et al.Twin support vector machine for clustering[J].IEEE Transactions on Neural Networks and Learning Systems,2015,26(10):2583-2588.
[22] KHEMCHANDANI R,PAL A,CHANDRA S.Fuzzy least squares twin support vector clustering[J].Neural Computing & Applications,2016,29(2):1-11.
[23] CHANDRASHEKAR G,SAHIN F.A Survey on Feature Selection Methods[M].US:Pergamon Press,Inc.2014.
[24] GUYON I.An Introduction to Variable and Feature Selection[M].US:JMLR,2003.
[25] MALDONADO S,WEBER R.A wrapper method for feature selection using support vector machines[J].Information Sciences,2009,179(13):2208-2217.
[26] HSU HH,HSIEH C W,LU M D.Hybrid feature selection by combining filters and wrappers[J].Expert Systems with Applications,2011,38(7):8144-8150.
[27] SEBBAN M,NOCK R.A hybrid filter/wrapper approach of feature selection using information theory[J].Pattern Recognition,2002,35(4):835-846.
[28] YANG C H,CHUANG L Y,YANG C H.IG-GA:A hybrid filter/wrapper method for feature selection of microarray data[J].Journal of Medical & Biological Engineering,2010,30(1):23-28.
[29] YANG Y,ZOU H.A fast unified algorithm for solving group-Lasso penalize learning problems[J].Statistics & Computing,2015,25(6):1129-1141.
[30] Moreno-VegaJ M.High-dimensional feature selection via feature grouping[J].Information Sciences an International Journal,2016,326(C):102-118.
[31] SHAO Y H,CHEN W J,DENG N Y.Nonparallel hyperplane support vector machine for binary classification problems[J].Information Sciences,2014,263(3):22-35.
[32] BRADLEY P S,MANGASARIAN O L.k-Plane clustering[J].Journal of Global Optimization,2000,16(1):23-32.
[33] YUILLE A L,RANGARAJAN A.The concave-convex procedure[J].Neural Computation,2003,15(4):915-936.
[34] CHEUNG P M,KWOK J T.A regularization framework for multiple-instance learning[A].International Conference on Machine Learning[C].US:DBLP,2006.193-200.
[35] CORTES C,VAPNIK V.Support-vector networks[J].Machine Learning,1995,20(3):273-297.
[36] DENG N,TIAN Y,ZHANG C.Support Vector Machines:Optimization Based Theory,Algorithms,and Extensions[M].US:Chapman & Hall/CRC,2012.
[37] SHAO Y H,ZHANG C H,WANG X B,et al.Improvements on twin support vector machines[J].IEEE Transactions on Neural Networks,2011,22(6):962-968.
[38] MANGASARIAN O L,MUSICANT D R.Successive overrelaxation for support vector machines[J].IEEE Transactions on Neural Networks,1999,10(5):1032-1037.
[39] BAI L,WANG Z,SHAO Y H,et al.A novel feature selection method for twin support vector machine[J].Knowledge-Based Systems,2014,59(2):1-8.
[40] DUDA R O,HART P E,STORK D G.Pattern Classification[M].US:Wiley,2001.
[41] GUYON I,WESTON J,BARNHILL S,et al.Gene selection for cancer classification using support vector machines[J].Machine Learning,2002,46(1-3):389-422.
[42] BRADLEY P S,MANGASARIAN O L.Feature selection via concave minimization and support vector machines[A].Fifteenth International Conference on Machine Learning[C].US:Morgan Kaufmann Publishers Inc,1998.82-90.
[43] YUAN M,LIN Y.Model selection and estimation in regression with grouped variables[J].Journal of the Royal Statistical Society,2006,68(1):49-67.
[44] CHEVILLARD S,LAUTER C.A certified infinite norm for the implementation of elementary functions[A].International Conference on Quality Software[C].US:IEEE,2007.153-160.
[45] ZHANG K,TSANG I W,KWOK J T.Maximum margin clustering made practical[J].IEEE Transactions on Neural Networks,2009,20(4):583-596.
[46] SCHÖLKOPF,BERNHARD,SMOLA A J.Learning with kernels[J].IEEE Transactions on Signal Processing,2002,52(8):2165-2176.
[47] BENNETT K P,BREDENSTEINER E J.Duality and geometry in SVM classifiers[A].Seventeenth International Conference on Machine Learning[C].US:Morgan Kaufmann Publishers Inc,2000.57-64.
[48] MALDONADO S,LÓPEZ J.Synchronized feature selection for support vector machines with twin hyperplanes[J].Knowledge-Based Systems,2017,132:119-128.
[49] BACHE K,LICHMAN M.UCI Machine Learning Repository[OL].http://archive.ics.uci.edu/ml/index.php,2013.
[50] GRAVIER E,PIERRON G,VINCENTSALOMON A,et al.A prognostic DNA signature for T1T2 node-negative breast cancer patients[J].Genes Chromosomes & Cancer,2010,49(12):1125-1134.
[51] ALON U,BARKAI N,NOTTERMAN D A,et al.Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays[J].Proceedings of the National Academy of Sciences of the United States of America,1999,96(12):6745.
[52] DAVIES A J,ROSENWALD A,WRIGHT G,et al.Transformation of follicular lymphoma to diffuse large B-cell lymphoma proceeds by distinct oncogenic mechanisms[J].British Journal of Hematology,2007,136(2):286.
[53] WEST M,BLANCHETTE C,DRESSMAN H,et al.Predicting the clinical status of human breast cancer by using gene expression profiles[J].Proceedings of the National Academy of Sciences of the United States of America,2001,98(20):11462-11467.
[54] POMEROY S L,TAMAYO P,GAASENBEEK M,et al.Prediction of central nervous system embryonal tumour outcome based on gene expression[J].Nature,2002,415(6870):436.
[55] SHIPP M A,ROSS K N,TAMAYO P,et al.Diffuse large B-cell lymphoma outcome prediction by gene-expression profiling and supervised machine learning[J].Nature Medicine,2002,8(1):68-74.
[56] YANG Z M,HE J Y,SHAO Y H.Feature selection based on linear twin support vector machines[J].Procedia Computer Science,2013,17:1039-1046.
[57] PEARSON K.Note on regression and inheritance in the case of two parents[J].Proceedings of the Royal Society of London,2006,58:240-242.
[58] NEUMANN J,SCHNÖRR C,STEIDL G.Combined SVM-based feature selection and classification[J].Machine Learning,2005,61(1-3):129-150.
[59] RAKOTOMAMONJY A.Variable selection using SVM based criteria[J].Journal of Machine Learning Research,2003,3(7-8):1357-1370.
[60] SCHÖLKOPF B,PLATT J,HOFMANN T.Generalized maximum margin clustering and unsupervised kernel learning[A].International Conference on Neural Information Processing Systems[C].US:MIT Press,2006.1417-1424.
[61] DJURIC N,LAN L,VUCETIC S,et al.Budgeted SVM:A toolbox for scalable SVM approximations[J].Journal of Machine Learning Research,2013,14(1):3813-3817.
[62] ÑANCULEF R,FRANDI E,SARTORI C,et al.A novel frank-wolfe algorithm analysis and applications to large-scale SVM training[J].Information Sciences,2014,285(C):66-99.

具有同步化特征选择的迭代紧凑非平行支持向量聚类算法

Iterative Tighter Nonparallel Hyperplane Support Vector Clustering with Simultaneous Feature Selection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张少波, 原刘杰, 毛新军, 朱更明. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报, 2022, 50(9): 2181-2188.
[2]	王波, 王悦, 王伟, 侯嘉尧. 开放环境下自适应聚类优化包络的相机来源取证[J]. 电子学报, 2022, 50(8): 1840-1850.
[3]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[4]	江兵兵, 何文达, 吴兴宇, 项俊浩, 洪立斌, 盛伟国. 基于自适应图学习的半监督特征选择[J]. 电子学报, 2022, 50(7): 1643-1652.
[5]	汪禹宏, 张屹. 基于适应度指导交配限制策略的重组算子与多目标优化研究[J]. 电子学报, 2022, 50(3): 710-717.
[6]	李凯, 张可心. 结构α-熵的加权高斯混合模型的子空间聚类[J]. 电子学报, 2022, 50(3): 718-725.
[7]	肖进胜, 张舒豪, 陈云华, 王元方, 杨力衡. 双向特征融合与特征选择的遥感影像目标检测[J]. 电子学报, 2022, 50(2): 267-272.
[8]	路皓翔, 刘振丙, 张静, 王子民. 结合多尺度循环卷积和多聚类空间的红外图像增强[J]. 电子学报, 2022, 50(2): 415-425.
[9]	赵嘉, 王刚, 吕莉, 樊棠怀. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730-2737.
[10]	刘浩阳, 林耀进, 刘景华, 吴镒潾, 毛煜, 李绍滋. 由粗到细的分层特征选择[J]. 电子学报, 2022, 50(11): 2778-2789.
[11]	高雷阜, 张梦瑶, 赵世杰. 融合簇边界移动与自适应合成的混合采样算法[J]. 电子学报, 2022, 50(10): 2517-2529.
[12]	江巨浪, 刘国明, 朱柱, 黄忠, 郑江云. 基于快速模糊聚类的动态多直方图均衡化算法[J]. 电子学报, 2022, 50(1): 167-176.
[13]	孟海宁, 冯锴, 朱磊, 张贝贝, 童新宇, 黑新宏. 基于Laplacian图谱的短文本聚类算法[J]. 电子学报, 2021, 49(9): 1716-1723.
[14]	张屹, 陆逸舟, 王帅, 陆曈曈. 基于多源交配选择策略的重组算子与多目标优化研究[J]. 电子学报, 2021, 49(9): 1754-1760.
[15]	李鹏, 闵慧, 罗爱静. 基于动态图的PPI网络构建和复合物挖掘算法研究[J]. 电子学报, 2021, 49(8): 1489-1497.