帶負(fù)項值的on-shelf效用項集并行挖掘算法

陳麗娟，謝伙生

(福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州 350116)

0 引 言

近年來，高效用項集挖掘已成為數(shù)據(jù)挖掘領(lǐng)域的熱門研究問題，高效用模式挖掘中每個事務(wù)中的項都有對應(yīng)的內(nèi)部效用值(如數(shù)量)，每個項都有外部效用值作為興趣度度量(如利潤)。傳統(tǒng)的高效用項集挖掘[1-4]是在外部效用值為正的情況進(jìn)行挖掘的，但現(xiàn)實生活中存在外部效用值為負(fù)的場景，如商場推出的買贈活動，贈送的商品的利潤值為負(fù)。針對此類問題，Chu等人提出了帶負(fù)項值的高效用項集挖掘算法HUINIV[5]，該算法框架為2階段算法，候選項集的數(shù)量大，挖掘時間空間消耗大。Fournier-Viger等人提出了垂直類的帶負(fù)項值的高效用項集挖掘算法FHN[6-7]，該算法定義了考慮負(fù)項值的效用列表結(jié)構(gòu)，相較于HUINIV算法，在時空效率上都有所提高。

在實際處理問題過程中，除了要考慮效用值外，往往與項的on-shelf時間段有關(guān)，例如：{外套，棉襪}這樣的商品組合，在商場的數(shù)據(jù)庫中可能不是高利潤的，而在冬季可能是高利潤的，一些商品在商場中由于季節(jié)等原因可能會頻繁地上架下架，因而在挖掘過程中考慮on-shelf時間段，更具有現(xiàn)實意義。如果不考慮時間，這些組合可能會被忽略。針對該類問題，Lan等人提出了on-shelf效用項集挖掘算法TP-Hou[8]，該算法在挖掘過程中不僅考慮了項的效用值，而且考慮了項的on-shelf時間段。Lan等人將效用值的取值范圍擴(kuò)展到負(fù)值，進(jìn)一步提出了TS-Houn算法[9]，該算法能夠有效找到所有的帶負(fù)項值的高on-shelf效用項集。但這類算法在挖掘過程中需要保存所有的候選項集以及多次數(shù)據(jù)庫掃描，時間和空間的消耗都較大。Fournier-Viger等人進(jìn)而提出FOSHU算法[10]，該算法根據(jù)效用列表的特性進(jìn)行剪枝，提高了挖掘效率，但最小on-shelf效用值過小時，算法需要構(gòu)建大量的效用列表結(jié)構(gòu)。

算法并行化是提高算法效率的一種有效途徑[11-12]，MapReduce是Google提出的一種編程框架，用于大規(guī)模數(shù)據(jù)的并行計算[13]。MapReduce框架通過對數(shù)據(jù)進(jìn)行劃分并提取出key/value鍵值對交給多個Mapper以及Reducer進(jìn)行處理，從而達(dá)到并行化處理的目的，是目前較好的分布式數(shù)據(jù)處理框架[14-15]。本文將MapReduce平臺引入帶負(fù)項值的on-shelf效用項集挖掘中，將事務(wù)數(shù)據(jù)庫根據(jù)時間段劃分成小數(shù)據(jù)庫，并行地在每個小數(shù)據(jù)庫中進(jìn)行高效用項集挖掘，提出帶負(fù)項值的on-shelf效用項集并行挖掘算法DTP-Houn。實驗結(jié)果表明DTP-Houn算法具有較好的挖掘效率。

1 相關(guān)定義與性質(zhì)

假設(shè)I={i1,i2,…,im}是由m個不同項組成的項集合，項ik(1km)的外部效用值記為p(ik)。事務(wù)數(shù)據(jù)庫D={T1,T2,…,Tn}是由n個事務(wù)組成的，D中的每個事務(wù)Tc(1cn)都是項集I的子集，唯一的標(biāo)識符(Tid)為c。給定事務(wù)Tc，對于?ik∈I其內(nèi)部效用值記為q(ik,Tc)。記P={p1,p2,…,pn}是時間段的集合，對于每個事務(wù)Tc的時間段pt(Tc)都滿足pt(Tc)∈P。數(shù)據(jù)庫D如表1所示。每個項對應(yīng)的外部效用值表以及時間段表如表2和表3所示。

表1 事務(wù)數(shù)據(jù)庫D

Tid事務(wù)時間段1(a,1)(b,2)(c,3)12(a,2)(c,1)(d,2)(e,4)13(b,1)(d,2)(e,2)(f,3)(g,1)24(c,2)(d,1)(f,1)25(a,3),(b,3)(d,1)(g,2)3

表2 外部效用值表

項abcdefg項值13251-2-1

表3 時間段表

項時間段123a101b111c110d111e110f010g011

定義4給定項集X,X的on-shelf效用值ou(X)=u(X)/to(X)，記λ為自定義閾值(0λ1)即最小on-shelf效用值。若ou(X)≥λ，則項集X為高on-shelf效用項集。

定義6給定時間段h，項集X的on-shelf效用值ou(X,h)=u(X,h)/pto(h)。

帶負(fù)項值的on-shelf效用項集挖掘的任務(wù)是找到所有的高on-shelf效用項集，其剪枝性質(zhì)如下：

性質(zhì)1給定項集X，若在任何一個時間段h都不滿足ou(X,h)≥λ，那么項集X不可能為高on-shelf效用項集。

性質(zhì)2給定項集X和時間段h，滿足TWU(X,h)/pto(h)≥ou(X,h)，這是由于TWU(X,h)≥u(X,h)總是成立的。

性質(zhì)3給定項集X和時間段h，若X不滿足TWU(X,h)/pto(h)≥λ，那么項集X不可能滿足ou(X,h)≥λ，且X的擴(kuò)展集X′也不可能滿足ou(X′,h)≥λ。

2 DTP-Houn算法

現(xiàn)有算法[8-10]提出了不少策略來提升on-shelf效用項集挖掘效率，但計算成本仍然較大。TP-Hou算法是一種基于Two-phase[16]的算法，它也是最早將on-shelf時間段引入效用挖掘中的算法，但不能處理含負(fù)項值的情況。TP-Houn算法重定義了TP-Hou算法中的TWU計算方法(見定義5)，由于TP-Houn算法為2階段算法，所以算法需要多次I/O以及數(shù)據(jù)庫掃描操作，面對數(shù)據(jù)量大的情況挖掘過程耗時較長。隨著處理數(shù)據(jù)量的增加，其處理效率難以滿足實際需求。為此，將MapReduce并行化框架也引入該問題的解決中來，充分利用其on-shelf時間段因素，將原始事務(wù)數(shù)據(jù)庫按照時間段進(jìn)行分片，將TP-Houn算法并行化，提出基于MapReduce的DTP-Houn算法，從而達(dá)到提高算法效率的目的。

DTP-Houn算法首先將原始事務(wù)數(shù)據(jù)庫按時間段劃分成n個分片數(shù)據(jù)庫(n為時間段個數(shù))，并行地在每個時間數(shù)據(jù)庫中挖掘高效用項集，算法需要一次MapReduce過程來完成項集挖掘。將原始事務(wù)數(shù)據(jù)庫分片記為D={D1,D2,…,Dn}，其中Dh(Dh∈D,1hn)是第h個時間段的分片數(shù)據(jù)庫。在分片數(shù)據(jù)庫Dh內(nèi)，記長度為k的項集集合為Ck，如，1-項集集合為C1。記長度為k的候選項集集合為Lk,Lk為Ck的子集，計算方法為Lk={itemset|TWU(itemset,h)/pto(h)≥λ∧itemset∈Ck}，為了便于算法描述，將其簡記為Lk=Calculate(Ck)。對應(yīng)地，Ck是由Lk-1中元素兩兩拼接得到的，簡記為Ck=genCandidate(Lk-1)。長度為k的高效用項集集合為Hk,Hk是Lk的子集，其計算方法為Hk={itemset|u(itemset,h)/pto(h)≥λ∧itemset∈Lk} ，同樣將其表示為Hk=genHighUtilityItem(Lk)。

在Map階段(如算法1所示)，算法首先掃描分片數(shù)據(jù)庫計算1-項集的TWU，根據(jù)TWU的向下封閉性進(jìn)行剪枝(性質(zhì)3)，生成1-候選項集。接著由1-候選項集拼接產(chǎn)生2-候選項集(行6-8)，進(jìn)而迭代產(chǎn)生k-候選項集，直至不再產(chǎn)生候選項集。最后，判斷候選項集是否為高效用項集，并將生成的高效用項集作為key，<效用值，周期效用值，時間段>作為value輸出到Reduce階段。

算法1Map函數(shù)

輸入：分片數(shù)據(jù)庫Dh，最小on-shelf效用值λ

輸出：

key為itemset,value為

1.掃描Dh，計算pto(h)以及Dh中每個項ik的u(ik,h)和TWU(ik,h)；

2.L1=Calculate(C1);

3.H1=genHighUtilityItem(L1);

4.output>(?ik∈H1);

//輸出到Reduce端

5.for(k=2;Lk-1≠Φ;k++)

6.Ck=genCandidate(Lk-1);

7.掃描Dh，計算Ck中每個itemset的u(itemset,h)與TWU(itemset,h);

8.Lk=Calculate(Ck);

9.Hk=genHighUtilityItem(Lk);

10.output>(?itemset∈Hk);

11.end for

Map階段產(chǎn)生的高效用項集為高on-shelf候選項集(性質(zhì)1)，Reduce階段需要計算候選項集的實際on-shelf效用值。在Reduce階段(如算法2所示)由于itemset為key，所以相同的itemset會被分配到同一Reducer中。算法首先循環(huán)判斷itemset的px(itemset)是否存在于Map階段傳遞的value中，若存在則可以直接從value中獲取，若不存在則需要掃描對應(yīng)時間段的分片數(shù)據(jù)庫計算得到。接著由定義4計算得到ou(itemset)，若ou(itemset)≥λ，則itemset為高on-shelf效用項集，輸出結(jié)果。

算法2Reduce函數(shù)

輸入：最小on-shelf效用值λ,

key和value與Map函數(shù)輸出一一對應(yīng)

輸出：

1.for時間段t in px(key)

2.if t?value.h

//value中是否包含時間段t

3.掃描Dt,計算u(key,t)與pto(t);

4.end if

5.u(key)+=u(key,t);

6.to(key)+=pto(t);

7.end for

8.ou(key)=u(key)/to(key);

9.if ou(key)≥λ

10.output;

11.end if

3 實驗結(jié)果

為了驗證DTP-Houn算法的有效性，將DTP-Houn算法和TP-Houn算法進(jìn)行3類不同的實驗比較。實驗平臺為由3臺VM(1個Master，2個DataNode)構(gòu)成的Hadoop集群，每臺VM的配置為2個單處理器和2.5 GB內(nèi)存，環(huán)境配置為Ubuntu 16.04.2和Hadoop 2.6.5。實驗選取chess,mushroom, T10I4D100K,accidents這4個數(shù)據(jù)集[17]，數(shù)據(jù)集的特征如表4所示。數(shù)據(jù)集中的內(nèi)部效用值在區(qū)間[1,5]內(nèi)隨機(jī)產(chǎn)生，外部效用值是以對數(shù)正態(tài)分布在[-1000,1000]內(nèi)產(chǎn)生的，時間段個數(shù)為5。

表4 數(shù)據(jù)集特征

數(shù)據(jù)集事務(wù)數(shù)項數(shù)目平均長度最長長度chess3196753636mushroom81241192323T10I4D100k10000087010.129accidents34018346833.851

3.1 最小on-shelf效用值影響實驗

算法運行時間比較如圖1所示。實驗結(jié)果表明，在4個數(shù)據(jù)集chess,mushroom,T10I4D100K,accidents中，DTP-Houn算法的挖掘時間都少于TP-Houn算法，挖掘效率相較更高，這是因為DTP-Houn算法將大的數(shù)據(jù)庫根據(jù)時間段劃分為較小的數(shù)據(jù)庫，充分利用集群的優(yōu)勢，將挖掘任務(wù)并行化運行在集群的DataNode上，使得算法運行效率提高。

(a) chess (b) mushroom

(c) T10I4D100K (d) accidents圖1 運行時間比較

3.2 DataNode個數(shù)影響實驗

圖2 不同DataNode個數(shù)下運行時間比較

在不同DataNode個數(shù)的集群下，DTP-Houn算法的運行時間比較如圖2所示。DataNode配置均為2個單處理器和2.5 GB內(nèi)存的VM。實驗使用chess,mushroom,T10I4D100K,accidents這4個數(shù)據(jù)集，分別固定最小on-shelf效用值為0.86，0.26，0.4，0.43。從實驗結(jié)果可以看出隨著DataNode個數(shù)的增加，DTP-Houn算法的運行時間逐漸減少。這是因為DTP-Houn算法的挖掘任務(wù)能夠并行運行在更多節(jié)點上，節(jié)省了每個節(jié)點的運行時間，但是節(jié)點的通信時間也會有所增加。然而，從實驗結(jié)果可以看出，DTP-Houn算法的運行效率得到提高，能夠較好地適應(yīng)MapReduce平臺。

3.3 on-shelf時間段個數(shù)影響實驗

由于帶負(fù)項值的on-shelf效用項集挖掘在挖掘中考慮了on-shelf時間段，相同最小on-shelf效用值的情況下，on-shelf時間段個數(shù)會影響高on-shelf效用項集數(shù)目。所以本文設(shè)計了不同on-shelf時間段個數(shù)對算法的影響實驗，時間段個數(shù)分別為5，25，50，DataNode個數(shù)為2。實驗選取數(shù)據(jù)量大的accidents數(shù)據(jù)集進(jìn)行實驗。不同on-shelf時間段個數(shù)下DTP_Houn算法和TP_Houn算法的運行時間比較如圖3所示，從實驗結(jié)果可以看出，不同的時間段個數(shù)下，DTP_Houn算法都比TP_Houn算法表現(xiàn)出較好的挖掘效率。

圖3 不同on-shelf時間段個數(shù)下運行時間比較

4 結(jié)束語

本文研究了帶負(fù)項值的on-shelf效用項集的并行化挖掘問題，提出了基于MapReduce的帶負(fù)項值的on-shelf效用項集挖掘算法DTP-Houn。算法根據(jù)挖掘的時間段特性對原始數(shù)據(jù)庫進(jìn)行分片，使得挖掘任務(wù)能夠并行化進(jìn)行。實驗從最小on-shelf效用值、DataNode個數(shù)和on-shelf時間段個數(shù)3個方面來驗證算法的有效性，實驗結(jié)果表明，DTP-Houn算法具有較好的挖掘效率。

參考文獻(xiàn)：

[1] Liu Junqiang, Wang Ke, Fung B C M. Mining high utility patterns in one phase without generating candidates[J]. IEEE Transactions on Knowledge and Data Engineering, 2016,28(5):1245-1257.

[2] Jin Jue, Wang Shui. Rup/Frup-growth: An efficient algorithm for mining high utility itemsets[J]. Procedia Engineering, 2017,174:895-903.

[3] Krishnamoorthy S. Pruning strategies for mining high utility itemsets[J]. Expert Systems with Applications, 2015,42(5):2371-2381.

[4] Zida S, Fournier-Viger P, Lin Chun-wei, et al. EFIM: A fast and memory efficient algorithm for high-utility itemset mining[J]. Knowledge & Information Systems, 2017,51(2):595-625.

[5] Chu C J, Tseng V S, Liang T. An efficient algorithm for mining high utility itemsets with negative item values in large databases[J]. Applied Mathematics and Computation, 2009,215(2):767-778.

[6] Fournier-Viger P. FHN: Efficient mining of high-utility itemsets with negative unit profits[C]// Proceedings of the 10th International Conference on Advanced Data Mining and Applications. 2014:16-29.

[7] Lin Chun-wei, Fournier-Viger P, Gan Wensheng. FHN: An efficient algorithm for mining high-utility itemsets with negative unit profits[J]. Knowledge-Based Systems, 2016,111:283-298.

[8] Lan Guo-cheng, Hong T P, Tseng V S. Discovery of high utility itemsets from on-shelf time periods of products[J]. Expert Systems with Applications, 2011,38(5):5851-5857.

[9] Lan Guo-cheng, Hong T P, Huang J P, et al. On-shelf utility mining with negative item values[J]. Expert Systems with Applications, 2014,41(7):3450-3459.

[10] Fournier-Viger P, Zida S. FOSHU: Faster on-shelf high utility itemset mining with or without negative unit profit[C]// Proceedings of the 30th Annual ACM Symposium on Applied Computing. 2015:857-864.

[11] 李偉衛(wèi),趙航,張陽,等. 基于MapReduce的海量數(shù)據(jù)挖掘技術(shù)研究[J]. 計算機(jī)工程與應(yīng)用, 2013,49(20):112-117.

[12] Al-Hamodi A A G, Lu Song-feng. MapReduce frequent itemsets for mining association rules[C]// Proceedings of the 2016 International Conference on Information System and Artificial Intelligence. 2016:281-284.

[13] 董新華,李瑞軒,周灣灣,等. Hadoop系統(tǒng)性能優(yōu)化與功能增強綜述[J]. 計算機(jī)研究與發(fā)展, 2013,50(S2):1-15.

[14] 杜江,張錚,張杰鑫,等. MapReduce并行編程模型研究綜述[J]. 計算機(jī)科學(xué), 2015,42(S1):537-541.

[15] 宋杰,孫宗哲,毛克明,等. MapReduce大數(shù)據(jù)處理平臺與算法研究進(jìn)展[J]. 軟件學(xué)報, 2017,28(3):514-543.

[16] Liu Ying, Liao Wei-keng, Choudhary A N. A two-phase algorithm for fast discovery of high utility itemsets[C]// Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. 2005:689-695.

[17] Fournier-Viger P, Gomariz A, Lam H, et al. SPMF: Open-source Data Mining Platform[EB/OL]. http://www.philippe-fournier-viger.com/spmf, 2017-09-20.