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

【參考文獻】

相關期刊論文 前8條

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

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

3 熊壬浩;劉羽;;A*算法的改進及并行化[J];計算機應用;2015年07期

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

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

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

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

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

相關博士學位論文 前1條

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

相關碩士學位論文 前4條

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

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

3 段明秀;層次聚類算法的研究及應用[D];中南大學;2009年

4 張鑫;層次聚類算法的研究與應用[D];江西理工大學;2009年

本文編號：2769206