西安邮电大学
毕业论文
题目: 基于基追踪方法的 LLE 降维算法研究
学院: 自动化学院
专业: 智能科学与技术
班级: 智能 1401 班
学生姓名: 郑渝阳
学号: 06143035
导师姓名: 吴新宇/吴青 职称: 研究员/教授
起止时间:2017 年 12 月 5 日 至 2018 年 6 月 10 日
毕业论文声明书
本人所提交的毕业论文《基于基追踪方法的LLE降维算法研究》
是本人在指导教师指导下独立研究、写作的成果,论文中所引用他人
的文献、数据、图件、资料均已明确标注;对本文的研究做出重要贡
献的个人和集体,均已在文中以明确方式注明并表示感谢。
本人完全理解《西安邮电大学本科毕业设计(论文)管理办法》
的各项规定并自愿遵守。
本人深知本声明书的法律责任,违规后果由本人承担。
论文作者签名:
日期: 年 月 日
西安邮电大学本科毕业设计(论文)选题审批表
申 报 人 吴新宇/吴青
职称
研究员/教授
学院
自动化学院
题目名称
基于基追踪方法的 LLE 降维算法研究
题目来源
科研
√
教学
题目类型 硬件设计
软件设计
√ 论文
其它
艺术作品
题目性质
实际应用
理论研究
√
题目
简述
对学
生知
识与
能力
要求
预期
目标
时间
进度
(为什么申报该课题)
为了避免局部线性嵌入(LLE)在取样本近邻权限系数中涉矩阵求逆的问
题,同时也为了提高降维后的数据依旧保持较高的原空间的距离关系,将基追
踪引入到局部线性嵌入中,提出一种新的局部稀疏线性嵌入。该方法可以避开
矩阵求逆的问题,能够得更加精确的得到近邻加权系数且获得的近邻样本点权
限系数是稀疏的,达到成功降维的目的。
了解降维的思想与方法;MATLAB 程序语言
(本题目应完成的工作,题目预期目标和成果形式)
1. 原空间每个样本的近邻样本权限系数的构造; 2. 以原空间的近邻样
本权限系数构建降维的样本; 3. 编程实现算法,并验证算法降维性能的优越
性; 4. 完成毕业设计论文。
1. 2017 年 12 月 5 日---2018 年 2 月 5 日 查询相关中英文资料,了解该
课题意义和主要研究内容,撰写开题报告。 2. 2018 年 2 月 6 日---2017 年 3
月 30 日 将基追踪引入到局部线性嵌入中,提出一种新的局部稀疏线性嵌入,
较好得保持样本之间在原空间的关系。 3. 2018 年 4 月 1 日---2018 年 4 月
20 日 编写程序实现算法。 4. 2018 年 4 月 21 日--2018 年 5 月 10 日 调试程
序,测试算法的效率和精度。 5. 2018 年 5 月 11 日--2018 年 6 月 10 日 整理
资料,撰写论文,准备答辩。
系(教研室)主任
签字
2017 年 12 月 9 日
主管院长
签字
2017 年 12 月 9 日
西安邮电大学本科毕业设计(论文)开题报告
学生姓名
郑渝阳
学号
06143035
专业班级
智能 1401
指导教师
吴青
题目
基于基追踪的 LLE 降维算法研究
选题目的(为什么选该课题)
为了解决决策过程必须在有限的时间和空间上处理超量信息的矛盾,对原有信息
进行压缩处理是一个必要的过程。
局部线性嵌入(LLE)是非常重要的信息降维方法, 属于流形学习的一种。LLE 关注
于降维时保持样本局部的线性特征,广泛地用于图像识别,高维数据可视化等领域。
压缩感知理论认为:如果信号是稀疏的,那么它可以由远低于采样定理要求的采
样点重建恢复。凸优化算法是压缩感知的一种重要算法,这类方法通过将非凸问题转
化为凸问题求解找到信号的逼近,其中最常用的方法就是基追踪(Basis Pursuit,
BP),该方法提出使用L1范数替代L0范数来解决最优化问题,以便使用线性规划方法来
进行最优化求解。
LLE 作为一种信息压缩的方法,其核心准则是在压缩过程中的损失要尽可能小,
因此作为一种对稀疏信号最优化原则的基追踪,可以尝试将其应用于 LLE 的处理过程
中,以改进 LLE。
前期基础(已学课程、掌握的工具,资料积累、软硬件条件等)
已学课程:线性代数。
掌握的工具:matlab 辅助分析与设计软件。
资料积累:《矩阵论》方保镕、周继东、李医民编著,清华大学出版社;
《矩阵分析与应用》张贤达著,清华大学出版社;
《深度学习》[美]伊恩·古德费洛、[加]约书亚·本吉奥、[加]亚伦·库
维尔著,赵申剑等译,人民邮电出版社;
《最优化方法》何坚勇编著,清华大学出版社。
要研究和解决的问题(做什么)
1.了解压缩感知以及流形算法,理解基追踪优化准则以及局部线性嵌入。
2.使用基追踪的优化准则进行局部线性嵌入的研究。
3.编写 matlab 程序验证算法的效率和精度。
4.完成论文。
工作思路和方案(怎么做)
工作思路:
1.掌握基追踪以及局部线性嵌入的思想及程序实现。
2.使用基追踪准则对局部线性嵌入进行最优化处理。
3.编写程序验证。
工作方案:
⑴2017 年 12 月 5 日---2018 年 1 月 5 日 查询相关中英文资料,了解该课题意义
和主要研究内容,撰写开题报告。
⑵2018 年 2 月 6 日---2018 年 3 月 30 日 理解基追踪的思想并将其用到局部线性
嵌入中。
⑶2018 年 4 月 1 日---2018 年 4 月 20 日 编写程序实现算法。
⑷2018 年 4 月 21 日--2018 年 5 月 10 日 调试程序,测试算法的效率和精度。
⑸2018 年 5 月 11 日--2018 年 6 月 10 日 整理资料,撰写论文,准备答辩。
指导教师意见
选题符合本专业,能够查阅有关资料,能够明确自己要做的课题的基本内容、关
键问题,并找到解决问题的思路和方案。本课题的鄙夷设计进展顺利,同意开题。
签字 2018 年 1 月 9 日
西安邮电大学毕业设计 (论文)成绩评定表
学生姓名 郑渝阳 性别 男 学号
06143035 专业班级 智能 1401 班
课题名称
基于基追踪的 LLE 降维算法研究
指
导
教
师
意
见
评
阅
教
师
意
见
验
收
小
组
意
见
答
辩
小
组
意
见
评分(百分制): 指导教师(签字): 年 月 日
评分(百分制): 评阅教师(签字): 年 月 日
评分(百分制): 验收教师(组长)(签字): 年 月 日
评分(百分制): 答辩小组组长(签字): 年 月 日
评分比例 指导教师评分 (20%) 评阅教师评分 (30%) 验收小组评分 (30%) 答辩小组评分 (20%)
总评成绩
百分制成绩
等级制成绩
毕业论文(设计)最终成绩(等级):
学院答辩委员会主任(签字): 年 月 日
答
辩
委
员
会
意
见
目 录
第一章 绪论 ............................................. 1
1.1 本课题的研究背景 ··································································· 1
1.2 流形学习与局部线性嵌入的研究进展 ··········································· 1
1.3 压缩感知 ··············································································· 2
1.4 本课题的研究意义 ··································································· 2
第二章 课题研究相关理论基础 ............................. 3
2.1 流形学习与局部线性嵌入 ·························································· 3
2.1.1 流形学习 ······································································· 3
2.1.2 局部线性嵌入(LLE) ····················································· 3
2.2 压缩感知 ·············································································· 5
2.2.1 压缩感知框架 ································································· 5
2.2.2 匹配追踪算法(MP) ······················································ 6
2.2.3 正交匹配追踪算法(OMP) ·············································· 6
2.2.4 基追踪(BP) ································································ 7
第三章 基于基追踪的 LLE 算法 ............................. 8
3.1 选取数据的近邻点 ·································································· 8
3.2 局部线性嵌入重构矩阵的计算 ··················································· 8
3.3 重构矩阵 的稀疏化 ····························································· 11
3.3.1 基于 LLE-OMP 算法的重构矩阵稀疏化过程 ························· 11
3.3.2 LLE-OMP 算法的优缺点 ·················································· 12
3.4 基于基追踪(BP)的局部线性嵌入(LLE-BP)重构矩阵的计算 ·········· 12
3.5 计算高维数据集 在低维空间上的映象 ······································ 13
3.5.1 最佳嵌入问题 ································································ 13
3.5.2 最佳嵌入问题的求解······················································· 14
3.5.3 最佳嵌入问题拉格朗日乘子式求偏导过程 ··························· 16
3.6 实验方案、结果与分析 ··························································· 17
3.6.1 实验步骤 ······································································ 17
3.6.2 实验结果 ······································································ 18
3.6.3 实验结果分析 ································································ 22
3.7 算法分析 ············································································· 23
第四章 总结与展望 ...................................... 24
4.1 总结 ··················································································· 24
4.2 展望 ··················································································· 24
致 谢 .................................................. 25
参考文献 ................................................ 26
WX
摘 要
流形学习能在降维过程中保持一定的原高维流形的几何结构特征。目前流形
学习的主要方法有:局部线性嵌入(LLE)、等距映射等。压缩感知理论能在一定
条件下以远低于奈奎斯特采样定理的采样率对信号进行采样并重构。
在 LLE 的降维过程中,若高维流形的数据量较大,为了保证提取流形的几
何结构特征具有全局特性,需要扩大近邻点的集合,这会导致求解重构矩阵的过
程耗时巨大。为解决这个问题,本文提出了基于基追踪的 LLE 改进算法。该算
法首先通过在重构矩阵的计算中引入正交匹配追踪,以达到将重构矩阵稀疏化的
目的,再通过使用压缩感知理论的基追踪方法,将求解稀疏化重构矩阵的 范数
优化过程改进为 范数优化过程。
经测试,基于基追踪的 LLE 改进算法有运算速度快,降维稳定性好,准确
率高,对数据要求较低的优点。
关键词:流形学习;局部线性嵌入;压缩感知;凸松弛技术;基追踪
I
0l1l