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

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

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

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

4、法。采用數據集劃分技術對數據集進行劃分，由控制處理器分配數據集到各個處理器，實現挖掘部分的并行化。該算法遵循FP-growth算法思想，然而基于FP-tree的挖掘要創(chuàng)建復雜的數據結構，要對數據庫進行兩遍掃描，當數據庫很大時FP-tree的創(chuàng)建是一個瓶頸問題?；诖耍岢隽艘环N新的創(chuàng)建FP-tree的并行算法——在各個處理器上建立FP-tree,以達到優(yōu)化各個處理器中所存儲數據的結構、有效利用內存的目的。然后通過控制處理器合并各FP-t