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

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

【摘要】：隨著網(wǎng)絡(luò)科技的發(fā)展和人們生活水平的提高,信息的交流與溝通變得越來(lái)越普遍,這不僅給我們的生活帶來(lái)了便利,也產(chǎn)生了海量的數(shù)據(jù)。海量數(shù)據(jù)使信息交流更加便捷的同時(shí),也加大了集中式運(yùn)算的承載量。當(dāng)今,數(shù)據(jù)正成為一種重要的資產(chǎn),數(shù)據(jù)的分析能力也逐漸成為核心競(jìng)爭(zhēng)力。人們對(duì)于海量數(shù)據(jù)的挖掘和運(yùn)用,將會(huì)使科技創(chuàng)新能力得到極大提升。信息化是社會(huì)發(fā)展的大趨勢(shì),其關(guān)鍵在于數(shù)據(jù)的運(yùn)用。而大規(guī)模的數(shù)據(jù)主要來(lái)源于云計(jì)算、物聯(lián)網(wǎng)以及移動(dòng)互聯(lián)網(wǎng)等多個(gè)渠道,它貫穿于信息化建設(shè)的過(guò)程之中,為信息化的發(fā)展提供了參考與決策�？梢钥吹�,信息化時(shí)代可用的資源非常豐富,但數(shù)據(jù)始終是其最重要的內(nèi)容,在日常生活中的應(yīng)用比例也在不斷攀升。隨著社會(huì)與科技的發(fā)展,數(shù)據(jù)處理的問(wèn)題層出不窮,我們寄希望于通過(guò)對(duì)大數(shù)據(jù)的挖掘和分析,將難題各個(gè)擊破。在這樣的大背景下,實(shí)現(xiàn)數(shù)據(jù)的分布式存儲(chǔ)以及計(jì)算的分布式進(jìn)行就顯得越來(lái)越重要。本文旨在研究分布式計(jì)算,以實(shí)現(xiàn)改進(jìn)和提高運(yùn)算效率的目的。 分布式計(jì)算使大規(guī)模的數(shù)據(jù)處理更加便捷,它將原先繁雜的計(jì)算任務(wù)劃分成小的子任務(wù),并且在各個(gè)子節(jié)點(diǎn)上進(jìn)行并行的操作,使整體運(yùn)算得到平衡,不僅提高了運(yùn)算的效率,也實(shí)現(xiàn)了信息時(shí)代高速高能高功的產(chǎn)業(yè)化要求。相對(duì)于集中式計(jì)算而言,分布式計(jì)算不再只是依靠單個(gè)的設(shè)備完成任務(wù)。分布式計(jì)算使兩個(gè)或多個(gè)計(jì)算機(jī)之間實(shí)現(xiàn)信息共享,因此可以通過(guò)網(wǎng)絡(luò)連接,使數(shù)據(jù)在多臺(tái)計(jì)算機(jī)上同時(shí)運(yùn)行操作,這樣就能夠快速簡(jiǎn)便的解決大型且復(fù)雜的計(jì)算問(wèn)題。隨著信息量的增長(zhǎng),眾多領(lǐng)域的計(jì)算規(guī)模也在不斷擴(kuò)大,人們對(duì)計(jì)算機(jī)性能的要求也越來(lái)越高。龐大的計(jì)算量使得單臺(tái)計(jì)算機(jī)無(wú)法完成任務(wù)要求,而高性能的計(jì)算機(jī)也因其價(jià)格過(guò)高而難以普及。因此,如何利用分布式計(jì)算框架,以并行方式完成大規(guī)模的計(jì)算,并大幅度地提高數(shù)據(jù)計(jì)算與處理的能力,開(kāi)始成為計(jì)算機(jī)領(lǐng)域的熱門(mén)課題。 一個(gè)有效而合理的分布式計(jì)算框架,應(yīng)該按照任務(wù)需求和處理器的運(yùn)行情況,將不同任務(wù)均衡地分配到相應(yīng)的處理器上,避免不必要的任務(wù)等待時(shí)間。在分布式計(jì)算系統(tǒng)中,一個(gè)計(jì)算任務(wù)常常被分成多個(gè)子任務(wù),然后將其分配到不同處理器上,通過(guò)并行的執(zhí)行方式,達(dá)到減少任務(wù)的運(yùn)行周期以及提高系統(tǒng)的吞吐量的目的。然而,子任務(wù)之間因執(zhí)行時(shí)的順序問(wèn)題受到約束,即一個(gè)子任務(wù)須在之前的任務(wù)結(jié)束后才能執(zhí)行。所以如何將任務(wù)合理地分配到各個(gè)處理器上,并且減少處理器空閑時(shí)間,就成為提高系統(tǒng)效率的關(guān)鍵。 本文的研究重點(diǎn)是利用分布式框架Spark,實(shí)現(xiàn)用交替方向乘子法(ADM-M)求解分組Dantzig選擇器。通過(guò)并行計(jì)算的方式提高了計(jì)算效率,與傳統(tǒng)的集中式計(jì)算相比,并行計(jì)算節(jié)省運(yùn)算開(kāi)銷(xiāo),消除了冗余的計(jì)算等待時(shí)間。本文的主要工作包括： (1)利用Dantzig選擇器的解路徑分段線(xiàn)性的特質(zhì),以改進(jìn)的DASSO算法來(lái)求解Dantzig選擇器,通過(guò)與線(xiàn)性化的交替方向乘子法進(jìn)行對(duì)比,突出了改進(jìn)算法的優(yōu)越性。 (2)克服了分組Dantzig選擇器中約束條件給求解帶來(lái)的困難,引入中間變量進(jìn)行簡(jiǎn)化,并應(yīng)用交替方向乘子法(ADMM)和線(xiàn)性化的交替方向乘子法(LADMM)算法,從而使分組Dantzig選擇器的求解變?yōu)榭赡堋?(3)在服務(wù)器上搭建分布式計(jì)算的平臺(tái),創(chuàng)建虛擬機(jī),利用Spark實(shí)現(xiàn)求解分組Dantzig選擇器的ADMM算法,并把集中式的計(jì)算與分布式的計(jì)算效率進(jìn)行對(duì)比。 分組Dantzig選擇器對(duì)于具有分組稀疏性的線(xiàn)性回歸模型,在特征選擇、模型預(yù)測(cè)等問(wèn)題方面,都有很好地應(yīng)用,比較著名的例子有腦電波醫(yī)學(xué)實(shí)驗(yàn)。首先通過(guò)設(shè)置在人體頭皮的64個(gè)微電極,以256Hz的頻率測(cè)量人體頭部腦電波,同時(shí)記錄樣本人群的疾病癥狀,建立回歸模型。然后根據(jù)這些數(shù)據(jù)計(jì)算出模型參數(shù),可以方便以后運(yùn)行預(yù)測(cè)。而分布式計(jì)算對(duì)于處理當(dāng)今越來(lái)越大規(guī)模的數(shù)據(jù),有著不容忽視的重要意義,這也是本文研究和寫(xiě)作的重要出發(fā)點(diǎn)。
【關(guān)鍵詞】：分組Dantzig選擇器 大規(guī)模數(shù)據(jù) 分布式計(jì)算 交替方向乘子法 線(xiàn)性化交替方向乘子法 Spark
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類(lèi)號(hào)】：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ù)時(shí)代15-16
• 1.1.2 分布式計(jì)算與優(yōu)化16-17
• 1.2 稀疏優(yōu)化問(wèn)題17-20
• 1.2.1 BP問(wèn)題19
• 1.2.2 LASSO問(wèn)題19-20
• 1.2.3 Dantzig選擇器問(wèn)題20
• 1.3 凸優(yōu)化算法20-24
• 1.3.1 無(wú)約束的凸優(yōu)化問(wèn)題20-22
• 1.3.2 含等式約束的凸優(yōu)化問(wèn)題22-24
• 1.4 研究目標(biāo)和意義24-25
• 1.5 文章結(jié)構(gòu)25-27
• 第二章 Dantzig選擇器的算法分析27-39
• 2.1 數(shù)學(xué)模型與應(yīng)用27-28
• 2.2 算法分析與比較28-33
• 2.2.1 LADMM求解Dantzig選擇器29-31
• 2.2.2 改進(jìn)的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 保險(xiǎn)記錄數(shù)據(jù)集35-37
• 2.3.4 實(shí)驗(yàn)結(jié)論37
• 2.4 本章小結(jié)37-39
• 第三章 分組Dantzig選擇器的算法分析39-51
• 3.1 分組稀疏的概念39-40
• 3.2 數(shù)學(xué)模型與應(yīng)用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 分布式計(jì)算框架51-53
• 4.2 Spark相關(guān)技術(shù)53-56
• 4.2.1 Spark運(yùn)行模式53-54
• 4.2.2 Spark的核心概念54-56
• 4.3 實(shí)驗(yàn)仿真56-61
• 4.3.1 平臺(tái)搭建56-57
• 4.3.2 實(shí)驗(yàn)程序57-60
• 4.3.3 實(shí)驗(yàn)結(jié)果60-61
• 4.4 本章小結(jié)61-63
• 第五章 結(jié)論與展望63-67
• 5.1 結(jié)論63-64
• 5.2 展望64-67
• 參考文獻(xiàn)67-73
• 附錄A 附錄73-77
• 致謝77-79
• 在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果79

【共引文獻(xiàn)】

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

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

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

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

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

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

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

7 傅鸝;兩類(lèi)逼近精確罰函數(shù)法及其數(shù)值試驗(yàn)[J];高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào);1998年02期

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

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

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

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

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

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

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

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

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

2 龍文;求解兩類(lèi)優(yōu)化問(wèn)題的混合進(jìn)化算法及其應(yīng)用[D];中南大學(xué);2011年

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

4 王豐輝;Hilbert空間非線(xiàn)性?xún)?yōu)化問(wèn)題之迭代方法[D];華東理工大學(xué);2011年

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

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

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

8 賀素香;非線(xiàn)性?xún)?yōu)化中的一類(lèi)對(duì)偶算法的理論研究[D];大連理工大學(xué);2002年

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

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

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

1 張麗霞;求解不等式約束優(yōu)化問(wèn)題的一個(gè)非線(xiàn)性L(fǎng)agrange函數(shù)[D];遼寧師范大學(xué);2010年

2 王小寶;求解非凸半定規(guī)劃的一個(gè)非線(xiàn)性L(fǎng)agrange方法[D];大連理工大學(xué);2010年

3 宋海明;幾種圖像復(fù)原方法[D];吉林大學(xué);2011年

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

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

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

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

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

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

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

本文編號(hào)：564169