Top-k高模糊效用項集挖掘算法

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

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

0 引 言

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

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

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

1 相關定義

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

表1 定量事務數據庫

表2 單元利潤

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

(1)

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

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

圖1 隸屬函數

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

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

(2)

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

fuyzl=fyzl×u(iz，Ty)

(3)

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

表3 定量事務數據庫中各項模糊域的模糊效用

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

(4)

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

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

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

(5)

其中，IX是模糊項集X的原始離散項集。例如，設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 由用戶預設一個最小模糊效用閾值，用min_futil表示。模糊項集X是高模糊效用項集，當且僅當afuX≥min_futil。用HFUI表示高模糊效用項集。

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

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

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

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

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

(6)

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

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

(7)

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

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

(8)

例如，設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}，設是作用于I中的排序符號。令I中的項按字典順序升序排序，即i1i2i3…im。設模糊項集X的離散項集IX={x1，x2，x3…，xL}?Ty，其中x1x2…xL，Ty?I。將Ty排序后，若存在ij∈Ty且滿足xkij，k∈(1，L)，則將Ty中出現在IX之后的項集稱作IX的剩余項集，記作Ty/IX。

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

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

(9)

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

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

mtfuyX=fuyX+mrfuyX

(10)

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

性質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 定量事務數據庫D中，模糊項集X的模糊項集效用上界，記作fiuubX，定義為

(12)

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

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

ifuubX≥fiuubX≥afuX′

(13)

證明：∵性質1∴imtfuyX≥mtfuyX≥fuyX′

→ifuubX≥fiuubX≥afuX′，得證。

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

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

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

2 算法設計

2.1 模糊項集效用列表

如圖2所示，我們設計了一種用于保存模糊項集及其效用信息的數據結構，即模糊項集效用列表，用fiul表示。fiul由模糊項集(X)、事務標識符(tid)、事務中模糊項集的模糊效用(fu)、事務中模糊項集的最大剩余模糊效用(mrfu)組成。列表中fu之和用sumFu表示，mrfu之和用sumMrfu表示。圖2中的模糊項集來自表3，列表中數據可由表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-項集的效用列表

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

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

2.2 剪枝策略

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

圖4 用例的集合枚舉樹

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

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

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

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

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

因此，若sumFuX+sumMrfuX

例如，設k=2，由表3創(chuàng)建1-項集模糊項集效用列表后，計算實際模糊效用，可得最大的兩個項集為{C.M}和{B.L}。根據性質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，根據性質4，{A.M，B.M}可能是潛在Top-k高模糊效用項集，則構建其模糊項集效用列表。計算sumFu{A.M，B.M}=21.4，sumFu{A.M，B.M}>min_futilBorder。根據性質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算法

根據上述內容，本文已經介紹了TKHFU算法的相關定義、數據結構及剪枝策略。接下來，開始詳細介紹本算法的挖掘過程。

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

算法1：TKHFU

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

算法2：Miner

輸入：共同前綴模糊項集P，P項集模糊效用列表fiulP，模糊項集效用列表的集合fiuls，Top-k模糊項集列表結構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個模糊項集效用列表作為輸入參數，負責使用兩個不同項集的列表去構建新的高層級項集的列表。對于1-項集的列表，它們的共同前綴設定為NULL。第(1)步，初始化新的擴展模糊項集Pxy的列表。然后，遍歷Px的列表中每個元素Pxe(第(2)步)。如果Py的列表fiulPy中存在元素Pye與Pxe有相同的tid，那么模糊項集Px和Py可用于形成一個新的模糊項集Pxy(第(5)步～第(6)步)。Pxye.fu的值應該減去Pe.fu的值，以避免重復計算(第(6)步)。此外，如果Px和Py是1-項集，那么程序會去構建一個Pxy列表的新元素Pxye，計算相應的fu及mrfu的值(第(8)步)。由于定量事務數據庫已經過修改，Pxye的mrfu的值應為Pye.mrfu。第(10)步，將構建好的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 時間復雜度分析

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

3 實驗分析

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

表4 數據集特征

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

3.1 時間和內存分析

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

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

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

圖6 TKHFU和EFUPM及HFUI-GA的內存消耗

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

3.2 可伸縮性分析

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

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

4 結束語

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

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