相似性矩阵的构造和约束是基于图的方法的关键.给定数据矩阵X∈ R^{d× n}, 考虑概率近邻^[28], 即对于数据x_i, 所有数据点{x₁, x₂, …, x_n}都有S_ij的概率与x_i成为邻居.通常越小的距离‖ x_i-x_j ‖22应有越大的概率S_ij.自适应确定具有概率近邻的初始相似矩阵S:

(1)

定理1^[28] 拉普拉斯矩阵L_S的特征值0的重数等于具有相似性矩阵S的图中连通分量的个数.

在将数据划分为c簇的聚类任务中, 理想的邻居分配是相似图的连通成分恰好为聚类数c.根据定理1, 约束拉普拉斯矩阵L_S的秩

rank(L_S)=n-c,

其中

L_S=D- S+ST2,

度矩阵D为对角矩阵, 对角线元素

D_ii= 12∑j=1n(S_ij+S_ji).

令σ ₁, σ ₂, …, σ _c为拉普拉斯矩阵最小的c个特征值, 则rank(L_S)=n-c等价于

∑i=1cσ _i(L_S)=0.

根据文献[29]:

∑i=1cσ _i(L_S)= minF∈Rn×cFTF=Itr(F^TL_SF).

具有c个连通分量的相似图构造如下:

如图1所示, 使用一个聚类数为3的数据集显示自适应概率近邻相似图和具有精确联通分量的相似图之间的差异.若S_ij> 0, 连接数据点x_i和它的近邻x_j.由(a)构造的相似图互相连通, 只有1个连通分量, 由(b)构造的相似图互不连通, 有3个连通分量, 恰好为该数据集的聚类数, 因此具有精确连通分量的相似性矩阵可学习准确的数据结构信息.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 两种相似图的区别Fig.1 Difference between two kinds of similarity graph

给定数据矩阵

X=[x₁, x₂, …, x_n]∈ R^{d× n},

x_i∈ R^{d× 1}为第i个样本, d为原始特征维数.X还可表示为

X=[f₁, f₂, …, f_d]^T,

f_i∈ R^{n× 1}为第i个特征, n为样本点的个数.无监督特征选择的目标为在不利用标签信息的情况下, 从原始数据中选择最具有代表性的k个特征子集, k为选择特征的个数, k≪d.

根据流形学习理论, 高维数据中的信息可由低维流形表示.投影矩阵

W=[w₁, w₂, …, w_d]^T∈ R^{d× m},

将数据点投影到低维空间, 即

W^TX= ∑i=1dw_i f Ti.

对于特征选择任务, W的第i行w_i衡量第i个特征的重要性.当

‖ w_i‖ ≠ 0

时, 选择第i个特征f_i, 当

‖ w_i‖ =0

时, 舍弃第i个特征f_i.若选择k个特征, 则理想情况为W恰好有k个非零行, 即

‖ W‖ _{2, 0}=k,

因此选择精确个数的特征选择任务即为求解

(2)

其中, g(· )的目标是学习一个投影矩阵W, 与原始数据矩阵X以最佳线性组合近似低维流形, 从而选择更好地保持数据流行结构的特征.

由于非凸非光滑性, 难以求解l_{2, 0}范数优化问题, 因此大部分研究使用W的l_{2, 1}正则化项代替W的l_{2, 0}范数约束, 即

minWg(W^TX)+λ ‖ W‖ _{2, 1}.

基于l_{2, 1}范数正则化模型求解的投影矩阵W不同于l_{2, 0}范数约束直接选择W的非零行对应的特征, 而是通过‖ w_i‖ ₂的大小衡量特征的重要性, 排序选择最大的‖ w_i‖ ₂对应的特征, 未考虑特征的相关性, 单个选择最优的特征.此外, 由于l_{2, 1}范数正则化问题中的正则化参数λ 无明确的含义, 需要花费时间对其进行调优, 而l_{2, 0}范数约束的参数k具有明确意义, 即选择特征的数量, 因此不需要进行参数的调节.

由于l_{2, 0}范数约束的上述优势, 学者们现已提出一些解决l_{2, 0}范数约束模型^{[24, 25, 26, 27]}.实际上, 模型仍类似l_{2, 1}范数, 通过某种排序选择特征, 而没有实现组特征选择.而本文提出将问题(2)转化为0-1整数约束, 直接选择得分为1对应特征的方法, 在优化过程中动态选择一组最优的特征.

在真实数据集MSRA25上利用l_{2, 0}范数和l_{2, 1}范数进行特征选择的区别如图2所示.2种方法均在数据集上选择10个特征.横坐标表示数据集的256个特征, 纵坐标表示2种不同特征选择方法对应的特征得分.图2(a)为基于l_{2, 1}范数的EGCFS^[23], 将求解的投影矩阵W的‖ w_i‖ ₂大小作为特征评分, 需要对分数进行排序, 选择得分前10的特征.然而, 从(a)中可观察到, 大多数分数非常相近, 因此根据得分大小单个选择的特征可能不是一组最佳的特征子集.图2(b)为本文提出的组特征选择方法.引入元素为0或1的特征选择向量, 并且约束元素为1的个数为选择特征的个数, 可通过直接选择得分为1的特征得到一组特征子集, 实现组特征选择.

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 两种特征选择方法在MSRA25数据集上选择10个特征的区别Fig.2 Difference of two feature selection strategies selecting 10 features on MSRA25 dataset

传统的基于图的无监督特征选择方法包括两个阶段:构造相似性矩阵和通过稀疏正则化进行特征选择.仅从原始数据矩阵中构造相似性矩阵, 在后续特征选择任务中保持不变, 那么由于原始数据通常包含噪声和冗余信息, 导致学习的相似性矩阵次优.本文提出基于l_{2, 0}范数稀疏性的无监督组特征选择方法(Unsupervised Group Feature Selection Method for Graph Optimization Based on l_{2, 0}-norm Sparsity, SUGFS), 将相似性矩阵学习与特征选择统一到同一框架, 同时学习具有精确连通分量的相似性矩阵S和具有l_{2, 0}范数约束的投影矩阵W.图学习可为特征选择提供精确的数据结构信息, 而特征选择过程又可为图学习去除冗余信息, 具体公式描述如下:

(3)

其中k为选择特征的个数, α 、 β 为正则化参数, 投影矩阵W∈ R^{d× m}, d为原始特征维数, m为投影维数.

为了精确选择k个特征, 约束W的非零行个数为k, 从而选择W的非零行 wTi对应的特征f_i.式(3)中投影矩阵W有两个功能:衡量特征的权重, 利用‖ w_i‖ 是否为0选择特征.但是, 由于l_{2, 0}范数为非凸约束, 很难直接求解.因此本文利用“ 解耦” 的思想, 引入0-1约束的特征选择向量r∈ {0, 1}^d, 分离W的第2个功能, 将W的非零行选择特征转化为利用向量r的分量为1的元素选择特征, 并且将约束

1Tdr=k

替代约束

‖ W‖ _{2, 0}=k,

直接选择k个特征.将式(3)中W^T替换为W^Tdiag(r), 得

(4)

这样, 通过特征选择向量r∈ {0, 1}^d, 可实现组特征选择, 同时选择一组最优的特征而不是逐个选择特征.

此外, 受FCM(Fuzzy C-means)在K-means聚类的基础上引入模糊因子以提高聚类精度的启发, 本文引入模糊相似因子ρ (ρ > 1), 进一步扩展模型(4), 提出基于l_{2, 0}范数稀疏性和模糊相似性的图优化无监督组特征选择方法(F-SUGFS), 具体公式描述如下:

(5)

为了求解SUGFS, 将目标函数(4)分解为4个子问题, 交替求解4个变量W, S, F, r.

2.2.1 固定W, S, F, 求解r

优化变量r∈ {0, 1}^d为一个0-1整数约束, 不易求解.本文利用l_p-box^[30]中p=2的情况, 称为l₂-box, 求解r的0-1整数规划问题, 将离散的0-1整数约束转化为2个连续的约束.具体方法如下.

命题1 l₂-box 二元集r∈ {0, 1}^d等价于一个“ 盒子” S_b与一个d-1维球体S_p的交集:

其中

l₂-box在二维情况下的几何解释如图3所示.当d=2, r为二维向量(x, y)时, r的0-1约束为r∈ {0, 1}^d, 即

x∈ {0, 1}, y∈ {0, 1}.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 l2-box在二维空间的几何解释Fig.3 Geometrical explanation of l2-box in two-dimensional space

根据命题1,

S_b={x∈ [0, 1], y∈ [0, 1]}

为一个实心正方形,

为半径为 22的圆.r∈ {0, 1}²的解恰好为S_b、S_p的四个交点(0, 0), (0, 1), (1, 0), (1, 1).

根据命题1, 固定W, S, F, 模型(4)变为

minr, r1, r2tr(W^Tdiag(r)XL_SX^Tdiag(r)W),
s.t. 1Td=k, r=r1_, r=r2_, r1_∈ Sb_, r2_∈ Sp_,

其中,

定义增广拉格朗日函数:

其中, η ₁∈ R^d, η ₂∈ R^d, η ₃∈ R, 为3个等式约束的拉格朗日乘子, σ > 0为惩罚参数.

为了求解模型(4), 利用ADMM迭代更新变量r, r₁, r₂和拉格朗日乘子η ₁, η ₂, η ₃.

1)更新变量r, r₁, r₂:

(6)

其中,

v=σ ( r1(t)+ r2(t))- η1(t)- η2(t)-( η3(t)-σ k)1_d,

PSb(a)=min{1_d, max{0_d, a}},

PSp(a)= 1d2+ d2(a-1d2)=a-1d2=2.

2)更新拉格朗日乘子η ₁, η ₂, η ₃:

2.2.2 固定S, r, F, 求解W

当S, r, F固定时, 模型(4)变为

(7)

W∈ R^{d× m}的最优解为A的最小的m个特征值对应的特征向量, 其中

A=diag(r)XL_SX^Tdiag(r).

2.2.3 固定W, S, r, 求解F

当W, S, r固定时, F的最优解为

minF∈Rn×cFTF=Itr(F^TL_SF), (8)

F∈ R^{n× c}的最优解为L_S的最小的c个特征值对应的特征向量.

2.2.4 固定W, r, F, 求解S

当W, r, F固定时, 模型(4)变为

(9)

可验证

2tr(F^TL_SF)= ∑i, j‖ f_i-f_j‖ 22S_ij, (10)

其中f_i为F∈ R^{n× c}的第i行.

将式(10)代入式(9), 可得

(11)

其中

d_ij=‖ W^Tdiag(r)x_i-W^Tdiag(r)x_j ‖22+

β ‖ f_i-f_j ‖22.

相似性矩阵S的第i行S_i表示第i个数据与其它数据点的相似性, 因此可独立求解每个S_i:

(12)

其中

d︿i= 12αd_i.

单纯性约束的S_i可利用文献[31]求解:

Si*=(u_i- λ¯*)₊, (13)

其中,

u_i= d︿i- 11Tnd︿i+ 1Tn,

λ¯*为

λ¯*= 1n∑i=1n( λ¯*-u_i)₊

的根.

相似性矩阵S表示数据间的相似性, 距离越近的数据具有越高的相似性.因此在实际应用中, 希望学习一个稀疏的S_i, 使每个数据x_i只与距离x_i最近的l个数据点相似, 相似度大于0, 与较远的数据点相似度为0.这样可获得良好的性能, 提高效率.

假设数据点x_i与其余数据点的距离由小到大为

d_{i, 1}, d_{i, 2}, … , d_{i, l}, d_{i, l+1}, … , d_{i, n},

因为与x_i距离最近的数据为x_i本身, d_{i, 1}=0, 所以x_i的l个近邻为d_{i, 2}, d_{i, 3}, …, d_{i, l+1}对应的数据.为了使S具有稀疏性, 每个S_i仅有固定的l个非零元素, 在实际求解过程中, 利用式(13)求解d_{i, 2}, … , d_{i, r}, d_{i, r+1}对应位置的S_{i, 2}, S_{i, 3}, …, S_{i, r+1}, 其余元素为0.

在SUGFS的基础上, 引入模糊相似因子ρ > 1, 进一步拓展为F-SUGFS, SUGFS表示为ρ =1的特殊情况, F-SUGFS变量W, r, F的求解与SUGFS类似.下面仅给出相似性矩阵S的求解.

当变量W, r, F固定时, 模型(5)转化为

(14)

其中

d︿ij=‖ W^Tdiag(r)x_i-W^Tdiag(r)x_j ‖22.

式(14)的增广拉格朗日函数定义为

L= ∑i, jn( d︿ijS ijρ+β ‖ f_i-f_j‖ 22S_ij+)

∑i=1nλ _i( ∑j=1nS_ij-1).

对S_ij求偏导等于0, 得

S_ij= (∑k=1n(QijQik)1ρ-1)-1, i≠j0, i=j(15)

其中

Q_ij= 1d︿ij(1+β ‖ f_i-f_j ‖22).

综上所述, F-SUGFS步骤如算法1所示.

算法1 F-SUGFS

输入 数据矩阵X∈ R^{d× n}, 选择特征个数k,

最近邻个数l, 投影矩阵维数m, 聚类数c

输出 特征选择向量r

初始化 求解式(1), 初始化相似性矩阵S, 拉普拉

斯矩阵

L_S=D- 12[S^ρ +(S^ρ )^T],

W^TW=I的投影矩阵W, 求解式(11), 初

始化F.

循环直至收敛.

step 1 利用ADMM求解r.

step 2 求解式(7), 更新W, 为A的最小m个特征值对应的特征向量.

step 3 求解式(8), 更新F, 为L_S的最小c个特征值对应的特征向量.

step 4 求解相似性矩阵S.当ρ =1时求解式(13); 当ρ > 1时求解式(15).

step 5 更新拉普拉斯矩阵L_S.

算法1交替求解4个变量W, S, F, r, 并且在每次迭代中单调减小式(4)中的目标函数值, 具体分析如下.

使用g(W^t, S^t, F^t, r^t)表示t次迭代时的目标函数(4), 则有

2.2.1节中利用l₂-box ADMM更新0-1向量r, 根据文献[30]可得l_p-box ADMM生成的变量序列的收敛性, 即

g(W^t, S^t, F^t, r^t)≥ g(W^t, S^t, F^t, r^t+1).

其次, 根据2.2.2节和2.2.3节, W^t+1和F^t+1为目标函数第t次迭代时的最优解:

因此有

g(W^t, S^t, F^t, r^t)≥ g(W^t+1, S^t, F^t+1, r^t+1).

最后根据式(12)和式(13), 得

g(W^t, S^t, F^t, r^t)≥ g(W^t+1, S^t+1, F^t+1, r^t+1).

同理可证F-SUGFS的收敛性.

根据算法1的步骤, 分析每步的时间复杂度.

step 1中通过ADMM过程求解r, 这个过程的主要步骤为计算式(6), 需要计算d× d矩阵的逆, 时间复杂度为O(d³), 假设step 1需要t₁次迭代, 因此step 1总共耗时O(t₁d³).考虑L_S的稀疏性, step 2和step 3的时间复杂度为O(n²l).step 4中需要独立求解S的每行, 时间复杂度为O(n²m+ndm).假设算法1需要迭代t₂次, 算法1的整体时间复杂度为

O(n²mt₂+d³t₁t₂).

为了说明F-SUGFS与其它无监督特征选择方法在计算复杂度上的差异, 5种无监督特征选择方法的计算复杂度如下.LS(Laplacian Score)^[14]为O(n²d), MCFS为O(n²d+ck³+nck²), UDFS为O(n²c+d³), SOGFS为O(n²m+d³), EGCFS为O(n²m+d³).

由对比结果可看出, 过滤式的特征选择方法LS具有较低的计算复杂度.相比其余4种嵌入式特征选择, MCFS计算复杂度较低.由于基于图的特征选择方法大多需要特征分解, 因此算法1的时间复杂度与基于图的特征选择算法SOGFS和EGCFS的时间复杂度相似.

本文实验在8个真实数据集上进行, 包括人脸数据集(MSRA25, Yale, COIL20)、生物数据集(Colon, Prostate_GE, GLIOMA, Lung)、语音字母识别数据集ISOLET、面部表情数据集JAFFE.数据集具体信息如表1所示.

表1

Table 1

表1(Table 1)

表1 实验数据集 Table 1 Experimental datasets 名称 样本数 特征数 类别数 选择特征的个数 MSRA25 1799 256 12 {50, 80, …, 200} ISOLET 1560 617 26 {50, 100, …, 300} JAFFE 213 676 10 {50, 100, …, 300} Yale 165 1024 15 {50, 100, …, 300} COIL20 1440 1024 20 {50, 100, …, 300} Colon 62 2000 2 {50, 100, …, 300} Lung 203 3312 5 {50, 100, …, 300} GLIOMA 50 4434 4 {50, 100, …, 300} Prostate_GE 102 5966 2 {50, 100, …, 300}

表1 实验数据集 Table 1 Experimental datasets

为了验证本文方法性能, 对比如下无监督特征选择方法.

1)Baseline.基线方法, 不进行特征选择, 使用原始数据进行K-means聚类任务.

2)LS^[14].经典的过滤式特征选择算法, 基本思想是根据特征的局部保持能力对特征进行评估, 选择得分最高的前K个特征作为最终选择的特征子集.

3)MCFS^[18].通过具有l₁范数正则化的回归模型衡量特征的重要性, 最近邻个数设置为5.

4)UDFS^[19].正则化参数取值范围为

{10^-2, 10^-1, 1, 10, 10², 10³}.

5)SOGFS^[21].同时进行局部结构学习和l_{2, 1}范数正则化的特征选择.正则化参数取值范围为

{10^-2, 10^-1, 1, 10, 10², 10³},

特征降维维数m设置在[ 13d, 23d]内, 最近邻个数设置为5.

6)EGCFS^[23].利用嵌入的图学习和约束选择不相关但有区别的特征.正则化参数α 、γ 取值范围为

{10^-2, 10^-1, 1, 10, 10², 10³}.

7)SUGFS.特征降维维数m设置在[ 13d, 23d]内, 最近邻个数l设置为5.

8)F-SUGFS.本文设置参数ρ =2, 与SUGFS进行对比.

为了评估所有无监督特征选择方法的性能, 将选择的特征用于基于K-means的聚类任务.为了避免K-means随机初始化的影响, 运行10次K-means聚类取平均结果.在评估每种方法的性能时, 使用2个经典的聚类算法评估指标:准确率(Accurary, ACC)及归一化互信息(Normalized Mutual Informa-tion, NMI).ACC和NMI值越大说明方法性能越优.

图4为8种无监督特征选择方法在9个数据集上选择特征个数与ACC和NMI的关系.在MSRA25数据集上选择50~200个特征, 间隔30.其余数据集上选择50~300个特征, 间隔50.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 各方法在9个数据集上选择不同特征数时的实验结果Fig.4 Experimental results of different methods with different feature numbers on 9 datasets

由图4可看出, 大部分特征选择方法仅选择少量特征进行聚类的结果便优于Baseline, 表明特征选择的必要性和有效性.特征选择可去除冗余、不相关特征及噪声, 选择具有代表性的特征, 提高聚类精度.

通过实验可看出, 并不是选择越多特征聚类效果越优.一般情况下, 聚类精度会随选择特征个数的增多呈现先增大后减小的趋势.因为随着选择特征个数的增多, 可能因此冗余特征或噪声被选择, 从而影响实验结果.

由图4也可直观看出, 在大部分数据集上, 本文方法在选择较少的特征时就取得比其他方法更高的聚类精度和归一化互信息.在面部表情数据集JAFFE和人脸数据集Yale上, SUGFS和F-SUGFS效果均较显著.

由图4还可观察到, 除了ISOLET、Lung数据集, 本文方法在其余7个数据集上无论选择多少特征, 均超过Baseline.相比其它嵌入式特征选择方法, 过滤式特征选择方法LS在多个数据集上性能较差, 这是因为过滤式特征选择未考虑针对后续学习器以选择特征子集.

表2和表3为各方法在9个数据集上的最佳聚类结果(ACC和NMI), 其中黑体数字为最佳值, 斜体数字为次优值.由表可看出, 本文方法在7个数据集上都取得最佳聚类结果, F-SUGFS取得和SUGFS同样好的结果, 并且在高维数据集GLIOMA与Prostate_GE上SUGFS的性能均有所提高.

表2

Table 2

表2(Table 2)

表2 各方法在9个数据集上的最高ACC值对比 Table 2 Optimal ACC comparison of different methods on 9 datasets % 数据集 Baseline MCFS LS UDFS SOGFS EGCFS SUGFS F-SUGFS MSRA25 51.53 54.88 53.25 54.29 53.91 52.81 57.52 56.26 ISOLET 56.79 62.00 57.76 58.99 59.12 62.54 62.30 60.75 JAFFE 68.22 76.29 74.46 71.92 72.72 75.21 78.97 77.75 Yale 38.42 42.18 41.52 41.21 42.85 41.03 46.48 46.91 COIL20 53.89 60.25 59.31 58.61 58.07 58.94 60.88 62.32 Colon 55.00 54.34 59.19 58.06 59.19 60.32 61.29 59.68 LUNG 69.66 75.43 72.17 72.91 65.52 71.43 74.78 71.67 GLIOMA 56.40 58.80 58.40 57.80 61.60 56.00 57.60 62.00 Prostate_GE 57.84 61.92 58.82 58.43 59.84 59.61 61.08 61.96

表2 各方法在9个数据集上的最高ACC值对比 Table 2 Optimal ACC comparison of different methods on 9 datasets %

表3

Table 3

表3(Table 3)

表3 各方法在9个数据集上的最高NMI值对比 Table 3 Optimal NMI comparison of different methods on 9 datasets % 数据集 Baseline MCFS LS UDFS SOGFS EGCFS SUGFS F-SUGFS MSRA25 58.24 63.29 62.25 61.42 61.44 60.13 67.16 63.98 ISOLET 73.32 74.13 72.91 73.43 73.96 76.79 75.47 74.92 JAFFE 74.56 85.77 81.04 78.33 79.80 82.21 85.61 84.62 Yale 45.06 48.84 46.75 46.73 48.97 45.95 53.54 53.59 COIL20 69.03 73.22 68.28 69.29 73.01 72.72 74.60 74.86 Colon 0.32 1.05 1.83 1.67 1.78 2.69 3.14 2.43 LUNG 52.25 59.22 51.61 58.07 49.92 57.83 58.97 57.62 GLIOMA 44.08 45.22 51.17 47.29 49.24 40.70 48.74 51.84 Prostate_GE 1.79 5.20 2.17 2.09 2.64 4.04 4.51 5.38

表3 各方法在9个数据集上的最高NMI值对比 Table 3 Optimal NMI comparison of different methods on 9 datasets %

表4和表5为各方法在9个数据集上均选择100个特征的聚类结果, 表中黑体数字表示最优值, 斜体数字表示次优值.表6给出本文方法与5种特征选择方法的运行时间对比.

表4

Table 4

表4(Table 4)

表4 各方法在9个数据集上选择100个特征的ACC值 Table 4 ACC of different methods with 100 selected features on 9 datasets % 数据集 Baseline MCFS LS UDFS SOGFS EGCFS SUGFS F-SUGFS MSRA25 51.53 54.88 48.46 51.23 52.93 52.70 53.78 55.26 ISOLET 56.79 59.48 53.58 54.17 52.56 51.99 62.30 60.75 JAFFE 68.22 73.71 69.95 64.55 72.72 71.74 78.64 75.59 Yale 38.42 38.73 38.55 36.12 40.06 38.79 44.36 45.82 COIL20 53.89 55.65 53.13 53.96 54.82 54.69 57.68 62.32 Colon 55.00 54.23 59.19 54.00 59.19 60.32 61.29 59.68 LUNG 69.66 75.43 63.25 61.82 58.82 67.98 73.60 70.54 GLIOMA 56.40 58.80 56.80 56.60 61.60 56.00 57.40 57.60 Prostate_GE 57.84 61.92 57.84 55.29 58.73 57.84 61.08 61.96

表4 各方法在9个数据集上选择100个特征的ACC值 Table 4 ACC of different methods with 100 selected features on 9 datasets %

表5

Table 5

表5(Table 5)

表5 各方法在9个数据集上选择100个特征的的NMI值 Table 5 NMI of different methods with 100 selected features on 9 datasets % 数据集 Baseline MCFS LS UDFS SOGFS EGCFS SUGFS F-SUGFS MSRA25 58.24 63.29 54.00 57.98 58.98 59.71 62.89 63.95 ISOLET 73.32 72.45 68.91 67.56 67.06 63.94 75.47 74.12 JAFFE 74.56 83.47 77.97 66.84 79.06 78.59 84.11 84.40 Yale 45.06 45.87 43.69 41.68 46.45 45.70 51.31 52.91 COIL20 69.03 72.28 62.35 63.17 70.04 68.01 73.02 74.86 Colon 0.32 0.58 1.34 1.67 1.78 2.69 3.14 2.43 LUNG 52.25 59.22 45.76 45.30 41.44 51.54 55.97 52.82 GLIOMA 44.08 40.39 51.17 43.89 49.22 39.33 47.75 48.51 Prostate_GE 1.79 5.20 1.76 1.80 2.64 2.83 4.51 5.38

表5 各方法在9个数据集上选择100个特征的的NMI值 Table 5 NMI of different methods with 100 selected features on 9 datasets %

表6

Table 6

表6(Table 6)

表6 各方法在9个数据集上的运行时间对比 Table 6 Running time comparison of different methods on 9 datasets s 数据集 LS MCFS UDFS SOGFS EGCFS SUGFS F-SUGFS MSRA25 0.531 1.107 5.101 12.630 13.174 6.842 9.889 ISOLET 0.033 0.611 7.104 14.995 7.186 12.198 7.913 JAFFE 0.066 0.895 1.954 2.627 1.702 2.128 2.498 Yale 0.046 0.634 2.877 14.233 11.655 11.810 6.294 COIL20 0.494 0.753 11.293 19.277 11.998 7.6458 9.039 Colon 0.475 0.667 19.119 67.458 40.213 38.754 39.86 LUNG 0.141 0.741 80.198 399.10 86.679 118.84 83.28 GLIOMA 0.550 3.392 185.89 475.81 102.31 159.19 133.01 Prostate_GE 0.748 3.741 446.93 533.32 257.85 345.85 338.22

表6 各方法在9个数据集上的运行时间对比 Table 6 Running time comparison of different methods on 9 datasets s

由表4和表5可看出, 本文方法选择特定个数的特征依然获得较优结果, 体现本文方法的稳定性.

对比SOGFS, 本文的l_{2, 0}范数约束在不同数据集上均取得显著优势, 表明l₂-box求解的0-1约束特征选择向量的有效性.对比Baseline, 本文方法明显提高Baseline的聚类精度, 在Yale数据集上提升最快, ACC和NMI值均提高20%左右, 在COIL20数据集上提升约15%, 在其余数据集上平均提升约8%.

由表6可知, 与2.5节复杂度分析一致, 过滤式特征选择方法LS的运行时间最短, 但从图4的实验结果来看, LS选择的特征聚类效果较差.本文方法与基于图的无监督特征选择方法SOGFS和EGCFS具有相近的运行时间, 随着数据集维数的增大, 运行时间也变长, 但从表1和表2的聚类效果来看, 本文方法具有较优性能.因此, 本文方法是一种相对高效的无监督特征选择方法.