發(fā)布時(shí)間：2020-01-23 15:46

【摘要】：聚類方法一直是數(shù)據(jù)挖掘中的研究熱點(diǎn)之一,近年來(lái)基于圖論的譜聚類方法是一個(gè)非�；钴S的研究方向。與K-Means等傳統(tǒng)的聚類算法相比,譜聚類方法能夠在任意形狀的樣本空間上聚類,并且收斂于全局的最優(yōu)解。譜聚類利用圖的鄰接矩陣,計(jì)算其對(duì)應(yīng)的拉普拉斯矩陣,然后求取特征值和特征向量,在特征向量上做聚類。傳統(tǒng)的譜聚類是基于簡(jiǎn)單圖的劃分,而簡(jiǎn)單圖模型往往對(duì)數(shù)據(jù)的多元關(guān)系表示有一定的缺陷。超圖模型與傳統(tǒng)的簡(jiǎn)單圖模型相比,能夠很好地對(duì)數(shù)據(jù)的高階信息進(jìn)行描述,可以將譜聚類算法應(yīng)用到超圖模型上。由于譜聚類本身的計(jì)算復(fù)雜度較高而且超圖模型的建立比簡(jiǎn)單圖也更為復(fù)雜,所以在大規(guī)模數(shù)據(jù)集上運(yùn)行超圖譜聚類算法,計(jì)算復(fù)雜度與存儲(chǔ)量都會(huì)非常大,單機(jī)條件下很難應(yīng)用。但是,近年來(lái)云計(jì)算和大數(shù)據(jù)處理平臺(tái)的研究非常流行。比如基于MapReduce的Hadoop平臺(tái),剛剛興起的基于RDD的Spark計(jì)算平臺(tái)等都可以實(shí)現(xiàn)算法的并行化,提高算法的運(yùn)行效率。Spark是基于內(nèi)存計(jì)算的分布式平臺(tái),處理速度相比Hadoop更優(yōu),而且更擅長(zhǎng)迭代計(jì)算,所以本文選擇Spark平臺(tái),在Spark上對(duì)超圖譜聚類進(jìn)行并行化研究與實(shí)現(xiàn)。本文首先介紹了論文涉及的相關(guān)技術(shù),包括Spark平臺(tái)及其編程模型、聚類算法以及聚類效果的評(píng)價(jià)準(zhǔn)則、簡(jiǎn)單圖理論與超圖的基本概念;然后介紹譜聚類算法的原理、圖的劃分與圖的拉普拉斯矩陣之間的關(guān)系,給出超圖譜聚類算法的一般步驟;其次在Spark平臺(tái)上對(duì)超圖譜聚類算法實(shí)現(xiàn)并行化,包含四個(gè)階段的并行化:超圖模型建立的并行、求取拉普拉斯矩陣的并行、求取拉普拉斯矩陣的特征值與特征向量的并行、K-Means聚類的并行;最后在公開的數(shù)據(jù)集和移動(dòng)用戶廣告數(shù)據(jù)集上分別設(shè)計(jì)實(shí)驗(yàn),在聚類效果上與傳統(tǒng)聚類算法K-Means算法進(jìn)行對(duì)比,得出了超圖譜聚類算法在聚類效果上更符合實(shí)際的結(jié)論,然后在Spark平臺(tái)上測(cè)試算法的運(yùn)行時(shí)間,實(shí)驗(yàn)表明并行后的算法在性能上有一定的提升。
【圖文】：

分布式框架，非常適合進(jìn)行海量數(shù)據(jù)的批處理與存儲(chǔ)。除了批處理務(wù)處理的需求，Twitter公司開發(fā)的Storm系統(tǒng)則滿足此種需求。除 AMP lab 所開發(fā)的 Spark 通用并行框架也越來(lái)越受關(guān)注，可以說(shuō)是繼計(jì)算平臺(tái)。k 簡(jiǎn)介與系統(tǒng)架構(gòu)源于美國(guó)加州伯克利分校 AMPLab 的集群計(jì)算平臺(tái)，用于對(duì)大規(guī)具有速度快、易用和容錯(cuò)性等特點(diǎn)。它不同于 MapReduce 的中間，可以保存到內(nèi)存中，因此 Spark 能夠很好地適用于機(jī)器學(xué)習(xí)等rk 有很多運(yùn)行模式，可以運(yùn)行在 Hadoop 上，Mesos 上和 standalo以使用 HDFS、Cassandra、HBase 和 S3 等。Spark 可以使用 Sca語(yǔ)言來(lái)編寫 Spark 應(yīng)用程序，并且提供了基于 Scala、Python、R

華南理工大學(xué)碩士學(xué)位論文常會(huì)在 master 節(jié)點(diǎn)上提交整個(gè)任務(wù)，此時(shí)會(huì)運(yùn)行一個(gè)驅(qū)動(dòng)器程序(di來(lái)發(fā)起集群上的各種并行操作，驅(qū)動(dòng)器程序會(huì)創(chuàng)建一個(gè) SparkContext行各種訪問和操作，這個(gè)對(duì)象 sc 代表了對(duì)分布式集群的一個(gè)連接。在，存在一個(gè)或多個(gè) executor 進(jìn)程，，負(fù)責(zé)對(duì) task 的執(zhí)行。
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 郭嘉凱;;云可大可小[J];軟件和信息服務(wù);2013年11期

2 范鵬飛;;超圖與組合優(yōu)化的探討[J];南京郵電學(xué)院學(xué)報(bào);1988年02期

3 郝忠孝;郭景峰;;一種基于超圖的最小覆蓋集求法[J];計(jì)算機(jī)研究與發(fā)展;1990年10期

4 楊春德;;偽超圖開關(guān)類的若干性質(zhì)[J];重慶郵電學(xué)院學(xué)報(bào);1993年01期

5 許小滿，孫雨耕，楊山，黃汝激;超圖理論及其應(yīng)用[J];電子學(xué)報(bào);1994年08期

6 高則年;具有最佳連通性超圖和容錯(cuò)多總線系統(tǒng)的設(shè)計(jì)[J];計(jì)算機(jī)學(xué)報(bào);1990年11期

7 牛祿青;;超圖軟件:內(nèi)外兼修[J];新經(jīng)濟(jì)導(dǎo)刊;2011年09期

8 郝忠孝,高巖,姚春龍;連接超圖的有關(guān)理論研究I:無(wú)α環(huán)分解的基本理論[J];計(jì)算機(jī)研究與發(fā)展;1997年S1期

9 黃汝激;應(yīng)用超圖理論實(shí)現(xiàn)有向基本割集矩陣[J];電子科學(xué)學(xué)刊;1992年01期

10 冷明;孫凌宇;邊計(jì)年;馬昱春;;一種時(shí)間復(fù)雜度為O(m)的無(wú)向超圖核值求解算法[J];小型微型計(jì)算機(jī)系統(tǒng);2013年11期

相關(guān)重要報(bào)紙文章 前10條

1 本報(bào)駐東京記者 吳仲國(guó);中國(guó)軟件在日本叫響知名品牌成市場(chǎng)寵兒[N];科技日?qǐng)?bào);2002年

2 證券時(shí)報(bào)記者 吳中珞;超圖軟件信披創(chuàng)新 微博釋疑股吧發(fā)帖詳解年報(bào)延期[N];證券時(shí)報(bào);2011年

3 本報(bào)記者 朱熹妍;地理信息火爆 超圖地理專注成器[N];經(jīng)濟(jì)觀察報(bào);2008年

4 記者 趙一蕙;超圖軟件業(yè)績(jī)快報(bào)“失準(zhǔn)”逾20%[N];上海證券報(bào);2013年

5 欒玲　趙培;超圖軟件：中國(guó)“智”造的跨國(guó)軟件企業(yè)[N];中國(guó)高新技術(shù)產(chǎn)業(yè)導(dǎo)報(bào);2010年

6 本報(bào)記者 解佳濤　戈清平;超圖軟件：做“中國(guó)智造”的跨國(guó)軟件企業(yè)[N];中國(guó)高新技術(shù)產(chǎn)業(yè)導(dǎo)報(bào);2010年

7 本報(bào)記者 梁爽;超圖：十年打造地理信息超級(jí)版圖[N];中國(guó)政府采購(gòu)報(bào);2012年

8 徐洋;北京市委書記郭金龍視察超圖軟件公司[N];中國(guó)測(cè)繪報(bào);2012年

9 本報(bào)記者 鄭燃;超圖軟件：讓應(yīng)急事件避免盲人摸象[N];政府采購(gòu)信息報(bào);2011年

10 江雪;鐘耳順鐘情GIS[N];中國(guó)企業(yè)報(bào);2007年

相關(guān)博士學(xué)位論文 前10條

1 古萬(wàn)榮;基于超圖模型的新聞推薦研究[D];華南理工大學(xué);2015年

2 孫艷萍;3一致超圖的拉格朗日和最大團(tuán)之間的關(guān)系的研究[D];湖南大學(xué);2016年

3 彭豪;超圖的Motzkin-Straus型結(jié)果及Frankl-F(?)redi猜想[D];湖南大學(xué);2015年

4 吳艷;3-一致超圖分解及相關(guān)問題[D];北京交通大學(xué);2010年

5 吳穎敏;市場(chǎng)機(jī)遇發(fā)現(xiàn)的超圖支持方法研究[D];華中科技大學(xué);2009年

6 葉淼林;圖與超圖理論中的譜方法[D];安徽大學(xué);2010年

7 吉日木圖;圖的標(biāo)號(hào)及超圖分解問題研究[D];大連理工大學(xué);2006年

8 王琦;網(wǎng)絡(luò)中的超圖嵌入問題[D];山東大學(xué);2007年

9 蔡p

本文編號(hào)：2572331