低秩约束的非线性属性选择算法

张乐园，李佳烨，李鹏清

(广西师范大学 计算机科学与信息工程学院，广西 桂林 541004))(*通信作者电子邮箱zhang7681193@163.com)

0 引言

图像处理[1-2]和数据挖掘等领域常用高维的矩阵来存储数据[3]。高维的矩阵在存储大量信息的同时，也会带来属性冗余、占用大量存储空间等问题。为了能够提取这些数据的有效信息，并提升处理效率，需要对这些数据进行预处理。因此属性约简成为了越来越重要的一个研究领域[4]。

属性选择是常见的属性约简方法。它主要是按照某种标准从纷繁杂乱的属性中选出能够最好表示出数据的原始属性的子集。属性选择广泛应用于模式识别、机器学习以及其他领域中[5-6]。之前的大部分研究都是基于线性条件下的属性选择，然而现实生活中的数据之间往往不是恰好线性的关系，有时需要去更多地考虑数据之间的非线性关系，因此可以引入核函数来实现非线性的属性选择[7]。

本文提出了一种基于核函数的属性自表达无监督属性选择算法——低秩约束的非线性属性选择算法(Low Rank Non-linear Feature Selection algroithm, LRNFS)。首先,用核函数将数据的每个属性映射到核空间上，在核空间中这些数据是线性可分的，然后在核空间上进行线性属性选择，即相当于进行了非线性属性选择[8]。其次用得到的属性核矩阵去作属性选择，同时通过属性自表达和偏差项得到一个自表达矩阵[9]，去解决无监督属性选择方法中无类标签的问题；然后在线性回归的模型框架中进行低秩属性选择，其中低秩属性选择运用了稀疏(利用l2,1-范数来去除冗余的属性)和低秩(假设矩阵具有低秩，以此来排除噪声的干扰)两种方法[9]。最后，提出一种新的优化方法，即对目标函数按顺序迭代执行低秩属性选择和l1-范数处理[10]的优化求解算法，不断交替迭代使得结果达到最优，最终取得全局最优解。由于本文引入了核函数进行非线性属性选择，所以比一般的线性属性选择学习方法具有更好的效果。实验结果表明，所提算法在分类准确率上能够达到较好的效果。

1 相关工作

参考模式识别理论[11]可知，低维空间中线性不可分的数据可以通过映射到高维空间中去实现线性可分。但是如果直接将低维数据映射到高维空间上进行机器学习的相关工作，将在高维空间上运算中出现“维数灾难”[12]，因此引入核函数这一概念来降低其计算复杂度。

设x,z∈X,X⊆Rn，非线性函数Φ实现低维数据集X到高维空间F上的映射，这里F⊆Rm,n≪m。由核方法可得：

K(x,z)=〈Φ(x),Φ(z)〉

(1)

其中：〈,〉为內积；K(x,z)为核函数。引入式(1)中核函数可以巧妙地把高维空间上的內积运算转化成低维空间上的计算，因此可以避免高维空间中高计算复杂度等问题，这样可以实现在高维空间中的一些机器学习问题。

依据Mercer定理，去确定一个核函数并不难[11]。常用的核函数有如下几种：

1)高斯核函数K(x,xi)=exp(-‖x-xi‖2/(2σ2))；

2)多项式核函数K(x,xi)=(x·xi+1)d,d=1,2,…,N；

3)感知器核函数K(x,xi)=tanh(βxi+b)；

4)样条核函数K(x,xi)=B2n+1(x-xi)。

目前，核函数在机器学习领域已经得到广泛的应用，它具有以下优点：

1)避免了“维数灾难”，降低了计算复杂度；

2)函数Φ的具体形式和参数不需要知道；

3)核函数通过其形式和具体参数的调整可以改变低维空间到高维核空间的映射，从而对高维核空间的性质产生影响，最终改变各种核方法的性能；

4)核方法可以应用到不同的算法中，从而将一些线性算法转换为非线性的算法，并且可以对于不同的应用选取不同的核函数。

2 算法介绍与优化

2.1 符号表示

用K(i)表示第i个属性映射到高维核空间上所对应的核矩阵。对于一个矩阵X=[xij]，它的第i行和第j列表示为Xi和Xj。矩阵X的迹表示为tr(X),XT代表矩阵X的转置。同时，把矩阵X的Frobenius范数和l2,p-范数分别表示为：

2.2 LRNFS

一般情况下，作属性选择时，通常把一个数据集表示为X∈Rn×d的形式，在有监督学习情况下，属性选择模型[9]为：

(2)

其中φ(W)是关于W的正则化因子。大部分情况下，数据之间的关系都不刚好是线性关系，式(2)通常不能表示出数据之间的非线性关系，因此需要引入核函数来对本文的目标函数来进行改进。

参考广义多核学习(Generalized Multiple Kernel Learning, GMKL)算法[8]，上面目标函数可以变成:

K(i)∈Rn×n,Y∈Rn×c,W∈Rn×c,α∈Rd×1

(3)

这样，W并不能起到对属性进行选择的作用，所以需要引入新的属性选择系数向量α，因此这里对W不用l2,1-范数，而是用l2-范数，它比较容易优化。对于α用一个l1-范数去得到稀疏的结果，显然，α是一个有d个元素的向量。如果α某个位置是0，对应X的那个属性就是被当作冗余的属性。

式(3)中的模型将数据的相似性和选择特征一起考虑。尽管它被广泛应用于许多属性选择方法中，但很难去选择合适的响应矩阵。由于属性的自表征性质的存在，本文提出了一个用于无监督属性选择的的正则化自表征模型。本文提出的模型简单地利用矩阵X作为响应矩阵，每个属性可以被所有属性很好地表示出来。对于每个X中属性fi，将其表示为其他属性的线性组合：

(4)

那么对于所有属性有:

(5)

通过将每个属性作为一项任务去预测，并使用l2,p-范数正则化项去约束任务之间的稀疏性。然后，定义了一个新的属性自表征目标函数如下：

λ2‖α‖1}

(6)

其中：λ1和λ2是控制参数，分别去影响系数矩阵W和向量α的稀疏性；l1-范数正则化项‖α‖1同时惩罚α中所有的元素去实现在属性选择向量α的稀疏来作出属性的选择和不选择的决定；p(0

在实际应用中，通常会发现噪声或异常数据会增加自表征系数矩阵的秩[13]，所以，低秩约束在处理高维数据时就显得特别合理。对W的秩施加约束[13]，即：

rank(W)=r；r≤min(n,d)

(7)

其中：n和d分别是样本和属性的数量。这样，对于W的低秩约束可以自然地表示为如下两个r秩矩阵的乘积：

W=AB

(8)

其中：A∈Rd×r,B∈Rr×d。那么最终的目标函数变为：

λ2‖α‖1}

(9)

其中：X∈Rd×r；λ1、λ2都是可调节参数。

2.3 优化过程

这一节给出目标函数式(9)的优化过程。由于本文用l2,p-范数去除异常值样本以及用l1-范数去实现属性选择，目标函数不能求出一个闭式解。同时，对于4个变量A、B、b、α，目标函数不是共凸的。因此，参照具有收敛速度快、逼近真实值等优点的迭代重新加权最小二乘法(Iteratively Re-weighted Least Squares, IRLS)[14]的思想，本文提出了一种新的用A、B、b、α迭代优化的方法。详细地说，本文迭代地执行以下三个步骤直到满足预定条件。

1)用固定的α、A、B更新b。

当α、A、B被固定，目标函数式(9)中的后面两项都可以被看作常数，其关于b的导数自然为0。将目标函数式(9)对b进行求导，令其为0：

(10)

经过简单计算得出：

b=(eTX-eTZAB)/n

(11)

2)用固定的α、b更新A、B。

把式(11)带入式(9)可以得到：

λ1‖AB‖2,p}

(12)

令H=In-eeT/n,H∈Rn×n,In∈Rn×n是一个单位矩阵，式(12)可以重写为：

(13)

λ1tr(BTATQAB)

(14)

式中：P∈Rn×n,Q∈Rd×d，是两个对角矩阵。其中：

i=1,2,…,n,0

(15)

(16)

对B求导,令其为0可以得到：

B=(AT(ZTHTPHZ+λ1Q)A)-1ATZTHTPHX

(17)

把式(17)代入式(14)可得：

λ1Q)A)-1ATZTHTPHXXTHTPTHZA

(18)

注意到：

St=ZTHTPHZ+λ1Q

(19)

Sb=ZTHTPHXXTHTPTHZ

(20)

式中：St和Sb分别是线性判别分析(Linear Discriminant Analysis, LDA)中定义的总类散布矩阵和类间散布矩阵。因此式(18)的解可以写成：

(21)

3)用固定的A、B、b更新α。

(22)

令K(i)W=Q(i)∈Rn×d,式(22)等价为：

λ2‖α‖1}

(23)

(24)

λ2‖α‖1}

(25)

(26)

(27)

令：

式(27)可以记为:

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

(28)

α的l1-范数使用一般的方法并不能得优化出来，这里使用加速近端梯度下降(Accelerated Proximal Gradient Descent, APGD)算法[10，15]来对α的l1-范数进行优化求解，具体过程如下：

(29)

Gηt(α,αt)=f(αt)+〈▽f(αt),α-αt〉+

ηt‖α-αt‖2/2+λ2‖α‖1

(30)

λ2‖α‖1/ηt}

(31)

令Ut=αt-▽f(αt)/ηt,有：

λ2‖α‖1/ηt}

(32)

令αi表示α的i第个分量，将式(31)按照分量展开可以看出，其中不存在αiαj(i≠j)这样的项，所以式(31)有如下闭式解：

(33)

同时，为了加速式(29)中的近似梯度法，本文进一步引入辅助变量V(t+1)，即:

V(t+1)=α(t)+(α(t+1)-α(t))(β(t)-1)/

β(t+1)

(34)

其中系数β(t+1)通常设置为:

(35)

至此，对于目标函数式(9)的优化已经完成，可由下面的算法1给出其具体的伪代码。

算法1 求解式(9)的伪代码。

输入η(0),β(1)=1,γ,X∈Rn×d，λ1,λ2,p,r；

输出α。

初始化t=1;

随机初始化α(1)∈Rd×1，P(1)为一个n×n对角阵，Q(1)为一

个d×d对角阵，令V(1)=α(1)；

repeat；

更新A(k+1)基于式(21)；

更新B(k+1)基于式(17)；

更新b(k+1)基于式(11)；

计算P(k+1)基于式(15)；

计算Q(k+1)基于式(16)；

whileF(α(t))>Gη(t-1)(πη(t-1))(α(t),α(t)) do

setη(t-1)=γη(t-1)；

end while

setη(t)=η(t-1)；

计算β(t+1)基于式(35)；

计算V(t+1)基于式(34)；

t=t+1；

unitil式(9)收敛。

2.4 收敛性证明

下面说明α优化的收敛性。

定理1 设{α(t)}是由算法1产生的序列，那么对于∀t≥1，式(36)成立:

(36)

定理1的证明详见文献[16]。定理1表明本文所用的加速近似梯度算法的收敛率为O(1/t2)，其中t是算法1的迭代次数。

接下来可以证明式(13)中的目标函数值在每次迭代中单调递减。目标函数式(13)等价于：

λ1tr(BTATQAB)

(37)

即要证明：

tr((HX-HZA(t+1)B(t+1))TP(t)(HX-HZA(t+1)B(t+1)))+

λ1tr((B(t+1))T(A(t+1))TQA(t+1)B(t+1))≤

tr((HX-HZA(t+1)B(t+1))TP(t)(HX-HZA(t)B(t)))+

λ1tr((B(t))T(A(t))TQA(t)B(t))

(38)

令Y=HX-HZAB，然后可以得到：

(39)

对于每个i，能够得到如下不等式：

(40)

对于每个j，可以得到：

(41)

由式(40)和式(41)可得：

(42)

然后合并式(39)和式(42)可得：

(43)

得证

通过上面分析可以看出，每次迭代过程中目标函数式(9)的值是单调递减的，同时目标函数式(9)对于A、B、b是凸函数，因此依据式(38)以及定理1可以得出目标函数式(9)会逐渐收敛到全局最优解。

3 实验结果及分析

3.1 实验数据集和对比算法

本文在6个数据集[17]上测试所提出的属性选择算法的性能，Glass、Hill-Valley1(含有大量噪声)、Hill-valley2(没有噪声)、Yale、Colon、Arrhythmia数据集详情如表1所示。

所有实验均在Windows 7系统下使用Matlab 2014a软件进行测试。选择5种对比算法来与本文算法LRNFS进行比较，有：

1)LDA[18]：是一种全局子空间学习方法，旨在最大限度地减少类间距离，同时在进行特征选择时最大化类间距离。

2)结构化最优图特征选择(Structured Optimal Graph Feature Selection, SOGFS)算法[19]：给出了一种进行特征选择和保持局部结构学习的无监督属性选择算法，同时适应性地去确定相似度矩阵，对相似度矩阵的限制可以保留更多的数据结构的信息。

3)重新调整的线性平方回归(Rescaled Linear Square Regression, RLSR)算法[20]：提出了一种可以学习投影矩阵的全局和稀疏解的新型半监督特征选择方法，在最小二乘回归中用一组比例因子调整回归系数，这些比例因子用于对各属性进行排名。

4)正则化自表征(Regularized Self-Representation, RSR)算法[21]：通过范数来规范化自表征系数矩阵以选择具有代表性的属性，并确保对离群点的健壮性。

5)希尔伯特-施密特独立标准压缩(Hilbert-Schmidt Independence Criterion Lasso, HSICLasso)估计算法[22]:通过核函数的映射使得数据线性可分，同时用Lasso来对属性权重向量进行稀疏，从而实现属性约简。

3.2 结果分析

本文采用分类准确率作为评价指标，分类准确率越高表示算法效果越好，并且引入P_value进行算法之间的显著性差异分析。实验通过10折交叉验证的方法把原始数据划分为训练集和测试集，再使用LIBSVM工具箱[23]在支持向量机(Support Vector Machine, SVM)上对使用各算法进行属性选择之后的数据集进行分类，得出其分类准确率。对于每个算法在每个数据集上进行10次实验并取10次实验结果的均值作为最终的分类准确率，这样可以降低实验过程中的偶然性，并取其标准差来预测模型的稳定性。

表1 实验中使用的数据集Tab. 1 Datasets used in the experiment

在各数据集上不同算法进行属性选择之后的分类准确率如图1所示。由图1可以看出，LRNFS在绝大多数情况下是优于对比算法的。由于Hill-Valley1数据集中含有大量噪声，所以各算法的分类准确率的波动比较大，导致有部分实验中效果比对比算法略差，但整体还是优于对比算法的，这点在表2中可以证实。

图1 不同数据集上各算法的实验结果Fig. 1 Experimental results of different algorithms on different datasets表2 不同属性选择算法在不同数据集上的分类准确率Tab. 2 Classification accuracy of different feature selection algorithms on different data sets

算法分类准确率均值/%glassHill-Valley1Hill-valley2YalecolonArrhythmia分类准确率标准差/%glassHill-Valley1Hill-valley2YalecolonArrhythmia平均准确率均值/%平均准确率标准差/%P_valueLDA69.6172.3475.0074.3664.5554.710.902.502.151.310.200.2168.431.200.0541SOGFS69.8172.3481.9073.5884.4070.531.002.501.041.070.870.9075.431.230.0030RLSR70.3972.5880.0973.5284.1070.570.961.421.421.581.190.6975.211.210.0046RSR70.1671.7381.5073.3984.2470.331.463.121.291.881.300.6275.231.610.0023HSICLasso68.0275.5680.9475.0983.2168.351.260.790.420.771.530.7175.200.910.0622LRNFS71.5774.1083.0876.2985.1071.671.282.821.151.221.080.5176.971.34—

各属性选择算法在不同数据集上的分类准确率如表2所示。从表2可以看出，LRNFS的平均分类准确率较传统的LDA提升了12.48%，较SOGFS提升了2.04%，较RLSR提升了2.34%，较RSR和HSICLasso分别提升了2.31%和2.35%。SOGFS、RLSR和RSR均是近几年性能较优的属性选择算法，在使用径向基函数(Radial Basis Function, RBF)核的SVM的情况下，本文方法的分类准确率得到了明显的提升。由此可以看出，LRNFS在属性选择的时候拥有较优的性能。从P_value可以看出，由于LRNFS采用了LDA思想和HSICLasso中核函数方法，所以其P_value值分别达到了0.054 1和0.062 2，而与其余对比算法的P_value都在0.01以下。

4 结语

本文在线性属性选择的基础上引入核函数，考虑了数据之间的非线性关系，并解决了数据在低维特征空间上线性不可分的问题，提升了属性选择的准确率。但引入核函数的同时，计算复杂度增加了，这是需要进一步解决的问题，而且通过实验结果可以看出，LRNFS的鲁棒性还有待提升。接下来的工作中，将拓展LRNFS为半监督属性选择算法，并逐步改进其计算复杂度和鲁棒性。