基于聚類劃分的高效用模式并行挖掘算法

邢淑凝　劉方愛　趙曉暉

摘要：針對在大規(guī)模數(shù)據(jù)庫中挖掘高效用模式產(chǎn)生大量基于內(nèi)存的效用模式樹，從而導(dǎo)致內(nèi)存空間占用較大以及丟失一些高效用項(xiàng)集的問題，提出在Hadoop分布式計(jì)算平臺下的基于聚類劃分的高效用模式并行挖掘算法PUCP。首先，采用聚類的方法把數(shù)據(jù)庫中相似的事務(wù)劃分為若干數(shù)據(jù)子集；然后，把若干劃分好的數(shù)據(jù)子集分配到Hadoop平臺的各個(gè)節(jié)點(diǎn)中構(gòu)造效用模式樹；最后，把各個(gè)節(jié)點(diǎn)中相同項(xiàng)的條件模式基分配到同一個(gè)節(jié)點(diǎn)中進(jìn)行挖掘，以減少各個(gè)節(jié)點(diǎn)交叉操作的次數(shù)。通過實(shí)驗(yàn)結(jié)果和理論分析表明：PUCP算法在不影響挖掘結(jié)果可靠性的前提下，與主流串行高效用模式挖掘——效用模式增長挖掘算法（UP-Growth）和現(xiàn)有的并行高效用模式挖掘算法PHUI-Growth相比，挖掘效率分別提高了61.2%和16.6%；并且使用了Hadoop計(jì)算平臺，能有效緩解挖掘大規(guī)模數(shù)據(jù)的內(nèi)存壓力。

關(guān)鍵詞：大數(shù)據(jù)；高效用模式挖掘；聚類；并行計(jì)算；Hadoop

中圖分類號：TP301.6

文獻(xiàn)標(biāo)志碼：A

0引言

在大規(guī)模數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則，是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)十分重要并且具有挑戰(zhàn)性的研究內(nèi)容。頻繁模式挖掘[1-2]是關(guān)聯(lián)規(guī)則挖掘研究領(lǐng)域的一個(gè)基礎(chǔ)課題，但其只關(guān)心項(xiàng)集在數(shù)據(jù)庫中是否出現(xiàn)，而沒有考慮項(xiàng)集在一個(gè)事務(wù)中出現(xiàn)的次數(shù)和項(xiàng)集的重要度（如利潤）。因此，近幾年提出了高效用模式挖掘[3-6]。在高效用模式挖掘中，每個(gè)項(xiàng)都有唯一的權(quán)值和在不同事務(wù)中出現(xiàn)的次數(shù)，如果一個(gè)項(xiàng)集的效用值大于或等于用戶指定的最小效用閾值，則稱這個(gè)項(xiàng)集為高效用項(xiàng)集。高效用項(xiàng)集挖掘可以應(yīng)用在移動商務(wù)環(huán)境規(guī)劃[7]和零售商營銷[8]等多個(gè)方面。

現(xiàn)有的高效用模式挖掘分為兩類：一類是以“產(chǎn)生測試”的方式進(jìn)行挖掘，如Two-Phase[9]算法；另一類是以“模式增長”的方式進(jìn)行挖掘，如效用模式增長（Utility Pattern Growth， UP-Growth）挖掘算法[10]。Two-Phase算法引入事務(wù)加權(quán)效用值（Transaction Weighted Utilization， TWU）這一概念，提出了高估計(jì)效用值的方法；然而，該方法需要多次掃描原始數(shù)據(jù)庫并且會產(chǎn)生大量的候選高效用項(xiàng)集。為了解決這一問題，算法UP-Growth引入效用模式樹（Utility Pattern Tree， UP-Tree）結(jié)構(gòu)，以“模式增長”的方式進(jìn)行挖掘，并提出DGU（Discarding Global Unpromising items）、DGN（Discarding Global Node utilities）、DLU（Discarding Local Unpromising items）和DLN（Decreasing Local Node utilities）四個(gè)策略來減少候選高效用項(xiàng)集的數(shù)量。算法UP-Growth+[11]為了減少局部的效用值，在UP-Growth算法的基礎(chǔ)上進(jìn)行了改進(jìn)，將DLU和DLN策略改進(jìn)成DNU（Discarding local unpromising items and their estimated Node Utilities）和DNN（Decreasing local Node utilities for local UP-Tree by estimated utilities of descendant Nodes）策略。

目前現(xiàn)有的高效用模式并行挖掘算法較少，文獻(xiàn)[12]探討應(yīng)用MapReduce編程模型實(shí)現(xiàn)并行的挖掘，提出了算法PHUI-Growth（Parallel mining High Utility Itemsets by pattern-Growth），但是該算法并沒有深入研究數(shù)據(jù)集的分塊處理和降低數(shù)據(jù)通信開銷的方法，并且使用“產(chǎn)生檢測”的方式進(jìn)行挖掘，在挖掘過程中可能存在丟失高效用項(xiàng)集、產(chǎn)生大量的候選項(xiàng)集等問題，而且還需要利用大量的內(nèi)存空間來存儲非候選項(xiàng)集，增大了內(nèi)存開銷。針對這些問題，本文提出了一種基于聚類劃分并且使用Hadoop分布式計(jì)算平臺挖掘高效用模式的算法——PUCP（Parallel Utility mining based on Cluster Partition）。該算法采用“模式增長”的方式進(jìn)行挖掘，以聚類劃分的方式對原始數(shù)據(jù)庫進(jìn)行水平劃分，通過將互不重疊的數(shù)據(jù)子集分配給不同的Hadoop中的節(jié)點(diǎn)進(jìn)行處理，以增大并行粒度，減小交叉操作的規(guī)模，確保獲得完整的高效用模式，提高并行挖掘效率。

具體步驟如下：

步驟1

在Hadoop平臺master主節(jié)點(diǎn)中，按照UP-Growth算法的第一步對整個(gè)數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行處理，即去掉TWU小于minutil的項(xiàng)，并且將事務(wù)中的項(xiàng)按照TWU降序的順序進(jìn)行重新排序。利用Jaccard相似度系數(shù)對處理過的數(shù)據(jù)庫中事務(wù)進(jìn)行水平聚類劃分，將相似的事務(wù)劃分到一起，作為一個(gè)數(shù)據(jù)子集，將這些數(shù)據(jù)子集由主節(jié)點(diǎn)master分配到Hadoop平臺中的不同slave從節(jié)點(diǎn)中進(jìn)行處理。如圖1中的第一階段所示。

步驟2

每個(gè)salve節(jié)點(diǎn)根據(jù)本文提出的新的建樹算法產(chǎn)生效用模式樹，該算法是在UP-Growth算法的基礎(chǔ)上進(jìn)行的改進(jìn)，在樹節(jié)點(diǎn)中設(shè)置一個(gè)前綴效用和（pru）域，由文獻(xiàn)[3]描述的前綴效用和可知，前綴效用和更加接近項(xiàng)集真實(shí)的效用值，以此來減少候選高效用項(xiàng)集的數(shù)量。如圖1中的第二階段所示。

步驟3

每個(gè)slave節(jié)點(diǎn)根據(jù)效用模式樹，依據(jù)本文提出的改進(jìn)的條件模式基結(jié)構(gòu)產(chǎn)生該樹所有項(xiàng)的條件模式基。

步驟4

把每個(gè)salve節(jié)點(diǎn)中相同項(xiàng)的條件模式基分配到同一個(gè)節(jié)點(diǎn)中進(jìn)行處理，也就是說，一個(gè)節(jié)點(diǎn)中只存儲一個(gè)項(xiàng)（如：im）的全部條件模式基，并將項(xiàng)im所有條件模式基中的MIU域進(jìn)行比較，得到一個(gè)最小值作為項(xiàng)im的全局MIU值。如圖1中的第三階段所示。

步驟5

每個(gè)節(jié)點(diǎn)根據(jù)項(xiàng)的條件模式基產(chǎn)生條件效用模式樹，采用UP-Growth算法中的DLU和DLN策略遞歸產(chǎn)生候選高效用項(xiàng)集。

步驟6

將所有節(jié)點(diǎn)產(chǎn)生的候選高效用項(xiàng)集匯聚到master節(jié)點(diǎn)中，掃描劃分后的數(shù)據(jù)庫，計(jì)算所有候選高效用項(xiàng)集的真實(shí)效用值，得到高效用項(xiàng)集。如圖1中的第四階段所示。

2.1局部節(jié)點(diǎn)的具體處理過程如下：

步驟1

對重排序后數(shù)據(jù)庫中的事務(wù)進(jìn)行水平聚類劃分。

針對分類屬性數(shù)據(jù)（特別是購物籃數(shù)據(jù)）的特性，本文采用Jaccard相似度系數(shù)sim（T1，T2）對重排序后數(shù)據(jù)庫中的所有事務(wù)進(jìn)行水平聚類劃分。把每個(gè)數(shù)據(jù)子集當(dāng)中的第一個(gè)事務(wù)作為代表點(diǎn)，新的事務(wù)與每個(gè)數(shù)據(jù)子集中的代表點(diǎn)比較相似度，將其劃入最相似的數(shù)據(jù)子集中，即如果相似度小于用戶指定的閾值，則將其劃入新的數(shù)據(jù)子集中。當(dāng)產(chǎn)生的數(shù)據(jù)子集的個(gè)數(shù)達(dá)到k-1后，就將第k個(gè)數(shù)據(jù)子集作為與前k-1個(gè)數(shù)據(jù)子集不相似的事務(wù)的集合。該算法的時(shí)間主要耗費(fèi)在與每個(gè)數(shù)據(jù)子集的代表點(diǎn)進(jìn)行比較上，因此，整個(gè)算法的時(shí)間花費(fèi)是小于kn的，該算法具有較高的時(shí)間效率。以表1數(shù)據(jù)庫為例，對重新排列后的事務(wù)進(jìn)行水平聚類，根據(jù)sim函數(shù)計(jì)算后得到3個(gè)數(shù)據(jù)子集，如圖2所示：數(shù)據(jù)子集D1包含事務(wù)T1、T2、T5；數(shù)據(jù)子集D2包含事務(wù)T3、T4；數(shù)據(jù)子集D3包含事務(wù)T6，由于T6中的項(xiàng)都是非高效用項(xiàng)，所以經(jīng)過計(jì)算刪除后得到的是一個(gè)空集。

步驟2

對聚類劃分后的數(shù)據(jù)子集建立效用模式樹。

在每個(gè)slave節(jié)點(diǎn)中按照本文建樹的偽代碼來構(gòu)造效用模式樹。其中，樹中的每個(gè)節(jié)點(diǎn)有四個(gè)域：name域用來標(biāo)識項(xiàng)，pru域用來記錄節(jié)點(diǎn)的前綴效用和，count域記錄節(jié)點(diǎn)出現(xiàn)的次數(shù)，parent域記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。以圖2中的數(shù)據(jù)為例，由于數(shù)據(jù)子集D3中沒有候選高效用項(xiàng)，因此不能產(chǎn)生效用模式樹，數(shù)據(jù)子集D1、D2的效用模式樹分別如圖3（a）、（b）所示。

每個(gè)slave節(jié)點(diǎn)構(gòu)造完效用模式樹，根據(jù)該效用模式樹產(chǎn)生項(xiàng)條件模式基，該條件模式基有三個(gè)域：路徑效用域記錄路徑的效用值，支持度域記錄路徑出現(xiàn)的次數(shù)，MIU域記錄項(xiàng)在計(jì)算節(jié)點(diǎn)的最小效用值。根據(jù)圖3的效用模式樹，表3、4分別是D1和D2的局部條件模式基。

步驟3

一個(gè)節(jié)點(diǎn)只處理一個(gè)項(xiàng)的全局條件模式基。

將步驟2中每個(gè)salve節(jié)點(diǎn)中的一個(gè)項(xiàng)（如項(xiàng)im）的局部效用模式基合并到一個(gè)節(jié)點(diǎn)中進(jìn)行處理，該節(jié)點(diǎn)得到im的全局效用模式基，同時(shí)得到im的局部MIU值，經(jīng)過比較這些MIU值可以得到im的全局最小效用值。在該節(jié)點(diǎn)中利用UP-Growth算法中的步驟DLU和DLN策略對全局條件模式基進(jìn)行挖掘，得到候選高效用項(xiàng)集。

步驟4

將所有節(jié)點(diǎn)中的候選高效用項(xiàng)集合并到master主節(jié)點(diǎn)中計(jì)算它們的真實(shí)效用值，以此得到全局高效用項(xiàng)集。

3實(shí)驗(yàn)與結(jié)果分析

3.1實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

將本文提出的PUCP算法與主流的串行挖掘算法UP-Growth和現(xiàn)有并行算法PHUI-Growth進(jìn)行對比實(shí)驗(yàn)。

實(shí)驗(yàn)平臺：實(shí)驗(yàn)環(huán)境采用基于云計(jì)算平臺Hadoop的計(jì)算集群，共有6個(gè)節(jié)點(diǎn)（1個(gè)主控節(jié)點(diǎn)（master），5個(gè)數(shù)據(jù)節(jié)點(diǎn)（slaves））；JDK是openjdk-6-jdk，Hadoop的版本采用0.21.0版。

實(shí)驗(yàn)數(shù)據(jù)集：本實(shí)驗(yàn)的數(shù)據(jù)集都由真實(shí)數(shù)據(jù)集組成，真實(shí)數(shù)據(jù)集的特征如表5所示。其中：|D|代表的是一個(gè)數(shù)據(jù)集中事務(wù)的數(shù)目，Tavg是事務(wù)的平均長度，|I|是數(shù)據(jù)集中項(xiàng)的數(shù)目。這些數(shù)據(jù)可從FIMI（Frequent Itemset Mining Implementations repository）[15]網(wǎng)站中下載。Chain-store和Retail這兩個(gè)數(shù)據(jù)集中都已經(jīng)包括了數(shù)據(jù)的內(nèi)部效用值和外部效用值。Mushroom數(shù)據(jù)集自身不包括內(nèi)部效用值和外部效用值，本實(shí)驗(yàn)給每個(gè)項(xiàng)隨機(jī)地產(chǎn)生一個(gè)大于0小于10的整數(shù)作為內(nèi)部效用值；項(xiàng)的外部效用值也是隨機(jī)產(chǎn)生的一個(gè)大于等于0.01小于等于10的數(shù)值，并且該數(shù)值符合對數(shù)正態(tài)分布。

3.2實(shí)驗(yàn)結(jié)果的分析

3.2.1查全結(jié)果實(shí)驗(yàn)

由于PHUI-Growth算法并沒有深入研究數(shù)據(jù)集的分塊處理，因此挖掘出的高效用項(xiàng)集會丟失一些項(xiàng)集，并且隨著事務(wù)長度的增大，丟失的項(xiàng)集會增多。本實(shí)驗(yàn)在數(shù)據(jù)集Mushroom中進(jìn)行，設(shè)定事物長度為50～70，每次事物長度增加5，分別比較PUCP算法、UP-Growth算法和PHUI-Growth算法產(chǎn)生高效用項(xiàng)集的數(shù)量，結(jié)果如表6所示。可以看出，隨著事務(wù)長度的增加，UP-Growth算法和PUCP算法所查找出的項(xiàng)集數(shù)量均比PHUI算法多，并且UP-Growth算法和PUCP算法所查找出的項(xiàng)集數(shù)量相差不大。

3.2.2挖掘結(jié)果的準(zhǔn)確性實(shí)驗(yàn)

在數(shù)據(jù)集Mushroom進(jìn)行實(shí)驗(yàn)，以對比三種算法的正確率，結(jié)果如圖4所示。從圖4可以看出：隨著效用閾值的不斷減小，三個(gè)算法挖掘結(jié)果的正確率隨之降低；三個(gè)算法在同一效用閾值下，正確率基本一致，并且維持在75%左右，這說明本文提出的PUCP算法在提高效率的同時(shí)不會影響挖掘結(jié)果的準(zhǔn)確性。

3.2.3算法的運(yùn)行時(shí)間實(shí)驗(yàn)

在高效用模式挖掘算法中，算法運(yùn)行時(shí)間會隨著最小效用閾值的降低而增加，本實(shí)驗(yàn)主要測試在不同最小效用閾值時(shí)算法運(yùn)行時(shí)間的對比。

在數(shù)據(jù)集Mushroom中，實(shí)驗(yàn)假定項(xiàng)集長度為14，在相同的最小效用閾值下，三個(gè)算法在該數(shù)據(jù)集中運(yùn)行5次，取5次運(yùn)行時(shí)間的平均值，結(jié)果如圖5所示。從圖5可以看出，在越稠密的數(shù)據(jù)集中，最小效用閾值越小，挖掘過程中產(chǎn)生的候選高效用項(xiàng)集的個(gè)數(shù)會越多，從而導(dǎo)致算法的運(yùn)行時(shí)間增長。PUCP算法和PHUI-Growth算法的運(yùn)行時(shí)間明顯少于UP-Growth算法，這是由于前兩個(gè)算法使用6臺機(jī)器組成的Hadoop集群并行地進(jìn)行挖掘；并且隨著閾值的減小，UP-Growth算法的運(yùn)行時(shí)間增加得越明顯。由于采用聚類劃分的方法將相似的事務(wù)放到一個(gè)計(jì)算節(jié)點(diǎn)中，因此每個(gè)節(jié)點(diǎn)中樹結(jié)構(gòu)較小，遍歷樹的時(shí)間較短，PUCP算法整體的運(yùn)行時(shí)間要小于PHUI-Growth算法。

3.2.4算法內(nèi)存消耗實(shí)驗(yàn)

本實(shí)驗(yàn)主要測試在不同最小效用閾值時(shí)三個(gè)算法在Chain-store數(shù)據(jù)集中的內(nèi)存消耗對比。實(shí)驗(yàn)內(nèi)存消耗的提取方法如下：在算法運(yùn)行的過程中，插入多個(gè)測試點(diǎn)，在每個(gè)測試點(diǎn)中，先強(qiáng)行刪除算法運(yùn)行過程中產(chǎn)生的垃圾節(jié)點(diǎn)，再提取出當(dāng)時(shí)的內(nèi)存消耗值，并以這些值中的最大值作為當(dāng)前算法的內(nèi)存消耗值。運(yùn)行結(jié)果如圖6所示。

由圖6可以看出，隨著最小效用閾值的降低，UP-Growth算法內(nèi)存消耗越來越大，這是因?yàn)殡S著最小效用閾值的降低，效用模式樹中的節(jié)點(diǎn)增多；但PUCP算法和PHUI-Growth算法的內(nèi)存消耗基本沒有太大變化，這是因?yàn)檫@兩個(gè)算法采用并行的策略；PUCP算法采用聚類劃分方法將相似的事務(wù)建成效用模式樹，樹結(jié)構(gòu)的分支少，并且采用模式增長的方式進(jìn)行挖掘，減少了候選項(xiàng)集的數(shù)量，采用樹形結(jié)構(gòu)，不存儲非候選項(xiàng)集，因此所占內(nèi)存比PHUI-Growth算法要少。

4結(jié)語

本文在Hadoop計(jì)算平臺下，提出了基于聚類劃分的高效用模式并行挖掘算法PUCP，該算法通過計(jì)算相似度Jaccard系數(shù)，將大規(guī)模數(shù)據(jù)庫聚類劃分成若干數(shù)據(jù)子集，并將這些數(shù)據(jù)子集分配到Hadoop若干計(jì)算節(jié)點(diǎn)中實(shí)現(xiàn)并行挖掘。本文采用3個(gè)典型的真實(shí)數(shù)據(jù)集進(jìn)行驗(yàn)證，結(jié)果表明算法PUCP在時(shí)間和空間方面效率都有所提高。目前高效用模式挖掘理論研究逐漸成熟，在今后的研究工作中，將著重考慮在挖掘的過程中高效地利用Hadoop平臺系統(tǒng)的計(jì)算、存儲資源以及容錯(cuò)、優(yōu)化負(fù)載均衡等問題。

參考文獻(xiàn)：

[1]JAGRAW R， SRIKANT R. Fast algorithms for mining association rules [C]// Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco， CA： Morgan Kaufmann， 1994： 487-499.

http：//cs.stanford.edu/people/chrismre/cs345/rl/ar-mining.pdf

[2]HAN J W， KAMBER M.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，孟小峰，譯.2版.北京：機(jī)械工業(yè)出版社，2007：206-228. （HAN J W， KAMBER M. Data Mining： Concepts and Techniques [M]. FAN M， MENG X F， translated. 2nd ed. Beijing： China Machine Press， 2007： 206-228.）

[3]ZIHAYAT M， AN A. Mining top-k high utility patterns over data streams [J]. Information Sciences， 2014， 285： 138-161.

[4]YUN U， RYANG H. Incremental high utility pattern mining with static and dynamic databases [J]. Applied Intelligence， 2015， 42（2）： 323-352.

[5]YUN U， RYANG H， RYU K H. High utility itemset mining with techniques for reducing overestimated utilities and pruning candidates [J]. Expert Systems with Applications， 2014， 41（8）： 3861-3878.

[6]SONG W， LIU Y， LI J. Mining high utility itemsets by dynamically pruning the tree structure [J]. Applied Intelligence， 2014， 40（1）： 29-43.

[7]SHIE B-E， HSIAO H-F， TSENG V S. Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments [J]. Knowledge and Information Systems， 2013， 37（2）： 363-387.

[8]LEE D， PARK S-H， MOON S. Utility-based association rule mining： a marketing solution for cross-selling [J]. Expert Systems with Applications， 2013， 40（7）： 2715-2725.

[9]LIU Y， LIAO W-K， CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets [M]// PAKDD 05： Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Berlin： Springer-Verlag， 2005： 689-695.

[10]TSENG V S， WU C-W， SHIE B-E， et al. UP-Growth： an efficient algorithm for high utility itemset mining [C]// KDD 10： Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 253-262.

[11]SHIE B-E， HSIAO H-F， TSENG V S. Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments [J]. Knowledge and Information Systems， 2013， 37（2）： 363-387.

[12]LIN Y C， WU C-W， TSENG V S. Mining high utility itemsets in big data [C]// PAKDD 2015： Proceedings of the 19th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining， LNCS 9078. Berlin： Springer-Verlag， 2015： 649-661.

[13]LIU Y， LIAO W-K， CHOUDHARY A. A fast high utility itemsets mining algorithm [C]// UBDM 05： Proceedings of the 1st International Workshop on Utility-based Data Mining. New York： ACM， 2005： 90-99.

[14]JAIN A K， DUBES R C. Algorithms for clustering data [M]// Algorithms for Clustering Data. Upper Saddle River， NJ： Prentice Hall， 1988： 227-229.

[15]Frequent itemset mining implementations repository [EB/OL]. [2015-12-22]. http：//fimi.cs. Helsinki.fi.