浦 蓉，邵劍飛，胡常禮，曲 坤

(昆明理工大學(xué)信息工程與自動化學(xué)院，云南 昆明 650500)

1 引言

在定量數(shù)據(jù)庫中挖掘高平均效用項集HAUIs(High Average-Utility Itemsets)是頻繁項集挖掘的傳統(tǒng)問題的擴展，具有若干實際應(yīng)用[1-3]。項集的平均效用是項集的總效用除以項集的長度，能更公平地衡量項集。挖掘HAUIs比使用傳統(tǒng)支持模型挖掘頻繁項集更具挑戰(zhàn)性，因為項集的平均效用不滿足向下閉合屬性；為了解決這個問題，并進一步縮小搜索空間，提出了平均效用上限模型[4 - 7]。然而，提取高平均效用項集仍然很耗時。因此，提高高平均效用項集挖掘技術(shù)的效率迫在眉睫。

Lin等人[8]提出了高效平均效用模式挖掘算法EHAUPM(Efficient algorithm for High Average-Utility Pattern Mining)。EHAUPM算法基于一種改進的平均效用列表結(jié)構(gòu)，通過2個更嚴(yán)格的上界模型和3種修剪策略來增強HAUIs挖掘的性能，但在最小平均效用閾值設(shè)置較低時，該算法無法更多地修剪沒有希望成為高平均效用項集的候選項集。Yun等人[9]提出了挖掘高平均效用項集MHAI(Mining High Average-utility Itemset)算法。MHAI算法基于高平均效用項集列表HAI-List(High Average-utility Itemset List)結(jié)構(gòu)，通過使用k個項集的HAI-List遞歸構(gòu)造(k+1)個項集的HAI-List，從而基于深度優(yōu)先的方式進行數(shù)據(jù)挖掘，但是數(shù)據(jù)庫排序和比較列表輸入會占用大量運行時間。

為了進一步提高HAUIs挖掘的效率，本文提出了一種dMHAUI(diffset technology for Mining High Average-Utility Itemsets)算法。該算法首先定義了集成矩陣Q，避免重復(fù)計算事務(wù)中每個項目的效用，并基于垂直形式提出4種更緊湊的平均效用上界和3種有效的剪枝策略，大幅度消除了沒有希望成為高平均效用項集的候選項集，縮小了搜索空間。在數(shù)據(jù)挖掘過程中，使用名為IDUL(Itemset-Diffset-UtilityList)的前綴樹結(jié)構(gòu)存儲挖掘HAUIs所需的信息，同時，利用改進后的diffset技術(shù)[10 - 12]快速計算項集的列效用和4種平均效用上界的值，從而減少了程序執(zhí)行的時間。仿真結(jié)果表明，相比EHAUPM算法和MHAI算法，dMHAUI算法在真實數(shù)據(jù)庫和合成數(shù)據(jù)庫上的運行時間、連接次數(shù)和可擴展性等方面都有較優(yōu)的性能。

2 模型

2.1 定義

設(shè)A*={aj,j∈J={1,2,…,M}}為一組有限的不同項目，項集A是A*的子集,如果項集中包含k個項目，則稱為k-項集(k=|A|)。不失一般性，假定每個項集中的所有項目都按升序排序()。此外，每個項目都有1個外部效用p(a)，表示商品的單位利潤，A*中所有項目的單位利潤組成利潤向量P=(p(aj),j∈J)。一個q-項目表示為(a,q)，其中a∈A*且q為非負(fù)數(shù)，表示項目a的內(nèi)部效用，例如商品的購買數(shù)量。每個事務(wù)都是1組q-項目，表示為ti={(aj,qij),j∈Ji}，Ji?J是J的索引子集。數(shù)據(jù)庫D={ti,i∈I={1,2,…,N}}是1組有限的事務(wù)，每個事務(wù)ti都有唯一的標(biāo)識符TID。q-項目(a,q)的效用為u(a,q)=q*p(a)。

當(dāng)挖掘定量數(shù)據(jù)庫以找到高效用模式時，為了避免重復(fù)計算在事務(wù)ti中的每個q-項目(aj,qij)的效用u(aj,qij)=qij*p(aj)，把每個q-項目的效用計算一次并存儲在轉(zhuǎn)換數(shù)據(jù)庫D′={t′i={(aj,q′ij),j∈Ji},Ji?J,i∈I}中，得到的轉(zhuǎn)換數(shù)據(jù)庫稱為簡要集成矩陣Q={q′ij,i∈I,j∈J}，q′ij定義如下：

此外，考慮一個算子ρ:2A→2J，定義如下： ?A?A*:A≠?,ρ(A)={ti∈D|{q′ij>0,?aj∈A}且按慣例ρ(?)=D。該運算符將每個非空項集A映射到A中所有項目的購買數(shù)量大于零的事務(wù)。由此，本文只考慮集合LS={A?A*|ρ(A)≠?}的項集，即至少在一個事務(wù)中出現(xiàn)的項集。

定義2事務(wù)ti的事務(wù)效用定義為tu(ti)=∑q′ij>0q′ij。定量數(shù)據(jù)庫D的總效用TU為事務(wù)效用的總和，定義為：TU=∑ti∈Dtu(ti)。

定義3令mu為最小平均效用閾值(正數(shù))。當(dāng)且僅當(dāng)au(A)≥mu時，項集A稱為高平均效用HAU(High Average-Utility)；否則，稱為低平均效用LAU(Low Average-Utility)。因此，高平均效用項集挖掘是找到所有的HAUS={A∈LS|au(A)≥mu}集合。

定義4在擴展HAU候選項集搜索空間時，項集P用項集B擴展，使得PB(即?a∈P,?b∈B,ab)，擴展后的項集稱為項集C=P∪B，項集P是項集C的前綴。如果B=或者P,則P擴展項集可以簡記為Pb。

定義5令E和R為LS中的項集，ub為平均效用au的上限，即對任意P∈LS，au(P)≤ub(P)。

2.2 效用u(A)的垂直形式

令vj(A)=∑ti∈ρ(A)q′ij為Q矩陣第j列項集A的列效用。設(shè)V(A)=(vj(A)，j≥minInd(A))是從minInd(A)列開始與A關(guān)聯(lián)的所有列效用值，其中,minInd(A)=min{j∈J|aj∈A}是A中項目aj的最小索引(或第1索引)，minInd(?)=1。基于這些定義，用垂直形式定義A的效用。

引理1對于每個項集:

(1)

證明

u(A)=∑ti∈ρ(A)[∑ajq′ij]=

∑aj[∑ti∈ρ(A)q′ij]=∑aj∈Avj(A)

□

3 dMHAUI算法

3.1 4個優(yōu)化的上界

(2)

(3)

(4)

(5)

定義8項集C的diffset表示為d(C)，定義為d(C)=ρ(LP)ρ(C)，其中 “”是設(shè)定差異算子。如果C是1-項集，則：

d(C)=Dρ(C)

(6)

對于任何k-項集C(k≥2)，有：

d(C)=d(RP)d(LP)

(7)

在式(6)和式(7)的基礎(chǔ)上，本文提出了2個遞歸公式，用于基于向量V(LP)和d(C)快速計算V(C)。假設(shè)項集C是給定項集P的項擴展，minInd(P)=minInd(C)?；赿(C)和V(P),V(C)=(vj(C),j≥minInd(C))的值的遞歸計算如下所示：

(8)

(9)

若d(C)=?,則V(C)=V(P)。

證明項集P用項目aR擴展后得到項集C=PaR，因此minInd(P)=minInd(C)。對于任何j≥minInd(P)=minInd(C)，有ρ(C)=ρ(P)d(C)，ρ(P)包含ρ(C)和d(C)。因此，vj(C)=∑i:ti∈ρ(C)q′ij=∑i:ti∈ρ(P)q′ij-∑i:ti∈d(C)q′ij=vj(P)-∑i:ti∈d(C)q′ij。若d(C)=?，則vj(C)≡vj(P)即?j≥minInd(P)=minInd(C),V(C)=V(P)。

□

3.2 基于UBs的3步修剪策略

根據(jù)每個UB的修剪能力，本文設(shè)計了3步修剪策略。將P及其所有的擴展項集表示為branch(P)。[P]={Px,…,Py,…,Pz,…}表示由P的所有項擴展組成的具有相同前綴P的項集。對于任何UB，當(dāng)且僅當(dāng)ub(P)

3.3 算法流程

dMHAUI算法的偽代碼如算法1所示。首先計算出每個項目的效用值得到集成矩陣Q(算法的第1行)。其次掃描Q計算所有項目的效用向量V(φ)，進而計算數(shù)據(jù)庫中第j列項目a的列效用向量V(aj)和4個上界值，應(yīng)用強寬修剪策略得到集合[φ](算法的第2、3行)。最后，調(diào)用搜索函數(shù)得到高平均效用項集。

算法1dMHAUI

輸入：數(shù)據(jù)庫D，最小平均效用閾值mu。

輸出：高平均效用項集HAUS。

1 創(chuàng)建集成矩陣Q；

2 掃描集成矩陣Q，計算每個aj∈A*的向量V(φ)和V(aj)；

4HAUS=?；

5HAU-Search([φ],HAUS)；

6 returnHAUS；

函數(shù)HAU-Search的偽代碼如下所示：

FuctionHAU-Search([P],HAUS)

1 if([P]≠?)then{

2 for在[P]中的每個(Ci,d(Ci),V(Ci)) do{

4 if(au(Ci)≥mu)then

5 將(Ci,au(Ci))加入HAUS；

6 if(|[P]|>1)then{

7 [Ci]=?;

8 for在[P]中的每個(Cj,d(Cj),V(Cj)),當(dāng)j>ido{

9E=Ci∪Cj;d(E)=d(Cj)d(Ci);

10 計算V(E)；

12 [Ci]=[Ci]∪{(E,d(E),V(E))};

13 }

14HAU-Search([Ci],HAUS);

15 }

16 }

17 }

18 }

19 return；

4 仿真分析

4.1 仿真環(huán)境設(shè)置

為了驗證本文算法的性能，將dMHAUI算法與EHAUPM算法、MHAI算法進行仿真比較。仿真環(huán)境設(shè)置如下：在4 GB內(nèi)存的Intel(R)Core(TM)i5-6200U 2.3 GHz CPU的計算機上進行實驗，并運行64位的Windows 10，算法用C#語言實現(xiàn)。算法使用的數(shù)據(jù)庫及其特征如表1所示，合成數(shù)據(jù)庫中各參數(shù)的定義如表2所示。數(shù)據(jù)庫Chess[14]和Mushroom[14]是真實數(shù)據(jù)庫，數(shù)據(jù)庫T11I6N30D100K、T15I9N100D100K、T*I9N50D100K、T16I9N*D100K、T16I9N60D*K是使用IBM人工模擬數(shù)據(jù)生成器生成的合成數(shù)據(jù)庫[14,15]，數(shù)據(jù)庫中參數(shù)字母后的符號*表示該參數(shù)是可變的。

Table 1 Simulation databases

Table 2 Definition of synthetic database parameters

4.2 運行時間分析

圖1～圖4 顯示了dMHAUI算法、EHAUPM算法與MHAI算法運行時間隨最小平均效用閾值mu(%)的變化情況。

Figure 1 Runtime on Mushroom database圖1 數(shù)據(jù)庫 Mushroom上的運行時間

Figure 2 Runtime on Chess database圖2 數(shù)據(jù)庫Chess上的運行時間

Figure 3 Runtime on T11I6N30D100K database圖3 數(shù)據(jù)庫T11I6N30D100K上的運行時間

Figure 4 Runtime on T15I9N100D100K database圖4 數(shù)據(jù)庫T15I9N100D100K上的運行時間

如圖1～圖4所示，隨著最小平均效用閾值mu的增大，3種算法的運行時間都逐漸減少；且對于所有的最小平均效用閾值mu，dMHAUI算法通常比EHAUPM算法、MHAI算法快1～2個數(shù)量級。在最小平均效用閾值mu較小時,dMHAUI算法修剪效果更好，能盡早從搜索空間中修剪大量沒有可能成為高平均效用項集的項集，從而顯著提高算法的運行速度。

4.3 算法連接次數(shù)分析

圖5～圖8顯示了dMHAUI算法、EHAUPM算法與MHAI算法連接次數(shù)隨最小平均效用閾值mu(%)的變化情況。連接次數(shù)的數(shù)值表征了搜索空間的大小。從圖5和圖6可以看出，在Mushroom數(shù)據(jù)庫和Chess數(shù)據(jù)庫上，dMHAUI算法與MHAI算法的連接次數(shù)相差不大，但在低最小平均效用閾值時，都遠小于EHAUPM算法的連接次數(shù)；在T11I6N30D100K和T15I9N100D100K合成數(shù)據(jù)庫上，dMHAUI算法的連接次數(shù)遠小于MHAI算法和EHAUPM算法的連接次數(shù)，搜索空間顯著減小。在數(shù)據(jù)庫T15I9N100D100K上，當(dāng)mu從0.42%增加到0.9%時，dMHAUI算法執(zhí)行的連接次數(shù)比EHAUPM算法少96.8%，比MHAI算法少95.4%。

Figure 5 Number of join operations on Mushroom database圖5 數(shù)據(jù)庫 Mushroom上的連接次數(shù)

Figure 6 Number of join operations on Chess database圖6 數(shù)據(jù)庫Chess上的連接次數(shù)

Figure 7 Number of join operations on T11I6N30D100K database圖7 數(shù)據(jù)庫T11I6N30D100K上的連接次數(shù)

Figure 8 Number of join operations on T15I9N100D100K database圖8 數(shù)據(jù)庫T15I9N100D100K上的連接次數(shù)

4.4 可擴展性分析

圖9～圖11顯示了dMHAUI算法、EHAUPM算法與MHAI算法在不同最小平均效用閾值mu(%)下運行時間隨數(shù)據(jù)庫參數(shù)的變化情況。

Figure 9 Relationship between runtime and T on T*I9N50D100K database圖9 數(shù)據(jù)庫T*I9N50D100K上的運行時間與平均事務(wù)長度T的關(guān)系

Figure 10 Relationship between runtime and N on T16I9N*D100K database圖10 數(shù)據(jù)庫T16I9N*D100K上的運行時間與項目數(shù)量N的關(guān)系

Figure 11 Relationship between runtime and D on T16I9N60D*K database圖11 T16I9N60D*K數(shù)據(jù)庫上的運行時間與事務(wù)數(shù)D的關(guān)系

圖9表示隨著合成數(shù)據(jù)庫中平均事務(wù)長度T增加各算法運行時間的變化；圖10表示隨著合成數(shù)據(jù)庫中不同項目數(shù)量N增加各算法運行時間的變化；圖11表示隨著數(shù)據(jù)庫中事務(wù)數(shù)D增加各算法運行時間的變化。從圖9～圖11中可以看出，隨著相應(yīng)參數(shù)值的增加，dMHAUI算法的運行時間短且變化幅度小，較穩(wěn)定；但EHAUPM算法和MHAI算法的運行時間長且波動大。對比EHAUPM算法和MHAI算法，dMHAUI算法具有最佳的線性可伸縮性。

可見，對于各種最小平均效用閾值mu，dMHAUI算法在真實數(shù)據(jù)庫和合成數(shù)據(jù)庫上的運行時間、算法操作連接次數(shù)和擴展性都優(yōu)于EHAUPM算法和MHAI算法。

5 結(jié)束語

為進一步縮減高效用項集挖掘過程中項集搜索空間的大小，提高數(shù)據(jù)挖掘的效率，本文提出了dMHAUI算法?；诙繑?shù)據(jù)庫的垂直形式計算效用值的思想，提出了4個更緊湊的上界以及3種修剪策略，用于盡早消除沒有希望的候選項集；隨后，在高平均效用項集挖掘過程中，將平均效用值以及上限值存儲在IDUL結(jié)構(gòu)樹中，利用改進后的diffset技術(shù)快速計算項集的平均效用和上限；最后調(diào)用遞歸搜索函數(shù)得到HAUS集合。仿真表明，dMHAUI算法在真實數(shù)據(jù)庫和合成數(shù)據(jù)庫上的運行時間、連接次數(shù)和可擴展性等方面都有較優(yōu)的性能。未來工作的方向主要是將提出的剪枝策略擴展到定量序列數(shù)據(jù)庫中，以挖掘所有的高效用序列，提高高效用序列挖掘效率。