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

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

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

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

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

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

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