自适应稀疏表示引导的无监督降维

岳 琴，魏 巍，2，冯 凯，2，崔军彪

1) 山西大学计算机与信息技术学院，山西太原030006；2)山西大学计算智能与中文信息处理教育部重点实验室，山西太原030006

随着数据维数的增加，传统机器学习算法的性能及可解释性都受到了严重影响．降维是缓解“维度灾难”[1]的一种有效手段．根据降维过程中所使用监督信息的多少，降维可被分为有监督降维[2-4]、半监督降维[5-7]和无监督降维．无监督降维指不利用任何监督信息的降维，它通常以保持某种数据分布信息(如几何信息和统计信息等)为准则[8]．然而，在高维场景中，如何有效挖掘数据分布信息是非常困难的．因此，相比其他两种降维方法，无监督降维更具挑战性．根据保持的数据分布信息的不同，无监督降维又可分为保持数据分布的局部信息降维和保持数据分布的全局信息降维两种．经典的保持数据分布局部信息的无监督降维方法有局部线性嵌入(locally linear embedding, LLE)[9]和局部保持投影(locality preserving projection, LPP)[10]等．LLE保持的是局部线性重构关系，在原始高维空间学习近邻线性重构系数，在低维空间中保持学到的线性重构关系．LPP保持的是样本间的局部相似性．由于LPP的相似性图是预先定义的，所以降维的结果很大程度上依赖于图的构建，而图构建本身是一个开放性问题，自适应图构建[11]是解决此问题的有效方法．图优化局部保持投影(graph-optimized locality preserving projections, GOLPP)[12]将图构建和降维任务统一到一个框架中，实现了图构建和降维相互指导，使得到的图对于具体任务是最优的．与GOLPP不同，自适应近邻投影聚类(projected clustering with adaptive neighbors, PCAN)[13]保持的是概率近邻图，若样本对是近邻的概率大，则该样本对降维后的距离近．经典的保持数据分布全局信息的无监督降维方法有多维缩放(multiple dimensional scaling, MDS)[14]、等度量映射(isometric mapping, IOSMAP)[15]和稀疏保持投影(sparsity preserving projections, SPP)[16]等．MDS保持降维前后样本间的欧式距离不变；IOSMAP保持降维前后样本间的测地距离不变；SPP通过稀疏表示挖掘数据分布的全局信息，在低维空间中保持学到的全局线性重构关系．为挖掘更多数据分布信息，QI等[17]提出基于自表示和邻接学习的维度约简(dimensionality reduction via representation and affinity learning, DRRAL)，采用文献[18]的模型进行邻接矩阵的学习并指导降维．HINTON等[19]利用神经网络学习高维数据的低维表示(自编码器)提出基于神经网络的维度约简方法．为学到更鲁棒的特征，ABAVISANI等[20]提出基于自动编码模型的稀疏深度编码．

在实际应用中，高维数据的潜在分布往往是复杂的，单独采用全局或局部的方法很难完全捕获数据的分布信息[21]．为同时挖掘数据分布的全局信息和局部信息，本研究提出一种自适应挖掘数据分布的局部和全局信息的无监督降维(adaptive sparse representation guided unsupervised dimensionality reduction, ASR_UDR)方法，用稀疏表示挖掘数据的类簇结构，再将稀疏表示的系数约束为凸组合，可直观地刻画样本间的概率近邻关系，并在投影后的低维数据中保持该关系，最后将上述两个过程统一到一个框架中，让二者相互指导，实现数据分布信息的自适应挖掘与数据降维．

1 基础知识

1.1 符号描述

给定数据集X=(xji)∈RD×n，xji为第i个样本的第j个特征．降维后的数据集为Y=(yji)∈Rd×n，d

1.2 稀疏表示与稀疏子空间聚类

稀疏表示指用所有样本的线性组合重构第i个样本，在重构系数si上加l0范数正则项，要求系数是稀疏的．在线性子空间中，si中的非零元素表示与样本xi在同一子空间中的样本在重构该样本时的贡献，表达式为

(1)

式(1)的求解是一个非确定性多项式困难(nondeterministic polynomially hard, NP-hard)问题，一般用l1范数近似l0范数，则式(1)重写为

(2)

将稀疏表示的重构系数用作邻接矩阵系数，此时当子空间是相互独立时，邻接矩阵S呈稀疏块对角结构，每一块对应一个子空间．

1.3 局部保持投影

局部保持投影目的是挖掘高维空间中的数据邻域信息并在低维数据空间得以保持[10]．其中，高维数据的邻域信息是通过邻接矩阵刻画的．算法步骤为：

1)构建邻接矩阵S=(sij)∈Rn×n． 若两个样本xi与xj相近，则节点i和节点j之间用边相连，且不同样本间边的权重sij不同．具体构建方法为

(3)

其中，Nk(xi)为xi的k近邻集合．

2)特征映射．在投影后的低维空间中若要保持高维空间中数据的邻域信息，则目标函数为

(4)

最小化后等价为

(5)

(6)

2 稀疏表示引导的无监督降维

2.1 模型构建

降维目的是在保持数据分布信息的前提下减少数据维度：一方面，将稀疏子空间聚类思想用于维度约简，用子空间学习挖掘到的数据分布的全局信息指导降维；另一方面，在降维中引入局部保持投影，并将子空间学习和降维统一到一个框架中，完成自适应地挖掘数据分布的全局信息和局部信息与降维相互指导的过程．目标函数为

(7)

其中，α为稀疏表示中重构误差和稀疏正则项的平衡参数；β为用于平衡全局和局部信息的参数．目标函数中的第1项是稀疏表示的目标函数，用来挖掘数据分布的全局信息；第2项是用稀疏表示的系数矩阵构建邻接图，使降维后的样本保持该图上的平滑性，即在图上相似的样本降维后也相似．为避免平凡解，增加约束项PTXHXTP=I， 约束降维后的特征与特征之间线性无关．其中，I为单位矩阵；H=I-(1/n)FFT是中心化矩阵，F为元素全为1的n×1维矩阵．为使稀疏表示的系数矩阵能更好地反映样本之间的相似性，采用除样本以外的其余样本的凸组合重构目标样本．凸组合系数具有天然的概率意义，稀疏性能直观地反映数据分布的局部信息．在降维过程中，若样本对(xi,xj)是近邻的概率大，则希望降维后的样本对(yi,yj)近．同时，降维后的样本也指导相似性矩阵的学习，即若(yi,yj)远，则希望该样本对的相似性小．所以，最终的优化模型为

(8)

2.2 模型的求解

采用交替优化方法求解优化问题(8)．首先，固定S，优化P， 则优化问题可写为

s.t.PTXHXTP=I

(9)

式(9)可等价为

s.t.PTXHXTP=I

(10)

上述优化问题对应一个广义特征值分解问题，

XLXTp=λXHXTp

(11)

其中，p为特征值λ对应的特征向量．

式(11)的最优解P*为由d个最小的广义特征值对应的特征向量组成的矩阵，具体的构造过程可参考文献[10]．

其次，固定P， 优化S， 则式(8)可写为

(12)

其中，yi=PTxi是第i个样本的低维表示．

(13)

对目标函数进行化简，可得

(14)

其中，F为元素全为1的n×1维矩阵.

由式(14)可见，S的每列都相互独立，可单独进行优化．对于S的第i列si， 去掉与目标函数中与si无关的常量后可得

(15)

优化问题(15)是一个凸的二次规划问题，可采用求解二次规划的算法[22]进行求解．

2.3 算法的描述

自适应稀疏表示引导的无监督降维算法描述见图1，算法收敛准则设为连续两次迭代目标函数值的差的绝对值小于1×10-5．

输入:数据矩阵X∈RD×n, 超参数α和β, 降维后数据的维数d输出:数据的低维表示Y∈Rd×n1)初始化 S=0;2)迭代优化各变量while 不满足收敛条件 求解式(10)对应的广义特征值问题更新变量 P; 求解式(15)对应的凸二次规划问题更新矩阵 S的每一列;end while3)计算: Y=PTX结束

图1 自适应稀疏表示引导的无监督降维算法描述

Fig.1 The algorithm description of adaptive sparse representation guided unsupervised dimensionality reduction

3 实 验

3.1 数据集

实验共使用5个数据集，基本信息见表1．其中，WarpAR10P为人脸图像数据集；USPS为手写字体数据集；MultiB、DLBCLA和DLBCLB为3个基因数据集．

表1 实验所用数据集基本信息Table 1 The information of data sets used in this experiment 个

3.2 实验设置

对比算法包括原始的高维数据(baseline)和5种经典的无监督降维算法GOLPP[12]、PCAN[13]、DRRAL[17]、SPP[16]和全局和局部保持投影(global and local structure preserving projection, GLSPP)[23]．其中，GOLPP和PCAN是只考虑数据分布局部信息的无监督降维算法；DRRAL和SPP是只考虑数据分布全局信息的无监督降维算法；GLSPP算法同时考虑了数据的全局信息和局部信息．在实验中，各种算法的参数设置如下：

GOLPP算法是对LPP[10]算法的改进．在LPP算法中，样本之间的相似性矩阵是预定义的，缺乏自适应能力，为此，GOLPP算法将相似性矩阵的学习与降维过程统一在一个框架中，相互指导．该方法需初始化邻接矩阵S，本实验采用文献[12]的初始化方式：

(16)

PCAN算法的主要思想是利用欧式距离指导概率近邻的学习，从而指导降维．在实验中，类簇的个数设置为数据集真实的类别个数，另外两个参数采用文献[13]中的设置．

DRRAL是基于自表示的无监督降维方法，算法分两个阶段：① 用文献[18]算法得到相似性矩阵，超参数λ1=λ2=λ3=λ∈{0.1, 0.2, …, 1.0}， 簇的个数设为数据集的真实类别数；② 将得到的相似性矩阵用于指导降维．

SPP算法是用稀疏表示学习重构系数关系，在低维数据中保持该重构系数关系．本实验采用文献[16]中的优化问题(16)进行稀疏重构．

GLSPP算法利用k-means聚类发现数据的标签信息，从全局角度和局部两个角度保持该信息．其中，用于平衡全局和局部信息的超参数β∈{0.01, 0.1, 1, 10, 100}. 本研究方法超参数集合α∈{0.001, 0.005, 0.010, 0.050, 0.100}，β∈{0.001, 0.01, 0.1, 1, 10, 100, 1 000}．

除baseline算法外，其他算法降维后的维数d∈{50, 60, …, 120}. 首先，在所得数据的低维表示数据集上执行k-means聚类，类的个数为真实类别数，类中心采用随机方法进行初始化.然后，计算k-means聚类得到的类标签向量与真实类标签向量的聚类精度(accuracy, ACC)和归一化互信息(normalized mutual information, NMI).为降低k-means聚类的随机性，此过程重复50次，再求平均值，以此来衡量降维结果的质量．

3.3 结果及分析

表2和表3分别展示了7种方法在5个数据集上所有维度d∈{50, 60, …, 120}中的最优ACC值和NMI值，以及对于对应的维度.

%

1)括号内数值为对应的维数

%

1)括号内数值为对应的维数

由表2可见，与其他方法相比，本研究方法在5个数据集上的ACC值都有提升，升幅3.02%～8.20%．由表3可见，本研究方法的NMI值比其他方法在5个数据集上都有提升，升幅为0.01%～6.20%．这是由于本研究方法利用稀疏表示挖掘数据分布的全局信息，约束降维后的样本保持该信息，同时约束系数矩阵是凸组合，进而有概率近邻的含义，以此挖掘数据分布的局部信息，而且将数据分布的挖掘和降维统一到一个框架中，相互指导，自适应得到数据的低维表示．

3.4 参数敏感性分析

图2和图3分别展示了5个数据集在不同α和β值下，采用ASR_UDR算法得到的聚类ACC和NMI值实验结果．由图2可见，ASR_UDR算法的ACC指标对参数α和β不是很敏感，且当α相同时，算法的ACC指标对β不敏感；当β相同时，算法对α较为敏感．由图3可见，相比聚类ACC指标，ASR_UDR算法的NMI指标对α和β较敏感，且当α相同时，算法的NMI指标对β不敏感；当β相同时，算法对α较为敏感．在少量参数组合下，算法可达到较高性能．

图2 ASR_UDR方法在5个数据集上不同参数下的聚类ACCFig.2 (Color online) Clustering ACC on five data sets with different parameters for ASR_UDR

图3 ASR_UDR方法在5个数据集上不同参数下的聚类NMIFig.3 (Color online) Clustering NMI on five data sets with different parameters for ASR_UDR

结 语

挖掘并保持数据的分布信息是无监督降维的关键问题．本研究用稀疏表示挖掘高维数据的子空间结构用于指导无监督降维，同时用无监督降维的结构进一步指导稀疏子空间的学习，二者相互提升从而自适应地挖掘数据分布的全局和局部信息并完成降维．在大量真实高维数据集上的实验结果表明，本研究方法可在显著降低数据维数的同时，有效提升后续学习方法的性能．