垂直模式類高效用模式挖掘的改進(jìn)算法*

黃劍雄，謝伙生

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

垂直模式類高效用模式挖掘的改進(jìn)算法*

黃劍雄，謝伙生

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

由于高效用模式挖掘較為復(fù)雜，提高其挖掘算法的效率是數(shù)據(jù)挖掘的研究熱點(diǎn)。HUP-miner算法是典型的基于垂直模式類的高效用模式挖掘算法，雖然能夠有效地減少效用列表的總個(gè)數(shù)，但對(duì)于項(xiàng)集的劃分，效用列表需要更多的空間。針對(duì)該問(wèn)題，在HUI-miner算法的基礎(chǔ)上充分考慮了1-擴(kuò)展集中項(xiàng)集的關(guān)聯(lián)性，減少了效用列表個(gè)數(shù)，提出了改進(jìn)的IHUI-miner算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法IHUI-miner在時(shí)間效率和減少效用列表的個(gè)數(shù)上都優(yōu)于HUP-miner與HUI-miner算法。

高效用模式；頻繁模式；頻繁項(xiàng)集；垂直模式

0 引言

近年來(lái)，高效用模式挖掘是頻繁模式挖掘研究的熱點(diǎn)之一。與傳統(tǒng)的頻繁模式相比，高效用模式挖掘中每條事務(wù)的項(xiàng)都有對(duì)應(yīng)的值(如數(shù)量)，同時(shí)項(xiàng)集的每個(gè)項(xiàng)也有對(duì)應(yīng)的值(如利潤(rùn))，其目標(biāo)就是尋找所有效用值大于或等于最小效用值的項(xiàng)集。傳統(tǒng)頻繁模式挖掘是利用向下閉合的性質(zhì)來(lái)減少挖掘過(guò)程中的空間搜索時(shí)間，而高效用模式挖掘是利用事務(wù)權(quán)重效用值TWU(Transaction-WeightedUtility)性質(zhì)[1]來(lái)減少搜索時(shí)間。

高效用模式挖掘算法主要有模式增長(zhǎng)類與垂直模式類算法。TWO-Phase算法[1]是最早運(yùn)用模式增長(zhǎng)方式來(lái)實(shí)現(xiàn)高效用模式挖掘的，需要花費(fèi)大量的時(shí)間和空間來(lái)產(chǎn)生候選集和計(jì)算實(shí)際效用值。大多數(shù)的高效用事務(wù)數(shù)據(jù)集只能有損地存儲(chǔ)在樹(shù)結(jié)構(gòu)中，這也是模式增長(zhǎng)類算法IHUP[2]、UP-Growth[3]和UP-Growh+[3]的改進(jìn)目標(biāo)，是減少候選集產(chǎn)生的關(guān)鍵所在，文獻(xiàn)[4]提出了垂直模式類高效用模式挖掘的HUI-miner算法，該算法與Eclat算法類似，能直接計(jì)算項(xiàng)集的實(shí)際效用值，每個(gè)項(xiàng)集擁有一個(gè)效用列表UL(UtilityList)，用來(lái)構(gòu)造其他項(xiàng)集的效用列表和計(jì)算實(shí)際效用值，并利用TWU性質(zhì)來(lái)剪枝。HUI-miner算法優(yōu)于模式增長(zhǎng)類的IUPTWU算法、UP-Growh+算法。文獻(xiàn)[5]提出了垂直模式類的HUP-miner算法，該算法提出了劃分效用列表PUL(PartitionedUtilityList)，每個(gè)PUL由項(xiàng)集的效用列表UL和劃分列表PL(PartitionList)組成，一方面利用PU-Prune性質(zhì)[5]和劃分列表來(lái)預(yù)判斷是否需要構(gòu)造項(xiàng)集的效用列表，另一方面在構(gòu)造PUL過(guò)程中，利用LA-Prune性質(zhì)[5]來(lái)及時(shí)判斷返回而不是等到構(gòu)造完成后再返回，以此來(lái)減少效用列表的數(shù)目，提高算法效率。盡管如此，HUP-miner算法還是存在一些值得改進(jìn)的地方，具體體現(xiàn)在：(1)在利用PU-Prune性質(zhì)和劃分列表進(jìn)行預(yù)判斷時(shí)，若最小效用值較小或數(shù)據(jù)集較密集，則可能會(huì)存在過(guò)多的冗余計(jì)算和內(nèi)存消耗。(2)在利用LA-Prune性質(zhì)來(lái)減少項(xiàng)集效用列表的構(gòu)造過(guò)程中，忽略了同一項(xiàng)集的1-擴(kuò)展集中項(xiàng)集之間的關(guān)聯(lián)性。針對(duì)這些不足，本文提出了一個(gè)改進(jìn)的高效用模式挖掘的改進(jìn)算法IHUI-miner(ImprovedHighUtilityItemsets)，該算法仍沿用HUI-miner中的效用列表來(lái)存儲(chǔ)數(shù)據(jù)集，以更新保留項(xiàng)集的效用列表剩余效用值，同時(shí)對(duì)HUP-miner中LA-Pruning策略進(jìn)行擴(kuò)展。實(shí)驗(yàn)結(jié)果表明，IHUI-miner算法在時(shí)間效率和減少列表的個(gè)數(shù)上都優(yōu)于HUP-miner與HUI-miner算法。

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

假設(shè)I={i1,i2,…,im}是由m個(gè)不同項(xiàng)組成的項(xiàng)集合，每項(xiàng)ik(1≤k≤m)都有一個(gè)稱為外效用的值，記為EU(ik)。D={T1,T2,…,Tn}是長(zhǎng)度為n的事務(wù)數(shù)據(jù)集，D中的每個(gè)事務(wù)Tb(1≤b≤n)都是項(xiàng)集I的子集，都有一個(gè)唯一的標(biāo)識(shí)符(TID)b。事務(wù)Tb中的每個(gè)項(xiàng)ic都有一個(gè)稱為內(nèi)效用的值，記為IU(ic,Tb)。若項(xiàng)集P是一個(gè)長(zhǎng)度為L(zhǎng)的項(xiàng)集，稱P為L(zhǎng)-項(xiàng)集；Pik(ik∈I)以P為前綴，長(zhǎng)度為L(zhǎng)+1的項(xiàng)集，稱Pik為P的1-擴(kuò)展項(xiàng)集。

定義1 項(xiàng)ik在事務(wù)Tb中的效用值記為U(ik,Tb)，其定義如下：

U(ik,Tb)=EU(ik)*IU(ik,Tb)

定義2 項(xiàng)集X在事務(wù)Tb中的效用值記為U(X,Tb)，其定義如下：

U(X,Tb)=∑ik∈X,X?TbU(ik,Tb)

定義3 項(xiàng)集X在D中的效用值記為U(X)，其定義如下：

U(X)=∑X?Tb,Tb∈DU(X,Tb)

定義4 一個(gè)事務(wù)Tb的效用值指的是事務(wù)Tb中所有項(xiàng)的效用值之和，記為TU(Tb)，其定義如下：

TU(Tb)=∑ik∈TbU(ik,Tb)

定義5 項(xiàng)集X在數(shù)據(jù)集D中的事務(wù)權(quán)重效用值TWU指的是事務(wù)數(shù)據(jù)集D中包含X的所有事務(wù)效用值之和，記為TWU(X)，其定義如下：

TWU(X)=∑X?Tb,Tb∈DTU(Tb)

定義6 X為任意給定的項(xiàng)集，minutil為用戶給定的最小效用值(下同)，若U(X)≥minutil，則稱項(xiàng)集X是高效用項(xiàng)集HUI；否則，項(xiàng)集X為非高效用項(xiàng)集。

定義7 在事務(wù)Tb中，項(xiàng)集X之后的項(xiàng)組成的集合記為Tb/X。

定義8 項(xiàng)集X在事務(wù)Tb中的剩余效用值RU(RemainingUtility)記為RU(X,Tb)，其定義如下：

RU(X,Tb)=∑ik∈Tb/XU(ik,Tb)

定義9 如果項(xiàng)集有完成構(gòu)造效用列表，則稱該項(xiàng)集為保留項(xiàng)集，否則稱為非保留項(xiàng)集。

TWU性質(zhì):對(duì)任意給定的項(xiàng)集X，若TWU(X)

由性質(zhì)1對(duì)LA-Prune性質(zhì)[3]進(jìn)行進(jìn)一步擴(kuò)展可得到性質(zhì)2。

2 IHUI-miner算法

改進(jìn)算法IHUI-miner仍沿用HUI-miner中的效用列表進(jìn)行存儲(chǔ)，每個(gè)效用列表由元素組成。雖然在生成項(xiàng)集的1-擴(kuò)展集時(shí)，HUP-miner算法有判斷是否需要生成該擴(kuò)展集的效用列表，但未對(duì)保留項(xiàng)集效用列表中元素對(duì)應(yīng)的RU進(jìn)行更新。IHUI-miner算法不僅對(duì)1-擴(kuò)展集中的保留項(xiàng)集效用列表中的每個(gè)元素的RU值進(jìn)行更新，同時(shí)對(duì)HUP-miner中的LA-Pruning策略進(jìn)行了擴(kuò)展。IHUI-miner算法仍沿用HUP-miner的方式來(lái)對(duì)空間進(jìn)行搜索，第一次掃描得到所有項(xiàng)的TWU值；第二次掃描構(gòu)造所有TWU值大于minutil的項(xiàng)的效用列表ULs，通過(guò)調(diào)用搜索算法Search-space(null，ULs，minutil)來(lái)輸出所有高效用項(xiàng)集。

改進(jìn)算法：IHUI-miner

輸入:事務(wù)數(shù)據(jù)庫(kù)D;

用戶最小效用值minutil;

1.掃描D的所有事務(wù)，計(jì)算所有項(xiàng)的TWU值；

2.forD中的每個(gè)事務(wù)Tbdo

3.對(duì)Tb中的項(xiàng)ik按TWU值降序排序；

4. 掃描排序后的Tb，構(gòu)造項(xiàng)的效用列表ULs；

5.End

6.Search-space(null，ULs，minutil); //算法1

2.1 空間的搜索

改進(jìn)算法IHUI-miner的空間搜索過(guò)程如算法1所示。采用深度優(yōu)先的遞歸方式來(lái)生成項(xiàng)集的1-擴(kuò)展集，從前往后依次取效用列表X作為前綴(第1行)，如果U(X)≥minutil，則輸出X(第2～4行)，隨后實(shí)現(xiàn)TWU性質(zhì)的判斷(第5行)。由于項(xiàng)集X效用列表的TID集包含其擴(kuò)展集X、Y的所有TID，取大小為X.size用來(lái)更新保留項(xiàng)集每個(gè)TID的RU值(第8,9行)。為了了解其后的項(xiàng)集是否為保留項(xiàng)集，從后往前得到后綴Y(第10行)；在構(gòu)造過(guò)程中，head保存著上一個(gè)保留項(xiàng)集中每個(gè)TID的RU值，tail保存著本次每個(gè)TID的RU值，其原因是并不知道本次是否會(huì)完成構(gòu)造效用列表，如果沒(méi)有，則head依然是最新的值，否則利用tail來(lái)對(duì)head進(jìn)行更新(第15行)。為了保證1-擴(kuò)展集中的次序，在存儲(chǔ)效用列表時(shí)，采用了相反的順序(第14行)。在下次遞歸之前提前回收head和tail的內(nèi)存(第18行)。

算法1:Search-space(ULP,ULs，minutil)

輸入:項(xiàng)集P的效用列表ULP，初值為null；

項(xiàng)集P的1-擴(kuò)展效用列表集ULs，初值為項(xiàng)的效用列表；

用戶給定的最小效用值minutil；

輸出：所有的高效用項(xiàng)集；

1.forULs中的每個(gè)效用列表Xdo

2.ifU(X) ≥minutilthen

3. 輸出項(xiàng)集X;

4.end

5.ifU(X) +RU(X) ≥minutilthen

6.exULs= {} ;

7. /*性質(zhì)1*/

8.head指向大小為X.size的空間;初始化為0;

9.tail指向大小為X.size的空間;

10.forULs中最后一個(gè)到X+1的每個(gè)效用

列表Ydo

11.ULXY=ConstructUL(ULP,X,Y，head，

tail,minutil) ; //算法2

12.ifULXY≠NULLthen

13. /*性質(zhì)1*/

14.ULXY插到exULs的前端 ;

15.head<->tail;

16.end

17.end

18.head=tail=null;

19.Search-space(X,exULs,minutil)

20.end

21.End

2.2 效用列表的構(gòu)造過(guò)程

效用列表的構(gòu)造過(guò)程包括項(xiàng)集的效用值的計(jì)算及效用列表的構(gòu)造，如算法2所示。在構(gòu)造過(guò)程中，從頭到尾掃描效用列表Px的每個(gè)元素位置pos(第3行)，在效用列表Py尋找相同的事務(wù)TID的元素(第6行)，計(jì)算該項(xiàng)集的最后一個(gè)項(xiàng)y在每個(gè)事務(wù)中的值(第7行)，所以tail的值可以由該值和head中的值來(lái)更新(第9,12行)，同時(shí)用head來(lái)更新項(xiàng)集效用列表中每個(gè)TID的RU值(第8，11行)。設(shè)Pxy的TWU初值取Px的TWU值(第2行)，用于在構(gòu)造過(guò)程中不斷地去逼近項(xiàng)集Pxy的TWU值。每次先減去事務(wù)中其后非保留項(xiàng)集最后一項(xiàng)的值(第15行)，再利用性質(zhì)2進(jìn)行判斷(第20行)。

算法2:ConstructULAlgorithm

輸入：項(xiàng)集P，Px，Py的效用列表ULP,ULPx,ULPy；

數(shù)組指針head，tail；

用戶給定的最小效用值minutil；

輸出：項(xiàng)集Pxy的效用列表ULPxy；

1.ULPxy=NULL

2.TWU_PX=U(Px) +RU(Px) //性質(zhì)2的初值

3.forULPx中的每個(gè)元素位置posdo

4.if?Ey∈ULpandULPx[pos].TID==Ey.TID

then

5.ifULP≠NULLthen

6.ULP中找元素E使得E.TID==Ey.TID;

7.y_utility=Ey.U-E.U;

8.Exy=

y_utility,head[pos]> ; /*性質(zhì)1*/

9.tail[pos] =head[pos] +y_utility;

10.else

11.Exy= ; /*性質(zhì)1*/

12.tail[pos]=head[pos] +Ey.U;

13.end

14. 將元素Exy添加到ULPxy;

15.TWU_PX-= (Ry.RU-head[pos]) ; /*性質(zhì)2*/

16.else

17.TWU_PX-= (Rx.U+Rx.RU) ;

18.tail[pos] =head[pos] ;

19.end

20.ifTWU_PX

returnNULL; /*性質(zhì)2*/

21 .end

22.returnULPxy

3 實(shí)驗(yàn)結(jié)果

通過(guò)與HUP-miner和HUI-miner的實(shí)驗(yàn)對(duì)比來(lái)測(cè)試新算法的性能，計(jì)算機(jī)的配置為InterCorei5-3470 3.20GHzCPU、16GB內(nèi)存、Windows7 64位系統(tǒng)，三個(gè)算法均用Java來(lái)實(shí)現(xiàn)，其中HUI-miner與HUP-miner的算法代碼來(lái)源于SPMF[6]，HUP-miner算法K值取為512。

實(shí)驗(yàn)所用的數(shù)據(jù)來(lái)源如表1所示，總共有6個(gè)數(shù)據(jù)集，其中Accident、Connect、Mushroom、Kosarak為實(shí)測(cè)數(shù)據(jù)[6]；t20i6d100k和t40i10d100k為合成數(shù)據(jù)，取自FIMI庫(kù)[7]，內(nèi)效用值在1～10之間隨機(jī)產(chǎn)生，外效用值采用log正態(tài)分布。

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

圖1 運(yùn)行時(shí)間比較

算法的運(yùn)行時(shí)間比較如圖1所示，從圖中可以看出，IHUI-miner算法在運(yùn)行時(shí)間上優(yōu)于HUI-miner算法和HUP-miner算法。當(dāng)數(shù)據(jù)集kosarak取值為0.7時(shí)，HUP-miner算法花費(fèi)的時(shí)間是IHUI-miner時(shí)間的近10倍，這主要是因?yàn)樵摂?shù)據(jù)集中在minutil值的變化時(shí)，高效用項(xiàng)集的數(shù)目并未有很大的浮動(dòng)；minutil的值減少，HUP-miner效用列表所占的比例并未有明顯的下降，效用列表的數(shù)目不斷增加，而IHUI-miner算法所占的比例不斷下降，并逐漸趨于0。

圖2 效用列表總數(shù)比較

算法的效用列表總數(shù)比較如圖2所示，圖中縱軸表示IHUI-miner算法、HUP-miner算法的效用列表總數(shù)與HUI-miner算法的效用列表總數(shù)的百分比。實(shí)驗(yàn)結(jié)果表明，IHUI-miner算法的效用列表總數(shù)明顯小于HUP-miner算法，兩者的效用列表總數(shù)都小于HUI-miner算法(小于100%)，表1中的后三個(gè)測(cè)試數(shù)據(jù)集最為明顯。

4 結(jié)論

本文對(duì)垂直模式類的高效用模式挖掘的HUI-miner與HUP-Mine算法進(jìn)行了分析總結(jié)，針對(duì)該類算法的不足，給出了擴(kuò)展項(xiàng)集的兩個(gè)性質(zhì)，在此基礎(chǔ)上提出了一個(gè)改進(jìn)的IHUI-miner高效用模式挖掘算法，該算法構(gòu)造的效用列表的項(xiàng)集是HUP-miner算法的子集，降低了效用列表的總數(shù)，去除了HUP-miner的PUL的劃分列表，理論分析與實(shí)驗(yàn)結(jié)果都表明，改進(jìn)算法IHUI-miner在時(shí)間和列表個(gè)數(shù)上都優(yōu)于HUP-miner與HUI-mine算法。

[1]LiuYing,LiaoWeikeng,CHOUDHARYA.Atwo-phasealgorithmforfastdiscoveryofhighUtilityItemsets[J]. 9thPacific-AsiaConferenceonAdvancesinKnowledgeDiscoveryandDataMining(PAKDD),Hanoi,Vietnam, 2005, 3518:689-695.

[2]AHMEDCF,TANBEERSK,JEONGBS,etal.Efficienttreestructuresforhighutilitypatternmininginincrementaldatabases[J].IEEETransactionsonKnowledgeandDataEngineering, 2009, 21(12):1708-1721.

[3]TSENGVS,SHIEBE,WUCW,etal.Up-growth：anefficientalgorithmforhighutilityitemsetsmining[C] .16thACMSIGKDDInternationalConferenceonKnowhedgeDiscoveryandDataMining(KDD),Washington,2010 :253-262.

[4]LiuMengchi,QuJunfeng.Mininghighutilityitemsetswithoutcandidategeneration[C].ACMinternationalconferenceonInformationandknowledgemanagement, 2012:55-64.

[5]SRIKUMARK.Pruningstrategiesformininghighutilityitemsets[J].ExpertSystemswithApplications2015, 42(5):2371-2381.

[6]FOURNIER-VIGERP,GOMARIZA,LAMH,etal.Spmf:open-sourcedataminingplatform[EB/OL].(2015-12-13)[2016-08-15]http://www.philippe-fournier-viger.com/spmf.

[7]Frequentitemsetminingdatasetrepository[EB/OL].(2015-12-31)[2016-08-15]http：//fimi.ua.ac.be.

黃劍雄(1990-), 男，碩士研究生，主要研究方向：關(guān)聯(lián)規(guī)則、圖像壓縮。

謝伙生(1964-)，通信作者，男，副教授，主要研究方向：數(shù)據(jù)挖掘、圖形圖像處理。E-mail：xiehs@qq.com。

Improved algorithm for mining high utility itemsets based on vertical pattern

HuangJianxiong,XieHuosheng

(CollegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou350116,China)

Improvingtheefficiencyofhighutilityitemsetsminingisoneofpromisingtopicsindatamining,forthehighutilitypatternminingiscomplex.TheHUP-mineralgorithmistypicalandbasedonverticalpattern.Althoughitreducesthattotalnumberofutilitylists,eachitemsetofpartitionedutilitylistneedsmorememoryspaces.Inordertosolvethisproblem,weproposetheIHUI-mineralgorithmtoimplementtherelationshipofitemsetsontheoneextensionwhichisbasedontheHUI-minerandreducethenumberofutilitylists.TheresultsofexperimentsshowthatIHUI-mineroutperformHUP-minerandHUI-minerinthetimeconsumptionandlistnumber.

highutilitypattern；frequentpattern；frequentitemset；verticalpattern

福建省自然科學(xué)基金(2014J01229)

TP

ADOI： 10.19358/j.issn.1674- 7720.2016.22.006

黃劍雄，謝伙生. 垂直模式類高效用模式挖掘的改進(jìn)算法[J].微型機(jī)與應(yīng)用，2016,35(22)：22-25.

2016-08-31)