黃 坤， 吳 玉 佳

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

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

黃 坤*1， 吳 玉 佳2

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

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

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

0 引 言

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

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

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

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

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

1 問題定義

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

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

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

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

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

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

項(xiàng)的單位利潤(rùn)見表2．

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

表2 項(xiàng)的單位利潤(rùn)

2 方法介紹

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

2.1 初始項(xiàng)集列表

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

圖1 初始項(xiàng)集列表

Fig.1 Initial itemset lists

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

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

策略1刪除初始項(xiàng)集列表中的無用項(xiàng)．

2.2 2-項(xiàng)集列表

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

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

圖2 初始2-項(xiàng)集列表

Fig.2 Initial 2-itemset lists

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

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

策略2刪除項(xiàng)集列表中的無用項(xiàng)集．

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

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

Fig.3 2-Itemset lists by applying Strategy 2

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

例如，項(xiàng)集{BC}的前綴項(xiàng)集為A，項(xiàng)集{DE}的前綴項(xiàng)集為ABC．

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

策略3刪除項(xiàng)集前綴效用．

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

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

Fig.4 2-Itemset lists by applying Strategy 3

2.3 k-項(xiàng)集列表

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

圖5 初始3-項(xiàng)集列表

Fig.5 Initial 3-itemset lists

圖6為使用策略3之后的3-項(xiàng)集列表．

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

Fig.6 3-Itemset lists by applying Strategy 3

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

2.4 本文提出的算法 MHUI

本文提出的算法MHUI，僅需掃描一次事務(wù)數(shù)據(jù)庫，在不產(chǎn)生候選項(xiàng)集的情況下，直接產(chǎn)生所有的高效用項(xiàng)集．效用項(xiàng)集挖掘算法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 實(shí) 驗(yàn)

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

3.2 運(yùn)行時(shí)間與內(nèi)存消耗

為了測(cè)試本文提出的算法MHUI的性能，對(duì)比實(shí)驗(yàn)分別采用了IHUP、HUI-Miner、UP-Growth和UP-Growth+等4個(gè)最新的算法．

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

(a) 運(yùn)行時(shí)間

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

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

Fig.7 The experimental results on database Chain-store

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

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

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

(a) 運(yùn)行時(shí)間

(a) 運(yùn)行時(shí)間

4 結(jié) 語

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61303046).

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

1000-8608(2017)05-0524-07

TP312

A

10.7511/dllgxb201705013