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

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

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

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