劉君強 ，周青峰 ，王文慧 ，時 磊

（1.浙江工商大學 杭州 310018；2浙江水利水電學院 杭州 310018）

1 引言

效用模式挖掘[1～6]是近年來發(fā)展起來的大數(shù)據(jù)分析技術(shù)，不僅考慮數(shù)據(jù)統(tǒng)計顯著性，而且也考慮用戶興趣和目標[7]。例如，傳統(tǒng)頻繁模式挖掘技術(shù)[8～11]只能從銷售數(shù)據(jù)中挖掘出購買頻率較高的產(chǎn)品組合，而效用模式挖掘技術(shù)可以從中發(fā)現(xiàn)利潤回報較高的產(chǎn)品組合。效用模式挖掘不僅是各種挖掘問題的基礎(chǔ)[12～14]，也可以直接應用于各種大數(shù)據(jù)分析。例如，網(wǎng)絡(luò)傳媒的點擊率和轉(zhuǎn)化率分析、價值鏈分析、網(wǎng)購的消費者行為理解和預測等。

然而，效用模式挖掘技術(shù)還不成熟，只有很少量成果。由于效用模式不具有反單調(diào)性，即一個低效用模式的超集可能是高效用的，挖掘高效用模式要比挖掘頻繁模式困難得多，因為很難剪裁搜索空間?，F(xiàn)有挖掘算法大多數(shù)采用兩階段法，即先在第1階段從原始數(shù)據(jù)中挖掘出候選模式，再在第2階段從候選模式中進一步挖掘出效用模式。其缺點是挖掘大數(shù)據(jù)時會產(chǎn)生大量候選模式，造成存儲空間開銷過大，形成可伸縮性瓶頸，并最終導致運行的時間效率低下。

不少工作[3,5]試圖降低第1階段生成候選模式數(shù)量。然而，對于海量的數(shù)據(jù)庫或給定較小的效用閾值時，候選模式數(shù)量還是巨大的。這不僅導致第1階段的伸縮性瓶頸，對于第2階段也是如此，并最終導致效率瓶頸。個別算法[15]雖然不生成候選模式，但是依賴于縱向數(shù)據(jù)表達形式和計算代價高昂的交集運算，缺少有效剪裁方法，運行效率比二階段算法還差[5]，不適合于大數(shù)據(jù)處理。為了克服這些問題，本文提出一個全新算法，在單個階段直接挖掘出效用模式。主要貢獻如下。

首先，提出一個全新算法SPUP（single phase utility pattern mining）來挖掘效用模式。具體地講，提出稀疏矩陣來表達事務效用的完整信息，使得單階段挖掘成為可能。這種稀疏矩陣表達比基于Fptree[9]的表達方法[1,2,5]結(jié)構(gòu)更緊湊，避免多遍掃描數(shù)據(jù)庫[3,4]。

第二，提出前綴生長策略及相應的前綴擴展樹，用于引導效用模式的挖掘過程，并得到效用模式搜索空間剪裁技術(shù)的支撐，即通過估算任意子空間的模式效用上限值，有效地剪裁前綴生成樹。

第三，采用人工數(shù)據(jù)和真實數(shù)據(jù)，對比已有最先進算法[1,4,5,15]的實驗結(jié)果表明，本文提出的SPUP算法在運行時間和空間開銷上均優(yōu)于其他算法。換言之，SPUP算法是效率最高、可伸縮性最佳的效用挖掘算法。

2 大數(shù)據(jù)分析中的效用模式挖掘問題

大數(shù)據(jù)分析的特點之一是數(shù)據(jù)來源的多樣性。多個不同的數(shù)據(jù)來源為每個被分析的對象提供了豐富多樣的屬性，但如何融合多源的數(shù)據(jù)卻是一個難題。效用挖掘通過引入效用模型，為融合多個屬性并從中提煉有價值信息提供一種通用方法。因此，效用挖掘在大數(shù)據(jù)分析中有著廣泛的應用。

簡要討論一個移動電子商務應用案例[12]。移動通信運營商保存大量移動設(shè)備軌跡數(shù)據(jù)，單純依賴軌跡數(shù)據(jù)只能分析“高頻繁度的軌跡”，例如“訪問A”以后很可能“訪問B”，其商業(yè)價值并不高。然而，如果將移動運營商的軌跡數(shù)據(jù)與消費者購物的支付數(shù)據(jù)結(jié)合起來進行大數(shù)據(jù)分析，通過融合網(wǎng)點、商品、商品價值等屬性進行效用挖掘，就可以找出“高價值的軌跡”，例如“訪問A購買唇膏”以后很可能“訪問B購買鉆戒”。另一個相似案例是電商平臺的大數(shù)據(jù)分析，通過效用挖掘分析客戶在線購物的消費行為，找出“高價值的網(wǎng)購軌跡”，用于改進電商平臺設(shè)計和指導網(wǎng)上促銷活動。

效用挖掘通過效用的概念將具體應用問題中多個屬性融合起來表達所研究對象的價值，并從中挖掘高價值的對象，即高效用模式。下面給出高效用模式挖掘的定義。

I={i1,i2,…,im}是所有項目的集合，D={t1,t2,…,tn}為數(shù)據(jù)庫，即事務記錄的集合。每個事務記錄t是一個項目集，即t哿I。而u(i,t)=iu(i,t)·eu(i)則是項目i在事務記錄t中的效用，其中iu(i,t)是項目i在事務記錄t中的份額，eu(i)是項目i獨立于任何事務記錄的外在效用。模式X是I的一個子集，如果模式X中的任意項目i在事務t中的份額非0，即iu(i,t)≠0，則模式X被事務記錄t所支持，即X哿t。

·TS(X)則是支持模式X的所有事務記錄的集合。

· 模式X稱作（高）效用模式，如果其效用值不低于給定閾值minutil，即u(X)≥minutil。

· 效用模式挖掘就是發(fā)現(xiàn)所有（高）效用模式，即求解HUPset={X|X哿I,u(X)≥minutil}。

例如，表1給定項目集合I={a,b,c,d,e,f,g}，數(shù)據(jù)庫D由5條事物記錄組成，其中t1包含3個項目a、c、e，并且iu(a,t1)=1、iu(c,t1)=1、iu(e,t1)=1。表 2是所有項目外在效用匯總。由eu(a)=1，可以得到u(a,t1)=iu(a,t1)×eu(a)=1。假定效用模式X={b,c}，由表 1可知：TS(X)={t2,t3}，X的總效用u(X)=u(X,t2)+u(X,t3)=u(b,t2)+u(c,t2)+u(b,t3)+u(c,t3)=24。給定最小效用閾值minutil=30，可以得到高效用模式的集合為{{a,b,c},{a,b,d},{a,d,e},{a,b,d,e},{b,d,e},{d,e},{a,b,c,d,e,g}}。

表1 事務數(shù)據(jù)庫D

表2 效用表UT

效用模式不具有反單調(diào)性，如上例中u({a,c})=28、u({a,b,c})=31、u({a,b,c,d})=13。因此，挖掘高效用模式要比挖掘頻繁模式困難得多。

3 相關(guān)工作

效用模式挖掘是頻繁模式挖掘的發(fā)展。頻繁模式挖掘算法以Agrawal和 Srikant的 Apriori算法[8]以及 Han等人的FP-Growth算法[9]最為著名。Apriori算法充分利用支持度的反單調(diào)性：任何頻繁模式的子集都是頻繁模式。FP-Growth算法采用基于樹的結(jié)構(gòu)存儲事務數(shù)據(jù)庫，也利用反單調(diào)性。

近幾年，效用模式挖掘受到越來越多關(guān)注。Yao等人[7]指出效用指標不具有反單調(diào)性。因此，大量算法采用生成候選模式的二階段挖掘方法。Liu等人[4]提出事務加權(quán)效用TWU向下閉合性質(zhì)，設(shè)計了兩階段算法TP，第1階段先找出具有高TWU的模式（候選模式），第2階段再次掃描數(shù)據(jù)庫來計算各個候選模式的實際效用，從而找出高效用模式。Li等人[3]提出孤立項剔除策略，用于逐層挖掘候選模式的第1階段，以減少多余候選模式。

為克服逐層生成候選模式時多遍掃描數(shù)據(jù)庫[3,4]的缺點，以便第1階段能高效率地生成候選模式，多個研究小組提出基于樹的效用模式挖掘算法[1,2,5]。Erwin等人[2]提出CTUPROL算法，運用事務加權(quán)效用TWU向下閉合性質(zhì)[4]、基于效用模式樹 CUP-tree、FP-Growth算法[9]進行挖掘。Ahmed等人[1]提出一種基于樹的IHUP算法，采用IHUP-tree來存儲各個事務的TWU信息，改進FP-Growth算法[9]來挖掘效用模式的候選模式集。Tseng等人[5]設(shè)計基于樹的二階段算法UPG，利用UP-tree壓縮存儲TWU信息，并提出遞減TWU的策略，因而生成較少數(shù)量的候選模式。

Liu等人[15]提出HUIMiner算法，直接計算各模式的效用信息，避免產(chǎn)生和計算候選模式，但是所依賴的縱向數(shù)據(jù)表達形式不適用于大數(shù)據(jù)，同時代價高昂的交集運算使得其運行效率比二階段算法還差[5]。

本文提出剪裁搜索空間的有效辦法和節(jié)省內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，解決可伸縮性與時間效率的瓶頸。

4 基于前綴生長的模式枚舉和剪裁策略

挖掘效用模式最基本的辦法是窮舉項目集合I的每一個子集X，但是組合爆炸的問題使得這種窮舉法行不通。因此，在挖掘效用模式過程中很有必要使用剪裁技術(shù)。本節(jié)首先引入一種新穎的枚舉效用模式的策略，然后提出剪裁技術(shù)。

4.1 前綴生長的模式枚舉策略

為了避免重復列舉效用模式，需要為數(shù)據(jù)庫中的所有項目指定一個排列順序。這樣，一個模式也可以表達為一個序列。因此，集合表達法（如{a,b,c}）與序列表達法（如）可以混合使用，集合“并”操作也可以用于兩個序列的連接，如∪=。下面提出一種前綴生長策略。

·prefix(X,t)是事務記錄t相對于模式X=的前綴，即t中按照指定順序排列在ik前的項目組成的一個子序列。

·preEXT(X,t)=prefix(X,t)∪X是模式X相對于事務記錄t的前綴擴展。

·前綴生長策略就是將空模式拼接前綴得到長度為1的模式，將長度為1的模式拼接前綴得到長度為2的模式，以此類推。

假定所有項目按照字典序進行排列，那么是空模式<>的一個前綴擴展，是模式的一個前綴擴展。對于表1數(shù)據(jù)庫D，可以得到：preEXT(,t1)=，preEXT(,t2)=。

根據(jù)所提出的前綴生長策略，枚舉效用模式可以看作使一顆前綴擴展樹不斷生長的過程。在前綴擴展樹中，根節(jié)點不標注任何項目代表一個空模式，其他每個節(jié)點標注數(shù)據(jù)庫的一個項目。樹中每一條到達根節(jié)點的路徑代表一個模式。對于標注項目i的節(jié)點來說，它的節(jié)點則標注那些按照指定順序排在項目i前面的項目。節(jié)點N到根節(jié)點的任一條路徑是一個有序序列，它與指定的項目排序是一致的，用pat(N)表示該路徑代表的模式。因此，在前綴擴展樹以節(jié)點N為根的子樹中，任何節(jié)點代表的模式是模式pat(N)的一個前綴擴展，可以表示為preEXT(pat(N))。圖1是一顆完整的前綴擴展樹，其中項目集合I={a,b,c,d}，采用字典序。

圖1 前綴擴展樹

4.2 基于效用上限值評估的前綴擴展樹剪裁

假定數(shù)據(jù)庫的項目集合I={i1,i2,…,im}，即有m個項目，完整的前綴擴展樹有2m個節(jié)點，表示序列的2m個子序列。遍歷這樣一棵樹在計算上是行不通的，因此進行有效的剪裁至關(guān)重要。

然而，在高效用模式挖掘過程中，反單調(diào)性不再適用。剪裁策略是評估以節(jié)點N為根的子樹中所有節(jié)點對應模式的效用上限值，當效用上限值小于minutil時，可以剪裁掉以節(jié)點N為根的子樹。

定理1 對于模式X的任何含有項目i的前綴擴展模式Y(jié)，其效用值u(Y)的一個上限值是：

證明 首先，Y是X的一個前綴擴展，并且i∈Y，因而{i}∪X哿Y，TS(Y)哿TS({i}∪X)。其次，Y是TS(Y)中的任何事務記錄t的子集，同時也是preEXT(X,t)的子集，所以u(Y,t)≤u(preEXT(X,t),t)，進而有：

根據(jù)定理1，如果效用上限值ubound(i,X)小于minutil，那么模式X的任何含有項目i的前綴擴展模式Y(jié)都不可能是高效用模式，因此在X的前綴擴展模式中，項目i可以被剔除。

· 當ubound(i,X)

· 定義ppFix(X,t)為prefix(X,t)剔除無關(guān)項目后的前綴。

· 定義ppEXT(X,t)=ppFix(X,t)∪X為剔除無關(guān)項目后的前綴擴展。

證明 首先，由于Y是X的前綴擴展，TS(Y)哿TS(X)。其次，根據(jù)定理1，Y不包含任何無關(guān)項目，否則Y就不可能是高效用模式。再者，Y是TS(Y)中任何事務記錄t的子集，所以u(Y,t)≤u(preEXT(X,t),t)=u(ppEXT(X,t),t)，進而有：

在前綴擴展樹生長的過程中，對于節(jié)點N對應的模式pat(N)，如果效用上限值ubound(pat(N))低于minutil，以節(jié)點N為根的子樹可被剪裁掉。

5 基于稀疏矩陣和虛擬投影的效用信息表達

高效用模式挖掘是使前綴擴展樹不斷生長的過程，是影響效率和伸縮性的因素之一，是有效表達新生節(jié)點N代表的模式所對應的事務記錄集合的效用信息。

5.1 基于稀疏矩陣的效用信息表達

準確地說，當搜索到前綴擴展樹的節(jié)點N時，在事務記錄集合TS(pat(N))中組成一個前綴擴展模式preEXT(pat(N),t)的所有項目的完整效用信息。為此，提出采用一種由穿線變長數(shù)組[11]實現(xiàn)的稀疏矩陣，如圖2所示。矩陣按行編排TS(pat(N))中的事務記錄，每行實現(xiàn)為變長數(shù)組；列按排列在pat(N)前的項目編排，每列實現(xiàn)為穿線鏈表；第t行第i列元素是u(i,t)，即項目i在事務記錄t中的效用。

圖2 表達效用信息的稀疏矩陣

這種表達法有3個長處：一是能夠完整地表達效用信息，克服了二階段法[1～5]只能表達TWU的缺陷；二是存儲開銷低，實際上比基于Fptree[9]的表達方法[1,2,5]更緊湊；三是計算開銷低，這種表達法是按事務記錄展開的橫向表達法，通過穿線的辦法可以快速確定各個模式的事務記錄集，計算開銷遠低于按項目展開的縱向表達法[15]所采用的交集運算。

表達一個模式X的事務記錄集TS(X)的效用信息的稀疏矩陣也稱為X的效用信息矩陣，記作uMatrix(X)。圖2是根據(jù)表1所示數(shù)據(jù)庫D和效用表UT確定的空模式{}的效用信息矩陣uMatrix({})。 因此，事務記錄集TS(X)和效用信息矩陣uMatrix(X)可以視為同一個數(shù)據(jù)結(jié)構(gòu)，下面不再加以區(qū)分。

5.2 基于虛擬投影的模式效用信息計算

通過搜索前綴擴展樹來枚舉模式時，樹節(jié)點N所代表模式的效用信息矩陣是其父親節(jié)點P所代表模式的效用信息矩陣的子矩陣，可以通過虛擬投影獲得。

具體來講，對于節(jié)點N的標記項目i的節(jié)點C，可以從uMatrix(pat(N))中選擇那些含有i的事務記錄，然后得到模式pat(C)= ({i}∪pat(N))對應的效用信息矩陣uMatrix(pat(C))。這種操作被稱作投影，即節(jié)點C對應的效用信息矩陣uMatrix(pat(C))通過投影其父親節(jié)點N對應的效用信息矩陣uMatrix(pat(N))得到。實際上，除了根節(jié)點之外，任何節(jié)點對應的效用信息矩陣都嵌套在其父親節(jié)點對應的效用信息矩陣中。例如，從uMatrix({})可得到uMatrix({c})，從后者可得到uMatrix({b,c})。

因此，只需要在內(nèi)存中保留根節(jié)點對應的效用信息矩陣，其他節(jié)點的效用信息矩陣只是父親節(jié)點的效用信息矩陣的子矩陣，不需要開辟獨立的內(nèi)存空間。從節(jié)點N的uMatrix(pat(N))推導出節(jié)點C的uMatrix(pat(C))的操作稱為虛擬投影，采用虛擬投影能進一步提高算法的伸縮性。

6 單階段挖掘高效用模式

本節(jié)提出單階段高效用模式挖掘算法SPUP。SPUP算法將第4.1節(jié)的前綴生長策略、第4.2節(jié)的基于效用上限值剪裁策略、第5節(jié)的基于稀疏矩陣的效用信息表達方法相結(jié)合，并應用到按深度優(yōu)先搜索高效用模式的過程中。SPUP算法采用深度優(yōu)先搜索時，只需要在內(nèi)存中保存當前正在生長的前綴擴展樹分支，極大地節(jié)省了內(nèi)存空間，進一步提高算法的伸縮性。下面是SPUP算法的偽代碼，大致分為5步，可以結(jié)合例子進行解釋。

算法 SPUP(D,UT,minutil)

步驟1 （第1～3行）：創(chuàng)建前綴擴展樹的根節(jié)點。通過掃描數(shù)據(jù)庫D，過濾掉全部無關(guān)的項目，得到根節(jié)點（空模式）對應的效用信息矩陣uMatrix({})。

步驟2 （第4～5行）：對于節(jié)點N對應的模式pat(N)=，根據(jù)定理 1，從uMatrix(pat(N))中過濾掉無關(guān)的項目。然后，對于按指定順序排在ik前面的非無關(guān)項目i，根據(jù)定理2，計算模式{i}∪pat(N)的效用值u({i}∪pat(N))和效用上限值ubound({i}∪pat(N))。

例如，圖3是根據(jù)表1的數(shù)據(jù)庫D和表2的外在效用表UT生成的部分前綴擴展樹，其中所有項目按照字典序排序，最小效用閾值minutil=30。每個節(jié)點N都標明其效用信息矩陣uMatrix(pat(N))以及各項目i的效用值(u)和上限值(uB)，即u({i}∪pat(N))和ubound({i}∪pat(N))。

步驟 3 （第 6行）：如果效用值u({i}∪pat(N))≥minutil，那么模式{i}∪pat(N)是一個高效用模式，將它輸出保存。如圖3所示，有一個節(jié)點對應模式{b,c}，其節(jié)點對應模式{a}∪{b,c}的效用值u({a}∪{b,c})=31>minutil，因此{a,b,c}是一個高效用模式，將它輸出。

圖3 前綴擴展樹以及各個節(jié)點的效用信息矩陣

步驟4 （第 7～11行）：如果N的節(jié)點C對應模式{i}∪pat(N) 的效用上限值ubound({i}∪pat(N))≥minutil，需要通過虛擬投影得到節(jié)點C對應的效用信息矩陣uMatrix({i}∪pat(N))，然后深度優(yōu)先搜索以節(jié)點C為根的子樹。如圖3所示，{a}、和 {c}都是根節(jié)點 {}的節(jié)點，由于ubound({a})和ubound()都小于minutil，項目 a、b 對應的節(jié)點被剪裁掉。與此同時，由于ubound({c})=37>minutil，項目c對應的節(jié)點被創(chuàng)建，然后繼續(xù)深度優(yōu)先搜索該節(jié)點對應的子樹。

步驟5 （第12～13行）：深度優(yōu)先搜索完節(jié)點N的所有后，以節(jié)點N為根的子樹就被清除，然后回溯到節(jié)點N的父親節(jié)點P，繼續(xù)深度優(yōu)先搜索P的下一個節(jié)點，以此類推。如圖3所示，搜索模式{a,b,c}相應的節(jié)點后，回溯到根節(jié)點，然后繼續(xù)深度優(yōu)先搜索根節(jié)點的項目d對應的節(jié)點。

7 實驗評價

本節(jié)通過實驗對比，評估效用挖掘的效果，并且評估所提出的單階段模式挖掘算法SPUP的效率和可伸縮性。實驗用到兩個數(shù)據(jù)集：第一個是IBM Quest人工數(shù)據(jù)集T20I6N1kD1mL6k，有100萬條事務記錄，事務記錄平均長度為20個項目，最大頻繁模式平均長度為6個項目，每一條事務記錄中各個項目份額服從1～5的均勻分布，每一個項目對應的外在效用值服從0.01～10的對數(shù)正態(tài)分布；第二個是美國加州一所大型百貨超市連鎖店銷售的真實數(shù)據(jù)集[4]，有1 112 949條銷售事務記錄，每一條事務記錄由商品和商品銷售數(shù)量組成，表示某一個消費者在某個時間段購買商品情況。事務記錄平均長度為7.2，效用表描述每種商品的利潤。實驗環(huán)境為3 GHz CPU/3 GB RAM的PC一臺，運行于Windows 7系統(tǒng)的Cygwin。

7.1 效用挖掘的效果評價

本小節(jié)通過對比本文SPUP算法挖掘得到的TopK高效用模式和CAP算法[10]挖掘得到的TopK閉合頻繁模式，評估效用挖掘的效果。具體采用兩個指標：第一個是覆蓋度（recall），定義為TopK高效用模式被 TopK閉合頻繁模式所覆蓋（包含）的比例；第二個是精確度（precision），定義為TopK閉合頻繁模式中包含TopK高效用模式的比例。如果覆蓋度和精確度比較低，則表明挖掘高效用模式和挖掘頻繁模式有著不同的效果。

圖4（a）是人工數(shù)據(jù)集的TopK閉合頻繁模式和TopK高效用模式的挖掘效果對比。當TopK從1 000變到10 000時，覆蓋度均低于18.2%，精確度均低于45.6%。例如，前5 000個閉合頻繁模式只覆蓋5.6%的前5 000個高效用模式，44.8%的前5 000個閉合頻繁模式包含前5 000個高效用模式。其中，精確度大于覆蓋度的原因是多個閉合模式包含同一個高效用模式。這個結(jié)果表明，大部分高效用模式不是頻繁模式。

圖4 TopK模式的覆蓋度recall和精確度precision

圖4（b）是真實數(shù)據(jù)集的挖掘效果對比。當TopK從1 000變到10 000時，覆蓋度均低于6%,精確度均低于12.1%。例如，前5 000個閉合頻繁模式只覆蓋2.5%的前5 000個高效用模式，10.9%的前5 000個閉合頻繁模式包含前5 000個高效用模式。相對于人工數(shù)據(jù)集，真實數(shù)據(jù)集的TopK閉合頻繁模式比TopK高效用模式的覆蓋度和精確度更低，這更說明高效用模式挖掘在實際應用中的價值遠遠高于頻繁模式挖掘。

7.2 算法效率評價

本小節(jié)通過對比現(xiàn)有最先進效用模式挖掘算法TP[4]、IHUP[1]、UPG[5]、HUIMiner[15]，評估所提出的單階段挖掘算法SPUP的效率，所有算法都采用C++實現(xiàn)。

圖5（a）是5種算法挖掘人工數(shù)據(jù)集的運行時間，其中橫坐標表示最小效用閾值minutil，范圍是0.005%～0.4%，縱坐標表示運行時間。當效用閾值minutil=0.2%時，SPUP算法運行 39 s，UPG算法運行 67 s，IHUP算法運行 98 s，HUIMiner算法運行118 s，而TP算法的運行時間達到1009 s。當效用閾值minutil<0.2%時，TP算法不能運行。當效用閾值minutil=0.005%時，SPUP算法運行 248 s，HUIMiner算法運行 1 052 s，UPG 算法運行 1 430 s，IHUP算法運行2 346 s。

圖5（b）是挖掘真實數(shù)據(jù)集的運行時間，minutil范圍是0.005%～0.2%。當效用閾值minutil≥0.2%時，高效用模式數(shù)量很少，此時HUIMiner算法運行最快；當minutil低于0.2%時，HUIMiner算法的運行時間增長很快。當效用閾值minutil=0.05%時，SPUP算法運行20 s，UPG算法運行52 s，IHUP算法運行55 s，HUIMiner算法運行630 s，而TP算法運行時間達到1 117 s；當效用閾值minutil=0.005%時，SPUP算法運行26 s，UPG運行116 s，IHUP算法運行154 s，HUIMiner算法運行1 797 s，TP算法不能運行。

圖5 各算法隨著minutil變動的運行時間比較

綜合比較可知，SPUP算法效率總是最高的，算法UPG[5]、HUIMiner[15]和IHUP[1]在不同情況下效率互有高低，SPUP算法的效率比后3個算法高5倍以上，TP算法[4]效率總是最低的，SPUP算法比TP算法高70倍。

7.3 存儲開銷和伸縮性評價

圖6（a）分別是算法 SPUP、HUIMiner、UPG 和 IHUP 挖掘人工數(shù)據(jù)集的最大內(nèi)存使用量，TP算法沒有統(tǒng)計內(nèi)存使用情況。當效用閾值minutil=0.4%時，SPUP算法消耗內(nèi)存295 MB，HUIMiner算法消耗內(nèi)存373 MB，UPG算法消耗內(nèi)存424 MB，IHUP算法消耗內(nèi)存426 MB。當效用閾值minutil=0.01%時，SPUP算法消耗內(nèi)存307 MB，HUIMiner算法消耗內(nèi)存380 MB，UPG算法消耗內(nèi)存485MB，IHUP算法消耗內(nèi)存534MB。盡管沒有直接統(tǒng)計數(shù)據(jù)，但TP算法消耗內(nèi)存最多，因為當效用閾值minutil<0.2%時，由于缺少內(nèi)存，TP算法不能運行。

圖6 各個算法隨著minutil變動的內(nèi)存開銷比較

圖6（b）是挖掘真實數(shù)據(jù)集的最大內(nèi)存使用量。當效用閾值minutil=0.2%時，SPUP算法消耗內(nèi)存26.8 MB，算法UPG和IHUP消耗內(nèi)存 63.2 MB，HUIMiner算法消耗內(nèi)存74.9 MB。當效用閾值minutil=0.05%時，SPUP算法消耗內(nèi)存 86.2 MB，HUIMiner算法消耗內(nèi)存 122.9 MB，UPG算法消耗內(nèi)存126.1 MB，IHUP算法消耗內(nèi)存126.5 MB。當效用閾值minutil=0.005%時，S PUP算法消耗內(nèi)存116.2 MB，HUIMiner算法消耗內(nèi)存149.9 MB，UPG算法消耗內(nèi)存165.4 MB，IHUP算法消耗內(nèi)存306.7 MB。TP算法消耗內(nèi)存最多，因為當minutil<0.01%時，TP算法因缺少內(nèi)存而不能繼續(xù)運行。

綜上可知，SPUP算法消耗內(nèi)存最少，HUIMiner算法和UPG算法內(nèi)存消耗量次之，IHUP算法消耗內(nèi)存最多，SPUP算法比后3個算法少消耗20%～60%的內(nèi)存，TP算法消耗內(nèi)存最多。

最后，通過實驗評估SPUP算法的可伸縮性。實驗采用人工數(shù)據(jù)集T20I6N1kL6k，令記錄數(shù)從10萬條變到100萬條，效用閾值minutil=0.01%。如圖7所示，SPUP算法的運行時間與記錄數(shù)的關(guān)系近似線性，SPUP算法的內(nèi)存開銷與記錄數(shù)的關(guān)系也是線性的，表明SPUP算法具有很好的可伸縮性。

圖7 SPUP算法的可伸縮性實驗結(jié)果

8 結(jié)束語

效用挖掘是融合多源的大數(shù)據(jù)進行綜合分析的一種通用方法，其挖掘效果顯著地不同于頻繁模式挖掘，但是遇到效率與可伸縮性難題。為此，本文提出大數(shù)據(jù)中發(fā)現(xiàn)效用模式的快速單階段挖掘算法SPUP，采用稀疏矩陣表達法保存事務記錄的完整效用信息，無須多次掃描數(shù)據(jù)庫，直接挖掘高效用模式；提出前綴生長策略和評估模式效用上限值的方法，能有效地剪裁搜索空間。實驗表明，SPUP算法的效率高于現(xiàn)有算法5倍以上，內(nèi)存開銷減少20%～60%，可伸縮性高。

1 Ahmed C F,Tanbeer S K,Jeong B S,et al.Efficient tree structures for high utility pattern mining in incremental databases.IEEE Transactions on Knowledge and Data Engineering,2009,21(12):1708～1721

2 Erwin A,Gopalan R P,Achuthan N R.Efficient mining of high utility itemsets from large datasets.Proceedings of PAKDD,Osaka,Japan,2008

3 Li Y C,Yeh J S,Chang C C.Isolated items discarding strategy for discovering high utility itemsets.Data & Knowledge Engineering,2008,64(1):98～217

4 Liu Y,Liao W,Choudhary A.A fast high utility itemsets mining algorithm. Proceedings of the Utility-Based Data Mining Workshop in Conjunction With the 11th ACM SIGKDD,Chicago,Illinois,USA,2005

5 Tseng V S,Shie B E,Wu C W,et al.Efficient algorithms for mining high utility itemsets from transactional databases.IEEE Transactions on Knowledge and Data Engineering,2013,25(8):1772～1786

6 Yen S J,Lee Y S.Mining high utility quantitative association rules.Proceeding of the 9th International Conference on Data Warehousing and Knowledge Discovery,Regensburg,Germany,2007

7 Yao H,Hamilton H J,Geng L.A unified framework for utility-based measures for mining itemsets.Proceedings of ACM SIGKDD the 2nd Workshop on Utility-Based Data Mining,Philadelphia,PA,USA,2006

8 Agrawal R,Srikant R.Fast algorithms for mining association rules.Proceedings of the 20th International Conference on Very Large Databases,Santiago,Chile,1994

9 Han J,Pei J,Yin Y.Mining frequent patterns without candidate generation.Proceedings of ACM SIGMOD conference,Dallas,USA,2000

10 Liu J,Pan Y.An efficient algorithm for mining closed itemsets.Journal of Zhejiang University Science,2004,5(1):8～15

11 Liu J,Pan Y,Wang K,et al.Mining frequent item sets by opportunistic projection.Proceedings of SIGKDD,Edmonton,Canada,2002

12 Shie B E,Cheng J H,Chuang K T,et al.A one-phase method for mining high utility mobile sequential patterns in mobile commerce environments.Proceedings of IEA/AIE12,Dalian,China,2012

13 Wu C W,Lin Y F,Yu P S,et al.Mining high utility episodes in complex event sequences.Proceedings of the 19th ACM SIGKDD International Conference on KnowledgeDiscoveryand Data Mining,Chicago Illinois,USA,2013

14 Wu C W,Shie B E,Tseng V S,et al.Mining top-Khigh utility itemsets.Proceedings of SIG KDD,Beijing,China,2012

15 Liu M,Qu J.Mining high utility itemsets without candidate generation.Proceedings of CIKM,Maui,HI,USA,2012