基于優(yōu)化上界的高平均效用項(xiàng)集垂直挖掘算法*

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

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

1 引言

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

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

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

2 模型

2.1 定義

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

當(dāng)挖掘定量數(shù)據(jù)庫以找到高效用模式時(shí)，為了避免重復(fù)計(jì)算在事務(wù)ti中的每個(gè)q-項(xiàng)目(aj,qij)的效用u(aj,qij)=qij*p(aj)，把每個(gè)q-項(xiàng)目的效用計(jì)算一次并存儲在轉(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定義如下：

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

定義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時(shí)，項(xiàng)集A稱為高平均效用HAU(High Average-Utility)；否則，稱為低平均效用LAU(Low Average-Utility)。因此，高平均效用項(xiàng)集挖掘是找到所有的HAUS={A∈LS|au(A)≥mu}集合。

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

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

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

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

引理1對于每個(gè)項(xiàng)集:

(1)

證明

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

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

□

3 dMHAUI算法

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

(2)

(3)

(4)

(5)

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

d(C)=Dρ(C)

(6)

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

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

(7)

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

(8)

(9)

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

證明項(xiàng)集P用項(xiàng)目aR擴(kuò)展后得到項(xiàng)集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ù)每個(gè)UB的修剪能力，本文設(shè)計(jì)了3步修剪策略。將P及其所有的擴(kuò)展項(xiàng)集表示為branch(P)。[P]={Px,…,Py,…,Pz,…}表示由P的所有項(xiàng)擴(kuò)展組成的具有相同前綴P的項(xiàng)集。對于任何UB，當(dāng)且僅當(dāng)ub(P)

3.3 算法流程

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

算法1dMHAUI

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

輸出：高平均效用項(xiàng)集HAUS。

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

2 掃描集成矩陣Q，計(jì)算每個(gè)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]中的每個(gè)(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]中的每個(gè)(Cj,d(Cj),V(Cj)),當(dāng)j>ido{

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

10 計(jì)算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è)置

為了驗(yàn)證本文算法的性能，將dMHAUI算法與EHAUPM算法、MHAI算法進(jìn)行仿真比較。仿真環(huán)境設(shè)置如下：在4 GB內(nèi)存的Intel(R)Core(TM)i5-6200U 2.3 GHz CPU的計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)，并運(yùn)行64位的Windows 10，算法用C#語言實(shí)現(xiàn)。算法使用的數(shù)據(jù)庫及其特征如表1所示，合成數(shù)據(jù)庫中各參數(shù)的定義如表2所示。數(shù)據(jù)庫Chess[14]和Mushroom[14]是真實(shí)數(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 運(yùn)行時(shí)間分析

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

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

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

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

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

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

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

圖5～圖8顯示了dMHAUI算法、EHAUPM算法與MHAI算法連接次數(shù)隨最小平均效用閾值mu(%)的變化情況。連接次數(shù)的數(shù)值表征了搜索空間的大小。從圖5和圖6可以看出，在Mushroom數(shù)據(jù)庫和Chess數(shù)據(jù)庫上，dMHAUI算法與MHAI算法的連接次數(shù)相差不大，但在低最小平均效用閾值時(shí)，都遠(yuǎn)小于EHAUPM算法的連接次數(shù)；在T11I6N30D100K和T15I9N100D100K合成數(shù)據(jù)庫上，dMHAUI算法的連接次數(shù)遠(yuǎn)小于MHAI算法和EHAUPM算法的連接次數(shù)，搜索空間顯著減小。在數(shù)據(jù)庫T15I9N100D100K上，當(dāng)mu從0.42%增加到0.9%時(shí)，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 可擴(kuò)展性分析

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

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

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

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

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

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

5 結(jié)束語

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