一種垂直結構的高效用項集挖掘算法

黃 坤， 吳 玉 佳

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

一種垂直結構的高效用項集挖掘算法

黃 坤*1， 吳 玉 佳2

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

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

數據挖掘；關聯分析；頻繁項集;高效用項集

0 引 言

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

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

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

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

HUI-Miner算法產生高效用項集可以分為兩個步驟：首先，將數據信息存儲到效用列表上；然后再從效用列表上計算得到高效用項集．而HUI-Miner產生的效用列表數量較多，消耗了存儲空間并影響算法運行性能．此外，由于該算法在效用列表中不僅存儲了項集的事務和效用信息，也存儲了用于對搜索空間進行剪枝的額外的剩余效用信息，這也降低了挖掘性能并占用了更多的內存資源．針對上述問題，本文提出一個新的數據結構和一個挖掘算法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-項集．一個事務數據庫D={T1,T2,…,Tn}，包含一組事務．其中，每一個事務Td(1≤d≤n)都是I的一個子集，具有一個唯一的標識符Td．每個事務Td中的一個項ip具有一個數量q(ip,Td)．

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

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

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

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

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

項的單位利潤見表2．

表1 事務數據庫示例

表2 項的單位利潤

2 方法介紹

在這部分，詳細介紹提出的數據結構和算法．掃描一次事務數據庫，并應用3種剪枝策略，產生存儲所有事務和項的效用信息的項集列表．最后，掃描所有的項集列表，產生高效用項集．

2.1 初始項集列表

首先，掃描如表1所示的事務數據庫一次，產生初始項集列表，如圖1所示．初始項集列表中存儲每個項所在的事務以及對應的效用．例如，項A在事務T1、T2、T6、T8中出現，對應的效用分別為8、16、16、8．

圖1 初始項集列表

Fig.1 Initial itemset lists

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

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

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

2.2 2-項集列表

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

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

圖2 初始2-項集列表

Fig.2 Initial 2-itemset lists

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

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

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

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

圖3 應用策略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中的事務效用TU值來計算項集列表{DE}的TWU值，則TWU({DE})=46．此時項集列表{DE}不能刪除，需要保留．如果利用定義9刪除前綴項集的效用，則項集{DE}的TWU值的計算方法為TWU({DE}) = 25，它的值小于minutl，根據性質2，項集{DE}及它的超集都不是高效用項集，將項集列表{DE}從2-項集列表中刪除，進一步減少項集列表的數量．

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

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

圖4 應用策略3后的2-項集列表

Fig.4 2-Itemset lists by applying Strategy 3

2.3 k-項集列表

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

圖5 初始3-項集列表

Fig.5 Initial 3-itemset lists

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

圖6 應用策略3后的3-項集列表

Fig.6 3-Itemset lists by applying Strategy 3

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

2.4 本文提出的算法 MHUI

本文提出的算法MHUI，僅需掃描一次事務數據庫，在不產生候選項集的情況下，直接產生所有的高效用項集．效用項集挖掘算法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 實 驗

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

3.1 實驗數據集

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

表3 數據集的特點

3.2 運行時間與內存消耗

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

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

(a) 運行時間

(b) 內存消耗

圖7 數據集Chain-store上的實驗結果

Fig.7 The experimental results on database Chain-store

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

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

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

(a) 運行時間

(a) 運行時間

4 結 語

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

[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．

國家自然科學基金資助項目(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