特征选择中的全局最优搜索策略研究

Feature selection is a multi-knowledge crossed research direction, since It refers to statistics, data mining, pattern recognition, machine learning and so on. Feature selection has been widely applied to Bioinformatics, medical science, information retrieval and so on. Traditional feature selection is achieved as a simple and fast search strategy, that can not guarantee an optimal solution and sometimes the obtained feature subset is far from perfect. This project, studying data in the high-dimensional space, solves the search solution for the global optimal feature subset. This project explores the relationship between matrix projection in feature extraction and optimal search direction and further proves the equivalence of both under some specified conditions. The anticipated achievements of this project are: (1) Instead of adding (or deleting) one feature gradually in traditional feature selection, this project adopts a special matrix projection. And it tries to construct a combinational optimization problem which has an global optimal solution.(2) This project defines some feature evaluation criterion that match the matrix projection, including evaluation criterions based on information entropy, sparse representation theory, subspace learning.(3) This project designs optimization algorithm for 0-1 large-scale sparse matrices..This project has significant importance to extend the traditional feature selection, and has wide application prospect.

特征选择是一门多学科的交叉研究方向，它涉及统计学、数据挖掘、模式识别和机器学习等相关学科，在生物信息学、医学、信息检索等诸多领域具有广泛应用前景。传统的特征选择以代价换取简单、快速的搜索策略实现，不能保证最优，甚至有时获得很不理想的特征子集。本项目以高维空间中的数据为研究对象，以全局最优特征子集的搜索方式为科学问题，深入挖掘特征抽取中的投影方式与特征选择中最优搜索之间的紧密联系，实现了两者在特定条件下的可通行。本项目研究的预期成果是：（1）采用特殊的矩阵投影方式替代传统特征选择流程中的逐渐增加（或删除）特征的搜索路径，力图构造一个存在全局最优解的组合优化问题；（2）定义出与矩阵投影方式相匹配的特征评估准则，包括基于信息熵、稀疏表示理论、图论的度量方式；（3）设计针对0-1大规模稀疏矩阵求解的优化算法。本项目对拓展传统特征搜索理论和算法有十分重要的意义，且具有十分广阔的应用前景。

传统的特征选择方法常常分步选择特征，不能保证所选特征子集的最优性。本项目以全局最优特征子集的搜索方式为研究内容，取得的主要学术成果包括： .1．.源于统计或几何理论的滤波方法都是一个一个地选择特征。这类方法忽略了特征间的相关性，所以获得的特征子集是次优的。为了解决这个不足，我们提出了同步特征权重学习框架，它能够自动确定最优特征子集的大小，且选择出针对给定连接图的最优特征子集。具体地说，此框架对特征权重施加了非负和l2,2范数约束，且迭代地同步学习特征权重。针对提出的非凸目标函数，我们设计了新的且可收敛的最小化算法。在此框架下，我们提出了一种新的非监督特征选择算法，命名为同步拉普拉斯特征权重学习算法。最后，实验结果也表明：我们的方法在五个真实库上是有效的。.2．.我们将基于稀疏表示分类器的度量方式引入特征选择中，并提出了稀疏鉴别特征选择方法。我们的目标函数致力于在特征子集空间中，找到最小化类内重构残差且最大化类间重构残差的特征子集。我们分别提出了贪婪搜索算法和同步搜索算法以解决联合优化目标函数。具体地说，我们的同步选择算法在目标函数中施加了l2,1范数约束，降低了特征间冗余性，且同步学习特征权重。最后，实验结果也表明：我们的方法在测试数据集上是有效的。.3．.局部保持度量准则常常被用来度量特征的好坏。但是，基于局部保持准则的非监督特征选择算法有两个广为人知的不足：(1) 特征选择的好坏非常依赖于相似矩阵构造的好坏。而相似矩阵一般都是在原特征空间中构造的，因此，它可能和加权特征空间中的相似矩是不一致的。(2) 贪婪搜索策略常常忽略了特征间的相关性和冗余性。为了弥补以上的不足，我们提出了新的非监督特征选择方法，此方法在加权特征空间中同步且自适应选择近邻。为了解决目标函数，我们提出了有效的迭代算法，此算法每次迭代中需解决一个凸的子问题，此子问题可以用现有的工具包有效解决。最后，实验结果也表明：我们的方法在UCI和人脸数据集上是有效的，并且和目前流行的监督和非监督特征选择相比，分类率更高。