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

陳鳳娟

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

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

陳鳳娟

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

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

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

1．引言

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

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

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

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

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

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

3．MapReduce模型

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

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

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

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

4．基于MapReduce的挖掘算法

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

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

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

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

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

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

5．結(jié)束語

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

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

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

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

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

[5]應毅，劉亞軍．MapReduce并行計算技術(shù)發(fā)展綜述[J]．計算機系統(tǒ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ù)挖掘、粗糙集。