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

1、隨著信息技術的不斷發(fā)展，各行各業(yè)已經積累了大量的數(shù)據，為了將這些數(shù)據轉化為有用的知識，產生了數(shù)據挖掘技術。然而，傳統(tǒng)的串行化數(shù)據挖掘技術在面對海量數(shù)據時效率難以讓人滿意。并行化技術近年來發(fā)展迅速，可以有效提升算法效率，是處理海量數(shù)據的利器，因此，使用并行化技術提升數(shù)據挖掘算法效率成為時下的研究熱點。
　　關聯(lián)規(guī)則挖掘技術是數(shù)據挖掘的一個重要分支，主要研究的是事務數(shù)據庫中有利用價值項之間的關系。頻繁項集挖掘是關聯(lián)規(guī)則挖掘中最重要的環(huán)

2、節(jié)，因此本文中的關聯(lián)規(guī)則挖掘算法其實也是針對如何挖掘頻繁模式的頻繁模式挖掘算法。關聯(lián)規(guī)則挖掘中的基本算法主要有多候選產生算法(Apriori，劃分，抽樣等)，模式增長算法(FP-growth，HMine，F(xiàn)PMax，Close+等)和垂直格式算法(Eclat，CHARM等)。本文旨在將部分關聯(lián)規(guī)則挖掘算法與并行計算技術相結合，介紹若干個關聯(lián)規(guī)則挖掘算法的并行化方案。本文分別探討了基于CPU、GPU和分布式環(huán)境下的并行關聯(lián)規(guī)則挖掘算法，介

3、紹了相關的并行化技術，并對本文中用到的兩個重要技術GPU-CUDA并行計算框架和MapReduce-Spark并行計算框架做了詳細介紹。
　　FP-growth算法是一種基于內存的頻繁模式挖掘算法。然而，當數(shù)據集很大或者支持度閡值太小時，構造基于主存的全局頻繁模式樹是不現(xiàn)實的。FP-growth算法擴展化方案將大數(shù)據集切分成小數(shù)據集，然后通過在這些小數(shù)據集執(zhí)行FP-growth算法來解決此問題。本文在分析研究FP-growth算法

4、擴展化方案的基礎上，采用并行投影的核心思想，介紹了一種簡單分組算法。在考慮節(jié)點間負載均衡的基礎上，對簡單分組算法改進，介紹了一種負載均衡的分組算法?；谏鲜龇纸M算法，實現(xiàn)了基于Spark的并行FP-growth算法—Spark-FP-growth算法，該算法通過分組算法將大數(shù)據集切分成小數(shù)據集，然后分別在小數(shù)據集上并行執(zhí)行FP-growth算法得到頻繁項集。為了進一步提升算法效率，本文又引入Topk聚集的思想，將小數(shù)據集上的FP-gro

5、wth算法提升為Topk-FP-growth算法，加強了算法的可用性和速度性能。
　　基于上述算法，本文又研究了關聯(lián)規(guī)則挖掘算法在Spark-GPU平臺上的并行化方案。在分析研究眾多Spark和GPU融合技術的基礎上，采用Spark RDD pipe接口調用GPU-CUDA程序實現(xiàn)Spark和GPU的結合。基于Spark-GPU平臺的關聯(lián)規(guī)則挖掘算法—Spark-GPU-Apriori算法依然采用Spark-FP-growth算法

6、的分組模型，但將小數(shù)據上的FP-growth算法替換為使用CUDA加速的Apriori算法。Spark-GPU-Apriori算法展現(xiàn)了一種涵蓋多種并行級別，將Spark和GPU有機結合的并行關聯(lián)規(guī)則挖掘算法。
　　以Spark-Apriori算法和Spark-mblib-FP-growth算法作為基準算法。本文分別測試對比了Spark-SPFP-growth算法、Spark-BPFP-growth算法和Spark-GPU-Apr