趙林莉+楊曉光

摘要：本文對(duì)關(guān)聯(lián)規(guī)則挖掘中的基于多最小支持度模型的MS-Apriori算法進(jìn)行了介紹，并且對(duì)MS-Apriori算法展開分析，針對(duì)該算法在單機(jī)串行模式下運(yùn)行效率較低的問題提出改進(jìn)方案，該方案主要依托云計(jì)算技術(shù)，基于hadoop平臺(tái)。算法經(jīng)過改進(jìn)，可實(shí)現(xiàn)數(shù)據(jù)的分布式和并行化處理，提高了傳統(tǒng)關(guān)聯(lián)規(guī)則算法的執(zhí)行效率。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則 MS-Apriori算法 MapReduce

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2015）10-0000-00

1 關(guān)聯(lián)規(guī)則挖掘概述

關(guān)聯(lián)規(guī)則挖掘是為了發(fā)掘事物之間的聯(lián)系，它是數(shù)據(jù)挖掘中應(yīng)用較為廣泛的方法之一。目前，社會(huì)上多個(gè)領(lǐng)域均已應(yīng)用此方法進(jìn)行數(shù)據(jù)分析。它的算法執(zhí)行過程為：

（1）找出所有頻繁集。根據(jù)用戶設(shè)定的最小支持度，在事務(wù)數(shù)據(jù)庫(kù)中找出全部滿足閾值要求的頻繁項(xiàng)集；

（2）產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。

由第（1）步產(chǎn)生的頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則，只有達(dá)到最小可信度要求的關(guān)聯(lián)規(guī)則才能成為強(qiáng)關(guān)聯(lián)規(guī)則。

因?yàn)樵诘冢?）步中，生成強(qiáng)關(guān)聯(lián)規(guī)則實(shí)現(xiàn)起來相對(duì)較簡(jiǎn)單，而快速有效地找出頻繁項(xiàng)集卻是一個(gè)相對(duì)復(fù)雜的過程，所以關(guān)聯(lián)規(guī)則挖掘研究的重點(diǎn)就集中在如何高效地生成有價(jià)值的頻繁項(xiàng)集[ ]。

2 MS-Apriori算法分析

MS-Apriori算法[ ]是一個(gè)基于多支持度模型的算法，它是Liu提出的Apriori算法的改進(jìn)算法，它為每個(gè)項(xiàng)目均指定一個(gè)最小支持度，這樣就可以解決由單一支持度所引發(fā)的“稀有項(xiàng)”[2]問題。此算法頻繁項(xiàng)集的生成方法與Apriori算法類似。

MS-Apriori算法在執(zhí)行時(shí)要將數(shù)據(jù)集中的項(xiàng)目按照給定的各個(gè)項(xiàng)的最小支持度排序，在生成1-頻繁項(xiàng)集時(shí)，符合條件的項(xiàng)集要滿足各自的最小支持度要求。在生成2-頻繁項(xiàng)集時(shí)，集合中的兩項(xiàng)都要滿足最低的最小支持度要求，并且滿足支持度差別才能成為候選集。生成k-頻繁項(xiàng)集時(shí)，在剪枝過程中不能輕易刪除項(xiàng)集，因?yàn)榧词鼓澈蜻x集的子集不是頻繁項(xiàng)集，但若它里面含有支持度限定較低的項(xiàng)，它很可能滿足較低的最小支持度的要求，這一點(diǎn)與Apriori有很大不同。

MS-Apriori算法簡(jiǎn)單，比較容易理解，利于編程實(shí)現(xiàn)，迭代次數(shù)易于控制。并且該算法使關(guān)聯(lián)規(guī)則挖掘在實(shí)用性方面有了很大改進(jìn)，但是由于其核心仍然是Apriori算法，它需要反復(fù)讀取數(shù)據(jù)集，并且會(huì)產(chǎn)生龐大的候選集，在單機(jī)模式下，算法的挖掘效率仍存在很大缺陷。

3基于云技術(shù)的MS-Apriori算法研究

經(jīng)過前面的分析，傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘模式多是基于本地的單機(jī)的挖掘模式，由于處理海量數(shù)據(jù)效率的低下，該模式越來越不能勝任當(dāng)前海量的數(shù)據(jù)存儲(chǔ)與處理的要求。 隨著云計(jì)算技術(shù)的發(fā)展，大數(shù)據(jù)的處理拋棄了傳統(tǒng)的方式。云計(jì)算是并行計(jì)算（Parallel Computing）、分布式計(jì)算（DistributedComputing）和網(wǎng)格計(jì)算（Grid Computing）的發(fā)展。利用云計(jì)算平臺(tái)對(duì)大數(shù)據(jù)進(jìn)行研究成為學(xué)者們熱衷的研究方式。

Hadoop作為一種開源的分布式處理的云計(jì)算框架，適合大數(shù)據(jù)的分布式處理和計(jì)算，可以有效解決傳統(tǒng)數(shù)據(jù)挖掘模式中處理數(shù)據(jù)效率低的問題。它的核心包括了分布式文件存儲(chǔ)和分布式任務(wù)管理兩部分，即HDFS和MapReduce。HDFS，是一個(gè)分布式文件系統(tǒng)。HDFS基于網(wǎng)絡(luò)進(jìn)行構(gòu)建，運(yùn)行于集群上，以流式數(shù)據(jù)訪問模式來存儲(chǔ)超大文件[ ]。MapReduce是一種編程模型，適用于并行處理大規(guī)模數(shù)據(jù)。

3.1 MapReduce編程模型

MapReduce編程模型是建立在HDFS基礎(chǔ)上的，它分為Map階段和Reduce階段。HDFS會(huì)將數(shù)據(jù)源分割為若干個(gè)子集，這些子集會(huì)存放在各個(gè)節(jié)點(diǎn)中，Map函數(shù)可以把復(fù)雜任務(wù)分解為若干個(gè)簡(jiǎn)單任務(wù)執(zhí)行，這些任務(wù)可以并行計(jì)算，這樣計(jì)算規(guī)模相較于原任務(wù)將大大縮小。Reduce階段的主要工作是對(duì)Map階段產(chǎn)生的結(jié)果進(jìn)行匯總。MapReduce處理流程如圖1所示。

3.2 基于MapReduce的MS-Apriori算法

在MapReduce模型的基礎(chǔ)上，可以將MS-Apriori算法轉(zhuǎn)換為分布和并行執(zhí)行的算法。其挖掘過程如下：

（1）轉(zhuǎn)換數(shù)據(jù)集，重新排列數(shù)據(jù)項(xiàng)，按多最小支持度值升序排列數(shù)據(jù)項(xiàng)；

（2）分割數(shù)據(jù)集，并將其分發(fā)到各個(gè)節(jié)點(diǎn)中。

（3）將數(shù)據(jù)轉(zhuǎn)換為的形式，其中key表示事務(wù)，value表示數(shù)據(jù)項(xiàng)。

（4）由map函數(shù)處理數(shù)據(jù)塊中的數(shù)據(jù)，按照MS-Apriori的算法產(chǎn)生局部候選項(xiàng)集，將結(jié)果轉(zhuǎn)換為鍵/值對(duì)的形式保存項(xiàng)目與其計(jì)數(shù)，若出現(xiàn)重復(fù)性鍵值，調(diào)用combiner函數(shù)。

（5）將由map階段產(chǎn)生的局部候選項(xiàng)集合并為全局候選項(xiàng)集，此項(xiàng)工作由reducer函數(shù)完成。

（6）最終通過掃描數(shù)據(jù)集得到候選項(xiàng)集的真實(shí)計(jì)數(shù)，與最小支持度對(duì)比得到k-頻繁項(xiàng)集。

其挖掘流程如圖2所示。

3.3 實(shí)例分析

示例數(shù)據(jù)集如表1所示，假設(shè)min_sup（I1）=50%，min_sup（I2）=70%，min_sup（I3）=20%，min_sup（I4）=35%，min_sup（I5）=40%，無支持度差別限制，m=3，r=1

4結(jié)語(yǔ)

傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法認(rèn)為數(shù)據(jù)項(xiàng)的分布是均勻的，它們出現(xiàn)的頻率是相近的，針對(duì)每一個(gè)數(shù)據(jù)項(xiàng)采用單一的最小支持度，但在實(shí)際應(yīng)用中數(shù)據(jù)項(xiàng)出現(xiàn)的頻率差別較大。多支持度模型可以很好地解決這一問題，云計(jì)算的發(fā)展，使算法分布式、并行化執(zhí)行變得可行，使關(guān)聯(lián)規(guī)則挖掘算法從執(zhí)行效率和實(shí)用性方面都得到了良好的改進(jìn)。