黃劍雄，謝伙生

　?。ǜＶ荽髮W(xué) 數(shù)學(xué)與計算機(jī)學(xué)院，福建 福州 350116）

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

　　關(guān)鍵詞：高效用模式；頻繁模式；頻繁項集；垂直模式

　　中圖分類號：TP311.13文獻(xiàn)標(biāo)識碼：A DOI： 10.19358/j.issn.16747720.2016.22.006

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

0引言

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

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

　　定義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)

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

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

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

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

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

　　TWU性質(zhì):對任意給定的項集X，若TWU(X)<minutil，則項集X的任意超集都不是高效用項集。

　　性質(zhì)1已知在P的1 擴(kuò)展集中保留項集的集合為Q={Pi′1,Pi′2,…,Pi′k}，則有對任意的1≤j≤k，Pi′jTb，RU(Pi′j,Tb)更新為∑km=j+1U(i′m,Tb)。

　　顯然可以證明更新后的RU(Pi′j,Tb)不會影響項集的生成，即若有U(Pi′j)+RU(Pi′j)<minutil，則以Pi′j為前綴的所有擴(kuò)展集都不是高效用項集。

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

　　性質(zhì)2已知在P的1擴(kuò)展集中，保留項集的集合為Q={Pi′1,Pi′2,…,Pi′k}， Tb∈D，Pi′m,Pi′n∈Q(m<n)，在構(gòu)造Pi′mi′n的效用列表過程中，若∑Pi′mTb,Pi′nTb(U(Pi′m,Tb)+RU(Pi′m,Tb)－(RU(Pi′n,Tb)－RU(Pi′mi′n,Tb))<minutil，則不必構(gòu)造Pi′mi′n的效用列表（其中RU(Pi′mi′n,Tb)為性質(zhì)1更新后的值）。

2IHUI-miner算法

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

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

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

　　用戶最小效用值minutil;

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

　　2.for D中的每個事務(wù)Tb do

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

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

　　5. End

　　6. Searchspace （null，ULs，minutil); //算法1

　　2.1空間的搜索

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

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

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

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

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

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

　　1. for ULs中的每個效用列表X do

　　2.if U(X) ≥ minutil then

　　3.輸出項集X ;

　　4.end

　　5.if U(X) + RU(X) ≥ minutil then

　　6.exULs = {} ;

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

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

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

　　10.for ULs中最后一個到X+1的每個效用

　　列表Y do

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

　　tail, minutil) ; //算法2

　　12. if ULXY≠ NULL then

　　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進(jìn)行判斷（第20行）。

　　算法2:ConstructUL Algorithm

　　輸入：項集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.for ULPx中的每個元素位置posdo

　　4. if Ey∈ULp and ULPx［pos］.TID == Ey.TID

　　then

　　5. ifULP ≠ NULL then

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

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

　　8.Exy=<Ey.TID,ULPx［pos］.U+

　　y_utility,head［pos］> ;/*性質(zhì)1*/

　　9. tail［pos］ = head［pos］ + y_utility ;

　　10. else

　　11.Exy=<Ex.TID,Ex.U +Ey. U,head［pos］> ; /*性質(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. if TWU_PX < minutil then

　　return NULL ;/*性質(zhì)2*/

　　21 .end

　　22.returnULPxy

3實驗結(jié)果

　　通過與HUP-miner和HUI-miner的實驗對比來測試新算法的性能，計算機(jī)的配置為Inter Core i53470 3.20 GHz CPU、16 GB內(nèi)存、Windows 7 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之間隨機(jī)產(chǎn)生，外效用值采用log正態(tài)分布。

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

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

　　參考文獻(xiàn)

　?。?］ Liu Ying, Liao Weikeng, CHOUDHARY A. A two phase algorithm for fast discovery of high Utility Itemsets［J］. 9th Pacific Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD), Hanoi, Vietnam, 2005, 3518:689-695.

　?。?］ AHMED C F, TANBEER S K, JEONG B S, et al.Efficient tree structures for high utility pattern mining in incremental databases［J］. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(12):1708-1721.

　　［3］ TSENG V S,SHIE B E,WU C W, et al. Up growth：an efficient algorithm for high utility itemsets mining［C］ .16th ACM SIGKDD International Conference on Knowhedge Discovery and Data Mining (KDD), Washington,2010 :253262.

　?。?］ Liu Mengchi, Qu Junfeng.Mining high utility itemsets without candidate generation［C］. ACM international conference on Information and knowledge management, 2012:55-64.

　?。?］ SRIKUMAR K. Pruning strategies for mining high utility itemsets［J］.Expert Systems with Applications 2015, 42(5):2371-2381.

　?。?］ FOURNIER VIGER P, GOMARIZ A, LAM H, et al. Spmf: opensource data mining platform［EB/OL］.（2015-12-13）［2016-08-15］http://www.philippefournier  viger.com/spmf.

　　［7］ Frequent itemset mining dataset repository［EB/OL］.（2015-12-31）［2016-08-15］http：//fimi.ua.ac.be.