智慧城市大數(shù)據(jù)中的關聯(lián)規(guī)則挖掘研究

姜群　田立偉　李蓉蓉　黃欣欣

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

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

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

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

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

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

1.1.1? 基本概念

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

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

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

1.2? Apriori算法

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

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

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

（3）找出強關聯(lián)規(guī)則：由頻繁項集中滿足最小支持度閾值和最小置信度閾值的規(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;

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

2? MapReduce

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

2.1? Map函數(shù)

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

2.2? Reduce函數(shù)

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

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

3? 實驗過程

3.1? 實驗運行環(huá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虛擬機。

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

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

3.3? 實驗結果

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

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

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

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

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

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

4? 結? 論

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

參考文獻：

[1] 覃雄派，王會舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS與MapReduce的競爭與共生 [J].軟件學報，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ù)挖掘中關聯(lián)規(guī)則挖掘算法比較研究 [J].計算機工程與設計，2005（5）：1265-1268.

[4] 姜群，傅瑜，李文生，等.基于謂詞的大數(shù)據(jù)抽樣技術研究 [J].重慶理工大學學報（自然科學），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ù)管理：概念、技術與挑戰(zhàn) [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-），女，漢族，重慶人，副教授，雙碩士學位，主要研究方向：大數(shù)據(jù)挖掘、智能計算研究;田立偉（1979-），男，漢族，山東濰坊人，副教授，博士，主要研究方向：云計算大數(shù)據(jù)。