一種垂直結(jié)構(gòu)的高效用項集挖掘算法

黃 坤， 吳 玉 佳

( 1.中國艦船研究設(shè)計中心， 湖北 武漢 430064；2.武漢大學(xué) 計算機(jī)學(xué)院， 湖北 武漢 430072 )

一種垂直結(jié)構(gòu)的高效用項集挖掘算法

黃 坤*1， 吳 玉 佳2

( 1.中國艦船研究設(shè)計中心， 湖北 武漢 430064；2.武漢大學(xué) 計算機(jī)學(xué)院， 湖北 武漢 430072 )

挖掘高效用項集已成為關(guān)聯(lián)分析中的熱點問題之一．多數(shù)高效用項集挖掘算法需要產(chǎn)生大量的候選項集，影響了算法性能．HUI-Miner是一個不需要產(chǎn)生候選項集就能發(fā)現(xiàn)事務(wù)數(shù)據(jù)庫中所有高效用項集的算法．但其需要產(chǎn)生大量效用列表，不僅消耗了過多的存儲空間，而且影響了算法的運行性能．針對此問題，提出一個新的數(shù)據(jù)結(jié)構(gòu)，稱為項集列表，用于存儲事務(wù)和項的效用信息．提出3種剪枝策略，減少項集列表的數(shù)量，通過掃描一次事務(wù)數(shù)據(jù)庫完成所有項集列表的構(gòu)建．提出算法MHUI，直接從項集列表中挖掘所有的高效用項集而不產(chǎn)生任何候選項集．在3個不同的稀疏數(shù)據(jù)集上和最新的算法進(jìn)行對比實驗證明，MHUI算法的運行時間和內(nèi)存消耗優(yōu)于其他算法．

數(shù)據(jù)挖掘；關(guān)聯(lián)分析；頻繁項集;高效用項集

0 引 言

數(shù)據(jù)挖掘中的一個重要任務(wù)是關(guān)聯(lián)分析．關(guān)聯(lián)分析的應(yīng)用非常廣泛，它一般分為兩個步驟：第一，從數(shù)據(jù)庫中挖掘頻繁項集；第二，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則．第二個步驟通常較為簡單，所以，大多數(shù)學(xué)者都將研究重點放在第一個步驟上面[1-3]．在頻繁項集挖掘算法中，Agrawal等[1]提出的Apriori算法是此領(lǐng)域的開創(chuàng)性算法，其特點是簡單、易實現(xiàn)，不足之處是需要多次掃描數(shù)據(jù)庫，這影響了算法的性能．Han等[2]在隨后提出了FP-Growth算法用于挖掘頻繁項集，這是一種基于樹結(jié)構(gòu)的算法．FP-Growth算法通過掃描數(shù)據(jù)庫將所有的信息存儲到一個FP-Tree上，它的性能大大超過了Apriori，因為它尋找頻繁項集時不需要產(chǎn)生任何候選項集．Zaki[3]提出一種基于垂直數(shù)據(jù)結(jié)構(gòu)的頻繁項集挖掘算法Eclat，將事務(wù)信息存儲到列表上，通過對列表的交集運算，能非常快實現(xiàn)對支持度計數(shù)以及產(chǎn)生頻繁項集．

然而，在這些頻繁項集挖掘的框架中，沒有考慮項在事務(wù)中的數(shù)量以及項的重要性(如單位利潤、價格、重要性等)．在實際應(yīng)用中，利益最大化對于銷售經(jīng)理來說是一個非常有吸引力的問題．因此，挖掘高效用項集迅速成為數(shù)據(jù)挖掘領(lǐng)域中的一個研究熱點問題．但是，在頻繁項集挖掘中，多數(shù)算法使用了向下閉性質(zhì)[1-3]，即如果一個項集是非頻繁的，則它的超集都是非頻繁的．利用此性質(zhì)能大大減少計算量并降低內(nèi)存消耗．但是這個性質(zhì)在高效用項集挖掘中卻不能直接使用．因此，這個問題給高效用項集挖掘帶來了一個巨大挑戰(zhàn)．

鑒于此，一些算法使用估計效用上界的方法來對搜索空間進(jìn)行剪枝，以提高效用項集挖掘的性能．Liu等[4]提出Two-Phase算法，算法通過兩個階段來確定高效用項集．Yao等[5]提出了UMining算法，使用一種估計方法來減少搜索空間．Li等[6]提出一個孤立項丟棄策略，用于減少候選項集的數(shù)量．雖然所有的高效用項集都能夠被發(fā)現(xiàn)，但這些方法經(jīng)常會產(chǎn)生大量的候選項集[4-11]，并且需要多次掃描數(shù)據(jù)庫．

Ahmed等[7]提出一個基于樹結(jié)構(gòu)的算法IHUP用于挖掘高效用項集，獲得了比IIDS和Two-Phase更好的性能．Tseng等提出了UP-Growth 算法[8]和UP-Growth+算法[9]，減少候選項集的數(shù)量，從而提高算法的性能．此外，Wu等[10]和Tseng等[11]也提出了先挖掘閉項集的方式來挖掘完全高效用項集，取得了較好的效果．Liu等[12]提出一種全新的用于挖掘高效用項集的算法HUI-Miner．HUI-Miner不需要產(chǎn)生候選項集，而是直接產(chǎn)生高效用項集．首先產(chǎn)生一系列稱為效用列表的數(shù)據(jù)結(jié)構(gòu)，用于存儲項集的事務(wù)信息、項的效用信息以及高估效用信息(剩余效用)．通過掃描效用列表的方式生成所有的高效用項集，而這一過程不需要產(chǎn)生任何候選項集，HUI-Miner算法在運行時間和內(nèi)存消耗上都優(yōu)于上述算法．

HUI-Miner算法產(chǎn)生高效用項集可以分為兩個步驟：首先，將數(shù)據(jù)信息存儲到效用列表上；然后再從效用列表上計算得到高效用項集．而HUI-Miner產(chǎn)生的效用列表數(shù)量較多，消耗了存儲空間并影響算法運行性能．此外，由于該算法在效用列表中不僅存儲了項集的事務(wù)和效用信息，也存儲了用于對搜索空間進(jìn)行剪枝的額外的剩余效用信息，這也降低了挖掘性能并占用了更多的內(nèi)存資源．針對上述問題，本文提出一個新的數(shù)據(jù)結(jié)構(gòu)和一個挖掘算法MHUI，以有效地挖掘高效用項集．

1 問題定義

給定一個有限的一組項I={i1,i2,…,im}，其中每個項ip(1≤p≤m)都有一個利潤值p(ip)．一個項集X由k個項{i1,i2,…,ik}組成，ij∈I,1≤j≤k，k是項集X的長度．長度為k的項集稱為k-項集．一個事務(wù)數(shù)據(jù)庫D={T1,T2,…,Tn}，包含一組事務(wù)．其中，每一個事務(wù)Td(1≤d≤n)都是I的一個子集，具有一個唯一的標(biāo)識符Td．每個事務(wù)Td中的一個項ip具有一個數(shù)量q(ip,Td)．

定義1項ip在事務(wù)Td中的效用u(ip,Td)，定義為u(ip,Td)=p(ip)×q(ip,Td)．

定義4給定項集X及用戶指定最小效用閾值minutl，若u(X)≥minutl，則稱X為高效用項集．

定義5事務(wù)Td的事務(wù)效用記為TU(Td)，定義為u(Td,Td)．

性質(zhì)1事務(wù)加權(quán)向下閉性質(zhì)[4]，縮寫為TWDC．規(guī)定如下：對于任何一個項集X，如果TWU(X)

例如：在表1中，TWU({AB})=TU(T6)=28．設(shè)minutl=30，則{AB}和它的超集都不是高效用項集，因為TWU({AB})

項的單位利潤見表2．

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

表2 項的單位利潤

2 方法介紹

在這部分，詳細(xì)介紹提出的數(shù)據(jù)結(jié)構(gòu)和算法．掃描一次事務(wù)數(shù)據(jù)庫，并應(yīng)用3種剪枝策略，產(chǎn)生存儲所有事務(wù)和項的效用信息的項集列表．最后，掃描所有的項集列表，產(chǎn)生高效用項集．

2.1 初始項集列表

首先，掃描如表1所示的事務(wù)數(shù)據(jù)庫一次，產(chǎn)生初始項集列表，如圖1所示．初始項集列表中存儲每個項所在的事務(wù)以及對應(yīng)的效用．例如，項A在事務(wù)T1、T2、T6、T8中出現(xiàn)，對應(yīng)的效用分別為8、16、16、8．

圖1 初始項集列表

Fig.1 Initial itemset lists

在圖1中，初始項集列表{F}的加權(quán)事務(wù)效用之和為TWU({F})=TU(T3)+TU(T7)=24．根據(jù)性質(zhì)1，項F和它的超集都不是高效用項集，因為TWU({F})

定義7(有用項和無用項) 給定一個項ip，如果TWU(ip)≥minutl，則稱其為有用項；否則，稱其為無用項．

策略1刪除初始項集列表中的無用項．

2.2 2-項集列表

在產(chǎn)生初始項集列表之后，通過對初始項集列表進(jìn)行交集運算，生成2-項集列表．例如項A和項B的共同事務(wù)為6，對應(yīng)的效用分別為16和4，所以項集{AB}的事務(wù)為6，效用為20，2-項集列表如圖2所示．

性質(zhì)2項集列表事務(wù)加權(quán)向下閉性質(zhì)，縮寫為ITWDC．規(guī)定如下：對于任何一個項集列表X，如果項集列表X的加權(quán)事務(wù)效用之和小于minutl，則項集X及其超集都不是高效用項集．

圖2 初始2-項集列表

Fig.2 Initial 2-itemset lists

項集列表{AD}的結(jié)果為空集，它的超集都為空集，可以直接從2-項集列表中刪除．計算每個2-項集列表的加權(quán)事務(wù)效用．其中，TWU({AB})=24，TWU({BG})=13，TWU({DG})=19．它們可以從2-項集列表中刪除，根據(jù)性質(zhì)2，項集{AB}、{BG}和{DG}的超集也不是高效用項集，都稱為無用項集．

定義8(有用項集和無用項集) 給定一個項集X，如果TWU(X)≥minutl，則稱其為有用項集；否則，稱其為無用項集．

策略2刪除項集列表中的無用項集．

圖3所示為應(yīng)用策略2之后的2-項集列表，2-項集列表的數(shù)量從最初的15個減少到11個．

圖3 應(yīng)用策略2后的2-項集列表

Fig.3 2-Itemset lists by applying Strategy 2

定義9(前綴項集) 給定一個項集X，由k個項{is,is+1,…,is+k-1}組成，所有的項按順序排列．項is即為項集X的前綴，排在項is前的項集稱為項集X的前綴項集．

例如，項集{BC}的前綴項集為A，項集{DE}的前綴項集為ABC．

觀察圖3中的項集列表{DE}，如果直接使用表1中的事務(wù)效用TU值來計算項集列表{DE}的TWU值，則TWU({DE})=46．此時項集列表{DE}不能刪除，需要保留．如果利用定義9刪除前綴項集的效用，則項集{DE}的TWU值的計算方法為TWU({DE}) = 25，它的值小于minutl，根據(jù)性質(zhì)2，項集{DE}及它的超集都不是高效用項集，將項集列表{DE}從2-項集列表中刪除，進(jìn)一步減少項集列表的數(shù)量．

策略3刪除項集前綴效用．

圖4所示為使用策略3之后的2-項集列表，2-項集列表的數(shù)量進(jìn)一步從11個減少到10個．

圖4 應(yīng)用策略3后的2-項集列表

Fig.4 2-Itemset lists by applying Strategy 3

2.3 k-項集列表

為了構(gòu)建k-項集列表，可以根據(jù)k-1項集列表進(jìn)行事務(wù)交集運算構(gòu)建．例如根據(jù)圖4所示的2-項集列表，進(jìn)行事務(wù)交集運算，生成3-項集列表，如圖5所示．在產(chǎn)生k-項集列表(k>2)時，需要減去重復(fù)效用值，文獻(xiàn)[12]有詳細(xì)說明．

圖5 初始3-項集列表

Fig.5 Initial 3-itemset lists

圖6為使用策略3之后的3-項集列表．

圖6 應(yīng)用策略3后的3-項集列表

Fig.6 3-Itemset lists by applying Strategy 3

至此，文章已介紹如何構(gòu)建項集列表以及3種剪枝策略的原理．接下來，介紹如何從項集列表中直接生成所有的高效用項集挖掘算法MHUI．

2.4 本文提出的算法 MHUI

本文提出的算法MHUI，僅需掃描一次事務(wù)數(shù)據(jù)庫，在不產(chǎn)生候選項集的情況下，直接產(chǎn)生所有的高效用項集．效用項集挖掘算法MHUI表述如下．Algorithm: MHUI

Input: DB: the transaction database;minutl: the minimum utility threshold.

Output: all the HUIs.

Step1: Produce the initialILsthrough scanning the DB. Calculate the initial transaction utilitytu. Output the HUIs of 1-itemset.

Step2: Delete the unpromise item from the initialILsand updatetu.

1.flag=0;

2. repeat

3.flag=IL.size();

4.twu(ip)=TWU(IL,tu);

5. if (twu(ip))

6. deleteipfromIL;

7. end

8.tu=TU(IL);

9. untilIL.size()

10. Output the HUIs ifu(X)≥minutl

Step3:ILsof 2-itemsets are generated by initialILs. Delete the unpromise itemset from theILs. Output the HUIs of 2-itemsets.

11.ILk=List(IL);

12. if (twu(X))

13. deleteXfromILk;

14. end

15. Output the HUIs ifu(X)≥minutl

Step4:ILsofk-itemsets obtained byILsof (k-1)-itemsets

16. repeat

17.k=k+1;

18.ILk=List(ILk-1);

19. Output the HUIs ifu(X)≥minutl

20. untilILk.size()=0

3 實 驗

為評估提出的算法的性能，將其同最新的算法進(jìn)行對比．實驗使用的計算機(jī)：3.3 GHz Intel i5-4590處理器；8 GB內(nèi)存，Windows 7操作系統(tǒng)；算法用Java語言實現(xiàn)．

3.1 實驗數(shù)據(jù)集

實驗數(shù)據(jù)集Chain-store[13]是一個真實數(shù)據(jù)集，采集于一家超市的銷售數(shù)據(jù)．Chain-store數(shù)據(jù)集提供了項在事務(wù)中的數(shù)量和單位利潤，可直接使用．?dāng)?shù)據(jù)集retail和T10I4D100K來自FIMI網(wǎng)站[14]．3個數(shù)據(jù)集的特點如表3所示．

表3 數(shù)據(jù)集的特點

3.2 運行時間與內(nèi)存消耗

為了測試本文提出的算法MHUI的性能，對比實驗分別采用了IHUP、HUI-Miner、UP-Growth和UP-Growth+等4個最新的算法．

圖7是Chain-store數(shù)據(jù)集的實驗結(jié)果，顯示在不同的最小閾值的情況下，5種算法的運行時間和內(nèi)存消耗情況．圖7(a)顯示的是運行時間，從圖中可以看到，MHUI算法比HUI-Miner算法要快1倍左右，主要原因是，本文提出的剪枝策略，使得參與計算的項集列表數(shù)量減少．圖7(b) 顯示的是內(nèi)存消耗，可以看到，MHUI和HUI-Miner比UP-Growth+消耗的內(nèi)存要少．主要原因是，Chain-store數(shù)據(jù)集所包含的項較多，達(dá)到46 086個，導(dǎo)致UP-Growth+構(gòu)建的UP-Tree規(guī)則較大，并且產(chǎn)生數(shù)量巨大的候選項集，消耗了大量的內(nèi)存．

(a) 運行時間

(b) 內(nèi)存消耗

圖7 數(shù)據(jù)集Chain-store上的實驗結(jié)果

Fig.7 The experimental results on database Chain-store

圖8顯示了在retail數(shù)據(jù)集上，5種算法在運行時間和內(nèi)存消耗上的差異．MHUI比HUI-Miner、IHUP、UP-Growth和UP-Growth+等4個算法在內(nèi)存消耗上優(yōu)勢明顯，運行速度一般也要快1倍以上．

圖9顯示在T10I4D100K數(shù)據(jù)集上，5種算法在運行時間和內(nèi)存消耗上的差異．算法MHUI在運行時間上和內(nèi)存消耗上的表現(xiàn)都比另外4種算法更好．其中，在運行時間上，MHUI比HUI-Miner要快60%以上，比UP-Growth和UP-Growth+要快2倍以上．

實驗結(jié)果顯示，在不同的數(shù)據(jù)集上，本文提出的算法在性能上好于最新算法．主要的原因如下：第一，提出的算法不產(chǎn)生候選項集；第二，提出的項集列表不存儲冗余信息，僅存儲事務(wù)和項的效用信息，占用空間少；第三，提出3種剪枝策略，減少了項集列表的數(shù)量，從而減少了算法的運行時間和內(nèi)存消耗．

(a) 運行時間

(a) 運行時間

4 結(jié) 語

本文提出了一個新的數(shù)據(jù)結(jié)構(gòu)——項集列表．僅需掃描一次數(shù)據(jù)庫，就能完成項集列表的構(gòu)建．并提出3種用于對項集列表進(jìn)行剪枝的策略，應(yīng)用這3種剪枝策略能減少項集列表的數(shù)量，減少算法的執(zhí)行時間，也能降低內(nèi)存的消耗．最后，提出一個算法MHUI，通過掃描項集列表，直接生成完全高效用項集，在這個過程中，不需要產(chǎn)生候選項集．該算法運行速度快，且減少內(nèi)存消耗，性能較好．

[1] AGRAWAL R, SRIKANT R. Fast algorithms for milling association rules in large databases [C] //Proceedingsofthe20thVLDBConference. Santiago: Morgan Kaufmann Publishers Inc., 1994:487-499.

[2] HAN Jiawei, PEI Jian, YIN Yiwen. Mining frequent patterns without candidate generation [C] //ProceedingsoftheACMSIGMODInternationalConferenceonManagementofData. Dallas: ACM, 2000:1-12.

[3] ZAKI M J. Scalable algorithms for association mining [J].IEEETransactionsonKnowledgeandDataEngineering, 2000,12(3):372-390.

[4] LIU Y, LIAO W, CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets [C] //Proceedingsofthe9thPacific-AsiaConferenceonKnowledgeDiscoveryandDataMining. Vietnam:Springer, 2005:689-695.

[5] YAO Hong, HAMILTON H J. Mining itemset utilities from transaction databases [J].Data&KnowledgeEngineering, 2006,59(3, SI):603-626.

[6] LI Y C, YEH J S, CHANG C C. Isolated items discarding strategy for discovering high utility itemsets [J].Data&KnowledgeEngineering, 2008,64(1):198-217.

[7] AHMED C F, TANBEER S K, JEONG B S,etal. Efficient tree structures for high utility pattern mining in incremental databases [J].IEEETransactionsonKnowledgeandDataEngineering, 2009,21(12):1708-1721.

[8] TSENG V S, WU Chengwei, SHIE Baien,etal. UP-Growth: an efficient algorithm for high utility itemset mining [C] //ProceedingsoftheACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining. Washington D C: ACM, 2010:253-262.

[9] TSENG V S, SHIE Baien, WU Chengwei,etal. Efficient algorithms for mining high utility itemsets from transactional databases [J].IEEETransactionsonKnowledgeandDataEngineering, 2013,25(8):1772-1786.

[10] WU Chengwei, FOURNIER-VIGER P, YU P S,etal. Efficient mining of a concise and lossless representation of high utility itemsets [C] //Proceedings-IEEEInternationalConferenceonDataMining,ICDM. Vancouver: IEEE, 2011:824-833.

[11] TSENG V S, WU Chengwei, FOURNIER-VIGER P,etal. Efficient algorithms for mining the concise and lossless representation of high utility itemsets [J].IEEETransactionsonKnowledgeandDataEngineering, 2015,27(3):726-739.

[12] LIU Mengchi, QU Junfeng. Mining high utility itemsets without candidate generation [C] //CIKM2012-Proceedingsofthe21stACMInternationalConferenceonInformationandKnowledgeManagement. Maui :ACM, 2012:55-64.

[13] PISHARATH J, LIU Y, PARHI J,etal. NU-MineBench Version 3.0.1 [DB/OL]. [2016-06-30]. http://cucis.ece.northwestern.edu/projects/DMS/MineBench.html

[14] GOETHALS B, ZAKI M J. Frequent itemset mining implementations repository [DB/OL]. [2016-06-30]. http://fimi.ua.ac.be/

Analgorithmofmininghighutilityitemsetswithverticalstructures

HUANG Kun*1, WU Yujia2

( 1.China Ship Development and Design Center, Wuhan 430064, China； 2.School of Computer, Wuhan University, Wuhan 430072, China )

Mining high utility itemsets (HUIs) is one of popular tasks in field of association analysis. Most of HUIs mining algorithms need to generate a lot of candidate itemsets (CIs) which will affect the performance of algorithm. HUI-Miner can mine all the HUIs from a transaction database without generating CIs. However, this algorithm generates a large number of utility lists (ULs) and so many ULs not only consume too much storage space but also affect the operation performance. To solve this problem, itemsets lists (ILs), new data structures are proposed to maintain information of transaction and item utility. Three pruning strategies are proposed to reduce the number of ILs and can build the ILs just scanning the transaction database only once. A new algorithm namely MHUI is proposed which mines all the HUIs directly from the ILs without generating any CIs. The experimental results show that the proposed method outperforms the state-of-the-art algorithms in terms of runtime and memory consumption on three different sparse datasets.

data mining; association analysis; frequent itemsets; high utility itemsets

2016-11-14；

2017-07-23．

國家自然科學(xué)基金資助項目(61303046).

黃 坤*(1979-)，男，高級工程師，E-mail:hkcfan@163.com；吳玉佳(1986-)，男，博士生，E-mail:wuyujia@whu.edu.cn.

1000-8608(2017)05-0524-07

TP312

A

10.7511/dllgxb201705013