聚類CLIQUE算法及其并行化研究.pdf

1、數(shù)據挖掘是幫助人們在海量數(shù)據中發(fā)現(xiàn)信息和知識的工具。近年來數(shù)據挖掘技術成了商業(yè)智能的核心技術，被廣泛應用到了諸多領域，引起了學術界極大的關注。聚類分析是數(shù)據挖掘中的一個重要研究領域，它從數(shù)據庫中尋找數(shù)據間的相似性，從而優(yōu)化大規(guī)模數(shù)據庫的查詢和發(fā)現(xiàn)數(shù)據中隱含的有用信息或知識。如何進行快速聚類以及如何取得更好的聚類結果成了聚類數(shù)據挖掘算法研究的重點和難點。 CLIQUE算法綜合了基于密度和基于網格的聚類方法，它有著速度快的優(yōu)點。但是

2、由于方法太簡化，可能會降低聚類結果的精確性。通過深入的研究和分析，發(fā)現(xiàn)由于CLIQUE算法沒有考慮到如何利用當前挖掘數(shù)據的特性，而是進行一種硬性的網格劃分，因此增加了計算復雜程度，而為了降低計算的復雜程度就只能降低聚類結果的精確性。針對上述問題論文引入了自適應的網格劃分方法，通過在一維的情況下預先分割區(qū)間，然后找出密集分割區(qū)間并對分界進行調整來得到密集區(qū)間，最后把這些密集區(qū)間作為劃分網格的依據。這種劃分網格的方法很好地利用了當前要挖掘的

3、數(shù)據的特性，同時減少了網格的數(shù)量以及密集單元候選集的數(shù)目，大幅度減少了計算的復雜程度，從而使得在每個子空間進行計算成為了現(xiàn)實，也大大提高了聚類結果的精確性，但算法的時間復雜度仍是指數(shù)級的。只是這個指數(shù)是維數(shù)，使得算法的時間復雜度比起很多聚類算法的仍然簡單很多。 為了進一步提高算法的執(zhí)行效率，論文還對并行CLIQUE算法進行了研究。選用通過商用網絡連接起來的PC機，以及并行虛擬機PVM和分布式操作系統(tǒng)LINUX，共同構成了一個機群

4、系統(tǒng)作為并行計算平臺。在并行程序的模型上選用了Master/Slave模型。該并行算法將數(shù)據集分配到各個節(jié)點機上實現(xiàn)了數(shù)據并行，在數(shù)據并行的基礎上，當生成密集單元候選集以及驗證密集單元的時候又采取了任務并行的方法。由于主體是數(shù)據并行，因此達到了接近線性的加速比。每個節(jié)點計算任務的時間復雜度由兩部分構成，一部分是指數(shù)級的驗證密集單元的時間復雜度，另一部分是線性的通信時間復雜度。 最后，通過實驗驗證了并行CLIQUE算法的可行性，從