黃劍雄，謝伙生

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

垂直模式類高效用模式挖掘的改進算法*

黃劍雄，謝伙生

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

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

高效用模式；頻繁模式；頻繁項集；垂直模式

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

定義5 項集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為任意給定的項集，minutil為用戶給定的最小效用值(下同)，若U(X)≥minutil，則稱項集X是高效用項集HUI；否則，項集X為非高效用項集。

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

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

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

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

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

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

2 IHUI-miner算法

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

改進算法：IHUI-miner

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

用戶最小效用值minutil;

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

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

3.對Tb中的項ik按TWU值降序排序；

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

5.End

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

2.1 空間的搜索

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

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

輸入:項集P的效用列表ULP，初值為null；

項集P的1-擴展效用列表集ULs，初值為項的效用列表；

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

輸出：所有的高效用項集；

1.forULs中的每個效用列表Xdo

2.ifU(X) ≥minutilthen

3. 輸出項集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中最后一個到X+1的每個效用

列表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)造過程

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

算法2:ConstructULAlgorithm

輸入：項集P，Px，Py的效用列表ULP,ULPx,ULPy；

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

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

輸出：項集Pxy的效用列表ULPxy；

1.ULPxy=NULL

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

3.forULPx中的每個元素位置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 實驗結(jié)果

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

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

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

圖1 運行時間比較

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

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

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

4 結(jié)論

本文對垂直模式類的高效用模式挖掘的HUI-miner與HUP-Mine算法進行了分析總結(jié)，針對該類算法的不足，給出了擴展項集的兩個性質(zhì)，在此基礎(chǔ)上提出了一個改進的IHUI-miner高效用模式挖掘算法，該算法構(gòu)造的效用列表的項集是HUP-miner算法的子集，降低了效用列表的總數(shù)，去除了HUP-miner的PUL的劃分列表，理論分析與實驗結(jié)果都表明，改進算法IHUI-miner在時間和列表個數(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].微型機與應(yīng)用，2016,35(22)：22-25.

2016-08-31)