陳麗娟，謝伙生

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

0 引 言

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

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

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

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

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

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

Tid事務(wù)時(shí)間段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 外部效用值表

項(xiàng)abcdefg項(xiàng)值13251-2-1

表3 時(shí)間段表

項(xiàng)時(shí)間段123a101b111c110d111e110f010g011

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

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

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

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

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

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

2 DTP-Houn算法

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

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

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

算法1Map函數(shù)

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

輸出：

key為itemset,value為

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

算法2Reduce函數(shù)

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

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

輸出：

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

2.if t?value.h

//value中是否包含時(shí)間段t

3.掃描Dt,計(jì)算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 實(shí)驗(yàn)結(jié)果

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

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

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

3.1 最小on-shelf效用值影響實(shí)驗(yàn)

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

(a) chess (b) mushroom

(c) T10I4D100K (d) accidents圖1 運(yùn)行時(shí)間比較

3.2 DataNode個(gè)數(shù)影響實(shí)驗(yàn)

圖2 不同DataNode個(gè)數(shù)下運(yùn)行時(shí)間比較

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

3.3 on-shelf時(shí)間段個(gè)數(shù)影響實(shí)驗(yàn)

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

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

4 結(jié)束語(yǔ)

本文研究了帶負(fù)項(xiàng)值的on-shelf效用項(xiàng)集的并行化挖掘問題，提出了基于MapReduce的帶負(fù)項(xiàng)值的on-shelf效用項(xiàng)集挖掘算法DTP-Houn。算法根據(jù)挖掘的時(shí)間段特性對(duì)原始數(shù)據(jù)庫(kù)進(jìn)行分片，使得挖掘任務(wù)能夠并行化進(jìn)行。實(shí)驗(yàn)從最小on-shelf效用值、DataNode個(gè)數(shù)和on-shelf時(shí)間段個(gè)數(shù)3個(gè)方面來驗(yàn)證算法的有效性，實(shí)驗(yàn)結(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),趙航,張陽(yáng),等. 基于MapReduce的海量數(shù)據(jù)挖掘技術(shù)研究[J]. 計(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)化與功能增強(qiáng)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2013,50(S2):1-15.

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

[15] 宋杰,孫宗哲,毛克明,等. MapReduce大數(shù)據(jù)處理平臺(tái)與算法研究進(jìn)展[J]. 軟件學(xué)報(bào), 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.