稀疏子空间聚类的惩罚参数自调整交替方向法
计算机技术与发展第24卷摇第11期摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇Vol.24摇No.11
2014年11月Nov.摇2014COMPUTERTECHNOLOGYANDDEVELOPMENT
稀疏子空间聚类的惩罚参数自调整交替方向法
姚摇刚,杨摇敏
(南京邮电大学自动化学院,江苏南京210023)
摘摇要:稀疏子空间聚类是利用子空间并集中数据向量的稀疏表示,从而将数据划分到各自子空间,该类方法关键是求出最优稀疏解。文中采用交替方向法求稀疏解,交替方向法把复杂问题分解成简单的、有效求解的子问题,达到最优速度。在交替方向法求解过程中,通常惩罚因子是恒定不变的。文中提出一种惩罚因子参数自调整策略,根据每次迭代信息,调整惩罚因子参数。基于运动分割数据和Hopkins数据库实验,结果表明在迭代次数和运算时间上,稀疏子空间聚类的交替方向法及其惩罚参数自调整策略比传统算法有很大提高,而且对噪声数据也非常有效。关键词:子空间聚类;稀疏表示;L1范数正则化;交替方向法
中图分类号:TP301摇摇摇摇摇摇文献标识码:A摇摇摇摇摇摇摇文章编号:1673-629X(2014)11-0131-04doi:10.3969/j.issn.1673-629X.2014.11.033
AlternatingDirectionMethodofSelf-adjustingPenaltyParametersof
SparseSubspaceClustering
(CollegeofAutomation,NanjingUniversityofPostsandTelecommunications,
Nanjing210023,China)
YAOGang,YANGMin
Abstract:Sparsesubspaceclusteringusesthesparserepresentationofvectorslyingonaunionofsubspacetoclusterthedataintoseparatesubspaces.Thekeyofthisalgorithmistofindtheoptimalsparsesolution.AlternatingDirectionMethod(ADM)isappliedtosolvesparseprobleminthispaper.ADMdividesthecomplexproblemintosimpleandeffectivelysolvingsub-problemtoachieveoptimalspeed.IntheprocessoftheADMsolving,thepenaltyfactorisconstant.Inthispaper,apenaltyfactorself-adjustingstrategyisproposed,accordingtotheeachiterativeinformation,adjustthepenaltyfactorparameters.TheexperimentbasedonmotiondivisiondataandHop鄄kinsdatabaseshowsthattheproposedmethodhasgreatimprovementiniterationtimesandcomputingtimecomparedwithtraditionalal鄄gorithms,isalsovalidfornoisydata.
Keywords:subspaceclustering;sparserepresentation;L1normregularization;alternatingdirectionmethod
0摇引摇言
在聚类分析中,高维数据聚类是聚类分析技术的难点和重点,子空间聚类[1]是实现高维数据集聚类的有效途径。子空间聚类常见算法有基于谱聚类算法[2],谱聚类的关键是相似矩阵构造;而近年来,随着稀疏学习的流行,相似矩阵构造常有基于稀疏表示的
[3]
稀疏表示。然后在谱聚类框架下,对数据进行划分。这种方法能有效克服数据噪声。文中主要研究稀疏子空间聚类算法。
近年来,压缩感知中稀疏优化[5-6]越来越流行,交替方向法[7-8]也备受关注。交替方向法常用于求解具有可分离结构的目标函数凸优化问题。文中采用交替方向法处理稀疏子空间聚类[9]问题。稀疏子空间聚类的关键是最优稀疏求解,一般转化为L1范数问题,常用内点算法CVX优化工具包求解。但是内点算法在处理一定规模的问题时,会花费很大的计算量。文中采用交替方向法求解L1范数,在求解中,一般惩罚因
和基于低秩描述的
[4]
法利用稀疏表示对低维子空间的数据进行聚类。子空间并集里每个点,可用空间里所有点构成的字典来稀疏表示。因此关键是找到子空间里每个特征点的最优
。稀疏表示的子空间聚类算
收稿日期:2013-12-03摇摇摇摇摇摇修回日期:2014-03-13摇摇摇摇摇摇网络出版时间:2014-07-28基金项目:江苏省自然科学基金(BK2011758);南京邮电大学攀登计划(NY212066)
作者简介:姚摇刚(1988-),男,江苏宝应人,硕士研究生,研究方向为图像处理与模式分类;杨摇敏,副教授,从事计算机视觉和图像理解的研
究工作。
网络出版地址:http://www.cnki.net/kcms/detail/61.1450.TP.20140728.1224.030.html
摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第24卷·摇13摇2·
子是常数不变的。文中研究了一种惩罚因子参数自调整策略,其根据一种更新规则,惩罚因子参数可以自适应改变,这样加快了收敛速度。
文中主要先对稀疏子空间模型进行介绍,然后提出解决模型中最稀疏解的交替方向法及惩罚因子参数自调整策略,最后基于运动分割数据仿真实验与Hop鄄比。
kins数据库[10],给出了改进算法与原算法实验结果对
量{ui}
伊k的矩阵;
(4)把k个特征(列)向量排列在一起组成一个N(5)把生成矩阵每一行看作k维空间中的一个向输出:数据集Y的n子集划分y1,y2,…,yn。
k
i=1
;
量,使用k-means算法聚类成n类。
2摇稀疏子空间模型求解
稀疏子空间模型一般常用内点算法CVX优化工具包求解,文中用交替方向及其改进算法对其求解。1摇稀疏子空间聚类模型
稀疏子空间聚类是一种基于稀疏表示的子空间聚
类算法。假设数据集Y=[yy1,y2,…,yN]沂RM伊N对于每个数据样本i而言,直接使用原始数据集作为冗余字典,得每个数据点的稀疏表示ci:
摇s.t.摇
Y掖minC=,ZYC业
椰C+椰0+
姿Z
2
z
椰Z椰2F(1)
摇其中摇Cii=0摇i=1,2,…,N,C是样本yi基于数据集Y的稀疏表示;
即表示矩阵中非零元个数;
椰·椰椰·椰0表示l0范数,式F为Frobenius范数。
(1)是非凸的并且是一个NP-hard问题,常使
用凸松弛方式(用l1范数替代原有的l0范数),将上述非凸优化转变如下:
摇s.t.摇
Ymin掖C,Z业椰C椰1+姿
2
z椰Z椰2F(2)
C=YC+iZ
ii=0摇=1,2,…,N
求解上式得到每个数据点的稀疏表示,构造相似
度矩阵W=[w定义如下:
1,w2,…,wN]沂WN伊N。为了使W对称,W=C+C
T
从另一方面说,节点i和j之间边的权重等(3)
于
cij+cji本y。这里W由n个独立子空间生成,每个样
i可以由属于同一个子空间的其他样本进行稀疏重构,属于不同子空间的样本的稀疏表示系数为零。
在相似度矩阵W上用谱聚类算法[2]进行划分。算法1:谱聚类算法(SpectralClustering)。输入:n个线性子空间{Si}
ni=1
组成的数据点
{yi
}
Ni(1)=1
。
构造基于数据集Y的相似矩阵W;
L=I(2)-D计算相似矩阵-1/2WD1/2,D沂WW的N伊NLaplacian为对角矩阵矩阵,,对角元素其中矩阵
Dii=
(3)移j
W
ij
求出;
L的前n个特征值,以及其对应的特征向
2.1摇交替方向法
首先根据式(2)的等式约束,可以消除目标函数
的Z,并引入辅助矩阵A沂RN伊N写成如下形式:
,那么公式(2)可以重摇摇
min椰C姿2
z
s.t.A(C=,A)
C
椰1+
椰Y-YA椰2F(4)
摇引进矩阵摇Cii=0摇i=1,2,…,N驻沂RN伊N拉格朗日乘子,可以得到增广
拉格朗日函数:
L(C,A,驻)=椰C椰1+
姿z
椰Y-YA椰2F+掖驻,A-C业2
+
籽
其中,籽为惩罚因子;掖·业表示标准内积2
椰A-C椰2F(5)
。通过固定(Ck摇摇
-姿,驻k),对L关于A求导可得:摇摇摇摇z[YT摇籽[(AYk+-1YA(k+1)-Ck]=)]+驻k+
0(6)化简可得:
(姿zYTY+籽I)Ak+1=姿zYTY+籽Ck-驻k
一般情况下,YTY为对角阵时,可以得到Ak+(7)
1的封闭解:
Ak+1=(姿zYTY+籽I)-1·(姿zYTY+籽Ck-驻k)
固定(Ak+1以得到其封闭解,驻k:C),k+1对=LJ关于-diag(C求导得到J),其中
Ck+1[5](8)
,可
J=壮1k+1
籽
(A
+驻k
籽
)(9)
其中,壮浊如下形式:
(·)是收缩阈值操作符,其可以定义成壮浊(x)={
x-浊,x>浊
x0,+others
浊,x
(10)
这里的x可以是数字,向量或是一个矩阵。
当得到(Ck+1如下:
,Ak+1)时,可以更新拉格朗日乘子,
第11期摇摇摇摇摇摇摇摇摇摇摇摇摇姚摇刚等:稀疏子空间聚类的惩罚参数自调整交替方向法·133·
驻k+1=驻k+籽(Ak+1-Ck+1)
迭代次数。迭代停止标准为椰Ak-Ck椰¥臆着,
{10-3,10-4}
这三步不断重复执行直到收敛完成或达到设定的
(11)endwhile
输出:最优稀疏系数矩阵C*=Ck。
椰Ak-Ak-1椰¥臆着。其中着表示容错率,一般取着沂(2)的过程。
,下面算法展示了交替方向法执行式子
3摇实验仿真与分析
为了测试交替方向法及其改进算法与传统算法对比效果,将稀疏子空间聚类应用于视频点特征运动分割[12-13]中。假设F帧图像中有N个特征点,运动分割问题可以通过提取跟踪视频序列中f=1,2,…,F帧的N个特征点{xfi沂R2}
称为一个特征轨迹[14],与视频里F帧特征点xfi组成的
Ni=1
算法2:稀疏求解的ADM算法。初始化:k=0,C0,A0,驻0为0。
while椰Ak-Ck椰¥逸着,椰Ak-Ak-1椰¥逸着做下来解决。每个数据点yi也被
面操作:
(1)(姿通过求解下列等式更新+籽I)Ak+1=姿TY+Ak+1
zYTYzY籽Ck-驻k
+1壮(A(2)更新Ck:Ck+1=J-diag(J),其中J=1k+1驻k
籽
+
(3)更新籽
)驻k+1
k+1
-C
k+1
)
end(4)输出while
k=K+1
:驻
=驻k
+籽(A
k+1
:最优稀疏系数矩阵C*=Ck2.2摇惩罚参数自调整策略
。
在交替方向算法中,惩罚因子籽是固定不变的。
但是可以观察到固定的惩罚因子的交替方向法收敛很慢,而且选择一个最优的惩罚因子很困难。所以文中研究了对于惩罚因子籽的自调整策略[11]籽。
k+1=min(籽其中,籽是max{,籽茁籽k),茁的值定义如下:
(12)
茁=
maxk}的上限{
茁1,0,k其他
当籽max(椰Ck+1-Ck椰,椰Ak+1-Ak椰)
其中,茁(13)
0选;着逸1是常数。实际应用中变化的茁是首这种方法根据迭代停止标准来平衡误差并且引进2为常数,文中此处取着2=10-4。几个参数。
算法3:稀疏求解的惩罚参数自调整交替方向法。初始化:k=0,C0whileA-Ck
椰,A0,着驻0和籽k
,椰Ak
0。
k-1
¥-A面操作:
椰逸椰¥逸着做下
(1)k+1
(姿通过求解下列等式更新T
Y+籽=姿AzYkI)A
k+1
zYT
Y+籽kCk
-驻
k
-diag(J),其中J=壮(A(2)更驻新k
Ck+1:Ck+1=J1k+1籽+
籽(3)(4)更新k
)驻
k+1
:驻
k+1
=驻k
+籽k(A
k+1
-C
k+1
)
(5)籽kk=+1K=+min(1
籽max,茁籽k)2F维向量相对应y,定义如下:
i=[xT所以,所有帧的特征点组合成一个1
i,xT2i,…,xTFi
]2F伊N的矩阵
Y=[y1,y2,…,yN]为一个字典,求出每个特征点的稀疏表示,在稀疏子空间聚类算法中C,于是形,Y作成(2)的凸优化问题。
实验软件平台为Matlab7.10,硬件平台为Intel
Pentium统的笔记本双核。CPU,2.如图13所示GHz,2,给出了三个测试视频点特GB内存,WindowsXP系征序列[15]中的3帧
。
图1摇三个视频点特征序列分割聚类效果图
(只显示其中三帧)
表1列出了3个视频中每个视频的帧和特征点的数量。对于每个视频系列,用稀疏子空间算法来对跟踪每个帧中的特征点进行分割聚类。用不同颜色标记‘+爷区分表1摇。
三个视频序列的帧数与特征点数
视频序列1
视频序列2
视频序列3
帧数3017100特征点数
136
63
73
摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第24卷·摇13摇4·
摇摇表2为三种算法在聚类误差,迭代次数和迭代时间上的对比。子空间聚类的误差定义如下:
子空间聚类误差=
错分类点的数
特征点的总数
对于传统的内点优化算法,在算法效率上有很大的提高。文中在交替方向法基础上提出惩罚参数自调整策略,使迭代次数相应减少并使运行时间有较大的降低,说明该策略有较好的改进效果。稀疏子空间聚类的交替方向法的快速和并行计算方法,有待进一步研究。
参考文献:
[1]摇VidalR.Subspaceclustering[J].IEEESignalProcessingMa-[2]摇vonLuxburgU.Atutorialonspectralclustering[J].Statisticsgazine,2011,28(2):52-68.
表2摇三种算法平均子空间误差率、平均迭代
次数和平均运行时间对比(1)
算法名称
CVX工具内点优化算法
交替方向法平均子空间聚类误差率0.2560平均迭代次数91118平均运行时间60.3230.484参数自调整交替方向法
34
0.135
摇空间聚类误差率摇如表2所示,、交替方向法及其改进算法迭代次数还是运算时间,都比传统的,无论在子内点优化算法有较大的改进提高。这里CVX内点优化算法的迭代次数小于交替方向法,是因为内点算法每次迭代都要经过两次求导,所以精度上会相对提高点,但是缺点就是每次迭代花费时间比较长,而改进的算法在迭代时间和每次迭代效率都比CVX内点算法和交替方向法有较大提升。
为了进一步验证文中提出的方法,使用公共的运动分割测评库—Hopkins数据库[10]进行对比实验分析,验证文中提出的方法的鲁棒性和有效性。Hopkins包含了155个运动视频序列,其中有120个视频序列包含两个运动物体,35个视频序列包含三个刚性运动物体。包含两个运动物体的视频序列有256个特征点和30帧。包含三个运动物体视频序列有398个特征点和29帧。将文中提出的方法与传统方法应用于此数据库,如表3所示。
表3摇三种算法平均子空间误差率、平均迭代
次数和平均运行时间对比(2)
两个运动物体
三个运动物体
算法名称
平均子空
平均子间聚类误
平均迭平均运空间聚类平均迭平均运差率代次数行时间
误差率代次数行时间CVX点优化算法工具内0.18162152.730.32244267.47交替方向法0.031071.30.061283.85参数自调整交替方向法
0.03
33
0.38
0.05
36
0.90
摇类误差率摇实验进一步表明、迭代次数和平均运行时间都比交替方向法,文中提出的改进算法在平均聚和传统的内点算法有较大的改进。
4摇结束语
文中针对交替方向法进行改进,从实验结果得出,交替方向法是目前较好求解稀疏系数的优化算法,相
[3]摇ElhamifarandComputing,2007,17(4):395-416.ofIEEEconferenceE,VidalR.onSparsecomputersubspacevisionclustering[C]//Proc
[4]摇tion.Liu[s.l.]:IEEE,2009:2790-2797.andpatternrecogni鄄mentationGuangcan,LinZhouchen,YongYu.Robustsubspaceseg鄄
ternationalbyconferencelow-rankonrepresentation[machinelearning.C]//ProcHaifa:of27thNationalin鄄[5]摇Science文再文[J].运筹学学报,Foundation,2010:663-670.
印卧涛,,2012,16(3):49-64.
刘摇歆,等.压缩感知和稀疏优化简介[6]摇TropptionofJlinearA,WrightinverseSJ.problems[ComputationalJ].ProceedingsmethodsforofsparsetheIEEE,
solu鄄
[7]摇2010,98(6):948-958.
YangL1-problemsJunfeng,ZhangincompressiveYin.Alternatingsensing[directionJ].algorithmsfor
[8]摇cessingIEEESignalPro鄄YuanselectionXiaoming.Letters,2012,20(1):63-66.
models[J].AlternatingJournalofdirectionScientificmethodComputing,2012,51forcovariance
[9]摇(2):261-273.
Elhamifartheory,andE,VidalR.Sparsesubspace[10]nalysisapplications[J].IEEETransactionsclustering:algorithm,
onPatternA鄄TrontionsegmentationR,VidalandMachineR.AbenchmarkIntelligence,2013,35(11):2765-2781.
forthecomparisonof3-Dmo鄄
[11]puteralgorithms[C]//Procofconferenceoncom鄄Linvisionandpatternrecognition.[s.l.]:IEEE,2007.
directionZhouchen,Liutation[Cmethod]//ProceedingswithRisheng,SuadaptiveofadvancespenaltyZhixun.forLinearizedlow-rankalternating
represen鄄processingsystems.[s.l.]:[s.n.],2011:612-620.inneuralinformation[12]LauermotionF,SchnorrsegmentationC.Spectral[C]//ProcclusteringofIEEEoflinear12thsubspacesinternational
for
[13]conference青摇波,杨晨辉oncomputer,陈摇涛vision..基于分割的复杂运动跟踪的研究Kyoto:IEEE,2009:678-685.[14][J].王洪斌计算机技术与发展,李摇华.基于运动轨迹聚类的运动分割,2009,19(4):157-159.机应用,2003,23(10):1-3.
[J].计算[15]SugayabodyY,KanataniK.Multi-stageoptimizationformulti-tionandmotionSystems,2004,E-87D(7):1935-1942.
segmentation[J],IEICETransactionsonInforma鄄
稀疏子空间聚类的惩罚参数自调整交替方向法
作者：作者单位：刊名：英文刊名：年，卷(期)：
姚刚， 杨敏， YAO Gang， YANG Min
南京邮电大学 自动化学院,江苏 南京,210023计算机技术与发展
Computer Technology and Development2014(11)
技术与发展 2014(11)
引用本文格式：姚刚.杨敏.YAO Gang.YANG Min 稀疏子空间聚类的惩罚参数自调整交替方向法[期刊论文]-计算机