第14卷第2期 智能系统学报 Vol.14 No.2 2019年3月 CAAI Transactions on Intelligent Systems Mar.2019 D0:10.11992/tis.201709033 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180418.0946.006.html 图正则测化字典对学习的轻度认知功能障碍预测 魏彩锋2，孙永聪2，曾宪华2 (1.重庆邮电大学计算机科学与技术学院，重庆400065,2.重庆邮电大学计算智能重庆市重点实验室，重庆 400065) 摘要：针对字典对学习(DPL方法只考虑了同类子字典的重构误差和不同类表示系数的稀疏性，没有考虑图 像间的几何近邻拓扑关系的问题。通过近邻保持使得在同类近邻投影系数之间的距离较小，而不同类投影系 数之间的距离大，能够有效提高字典对学习算法的分类性能，基于此提出了基于几何近邻拓扑关系的图正则化 的字典对学习(GDPL)算法。在ADNII数据集上对轻度认知功能障碍预测的实验表明，使用GDPL算法学习 的编码系数作为特征预测的准确率(ACC)和ROC曲线下的面积(AUC)比使用结合生物标志作为特征预测的 准确率提高了2%6%.使用GDPL算法比DPL算法的实验结果也有提高。 关键词：图正则化：字典对学习；几何近邻关系：图像分类；轻度认知功能障碍预测 中图分类号：TP391:R749 文献标志码：A文章编号：1673-4785(2019)02-0369-09 中文引用格式：魏彩锋，孙永聪，曾宪华.图正则化字典对学习的轻度认知功能障碍预测.智能系统学报，2019,14(2)： 369-377. 英文引用格式：VEI Caifeng,SUN Yongcong,ZENG Xianhua..Dictionary pair learning with graph regularization for mild cognit- ive impairment prediction[J.CAAI transactions on intelligent systems,2019,14(2):369-377. Dictionary pair learning with graph regularization for mild cognitive impairment prediction WEI Caifeng,SUN Yongcong,ZENG Xianhua2 (1.College of Computer Science and Technology,Chongqing University of Posts and Telecommunication,Chongqing 400065, China;2.Chongqing Key Laboratory of Computation Intelligence,Chongqing University of Posts and Telecommunications, Chongqing 400065,China) Abstract:Aiming at dictionary pair learning(DPL)methods only consider the reconstruction error of a sub-dictionary from the same class and the sparseness of coefficients from different classes,and do not consider the geometric neigh- borhood topological relationships between images.To improve the classification ability of DPL algorithms,we propose a DPL with graph regularization(GDPL)algorithm based on geometric neighborhood topological relationships.This al- gorithm is based on the idea that keeping the neighborhood relationship makes the distance between the neighborhood projection coefficients of the same kind small,while the distance between projection coefficients of different kinds is large.Experiments on mild cognitive impairment prediction using the ADNII dataset show that the coding coefficient learned from the GDPL algorithm is 2%~6%higher than that which uses the combined biomarker as feature prediction. according to accuracy (ACC)and area under curve (AUC)metrics.Moreover,the experimental result obtained using GDPL is also better than that obtained using DPL algorithm. Keywords:graph regularization;dictionary pair learning;geometric neighborhood relationship;image classification; mild cognitive impairment prediction 目前，多媒体技术飞速发展，图像数量呈指数 级增长，图像分类技术也得到了飞速发展。图像 分类方法主要包括分类器的设计和特征提取两个 收稿日期：2017-09-16.网络出版日期：2018-04-18. 基金项目：国家自然科学基金项目(61672120)：重庆市科委基 部分，目前对图像分类的研究主要集中在分类器 础学科和前沿技术研究一般项目(cstc2015 SjcyjA40036, 性能的改进和改善特征提取方法两方面。稀疏编 cstc2014jcyjA40049). 通信作者：曾宪华.E-mail:zengxh@cqupt.cdu.cn. 码（字典学习）0是图像分类的有效技术之一，用
DOI: 10.11992/tis.201709033 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180418.0946.006.html 图正则化字典对学习的轻度认知功能障碍预测 魏彩锋1,2，孙永聪1,2，曾宪华1,2 （1. 重庆邮电大学 计算机科学与技术学院，重庆 400065; 2. 重庆邮电大学 计算智能重庆市重点实验室，重庆 400065） 摘 要：针对字典对学习 (DPL) 方法只考虑了同类子字典的重构误差和不同类表示系数的稀疏性，没有考虑图 像间的几何近邻拓扑关系的问题。通过近邻保持使得在同类近邻投影系数之间的距离较小，而不同类投影系 数之间的距离大，能够有效提高字典对学习算法的分类性能，基于此提出了基于几何近邻拓扑关系的图正则化 的字典对学习 (GDPL) 算法。在 ADNI1 数据集上对轻度认知功能障碍预测的实验表明，使用 GDPL 算法学习 的编码系数作为特征预测的准确率 (ACC) 和 ROC 曲线下的面积 (AUC) 比使用结合生物标志作为特征预测的 准确率提高了 2%~6%，使用 GDPL 算法比 DPL 算法的实验结果也有提高。 关键词：图正则化；字典对学习；几何近邻关系；图像分类；轻度认知功能障碍预测 中图分类号：TP391; R749 文献标志码：A 文章编号：1673−4785(2019)02−0369−09 中文引用格式：魏彩锋, 孙永聪, 曾宪华. 图正则化字典对学习的轻度认知功能障碍预测[J]. 智能系统学报, 2019, 14(2): 369–377. 英文引用格式：WEI Caifeng, SUN Yongcong, ZENG Xianhua. Dictionary pair learning with graph regularization for mild cognitive impairment prediction[J]. CAAI transactions on intelligent systems, 2019, 14(2): 369–377. Dictionary pair learning with graph regularization for mild cognitive impairment prediction WEI Caifeng1,2 ，SUN Yongcong1,2 ，ZENG Xianhua1,2 (1. College of Computer Science and Technology, Chongqing University of Posts and Telecommunication, Chongqing 400065, China; 2. Chongqing Key Laboratory of Computation Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China) Abstract: Aiming at dictionary pair learning (DPL) methods only consider the reconstruction error of a sub-dictionary from the same class and the sparseness of coefficients from different classes, and do not consider the geometric neighborhood topological relationships between images. To improve the classification ability of DPL algorithms, we propose a DPL with graph regularization (GDPL) algorithm based on geometric neighborhood topological relationships. This algorithm is based on the idea that keeping the neighborhood relationship makes the distance between the neighborhood projection coefficients of the same kind small, while the distance between projection coefficients of different kinds is large. Experiments on mild cognitive impairment prediction using the ADNI1 dataset show that the coding coefficient learned from the GDPL algorithm is 2%~6% higher than that which uses the combined biomarker as feature prediction, according to accuracy (ACC) and area under curve (AUC) metrics. Moreover, the experimental result obtained using GDPL is also better than that obtained using DPL algorithm. Keywords: graph regularization; dictionary pair learning; geometric neighborhood relationship; image classification; mild cognitive impairment prediction 目前，多媒体技术飞速发展，图像数量呈指数 级增长，图像分类技术也得到了飞速发展。图像 分类方法主要包括分类器的设计和特征提取两个 部分，目前对图像分类的研究主要集中在分类器 性能的改进和改善特征提取方法两方面。稀疏编 码 (字典学习) [1-10]是图像分类的有效技术之一，用 收稿日期：2017−09−16. 网络出版日期：2018−04−18. 基金项目：国家自然科学基金项目 (61672120)；重庆市科委基 础学科和前沿技术研究一般项目 (cstc2015jcyjA40036， cstc2014jcyjA40049). 通信作者：曾宪华. E-mail：zengxh@cqupt.edu.cn. 第 14 卷第 2 期 智 能 系 统 学 报 Vol.14 No.2 2019 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2019
·370· 智能系统学报 第14卷 于图像分类的字典学习算法也可以分为2类：1)】 文提出的图正则化字典对学习算法用于轻度认知 学习字典把原始图像映射到有利于图像分类的空 功能障碍预测。 间上，用传统的分类器去分类；2)用稀疏系数所 表示出来的样本属性进行分类。 1相关工作 在用于图像分类的字典学习算法中，字典和 1.1字典学习 编码系数的设计从中起着关键作用。基于稀疏 表示的分类算法，将整个训练样本作为字典，利 设X=[X…X…Xx小∈R是一个K类p维的 用测试样本在字典上的重构误差分类。在字典中 训练样本，第k类样本X=[x……xm,X∈R0, 的每个原子都是一个样本，由于样本数量的限 k=1,2,…,K是第k类训练n样本，n=m+2+…+ 制，字典原子中有相同或相似的，还有一些则不 :+…+nx。字典学习模型的分类任务是通过利 包含在内造成分类错误。而Aharon M等提出的 用训练数据的类标签信息学习一个有效的数据表 KSVD算法学习的字典具有自适应性，能够更好 示模型去进行分类。在使用字典学习算法的图像 对信号进行稀疏表示。虽然，使用重构误差作为 分类研究中，如何设计对特征提取有效的字典和 损失函数，可以用于图像分类，但是还有许多因 编码系数是决定算法性能的关键因素四。对于字 素没有考虑到。Yang等提出Fisher字典学习在 典学习算法设计考虑的有三方面：1)稀疏表示残 自适应字典基础上，考虑到相同的样本之间的类 差（重构误差）小，使样本在稀疏表示时尽可能的 内散度较小，类间散度大，在目标函数上加入了 接近原始样本；2)对表示系数约束，使表示系数 识别系数项，提高分类能力。Jiang等提出的 稀疏；3)考虑能够更好提取更多的判别信息的判 LC-KVD算法，在KSVD算法基础上加入了标 别项。用于图像分类的判别字典学习模型672 签约束项。在文献[8]中，由于分别学习特征影射 可通常以表示为： 矩阵和字典，会影响特征影射矩阵的判别信息， minllX-DAl+g(A)+nf(D.A,Y) (1) 提出了同时学习投影矩阵和字典，为了能够提取 式中：、n是常量（平衡因子）：Y是样本X的标签 更多的判别信息，加入图正则项。构建近邻图， 向量；D是学习的综合字典；A是X在综合字典D 近邻且同类相似度为1，近邻但不同类相似度为 上的编码系数矩阵。在训练模型时，数据保真项 -1,其他为0。在文献[9]中图正则化中的相似度 X-DA是为了保证字典D的表示能力，使训 矩阵定义为两近邻样本的相似度为两样本之间的 练数据的重构误差最小，重构出来的图像尽可能 欧氏距离，不近邻样本之间的相似度为0。使用 的接近原始样本。正则项用于约束编码系数的稀 不同的相似矩阵，分类效果也不同。另一方面， 由于字典学习大多是使用编码系数的0或1范 疏性，其通常应用范数表示为： 3(A)=IIAllp (2) 数作正则项，在训练和测试阶段效率较低，运行 时间长。2014年在NIPS上Gu等1提出了字典 式中：I•是编码系数A正则项的常用形式(p<2), 对学习，联合学习一个综合字典和分析字典，用 使编码系数A在重建误差满足要求的情况下尽 分析字典去分析编码，由于综合字典的重构效果 可能地稀疏。f(D,A,Y)是字典学习用于分类的判 比较好，使用综合字典去重构图像。它不仅减少 别函数项，保证D和A的判别能力。 了在训练和测试阶段的时间复杂度，也提高了模 1.2字典对学习 型的分类能力。但是，字典对学习模型没有考虑 在1.1中描述的判别式字典学习模型是学习 图像的几何近邻拓扑关系。为了提高模型的分类 一个共享字典，对系数的约束都是使用或者是 能力，基于同类样本的系数之间的距离小，不同 1,范数对编码系数进行系数正则化约束，使训练 类系数之间的距离大的思想，提出了基于图正则 模型在训练阶段和测试阶段效率降低。Gu等u 化字典对学习(GDPL)算法。 为了提高模型在训练阶段和测试阶段的效率和整 在最近的综合研究中，用十倍交叉验证的 体的识别能力，提出了联合学习一个综合字典和 方法评估轻度认知功能障碍(MC)到阿尔兹海默 分析字典的字典对学习(DPL),不使用或者是1 症(AD)的预测，只有4种方法的实验结果比随机 范数对编码系数进行稀疏正则化，而是找到一个 分类的结果好，因此，提出新的方法提高MCI- 分析字典P,使训练样本X在分析字典P上线性 AD的预测是十分必要的。在图像分类中，并不 投影得出编码系数A,即A=PX保持稀疏性，重 是所有的特征都与识别分类有关，其中有一些是 建误差与判别约束保证下使训练样本X的稀疏 无关特征，将这些特征用于分类会出现过拟合现 表示变的更加有效且解决了out-of-sample问题。 象。由于稀疏表示中表示系数具有稀疏性，将本 字典对模型描述表示如下：
于图像分类的字典学习算法也可以分为 2 类：1) 学习字典把原始图像映射到有利于图像分类的空 间上，用传统的分类器去分类；2) 用稀疏系数所 表示出来的样本属性进行分类。 在用于图像分类的字典学习算法中，字典和 编码系数的设计从中起着关键作用[3]。基于稀疏 表示的分类算法[4] ，将整个训练样本作为字典，利 用测试样本在字典上的重构误差分类。在字典中 的每个原子都是一个样本，由于样本数量的限 制，字典原子中有相同或相似的，还有一些则不 包含在内造成分类错误。而 Aharon M 等提出的 KSVD 算法[5]学习的字典具有自适应性，能够更好 对信号进行稀疏表示。虽然，使用重构误差作为 损失函数，可以用于图像分类，但是还有许多因 素没有考虑到。Yang 等 [6]提出 Fisher 字典学习在 自适应字典基础上，考虑到相同的样本之间的类 内散度较小，类间散度大，在目标函数上加入了 识别系数项，提高分类能力。Jiang 等 [7]提出的 LC-KVD 算法，在 KSVD 算法[5]基础上加入了标 签约束项。在文献[8]中，由于分别学习特征影射 矩阵和字典，会影响特征影射矩阵的判别信息， 提出了同时学习投影矩阵和字典，为了能够提取 更多的判别信息，加入图正则项。构建近邻图， 近邻且同类相似度为 1，近邻但不同类相似度为 −1，其他为 0。在文献[9]中图正则化中的相似度 矩阵定义为两近邻样本的相似度为两样本之间的 欧氏距离，不近邻样本之间的相似度为 0。使用 不同的相似矩阵，分类效果也不同。另一方面， 由于字典学习[3-9]大多是使用编码系数的 0 或 1 范 数作正则项，在训练和测试阶段效率较低，运行 时间长。2014 年在 NIPS 上 Gu 等 [10]提出了字典 对学习，联合学习一个综合字典和分析字典，用 分析字典去分析编码，由于综合字典的重构效果 比较好，使用综合字典去重构图像。它不仅减少 了在训练和测试阶段的时间复杂度，也提高了模 型的分类能力。但是，字典对学习模型没有考虑 图像的几何近邻拓扑关系。为了提高模型的分类 能力，基于同类样本的系数之间的距离小，不同 类系数之间的距离大的思想，提出了基于图正则 化字典对学习 (GDPL) 算法。 在最近的综合研究[11]中，用十倍交叉验证的 方法评估轻度认知功能障碍 (MCI) 到阿尔兹海默 症 (AD) 的预测，只有 4 种方法的实验结果比随机 分类的结果好，因此，提出新的方法提高 MCIAD 的预测是十分必要的。在图像分类中，并不 是所有的特征都与识别分类有关，其中有一些是 无关特征，将这些特征用于分类会出现过拟合现 象。由于稀疏表示中表示系数具有稀疏性，将本 文提出的图正则化字典对学习算法用于轻度认知 功能障碍预测。 1 相关工作 1.1 字典学习 X = [X1 ··· Xk ··· XK] ∈ R p×n Xk = [x1 ··· xi ··· xnk ] Xk ∈ R p×nk , k = 1,2,··· ,K nk n = n1 +n2 +···+ nk +···+nK 设 是一个 K 类 p 维的 训练样本，第 k类样本 ， 是第 k 类训练 样本， 。字典学习模型的分类任务是通过利 用训练数据的类标签信息学习一个有效的数据表 示模型去进行分类。在使用字典学习算法的图像 分类研究中，如何设计对特征提取有效的字典和 编码系数是决定算法性能的关键因素[1]。对于字 典学习算法设计考虑的有三方面：1) 稀疏表示残 差 (重构误差) 小，使样本在稀疏表示时尽可能的 接近原始样本；2) 对表示系数约束，使表示系数 稀疏；3) 考虑能够更好提取更多的判别信息的判 别项。用于图像分类的判别字典学习模型[6-7, 12-13] 可通常以表示为： min D,A ||X− DA||2 F +λg(A)+η f(D, A,Y) (1) λ、η ||X− DA||2 F 式中： 是常量 (平衡因子)；Y 是样本 X 的标签 向量；D 是学习的综合字典；A 是 X 在综合字典 D 上的编码系数矩阵。在训练模型时，数据保真项 是为了保证字典 D 的表示能力，使训 练数据的重构误差最小，重构出来的图像尽可能 的接近原始样本。正则项用于约束编码系数的稀 疏性，其通常应用范数表示为： g(A) = ||A||p (2) || • ||p p < 2 f(D, A,Y) 式中： 是编码系数 A 正则项的常用形式 ( )， 使编码系数 A 在重建误差满足要求的情况下尽 可能地稀疏。 是字典学习用于分类的判 别函数项，保证 D 和 A 的判别能力。 1.2 字典对学习 l0 l1 l0 l1 在 1.1 中描述的判别式字典学习模型是学习 一个共享字典，对系数的约束都是使用 或者是 范数对编码系数进行系数正则化约束，使训练 模型在训练阶段和测试阶段效率降低。Gu 等 [10] 为了提高模型在训练阶段和测试阶段的效率和整 体的识别能力，提出了联合学习一个综合字典和 分析字典的字典对学习 (DPL)，不使用 或者是 范数对编码系数进行稀疏正则化，而是找到一个 分析字典 P，使训练样本 X 在分析字典 P 上线性 投影得出编码系数 A，即 A = PX 保持稀疏性，重 建误差与判别约束保证下使训练样本 X 的稀疏 表示变的更加有效且解决了 out-of-sample 问题。 字典对模型描述表示如下： ·370· 智 能 系 统 学 报 第 14 卷
第2期 魏彩锋，等：图正则化字典对学习的轻度认知功能障碍预 ·371· (P.D)minllX-DPX+f(D.P.X,Y) (3) 本；Px.和Px,是训练样本x和x,在分析字典P 式中：fD,P,X,Y)表示判别函数。D和P是一个 的投影，即分析编码系数。 字典对：分析字典P用于编码X,综合字典D用 在大多数图正则项，都是对数据集构建近邻 于重构X。学习一个结构综合字典D=[D 图，用图的边的权值表示数据之间的关联度。 D4…Dx]和结构分析字典P=[P…P…PJ,其 但是本文利用样本总数去平衡类内和类间的距 中{D,P}是第k类的子字典对。对于分析字典 离，已经证明能够提高在字典上的编码系数的判 P使其满足第i(i≠k)类样本在第k类的子字典 别能力)，因此，本文中相似度矩阵S是依据x P上的投影系数为空，即PX:≈O,k≠i,也就是 和x,的标签保证相应系数之间的相似性。用 编码系数矩阵PX接近块正交。对于合成字典 训练集构建近邻图，用标签信息判读样本是否近 D,使其子字典D与投影编码矩阵PX能够很好 邻。如果x和x标签相同，则为近邻，相似度为 的重构样本X,要求字典对有最小的重构误差： Sw=l/m,;如果x和x,标签不同，则不近邻，相 似度为Sm=-1/n-n)。相似度矩阵S的第u行 吧∑X-DP (4) v列的元素为： k=1 因此，DPL模型的目标函数可以写为： Su= 1/no 1x)=1(x) -1/(n-nx).otherwise (7 B,D1=吧X-DPX形+PX (5) 式中：1(x)和(x)表示的是样本x和x,的类标 s.tld,l≤1 签；n)是训练样本中标签为1(x)的样本总数。 式中：x是X在整个训练集中的补集；是一个 矩阵L=C-S,其中C=diag{c1,c2,…,cn}是对角矩 标准常量；4，是合成字典的第i个原子。 阵，且cm=∑=imo 在DPL算法的基础上，构建近邻图保持原始 2图正则化字典对学习 图像间的近邻关系，由此提出了图正则化字典对 字典对学习只考虑图像的重构误差和不同类 学习(GDPL)算法。GDPL算法的目标函数可写为： 的分析字典和样本的投影系数尽可能的小，没有 考虑原始样本的近邻几何结构，引入图正则化， P,D1=ag吧∑X-DPX形+APX)+ k=1 使低维表示能够保留原始样本的近邻结构。 2.1图正则化字典对学习 22r- (8) 在流形学习中，假设两个高维空间的相邻的 式中：入和B是平衡因子，在公式(9)中的第1项 两点，在其对应的低维空间仍保持其在高维空间 是重构误差项，重构误差项尽可能的小，使重构 的几何近邻拓扑关系。为了使样本之间可区分， 出来的图像与原图像尽可能的接近。是X在 并同时保持原始图像的几何近邻结构，且使同类 整个训练样本上的补集，第2项是第K类以外的 样本在分析字典P上的投影系数之间距离小，不 训练样本，在第K类的分析字典上的编码系数尽 同类之间的距离大。对编码系数的图正则项约束 可能小，使编码系数尽可能的稀疏。第3项是图 表示为： 正则项，使图像在字典上的编码系数仍旧保持原 始图像的近邻关系。 (6) =1= 引入变量编码系数A,使A=PX,目标函数可 式中：n是所有样本总数；u和v是第u(w训练样 以写为下面式子： PD=gne∑dK.-DAf+rP,x-A斤+P,R)+I-ap之IPu-PxS =1y= g驴e2aX-nAe+nx-Ae+n+I-oe2(Pe广-2PP+Prs P.D 立a-nAie+nX-Ai+R+I-o2P-22PPs (9 字2a式-aA+P-Ae+4e-0-PXP-Pn8Px arg mina (IX:-D:Af+rlP-A+)+(1-a)Bur(PXLXT P) P.D
{P, D} = min P,D ||X− DPX||2 F + f(D, P,X,Y) (3) f(D, P,X,Y) D = [D1 ··· Dk ··· DK] P = [P1 ··· Pk ··· PK] {Dk , Pk} i , k Pk PkXi ≈ 0,∀k , i Dk PkXk Xk 式中： 表示判别函数。D 和 P 是一个 字典对：分析字典 P 用于编码 X，综合字典 D 用 于重构 X。学习一个结构综合字典 和结构分析字典 ，其 中 是第 k 类的子字典对。对于分析字典 P 使其满足第 i ( ) 类样本在第 k 类的子字典 上的投影系数为空，即 ，也就是 编码系数矩阵 PX 接近块正交。对于合成字典 D，使其子字典 与投影编码矩阵 能够很好 的重构样本 ，要求字典对有最小的重构误差： min P,D ∑K k=1 ||Xk − DkPkXk ||2 F (4) 因此，DPL 模型的目标函数可以写为： {P, D} = min P,D ∑K k=1 ||Xk − DkPkXk ||2 F +λ||PkXk ||2 F s.t.||di ||2 2 ⩽ 1 (5) Xk Xk λ di i 式中： 是 在整个训练集中的补集； 是一个 标准常量； 是合成字典的第 个原子。 2 图正则化字典对学习 字典对学习只考虑图像的重构误差和不同类 的分析字典和样本的投影系数尽可能的小，没有 考虑原始样本的近邻几何结构，引入图正则化， 使低维表示能够保留原始样本的近邻结构。 2.1 图正则化字典对学习 在流形学习中，假设两个高维空间的相邻的 两点，在其对应的低维空间仍保持其在高维空间 的几何近邻拓扑关系。为了使样本之间可区分， 并同时保持原始图像的几何近邻结构，且使同类 样本在分析字典 P 上的投影系数之间距离小，不 同类之间的距离大。对编码系数的图正则项约束 表示为： f(X) = ∑n u=1 ∑n v=1 ||Pxu − Pxv ||2 2Suv (6) 式中：n 是所有样本总数；u 和 v 是第 u(v) 训练样 本； Pxu 和 Pxv 是训练样本 xu 和 xv 在分析字典 P 的投影，即分析编码系数。 xu xv xu xv Suv = 1/nl(xu) xu xv Suv = −1/(n−nl(xu )) u v 在大多数图正则项，都是对数据集构建近邻 图 [9] ，用图的边的权值表示数据之间的关联度。 但是本文利用样本总数去平衡类内和类间的距 离，已经证明能够提高在字典上的编码系数的判 别能力[12] ，因此，本文中相似度矩阵 S 是依据 和 的标签保证相应系数之间的相似性[12]。用 训练集构建近邻图，用标签信息判读样本是否近 邻。如果 和 标签相同，则为近邻，相似度为 ；如果 和 标签不同，则不近邻，相 似度为 。相似度矩阵 S 的第 行 列的元素为： Suv = { 1/nl(xu ) , l(xu) = l(xv) −1/(n−nl(xu)), otherwise (7) l(xu) l(xv) xu xv nl(xu) l(xu) L = C−S C = diag{c1, c2,··· , cn} cv = ∑ v=1 Suv 式中： 和 表示的是样本 和 的类标 签； 是训练样本中标签为 的样本总数。 矩阵 ，其中 是对角矩 阵，且 。 在 DPL 算法的基础上，构建近邻图保持原始 图像间的近邻关系，由此提出了图正则化字典对 学习 (GDPL) 算法。GDPL 算法的目标函数可写为： {P ∗ ,D ∗ } =argmin P,D ∑K k=1 (||Xk − DkPkXk ||2 F +λ||PkX¯ k ||2 F )+ β ∑n u=1 ∑n v=1 ||Pxu − Pxv ||2 2Suv (8) λ β X¯ k Xk 式中： 和 是平衡因子，在公式 (9) 中的第 1 项 是重构误差项，重构误差项尽可能的小，使重构 出来的图像与原图像尽可能的接近。 是 在 整个训练样本上的补集，第 2 项是第 K 类以外的 训练样本，在第 K 类的分析字典上的编码系数尽 可能小，使编码系数尽可能的稀疏。第 3 项是图 正则项，使图像在字典上的编码系数仍旧保持原 始图像的近邻关系。 引入变量编码系数 A ，使 A = PX ，目标函数可 以写为下面式子： {P ∗ ,D ∗ } = argmin P,D α ∑K k=1 (||Xk − DkAk ||2 F +τ||PkXk − Ak ||2 F +λ||PkX¯ k ||2 F )+(1−α)β ∑n u=1 ∑n v=1 ||Pxu − Pxv ||2 FSuv = argmin P,D α ∑K k=1 (||Xk − DkAk ||2 F +τ||PkXk − Ak ||2 F +λ||PkX¯ k ||2 F )+(1−α)β ∑n u=1 ∑n v=1 ( (Pxu) 2 −2PxuPxv +(Pxv) 2 ) Suv = argmin P,D α ∑K k=1 (||Xk − DkAk ||2 F +τ||PkXk − Ak ||2 F +λ||PkX¯ k ||2 F )+(1−α)β ∑n u=1 cu(Pxu) 2 − ∑n u=1 ∑n v=1 PxuPxvSuv = argmin P,D α ∑K k=1 (||Xk − DkAk ||2 F +τ||PkXk − Ak ||2 F +λ||PkX¯ k ||2 F )+(1−α)β(PX)C(PX) T −(PX)S(PX) T = argmin P,D α ∑K k=1 (||Xk − DkAk ||2 F +τ||PkXk − Ak ||2 F +λ||PkX¯ k ||2 F )+(1−α)βtr(PXLXT P T ) (9) 第 2 期 魏彩锋，等：图正则化字典对学习的轻度认知功能障碍预测 ·371·
·372· 智能系统学报 第14卷 式中：r()表示矩阵的迹。矩阵L=C-S,C= 对S求导： diag{c1,c2,…,cn}该对角矩阵的对角元素是S的行 0 =-2p(D+T)+2pSe (列)的元素之和。 aSk 2.2图正则化字典对学习 o =0得： OSk 在流形学习中，假设两个高维空间的相邻的 S&=DD+T (15) 两随机初始化分析字典P和综合字典D,之后， 2.3图正则化字典对学习训练算法 迭代更新编码系数A和{P,D。 由于算法中的图正则项，需要先用训练样本 1)固定综合字典D和分析字典P,更新编 构建近邻图，计算出相似矩阵S和拉普拉斯矩阵 码系数A,由于含有A:的式子前面有相同的系 L。利用目标函数优化过程进行迭代更新，学习 数α，在计算的过程中可以消去，所以可以利用 字典对P,D。图正则化字典对学习算法的训练 式(10)解出A: 过程在算法1中详细描述。 Ak=(DID:+D(DIX:+TPX) (10) 算法1GDPL训练算法 2)固定编码系数Ak,更新综合字典D和分 输入训练样本X=[X1X2…Xx],训练样本 析字典Po 标签信息Y=[YY2…Y,参数α，x,B,子字典原 子数m。最大迭代次数max。 =agma2PX-A+P,X眼 P 1)利用样本标签信息构建近邻图。根据样本 Bu(PXLXP!) (11) 标签信息判断样本是否为近邻点。若x和x,标 D,=argmina∑IX-DAf 签相同，则为近邻点，相似度S=1/m:若x和x k=1 标签不相同，则不是近邻点，相似度S=-1/n-n s.tld服≤1 对角矩阵C=diag{c,c2,…,cn},其中c,=∑=1Sw, 对P封闭求解，即 拉普拉斯矩阵L=C-S。 P.=argmgnaP 2)初始化：随机生成综合字典D。和分析字 k=1 典Po,迭代次数t=0。 (1-a)Btr(PXLXTPE) 3)For i=1:K 对P求导，得 While未收敛（具体的在收敛性分析中）执行 -2P.(rrX.Xj+alS8+ 下面步骤： aP (1-a)BXLXT +yD-2aTAXI 1)固定字典Dk和P,由目标函数中含有A 令品0科 的式子求解得出式(10)，根据式(10)，更新编码系 数A; Pi=QTA XI(QTX XI+a XX+ (12) 2)固定编码系数Ak,由式(11)中Dk使用 yI+(1-a)BXLXT)-1 ADMM算法得出式(I4)更新字典Dk;在ADMM 式中：y=10e-4,1是单位矩阵，在公式加人（一个 算法中D、Sk、T根据式(14)、(15)、(13)中最后一 极小的常数)是为了保证逆运算有解。 个式子更新直到达到ADMM算法的收敛条件 在公式(13)中用交替方向乘子算法(AMMD) 停止。 对D优化求解。具体的求解过程如下所示： 3)固定编码系数Ak,由式(11)中P解出式(12)， 根据式(12)更新字典P: arg minDAD? End While End For S+=argmin∑plID-Se+T2Is.s服≤1 输出综合字典D,分析字典P。 TD)T+D(D-SD 2.4、分类方法 (13) 在图像分类中，并不是所有的特征都与识别 对D求导： 分类有关，其中有一些是无关特征，将这些特征 =2D.(4A+pD-2XAI+(S-T) 用于分类会出现过拟合现象。另一方面，稀疏表 令品=附： 示是在超完备字典中用尽可能少的原子去表示原 来的图像信号，其中的表示系数具有稀疏性。用 D:=(XxA+P(S:-T)(AAI+pD- (14) 表示系数作为特征去分类，可以减少无关特征的影
tr(•) L = C−S C = diag{c1, c2,··· , cn} 式中： 表示矩阵的迹。矩阵 , 该对角矩阵的对角元素是 S 的行 (列) 的元素之和。 2.2 图正则化字典对学习 {P, D} 在流形学习中，假设两个高维空间的相邻的 两随机初始化分析字典 P 和综合字典 D，之后， 迭代更新编码系数 A 和 。 Dk Pk Ak Ak α Ak 1) 固定综合字典 和分析字典 ，更新编 码系数 ，由于含有 的式子前面有相同的系 数 ，在计算的过程中可以消去，所以可以利用 式 (10) 解出 ： Ak = (D T k Dk +τI) −1 (D T k Xk +τPkXk) (10) Ak Dk Pk 2) 固定编码系数 ，更新综合字典 和分 析字典 。 Pk = argmin Pk α ∑K k=1 τ||PkXk − Ak ||2 F +λ||PkXk ||2 F+ βtr(PkXLXT P T k ) Dk = argmin Dk α ∑K k=1 ||Xk − DkAk ||2 F s.t.||di ||2 2 ⩽ 1 (11) 对 Pk 封闭求解，即 Pk = argmin Pk α ∑K k=1 τ||PkXk − Ak ||2 F +λ||PkXk ||2 F+ (1−α)βtr(PkXLXT P T k ) 对 Pk求导，得 ∂ ∂Pk = 2Pk(ατXkX T k +αλX¯ kX¯ T k + (1−α)βXLXT +γI)−2ατAkX T k ∂ ∂Pk 令 = 0 ，得 P ∗ k = ατAkX T k (ατXkX T k +αλ3X¯ kX¯ T k + γI+(1−α)βXLXT ) −1 (12) γ = 10e−4 式中： ，I 是单位矩阵，在公式加入 (一个 极小的常数) 是为了保证逆运算有解。 在公式 (13) 中用交替方向乘子算法 (AMMD)[8] 对 D 优化求解。具体的求解过程如下所示： D (r+1) = argmin D ∑K k=1 ||Xk − DkAk ||2 F +ρ||Dk −S (r) k + K (r) k ||2 F S (r+1) = argmin S ∑K k=1 ρ||D (r+1) k −Sk +T (r) k ||2 F s.t.||si ||2 2 ⩽ 1 T (r+1) = T (r) + D (r+1) k −S (r+1) k (13) 对 Dk求导： ∂ ∂Dk = 2Dk(AkA T k +ρI)−2(XkA T k +ρ(S r k −T r k )) ∂ ∂Dk 令 = 0 得： Dk = (XkA T k +ρ(S r k −T r k ))(AkA T k +ρI) −1 (14) 对 Sk求导： ∂ ∂Sk = −2ρ(D (r+1) k +T (r) k )+2ρSk ∂ ∂Sk 令 = 0 得： Sk = D (r+1) k +T (r) k (15) 2.3 图正则化字典对学习训练算法 S L {P, D} 由于算法中的图正则项，需要先用训练样本 构建近邻图，计算出相似矩阵 和拉普拉斯矩阵 。利用目标函数优化过程进行迭代更新，学习 字典对 。图正则化字典对学习算法的训练 过程在算法 1 中详细描述。 算法 1 GDPL 训练算法 X = [X1 X2 ··· XK] Y = [Y1 Y2 ··· Yk] α,τ, λ, β m 输入 训练样本 ，训练样本 标签信息 ，参数 ，子字典原 子数 。最大迭代次数 max。 xu xv Suv = 1/nl(xu) xu xv Suv = −1/(n−nl(xu )) C = diag{c1, c2,··· , cn} cv = ∑ v=1 Suv L = C−S 1) 利用样本标签信息构建近邻图。根据样本 标签信息判断样本是否为近邻点。若 和 标 签相同，则为近邻点，相似度 ；若 和 标签不相同，则不是近邻点，相似度 。 对角矩阵 ，其中 ， 拉普拉斯矩阵 。 D0 P0 t = 0 2) 初始化：随机生成综合字典 和分析字 典 ，迭代次数 。 3) For i = 1 : K While 未收敛 (具体的在收敛性分析中) 执行 下面步骤： Dk Pk Ak Ak 1) 固定字典 和 ，由目标函数中含有 的式子求解得出式 (10)，根据式 (10)，更新编码系 数 ； Ak Dk Dk Dk Sk Tk 2) 固定编码系数 ，由式 (11) 中 使用 ADMM 算法得出式 (14) 更新字典 ；在 ADMM 算法中 、 、 根据式 (14)、(15)、(13) 中最后一 个式子更新直到达到 ADMM 算法的收敛条件 停止。 Ak Pk Pk 3) 固定编码系数 ，由式 (11) 中 解出式 (12)， 根据式 (12) 更新字典 ； End While End For 输出 综合字典 D，分析字典 P。 2.4 分类方法 在图像分类中，并不是所有的特征都与识别 分类有关，其中有一些是无关特征，将这些特征 用于分类会出现过拟合现象。另一方面，稀疏表 示是在超完备字典中用尽可能少的原子去表示原 来的图像信号，其中的表示系数具有稀疏性。用 表示系数作为特征去分类，可以减少无关特征的影 ·372· 智 能 系 统 学 报 第 14 卷
第2期 魏彩锋，等：图正则化字典对学习的轻度认知功能障碍预 ·373· 响，提高模型的判别能力。用ADNI1数据集进行 3.2收敛性分析 验证，具体的实验结果在第4部分中，使用编码系数 在目标函数式(1)中对于{(D,P),(A)》的迭代 用分类器分类效果比直接使用分类器的效果好。 更新是一个双凸问题。在优化求解的过程中，固 在分类模型中，输入训练样本X使用算法1 定A对D和P求解是一个凸问题；固定D和P 训练出来的综合字典D和分析字典P,由A,计算 对A求解也是一个凸问题，因此目标函数是一个 出训练集在分析字典上的投影系数即稀疏表示中 双凸问题。根据文献[10]的补充材料，收敛时目 的编码系数Arm=PX,由测试样本Xe和分析字 标函数的能量值达到一个局部最小值。为了避免 典P,可以计算出测试集的编码系数Aet=PXe。 在更新过程中达到收敛条件，不同类之间单个样 将编码系数作为特征，用分类器对测试样本进行 本的能量不在同一个数量级上，所以，本文的收 分类。 敛条件是单个样本的能量到达某一局部最小。目 3算法分析 标函数中各项的曲线如图1所示。图1只是以 GDPL算法过程中使用其中一类迭代过程中的目 本节主要对提出的图正则化字典对算法 标函数值画出曲线为例。算法1中while后面的 (GDPL)进行时间复杂度分析和收敛性分析，该算 收敛条件为前后两次迭代的整个目标函数值之差 法通过联合学习一个综合字典和分析字典，将样 小于0，单个样本的重构误差的绝对值小于1，保 本在分析字典上的投影作为表示系数，减小了算 证目标函数值在每次迭代过程中逐渐减小，最大 法的时间复杂度。 迭代次数为50。 3.1时间复杂度分析 ×109 损失函数值 在GDPL算法中主要是计算训练阶段的时间 2 0 复杂度。在训练阶段Ak和{P,D}交替更新，每 -2 次更新过程相同，在此以一次更新为例。固定 -4 {P,D}由式(1O)更新Ak,Ak更新的时间复杂度 -6 -8 是一个逆矩阵和一个矩阵相乘的时间复杂度即 mXm的矩阵，{DDk+x的时间复杂度为O(m), -12 -14 在mXk的矩阵{rPX+DTX}中，PX的时间复 -16 杂度为O(mpm),DX的时间复杂度也是O(mpm), -18 10 2030405060 所以矩阵{rPXk+DX}的时间复杂度为Omp)。 迭代次数 矩阵(DD+tD'和(rPX+DX)相乘的时间复 图1目标函数值随迭代次数变化 杂度为O(m2),整个更新Ak的时间复杂度为 Fig.1 The value of the objective function varies with the Om3+mpm4+m2)。固定Ak,更新{P,D}。Pk由 number of iterations 式(12)进行更新，在式(14)中p×p的矩阵 图1中单个样本的整个目标函数值在开始到 (rXx+3+yl+BXLX的时间复杂度为 40次的变化趋势是平行趋于0，之后变成一个比 O(p2ne+p2(n-n)+pm2+p2n),但是在迭代过程中该 较大的负值，由于相似度矩阵不是半正定矩阵， 矩阵值不变，在初始化阶段提前计算出来，在迭 由此使图正则项的值变成负值，并引起其他项的 代过程中不需要重复计算，因此不影响更新P的 变化。并且由于图像的损失函数一般都不会小 时间复杂度。只需计算（πXX+3可+yl+BXLX 于0，所以，从图1可以看出算法在2~40次之间 逆矩阵的时间复杂度为O(p)。A?的时间复杂 是局部收敛的。所以，有的实验在第2次迭代就 度为O(mmp),两矩阵相乘的时间复杂度为 达到最优值。 Omp2),更新P.的时间复杂度为O(mmp+p23+mp2)。 4实验结果与分析 使用ADMM更新Dk,将ADMM算法中迭代更新 次数记为H,ADDM算法中，主要计算在式 为了验证图正则化字典对学习算法在图像分 (13)中D更新过程的时间复杂度。D根据式 类中的性能，本文在ADNI1数据集上进行验证。 (14)更新的，式(14)中XA、AkA、(AkA+pl)的 ADNI由国际老年研究所、生物医学成像和生物 逆矩阵、XAT(AAT+p)-1的时间复杂度分别为 工程研究所、美国食品和药物管理局、民营医药 O(pnm)、Om2n)、O(m3)、O(pm2),更新Dk整个过 企业和非营利组织在2003年启动，资金为60万 程的时间复杂度为O(H(pmm,+m2n:+m3+pm2)》。 美元。ADNI的主要目标是测试是否能通过组合
响，提高模型的判别能力。用 ADNI1 数据集进行 验证，具体的实验结果在第 4 部分中，使用编码系数 用分类器分类效果比直接使用分类器[14]的效果好。 Atrain = PX Xtest Atest = PXtest 在分类模型中，输入训练样本 X 使用算法 1 训练出来的综合字典 D 和分析字典 P，由 A，计算 出训练集在分析字典上的投影系数即稀疏表示中 的编码系数 ，由测试样本 和分析字 典 P，可以计算出测试集的编码系数 。 将编码系数作为特征，用分类器对测试样本进行 分类。 3 算法分析 本节主要对提出的图正则化字典对算 法 (GDPL) 进行时间复杂度分析和收敛性分析，该算 法通过联合学习一个综合字典和分析字典，将样 本在分析字典上的投影作为表示系数，减小了算 法的时间复杂度。 3.1 时间复杂度分析 Ak {Pk , Dk} {Pk , Dk} Ak Ak m×m {D T k Dk +τI} O(m 3 ) m×nk {τPkXk + D T k Xk} PkXk O(mpnk) D T k Xk O(mpnk) {τPkXk + D T k Xk} O(mpnk) (D T k Dk +τI) −1 (τPkXk + D T k Xk) O(m 2nk) Ak O(m 3 +mpnk +m 2nk) Ak {Pk , Dk} Pk p× p (τXkX T k +λ3X¯ kX¯ T k +γI+βXLXT ) O(p 2nk + p 2 (n−nk)+ pn2 + p 2n) Pk (τXkX T k +λ3X¯ kX¯ T k +γI+βXLXT ) O(p 3 ) AkX T k O(mnp) O(mp2 ) Pk O(mnk p+ p 3+mp2 ) Dk Dk XkA T k AkA T k (AkA T k +ρI) XkA T k (AkA T k +ρI) −1 O(pnkm) O(m 2nk) O(m 3 ) O(pm2 ) Dk O(H(pmnk +m 2nk +m 3 + pm2 )) 在 GDPL 算法中主要是计算训练阶段的时间 复杂度。在训练阶段 和 交替更新，每 次更新过程相同，在此以一次更新为例。固定 由式 (10) 更新 ， 更新的时间复杂度 是一个逆矩阵和一个矩阵相乘的时间复杂度即 的矩阵， 的时间复杂度为 ， 在 的矩阵 中， 的时间复 杂度为 ， 的时间复杂度也是 ， 所以矩阵 的时间复杂度为 。 矩阵 和 相乘的时间复 杂度为 ，整个更新 的时间复杂度为 。固定 ，更新 。 由 式 (12 ) 进行更新，在 式 (14 ) 中 的矩阵 的时间复杂度为 ，但是在迭代过程中该 矩阵值不变，在初始化阶段提前计算出来，在迭 代过程中不需要重复计算，因此不影响更新 的 时间复杂度。只需计算 逆矩阵的时间复杂度为 。 的时间复杂 度 为 ，两矩阵相乘的时间复杂度为 ，更新 的时间复杂度为 。 使用 ADMM 更新 ，将 ADMM 算法中迭代更新 次数记 为 H ， ADD M 算法中，主要计算在 式 (13) 中 D 更新过程的时间复杂度。 根据式 (14) 更新的，式 (14) 中 、 、 的 逆矩阵、 的时间复杂度分别为 、 、 、 ，更新 整个过 程的时间复杂度为 。 3.2 收敛性分析 在目标函数式 (1) 中对于 {(D, P),(A)} 的迭代 更新是一个双凸问题。在优化求解的过程中，固 定 A 对 D 和 P 求解是一个凸问题；固定 D 和 P 对 A 求解也是一个凸问题，因此目标函数是一个 双凸问题。根据文献[10]的补充材料，收敛时目 标函数的能量值达到一个局部最小值。为了避免 在更新过程中达到收敛条件，不同类之间单个样 本的能量不在同一个数量级上，所以，本文的收 敛条件是单个样本的能量到达某一局部最小。目 标函数中各项的曲线如图 1 所示。图 1 只是以 GDPL 算法过程中使用其中一类迭代过程中的目 标函数值画出曲线为例。算法 1 中 while 后面的 收敛条件为前后两次迭代的整个目标函数值之差 小于 0，单个样本的重构误差的绝对值小于 1，保 证目标函数值在每次迭代过程中逐渐减小，最大 迭代次数为 50。 2 0 −2 −4 −6 −8 −10 −12 −14 −16 −18 0 10 20 30 40 50 60 迭代次数 损失函数值 目标函数值 ×109 图 1 目标函数值随迭代次数变化 Fig. 1 The value of the objective function varies with the number of iterations 图 1 中单个样本的整个目标函数值在开始到 40 次的变化趋势是平行趋于 0，之后变成一个比 较大的负值，由于相似度矩阵不是半正定矩阵， 由此使图正则项的值变成负值，并引起其他项的 变化。并且由于图像的损失函数一般都不会小 于 0，所以，从图 1 可以看出算法在 2～40 次之间 是局部收敛的。所以，有的实验在第 2 次迭代就 达到最优值。 4 实验结果与分析 为了验证图正则化字典对学习算法在图像分 类中的性能，本文在 ADNI1 数据集上进行验证。 ADNI 由国际老年研究所、生物医学成像和生物 工程研究所、美国食品和药物管理局、民营医药 企业和非营利组织在 2003 年启动，资金为 60 万 美元。ADNI 的主要目标是测试是否能通过组合 第 2 期 魏彩锋，等：图正则化字典对学习的轻度认知功能障碍预测 ·373·