基于稀疏矩阵结构的特征选择算法现状研究

doi:10.3969/j.issn.1671-1122.2024.03.002

摘要/Abstract

摘要：

在信息时代，数据获取方式简单快捷，使得数据量呈指数型增长。然而这些数据往往是多源高维的，增加了模型的复杂度，容易造成模型过拟合，并且数据中存在的冗余特征会降低模型分类精度。特征选择算法旨在通过去除不相关、冗余或嘈杂的特征，从原始特征中选择一小部分最有效特征，达到降维的效果。目前特征选择算法种类繁多，其中，基于稀疏矩阵结构的特征选择算法由于具有模型简单易懂和易求解的特点而被学者们广泛关注。本文归纳总结了基于稀疏矩阵结构的特征选择算法分类，重点介绍了鲁棒特征选择模型和多视图特征选择模型。首先，介绍了基于稀疏矩阵结构的特征选择算法基本框架；然后，介绍了基于稀疏矩阵结构的一般模型、鲁棒特征选择模型、多视图的特征选择模型，比较了它们在解决目前特征选择算法研究难点中存在的优势和不足；最后，对基于稀疏矩阵结构的特征选择算法进行了总结。文章阐明了理论研究中存在的问题和难点，探讨了基于稀疏矩阵结构的特征选择算法发展思路。

关键词: 稀疏矩阵结构, 特征选择, 降维, 分类

Abstract:

In the information age, data acquisition methods are simple and fast, resulting in an exponential growth in data volume. However, these data are often multi-source and high-dimensional, which increases the complexity of the model and can easily lead to overfitting of the model, and the redundant features in the data can reduce the classification accuracy of the model. The feature selection algorithm aims to reduce dimensionality by removing irrelevant, redundant, or noisy features and selecting a small subset of the most effective features from the original ones. At present, there are various types of feature selection algorithms, among which the feature selection algorithm based on sparse matrix structure is widely studied by scholars due to its simple and easy to understand model and easy to solve characteristics. This article summarized the classification of feature selection algorithms based on sparse matrix structures, with a focus on robust feature selection models and multi view feature selection models. Firstly, the basic framework of feature selection algorithm based on sparse matrix structure was introduced; Secondly, the general model based on sparse matrix structure, robust feature selection model, and multi view feature selection model were introduced respectively, and their advantages and disadvantages in solving the current research difficulties of feature selection algorithms were compared. Finally, a summary of feature selection algorithms based on sparse matrix structures was provided. The article elucidates the problems and difficulties in theoretical research, exploring the development ideas of feature selection algorithms based on sparse matrix structures.

Key words: sparse matrix structure, feature selection, dimensionality reduction, classification

中图分类号:

TP309

钟静, 方冰, 朱江. 基于稀疏矩阵结构的特征选择算法现状研究[J]. 信息网络安全, 2024, 24(3): 352-362.

ZHONG Jing, FANG Bing, ZHU Jiang. Recent Research of Feature Selection Algorithms Based on Sparse Matrix Structure[J]. Netinfo Security, 2024, 24(3): 352-362.

图/表 9

图1

图2

表1

表2

表3

表4

表5

图3

图4

参考文献 62

[1]	LIU Xinwang. Research on the Basic Theory and Methods of Multi View Learning[J]. Basic Science in China, 2022, 24(3): 27-34.
	刘新旺. 多视图学习的基础理论和方法研究[J]. 中国基础科学, 2022, 24(3): 27-34.
[2]	YANG Yi, ZOU Yunjin. Coming of a Big Data Age? Introducing a Latest Dimension Reduction Technique for Public Management: Data Visualization[J]. Chinese Administrative Management, 2022, 1: 105-113.
	杨一, 邹昀瑾. 以机器学习应对信息“爆炸”时代:公共管理研究的降维可视化探析[J]. 中国行政管理, 2022, 1:105-113.
[3]	ZHU Pengfei, XU Qian, HU Qinghua, et al. Co-Regularized Unsupervised Ueature Selection[J]. Neurocomputing, 2018, 275: 2855-2863. doi: 10.1016/j.neucom.2017.11.061 URL
[4]	SALAU A O, JAIN S. Feature Extraction:A Survey of the Types, Techniques, Applications[C]// IEEE. 2019 International Conference on Signal Processing and Communication (ICSC). New York: IEEE, 2019: 158-164.
[5]	PETER M, MINOI J, HIPINY I. 3D Face Recognition Using Kernel-Based PCA Approach[J]. Lecture Notes in Electrical Engineering, 2019, 481: 77-86.
[6]	BERNSTEIN R, OSADCHY M, KEREN D, et al. LDA Classifier Monitoring in Distributed Streaming Systems[J]. Journal of Parallel and Distributed Computing, 2019, 123: 156-167. doi: 10.1016/j.jpdc.2018.09.017
[7]	HUANG Yuhang, SONG You, WANG Baohui. Application of Improved Forest Optimized Feature Selection Algorithm in Credit Evaluation[J]. Computer Science, 2023, 50(S1): 531-536.
	黄宇航, 宋友, 王宝会. 改进的森林优化特征选择算法在信用评估中的应用[J]. 计算机科学, 2023, 50(S1):531-536.
[8]	HUANG Xianliang. Application of Feature Selection Method in Dam Deformation Prediction: Taking Encapsulated Feature Selection Method Based on Genetic Algorithm as an Example[J]. Yangtze River Information and Communication, 2023, 36(4): 140-143.
	黄先亮. 特征选择方法在大坝变形预测中的应用研究——以基于遗传算法的封装式特征选择方法为例[J]. 长江信息通信, 2023, 36(4): 140-143.
[9]	GENG Huantong, DAI Zhongbin, SHEN Yang. Application of Feature Selection Method Based on Genetic Algorithm in Short-Term Heavy Precipitation Forecast[J]. Meteorological Science, 2023, 43(1): 126-134.
	耿焕同, 戴中斌, 沈阳. 基于遗传算法的特征选择方法在短时强降水预报中的应用[J]. 气象科学, 2023, 43(1):126-134.
[10]	LI Yonghong, WANG Ying, LI Laquan, et al. Application of an Improved Feature Selection Algorithm in E-Mail Filtering[J]. Computer Science, 2022, 49(S2): 740-744.
	李永红, 汪盈, 李腊全, 等. 一种改进的特征选择算法在邮件过滤中的应用[J]. 计算机科学, 2022, 49(S2):740-744.
[11]	PARLAK B, UYSAL A K. A Novel Filter Feature Selection Method for Text Classification: Extensive Feature Selector[J]. Journal of Information Science, 2023, 49(1): 59-78. doi: 10.1177/0165551521991037 URL
[12]	KIRA K, RENDELL L A. The Feature Selection Problem: Traditional Methods and a New Algorithm[C]// AAAI. Procceedings of the 9th National Conference on Artificial Intelligence. Menlo Park: AAAI, 1992: 129-134.
[13]	VOMMI A M, BATTULA T K. A Hybrid Filter-Wrapper Feature Selection Using Fuzzy KNN Based on Bonferroni Mean for Medical Datasets Classification: A COVID-19 Case Study[J]. Expert Systems with Applications, 2023, 218: 119612. doi: 10.1016/j.eswa.2023.119612 URL
[14]	YOUSEF M, OZDEMIR F, JABER A, et al. PriPath: Identifying Dysregulated Pathways from Differential Gene Expression via Grouping, Scoring, and Modeling with an Embedded Feature Selection Approach[J]. BMC Bioinformatics, 2023, 24(1): 1-24. doi: 10.1186/s12859-022-05124-9
[15]	ORENDER J, ZUBAIR M, SUN Jiangwen. LASSO Logic Engine: Harnessing the Logic Parsing Capabilities of the LASSO Algorithm for Longitudinal Feature Learning[C]// IEEE. 2022 IEEE International Conference on Big Data. New York: IEEE, 2022: 309-318.
[16]	WANG Lei, ZHAO Jing, ZHANG Yuxin. Ridge-Regression Echo State Network for Effluent Ammonia Nitrogen Prediction. 2022 China Automation Congress (CAC)[C]// ACM. 2022 China Automation Congress (CAC). New York: ACM, 2022: 6509-6512.
[17]	WANG Hua, NIE Feiping, HUANG Heng, et al. Sparse Multi-Task Regression and Feature Selection to Identify Brain Imaging Predictors for Memory Performance[C]// IEEE. IEEE International Conference on Computer Vision. New York: IEEE, 2011: 557-562.
[18]	HE Wei, CHENG Xiaohui, HU Rongyao, et al. Feature Self-Representation Based Bypergraph Unsupervised Feature Selection via Low-Rank Representation[J]. Neurocomputing, 2017, 253: 127-134. doi: 10.1016/j.neucom.2016.10.087 URL
[19]	WANG Shiping, WANG Han. Unsupervised Feature Selection via Low-Rank Approximation and Structure Learning[J]. Knowledge-Based Systems, 2017, 124: 70-79. doi: 10.1016/j.knosys.2017.03.002 URL
[20]	ZHANG Rui, NIE Feiping, LI Xuelong. Self-Weighted Supervised Discriminative Feature Selection[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(8): 3913-3918. doi: 10.1109/TNNLS.2017.2740341 pmid: 28910778
[21]	OBOZINSKI G, TASKAR B, JORDAN M. Multi-Task Feature Selection[D]. Berkeley: UC Berkeley, 2006.
[22]	LUO Dijun, DING C, HUANG Heng. Towards Structural Sparsity:An Explicit l2/l0 Approach[C]// IEEE. The 10th IEEE International Conferenceon Data Mining. New York: IEEE, 2010: 14-17.
[23]	TURLACH B, VENABLES W, WRIGHT S. Simultaneous Variable Selection[J]. Technometrics, 2005, 47(3): 349-363. doi: 10.1198/004017005000000139 URL
[24]	QUATTONI A, COLLINS M, DARRELL T. Transfer Learning for Image Classification with Sparse Prototype Representations[C]// IEEE. The 2008 IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE, 2008: 2300-2307.
[25]	ZHOU Yang, JIN R, HOI S. Exclusive Lasso for Multi-Task Feature Selection[J]. Journal of Machine Learning Research, 2010, 9: 988-995.
[26]	ZHENG Wei, YAN Hui, YANG Jian. Robust Unsupervised Feature Selection by Nonnegative Sparse Subspace Learning[J]. Nuerocomputing, 2019, 334: 156-171.
[27]	NIE Feiping, HUANG Heng, CAI Xiao, et al. Efficient and Robust Feature Selection via Joint L2,1 Norm Minimization[C]// ACM. The 24th Annual Conference on Neural Information Processing Systems. New York: ACM, 2010: 1813-1821.
[28]	CAI Xiao, NIE Feiping, HUANG Heng. Exact Top-K Feature Selection via L2,0 -Norm Constraint[C]// IEEE. International Joint Conference on Artificial Intelligence. New York: IEEE, 2013: 1240-1246.
[29]	WANG Xiaodong, ZHANG Xu, ZENG Zhiqiang, et al. Unsupervised Spectral Feature Selection with L1 -Norm Graph[J]. Neurocomputing, 2016, 200: 47-54. doi: 10.1016/j.neucom.2016.03.017 URL
[30]	DU Shiqiang, MA Yide. Robust Unsupervised Feature Selection via Matrix Factorization[J]. Neurocomputing, 2017, 241: 115-127. doi: 10.1016/j.neucom.2017.02.034 URL
[31]	WANG Feng, RAO Qi, ZHANG Yongquan, et al. Robust Sparse Subspace Learning for Unsupervised Feature Selection[C]// IEEE. The 2016 International Joint Conference on Neural Networks. New York: IEEE, 2016: 4205-4212.
[32]	TANG Chang, LIU Xinwang, LI Miaomiao, et al. Robust Unsupervised Feature Selection via Dual Self-Representation and Manifold Regularization[J]. Knowledge-Based Systems, 2018, 145: 109-120. doi: 10.1016/j.knosys.2018.01.009 URL
[33]	GAO Hongchang, NIE Feiping, CAI Weidong, et al. Robust Capped Norm Nonnegative Matrix Factorization[C]// ACM. The 24th ACM International Conference on Information and Knowledge Management. New York: ACM, 2015: 871-880.
[34]	LAN Gongmin, HOU Chenping, YI Dongyun. Robust Feature Selection via Simultaneous Capped l2norm and L2,1 Norm Minimization[C]// IEEE. The 2016 IEEE International Conference on Big Data Analysis. New York: IEEE, 2016: 1-5.
[35]	LAN Gongmin, HOU Chenping, NIE Feiping, et al. Robust Feature Selection via Simultaneous Sapped Norm and Sparse Regularizer Minimization[J]. Neurocomputing, 2018, 283: 228-240. doi: 10.1016/j.neucom.2017.12.055 URL
[36]	ZHONG Jing, WANG Nan, LIN Qiang, et al. Weighted Feature Selection via Discriminative Sparse Multi-View Learning[J]. Knowledge-Based Systems, 2019, 178: 132-148. doi: 10.1016/j.knosys.2019.04.024
[37]	WANG Zhi, ZHONG Jing, CHEN Yiming, et al. Sparse Robust Multiview Feature Selection via Adaptive Weighting Strategy[J]. International Journal of Machine Learning and Cybernetics, 2022: 1387-1408.
[38]	WANG Hua, NIE Feiping, HUANG Heng, et al. Identifying Disease Sensitive and Quantitative Trait-Relevant Biomarkers From Multidimensional Heterogeneous Imaging Genetics Data via Sparse Multimodal Multitask Learning[J]. Bioinformatics, 2012, 28(12): I127-I136. doi: 10.1093/bioinformatics/bts228 URL
[39]	WANG Hua, NIE Feiping, HUANG Heng, et al. Identifying Quantitative Trait Loci via Group Sparse Multitask Regression and Feature Selection: An Imaging Genetics Study of the ADNI Cohort[J]. Bioinformatics, 2012, 28(2): 229-237. doi: 10.1093/bioinformatics/btr649 URL
[40]	WANG Hua, NIEFeiping, HUANGHeng. Multi-View Clustering and Feature Learning via Structured Sparsity[C] // IEEE. The International Conference on Machine Learning. New York: IEEE, 2013: 352-360.
[41]	WANG Hua, NIE Feiping, HUANG Heng, et al. Heterogeneous Visual Features Fusion via Sparse Multimodal Machine[C]// IEEE. The Computer Vision and Pattern Recognition on IEEE. New York: IEEE, 2013: 3097-3102.
[42]	ZHANG Qian, TIAN Yuan, YANG Yiping, et al. Automatic Spatial-Spectral Feature Selection for Hyperspectral Image via Discriminative Sparse Multimodal Learning[J]. IEEE Transactions on Geoscience and Remote Sensing, 2014, 53(1): 261-279. doi: 10.1109/TGRS.2014.2321405 URL
[43]	ZHU Xiaofeng, LI Xuelong, ZHANG Shichao. Block-Row Sparse Multiview Multilabel Learning for Image Classification[J]. IEEE Transactions on Cybernetics, 2016, 46(2): 450-461. doi: 10.1109/TCYB.2015.2403356 pmid: 25730838
[44]	LI Yangxi, SHI Xin, DU Cuilan, et al. Manifold Regularized Multi-View Feature Selection for Social Image Annotation[J]. Neurocomputing, 2016, 204: 135-141. doi: 10.1016/j.neucom.2015.07.151 URL
[45]	XU Yumeng, WANG Changdong, LAI Jianhuang. Weighted Multi-View Clustering with Feature Selection[J]. Pattern Recongition, 2016, 53: 25-35.
[46]	SHI Caijuan, AN Gaoyun, ZHAO Ruizhen, et al. Multiview Hessian Semisupervised Sparse Feature Selection for Multimedia Analysis[J]. IEEE Transactiona on Circuits and Systems for Video Technology, 2017, 27(9): 1947-1961.
[47]	WANG Nan, XUE Yiming, LIN Qiang, et al. Structured Sparse Multi-View Feature Selection Based on Weighted Hinge Loss[J]. Multimedia Tools and Applications, 2019, 78(11): 15455-15481. doi: 10.1007/s11042-018-6937-x
[48]	SHI Caijuan, DUAN Changyu, GU Zhibin, et al. Semi-Supervised Feature Selection with Strctured Multi-View Sparse Regularization[J]. Neurocomputing, 2019, 330: 412-424. doi: 10.1016/j.neucom.2018.10.027
[49]	LIN Qiang, XUE Yiming, WEN Juan, et al. A Sharing Multi-View Feature Selection Method via Alternating Direction Method of Multipliers[J]. Neurocomputing, 2019, 333: 124-134. doi: 10.1016/j.neucom.2018.12.043
[50]	HUANG Shudong, REN Yazhou, XU Zenglin. Robust Multi-View Data Clustering with Multi-View Capped-Norm K-Means[J]. Neurocomputing, 2018, 311: 197-208. doi: 10.1016/j.neucom.2018.05.072 URL
[51]	LIN Qiang. Supervised Multi-View Feature Selection Via Maximum Margin Criterion Joint Distributed Optimization[C]// IEEE. 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems (CCIS). New York: IEEE, 2022: 138-142.
[52]	LIU Hongfu, MAO Haiyi, FU Yun. Robust Multi-View Feature Selection[C]// IEEE. 2016 IEEE 16th International Conference on Data Mining (ICDM). New York: IEEE, 2016: 281-290.
[53]	XU Jinglin, HAN Junwei, NIE Feiping, et al. Re-Weighted Discriminatively Embedded K-Means for Multiview Clustering[J]. IEEE Transactions on Image Processing, 2017, 26(6): 3016-3027. doi: 10.1109/TIP.2017.2665976 pmid: 28186894
[54]	WANGILA K W, GAO Ke, ZHU Pengfei, et al. Mixed Sparsity Regularized Multi-View Unsupervised Feature Selection[C]// IEEE. The International Conference on Image Processing. New York: IEEE, 2017: 1930-1934.
[55]	NIE Feiping, LI Jing, LI Xuelong. Convex Multiview Semi-Supervised Classification[J]. IEEE Trainsactions on Image Processing, 2017, 26(12): 5718-5729.
[56]	YANG Muli, CHENG Deng, NIE Feiping. Adaptive-Weighting Discriminative Regression for Multi-View Classification[J]. Pattern Recognition, 2019, 88: 236-245. doi: 10.1016/j.patcog.2018.11.015
[57]	HE Tian. Adaptive Learning-Based Multi-View Unsupervised Feature Selection[D]. Chegndu: Southwest University of Finance and Economics, 2023.
	何添. 基于自适应学习的多视图无监督特征选择方法研究[D]. 成都: 西南财经大学, 2023.
[58]	LIU Yuxin, HAN Xiaohong, SONG Ke. Unsupervised Multi View Feature Selection Based on Adaptive Similarity[J]. Computer Engineering and Design, 2021, 48(11): 3158-3163.
	刘宇欣, 韩晓红, 宋可. 基于自适应相似性的无监督多视图特征选择[J]. 计算机工程与设计, 2021, 48(11):3158-3163.
[59]	GUI Jie. Multi-View Feature Selection for Heterogeneous Face Recognition[C]// IEEE. 2018 IEEE International Conference on Data Mining (ICDM). New York: IEEE, 2018: 983-988.
[60]	CHEN Xi, LIU Wei, SHAO Guofang, et al. Semi-Supervised Multiview Feature Selection with Label Learning for VHR Remote Sensing Images[C]// IEEE. 2016 IEEE International Geoscience and Remote Sensing Symposium (IGARSS). New York: IEEE, 2016: 2372-2375.
[61]	WANG Yu, ZHAO Xiaoyan, YANG Xinli, et al. The Confidence Interval of AUC Metric Based on K-Fold Cross Validation Beta Distribution[J]. System Science and Mathematics, 2020, 49(10): 1564-1577.
	王钰, 赵晓燕, 杨信丽, 等. 基于K折交叉验证Beta分布的AUC度量的置信区间[J]. 系统科学与数学, 2020, 49(10):1564-1577.
[62]	LIU Jiaxing. Support Vector Regression Based on Grid Search Hyperparameter Optimization[J]. Scientific and Technological Innovation, 2022(13): 71-75.
	刘佳星. 基于网格搜索超参数优化的支持向量回归[J]. 科学技术创新, 2022(13):71-75.

特征选择算法类型	具体模型	是否考虑噪声影响	是否考虑视图间的联系	是否拆分视图求解	算法复杂度
传统特征选择算法	SMART	未考虑噪声	否	否	$\begin{align} & O(c({{d}^{3}}+{{d}^{2}}n+ \\ & d({{n}^{2}}+n+c))) \\ \end{align}$	高
基于l_2,1范数损失的特征选择	RFS	降低噪声影响	否	否	$O({{d}^{3}}+{{d}^{2}}n+dnc)$	高
基于Capped范数损失的特征选择	SCM	去除离群点	否	否	$\begin{align} & O({{d}^{3}}+{{d}^{2}}n+ \\ & d({{n}^{2}}+c+nc)) \\ \end{align}$	高
基于G₁, G_2,1范数损失的多视图特征选择	MVML	不考虑噪声	是	否	$\begin{align} & O({{d}^{3}}+{{d}^{2}}n+ \\ & c)+d(c+nc)) \\ \end{align}$	高
基于视图加权的多视图特征选择	VWRFS	降低噪声影响	是	是	$O(\sum\limits_{v=1}^{m}{(}d_{v}^{3}+d_{v}^{2}n+d_{v}^{2}+$${{d}_{v}}c+{{d}_{v}}nc+nc))$	低
基于视图自加权的多视图特征选择	ADVW	去除离群点	是	是	$O(\sum\limits_{v=1}^{m}{(}d_{v}^{3}+d_{v}^{2}n+$${{d}_{v}}{{n}^{2}}+{{d}_{v}}c+{{d}_{v}}nc))$	低
基准算法（不选择特征）	Allfea	—	—	—	—	—

算法	ACC	F1	计算W所需的时间/s
SMART	0.8556	0.8263	22
RFS	0.8579	0.8527	10
SCM	0.8594	0.8544	20
MVML	0.8561	0.8451	18
VWRFS	0.8600	0.8613	10
ADVW	0.8602	0.8621	9
Allfea	0.8149	0.8200	—

算法	ACC	F1	计算W所需的时间/s
SMART	0.9863	0.9861	14
RFS	0.9860	0.9860	4
SCM	0.9865	0.9862	6
MVML	0.9856	0.9856	5
VWRFS	0.9865	0.9862	2
ADVW	0.9867	0.9865	2
Allfea	0.9780	0.9781	—

算法	ACC	F1	计算W所需的时间/s
SMART	0.2443	0.2496	16
RFS	0.2453	0.2550	4
SCM	0.2455	0.2552	8
MVML	0.2461	0.2560	6
VWRFS	0.2548	0.2566	3
ADVW	0.2550	0.2618	3
Allfea	0.2410	0.2428	—

算法	ACC	F1	计算W所需的时间/s
SMART	0.4920	0.4933	477
RFS	0.4960	0.4966	47
SCM	0.4965	0.4968	250
MVML	0.4958	0.4965	220
VWRFS	0.4977	0.4978	40
ADVW	0.4978	0.4980	36
Allfea	0.4915	0.4920	—