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

武 妍，荀亞玲，馬 煜

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

0 引 言

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

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

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

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

1.1 問題描述

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

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

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

1.2 基本定義

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

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

(1)

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

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

(2)

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

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

(3)

式中：Td為包含項(xiàng)集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]：項(xiàng)集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 高效用項(xiàng)集[1]：給定項(xiàng)集X及用戶指定的最小效用閾值Minutl，若U(X)≥Minutl，則稱項(xiàng)集X為高效用項(xiàng)集，否則為低效用項(xiàng)集，低效用項(xiàng)集的超集不可能是高效用項(xiàng)集。

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

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

(6)

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

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

(7)

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

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

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

(8)

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

2 算法描述及實(shí)例描述

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

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

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

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

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

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

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

表2 W1項(xiàng)目及其PTWU

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

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

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

輸出：依PTWU值排序的項(xiàng)目序列。

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

(2)for each batchBk∈Ddo

(3) for each transactionTd∈Bkdo

(4) for each itemX?Td

(5) 計(jì)算PTWU(X)

(6) end for

(7) ifPTWU(X)≥Minutl

(8) 對(duì)PTWU升序排序,正項(xiàng)在前,負(fù)項(xiàng)在后

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

(10) end if

(11) end for

(12) 構(gòu)建項(xiàng)集列表,挖掘高效用項(xiàng)集,然后進(jìn)行窗口滑動(dòng)

(13)end for

步驟2 構(gòu)造1-項(xiàng)集列表：putil和nutil分別是當(dāng)前正負(fù)項(xiàng)目數(shù)目與利潤的乘積；rputil是當(dāng)前PTWU升序排序項(xiàng)目之后的項(xiàng)目利潤總和(正利潤)。根據(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ù)項(xiàng)目數(shù)和利潤的乘積，所以nutil(T3) 為0，rputil是按PTWU升序排列的模式項(xiàng)目B后的其余項(xiàng)目(即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。項(xiàng)目D作為下一個(gè)訪問的列表。當(dāng)所有屬于B1，B2和B3的事務(wù)以相同的方式處理完成后，可得到如圖2所示的1-項(xiàng)集的PNSWU-List列表。

圖2 1-項(xiàng)集的PNSWU-List

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

步驟3 將列表和其它的列表進(jìn)行組合。

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

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

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

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

進(jìn)一步構(gòu)造3-項(xiàng)集PNSWU-List列表。構(gòu)造3-項(xiàng)集列表中兩個(gè)2-項(xiàng)集列表組合：putil和nutil為兩相同項(xiàng)集之和與兩者交集項(xiàng)目的差值；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}作為前綴項(xiàng)的3-項(xiàng)集。

圖4 以{D}為前綴項(xiàng)的3-項(xiàng)集的PNSWU-List列表

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

算法2：列表的組合

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

輸出：高效用項(xiàng)集

(1)輸入一系列列表

(2)for each list

(3) if psum+nsum≥Minutl

(4) 輸出高效用項(xiàng)集

(5) else if psum+rpsum≥Minutl

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

/*構(gòu)造k-項(xiàng)集列表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的高效用項(xiàng)集后，進(jìn)行窗口滑動(dòng)。

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 效用閾值對(duì)算法性能的影響

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

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

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

從圖5和圖6可以看出，4種算法都隨著最小效用閾值的增大，運(yùn)行時(shí)間也逐漸變小。因?yàn)樽钚⌒в瞄撝翟酱?，算法產(chǎn)生的高效用項(xiàng)集就越少，運(yùn)行時(shí)間就越小。在Retail數(shù)據(jù)集中，HUPMS算法和CHUI-Miner算法耗時(shí)明顯多于HUPN_SW算法，GHUM算法與HUPN_SW算法相差不大；在Connect數(shù)據(jù)集中，HUPMS算法運(yùn)行時(shí)間明顯高于其它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 可擴(kuò)展性測試

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

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

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

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

3.2.3 不同批次大小的運(yùn)行時(shí)間

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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