發(fā)布時(shí)間：2017-10-21 06:25

  本文關(guān)鍵詞：基于云平臺(tái)的聚類(lèi)算法并行化研究

  更多相關(guān)文章： 聚類(lèi) 云計(jì)算 Hadoop Kmeans DBSCAN

【摘要】：聚類(lèi)算法是數(shù)據(jù)挖掘中的重要內(nèi)容,能夠從數(shù)據(jù)中提取出隱藏的有用信息和知識(shí)來(lái)為人們服務(wù),在工業(yè)、商業(yè)以及科研領(lǐng)域都得到了廣泛應(yīng)用。隨著當(dāng)今社會(huì)數(shù)據(jù)量急劇增加,單機(jī)聚類(lèi)算法的計(jì)算能力漸漸無(wú)法滿足需求,廣大互聯(lián)網(wǎng)公司為了從激烈的商業(yè)競(jìng)爭(zhēng)中脫穎而出以獲得商業(yè)成功和大量的經(jīng)濟(jì)利益,紛紛為大規(guī)模數(shù)據(jù)的處理尋求有效策略,于是多臺(tái)計(jì)算機(jī)共同參與運(yùn)算的分布式聚類(lèi)算法成為當(dāng)前研究熱點(diǎn)。云計(jì)算平臺(tái)是一個(gè)優(yōu)秀的新型商業(yè)計(jì)算模型,通過(guò)虛擬化技術(shù)把互聯(lián)網(wǎng)中的節(jié)點(diǎn)資源相融合來(lái)提供優(yōu)越的計(jì)算能力,并且能夠根據(jù)計(jì)算任務(wù)中任務(wù)量的實(shí)時(shí)變化情況來(lái)動(dòng)態(tài)擴(kuò)展集群中的節(jié)點(diǎn)。系統(tǒng)將待處理的計(jì)算任務(wù)合理分配到計(jì)算機(jī)集群中的節(jié)點(diǎn)上,根據(jù)實(shí)際需求得到所需的存儲(chǔ)空間和計(jì)算能力等資源,用戶在無(wú)需理解云內(nèi)部的知識(shí)和細(xì)節(jié)的情況下也可以使用云平臺(tái)中的基礎(chǔ)設(shè)施。Hadoop作為Apache基金會(huì)開(kāi)發(fā)的開(kāi)源云計(jì)算平臺(tái),以一種高效可靠可伸縮的方式處理數(shù)據(jù),此外還具有高容錯(cuò)性和低成本等優(yōu)點(diǎn),是一個(gè)能夠分布式處理海量數(shù)據(jù)的軟件框架。Hadoop核心設(shè)計(jì)是底部HDFS(分布式文件系統(tǒng))和上層MapReduce(編程模式),分別為海量數(shù)據(jù)提供存儲(chǔ)和計(jì)算。本文主要研究如何運(yùn)用云平臺(tái)中大量計(jì)算機(jī)節(jié)點(diǎn)的并行計(jì)算能力來(lái)解決大規(guī)模數(shù)據(jù)聚類(lèi)的難題。針對(duì)Kmeans算法中一些不足之處提出改進(jìn):采用Canopy算法作為Kmeans聚類(lèi)的初始步驟,并基于“最小最大原則”優(yōu)化初始聚類(lèi)中心的選取;對(duì)Kmeans迭代過(guò)程加以優(yōu)化使整體計(jì)算量得到降低,進(jìn)一步提高算法效率。詳細(xì)分析DBSCAN算法在參數(shù)選擇,內(nèi)存使用、I/O開(kāi)銷(xiāo)等方面存在的問(wèn)題,提出了一個(gè)基于層次的優(yōu)化算法。既解除了因參數(shù)選擇不當(dāng)而對(duì)算法效率造成的影響,還在一定程度上降低了查詢次數(shù)從而減小I/O開(kāi)銷(xiāo)。最后,通過(guò)搭建Hadoop平臺(tái)分別對(duì)基于MapReduce的Kmeans和DBSCAN并行優(yōu)化算法進(jìn)行一系列的測(cè)試實(shí)驗(yàn)來(lái)驗(yàn)證性能。實(shí)驗(yàn)表明:Kmeans優(yōu)化算法在迭代速度及聚類(lèi)結(jié)果準(zhǔn)確率上有所提升;DBSCAN優(yōu)化算法在正確率和實(shí)效性方面均得到改善;并且通過(guò)加速比實(shí)驗(yàn)證明本文的并行算法更適合處理大規(guī)模數(shù)據(jù)集。
【關(guān)鍵詞】：聚類(lèi) 云計(jì)算 Hadoop Kmeans DBSCAN
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：TP311.13;TP393.09
【目錄】：

• 摘要4-5
• abstract5-8
• 第一章 緒論8-11
• 1.1 課題背景8-9
• 1.1.1 大規(guī)模數(shù)據(jù)挖掘8
• 1.1.2 聚類(lèi)算法8
• 1.1.3 云計(jì)算平臺(tái)8-9
• 1.2 研究目的和意義9
• 1.3 論文研究?jī)?nèi)容9-10
• 1.4 論文組織結(jié)構(gòu)10-11
• 第二章 數(shù)據(jù)聚類(lèi)相關(guān)技術(shù)11-21
• 2.1 聚類(lèi)分析概述11-15
• 2.1.1 聚類(lèi)分析的定義11-12
• 2.1.2 聚類(lèi)分析中的數(shù)據(jù)結(jié)構(gòu)12-13
• 2.1.3 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型13
• 2.1.4 聚類(lèi)的相似性計(jì)算方法13-15
• 2.2 聚類(lèi)基本步驟15
• 2.3 主要聚類(lèi)算法15-18
• 2.3.1 層次方法16
• 2.3.2 劃分方法16-17
• 2.3.3 基于密度的方法17
• 2.3.4 基于網(wǎng)格的方法17
• 2.3.5 基于模型的方法17-18
• 2.4 并行聚類(lèi)相關(guān)技術(shù)18-20
• 2.4.1 并行計(jì)算簡(jiǎn)介18
• 2.4.2 并行策略18-19
• 2.4.3 并行算法的性能評(píng)價(jià)19-20
• 2.5 本章小結(jié)20-21
• 第三章 Hadoop云計(jì)算平臺(tái)21-31
• 3.1 Hadoop簡(jiǎn)介21-22
• 3.2 HDFS分布式文件系統(tǒng)22-27
• 3.2.1 HDFS的特點(diǎn)22-23
• 3.2.2 HDFS的體系結(jié)構(gòu)23-25
• 3.2.3 保障HDFS可靠性措施25-26
• 3.2.4 HDFS缺點(diǎn)及改進(jìn)26-27
• 3.3 Mapreduce編程模型27-30
• 3.3.1 MapReduce編程思想27-29
• 3.3.2 MapReduce處理流程29-30
• 3.4 本章小結(jié)30-31
• 第四章 基于MapReduce的Canopy-Kmeans算法并行優(yōu)化31-43
• 4.1 Kmeans算法簡(jiǎn)介31-34
• 4.1.1 Kmeans算法思想31-32
• 4.1.2 Kmeans算法流程32-33
• 4.1.3 Kmeans算法復(fù)雜度與性能分析33-34
• 4.2 Canopy- Kmeans算法簡(jiǎn)介34-36
• 4.2.1 Canopy算法思想34-35
• 4.2.2 Canopy算法流程35-36
• 4.3 改進(jìn)算法設(shè)計(jì)36-37
• 4.3.1 初始聚類(lèi)中心優(yōu)化36
• 4.3.2 Kmeans迭代過(guò)程優(yōu)化36-37
• 4.3.3 基于Hadoop平臺(tái)的算法并行化37
• 4.4 基于Hadoop平臺(tái)的Canopy-Kmeans算法并行實(shí)現(xiàn)37-41
• 4.4.1 Canopy中心點(diǎn)生成37-39
• 4.4.2 輸入數(shù)據(jù)標(biāo)注39
• 4.4.3 Kmeans迭代39-40
• 4.4.4 聚類(lèi)結(jié)果輸出40-41
• 4.5 實(shí)驗(yàn)及結(jié)果分析41-42
• 4.5.1 優(yōu)化算法性能測(cè)試41-42
• 4.5.2 Kmeans并行優(yōu)化算法算法可擴(kuò)展性測(cè)試42
• 4.6 本章小結(jié)42-43
• 第五章 基于MapReduce的DBSCAN算法并行優(yōu)化43-53
• 5.1 DBSCAN聚類(lèi)算法介紹43-46
• 5.1.1 DBSCAN算法基本概念43-44
• 5.1.2 DBSCAN算法執(zhí)行流程44-46
• 5.2 改進(jìn)算法設(shè)計(jì)46-48
• 5.2.1 優(yōu)化算法思想46-47
• 5.2.2 優(yōu)化算法描述47
• 5.2.3 優(yōu)化算法性能分析47-48
• 5.3 基于MapReduce的算法并行實(shí)現(xiàn)48-50
• 5.4 實(shí)驗(yàn)與結(jié)果分析50-52
• 5.4.1 優(yōu)化算法準(zhǔn)確率測(cè)試50-51
• 5.4.2 優(yōu)化算法可擴(kuò)展性測(cè)試51-52
• 5.5 本章小結(jié)52-53
• 第六章 總結(jié)與展望53-55
• 6.1 總結(jié)53
• 6.2 展望53-55
• 參考文獻(xiàn)55-57
• 附錄1攻讀碩士學(xué)位期間撰寫(xiě)的論文57-58
• 致謝58

【相似文獻(xiàn)】

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

1 劉波;;“算法設(shè)計(jì)與分析”教學(xué)探討[J];高等理科教育;2007年04期

2 肖小克;陳莉;;《算法設(shè)計(jì)與分析》實(shí)踐教學(xué)探討[J];福建電腦;2009年10期

3 穆瑞輝;;計(jì)算機(jī)算法設(shè)計(jì)研究與思考[J];數(shù)字技術(shù)與應(yīng)用;2012年12期

4 潘博;;構(gòu)建“算法設(shè)計(jì)與分析”趣味課堂[J];科教文匯(下旬刊);2013年06期

5 王希常,楊志強(qiáng);一類(lèi)考場(chǎng)編排算法的設(shè)計(jì)[J];山東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年04期

6 龍騰芳,高金文;“分而治之”方法在算法設(shè)計(jì)中的應(yīng)用[J];渤海大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年01期

7 呂國(guó)英;;《算法設(shè)計(jì)與分析》教材建設(shè)的實(shí)施[J];計(jì)算機(jī)教育;2007年19期

8 徐子珊;;“算法設(shè)計(jì)與分析”教學(xué)中理論與技術(shù)的平衡[J];計(jì)算機(jī)教育;2008年10期

9 鄭紅;邵志清;符海波;;“算法設(shè)計(jì)與分析”課程教學(xué)改革初探[J];計(jì)算機(jī)教育;2008年14期

10 高尚;;“算法設(shè)計(jì)與分析”課程改革初探[J];計(jì)算機(jī)教育;2008年14期

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

1 雷詠梅;;橢圓曲線密碼體制的算法設(shè)計(jì)與實(shí)現(xiàn)[A];西部大開(kāi)發(fā) 科教先行與可持續(xù)發(fā)展——中國(guó)科協(xié)2000年學(xué)術(shù)年會(huì)文集[C];2000年

2 楊盤(pán)洪;朱軍祥;趙建安;楊靜;;機(jī)動(dòng)目標(biāo)跟蹤的模糊變結(jié)構(gòu)交互多模算法[A];2007'中國(guó)儀器儀表與測(cè)控技術(shù)交流大會(huì)論文集（二）[C];2007年

3 徐子珊;;《算法設(shè)計(jì)與分析》課程中的工程教育[A];2005年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

4 王輝;劉治昌;;用一種新算法設(shè)計(jì)的安全系統(tǒng)[A];2007年中國(guó)智能自動(dòng)化會(huì)議論文集[C];2007年

5 舒輝;柳清峰;杜祝平;周蓓;;實(shí)踐教學(xué)模式在本科專業(yè)課程教學(xué)中的應(yīng)用[A];中國(guó)電子教育學(xué)會(huì)高教分會(huì)2010年論文集[C];2010年

6 彭小宏;陽(yáng)東升;劉忠;;基于聚類(lèi)算法的組織協(xié)作網(wǎng)設(shè)計(jì)[A];2006中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2006年

7 李皓;羅熊;;云存儲(chǔ)部署優(yōu)化的進(jìn)化算法設(shè)計(jì)[A];2013年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第三分冊(cè)）[C];2013年

8 羅長(zhǎng)政;李熙瑩;王鎮(zhèn)波;羅東華;;一種大流量交叉路口的背景提取與更新算法[A];第十五屆全國(guó)圖象圖形學(xué)學(xué)術(shù)會(huì)議論文集[C];2010年

9 楊利;李霖;昌月樓;陽(yáng)國(guó)貴;;對(duì)稱位向量及啟發(fā)式并行散列連接算法[A];數(shù)據(jù)庫(kù)研究與進(jìn)展95——第十三屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集[C];1995年

10 張晉;;嵌入式電腦鼠運(yùn)行算法的研究[A];全國(guó)第20屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議（CACIS·2009）暨全國(guó)第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];2009年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

1 ;算法設(shè)計(jì)的策略[N];電腦報(bào);2003年

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

1 谷偉哲;齊次光滑算法及其應(yīng)用[D];天津大學(xué);2010年

2 龍海俠;進(jìn)化算法及其在生物信息中的應(yīng)用[D];江南大學(xué);2010年

3 譚躍;具有混沌局部搜索策略的粒子群優(yōu)化算法研究[D];中南大學(xué);2013年

4 尤海峰;求解隱式目標(biāo)優(yōu)化問(wèn)題的交互式進(jìn)化算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

5 張常淳;基于MapReduce的大數(shù)據(jù)連接算法的設(shè)計(jì)與優(yōu)化[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

6 郭崇慧;地區(qū)中長(zhǎng)期發(fā)展規(guī)劃若干定量模型、算法及應(yīng)用研究[D];大連理工大學(xué);2002年

7 蔣蔚;粒子濾波改進(jìn)算法研究與應(yīng)用[D];哈爾濱工業(yè)大學(xué);2010年

8 孫賀;算法設(shè)計(jì)中的若干前沿問(wèn)題[D];復(fù)旦大學(xué);2009年

9 陳寧濤;基于二分技術(shù)的高效算法設(shè)計(jì)及其應(yīng)用[D];華中科技大學(xué);2006年

10 婁曉文;無(wú)符號(hào)基因組切割再粘貼重組問(wèn)題的算法研究[D];山東大學(xué);2010年

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

1 李欣園;基于選擇偏好的組合聚類(lèi)算法研究與實(shí)現(xiàn)[D];內(nèi)蒙古大學(xué);2015年

2 楊瀟;界約束非線性最小二乘問(wèn)題的無(wú)導(dǎo)數(shù)算法[D];上海交通大學(xué);2015年

3 王曉璐;基于Zynq的LS-SVM算法加速器設(shè)計(jì)[D];哈爾濱工業(yè)大學(xué);2015年

4 樓磊磊;醫(yī)療保險(xiǎn)數(shù)據(jù)異常行為檢測(cè)算法和系統(tǒng)[D];浙江大學(xué);2015年

5 齊海龍;基于改進(jìn)人工蜂群算法的非線性系統(tǒng)辨識(shí)方法研究[D];北京化工大學(xué);2015年

6 蔡平梅;結(jié)構(gòu)化稀疏信號(hào)的恢復(fù)算法研究[D];上海大學(xué);2015年

7 趙晨陽(yáng);基于蟻群算法的高階圖匹配方法研究[D];西安電子科技大學(xué);2014年

8 茍清松;多目標(biāo)粒子濾波檢測(cè)前跟蹤算法研究[D];電子科技大學(xué);2015年

9 李枝勇;蝙蝠算法及其在函數(shù)優(yōu)化中的應(yīng)用研究[D];上海理工大學(xué);2013年

10 李蓮;基于蜂群和粗糙集的聚類(lèi)算法研究[D];長(zhǎng)沙理工大學(xué);2014年

，

本文編號(hào)：1071789