基于核稀疏表示的属性选择算法*

吕治政，李扬定，雷 聪

(广西师范大学计算机科学与信息工程学院,广西 桂林 541004)

1 引言

随着云计算和大数据技术的发展，大量高维数据易于获取，高维数据随处可见。高维特征数据样本准确且能够多样性地表现样本的特性[1]，但由于其维数过高，不仅增大了数据存储容量，而且在数据处理过程中容易导致“维数灾难”问题[2]。属性选择技术的兴起，使得其能够按照某种评价指标，选出最优的属性子集对数据进行稀疏重构，保持了数据内在的关联信息，使得分类器在低维子空间上进行训练，很大程度上提高了在分类器上的训练效率和预测准确率[3]。属性选择既可以使我们更加清楚地知道是哪种属性导致了分类类别的不同，又可以有效地降低分类算法的计算复杂度，提高分类准确率。

针对数据“维数灾难”问题，我们真正要解决的就是数据降维，通俗地讲就是属性选择。近几年对于属性选择的研究主要集中在线性属性选择算法和非线性属性选择算法。Luebke等人[4]提出了一种新的线性自适应属性选择算法，自适应的属性选择算法的优点是对数据属性选择分类任务处理过程是自适应的，而且它也适用于各种数据类型的数据集，缺点就是在处理含有较多噪声属性的数据集时，从分类准确率的角度，还需要对算法进一步优化。Magdalinos等人[5]提出了一种属性选择效果好且性能优的属性选择算法，该算法的优点是时间和空间复杂度小，但是目前该算法只在分类任务和聚类任务中得到了验证，在处理高维大数据集时需要进一步加以验证。Lee等人[6]基于统计学的方法提出了一种“内在”距离概念的属性选择算法。该算法的缺点是需要引入1个参数t，参数t的选取不是固定的，需要手动调节，同时该方法需要在较大的数据集上进一步验证。现有的大多数关于属性选择的方法研究基本都是在传统的方法上加以改进，依然存在很大的局限性。在最近也有了一些其他的属性选择方法出现，如：最小二乘回归、样本依赖图、图优化的局部保持投影等。然而这些方法对参数是非常敏感的，在实际问题当中参数值的选择是非常困难的，特别在处理高维数据集时，参数选择对实验结果的影响会很大，不能很好地反映属性和类标签之间的关系。

本文针对以上问题运用了稀疏表示(Sparse Representation)的思想，提出一种基于核稀疏表示的属性选择算法KSFS(Feature Selection based on Kernel Sparse representation)。该算法将核函数与稀疏学习相结合，通过核函数将原始数据映射到高维核空间中，使得在低维空间线性不可分的数据，在高维核空间中具有更高程度的可分性[7]。同时，对核空间的高维数据进行稀疏表示，按照评价指标找出最优的属性子集，在一定程度上降低了分类算法的计算量，提高了分类算法的稳定性和准确率。具体地，该算法首先运用核函数构建与属性相关联的属性核矩阵，属性核矩阵数目与属性数目一致，从而可以挖掘属性核矩阵和类标签之间的非线性关系；同时利用L1范数有效地构建属性评分选择机制来确定稀疏向量元素取值为0或非0，对应着数据属性的取舍(0代表不选此属性)，得到原始数据集的一种稀疏表示方式；在算法优化过程中引入了低秩约束方法，既去除了噪声样本和冗余属性的影响，又考虑了数据之间的全局结构，从而选出最优的属性结构子集[2]。最终将最优的属性结构子集用于分类实验得到分类准确率。

2 相关理论背景及简介

2.1 核函数方法

只要任何1个对称函数所对应的核矩阵是半正定的，那么就可以称之为核函数，可以通过核函数构建原始样本的1个高维特征空间——核空间。核函数的1个非常重要的作用就是将原始样本在低维空间线性不可分的问题转化为高维核空间中的线性可分问题[8]。

定义k(xi,xj)是在Rn×n上的对称函数，则k是核函数当且仅当对于任意数据X∈Rn×d，“核矩阵”K总是半正定的，通过核函数k(xi,xj)，将数据集每1个列向量xi∈Rn×1=[x11,x21,…,xn1]T，i=1,2,…,d映射到核空间得到如下形式：

(1)

其中，K(i)∈Rn×n，i=1,2,…,d；m=1,2,…,n。

2.2 常见的核函数

常用的核函数主要有以下几种形式：

多项式核:

(2)

线性核:

(3)

拉普拉斯核:

k(xi,xj)=exp(-‖xi-xj‖2/σ)

(4)

高斯核:

k(xi,xj)=exp(-‖xi-xj‖2/(2σ2))

(5)

2.3 核稀疏表示

稀疏表示理论由于具有坚实的内在理论和重要的实际应用价值，使得稀疏表示得到了快速的发展，并且已经在数据挖掘和机器学习等重要领域得到了广泛的应用。

在稀疏学习的基础上，引入核函数将训练样本数据X∈Rn×d分解成为d个列向量xi∈Rn×1,i=1,2,…,d，通过核函数k(xi,xj)将每1个列向量xi投影到核空间生成新的属性核矩阵K(i)∈Rn×n,i=1,2,…,d，进一步对核空间数据进行稀疏表示，称为核稀疏表示，即解决问题：

(6)

其中，Y表示训练集类标签，W为系数矩阵，ε为最大误差容忍变量。式(6)是一个典型的凸优化问题，可以通过优化L1范数得到问题的最优解[9]。计算求解其最优的稀疏向量α=[α1,α2,…,αd]T。

3 算法描述及优化

3.1 算法描述

假设给定1个训练集X∈Rn×d，其中n和d分别表示训练集样本数目和属性数目，Y∈Rn×c表示训练集类标签，n和c分别表示类标签样本个数和类标签类别数。通常情况下，在有监督学习情况，属性选择的模型为：

(7)

其中,φ(W)是关于W∈Rd×c的正则化因子。式(7)通常情况下不能表示数据之间的非线性关系[10]，因此我们需要引入核函数，通过核函数把数据映射到高维核空间。理论已经证明核空间的数据是线性可划分的[9]，利用该方法在核空间上执行线性的属性选择从而实现低维空间上的非线性属性选择。

本文结合核函数和稀疏学习模型，将训练样本数据集X∈Rn×d分解成为d个列向量xi∈Rn×1，i=1,2,…,d，把列向量xi通过核函数k(xi,xj)投影到核空间生成新的属性核矩阵K(i)∈Rn×n,i=1,2,…,d。对于整个数据集X∈Rn×d通过核函数映射会生成d个与属性相关的核矩阵K(i)∈Rn×n，则核矩阵K(i)中的每1个元素为ki,j=k(xi,xj)，其中k(xi,xj)为高斯核函数，具体如式(5)所示，其中σ>0为核函数的带宽。

由于属性和类标签之间存在某种联系，在此本文引入核函数考虑属性与类标签之间的非线性关系，把类标签Y作为响应矩阵，把X通过核函数投影后形成属性核矩阵K(i),i=1,2,…,d，通过矩阵Z和属性选择系数αi来表示响应矩阵Y与核矩阵K(i)之间的关系：

(8)

其中，Y∈Rn×c表示响应矩阵，K(i)∈Rn×n表示核矩阵，Z∈Rn×c表示系数矩阵。

为了使式(8)等号右边的式子尽量拟合响应矩阵Y，用LF范数计算两者之间的偏差，即可得到如下关系：

(9)

在式(9)基础上引入Z的L2,p范数正则化项调整类标签和属性核矩阵之间的关系，避免模型过拟合，减少计算误差，因此可得到如下关系：

(10)

(11)

其中，λ1,λ2为控制参数，0

因为噪声样本和冗余属性会增加系数矩阵的秩，所以假设rank(Z)=r≤min(n,d),低秩限制的Z可以表示为Z=AB，其中A∈Rn×r,B∈Rr×c。综上所述，最后可以得到如下目标函数：

s.t.rank(AB)≤min(n,d)

(12)

其中,K(i)∈Rn×n,Y∈Rn×c,AB∈Rn×c,α∈Rd×1，AB为重构系数矩阵，α为属性选择向量。

本文提出的KSFS算法具有以下优点：

(1)KSFS算法采用有监督方式建立模型，在目标函数中充分利用类标签信息，将类标签作为目标函数的响应矩阵，从而很好地考虑了类标签和属性之间的相关性；其次，在线性回归模型下引入低秩约束方法来去除一些噪声和冗余数据，从而实现了子空间学习的效果；同时提高了模型对高维数据分类的准确率。所以，KSFS算法相对于单一子空间学习方法具有更好的效果。

(2)KSFS算法在稀疏学习模型的基础之上引入了核函数，通过核函数将原始数据映射到高维核空间，使得原始数据在高维核空间具有更高的可分性，在高维核空间上充分考虑了属性与类标签之间的非线性关系，属性选择效果比在低维空间要好很多。

(3)KSFS算法在目标函数中引入了向量α的L1范数，利用L1范数对模型具有很好的稀疏效果，从而使得稀疏向量α元素取值为0或非0，分别对应着数据属性的取舍(0代表不选此属性)。所以，在模型中把L1范数作为属性选择评分机制会起到良好的属性选择作用。

本文算法的伪代码如下所示：

算法1KSFS算法

输入：训练集X∈Rn×d,Y∈Rn×c;正则化参数λ1,λ2;SVM分类器中参数(c,g)∈[-10:2:10]，分类器选择非线性模式。

输出：样本分类准确率。

步骤1根据目标函数式(12)，调用算法2，求解目标函数全局最优解属性选择向量α；

步骤2根据最优解向量α，对原始数据集X∈Rn×d进行属性选择后得到的数据集，作为新的样本数据集；

步骤3对新的样本数据集样本采用SVM分类。

3.2 算法优化

目标函数式(12)中需要优化的3个参数分别是A,B,α。由于目标函数中有L1范数的存在，且目标函数是非凸的，所以需要去分步迭代求解最优的参数A,B,α。

s.t.rank(AB)≤min(n,d)

(13)

根据矩阵论知识[11]，可以将目标函数的每1项表示为如下形式:

(14)

λ1‖AB‖2,p=λ1tr(BTATDAB)

(15)

(16)

式(15)中的D∈Rm×m是一个对角矩阵，且D中的对角元素根据参考文献[11,12]可知为如下形式：

dii=1/(2/p)(‖gi‖2)2-p

s.t.i=1,2,…,m;0

(17)

其中,gi表示矩阵AB的第i行。

那么我们的目标函数可以进一步表示为如下形式：

(18)

(1)固定α，优化A,B。

由于优化B的过程实质是1个求导的过程，所以可以将目标函数中不包含B的项视为常数项，即在求导时此项为零，且令目标函数式(18)为J(A,B,α)，那么可以得到：

(19)

对B求偏导，并令其所得偏导数等于零：

ATDTA)B-2ATPTY=0

(20)

从式(20)可以求解得到B：

B=(AT(PTP+λ1D)A)-1ATPTY

(21)

然后,把求解得到的矩阵B代入目标函数式(18)中可得到：

λ1‖A(AT(PTP+λ1D)A)-1ATPTY‖2,p+λ2‖α‖1

(22)

最后通过一系列的化简可以得到：

(23)

在固定α的同时，式(23)要达到最小值，那么需要：

(24)

从式(24)中注意到：

St=PTP+λ1D,Sb=PTYYTP

(25)

其中,St和Sb分别表示线性判别分析LDA(Linear Discriminant Analysis)中的类内离散矩阵和类间离散矩阵，所以可以将式(25)代入式(24)求解得到A：

(26)

(2)固定A,B，优化α。

因为只是优化α，所以可以将目标函数式(12)进一步化简展开为：

(27)

我们可以进一步令K(i)AB=Q(i)∈Rn×c，那么式(27)可以表示为：

(28)

αTS(i)(S(i))Tα)+λ2‖α‖1⟺

(29)

式(29)中f(α)定义如下：

(30)

进一步定义F(α)：

F(α)=f(α)+λ2‖α‖1

(31)

很明显，f(α)是可导的，而且▽f(α)满足L-Lipschitz条件，那么就存在1个常数L>0，使得：

(32)

则在第t次迭代的向量αt附近可将f(α)通过二阶泰勒展开式近似为如下：

(33)

很显然，式(33)的最小值在式(34)中取得：

(34)

通过梯度下降法[8]对f(α)进行最小化，同时在每1步对f(α)进行梯度下降迭代考虑α的L1范数最小化，最终可以得到使F(α)最小化的向量α，即可得到如下表达式：

αt+1=

(35)

定义Ut：

(36)

然后将其代入式(35)得：

(37)

(38)

根据以上目标函数优化过程，优化算法能够确保目标函数值在每1次迭代过程中逐步收敛，最终获取全局最优解。

算法2优化求解表达式(12)的伪代码

输入：训练集X∈Rn×d,Y∈Rn×c；属性关联结构度参数p；正则化参数λ1,λ2；梯度下降参数L。

输出：矩阵AB，属性选择向量α。

1.初始化t=0；

2.初始化矩阵A,D，α为单位向量；

3.计算属性核矩阵K(i)∈Rn×n；

4.repeat

4.1.根据式(21)，更新B(t+1);/*表示第t+1次迭代的B*/

4.2.根据式(26)，更新A(t+1);/*表示第t+1次迭代的A*/

4.3.更新对角矩阵D(t+1);/*表示第t+1次迭代的D*/

4.4.根据式(37)和式(38)，更新α(t+1);

4.5.更新t=t+1;

4.6.Until目标函数式(12)收敛；

5.end

4 算法收敛性证明

因为从目标函数式(12)中可以很清楚地看到它是非平滑的，它不仅有3个变量A,B,α需要优化求解，而且它的正则化项也是非平滑的，所以在目标函数收敛性证明上还是存在一定的难度。但是，本文提出了一种有效的方法，下面是目标函数收敛性证明的具体过程。

从算法2中4.1到4.6迭代到第t次产生的结果：

〈A(t+1),B(t+1),α(t+1)〉=

λ1tr(BTATD(t)AB)+λ2‖α‖1

(39)

从而可以得到：

(40)

其中，令G(t)=A(t)B(t),G(t+1)=A(t+1)B(t+1)，由式(17)构成的对角矩阵D，代入式(40)可以得到：

(41)

(42)

然后，结合式(42)就可以得到：

(43)

综合以上所述，可以得到如下结果：

(44)

接下来，证明α优化的收敛性。

定理1假设{αt}是由算法1产生的序列，那么对于任意t≥1时，就有以下式子成立：

(45)

定理1的证明可以参考文献[13]，该定理表明了近端梯度下降算法收敛计算复杂度为O(1/t2)，其中t表示的迭代次数，同时也表明了式(31)是收敛的。

结合以上不等式和定理1就能证明目标函数是单调递减的，所以目标函数是收敛的。

5 相关理论实验结果与分析

5.1 实验数据集和对比算法

本文采用了10个常用的做属性选择的数据集，并且在数据集上测试本文提出的KSFS算法和近几年比较优秀的属性选择对比算法，通过实验结果比较算法的性能和效果。实验数据集的具体相关信息如表1所示。

Table 1 Data set information statistics表1 数据集信息统计

本文所有实验都在Windows 7系统环境下运行的，使用Matlab 2014a编译器编写实验算法和测试实验效果性能。对比实验选取了5种对比算法，将其实验所得的结果与本文提出的KSFS算法所的结果进行比较。本文所有算法都采用10折交叉验证方法和选择不同的参数对实验结果进行评估，实验所选择的分类器为Matlab工具箱中的SVM分类器，且分类器中参数(c,g)∈[-10:2:10]，分类器类型都选择非线性模式。

以下分别介绍5种对比算法：

(1)FSPG(Feature Selection for linear SVM with Provable Guarantees)算法[14]：是一种改进的SVM的属性选择算法。它可以用来做有监督的学习算法，也可以用来做无监督的学习算法，通过调节参数来选择属性选择模型，从而确定它是有监督的还是无监督的，本文选择有监督学习模型作为对比算法。它是基于支持向量来提取特征的，在最坏的情况，保证了局部特征空间的边缘距离在全局特征空间的边缘距离误差范围之内，从而达到属性选择的目的。

(2)Lasso(high-dimensional feature selection by feature-wise kernelized Lasso)算法[15]：是一个有监督学习属性选择算法，是在输入特征和输出值之间建立一种非线性依赖关系来进行高效的属性选择，其目的是通过引入核函数挖掘输入特征数据与输出值之间的非线性关系。通过求解非负约束的Lasso优化问题、对偶增广拉格朗日方法有效地求解问题，最终得到全局最优解。

(3)FSSL(joint Feature Selection and Subspace Learning for cross-modal retrieval)算法[16]：是一种有监督学习模型的算法。它是在跨模态检索领域为了解决数据相关性度量和特征选择问题所提出的一种属性选择算法，通过投影矩阵将数据投影到一个公共的子空间上，并在投影过程中同时选择不同空间的相关性特征和判别特征，保证了数据间和数据内的结构相似性，此外在映射时引入L2,1范数正则项实现稀疏化，达到属性选择的效果。

(4)ERFS(Efficient and Robust Feature Selection via jointL2,1-norm minimization)算法[17]：是一种具有高效和鲁棒性的有监督属性选择算法。它的损失函数是基于L2,1范数回归的损失函数，在数据特征提取和消除噪声特征方面有很大作用。正则项部分也是基于L2,1范数，能够对所有数据点特征进行关联性稀疏，从而实现特征选择的效果。

(5)CSFS(a Convex formulation for Semi-supervised multi-label Feature Selection)算法[18]：是一种利用半监督学习方式结合了稀疏学习模型，并引入L2,1范数的正则化项来进行属性选择的算法。但是，并没有考虑数据的全局结构和属性之间的关系，所以属性选择效果也不是很理想。

5.2 实验结果和分析

本文中对比算法的实验参数按照参考文献设置，本文的KSFS算法实验相关参数分别有r，λ1∈{108,109,1010,1011},λ2∈{0.05,0.06,0.07,0.08,0.09}，L2,p范数中参数p取值为0

在进行分类任务之前，在10个数据集上测试本文算法，同时也证明了本文 KSFS算法的目标函数是收敛的。从图1～图10我们可以看出，本文提出的属性选择模型可以很好地拟合属性和类标签之间的关系，通过实验发现，当梯度下降的参数在可控的范围之内，L选取最大值时，目标函数的收敛速度越快，梯度下降参数L为10时，目标函数的收敛速度是最快的，图1～图10是L为10时目标函数在每个数据集上的收敛图。

Figure 1 Convergence plot of the target function on Colon图1 目标函数在Colon上的收敛图

Figure 2 Convergence plot of the target function on Ecoli图2 目标函数在Ecoli上的收敛图

Figure 3 Convergence plot of the target function on Yale图3 目标函数在Yale上的收敛图

Figure 4 Convergence plot of the target function on Isolets图4 目标函数在Isolets上的收敛图

Figure 5 Convergence plot of the target function on PCMAC图5 目标函数在PCMAC上的收敛图

Figure 6 Convergence plot of the target function on Madelon图6 目标函数在Madelon上的收敛图

Figure 7 Convergence plot of the target function on Multiple图7 目标函数在Multiple上的收敛图

Figure 8 Convergence plot of the target function on SECOM图8 目标函数在SECOM上的收敛图

Figure 9 Convergence plot of the target function on CNAE图9 目标函数在CNAE上的收敛图

Figure 10 Convergence plot of the target function on CCUDS图10 目标函数在CCUDS 上的收敛图

实验采用样本分类准确率作为属性选择效果好坏评价的指标，样本分类准确率越高，表明属性选择算法性能越好，反之属性选择算法性能越差。本文所有实验采用10折交叉验证方法，来验证KSFS算法和对比算法的性能，把数据集按照10折交叉验证方法分为10折，其中9折作为训练集，1折作为测试集，并且选用SVM分类器进行分类，就可以得到不同属性选择算法的分类准确率。为了确保实验的公平性和准确性，本文所有算法都在同一实验环境下进行。最终把实验10次运行结果的平均值和均方误差作为属性选择算法性能评价的指标。最后把每个算法的实验结果在10个公开数据集上绘制成对比图，如图11～图20所示，相关算法具体实验数据结果，如表2所示。

Figure 11 Accuracy of algorithms on Colon图11 各算法在Colon上的准确率

通过图11～图20和表2所示的实验结果可以看出，本文所有算法在10个公开数据集上的分类准确率，因为10折交叉验证的随机性，所以并不能确保KSFS算法每次的实验结果都高于其他算法。但是，KSFS算法在每个数据集上的10次实验结果大部分比对比算法要好，而且最终的平均准确率也是最高的。通过表2分析得出，KSFS算法与其他5种对比算法相比，其平均分类准确率均高于其他算法，同时通过表3可知，KSFS算法在10个数据集上运行所用的时间比对比算法所用的时间要少很多。与半监督属性选择CSFS算法相比较，平均分类准确率提高了近7%，说明充分利用好数据的类标签，对提高分类准确率是非常重要的；与经典的FSSL算法相比较，平均分类准确率提高了2%，从而更好地证明了本文KSFS算法比单纯的子空间学习算法性能要好很多，同时运用了低秩约束的方法，去除冗余的属性和噪声样本，充分考虑数据之间的全局结构，不断调整属性选择的结果，从而使之达到最优。在庞大样本数量的Isolets和PCMAC等数据集上低秩约束的方法效果比较显著，分类准确率提高了2%～3%；其次与近几年比较优秀的属性选择算法FSPG和Lasso、ERFS相比都有比较好的效果。通过引入核函数进行属性选择充分挖掘了属性与类标签之间的非线性关系，采用低秩约束的方法充分考虑了数据之间的全局结构，所以本文提出的算法有比较好的效果。

Table 2 Statistical results of classification accuracy表2 分类准确率(±均值方差)统计结果

Table 3 Running time statistics of the algorithm on data sets 表3 算法在数据集上的运行时间统计结果 s

Figure 12 Accuracy of algorithms on Ecoli图12 各算法在Ecoli上的准确率

Figure 13 Accuracy of algorithms on Yale图13 各算法在Yale上的准确率

Figure 14 Accuracy of algorithms on Isolets图14 各算法在Isolets上的准确率

Figure 15 Accuracy of algorithms on PCMAC图15 各算法在PCMAC上的准确率

Figure 16 Accuracy of algorithms on Madelon图16 各算法在Madelon上的准确率

Figure 17 Accuracy of algorithms on Multiple图17 各算法在Multiple上的准确率

Figure 18 Accuracy of algorithms on SECOM图18 各算法在SECOM上的准确率

Figure 19 Accuracy of algorithms on CNAE图19 各算法在CNAE上的准确率

Figure 20 Accuracy of algorithms on CCUDS图20 各算法在CCUDS 上的准确率

6 结束语

本文结合核函数和稀疏学习提出了一种新颖的有监督属性选择算法—KSFS算法。该算法将核函数嵌入到稀疏学习模型中，将原始数据集投影到高维核空间，使得原始数据集在高维核空间中具有更高的可分性，进一步在核空间上进行属性选择；在此基础上利用L1范数正则化惩罚模型，避免模型过拟合，减小了计算误差；同时，利用L1范数作为属性选择评分机制，选出重要的样本属性。该算法在回归模型的基础上，结合低秩约束的方法弥补了数据几何结构方面的不足之处。实验结果显示，本文算法在分类准确率和稳定性上都有了较大的提升，所以KSFS算法可以得到比较好的属性选择效果。在接下来的工作中，将尝试用半监督学习的属性选择方法扩展本文所提出的算法，并尝试使用更好的方法来降低算法的计算复杂度和提高算法的稳定性。