联合L2,1范数正则约束的特征选择方法

　　【摘要】本文中，我们提出了一种新颖的特征选择算法，将L2，1范数正则项合并到一块进行非监督特征选择。L2，1范数正则项通过作用在转移矩阵上使得对所有样本数据进行特征选择，本文还包括这种方法的收敛性以及计算复杂度的分析。最后运用我们的算法进行聚类分析，在典型实测数据上开展了方法验证，实验结果表明，该方法能有效地选择出所需的特征，且具有很高的准确率。 　　【关键词】特征选择， L2，1范数正则，邻域保持映射，稀疏回归 　　1、引言 　　如何从高维数据中选择或提取对识别或分类有效的特征已成为当前的研究热点和难点，维数约简由此应运而生。特征选择和特征提取是维数约简的最主要的两种方法。特征选择旨在保持原始特征，而特征提取生成新的特征。和特征提取比较起来，特征选择不会改变数据变量的原始特征，比如生物学分析就需要保持原始数据的特征。特征选择的方法大致可以分成两类，即监督的特征选择和非监督的特征选择。在现实生活中，想要获取带有标签的数据是很困难的，并且很代价很高。所以非监督的特征选择更加具有现实意义。 　　近年来，涌现了多种高效的无监督特征选择方法，例如主元分析理论（Pcascor）[1]，拉普拉斯变换理论（Lapscor）[2]，谱特征选择（SPEC）[3]，多重聚类特征选择（MCFS）[4]以及最小冗余谱特征选择（MRSF）[5]，邻域保持映射（LLE）[6]。这些方法因为高效而得到了广泛的应用。此外，这些方法将分类与特征选择两者分步实行，约束限制较少。我们能通过添加优化约束步骤，或者通过线权法将各个优化约束进行联合，来进一步地改进分类、选择的性能。根据【7】，将L2，1范数正则项与其他特征选择方法相联合，能显著地提高特征选择的准确度以及收敛速度。 　　本文中，我们提出了一种将L2，1范数正则项与各种维数约简方法相联合的特征选择。主要分为两块：第一，邻域保持映射与L2，1范数正则联合；第二，拉普拉斯特征映射（Laplacian Eigenmaps）与L2，1范数正则联合。 　　2、邻域保持映射与L2，1范数正则联合模型建立与求解 　　邻域保持映射与L2，1范数正则联合模型，简记为LLELDO。在这一节中，我们首先建立详细的模型，然后提出一个有效的算法来解决这个问题。在介绍算法之前，说明一下需要用到的数学符号。记作为无标签的数据集，从原始数据中选择s个特征来代表它们，。对于一个向量x，其r-范数记为； 　　对于一个矩阵，Lr，p范数定义为， 　　（1） 　　设是W的第i行向量，即。可以验证Lr，p范数是合理范数。由此可以得到L2，1范数的定义为， 　　（2） 　　2.1邻域保持映射与L2，1范数正则联合模型建立 　　我们的算法有两个目标函数。考虑到邻域保持映射能有效地进行维数约简，而拉普拉斯图能赋予流型结构特征，我们将它们的优点合并在一起继而构成新的特征选择算法。 　　步骤1. 考虑到相邻数据点之间应具有相似的特点，先建立一个权重图G=（V，E，S）来表征数据点之间的联系。其中是图的顶点集，E为所构造的图的边的集合，边的权重，构造加权图G的具体步骤为： 　　步骤1：将各个数据点Xi与其相应的k个相邻最近的点连接 　　步骤2：确定权重矩阵S 　　Sij为i到j的边界权值，若没有边界则记为0，非零权值由如下式子决定， 　　（3） 　　这里表示Xi所有邻接点构成的集合。 　　由邻域保持映射可知，我们用经低维线性映射处理所得的数据来表示原始数据Xi，其中m为映射的维数。通过以上变换，保留了最有价值的信息的同时去掉了冗余的信息。由此，可得 　　（3） 　　其中图拉普拉斯的变换。当时， 是Xi的低维线性映射的象，记。 　　步骤2. 第二个目标函数用作特征选择。根据LLE和等式（4），可以得到等式，其中W是转移矩阵，记为。设 是W的第i行向量，关键之处在于，可以衡量第i个特征的重要程度。 　　我们希望只有小部分是非零的，这样就能通过提取出一小部分特征来反映初始的高维数据，由稀疏性我们可以得到以下目标函数， 　　（4） 　　其中就是等式（1）中定义的L2，1范数。 　　将等式（4）和等式（5）合并到一起，我们的LLELDO算法可以记为， 　　（5） 　　2.2模型求解 　　由等式（6）可知，我们的目标是优化Y和W，对此我们将采用迭代的方法实现。通过迭代的方法我们交替地更新Y和W。 　　记为对角矩阵，其中第i个对角元素记为， 　　（6） 　　于是等式（6）转化为， 　　（7） 　　下面我们说明一下优化等式（8）可以得到稀疏解的原因。由等式（7） 的定义，可以得知当不等于0时有，因此优化可以将稀疏条件限制在W上。显然，若很小，则很大，而 变得更小。经过几轮迭代以后，一些的范数将趋近于零，继而得到稀疏矩阵W。另外，当时，等式（8）不成立。 　　当U是固定的，对W和Y来说目标函数等式（8）是凸的。当固定W时，我们可以由等式（7）直接得到U。总之，当W是固定的，我们可以计算得到U，而当U是固定的时候我们可以更新得到W和Y。 　　由邻域保持映射可知，因而有，等式（8）转换为， 　　（8） 　　由等式（9）和限制条件可知，上述优化问题转变为， 　　（9） 　　总之，我们用迭代的方法优化等式（6）。若固定U，我们首先优化等式（10）得到Y，然后根据得到W。接着根据等式（7）得到U。算法的具体过程将详细地列在表1中。 　　表1： 邻域保持映射与L2，1范数正则联合算法 　　输入：数据集； 平衡参数a； 邻域参数k； 邻域保持映射维数m； 选择特征的个数s. 　　输出：选择的特征指标集. 　　步骤 1： 图的构造 　　1.构造k近邻图G； 　　2.计算相似矩阵S，图的拉普拉斯值L； 　　Step2：迭代优化 　　1.初始化； 　　2.交替优化U，Y和W直到收敛. 　　a.固定U，由等式（10）优化Y，由计算W； 　　b.固定W，由等式 （7）优化U； 　　Step3： 特征选择 　　1.计算所有特征的值； 　　2.将所有特征进行降序排列，选择最大的s个特征值. 　　它们相应的指标构成了特征指标集. 　　3、拉普拉斯特征映射与L2，1范数正则联合模型建立与求解 　　拉普拉斯特征映射与L2，1范数正则联合模型，简记为JERSL[7]，这模型的推导以及相应符号的意义，与上述邻域保持映射与L2，1范数正则联合模型中所提及的相一致。相应的目标方程为： 　　（11） 　　方程（11）最终转化为求解以下优化问题： 　　（12） 　　另外，JERSL的求解过程与LLELDO的求解步骤相同，唯一的不同在于，JERSL的迭代求解中，Y的迭代为对方程（12）的求解，而W的迭代公式为： 　　（13） 　　4、拉普拉斯特征映射与L2，1范数正则联合模型收敛性讨论 　　引理一：对于任意非零向量，成立如下不等式： 　　（14） 　　定理一：表格一中的第二步优化过程的每一次迭代，都会使得目标方程（7）的函数值下降。 　　证明： 　　从表格一中算法可知，设Ut为第t次迭代过程中的U的取值，以此计算，以下不等式成立： 　　（15） 　　又由于，以上的不等式表明， 　　（16） 　　不等式（16）表明了目标方程（11）的函数值在每一次迭代过程中都会下降。此外，由于目标方程函数值有下限，例如0，因此，此迭代过程会收敛。下述实验结果也表明，此算法收敛速度非常快，直至收敛的迭代次数一般不超过20次。 　　同理，可以推导出邻域保持映射与L2，1范数正则联合模型的收敛性分析，其与拉普拉斯特征映射与L2，1范数正则联合模型一样具有很高的收敛性。 　　5、计算复杂度分析 　　与其他方法相比，例如PcaScor、LapScor、MCFS、MRSF，上述两种特征提取方法具有相当的计算复杂度。在求解过程中，最耗时间的是方程（11）与（12）以及W的迭代求解。事实上，LLELDO的计算复杂度为，JERSL的计算复杂度为。 　　6、应用实例 　　为了衡量特征选择的效果，采用了相应的评价指标，也即聚类准确率（ACC），其计算公式为： 　　（16） 　　其中Li是现实中的实际标签，ci是计算所得聚类指标，是一个将聚类指标与分类结果相匹配的一个函数，而 　　（17） 　　本文用三组真实的数据集（Umist [14]、ORL [15] 、Isolet [17]）以验证算法的有效性。通过K-均值聚类，采用传统的非监督的特征选择方法和LLELDO、JELSR分别对三组数据分别进行处理，结果如下： 　　图1：三组数据集上，不同的低维特征数目下的ACC结果（K均值聚类法），x轴表示所选择的低维特征数，y轴表示ACC结果。 　　由图1可看出，上述两个算法在特征选择中具有很高的准确率，在大多数情况下优于传统的方法。 　　7、结论 　　本文建立了一种联合L2，1范数正则约束的新的无监督型特征选择方法，与传统方法相比，具有很高的选择准确率。此外，本文还提供了解决L2，1范数正则约束问题的一种有效的方法，并分析了其收敛性质。 　　参考文献 　　[1]W. J. Krzanowski， Selection of Variables to Preserve Multivariate Data Structure， Using Principal Components，Journal of the Royal Statistical Society. Series C （Applied Statistics）， vol. 36， no. 1， pp. 22–33， 1987. 　　[2]X. He， D. Cai， and P. Niyogi， Laplacian score for feature selection， in NIPS， 2005. 　　[3]Z. Zhao and H. Liu， Spectral feature selection for supervised and unsupervised learning， in ICML， 2007， pp. 1151–1157. 　　[4]D. Cai， C. Zhang， and X. He， Unsupervised feature selection for multi-cluster data， ser. KDD’ 10， 2010， pp. 333–342. 　　[5]Z. Zhao， L. Wang， and H. Liu， Ef?cient spectral feature selection with minimum redundancy， in AAAI， 2010. 　　[6]X. He and D. Cai. Neighborhood Preserving Embedding. In IEEE， Vol（2）， 1208-1213， 2005. 　　[7]C. Hou， F. Nie， D. Yi， and Y. Wu， Feature selection via joint embedding learning and sparse regression， in IJCAI， 2011. 　　[8]F. P. Nie et.al. Ef?cient and robust feature selection via joint L2，1-norm minimization. In NIPS， pp.1813-1821， 2010. 　　[9]http：//images.ee.umist.ac.uk/danny/database.html. 　　[10]http：//www.zjucadcg.cn/dengcai/Data/FaceData.html. 　　[11]http：//archive.ics.uci.edu/ml/machine-learning-databases/isolet