一种基于整数规划的无监督特征选择方法

Unsupervised Feature Selection Method Based on Integer Programming

特征选择方法可以剔除冗余特征,保留关键的数据特征,是一种有效解决维数灾难问题的途径.本文利用特征与特征之间的重构关系建立损失函数,并且基于投影矩阵的l2,0范数作为稀疏约束项,提出一种新型的无监督特征选择方法.由于优化问题涉及离散稀疏的矩阵l2,0范数约束条件,无法直接求得全局最优解.我们先将矩阵的l2,0范数约束等价转化为0-1整数规划约束形式,然后再利用圆盒模型将0-1整数约束等价转化为两个连续的约束条件.对于新约束条件的优化问题,采用交替方向乘子法优化求解.在5个公开数据集上的分类和聚类实验结果表明,本文方法比其他9种无监督特征选择方法的效果更好,能够在指定特征数目时选择出判别能力更强的特征.

As an important approach to circumvent the curse of dimensionality,feature selection is able to remove the redundant features and preserve the key informative features.In this paper,we propose a novel unsupervised Feature Selection(FS)method based on the projective matrix l2,0 norm as the sparse constraint and the loss function established by using the reconstruction relationship between features.Because the optimization problem involves discrete and sparse matrix l2,0 norm constraints,the global optimal solution cannot be obtained directly.To address this issue,we transform matrix l2,0 norm constraint to be a 0-1 integer constraint,and utilize circle-box approach to replace the 0-1 constraints with two continuous constraints.Finally,using the alternating direction method of multipliers,we get optimal solution for the optimization problem with new constraints.The experimental results of classification and clustering on five public data sets show that the proposed method in this paper is better than other nine unsupervised feature selection methods and can select features with stronger discrimination ability when the number of features is specified.