基于图结构优化的自适应多度量非监督特征选择方法

林筠超，万 源

（武汉理工大学理学院，武汉 430070）

（*通信作者电子邮箱wanyuan@whut.edu.cn）

0 引言

随着数据采集技术的飞速发展，在计算机视觉、数据挖掘、生物医学等许多邻域中产生了大量未标记的高维数据［1］。高维数据通常包含很多噪声，处理分析过程中会带来高昂的计算成本和维数灾难，因此非监督特征选择成为高维数据降维中重要且具有挑战的问题［2-3］。

由于没有标签信息作为参考，相较于有监督方法，非监督特征选择方法更具有挑战性。高维度空间的特征选择降维方法的相关研究表明，应该通过选择出的特征来保持原始数据的重要信息［4-5］，这些信息包括数据的全局结构和局部流形结构。拉普拉斯分数法（Laplacian Score，LapScore）［6］通过图拉普拉斯算法来选择特征，使数据的局部流形结构得以保留。受流形学习和l1正则化子集选择模型的启发，UDFS（Unsupervised Discriminative Feature Selection）［7］将判别分析和l2，1范数最小化合并到非监督特征选择的联合框架之中。文献［8］中提出的多聚类特征选择方法（Multi-Cluster Feature Selection，MCFS），通过谱分析和l1范数正则化来保留多簇结构以选择特征，而非独立地评估每个特征的分数。非负判别特征选择（Nonnegative Discriminative Feature Selection，NDFS）方法［9］将判别信息和特征间的相互性合并于一个联合框架中，充分利用了鲁棒非负矩阵分解、局部学习和鲁棒特征学习的优势。JELSR（Joint Embedding Learning and Sparse Regression）［10］则考虑联合嵌入学习和稀疏回归，而非用图拉普拉斯来表征高维数据结构。结构化最优图特征选择（Structured Optimal Graph Feature Selection，SOGFS）［11］则提出了一种局部结构学习的同时进行特征选择的方法。这些特征选择方法都能很好地解决通过全局结构构造相似矩阵所带来的弊端。依赖指导的非监督特征选择（Dependence Guided Unsupervised Feature Selection，DGUFS）方法［12］提出了两个依赖关系指导项，一项增加了所需聚类标签对原始数据的依赖性，而另一项使所选特征对聚类标签的依赖性最大化，以指导特征选择过程，特别地，提出了一种基于l2，0范数相等约束的无投影特征选择模型。自适应近邻特征选择（Adaptive Neighbors Feature Selection，ANFS）方法［13］通过自适应重构图来描述局部结构，并通过在相应的拉普拉斯矩阵上施加秩约束来同时考虑多簇结构。自加权多视角聚类（Self-weighted Multiview Clustering，SwMC）方法［14］在学习视角权重的同时实现对多视角数据的聚类，并且提出权重可以通过引入一个超参数来学习。

然而，由于没有标签信息作为参考，上述非监督特征选择方法都是使用某一种度量方法来表示数据点之间的相似度。考虑到各方法构造相似矩阵的标准并不统一，如何从多种度量标准中总结出一种统一度量标准是值得研究的；另外，通过常规的K最近邻（K-Nearest Neighbors，K-NN）法分配得到的相似矩阵，难以确保其具有理想的连通分量数［11］。

针对上述两个问题，本文将不同的度量函数自适应地融合为统一的相似性度量，并将图结构优化嵌入非监督特征选择之中，提出了一种基于图结构优化的自适应多度量非监督特征选择（Self-Adaptive Multi-measure unsupervised feature selection with Structured Graph Optimization，SAM-SGO）方法，为了能根据统一的相似度得到相关子空间，本文将基于图的降维问题合并于目标函数之中，并引入稀疏性l2，0正则化约束以避免噪声样本和特征带来的影响。与已有的算法相比，本文方法能更好地保留图的结构信息，并使获得的稀疏投影能高效地进行特征选择；通过对多种度量标准进行自适应融合，有效地避免了单一度量标准对相似矩阵的构造所带来的偏差。

1 相关工作

1.1 局部保留投影

文献［15］中提出的局部保留投影（Locality Preserving Projections，LPP）法被广泛应用在降维方法USSL（Unified Sparse Subspace Learning）［16］、FSSL（joint Feature Selection and Subspace Learning）［17］、FSASL（unsupervised Feature Selection with Adaptive Structure Learning）［18］等算法中。

对于给定数据集X={xi|xi∈Rd×1；i=1，2，…，n}，相关的数据矩阵表示为X=[x1，x2，…，xn]，xi∈Rd，其中d为数据维数，n为数据的样本数。构造一个无向图G={X，S}，顶点由数据集X构成，边由相似矩阵S∈Rn×n构成。图G 的每条边，表示近邻点之间相互连接。对于无向图G，其极大连通子图称为G的连通分量（connected component）［19］。令Sij为第i个数据点与第j个数据点之间的相似度，其值与顶点间距离成反比。对角矩阵D定义为，∀i，拉普拉斯矩阵L定义为L=D-

一个特征的重要性取决于其表达图结构信息的能力［15］。为简化说明，假设向量y=[y1，y2，…，yn]T为图G 顶点的低维表示，即yi是数据点xi的低维表示。为在各顶点之间找到一组低维向量，以最好地表征顶点对之间的相似关系，可以通过最小化下列目标函数来获得较优的特征：

为实现最小化目标函数，当样本xi和xj之间相似性越大，对应地yi和yj之间距离应该越小，反之亦然。进一步，为构造拉普拉斯特征映射的线性逼近，假设用于表示数据的低维向量yi通过线性映射yi=WTxi表示，W∈Rd×m是投影矩阵，d和m分别为数据投影前后的维数。则式（1）目标函数变为：

为避免目标函数的平凡解，通常增加约束WTW=I［21］。

1.2 l2，0范数稀疏约束

在实际应用中，为了让获得的投影矩阵W保持行稀疏，Cai 等［22］提出，将稀疏l2，0诱导约束引入图嵌入问题（2），使稀疏特征选择问题有效地嵌入于图降维问题中，优化问题（2）改进为：

增加的约束||W||2，0=r使得正交投影W仅具有r个非零行，且这r个非零行即为所选特征。求解时，优化问题（3）等价于其对偶问题（4）：

其中：r是预设常数，β是正则化参数。显然，当β足够大时，问题（4）等价于问题（3）。

2 SAM-SGO算法

非监督特征选择方法通常分为两个独立的步骤，首先通过局部结构构造相似矩阵，然后通过稀疏正则化选择较优特征，如USSL［16］、FSSL［17］、DGUFS［12］等，这些方法所构造的相似矩阵是独立于特征选择的，即从原始数据中得出的相似矩阵在之后的步骤中保持不变，但实际数据必然包含噪声特征，从而导致相似矩阵不可靠。针对这个问题，FSASL 方法［18］提出了一种自适应结构学习方法，通过迭代优化思想反复构造相似矩阵，避免了固定的相似矩阵对特征选择的影响。

然而在构造相似矩阵的过程中，这些方法所采用的度量标准仅限于某一种，而忽略了数据点之间的相似性程度，且通过常规的K近邻法得到的相似矩阵，难以确保其具有理想的连通分量数［14］。本文提出一种基于图结构优化的自适应多度量融合方法，将多种度量函数自适应地融合为统一的相似性度量，解决了单一方法对谱图的构建所带来的偏差，并增加拉普拉斯矩阵秩约束，以保证相似矩阵的连通分量数是理想的。

2.1 自适应多度量融合

在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间。而寻找合适的空间，实质上就是在寻找一个合适的距离度量［23］。令ft为第t个给定的度量函数，对于数据矩阵X，ft(X) ∈Rn×n表示为基于度量函数ft所构造的相似矩阵。为评价样本点之间的相似性，根据数据的特性的不同，LapScore、MCFS 选择高斯核函数度量［8］，DGUFS 使用欧氏加权函数［12］，SOGFS 使用的是基于概率邻域的相似矩阵度量法［24］，LMNN（Large Margin Nearest Neighbor）算法使用的是夹角余弦法［25］等。

然而，上述方法所采用的距离度量都是固定且单一的，没有可调节参数，难以通过对样本数据的学习来加以改善。因此，针对这个问题，本文考虑用多种度量自适应融合成的统一度量方法，相较于上述的单一度量方法，本文所构造的相似矩阵能更好地表达数据之间的联系。为了将多种度量方法进行统一，本文构造下列目标函数：

其中I=(1，1，…，1)T∈Rn×1。为有效融合所有选定的度量，将自适应权重ht分配给每项，以便对其重新加权。式（5）重新写为：

在式（6）中，自适应权重ht通过ht迭代更新。其优势在于，对于相似矩阵S与各度量标准计算得到的相似矩阵ft(X)之差，差额较大的项自动分配较小的权重ht，同样地，较大的权重ht将自适应地分配给差额较小的项。因此，对于任意给定数据，本方法能自适应地将权重分配给各度量，从而减轻了单一度量标准对实验所带来的偏差。

2.2 结构最优图

理想情况下，在将数据划分为c个簇的聚类任务中，相似矩阵S应含有c个连通分量，然而在多数情况下，通过局部保留投影方法LPP 所获得的相似矩阵S，其具有的连通分量数不能达到理想情况［11］，很容易出现所构成的无向图仅有一个连通分量的情况［24］，这表明得到的相似矩阵不够优秀。因此，需要对该图的结构进行进一步优化，使得其连通分量数满足要求。

假设相似矩阵S非负，首先给出关于拉普拉斯矩阵L所满足的定理［20］：

定理对于拉普拉斯矩阵L，特征值为0的重根数为c（即矩阵L的秩为n-c），等价于相似矩阵S包含c个连通分量。

该定理表明，若拉普拉斯矩阵L满足rank(L)=n-c，则原始数据所构成的相似矩阵S可被划分为c个簇，从而能够得到具有最优结构的无向图G。因此，通过增加对于拉普拉斯矩阵L的秩约束，可使得相似矩阵S能包含准确个数的连通分量，使得无向图G的结构信息更为准确。

综上所述，通过融合了自适应多度量思想，并在l2，0范数稀疏约束的图嵌入非监督特征选择中增加了优化图结构的约束项rank(L)=n-c，本文方法SAM-SGO 所得到的目标函数为：

3 算法求解

目标函数（7）中包含l2，0范数正则化、秩约束以及3 个未知变量，同时优化求解这几个变量较为困难，本文引入交替迭代更新的思想，在优化某个变量时固定其他所有变量，反复对变量进行迭代更新直至收敛，最终得到目标函数的最优解。

对于问题（7），考虑到拉普拉斯矩阵L=及其秩rank(L)=n-c的值都取决于相似矩阵S。令σi(L)表示L的第i个最小特征值，由于L为半正定矩阵，其每个特征值均非负，即σi(L) ≥0，进而约束rank(L)=n-c等价于根据Ky Fan’s定理［26］有：

通过定理将原式中拉普拉斯矩阵L的秩约束转化为迹，于是式（7）可优化为：

显然，在式（9）中，当λ足够大，项Tr(FTLF)将趋于0。在每次迭代过程中，当连通分量比c小，可以相应地增加λ，反之亦然，直至趋于收敛。通过此方法，将矩阵秩的约束转变为迹，使得问题变得更易解决。

3.1 固定S和F，优化投影矩阵W

当S和F固定时，仅保留含有W的项，于是目标函数（9）式可以变换为：

由于l2，0范数的特殊性，不易对式（10）直接求解。文献［22］中提出，问题的求解等价于问题的求解，因此在该式中用代替||W||2，1，同时省略与W最优取值无关的常数项r，将式（10）变形为：

对于式（11），其拉格朗日函数表示为：

其中，斜对角矩阵A∈Rm×m由拉格朗日乘子构成。通过求解式（12），其关于W的卡罗需-库恩-塔克（Karush-Kuhn-Tucker，KKT）条件为：

其中Ω=diag(Λ1，Λ2，…，Λd)，Λi=+ε)-1/2/2，增加扰动项ε以防止行稀疏投影矩阵W出现平凡解，ε通常取极小值。因此，问题（12）的求解等价于问题（14）：进而通过求解矩阵XTLX+βΩ/2α的前m个最小特征值所对应特征向量，即可得到最优投影矩阵W。

3.2 固定S和W，优化F

当S和W固定时，变量F仅存在于目标函数的最后一项，故式（9）变为：

其中，最优解所对应的F即为拉普拉斯矩阵L的前c个最小特征值所对应的特征向量组成的矩阵。

3.3 固定W和F，优化S

W和F固定后，仅保留与变量S和ht有关的项后，问题（9）变换为：

进行恒等式变换得到：

将式（17）拆成n项，其第k项的拉格朗日方程为：

其中μ为等式约束乘子，θk≥0(k=1，2，…，n)为不等式约束乘子。对于∀h，关于式（18）的KKT条件如式（19）、（20）所示：

由此分别得到了3个变量W、S、F的优化更新表达式，其具体的算法流程总结如下：

输入 原始数据X=[x1，x2，…，xn]，xi∈Rd×1；聚类数c；目标维数m；参数α、β；r个选定的度量函数ft。

输出 投影矩阵W∈Rr×d。

初始化 随机生成ht，计算初始拉普拉斯矩阵L，并通过式（14）和（15）计算初始W和F

重复迭代：

对于k∈1到n

通过式（22）更新skh

通过ht=更新ht

通过式（15）更新F

根据式（14），通过求解矩阵XTLX+βΩ/2α的前m个最小特征值，获得所对应的特征向量，更新W直至收敛

计算所有的‖wi‖2并排序，选取前m个特征代入K-means 聚类得到聚类结果并计算准确率。

4 实验

本文设计了多项实验来测试本文所提出的基于图结构优化的自适应多度量非监督特征选择（SAM-SGO）方法的性能。

4.1 实验数据集与实验设置

本文使用了6组公开图像数据集，包括3组人脸图像数据集MSRA25［27］、ORL［28］、Yale［29］，1 组实物数据集COIL20［30］，1组生物数据集Lung［31］和1组手写图像数据集USPS［32］。表1汇总了这些数据集的具体信息，并在图1中展示了3个不同领域数据COIL20、Yale、USPS的部分图像。

图1 部分样本图像Fig.1 Some sample images

表1 样本数据集信息Tab.1 Sample dataset information

为验证SAM-SGO 方法的有效性，将本文方法与下列几种常见的非监督特征选择算法进行了比较分析，包括：

1）拉普拉斯分数（LapScore）方法［6］：通过计算特征对于保持局部流形结构能力，并根据得分大小选择特征。

2）多集群特征选择（MCFS）方法［8］：该方法使用了图拉普拉斯算子的多个特征向量来捕获数据的多簇结构，通过谱分析和l1范数正则化来保留多簇结构以选择特征，而非独立地评估每个特征的分数，在聚类和分类上都能取得很好的性能。

3）基于局部学习聚类的特征选择和内核学习（LLCFS）方法［33］：该方法旨在通过基于局部学习聚类（Local Learningbased Clustering，LLC）方法的框架中的特征选择来获得合适的数据表示，在处理位于流形上的高维数据时要优于基于全局学习的方法。

4）依赖指导的非监督特征选择（DGUFS）方法［12］：提出了基于l2，0范数相等约束的无投影特征选择模型，以联合方式选择特征和分区数据。

5）基于图结构优化的非监督特征选择（SOGFS）方法［11］：该方法同时执行特征选择和局部结构学习，并通过图结构约束相似矩阵，使该方法所选择的特征能更好地表达数据的结构信息。

6）使用全部特征并进行K-means 聚类的基准线作为对照组（Baseline）。

为了算法比较的公平性，本文所采用的度量方法部分源于上述对比方法，包括：LapScore、MCFS 所使用的高斯核函数度量法［8］，SOGFS 所使用的基于概率邻域的相似矩阵度量法［24］，LMNN 算法所使用的夹角余弦法［25］，以及在模糊数学领域中常见的绝对值倒数法［34］。

在实验参数上，MCFS，LapScore 和SOGFS 中的近邻个数k均设置为5，DGUFS 所使用的参数α和β以及SOGFS 中参数γ采用层次网格搜索法来确定。考虑到聚类性能随初始聚类中心的选择而变化，为减轻聚类方法带来的随机效应，对于所选择的特征，本文从不同的起点重复10 次K-means 聚类实验并只取最优结果。本文采用聚类准确度（Accuracy，ACC）作为评价指标来评估所选特征，定义为：

其中：pi和qi分别是数据提供的标签和得到的标签；δ(x=y)为条件判断函数，若x=y则函数值为1，反之则为0；map(qi)是排列映射函数，可通过Kuhn-Munkres 算法得到，它能将得到的集群标签qi映射为数据集中的等效标签。

4.2 实验结果与分析

本文实验环境为Inter Core i7-6500U，CPU@2.50 GHz，12 GB 内存，Windows 10 64 位操作系统，编程软件为Matlab 2016a。对所提出的SAM-SGO算法进行了3组实验：在固定所选特征数时各算法之间的性能对比；对于不同数据集，不同算法的聚类准确率随所选特征数增加的变化曲线；各实验参数对于本方法的灵敏度分析。

4.2.1 对于不同所选特征数，不同算法在各数据集下的聚类结果

对于各非监督特征选择方法，本文使用了上述实验数据及相应设置，采用十折交叉验证法对特征子集进行评价，在表2 中展示了各特征选择方法在选择前90 个特征的聚类结果（其中对最优方法用加粗表示，次优方法用下划线表示）。可以看出，本文提出的SAM-SGO 非监督特征选择方法在不同的数据集上普遍优于其他5 种方法，具体而言：相较于次优的方法，本文方法在人脸图像数据集ORL、Yale、MSRA25 上，聚类准确度（ACC）分别提高了6.8 个百分点，4.0 个百分点和4.3个百分点；在实物图像数据集COIL20 和手写图像数据集USPS 中分别提高了2.5 个百分点和3.4 个百分点；在生物数据集Lung中提高了0.7个百分点。

表2 各算法在选取前90个特征的聚类准确度（ACC）平均值和标准偏差 单位：%Tab.2 Average clustering accuracy（ACC）and standard deviation of each algorithm with selecting top 90 features unit：%

通过对比可以发现，本文所提出的方法在不同的数据集上的性能都较高，特别是对于人脸图像数据集，其聚类正确率不仅优于使用全部特征的聚类方案，更是显著高于其他方法所得到的结果。由此可见，相较于其他特征选择方法，本文所提出的基于图结构优化的自适应多度量非监督特征选择（SAM-SGO）方法能有效地筛选出较为精炼的数据特征，从而提高聚类的正确率。

4.2.2 各算法聚类性能对比

为直观地观察不同方法之间的性能差异，本文分别在6组数据中进行实验，并绘制出在特征数为10、20、30、…、110，不同算法所选特征的K-means 聚类准确度（ACC），如图2所示。

通过分析，可以得出以下结论：

1）随着特征数的增加，本文所述的方法的聚类准确度通常呈现先上升后稳定的趋势。这是由于现实数据中包含许多冗余特征，值得挖掘的信息通常包含在少数特征中，若所选特征过多，导致噪声特征的增加，势必影响聚类结果。这种趋势间接验证了特征选择方法的有效性。

2）在大多数情况下，由于数据中经常包含许多噪声数据或冗余数据，相较于直接使用所有特征进行K-means 聚类，仅使用特征选择方法选定的少数特征进行聚类，其结果会更好。特别是本文所提出的SAM-SGO 方法，在大多数数据中都有较好的改善。说明了特征选择方法能有效地提高数据的质量，获得精炼后的数据，从而提高聚类的准确率。

3）由图2（e）可以看出，并非在所有的数据集中，使用特征选择方法的聚类正确率都能比基线方法高，这是由于原始数据本身的特性不同，这也说明了特征选择方法仍有进步的空间。

图2 六组数据在不同所选特征数下各算法的聚类准确度Fig.2 Clustering accuracy of each algorithm for 6 groups of data under different feature numbers

4.2.3 自适应权重ht的收敛性

本文所采用的四种度量方法，包括：高斯核函数度量法、基于概率邻域的相似矩阵度量法、夹角余弦法，以及绝对值倒数法。本文给出了对于COIL20数据集和Yale数据集，自适应权重ht随迭代次数增加的曲线，如图3所示。

图3 自适应权重ht的收敛曲线Fig.3 Convergence curve of adaptive weight ht

可以看到，本方法中的自适应度量权重ht收敛速度是非常快的。在以上两个示例中，经过若干次迭代之后均趋近收敛于一个定值。从图3（a）可以看出在数据集COIL20中，绝对值倒数函数对于该数据的适应程度远高于其他方法，而夹角余弦法的适应程度最低。而对于图3（b）中数据集Yale，高斯核函数度量法的适应度最高，其次是基于概率邻域的相似矩阵度量法，反而数据集COIL20中表现良好的绝对值倒数法权重较低。由此可以看出在不同数据集下，SAM-SGO 方法对于度量方法的选择是有所偏好的。

4.2.4 统一相似矩阵的稀疏性

为了对比本文SAM-SGO 方法处理相似矩阵能力，本文给出了本文方法在处理COIL20 数据集前后，相似矩阵S的稀疏程度对比，如图4所示，其中，横坐标表示相似矩阵S的第i列，纵坐标表示相似矩阵S的第j行，右侧颜色栏（colorbar）表示颜色范围所对应的数值范围。

图4 相似矩阵S稀疏程度Fig.4 Sparsity of similarity matrix S

可以看出迭代收敛后的相似矩阵，除主对角线以外的元素，绝大多数元素均为0或趋近于0。相较于迭代开始前的相似矩阵，SAM-SGO 方法迭代收敛后的矩阵更为稀疏，其结构也更加清晰，验证了采用本方法构造的统一相似矩阵是足够稀疏的。

4.2.5 灵敏度分析

本文研究了SAM-SGO 方法中，参数对实验结果影响。在本方法中，不确定参数包括m、α、β三项。

对于参数m（数据投影后的维数），其值会稍微影响结果，根据实验经验，通常将其设置在d/3～d/2。

而对于参数α、β，其值对聚类结果的影响不大。对于数据集COIL20，本文给出了参数α、β的值对聚类准确率ACC结果的灵敏度分析，包括固定β=0.7，变化α和特征数，以及固定α=3，变化β和特征数两组对比实验，如图5所示。

图5 SAM-SGO方法在COIL20数据集上的灵敏度分析Fig.5 Sensitivity analysis for SAM-SGO method on dataset COIL20

可以发现，随着所选特征数的增加，聚类准确度有着上升的趋势；而固定特征数个数时，聚类准确度不会随着参数β的改变而出现太大的变化。整体而言，参数的小幅度调整对于结果的影响不会很大，这说明了SAM-SGO 方法在某种程度上对参数α、β具有鲁棒性。尽管如此，本文仍建议在实际应用中使用分层网格搜索来寻找最优的参数。

5 结语

为统一不同度量的相似矩阵，使得到的相似矩阵具有理想的连通分量数，本文提出了一种基于图结构优化的自适应多度量非监督特征选择方法（SAM-SGO），将自适应度量嵌入基于图的降维问题，并对图结构进行优化。考虑到噪声数据带来的影响而引入了l2，0范数正则化。为解决所提出的问题，给出了一种有效的迭代优化算法，在不同领域的多个基准数据集上进行的综合实验，验证了本文方法的有效性。

尽管SAM-SGO 方法通过寻求线性变换来进行特征选择，能够表现出非常好的性能，但相较于图像数据集，本算法在非图像数据集上的表现不够优秀，可以考虑使用核映射的非线性模型来扩展所提出的方法，可能会提高本算法的普适性；另外，可以尝试将自适应多度量思想方法应用到有监督和半监督的分类领域之中。