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

陳鳳娟

(遼寧對(duì)外經(jīng)貿(mào)學(xué)院，遼寧 大連 116052)

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

陳鳳娟

(遼寧對(duì)外經(jīng)貿(mào)學(xué)院，遼寧 大連 116052)

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一項(xiàng)重要技術(shù)，它主要是通過(guò)頻繁項(xiàng)集挖掘得到關(guān)聯(lián)規(guī)則?；谠朴?jì)算的MapReduce模型的數(shù)據(jù)挖掘算法可以提高挖掘的效果及性能。

關(guān)聯(lián)規(guī)則；頻繁項(xiàng)集；MapReduce；數(shù)據(jù)挖掘

1．引言

計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)飛速發(fā)展，各個(gè)行業(yè)中存儲(chǔ)了海量的數(shù)據(jù)，并且這些數(shù)據(jù)的數(shù)量還在增長(zhǎng)。這些海量數(shù)據(jù)蘊(yùn)含著豐富的知識(shí)，如何找出數(shù)據(jù)中蘊(yùn)含的知識(shí)，為各種決策提供幫助成為了一個(gè)迫切需要解決的問(wèn)題。數(shù)據(jù)挖掘技術(shù)運(yùn)用了機(jī)器學(xué)習(xí)和模式識(shí)別等多個(gè)領(lǐng)域的知識(shí)，為解決這個(gè)實(shí)際問(wèn)題提供了有力的工具。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個(gè)主要技術(shù)，它能從給定的數(shù)據(jù)集中，通過(guò)關(guān)聯(lián)規(guī)則挖掘算法，找出各個(gè)屬性之間的關(guān)聯(lián)關(guān)系，以及多個(gè)屬性域之間的依賴關(guān)系，這種依賴關(guān)系對(duì)決策和預(yù)測(cè)有作用。

MapReduce是由谷歌研究員提出的一種分布式編程框架，是一個(gè)用于處理海量數(shù)據(jù)的并行編程模型，可以運(yùn)行在異構(gòu)環(huán)境下，編程簡(jiǎn)單，不必關(guān)心底層實(shí)現(xiàn)細(xì)節(jié)。對(duì)現(xiàn)有的關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行改進(jìn)，使這些算法能在MapReduce模型中運(yùn)行，利用并行技術(shù)提高算法的性能。

2．關(guān)聯(lián)規(guī)則的基本概念

關(guān)聯(lián)規(guī)則的挖掘是分兩步來(lái)實(shí)現(xiàn)的，首先按照用戶給定的最低閾值，找出數(shù)據(jù)集中的所有頻繁項(xiàng)目集，然后從頻繁項(xiàng)目集中構(gòu)造規(guī)則，要求構(gòu)造的規(guī)則的可信度大于等于用戶設(shè)定的最低值。支持度是對(duì)關(guān)聯(lián)規(guī)則代表的重要性進(jìn)行度量的指標(biāo)，它體現(xiàn)了關(guān)聯(lián)規(guī)則的頻度。如果某個(gè)項(xiàng)集的支持度的值太小，則表明相應(yīng)的規(guī)則很可能只是偶然發(fā)生的。

設(shè)U={U1，U2，…，Un}為n個(gè)不同字符的集合，其中的字符稱為項(xiàng)或商品。任意一個(gè)集合X?U稱為一個(gè)項(xiàng)集，若|X|=k，則稱X為k項(xiàng)集。事務(wù)（或交易）T是項(xiàng)的集合，且任意的T?U，對(duì)應(yīng)每一個(gè)事務(wù)有唯一的標(biāo)識(shí)，記作TID。設(shè)A= {T1，T2，…，Tn}，稱A為U上的交易集或者數(shù)據(jù)集，簡(jiǎn)稱交易集或者數(shù)據(jù)集。如果X?T，稱事務(wù)T包含X。對(duì)于一個(gè)項(xiàng)集X和一個(gè)交易集A，X在A中的支持度定義為X在A中的支持計(jì)數(shù)與A中總的交易個(gè)數(shù)之比，記作sup(X)。如果X的支持度大于某個(gè)給定的最小閾值，則稱X是頻繁的。

頻繁項(xiàng)集挖掘就是要在事務(wù)數(shù)據(jù)庫(kù)里找出所有大于給定的最小支持度的頻繁項(xiàng)集。頻繁閉項(xiàng)集是一組事務(wù)都包含的項(xiàng)的最大項(xiàng)集。頻繁閉項(xiàng)集和頻繁項(xiàng)集的信息量相等，但是頻繁閉項(xiàng)集比頻繁項(xiàng)集的元素少很多，因此挖掘頻繁閉項(xiàng)集能夠滿足用戶的需求并且對(duì)減少了算法的開銷，提升了頻繁項(xiàng)集挖掘的效率，同時(shí)還減少了冗余信息的輸出。

3．MapReduce模型

MapReduce是一個(gè)將大型分布式計(jì)算轉(zhuǎn)換成為行串行化分布式計(jì)算的編程模型，它用Key/Value，即鍵/值對(duì)的形式來(lái)表示分布式計(jì)算，完成分布式操作。通過(guò)計(jì)算機(jī)集群，在Hadoop/MapReduce框架中，把用戶定義的MapReduce任務(wù)分布到集群中的各個(gè)節(jié)點(diǎn)上執(zhí)行。

能用MapReduce來(lái)處理的數(shù)據(jù)集必須是能分解成多個(gè)小數(shù)據(jù)集的數(shù)據(jù)集合，并且每個(gè)小數(shù)據(jù)集都可以完全并行地進(jìn)行處理，否則，這個(gè)數(shù)據(jù)集合是不能用MapReduce來(lái)處理的。一個(gè)MapReduce分布式計(jì)算由兩個(gè)過(guò)程組成，一個(gè)是Map過(guò)程，一個(gè)是Reduce過(guò)程，其中，Map過(guò)程也叫映射過(guò)程，而Reduce過(guò)程也叫規(guī)約過(guò)程。MapReduce框架將輸入的數(shù)據(jù)分成多個(gè)能并行運(yùn)算的數(shù)據(jù)片段，然后將每一個(gè)數(shù)據(jù)片段分配給一個(gè)Map任務(wù)，每一個(gè)Map任務(wù)執(zhí)行相同的操作，即對(duì)分配給它的數(shù)據(jù)片段的key/value對(duì)進(jìn)行計(jì)算，生成一個(gè)中間結(jié)果，這個(gè)過(guò)程稱為Map過(guò)程。Map過(guò)程把計(jì)算得到的所有具有相同key值的value，經(jīng)過(guò)計(jì)算后傳遞給Reduce函數(shù)，而Reduce任務(wù)會(huì)將從Map得到的二元組key/value集合的片段作為輸入，調(diào)用用戶定義的Reduce函數(shù)，將value值合并，得到value的集合，這個(gè)過(guò)程稱為Reduce過(guò)程。

無(wú)論是Map過(guò)程還是Reduce過(guò)程，它們的每個(gè)任務(wù)的執(zhí)行都支持容錯(cuò)功能，當(dāng)任一個(gè)或多個(gè)節(jié)點(diǎn)在計(jì)算過(guò)程中出現(xiàn)錯(cuò)誤時(shí)，都會(huì)自動(dòng)將出錯(cuò)的任務(wù)重新分配到其他節(jié)點(diǎn)上，讓其他節(jié)點(diǎn)完成計(jì)算。并行運(yùn)行多個(gè)Map和Reduce任務(wù)，為系統(tǒng)提供了很好的負(fù)載均衡同時(shí)也降低了運(yùn)行中失敗的任務(wù)被重新運(yùn)行的代價(jià)。

MapReduce采用“分而治之”的思想，有效地降低每一部分的運(yùn)算復(fù)雜度，提高了運(yùn)算效率，屏蔽了底層的實(shí)現(xiàn)細(xì)節(jié)，有效降低并行編程難度，提高編程效率。它的不足主要體現(xiàn)在以下方面：首先它善于處理松耦合型的數(shù)據(jù)，對(duì)不容易分解成多個(gè)相互獨(dú)立的子任務(wù)的計(jì)算任務(wù)的處理效率很低；其次，它不能顯式地支持迭代計(jì)算；最后它是一種離線計(jì)算框架，不擅長(zhǎng)進(jìn)行流式計(jì)算和實(shí)時(shí)分析。

4．基于MapReduce的挖掘算法

常用的關(guān)聯(lián)規(guī)則挖掘算法有Apriori算法、A-Coles算法、Closet算法和ECLAT算法。這些算法都可以轉(zhuǎn)化成基于MapReduce的挖掘算法。

Apriori算法是一種寬度優(yōu)先的多趟掃描算法，主要包含連接和剪枝兩個(gè)步驟。連接操作主要是生成候選集Ck，而剪枝主要是刪除候選集中不可能成為頻繁項(xiàng)集的元素。該算法首先掃描數(shù)據(jù)集，計(jì)算數(shù)據(jù)集中所有單個(gè)項(xiàng)目的支持度計(jì)數(shù)，然后再次掃描數(shù)據(jù)集，第k次掃描時(shí)，首先通過(guò)對(duì)Lk-1中的項(xiàng)目集的連接操作生成k-項(xiàng)集的候選集Ck，再利用Apriori性質(zhì)進(jìn)行剪枝，刪除Ck中不可能是頻繁項(xiàng)集的候選項(xiàng)，最后的頻繁項(xiàng)集的集合為∪Lk。

A-Coles算法是一個(gè)基于Apriori算法的挖掘頻繁閉項(xiàng)集的算法，它的主要思想是通過(guò)多次掃描數(shù)據(jù)集生成所有的頻繁閉項(xiàng)集，屬于自底向上的寬度優(yōu)先的搜索。A-Coles算法主要由兩步組成，第一步是通過(guò)寬度優(yōu)先的搜索策略發(fā)現(xiàn)所有的頻繁閉項(xiàng)集的生成器，第二步利用函數(shù)計(jì)算出每一個(gè)生成器對(duì)應(yīng)的頻繁閉項(xiàng)集。A-Close通過(guò)引入剪裁技術(shù)減小搜索范圍，但是該算法需要多次掃描數(shù)據(jù)集，而且會(huì)產(chǎn)生大量的候選項(xiàng)集，因此對(duì)內(nèi)存的消耗較大。

Closet算法是一個(gè)基于頻繁模式樹的頻繁閉項(xiàng)集挖掘算法，它把原始數(shù)據(jù)集中的事務(wù)間的關(guān)聯(lián)信息壓縮到頻繁模式樹中，通過(guò)得到的頻繁模式樹生成每一個(gè)頻繁項(xiàng)的條件頻繁模式樹，每一個(gè)條件模式樹中存儲(chǔ)了包含該頻繁項(xiàng)并且支持度大于等于給定支持度的頻繁模式。Closet算法只需遍歷兩次原始數(shù)據(jù)集，降低了對(duì)數(shù)據(jù)集的訪問(wèn)，不需要生成任何侯選項(xiàng)集，有效地提高了挖掘效率。但是當(dāng)數(shù)據(jù)量大的時(shí)候，Closet算法生成的頻繁模式樹的規(guī)模過(guò)大，導(dǎo)致算法性能下降。

ECLAT算法是采用垂直數(shù)據(jù)表示的頻繁項(xiàng)集挖掘算法，在該算法中，首次提出垂直數(shù)據(jù)表示的概念，用垂直數(shù)據(jù)表示可以大大減少掃描數(shù)據(jù)集的次數(shù)，以概念格理論為基礎(chǔ)，采用深度優(yōu)先搜索策略，采用前綴等價(jià)關(guān)系劃分搜索空間。ECLAT算法對(duì)數(shù)據(jù)集只需要掃描一次，使用數(shù)據(jù)垂直表示形式，通過(guò)交叉計(jì)數(shù)來(lái)計(jì)算支持度，在實(shí)際應(yīng)用中有較好的效果，是一種性能較好的頻繁項(xiàng)集挖掘算法。

可以充分利用云計(jì)算提供的分布式并行計(jì)算功能，對(duì)Apriori算法、A-Coles算法、Closet算法和ECLAT算法加以改進(jìn)，得到新的適用于云計(jì)算的頻繁項(xiàng)集挖掘方法。

5．結(jié)束語(yǔ)

關(guān)聯(lián)規(guī)則有許多挖掘算法，這些算法各自都有自己的優(yōu)點(diǎn)和不足，為了提高這些算法的效果，可以依托于云計(jì)算平臺(tái)，基于MapReduce模型，改進(jìn)已有的各種算法，利用并行計(jì)算的功能，提升算法的性能。

[1]戎祥，李玲娟．基于MapReduce的頻繁項(xiàng)集挖掘方法[J]．西安郵電學(xué)院學(xué)報(bào)，2011，16(4)：37-40．

[2]付沙，周航軍．關(guān)聯(lián)規(guī)則挖掘Aproiri算法的研究與改進(jìn)[J]．微電子學(xué)與計(jì)算機(jī)，2013，30(9)：110-114．

[3]趙偉衛(wèi)，趙航等．基于MapReduce的海量數(shù)據(jù)挖掘技術(shù)研究[J]．計(jì)算機(jī)工程與應(yīng)用，2013，49(20)：112-117．

[4]霍然，王宏志等．基于Map-Reduce的大數(shù)據(jù)實(shí)體識(shí)別算法[J]．計(jì)算機(jī)研究與發(fā)展，2013，50(16)：170-179．

[5]應(yīng)毅，劉亞軍．MapReduce并行計(jì)算技術(shù)發(fā)展綜述[J]．計(jì)算機(jī)系統(tǒng)應(yīng)用，2014，23(4)：1-11．

Association Rules Mining Based on MapReduce

Chen Fengjuan
(Liaoning University of International Business and Economics,Dalian 116052,Liaoning)

tract】 Association rules mining is one of the most important techniques of data mining.It mainly gets the association rules by mining frequent itemsets.The data mining algorithms which are based on MapReduce model of cloud computing can improve the effect and performance.

words】 association rules;frequent itemset;MapReduce;data mining

陳鳳娟，女，遼寧本溪人，碩士，副教授，研究領(lǐng)域：數(shù)據(jù)挖掘、粗糙集。