發(fā)布時(shí)間：2020-07-24 18:08

【摘要】：聚類是數(shù)據(jù)分析的一種基礎(chǔ)操作。聚類算法由于聚類過程和結(jié)果形式的不同,分為劃分聚類和分層聚類兩大類。因?yàn)榉謱泳垲愃惴ㄊ褂脴湫徒Y(jié)構(gòu)表示結(jié)果,其包含的信息量更大,并且不需要用戶提供任何參數(shù),由此可見分層聚類算法具有一定的優(yōu)勢。但在實(shí)際應(yīng)用中,由于分層聚類算法的過程是確定的,如果在算法執(zhí)行過程中某一合并或分裂操作不當(dāng),就會(huì)導(dǎo)致錯(cuò)誤的聚類結(jié)果,從而影響聚類的準(zhǔn)確性。近幾年,計(jì)算機(jī)界出現(xiàn)了一種解題的新思路,將目標(biāo)問題轉(zhuǎn)換為最短路徑問題,再借助求解最短路徑問題的思路求解目標(biāo)問題。因此,本文借鑒了求解最短路徑問題的思路對分層聚類算法進(jìn)行了深入的研究。首先,分析現(xiàn)有的聚類算法,通過對分層聚類算法與劃分聚類算法進(jìn)行比較,剖析了分層聚類算法的優(yōu)勢和不足之處;并研究現(xiàn)有的路徑搜索算法,分析搜索算法的優(yōu)缺點(diǎn)。其次,為了解決分層聚類算法中不能回溯的問題,提出了一種基于最短路徑策略的分層聚類算法(Shortest path hierarchical clustering algorithm,簡稱SPC)。其基本思想是首先將分層聚類問題轉(zhuǎn)換為一個(gè)最短路徑問題,然后通過A~*(A-Star,簡稱A~*)算法的搜索策略來求解該最短路徑問題,進(jìn)而達(dá)到對分層聚類問題的求解。通過理論分析和模擬實(shí)驗(yàn),驗(yàn)證了SPC算法相對于DNA簡約算法(DNA parsimony program,簡稱DNAPARS)在運(yùn)行效率和準(zhǔn)確性上都有提高,說明SPC算法具有一定的優(yōu)越性。再次,由于當(dāng)數(shù)據(jù)量較大時(shí),SPC算法所需的運(yùn)行時(shí)間比較長,針對此問題,提出了一種基于CUDA(Compute Unified Device Architecture,簡稱CUDA)加速的SPC算法(Shortest path hierarchical clustering algorithm based on CUDA accelerated,簡稱cudaSPC)。其主要的工作是利用GPU(Graphics Processing Unit,簡稱GPU)硬件并行地?cái)U(kuò)展多個(gè)節(jié)點(diǎn)。在模擬實(shí)驗(yàn)中,通過與SPC算法進(jìn)行比較,結(jié)果表明cudaSPC算法在準(zhǔn)確性不變的情況下,提高了算法的執(zhí)行效率。最后,對全文進(jìn)行了概括,并對將來的研究工作進(jìn)行了展望。
【學(xué)位授予單位】：中國民航大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP311.13

【參考文獻(xiàn)】

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

1 牛新征;司偉鈺;佘X;;基于進(jìn)化聚類的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)[J];軟件學(xué)報(bào);2017年07期

2 余騫;彭智勇;洪亮;萬言歷;;基于用戶鄰域和主題的新穎性Web社區(qū)推薦方法[J];軟件學(xué)報(bào);2016年05期

3 熊壬浩;劉羽;;A*算法的改進(jìn)及并行化[J];計(jì)算機(jī)應(yīng)用;2015年07期

4 李建伏;趙玉成;賀懷清;;基于最大似然原理的分類屬性數(shù)據(jù)分層聚類算法[J];計(jì)算機(jī)應(yīng)用與軟件;2015年03期

5 方濱興;賈焰;韓毅;;社交網(wǎng)絡(luò)分析核心科學(xué)問題、研究現(xiàn)狀及未來展望[J];中國科學(xué)院院刊;2015年02期

6 李建伏;吳鳳珍;趙玉成;;一種基于啟發(fā)式的分層聚類[J];計(jì)算機(jī)應(yīng)用與軟件;2014年05期

7 方媛;車啟鳳;;數(shù)據(jù)挖掘之聚類算法綜述[J];河西學(xué)院學(xué)報(bào);2012年05期

8 龍真真;張策;劉飛裔;張正文;;一種改進(jìn)的Chameleon算法[J];計(jì)算機(jī)工程;2009年20期

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

1 李建伏;基于DNA序列的進(jìn)化樹構(gòu)建算法的研究[D];哈爾濱工業(yè)大學(xué);2008年

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

1 趙振國;向量空間中A*算法的優(yōu)化及應(yīng)用[D];哈爾濱理工大學(xué);2016年

2 李大為;基于圖規(guī)劃和啟發(fā)式搜索的一致性規(guī)劃求解[D];吉林大學(xué);2013年

3 段明秀;層次聚類算法的研究及應(yīng)用[D];中南大學(xué);2009年

4 張鑫;層次聚類算法的研究與應(yīng)用[D];江西理工大學(xué);2009年

本文編號：2769206