联合Capped范数极小化的子空间聚类算法*
2020-11-12涂志辉张子长朱雪芳胡文玉
涂志辉,陈 龙,张子长,朱雪芳,胡文玉
(赣南师范大学 数学与计算机科学学院,江西 赣州 341000)
1 引言
近年来,随着互联网发展迅速,数据收集变得越来越容易,最直接的结果是导致数据集变得越来越庞大和复杂,且这些数据通常由多种高维模式产生.然而,观测到的高维数据集通常源自于多个低维子空间的联合分布.因此需要一种能够查找多个低维子空间,并同时将数据聚类到不同子空间的技术.上述问题称为子空间聚类(Subspace Clustering, SC),近年来备受关注,已经广泛应用于图像处理和计算机视觉等实际问题.
在最近的20年,许多子空间聚类方法被提出,包括迭代方法、代数方法、统计方法和谱聚类方法[1].其中,基于谱聚类的方法在处理实际数据时显示出了优越性.基于谱聚类的方法包括2个主要步骤:首先找到一个能刻画数据间拓扑关系的关联矩阵,然后基于该关联矩阵利用聚类方法将数据划分到不同的子空间中.假若数据满足自表达性,即原始数据中每一个样本能由其余样本线性表示,谱聚类的一般模型可以表述为:
(1)
其中X表示原始数据矩阵,Z表示系数(关联)矩阵,φ(·)和δ(·)分别表示数据拟合项和正则项,Δ为系数矩阵Z的约束条件,λ为正则项的参数.
谱聚类方法成功的关键在于关联矩阵Z的构建,常见方法有稀疏子空间聚类方法(SparseSubspaceClustering,SSC)[1],低秩表示方法(LowRankRepresentation,LRR)[2]和自适应子空间分割方法(CorrelationAdaptiveSubspaceSegmentation,CASS)[3].其中SSC方法使用l1范数针对每个点找最稀疏的表示,LRR方法使用核范数去找低秩的关联矩阵,而CASS自适应考虑了数据间的相关性.然而,实际数据往往受到噪声的污染,并且噪声的统计分布十分复杂.正如[4-5]所指出,如果不能有效地描述噪声,系数矩阵将无法捕获数据间的内在拓扑关系,这将降低子空间聚类的性能.
为了解决这个问题,Lu等人[6]提出了通过cappedl1范数的鲁棒子空间聚类算法去惩罚噪声项,但该算法利用Frobenius范数作为矩阵秩的正则化,不能较好地逼近秩函数.针对上述问题,本文提出联合capped范数极小化的子空间聚类算法(JointCappedNormsMinimizationforSubspaceClusering,CNSC),使用capped核范数代替Frobenius范数,使模型能较好地刻画数据的低秩性,同时对数据噪声和异常值鲁棒.
2 相关工作
稀疏子空间聚类方法(SSC)[1]试图寻找每个数据点的稀疏表示,其模型在数学上可表述为:
(2)
SSC方法的不足是SSC单独寻找每个数据点的稀疏表示, 所得的矩阵Z可能过于稀疏,从而导致过度分割.
低秩表示方法(LRR)[2]目标是共同寻求所有数据的最低秩表示,LRR模型的优化模型表为:
(3)
Lu等人[7]提出最小二乘回归方法(LeastSquaresRegression,LSR).该方法采用Frobenius范数来替代秩函数,所得模型是:
(4)
可以证明,当数据来自独立子空间且无噪声时,SSC,LRR和LSR均可以得到块对角型的系数矩阵Z.这些方法主要聚焦于关联矩阵的构造,而忽视了噪声对聚类性能的影响.然而,真实数据总是会受到噪声或异常值的污染,通过上述求解方案得到的关联矩阵可能并不是块对角的.
最近,Lu等人[6]利用cappedl1范数作为噪声惩罚项,来提升聚类结果对噪声的鲁棒性.其优化模型如下:
(5)
3 联合capped范数的子空间聚类
首先介绍capped核范数的定义,然后给出联合cappedl1范数和capped核范数的聚类模型和求解算法,最后给出算法的收敛性证明.
3.1 capped核范数定义
(6)
由定义可知,相比于核范数,capped核范数是秩函数更好的近似.这是因为:当矩阵的最大奇异值不断变大时,矩阵的秩始终保持不变,但是矩阵的核范数却会随之发生很大改变.另一方面,由于capped核范数仅仅最小化小于ε的奇异值,故而奇异值的极端变化不会改变,甚至仍保持capped核范数的值.
图1给出了函数f(x)=min(|x|,ε)的函数图像,其中取ε=1.如图所示,f(x)在(-∞,-1)∪(1,+∞)区域上保持常值.可知,通过选择合适的ε,capped核范数能减少矩阵大奇异值对子空间聚类性能的影响.
图1 capped函数f(x)的函数图像(ε=1)
3.2 子空间聚类模型
我们联合矩阵的cappedl1范数与capped核范数建立如下的子空间聚类模型(CNSC):
(7)
特别地,式(7)可以等价写为:
(8)
其中n表示数据样本的个数,xi∈Rd表示数据矩阵X的第i个样本向量,zi表示关联表示向量,r=min(d,n).从式(8)可以看出,当ε1,ε2趋于无穷大时,目标函数变成了LRR模型,说明LRR方法是本文的一个特例.
问题(8)的求解看似非常困难,因为式(8)的两项都是凹函数.然而,受重加权(re-weighted)技巧的启发[8],这个问题能够简单地得以解决.首先,构造辅助变量D、si,并且使用下列的规则依次更新si、D和Z:
(9)
(10)
(11)
其中Z=U∑VT表示矩阵Z的奇异值分解,U=[u1,u2,…,ud],V=[v1,v2,…,vn],∑=diag(σ1,σ2,…,σr),奇异值σi从小到大排列,假设小于ε2的奇异值个数为k.
为求解子问题(11),我们将它分解成n个独立的子问题.具体的计算过程如下:
(12)
(13)
(14)
3.3 求解算法
通过上述分析,问题(7)和(8)的最优解可以通过迭代方法求得.我们将整个迭代过程描述成如下算法:
算法1联合capped范数的子空间聚类(CNSC)算法
输入 数据矩阵X,最大迭代数kmax,参数λ、ε1、ε2,k=1,Z0=单位矩阵;
输出 系数矩阵Z.
Step 3 根据式(14)更新Zk;
Step 4 若k≥kmax或收敛,输出结果;否则,k=k+1,转至step 1.
3.4 收敛性证明
受文献[10]启发,本小节证明算法1的收敛性.为此,需要引入如下几个引理:
引理1[9]对两个任意给定的Hermitian矩阵A、B∈Rn×n,假设它们的特征值满足λ1(A)≤λ2(A)≤…≤λn(A),λ1(B)≤λ2(B)≤…≤λn(B),则
(15)
(16)
于是,我们有
其中第一个不等式利用了凹函数性质,最后一个等式利用了特征值与矩阵迹的关系,而最后一个等式利用了引理1中式(15)的前半部分.移项即得式(16).
(17)
于是根据凹函数的性质,可得
移项整理后,得式(17).
定理1通过算法1,目标函数(8)随着迭代的进行而单调递减,直到收敛.
由Dk-1的定义,上式可改写为
(18)
也即
(19)
(20)
依次累加式(18)(19)和(20)的两边,从而得到:
最后,由于目标函数(8)有下界0,故算法1必收敛.
4 数值实验
将CNSC和3种经典的聚类方法进行对比,即稀疏子空间聚类方法(SSC)[1]、低秩表示子空间聚类方法(LRR)[2],cappedl1范数子空间聚类算法(cappedl1)[6].实验中,使用准确率(Accuracy,ACC)作为算法性能的衡量指标:
(21)
其中ri表示xi的各类算法预测的聚类标签,li表示真实的聚类标签,n表示子空间数量.为了保证实验对比的公平性,所有算法都独立进行10次实验,比较各算法运行结果的平均值.
根据式(8),本文的算法需要调整3个参数ε1,ε2,λ.我们参照文献[10]提到的方法进行调整.
4.1 合成数据
表1 四种方法聚类效果比较(合成数据)
由图2可知,本文提出的算法在噪声影响下仍可获得清晰的分块对角型系数矩阵,LRR和SSC方法都无法保持正确的块对角结构.相比之下,cappedl1和本文提出的CNSC算法拥有良好的分块对角特征,但是CNSC对角矩阵块更稠密.
图2 4种算法在合成数据上的关联矩阵对角特征比较
4.2 人脸数据聚类
图3 数据集部分例子
从表2和表3可以看出,在真实数据含有噪声和异常值的情况下,本文提出的CNCS方法迭代步数少,精确度最高.说明本文提出的算法聚类性能较好且对异常值鲁棒.
表2 4种方法在人脸集的聚类效果比较(5类)
表3 4种方法在人脸集的聚类效果比较(10类)
5 结束语
本文提出了一种联合capped范数的子空间聚类算法(CNCS),即分别使用cappedl1范数处理数据噪声和异常值和capped核范数逼近数据的低秩性.而且,通过数值实验,说明了本文算法的优越性.将来,我们将把本文算法推广至时序数据的子空间聚类问题.