本文關鍵詞：分組Dantzig選擇器的大規(guī)模分布式求解

  更多相關文章： 分組Dantzig選擇器 大規(guī)模數(shù)據(jù) 分布式計算 交替方向乘子法 線性化交替方向乘子法 Spark

【摘要】：隨著網(wǎng)絡科技的發(fā)展和人們生活水平的提高,信息的交流與溝通變得越來越普遍,這不僅給我們的生活帶來了便利,也產(chǎn)生了海量的數(shù)據(jù)。海量數(shù)據(jù)使信息交流更加便捷的同時,也加大了集中式運算的承載量。當今,數(shù)據(jù)正成為一種重要的資產(chǎn),數(shù)據(jù)的分析能力也逐漸成為核心競爭力。人們對于海量數(shù)據(jù)的挖掘和運用,將會使科技創(chuàng)新能力得到極大提升。信息化是社會發(fā)展的大趨勢,其關鍵在于數(shù)據(jù)的運用。而大規(guī)模的數(shù)據(jù)主要來源于云計算、物聯(lián)網(wǎng)以及移動互聯(lián)網(wǎng)等多個渠道,它貫穿于信息化建設的過程之中,為信息化的發(fā)展提供了參考與決策�？梢钥吹�,信息化時代可用的資源非常豐富,但數(shù)據(jù)始終是其最重要的內(nèi)容,在日常生活中的應用比例也在不斷攀升。隨著社會與科技的發(fā)展,數(shù)據(jù)處理的問題層出不窮,我們寄希望于通過對大數(shù)據(jù)的挖掘和分析,將難題各個擊破。在這樣的大背景下,實現(xiàn)數(shù)據(jù)的分布式存儲以及計算的分布式進行就顯得越來越重要。本文旨在研究分布式計算,以實現(xiàn)改進和提高運算效率的目的。 分布式計算使大規(guī)模的數(shù)據(jù)處理更加便捷,它將原先繁雜的計算任務劃分成小的子任務,并且在各個子節(jié)點上進行并行的操作,使整體運算得到平衡,不僅提高了運算的效率,也實現(xiàn)了信息時代高速高能高功的產(chǎn)業(yè)化要求。相對于集中式計算而言,分布式計算不再只是依靠單個的設備完成任務。分布式計算使兩個或多個計算機之間實現(xiàn)信息共享,因此可以通過網(wǎng)絡連接,使數(shù)據(jù)在多臺計算機上同時運行操作,這樣就能夠快速簡便的解決大型且復雜的計算問題。隨著信息量的增長,眾多領域的計算規(guī)模也在不斷擴大,人們對計算機性能的要求也越來越高。龐大的計算量使得單臺計算機無法完成任務要求,而高性能的計算機也因其價格過高而難以普及。因此,如何利用分布式計算框架,以并行方式完成大規(guī)模的計算,并大幅度地提高數(shù)據(jù)計算與處理的能力,開始成為計算機領域的熱門課題。 一個有效而合理的分布式計算框架,應該按照任務需求和處理器的運行情況,將不同任務均衡地分配到相應的處理器上,避免不必要的任務等待時間。在分布式計算系統(tǒng)中,一個計算任務常常被分成多個子任務,然后將其分配到不同處理器上,通過并行的執(zhí)行方式,達到減少任務的運行周期以及提高系統(tǒng)的吞吐量的目的。然而,子任務之間因執(zhí)行時的順序問題受到約束,即一個子任務須在之前的任務結(jié)束后才能執(zhí)行。所以如何將任務合理地分配到各個處理器上,并且減少處理器空閑時間,就成為提高系統(tǒng)效率的關鍵。 本文的研究重點是利用分布式框架Spark,實現(xiàn)用交替方向乘子法(ADM-M)求解分組Dantzig選擇器。通過并行計算的方式提高了計算效率,與傳統(tǒng)的集中式計算相比,并行計算節(jié)省運算開銷,消除了冗余的計算等待時間。本文的主要工作包括： (1)利用Dantzig選擇器的解路徑分段線性的特質(zhì),以改進的DASSO算法來求解Dantzig選擇器,通過與線性化的交替方向乘子法進行對比,突出了改進算法的優(yōu)越性。 (2)克服了分組Dantzig選擇器中約束條件給求解帶來的困難,引入中間變量進行簡化,并應用交替方向乘子法(ADMM)和線性化的交替方向乘子法(LADMM)算法,從而使分組Dantzig選擇器的求解變?yōu)榭赡堋?(3)在服務器上搭建分布式計算的平臺,創(chuàng)建虛擬機,利用Spark實現(xiàn)求解分組Dantzig選擇器的ADMM算法,并把集中式的計算與分布式的計算效率進行對比。 分組Dantzig選擇器對于具有分組稀疏性的線性回歸模型,在特征選擇、模型預測等問題方面,都有很好地應用,比較著名的例子有腦電波醫(yī)學實驗。首先通過設置在人體頭皮的64個微電極,以256Hz的頻率測量人體頭部腦電波,同時記錄樣本人群的疾病癥狀,建立回歸模型。然后根據(jù)這些數(shù)據(jù)計算出模型參數(shù),可以方便以后運行預測。而分布式計算對于處理當今越來越大規(guī)模的數(shù)據(jù),有著不容忽視的重要意義,這也是本文研究和寫作的重要出發(fā)點。
【關鍵詞】：分組Dantzig選擇器 大規(guī)模數(shù)據(jù) 分布式計算 交替方向乘子法 線性化交替方向乘子法 Spark
【學位授予單位】：中國科學技術(shù)大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：TP311.13;TP338.8
【目錄】：

• 摘要5-7
• ABSTRACT7-10
• 目錄10-13
• 表格13-14
• 插圖14-15
• 第一章 緒論15-27
• 1.1 背景15-17
• 1.1.1 數(shù)據(jù)時代15-16
• 1.1.2 分布式計算與優(yōu)化16-17
• 1.2 稀疏優(yōu)化問題17-20
• 1.2.1 BP問題19
• 1.2.2 LASSO問題19-20
• 1.2.3 Dantzig選擇器問題20
• 1.3 凸優(yōu)化算法20-24
• 1.3.1 無約束的凸優(yōu)化問題20-22
• 1.3.2 含等式約束的凸優(yōu)化問題22-24
• 1.4 研究目標和意義24-25
• 1.5 文章結(jié)構(gòu)25-27
• 第二章 Dantzig選擇器的算法分析27-39
• 2.1 數(shù)學模型與應用27-28
• 2.2 算法分析與比較28-33
• 2.2.1 LADMM求解Dantzig選擇器29-31
• 2.2.2 改進的DASSO算法求解Dantzig選擇器31-33
• 2.3 數(shù)值仿真33-37
• 2.3.1 synthetic數(shù)據(jù)集33-35
• 2.3.2 糖尿病數(shù)據(jù)集35
• 2.3.3 保險記錄數(shù)據(jù)集35-37
• 2.3.4 實驗結(jié)論37
• 2.4 本章小結(jié)37-39
• 第三章 分組Dantzig選擇器的算法分析39-51
• 3.1 分組稀疏的概念39-40
• 3.2 數(shù)學模型與應用40-41
• 3.3 算法分析與比較41-47
• 3.3.1 ADMM求解分組Dantzig選擇器41-44
• 3.3.2 LADMM求解分組Dantzig選擇器44-47
• 3.4 數(shù)值仿真47-49
• 3.4.1 等分組塊數(shù)據(jù)集47-48
• 3.4.2 不等分組塊數(shù)據(jù)集48-49
• 3.5 本章小結(jié)49-51
• 第四章 分組Dantzig選擇器的大規(guī)模分布式求解51-63
• 4.1 分布式計算框架51-53
• 4.2 Spark相關技術(shù)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 實驗結(jié)果60-61
• 4.4 本章小結(jié)61-63
• 第五章 結(jié)論與展望63-67
• 5.1 結(jié)論63-64
• 5.2 展望64-67
• 參考文獻67-73
• 附錄A 附錄73-77
• 致謝77-79
• 在讀期間發(fā)表的學術(shù)論文與取得的研究成果79

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 尚高峰;張愛鋒;萬正權(quán);;承受靜水外壓作用的圓柱形殼體結(jié)構(gòu)優(yōu)化設計(英文)[J];船舶力學;2010年12期

2 趙花麗;桂云麗;劉紅衛(wèi);;解半定規(guī)劃的帶篩子的正則化方法[J];長春大學學報;2009年04期

3 彭軍還;張亞利;章紅平;劉星;;不等式約束最小二乘問題的解及其統(tǒng)計性質(zhì)[J];測繪學報;2007年01期

4 仲偉俊;陳森發(fā);徐南榮;;供水系統(tǒng)調(diào)度問題的凸化及其優(yōu)化算法[J];東南大學學報;1989年05期

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

6 杜學武;李毓;李倩;秦帥;;不等式約束優(yōu)化問題的Hestenes-Powell增廣拉格朗日函數(shù)的精確性質(zhì)(英文)[J];工程數(shù)學學報;2009年01期

7 傅鸝;兩類逼近精確罰函數(shù)法及其數(shù)值試驗[J];高等學校計算數(shù)學學報;1998年02期

8 趙可f3;不等式約束優(yōu)化問題的精確罰函數(shù)法[J];高等學校計算數(shù)學學報;1998年04期

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

10 唐國吉;;求解極大單調(diào)算子零點的一個近似鄰近點算法[J];廣西科學;2007年04期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 仲偉俊;徐南榮;陳森發(fā);;一類動態(tài)大規(guī)模非凸優(yōu)化問題的分解算法及其應用[A];科學決策與系統(tǒng)工程——中國系統(tǒng)工程學會第六次年會論文集[C];1990年

2 紀魁;王樹盛;;基于隨機用戶均衡的城市交通流分配優(yōu)化模型[A];城市時代，，協(xié)同規(guī)劃——2013中國城市規(guī)劃年會論文集（01-城市道路與交通規(guī)劃）[C];2013年

3 祁昊穎;;大數(shù)據(jù)時代電信運營商文件系統(tǒng)新思考[A];2013年中國信息通信研究新進展論文集[C];2014年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 黃遠程;高光譜影像混合像元分解的若干關鍵技術(shù)研究[D];武漢大學;2010年

2 龍文;求解兩類優(yōu)化問題的混合進化算法及其應用[D];中南大學;2011年

3 劉鵬;地震作用下橋梁梁體與橫向擋塊動態(tài)碰撞研究[D];西南交通大學;2011年

4 王豐輝;Hilbert空間非線性優(yōu)化問題之迭代方法[D];華東理工大學;2011年

5 鄭芳英;簡單光滑精確罰函數(shù)方法的研究[D];上海大學;2012年

6 田榮;連續(xù)與非連續(xù)變形分析的有限覆蓋無單元方法及其應用研究[D];大連理工大學;2000年

7 劉應華;結(jié)構(gòu)極限與安定分析的數(shù)值方法研究及其工程應用[D];清華大學;1995年

8 賀素香;非線性優(yōu)化中的一類對偶算法的理論研究[D];大連理工大學;2002年

9 廖良才;成品油調(diào)合調(diào)度優(yōu)化模型及其應用研究[D];國防科學技術(shù)大學;2003年

10 孫建芳;鋼絲繩捻制成形數(shù)值模擬與制品力學強度分析[D];華中科技大學;2004年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 張麗霞;求解不等式約束優(yōu)化問題的一個非線性Lagrange函數(shù)[D];遼寧師范大學;2010年

2 王小寶;求解非凸半定規(guī)劃的一個非線性Lagrange方法[D];大連理工大學;2010年

3 宋海明;幾種圖像復原方法[D];吉林大學;2011年

4 李英芝;求解半無限規(guī)劃問題的對數(shù)型Lagrange函數(shù)[D];遼寧師范大學;2011年

5 邵俊;面向IICCD相機不完全隨機采樣遙感圖像的重建算法[D];南京理工大學;2011年

6 張景;一類新的增廣拉格朗日函數(shù)的鞍點性質(zhì)[D];山東理工大學;2011年

7 黃元元;求解單調(diào)包含問題的分裂算法及預解動力系統(tǒng)[D];鄭州大學;2011年

8 李璞;約束非線性最優(yōu)化的罰函數(shù)法[D];河南科技大學;2011年

9 童露霞;基于壓縮傳感的重構(gòu)算法研究[D];上海交通大學;2011年

10 朱欽佩;求解圖像去噪問題的變權(quán)重不動點算法研究[D];上海交通大學;2012年

本文編號：564169