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

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

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

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

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