1. 引言
随着大数据时代的到来,高维数据的种类越来越多,高维图像的处理越来越复杂。而子空间聚类的应用也更加广泛,如图像处理,运动分割以及计算机视觉等 [1] 。虽然高维数据越来越复杂,但是学者们认为高维数据通常位于低维子空间中。例如,人脸图像由几十万个像素组成,这些像素位于若干个低维子空间的并中,如图1所示,高维空间yi由低维空间S1、S2及S3共同组成,子空间聚类的目的是通过利用多个低维结构来洞察高维数据的内在结构。并将高维数据划分到这些低维子空间中 [2] 。
为了解决子空间聚类算法中的亲和矩阵学习问题,提出了稀疏子空间聚类算法(sparse subspace clustering algorithm, SSC) [3] 。然而,SSC的缺点是在追求数据表示矩阵的整体稀疏性以提高计算效率时忽略了每个数据样本的稀疏性。为了解决这个问题,许多学者针对各种特征学习任务提出了低秩表示(LRR)模型 [4] 。
![](//html.hanspub.org/file/14-1542921x8_hanspub.png?20230630101543843)
Figure 1. High-dimensional data composition schematic
图1. 高维数据组成示意图
2. 研究背景及相关工作
在本节中,我们概述了基于低秩表示的子空间聚类算法(LRR)和稀疏子空间聚类算法(SSC)。
2.1. 基于低秩表示的子空间聚类方法(LRR)
假设数据样本
为多个低维线性子空间的并,低维线性子空间表示为
,其中
是低维子空间。数据样本
,其中
是低秩矩阵,E表示随机的噪声项。求D的低阶近似值的问题公式如下:
(1)
其中
是一个参数,L是Y的低秩近似表示。但是由于秩函数的离散性,问题(1)很难解决。而且求噪声项E的
范数属于非凸问题,要求解也非常困难。所以使用秩函数的近似(即核范数)来代替秩函数 [5] ,而使用
的近似(即
范数)来代替
范数,问题(1)的公共凸松弛表示为:
(2)
公式(2)最优解能表示为 [6] :
(3)
其中,V为矩阵Y的奇异值分解后的右奇异矩阵,当数据矩阵被高斯白噪声污染时 [7] ,改写公式(1):
(4)
的最优解表示为 [8] :
(5)
其中
、
和
。矩阵根据集合
和
进行划分 [9] 。
2.2. 基于稀疏表示的子空间聚类方法(SSC)
稀疏子空间聚类(SSC)的核心内容是使数据集中的任何一个数据点都可以用其它数据点的稀疏线性组合来代替,同时还能够捕获数据的局部结构 [10] ,它解决以下凸优化问题:
(6)
当数据被高斯白噪声污染时,方程(6)可以表示为:
(7)
其中
是稀疏正则化常数。方程(7)能够使用ADMM优化,且能够得到有效解决。
3. 基于质心的自适应字典学习的多视图低秩稀疏子空间聚类(Centroid ADLMLRSSC)
考虑到SSC主要捕获数据的局部结构,而LRR主要对数据的全局结构进行计算,该两种方法均有自身的缺陷,因此我们在本节提出一种基于质心的自适应字典学习的多视图低秩稀疏子空间聚类。
对于一个具有
个视图的数据集X,其中每个
用它自己的一组
特征来描述。
目标是找到一个联合表示矩阵C,该矩阵能够平衡不同视图之间的一致性,同时使得到的解兼具稀疏性和低秩性。
为了使表示矩阵
跨越不同的视图,以获得共同的联合表示矩阵,制定了联合目标函数 [11] 。本节提出了一种ADLMLRSSC算法的正则化方案:基于质心的ADLMLRSSC。该算法强制不同视图之间的表示指向一个共同的质心。首先建立目标函数:
(8)
这里的
表示共识变量。这个目标函数可以通过对观点和共识变量的交替最小化循环来最小化。就是重复以下两个步骤:
1) 固定共识变量
,并更新每个
;
2) 固定
和更新
。
固定除
之外的所有变量,重写目标函数:
(9)
引入自适应字典学习,即将X替换为
,同时,使用ADMM解决凸优化问题。通过引入辅助变量
和
,可以得出以下公式:
(10)
可以推导出其增广拉格朗日函数是:
(11)
其中,
表示的是矩阵的内积,
表示的是惩罚参数,而
表示的是拉格朗日对偶变
量。为了解决这个凸优化问题,引入可变方向乘子法(ADMM)。用于收敛于由两个块凸可分问题组成的目标,但向量
和
互不依赖,因此可以单独的以其中作为一个变量块观察。
1) 在迭代K + 1次时更新
:
给定迭代k次时的
和
,将目标矩阵
最小化:
(12)
上式即由公式(13)对
求偏导之后,设置其导数为零得出。求出低秩矩阵A后。给定一个矩阵
和一个参数
,P可以通过以下方程来求解:
(13)
其中,P由
给出,它由矩阵
对应于前d个最小特征值的d个特征向量组成,
。
2) 在迭代K + 1次时更新
:
给定迭代k + 1次的
和迭代k次的
,最小化目标函数中的
:
(14)
公式(16)中的
最小化表达式为:
(15)
其中,
表示软阈值算子,定义为
和
。
表示的是对数据矩阵Y的奇异值
执行软阈值运算,而
。
3) 在迭代K + 1次时更新
:给定迭代K+1次后的
和迭代k次后的
,最小化拉格朗日函数中的
,其更新方法同样使用软阈值算子更新,即:
(16)
其中,
表示软阈值算子按入口方向应用于
。
4) 在迭代K + 1次时
的更新规则。
给定迭代k + 1次时的
和迭代k时的
和
,以上拉格朗日函数中目标相对于
的最小化即可以得到以下对
的求解公式:
(17)
更新
规则。将目标函数中关于
的偏导数设为零,即可得到
的封闭解:
(18)
5) 在迭代k+ 1次时双变量
的更新规则。
在迭代k + 1次时,固定
和
,用以下等式更新对偶变量:
(19)
为了将模型扩展到受加性高斯白噪声污染的数据,对(9)中的目标函数修改如下:
(20)
与干净数据的模型相比,唯一需要修改的更新规则是
,在迭代k + 1次时更新
:
和
的更新规则与噪声项无关,因此这些变量的更新方式不变。给定迭代k次时的
和
,
使等式中
最小化,为了简化公式,用Gram矩阵K来代替
[12] 。
在由内积导出的多维矩阵中,对角元素提供不同特征图自身的信息,从而反映出自身的特征信息,其他位置元素则提供不同特征图之间的相关信息,从而反映不同特征之间的紧密程度 [13] 。所以Gram矩阵通常用于度量维度本身的属性以及各维度之间的关系。
(21)
重复这些更新步骤,直到各变量均收敛或达到最大迭代次数,即停止迭代计算。通过在每次迭代后都验证以下约束来检查收敛性,只有当所有变量均小于
,才可以视作变量达到收敛条件:
(22)
在基于质心的ADLMLRSSC中,不需要跨视图组合亲和矩阵,因为联合亲和矩阵可以直接从质心矩阵计算,即
。表1汇总了基于质心的ADLMLRSSC算法的步骤。
![](Images/Table_Tmp.jpg)
Table 1. Centroid-based ADLMLRSSC algorithm steps
表1. 基于质心的ADLMLRSSC算法的步骤
4. 基于核的质心的自适应字典学习的多视图低秩稀疏子空间聚类算法 (Centroid KADLMLRSSC)
拉普拉斯的谱分解使谱聚类能够分离具有非线性超曲面的数据点。然而,通过将数据点表示为其他数据点的线性组合,ADLMLRSSC算法学习了对数据的线性子空间结构建模的亲和矩阵。为了使算法在非线性子空间数据中也可以有良好的聚类效果,本节提出通过隐式将数据点映射到高维特征空间来求解再生核希尔伯特空间(Reproducing kernel Hilbert space, RKHS)中的ADLMLRSSC。
首先定义一个函数
为将原始输入空间
映射到高维(可能是无限)特征空间
的函数。由于所提出的基于质心的KADLMLRSSC的损坏数据的更新规则仅依赖于点积
,因此该方法可在再生希尔伯特空间(RKHS)中求解,并可推广到非线性流形结构的建模中。
设
表示数据点集合
映射到高维特征空间。对于被噪声污染过的数据,基于质心的核ADLMLRSSC在希尔伯特空间中的目标函数为:
(23)
由于
是唯一依赖于
的变量,因此
和对偶变量
的更新规则保持不变。
迭代
次时的更新规则。给定在迭代k次时的
和对偶变量
,用Gram矩阵
代替点积
可以得到
的更新规则如下:
(24)
5. 实验及结果分析
5.1. 评价指标
本节使用五个不同的指标来评估聚类性能,对于所有这些指标,数值越高表示算法聚类性能越好。设由N个p维的数据
,真实数据共有R簇
,而聚类算法将数据划分为J簇
。
1) 精度(Precision):表示预测的正例样本中有多少是真正的正样本。
2) 召回率(Recall):表示示例中有多少正面示例被正确预测(全部找到)与所有的正面示例的比例。
3) F-分数(F-score):用于调和Precision和Recall这两个指标。
4) 标准化互信息(NMI):用于衡量两个数据分布的吻合程度。值越大表示结果与真实情况越吻合。
5) 调整后的rand指数(ARI):通常将ARI视作一个评估不同集群模型性能的通用指标。
5.2. 实验数据
3-sources dataset:该数据集是从三个在线新闻来源收集的新闻文章数据集:BBC、路透社和卫报。所有的词汇都储存在词袋中。在948篇文章中,使用了所有三个来源的169篇。数据集中的每一篇文章都用一个主要的主题类进行注释。
Reuters dataset:路透社数据集 [14] 包含了五种不同语言的文档特征及其在六个共同类别中的翻译。所有的文件都在文件袋里。使用原本用英文写的文件作为一个视图,并将其翻译成法文、德文、西班牙文和意大利文作为其他四个视图。从每个类别随机抽取了10份文件,得到了600份文件的数据集。
UCI Digit dataset:UCI数字数据集 [15] 可从UCI存储库获得。该数据集由200个从荷兰公用设施地图中提取的手写数字(0~9)示例组成。每个类中有200个示例,每个示例由六个特征集表示。根据C. Lu的实验,本实验使用了三个特征集:76个字符形状的傅里叶系数、216个轮廓相关和64个Karhunen-Love系数。
5.3. 参数设置
为了比较出各类算法的优势,将本文所提出的算法于原始类算法的数据进行对比,本实验一共包含四类算法,其中包含两类原始算法,即基于低秩表示的稀疏子空间聚类算法(LRSSC)与基于多视图的低秩稀疏子空间聚类算法(MLRSSC),而本文所提出的算法,即基于质心的ADLMLRSSC和基于质心的KADLMLRSSC,则需要通过实验来调整一系列参数,以使其效果达到最好。表2和表3分别统计了Centroid ADLMLRSSC算法和Centroid KADLMLRSSC算法测试各数据集的参数设置。
5.4. 实验结果
为了实验的均衡性,在每个数据库上都运行代码20次,并取平均值,同时计算出这20个值的标准差,再与其它算法的结果进行比较,以对比出算法的稳定性。为了保证实验的公平性,实验参数均调整到使算法聚类效果达到最好,针对不同的数据集,通过实验调整了它的λ1、λ3以及最大迭代次数。其中,数值最大的指标数值我们用粗体标注出来,标准差用括号放于指标数值的下方。表4记录了五类算法测试三个数据集的实验结果。
![](Images/Table_Tmp.jpg)
Table 2. The Centroid ADLMLRSSC algorithm runs the parameter settings for each data set
表2. Centroid ADLMLRSSC算法运行各数据集的参数设置
![](Images/Table_Tmp.jpg)
Table 3. The Centroid KADLMLRSSC algorithm runs the parameter settings for each data set
表3. Centroid KADLMLRSSC算法运行各数据集的参数设置
![](Images/Table_Tmp.jpg)
Table 4. Experimental data of five algorithms on three data sets
表4. 五类算法测试三个数据集的实验数据
5.5. 实验分析
根据表4显示的实验结果,可以得出:
1) 在3-source数据集上,Centroid ADLMLRSSC的F-score比MLRSSC高出7.3 %,Precision比LRSSC高出15.2%,Recall比MLRSSC高出%,NMI比MLRSSC高出2.1%,Adj-RI比MLRSSC高出13.8%。表明本文的算法的主题分类的效果比较好。
2) 在Reuters数据库中,的F-score比Centroid KADLMLRSSC高出16.2%,Precision比Centroid KADLMLRSSC高出12.5%,NMI比Centroid KADLMLRSSC高出30.7%,Adj-RI比Centroid KADLMLRSSC高出30.5%。结果表明,Centroid ADLMLRSSC算法对手写数字的聚类效果比较好。
3) 在UCI digit数据库中,Centroid ADLMLRSSC的F-score比Centroid KADLMLRSSC高出10.7%,Precision比Centroid KADLMLRSSC高出10.1%,NMI比Centroid KADLMLRSSC高出9.1%,Adj-RI比Centroid KADLMLRSSC高出12.6%。可以看出算法对于文字图像识别相比有较大的优势。
6. 结语
本文提出了一种基于质心的自适应字典学习的多视图低秩稀疏子空间聚类算法Centroid ADLMLRSSC,并将其投影到希尔伯特空间当中,衍生出新的算法,即基于核的质心的自适应字典学习的多视图低秩稀疏子空间聚类算法(Centroid KADLMLRSSC),Centroid KADLMLRSSC强制对公共质心进行特定于视图的表示,以获取数据信息。该算法最大的特点是在联合字典学习的同时,可以得到一个兼顾稀疏性和低秩约束的亲和矩阵。不仅定义了优化问题,制定了目标函数,而且通过ADMM方法得到了目标函数的最优解。此外,通过引入三个不同领域的多视图数据集,我们的实验结果表明,该算法优于目前大多数多视图子空间聚类算法。
基金项目
本研究得到了国家自然科学基金(批准号:61902160,61806088,62002142)、江苏省高等院校自然科学基金(批准号:19KJB520006)和江苏省自然科学基金的支持(批准号:BK20201057)。
NOTES
*通讯作者。