刘欣宇,韩晓红,宋 可
(太原理工大学 大数据学院,山西 晋中 030600)
降维[1]常用的方法是特征选择,根据所使用数据集的不同来源,特征选择可分为单视图特征选择方法与多视图特征选择方法。较早的特征选择方法大多使用单视图特征,但目前单视图特征已经满足不了日常生活的需要,所以高维度的多视图特征被广泛用于各种研究领域中,例如多媒体计算、机器学习和数据挖掘[2]。多视图特征可以从不同角度更精确、更全面地表征数据,其主要问题在于怎样有效地将多视图特征的多样性和一致性结合起来识别特征,以此来保留原始特征的一些关键特征。但是高维多视图特征将不可避免地产生昂贵的计算成本及大量的存储成本。这个问题的解决方法在于将多视图特征整合,并将多视图特征看成单视图特征进行特征选择。代表性的方法包括拉普拉斯分数(LapScor)[3]、光谱特征选择(SPEC)[4]、最小冗余谱特征选择算法(MRSF)[5]等。尽管这些方法取得了一定的成功,但这类方法忽略了视图内部间的特征相关性和不同视图特征间的关联性,使特征选择的性能受到了影响。为了解决以上的问题,本文将自适应相似性应用到无监督多视图特征选择中,并考虑视图内部特征的相关性及不同视图之间的特征关联性,同时,通过引入图正则化以利用数据的局部几何特性,使得同类别特征之间的联系更加密切,从而增加算法的鲁棒性。为了降低特定视图相似结构中潜在的数据噪声对特征选择的影响,本文引入L1/2稀疏范数在降低噪声的同时提高分类模型的准确率。
给定训练集X=[X1,X2,…,XV]∈RN×d, 其表示第V个视图的全部特征数据集,XV∈RN×dV代表第V个视图的样本,dV表示第V个视图的特征维数,xi表示矩阵X的第i行,xj表示矩阵X的第j列,为了选择最具有代表性的特征,本文首先要利用最小损失函数来使特征间的差距最小化
(1)
(2)
(3)
本文方法具有两个优势:①由于本文模型的每个变量都存在约束条件,所以可以采用固定某一变量,求其它变量的迭代优化算法;②我们并不是直接的对X进行聚类,而是将X投影到对应的聚类中心F附近,这样能够选择更具有分辨性的特征。
更新Q:固定F,S和W,使Q最小化,Q的优化可以推导为
(4)
对于L1/2稀疏约束项,我们参照已有的添加稀疏约束的方法[7]
(5)
更新F:固定其它变量,F的优化可以推导为
(6)
由文献[8]可知,图正则化理论中引入以下公式
(7)
对R进行变换,可得
(8)
我们对F进行更新时,需要考虑Tr(FLFT), 我们根据文献[9]中的方法,最终可得公式
(9)
其中,δij是步长参数。
令δij=-fij/(XTXF+FDT)i,j可得
(10)
最终可得到更新规则如下
(11)
更新S:固定其它变量,S的优化能够写成如下形式
(12)
式(12)能够被写成
(13)
Si,j表示S矩阵第i行、第j列的元素,S矩阵的优化过程是独立的,因此,S又能够被写成
(14)
(15)
式(15)可由文献[10]所求得。
更新W:与更新S类似,W也是独立于其它变量,因此,W矩阵的第j列能够被表示成
(16)
(17)
利用拉格朗日函数可得
(18)
ψ是拉格朗日乘数,通过对上式Wj求导,并令其为0,最终获得
(19)
算法1给出了求解(3)的迭代过程。
算法1:QFSW的更新与多视图特征选择
输出:协作相似结构S, 投影矩阵Q, 识别到的特征l。
(2)更新
(3)利用等式(5)来更新Q
(4)利用等式(11)来更新F
(5)利用等式(15)来更新S
(6) 利用等式(19)来更新W
(7) 直到收敛特征选择
(8)找出Qi,i=1,2,…,d并对其排序,最终将具有最高排名的一个特征确定为要选择的特征。
本实验采用4个数据集。包括MSRC-v1、Outdoor Scene、Handwritten Numeral、YouTube这4个数据集。详细的描述见表1。对于每个数据集,我们将数据集分类,然后再从每张图片中提取5类视觉特征,其中包括颜色矩特征、GIST特征、SIFT特征、CENTRIST特征和LBP特征。然后将提取出的特征改为.mat形式的文件加以应用。
表1 实验数据集相关描述
对每个数据集,本文将提出的方法与其它无监督多视图特征选择方法进行比较,其中进行比较的方法包括:LapScor[3]、SPEC[4]、MRSF[5]、AMFS[11]、MVFS[12]和AUMFS[13]。每次利用K-means聚类将实验重复50次,并取其平均值。
参数设置:在执行上述方法时,α,β,γ的取值范围为10-4到104。图1为MSRC-v1数据集的不同参数选择情况。
我们采用两个经典的评价指标:标准化互信息NMI和聚类准确率ACC。ACC和NMI的值越大,代表特征选择的效果越好,根据文献[14],ACC与NMI的定义如下:
ACC
(20)
其中,N为数据集的个数,yi是真实类别标签,ci预测类别标签。 δ(yi,c) 为函数,当y=c时,该函数值为1,否则为0。map(·)为最优映射函数。
NMI
(21)
其中,P表示K-means聚类结果,Q表示真实标签值,H(*) 表示熵,I(P,Q) 表示P、Q的互信息。
实验结果见表2、表3和图2、图3所示。表2、表3展示了在不同特征维度情况下的不同特征选择方法的ACC与NMI结果。图2、图3不同特征维度情况下的不同特征选择方法的ACC与NMI折线图。将本文提出的方法与LapScor、SPEC、MRSF、MVFS、AUMFS、AMFS进行比较,采用ACC评价指标,在数据集MSRC-v1、Outdoor Scene、Handwritten Numeral中,与最优方法SPEC、LapScor、LapScor相比分别提升了2%、10%、2%。采用NMI评价指标,在数据集MSRC-v1、Outdoor Scene、Handwritten Numeral中,与最优方法SPEC、LapScor、LapScor相比分别提升了10%、5%、1%。对比本文的方法与其它方法,ACC和NMI在各个数据集上均大于后者,验证了本文方法确实能够提高聚类学习的性能。
表2 聚类准确率
表3 标准化互信息
图2 不同算法的ACC对比
图3 不同算法的NMI对比
本文提出了一种基于自适应相似性的特征选择学习方法,该方法考虑了视图内部与视图间的相关性,同时将图正则化,L1/2正则化同时结合在目标函数中,在算法中,图正则化能够表现出较高的识别率、较好的鲁棒性和可解释性,从而更准确选择具有判别性的特征。L1/2正则化能够产生更加稀疏的解,降低噪声。结合这两种算法,本文提出的方法不但可以有效降低数据集的维度,也能提高数据分类的准确度。同时对数据的类别标签进行稀疏性约束将有助于提高分类的准确度。在很大程度上能够提高算法性能,通过在真实数据集上的实验能够验证所提算法的优越性。