背景技术
[0002] 在机器学习中传统算法经常遇到众所周知的维数灾难的问题。在这种情形下，通过降低数据的维数有利于提高数据分析的效率和精确度。特征选择是从一组特征中选出一组最相关的特征的子集以降低特征空间维数的过程，从而达到改善学习模型性能的目标。
[0003] 研究人员已提出各种特征选择方法。这些方法大致分为两类：(1)特征排名方法；(2)特征子集搜索方法。特征排名方法通常单独考虑每个特征的重要性，并对其排名，从而从中选择一组最重要的特征；而特征子集方法则根据一些准则(如一致性和相关性等)来判断可能的候选特征子集的重要性，并从中选择最优的一个。相比较前者，后者通常能够获得更好的性能和对结果的解释性。因此，文章主要关注对后者的研究。
[0004] 目前，研究人员已经提出许多著名的特征子集搜索方法，如顺序飘动向前搜索方法(sequential floating forward selection，SFFS)，稀疏化的方法(如Lasso)等。其中，Lasso方法由于能够同时进行回归和特征选择，并且选择出的特征与类标签非常相关，因此得到了广泛研究和应用。但是，在基于Lasso的方法中，一个主要缺点是只考虑了样本和类标签之间的关联，而忽略了样本与样本之间的相互依赖，如同类样本的局部相邻结构信息，而这些信息能够帮助诱导出更有判别力的特征，从而完成更好的分类。
[0005] 在各种特征选择方法中，基于Lasso的方法取得了广泛的研究和应用。然而，这类方法的一个主要缺点是只考虑了样本和类标签之间的相关性，却忽略了样本自身的内在关联信息，而这些信息有助于诱导出更具有判别力的特征。
[0006] 基于Lasso的特征选择方法介绍如下：
[0007] 给定训练样本集X＝[x1，x2，…，xN]T∈RN×d，其中xi表示第i个样本的特征向量，N表示训练样本个数，d表示特征维数。假定Y＝[y1，y2，…，yN]∈RN表示这些样本所对应的相应向量。对于监督分类问题，yi表示样本的类标签。不失一般性，本发明只考虑两类分类问题，即yi∈{+1，-1}。则Lasso特征选择方法优化的目标函数是：
[0008]
[0009] 其中w表示特征向量的回归系数。正则化项‖w‖1采用L1-范式将在特征空间中产生一个稀疏解，即不相关的和多余的特征所对应的系数将被置为0，而非0系数所对应的特征将被保留下来用于随后的分类。λ>0是一个正则化参数，用于平衡模型复杂度和数据的拟合程度。
[0010] 与传统的特征选择方法相比，Lasso方法通过最小化一个目标函数来完成特征选择，而且经验数据已经表明当有大量的不相关特征而只有少量的样本时，Lasso方法非常有效。因此，Lasso方法已经被应用到许多问题当中，如：寻找疾病的生物标志和脑疾病的分类。在Lasso方法中存在的一个限制是：当特征维数d大于样本个数N时，Lasso最多只能选择N个特征。针对这一不足，Zou等人通过增加了一个L2-范式正则化项，提出了一种称之为elastic net的特征选择方法。考虑一些数据的特征具有平滑性特点(即相邻的特征应该具有相同或相似的权重系数)，Tibshirani等人在Lasso基础上通过增加一个新的L1-范式，提出了一种Fused Lasso的方法，Ye等人给出了对Fused Lasso进行快速优化的方法。最近，Yamada等人基于核的方法将Lasso从线性情况推广到非线性情况。
[0011] 另一方面，针对几组特征需要联合地进行特征选择的情况，Yun等人提出了group Lasso方法。而一些研究人员将group Lasso思想应用到多任务学习当中，取得了很好的效果。另外，研究人员也提出了sparse group Lasso的方法来联合地选择具有共性的特征和个性的特征。最近，研究人员通过增加正则化项方法进一步推广group Lasso方法，如：Gong等人提出了一种鲁棒的group Lasso来处理数据中包含噪声的情况；而Kim等人针对数据特征中存在分层结构情况，提出一种tree-guided group Lasso的方法。
[0012] 在这些基于Lasso的方法中，存在的一个主要的不足是只考虑到样本和预测值(即标签)之间的依赖关系，而忽略了样本与样本之间的相互依赖的关系，如同类样本的局部相邻结构，这些信息的丢失可能会影响到选择特征的判别性，从而影响到分类器最终的分类性能。为了解决这一问题，并受最近一些工作的启发，提出了一种新的基于Laplacian的特征选择方法Lap-Lasso。
