基于MPI的層次聚類算法的研究及實現(xiàn).pdf

1、數(shù)據(jù)挖掘領域涉及很多方面的知識，聚類分析是該領域中的技術之一，也是該領域中重點研究內容之一。聚類分析實際上是對數(shù)據(jù)集進行分類、分組的一種方法。聚類分析應用廣泛，在機器學習、生物學、統(tǒng)計學、市場營銷等等很多領域都被用到，在這些領域中聚類分析起到了至關重要的作用，做出了不小的貢獻。聚類算法是聚類分析中起著決定性作用的部分，聚類分析的中的聚類算法有很多，其中層次聚類算法是主要算法之一。層次聚類算法的特點是結構簡單、運行時速度快，并且在遇到大規(guī)

2、模數(shù)據(jù)集的時候，它能夠對其進行有效的處理。該算法是實際應用中聚類分析的支柱。層次聚類算法在運行時，會對所有待聚類數(shù)據(jù)進行距離計算，得到距離矩陣，然后按照矩陣中元素的值對類進行合并操作，產(chǎn)生新的類，但是每一次合并操作之后，要再次對需所有類進行類間距離的計算，這樣的操作使得計算的時間復雜度很高。隨著數(shù)據(jù)規(guī)模的不斷遞增，提高聚類效率和聚類質量也是一個刻不容緩的研究方向。
　　 基于上述分析，針對層次聚類算法存在的問題，本文對傳統(tǒng)層次聚

3、類算法進行了改進，通過把類之間的距離按照一定順序進行排序，以此來解決合并類后還要重新計算距離的問題，在此基礎上本文又結合了最小生成樹的算法，即克魯斯卡爾算法對層次聚類算法做了進一步改進，總體上使得算法可伸縮性得到提高，計算復雜性得到降低。
　　 為進一步提高算法執(zhí)行效率，論文同時研究了并行層次聚類算法的并行實現(xiàn)。選用局域網(wǎng)環(huán)境，并行虛擬機PVM和LINUX，共同搭建的機群系統(tǒng)作為并行計算平臺。在并行程序的模型上采用了基于MPI消