基于窗口內投影的閉合高效用模式挖掘

李慕航，韓 萌，陳志強，武紅鑫，張喜龍

(北方民族大學 計算機科學與工程學院，銀川 750021)

高效用模式挖掘(HUIM)已成為數據挖掘領域中一個重要的研究主題。給定一個事務數據庫，HUIM的目標是在事務數據庫中找出具有高效用(高利潤)的項集(HUIs)[1].HUIM通過綜合考慮內部效用(購買數量)以及外部效用(利潤)，解決了傳統頻繁模式挖掘(FIM)只考慮了模式出現的頻率而無法找出利潤較高的模式的限制。傳統HUIM的一個主要缺陷是會產生大量冗余的高效用項集。對用戶來說，分析這些算法的輸出會消耗大量時間。同時，算法產生這些冗余項集會消耗大量的運行時間以及內存空間[2]。為了解決該問題，提出了閉合高效用項集(CHUIs)[3]，CHUIs能夠比HUIs的數量小幾個數量級，并且能夠從CHUIs中恢復HUIs的全集，所以CHUIs是HUIs的精簡且無損的表示方法[2]。已有很多算法[2-5]被提出在事務數據庫中高效地挖掘CHUIs.

近年來，在數據流環境中挖掘高效用項集引發了越來越多的關注。數據流具有持續且無邊界的特性，其產生來自于多種場景，例如：網絡點擊流、傳感器網絡、電信網絡等。由于內存和時間限制，無法存儲和處理整個數據流，因此數據流中的模式挖掘是一種具有挑戰的任務[6]。一些算法[7-9]已被提出在數據流環境中挖掘高效用項集，但這些算法通常會產生大量的冗余項集。為了減小這些無用項集的數量且不丟失重要的信息，程浩東等[10]提出了第一種數據流環境下的閉合高效用模式挖掘算法CHUI_DS.但是由于該算法是一種基于列表的算法，列表的交叉操作會消耗大量的時間，并且新批次到來時算法需要對列表進行更新操作，也會消耗大量時間，導致算法效率不高。

因此，本文通過提出一種更有效的數據流高效用閉合模式挖掘算法EFIM_Closed_DS來解決上述問題。算法將每個滑動窗口都視為一個新的數據庫，在每個窗口中使用數據庫投影技術以及事務合并技術來減少數據庫掃描的代價，在窗口中調用深度優先的搜索算法挖掘閉合高效用項集。算法使用子樹效用以及本地效用剪枝低效用項集，采用有效的前向擴展、后向擴展策略在窗口中剪枝非閉合項集，并使用閉包跳躍策略有效地在數據流環境中挖掘閉合高效用項集。本文的貢獻如下：

1)提出一種新的基于窗口內投影的候選集生成策略，在每個滑動窗口內部利用數據庫投影技術以及事務合并技術減少數據庫掃描的代價。

2)提出一種基于窗口內投影技術的數據流閉合高效用模式挖掘算法EFIM_Closed_DS，能夠快速且高效地挖掘CHUI的全集。

3)在6種數據集上的大量評估實驗顯示，提出的算法比之前的CHUI_DS算法在運行時間和內存消耗方面都更加有效。

1 相關工作

1.1 靜態數據庫高效用閉合模式挖掘算法

HUIM的缺陷在于會產生大量的模式，導致用戶需要消耗大量時間分析這些模式。此外，大量的結果集導致HUIM算法會消耗大量時間且占用較多內存空間[3]。而CHUI是HUIM精簡且無損的表示方式，CHUIs要比HUIs要小數個數量級且能夠在不掃描數據庫的情況下恢復HUI的全集[5]，所以CHUI算法能夠給用戶提供精簡且無損的信息。

WU et al[2]提出不產生候選項集的閉合高效用項集挖掘算法CHUI-Miner，算法設計了一個EU-List效用列表結構采用分而治之的方法挖掘高效用閉合項集，算法在密集數據集上有著更好的性能。FOURNIER-VIGER et al[4]提出了EFIM_Closed算法，使用高效用數據庫投影和高效用事務合并方法減少數據庫掃描的代價。采用3個高效的剪枝策略閉合跳躍(closure-jumping)、前向閉合檢查(forward closure checking)還有后向閉合檢查(backward closure checking)，來剪枝非閉合高效用項集。DAM et al[5]提出了CLS-Miner算法，該算法使用效用列表結構來直接計算項集的效用而無需產生候選項集。該算法提出了3種策略：Chain-EUCP策略、LBP策略以及coverage概念，分別用來估計成對的項的效用、剪枝低效用的項集及其擴展和快速發現項集的閉包。該算法還引入了快速預檢查策略來快速執行閉包計算及包含性檢查，從而高效地發現高效用閉合項集。

1.2 動態數據庫高效用模式挖掘

動態數據庫例如數據流環境中的數據具有持續且無限的特性。由于受到時間以及內存空間的限制，數據流環境下的HUIM算法無法像靜態環境中那樣將全部數據保存在內存空間中進行存儲及處理[6]。數據流CHUI算法能夠適用于現實生活中例如網絡點擊流、傳感器網絡以及典型網絡等具有實時且數據量較大的環境。

AHMED et al[7]提出了一種兩階段的HUPMS算法在數據流環境中挖掘高效用項集。該算法設計了一種HUS-tree結構保存數據流中的信息。算法利用HUS-tree結構以模式增長的方式挖掘數據流中的高效用項集。DAWAR et al[6]提出的Vert_top-k_DS算法是一種不產生候選項集的一階段數據流top-k高效用項集挖掘算法。算法設計一種iList列表結構能夠對批次進行有效的插入與刪除，還提出了一個有效的效用閾值提升策略，通過計算兩個窗口之間的共有批次中的top-k項集效用來快速提升閾值。JAYSAWAL et al[8]提出了一種一階段的算法SOHUPDS在數據流中挖掘高效用項集，設計了一種IUDataListSW結構存儲當前滑動窗口中項的效用、上邊界以及項在事務中的位置。通過該結構，該算法能夠利用之前窗口挖掘的高效用項集更新當前窗口中的高效用項集。

1.3 動態數據庫高效用閉合模式挖掘

動態環境下的閉合模式挖掘算法克服了增量以及數據流環境中HUIs結果冗余且較多的缺點，能夠適用于現實生活中數據動態變化的環境。

DAM et al[9]提出了IncCHUI算法，是首個在動態數據庫中增量挖掘閉合高效用項集的算法。算法引入了一個增量效用列表結構來存儲原始數據庫和添加的事務中單一項的關鍵信息。算法使用有效的剪枝策略來剪枝沒有更新的項集，從而快速地構建增量效用列表。該算法只需要掃描一次數據庫來構建以及更新增量效用列表，使用一個基于哈希表的結構CHT來保存閉合高效用項集。程浩東等[10]提出的CHUI_DS算法是第一種在數據流環境中挖掘高效用閉合模式的算法。該算法基于滑動窗口模型處理數據流，提出一種新的效用列表結構CH-List，該結構能夠記錄當前窗口中項集的效用信息，并使用一種被稱為BRU_table的雙重散列表，初始時保存當前窗口中所有批次的事務效用信息，BRU_table以批次Bid為鍵，值為一個以事務效用Tid為鍵、剩余效用為值的散列表，該散列表中的項會隨著窗口的滑動而更新。BRU_table結構能夠方便地更新窗口滑動后CH-List中項的剩余效用。算法提出一種有效的事務重組算法，能夠快速計算窗口中效用列表的剩余效用。

2 定義

本節介紹在數據流中挖掘高效用閉合模式的相關定義。設I={I1,I2,…,In}是項的有限集合，其中每個項Ii都與一個正數相關聯，被稱為外部效用(利潤)。一個項集X?I是一個項的有限集合。事務Tc?I，其中c是事務Tc的唯一標識符，稱為Tc的Tid.在事務中每個項Ii∈Tc都與一個正數q(Ii,Tc)相關聯，稱為Tc中項Ii的內部效用(數量)。數據流DS={T1,T2,…,Tm}是由事務組成的有限序列，s(1≤s≤m)代表第s個到達的事務。

在基于滑動窗口的數據流挖掘算法中，每個窗口Wk={Bi,Bi+1,…,Bv}由固定數量的批次組成，Wk的窗口大小(win_size)為v.每個批次Bl={T1,T2,…,Tz}由固定數量的事務組成，Bl的批次大小(batch_size)為z.

圖1是一個數據流的示例，表1為圖1的數據流示例中所有項的外部效用(利潤)。圖1中每一行代表一個事務，并在右側列出了每個事務的事務效用Tu.示例中包含3個批次{B1,B2,B3}，每個批次包含3個事務，數據流中有兩個窗口{W1,W2}，每個窗口包含兩個批次。

圖1 數據流示例Fig.1 Example of data stream

表1 外部效用表(利潤)Table 1 External utility(Profit)

定義1 項的效用。事務Tc中項Ii的效用被表示為u(Ii,Tc)，被定義為p(Ii)×q(Ii,Tc).在一個批次Bj中，u(Ii,Bj)=∑Tc∈Bju(Ii,Tc).在窗口Wk中，u(Ii,Wk)=∑Bj∈Wku(Ii,Bj).例如，u(a,T1)=1×5=5；u(a,B1)=u(a,T1)+u(a,T2)+u(a,T3)=5+15+0=20；u(a,W1)=u(a,B1)+u(a,B2)=20+10=30.

定義2 項集的效用。事務Tc中k項集X={I1,I2,…,Ik}的效用被表示為u(X,Tc)，被定義為∑Ii∈Xu(Ii,Tc).在一個批次中，u(X,Bj)=∑X∈Tcu(X,Tc).在窗口Wk中，u(X,Wk)=∑Bj∈Wku(X,Bj).例如，u(ac,T1)=u(a,T1)+u(c,T1)=5+4=9；u(ac,B1)=u(ac,T1)+u(ac,T2)=9+19=28；u(ac,W1)=u(ac,B1)+u(ac,B2)=28+22=50.

定義3 事務效用。事務Tc的效用被表示為Tu(Tc)，被定義為∑Ii∈Tcu(Ii,Tc).例如，Tu(T1)=u(a,T1)+u(c,T1)+u(d,T1)=11.

定義4 閉合項集。如果窗口Wk中不存在一個項集Y?X，且sup(X)=sup(Y)，則項集X在窗口Wk中是一個閉合項集。

定義5 高效用項集。在窗口中，如果一個項集X的效用大于用于定義的最小效用閾值minutil，則X是一個高效用項集，即：u(X,Wk)≥minutil.

定義6 閉合高效用項集。如果項集X在窗口Wk中是一個閉合項集，且滿足u(X,Wk)≥minutil,則該項集是一個閉合高效用項集(CHUI).

定義7 事務加權效用(UTW)。項集X的UTW是為當前窗口Wk中所有包含項集X的事務的效用之和，被表示為UTW，Wk(X)，定義為∑X∈Tc∧Tc∈WkUT(Tc).例如，UTW，W1(cd)=UT(T1)+UT(T2)+UT(T5)=67.

屬性1 事務加權向下閉包屬性。對于窗口Wk中的一個項集X，如果UTW，Wk(X)≤minutil，則項集X以及它的所有超集都是低效用項集。

定義8 子樹效用(sub-tree utility，us)[4]。設有一個項集α以及一個項z∈E(α).z關于項集α的子樹效用us(α,z)=∑T∈g(α∪{z})[u(α,T)+u(z,T)+∑i∈T∧i∈E(α∪{z} )u(i,T)].

屬性2 利用子樹效用剪枝[4]。設有一個項集以及一個項z∈E(α).若us(α,z)

定義9 本地效用(local utility，ul)[4]。設有一個項集α以及一個項z∈E(α).z關于項集α的本地效用UL(α,z)=∑T∈g(α∪{z})[u(α,T)+re(α,T)].

屬性3 利用本地效用剪枝[4]。設有一個項集以及一個項z∈E(α).若ul(α,z)

定義10 投影窗口。一個事務關于一個項集α的投影被表示為α-T，被定義為α-T={Ii|Ii∈T∧Ii∈E(α)}[4].窗口Wk關于項集α的投影被表示為α-Wk，被定義為α-Wk={α-T|T∈Wk∧α-T≠?}.

定義11 前向擴展與后向擴展(Forward/backward extensions)[4].設項集β=α∪{i}.如果存在一個項z>i且滿足z∈E(β)，sup(β∪{z})=sup(β)，則稱項集β有前向擴展。如果存在一個項z

屬性4 識別非閉合項集[4]。如果一個項集β=α∪{i}不存在前向擴展以及后向擴展，且最小效用閾值大于minutil，則β是一個閉合高效用項集(CHUI).

屬性5 閉包跳躍(closure jumping)[4]。設有項集β以及一個投影窗口β-W.如果對于所有的z∈E(β)，滿足sup(β)=sup(β∪{z})，則項集β∪E(β)是β的子樹中唯一的閉合項集。

3 EFIM_Closed_DS算法

本節提出一種新的基于窗口內投影的數據流閉合高效用模式挖掘算法EFIM_Closed_DS.算法在滑動窗口內采用窗口內投影技術以及事務合并技術來減小數據庫掃描的代價。

3.1 窗口內投影技術

根據定義10，隨著算法的執行，在窗口中探索的項集越大，在窗口中對該項集進行投影產生的投影數據庫就越小，所以窗口內的投影技術能夠大量減少窗口中對數據進行掃描的消耗。

例如，在圖1的數據流示例中，以窗口W1為例。設有項集α，對項集α在窗口W1中進行投影，得到投影窗口α-W1，如圖2所示，當在搜索與α相關的項集時，僅需要搜索α-W1，并不斷進行投影，所以窗口內投影技術可以極大地減小搜索項集時掃描數據庫的代價。

P-TidProjected transactionP-UTα-T1(c,1)(d,1)6α-T2(b,2)(c,1)(d,7)(d,1)(f,3)28α-T6(c,3)(e,1)(f,3)18

3.2 EFIM_Closed_DS

本節描述整個算法的運行過程。首先，如果批次中的事務數沒有達到用戶設定的批次大小，則讀入一個事務，并將其添加到當前批次中，否則將當前批次添加到窗口中。如果當前批次數沒有滿足用戶設定的窗口大小，則將當前批次添加到當前窗口中，否則開始挖掘當前窗口中的CHUI.具體如算法1所示。

算法1:EFIM_Closed_DS算法

輸入：數據流 DS，最小效用閾值 minutil，窗口大小win_size，批次大小batch_size.

輸出：數據流中所有滿足閾值的閉合高效用項集。

while transaction in stream do

transaction_number++;

if(transaction_number≤batch_size)

batch.add(tranction);

if(tranction_number=batch_size)

batch_number++;

window.add(batch);

if(batch_number==win_size)

prepare_mining(window,minutil);

window.remove(0);/刪除舊批次

end if

end if

end while

在挖掘過程中，將項集α設置為空集。算法掃描整個窗口來計算窗口中所有項的UTW.然后通過比較每個項的本地效用(local utility)(當前與UTW相同)與minutil，找出Secondary(α).然后將這些項按照UTW升序排序。然后掃描窗口一次，刪除所有不屬于Secondary(α)的項。如果事務為空，則從窗口中刪除。然后掃描窗口一次將窗口中的事務按照?T順序排序，以便進行事務合并。隨后，掃描窗口一次來計算Secondary(α)中項的子樹效用(sub-tree utility)。最后算法調用mining_process來遞歸地挖掘CHUI.如算法2所示。

算法2:prepare_mining

輸入：窗口Window，最小效用閾值minutil.

輸出：當前窗口中的閉合高效用項集。

α=?;

Calculate lu(α,i)for all itemi∈Iby scanning Window,using a utility-bin array;

Secondary(α)={i|i∈I∧ul(α,i)≥minutil};

let ? be the total order ofUTWascending values on Secondary(α);

Scan Window to remove each item ? Secondary(α)from the transaction,and delete empty transactions;

Sort transactions in Window according to ?T;

Calculate the sub-tree utility su(α,i)of each itemi∈ Secondary(α)by scanning Window,using a utility-bin array;

Primary(α)={i|i∈Secondary(α)∧ul(α,i)≥minutil};

Search(α,Window,Primary(α),Secondary(α),minutil);

Mining_process算法將項集α，α的投影數據庫，α的primary(α)以及secondary(α)項與最小效用閾值minutil作為輸入參數。算法首先遍歷所有能夠用于擴展α的項i∈Primary(α)，來構建α的擴展β=α∪{i}.對于每個項集β，通過掃描α的投影數據庫來計算β的效用，同時構建β的投影數據庫。如果β有后向擴展，則不必探索β的擴展。否則，掃描β的投影數據庫來計算β的支持度、子樹和本地效用。如果β的支持度等于β的擴展的支持度，并且該擴展是高效用項集，則使用閉包跳躍策略直接輸出該閉合項集。否則遞歸調用Mining_process算法來深度優先搜索β的擴展。根據定理3，如果不存在β的擴展具有與β相同的支持度，并且β的效用不小于minutil，則β是一個CHUI，并輸出。如算法3所示。

算法3:Search

輸入：α一個項集，α-Windowα在窗口中的投影數據庫，Primary(α)α的primary項，Secondary(α)α的Secondary項，minutil最小效用閾值。

輸出：α的擴展的高效用項集

foreach itemi∈ Primary(α)do

β=α∪{i};

Scanα-Window to calculateu(β)and creatβ-Window;∥with transaction merging

ifβhas no backward extension then calculate sup(β,z),us(β,z),UL(β,z)for all itemz∈Secondary(α)by scanningβ-Window once using three utility-bin arrays;

if sup(β)=sup(β∪{z})?z?i∧z∈E(α)then

outputβ∪U(z?i∧z∈E(α)){z}/閉包跳躍

else

Primary(β)={z│z∈Secondary(α)∧us(β,z)≥minutil};

Secondary(β)={z│z∈Secondary(α)∧ul(β,z)≥minutil};

Search(β,β-Window,Primary(β),Secondary(β),minutil);

ifβhas no forward extension andu(β)≥minutil then outputβ;

end if

end if

end for

3.3 算法實例

本小節對所提出的算法給出一個詳細的實例來描述算法的具體運行過程。將圖1中的數據流作為一個實例，設置最小效用閾值minutil為50.如圖1中所示，批次大小batch_size為3(3個事務)，窗口大小win_size為2(2個批次)。

以數據流示例中第一個窗口為例，窗口中事務數量為win_size×batch_size=2×3=6.算法首先掃描整個窗口計算窗口中的本地效用以及子樹效用，按照定義8以及定義9，本地效用以及子樹效用如表2-3所示。設置算法按照字典順序對項進行排序，當前α=?，Secondary(α)={a,b,c,d,e,f},Primary(α)={a,b,c}.算法掃描數據庫刪除所有不滿足子樹效用的項，然后對相同的事務進行合并。隨后算法開始搜索，根據算法3，對于Primary(α)中的每一項，掃描窗口計算項集β=α∪{i}的效用并執行對窗口的投影。由于當前α=?所以分別計算Primary(α)中a,b,c三項的效用，并執行對窗口的投影，以a為例。根據定義10，對窗口W1投影的結果窗口α—W1如圖2所示。通過掃描窗口，項a的效用為30，且根據定義11，項a不存在后向擴展(按照字母順序項a是第一項)，所以繼續執行進一步的深度搜索。此時，在投影窗口α—W1中，項a的Secondary(α)={c},Primary(α)={c}.所以β=α∪c=αc，通過掃描投影窗口α—W1，計算得項集αc的效用為28，創建αc的投影窗口αc—W1，項集αc沒有前向擴展以及后向擴展，即：αc為閉合項集，但由于效用小于minutil，所以項集αc不是閉合高效用模式。算法結束項a的深度搜索，轉而以同樣的方式分別執行項b,c的深度搜索過程，最終完成對窗口W1中所有閉合高效用項集的搜索，然后加入新的批次，窗口滑動，執行新窗口內的搜索過程。

表2 本地效用表Table 2 Local utility table

表3 子樹效用表Table 3 Subtree utility table

4 實驗

本節進行了大量的對比實驗以評估提出的算法的效率。實驗將提出的算法與之前較為先進的閉合高效用模式挖掘算法EFIM_Closed、CHUI_Miner、CLS_Miner以及CHUI_DS算法進行對比。主要從以下幾方面評估算法的性能：1)變化最小效用閾值；2)變化窗口大小；3)變化批次大小。所有對比試驗均在SPMF中使用JAVA語言實現。實驗中使用了6種HUIM中通常使用的基準數據集來進行對比實驗，包括3種密集數據集以及3種稀疏數據集，數據集的特性在表4中給出。

表4 實驗數據集Table 4 Datasets

4.1 最小效用閾值對實驗的影響

本小節通過逐漸減小最小效用閾值來比較提出的算法EFIM_Closed_DS與之前的EFIM_Closed、CHUI_Miner、CLS_Miner以及CHUI_DS算法在運行時間方面的性能。實驗分別在數據流環境以及靜態環境下進行對比試驗。其中，在靜態數據集上與其他4種閉合高效用模式挖掘算法EFIM_Closed、CHUI_Miner、CLS_Miner、CHUI_DS算法對比時，提出的算法與CHUI_DS算法采用單窗口處理方式運行(即：將數據集中所有事務輸入一個窗口)，以評估靜態環境下二者與其他靜態閉合模式挖掘算法的性能。在數據流環境下，控制窗口大小以及批次大小，比較算法的運行時間。

在靜態環境下，隨著最小效用閾值的增大，算法產生的結果集逐漸減少，5種對比算法的運行時間逐漸減小。在圖3中，除Chainstore以及Retail數據集上，提出的算法與EFIM_Closed算法均具有最好的性能，消耗了最少的運行時間。提出的算法與EFIM_Closed使用了有效的子樹效用與本地效用能夠剪枝大量的搜索空間，提出的高效用事務合并技術通過合并相同的事務大量減少了數據庫掃描的消耗。此外使用的前向、后向擴展技術相較CHUI_Miner、CLS_Miner、CHUI_DS使用的閉包計算策略以及包含性檢查操作能夠更快地計算閉合項集。在Chainstore和Retail數據集兩個稀疏數據集中，提出的算法與對比算法在最小效用閾值較大時，運行時間較為接近，但算法在最小效用閾值較小時，CLS_Miner算法消耗了最少的運行時間，該算法所使用的基于EUCS結構的Chain_EUCP策略、LBP策略以及coverage概念有效地提升了CHUI_Miner算法的效率，且在稀疏數據集上也相當有效[5]。由于提出的算法與EFIM_Closed算法在遞歸過程中執行了過多的數據庫投影，因此消耗了大量的時間。實驗結果顯示，提出的算法基于EFIM_Closed算法增加基于數據流環境做出的改進并未影響算法的性能，在靜態數據環境下同樣具有較好的性能。同時，由于密集數據集更容易在投影過程中產生相同的投影事務，而提出的算法所使用的事務合并以及閉包跳躍技術能夠更為有效地減少投影事務，從而在密集數據集上具有比稀疏數據集更好的性能。

圖3 靜態數據庫中比較不同最小效用閾值情況下算法運行時間Fig.3 Runtime comparison among various utility thresholds

在數據流環境下，實驗對提出的算法以及CHUI_DS算法在Retail以及Foodmart兩個數據集上進行對比。在Retail數據集上設置窗口大小為10，批次大小為1 000，Foodmart數據集上窗口大小設置為10，批次大小為100.最小效用閾值變化范圍均從10 000到500.如圖4所示，運行時間方面，隨著最小效用閾值的減小，算法產生的閉合高效用模式數量不斷增加，所耗費的時間也隨之增加。通過對比實驗可以看出，所提出的算法在Retail數據集上的運行時間比CHUI_DS最高要快7倍左右，在Foodmart數據集上的運行時間最高要快10倍左右。實驗結果顯示，提出的EFIM_Closed_DS算法與CHUI_DS算法雖均基于滑動窗口技術，但提出的算法所使用的窗口內投影技術比基于效用列表的CHUI_DS算法的公共批次重組技術和改進的閉包挖掘技術更為高效。

圖4 數據流環境下比較不同最小效用閾值情況下算法運行時間Fig.4 Runtime comparison among various utility thresholds

4.2 不同窗口大小與批次大小下的對比

由于CHUI_DS算法和EFIM_Closed_DS算法均基于滑動窗口模型，均有兩個參數：1)窗口的大小；2)批次大小。本節分別控制算法所使用的窗口大小與批次大小進行對比實驗。采用密集數據集Accidents和稀疏數據集Chainstore進行實驗。設定Accidents數據集的最小效用閾值為1.5×107，設定Chainstore數據集的最小效用閾值為9.5×107.

首先，固定實驗中每個事務的批次大小，調節窗口大小對比兩個算法的運行時間。固定數據集Accidents批次大小為3×104，固定數據集Chainstore批次大小為1×105.在Accidents數據集上控制窗口大小從1到4，Chainstore數據集上窗口大小從4到10進行對比，實驗結果如圖5所示。在固定批次大小的情況下，提出的EFIM_Closed_DS算法在兩個數據集上的運行時間均快于CHUI_DS算法。在兩個數據集上兩個算法隨著窗口大小的增大，差距越來越大。在Accidents數據集上，提出的算法的運行時間最高比對比算法要快300倍左右。在Chainstore數據集上，最高要快130倍左右。

圖5 不同窗口大小下運行時間對比Fig.5 Runtime comparison among various window sizes

其次，算法固定窗口大小為2，比較批次大小不同時的總運行時間。控制算法在Accidents數據集上批次大小從4×104到8×104，在Chainstore數據集上控制批次大小從10×104到20×104.實驗結果如圖6所示，隨著批次大小的增加，每個窗口中算法需要處理的數據量不斷增大，運行時間不斷增加。提出的EFIM_Closed_DS算法在兩個數據集上運行時間均優于CHUI_DS算法，且隨著批次大小的增加，二者的差距也逐漸增大。

圖6 不同批次大小下運行時間對比Fig.6 Runtime comparison among various batch sizes

通過控制窗口大小與批次大小，實驗結果可以看出，提出的算法隨著處理的數據量的增大，與對比算法之間的差距不斷增大，提出的算法比對比算法在數據流環境中運行更為有效，是更高效的一種基于滑動窗口的算法。算法在密集數據集(Accidents)上更加有效，與對比算法之間的差距更大，且隨著處理的數據量增大，差距成線性增加。在兩種數據集上，隨著數據量的增大，提出的算法運行時間曲線相對較為平緩，運行時間變化不大。

4.3 不同最小效用閾值下算法使用內存大小對比

在數據流環境下，控制窗口大小以及批次大小，對比提出的算法與CHUI_DS算法在不同最小效用閾值情況下的內存占用大小。實驗中，控制窗口大小為10，控制批次大小為100，變化最小效用閾值從10 000到500.如圖7所示，內存占用方面，隨著最小效用閾值的減小，算法需要占用更大的內存空間來處理候選項集。在大部分情況下，提出的算法EFIM_Closed_DS的內存消耗更小，最好的情況下內存占用比CHUI_DS小11倍。CHUI_DS算法改進自CHUI_Miner算法，是一種一階段基于效用列表的算法，該算法的缺點在于需要構建搜索空間中所有項集的效用列表，會占用大量內存空間，且構建效用列表的交叉操作也會消耗大量時間[5]。這導致了實驗結果中CHUI_DS算法內存占用較高，且隨著最小效用閾值的減小，會產生更多的候選項集，使得CHUI_DS算法所占用的內存空間逐漸增多。

圖7 不同最小效用閾值情況下內存占用對比Fig.7 Memory used comparison among various utility thresholds

4.4 實驗結論

CHUI_DS算法是一種基于效用列表結構的算法，算法需要執行大量的列表交叉操作，會耗費大量時間，并且算法需要將項的列表結構保存在內存當中，會占用大量內存空間。同時，CHUI_DS算法在新批次到來時，需要進行公共批次事務重組來對之前窗口構建的效用列表進行更新，同樣消耗了大量時間。CHUI_DS算法基于批次更新，無法通過UTW剪枝技術刪除窗口中無希望的項，導致搜索過程中浪費更多的時間。EFIM_Closed_DS算法基于窗口內投影技術能夠減少數據庫掃描的代價，在每個窗口中使用UTW剪枝技術刪除無希望的項也能夠大量減小搜索范圍，通過子樹效用以及本地效用的剪枝技術能剪枝大量的無希望項集。在靜態數據環境下的對比實驗結果顯示，提出的算法性能并未因改進到數據流環境而受到影響，與EFIM_Closed性能相比差異不大，比多數靜態環境下的閉合模式挖掘算法性能優異，尤其在密集數據集上比之前較先進的CLS_Miner算法的最佳性能提升了1倍到50倍。在數據流環境下，提出的算法運行時間比對比算法最好能夠提升300倍且在實驗設置條件下差異呈線性增加，提出的算法內存占用比對比算法最好要小11倍。因此，提出的算法在運行時間和內存占用方面比CHUI_DS都更加有效。

5 結束語

本文提出了一種新的基于窗口內投影的數據流閉合高效用模式挖掘算法EFIM_Closed_DS.算法使用數據庫投影以及事務合并兩種技術有效地減少了數據庫掃描的代價。通過前向閉包檢查、后向閉包檢查以及閉包跳躍3種策略探索閉合的高效用項集。通過在窗口中利用本地效用以及子樹效用剪枝技術，有效地減少了搜索空間。在6種不同數據集上的大量實驗結果證明算法比之前的CHUI_DS算法在時間以及內存方面效果有顯著的提高。