[發明專利]一種基于MapReduce模型的并行關聯方法

無效

• 申請號: 201310064117.1
• 申請日: 2013-03-01
• 公開（公告）號: CN103150163A
• 公開（公告）日: 2013-06-12
• 發明（設計）人: 李千目;陳強富;施叢叢;魏士祥;印杰;侯君
• 申請（專利權）人: 南京理工大學常熟研究院有限公司
• 主分類號: G06F9/44
• 分類號: G06F9/44;G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于數據挖掘技術，特別是一種基于MapReduce模型的并行關聯方法。

背景技術

隨著信息化技術的不斷發展，人們的現實生活都被數字化了，各種數據被搜集起來，引起了數據爆炸式的增長，為了充分挖掘這些數據之間的關聯性，許多公司投入了大量了人力財力來進行數據分析。數據分析得到的結果是企業決策的重要依據，所以，數據分析的方法決定了這些數據的價值。

在數據挖掘方面，關聯規則是非常重要的一種技術。它能夠將數據庫中的一些具有相關聯性的數據分析出來。關聯規則的挖掘一般分為兩步的步驟。第一階段，從原始資料集合中找出所有頻繁項集(Large?Itemsets)。頻繁的意思是指某一項目組出現的頻率相對于所有記錄而言，必須達到某一水平。該水平值被稱為支持度，若支持度大于等于所設定的最小支持度(Minimum?Support)閥值時，則該項目組稱為頻繁項集。一個滿足最小支持度的k項集，則稱為頻繁k項集(Frequent?k-itemset)。算法從頻繁k項集中再產生頻繁k+1項集，直到無法再找到更長的頻繁項集為止。第二階段是產生關聯規則(Association?Rules)。從頻繁項集產生關聯規則，是利用前一步驟的頻繁k項集來產生規則，在最小置信度(Minimum?Confidence)的閥值下，若一規則所求得的置信度滿足最小置信度，稱此規則為關聯規則。

在并行式的關聯規則挖掘算法方面，Rakesh?Agrawal等（Rakesh?Agrawal,John?C.?Shafer.?Parallel?Mining?of?Association?Rules[J].?IEEE?Transactions?on?Knowledge?and?Data?Engineering.?1996,?8(6):?962-969P.）提出了三種并行式的關聯規則挖掘算法：CD，DD，CaD。這幾種關聯規則挖掘算法都是基于Apriori算法，主要是通過計數來獲得頻繁項集并通過集合遞推的方式來獲得最終結果。

在分布式的編程模型方面，谷歌公司提出了Map/Reduce的分布式編程模型，如圖1所示，其利用map和reduce框架能夠在分布式的集群上實現大規模的分布式計算（Dean?J.?and?Ghemawat?S.?Mapreduce:?simplified?data?processing?on?large?clusters[J],?Commun.?ACM,?51,?1,?pp.?107-113,?2008.），并且具有很高的穩定性能。

發明內容

本發明的目的在于提供一種基于MapReduce模型的并行關聯方法，從而實現了在巨量的數據中并行式的數據關聯性分析，并且克服并行計算的弊端。

實現本發明目的的技術解決方案為：一種基于MapReduce模型的并行關聯方法，步驟如下：

第一步，對數據進行預處理，將所有的數據值規約在有限的離散集合中，并設置最小支持度fF和最小置信度fS。

第二步，在MapReduce編程框架下，特殊處理1項集，即：把整個數據集作為輸入文件，實現一個map類來統計數據中候選項的計數，實現一個reduce類來合并由map進程返回的計數，然后處理第一個任務，輸出作為一個文件，包含1項集的計數m和總記錄個數n。

第三步，主進程讀取第一個任務的輸出文件，利用公式???????????????????????????????????????????????計算出支持度，如果該支持度不小于最小支持度fF的話，可以得到頻繁1項集。

第四步，為第k（k>=2）個任務設置map類和reduce類，這兩個類實現并行關聯算法CD，利用map/reduce框架來執行任務，輸出包含k項集的項目名和該項目的計數。

第五步，主進程讀取第k個任務的輸出集合，計算并對比支持度，獲得了頻繁k項集，然后計算出k+1項侯選集，如果k+1項候選集為空，那么結束該步驟；如果候選集為非空，那么執行第四步，設置k值等于k+1，開始下一輪的循環。

第六步，利用公式來計算置信度，如果置信度大于最小置信度fS，該規則就是強規則。

本發明與現有技術相比，其顯著優點：（1）利用Map/Reduce編程模型，能夠執行分布式的計算，充分地利用集群的效率；（2）使用Map/Reduce能夠有效地進行負載均衡；（3）使用Map/Reduce能夠有效的避免分布式的節點失效。

附圖說明

圖1是現有技術中MapReduce編程模型。