并行關(guān)聯(lián)規(guī)則挖掘算法的研究.pdf

1、隨著數(shù)據(jù)庫(kù)技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫(kù)管理系統(tǒng)的廣泛應(yīng)用，人們積累的數(shù)據(jù)越來(lái)越多。面對(duì)海量的存儲(chǔ)數(shù)據(jù)，如何從中發(fā)現(xiàn)有價(jià)值的信息或知識(shí)是一項(xiàng)非常艱巨的任務(wù)。數(shù)據(jù)挖掘就是為了滿足這種需求而迅速發(fā)展起來(lái)的。數(shù)據(jù)挖掘是指從大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中提取隱含的、先前未知的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則。數(shù)據(jù)挖掘是人工智能和數(shù)據(jù)庫(kù)發(fā)展相結(jié)合發(fā)展的產(chǎn)物，是目前國(guó)際上數(shù)據(jù)庫(kù)和信息決策系統(tǒng)最前沿的研究方向之一。
　　 關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)重要

2、的研究問(wèn)題，從1993年Agrawal等人提出至今，一直是學(xué)術(shù)界和產(chǎn)業(yè)界廣泛關(guān)注的熱點(diǎn)。挖掘關(guān)聯(lián)規(guī)則問(wèn)題的核心是發(fā)現(xiàn)頻繁項(xiàng)集。隨著數(shù)據(jù)庫(kù)中存儲(chǔ)的數(shù)據(jù)量不斷增大，提高挖掘效率，研究具有高性能的數(shù)據(jù)挖掘算法，快速發(fā)現(xiàn)頻繁項(xiàng)集是一個(gè)非常重要的課題。而并行計(jì)算是處理大數(shù)據(jù)量最直接有效的方法。
　　 CD算法是對(duì)Apriori算法的簡(jiǎn)單并行化，其目的是減少通信量，獲得較好的任務(wù)分布性。但當(dāng)頻繁的模式長(zhǎng)度較長(zhǎng)時(shí)它的性能會(huì)很差，其中候選集的產(chǎn)

3、生是最耗時(shí)的工作，占據(jù)了整個(gè)計(jì)算量的大部分。FP-growth(frequent pattern-growth)是近年來(lái)公布的效率較高的頻繁集挖掘算法之一，它是一種不產(chǎn)生候選的挖掘頻繁項(xiàng)目集的方法。它通過(guò)構(gòu)造一個(gè)高度壓縮的數(shù)據(jù)結(jié)構(gòu)(FP-tree),壓縮原來(lái)的事務(wù)數(shù)據(jù)庫(kù)，避免了高代價(jià)的候選項(xiàng)的產(chǎn)生，獲得更高的效率。
　　 本文針對(duì)CD算法存在的I/O量較重、數(shù)據(jù)結(jié)構(gòu)重復(fù)、不能有效利用整個(gè)內(nèi)存等問(wèn)題，提出一種新的并行關(guān)聯(lián)規(guī)則挖掘算

4、法。采用數(shù)據(jù)集劃分技術(shù)對(duì)數(shù)據(jù)集進(jìn)行劃分，由控制處理器分配數(shù)據(jù)集到各個(gè)處理器，實(shí)現(xiàn)挖掘部分的并行化。該算法遵循FP-growth算法思想，然而基于FP-tree的挖掘要?jiǎng)?chuàng)建復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，要對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩遍掃描，當(dāng)數(shù)據(jù)庫(kù)很大時(shí)FP-tree的創(chuàng)建是一個(gè)瓶頸問(wèn)題。基于此，提出了一種新的創(chuàng)建FP-tree的并行算法——在各個(gè)處理器上建立FP-tree,以達(dá)到優(yōu)化各個(gè)處理器中所存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)、有效利用內(nèi)存的目的。然后通過(guò)控制處理器合并各FP-t