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

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

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

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

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