黃劍雄，謝伙生

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

       摘要：由于高效用模式挖掘較為復(fù)雜，提高其挖掘算法的效率是數(shù)據(jù)挖掘的研究熱點(diǎn)。HUPminer算法是典型的基于垂直模式類(lèi)的高效用模式挖掘算法，雖然能夠有效地減少效用列表的總個(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算法。

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

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

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

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 Weighted Utility）性質(zhì)［1］來(lái)減少搜索時(shí)間。

　　高效用模式挖掘算法主要有模式增長(zhǎng)類(lèi)與垂直模式類(lèi)算法。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)類(lèi)算法IHUP［2］、UP-Growth［3］和UP-Growh+［3］的改進(jìn)目標(biāo)，是減少候選集產(chǎn)生的關(guān)鍵所在，文獻(xiàn)［4］提出了垂直模式類(lèi)高效用模式挖掘的HUI-miner算法，該算法與Eclat算法類(lèi)似，能直接計(jì)算項(xiàng)集的實(shí)際效用值，每個(gè)項(xiàng)集擁有一個(gè)效用列表UL（Utility List），用來(lái)構(gòu)造其他項(xiàng)集的效用列表和計(jì)算實(shí)際效用值，并利用TWU性質(zhì)來(lái)剪枝。HUI-miner算法優(yōu)于模式增長(zhǎng)類(lèi)的IUPTWU算法、UP-Growh+算法。文獻(xiàn)［5］提出了垂直模式類(lèi)的HUP-miner算法，該算法提出了劃分效用列表PUL(Partitioned Utility List)，每個(gè)PUL由項(xiàng)集的效用列表UL和劃分列表PL（Partition List）組成，一方面利用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(Improved High Utility Itemsets)，該算法仍沿用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è)稱(chēng)為外效用的值，記為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è)稱(chēng)為內(nèi)效用的值，記為IU(ic,Tb)。若項(xiàng)集P是一個(gè)長(zhǎng)度為L(zhǎng)的項(xiàng)集，稱(chēng)P為L(zhǎng)項(xiàng)集；Pik（ik∈I）以P為前綴，長(zhǎng)度為L(zhǎng)+1的項(xiàng)集，稱(chē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)的效用值之和，記為T(mén)U(Tb)，其定義如下：

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

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

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

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

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

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

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

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

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

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

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

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

　　性質(zhì)2已知在P的1擴(kuò)展集中，保留項(xiàng)集的集合為Q={Pi′1,Pi′2,…,Pi′k}， Tb∈D，Pi′m,Pi′n∈Q(m<n)，在構(gòu)造Pi′mi′n的效用列表過(guò)程中，若∑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)行存儲(chǔ)，每個(gè)效用列表由元素<TID，U，RU>組成。雖然在生成項(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;

　　用戶(hù)最小效用值minutil;

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

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

　　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)的效用列表；

　　用戶(hù)給定的最小效用值minutil；

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

　　1. for ULs中的每個(gè)效用列表X do

　　2.if U(X) ≥ minutil then

　　3.輸出項(xiàng)集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中最后一個(gè)到X+1的每個(gè)效用

　　列表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)造過(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:ConstructUL Algorithm

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

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

　　用戶(hù)給定的最小效用值minutil；

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

　　1.ULPxy= NULL

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

　　3.for ULPx中的每個(gè)元素位置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實(shí)驗(yàn)結(jié)果

　　通過(guò)與HUP-miner和HUI-miner的實(shí)驗(yàn)對(duì)比來(lái)測(cè)試新算法的性能，計(jì)算機(jī)的配置為Inter Core i53470 3.20 GHz CPU、16 GB內(nèi)存、Windows 7 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)分布。

　　算法的運(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。

　　算法的效用列表總數(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ì)垂直模式類(lèi)的高效用模式挖掘的HUI-miner與HUP-Mine算法進(jìn)行了分析總結(jié)，針對(duì)該類(lèi)算法的不足，給出了擴(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算法。

　　參考文獻(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.

　　［2］ 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.

　?。?］ 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.

　　［4］ 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.

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