基于矩阵分解和自适应图的无监督特征选择

doi:10.12305/j.issn.1001-506X.2021.08.22

摘要/Abstract

摘要：

在高维数据分析中，一个不可避免且棘手的问题是维度诅咒，因而如何将高维数据通过特征选择降维为低维数据显得尤为重要。对此, 提出了基于鲁棒矩阵分解和自适应图的无监督特征选择模型(unsupervised feature selection model based on robust matrix factorization and adaptive graph, MFAGFS), 实现在一个统一的学习框架下执行鲁棒矩阵分解、特征选择以及局部结构学习。模型首先通过鲁棒矩阵分解可获得聚类标签, 将聚类标签和局部结构信息用来引导特征选择过程, 再从特征选择的结果中自适应地学习数据局部结构。通过局部结构学习和特征选择这两个基本任务的相互作用, MFAGFS可以精确捕获数据的结构信息以及选择出具有判别性的特征。然后，详细阐述了算法优化求解方法, 并证明了算法的收敛性。最后，在6个公开数据集上进行试验对比分析, 参数敏感性分析, 验证了所提模型的有效性。实验结果表明, 所提的方法与其他方法相比, 性能均有不同程度的提高。

关键词: 特征选择, 图嵌入, 自适应, 矩阵分解

Abstract:

Due to the so-called curse of dimensionality, which is inevitable and tricky in high-dimensional data analytics, it is of great importance to perform dimensionality reduction via feature selection methods. Therefore, an unsupervised feature selection model based on robust matrix factorization and adaptive graph (MFAGFS) is proposed, which can perform robust matrix factorization, feature selection and local structure learning under a unified learning framework. The model first obtains cluster tags by robust matrix decomposition, cluster tags and local structure information are used to guide the feature selection process. Then, learning the local structure of the data adaptively from the result of feature selection. MFAGFS can accurately capture the structure information of the data and select discriminative features through the interaction between the two basic tasks of the local structure learning and feature selection. Then, the optimization method of the algorithm is described in detail, and the convergence of the algorithm is proved. Finally, experimental comparative analysis and parameter sensitivity analysis are carried out on six public data sets to verify the effectiveness of the proposed model. The experimental result shows that the performance of the proposed methods presented is improved in different degrees compared with other methods.

Key words: feature selection, graph embedding, adaptation, matrix factorization

中图分类号:

曹浪财, 林晓昌, 苏思行. 基于矩阵分解和自适应图的无监督特征选择[J]. 系统工程与电子技术, 2021, 43(8): 2197-2208.

Langcai CAO, Xiaochang LIN, Sixing SU. Unsupervised feature selection based on matrix factorization and adaptive graph[J]. Systems Engineering and Electronics, 2021, 43(8): 2197-2208.

图/表 8

图1

表1

表2

表3

图2

图3

图4

图5

参考文献 30

1	包芳, 殷柯欣. 特征选择算法综述及进展研究[J]. 科技风, 2020, (6): 231.
	BAO F , YIN K X . Review and progress of feature selection algorithms[J]. Science and Technology Wind, 2020, (6): 231.
2	NIE F P, XIANG S M, JIA Y Q, et al. Trace ratio criterion for feature selection[C]//Proc. of the 23rd AAAI Conference on Artificial Intelligence, 2008: 671-676.
3	YANG Y, SHEN H T, MA Z, et al. L21-norm regularized discriminative feature selection for unsupervised learning[C]//Proc. of the 22nd International Joint Conference on Artificial Intelligence, 2011: 1589-1594.
4	CAI D, HE X, HAN J W. Spectral regression: a unified approach for sparse subspace learning[C]//Proc. of the IEEE 7th International Conference on Data Mining, 2007: 73-82.
5	CAI D, ZHANG C Y, HE X F. Unsupervised feature selection for multi-cluster data[C]//Proc. of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010.
6	ZHAO Z, WANG L, LIU H. Efficient spectral feature selection with minimum redundancy[C]//Proc. of the 24th AAAI Conference on Artificial Intelligence, 2010: 673-678.
7	LIU X W , WANG L , ZHANG J . Global and local structure preservation for feature selection[J]. IEEE Trans.on Neural Networks & Learning Systems, 2014, 25 (6): 1083- 1095.
8	HOU C P , NIE F P , LI X L , et al. Joint embedding learning and sparse regression: a framework for unsupervised feature selection[J]. IEEE Trans.on Cybern, 2013, 44 (6): 793- 804.
9	QIAN M J, ZHAI C X. Robust unsupervised feature selection[C]//Proc. of the 23rd International Joint Conference on Artificial Intelligence, 2013.
10	LI Z C, YANG Y, LIU J, et al. Unsupervised feature selection using nonnegative spectral analysis[C]//Proc. of the 26th AAAI Conference on Artificial Intelligence, 2012: 1026-1032.
11	SHI L, DU L, SHEN Y D, et al. Robust spectral learning for unsupervised feature selection[C]//Proc. of the International Conference on Data Mining, 2014: 977-982.
12	ZENG H , CHEUNG Y M . Feature selection and kernel learning for local learning-based clustering[J]. IEEE Trans.on Software Engineering, 2010, 33 (8): 1532- 1547.
13	DU L, SHEN Y D. Unsupervised feature selection with adaptive structure learning[EB/OL]. [2020-10-26]. https://arxiv.org/abs/1504.00736.
14	NIE F P, ZHU W, LI X L. Unsupervised feature selection with structured graph optimization[C]//Proc. of the 30th AAAI Conference on Artificial Intelligence, 2016: 1302-1308.
15	DU S Q , MA Y D , LI S L , et al. Robust unsupervised feature selection via matrix factorization[J]. Neurocomputing, 2017, 241 (7): 115- 127.
16	占善华, 武继刚, 房小兆. 自适应图嵌入的鲁棒稀疏局部保持投影[J]. 计算机工程与设计, 2020, 41 (8): 2296- 2301.
	ZHAN S H , WU J G , FANG X Z . Robust sparse locally preserving projection for adaptive graph embedding[J]. Computer Engineering and Design, 2020, 41 (8): 2296- 2301.
17	CAI D , HE X F , HAN J W , et al. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Trans.on Pattern Analysis & Machine Intelligence, 2011, 33 (8): 1548- 1560.
18	HUANG J , NIE F P , HUANG H , et al. Robust manifold nonnegative matrix factorization[J]. ACM Trans.on Knowledge Discovery from Data (TKDD), 2014, 8 (3): 1- 21.
19	TAO H , HOU C P , NIE F P , et al. Effective discriminative feature selection with nontrivial solution[J]. IEEE Trans.on Neural Networks and Learning Systems, 2017, 27 (4): 796- 808.
20	WANG X D , ZHANG X , ZENG Z Q , et al. Unsupervised spectral feature selection with l1-norm graph[J]. Neurocomputing, 2016, 200, 47- 54. doi: 10.1016/j.neucom.2016.03.017
21	NIE F P, WANG X Q, HUANG H. Clustering and projected clustering with adaptive neighbors[C]//Proc. of the ACM International Conference on Knowledge Discovery & Data Mining, 2014.
22	CHUNG F R K . Spectral graph theory, regional conference series in math[M]. America: American Mathematical Society, 1997.
23	NIE F P, WANG X Q, JORDAN M I, et al. The constrained laplacian rank algorithm for graph-based clustering[C]//Proc. of the 13th AAAI Conference on Artificial Intelligence: 1969-1976.
24	FAN K . On a theorem of Weyl concerning eigenvalues of linear transformations Ⅱ[J]. Proceedings of the National Academy of Sciences, 1950, 35 (1): 652- 655.
25	高小方. 流形学习方法中的若干问题分析[J]. 计算机科学, 2009, 36 (4): 25- 28, 59. doi: 10.3969/j.issn.1002-137X.2009.04.006
	GAO X F . Analysis of some problems in manifold learning method[J]. Computer Science, 2009, 36 (4): 25- 28, 59. doi: 10.3969/j.issn.1002-137X.2009.04.006
26	BOYD S , PARIKH N , CHU E , et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3 (1): 1- 122.
27	BOYD V F . Convex optimization[J]. IEEE Trans.on Automatic Control, 2006, 51 (11): 1859- 1859. doi: 10.1109/TAC.2006.884922
28	NIE F P, HUANG H, CAI X, et al. Efficient and robust feature selection via joint l₂, 1-norms minimization[C]//Proc. of the Advances in Neural Information Processing Systems 23: Conference on Neural Information, 2010.
29	MOKLYACHUK M . Convex optimization: introductory course[M]. America: John Wiley & Sons, 2021.
30	HE X F, CAI D, NIYOGI P. Laplacian score for feature selection[C]//Proc. of the Advances in Neural Information Processing Systems 18, 2005: 505-512.

数据集	样本数	特征维度	类别数	选择的特征个数
PalmData25	2 000	256	100	[5, 10, …, 50]
ECOLI	336	343	8	[5, 10, …, 50]
ISOLET	1 560	617	26	[5, 10, …, 50]
JAFFE	213	676	10	[5, 10, …, 50]
YALE	165	1 024	15	[5, 10, …, 50]
COIL20	1 440	1 024	20	[50, 60, …, 150]

数据集	PalmData25	ECOLI	ISOLET	JAFFE	YALE	COIL20	AVERAGE
Baseline	68.41	57.44	56.55	72.85	38.64	59.17	58.84
LapScore	62.88	59.75	53.65	73.93	41.85	57.22	58.21
UDFS	67.79	59.93	54.85	72.93	39.76	56.59	58.64
NDFS	69.29	61.43	60.19	76.03	38.67	63.28	61.48
FASAL	68.07	65.46	59.93	73.12	38.88	61.56	61.17
SOGFS	67.89	63.66	55.48	75.65	43.33	62.00	61.34
MFAGFS	69.43	73.04	62.92	80.39	44.15	63.01	65.49

数据集	PalmData25	ECOLI	ISOLET	JAFFE	YALE	COLI20	AVERAGE
Baseline	90.24	55.48	1.26	81.17	46.48	75.58	58.37
LapScore	86.99	60.16	0.39	83.48	49.18	71.38	58.60
UDFS	89.14	59.86	0.72	78.39	48.97	71.30	58.06
NDFS	89.89	60.26	3.16	85.80	46.51	73.02	59.77
FASAL	89.48	60.57	3.18	80.58	46.27	74.72	59.13
SOGFS	89.53	60.35	0.89	83.92	52.98	76.37	60.67
MFAGFS	89.74	62.63	4.88	85.40	54.49	78.17	62.55

[1]	常浩伟, 庞春雷, 郭泽辉, 张良, 吕敏敏, 张闯. 基于自适应免疫算法的欺骗信号检测方法[J]. 系统工程与电子技术, 2022, 44(8): 2419-2426.
[2]	熊元燚, 谢文冲. 基于空时约束的自适应迭代单脉冲估计方法[J]. 系统工程与电子技术, 2022, 44(8): 2506-2514.
[3]	方志耕, 夏悦馨, 张靖如, 熊仪, 陈静邑. 基于Agent的体系过程A-GERT网络“刺激-反应”学习模型[J]. 系统工程与电子技术, 2022, 44(8): 2540-2553.
[4]	王帅, 向建军, 彭芳, 唐书娟, 李志军. 基于新最速下降算法的自适应波束形成[J]. 系统工程与电子技术, 2022, 44(7): 2104-2111.
[5]	闫世瑛, 颜克斐, 方伟, 陆恒杨. 基于差分进化邻域自适应的大规模多目标算法[J]. 系统工程与电子技术, 2022, 44(7): 2112-2124.
[6]	李波, 周家豪, 刘民岷, 朱品朝. 基于改进NSGA3的焊接缺陷评估特征选择[J]. 系统工程与电子技术, 2022, 44(7): 2211-2218.
[7]	王冠, 茹海忠, 张大力, 马广程, 夏红伟. 弹性高超声速飞行器智能控制系统设计[J]. 系统工程与电子技术, 2022, 44(7): 2276-2285.
[8]	高升, 马广富, 郭延宁. 基于自适应未知输入观测器的多故障快速重构[J]. 系统工程与电子技术, 2022, 44(7): 2364-2373.
[9]	魏法, 杨明磊, 何小静, 周鼎森, 陈伯孝. 基于改进粒子群算法的平面阵同时多波束赋形方法[J]. 系统工程与电子技术, 2022, 44(6): 1789-1797.
[10]	陈江美, 张文德. 基于灰关联分析和时空偏好特征的兴趣点推荐算法[J]. 系统工程与电子技术, 2022, 44(6): 1934-1941.
[11]	董一平, 刘宁, 苏中, 王靖骁, 白宏阳. 基于AEKF的高速自旋飞行体组合导航方法[J]. 系统工程与电子技术, 2022, 44(6): 1977-1983.
[12]	韦娟, 杨皇卫, 宁方立. 基于NMF与CNN联合优化的声学场景分类[J]. 系统工程与电子技术, 2022, 44(5): 1433-1438.
[13]	王帅, 向建军, 彭芳, 唐书娟. 基于新最速下降法的目标跟踪算法[J]. 系统工程与电子技术, 2022, 44(5): 1512-1519.
[14]	罗世彬, 李晓栋, 王忠森, 徐骋. 并联式运载器上升段广义超螺旋有限时间控制[J]. 系统工程与电子技术, 2022, 44(5): 1626-1635.
[15]	李海, 程伟杰, 谢瑞杰. 基于同伦稀疏STAP的低空风切变风速估计[J]. 系统工程与电子技术, 2022, 44(4): 1174-1181.