基于滑動窗口模型的數(shù)據(jù)流閉合高效用項(xiàng)集挖掘

程浩東 韓 萌 張 妮 李小娟 王 樂

(北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 銀川 750021) (734811467@qq.com)

高效用項(xiàng)集挖掘(high utility itemset mining, HUIM)是一項(xiàng)經(jīng)過廣泛研究的數(shù)據(jù)挖掘任務(wù)[1]，它通過考慮一些其他因素?cái)U(kuò)展了頻繁項(xiàng)集挖掘(frequent itemset mining, FIM)[2].FIM僅將項(xiàng)集出現(xiàn)的頻率作為其在數(shù)據(jù)庫中的重要性度量，不考慮每個項(xiàng)目的效用價值.但是，HUIM則同時會考慮項(xiàng)目的效用或?qū)嵱脙r值.在高效用項(xiàng)集挖掘領(lǐng)域，交易事務(wù)中物品的數(shù)量稱為內(nèi)部效用，項(xiàng)目的利潤被稱為外部效用.項(xiàng)目的效用被定義為物品數(shù)量和利潤(即內(nèi)部效用和外部效用)的乘積.挖掘高效用項(xiàng)集(high-utility itemset, HUI)的問題可以描述為找到所有效用值大于或等于用戶自定義閾值的項(xiàng)集，這個閾值稱為最小效用閾值(minutil).較早的算法[3-6]被設(shè)計(jì)為在2個階段挖掘高效用項(xiàng)集，其后又引入1階段算法[7-14].

高效用項(xiàng)集在市場籃分析、產(chǎn)品推薦等實(shí)際應(yīng)用中效果顯著，但靜態(tài)數(shù)據(jù)庫的高效用項(xiàng)集包含了舊數(shù)據(jù)的影響.近年來，無線傳感器網(wǎng)絡(luò)、零售市場交易、通信網(wǎng)絡(luò)和網(wǎng)站在線點(diǎn)擊等場景都在生成數(shù)據(jù)流.挖掘來自數(shù)據(jù)流的項(xiàng)集更加有用，因?yàn)樗谧钚聰?shù)據(jù)且不受舊數(shù)據(jù)影響的項(xiàng)集或模式，用戶可快速獲取相關(guān)信息以采取適當(dāng)?shù)拇胧?例如，考慮在企業(yè)環(huán)境中部署多個WiFi接入點(diǎn)的場景[15]，HUIM可以用于該網(wǎng)絡(luò)中的實(shí)時負(fù)載均衡.每個事務(wù)被建模為一天中訪問點(diǎn)的使用情況，其中將訪問點(diǎn)定義為項(xiàng)目，并且將連接到其的客戶端負(fù)載表示為訪問點(diǎn)的內(nèi)部效用，將數(shù)據(jù)傳輸?shù)椒?wù)器的成本定義為與其關(guān)聯(lián)的外部效用.訪問點(diǎn)的效用可以定義為負(fù)載和成本的乘積，近而實(shí)時識別高負(fù)載訪問點(diǎn)集，此類信息可用于負(fù)載的重新分配或調(diào)控.

文獻(xiàn)[16-18]中已經(jīng)提出了算法用于從數(shù)據(jù)流中挖掘高效用項(xiàng)集，但這些算法均屬于全集高效用項(xiàng)集挖掘算法.全集項(xiàng)集挖掘算法的固有問題是生成大量模式信息冗余的項(xiàng)集，難以被用戶理解和運(yùn)用.因此，一些壓縮或緊湊的HUI表示方法被提出.靜態(tài)高效用項(xiàng)集挖掘領(lǐng)域已提出一種稱為閉合高效用項(xiàng)集(closed high utility itemset, CHUI)的概念[19]，它的大小比高效用項(xiàng)集全集小幾個數(shù)量級，且不丟失任何有用信息.相對于比較有限的內(nèi)存空間，CHUI挖掘能更好地滿足用戶需求，開展此類挖掘的研究具有重要意義.仍以WiFi場景為例，假設(shè)在相同日期內(nèi)某一區(qū)域訪問點(diǎn)A和B均處于高負(fù)載狀態(tài)，且{A}，{A,B}都是HUI，則{A，B}即為需要挖掘的CHUI.顯然該項(xiàng)集減少了冗余信息，在準(zhǔn)確識別所有高負(fù)載訪問點(diǎn)的基礎(chǔ)上，后者為企業(yè)按區(qū)域優(yōu)化網(wǎng)絡(luò)配置提供更佳方案，向運(yùn)營企業(yè)提供更有意義的決策信息.現(xiàn)有文獻(xiàn)已提出多種有效挖掘CHUI的算法，比如CHUD[19]，CHUI-Miner[20]，EFIM-Closed[21]，CLS-Miner[22]等.而后Dam等人[23]針對動態(tài)增量數(shù)據(jù)庫提出新的閉合算法IncCHUI.

類似于靜態(tài)數(shù)據(jù)和增量數(shù)據(jù)，數(shù)據(jù)流中同樣迫切需要進(jìn)行CHUI挖掘.由于數(shù)據(jù)流的海量性等特點(diǎn)，造成對于它的挖掘和存儲都有一定難度.同時，隨著時間的不斷推移，用戶通常只關(guān)注數(shù)據(jù)流中近期有價值的信息.所以已提出的靜態(tài)和增量閉合高效用項(xiàng)集挖掘算法并不能直接適用于數(shù)據(jù)流挖掘任務(wù).

為此，本文設(shè)計(jì)了第1種基于滑動窗口的數(shù)據(jù)流閉合高效用項(xiàng)集挖掘算法，以解決數(shù)據(jù)流全集高效用項(xiàng)集挖掘帶來的項(xiàng)集信息冗余問題，而這一主題在此之前尚未被探討.這項(xiàng)工作的貢獻(xiàn)總結(jié)為：

1) 提出一個名為CH-List的新穎數(shù)據(jù)結(jié)構(gòu)，它可以有效地計(jì)算內(nèi)存中項(xiàng)集的效用和支持?jǐn)?shù)，而無需重復(fù)掃描原始數(shù)據(jù)流.CH-List相較于傳統(tǒng)閉合EU_List[20]，IUL(incremental utility-list)[23]等結(jié)構(gòu)，適用于數(shù)據(jù)流滑動窗口，在批次的插入和刪除方面非常有效.

2) 提出了一種新的融合CH-List結(jié)構(gòu)的算法，即基于滑動窗口模型的數(shù)據(jù)流閉合高效用項(xiàng)集挖掘(closed high utility itemsets mining over data stream based on sliding window model, CHUI_DS)算法.該算法采用分而治之的思想，通過創(chuàng)新一種事務(wù)重組方法以及改進(jìn)的閉包挖掘技術(shù)，近而在數(shù)據(jù)流滑動窗口中挖掘出完整的CHUI.

3) 對真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集進(jìn)行了廣泛的實(shí)驗(yàn)研究，以評估所提出算法的性能.實(shí)驗(yàn)結(jié)果表明：CHUI_DS的總體性能優(yōu)于目前最先進(jìn)的相關(guān)批處理和增量算法.此外，算法在不同窗口環(huán)境下的可擴(kuò)展性也得到有效驗(yàn)證.

1 相關(guān)工作

高效用項(xiàng)集挖掘的缺點(diǎn)是算法返回的結(jié)果集數(shù)量巨大，這使得分析這些結(jié)果集成為一項(xiàng)艱巨的任務(wù)，同時它們包含很多冗余項(xiàng)集信息.針對以上問題，Tseng等人[19]提出了一種緊湊且無損的高效用項(xiàng)集表示形式，如果項(xiàng)集的效用不小于用戶指定的最小效用閾值，并且不存在相同支持?jǐn)?shù)的真超集，則該項(xiàng)集稱為閉合高效用項(xiàng)集.每個CHUI都由一種稱為效用單元陣列的特殊結(jié)構(gòu)進(jìn)行注釋，采用這種結(jié)構(gòu)，高效用項(xiàng)集全集得以在無需訪問原始數(shù)據(jù)庫的情況下從該集合派生出來，因此CHUI的集合是無損的.另外，研究者提出了第1種發(fā)現(xiàn)靜態(tài)數(shù)據(jù)庫中CHUI的算法，名為CHUD[19]，以及一種名為DAHU的方法從完整的CHUI集中恢復(fù)所有HUI.Wu等人[20]提出了一種名為CHUI-Miner的新穎算法，該算法依賴Utility-List垂直列表結(jié)構(gòu)以單階段發(fā)現(xiàn)CHUI.通過該結(jié)構(gòu)的剩余效用(remaining utility, RU)屬性，可以獲得項(xiàng)集超集更嚴(yán)格的效用上限，從而可以較大范圍地修剪搜索空間.Fournier-Viger等人[21]提出了一種名為EFIM-Closed的閉合高效用項(xiàng)集挖掘算法.該算法包括3種修剪策略，分別為閉合跳躍、向前閉合檢查和向后閉合檢查，以修剪非閉合的HUI.此外，它還引入了事務(wù)投影和事務(wù)合并機(jī)制.實(shí)驗(yàn)結(jié)果表明：與CHUD算法相比，EFIM-Closed運(yùn)行快1個數(shù)量級以上，并且消耗的內(nèi)存少1個數(shù)量級.Dam等人[22]提出一種稱為CLS-Miner的算法，應(yīng)用鏈估計(jì)效用共現(xiàn)修剪、較低分支修剪和按覆蓋范圍修剪等新穎剪枝策略減少搜索空間，提出的CLS-Miner算法優(yōu)于CHUD和CHUI-Miner算法.

在增量數(shù)據(jù)環(huán)境中，同樣針對上段描述的相關(guān)問題，研究者提出IncCHUI[23]算法，其使用增量效用列表結(jié)構(gòu)從數(shù)據(jù)庫中挖掘CHUI.IncCHUI僅掃描原始或更新的數(shù)據(jù)庫1次，以構(gòu)造單個項(xiàng)的列表.使用稱為CHT的散列表存儲目前為止發(fā)現(xiàn)的CHUI.對于在更新的數(shù)據(jù)庫上挖掘時發(fā)現(xiàn)的每個閉合高效用項(xiàng)集P，算法首先檢查該項(xiàng)集是否已在CHT中，再決定是否需要將P插入表CHT中.這是目前首個對增量數(shù)據(jù)庫進(jìn)行閉合高效用項(xiàng)集挖掘的算法.

在數(shù)據(jù)流上挖掘HUI比在靜態(tài)或增量數(shù)據(jù)庫中更具挑戰(zhàn)性.因?yàn)閭魅氲臄?shù)據(jù)流必須在時間和存儲內(nèi)存約束下進(jìn)行實(shí)時處理.目前有3種主要的流處理模型[24-25]：1)阻尼窗口模型；2)地標(biāo)窗口模型；3)滑動窗口模型.其中窗口是1組連續(xù)交易，被視為數(shù)據(jù)流中的單位.在滑動窗口模型[26-27]中，方法使用固定大小窗口中的最新數(shù)據(jù)來發(fā)現(xiàn)數(shù)據(jù)流中有意義的項(xiàng)集.該模型因能夠強(qiáng)調(diào)最新數(shù)據(jù)并占用較小內(nèi)存資源而被廣泛用于數(shù)據(jù)流挖掘.為考慮資源受限環(huán)境中真實(shí)的數(shù)據(jù)流挖掘任務(wù)，Ahmed等人[16]提出了基于滑動窗口的HUIM.為了滿足向下閉包特性，早前基于滑動窗口的研究采用了事務(wù)加權(quán)效用(transaction weighted utility, TWU)高估概念[28]，缺點(diǎn)是導(dǎo)致生成大量候選項(xiàng)集，處理這些候選項(xiàng)集需要更多的執(zhí)行時間.Ryang等人[17]提出一種樹結(jié)構(gòu)的高效用挖掘算法SHU-Grow，用于從滑動窗口模型中挖掘HUI.此外，其還開發(fā)了2種技術(shù)：降低的全局估計(jì)效用(reducing global estimated utilities, RGE)和降低的局部估計(jì)效用(reducing local estimated utilities, RLE)，以取代TWU高估方法來減少搜索空間和候選項(xiàng)集.上述在數(shù)據(jù)流上挖掘高效用項(xiàng)集的算法是2階段的.隨后Jaysawal等人[18]提出一種有效的單程1階段算法SOHUPDS來在數(shù)據(jù)流上挖掘HUI，借助IUDataListSW結(jié)構(gòu)，存儲項(xiàng)目在事務(wù)中的位置和實(shí)際效用，以及可以從項(xiàng)目擴(kuò)展項(xiàng)集效用上限，它比之前的算法更加有效.

一些工作還提出了在數(shù)據(jù)流上挖掘HUI的衍生算法.Zihayat等人[29]提出了一種稱為HUDS-tree的樹狀結(jié)構(gòu)，樹中每個節(jié)點(diǎn)逐批維護(hù)高估的效用值.采用基于滑動窗口模型的2階段算法T-HUDS挖掘前k個HUI，它在第1階段生成候選的高效用項(xiàng)集，在第2階段驗(yàn)證項(xiàng)集的確切效用.Dawar等人[15]提出一種稱為Vert_top-k_DS的算法，該算法可在不生成任何候選項(xiàng)的前提下挖掘出前k個HUI.其在動態(tài)閾值提升策略的基礎(chǔ)上，利用k-項(xiàng)集在公共批次的實(shí)際效用值增加窗口滑動時的初始閾值，是目前最先進(jìn)的數(shù)據(jù)流top-k高效用項(xiàng)集挖掘算法.在文獻(xiàn)[30-31]中提出的算法用于在數(shù)據(jù)流上挖掘高效用序列模式(high utility sequence pattern, HUSP)，前者提出的HUSP-Stream是在數(shù)據(jù)流上查找HUSP的第1種方法，后者提出了一種名為HUSP-UT的新挖掘算法，實(shí)驗(yàn)性能大幅優(yōu)于HUSP-Stream.

2 定 義

設(shè)由不同項(xiàng)構(gòu)成的有限集合I*={I1,I2,…,Im}，其中每個項(xiàng)Ii∈I*都與1個正數(shù)p(Ii,DS)相關(guān)聯(lián)，稱為外部效用.令數(shù)據(jù)流DS=(T1,T2,…,Ts)是有限事務(wù)組成的序列，數(shù)據(jù)流DS中的每個事務(wù)Tr(1≤r≤s)表示第r個到達(dá)的事務(wù)，其中每個事務(wù)Tr∈DS是I*的子集，并且具有唯一的標(biāo)識符r，稱為其Tid.在事務(wù)Tr中，每一項(xiàng)Ii∈I*都與1個正數(shù)q(Ii,Tr)相關(guān)聯(lián)，在Tr中稱為其內(nèi)部效用(例如購買數(shù)量).項(xiàng)集P是由1組屬于I*的項(xiàng){I1,I2,…,Ik}構(gòu)成的集合，P的長度表示為k，其中P?I*且1≤k≤m.

在滑動窗口模型中，每個窗口SWk由固定數(shù)量的n個最近的批次組成的有序集合,可以表示為SWk=(Bj,Bj+1,…,Bn)，該窗口大小(winSize)為n.批次Bj包含固定數(shù)量的事務(wù)，即Bj=(T1,T2,…,Tr).窗口SWk-1滑動時，最舊的批次被從窗口移除出去，最新的一個批次將被添加進(jìn)來，這個新生成的窗口即為SWk.其中Bj+1,Bj+2,…,Bn-1稱為SWk-1和SWk的公共批次(CommomBatches).

Fig.1 Example of stream data圖1 數(shù)據(jù)流示例

圖1顯示了一個數(shù)據(jù)流的示例，示例中的每一行代表1個事務(wù)，事務(wù)中每個字母代表1個項(xiàng)目，并在右側(cè)附其內(nèi)部效用.表1列出了每個項(xiàng)目的外部效用.該數(shù)據(jù)流分為3個批次B1,B2,B3，其中每個滑動窗口由2個批次組成.示例中共存在2個滑動窗口，SW1={B1,B2}和SW2={B2,B3}.在此，SW1是初始滑動窗口.隨著新數(shù)據(jù)的到達(dá)，由于第1個窗口已滿，通過移除最舊的批次并插入新批次后，SW1更新為滑動窗口SW2.

Table 1 Profit Table表1 外部效用表

例如，T1的事務(wù)效用為TU(T1)=U({ABCE},T1)=23.

定義4.超集和子集.設(shè)非空項(xiàng)集X和Y.X是Y的子集，如果X?Y，則等效地Y是X的超集.如果X?Y，則X是Y的真子集，而Y是X的真超集.

例如，SUPSW1({ACE})=|TidSetSW1({ACE})|=|{1,3,4,6}|=4.

屬性1.對窗口SWk中的k項(xiàng)集X，SUPSWk(X)=|TidSetSWk(I1)∩TidSetSWk(I2)∩…∩TidSetSWk(Ik)|.

屬性2.對窗口SWk,令項(xiàng)集Y為X的真超集，則有TidSetSWk(Y)?TidSetSWk(X).

定義6.閉合項(xiàng)集.如果SWk中不存在真超項(xiàng)集Y?X使得SUPSWk(X)=SUPSWk(Y)，則項(xiàng)集X在窗口SWk中稱為閉合項(xiàng)集.閉合項(xiàng)集的完整集合表示為CSWk.

例如，窗口SW1中,closure({AB})=T1∩T5∩T6={ABCE}∩{ABEF}∩{ABCDE}={ABE}.

定義9.總效用.滑動窗口SWk的總效用表示為TotalUtility，并定義為

定義10.高效用項(xiàng)集(HUI).如果窗口SWk中的項(xiàng)集X的效用USWk(X)≥minutil，則在SWk中將X稱為高效用項(xiàng)集.

例如，窗口SW1中{BE}的效用為USW1(BE)=U(BE，B1)+U(BE，B2)=9+25=34.SW1中事務(wù)的總效用為172.若minutil=30.96，則{BE}在SW1中是高效用項(xiàng)集，因?yàn)槠湫в肬SW1(BE)=34>minutil.

定義11.閉合高效用項(xiàng)集(CHUI).如果項(xiàng)集P是SWk中的高效用項(xiàng)集且滿足P?CSWk，則P為閉合高效用項(xiàng)集.

屬性3.對于任何高效用項(xiàng)集X，都存在一個閉合高效用項(xiàng)集Y，使得Y=closure(X)并且U(Y)≥U(X).

屬性4.對于不是閉合高效用項(xiàng)集的任何項(xiàng)集X，其所有子集都是低效用的.

例如，TWUSW1(AC)=TU(T1)+TU(T3)+TU(T4)+TU(T6)=23+30+39+26=118.

定義13[28].事務(wù)權(quán)重使用率向下封閉(TWDC)屬性.對于任何項(xiàng)集X，如果其TWU

定義14.窗口中的高事務(wù)加權(quán)效用項(xiàng)集.如果TWUSWk(X)≥minutil，則項(xiàng)集X稱為窗口SWk的高事務(wù)加權(quán)效用項(xiàng)集.

屬性5[28].使用TWU修剪.假設(shè)有一個項(xiàng)集X不是高TWU項(xiàng)集，則X及其超集均是低效用項(xiàng)集.

對于數(shù)據(jù)流中的滑動窗口SWk，問題是要在SWk中找到所有CHUI，其中minutil是用戶定義的參數(shù).

3 CHUI_DS算法

本節(jié)提出一種新的效用列表結(jié)構(gòu)CH-List和基于滑動窗口模型的數(shù)據(jù)流閉合高效用項(xiàng)集挖掘算法CHUI_DS，利用滑動窗口在數(shù)據(jù)流中挖掘閉合項(xiàng)集是為了在有限的內(nèi)存資源下從連續(xù)數(shù)據(jù)中及時發(fā)現(xiàn)最新的無冗余項(xiàng)集.此外，算法開發(fā)了2種技術(shù)：基于批次剩余效用表(batch based remaining utility table, BRU_table)的公共批次事務(wù)重組方法和減少閉包計(jì)算的效用剪枝技術(shù)，以通過高估候選閉包項(xiàng)集的效用來減少搜索空間.在描述本節(jié)的數(shù)據(jù)結(jié)構(gòu)之前，先介紹一些術(shù)語.

定義18.項(xiàng)集的擴(kuò)展.設(shè)X={x1,x2,…,xv}(Xi∈I*,1≤i≤v)和Y={y1,y2,…,yu}(yj∈I*,1≤j≤u)為2-項(xiàng)集.如果X?Y并且每個項(xiàng)在TWU升序排序中都在X的項(xiàng)之后，則Y是X的擴(kuò)展.例如，圖1中{CAE}并非{CE}的擴(kuò)展，而是{CA}的擴(kuò)展.因?yàn)楦鶕?jù)表2示出的滑動窗口SW1中各項(xiàng)的TWU，以TWU的升序排列的項(xiàng)的順序?yàn)镕BDCAE.在此，{A}排在{E}之前.

Table 2 TWU Information of Items in SW1表2 SW1中項(xiàng)的TWU信息

3.1 數(shù)據(jù)結(jié)構(gòu)BRU_table和公共批次事務(wù)重組

本文提出一種名為BRU_table的雙重散列表，該結(jié)構(gòu)是在對當(dāng)前窗口第1次事務(wù)掃描時被構(gòu)建或更新的，包含了當(dāng)前窗口的所有批次，并為每個批次給予一個唯一的編號，其值為該批次所包含的事務(wù)Tid和該事務(wù)對應(yīng)的BRU，BRU初始值為每個事務(wù)的事務(wù)效用.隨著窗口的滑動，批次更新的同時散列表的項(xiàng)也會隨之更新.待新批次到來，在移除各項(xiàng)CH-List舊批次信息時同步移除其批次的BRU_table項(xiàng).

BRU_table作為臨時存儲結(jié)構(gòu)，為新窗口的事務(wù)重組提供了必要信息.因?yàn)殡S著新批次的到來，項(xiàng)的TWU和順序已經(jīng)發(fā)生變化，根據(jù)屬性6，剩余效用修剪策略將無法正確對新搜索空間進(jìn)行剪枝.需要根據(jù)當(dāng)前事務(wù)元組信息和TWU順序重構(gòu)前一窗口和新窗口的CH-List公共批次事務(wù)元組.從更新后TWU最小的項(xiàng)開始遍歷公共批次中所有CH-List，并相應(yīng)地更新RU值.在遍歷時，使用BRU_table中存儲的相關(guān)批次散列表及其初值來存儲和計(jì)算具有相同Tid的RU值，并且每個散列項(xiàng)條目處的BRU值將減去該處當(dāng)前RU值.不同于IncCHUI[23]的全局列表更新結(jié)構(gòu)，本文提出的結(jié)構(gòu)不需要對項(xiàng)的總順序倒序遍歷，且適用于滑動窗口機(jī)制.圖2為一個BRU_table結(jié)構(gòu)示意圖，此時其存儲的是第1個窗口2個批次的事務(wù)信息.

Fig.2 BRU_table in SW1after the first scan圖2 窗口SW1首次掃描后的BRU_table

3.2 CH-List數(shù)據(jù)結(jié)構(gòu)

各批次構(gòu)成的FIFO隊(duì)列效用信息由CH-List維護(hù)，該結(jié)構(gòu)記錄先前與當(dāng)前窗口的項(xiàng)集有關(guān)效用信息.在提出的算法中，批次事務(wù)中的每個項(xiàng)(集合)都與一個CH-List列表相關(guān)聯(lián).項(xiàng)(集合)X的CH-List包括Utility-List以及一種名為HistorySet(X)的有序集合.X的Utility-List由當(dāng)前窗口各批次的事務(wù)元組組成.X的Utility-List中的各個元組存儲在以批次號(Bid)為鍵、批次元組為值的散列表中.每個元組代表重組事務(wù)Tr中X的效用信息，并具有3個字段：Tid，EU和RU.Tid存儲包含項(xiàng)集的事務(wù)標(biāo)識符,EU是項(xiàng)集的實(shí)際效用,RU是項(xiàng)集的剩余效用.當(dāng)新批次的事務(wù)到達(dá)時，按這些事務(wù)構(gòu)造的元組會被添加到隊(duì)列的尾部.一旦隊(duì)列的大小超過窗口大小，則將屬于第1批次的元組從項(xiàng)的CH-List中移除.可以看出，在滑動窗口滑動過程中，其效用信息更新是以批次為單位的.CH-List相較于傳統(tǒng)EU-List[20]數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)是它可以快速執(zhí)行批次的插入和刪除.例如，分別在圖3(a)(b)中示出了滑動窗口SW1和SW2中項(xiàng){A}的CH-List變化情況.

Fig.3 CH-List{A} in different windows圖3 不同窗口的項(xiàng){A}的CH-List變化

Fig.4 CH-List{CA} in SW1圖4 項(xiàng)集{CA}在SW1的CH-List

通過掃描滑動窗口2次來構(gòu)造CH-List數(shù)據(jù)結(jié)構(gòu).在第1次掃描中，將計(jì)算項(xiàng)的TWU和事務(wù)效用.在第2次掃描期間，根據(jù)TWU的升序?qū)γ總€事務(wù)中的項(xiàng)目進(jìn)行排序，由上述過程產(chǎn)生重組事務(wù).接著程序?yàn)槊總€項(xiàng)更新CH-List信息，由2個項(xiàng)組成的項(xiàng)集，其CH-List的Utility-List部分是通過將單個項(xiàng)的Utility-List相交而創(chuàng)建的.第1步是查找包含2個項(xiàng)的批次.例如SW1中，要分別從CH-List{C}和{A}構(gòu)造項(xiàng)集{CA}的CH-List.{C}和{A}的CH-List共同批次為B1，B2.一旦確定了其共同出現(xiàn)的批次，就確定了包含這2個項(xiàng)的事務(wù).項(xiàng){C}和{A}分別出現(xiàn)在事務(wù)T1，T3，T4，T6中.圖4中顯示了項(xiàng)集{CA}的CH-List.構(gòu)造k-項(xiàng)集的CH-List的過程與上述過程相似.

定義19.在項(xiàng)集X的CH-List中，其EU和RU值的總和分別表示為SumEUSWk(X)和SumRUSWk(X)，它們是將當(dāng)前窗口SWk下列表所含所有批次事務(wù)的EU，RU分別相加得到的.

屬性6.如果SumEUSWk(X)+SumRUSWk(X)

證明.設(shè)項(xiàng)集Y為X的擴(kuò)展，X?Y，TidSetSWk(Y)?TidSetSWk(X).令Y/X表示Y中在X之后的所有項(xiàng)的集合.根據(jù)定義2和定義16，存在:

且

因此，

證畢.

3.3 CHUI_DS

收到一個新批次Bnew后，算法會檢查該窗口SWk是否為初次創(chuàng)建，若非創(chuàng)建的首個窗口，則更新前一個窗口SWk-1中項(xiàng)的CH-List，刪除這些CH-List中最舊批次Bold存儲的信息；同時清除BRU_table中關(guān)于最舊批次事務(wù)的相關(guān)值(算法1的行①～④).逐個遍歷新批次的事務(wù)，對事務(wù)中的項(xiàng)進(jìn)行掃描，檢查它的CH-List是否為空.若為空，則算法創(chuàng)建其CH-List結(jié)構(gòu)，并計(jì)算當(dāng)前批次所在窗口SWk下各項(xiàng)的TWU.否則，為當(dāng)前項(xiàng)更新該批次插入后的TWU.本文的算法逐批維護(hù)事務(wù)中項(xiàng)的TWU，以便在新批次到達(dá)并移除最舊的批次時可以迅速更新項(xiàng)的TWU.同時新批次的各事務(wù)效用會被添加到BRU_table散列表中(算法1的行⑤～).

若窗口批次數(shù)達(dá)到設(shè)定值，令SWk中所有項(xiàng)屬于集合I.按對集合I中各項(xiàng)的CH-List排序(算法1的行～).接下來通過BRU_table及CH-List公共批次信息進(jìn)行公共批次事務(wù)重組.在算法2中，按照項(xiàng)的TWU升序遍歷各項(xiàng)在公共批次的所有事務(wù)，根據(jù)當(dāng)前事務(wù)元組信息和各事務(wù)BRU重構(gòu)事務(wù)元組，更新項(xiàng)的CH-List，同時更新各事務(wù)的BRU值(算法2的行①～⑦).以圖1為例，SW1與SW2窗口公共批次B2中{C}，{D}的CH-List和BRU_table在重構(gòu)過程中變化分別如圖5和圖6所示.

Fig.5 CommonBatches changes during revised CH-List圖5 SW2公共批次重組過程中CH-List變化

Fig.6 BRU_table changes during revisedCH-List in SW2圖6 SW2公共批次重組過程中BRU_table變化

緊接著返回算法1，對SWk中除公共批次之外的批次進(jìn)行第2次掃描，以創(chuàng)建和更新CH-List中的元組信息.待I中所有項(xiàng)的CH-List創(chuàng)建完成，根據(jù)屬性5篩選出所有高TWU的項(xiàng)組成集合I′(算法1的行～).

算法1.CHUI_DS算法.

輸入:批次Bold,Bnew;窗口大小winSize;批次事務(wù)數(shù)number_of_batches;列表CH-List;窗口SWk;閾值minutil;項(xiàng)的集合I.

輸出:數(shù)據(jù)流中所有CHUI.

① ifSWk不是首個滑動窗口then

② 更新前一窗口SWk-1中屬于I的項(xiàng)的

CH-List;

③ 將最舊批次Bold從BRU_table中移除；

④ end if

⑤ for事務(wù)Tr∈Bnewdo

⑥ 構(gòu)造記錄(Tid,TU)插入BRU_table(Bnew);

⑦ foritem∈Trdo

⑧ ifitem的CH-List不存在 then

⑨ 創(chuàng)建CH-List，更新item的集合I;

⑩ 首次計(jì)算item的TWUSWk;

算法2.公共批次事務(wù)重組算法.

輸入:列表CH-List、散列表BRU_table、窗口SWk；

輸出:公共批次事務(wù)重組后的CH-List.

① forCL(i)∈CH-List組成的集合 do

② forCL(i)在窗口SWk-1和SWk公共批次中的全部元組do

③ 元組RU=BRU_table[Bid][Tid]-元組EU;

④BRU_table[Bid][Tid]=元組RU;

⑤ end for

⑥ end for

⑦ 返回CH-List.

接下來就可以開始窗口SWk的挖掘過程，調(diào)用算法CHUI_DS_Miner以使用有前途的項(xiàng)構(gòu)成的集合I′生成CHUI.該過程具有5個輸入?yún)?shù)：1)項(xiàng)集X；2)HistorySet(X)；3)X的擴(kuò)展(extendOfX)；4)minutil；5)窗口SWk.對于該算法發(fā)現(xiàn)的每個閉合項(xiàng)集X，構(gòu)造其CH-List來計(jì)算其效用，以確定其是否為CHUI.如果實(shí)際效用和剩余效用之和小于minutil，則將修剪搜索空間.CHUI_DS_Miner的偽代碼如算法3所示：

算法3.CHUI_DS_Miner算法.

輸入:項(xiàng)集X、集合HistorySet(X)、X的擴(kuò)展集合extendOfX、閾值minutil、窗口SWk；

輸出:窗口SWk中所有CHUI.

① for項(xiàng)a∈extendOfXdo

② 將a從extendOfX移除；

③Y←X∪a；

④ 初始化extendOfY={}；

⑤ 構(gòu)造CH-List(Y)；

⑥HistorySet(Y)=HistorySet(X)；

⑦ ifSumEUSWk(Y)+SumRUSWk(Y)≥

minutilthen

⑧ ifSubsumedCheck(Y,HistorySet(Y))=

false then

⑨ for項(xiàng)Z∈extendOfXdo

⑩ ifTidSetSWk(Y)?TidSetSWk(Z)

then

SumRUSWk(Y)

History-Set(Y),extendOfY,

minutil,SWk)；

定義20.閉合項(xiàng)集的包含.如果Y?S并且SUPSWk(Y)=SUPSWk(S)，則項(xiàng)集Y被包含在項(xiàng)集S中.例如SW1中，{C}被{ACE}閉合包含，因?yàn)閧C}?{ACE}并且SUPSW1({C})=SUPSW1({ACE}).

屬性7.在SWk中，給定2個項(xiàng)集X和S，如果X?S且SUPSWk(X)=SUPSWk(S)，則closure(X)=closure(S).

屬性8.在SWk中，給定1個項(xiàng)集X和1個項(xiàng)Ii∈I*(1≤i≤m)，則TidSetSWk(X)?TidSetSWk(I*)和I*∈closure(X)互為充要條件.

根據(jù)定義20，如果存在1個包含Y的已挖掘的閉合高效用項(xiàng)集S，則可以得出結(jié)論：Y沒有閉合，并且closure(S)=closure(Y).因此，可以安全地修剪項(xiàng)集Y并停止探索Y后續(xù)超集的搜索空間.否則，程序繼續(xù)向下探索.

假設(shè)Y通過了閉合包含檢測過程，接下來計(jì)算Y的閉包，并將Y更新后的CH-List結(jié)構(gòu)作為其閉包的CH-List(算法3的行⑨～).其執(zhí)行過程為：初始化extendOfY集合，對于extendOfX中的每個項(xiàng)Z，算法檢查TidSetSWk(Z)中是否包含TidSetSWk(Y).由屬性8可知Z是否包含在Y的閉包中.若包含，則在extendOfX中移除Z，并將Z添加到Y(jié)，更新Y的CH-List.處理完extendOfX中的所有項(xiàng)后，根據(jù)此時extendOfX的值，更新extendOfY，返回更新后已經(jīng)閉合的Y和extendOfY.

與DCI_CLOSED[32]和IncCHUI[23]相比，本文算法依據(jù)屬性6，通過添加剩余效用剪枝策略修剪潛在低效用的閉包候選對象(算法3的行)，避免了構(gòu)造低候選效用或非閉合項(xiàng)集的效用列表.

若Y的實(shí)際效用不小于minutil，則算法3輸出Y為CHUI，因?yàn)閅滿足條件：閉合項(xiàng)集、高效用項(xiàng)集.然后CHUI_DS_Miner算法調(diào)用自身以進(jìn)一步遞歸探索搜索空間并找到作為Y后續(xù)超集的CHUI.遞歸過程完成后，將項(xiàng)a添加到HistorySet(X)中.待對所有項(xiàng)遍歷完畢，得到該窗口SWk中所有CHUI.

在滑動窗口模型中，最后winSize-1個批次在2個連續(xù)的窗口之間保持相同.即在對新的窗口掃描前，上一窗口項(xiàng)其CH-List最后winSize-1批次的元組將得到保存.因?yàn)槠錇橥诰蛳乱淮翱陂]合項(xiàng)集提供必要事務(wù)計(jì)數(shù)信息.同時，由于進(jìn)入新滑動窗口，項(xiàng)的TWU被重新計(jì)算，CH-List也需要更新.因此，相比于EU-List，CH-List取消了每個項(xiàng)的PostSet屬性，CHUI_DS中的全局extendOfX結(jié)構(gòu)在實(shí)現(xiàn)PostSet原有功能的基礎(chǔ)上，僅在項(xiàng)進(jìn)行排序后初始1次，節(jié)約了內(nèi)存空間.

接下來，本文通過一個例子來說明算法的工作原理.考慮圖1中所示的數(shù)據(jù)庫.令minutil=30，窗口大小為2.第1個窗口由批次B1和B2組成.每條事務(wù)中的項(xiàng)均按照TWU的升序排序.對于第1個滑動窗口，項(xiàng)的排序?yàn)镕BDCAE.獲取完整的滑動窗口后，本文的算法將構(gòu)建單個項(xiàng)的CH-List，由于每個項(xiàng)的TWU全部大于30，因此將其全部加入extendOfX中.

依次向CHUI_DS_Miner傳入?，HistorySet(?)，extendOfX等參數(shù)，開始遍歷extendOfX，并首先處理其中的第1個項(xiàng){F}.同時將{F}從extendOfX集合中去除，而后?和{F}進(jìn)行組合得到{F}，并構(gòu)建其組合后的CH-List.因?yàn)閄此時為?，所以：

HistorySet({F})=HistorySet(?)=?.
SumEUSW1({F})+SumRUSW1({F})=
36+57=93>30.

下一步對{F}進(jìn)行包含檢測，由于{F}是初始結(jié)點(diǎn)，不會出現(xiàn)被前項(xiàng)包含的情況.因此可通過集合extendOfX計(jì)算{F}的閉包.首先循環(huán)extendOfX中的各項(xiàng)，此時因?yàn)閧F}的Tid集合不含于{B}所在的集合，于是跳過本項(xiàng)直接進(jìn)入下一循環(huán).否則，基于{F}的事務(wù)集合構(gòu)造{FB}的效用列表，并將{B}從extendOfX中刪除.待遍歷完最后1個元素，返回的結(jié)果是{F}，extendOfX={B,D,C,A,E}.因?yàn)閁SW1({F})=36,所以{F}為找到的第1個CHUI，支持計(jì)數(shù)為3.之后遞歸進(jìn)行搜索，此時的X={F}，其繼續(xù)和{B}聯(lián)接，由于SumEUSW1({FB})+SumRUSW1({FB})=32+22=54>36，因此可以進(jìn)行閉包計(jì)算，此時Y={FB}.直到遞歸完{F,B,D,C}下的所有搜索空間,HistorySet({FBD})={C}，緊接著遍歷{F,B,D}的其余搜索擴(kuò)展{A,E}，由于2次執(zhí)行SubsumedCheck均返回false，所以本次遞歸停止，開始回溯.此時HistorySet({FB})={D}.以同樣的方法，算法完成對剩余所有搜索空間的搜索，最終完成對第1個滑動窗口的閉合高效用項(xiàng)集挖掘.

在下一批次B3到達(dá)時，算法1構(gòu)造滑動窗口SW2.窗口SW2中的項(xiàng)目TWU如表3所示.算法從第2個窗口中繼續(xù)運(yùn)行以挖掘CHUI，當(dāng)沒有新傳入的批處理數(shù)據(jù)時算法終止.

Table 3 TWU Information of Items in SW2表3 SW2中項(xiàng)的TWU信息

4 實(shí)驗(yàn)與結(jié)果

本節(jié)提供了廣泛的實(shí)驗(yàn)以評估算法的效率，包括其在3種情況下的性能：1)最小效用閾值；2)窗口大小和批次數(shù)；3)數(shù)據(jù)集的大小(可伸縮性測試).由于CHUI _DS是第1種用于數(shù)據(jù)流環(huán)境挖掘CHUI的算法，因此，針對最新的CHUI挖掘算法，評估其性能的可靠方法是將其與靜態(tài)或增量數(shù)據(jù)庫中現(xiàn)有的算法進(jìn)行比較.對于情況1(變化最小效用閾值角度)和情況3(變化數(shù)據(jù)集大小的角度)，本文的算法CHUI _DS以單窗口批處理方式運(yùn)行，對比算法包括CHUI-Miner[20]，EFIM-Closed[21]，CLS-Miner[22]，IncCHUI[23].CHUI-Miner,IncCHUI采用效用列表結(jié)構(gòu)，IncCHUI是目前為止最先進(jìn)的增量閉合高效用挖掘算法，具有與算法CHUI _DS類似的搜索技術(shù).而EFIM-Closed利用數(shù)據(jù)庫投影和事務(wù)合并技術(shù)，是目前對靜態(tài)數(shù)據(jù)挖掘閉合高效用項(xiàng)集最高效的算法之一.情況2中，實(shí)驗(yàn)主要通過控制窗口和批次大小對算法的影響來驗(yàn)證算法性能，對比算法是去掉閉包計(jì)算過程剪枝策略的CHUI_DS，稱為CHUI_DS(no_sup).表4列出了本文用于實(shí)驗(yàn)的數(shù)據(jù)集，包括稀疏和密集數(shù)據(jù)集.其中Connect數(shù)據(jù)集是真實(shí)的數(shù)據(jù)集，但具有合成效用值，內(nèi)部效用值是通過在[1，10]中均勻分布生成的，其余數(shù)據(jù)集為真實(shí)效用值.

Table 4 Details of the Datasets表4 實(shí)驗(yàn)數(shù)據(jù)集

4.1 最小效用閾值的影響

本節(jié)在每個數(shù)據(jù)集上運(yùn)行所有比較的算法，同時逐漸增大最小效用閾值，直到觀察到明顯的對比結(jié)果為止.執(zhí)行時間包括讀取輸入數(shù)據(jù)、發(fā)現(xiàn)項(xiàng)集以及將結(jié)果寫入輸出文件的總時間.

Fig.7 Runtime comparison when varying utility threshold圖7 不同效用閾值時的運(yùn)行時間比較

在圖7中，所有對比算法的運(yùn)行時間都隨著minutil的增加而逐漸降低至某個較低水平，因?yàn)樗惴ǖ倪\(yùn)行時間與產(chǎn)生的中間項(xiàng)集數(shù)量成正比，當(dāng)閾值越大時，產(chǎn)生的中間項(xiàng)集越少，其運(yùn)行時間就越短.在這個過程中，不同算法使用的數(shù)據(jù)庫掃描方式、閉合項(xiàng)集搜索策略以及剪枝策略都不盡相同，造成下降速率也隨之不同.在Connect數(shù)據(jù)集上，本文提出的算法運(yùn)行時間大幅小于除EFIM-Closed之外的所有算法.盡管minutil較大時，EFIM-Closed比其余算法快；但當(dāng)minutil較小時，EFIM-Closed需要增加大量執(zhí)行時間，消耗的時間最大.這是因?yàn)镃onnect數(shù)據(jù)集平均事務(wù)長度在實(shí)驗(yàn)的所有數(shù)據(jù)集中最長，而EFIM-Closed需遞歸構(gòu)建子投影數(shù)據(jù)庫，這個過程依靠多次查找每條投影事務(wù)數(shù)組以尋找待擴(kuò)展投影項(xiàng)索引，閾值低時的侯選待投影項(xiàng)數(shù)量巨大，近而導(dǎo)致EFIM-Closed在該數(shù)據(jù)集上表現(xiàn)差異較大.因此本文提出的算法在該數(shù)據(jù)集不同閾值下平均運(yùn)行時間最低，總體表現(xiàn)優(yōu)異.對于其他數(shù)據(jù)集，本文提出的算法比IncCHUI，EFIM-Closed都要略快，并且和CHUI-Miner拉開了較大差距.特別是在Connect，Mushroom，Chainstore數(shù)據(jù)集上，當(dāng)閾值設(shè)置較低時運(yùn)行時間大約比IncCHUI，EFIM-Closed縮短1/2.此外，當(dāng)在Foodmart，Mushroom數(shù)據(jù)集上降低minutil時，本文算法的運(yùn)行時間幾乎相同.同時可以看到CHUI-Miner在絕大部分?jǐn)?shù)據(jù)集上具有最大的時間消耗.原因可以解釋如下.

盡管CHUI-Miner，CLS-Miner，IncCHUI和本文的算法采用相似的效用列表結(jié)構(gòu)，但是CHUI-Miner和CLS-Miner都使用傳統(tǒng)的效用列表，需要2次掃描數(shù)據(jù)庫以構(gòu)建效用列表，且在閉包計(jì)算等過程缺乏修剪策略.這也適用于EFIM-Closed，即使它采用了不同的技術(shù)來降低數(shù)據(jù)庫掃描的成本.IncCHUI其閉包計(jì)算過程并沒有使用適用于非增量環(huán)境的修剪策略，因此在閾值較低時慢于本文提出的算法.

4.2 不同窗口和批次大小的效率測試

在滑動窗口模型中，算法使用2個參數(shù)：1)窗口中的批次數(shù)量；2)批次中的事務(wù)數(shù)量.為了分析它們的影響，本節(jié)使用密集的數(shù)據(jù)集“Accidents”和稀疏的數(shù)據(jù)集“Chainstore”在各種參數(shù)下進(jìn)行實(shí)驗(yàn).其中Accidents的實(shí)驗(yàn)閾值設(shè)定為1.5×107，Chainstore的實(shí)驗(yàn)閾值為9.5×107.由于比較的算法是基于窗口的，因此其挖掘性能通常取決于窗口大小和批次大小.首先，比較窗口中含不同批次時的總運(yùn)行時間，即固定Accidents每個批次的事務(wù)數(shù)為3×104，Chainstore每個批次的事務(wù)數(shù)為1×105.2個數(shù)據(jù)集的窗口大小參數(shù)設(shè)置，以及實(shí)驗(yàn)結(jié)果如圖8所示：

Fig.8 Accumulated runtime comparison when varying window sizes圖8 不同窗口大小下運(yùn)行時間對比

圖8表明，CHUI_DS(no_sup)在2個數(shù)據(jù)集中表現(xiàn)都要慢于CHUI_DS.特別是在Accidents這種密集程度較大的數(shù)據(jù)集上，表現(xiàn)差距較大.原因在于本文是利用改進(jìn)的閉包計(jì)算和遞歸搜索進(jìn)行項(xiàng)集的閉合擴(kuò)展，而密集數(shù)據(jù)集相比于稀疏數(shù)據(jù)集需要更多次深度搜索.若無有效的剪枝策略，在這個過程會產(chǎn)生大量候選項(xiàng)集，導(dǎo)致程序計(jì)算的成本大幅增加.與CHUI_DS(no_sup)相比，CHUI_DS在CHUI-Miner，IncCHUI的基礎(chǔ)上對閉包挖掘過程額外增加了剪枝策略，同時利用提出的高效列表重組方法，使該剪枝策略能適用于任意滑動窗口，以此保證每個滑動窗口處理速度都得到提升.盡管公共批次列表的重組會產(chǎn)生一定時間消耗，但該過程并不需要重新掃描數(shù)據(jù)集，相較于剪枝掉的時空代價對算法效果影響有限.尤其是在閾值和數(shù)據(jù)集大小一定的情況下，加大窗口內(nèi)批次數(shù)意味著事務(wù)數(shù)的增加，密集數(shù)據(jù)集下的候選項(xiàng)集將成數(shù)倍增大，對算法運(yùn)行時間影響較大.由于Chainstore數(shù)據(jù)集的稀疏性，列表可復(fù)用率低，新增的中間候選項(xiàng)集數(shù)相對較少，由此其候選項(xiàng)集數(shù)量受窗口增大的影響較輕.盡管前期算法運(yùn)行時間略微增加，但隨著窗口的擴(kuò)大，算法對整個數(shù)據(jù)集窗口滑動和垂直數(shù)據(jù)結(jié)構(gòu)更新的次數(shù)明顯減少，因此2種算法運(yùn)行時間后期均出現(xiàn)下降.

Fig.9 Accumulated runtime comparison when varying batch sizes圖9 批次內(nèi)含不同事務(wù)數(shù)下運(yùn)行時間對比

考慮算法固定窗口內(nèi)的批次數(shù)為2，比較批次中事務(wù)數(shù)不同時的總運(yùn)行時間，2個數(shù)據(jù)集的實(shí)驗(yàn)參數(shù)設(shè)置及結(jié)果分別如圖9(a)(b)所示.實(shí)驗(yàn)逐漸增加每個批次中的事務(wù)數(shù)，運(yùn)行時間的變化趨勢和數(shù)據(jù)集的稀疏類型關(guān)系較大，具體表現(xiàn)為Accidents數(shù)據(jù)集運(yùn)行時間逐漸變長，而Chainstore數(shù)據(jù)集運(yùn)行時間變短.原因在于Accidents這樣的密集型數(shù)據(jù)集，其往往會生成大量長度較長的高效用項(xiàng)集.和圖8實(shí)驗(yàn)部分給出的原因相似，對于Chainstore稀疏數(shù)據(jù)集而言，因略微增大批次事務(wù)數(shù)而新增的中間候選項(xiàng)集數(shù)較小，批次中事務(wù)數(shù)越多從一定程度上減少滑動窗口的創(chuàng)建次數(shù)和挖掘算法的執(zhí)行次數(shù)，因此算法運(yùn)行時間穩(wěn)步下降.實(shí)驗(yàn)同時證明，與CHUI_DS(no_sup)相比，CHUI_DS具有更大的可擴(kuò)展性，適用于大型窗口.

4.3 可擴(kuò)展性測試

本節(jié)選取表4中的Mushroom，Retail數(shù)據(jù)集評估算法的可擴(kuò)展性，以驗(yàn)證本文算法的運(yùn)行時間和內(nèi)存消耗沒有呈指數(shù)增長.實(shí)驗(yàn)是根據(jù)總運(yùn)行時間和內(nèi)存進(jìn)行的，采用4.1節(jié)實(shí)驗(yàn)中使用的最低minutil來執(zhí)行相關(guān)工作中的算法.需要注意的是，IncCHUI在本實(shí)驗(yàn)部分以增量方式運(yùn)行，即使用數(shù)據(jù)集中20%的事務(wù)作為原始數(shù)據(jù)集，然后分別對Mushroom，Retail數(shù)據(jù)集按5%，10%的插入率添加到原始數(shù)據(jù)集.

Fig.10 Scalability test of runtime圖10 運(yùn)行時間可擴(kuò)展性測試

圖10顯示了運(yùn)行時間評估的結(jié)果.IncCHUI的運(yùn)行時間是處理每個遞增部分的時間，其余算法的運(yùn)行時間是累積的執(zhí)行時間.本文的算法使用單窗口運(yùn)行，因?yàn)槠溆嗨惴ň耘幚砟Ｊ竭\(yùn)行在靜態(tài)數(shù)據(jù)集中.可以看到，當(dāng)使用的數(shù)據(jù)集事務(wù)變多時，5種算法都需要更多的執(zhí)行時間，其中在密集數(shù)據(jù)集Mushroom中CHUI_DS具有最佳的可伸縮性，在稀疏數(shù)據(jù)集Retail中CHUI_DS和IncCHUI性能均接近最優(yōu).CHUI_DS運(yùn)行速度最快的原因是，與CLS-Miner和EFIM-Closed相比，CHUI-Miner僅采用了簡單的TWU高估策略.盡管IncCHUI增加了相關(guān)修剪策略，但其以增量方式插入原始數(shù)據(jù)庫，每次新數(shù)據(jù)到來都需要對項(xiàng)逆TWU順序遍歷，并依此進(jìn)行先前全部效用列表事務(wù)元組的更新，且其需要判斷閉合項(xiàng)集是否存在于已發(fā)掘的CHT表中，特別是當(dāng)數(shù)據(jù)密集時時間開銷會增加較快.

Fig.11 Scalability test of memory圖11 內(nèi)存可擴(kuò)展性測試

在內(nèi)存使用方面，圖11中實(shí)驗(yàn)結(jié)果表明：CHUI_DS在Mushroom數(shù)據(jù)集上的內(nèi)存消耗比絕大部分算法都要低.在Retail數(shù)據(jù)集上，CHUI_DS隨著其事務(wù)數(shù)量的變化內(nèi)存總體呈增加趨勢，相較于Mushroom數(shù)據(jù)集，算法產(chǎn)生更多的中間項(xiàng)集，內(nèi)存占用普遍大于Mushroom數(shù)據(jù)集.但由于Retail數(shù)據(jù)集的高稀疏性，隨著事務(wù)的階段性增加，產(chǎn)生的中間項(xiàng)集數(shù)量和高TWU項(xiàng)在該閾值條件下并非一直大幅增多.在此基礎(chǔ)上，非閉合的項(xiàng)集冗余比例在部分階段略微增大，導(dǎo)致內(nèi)存消耗呈階段性增長.總體來說，CHUI_DS在各數(shù)據(jù)集整個挖掘過程的最大內(nèi)存結(jié)果合理，運(yùn)行時間和內(nèi)存消耗均沒有呈指數(shù)增長.通常，對于所有算法，內(nèi)存消耗的趨勢會根據(jù)所使用的數(shù)據(jù)集、算法采用的結(jié)構(gòu)以及在挖掘過程中生成的候選總數(shù)而變化很大.例如，Retail是一個稀疏的數(shù)據(jù)集.在此數(shù)據(jù)集上，CLS-Miner消耗更多的內(nèi)存，因?yàn)樗枰鎯ζ湫藜舨呗缘慕Y(jié)構(gòu)，例如項(xiàng)的覆蓋范圍和估計(jì)的效用共現(xiàn)結(jié)構(gòu).但是此數(shù)據(jù)集上CLS-Miner的運(yùn)行時間非常低.在密集數(shù)據(jù)集Mushroom上，由于其覆蓋修剪策略的有效性，CLS-Miner的內(nèi)存消耗較低，IncCHUI在此數(shù)據(jù)集上的總體內(nèi)存消耗幾乎最少，這是因?yàn)槠湓诖瞬糠值膶?shí)驗(yàn)以增量方式運(yùn)行，只需要掃描數(shù)據(jù)庫1次以構(gòu)建全局列表，采用候選項(xiàng)集構(gòu)建的增量修剪策略和高效用閉合項(xiàng)集更新機(jī)制來節(jié)約內(nèi)存占用，而在Retail數(shù)據(jù)集上又高于CHUI_DS.

綜合來看，本文提出的算法對于不同類型數(shù)據(jù)集均有較強(qiáng)適應(yīng)能力，總體性能良好.特別是在不同閾值、不同數(shù)據(jù)集大小等條件下的時間性能要優(yōu)于先前提出的所有閉合高效用項(xiàng)集挖掘算法，內(nèi)存占用相對其他算法處于較低水平.所提出的算法不僅對滑動窗口大小和批次事務(wù)數(shù)量具有良好的可伸縮性，而且?guī)缀踉诿糠N情況下都保持較低的時間消耗.這些結(jié)果驗(yàn)證了該算法在各種現(xiàn)實(shí)世界數(shù)據(jù)流環(huán)境中的挖掘效率.因此，所提出的算法可以作為基礎(chǔ)部分應(yīng)用于專家和智能系統(tǒng)，通過滑動窗口參數(shù)設(shè)置以及對現(xiàn)實(shí)世界數(shù)據(jù)庫特性的考慮，幫助用戶更輕松地分析數(shù)據(jù)流并從中獲取有意義的信息.

5 總 結(jié)

為了應(yīng)對數(shù)據(jù)流的動態(tài)特性帶來的挑戰(zhàn)，本文提出了一種稱為CHUI_DS的新算法，其可以有效地挖掘和維護(hù)數(shù)據(jù)流中閉合的高效用項(xiàng)集CHUI，同時CHUI_DS也是第1種基于滑動窗口模型的數(shù)據(jù)流閉合高效用項(xiàng)集挖掘算法.首先，本文提出了一種新型效用列表結(jié)構(gòu)，用于將數(shù)據(jù)流關(guān)鍵信息存儲在項(xiàng)集中.此列表結(jié)構(gòu)的一個重要方面是它能快速準(zhǔn)確構(gòu)建和更新數(shù)據(jù)流中的大量最新信息，適用于對數(shù)據(jù)流進(jìn)行閉合高效用項(xiàng)集的挖掘任務(wù).其次，本文基于該效用列表結(jié)構(gòu)，提出數(shù)據(jù)流上無候選者產(chǎn)生的閉合高效用項(xiàng)集挖掘算法.第三，為了提高效率，本文對閉合項(xiàng)集挖掘過程進(jìn)行改進(jìn)，使用一個更加緊湊的效用剪枝策略.為了評估提出的算法，本文對現(xiàn)實(shí)和合成數(shù)據(jù)集進(jìn)行了廣泛的實(shí)驗(yàn)，并將其與現(xiàn)有算法進(jìn)行了比較，該評估證實(shí)了本文算法的效率和可行性.