分组Dantzig选择器的大规模分布式求解

发布时间：2017-07-19 18:13

  本文关键词：分组Dantzig选择器的大规模分布式求解

  更多相关文章： 分组Dantzig选择器 大规模数据 分布式计算 交替方向乘子法 线性化交替方向乘子法 Spark

【摘要】：随着网络科技的发展和人们生活水平的提高,信息的交流与沟通变得越来越普遍,这不仅给我们的生活带来了便利,也产生了海量的数据。海量数据使信息交流更加便捷的同时,也加大了集中式运算的承载量。当今,数据正成为一种重要的资产,数据的分析能力也逐渐成为核心竞争力。人们对于海量数据的挖掘和运用,将会使科技创新能力得到极大提升。信息化是社会发展的大趋势,其关键在于数据的运用。而大规模的数据主要来源于云计算、物联网以及移动互联网等多个渠道,它贯穿于信息化建设的过程之中,为信息化的发展提供了参考与决策。可以看到,信息化时代可用的资源非常丰富,但数据始终是其最重要的内容,在日常生活中的应用比例也在不断攀升。随着社会与科技的发展,数据处理的问题层出不穷,我们寄希望于通过对大数据的挖掘和分析,将难题各个击破。在这样的大背景下,实现数据的分布式存储以及计算的分布式进行就显得越来越重要。本文旨在研究分布式计算,以实现改进和提高运算效率的目的。 分布式计算使大规模的数据处理更加便捷,它将原先繁杂的计算任务划分成小的子任务,并且在各个子节点上进行并行的操作,使整体运算得到平衡,不仅提高了运算的效率,也实现了信息时代高速高能高功的产业化要求。相对于集中式计算而言,分布式计算不再只是依靠单个的设备完成任务。分布式计算使两个或多个计算机之间实现信息共享,因此可以通过网络连接,使数据在多台计算机上同时运行操作,这样就能够快速简便的解决大型且复杂的计算问题。随着信息量的增长,众多领域的计算规模也在不断扩大,人们对计算机性能的要求也越来越高。庞大的计算量使得单台计算机无法完成任务要求,而高性能的计算机也因其价格过高而难以普及。因此,如何利用分布式计算框架,以并行方式完成大规模的计算,并大幅度地提高数据计算与处理的能力,开始成为计算机领域的热门课题。 一个有效而合理的分布式计算框架,应该按照任务需求和处理器的运行情况,将不同任务均衡地分配到相应的处理器上,避免不必要的任务等待时间。在分布式计算系统中,一个计算任务常常被分成多个子任务,然后将其分配到不同处理器上,通过并行的执行方式,达到减少任务的运行周期以及提高系统的吞吐量的目的。然而,子任务之间因执行时的顺序问题受到约束,即一个子任务须在之前的任务结束后才能执行。所以如何将任务合理地分配到各个处理器上,并且减少处理器空闲时间,就成为提高系统效率的关键。 本文的研究重点是利用分布式框架Spark,实现用交替方向乘子法(ADM-M)求解分组Dantzig选择器。通过并行计算的方式提高了计算效率,与传统的集中式计算相比,并行计算节省运算开销,消除了冗余的计算等待时间。本文的主要工作包括： (1)利用Dantzig选择器的解路径分段线性的特质,以改进的DASSO算法来求解Dantzig选择器,通过与线性化的交替方向乘子法进行对比,突出了改进算法的优越性。 (2)克服了分组Dantzig选择器中约束条件给求解带来的困难,引入中间变量进行简化,并应用交替方向乘子法(ADMM)和线性化的交替方向乘子法(LADMM)算法,从而使分组Dantzig选择器的求解变为可能。 (3)在服务器上搭建分布式计算的平台,创建虚拟机,利用Spark实现求解分组Dantzig选择器的ADMM算法,并把集中式的计算与分布式的计算效率进行对比。 分组Dantzig选择器对于具有分组稀疏性的线性回归模型,在特征选择、模型预测等问题方面,都有很好地应用,比较著名的例子有脑电波医学实验。首先通过设置在人体头皮的64个微电极,以256Hz的频率测量人体头部脑电波,同时记录样本人群的疾病症状,建立回归模型。然后根据这些数据计算出模型参数,可以方便以后运行预测。而分布式计算对于处理当今越来越大规模的数据,有着不容忽视的重要意义,这也是本文研究和写作的重要出发点。
【关键词】：分组Dantzig选择器 大规模数据 分布式计算 交替方向乘子法 线性化交替方向乘子法 Spark
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP311.13;TP338.8
【目录】：

• 摘要5-7
• ABSTRACT7-10
• 目录10-13
• 表格13-14
• 插图14-15
• 第一章 绪论15-27
• 1.1 背景15-17
• 1.1.1 数据时代15-16
• 1.1.2 分布式计算与优化16-17
• 1.2 稀疏优化问题17-20
• 1.2.1 BP问题19
• 1.2.2 LASSO问题19-20
• 1.2.3 Dantzig选择器问题20
• 1.3 凸优化算法20-24
• 1.3.1 无约束的凸优化问题20-22
• 1.3.2 含等式约束的凸优化问题22-24
• 1.4 研究目标和意义24-25
• 1.5 文章结构25-27
• 第二章 Dantzig选择器的算法分析27-39
• 2.1 数学模型与应用27-28
• 2.2 算法分析与比较28-33
• 2.2.1 LADMM求解Dantzig选择器29-31
• 2.2.2 改进的DASSO算法求解Dantzig选择器31-33
• 2.3 数值仿真33-37
• 2.3.1 synthetic数据集33-35
• 2.3.2 糖尿病数据集35
• 2.3.3 保险记录数据集35-37
• 2.3.4 实验结论37
• 2.4 本章小结37-39
• 第三章 分组Dantzig选择器的算法分析39-51
• 3.1 分组稀疏的概念39-40
• 3.2 数学模型与应用40-41
• 3.3 算法分析与比较41-47
• 3.3.1 ADMM求解分组Dantzig选择器41-44
• 3.3.2 LADMM求解分组Dantzig选择器44-47
• 3.4 数值仿真47-49
• 3.4.1 等分组块数据集47-48
• 3.4.2 不等分组块数据集48-49
• 3.5 本章小结49-51
• 第四章 分组Dantzig选择器的大规模分布式求解51-63
• 4.1 分布式计算框架51-53
• 4.2 Spark相关技术53-56
• 4.2.1 Spark运行模式53-54
• 4.2.2 Spark的核心概念54-56
• 4.3 实验仿真56-61
• 4.3.1 平台搭建56-57
• 4.3.2 实验程序57-60
• 4.3.3 实验结果60-61
• 4.4 本章小结61-63
• 第五章 结论与展望63-67
• 5.1 结论63-64
• 5.2 展望64-67
• 参考文献67-73
• 附录A 附录73-77
• 致谢77-79
• 在读期间发表的学术论文与取得的研究成果79

【共引文献】

中国期刊全文数据库 前10条

1 尚高峰;张爱锋;万正权;;承受静水外压作用的圆柱形壳体结构优化设计(英文)[J];船舶力学;2010年12期

2 赵花丽;桂云丽;刘红卫;;解半定规划的带筛子的正则化方法[J];长春大学学报;2009年04期

3 彭军还;张亚利;章红平;刘星;;不等式约束最小二乘问题的解及其统计性质[J];测绘学报;2007年01期

4 仲伟俊;陈森发;徐南荣;;供水系统调度问题的凸化及其优化算法[J];东南大学学报;1989年05期

5 陶敏;;快速交替方向乘子法求解基于全变分的图像重建问题(英文)[J];Journal of Southeast University(English Edition);2011年04期

6 杜学武;李毓;李倩;秦帅;;不等式约束优化问题的Hestenes-Powell增广拉格朗日函数的精确性质(英文)[J];工程数学学报;2009年01期

7 傅鹂;两类逼近精确罚函数法及其数值试验[J];高等学校计算数学学报;1998年02期

8 赵可f3;不等式约束优化问题的精确罚函数法[J];高等学校计算数学学报;1998年04期

9 ;Some Remarks on the Convex Feasibility Problem and Best Approximation Problem[J];Numerical Mathematics:Theory,Methods and Applications;2008年01期

10 唐国吉;;求解极大单调算子零点的一个近似邻近点算法[J];广西科学;2007年04期

中国重要会议论文全文数据库 前3条

1 仲伟俊;徐南荣;陈森发;;一类动态大规模非凸优化问题的分解算法及其应用[A];科学决策与系统工程——中国系统工程学会第六次年会论文集[C];1990年

2 纪魁;王树盛;;基于随机用户均衡的城市交通流分配优化模型[A];城市时代，，协同规划——2013中国城市规划年会论文集（01-城市道路与交通规划）[C];2013年

3 祁昊颖;;大数据时代电信运营商文件系统新思考[A];2013年中国信息通信研究新进展论文集[C];2014年

中国博士学位论文全文数据库 前10条

1 黄远程;高光谱影像混合像元分解的若干关键技术研究[D];武汉大学;2010年

2 龙文;求解两类优化问题的混合进化算法及其应用[D];中南大学;2011年

3 刘鹏;地震作用下桥梁梁体与横向挡块动态碰撞研究[D];西南交通大学;2011年

4 王丰辉;Hilbert空间非线性优化问题之迭代方法[D];华东理工大学;2011年

5 郑芳英;简单光滑精确罚函数方法的研究[D];上海大学;2012年

6 田荣;连续与非连续变形分析的有限覆盖无单元方法及其应用研究[D];大连理工大学;2000年

7 刘应华;结构极限与安定分析的数值方法研究及其工程应用[D];清华大学;1995年

8 贺素香;非线性优化中的一类对偶算法的理论研究[D];大连理工大学;2002年

9 廖良才;成品油调合调度优化模型及其应用研究[D];国防科学技术大学;2003年

10 孙建芳;钢丝绳捻制成形数值模拟与制品力学强度分析[D];华中科技大学;2004年

中国硕士学位论文全文数据库 前10条

1 张丽霞;求解不等式约束优化问题的一个非线性Lagrange函数[D];辽宁师范大学;2010年

2 王小宝;求解非凸半定规划的一个非线性Lagrange方法[D];大连理工大学;2010年

3 宋海明;几种图像复原方法[D];吉林大学;2011年

4 李英芝;求解半无限规划问题的对数型Lagrange函数[D];辽宁师范大学;2011年

5 邵俊;面向IICCD相机不完全随机采样遥感图像的重建算法[D];南京理工大学;2011年

6 张景;一类新的增广拉格朗日函数的鞍点性质[D];山东理工大学;2011年

7 黄元元;求解单调包含问题的分裂算法及预解动力系统[D];郑州大学;2011年

8 李璞;约束非线性最优化的罚函数法[D];河南科技大学;2011年

9 童露霞;基于压缩传感的重构算法研究[D];上海交通大学;2011年

10 朱钦佩;求解图像去噪问题的变权重不动点算法研究[D];上海交通大学;2012年

本文编号：564169