基于矩阵分解和自适应图的无监督特征选择

曹浪财, 林晓昌, 苏思行

(1.厦门大学航空航天学院, 福建 厦门 361005;2.厦门大数据智能分析与决策重点实验室, 福建 厦门 361005)

0 引 言

特征选择可以通过某种标准从原始的特征集中选择出最优的特征子集解决维数灾难[1]。根据特征选择过程中涉及的不同子步骤,这些嵌入式方法可以进一步分为以下4种类型。

第1种嵌入式方法首先检测数据的结构,然后直接选择能用于最好地保留封闭结构的那些特征。典型的方法有迹比准则[2]和无监督判别性特征选择(unsupervised discriminant feature selection,UDFS)算法[3]。

第2种嵌入式特征选择方法首先通过构造各式各样的拉普拉斯图捕获样本的相似性信息,通过谱分析检测数据的簇结构。然后,通过稀疏谱回归[4]得到稀疏的特征选择矩阵。最后,选择特征选择矩阵中得分最高的p个特征,也就是和簇结构最契合的p个特征。这些通过图嵌入或者通过其他聚类方式挖掘数据的簇结构都可以看作对真实数据标签的近似过程。典型的方法包括多簇特征选择[5],最小冗余谱特征选择[6],全局和局部结构保留特征选择[7]。

第3种嵌入方法的簇结构是由拉普拉斯图以及自适应判别正则共同决定的,是动态改变的。通过特征选择结果的反馈,这类方法可以得到更好的聚类分析。典型算法包括联合嵌入学习和谱回归[8],鲁棒无监督特征选择方法[9],非负判别特征选择[10],鲁棒的谱学习特征选择[11]。

第4种嵌入式方法为了提高结构学习的质量,将特征选择的结果输入到结构学习中,并使用矫正后的数据结构引导选择特征过程。典型算法包括基于局部学习聚类的特征选择方法[12],自适应结构学习的无监督特征选择(unsupervised feature selection with adaptive structure learning,FSASL)[13],结构最优图特征选择(structured optimal graph feature selection, SOGFS)[14]。

综合以上特征选择方法可知,一个好的特征选择方法需要提取到可靠的数据几何结构以及可靠的簇结构来引导特征选择过程,但是现有的算法或侧重于理想数据几何结构的提取(FSASL,SOGFS),或侧重于通过鲁棒聚类进而引导更好的特征选择，比如基于矩阵分解的鲁棒无监督特征选择[15],很少同时兼顾这两方面。

基于以上分析,本文拟建立一个特征选取方法统一的框架,将自适应的局部结构学习、判别性信息的提取以及特征选择融合到该框架。在此基础上提出了一种基于鲁棒矩阵分解和自适应图的无监督特征选择(unsupervised feature selection based on robust matrix factorization and adaptive graph, MFAGFS)方法。该方法通过鲁棒矩阵分解获取判别性信息,并通过自适应图嵌入[16],学习数据集中的局部结构信息,并对学习到的相似性矩阵添加先验约束,而无需预先构建样本间的相似性矩阵, 降低了噪声和冗余特征的影响,从而提高了模型的鲁棒性,使得学习到的局部结构信息更加精确。最后通过对特征选择矩阵施加行稀疏的范数实现特征选择功能。

1 MFAGFS建模

传统的无监督特征选择模型在学习数据的局部结构的时候,通常在样本的原始特征空间中通过建立邻边和计算权重得到样本间的相似矩阵。然而原始样本空间中往往存在着许多的冗余甚至噪声,这种信息提取过程是不可靠的。因此，本文选择从纯净的投影空间中构造更加可靠的相似性矩阵,并对相似矩阵添加先验约束使得其具有c个连接分量(c为簇的个数)得到理想的局部结构信息。在此基础上通过矩阵分解进一步添加判别性信息防止过拟合。

为方便本节首先以矩阵A∈Rm×n介绍本文中所涉及到的各种范数和矩阵分解。

1.1 鲁棒矩阵分解

X∈Rm×n，其中m是特征的维数,n是样本的数目。每一个样本点可以表示为xi∈Rm×1。将矩阵X进行分解:

式中：V∈Rm×c是潜在的特征矩阵(聚类中心)；U∈Rn×c是类指示矩阵(c为聚类个数)[17-18]。存在着正交和非负约束的矩阵U可以看作是一个放缩的聚类索引矩阵。正交约束和非负约束的同时存在提高矩阵的质量,并且非负约束更符合实际情况。由于用F范数作为损失函数容易受到噪声点和异常点的影响。本文用l2,1范数来代替常见的F范数来避免大的损失从而使得所提的模型更加鲁棒。表示如下:

(1)

通过优化式(1)可得到聚类索引矩阵,然后用聚类索引指示矩阵去指导特征选择。但是这还远远不够的,需要增添更多的信息去提升所选择特征子集的质量。由于在无监督特征选择任务中数据的局部几何结构是十分重要的[19-20]。本文后续通过自适应图学习,进行基于数据内部几何结构的样本相似度提取,使得聚类索引矩阵更加接近数据的真实类别,获得理想的聚类效果,最终提升特征选择的性能。

1.2 自适应图构建

1.2.1 基于局部结构的自适应图

(2)

式中：1n是长度为1的全1列向量；α是正则化参数,正则化参数是为了避免无效解。考虑两个极端的例子:①α=0,对于向量si∈Rn×1有且只有一个元素的值为1,其他的都为0;②α=∞,这会让向量si中的每一个元素都为1/n;显而易见,正则项α可以用来调节邻居节点的个数。最佳的α值应该使大部分向量si只包含k个非零元素,其中k是与xi连接的邻居数。最优α值自动求解将在第2.3节详细给出。在得到相似性矩阵后可以对其进一步添加先验约束提高其可靠性。下一节将提出一种基于理想局部结构的自适应图优化,来进一步提升自适应图的正确性。

1.2.2 基于理想局部结构自适应图

对于相似性矩阵来说最理想的状态是只包含c个连通分量,即c个簇。然而通过局部结构学习到的相似性矩阵几乎不可能处于这种状态。注意到:

(3)

(4)

因此可以将优化问题式(4)改写为

(5)

1.3 MFAGFS算法流程

根据流形学习理论[25],始终存在可以表达高维数据结构的低维流形。WTX表示为此线性组合,其中W∈Rm×d是投影矩阵,m和d分别是原始特征维度和投影特征尺寸。将投影后的数据用在相似性矩阵的学习中,可以有效降低无关特征和冗余特征的负面影响。整理式(1)和式(5)可以得到MFAGFS模型的公式:

2γtr(UTLU)+η‖W‖2,1

(6)

图1 模型算法流程图

图1中,投影矩阵W用来特征选择,相似性矩阵S用来获取局部结构。将自适应的局部结构学习、判别性信息的提取以及特征选择融合到一体。

2 MFAGFS算法优化

2.1 模型优化求解

式(6)需要对S,U,V,W4个未知变量进行求解。为了降低模型求解的复杂度引入辅助变量E=X-VUT和Z=U。Z的作用是通过约束Z=U将获得的非负性传递给U,并在此过程中保持U的正交性不变。引入辅助变量后,同时使用增广拉格朗日法进行处理,式(6)可以改写为

‖E‖2,1+2γtr(ZTLU)+η‖W‖2,1+

<λ1,X-VUT-E>+<λ2,Z-U>+

(7)

式中：λ1,λ2是拉格朗日乘子;μ是惩罚参数,用来控制两个等式约束的惩罚。由于上面的目标函数包含多个变量,因此采用交替方向乘子法(alternating direction method of multipliers, ADMM)[26]来求解,通过交替迭代的方式将原问题简化为几个方便求解的子问题,即当更新某一变量的时候,其他变量固定,并由此依次对每个变量进行更新,具体流程如下所示。

算法1 基于鲁棒矩阵分解和自适应图的无监督特征选择的优化算法输入:数据集X∈Rm×n,特征选择个数h,聚类个数c,投影维度d。正则化参数η,β,足够大的γ,以及参数α。初始化:k均值聚类初始化U,V=XU,E=X-VUT,W=Id×m。迭代:1更新相似性阵S;2计算拉普拉斯矩阵L=D-ST+S2;3通过算法2更新特征选择矩阵W;4更新聚类索引矩阵U;5更新聚类中心V;6更新辅助变量E;7更新辅助变量Z;8更新拉格朗日乘子λ1,λ2,μ,直至收敛。输出:计算所有的‖wi‖2(i=1,2,…,n)并按降序排序,选择排名靠前p的特征作为最后结果。

算法1中相似性矩阵S、特征选择矩阵W、聚类索引矩阵U、聚类中心V、辅助变量E、辅助变量Z、拉格朗日乘子λ1,λ2,μ等子问题求解公式优化如下:

(1)相似性矩阵S

移除式(7)中与相似性矩阵S无关的项,得

2γtr(ZTLU)

(8)

(9)

(2)特征选择矩阵W

W通过求解以下问题更新:

s.t.WTW=I

(10)

(11)

显然当ε等于0时与原问题等价。式(11)写成拉格朗日乘子法形式:

tr(ΛWTW-1)

(12)

式中:Λ为拉格朗日乘子。

对W求导并令其等于0可以得到:

(13)

式中：Q∈Rd×d是一个对角矩阵,其中第i个元素定义如下:

(14)

矩阵Q是未知的,并且依赖于投影矩阵W。因此,本文采用一个迭代算法来求解式(11)。当固定W的时候,Q可以通过式(14)获得。而当固定Q的时候,特征选择矩阵W可以通过求解下式得到:

(15)

特征选择矩阵W的求解详细描述如算法2所示。

算法2 更新特征选择矩阵W输入:数据矩阵X∈Rn×d,拉普拉斯矩阵L∈Rn×n,参数η,参数β,投影维度d。初始化:Q∈Rn×n,Q=I。迭代:1根据现有的Q值,通过XTLX+βQ/η最小的d个特征值所对应的特征向量,更新特征选择矩阵W;2根据现有的W值,更新Q,直至收敛。输出:特征选择矩阵W∈Rm×d。

(3)聚类索引矩U

U通过求解以下问题更新:

经过进一步的整理可以得到:

(16)

式中：

(17)

式(16)可以进一步化简为

(18)

最后得到聚类标签U的迭代更新公式:

(19)

式中：NU,QU分别对应于矩阵H奇异值分解的左奇异矩阵和右奇异矩阵。

(4)聚类中心V

聚类中心V子问题如下所示:

(20)

考虑到U是正交的,也就是UTU=I,进一步整理可得

最后得到聚类中心V的更新式:

(21)

(5)辅助变量E

子问题E如下所示:

(22)

(23)

(6)辅助变量Z

移除式(7)与辅助变量Z无关的项,得

(24)

(25)

(7)拉格朗日乘子以及w

参考文献[27]更新方式如下:

λ1=λ1+μ(X-VUT-E)

(26)

λ2=λ2+μ(Z-U)

(27)

μ=min(μmax,pμ)

(28)

式中：μmax是常数;p是迭代步长。

2.2 算法2的收敛性分析

特征选择矩阵迭代过程中的收敛性直接影响到算法的可行性,本节给与证明。首先给出以下引理。

引理 1对于任意的正实数u,v,下面的不等式[28]恒成立:

定理 1算法1中的目标函数将单调递减直到收敛。

(29)

基于引理1,可知:

(30)

通过整理式(29)和式(30),可得到:

(31)

证毕

2.3 正则化参数α值的求解

式(9)满足KKT(Karush-Kuhn-Tuckre)[29]条件的最优解为

(32)

式中:(·)+表示相似向量si是稀疏并且非负,意味着向量si中有且只有k个数据大于0,其他都是等于0。如果将sij从大到小排列,则si,k>0,si,k+1≤0,也就是:

(33)

(34)

(35)

整理式(33)～式(35),得到:

(36)

(37)

最后对所有的αi加和平均得到:

(38)

3 实验与分析

本节将通过对比实验验证提出的无监督特征选择算法的有效性。

3.1 实验准备

3.1.1 数据集介绍

在MFAGFS模型对比实验中,使用了6个常见的公开数据集。这6个公开数据集的样本数,特征维度、类别数以及实验中选择的特征个数在表1中详细给出。这6个数据集的类别数最少的有8类,最多的高达100类。样本数目也具有多样性,最少的有165个,最多的有2 000个。

表1 数据集的简要信息和特征选择维度

3.1.2 实验设置

为了对MFAGFS模型的性能有个客观的认识。实验中将采用所有特征作为基准,并与其他5个相关的无监督特征选择算法进行比较。实验中涉及到的对照模型为Baseline、LapScore[30]、UDFS、NDFS、FSASL、SOGFS。

为了保证对比实验的公平性和有效性,实验中需要提前设置近邻参数时,统一设置为k=5,高斯热核函数中的参数σ大小设为1。此外,对于特征选择矩阵(投影矩阵)的维数空间和潜在簇的个数都设为c(c是数据集的真实类别数)。MFAGFS模型还需要调节η,β和γ这3个参数。其中γ用来实现对秩的约束,在具体实验操作中根据秩的大小自动调节γ的值。对于剩下的参数η和参数β采用网格搜索的方式来确定。搜索的范围为{10-3,10-2,10-1,100,101,102,103}。为了公平起见,其他对比模型的正则参数统一进行范围大小为{10-3,10-2,10-1,100,101,102,103}的网格搜索。

由于k均值聚类的效果与初始化紧密相关,所以在实验中重复实验20次并记录其平均值。

3.1.3 实验评价指标

为了准确地观察算法的效果,需要采用相应的评价指标得到客观的量化结果。本文采用准确率(accuracy, ACC)以及归一化互信息(normalized mutual information,NMI)这两个评价准则来评估特征子集的聚类性能[7]。

3.2 实验结果分析

3.2.1 特征有效性分析

本节通过对比实验来验证MFAGFS模型所选择的特征的有效性。总共采用了6个数据集进行聚类分析。实验结果中的测试指标用粗体表示最好的结果,下划线表示次好的结果。AVERAGE表示各个特征选择方法在6个数据集上的平均表现。

表2和表3描述的是各个模型在各个数据集上的最优表现情况。

从表2以及表3中可以得到如下结论。

表2 各算法最优识别率比较

表3 各算法最优标准互信息比较

(1)大部分的无监督特征选择算法都比基线有着更加优异的表现。说明原始数据中有着大量冗余以及噪声特征。通过特征选择可以提高学习器的性能。说明了进行特征选择的重要性。

(2)LapScore的特征选择结果差强人意,这是由于它的特征选择策略是逐个选取特征的方式。这种特征选择方式忽略了特征之间的关系选出来的特征与其他模型相比特征冗余度高。

(3)在6个数据集的平均准确率上,MFAGFS比次优的NDFS模型高出了4.01%。另外值得注意的是,MFAGFS算法在所有数据集上的表现比基准方法提高了1.01%到15.60%。说明MFAGFS能够选择出更加具有区分性的特征子集。

3.2.2 特征个数和聚类结果之间的关系分析

从实验结果中,可以进一步分析特征个数和聚类结果之间的关系。从图2和图3中可以得出如下结论。

图2 ACC随选择特征数量变化曲线

图3 NMI随着选择特征数量变化曲线

(1)基线在PalmData25上的最好结果稍微好于其他数据集,这是由于PalmData25数据集的特征维度低,特征冗余度比较低。进行特征选择的难度比较高。

(2)ACC和NMI并不是简单的随着特征维度的增高而增高,而是处于一种进入一定的特征维数后就开始稳定,甚至波动。这说明了数据中真正的有效特征是少数的,大部分特征是冗余、无效的,过多的特征不仅带来计算负担还可能带来负面效果。这也说明了特征选择的必要性。

(3)SOGFS、FSASL以及MFAGFS这3个有自适应学习数据的局部流形结构的模型的表现比其他模型的表现要更加出色。说明了局部几何信息在无监督特征选择中的重要性。

(4)MFAGFS的曲线基本处于其他算法的上方(除了PalmData25),这说明了局部几何结构和判别信息的充分利用有助于选择出好的特征子集。

3.3 参数敏感度分析

MFAGFS在实验中需要提前设置一些参数,本节主要关注两个主要正则参数η和β对实验结果的影响,即用来保证数据局部相似性的β,以及用来控制特征选择矩阵稀疏约束的η。通过重复使用k均值聚类20次并取其平均值,并取得到最好结果的维度作三维图,如图4和图5所示。

图4 ACC随η和β的变化情况

图5 NMI随η和β的变化情况

3.3.1 聚类ACC分析

图2和图4是MFAGFS在6个数据集上,不同的β和η值所对应的聚类ACC结果。算法在PalmData25和COIL20上的结果比较稳定。这可能与PalmData25以及COIL20数据集样本数目多进行特征选择的难度比较低有关。

3.3.2 聚类NMI分析

图3和图5为MFAGFS在6个公开数据集上对应不同的参数的聚类NMI的结果。从数据集ECOLI和ISOLET的聚类NMI上来看可以得到对数据进行参数选择是必要的,不同的参数组合对结果的影响可能是巨大的。

另外从图2～图5上可以得出如下结论:同一参数组合下的ACC和NMI的表现可能有巨大差异。这是由于ACC和NMI是两个完全不同的评价指标,不同的评价指标造就不同的评价结果。

4 结 论

特征选择是一种成熟的数据预处理方法,可以有效地去除冗余特征以及噪声,进而达到降低数据维度且同时保留数据的重要信息的目的。无监督的特征选择算法相比于有监督的特征选择更加富有挑战性。

本文提出了一种MFAGFS方法,通过矩阵分解得到的聚类信息以及通过自适应图得到的局部结构信息指导特征选择过程,为了防止过拟合进一步通过行稀疏的l2,1范数来去除数据中冗余特征提升特征选择的效果。在6个真实世界的数据集上进行了对比试验以及稳定性试验,试验结果表明,提出的MFAGFS模型与相比其他无监督特征选择模型相比,ACC和NMI都有一定程度的提升,模型具有更高的精度,且具有较高的鲁棒性,对参数不敏感。

MFAGFS与NDFS一样,都有通过聚类来获得到判别性信息。但是NDFS进行谱聚类的时候是在原始空间,而数据在原始空间中有大量的噪声和冗余特征,这会影响到所学习到的特征准确性。而MFAGFS通过鲁棒的矩阵分解获得聚类标签可以有效地降低噪声和异常点对特征选择的影响。

MFAGFS和FSASL都考虑了噪声点和异常点的影响,模型都比较鲁棒。但是不同的是MFAGFS有对相似性矩阵进行更加细致的先验约束,因此得到的结构信息更加精确。

采用矩阵分解的模型来进行数据点的聚类,这是一个线性的模型。然而数据往往是嵌入在一个低维流形上的,数据之间存在复杂的非线性关系,这是线性的矩阵分解模型所处理不了的。如何应用更先进的技术到特征选择的过程中来,如张量分析、分解机,是本文后续重点研究的课题。