基于滑動窗口含負(fù)項的高效用模式挖掘

武 妍，荀亞玲，馬 煜

(1.太原科技大學(xué) 經(jīng)濟與管理學(xué)院，山西 太原 030024；2.太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0 引 言

傳統(tǒng)基于支持度框架的頻繁模式挖掘，因其僅考慮高頻模式導(dǎo)致一些真正有價值但支持度較低的模式被忽略。因此，考慮“效用”的高效用模式挖掘(high utility pattern mining，HUPM)被提出并取得了很大進展[1-3]，然而它們都假設(shè)數(shù)據(jù)是靜態(tài)的。而在互聯(lián)網(wǎng)時代，數(shù)據(jù)大都是以流的形式產(chǎn)生，流數(shù)據(jù)連續(xù)、快速且不受限制的特征使流中的每個項只能被檢查一次，傳統(tǒng)的增量挖掘方式[4-9]已不能滿足流數(shù)據(jù)對時效性的要求，且現(xiàn)實場景中一般認(rèn)為最新數(shù)據(jù)比舊數(shù)據(jù)對于決策更重要，而增量挖掘中并不區(qū)分新舊數(shù)據(jù)。目前，流數(shù)據(jù)處理模型主要包含3種：基于衰減窗口[10，11]、基于界標(biāo)窗口[12]、基于滑動窗口[13-15]。衰減模型的局限性在于很難確定一個合適的衰減函數(shù)或衰減率；界標(biāo)窗口方法的局限性是需要長時間捕獲數(shù)據(jù)信息，數(shù)據(jù)量龐大。滑動窗口模型只針對窗口內(nèi)最近批次的數(shù)據(jù)塊挖掘高效用項集，消除了過期數(shù)據(jù)的影響，有效提高了挖掘效率。

此外，傳統(tǒng)HUPM僅考慮了項效用值為正的情況，為在挖掘過程中不丟失某些有價值的結(jié)果集，Chu等[16]提出的HUINIV(high utility itemsets with negative item values)-Mine算法是第一個考慮帶有負(fù)效用的HUPM算法，由兩階段算法擴展而來。Lin等[17]提出FHN(faster high-utility itemset miner with negative unit profits)算法，利用效用列表來有效地挖掘高效用項集，同時利用事務(wù)加權(quán)效用和剩余效用來修剪搜索空間，但可能會生成不在數(shù)據(jù)庫中的模式集。Sun等[18]亦提出基于列表結(jié)構(gòu)的可挖掘含負(fù)項的效用項集挖掘算法。總之，基于效用列表結(jié)構(gòu)的單階段算法被認(rèn)為是更有效的，其主要局限性在于創(chuàng)建和維護列表的成本非常昂貴。

針對以上局限性，本文定義了一種新的效用列表結(jié)構(gòu)以維護挖掘最近批次高效用模式集所需的所有信息，避免了數(shù)據(jù)庫的重復(fù)掃描；并基于該列表結(jié)構(gòu)，提出一種基于滑動窗口含負(fù)項的高效用模式挖掘算法(high utility pattern with negative unit profit based on sliding window，HUPN_SW)，在不產(chǎn)生候選效用模式集的情況下，直接挖掘出高效用模式集。

1 問題陳述及相關(guān)定義

1.1 問題描述

給定一組有限的項I={i1，i2，…，im}，每個項目ip(1≤p≤m) 的單位利潤為p(ip)。項集X是k個不一致項 {i1，i2，…，ik} 組成的，其中ij∈I，1≤j≤k，k是X的長度，長度為k的項集稱為k項集。一個事務(wù)數(shù)據(jù)庫D={T1，T2，…，Tn} 中包含一組事務(wù)，其中每個事務(wù)Td(1≤d≤n) 都有唯一的標(biāo)識符Tid。用q(ip，Td) 表示在交易Td中項目ip的購買數(shù)量。一個示例數(shù)據(jù)庫如圖1所示，表1為各項目對應(yīng)的利潤，即外部效用。

圖1 示例數(shù)據(jù)庫

基于滑動窗口的技術(shù)，將一個給定的流數(shù)據(jù)庫分成幾個包含相等數(shù)量事務(wù)的批。假設(shè)D為流數(shù)據(jù)庫。在滑動窗口模型中，根據(jù)事務(wù)的生成時間，D可以被分割成多個批次。該事務(wù)流被劃分為等長的4個批次(圖1的示例數(shù)據(jù)庫)。每一批B={T1，T2，…，Tn} 是一組事務(wù)，n為每批的大小；W={B1，B2，…，Bm} 是一組稱為窗口的批次，m表示窗口的大小。每個批次和窗口的大小由用戶指定。示例中，有兩個滑動窗口，W1={B1，B2，B3} 和W2={B2，B3，B4}，每批的大小為2，一個窗口的大小為3。W1是初始滑動窗口，W2是滑動W1的結(jié)果，通過刪除最舊的批次并插入最新的批次，即隨著時間的推移，最老的一批B1被移出，B4被新添加到窗口中，W2成為當(dāng)前窗口。使用滑動窗口技術(shù)的目標(biāo)是不必掃描整個數(shù)據(jù)庫，只從當(dāng)前窗口中挖掘所有的高效用項集，從而提高挖掘效率。

1.2 基本定義

定義1 項目效用[1]：在事務(wù)Td中項目ip的效用表示為U(ip，Td)，定義為

U(ip，Td)=p(ip)×q(ip，Td)

(1)

式中：p(ip) 為項目ip的外部效用，q(ip，Td) 為項目ip在事務(wù)Td中的數(shù)量。例如，圖1中項目A在事務(wù)T1中的效用U(A，T1)=(-3)×1=-3。

定義2 項集在事務(wù)中的效用[1]：項集X在事務(wù)Td中的效用表示為U(X，Td)，定義為

(2)

例如，圖1中U(AC，T1)=-3×1+4×2=5。

定義3 項集的效用[1]：項集X的效用表示為U(X)，定義為

(3)

式中：Td為包含項集X的事務(wù)。例如，圖1中U(AC)=U(AC，T1)+U(AC，T2)+U(AC，T3)+U(AC，T6)+U(AC，T8)=5+10+(-5)+7+10=20。

定義4 事務(wù)效用[1]：事務(wù)Td的效用表示為TU(Td)，定義為

(4)

例如，圖1中TU(T1)=U(A，T1)+U(C，T1)+U(D，T1)=(-3)+8+4=9。

定義5 事務(wù)加權(quán)效用[1]：項集X的事務(wù)加權(quán)效用表示為TWU(X)，定義為

(5)

例如，圖1中TWU(A)=TU(T1)+TU(T2)+TU(T3)+TU(T6)+TU(T8)=9+20+21+18+18=86。

定義6 高效用項集[1]：給定項集X及用戶指定的最小效用閾值Minutl，若U(X)≥Minutl，則稱項集X為高效用項集，否則為低效用項集，低效用項集的超集不可能是高效用項集。

為了挖掘高效用項集，同時考慮正、負(fù)單位利潤，則對將相關(guān)的概念進行重新定義如下：

定義7 重定義事務(wù)效用[19]：事務(wù)Td的具有正外部效用的項目效用之和為重定義事務(wù)效用，表示為PTU(Td)，計算公式為

(6)

例如，圖1中PTU(T1)=8+4=12。

定義8 重定義事務(wù)加權(quán)效用[19]：項集X的重定義事務(wù)加權(quán)效用表示為PTWU(X)，定義為

(7)

例如，圖1中窗口W1中PTWU(C)=12+26+30+26+17+18=129。

TWU用于修剪搜索空間，但是只有當(dāng)項目的外部效用值為正值時，這些屬性才有效。所以基于重新定義的交易效用PTU，進而計算項集的PTWU。

定義9 窗口中項集的效用[20]：窗口W中項目X的效用表示為U(X，W)，通過將X在屬于W的所有事務(wù)中的效用相加來計算。計算公式為

(8)

式中：Td為窗口W中包含項集X的事務(wù)。例如，圖1中U(AC，W1)=U(AC，T1)+U(AC，T2)+U(AC，T3)+U(AC，T6)=5+10+(-5)+7=10。

2 算法描述及實例描述

HUPN_SW算法首先要構(gòu)造一種效用列表結(jié)構(gòu)：滑動窗口正負(fù)效用列表(positive and negative with sliding window utility-list，PNSWU-List)，PNSWU-List定義如下：

定義10 PNSWU-List：數(shù)據(jù)庫D中項集X的PNSWU-List是一組元組，每個包含X的事務(wù)T都有一個元組，每個元組包含以下4個字段：①Tid，事務(wù)標(biāo)識符；②putil，事務(wù)中的正效用；③nutil，事務(wù)中的負(fù)效用；④rputil，事務(wù)中只有正效用值的剩余效用。

對于任意項集X，都有U(X)=putil(X)+nutil(X)。X中效用值為正的項目只能增加X的效用，而效用值為負(fù)的項目只能降低X的效用，因此有：nutil(X)≤U(X)≤putil(X)；若U(X)+rputil(X)

HUPN_SW算法的框架由以下部分組成：掃描數(shù)據(jù)庫，計算每個項目的PTWU且依PTWU值升序排列；構(gòu)造1-項集PNSWU-List；列表兩兩組合，進而挖掘高效用項集；進行窗口滑動，挖掘下一個窗口的高效用項集。

基于滑動窗口含負(fù)項的高效用項集挖掘算法步驟如下：

步驟1 窗口W1被最近的批次填滿，從該窗口中找到高效用項集。首先對數(shù)據(jù)庫進行第一次掃描，由于W1={B1，B2，B3}，第一批B1={T1，T2}，按照事務(wù)標(biāo)識符的順序，T1在T2之前被處理。項目的PTWU值可以根據(jù)屬于B1，B2和B3中的交易計算，即項目的PTWU值僅根據(jù)屬于當(dāng)前窗口的事務(wù)來確定。根據(jù)定義計算事務(wù)效用TU，正事務(wù)加權(quán)效用PTWU。

假設(shè)事務(wù)數(shù)據(jù)庫最小效用閾值Minutl為45，從表2可以得到，由于PTWU(F)

表2 W1項目及其PTWU

事務(wù)數(shù)據(jù)庫中的項目的事務(wù)加權(quán)效用PTWU排序規(guī)則：負(fù)項事務(wù)加權(quán)效用總是在所有正項之后；正項事務(wù)加權(quán)效用升序排序；負(fù)項按其絕對值升序排序。即交易中的項目順序為B、D、E、C、A。

算法1：對事務(wù)加權(quán)效用PTWU排序

輸入：交易數(shù)據(jù)庫D，最小效用閾值Minutl，批次大小n，窗口大小m

輸出：依PTWU值排序的項目序列。

(1)根據(jù)數(shù)據(jù)的生成時間,用事務(wù)將D分割為多個批次Bk

(2)for each batchBk∈Ddo

(3) for each transactionTd∈Bkdo

(4) for each itemX?Td

(5) 計算PTWU(X)

(6) end for

(7) ifPTWU(X)≥Minutl

(8) 對PTWU升序排序,正項在前,負(fù)項在后

(9) 依PTWU值升序輸出項目序列

(10) end if

(11) end for

(12) 構(gòu)建項集列表,挖掘高效用項集,然后進行窗口滑動

(13)end for

步驟2 構(gòu)造1-項集列表：putil和nutil分別是當(dāng)前正負(fù)項目數(shù)目與利潤的乘積；rputil是當(dāng)前PTWU升序排序項目之后的項目利潤總和(正利潤)。根據(jù)PTWU的順序，首先訪問的是B的列表。例如B列表中有在批次B2里的事務(wù)T3，T4和批次B3中的事務(wù)T5，putil(T3)=B.num×B.profit=2×2=4，nutil(T3)=0，rputil(T3)=C.num×C.profit+D.num×D.profit+E.num×E.profit=1×4+2×2+4×3=20，由于B的利潤是正值，nutil是負(fù)項目數(shù)和利潤的乘積，所以nutil(T3) 為0，rputil是按PTWU升序排列的模式項目B后的其余項目(即D、E、C)的利潤總和，rputil(T3) 為20。同法可得出：putil(T4)=4，nutil(T4)=0，rputil(T4)=22；putil(T5)=6，nutil(T5)=0，rputil(T5)=10；sum(putil)=putil(T3)+putil(T4)+putil(T5)=14；sum(nutil)=nutil(T3)+nutil(T4)+nutil(T5)=0；sum(rputil)=rputil(T3)+rputil(T4)+rputil(T5)=52。項目D作為下一個訪問的列表。當(dāng)所有屬于B1，B2和B3的事務(wù)以相同的方式處理完成后，可得到如圖2所示的1-項集的PNSWU-List列表。

圖2 1-項集的PNSWU-List

檢查數(shù)據(jù)庫中的列表以及和其它的列表組合是否可以生成高效用模式集。B列表中，psum+nsum為14，小于Minutl，則{B}不是高效用項集，psum+rpsum為14+52=66，大于Minutl。然后對列表B進行進一步的組合處理。同理{D}、{E}、{A}也不是高效用項集。C列表中，psum + nsum為50，大于Minutl，則{C}為高效用項集。對列表D，E，C，A進行進一步組合處理。

步驟3 將列表和其它的列表進行組合。

B，D，E，C列表中psum+rpsum都大于Minutl，因此B，D，E，C的遞歸列表構(gòu)造是為了構(gòu)造較長模式的列表而進行的。

現(xiàn)構(gòu)造了如圖3所示的以{D}作為前綴項的2-項集，為了組合D和E的列表，先比較兩個列表的條目，找到C和E的公共事務(wù)。兩個列表的公共事務(wù)是T3，T4。因此，構(gòu)建了一個DE的PNSWU-List列表，并在該列表中創(chuàng)建了T3，T4兩個條目。D和E是長度為1的模式，所以它們的公共前綴模式是空。構(gòu)造2-項集列表中兩個1-項集列表組合：putil和nutil為兩相同項集之和；rputil設(shè)置為PTWU序列中靠后的項目rputil的值。比如，DE列表中putil(T3) 等于D列表中putil(T3) 與E列表中putil(T3) 的和，即12+4=16，DE列表中rputil(T3) 等于E列表中rputil(T3) 的值，即4，同理DE列表中putil(T4)=6+12=18，rputil(T4)=4。

圖3 以{D}為前綴項的2-項集的PNSWU-List列表

DE列表中psum+nsum為34，小于Minutl，則{DE}不是高效用項集；psum+rpsum為42，小于Minutl，則不能通過將列表DE與其它項目的列表組合來生成任何高效用模式集。

同理可得出，{DA}不是高效用項集，且不能通過將列表DA與其它項目的列表組合來生成任何高效用模式集。DC列表中psum+nsum為48，大于Minutl，因此，{DC}是高效用項集，對列表DC進行進一步的組合處理。

進一步構(gòu)造3-項集PNSWU-List列表。構(gòu)造3-項集列表中兩個2-項集列表組合：putil和nutil為兩相同項集之和與兩者交集項目的差值；rputil設(shè)置為PTWU值后邊的rputil的值。比如，DCE列表中putil(T3) 等于DC列表中putil(T3) 與DE列表中putil(T3) 的和與D列表中putil(T3) 值的差，即16+8-4=20，DCE列表中rputil(T3) 等于0，同理DCE列表中putil(T4)=18+10-6=22，rputil(T4)=0。得到如圖4所示的以{D}作為前綴項的3-項集。

圖4 以{D}為前綴項的3-項集的PNSWU-List列表

DCE列表psum+nsum為42，小于Minutl，則{DCE}不是高效用項集。psum+rpsum為42，小于Minutl，不能通過將列表DE與其它項目的列表組合來生成任何高效用模式集。同理可得出{DCA}也不是高效用項集，并且也不能通過與其它項目的列表組合來生成任何高效用模式集。至此，以{D}為前綴的模式挖掘結(jié)束，得到高效用項集{DC}。

算法2：列表的組合

輸入：一系列列表，最小效用閾值Minutl

輸出：高效用項集

(1)輸入一系列列表

(2)for each list

(3) if psum+nsum≥Minutl

(4) 輸出高效用項集

(5) else if psum+rpsum≥Minutl

(6) do 列表兩兩組合,列表x.Td=列表y.Td

/*構(gòu)造k-項集列表xy,k≥2*/

(7) if k=2

(8) xy.putil=x.putil+y.putil,

(9) xy.nutil=x.nutil+y.nutil,

(10) xy.rputil=y.util

(11) else

(12) xy.putil=x.putil+y.putil-x∩y.putil,

(13) xy.nutil=x.nutil+y.nutil-x∩y.nutil,

(14) xy.rputil=y.util

(15) end if

(16) while psum+rpsum

(17) end if

(18) end if

步驟4 得到窗口W1的高效用項集后，進行窗口滑動。

當(dāng)有新批次數(shù)據(jù)到達(dá)時，需要從列表中刪除最老批次的數(shù)據(jù)，如圖1所示，按批號將條目分組，可以簡單地從所有列表中刪除屬于最早一批的條目，即刪除最老的批次B1，新插入B4。然后重復(fù)對窗口中的數(shù)據(jù)按以上的步驟進行處理，得到高效用項集。如此往復(fù)，直到數(shù)據(jù)集中沒有更多的批次。

3 實驗結(jié)果及分析

3.1 實驗環(huán)境及數(shù)據(jù)集

為驗證提出算法HUPN_SW的性能，選擇具有代表性的GHUM[19]、CHUI-Miner[21]、和HUPMS[22]進行對比分析。

實驗平臺：實驗所使用的系統(tǒng)是64位的Windows 10，CPU為英特爾i7處理器，內(nèi)存8 GB。

實驗數(shù)據(jù)集：實驗中使用了2個標(biāo)準(zhǔn)的數(shù)據(jù)集Retail、Connect，分別來源于匿名比利時零售商店的客戶交易(source FIMI：http：//fimi.ua.ac.be/data/)和基于UCI connect-4數(shù)據(jù)集(source：FIMI)。數(shù)據(jù)密度分別為0.06%，33.33%。這2個數(shù)據(jù)集的數(shù)據(jù)特性見表3，其中包括：交易總數(shù)；同項目的數(shù)量；平均交易長度；最大交易長度。實驗中2個數(shù)據(jù)集都沒有提供對應(yīng)的數(shù)量和單位利潤。在這里，項目的外部效用是采用對數(shù)正態(tài)分布在0.01～10之間產(chǎn)生的，項目的內(nèi)部效用是隨機在1～5之間產(chǎn)生的。

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

在基于滑動窗口的實驗中，將數(shù)據(jù)集劃分為若干個窗口，包括固定批次數(shù)量。首先，在W1內(nèi)進行挖掘，然后，當(dāng)前窗口從W1滑動到W2。滑動過程中，淘汰了一批在W1中過時的批次，并插入一個新的批次，在W2內(nèi)進行挖掘。

3.2 實驗結(jié)果分析

3.2.1 效用閾值對算法性能的影響

本實驗分別給出了在不同最小效用閾值時下4種算法在數(shù)據(jù)集Retail和Connect上的運行性能，實驗結(jié)果如圖5、圖6所示。運行時間性能是在執(zhí)行所有窗口的挖掘過程的總運行時間。

圖5 不同支持度下算法運行時間(Retail數(shù)據(jù)集)

圖6 不同支持度下算法運行時間(Connect數(shù)據(jù)集)

從圖5和圖6可以看出，4種算法都隨著最小效用閾值的增大，運行時間也逐漸變小。因為最小效用閾值越大，算法產(chǎn)生的高效用項集就越少，運行時間就越小。在Retail數(shù)據(jù)集中，HUPMS算法和CHUI-Miner算法耗時明顯多于HUPN_SW算法，GHUM算法與HUPN_SW算法相差不大；在Connect數(shù)據(jù)集中，HUPMS算法運行時間明顯高于其它3種算法。原因是：HUPN_SW算法與GHUM算法采用相似的列表結(jié)構(gòu)，而CHUI-Miner算法執(zhí)行需要兩次掃描數(shù)據(jù)庫來構(gòu)建效用列表，HUPMS算法則需要執(zhí)行兩次掃描數(shù)據(jù)庫構(gòu)建樹結(jié)構(gòu)。

3.2.2 可擴展性測試

該組實驗通過增加數(shù)據(jù)集規(guī)模驗證了4種算法的可擴展性能。選取數(shù)據(jù)集總量的20%、40%、60%、80%、100%，在相同的最小效用閾值情況下，通過數(shù)據(jù)交易總數(shù)的變化進行算法運行時間分析，實驗結(jié)果如圖7、圖8所示。

圖7 數(shù)據(jù)集Retail上算法的可擴展性

圖8 數(shù)據(jù)集Connect上算法的可擴展性

從圖7和圖8可以清晰地看出，隨著數(shù)據(jù)集占總數(shù)的比例越來越多，各算法運行時間也逐漸增加。4種算法在數(shù)據(jù)集Connect的可擴展性表現(xiàn)的更佳。原因是：數(shù)據(jù)集Connect的稀疏密度明顯大于數(shù)據(jù)集Retail的稀疏密度。挖掘稀疏密度大的數(shù)據(jù)集運行時間更小。

3.2.3 不同批次大小的運行時間

本小節(jié)顯示了在相同的最小效用閾值，不同批次大小下，算法HUPMS和算法HUPN_SW在數(shù)據(jù)集Retail和數(shù)據(jù)集Connect的運行時間測試結(jié)果。在數(shù)據(jù)集Retail上，批次大小的尺寸從10 K逐漸增大到14 K；數(shù)據(jù)集Connect上，批次大小從11 K逐漸增大到15 K，實驗結(jié)果如圖9、圖10所示。

圖9 不同窗口下算法運行時間(Retail數(shù)據(jù)集)

圖10 不同窗口下算法運行時間(Connect數(shù)據(jù)集)

從圖9和圖10可以看出，算法的運行時間隨著批次大小的增大而減小。原因是，批次大小越大，數(shù)據(jù)集產(chǎn)生的窗口數(shù)相對越少，算法對給定的數(shù)據(jù)集進行更少次數(shù)的挖掘。HUPN_SW算法在不生成候選模式的情況下執(zhí)行挖掘過程，消耗的運行時間更少。

3.2.4 挖掘結(jié)果的準(zhǔn)確性實驗

在不同最小效用閾值下，將算法HUPN_SW與算法GHUM在數(shù)據(jù)集Retail和數(shù)據(jù)集Connect上分別進行數(shù)據(jù)準(zhǔn)確性對比實驗，結(jié)果如圖11、圖12所示。

圖11 數(shù)據(jù)集Retail上算法的準(zhǔn)確性

圖12 數(shù)據(jù)集Connect上算法的準(zhǔn)確性

從圖11和圖12可以看出：HUPN_SW算法在兩個數(shù)據(jù)集的準(zhǔn)確度分別維持在85%和90%左右，準(zhǔn)確性在可接受范圍內(nèi)。原因是HUPN_SW算法基于滑動窗口實現(xiàn)流數(shù)據(jù)的局部挖掘而不是全局挖掘，因而挖掘結(jié)果不精確；同時，由于在數(shù)據(jù)集Connect的數(shù)據(jù)密度和平均長度都高于Retail，因此在Connect數(shù)據(jù)集上算法準(zhǔn)確度會更高。

4 結(jié)束語

本文提出了一種基于滑動窗口含負(fù)項的高效用項集挖掘算法HUPN_SW，用于挖掘流數(shù)據(jù)上最近的高效用項集，在不產(chǎn)生候選效用模式集的情況下，直接挖掘出高效用模式集，避免了驗證候選模式的大量資源消耗。實驗結(jié)果表明了HUPN_SW算法有較高的運行效率和較好的伸縮性。該方法可以發(fā)現(xiàn)最近的有價值的信息，有助于用戶了解客戶最近的購買偏好，做出更好的經(jīng)濟決策。