本文關鍵詞：基于云平臺的聚類算法并行化研究

  更多相關文章： 聚類 云計算 Hadoop Kmeans DBSCAN

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

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

【相似文獻】

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

1 劉波;;“算法設計與分析”教學探討[J];高等理科教育;2007年04期

2 肖小克;陳莉;;《算法設計與分析》實踐教學探討[J];福建電腦;2009年10期

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

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

5 王希常,楊志強;一類考場編排算法的設計[J];山東師范大學學報(自然科學版);2002年04期

6 龍騰芳,高金文;“分而治之”方法在算法設計中的應用[J];渤海大學學報(自然科學版);2004年01期

7 呂國英;;《算法設計與分析》教材建設的實施[J];計算機教育;2007年19期

8 徐子珊;;“算法設計與分析”教學中理論與技術的平衡[J];計算機教育;2008年10期

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

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

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

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

2 楊盤洪;朱軍祥;趙建安;楊靜;;機動目標跟蹤的模糊變結構交互多模算法[A];2007'中國儀器儀表與測控技術交流大會論文集（二）[C];2007年

3 徐子珊;;《算法設計與分析》課程中的工程教育[A];2005年全國理論計算機科學學術年會論文集[C];2005年

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

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

6 彭小宏;陽東升;劉忠;;基于聚類算法的組織協(xié)作網設計[A];2006中國控制與決策學術年會論文集[C];2006年

7 李皓;羅熊;;云存儲部署優(yōu)化的進化算法設計[A];2013年中國智能自動化學術會議論文集（第三分冊）[C];2013年

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

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

10 張晉;;嵌入式電腦鼠運行算法的研究[A];全國第20屆計算機技術與應用學術會議（CACIS·2009）暨全國第1屆安全關鍵技術與應用學術會議論文集（上冊）[C];2009年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 ;算法設計的策略[N];電腦報;2003年

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

1 谷偉哲;齊次光滑算法及其應用[D];天津大學;2010年

2 龍海俠;進化算法及其在生物信息中的應用[D];江南大學;2010年

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

4 尤海峰;求解隱式目標優(yōu)化問題的交互式進化算法研究[D];中國科學技術大學;2011年

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

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

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

8 孫賀;算法設計中的若干前沿問題[D];復旦大學;2009年

9 陳寧濤;基于二分技術的高效算法設計及其應用[D];華中科技大學;2006年

10 婁曉文;無符號基因組切割再粘貼重組問題的算法研究[D];山東大學;2010年

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

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

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

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

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

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

6 蔡平梅;結構化稀疏信號的恢復算法研究[D];上海大學;2015年

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

8 茍清松;多目標粒子濾波檢測前跟蹤算法研究[D];電子科技大學;2015年

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

10 李蓮;基于蜂群和粗糙集的聚類算法研究[D];長沙理工大學;2014年

，

本文編號：1071789