基于MapReduce的并行關(guān)聯(lián)規(guī)則挖掘算法

　　數(shù)據(jù)挖掘（ data mining）又稱做知識(shí)發(fā)現(xiàn)（knowledge disco-ver in database，KDD），其目的在于發(fā)現(xiàn)大量數(shù)據(jù)集中有價(jià)值的隱含信息。常見的數(shù)據(jù)挖掘任務(wù)有關(guān)聯(lián)規(guī)則挖掘、分類、聚集、離群點(diǎn)檢測(cè)等。關(guān)聯(lián)規(guī)則挖掘是最重要的數(shù)據(jù)挖掘任務(wù)之一，由Agrawal等人提出，其目的是發(fā)現(xiàn)事務(wù)（項(xiàng)）之間存在的隱含關(guān)聯(lián)。關(guān)聯(lián)規(guī)則挖掘一般分為兩個(gè)階段，即發(fā)現(xiàn)頻繁項(xiàng)集和根據(jù)頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。由于根據(jù)頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則相對(duì)容易實(shí)現(xiàn)，所以關(guān)聯(lián)規(guī)則挖掘研究主要關(guān)注的是如何在數(shù)據(jù)集中找到頻繁出現(xiàn)的項(xiàng)集，這個(gè)過程也稱為頻繁項(xiàng)集挖掘（ frequent itemsets mining）或頻繁模式挖掘（frequent patterns　mining）。傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法主要可以分為三類：a）產(chǎn)生測(cè)試方法，通過迭代產(chǎn)生候選頻繁項(xiàng)集并進(jìn)行分別計(jì)數(shù)，統(tǒng)計(jì)得到頻繁項(xiàng)集，典型的算法是Agrawal等人心1提出的算法及其一系列的改進(jìn)算法，如DHP、DIC等；b）模式增長(zhǎng)方法，它不用產(chǎn)生候選項(xiàng)集，而是將所有頻繁項(xiàng)壓縮成一種特殊的數(shù)據(jù)結(jié)構(gòu)（一般為樹結(jié)構(gòu)），通過在數(shù)據(jù)結(jié)構(gòu)上進(jìn)行遍歷直接產(chǎn)生頻蘩項(xiàng)集，典型的算法有FP-Growth、LP-tree、FIUT、IFP、FPUTPLElol等；c）垂直格式方法，是將水平格式的數(shù)據(jù)集轉(zhuǎn)換成垂直格式，通過交運(yùn)算來得到頻繁項(xiàng)集，典型的算法有Eclat等。

　　隨著信息技術(shù)的快速發(fā)展，需要存儲(chǔ)和分析的數(shù)據(jù)量呈爆炸性增長(zhǎng)，人類已經(jīng)進(jìn)入了大數(shù)據(jù)時(shí)代，傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法已經(jīng)不能適應(yīng)大數(shù)據(jù)挖掘的要求，主要困難是：?jiǎn)我挥?jì)算機(jī)無法存儲(chǔ)所需要挖掘的所有數(shù)據(jù)及挖掘過程中產(chǎn)生的中間結(jié)果；挖掘過程所需要的內(nèi)存遠(yuǎn)遠(yuǎn)超過單一機(jī)器的存儲(chǔ)量；計(jì)算時(shí)間太長(zhǎng)無法忍受等。需要開發(fā)分布式、并行關(guān)聯(lián)規(guī)則挖掘算法解決上述問題。

　　MapReduce是一種由Google于2004年提出的一種易用且功能強(qiáng)大的并行編程模型，具有使用簡(jiǎn)單、自動(dòng)容錯(cuò)、負(fù)載均衡、伸縮性好等優(yōu)點(diǎn)，其開源實(shí)現(xiàn)Hadoop已經(jīng)廣泛應(yīng)用于很多大數(shù)據(jù)分析領(lǐng)域，已經(jīng)有了很多將傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法向MapReduce模型進(jìn)行遷移的研究，很大程度上解決了大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的問題。這些算法的主要思想都是利用Ha-doop中的分布式文件系統(tǒng)（HDFS）來解決海量數(shù)據(jù)存儲(chǔ)和分片的問題，利用MapReduce未實(shí)現(xiàn)挖掘算法的并行執(zhí)行。