黃劍雄，謝伙生
（福州大學 數學與計算機學院，福建 福州 350116）
摘要：由于高效用模式挖掘較為復雜，提高其挖掘算法的效率是數據挖掘的研究熱點。HUPminer算法是典型的基于垂直模式類的高效用模式挖掘算法，雖然能夠有效地減少效用列表的總個數，但對于項集的劃分，效用列表需要更多的空間。針對該問題，在HUI-miner算法的基礎上充分考慮了1擴展集中項集的關聯性，減少了效用列表個數，提出了改進的IHUI-miner算法。實驗結果表明，改進算法IHUI-miner在時間效率和減少效用列表的個數上都優于HUP-miner與HUI-miner算法。
中圖分類號：TP311.13文獻標識碼：A DOI： 10.19358/j.issn.16747720.2016.22.006
引用格式：黃劍雄，謝伙生. 垂直模式類高效用模式挖掘的改進算法［J］.微型機與應用，2016,35（22）：22-25.
0引言
近年來，高效用模式挖掘是頻繁模式挖掘研究的熱點之一。與傳統的頻繁模式相比，高效用模式挖掘中每條事務的項都有對應的值（如數量），同時項集的每個項也有對應的值（如利潤），其目標就是尋找所有效用值大于或等于最小效用值的項集。傳統頻繁模式挖掘是利用向下閉合的性質來減少挖掘過程中的空間搜索時間，而高效用模式挖掘是利用事務權重效用值TWU（Transaction Weighted Utility）性質［1］來減少搜索時間。
高效用模式挖掘算法主要有模式增長類與垂直模式類算法。TWO-Phase算法［1］是最早運用模式增長方式來實現高效用模式挖掘的，需要花費大量的時間和空間來產生候選集和計算實際效用值。大多數的高效用事務數據集只能有損地存儲在樹結構中，這也是模式增長類算法IHUP［2］、UP-Growth［3］和UP-Growh+［3］的改進目標，是減少候選集產生的關鍵所在，文獻［4］提出了垂直模式類高效用模式挖掘的HUI-miner算法，該算法與Eclat算法類似，能直接計算項集的實際效用值，每個項集擁有一個效用列表UL（Utility List），用來構造其他項集的效用列表和計算實際效用值，并利用TWU性質來剪枝。HUI-miner算法優于模式增長類的IUPTWU算法、UP-Growh+算法。文獻［5］提出了垂直模式類的HUP-miner算法，該算法提出了劃分效用列表PUL(Partitioned Utility List)，每個PUL由項集的效用列表UL和劃分列表PL（Partition List）組成，一方面利用PU-Prune性質［5］和劃分列表來預判斷是否需要構造項集的效用列表，另一方面在構造PUL過程中，利用LA-Prune性質［5］來及時判斷返回而不是等到構造完成后再返回，以此來減少效用列表的數目，提高算法效率。盡管如此，HUP-miner算法還是存在一些值得改進的地方，具體體現在：（1）在利用PU-Prune性質和劃分列表進行預判斷時，若最小效用值較小或數據集較密集，則可能會存在過多的冗余計算和內存消耗。（2）在利用LA-Prune性質來減少項集效用列表的構造過程中，忽略了同一項集的1 擴展集中項集之間的關聯性。針對這些不足，本文提出了一個改進的高效用模式挖掘的改進算法IHUI-miner(Improved High Utility Itemsets)，該算法仍沿用HUI-miner中的效用列表來存儲數據集，以更新保留項集的效用列表剩余效用值，同時對HUP-miner中LA-Pruning策略進行擴展。實驗結果表明，IHUI-miner算法在時間效率和減少列表的個數上都優于HUP-miner與HUI-miner算法。
1相關定義與性質
假設I={i1,i2,…,im}是由m個不同項組成的項集合，每項ik(1≤k≤m)都有一個稱為外效用的值，記為EU(ik)。D={T1,T2,…,Tn}是長度為n的事務數據集，D中的每個事務Tb(1≤b≤n)都是項集I的子集，都有一個唯一的標識符（TID）b。事務Tb中的每個項ic都有一個稱為內效用的值，記為IU(ic,Tb)。若項集P是一個長度為L的項集，稱P為L項集；Pik（ik∈I）以P為前綴，長度為L+1的項集，稱Pik為P的1 擴展項集。
定義1項ik在事務Tb中的效用值記為U(ik,Tb)，其定義如下：
U(ik,Tb)=EU(ik)*IU(ik,Tb)
定義2項集X在事務Tb中的效用值記為U(X,Tb)，其定義如下：
U(X,Tb)=∑ik∈X,XTbU(ik,Tb)
定義3項集X在D中的效用值記為U(X)，其定義如下：
U(X)=∑XTb,Tb∈DU(X,Tb)
定義4一個事務Tb的效用值指的是事務Tb中所有項的效用值之和，記為TU(Tb)，其定義如下：
TU(Tb)=∑ik∈TbU(ik,Tb)
定義5項集X在數據集D中的事務權重效用值TWU指的是事務數據集D中包含X的所有事務效用值之和，記為TWU(X)，其定義如下：
TWU(X)=∑XTb,Tb∈DTU(Tb)
定義6X為任意給定的項集，minutil為用戶給定的最小效用值（下同），若U(X)≥minutil，則稱項集X是高效用項集HUI；否則，項集X為非高效用項集。
定義7在事務Tb中，項集X之后的項組成的集合記為Tb/X。
定義8項集X在事務Tb中的剩余效用值RU(Remaining Utility)記為RU(X,Tb)，其定義如下：
RU(X,Tb)=∑ik∈Tb/XU(ik,Tb)
定義9如果項集有完成構造效用列表，則稱該項集為保留項集，否則稱為非保留項集。
TWU性質:對任意給定的項集X，若TWU(X)<minutil，則項集X的任意超集都不是高效用項集。
性質1已知在P的1 擴展集中保留項集的集合為Q={Pi′1,Pi′2,…,Pi′k}，則有對任意的1≤j≤k，Pi′jTb，RU(Pi′j,Tb)更新為∑km=j+1U(i′m,Tb)。
顯然可以證明更新后的RU(Pi′j,Tb)不會影響項集的生成，即若有U(Pi′j)+RU(Pi′j)<minutil，則以Pi′j為前綴的所有擴展集都不是高效用項集。
由性質1對LA-Prune性質［3］進行進一步擴展可得到性質2。
性質2已知在P的1擴展集中，保留項集的集合為Q={Pi′1,Pi′2,…,Pi′k}， Tb∈D，Pi′m,Pi′n∈Q(m<n)，在構造Pi′mi′n的效用列表過程中，若∑Pi′mTb,Pi′nTb(U(Pi′m,Tb)+RU(Pi′m,Tb)－(RU(Pi′n,Tb)－RU(Pi′mi′n,Tb))<minutil，則不必構造Pi′mi′n的效用列表（其中RU(Pi′mi′n,Tb)為性質1更新后的值）。
2IHUI-miner算法
改進算法IHUI-miner仍沿用HUI-miner中的效用列表進行存儲，每個效用列表由元素<TID，U，RU>組成。雖然在生成項集的1擴展集時，HUPminer算法有判斷是否需要生成該擴展集的效用列表，但未對保留項集效用列表中元素對應的RU進行更新。IHUI-miner算法不僅對1 擴展集中的保留項集效用列表中的每個元素的RU值進行更新，同時對HUP-miner中的LA-Pruning策略進行了擴展。IHUI-miner算法仍沿用HUP-miner的方式來對空間進行搜索，第一次掃描得到所有項的TWU值；第二次掃描構造所有TWU值大于minutil的項的效用列表ULs，通過調用搜索算法Search space（null，ULs，minutil)來輸出所有高效用項集。
改進算法： IHUI-miner
輸入:事務數據庫D;
用戶最小效用值minutil;
1.掃描D的所有事務，計算所有項的TWU值；
2.for D中的每個事務Tb do
3.對Tb中的項ik按TWU值降序排序；
4. 掃描排序后的Tb，構造項的效用列表ULs；
5. End
6. Searchspace （null，ULs，minutil); //算法1
2.1空間的搜索
改進算法IHUI-miner的空間搜索過程如算法1所示。采用深度優先的遞歸方式來生成項集的1 擴展集，從前往后依次取效用列表X作為前綴（第1行），如果U(X)≥minutil，則輸出X（第2~4行），隨后實現TWU性質的判斷（第5行）。由于項集X效用列表的TID集包含其擴展集X、Y的所有TID，取大小為X.size用來更新保留項集每個TID的RU值（第8,9行）。為了了解其后的項集是否為保留項集，從后往前得到后綴Y（第10行）；在構造過程中，head保存著上一個保留項集中每個TID的RU值，tail保存著本次每個TID的RU值，其原因是并不知道本次是否會完成構造效用列表，如果沒有，則head依然是最新的值，否則利用tail來對head進行更新（第15行）。為了保證1擴展集中的次序，在存儲效用列表時，采用了相反的順序（第14行）。在下次遞歸之前提前回收head和tail的內存（第18行）。
算法1: Search space(ULP,ULs，minutil)
輸入:項集P的效用列表ULP，初值為null；
項集P的1 擴展效用列表集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. /*性質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./*性質1*/
14.ULXY插到exULs的前端 ;
15.head <－> tail ;
16. end
17. end
18.head = tail = null ;
19. Searchspace (X, exULs, minutil)
20. end
21. End
2.2效用列表的構造過程
效用列表的構造過程包括項集的效用值的計算及效用列表的構造，如算法2所示。在構造過程中，從頭到尾掃描效用列表Px的每個元素位置pos（第3行），在效用列表Py尋找相同的事務TID的元素（第6行），計算該項集的最后一個項y在每個事務中的值（第7行），所以tail的值可以由該值和head中的值來更新（第9,12行），同時用head來更新項集效用列表中每個TID的RU值（第8，11行）。設Pxy的TWU初值取Px的TWU值（第2行），用于在構造過程中不斷地去逼近項集Pxy的TWU值。每次先減去事務中其后非保留項集最后一項的值（第15行），再利用性質2進行判斷（第20行）。
算法2:ConstructUL Algorithm
輸入：項集P，Px，Py的效用列表ULP,ULPx,ULPy；
數組指針head，tail；
用戶給定的最小效用值minutil；
輸出：項集Pxy的效用列表ULPxy；
1.ULPxy= NULL
2.TWU_PX= U(Px) + RU(Px)//性質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］> ;/*性質1*/
9. tail［pos］ = head［pos］ + y_utility ;
10. else
11.Exy=<Ex.TID,Ex.U +Ey. U,head［pos］> ; /*性質1*/
12.tail［pos］=head［pos］ + Ey. U;
13. end
14. 將元素Exy添加到ULPxy;
15.TWU_PX -= (Ry.RU - head［pos］) ; /*性質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 ;/*性質2*/
21 .end
22.returnULPxy
3實驗結果
通過與HUP-miner和HUI-miner的實驗對比來測試新算法的性能，計算機的配置為Inter Core i53470 3.20 GHz CPU、16 GB內存、Windows 7 64位系統，三個算法均用Java來實現，其中HUI-miner與HUP-miner的算法代碼來源于SPMF［6］，HUP-miner算法K值取為512。
實驗所用的數據來源如表1所示，總共有6個數據集，其中Accident、Connect、Mushroom、Kosarak為實測數據［6］；t20i6d100k和t40i10d100k為合成數據，取自FIMI庫［7］，內效用值在1~10之間隨機產生，外效用值采用log正態分布。
算法的運行時間比較如圖1所示，從圖中可以看出，IHUI-miner算法在運行時間上優于HUI-miner算法和HUP-miner算法。當數據集kosarak取值為0.7時，HUP-miner算法花費的時間是IHUI-miner時間的近10倍，這主要是因為該數據集中在minutil值的變化時，高效用項集的數目并未有很大的浮動；minutil的值減少，HUP-miner效用列表所占的比例并未有明顯的下降，效用列表的數目不斷增加，而IHUI-miner算法所占的比例不斷下降，并逐漸趨于0。
算法的效用列表總數比較如圖2所示，圖中縱軸表示IHUI-miner算法、HUP-miner算法的效用列表總數與HUI-miner算法的效用列表總數的百分比。實驗結果表明，IHUI-miner算法的效用列表總數明顯小于HUP-miner算法，兩者的效用列表總數都小于HUI-miner算法（小于100%），表1中的后三個測試數據集最為明顯。
4結論
本文對垂直模式類的高效用模式挖掘的HUI-miner與HUP-Mine算法進行了分析總結，針對該類算法的不足，給出了擴展項集的兩個性質，在此基礎上提出了一個改進的IHUI-miner高效用模式挖掘算法，該算法構造的效用列表的項集是HUP-miner算法的子集，降低了效用列表的總數，去除了HUP-miner的PUL的劃分列表，理論分析與實驗結果都表明，改進算法IHUI-miner在時間和列表個數上都優于HUP-miner與HUI-mine算法。
參考文獻
［1］ 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.
［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 :253262.
［4］ Liu Mengchi, Qu Junfeng.Mining high utility itemsets without candidate generation［C］. ACM international conference on Information and knowledge management, 2012:55-64.
［5］ SRIKUMAR K. Pruning strategies for mining high utility itemsets［J］.Expert Systems with Applications 2015, 42(5):2371-2381.
［6］ FOURNIER VIGER P, GOMARIZ A, LAM H, et al. Spmf: opensource data mining platform［EB/OL］.（2015-12-13）［2016-08-15］http://www.philippefournier viger.com/spmf.
［7］ Frequent itemset mining dataset repository［EB/OL］.（2015-12-31）［2016-08-15］http：//fimi.ua.ac.be.