【摘要】：隨著互聯(lián)網(wǎng)在全球范圍內(nèi)的快速普及,我們每天都會面對來自社會、商業(yè)、醫(yī)學(xué)、工程和科學(xué)以及我們?nèi)粘Ｉ罡鱾�方面的海量數(shù)據(jù)。數(shù)據(jù)的爆炸式增長、廣泛可用和巨大規(guī)模把我們帶入了一個真正的數(shù)據(jù)時代。而如何可以快速方便地從這些雜亂無章的大規(guī)模數(shù)據(jù)中挖掘出有用的信息,并將這些非結(jié)構(gòu)化的數(shù)據(jù)轉(zhuǎn)變成知識,已經(jīng)成為當(dāng)今科學(xué)領(lǐng)域的一個熱門研究課題。基于密度峰值聚類算法(Clustering by fast search and find of density peaks,FSDP)是Rodriguez等人于2014年在Science雜志上發(fā)表的一種新型密度聚類算法。因其具有算法原理簡單、易于實(shí)現(xiàn)且能夠快速發(fā)現(xiàn)任意形狀簇的優(yōu)點(diǎn),自該算法被出以來,大量的研究學(xué)者對其進(jìn)行了研究與應(yīng)用。FSDP聚類算法的優(yōu)點(diǎn)突出,然而其缺點(diǎn)也很明顯。FSDP聚類算法主要存在以下幾個方面的不足:(1)截斷距離參數(shù)?_?的取值難以確定,主要依靠主觀經(jīng)驗(yàn),缺乏一定的選擇依據(jù);(2)聚類中心的選取需要人為參與,聚類結(jié)果的客觀性和準(zhǔn)確性得不到保障;(3)在計(jì)算數(shù)據(jù)對象的局部密度和最小距離時,由于需要遍歷數(shù)據(jù)集中所有的數(shù)據(jù)對象,導(dǎo)致算法的時間復(fù)雜度過高,不適用于大規(guī)模數(shù)據(jù)集的聚類分析工作。針對FSDP聚類算法存在的上述問題,本文分別出了相應(yīng)的改進(jìn)方案:(1)針對FSDP聚類算法中截斷距離參數(shù)?_?的取值難以確定和聚類中心的選取需要人為參與的問題,出了一種將布谷鳥搜索算法與基于密度峰值聚類算法相融合的聚類算法。首先,改進(jìn)后的算法利用布谷鳥搜索算法通過預(yù)定義的局部密度信息熵適應(yīng)度函數(shù),為FSDP聚類算法搜索到恰當(dāng)?shù)慕財嗑嚯x,并通過得到的截斷距離求得數(shù)據(jù)集中數(shù)據(jù)對象的局部密度和最小距離。然后,利用布谷鳥搜索算法通過預(yù)定義的Rand適應(yīng)度函數(shù)在數(shù)據(jù)集的局部密度和最小距離空間內(nèi)為FSDP尋找到一組合適的局部密度和最小距離閥值(這里為了加快這組閥值的搜索速度,針對原始布谷鳥搜索算法存在后期收斂速度慢、搜索精度低的缺點(diǎn),出了一種改進(jìn)的布谷鳥搜索算法來替代原始布谷鳥搜索算法執(zhí)行搜索操作)。通過比較數(shù)據(jù)集中數(shù)據(jù)對象的局部密度和最小距離與這組閥值的大小關(guān)系,選取局部密度和最小距離均大于這組閥值的數(shù)據(jù)對象作為聚類中心執(zhí)行聚類。通過實(shí)驗(yàn)證明,改進(jìn)后的聚類算法在不需要人為參與的情況下,不僅能夠有效地自動選取到正確的聚類中心,并且可以取得較好的聚類效果。(2)針對FSDP聚類算法對大規(guī)模數(shù)據(jù)集進(jìn)行聚類分析時,由于算法的時間復(fù)雜度過高而導(dǎo)致算法運(yùn)行效率過低的問題,出了一種基于Spark的并行FSDP聚類算法SFSDP,并將SFSDP算法應(yīng)用到城市熱點(diǎn)區(qū)域探測應(yīng)用中。通過對城市熱點(diǎn)區(qū)域的有效探測驗(yàn)證了該算法的實(shí)用性。首先,算法通過空間網(wǎng)格劃分將待聚類數(shù)據(jù)集劃分成多個數(shù)據(jù)量相對均衡的數(shù)據(jù)分區(qū);然后,利用改進(jìn)的FSDP聚類算法并行地對各個數(shù)據(jù)分區(qū)內(nèi)的數(shù)據(jù)對象執(zhí)行聚類分析工作;最后,通過將各個數(shù)據(jù)分區(qū)聚類得到的局部聚簇集合并,生成全局聚簇集。實(shí)驗(yàn)結(jié)果表明,SFSDP并行聚類算法與FSDP聚類算法相比能夠有效地進(jìn)行大規(guī)模數(shù)據(jù)集的聚類分析工作,并且SFSDP聚類算法在準(zhǔn)確性和擴(kuò)展性方面都有很好的表現(xiàn)。
【圖文】：

圖 2-2 Spark 分布式執(zhí)行涉及的組件[29] Spark 數(shù)據(jù)分析棧 為大數(shù)據(jù)分析應(yīng)用 供了一個統(tǒng)一數(shù)據(jù)處理的平臺，在這個平的組件。Spark 在架構(gòu)上主要包含內(nèi)核（Spark Core）部分和多QL、Spark Streaming、MLlib、GraphX）。圖 2-3 給出了 Spark 的它們進(jìn)行簡單介紹。圖 2-3 Spark 數(shù)據(jù)分析棧Spark Core 模塊

圖 2-3 Spark 數(shù)據(jù)分析棧Spark Core 模塊park 整個計(jì)算框架實(shí)現(xiàn)的基石，Spark 核心模塊除了為 Spark 計(jì)須的基礎(chǔ)功能外，還給出了彈性分布式數(shù)據(jù)集 RDD 的 API 定義是 Spark 的主要編程接口，自 Spark 2.0 起，RDD 被 Dataset 所DD 的強(qiáng)類型，但對其進(jìn)行了更多的優(yōu)化。Spark Core 供了創(chuàng)的多個 API。Spark SQL 模塊SQL 是 Spark 用來對結(jié)構(gòu)化數(shù)據(jù)進(jìn)行操作的程序包。與基本的SQL 所 供的接口為 Spark 應(yīng)用 供了更多與正在執(zhí)行的數(shù)據(jù)在內(nèi)部，Spark SQL 通過利用這些額外的信息為應(yīng)用 供更多 供了多種與 Spark SQL 進(jìn)行交互的方式，包括 SQL 和 Data，不管上層使用哪種方式或編程語言來表示計(jì)算，底層都會使開發(fā)人員在不同 API 之間來回切換時 供了很大的便利。Spark Streaming 模塊
【學(xué)位授予單位】：江南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP311.13

【參考文獻(xiàn)】

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

1 蘇芙華;劉云連;伍鐵斌;;求解無約束優(yōu)化問題的改進(jìn)布谷鳥搜索算法[J];計(jì)算機(jī)工程;2014年05期

2 楊志;羅可;;一種改進(jìn)的基于粒子群的聚類算法[J];計(jì)算機(jī)應(yīng)用研究;2014年09期

3 楊燕;靳蕃;KAMEL Mohamed;;聚類有效性評價綜述[J];計(jì)算機(jī)應(yīng)用研究;2008年06期

4 賀玲;吳玲達(dá);蔡益朝;;數(shù)據(jù)挖掘中的聚類算法綜述[J];計(jì)算機(jī)應(yīng)用研究;2007年01期

5 陳寧,陳安,周龍驤;基于密度的增量式網(wǎng)格聚類算法(英文)[J];軟件學(xué)報;2002年01期

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

1 周瑞紅;基于群智能優(yōu)化理論的聚類改進(jìn)方法及應(yīng)用研究[D];吉林大學(xué);2017年

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

1 楊志偉;基于Spark平臺推薦系統(tǒng)研究[D];中國科學(xué)技術(shù)大學(xué);2015年

2 孫科;基于Spark的機(jī)器學(xué)習(xí)應(yīng)用框架研究與實(shí)現(xiàn)[D];上海交通大學(xué);2015年

3 林澤楨;聚類分析中基于密度算法的研究與改進(jìn)[D];復(fù)旦大學(xué);2013年

，

本文編號：2605021