王 斌，周 偉，李曉華，胡克勇

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

0 引 言

在數(shù)據(jù)挖掘中，高效用項集挖掘算法是一項重要的研究課題[1-6]。然而，高效用項集挖掘算法的輸出結(jié)果中，只包含項集的組成項及效用信息。決策者很難從中獲取到其它信息，例如高效用項集中每個項的數(shù)量區(qū)間，導(dǎo)致無法做出精確的決策。

為解決這一問題，模糊集理論引入到了高效用項集挖掘中，產(chǎn)生了高模糊效用項集挖掘算法。HFUI-GA[7]將進化計算方法引入了高模糊效用項集挖掘中。EFUPM[8]算法提出了緊密的模糊效用上界模型，有效減少了搜索空間。

上述高模糊效用項集挖掘算法，均需要事先確定最小模糊效用閾值，再去挖掘模糊效用值不小于閾值的高模糊效用項集(high fuzzy utility itemset，HFUI)。然而，閾值的設(shè)定并非易事。如果閾值設(shè)置太低，會輸出大量的HFUI；如果閾值設(shè)置太高，會產(chǎn)生極少的HFUI。用戶都不能從結(jié)果中發(fā)現(xiàn)真正有用的項集。通常，研究人員會多次更換閾值，重復(fù)運行算法，直至找到最合適的閾值。顯然，這種方法很不高效。為解決閾值選擇的難題，受Top-k高效用項集挖掘算法的啟發(fā)[9-15]，本文將設(shè)定閾值的問題轉(zhuǎn)化成設(shè)定所需高模糊效用項集數(shù)量k的問題，提出了Top-k高模糊效用項集挖掘TKHFU。該算法設(shè)計了一種模糊項集效用列表結(jié)構(gòu)，避免了項集間復(fù)雜的連接過程；提出了兩種有效的剪枝策略Afu-Prune和FI-Prune，并將兩種剪枝策略與列表結(jié)構(gòu)進行結(jié)合，減少了無意義項集列表的構(gòu)建，提升了算法的性能。

1 相關(guān)定義

給定一個含有m個不同項的有限項集合I={i1，i2，i3，…，im}，稱此集合為m-項集。設(shè)含有n條事務(wù)的定量事務(wù)數(shù)據(jù)庫D={T1，T2，T3，…，Tn}，任意事務(wù)Ty(1≤y≤n) 是I的一個子集。任意項iz∈Ty，有一個內(nèi)部效用q(iz，Ty) (數(shù)量)，外部效用p(iz) (單元利潤)。一個定量事務(wù)數(shù)據(jù)庫如表1所示，其各項單元利潤見表2。本研究中，對表1中的各項使用相同的隸屬函數(shù)，均有3個模糊域，分別為低(L)、中(M)、高(H)。

表1 定量事務(wù)數(shù)據(jù)庫

表2 單元利潤

定義1[8］第y條事務(wù)Ty中第z項iz的數(shù)量vyz的模糊集用fyz表示，可由給定的隸屬函數(shù)描述為

(1)

其中，h是項iz的隸屬函數(shù)(模糊域或語義術(shù)語)的數(shù)量，Rzl是項iz的第l模糊域，fyzl是第z項的數(shù)量vyz在第l模糊域Rzl的模糊隸屬度，且fyzl∈[0，1]。

例如，表1中T4的項B的數(shù)量(=4)可以由圖1中隸屬函數(shù)轉(zhuǎn)換成f4，B=(0.4/B.L，0.6/B.M，0/B.H)。

圖1 隸屬函數(shù)

定義2 事務(wù)Ty中項iz的效用，是其數(shù)量和單元利潤的乘積，用u(iz，Ty) 表示，定義為

u(iz，Ty)=q(iz，Ty)×p(iz)

(2)

定義3[8］事務(wù)Ty中項iz的第l模糊域的模糊效用，用fuyzl表示，定義為

fuyzl=fyzl×u(iz，Ty)

(3)

例如，由表1、表2和圖1可知，表1的T2中項A的數(shù)量為2，單元利潤為1，A的第一個模糊域A.L的隸屬度為0.8，則fu2，A.L=0.8×2×1=1.6。按此計算方式，我們計算出了表2中所有項的各模糊域的模糊效用，見表3。

表3 定量事務(wù)數(shù)據(jù)庫中各項模糊域的模糊效用

定義4[8］事務(wù)Ty中模糊項集X的模糊效用fuyX是X中所有模糊項的模糊效用之和，定義為

(4)

在模糊項集X中，模糊項fizl是指，帶有第l模糊域的項iz。值得注意的是，模糊項集中的模糊項，只能來自不同的離散項。

例如，設(shè)X={A.L，C.M}，模糊項A.L和C.M分別來自項A和C。由表3可知，事務(wù)T2中X的兩個模糊項的模糊效用分別為1.6和20，則fu2，X=1.6+20=21.6。

定義5 模糊項集X的實際模糊效用，用afuX表示，是事務(wù)數(shù)據(jù)庫D中所有包含IX的事務(wù)中的X的模糊效用總和，定義為

(5)

其中，IX是模糊項集X的原始離散項集。例如，設(shè)X={A.L，C.M}，則其IX={A，M}。由表3可知，模糊項集X的實際模糊效用為：afuX=fu2，X+fu4，X+fu5，X=(1.6+20)+(1.8+30)+(1.6+20)=75。

定義6 由用戶預(yù)設(shè)一個最小模糊效用閾值，用min_futil表示。模糊項集X是高模糊效用項集，當(dāng)且僅當(dāng)afuX≥min_futil。用HFUI表示高模糊效用項集。

現(xiàn)有高模糊效用項集挖掘算法，需先設(shè)置最小模糊效用閾值min_futil，再去挖掘?qū)嶋H模糊效用值不小于min_futil的HFUI。然而，閾值的設(shè)定并不容易。如果閾值設(shè)置得太低，將會產(chǎn)生大量的HFUI，用戶很難去發(fā)現(xiàn)真正有趣的項集，算法的性能也會嚴(yán)重衰減，同時會消耗大量的內(nèi)存。而如果閾值設(shè)置得太高，算法將產(chǎn)生很少的HFUI，用戶同樣也無法發(fā)現(xiàn)有趣的項集。通常，研究人員采用試錯的方法。即，不斷更換閾值，重復(fù)算法，直至找到最合適的閾值。顯然，這種方法是不高效的。

鑒于上述問題，本文借鑒了Top-k高效用項集挖掘算法的思想[9-15]，將設(shè)定min_futil的問題轉(zhuǎn)化成設(shè)定所需高模糊效用項集數(shù)量k的問題，提出了Top-k高模糊效用項集挖掘的概念，如下定義7。

定義7 給定一個定量事務(wù)數(shù)據(jù)庫D及用戶指定的正整數(shù)k，Top-k高模糊效用項集挖掘，記作TKHFU，旨在發(fā)現(xiàn)前k個具有最大模糊效用的模糊項集。

定義8[8］事務(wù)Ty中，項iz的最大模糊效用定義為

mfuyz=max{fuyz1，fuyz2，…，fuyzl}

(6)

其中，fuyzk(1≤k≤l) 是事務(wù)Ty中項iz的第k模糊域的模糊效用。例如，由表3可知，事務(wù)T4中，項B的最大模糊效用mfu4，B=max{fu4，B.L，fu4，B.M，fu4，B.H}=19.2。

定義9[8］事務(wù)Ty中模糊項集X的項集最大事務(wù)模糊效用，用imtfuyX表示，定義為

(7)

例如，設(shè)X={A.L，C.M}，由表3可知，X在T4中的項集最大事務(wù)模糊效用為：imtfu4，X=fu4，X+mfu4，B=(1.8+30)+19.2=51。

定義10[8］模糊項集X的項集模糊效用上界，用ifuubX表示，是數(shù)據(jù)庫D中所有包含IX的事務(wù)中X的項集最大事務(wù)模糊效用的總和，定義為

(8)

例如，設(shè)X={A.L，C.L}，其IX={A，C}。由表3可知，X的項集模糊效用上界為：ifuubX=imtfu2，X+imtfu4，X+imtfu5，X=34.2。

定義11 給定一個有限項的集合I={i1，i2，i3，…，im}，設(shè)是作用于I中的排序符號。令I(lǐng)中的項按字典順序升序排序，即i1i2i3…im。設(shè)模糊項集X的離散項集IX={x1，x2，x3…，xL}?Ty，其中x1x2…xL，Ty?I。將Ty排序后，若存在ij∈Ty且滿足xkij，k∈(1，L)，則將Ty中出現(xiàn)在IX之后的項集稱作IX的剩余項集，記作Ty/IX。

例如，表1中項的順序為ABC，T4={A，B，C}，設(shè)IX={B}，則IX剩余項集Ty/IX={C}。

定義12 事務(wù)Ty中模糊項集X的最大剩余模糊效用，記作mrfuyX，定義為

(9)

例如，設(shè)X={A.L，B.L}，其IX={A，B}。由表3可知，在事務(wù)T4中T4/IX={C}，則X在T4中的最大剩余模糊效用為：mrfu4，X=mfu4，C=30。

定義13 事務(wù)Ty中模糊項集X的最大事務(wù)模糊效用等于其模糊效用與最大剩余模糊效用之和，記作mtfuyX，定義為

mtfuyX=fuyX+mrfuyX

(10)

例如，設(shè)X={B.L}，其IX={B}。由表3可知，在事務(wù)T4中T4/IX={C}，則X的最大事務(wù)剩余模糊效用為：mtfu4，X=fu4，X+mrfu4，X=fu4，X+mfu4，C=12.8+30=42.8。

性質(zhì)1 給定模糊項集X及其擴展項集X′，其中X?X′，IX?Ty，則有

imtfuyX≥mtfuyX≥fuyX′

(11)

證明：

(1)imtfuyX≥mtfuyX：

(2)若IX′?Ty：

∵fuyX′=0 ∴mtfuyX≥fuyX′

(3)若IX′?Ty：

mtfuyX=fuyX+mrfuyX

≥fuyX+fuy(X′-X)+mrfuyX′

=fuyX′+mrfuyX′≥fuyX′

∵(1)和(2)∴imtfuyX≥mtfuyX≥fuyX′。

定義14 定量事務(wù)數(shù)據(jù)庫D中，模糊項集X的模糊項集效用上界，記作fiuubX，定義為

(12)

例如，設(shè)X={B.L}。由表3可知，X的模糊項集效用上界fiuubX=mtfu3，X+mtfu4，X=(8+0)+(12.8+30)=50.8。

性質(zhì)2 給定模糊項集X及其擴展項集X′，其中X?X′，IX?Ty，則有

ifuubX≥fiuubX≥afuX′

(13)

證明：∵性質(zhì)1∴imtfuyX≥mtfuyX≥fuyX′

→ifuubX≥fiuubX≥afuX′，得證。

由性質(zhì)2可知，本文提出的fiuub是比文獻(xiàn)[8]中的ifuub更緊密的模糊效用上界。

定義15 Top-k項集列表結(jié)構(gòu)，記作Topk-List，負(fù)責(zé)保存挖掘過程中發(fā)現(xiàn)的k個潛在Top-k高模糊效用項集，隨挖掘過程不斷更新。邊緣模糊效用閾值，記作min_futilBorder，用于記錄Topk-List中k個項集中的最小實際模糊效用值(記作Topk-List.minafu)，隨Topk-List.min的更新而更新。

其中，潛在Top-k高模糊效用項集，指的是挖掘過程中實際模糊效用值afu不小于當(dāng)前的邊緣模糊效用閾值min_futilBorder的模糊項集。

2 算法設(shè)計

2.1 模糊項集效用列表

如圖2所示，我們設(shè)計了一種用于保存模糊項集及其效用信息的數(shù)據(jù)結(jié)構(gòu)，即模糊項集效用列表，用fiul表示。fiul由模糊項集(X)、事務(wù)標(biāo)識符(tid)、事務(wù)中模糊項集的模糊效用(fu)、事務(wù)中模糊項集的最大剩余模糊效用(mrfu)組成。列表中fu之和用sumFu表示，mrfu之和用sumMrfu表示。圖2中的模糊項集來自表3，列表中數(shù)據(jù)可由表3計算得到。由列表計算可知，1-項集的實際模糊效用afu和模糊項集效用上界fiuub。例如，{A.L}的模糊項集效用上界fiuub{A.L}= (1.6+20)+(1.8 +49.2)+(1.6+20)=94.2，afu{A.L}=1.6+1.8+1.6=5。

圖2 模糊1-項集的效用列表

借助列表結(jié)構(gòu)，不需要重復(fù)掃描數(shù)據(jù)庫，便可將兩個不同(k-1)-項集的fiul進行連接，形成一個新的k-項集(k≥2)的fiul。兩個項集進行連接操作時，具有相同的tid的元組會結(jié)合在一起。為了加速連接過程，規(guī)定列表的每一列按照tid升序排序，可采用二分查找的方式去定位元組。假設(shè)兩個不同列表的大小分別為m和n，由于列表中的tid按升序排序，則在最壞情況下，時間復(fù)雜度為O(m+n)。圖3是2-項集的列表結(jié)構(gòu)。各元組fu的值等于項集中各模糊項在同一事務(wù)中的模糊效用之和。由定義13及定義14分析可知，兩不同(k-1)-項集連接時，應(yīng)取事務(wù)中順序靠后的模糊項集的mrfu的值作為k-項集的mrfu的值。例如，mrfu4，{A.L，B.L}=mrfu4，{B.L}=30。

圖3 模糊2-項集的效用列表

2.2 剪枝策略

根據(jù)上一節(jié)提出的列表結(jié)構(gòu)，項集間連接方式的搜索空間可視作一棵集合枚舉樹，如圖4所示。由圖4可知，由于樹中存在大量的節(jié)點，搜索過程會變得非常耗時。如果存在n個模糊項，則意味著需要檢索2n個模糊項集。因此，為減少搜索空間，本文提出了兩種剪枝策略。相關(guān)描述如下。

圖4 用例的集合枚舉樹

性質(zhì)3 Afu-prune：給定模糊項集X及其模糊項集效用列表fiulX。在挖掘過程中，若fiulX中所有的fu之和不小于當(dāng)前的邊緣模糊效用閾值min_futilBorder，則X是一個潛在Top-k高模糊效用項集，可添加到Topk-list中。

證明：給定模糊項集X及相應(yīng)的模糊項集效用列表fiulX，設(shè)X.tids是fiulX中tid的集合，則有

由定義15可知，X是潛在的Top-k高模糊效用項集，可將X加到Topk-list中。

性質(zhì)4 FI-Prune：給定模糊項集X及其模糊項集效用列表fiulX。若fiulX中所有的fu及mrfu的總和不小于當(dāng)前的邊緣模糊效用閾值min_futilBorder，則存在X的擴展項集X′可能是潛在Top-k高模糊效用項集。否則，就無需去構(gòu)建一個新的項集模糊效用列表。

證明：設(shè)模糊項集X的擴展為X′。由性質(zhì)2可知，X′實際模糊效用afuX′≤fiuubX。由定義13和14可知，fiuubX=sumFuX+sumMrfuX。

因此，若sumFuX+sumMrfuX

例如，設(shè)k=2，由表3創(chuàng)建1-項集模糊項集效用列表后，計算實際模糊效用，可得最大的兩個項集為{C.M}和{B.L}。根據(jù)性質(zhì)3，Top2-list更新后，其中保存的項集為：{{B.L}，{C.M}}，min_futilBorder=afu{B.L}=20.8。考慮1-項集{A.M}及其擴展項集{A.M，B.M}，由于sumFu{A.M}+sumMrfu{A.M}=93.2>min_futilBorder，根據(jù)性質(zhì)4，{A.M，B.M}可能是潛在Top-k高模糊效用項集，則構(gòu)建其模糊項集效用列表。計算sumFu{A.M，B.M}=21.4，sumFu{A.M，B.M}>min_futilBorder。根據(jù)性質(zhì)3，2-項集{A.M，B.M}是潛在Top-k高模糊效用項集，可添加到Top2-List。更新Top2-List：{{A.M，B.M}，{C.M}}，更新min_futilBorder=afu{A.M，B.M}=21.4。

2.3 TKHFU算法

根據(jù)上述內(nèi)容，本文已經(jīng)介紹了TKHFU算法的相關(guān)定義、數(shù)據(jù)結(jié)構(gòu)及剪枝策略。接下來，開始詳細(xì)介紹本算法的挖掘過程。

算法1是TKHFU的主函數(shù)，其輸入?yún)?shù)包括：定量事務(wù)數(shù)據(jù)庫D，期望發(fā)現(xiàn)的高模糊效用項集的數(shù)量k，模糊隸屬函數(shù)R。輸出Top-k高模糊效用項集的集合TKHFUs。第(1)步～第(5)步，TKHFU檢索數(shù)據(jù)庫D中的每一條事務(wù)Ty，將Ty中每個項按給定的模糊隸屬函數(shù)轉(zhuǎn)化成模糊項，計算每個模糊項的模糊效用fu及最大剩余模糊效用mrfu。然后，按定義11對事務(wù)中各項排序，得到修改后的數(shù)據(jù)庫(第(6)步)。之后，初始化共同前綴項集及其模糊項集效用列表，以便后續(xù)構(gòu)建高層級的模糊項集(第(7)～第(8)步)。初始化Topk-List為NULL，邊緣模糊效用閾值為0(第(9)步)。然后，構(gòu)造所有一項集的效用列表，得到一項集所有列表的集合fiul1(第(10)～第(12)步)。第(13)步，調(diào)用算法2，遞歸挖掘Top-k項集。最后，輸出Top-k高模糊效用項集的集合TKHFUs。

算法1：TKHFU

輸入：定量事務(wù)數(shù)據(jù)庫D，k，模糊隸屬函數(shù)R。

輸出：Top-k高模糊效用項集的集合TKHFUs。

(1)foreach transactionTyinDdo

(2) Convert the value of all every itemiz∈IinTyto fuzzy items byR;

(3) compute the fuzzy utility value of every fuzzy item(fu);

(4) calculate the maximal remaining fuzzy utility value of every fuzzy item inTy(mrfu);

(5)end

(6) sort all itemsiz∈IinTywith thei1i2i3…imorder then get revised transactions;

(7) initial common prefix itemsetP←NULL;

(8) initial fuzzy itemset utility list ofP,fiulP←NULL;

(9) initial Topk-List←NULL,min_futilBorder←0;

(10)foreachiz∈Ido

(11) getfiulof every fuzzy item ofiz(fiul1);

(12)end

(13) callMiner(P,fiulP,fiul1,Topk-List,min_futilBorder);

(14)returna complete set of TKHFUs;

算法2是一個遞歸函數(shù)，輸入?yún)?shù)包括：共同前綴模糊項集P，P項集模糊效用列表fiulP，模糊項集效用列表的集合fiuls，Top-k模糊項集列表結(jié)構(gòu)Topk-List，邊緣模糊效用閾值min_futilBorder。對于任意fiulX∈fiuls，首先判斷X是否為潛在候選Top-k高模糊效用項集。根據(jù)性質(zhì)3，如果fiulX中所有的fu之和不小于當(dāng)前的邊緣模糊效用閾值min_futilBorder，則將X添加到Topk-List中。之后，移除Topk-List中實際模糊效用值最小的項集，將邊緣模糊效用閾值更新到當(dāng)前Topk-List中的最小實際模糊效用值(第(2)步～第(5)步)。然后，根據(jù)性質(zhì)4，如果fiulX中所有的fu及mrfu的總和不小于當(dāng)前的邊緣模糊效用閾值min_futilBorder，那么存在X的擴展項集可能是潛在Top-k高模糊效用項集，則可用X去構(gòu)建高層級的模糊項集(第(7)步～第(15)步)。第(8)步，使用exfiuls收集新的擴展模糊項集的列表，并將其初始化為NULL。第(9)步，由于所有的1-項集是排好序的，因此只需要考慮fiulX之后的fiulY即可。調(diào)用算法3去構(gòu)建新的高層級的模糊項集的效用列表(第(10)步)。最后，程序設(shè)置新的輸入?yún)?shù)，遞歸地執(zhí)行算法，直到挖掘出全部的Top-k項集(第(16)步)。

算法2：Miner

輸入：共同前綴模糊項集P，P項集模糊效用列表fiulP，模糊項集效用列表的集合fiuls，Top-k模糊項集列表結(jié)構(gòu)Topk-List，邊緣模糊效閾值min_futilBorder。

(1)foreachfiulXinfiulsdo

(2)ifsumFuthen

(3) Topk-List←X;

(4) Remove fuzzy itemset with minimal actual fuzzy utility from Topk-List;

(5)min_futilBorder←Topk-List.minafu;

(6)end

(7)ifsumFuX+sumMrfuX≥min_futilBorderthen

(8) initialexfiulswhich is a new set of extended fuzzy itemset uitility listsfiulsasNULL;

(9)foreachfiulYafterfiulXinfiulsdo

(10) newfiultmp←Construct(fiulP,fiulX,fiulY);

(11)ifsumFutmp> 0then

(12) addfiultmpintoexfiuls;

(13)end

(14)end

(15)P←P∪X;

(16) callMiner(P,fiulX,exfiuls,Topk-List,min_futilBorder);

(17)end

(18)end

算法3以3個模糊項集效用列表作為輸入?yún)?shù)，負(fù)責(zé)使用兩個不同項集的列表去構(gòu)建新的高層級項集的列表。對于1-項集的列表，它們的共同前綴設(shè)定為NULL。第(1)步，初始化新的擴展模糊項集Pxy的列表。然后，遍歷Px的列表中每個元素Pxe(第(2)步)。如果Py的列表fiulPy中存在元素Pye與Pxe有相同的tid，那么模糊項集Px和Py可用于形成一個新的模糊項集Pxy(第(5)步～第(6)步)。Pxye.fu的值應(yīng)該減去Pe.fu的值，以避免重復(fù)計算(第(6)步)。此外，如果Px和Py是1-項集，那么程序會去構(gòu)建一個Pxy列表的新元素Pxye，計算相應(yīng)的fu及mrfu的值(第(8)步)。由于定量事務(wù)數(shù)據(jù)庫已經(jīng)過修改，Pxye的mrfu的值應(yīng)為Pye.mrfu。第(10)步，將構(gòu)建好的Pxye添加到fiulPxy中。最后，算法3返回一個新的列表fiulPxy。

算法3：Construct

輸入：共同前綴模糊項集的效用列表fiulP，模糊項集Px的效用列表fiulPx，模糊項集Py的效用列表fiulPy。

輸出：一個新的高層級的模糊項集的效用列表

(1) initialfiulPxy←NULL;

(2)foreach elementPxe∈fiulPxdo

(3)if?Pye∈fiulPyandPxe.tid==Pye.tidthen

(4)iffiulP≠NULLthen

(5) adopt binary search method find elementPe∈fiulPwhichPe.tid==Pxe.tid;

(6)Pxye=(Pxe.tid,Pxye.fu-Pe.fu,Pye.mrfu);

(7)else

(8)Pxye=(Pxe.tid,Pxye.fu-Pe.fu,Pye.mrfu);

(9)end

(10) addPxyeintofiulPxy;

(11)end

(12)end

(13)returna fuzzy itemset utility list of new fuzzy itemsetPxy

2.4 時間復(fù)雜度分析

本算法的時間復(fù)雜度主要由算法1的步驟(1)和步驟(13)決定。步驟(1)是遍歷數(shù)據(jù)庫中的事務(wù)及對每條事務(wù)中的項進行處理，執(zhí)行次數(shù)主要由事務(wù)數(shù)m和事務(wù)中的項數(shù)n決定，執(zhí)行次數(shù)為mn。算法1的步驟(13)為算法2，是一個遞歸函數(shù)，其執(zhí)行次數(shù)等于遞歸次數(shù)×每次遞歸執(zhí)行次數(shù)。由算法2的步驟(7)可知，遞歸次數(shù)由if語句成立的次數(shù)q決定，q不大于步驟(1)中列表的數(shù)量p。算法2每次遞歸的執(zhí)行次數(shù)由(1)、(9)和(10)決定。(1)是一個外循環(huán)，執(zhí)行次數(shù)由列表的數(shù)量p決定。(9)是一個內(nèi)循環(huán)，執(zhí)行次數(shù)由排在模糊項集X后的模糊項集Y的數(shù)量x1決定。(10)是算法3，執(zhí)行次數(shù)由算法3中的步驟(2)決定。算法3中，設(shè)fiulPx和fiulPy中元素數(shù)量分別為x2和x3，查找相同tid的元素，最壞情況下，執(zhí)行次數(shù)為x2+x3。因此，算法1步驟(13)的執(zhí)行次數(shù)為qp(x2+x3)。綜上，本算法總體時間復(fù)雜度為O(mn+qpx1(x1+x3))。

3 實驗分析

實驗平臺：Windows 10操作系統(tǒng)，16 G內(nèi)存，Intel(R) Core(TM)i5-9300H CPU @2.40 GHz。本實驗中所有算法均采用java實現(xiàn)。實驗中用到的數(shù)據(jù)集，包括真實數(shù)據(jù)集和合成數(shù)據(jù)集，其特征見表4。數(shù)據(jù)集foodmart和Skin屬于真實數(shù)據(jù)集，來源于SPMF[16]；c4d250k是由SPMF上的spmf.jar發(fā)行版工具合成的一組數(shù)據(jù)集；項的數(shù)量在1～12之間隨機產(chǎn)生，項的單元利潤在1～8之間隨機產(chǎn)生。本文從運行時間、內(nèi)存占用及可伸縮性3個方面對算法性能進行了評估。

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

為評估TKHFU的性能，本節(jié)將其與HFUI-GA[7]及EFUPM[8]進行了比較。由于HFUI-GA和EFUPM是高模糊效用項集挖掘算法，無法直接與TKHFU比較。為比較這3種算法，可采取先確定k值來運行TKHFU，再取算法挖掘結(jié)果中第k項的afu的值作為HFUI-GA和EFUPM的min_futil的方法。本文從運行時間、內(nèi)存占用及可伸縮性3個方面評估了3種算法的性能。

3.1 時間和內(nèi)存分析

圖5顯示了3種算法在真實數(shù)據(jù)集foodmart和Skin上運行時間的比較。在較小的數(shù)據(jù)集foodmart上，當(dāng)k值等于200時，TKHFU算法僅需2 s，而HFUI-GA和EFUPM運行時間分別需要11 s和5 s。在較大的數(shù)據(jù)集Skin上，TKHFU算法表現(xiàn)同樣出色，TKHFU算法不僅所需時間最少，而且隨著k值的增長，時間變化也較其它兩者更為平穩(wěn)。當(dāng)k值從1上升到100時，TKHFU運行時間僅從3 s上升到6 s，而HFUI-GA算法已經(jīng)從20 s上升到51 s，EFUPM也從7 s上升到了18 s。主要原因是，算法只掃描了一次數(shù)據(jù)庫，構(gòu)建一項集的模糊項集效用列表之后，直接根據(jù)列表中tid來產(chǎn)生高層級的項集，大大減少了項集連接操作的耗時；其次，使用了兩種有效的剪枝策略，減少了非潛在Top-k高模糊效用項集的產(chǎn)生，避免了創(chuàng)建無意義項集的列表所需的時間。

圖5 TKHFU和EFUPM及HUFI-GA的運行時間

圖6顯示了3種算法在真實數(shù)據(jù)集foodmart和Skin上內(nèi)存占用的比較。無論是在小數(shù)據(jù)集foodmart還是在較大數(shù)據(jù)集Skin上，TKHFU的內(nèi)存占用情況均明顯優(yōu)于HUFI-GA算法，略好于EFUPM算法。原因主要是，TKHFU相較于HFUI-GA，使用了新的緊湊的數(shù)據(jù)結(jié)構(gòu)，并將其與兩種剪枝策略結(jié)合，避免占用大量內(nèi)存去創(chuàng)建無意義的項集；TKHFU相較于EFUPM，改進了模糊效用上界，使用了一種更緊密的模糊效用上界，從而減少了內(nèi)存消耗。

圖6 TKHFU和EFUPM及HFUI-GA的內(nèi)存消耗

總體來說，基于真實數(shù)據(jù)集的實驗驗證了TKHFU算法的可行性和有效性，表明了TKHFU算法的運行時間和內(nèi)存占用都隨k值增大而增大，但TKHFU在運行時間和內(nèi)存占用方面均優(yōu)于其它兩種算法。

3.2 可伸縮性分析

圖7顯示了3種算法在不同條件下的可伸縮性。實驗中，k值設(shè)定為50。圖7(a)顯示，在數(shù)據(jù)庫大小固定為50 K，數(shù)據(jù)集c4d250k不同項的數(shù)量從1 K到5 K變化時，3種算法的運行時間。圖7(b)顯示，在不同項的數(shù)量固定為1 K，數(shù)據(jù)集c4d250k的大小從50 K到250 K變化時，3種算法的運行時間。分析可知，在不同設(shè)定條件下，TKHFU具有更好的伸縮性。

圖7 不同條件下算法的可伸縮性

4 結(jié)束語

本文提出了TKHFU算法，解決了高模糊效用項集挖掘中存在的閾值選擇的難題。設(shè)計了項集模糊效用列表結(jié)構(gòu)，減少了項集間連接的時間。提出了一種更緊密的模糊效用上界及兩種剪枝策略，將剪枝策略運用到了列表中，提升了算法的效率?；趦煞N真實數(shù)據(jù)集及一組合成數(shù)據(jù)集的實驗結(jié)果表明，TKHFU在運行時間、內(nèi)存占用及可伸縮性上均優(yōu)于HUFI-GA及EFUPM。

未來，我們會進一步將提出的算法應(yīng)用到實際中，例如數(shù)據(jù)流等。此外，采用基于樹的結(jié)構(gòu)及分布式架構(gòu)，將算法運行在百萬量級的超大數(shù)據(jù)集上，也是我們需要考慮的重點。