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

1、在數(shù)據(jù)挖掘領(lǐng)域,關(guān)聯(lián)規(guī)則挖掘算法是用來(lái)解決所挖掘事務(wù)之間的聯(lián)系和相關(guān)性,該算法在商業(yè)、科研以及物流等方面得到了廣泛的應(yīng)用。伴隨大數(shù)據(jù)時(shí)代的來(lái)臨,數(shù)據(jù)挖掘中所要處理海量數(shù)據(jù)維度也由簡(jiǎn)單的一維拓展到高維。傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法對(duì)于海量數(shù)據(jù)的處理,在時(shí)空性能和效率方面都捉襟見(jiàn)肘。同時(shí),高性能計(jì)算和云計(jì)算的快速發(fā)展為并行關(guān)聯(lián)規(guī)則挖掘算法帶來(lái)了新的機(jī)遇和挑戰(zhàn)。論文首先針對(duì)串行 FP-growth算法提出了一種并行化改進(jìn)思想,其次利用高性能計(jì)算集群

2、和Hadoop不同的編程策略,對(duì)改進(jìn)思想在兩平臺(tái)上進(jìn)行實(shí)例化測(cè)試,測(cè)試結(jié)果表明,雖然兩平臺(tái)上都較好地降低了挖掘頻繁項(xiàng)集時(shí)的I/O和通信開(kāi)銷(xiāo),但Hadoop環(huán)境下算法測(cè)試性能更佳。論文的創(chuàng)新性工作如下:
　　(1)針對(duì)傳統(tǒng) FP-growth改進(jìn)算法需要多次訪問(wèn)多個(gè)數(shù)據(jù)庫(kù),內(nèi)部處理器間通信成本高等問(wèn)題,提出了一種改進(jìn)的并行FP-growth算法。該算法利用一種已存在的高效樹(shù)的重構(gòu)機(jī)制,對(duì)初始化的FP-tree進(jìn)行重構(gòu),進(jìn)而降低挖掘頻

3、繁項(xiàng)集時(shí)的I/O開(kāi)銷(xiāo),同時(shí),該算法僅需對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次訪問(wèn),較好地降低了時(shí)間開(kāi)銷(xiāo)。
　　(2)針對(duì)傳統(tǒng)并行頻繁項(xiàng)集挖掘算法往往基于單一的MPI(Message Passing Interface)編程模式不能取得理想的性能,提出了一種基于MPI/OpenMP混合編程的并行FP-growth算法。該方法結(jié)合高性能計(jì)算集群,采用MPI/OpenMP混合編程模式,在高性能計(jì)算分布式集群環(huán)境中移植IPF算法,利用OpenMP在節(jié)點(diǎn)內(nèi)核間多

4、核并行建立數(shù)據(jù)庫(kù),MPI進(jìn)行進(jìn)程間計(jì)算結(jié)果的傳遞。測(cè)試結(jié)果表明,移植的算法具有較好的加速比,可擴(kuò)展性強(qiáng)。
　　(3)針對(duì)傳統(tǒng)高性能計(jì)算集群不能有效處理節(jié)點(diǎn)失效、負(fù)載均衡等問(wèn)題,提出了一種基于 Hadoop平臺(tái)的并行 FP-growth算法。該方法在 Hadoop平臺(tái)中移植 IPF算法,利用 Hadoop分布式文件系統(tǒng)(HDFS)存儲(chǔ)數(shù)據(jù),MapReduce模式實(shí)現(xiàn)并行調(diào)度以及負(fù)載均衡,而且提出了一種基于Hadoop平臺(tái)的并行安全架