姜群　田立偉　李蓉蓉　黃欣欣

摘? 要：為了解決傳統(tǒng)關(guān)聯(lián)規(guī)則算法在數(shù)據(jù)存儲(chǔ)、挖掘效率和算法的擴(kuò)展性等方面無法滿足智慧城市大數(shù)據(jù)挖掘需求的問題，采用Hadoop及MapReduce計(jì)算框架，實(shí)現(xiàn)了數(shù)據(jù)的分布式存儲(chǔ)以及Apriori算法的并行化計(jì)算。在此基礎(chǔ)上，通過進(jìn)一步的實(shí)驗(yàn)，證明了Apriori算法的挖掘效率及可擴(kuò)展性。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則;挖掘;算法

中圖分類號(hào)：TP311.13;TP393? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）02-0020-03

Abstract：In order to solve the problem of the traditional association rule algorithm unable to meet the needs of mining smart city big data in terms of data storage，mining efficiency and algorithm scalability，this paper uses Hadoop and MapReduce computing frameworks to implement distributed storage of data and parallelized Apriori algorithm. On this basis，through further experiments，the efficiency and scalability of Apriori algorithm are proved.

Keywords：association rule;mining;algorithm

0? 引? 言

智慧城市利用多種現(xiàn)代技術(shù)提高醫(yī)療、交通、能源、教育和生活服務(wù)的質(zhì)量及效率。隨著城市智能化的廣泛開展，所產(chǎn)生的數(shù)據(jù)量越來越大，這些數(shù)據(jù)往往是TB甚至PB級(jí)的、異構(gòu)的和多學(xué)科的，很難直接被使用[1]。怎樣從這些數(shù)據(jù)中提取有價(jià)值的信息，發(fā)現(xiàn)信息之間的聯(lián)系，進(jìn)一步為智慧城市的決策和維護(hù)提供支持，成為當(dāng)前亟待解決的問題。數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘是解決此類問題潛力最大的現(xiàn)代技術(shù)之一，它能夠發(fā)現(xiàn)隱藏在大數(shù)據(jù)集中的關(guān)聯(lián)鏈接。然而，傳統(tǒng)的關(guān)聯(lián)規(guī)則算法Apriori算法需要多次搜索事務(wù)庫，容易造成很大的I/O開銷、時(shí)間開銷及可能的內(nèi)存溢出等問題。因此，應(yīng)用大數(shù)據(jù)平臺(tái)并行化算法成為解決智慧城市大數(shù)據(jù)挖掘的關(guān)鍵問題。筆者在廣東科技學(xué)院高校重點(diǎn)平臺(tái)建設(shè)躍升計(jì)劃類基金項(xiàng)目的子項(xiàng)目“數(shù)據(jù)學(xué)科與大數(shù)據(jù)技術(shù)專業(yè)——數(shù)據(jù)分析、數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)方向科研支撐項(xiàng)目”的支持下，對(duì)算法的并行化進(jìn)行了研究，本文是該研究的成果。

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

1.1? 關(guān)聯(lián)規(guī)則

數(shù)據(jù)挖掘也稱為KDD，指的是從數(shù)據(jù)庫中挖掘大量數(shù)據(jù)以揭示隱含的、未知的和可能有用的信息。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的重要分支[2]。關(guān)聯(lián)規(guī)則挖掘用于發(fā)現(xiàn)隱藏在大數(shù)據(jù)集中的關(guān)聯(lián)鏈接。

1.1.1? 基本概念

關(guān)聯(lián)規(guī)則挖掘是一種基于規(guī)則的機(jī)器學(xué)習(xí)方法，用于發(fā)現(xiàn)大型數(shù)據(jù)庫中項(xiàng)集之間的相互關(guān)系，旨在使用支持度及置信度技術(shù)來識(shí)別數(shù)據(jù)庫中的強(qiáng)關(guān)聯(lián)。在事務(wù)數(shù)據(jù)庫中，項(xiàng)的集合稱為項(xiàng)集，包含K個(gè)項(xiàng)的項(xiàng)集稱為K-項(xiàng)集。設(shè)有項(xiàng)集X和項(xiàng)集Y，支持度support（X->Y）=（同時(shí)包含項(xiàng)集X和項(xiàng)集Y的事務(wù)數(shù)/事務(wù)總數(shù)）×100%，即支持度為X，Y同時(shí)出現(xiàn)的概率;置信度confidence（X->Y）=（同時(shí)包含項(xiàng)集X和項(xiàng)集Y的事務(wù)數(shù)/包含項(xiàng)集X的事務(wù)數(shù)）×100%，即置信度為條件概率P（Y|X）。如果支持度和置信度均大于給定的閾值，即：support（X->Y）≥最小支持度閾值，并且confidence（X->Y）≥最小置信度閾值的關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘主要是通過對(duì)強(qiáng)關(guān)聯(lián)規(guī)則的挖掘發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)程度。

1.1.2? 關(guān)聯(lián)規(guī)則挖掘過程

關(guān)聯(lián)規(guī)則的挖掘過程主要包含兩步[3]：首先，找出支持度大于或等于所設(shè)定的最小支持度的所有項(xiàng)集，即找到數(shù)據(jù)庫中所有頻繁項(xiàng)集;然后對(duì)頻繁項(xiàng)集應(yīng)用最小置信度限制條件產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。雖然第二步比較直接，但要找到數(shù)據(jù)庫中所有的頻繁項(xiàng)集，需要搜索數(shù)據(jù)庫中所有可能的項(xiàng)集是很難的，而Apriori算法采用廣度優(yōu)先搜索，很好地解決了問題。

1.2? Apriori算法

Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，它有效地采用了廣度優(yōu)先逐層搜索的迭代方法，使搜索過程快速完成。算法流程如下：

（1）找出頻繁項(xiàng)：數(shù)據(jù)庫中所有出現(xiàn)頻率大于或等于最小支持度閾值的項(xiàng)。

（2）找出頻繁項(xiàng)集：由頻繁項(xiàng)產(chǎn)生候選項(xiàng)集，并剪枝。

（3）找出強(qiáng)關(guān)聯(lián)規(guī)則：由頻繁項(xiàng)集中滿足最小支持度閾值和最小置信度閾值的規(guī)則產(chǎn)生。

Apriori算法核心偽代碼：

Ck as a candidate itemset of size k.

Lk as a frequent itemset of size k.

L1= {frequent items};

For? （k= 2; Lk-1！ = ?; k++） do begin

Ck= candidates generated from Lk-1;

For each transaction t in database D do

Incrementing the count of all candidates in Ck that are contained in t

Lk = candidates in Ck with min_sup

End

return? ∪K LK? //all frequent itemsets;

由于算法需要多次掃描事務(wù)數(shù)據(jù)庫進(jìn)行候選計(jì)數(shù)，導(dǎo)致Apriori算法的效率相對(duì)較低。在最壞的情況下，會(huì)產(chǎn)生相當(dāng)多的非頻繁候選項(xiàng)集，并且計(jì)算成本較高，特別是當(dāng)候選集相對(duì)較長的時(shí)候，時(shí)間和空間受到挑戰(zhàn)。本文采用MapReduce編程框架并行化Apriori算法，由于MapReduce數(shù)據(jù)分片，降低了時(shí)間成本，提高了挖掘效率。

2? MapReduce

MapReduce[4]是Hadoop的核心計(jì)算框架，用于支持計(jì)算機(jī)集群上大型數(shù)據(jù)集的分布式計(jì)算。MapReduce將復(fù)雜的、大規(guī)模集群上的并行計(jì)算過程抽象到Map函數(shù)和Reduce函數(shù)上，其核心思想是“分而治之”——把用戶的原始數(shù)據(jù)源進(jìn)行分塊，分發(fā)給由一個(gè)主節(jié)點(diǎn)管理下的各個(gè)分節(jié)點(diǎn)共同并行處理完成。

2.1? Map函數(shù)

Map函數(shù)的輸入來自HDFS的文件塊，文件塊是一系列元素的集合，Map函數(shù)對(duì)以鍵值對(duì)形式的輸入元素根據(jù)需求進(jìn)行處理，轉(zhuǎn)換成新的鍵值對(duì)，發(fā)送給Reduce函數(shù)[5]。在鍵值對(duì)中，value代表與任務(wù)相關(guān)的數(shù)據(jù)，key代表“組號(hào)”的值，key和value的類型可以是任意的，key也沒有唯一性。

2.2? Reduce函數(shù)

Reduce函數(shù)根據(jù)key值進(jìn)行排序，將具有相同key值的鍵值對(duì)組織在一起，輸出Reduce函數(shù)處理后的鍵值對(duì)，所有輸出結(jié)果會(huì)合并成一個(gè)文件。

在MapReduce模型中，程序員不需要關(guān)心數(shù)據(jù)通信的細(xì)節(jié)，因此在MapReduce模型中，對(duì)程序員來說就是接口。可以被看作是一個(gè)“l(fā)etter”，key是字母的發(fā)送地址，value是字母的內(nèi)容。具有相同地址的字母將被傳遞到同一個(gè)地方。程序員只需要正確設(shè)置，MapReduce模型就可以自動(dòng)準(zhǔn)確地將相同鍵的值聚集在一起。MapReduce框架的工作原理[6]如圖1所示。

3? 實(shí)驗(yàn)過程

3.1? 實(shí)驗(yàn)運(yùn)行環(huán)境

實(shí)驗(yàn)基于具有以下硬件配置的PC：Intel（R）Core（TM）i7-6500U，CPU @ 2.50 GHz * 4，8.00 GB RAM和1 TB硬盤，64位操作系統(tǒng)。軟件環(huán)境使用相同的配置：Linux操作系統(tǒng)（Ubuntu 16.04），Cloudera–QuickStart-VM，選用VirtualBox虛擬機(jī)。

3.2? 數(shù)據(jù)集

本實(shí)驗(yàn)使用的大數(shù)據(jù)來自網(wǎng)站[7]，該數(shù)據(jù)是比利時(shí)法蘭德斯地區(qū)的智能交通事故數(shù)據(jù)集，共包含340 184個(gè)交通事故記錄，572個(gè)不同的屬性值，平均每個(gè)事故包含45個(gè)屬性。交通事故數(shù)據(jù)包含有關(guān)事故發(fā)生的不同情況的大量信息：事故過程（碰撞類型、道路使用者、受傷情況……）、交通狀況（最大速度、優(yōu)先規(guī)則……）、環(huán)境條件（天氣、光照條件、事故發(fā)生時(shí)間……）、道路狀況（路面狀況、障礙物……）和地理狀況（地點(diǎn)、物理特征……）等。

3.3? 實(shí)驗(yàn)結(jié)果

Apriori算法用Java實(shí)現(xiàn)，最小支持度設(shè)定為30%，其運(yùn)行結(jié)果如表1所示。

從表1中可以看出有用的關(guān)聯(lián)，比如高速公路（HIW）附近地區(qū)（COL）的交叉口（INT）比非高速公路（NHW）地區(qū)更容易發(fā)生兩輪車事故（1）。高速公路上多車道（MVHNLT）和固定物/分隔物（FO）撞擊事故多發(fā)生在夜間（T6），并且高速公路上的交叉口是發(fā)生此類撞擊事故的一個(gè)道路特征。此外，晚上在森林地帶（FOR）和農(nóng)業(yè)區(qū)域（AGL）附近的道路易發(fā)生車輛翻車事故（TWH）……

基于MapReduce的并行Apriori算法用于從大數(shù)據(jù)集中提取頻繁項(xiàng)集，并獲取有助于決策的關(guān)聯(lián)規(guī)則，但為了進(jìn)一步提高挖掘效率，下面比較當(dāng)數(shù)據(jù)集的大小增加時(shí)的運(yùn)行時(shí)間效率。

3.4? 不同數(shù)據(jù)集及節(jié)點(diǎn)數(shù)的運(yùn)行效果比較

該實(shí)驗(yàn)在兩個(gè)不同數(shù)據(jù)集上測(cè)試算法的性能，兩個(gè)數(shù)據(jù)集分別包含150 000個(gè)事務(wù)和340 000個(gè)事務(wù)，并且在具有不同數(shù)量節(jié)點(diǎn)的Hadoop集群上運(yùn)行。Apriori算法在兩個(gè)數(shù)據(jù)集的第1～第6個(gè)節(jié)點(diǎn)上運(yùn)行，以便比較運(yùn)行算法所需的時(shí)間。獲得的結(jié)果如圖2所示。

本文使用速度增加作為標(biāo)準(zhǔn)來測(cè)量基于MapReduce的并行Apriori算法的性能。當(dāng)節(jié)點(diǎn)數(shù)量增加時(shí)，計(jì)算和傳輸并行執(zhí)行，在這種情況下，速度隨著數(shù)據(jù)數(shù)量的增加而增加，這證明并行計(jì)算Apriori算法可以提高大規(guī)模數(shù)據(jù)集的挖掘速度，并且具有可擴(kuò)展性。

4? 結(jié)? 論

本文使用MapReduce模型并行化Apriori算法。實(shí)驗(yàn)結(jié)果證明：當(dāng)節(jié)點(diǎn)數(shù)量增加，Apriori的并行化運(yùn)行速度增加;當(dāng)節(jié)點(diǎn)數(shù)不變，數(shù)據(jù)量成倍增加，不會(huì)導(dǎo)致并行化運(yùn)行速度成倍減少。因此，Apriori的并行化不僅能夠解決智慧城市大數(shù)據(jù)的關(guān)聯(lián)挖掘難題，還能提高數(shù)據(jù)挖掘效率，且擴(kuò)展性良好。未來的工作是優(yōu)化算法設(shè)計(jì)，以減少掃描事務(wù)數(shù)據(jù)庫和保存數(shù)量龐大的頻繁項(xiàng)候選集的開銷。

參考文獻(xiàn)：

[1] 覃雄派，王會(huì)舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS與MapReduce的競(jìng)爭與共生 [J].軟件學(xué)報(bào)，2012，23（1）：32-45.

[2] HIPP J，G?NTZER U，NAKHAEIZADEH G. Algorithms for association rule mining——a general survey and comparison [J]. ACM SIGKDD Explorations Newsletter，2000，2（1）：58-64.

[3] 何小東，劉衛(wèi)國.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法比較研究 [J].計(jì)算機(jī)工程與設(shè)計(jì)，2005（5）：1265-1268.

[4] 姜群，傅瑜，李文生，等.基于謂詞的大數(shù)據(jù)抽樣技術(shù)研究 [J].重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)），2017，31（8）：120-124+203.

[5] Lars Vogel. MapReduce Introduction-Tutorial [EB/OL]. [2016-10-10].http：//www.vogella.com/tutorials/MapReduce/article.html.

[6] 孟小峰，慈祥.大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn) [J].計(jì)算機(jī)研究與發(fā)展，2013，50（1）：146-169.

[7] NIS. Frequent Itemset Mining Implementations Repository [EB/OL].[2012-04-06].http：//fimi.ua.ac.be/data/.

作者簡介：姜群（1959-），女，漢族，重慶人，副教授，雙碩士學(xué)位，主要研究方向：大數(shù)據(jù)挖掘、智能計(jì)算研究;田立偉（1979-），男，漢族，山東濰坊人，副教授，博士，主要研究方向：云計(jì)算大數(shù)據(jù)。