自适应图正则化稀疏编码算法.pdf
《自适应图正则化稀疏编码算法.pdf》由会员分享,可在线阅读,更多相关《自适应图正则化稀疏编码算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、第 卷第期陕西师范大学学报(自然科学版)V o l N o 年月J o u r n a l o fS h a a n x iN o r m a lU n i v e r s i t y(N a t u r a lS c i e n c eE d i t i o n)S e p,人工智能专题(主持人:谢娟英)引用格式:余沁茹,卢桂馥,李华自适应图正则化稀疏编码算法J陕西师范大学学报(自然科学版),():YU QR,L UGF,L IH G r a p hr e g u l a r i z a t i o ns p a r s e c o d i n gw i t ha d a p t i v e
2、n e i g h b o u rJ J o u r n a l o fS h a a n x iN o r m a lU n i v e r s i t y(N a t u r a lS c i e n c eE d i t i o n),():D O I:/j c n k i j s n u 收稿日期:基金项目:国家自然科学基金(,);安徽省自然科学基金(MF )通信作者:卢桂馥,男,教授,博士,主要从事模式识别、机器学习与计算机视觉等方面的研究.E m a i l:l u g u i f u_j s j c o m自适应图正则化稀疏编码算法余沁茹,卢桂馥,李华(芜湖职业技术学院,安徽 芜
3、湖 ;安徽工程大学 计算机与信息学院,安徽 芜湖 )摘要:在G r a p h S C算法中,拉普拉斯图是预先定义并且固定不变的,并不会参与之后对于字典与稀疏编码的学习过程,而预先定义的拉普拉斯图往往不是最合适的.针对此问题,提出了自适应正则化稀疏编码(g r a p hr e g u l a r i z a t i o ns p a r s ec o d i n gw i t ha d a p t i v en e i g h b o u r,G r a p h S C AN)算法.该算法使用自适应方法构建合适的局部拉普拉斯图,然后将其加到S C的目标函数中;从而将图的构建和稀疏编码纳入到统
4、一框架中,使得图的构建与稀疏编码的运算同时迭代进行.在CMU人脸数据与C O I L 数据上进行的图像聚类实验结果验证了G r a p h S C AN算法的有效性.关键词:图正则化;稀疏编码;图聚类;自适应聚类中图分类号:T P 文献标志码:A文章编号:()G r a p hr e g u l a r i z a t i o ns p a r s ec o d i n gw i t ha d a p t i v en e i g h b o u rYU Q i n r u,L UG u i f u,L IH u a(W u h u I n s t i t u t eo fT e c h n
5、o l o g y,W u h u ,A n h u i,C h i n a;S c h o o l o fC o m p u t e r a n d I n f o r m a t i o n,A n h u i P o l y t e c h n i cU n i v e r s i t y,W u h u ,A n h u i,C h i n a)A b s t r a c t:I nt h eG r a p h S Ca l g o r i t h m,t h eL a p l a c i a ng r a p hi sp r e d e f i n e da n df i x e d
6、,a n dw i l ln o tp a r t i c i p a t e i nt h e s u b s e q u e n t l e a r n i n gp r o c e s so f t h ed i c t i o n a r ya n ds p a r s e c o d i n g,t h ep r e d e f i n e dL a p l a c i a ng r a p hi s n tt h e m o s ts u i t a b l e G r a p h r e g u l a r i z a t i o n s p a r s ec o d i n g
7、 w i t h a d a p t i v en e i g h b o u ra l g o r i t h m(G r a p h S C AN)i sp r o p o s e dt os o l v et h ep r o b l e m T h ea l g o r i t h m u s e sa na d a p t i v em e t h o d t oc o n s t r u c t a s u i t a b l e l o c a lL a p l a c i a ng r a p h,a n d t h e na d d s i t t o t h eS Co b
8、 j e c t i v ef u n c t i o n G r a p h S C AN i n c o r p o r a t e s g r a p h c o n s t r u c t i o n a n d s p a r s e c o d i n g i n t o a u n i f i e df r a m e w o r k,s ot h a tg r a p hc o n s t r u c t i o na n ds p a r s ec o d i n go p e r a t i o n sa r ei t e r a t i v e l yp e r f o
9、r m e ds i m u l t a n e o u s l y T h e e x p e r i m e n t a l r e s u l t so f i m a g e c l u s t e r i n go nCMUf a c ed a t aa n dC O I L d a t as u p p o r t t h ee f f e c t i v e n e s so f t h eG r a p h S C ANa l g o r i t h mK e y w o r d s:g r a p hr e g u l a r i z a t i o n;s p a r s
10、ec o d i n g;i m a g ec l u s t e r i n g;a d a p t i v ec l u s t e r i n g在图像处理过程中,图像本身的表示形式是影响处理结果的关键因素.稀疏表示已被证明是一种极有效的图像表示算法.近年来,为了实现稀疏表示,研究人员已经开发出例如稀疏主成分分析(P C A)、稀疏非负矩阵分解(NMF)等多种算法.作为稀疏表示最典型的方法之一,稀疏编码(s p a r e sc o d i n g,S C)在机器学习、信号处理和神经科学 等领域中得到了广泛的关注.陕西师范大学学报(自然科学版)第 卷S C是利用过完备字典来线性表示图像的
11、编码过程,其中的非零元素只占所有元素的极小部分,体现了编码的稀疏性.S C具有众多优点,如:稀疏表示时其每个数据点都表示为少量基本矢量的线性组合,表示方式更简洁;编码状的稀疏表示可以允许数据快速检索等.S C算法目前已被应用于如图像恢复、信号分类、人脸识别 和图像分类 等多个领域中.近年来,研究人员针对S C的部分缺点提出了改进算法.对于S C计算复杂度过高的问题,文献 提出了一种迭代的软阈值方法,该方法在负梯度方向上取B a r z i l a i B o r w e i n步长,然后将软阈值算子应用于结果,提升了S C的计算速率.L e e等 提出了一种特征符号搜索方法,将不可微L范数问题
12、简化为L正则化最小二乘问题,从而加快了优化过程.在传统方法中,S C的字典选择也是影响算法效果的一个关键因素,然而其字典一般是从标准库中选择的,甚至是从随机矩阵 中生成的.因此,有些学者试图通过为稀疏编码设计一个更合适的字典来提升S C的性能.A h a r o n等 提出的K S V D方法不同于之前利用标准库获得数据稀疏表示的算法,该 算 法 使 用 正 交 匹 配 追 踪 算 法(o r t h o g o n a lm a t c h i n gp u r s u i t,OMP)或基追踪算法(b a s i sp u r s u i t,B P),作为其学习词典迭代过程的一部分.还有
13、些学者致力于将稀疏编码与经典机器学习方法相结合以提出新的理论框架.文献 将线性判别分析(l i n e a rd i s c r i m i n a n ta n a l y s i s,L D A)与稀疏表示相结合提出了稀疏主成分判别分析的方法(s p a r s el i n e a rd i s c r i m i n a n ta n a l y s i s,S D A),该方法可以通过重建特性、辨别力和稀疏性来进行分类.文献 提出了一种新的判别方法,称为监督字典学习算法(s u p e r v i s e dd i c t i o n a r yl e a r n i n g,S D
14、 L),有效地利用图像分类任务中相应的稀疏信号分解去学习共享字典和判别模型.以上研究都在克服原始稀疏编码的不同缺点,但是都没有考虑到数据中潜在的几何结构.K a v u k c u o g l u等 提出了几种稀疏编码方法的变体,这些算法通过增加一些稀疏编码系数的附加约束来捕获数据中的结构,即它们可以通过添加额外的空间一致约束来学习,以获得局部不变的稀疏表示.G a o等 首次提出了使用流形学习算法学习数据几何结构的方法,但未明确提出详细的优化方案,所提方法的性能仅在图像分类任务上进行了评估.Z h e n g等 在文献 的基础上提出了一种新的算法,称为图正则化稀疏编码(g r a p hr
15、e g u l a r i z a t i o ns p a r s ec o d i n g,G r a p h S C),该算法明确考虑了数据的局部几何结构.G r a p h S C通过构建一个近邻图来编码数据中的几何信息,并使用谱图理论中的图拉普拉斯算子作为光滑算子来保留局部流形结构.与传统的S C算法相比,G r a p h S C具有更强大的分类能力.基于文献 的研究,G a o等 基于直方图交点的度构建相似度图,利用超图捕获样本之间的高阶关系,进一步提升了G r a p h S C的性能.此后,S h a等 提出将低秩表示(l o w r a n kr e p r e s e n
16、 t a t i o n,L R R)引入图正则化的处理过程,并就此提出了低秩正则化稀疏编码算法(l o w r a n kr e g u l a r i z e ds p a r e sc o d i n g,L o g S C).由 于 添 加 了 低 秩 约 束,L o g S C在部分任务中获得了较G r a p h S C更优秀的性能.然而,G r a p h S C及其改进方法中的拉普拉斯图都是预先定义且固定不变的,并不会参与之后对于字典与稀疏编码的学习过程,而预先定义的拉普拉斯图往往不是最合适的.针对这个问题,我们对G r a p h S C算法进行了改进,提出了自适应正则化稀疏
17、编码(g r a p hr e g u l a r i z a t i o ns p a r s ec o d i n gw i t ha d a p t i v en e i g h b o u r,G r a p h S C AN)算法.我们假设数据指向较小的距离代表更可能成为邻居,因此G r a p h S C AN可以从自适应性分解的结果中学习局部流形结构,并重新构造以保留精炼的局部结构,根据每个数据点的本地连通性选择自适应近邻(a d a p t i v en e i g h b o r,AN)以获得相似度图,然后将AN s正则化约束合并到G r a p h S C中.G r a p
18、 h S C AN将图的构建和稀疏编码纳入到统一框架中,使得内部局部结构学习的过程和图稀疏编码的过程同时进行,并最终提高了G r a p h S C的性能.相关工作 稀疏编码(S C)S C的目的是对于给定的一个数据矩阵,找到一组捕获高级语义的基础向量(即字典),并输出数据的稀疏表示.给定 一 个 数 据 矩 阵Xx,x,xnRnm,X的每一列都是样本矢量.令Aa,a,ak Rnk为字典矩阵,其中ai表示字典中的基础向量.令Ee,e,emRkm为系数矩阵,其中每一列都是数据点的稀疏表示.每个数据点都可以表示为字典中基向量的稀疏线性组合.稀疏编码的目标函数定义如下:m i ns t aic,i,
19、kXA EFmif(ei).()式中:F表示矩阵的F范数;f是度量的稀疏性第期余沁茹 等:自适应图正则化稀疏编码算法 函数,其最直接的选择是e的L范数.然而,当固定字典B时,系数e的极小化问题被证明是一个N P困难问题.因此,可以转而讨论这个问题的近似或松弛.近似求解该问题有种常用的方法,即匹配追踪(m a t c h i n g p u r s u i t,MP)和 基 追 踪(b a s i sp u r s u i t,B P).MP以贪心的方式一次只寻找一个条目的解,而B P用L范数代替L范数对原问题进行凸松弛.因此,由文献,可令f为f(ei)ei,此时目标函数化为m i ns t a
20、ic,i,kXA EFmiei.()由于()式中的目标函数可能仅A或E是凸的,个变量不能同时为凸.因此,可以通过固定一个变量、最小化另一个变量来迭代优化目标函数().图正则化稀疏编码(G r a p h S C)G r a p h S C将拉普拉斯图引入S C算法,并使用图拉普拉斯正则项来保留数据局部流形结构.对于给定一组n维数据点x,x,xm,构造一个有m个顶点的最近邻图G,其中每个顶点代表一个数据点.令W为图的权重矩阵,若xi是xj的最近邻或者xj是xi的最近邻,那么Wi j,否则Wi j.定 义xi的 度 为dimjWi j,且Dd i a g(d,d,dm).图正则化目标函数 可表示为
21、mi,j(eiej)Wi jt r(ETL E),()式中L是图拉普拉斯矩阵,LDS.由()、()式可得G r a p h S C的目标函数为m i ns t aic,i,kXA EFmieit r(ETL E).()自适应图正则化稀疏编码算法及其求解利用数据的局部几何结构,G r a p h S C算法提升了S C算法的计算能力.但G r a p h S C使用的拉普拉斯图会在全局计算前预先定义且固定不变,并不参与之后对于字典与稀疏编码的学习过程.我们提出自 适 应 方 图 正 则 化 稀 疏 编 码 的 算 法(g r a p hr e g u l a r i z a t i o ns p
22、 a r s ec o d i n gw i t ha d a p t i v en e i g h b o u r,G r a p h S C AN)对G r a p h S C所存在的这个问题进行了改进.G r a p h S C A N的算法模型设输入的原始数据集为X,X中的任意一数据点xi都有所有数据点x,x,xn可以作为近邻与之连接,连接的概率为si j.基于数据点间的欧几里得距离构造邻域矩阵,距离越小则成为最近邻的可能性越大.本文算法的求解形式如下:m i ns t aic,sTi,siXA EFnj(xixjsi j si j)nieit r(ETLSE).()()式第项对原始数
23、据集X求其字典及其稀疏编码,其中矩阵X为原始数据集,A代表字典阵,E代表其稀疏阵.()式第项是自适应正则化函数,使用其完成自适应相似矩阵的构造.其中和均为正则化参数,si Rn 表示向量,其第j个元素为si j.在所有xi有相同的概率即n时,第二项可写作m i nsTi,sinj(xixjsi j si j),()式中是正则化参数.因此,可以将()式重新表示为m i nsTi,sisidXi.()通过求解()式获得的矩阵SRnn,可被视为相似度矩阵 .可通过以下步骤来表示数据平滑度:ni,jeiejsi jni,jeisi jeTini,jeisi jeTjni,jei(Ds)i ieTini
24、,jeisi jeTj t r(ETDSE)t r(ETWSE)t r(ETLSE).()()式第项是度量第一项中稀疏矩阵E稀疏度的函数,设f(ei)ei作为度量函数.()式第项是局部图拉普拉斯约束函数,使用其增强传统低秩表示模型的局部性和稀疏性.其中LS是Si的拉普拉斯矩阵,LSDSWS,t r()表示矩阵的迹.G r a p h S C A N的算法求解本节提出求解G r a p h S C AN的更新算法,该算法通过固定其他变量更新一个变量的值来优化目标,此过程重复直到收敛.陕西师范大学学报(自然科学版)第 卷 固定A、E更新S观察()式不难发现,在固定A、E时更新S,最小化()式可等价
25、于解决下式:m i nsni,j(xixjsi j si j)t r(ETLSE),s t sTi,si,()式中.由()式结合()式有m i nsni,j(xixjsi j si jeiejsi j),s t sTi,si.()可通过逐个求解的方式求解()式,此时()式等价于m i nsini,j(xixjeiej)si j si j),s t sTi,si.()令dXi j xixj,dEi jeiej,且diRn,第j个元素为di jdXi j dEi j,将其代入()式可得m i nsTi,sisidXi.()设和为拉格朗日乘子,则()式的拉格朗日函数为R(si,i)siidXi(sT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自适应 正则 稀疏 编码 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。