文 凱,許萌萌,張許紅

(1.重慶郵電大學通信與信息工程學院，重慶 400065；2.重慶郵電大學通信新技術(shù)應(yīng)用研究中心，重慶 400065； 3.重慶信科設(shè)計有限公司，重慶 401121)

1 引言

當今大數(shù)據(jù)時代，隨著時間的推移各個領(lǐng)域都會積累越來越多的數(shù)據(jù)。如何從這些海量數(shù)據(jù)中找到有趣的知識，是當今人們關(guān)注的重要研究課題，數(shù)據(jù)挖掘技術(shù)也由此受到人們的青睞。項集挖掘是從數(shù)據(jù)庫中提取有用項集信息的一系列過程，是實現(xiàn)數(shù)據(jù)挖掘的主要方法之一。Apriori算法是首次提出的頻繁項集挖掘算法，它是一種廣度優(yōu)先算法，需多次掃描數(shù)據(jù)庫，算法擴展性較好，但無法高效處理大數(shù)據(jù)集。FP-Growth算法是一種深度優(yōu)先算法，采用分而治之策略并只需掃描2次數(shù)據(jù)庫即可完成頻繁項集的挖掘。作為數(shù)據(jù)挖掘領(lǐng)域的研究熱點，頻繁項集[1]受到學者們的廣泛關(guān)注，并由其衍生出不同類型的挖掘算法：top-rank-k頻繁項集[2]、高效用項集[3]、閉頻繁項集[4]、最大頻繁項集[5]、加權(quán)頻繁項集[6]和可擦除項集[7]等。

傳統(tǒng)方法大都根據(jù)用戶給定的閾值，提取出不低于閾值的項集，而可擦除項集提取的是不高于閾值的項集。在經(jīng)濟條件不好的情況下，可擦除項集挖掘方法通過提取對利潤影響不大的項集，從而可以為生產(chǎn)多種產(chǎn)品的廠商制定新的產(chǎn)品計劃，以改善廠商的財務(wù)狀況，保證廠商的運作穩(wěn)定。但是，傳統(tǒng)的可擦除項集挖掘方法存在以下問題：認為項的重要性相同，如以位圖表示的可擦除項集挖掘BERM (Bintmap Representation for Erasable Mining approach)算法[8]；處理的數(shù)據(jù)庫是靜態(tài)的，如使用樹結(jié)構(gòu)的加權(quán)可擦除模式WEP(Weighted Erasable Patterns with a tree structure)[9]算法。在真實環(huán)境中，項因其價格、稀缺程度等因素具有不同的重要性，因此不能認為項都具有相同的重要性。此外，數(shù)據(jù)的不斷累積會使數(shù)據(jù)庫動態(tài)更新，若有新的數(shù)據(jù)被添加到數(shù)據(jù)庫中，以往挖掘出的項集可能就不再是人們感興趣的。為滿足這些條件，在增量數(shù)據(jù)集上進行加權(quán)可擦除項集挖掘的研究應(yīng)運而生。IWEI(Incremental mining of Weighted Erasable Itemsets)算法[10]掃描一次增量數(shù)據(jù)庫即可構(gòu)建IWEI-tree，然后執(zhí)行樹重構(gòu)過程更新樹結(jié)構(gòu)，結(jié)合加權(quán)條件進行可擦除項集挖掘；基于列表的增量可擦除模式挖掘LINE (List-based INcremental Erasable pattern mining)算法[11]是基于列表結(jié)構(gòu)的可擦除項集挖掘算法，該算法首先構(gòu)造1-項集的EI-list，并通過EI-list構(gòu)造存儲k-項集的EP-list進而快速執(zhí)行挖掘操作，提高算法的效率。但是，IWEI算法采用樹結(jié)構(gòu)，導致算法運行時間過長，且在構(gòu)建和重構(gòu)樹的過程中，消耗的內(nèi)存過多；而LINE算法認為項具有相同的重要性。除了權(quán)重和數(shù)據(jù)庫積累問題，數(shù)據(jù)的實時流入導致數(shù)據(jù)不斷積累，則處理增量數(shù)據(jù)集的可擦除項集挖掘算法必須在一次掃描后就將所得結(jié)果快速反饋給用戶。因此，為更好地滿足這些條件，在增量數(shù)據(jù)集上快速挖掘出加權(quán)可擦除項集WEIs(Weighted Erasable Itemsets)很重要。

本文提出了基于列表結(jié)構(gòu)的WEIs挖掘算法WELI(Weighted Erasable itemsets mining using List structure over Incremental database)，該算法考慮項的重要性，采用列表結(jié)構(gòu)有效存儲項集信息，利用權(quán)重條件修剪無效項集，以減少挖掘過程中的內(nèi)存消耗，結(jié)合包含索引和差集概念加快計算項集的增益值，從而提高在增量數(shù)據(jù)集上挖掘WEIs的效率。

2 問題定義及基本概念

設(shè)數(shù)據(jù)庫DB={P1,P2,P3,…,Pm}，項集IS={i1,i2,i3,…,in}，其中數(shù)據(jù)庫由m個交易集組成，IS是由n個項組成的集合，每個產(chǎn)品Pk?IS(1≤k≤m)由唯一標識符PID、項集和產(chǎn)品利潤Pk.profit組成。設(shè)IS中對應(yīng)項的權(quán)重由w={w1,w2,…,wn}表示。設(shè)增量數(shù)據(jù)庫用DBi∈{DB0,DB1,DB2,…,DBl}表示，即表示有l(wèi)+1個數(shù)據(jù)庫，主要體現(xiàn)數(shù)據(jù)庫的增加。如DB0是原始數(shù)據(jù)庫，包括6個交易集，當沒有增量數(shù)據(jù)庫時，算法所挖掘的是原始數(shù)據(jù)庫的結(jié)果；隨著數(shù)據(jù)不斷增多，設(shè)DB1是增量數(shù)據(jù)庫1，包括3個交易集，則基于原始數(shù)據(jù)庫結(jié)果，需要處理增量數(shù)據(jù)庫。

定義1項集X={i1,i2,…,ir}的增益Gain(X)指至少包含X中1項的產(chǎn)品利潤的總和，如式(1)所示：

Gain(X)=∑{Pk∈DB|X∩Pk.Items≠?}Pk.profit

(1)

其中，1≤r≤n，X?IS。

定義2設(shè)用戶給定的閾值為δ，最大增益閾值MGT為數(shù)據(jù)庫中產(chǎn)品總利潤與閾值之積,即：

MGT=δ*∑Pk∈DBPk.profit

(2)

定義3設(shè)產(chǎn)品集Pm={i1,i2,…,is}，項ir(1≤r≤s)的權(quán)重比WR指產(chǎn)品中該項的權(quán)重與該產(chǎn)品中項的總權(quán)重之比。Pm中ir的權(quán)重比表示如式(3)所示：

(3)

定義4設(shè)項集X={i1,i2,…,iy}(1≤y≤n,X?IS)，則X是個r-項集(包含r個項的項集)，假設(shè)項ir在Pk={P1,P2,…,Pp}產(chǎn)品中，那么包含在項集X中的ir的平均權(quán)重AW(ir)如式(4)所示：

(4)

其中，j為產(chǎn)品唯一標識符。

項集X的平均權(quán)重為X中每一項AW(ir)的平均值：

(5)

定義5項集X的加權(quán)增益WGain(X)表示X的增益與X平均權(quán)重的比值，即：

(6)

若項集滿足WGain(X)≤MGT，則X是WEIs。式(6)中，隨著數(shù)據(jù)不斷累積，Gain(X)是不斷增加的，由于AW(X)是均值，其增減情況不定。由此可知，若項集X為加權(quán)不可擦除項集，與一個平均權(quán)重值較高的項集結(jié)合得到一個WEIs，這種情況違反了反單調(diào)性。反單調(diào)性的應(yīng)用可以加快挖掘操作，因此，本文采用以下方法保證算法的反單調(diào)性。

定義6最大加權(quán)增益用MGain表示，項集X的最大加權(quán)增益MGain(X)定義如式(7)所示：

(7)

其中，MAW是1-項集中的最大平均權(quán)重值，通常情況下其值不低于平均權(quán)重，與平均權(quán)重不同，MAW值固定，不會出現(xiàn)項集丟失情況[10]。

3 WELI算法

3.1 改進的列表結(jié)構(gòu)

執(zhí)行增量挖掘的條件是：(1)挖掘WEIs所需的所有操作必須在一次掃描數(shù)據(jù)庫操作內(nèi)完成；(2)構(gòu)建的數(shù)據(jù)結(jié)構(gòu)需在操作過程中多次使用；(3)插入的數(shù)據(jù)需在合理時間內(nèi)反饋出新結(jié)果。為滿足以上條件，本文對列表結(jié)構(gòu)進行改進，以挖掘WEIs。詳細描述如下所示：

首先當新添加一產(chǎn)品數(shù)據(jù)庫時，產(chǎn)品PID值和其利潤值存儲在產(chǎn)品集列表WELI-table中，該表可在后續(xù)的k-項集擴展中用于引用數(shù)據(jù)庫中的增益值。項列表WEI-list是由項、項的PID和項的增益值組成，用于存儲項及其所在產(chǎn)品的信息。k-項集的存儲則采用項集列表WEIs-list，它主要由項集、差集標識符dPID及其增益組成。若WEI-list或WEIs-list構(gòu)建完成，將其按照增益的非升序排列重構(gòu)，為后續(xù)挖掘提供便利。然后，計算各項在產(chǎn)品集中的平均權(quán)重并存儲到平均權(quán)重列表AW-list中。AW-list主要由項集和AW值組成。

圖1是列表結(jié)構(gòu)的框圖，WELI-table、WEI-list、AW-list和WEIs-list的形式分別如圖1a～圖1d所示。這些結(jié)構(gòu)一旦在原始數(shù)據(jù)庫中完成構(gòu)建，在后續(xù)整個增量挖掘中會重復使用并更新。由于算法是以增量方式進行挖掘，為防止項集丟失，不滿足閾值條件的無效項不予刪除。

Figure 1 List structure圖1 列表結(jié)構(gòu)框圖

性質(zhì)1設(shè)E={e1,e2,…,er}是一組可擦除項集列表，而E′={e′1,e′2,…,e′o}是一組不可擦除項集列表，刪除E′會在后續(xù)挖掘過程中導致嚴重的項集丟失。

證明傳統(tǒng)的靜態(tài)數(shù)據(jù)庫中，有效的可擦除項集都是由E根據(jù)反單調(diào)性而產(chǎn)生的，而增量數(shù)據(jù)的特點是數(shù)據(jù)不斷更新。在增量挖掘中，E中每個項e會出現(xiàn)2種情況：(1)可擦除項；(2)變成不可擦除項。同樣，E′中每個項e′會出現(xiàn)2種情況：(1)不可擦除項；(2)變成可擦除項。假設(shè)在原始數(shù)據(jù)庫挖掘中刪除E′，E′和E的情況(1)中是否可擦除項的狀態(tài)都保持不變；E的情況(2)對挖掘結(jié)果不產(chǎn)生影響，只需忽略與之相關(guān)的WEI-list即可；E′的情況(2)說明之前的不可擦除項集變成可擦除的，而在原始數(shù)據(jù)庫中已經(jīng)將其刪除，因此造成了項集丟失。所以在增量挖掘中，為避免造成項集丟失，最大加權(quán)增益高于MGT的項不予以刪除。

□

定義7加權(quán)可擦除項集A的包含索引用subsume(A)表示，其中PID(A)表示項集A的產(chǎn)品集標識符。

subsume(A)={B∈WEIs1|PID(A)?PID(B)}

(8)

性質(zhì)2設(shè)項集A包含索引[12]為subsume(A)= {A1,A2,…,Ai},則{A1,A2,…,Ai}與A相結(jié)合的2i-1個非空子集的每個增益等于A的Gain(A)。

證明若subsume(A)={A1,A2,…,Ai}，則分以下2種情況證明：

(1)當{A1,A2,…,Ai}與A相結(jié)合的非空子集為2-項集時，PID(A)?PID(At)，1≤t≤i，因此包含A的產(chǎn)品一定包含項At，而包含項At的產(chǎn)品不一定包含項A，由定義1可知，Gain(AAt)=Gain(At)。

(2)當{A1,A2,…,Ai}與A相結(jié)合的非空子集為k-項集(k>2)時，設(shè)包含索引{A1,A2,…,Ai}中的任意子集為S(S的長度至少為2)，則PID(A)?PID(S)，因此，根據(jù)式(1)可知，Gain(AS)=Gain(S)。

□

使用包含索引可快速計算k-項集的增益值，將具有包含索引關(guān)系的項直接結(jié)合而無需計算其增益值，從而避免重復計算。因此，在生成1-項集后，若具有包含索引關(guān)系的項已確定，生成k-項集(k≥2)時直接進行項集結(jié)合而無需計算其增益(性質(zhì)2)。使用包含索引可加快確定k-項集的增益值，在稠密型數(shù)據(jù)集上此作用效果明顯。

3.2 更新的列表結(jié)構(gòu)

數(shù)據(jù)的不斷積累導致列表結(jié)構(gòu)不斷更新。首先掃描原始數(shù)據(jù)庫建立空表，讀取產(chǎn)品集時將產(chǎn)品PID值和其利潤值存儲在空表中，當有新數(shù)據(jù)插入時更新WEI-list。若添加項在WEI-list中不存在，則只需在WEI-list末端創(chuàng)建該項并存儲相關(guān)信息；若新添加項在WEI-list中存在，則更新所添加項的PID及累積后的增益值。對所有插入的新產(chǎn)品集遞歸地生成WELI-table和WEI-list。而WEIs-list在進行項集更新和結(jié)合后會被立即刪除，防止占用過多資源。這些列表結(jié)構(gòu)可有效地存儲當前數(shù)據(jù)庫的全部信息。然后，根據(jù)權(quán)重信息進行項集平均權(quán)重的計算，并將其信息存儲在AW-list中。

傳統(tǒng)可擦除項集挖掘算法都是采用樹結(jié)構(gòu)，將項的信息壓縮到樹結(jié)構(gòu)中，若處理增量數(shù)據(jù)，在添加新元素時會需要多次進行樹的構(gòu)建，導致挖掘性能低下。采用列表結(jié)構(gòu)使算法能夠更有效地在增量挖掘環(huán)境中提取可擦除項集。

3.3 可擦除項集的增量挖掘

定義8項集XA和XB的差集標識符索引d(XAB)表示如下：

d(XAB)=XB.PID-XA.PID

(9)

性質(zhì)3設(shè)M和N項的PID分別為：M.PID= {x1,x2,…,xi}，N.PID={y1,y2,…,yi}，M和N的差集標識符索引用d(M,N)表示，d(M,N)={xy1,xy2,…,xyk}，則MN的增益值為Gain(MN)=Gain(M)+∑xyl∈d(M,N)Pxyl.profit，證明見文獻[11]。

若WELI-table和WEI-list根據(jù)新增數(shù)據(jù)庫已構(gòu)造或重構(gòu)完成，算法則等待用戶或新輸入數(shù)據(jù)的請求，若用戶請求挖掘操作，則算法通過遞歸地結(jié)合WEI-list，進而生成可擦除候選k-項集并將k-項集存儲在WEIs-list中。WEIs-list存儲長度為2或更長項集的信息，項集越長，所需要存儲的PID越多，若使用產(chǎn)品PID的差集則數(shù)量會減少很多，可節(jié)約資源存儲空間，并且使用差集的相關(guān)性質(zhì)可減少計算開銷。根據(jù)WEIs-list中各項集增益值得到項集的最大加權(quán)增益，并與MGT對比判斷是否是可擦除候選項集。若是則進行加權(quán)增益的計算，進而與MGT對比判斷是否是WEIs；若不是則不進行后續(xù)更長項集的連接。若判斷的結(jié)果是WEIs，則存儲到WEIs-list中，否則不存儲。

4 WELI算法主要流程

根據(jù)上述知識，本文提出了基于增量數(shù)據(jù)的加權(quán)可擦除項集挖掘算法WELI，其偽代碼如算法1所示。首先初始化列表信息，產(chǎn)生更新的列表；然后產(chǎn)生1-項集的包含索引，方便計算k-項集的增益(1～4行)；若出現(xiàn)用戶需求，則計算閾值MGT，并判斷所挖掘出的項是否是WEIs(5～9行)；最后調(diào)用生成k-項集的子算法并存儲在結(jié)果E中。對增量數(shù)據(jù)庫重復以上過程直到無新增數(shù)據(jù)，結(jié)束算法。

算法1WELI算法

輸入：增量數(shù)據(jù)庫DBi∈{DB0,DB1,DB2,…,DBl}，閾值δ，項的權(quán)重w。

輸出：加權(quán)可擦除項集E。

1 InitializeWL,WEI，AW;/*WL、WEI和AW分別表示產(chǎn)品集列表WELI-table、項列表WEI-list、平均權(quán)重列表AW-list*/

2Foreach incremental databaseDBkinDB//k≥0,k≤l+1

3 CallConstruct-DB(WL,WEI,AW,DBk)/*調(diào)用構(gòu)建列表結(jié)構(gòu)子過程*/

4 Callsubsume(I1)//生成1-項集的包含索引

5Ifmining demand appearsthen//出現(xiàn)挖掘請求

6 CalculateMGT；

7If(wei.Gain/wei′sAW)≤MGTthen/*wei為加權(quán)可擦除項集的元素*/

8E=E∪{wei}；/*E用于存儲滿足上一步條件的加權(quán)可擦除項集*/

9Endif

10 CallConstruct_WEIS(MGT,E,I1);

11 Provide the user withE//返回結(jié)果

12 InitializeE//初始化結(jié)果

13Endif

14Endfor

WELI算法的流程如圖2所示。

Figure 2 Flow chart of WELI algorithm圖2 WELI算法流程圖

挖掘步驟如下所示：

(1)掃描數(shù)據(jù)庫DB，創(chuàng)建WELI-table和WEI-list，并將數(shù)據(jù)庫中的數(shù)據(jù)存儲在列表中；然后計算數(shù)據(jù)庫中每個項的平均權(quán)重并存儲在AW-list中。

(2)獲取數(shù)據(jù)庫中1-項集的包含索引。

(3)若算法未得到用戶的挖掘請求，且無新數(shù)據(jù)插入時則進行等待；當有新增數(shù)據(jù)插入時，則返回執(zhí)行(1)，將新數(shù)據(jù)信息添加到構(gòu)建的WEI-list中，同時更新AW-list，并對WEI-list進行重構(gòu)，其重構(gòu)規(guī)則是按照項的增益值降序進行。

(4)用戶請求挖掘并給出閾值，計算MGT。

(5)計算項集的加權(quán)增益和最大加權(quán)增益，得到加權(quán)可擦除候選1-項集WEC1。然后進行項集擴展產(chǎn)生k-項集，直到無新候選項，提取所有加權(quán)增益值不高于MGT的項集，即為WEIs，并將其結(jié)果反饋給用戶。

算法2是生成k-項集(k≥2)的過程，其中In表示項集，首先初始化項集列表WEIs，得到MAW(1～2行)；然后算法遍歷WEI或WEIs中的每一對元素，若生成的是2-項集，參數(shù)是WEI，否則是WEIs。再利用標識符范圍索引PRI(PID Range Index)條件[11]將WEI或WEIs結(jié)合，該條件在處理WEIs-list的過程中有選擇地檢查2項的獨立關(guān)系，而不需研究所有的PID或dPID，簡化算法過程。在使用PRI條件時，判斷2項是否存在包含索引關(guān)系，從而加快生成k-項集的過程(8～14行)，若不存在包含索引關(guān)系，則判斷產(chǎn)生項集的增益值除以MAW的值是否滿足閾值條件，若滿足則添加到WEIs中，然后將項集增益值除以其本身的平均權(quán)重值判斷是否滿足閾值條件，若滿足則將其添加到結(jié)果E中(19～25行)；若不滿足PRI條件，則使用差集方式快速產(chǎn)生k-項集(29～35行)。遞歸調(diào)用當前函數(shù)，直到無新的列表需要連接結(jié)束操作，得到最終的WEIs。

算法2Construct_WEIS(MGT,E,In)

輸入：WL,WEI,AW。/*WL、WEI和AW分別代表WELI-table、WEI-list和AW-list*/

輸出：加權(quán)可擦除項集E。

1 Create a new empty set of WEI-list，簡稱WEIs；

2MAW←maximumAW;//計算最大平均權(quán)重

3Foreach elementIiinWEIorWEIs;/*生成2-項集時參數(shù)為WEI*/

4Foreach elementIjinWEIorWEIs/*生成k-項集時參數(shù)為WEIs*/

5 Create a new WEIs-list，簡稱weis;

6weis的名稱←combination ofIiandIj

7IfIiandIjsatisfy the PRI conditionthen/*判斷是否滿足PRI條件*/

8IfIj?Ii.subsumethen//存在包含索引關(guān)系

9foreachIjgenerated from all elements ofIi.subsume//性質(zhì)2

10weis.Gain←Gain(Ij);

11d(IiIj)=(Ij.PID-Ii.PID)←?;

12ElseifIi?Ij.subsumethen

13foreachIigenerated from all elements ofIj.subsume//性質(zhì)2

14weis.Gain←Gain(Ii);

15d(IiIj)=(Ii.PID-Ij.PID)←?;

16Else//不存在包含索引關(guān)系

17weis.dPID←Ij.dPID

18weis.Gain←Gain(Ii)+Gain(Ij);/*滿足PRI條件求并集*/

19If(weis.Gain/MAW)≤MGTthen

20WEIs=WEIs∪weis

21If(weis.Gain/weis’sAW)≤MGTthen

22E=E∪weis;

23Endif

24Endif

25Endif

26Else

27weis.dPID←d(IiIj)/*不滿足PRI條件求差集*/

28weis.Gain←Ii.Gain+Gain(weis.dPID);

29If(weis.Gain/MAW)≤MGTthen

30WEIs=WEIs∪weis/*產(chǎn)生加權(quán)可擦除候選項*/

31If(weis.Gain/weis’sAW)≤MGTthen

32E=E∪weis/*產(chǎn)生加權(quán)可擦除項集*/

33Endif

34Endif

35Endif

36Endfor

37If|WEIs|>1then

38 CallConstruct_WEIS(MGT,E,Inext)

39Endif

40Endfor

5 實驗與結(jié)果分析

對WELI算法進行實驗驗證，對比算法為IWEI和LINE算法，其中IWEI采用權(quán)重條件而LINE則反之，為保證實驗公平性，對所測試算法在相同條件下進行實驗。實驗平臺為Intel(R) Core(TM) i7-6700 CPU@3.40 GHz，內(nèi)存8 GB，64位Windows操作系統(tǒng)，所有算法均使用Java語言實現(xiàn)，實驗數(shù)據(jù)包括真實數(shù)據(jù)集和合成數(shù)據(jù)集，數(shù)據(jù)集信息如表1所示。其中，真實數(shù)據(jù)集來自http://fimi.cs.helsinkki.fi/data，合成數(shù)據(jù)集采用T10I4DxK(10≤x≤100)，用于測試算法時間和內(nèi)存的可伸縮性。這些數(shù)據(jù)集不提供利潤值和權(quán)值，因此本文算法采用高效用項集挖掘中分配效用值的方法，為以上數(shù)據(jù)集添加一個新屬性來存儲與每個產(chǎn)品相關(guān)的利潤。利潤值在100～15 000，按照對數(shù)的正態(tài)分布隨機設(shè)置，權(quán)值采用文獻[10]的方法。為體現(xiàn)增量挖掘特點，將數(shù)據(jù)集分成10部分，第1部分為原始數(shù)據(jù)庫，剩余9部分作為增量數(shù)據(jù)庫。

Table 1 Parameters of test datasets表1 測試數(shù)據(jù)集參數(shù)

圖3是在Connect(稠密型)數(shù)據(jù)集上的運行時間?？刹脸椉诰虻氖抢麧欀甸撝狄韵碌捻椉撝翟酱笏诰虺龅腤EIs越多，消耗的時間就越多。如圖3所示，隨著閾值增大，3個算法運行時間逐漸增加。WELI算法的運行時間增長最慢，IWEI的增長最快。WELI和IWEI算法都采用權(quán)重條件，由此可刪除一些無效項集。而基于列表的LINE算法雖然不利用權(quán)重，運行時間卻低于基于樹結(jié)構(gòu)的IWEI，說明列表結(jié)構(gòu)的構(gòu)建比樹型結(jié)構(gòu)的構(gòu)建消耗時間少。圖4是在Connect數(shù)據(jù)集上的內(nèi)存消耗，可以看出，隨著閾值的增大，3個算法的內(nèi)存消耗基本不變。原因是閾值增大雖會導致1-項集的候選項集數(shù)量增大，通過結(jié)合生成的k-項集數(shù)量也會變多，但算法不會存儲其候選項集。IWEI算法構(gòu)建樹結(jié)構(gòu)會消耗大量內(nèi)存，比采用列表結(jié)構(gòu)的WELI和LINE算法消耗的內(nèi)存多，而LINE算法不使用權(quán)重條件，所以比WELI算法內(nèi)存消耗略少。從以上實驗可得，WELI在稠密型數(shù)據(jù)集上提取WEIs很有效。

Figure 3 Runtime on Connect dataset圖3 Connect數(shù)據(jù)集上的運行時間

Figure 4 Memory consumption on Connect dataset圖4 Connect數(shù)據(jù)集上的內(nèi)存消耗

圖5是在Retail(稀疏型)數(shù)據(jù)集上的運行時間。分析可知，隨著閾值增大，3種算法的運行時間都增大，IWEI算法的運行時間增加迅速，而WELI和IWEI算法的增加緩慢。原因是增益值越大，挖掘消耗的時間也越多，另外，樹型結(jié)構(gòu)的構(gòu)建比列表結(jié)構(gòu)的構(gòu)建消耗時間多。但是，WELI算法始終比對比算法表現(xiàn)出更好的性能。為減小算法運行時間之間的差距，圖5中的縱坐標采用對數(shù)刻度(lb)。圖6是在Retail數(shù)據(jù)集上的內(nèi)存消耗，分析可知，采用列表結(jié)構(gòu)的WELI和LINE算法所消耗的內(nèi)存比采用樹型結(jié)構(gòu)的IWEI算法少很多，而WELI算法采用了權(quán)重條件，其內(nèi)存消耗比LINE算法消耗略多。從以上實驗可知，WELI算法在稀疏型數(shù)據(jù)集上提取WEIs具有較好的效果。

Figure 5 Runtime on Retail dataset圖5 Retail數(shù)據(jù)集上的運行時間

Figure 6 Memory consumption on Retail dataset圖6 Retail數(shù)據(jù)集上的內(nèi)存消耗

圖7是3個算法在合成數(shù)據(jù)集的時間可伸縮性實驗結(jié)果，其中橫坐標為交易集的數(shù)量(100≤z≤1000)，閾值設(shè)為0.13%，項的數(shù)量固定為1 000。隨著產(chǎn)品數(shù)量的增加，WELI和LINE算法的運行時間穩(wěn)定地增加，而IWEI算法的運行時間增加緩慢。圖8是3個算法的內(nèi)存可伸縮性實驗結(jié)果，WELI和LINE所消耗的內(nèi)存隨著產(chǎn)品數(shù)量的增加而逐漸增加，而IWEI的內(nèi)存消耗則基本保持不變。但是，IWEI要維持樹型結(jié)構(gòu)通常比以上2種算法消耗內(nèi)存多。實驗結(jié)果表明，在考慮權(quán)重因子的條件下，WELI算法在時間和內(nèi)存上均具有較好的可伸縮性，因此在不斷增長的增量數(shù)據(jù)集下，該算法可有效地提取加權(quán)可擦除項集。

Figure 7 Runtime scalability on Retail dataset圖7 Retail數(shù)據(jù)集上的時間可伸縮性

Figure 8 Memory scalability on Retail dataset圖8 Retail數(shù)據(jù)集上的內(nèi)存可伸縮性

6 結(jié)束語

本文結(jié)合權(quán)重條件，提出了一種有效的基于增量數(shù)據(jù)集的可擦除項集挖掘算法WELI。WELI算法采用列表結(jié)構(gòu)存儲項的信息，該結(jié)構(gòu)掃描一次數(shù)據(jù)庫即可完成創(chuàng)建，使用包含索引和差集思想加快執(zhí)行增益計算操作。實驗表明WELI算法具有良好的時間和內(nèi)存效率，比目前先進的算法更有效，且該算法具有很好的擴展性，可有效處理大規(guī)模增量數(shù)據(jù)。在未來研究工作中，會針對當前數(shù)據(jù)的特點研究高效用項集的增量挖掘。