挖掘意外高效用項(xiàng)集的有效方法

王 斌,姚銀鳳,周 偉,胡克勇

(青島理工大學(xué)信息與控制工程學(xué)院,山東 青島 266000)

1 引言

頻繁模式挖掘(Frequent Patterns Mining,FPM)[1]作為關(guān)聯(lián)規(guī)則[2]的一種具有代表性的方法,它因能夠有效的找到模式之間的關(guān)系而被應(yīng)用于各種現(xiàn)實(shí)問題。然而,傳統(tǒng)的頻繁模式挖掘[3]有一定的局限性。數(shù)據(jù)庫項(xiàng)目不僅包括頻率,還包括真實(shí)世界中的獨(dú)特利潤,這意味著頻繁的模式挖掘不能反映現(xiàn)實(shí)世界的問題[4]。例如,數(shù)據(jù)庫中有由鉆石和杯子組成的事務(wù)。杯子比鉆石有更高的頻率,但鉆石的利潤高于幾萬個杯子,即鉆石比杯子更有價(jià)值。為了克服這一缺點(diǎn),提出了高效用項(xiàng)集挖掘(High Utility Itemstes Mining,HUIM)[5]。HUIM是一種流行的數(shù)據(jù)挖掘方法,用于發(fā)現(xiàn)客戶事務(wù)數(shù)據(jù)庫中的有用模式。它包括發(fā)現(xiàn)產(chǎn)生高效用(高利潤)的項(xiàng)集,即高效用項(xiàng)集(HUIs)。除了客戶交易分析外,HUIM在其它領(lǐng)域也有應(yīng)用,如點(diǎn)擊流分析和生物醫(yī)學(xué)[6]等。HUIM可以看作是頻繁項(xiàng)集挖掘問題的擴(kuò)展,其中單位利潤可以分配給每一個項(xiàng)目。然而傳統(tǒng)的高效用項(xiàng)集挖掘在計(jì)算上具有很大的挑戰(zhàn)性,這是由于其缺乏傳統(tǒng)的頻繁項(xiàng)集挖掘中的反單調(diào)特性。傳統(tǒng)的HUIM算法還會產(chǎn)生大量的模式,對于用戶來說分析大量的模式是困難和耗時(shí)的。此外,隨著發(fā)現(xiàn)的模式的增多,HUIM算法的運(yùn)行時(shí)間會變長,消耗的內(nèi)存也越來越多。因此,高效的HUIM算法需要設(shè)計(jì)新的數(shù)據(jù)結(jié)構(gòu)來提高算法性能。近年來提出的HUI-Miner算法[7]采用了效用列表的數(shù)據(jù)結(jié)構(gòu),一定程度提高了運(yùn)行效率,但由于傳統(tǒng)的效用列表占用內(nèi)存過大,不適用于大型的數(shù)據(jù)集。最近提出的ULB-miner算法[8]采用了效用列表-緩沖區(qū)結(jié)構(gòu),能夠有效地存儲和檢索效用列表,但隨著大量模式的產(chǎn)生也會導(dǎo)致運(yùn)行時(shí)間長及內(nèi)存消耗大等問題。因此,有必要尋找一個更小的集合來挖掘高效用項(xiàng)集。

本文提出了一種挖掘意外高效用項(xiàng)集的算法,使用的UHUI-list數(shù)據(jù)結(jié)構(gòu)能更加緊湊的存儲項(xiàng)集的有效信息,并通過列表的重構(gòu)及相互結(jié)合來進(jìn)行挖掘工作。本文提出的UHUI-Prune策略能夠有效減少搜索空間,最終尋找到特定子組中所有有意義的高效用項(xiàng)集。最終實(shí)驗(yàn)結(jié)果表明該算法性能優(yōu)于當(dāng)前先進(jìn)的算法。

本文第2節(jié)介紹了的問題定義;第3節(jié)主要介紹了UHUI-list的構(gòu)造和剪枝策略;第4節(jié)介紹了提出的UHUIM算法;第5節(jié)在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)并對結(jié)果進(jìn)行分析;第6節(jié)進(jìn)行總結(jié)與展望。

2 問題定義

本文目標(biāo)是在表格式多維數(shù)據(jù)的事務(wù)維度子組中挖掘意外高效用項(xiàng)集。在本節(jié)中介紹意外[9]項(xiàng)集(Unexpected Itemsets, UI)及意外高效用項(xiàng)集的相關(guān)問題定義。

2.1 意外項(xiàng)集相關(guān)概念

多維表格數(shù)據(jù)集D由一組元組(也稱為行或事務(wù))組成,其中每個元組t都有一列稱為唯一的元組ID(由TID表示),其它則是稱為屬性的列(由A={a1,a2,…,an}表示)。每個屬性ai都有其值域Rg(ai),見表1。

表1 某商品購買實(shí)例(其中n=no,y=yes)

D的多維項(xiàng)是一對(ai,vi)對,其中vi是Rg(ai)中可能的值。由Im表示的m級多維項(xiàng)集,它不包含重復(fù)屬性。從形式上講,有

Im={(ai1,vi1),…,(aim,vim)}

(1)

D上的多維項(xiàng)集Im的支持度被定義為包含Im的D中元組的百分比。例如,表1中多維項(xiàng)集I0={(season,spring)}的支持度為sup(I0)=0.2。下面需要研究D的切片上多維項(xiàng)集的支持度。給定用戶指定的最小支持度閾值min＿sup,如果sup(Im)>min＿sup,則多維項(xiàng)集Im在D上是頻繁的。

定義1:D的子組定義為k個多維對的結(jié)合,即S(k)={(ai1,vi1),…,(aik,vik)},子組中的屬性值稱為固定屬性值(FVs)。

定義2:給定固定的k個屬性值,通過S(k)中指定的多維對對D執(zhí)行關(guān)系選擇來獲得S(k)的切片[10]。切片中非固定的屬性值稱為可變屬性值(VVs)。

slice(S(k))=σ(S(k))

(2)

例如表1的子組S(1)={(season=winter)}的切片為一個包含TID={7,8,9,10}4個元組的子集,見表2。

表2 S=(season=winter). winter是一個FV

給定一個子組S(k),在后續(xù)對多維項(xiàng)集Im的探索中,不進(jìn)一步考慮S(k)中的FVs。為簡單起見,將在余文用S表示一個子組。

子組的覆蓋范圍為切片中的元組在整個數(shù)據(jù)集D中的百分比,表示為

cov(S)=|slice(S)|/|D|

(3)

如果一個子組的覆蓋范圍不小于最小閾值min＿cov,則該子組是重要的。如果不存在滿足S?S′的重要的子組S′,則S是最大的重要子組。

定義3:給定min＿sup和min＿cov,數(shù)據(jù)集D上的意外項(xiàng)集(UI)被定義為〈子組,多維項(xiàng)集〉對,由表示,其中多維項(xiàng)集Im在D上不頻繁,但在S上頻繁,其中S是D的一個重要子組。

給定min＿sup=0.5和min＿cov=0.2,很容易看出I1={(buy,y)}在原始數(shù)據(jù)集D(見表1)上不頻繁,但在子組S1={(season=winter)}的切片(見表2)上頻繁。因此,是D上的一個意外項(xiàng)集。

通過對D進(jìn)行切片操作而獲得的子集被稱為參考數(shù)據(jù)集D′。

定義4:給定一個min＿sup,min＿cov和D′=R(S),更具體地說,D′=R(S)=slice(S)。一個D′上的意外項(xiàng)集(UI)由表示,其中多維項(xiàng)集Im在D′上不頻繁,但在S上頻繁,其中S是D′的一個重要子組。

問題1:給定一個多維數(shù)據(jù)集D,一個用戶指定的子組S,兩個用戶指定的閾值min＿sup和min＿cov,在對D進(jìn)行切片操作獲得的D′=R(S)上找到所有意外的項(xiàng)集。

在D′=R(S)上,S={(season=winter)}。如果在D′上再執(zhí)行切片操作,取S={(worked=n)},可得D′的切片,見表3。

表3 D′=R(S)的切片S={(worked=n)}

2.2 意外高效用項(xiàng)集相關(guān)概念

本小節(jié)定義了意外高效用項(xiàng)集的相關(guān)術(shù)語?？梢姳? 中包含十個事務(wù)(Transaction,T),每個事務(wù)中包含一系列的項(xiàng)。其中項(xiàng)的頻率是項(xiàng)的內(nèi)部效用,用IU表示,見表4。項(xiàng)具有獨(dú)特的利潤,稱為外部效用[11],用EU表示,見表5。

表4 運(yùn)行數(shù)據(jù)集D上的事務(wù)和項(xiàng)

表5 項(xiàng)的單位利潤表

在D′上,取事務(wù)一維進(jìn)行挖掘,其中I={I1,I2,…,Id}是一組不同的項(xiàng),事務(wù)Tj={xn∣n=1,2,3,…,Nj,xn∈I},其中Nj是事務(wù)Tj中項(xiàng)的數(shù)量。事務(wù)數(shù)據(jù)庫D有一組事務(wù),D={T1,T2,…,Tj},其中j是數(shù)據(jù)庫中的事務(wù)總數(shù)。

定義5:xj∈Tj的效用,表示為U(xj,Tj),計(jì)算為事務(wù)中項(xiàng)的外部和內(nèi)部效用的乘積。即

U(xi,Tj)=IU(xi,Tj)*EU(xi)

(4)

定義6:數(shù)據(jù)庫中的一個子項(xiàng)集X的效用表示為U(X)。U(X,Tj)為項(xiàng)集X在事務(wù)Tj中的效用。

(5)

定義7:事務(wù)Tj的事務(wù)效用,表示為TU(Tj),定義為

(6)

定義8:項(xiàng)集X的事務(wù)加權(quán)效用[12]表示為TWU(X),定義為

(7)

定義9:最小意外效用閾值表示為uminutil,它的計(jì)算方式為數(shù)據(jù)庫D的總效用和用戶定義的百分比值δ的乘積。

(8)

在本文中,表3僅包含T7,T9,T10三個事務(wù),若給定δ=24%,則uminutil=24%*(16+18+19)=12.72。

問題2:給定一個多維數(shù)據(jù)集D,一個用戶指定的子組S,三個用戶指定的閾值min＿sup,min＿cov和uminutil,在D′=R(S)上找到所有意外的項(xiàng)集,并在意外項(xiàng)集的事務(wù)一維中找到項(xiàng)的效用值大于uminutil的1-高效用項(xiàng)集,即意外高效用項(xiàng)集(Unexpected High Utility Itemset,UHUI),并通過構(gòu)造UHUI-list存儲m-項(xiàng)集的有效信息,最終經(jīng)過UHUI-Prune策略得到所有的意外高效用項(xiàng)集。

定義10:如果項(xiàng)集X的效用大于等于最小意外效用閾值,則X為意外高效用項(xiàng)集,否則舍棄。

U-U(X)≥uminutil

(9)

例如,在表3中,U-U(f)=3<12.72,因此1-項(xiàng)集f不是意外高效用項(xiàng)集。

性質(zhì)1:對于任意的意外高效用項(xiàng)集X,都存在其超集X′,使得TWU(X′)≤TWU(X)。

證明:設(shè)X′為項(xiàng)集X的超集,由先驗(yàn)屬性[6]知

sup(X′)

∵U(X′)

得證。

性質(zhì)2若項(xiàng)集X不是意外高效用項(xiàng)集,則其超集X′也不會是意外高效用項(xiàng)集。

證明:略。

3 基于UHUI-lists的UHUIs挖掘

本節(jié)介紹提出的UHUI-list數(shù)據(jù)結(jié)構(gòu)以及UHUI-Prune策略來更有效地挖掘意外高效用項(xiàng)集。

3.1 UHUI-list的組成及構(gòu)造

本文提出了一個新的數(shù)據(jù)結(jié)構(gòu)UHUI-list來更緊湊的存儲有效的項(xiàng)集信息,該列表包含一系列元組,一個元組包含了該項(xiàng)集所存在的事務(wù)的信息。利用UHUI-lists來挖掘意外高效用項(xiàng)集。

3.1.1 相關(guān)概念

定義11:在一個事務(wù)Tj中,最大效用就是事務(wù)T中所包含的項(xiàng)效用的最大值,記為umax(Tj)。

umax(Tj)=max({u(xi,Tj)|xi∈Tj})

(10)

定義12:對于項(xiàng)集X,包含X的所有事務(wù)的最大效用之和稱為效用上限[13],記為uUB(X)。

(11)

定義13:事務(wù)Tj中項(xiàng)集X的剩余效用[14]記為RU(X,Tj)。

(12)

其中Tj/X表示為在事務(wù)Tj中位于項(xiàng)集X后的所有項(xiàng)的集合。例如,在表3中,RU(ad,T7)=3。

數(shù)據(jù)庫D中項(xiàng)集X的剩余效用記為:RU(X)。

(13)

3.1.2 UHUI-list構(gòu)造過程

項(xiàng)集X的UHUI-list記為UL(X),由UL(X).TWU和n個UL(X).tuplen兩部分組成。UL(X).tuplen由以下三部分組成:事務(wù)標(biāo)識符TID;項(xiàng)效用U,表示為UL(X).tuplen.u;剩余效用RU,表示為UL(X).tuplen.ru。UHUI-list的創(chuàng)建過程如下:

1)掃描D′的切片S={(worked=n)}并讀取第一個事務(wù)T7。由表3可知,T7={a,c,d,f},從a項(xiàng)開始創(chuàng)建UL(a)。RU值初始化為0。將UL(a).tupleT7附加到UL(a),UL(a).tupleT7可表示為<7,5,0>。然后以同樣的過程創(chuàng)建UL(c)等;

2)按照上述過程依次對T9,T10創(chuàng)建UHUI-list,直至所有事務(wù)的所有項(xiàng)構(gòu)建完,見表6。

表6 構(gòu)建UL(a)、UL(c)和uUB表

3)對所有的事務(wù)中的各項(xiàng)創(chuàng)建完UHUI-list之后,由定義8可得a、c、d、f的TWU值,由定義12可得uUB表。見表6。

3.1.3 UHUI-list重構(gòu)

UHUI-list創(chuàng)建完成后,重構(gòu)過程如下:

1)對上述創(chuàng)建UHUI-list的所有項(xiàng)按照uUB升序排序,結(jié)果為:f?d?a?c,根據(jù)uUB升序?qū)Ρ?重新進(jìn)行排序,見表7。

表7 按uUB升序排序后的S={(worked=n)}

2)由f?d?a?c的最后一項(xiàng)c開始重構(gòu)UHUI-list,由表7可重新計(jì)算RU值。在此過程中,各項(xiàng)的TWU值不變。RU值計(jì)算完成后,重構(gòu)過程結(jié)束,見表8。

表8 重構(gòu)的UL(a)、UL(c)和uUB表

3.2 剪枝策略及挖掘過程

當(dāng)前的UHUI-lists包含按照uUB升序排序的1-項(xiàng)集,挖掘過程從含有最小uUB值的UHUI-list開始。

3.2.1UHUI-Prune策略

本文提出UHUI-Prune策略,即在用戶定義固定屬性值下得到的意外高效用項(xiàng)集的數(shù)據(jù)集DU上進(jìn)行剪枝,該策略主要分四步進(jìn)行剪枝:

剪枝1(U-TWU剪枝)在數(shù)據(jù)集DU上,若TWU(X)

剪枝2(U-uUB剪枝)在數(shù)據(jù)集DU上,若uUB(X)

剪枝3(U-EUCS′剪枝)在數(shù)據(jù)集DU上,若EUCS(X)

剪枝4(U-U剪枝)在數(shù)據(jù)集DU上,若RU(X)+U(X)

由UHUIs定義以及上述剪枝可知d,f兩項(xiàng)不是UHUIs,由于d,f不滿足U-TWU剪枝,故其擴(kuò)展項(xiàng)有可能為UHUIs,但f項(xiàng)滿足U-uUB剪枝,故剪枝掉f項(xiàng)。

3.2.2 從UHUI-lists中挖掘UHUIs

下面介紹UL(Xi)相互結(jié)合的過程步驟:假設(shè)重構(gòu)后的項(xiàng)集排序?yàn)?X1?X2?X3?…?Xi。

1)檢查X1是否為意外高效用項(xiàng)集,如果U(Xi)≥uminutil,則Xi為意外高效用項(xiàng)集;

2)檢查X1的超集是否為意外高效用項(xiàng)集:若TWU(X1)≥uminutil,則X1的超集可能為意外高效用項(xiàng)集。經(jīng)U-TWU剪枝策略過濾后,將剩下的項(xiàng)進(jìn)行U-uUB剪枝,若uUB(X1)≥uminutil,則繼續(xù)對X1進(jìn)行挖掘;

3)對X1進(jìn)行列表結(jié)合。首先與下一項(xiàng)X2進(jìn)行結(jié)合產(chǎn)生X1X2,具體結(jié)合過程如下:先將UL(X1)與UL(X2)中具有相同TID的元組進(jìn)行結(jié)合。假設(shè)X1和X2出現(xiàn)在同一個事務(wù)Tm中,則生成一組列表UL(X1X2).tupleTm;其次UL(X1X2).tupleTm.u的計(jì)算分為兩種情況:

第一種,如果X1X2沒有共同前綴,則

UL(X1X2).tupleTm.u

=UL(X1).tupleTm.u+UL(X2).tupleTm.u

(14)

第二種,如果X1X2有共同前綴X0,則

UL(X1X2).tupleTm.u=UL(X1).tupleTm.u

+UL(X2).tupleTm.u-UL(X0).tupleTm.u

(15)

接下來UL(X1X2).tupleTm.ru的計(jì)算如下

(16)

并對于X1X2的每個元組都執(zhí)行上述過程;最后計(jì)算UL(X1X2).TWU:X1X2的TWU值為其所在共同事務(wù)中的事務(wù)效用之和;

4)在將兩個UHUI-lists的元組組合起來后,下面將計(jì)算X1X2是否可擴(kuò)展挖掘:先計(jì)算U-U(X1X2),如果U-U(X1X2)≥uminutil則X1X2為意外高效用項(xiàng)集;其次若EUCS(X1X2)≥uminutil,則X1X2的超集可能為意外高效用項(xiàng)集。

從X1到Xi重復(fù)上述所有過程以進(jìn)行UHUI-lists的結(jié)合。如果生成具有前綴X1組合的UHUI-lists,則對這些組合的UHUI-lists執(zhí)行挖掘過程,運(yùn)用剪枝4:U-U剪枝。這個過程將遞歸地重復(fù),直到基于最后一個項(xiàng)集的組合過程結(jié)束。最終挖掘結(jié)果為:j5i0abt0b,{dc},{dac},{a},{ac}和{c}為意外高效用項(xiàng)集。部分結(jié)果見表9。

表9 UL(dc)及UL(dac)

4 UHUIM算法

本節(jié)介紹UHUIM算法的偽代碼。對于D的任何給定的切片,用(S,I)all表示切片S上所有意外項(xiàng)集的集合。

Algorithm 1(UHUIMmainalgorithm)

1)K=1

2)生成候選的1-Mitemsets集合I-1

3)基于I1生成重要的1-subgroups集合S1

4)Repeat

5)Sk+1=?

6)for all significant k-subgroup S∈Skdo

8)Sk+1. add All(Snew)

9) K=k+1

10)untilSk=?

11)kmax=k-1

12)for k=kmax-1 to1 do

13) for allsignificant k-subgroupS∈Skdo

15)?I ∈(S,I)all,return (S,I) as 意外項(xiàng)集

16)將(S,I)存入集合(S,I)all中 ∥(S,I)all用于保存所有的意外項(xiàng)集

17)Generate＿UHUIs((S,I)all,uminutil);∥生成意外高效用項(xiàng)集

18)End

Algorithm 2 (Generate＿UHUIS)

Input:所有的意外項(xiàng)集(S,I)all

用戶指定的最小效用閾值uminutil

Output:A list of unexpected high utility itemsets

A set of UHUI-lists of

1-length itemsets,UHUI-lists

2)A set of unexpected high utility itemsets,Result-Set

3)A table of upper bound of

1-length itemsets, uUB

4)Foreach 意外項(xiàng)集(S,I) ∈(S,I)all

5)For each 事務(wù)Transaction∈(S,I)

6)Foreach i in Transaction

7)If i not in UHUI-lists

8) insert i into UHUI-lists

9) Else

10) Update entry of I in UHUI-lists ∥更新UHUI-list

11) Calculate umaxof T and update uUB

12)Restructure(UHUI-lists, uUB)∥重構(gòu)UHUI-lists

13) If user requests mining ∥如果用戶請求挖掘

14)Mining(NULL,UHUI-lists,uminutil,Result-Set)∥執(zhí)行挖掘操作

15) Return Result-Set∥返回意外高效用項(xiàng)集

5 實(shí)驗(yàn)

在本節(jié)中,評估了該挖掘方法的性能。為了客觀地比較方法,UHUIM算法與當(dāng)前最先進(jìn)的兩個算法ULB-Miner以及HUI-Miner進(jìn)行對比評估。

5.1 實(shí)驗(yàn)設(shè)置

所有的算法都是由Java編程語言實(shí)現(xiàn)的。PC環(huán)境包括32GB內(nèi)存、4.00GHzCPU和Window10(64位)操作系統(tǒng)。本文在3個真實(shí)數(shù)據(jù)集上評估三個算法的運(yùn)行時(shí)間、內(nèi)存使用及可伸擴(kuò)展性性能。所有數(shù)據(jù)集均可從SPMF庫[15]下載。數(shù)據(jù)集特征見表10。

表10 數(shù)據(jù)集特征

5.2 對運(yùn)行時(shí)間性能的評估

本節(jié)比較了UHUIM,ULB-Miner及HUI-Miner三種算法在3個真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間性能。對于小型稠密的數(shù)據(jù)集chess,當(dāng)uminutil為3500000左右時(shí),UHUIM算法比ULB-miner算法的運(yùn)行時(shí)間快一個左右數(shù)量級,當(dāng)uminutil越小,運(yùn)行時(shí)間越長。實(shí)驗(yàn)結(jié)果表明,3種算法的運(yùn)行速度由快到慢為:UHUIM>ULB-Miner>HUI-Miner。見圖1(a)-(c)。

圖1 在不同uminutil值下的運(yùn)行時(shí)間性能

5.3 對內(nèi)存使用性能的評估

本小節(jié)對三種算法進(jìn)行內(nèi)存性能評估。大中型數(shù)據(jù)集chainstore及connect高于chess的內(nèi)存使用。對于chainstore,在uminutil=1000000時(shí),ULB-Miner算法比UHUIM算法的內(nèi)存使用多大約5倍,HUI-Miner算法使用內(nèi)存約為UHUIM算法的3.7倍。實(shí)驗(yàn)結(jié)果表明,UHUIM算法的內(nèi)存消耗低于其它兩種算法。見圖2(d)-(f )。

圖2 在不同uminutil值下的內(nèi)存使用性能

5.4 對可伸縮性的評估

由圖1、2可知,UHUIM算法在大小不同的3個數(shù)據(jù)集上運(yùn)行時(shí)間差別不大,內(nèi)存性能也高于其它兩個算法。因此,UHUIM算法在各個數(shù)據(jù)集上的可伸縮性均優(yōu)于ULB-Miner算法及HUI-Miner算法。

6 結(jié)束語

本文提出的UHUIM算法能夠有效的挖掘意外高效用項(xiàng)集,給經(jīng)營者帶來意想不到的利潤。本文采用新提出的UHUI-list結(jié)構(gòu)更緊湊的存儲項(xiàng)集信息,節(jié)省時(shí)間與空間。本文提出的UHUI-Prune策略能夠有效的減少搜索空間,提高挖掘效率。經(jīng)過在3個真實(shí)數(shù)據(jù)集上進(jìn)行運(yùn)行時(shí)間、存儲空間及可伸縮性的實(shí)驗(yàn)評估,結(jié)果表明本文提出的UHUIM算法性能優(yōu)于ULB-Miner算法及HUI-Miner算法。

在未來的工作中計(jì)劃調(diào)整UHUI-list為UHUI-list-緩沖區(qū)結(jié)構(gòu),并研究在動態(tài)數(shù)據(jù)庫中挖掘意外高效用項(xiàng)集的有效方法。