基于子空间学习和伪标签回归的无监督特征选择

盛 超 宋 鹏 郑文明 赵 力

(1. 烟台大学计算机与控制工程学院, 山东烟台 264005; 2. 东南大学儿童发展与学习科学教育部 重点实验室, 江苏南京 210096; 3. 东南大学信息科学与工程学院, 江苏南京 210096)

1 引言

随着信息技术的迅速发展,在机器学习、模式识别等领域产生了大量的无标签高维数据。这些高维数据存在着大量的噪音和冗余数据,不仅会增加计算机的存储负担和处理时间,而且会降低算法的性能[1-2]。因此,如何更高效便捷的处理和使用这些高维数据已经成为一个非常重要的研究方向。处理高维数据的非常关键的一点则是去除无关的冗余特征,将有效的特征提取出来生成一个最优特征子集[3- 4]。在完成了对高维数据的处理后,后续对数据的使用将会变得更加高效和方便。

目前,特征提取和特征选择是两种重要的数据降维技术。特征提取方法并不考虑特征是否有用,只是单纯的将原始数据转换成一种容易识别的特定形式[5]。特征选择方法是从原始高维数据中选择一部分最能够表示数据信息的特征,以生成新的特征子集,它并不会改变原始的数据表示。根据是否包含标签信息,可以将特征选择方法大致分为有监督特征选择、半监督特征选择和无监督特征选择。有监督特征选择方法是指在进行特征选择之前数据的标签信息是已知的[6];半监督特征选择方法是只有一部分数据标签信息是已知的,这样可以通过已知的标签信息来提升方法的性能[7];与有监督和半监督特征选择方法相比,由于缺少数据的标签信息,无监督特征选择方法更加具有挑战性[8-11]。也正因为高维数据通常不含有标签信息,所以近些年来无监督特征选择引起了广泛的关注。

无监督特征选择方法分为过滤式[12]、包裹式[13]和嵌入式[14-15]三类。过滤式方法的特征选择过程是完全独立于学习算法的,通常是对特征进行打分排序,然后选择分数较高的特征,经典方法如Laplacian score[16]。独立于学习算法选择出来的特征可能并不适合特定的学习算法,为了解决这一问题,许多包裹式方法被提出。包裹式方法基于学习算法来选择特征。常见的包裹式方法包括greedy search[17]、floating search[18]和random search[19]等。但是包裹式方法对学习算法的依赖性过强,这在一定程度上限制了特征选择的性能。嵌入式方法是将特征选择的过程和学习算法结合起来。许多研究发现数据的局部流形结构中包含许多重要的信息,因此一些保持数据局部结构的特征选择方法被提出。如Cai等人提出了一种多聚类的特征选择方法(Multi-cluster feature selection,MCFS)[20],利用谱分析的理论来保持数据的局部结构,选择出来的特征可以很好的保持数据的谱聚类结构。Yang等人提出了一种L2,1范数正则化的判别特征选择(L2,1-norm regularized discriminative feature selection for unsupervised learning,UDFS)[21]。基于线性判别分析(Linear discriminant analysis,LDA)方法[22],UDFS利用线性分类器去预测数据的标签并标签来指导算法选择具有判别力的特征。对于处理高维数据,子空间学习作为降维的重要方法,也被应用到了特征选择中。如Shang等人提出的基于子空间学习的图正则化特征选择(Subspace learning based graph regularized feature selection,SGFS)[23],将子空间学习和图正则化结合到特征选择中,能够在处理高维数据的同时较好地保持数据的局部结构。在[24]中,Shang等人提出了基于局部判别的稀疏子空间学习特征选择(Local discriminative based sparse subspace learning for feature selection,LDSSL),通过将局部判别引入到子空间学习的特征选择中,可以很好地选择更有判别力的特征。

通过对近几年无监督特征选择算法的研究和分析,本文提出了一种基于子空间学习和伪标签回归的无监督特征选择方法。首先,为了更好地处理高维数据,我们将子空间学习和特征选择融合在统一框架中,并且对特征选择矩阵进行了L2,1范数的稀疏约束;其次,我们利用回归函数来学习特征子空间和伪标签之间的映射关系,从而选择出更具有判别力的特征;最后,在样本和特征空间分别加入图正则化来保持局部结构。因此,该方法能够有效地将包含数据有效信息的特征选择出来,完成对高维数据的处理。

2 基于子空间学习和伪标签回归的特征选择

为了能够更直观地描述本文提出的算法，图1给出了算法的框架图。

图1 提出方法的框架图Fig.1 The framework of proposed method

2.1 基于子空间学习的特征选择

对于高维数据,首先利用子空间学习找到一个较低维度的低维子空间,实现对原始数据的降维。假定X∈Rn×d为原始高维数据,n表示数据的数量,d表示特征的维度。可以通过以下损失函数来学习一个子空间:

(1)

其中H∈Rl×d是重构系数矩阵,用来映射学习到的子空间和原始数据空间之间的关系。XI∈Rn×l是学习到的子空间,|I|是子空间的维度。利用矩阵分解的原理,可以将子空间学习和特征选择结合起来,得到子空间学习特征选择的目标函数如下:

(2)

2.2 伪标签回归

缺乏标签信息是无监督特征选择存在的挑战之一。由于无法有效利用标签信息,很难选择出具有判别力的特征。为了解决这一问题,本文利用回归函数学习到的伪标签来指导特征选择,从而使得选择出来的特征更具有判别力。学习到的特征子空间和伪标签空间之间通常存在一种线性关系[25],通过回归函数来学习这种映射关系,得到的目标函数如下:

(3)

其中F∈Rn×c表示伪标签矩阵,c为数据类别的数量,P∈Rl×c为系数矩阵,用来映射特征子空间和伪标签空间之间的关系。这里采用L2,1范数来约束回归函数,提高模型的鲁棒性。

2.3 双图正则化

在高维空间中,数据的局部几何结构中通常包含着许多重要的信息[20]。充分挖掘这些局部信息可以提高算法的性能。这里我们引入两个图拉普拉斯分别保持样本空间和特征空间的局部结构。

2.3.1样本空间的局部结构保持

假定两个样本是相互接近的,那么它们各自的相关重构也应该接近。为了保持数据空间的局部几何结构,引入一个相似度矩阵Sd来表示数据之间的相似度。这里利用高斯热核函数计算样本之间的相似度,公式如下:

(4)

其中Nk(xi,:)表示xi,:的k个近邻。最终我们得到样本空间的局部结构保持目标函数如下:

(5)

式中Ld=Dd-Sd为拉普拉斯矩阵,[Dd]ii=∑j[Sd]ij为对角矩阵,Tr(·)表示矩阵的迹。

2.3.2特征空间的局部结构保持

同样地,把矩阵的每一列看成一个特征,寻找特征空间的局部几何结构。利用高斯热核函数求得不同特征之间的相似度矩阵Sf,公式如下:

(6)

其中Nk(x:,i)表示x:,i的k个近邻。最终我们得到特征空间的局部结构保持公式如下:

(7)

式中Lf=Df-Sf为拉普拉斯矩阵,[Df]ii=∑j[Sf]ij为对角矩阵。

最后,将子空间学习特征选择(2)、伪标签回归(3)、样本空间的局部结构保持(5)和特征空间的局部结构保持(7)结合到统一的框架中,得到最终的目标函数。如下:

s.t.W,H,F,P≥0,WTW=Il,FTF=Ic

(8)

其中α、β和λ为平衡参数。

3 优化求解

对于提出的目标函数(8),其包含L2,1范数,是非光滑的,很难直接对其进行优化求解。因此,本文提出了一种迭代更新的方法来进行优化求解,即在求解一个变量时保持其他变量不变。下面给出了具体的优化求解过程:

(9)

其中γ和γ1是平衡参数。

(1)对W进行求解,固定H,F,P,U和Q。使用KKT条件(Karush-Kuhn-Tucker)[25],令δijWij=0,得到W的更新公式:

(10)

(11)

(3)对F进行求解,固定W,H,P,U和Q。使用KKT条件,令θijFij=0,得到F的更新公式:

(12)

(4)对P进行求解,固定W,H,F,U和Q。使用KKT条件,令ηijPij=0,得到P的更新公式:

(13)

最终,我们得到四个变量的求解公式,对它们进行迭代更新求解,直到满足迭代次数或收敛条件。

4 时间复杂度分析

本节给出算法的时间复杂度分析,以证明算法的可行性。通过对公式(8)进行分析,算法主要包括子空间学习、伪标签回归、图约束和L2,1范数约束。d为数据的维度,n为数据的样本数,c为样本的类别数,l为子空间的维度。样本空间构图和特征空间构图的时间复杂度分别为O(dn2)和O(d2n)。得到计算W,H,F和P的时间复杂度分别为O(nd+nc+dn2+dl),O(nd+d2n),O(nc)和O(cl)。由于子空间的维度和数据的样本数都小于数据的维度,所以得到算法的时间复杂度为O(T(dn2+nd2))。

5 实验与分析

5.1 实验准备

为了验证提出方法的有效性,本文在六个公开数据集上与几种经典及新颖的特征选择算法进行了对比实验,在下文给出了数据集和对比方法的详细介绍。

使用的数据集包括Lung_dis数据集[27]、COIL20数据集[28]、ORL数据集[20]、Isolet数据集[29]、Yale64数据集[20]和JAFFE数据集[30]。其中Lung_dis是关于人类肺部疾病的生物数据集,包含7种不同类别的疾病;COIL20数据集共有1440张灰度图像,这些图像是20种不同物体从不同角度拍摄得来的;ORL是一种人脸数据集,由40位志愿者的人脸图像组成,这些图像是在时间不同、灯光不同和面部表情不同的条件下拍摄的;Isolet是字母语音信号数据集,共包含1560个训练样本;Yale64是关于人脸表情的数据集,共包含15个不同的个体,165张人脸图像;JAFFE数据集是由来自日本的10位女性的人脸表情图像构成的,共包含213幅人脸图像。为了保证与对比方法之间的一致性,以上所使用的数据集均为原始矩阵格式,未进行进一步的特征提取。

对比的特征选择算法包括Baseline、LS[16]、MCFS[20]、UDFS[21]、SGFS[23]和LDSSL[24]。其中Baseline是使用所有特征进行实验的基准方法;LS是一种经典过滤式的方法;MCFS将流形学习的思想引入到特征选择的算法中;UDFS考虑局部判别信息,可以选择出具有判别力的特征;SGFS在子空间学习特征选择中加入了图正则化,保持了特征空间的局部结构;LDSSL则在子空间学习特征选择的基础上加入了局部判别模型。

5.2 实验参数设置

首先,对于需要构建局部图的方法,将k近邻的个数设置为5,计算相似度的高斯函数参数设置为10。对于本文提出的方法,为了保证特征选择矩阵W和伪标签矩阵F的正交性,正交约束的平衡参数γ和γ1调节的范围为105～108。目标函数中的其他平衡参数α、β和λ调整的范围为{10-3, 10-2, 10-1, 1, 10, 102, 103}。理论上子空间的维度应该远小于原始数据的维度,所以子空间的维度在{100, 200, 300, 400, 500}内调整。对于所有方法,选择特征的数量为{20, 30, 40, 50, 60, 70, 80, 90, 100}。在选择特定数量的特征后,使用K-means进行聚类。总共进行40次聚类实验,选择最优结果和其他对比方法的最优结果进行比较。算法迭代求解的最大次数设置为30。

5.3 实验结果分析

本文对比了不同方法在不同数据集上的聚类精确率(ACC)和互信息率(NMI),结果如表1和表2所示。从表中可以看出,与对比方法进行比较,本文提出的方法在所有数据集上都可以取得更好的结果。这表明利用本文提出的方法选择出的特征可以更好地表示原始数据的信息,在学习算法上也有更好的表现。对比SGFS,本文提出的方法在考虑了双图正则化和伪标签回归后,结果有了显著的提升。这表明双图正则化约束可以充分地利用隐藏在原始数据里的局部结构信息,同时伪标签回归可以弥补无监督特征选择缺乏标签信息这一缺点;LDSSL将判别分析和子空间学习结合在一起,但并没有考虑到伪标签空间和子空间之间的关系。本文提出的方法利用回归函数映射特征子空间和伪标签空间之间的线性关系,从而使得选择出的特征更具有判别力。

表1 不同数据集上不同方法的聚类精确率

表2 不同数据集上不同方法的互信息率

为了进一步验证本文方法的优越性,图2给出了在六种不同数据集上对于聚类精确率的参数敏感性分析。在本文提出的方法中,主要的平衡参数为控制伪标签回归系数α和图正则约束系数β。因此,这里主要对这两个参数进行参数敏感性实验。从图2可以看出,随着参数值的改变,大部分数据集上的聚类精确率在相对稳定的范围内变化。对于部分存在波动的数据集如JAFFE,本文的方法仍可以在特定的参数组合下得到良好的聚类结果。通过以上分析,可以证明本文提出方法的优越性和稳定性。

图2 不同数据集上的聚类精确率参数敏感性分析Fig.2 Sensitivity analysis of cluster accuracy parameters on different datasets

5.4 有效性实验

本节对提出的方法进行了有效性实验,通过设置伪标签回归和图正则化的参数来验证方法的有效性。将控制伪标签回归的平衡参数α设置为0,可以得到不包含伪标签回归的方法,简称为Ours1;将图正则约束系数β设置为0,则可以得到没有图约束的方法,简称为Ours2。

图3给出了聚类精确率在两种消融方法和完整方法之间的对比结果。从图中可以看出,在六个数据集上,Ours的效果都要优于Ours1和Ours2。这表明伪标签回归和图正则约束都可以提高方法的效果,也证明了本文提出方法的有效性。

图3 不同数据集上关于聚类精确率的有效性分析Fig.3 Effectiveness analysis of cluster accuracy on different datasets

6 结论

本文提出了一种基于子空间学习和伪标签回归的无监督特征选择算法。该方法将子空间学习的特征选择作为基础框架;在此基础之上引入了伪标签回归,可以利用数据的伪标签信息指导特征选择;进一步还通过双图正则化分别在数据空间和特征空间进行局部结构保持;最后,利用L2,1范数约束回归函数和特征选择矩阵,保证算法的鲁棒性和特征的稀疏性。实验结果表明,相比其他对比方法,本文提出的方法能够选择出更具代表性的特征。本文提出的无监督特征选择算法主要适用于小样本高维数据,未来算法优化的方向则是如何处理大规模高维数据。可设计并行算法将时间复杂度降低,使之能够在较短的时间内完成对大规模数据的特征选择。