動(dòng)態(tài)數(shù)據(jù)上的高效用模式挖掘綜述

單芝慧，韓 萌，韓 強(qiáng)

（北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，銀川 750021）

0 引言

頻繁模式挖掘（Frequent Pattern Mining，F(xiàn)PM）旨在發(fā)現(xiàn)客戶事務(wù)數(shù)據(jù)集中的頻繁模式。1994 年Agrawal 等［1］第一次提出了頻繁模式挖掘算法Apriori，但挖掘出的項(xiàng)集不能體現(xiàn)項(xiàng)的利潤，會(huì)出現(xiàn)無意義的模式。為了解決頻繁模式挖掘的限制，提出了高效用模式挖掘（High Utility Pattern Mining，HUPM）。效用挖掘是為了發(fā)現(xiàn)具有高效用的模式，為每個(gè)項(xiàng)設(shè)置內(nèi)部效用和外部效用，以挖掘高利潤的項(xiàng)集。若項(xiàng)集的效用大于或等于用戶設(shè)置的最小效用閾值，該項(xiàng)集便被認(rèn)為是具有高利潤的即高效用的。Liu 等［2］提出了兩階段高效用項(xiàng)集挖掘（High Utility Itemset Minging，HUIM）算法。考慮到事務(wù)的長度對(duì)利潤的影響，研究者進(jìn)一步提出了高效用平均項(xiàng)集挖掘［3-4］。對(duì)于序列數(shù)據(jù)集，Yin 等［5］首次提出了高效用序列模式挖掘。由于用戶通常很難界定閾值的大小，研究者進(jìn)一步提出了在事務(wù)數(shù)據(jù)集中挖掘top-k個(gè)高效用模式［6］。

在移動(dòng)計(jì)算方面應(yīng)用高效用模式挖掘能夠發(fā)現(xiàn)有趣的模式。高效用空間模式挖掘可以通過具有全球定位系統(tǒng)（Global Positioning System，GPS）服務(wù)的移動(dòng)設(shè)備記錄用戶的移動(dòng)日志，結(jié)合日志和支付記錄，可以生成移動(dòng)路徑與購買事務(wù)的序列。例如，一個(gè)移動(dòng)序列模式表示顧客經(jīng)常通過路徑在A 處吃火鍋，在C 處購買果茶。若店主了解這種模式，就可以對(duì)在A 處吃過火鍋的顧客促銷果茶，提高顧客的購買欲望；投資者也可借助該模式判斷是否在周邊開設(shè)果茶店鋪［7］。挖掘Web 訪問序列可以從Web 日志中發(fā)現(xiàn)有用的知識(shí)，通過分析用戶在網(wǎng)頁中花費(fèi)的時(shí)間，提取更真實(shí)的信息［8］。對(duì)生物基因序列應(yīng)用高效用模式挖掘技術(shù)也可以發(fā)現(xiàn)有用的知識(shí)，同時(shí)考慮基因-疾病關(guān)聯(lián)程度來提出效用模型，從時(shí)間進(jìn)程微陣列數(shù)據(jù)集中發(fā)現(xiàn)重要的高效基因調(diào)控序列模式［9］。高效用模式挖掘在商業(yè)智能中有廣泛的應(yīng)用如購物籃分析。用戶的購買行為包含有價(jià)值的信息，可以通過分析用戶行為，挖掘具有高利潤的購買行為。將用戶購買數(shù)量定義為內(nèi)部效用，物品利潤定義為外部利潤，從而進(jìn)行挖掘操作［10］。使用“效用”衡量模式對(duì)用戶的重要性，高效用模式挖掘還可以用于風(fēng)險(xiǎn)預(yù)測(cè)，如預(yù)測(cè)疫情期間哪個(gè)城市將會(huì)成為疫情暴發(fā)點(diǎn)，或預(yù)測(cè)微博、推特等社交媒體中下一階段的熱門話題。詳細(xì)信息如圖1 所示。

圖1 常見高效用模式的應(yīng)用Fig.1 Common applications of high utility pattern

在實(shí)際應(yīng)用中事務(wù)數(shù)據(jù)集會(huì)插入新的事務(wù)，使得存儲(chǔ)在數(shù)據(jù)集中的數(shù)據(jù)量不斷增加。傳統(tǒng)的高效用模式挖掘是以批處理模式運(yùn)行的，若用戶想要從更新的數(shù)據(jù)集中提取模式，需要從頭開始挖掘，即它忽略了先前的結(jié)果，這種方式效率低下。近年來，已經(jīng)提出了幾種增量高效用項(xiàng)集挖掘（incremental High Utility Itemset Mining，iHUIM）算法［11-12］。開發(fā)高效的iHUIM 算法是一個(gè)新興的研究，它使HUIM 任務(wù)在數(shù)據(jù)集更新方面具有更好的伸縮性。為了提高性能，還提出了基于樹結(jié)構(gòu)［13-14］和列表結(jié)構(gòu)［15］的iHUIM 算法。在信息時(shí)代，數(shù)據(jù)都是作為流產(chǎn)生的，網(wǎng)站上的用戶活動(dòng)、金融交易等數(shù)據(jù)流包含與一般靜態(tài)數(shù)據(jù)相似的信息，但其到達(dá)速度快、數(shù)量多，使得流中的數(shù)據(jù)只能挖掘檢查一次，且盡快生成挖掘結(jié)果。目前已經(jīng)提出了在滑動(dòng)窗口（sliding window）［16］、衰減窗口（damped window）［17］、界標(biāo)窗口（landmark window）［18］上挖掘高效用模式的技術(shù)。

Gan 等［19］對(duì)增量高效用模式挖掘算法進(jìn)行了分類對(duì)比。Suvarna 等［20］從數(shù)據(jù)集的角度對(duì)靜態(tài)數(shù)據(jù)及數(shù)據(jù)流上的高效用模式挖掘算法進(jìn)行了總結(jié)。Fournier-Viger 等［21］對(duì)高效用模式挖掘算法進(jìn)行了總結(jié)，主要是針對(duì)靜態(tài)數(shù)據(jù)，僅有一小節(jié)涉及動(dòng)態(tài)數(shù)據(jù)。王少峰等［22］對(duì)數(shù)據(jù)流上的高效用模式挖掘算法進(jìn)行了總結(jié)比較。此前的文獻(xiàn)大多從靜態(tài)數(shù)據(jù)或僅從增量或者數(shù)據(jù)流中的一個(gè)方面介紹算法，并未對(duì)整個(gè)動(dòng)態(tài)數(shù)據(jù)上的算法進(jìn)行分類總結(jié)，而本文對(duì)不同類型的動(dòng)態(tài)數(shù)據(jù)上的高效用模式挖掘算法進(jìn)行了分類總結(jié)。本文的主要工作如下：

1）首次從動(dòng)態(tài)數(shù)據(jù)的角度，即增量數(shù)據(jù)、數(shù)據(jù)流、動(dòng)態(tài)刪除和動(dòng)態(tài)修改數(shù)據(jù)上對(duì)高效用模式及融合高效用模式進(jìn)行了較全面的分析總結(jié)。

2）從樹結(jié)構(gòu)、列表結(jié)構(gòu)和其他結(jié)構(gòu)對(duì)高效用模式進(jìn)行了分類總結(jié)，明確了不同結(jié)構(gòu)上算法的特點(diǎn)。

3）從動(dòng)態(tài)利潤、動(dòng)態(tài)序列和動(dòng)態(tài)空間數(shù)據(jù)的角度對(duì)算法進(jìn)行了總結(jié)。

1 概念與定義

本章介紹高效用模式的一些基本計(jì)算公式及定義，此外，還介紹了不同動(dòng)態(tài)數(shù)據(jù)集的特點(diǎn)。

令I(lǐng)表示項(xiàng)i的集合，即I={i1，i2，…，im}是一組項(xiàng)，D={T1，T2，…，Tn}是事務(wù)數(shù)據(jù)集，其中每個(gè)事務(wù)Ti中的項(xiàng)是I的子集。項(xiàng)集X是I的子集。事務(wù)Tq中的項(xiàng)ip的數(shù)量由n(ip，Tq)表示。外部效用s(ip)是效用表中項(xiàng)ip的單位值（例如利潤）。事務(wù)Tq中項(xiàng)ip的效用，由u(ip，Tq)表示，為內(nèi)部效用與外部效用的乘積，定義為n(ip，Tq)×s(ip)。

定義1內(nèi)部效用［23］。在事務(wù)T中項(xiàng)i的內(nèi)部效用定義為in(i，T)。

例如：在表1 中，T2中項(xiàng)a的內(nèi)部效用為in(a，T2)=1。

表1 事務(wù)數(shù)據(jù)集Tab.1 Transaction dataset

定義2外部效用［23］。項(xiàng)i的外部效用定義為ex(i)。

例如：在表2 中，項(xiàng)a的外部效用為ex(a)=5。

表2 效用表Tab.2 Utility table

定義3項(xiàng)的效用［23］。事務(wù)T中項(xiàng)i的效用定義為：

例如：在表1 中，事務(wù)T2中項(xiàng)a的效用為：

定義4項(xiàng)集的效用［23］。項(xiàng)集X為I的子集。事務(wù)Tq中X的效用，由u(X，Tq)表示，定義為：

例如：表1 中，在事務(wù)T2中項(xiàng)集{ab}的效用為u(ab，T2)=u(a，T2)+u(b，T2)=1× 5+2× 4=13。

定義5項(xiàng)集在數(shù)據(jù)集中的效用［23］。項(xiàng)集X在數(shù)據(jù)集中的效用，由u(X)表示，定義為：

例如：項(xiàng)集{ab}在數(shù)據(jù)集中的效用為

定義6最小效用閾值［23］。δ是用戶指定的0-1 的數(shù)，最小效用閾值為：

定義7事務(wù)效用［23］。事務(wù)Tq的事務(wù)效用定義為：

定義8事務(wù)加權(quán)效用［23］。項(xiàng)集X的事務(wù)加權(quán)效用定義為twu(X)，是項(xiàng)集X包含的所有事務(wù)的效用之和：

定義9高事務(wù)加權(quán)效用項(xiàng)集［23］。對(duì)于項(xiàng)集X，如果twu(X) ≥mintuil，則X是高事務(wù)加權(quán)效用項(xiàng)集。

定義10 平均效用［3-4］。l(X)表示項(xiàng)集X的長度或大小，項(xiàng)集X在事務(wù)T中的平均效用定義為au(X，T)：

定義11高平均效用項(xiàng)集［3-4］。如果au(X) ≥minutil，X是高平均效用項(xiàng)集。

定義12最大效用［3-4］。事務(wù)T的最大效用標(biāo)記為mu(T)，定義為：

定義13平均效用上邊界［3-4］。項(xiàng)集X的平均效用上界標(biāo)記為ub(X)，定義為：

對(duì)于序列數(shù)據(jù)集，序列S的每個(gè)事件e中的每個(gè)項(xiàng)i都包含一個(gè)內(nèi)部效用值intU(i，e，S)［5］。每個(gè)不同的項(xiàng)都有相應(yīng)的外部效用程序值extU(i)。

在序列S的事件e中，項(xiàng)i的效用是utility(i，e，S)，是其內(nèi)部效用和外部效用的乘積utility(i，e，S)=intU(i，e，S)×extU(i)。序列S中的模式P的效用為utility(P，S)，可以通過對(duì)該序列中出現(xiàn)的所有模式項(xiàng)的效用求和得出。n個(gè)序列的序列數(shù)據(jù)集SD中的模式P的效用［5］定義為：

例如表3 和表4，序列S2的事件2 中d的效用定義為：

表3 序列數(shù)據(jù)集Tab.3 Sequence dataset

表4 序列數(shù)據(jù)集的外部效用Tab.4 External utility of sequence dataset

utility(d，2，S2)=intU(d，2，S2)×extU(d)=2× 2=4，同理可得utility(b，3，S3)=9。

例如表3 和表4，序列S5中模式的效用為utility()=12+4=16。

事務(wù)中項(xiàng)的單位利潤記為pu(i，T)，事務(wù)T中的項(xiàng)i的購買數(shù)量表示為qu(i，T)。項(xiàng)在事務(wù)中的效用表示為u(i，T)［24］得出u(i，T)=qu(i，T)×pu(i，T)。

例如，表5 描述的數(shù)據(jù)集［24］，事務(wù)T2中項(xiàng)b的單位利潤為1.9，在T2中的購買數(shù)量為1，因此在T2中項(xiàng)b的效用為u(b，T2)=qu(b，T2)×pu(i，T2)=1.9× 1=1.9。項(xiàng)b在數(shù)據(jù)集中的效用計(jì)算為u(b，T1)+u(b，T2)+u(b，T4)+u(b，T5)=2+1.9+4+8=15.9。

表5 動(dòng)態(tài)利潤數(shù)據(jù)集Tab.5 Dynamic profit dataset

2 增量數(shù)據(jù)

數(shù)據(jù)的時(shí)間尺度決定了如何處理和存儲(chǔ)數(shù)據(jù)。動(dòng)態(tài)數(shù)據(jù)或事務(wù)數(shù)據(jù)定期更新信息，隨著新信息的出現(xiàn)，它會(huì)隨時(shí)間產(chǎn)生變化?，F(xiàn)實(shí)世界的數(shù)據(jù)大多數(shù)是動(dòng)態(tài)數(shù)據(jù)，隨著時(shí)間的推移事務(wù)不斷積累。本章總結(jié)了增量數(shù)據(jù)上的高效用模式挖掘算法。

2.1 基于樹結(jié)構(gòu)

使用樹結(jié)構(gòu)將效用信息存儲(chǔ)在樹節(jié)點(diǎn)上能夠減少數(shù)據(jù)集掃描次數(shù)，減少內(nèi)存的使用且能夠更高效地挖掘高效用模式。目前，研究者已經(jīng)提出了不同的樹結(jié)構(gòu)挖掘高效用模式，都具有較好的性能。本節(jié)總結(jié)了基于樹結(jié)構(gòu)的增量高效用模式挖掘算法，并對(duì)算法使用的剪枝策略、方法及優(yōu)缺點(diǎn)等信息進(jìn)行了總結(jié)。

Ahmed 等［25］第一次提出了在動(dòng)態(tài)數(shù)據(jù)上挖掘高效用項(xiàng)集（High Utility Item，HUI）的算法，使用樹結(jié)構(gòu)IIUT（Incremental and Interactive Utility Tree），該數(shù)據(jù)結(jié)構(gòu)具有構(gòu)建一次數(shù)據(jù)結(jié)構(gòu)執(zhí)行多次挖掘操作的性能。它利用模式增長挖掘方法避免逐級(jí)生成候選和測(cè)試問題，與其他算法相比，僅需兩次數(shù)據(jù)集掃描。它使用事務(wù)加權(quán)效用（Transaction Weighted Utilization，TWU）值作為剪枝策略減少搜索空間。IIUT 在頭表和樹的節(jié)點(diǎn)內(nèi)顯式維護(hù)TWU。為了促進(jìn)樹的遍歷，還維護(hù)了相鄰的鏈接。Ahmed 等［26］進(jìn)一步提出了三種樹結(jié)構(gòu)來提高算法的性能，分別為IHUPL-Tree（IHUP Lexicographic Tree），IHUPTF-Tree（IHUP Transaction Frequency Tree），IHUPTWU-Tree（IHUP-Transaction-Weighted Utilization Tree）。前兩者減少了內(nèi)存，后者提高了挖掘效率。引入事務(wù)頻率（Transaction Frequency，TF）提高第二次數(shù)據(jù)集掃描的速度，但該樹結(jié)構(gòu)IHUP-Tree 是冗余的，因此IHUP 算法的效率相對(duì)較低。Song 等［13］提出了一種并發(fā)算法CHUI-Mine（Concurrent High Utility Itemsets Mine），用于通過動(dòng)態(tài)剪枝樹結(jié)構(gòu)來挖掘高效用項(xiàng)集。該算法引入CHUI-Tree樹結(jié)構(gòu)存儲(chǔ)候選項(xiàng)集的效用信息，通過樹構(gòu)建過程中的高效用項(xiàng)集的計(jì)數(shù)變化實(shí)現(xiàn)樹的剪枝。CHUI-Mine 算法利用并發(fā)策略，可以同時(shí)實(shí)現(xiàn)構(gòu)建CHUI-Tree 和發(fā)現(xiàn)高效用項(xiàng)集，無需等待整棵樹構(gòu)建完成。

為了進(jìn)一步優(yōu)化數(shù)據(jù)結(jié)構(gòu)，Zheng 等［14］提出了iCHUM（incremental Compressed High Utility Mining）算法。該算法利用項(xiàng)的TWU 來構(gòu)造樹結(jié)構(gòu)iCHUM-Tree，將新增的數(shù)據(jù)附加到原始數(shù)據(jù)集后，iCHUM 算法將更新iCHUM-Tree，無需完全重建樹結(jié)構(gòu)。高效用項(xiàng)集的信息保留在iCHUM 樹中，在頭表中按照TWU 降序排序，自底向上有序遍歷分支，提高挖掘效率。該算法使用模式增長方法挖掘，遞歸挖掘的復(fù)雜度由iCHUM-Tree 的高度和節(jié)點(diǎn)數(shù)確定。Yun 等［27］基于樹結(jié)構(gòu)HUPID-Tree（High Utility Patterns in Incremental Databases Tree）提出了 HUPID-Growth（High Utility Patterns in Incremental Databases Growth）算法。HUPID-Tree 只需要一次數(shù)據(jù)集掃描，為了更有效地處理增量數(shù)據(jù)創(chuàng)建了TIList（Tail-node Information List），使用HUPID-Growth 挖掘方法減少高估的效用，以此來減少搜索空間和候選項(xiàng)集的數(shù)量。

Kim 等［28］提出了IMHAUI（Incremental Mining of High Average-Utility Itemsets）算法用于在增量數(shù)據(jù)集上挖掘高平均效用項(xiàng)集。該算法提出了一個(gè)新的樹結(jié)構(gòu)IHAUI-Tree（Incremental High Average Utility Itemset Tree），采用了重組技術(shù)中的路徑調(diào)整方法來構(gòu)建更緊湊的樹，基于AUUB（Average-Utility Upper-Bound）降序重構(gòu)IHAUI-Tree。該算法使用模式增長方式來挖掘，減少了數(shù)據(jù)集掃描的次數(shù)及產(chǎn)生候選項(xiàng)集的數(shù)量，但是產(chǎn)生候選項(xiàng)集仍需消耗大量的時(shí)間。Radkar 等［29］提出了FUPT-HOUIN（Fast updated Utility Pattern Tree for High On-shelf Utility Items with Negative value）算法，用于從動(dòng)態(tài)數(shù)據(jù)集中挖掘帶有負(fù)項(xiàng)值高效用貨架項(xiàng)集。該算法采用樹結(jié)構(gòu)，在第一階段，掃描原始數(shù)據(jù)集構(gòu)建效用樹；在第二階段更新效用樹，必要時(shí)會(huì)重新掃描數(shù)據(jù)集，不是每次變化都掃描數(shù)據(jù)集。效用樹避免了不必要的項(xiàng)集產(chǎn)生并減少了執(zhí)行時(shí)間。Ahmed 等［30］提出了在Web 序列中挖掘高效用項(xiàng)集的方法，提出了新的樹結(jié)構(gòu)IUWAS-tree（Incremental Utility-based Web Access Sequence Tree）。該樹結(jié)構(gòu)只需要一次數(shù)據(jù)集掃描即可構(gòu)建并挖掘所有的候選序列，使用Web 訪問序列效用（Web access sequence utility，wasu）來剪枝搜索空間，該算法使用序列模式增長挖掘方法避免逐級(jí)生成候選、驗(yàn)證和多次數(shù)據(jù)集掃描問題。Wang等［31］提出了IncUSP-Miner（Incremental Utility Sequential Patterns Miner）算法在增量數(shù)據(jù)上挖掘高效用序列模式（High Utility Sequential Pattern，HUSP）。該算法提出了一個(gè)更嚴(yán)格的序列效用上邊界（Tight Sequence Utility，TSU）來避免冗余計(jì)算；此外，還設(shè)計(jì)了新的候選模式樹來維護(hù)TSU 值大于或等于最小效用閾值的序列，將一組輔助效用信息存儲(chǔ)在每個(gè)節(jié)點(diǎn)中，并且無需重新計(jì)算就可以快速獲得該序列的輔助信息，從而提高了挖掘效率。Wang 等［32］進(jìn)一步提出了IncUSP-Miner+算法來逐步挖掘HUSP。該算法提出了一個(gè)更嚴(yán)格TSU，并且設(shè)計(jì)了緊湊的候選模式樹，以緩沖其序列TSU 值大于或等于原始數(shù)據(jù)集中的最小效用閾值；使用節(jié)點(diǎn)跳過策略來提高挖掘效率，對(duì)于不能跳過的節(jié)點(diǎn)，使用了兩個(gè)策略來減少數(shù)據(jù)集掃描的規(guī)模。為了更清晰地比較各個(gè)算法的區(qū)別，本文對(duì)動(dòng)態(tài)數(shù)據(jù)集上使用樹結(jié)構(gòu)的高效用模式挖掘算法進(jìn)行總結(jié)，如圖2 所示。

圖2 基于樹結(jié)構(gòu)的HUPM算法Fig.2 Tree structure-based HUPM algorithms

2.2 基于列表結(jié)構(gòu)

效用列表通常會(huì)存儲(chǔ)項(xiàng)的標(biāo)識(shí)符、效用及剩余效用，并按照TWU 大小排列，隨著事務(wù)的插入，TWU 與剩余效用將會(huì)不斷變化。效用列表結(jié)構(gòu)占用的內(nèi)存相較于原始數(shù)據(jù)集非常小，能夠有效減少內(nèi)存，且列表結(jié)構(gòu)無需產(chǎn)生候選項(xiàng)集。本節(jié)對(duì)使用列表結(jié)構(gòu)的高效用模式挖掘算法進(jìn)行了總結(jié)。

Lin 等［15］提出了HUI-list-INS（High Utiltity Itemsets list INSertion）算法。該算法使用列表結(jié)構(gòu)減少計(jì)算消耗，且不產(chǎn)生候選項(xiàng)集，使用枚舉樹和2-項(xiàng)集之間的關(guān)系提高計(jì)算速度，使用項(xiàng)集的內(nèi)部效用與剩余效用之和作為剪枝策略，減小了搜索空間。另外，在該算法中還采用了估計(jì)效用共現(xiàn)（Estimated Utility Co-occurrence，EUCP）修剪策略，以進(jìn)一步保持2-項(xiàng)集的關(guān)系，從而消除了效用較低的擴(kuò)展項(xiàng)集。Yun等［33］提出的LIHUP（List based Incremental High Utiltiy Pattern）也使用效用列表存儲(chǔ)效用信息，僅需掃描數(shù)據(jù)集一次，無需產(chǎn)生候選項(xiàng)集，通過掃描原始數(shù)據(jù)集來構(gòu)建全局列表，利用ru（remain utiltiy）來重建全局列表。Kim 等［34］提出了LIMHAUP（List based Incremental Mining of High Average Utility Pattern），使用HAUP-List（High Average Utility Pattern List）更緊湊地存儲(chǔ)模式信息，并設(shè)計(jì)了一個(gè)重組過程來處理新插入的數(shù)據(jù)。

Yun 等［35］提出了基于索引列表的IIHUM（Indexed list based Incremental High Utility pattern Mining）算法，僅需要一次數(shù)據(jù)集掃描。數(shù)據(jù)集的信息被存儲(chǔ)在IIU-List（Incremental Indexed Utility List）中，列表存儲(chǔ)了NextItem，NextItem 指向相應(yīng)事務(wù)中當(dāng)前項(xiàng)旁邊的項(xiàng)標(biāo)簽；ActUtil（Actual Utility）是事務(wù)中當(dāng)前項(xiàng)的實(shí)際效用值；NextIdx 指示IIU 列表中與當(dāng)前項(xiàng)所在的下一個(gè)項(xiàng)相對(duì)應(yīng)的條目；SumUtil（Sum of the ActUtil）是當(dāng)前IIU 列表中所有ActUtil 值的總和；RUtil 表示當(dāng)前項(xiàng)擴(kuò)展到最大值時(shí)可以添加到SumUtil 的最大效用值。該算法通過TWU 升序重組全局IIU-List，以更有效的方式從增量數(shù)據(jù)中挖掘高效用模式，將模式P的上邊界設(shè)置為效用與剩余效用之和。Dam 等［36］提出了IncCHUI（Incremental Closed High-Utility Itemset miner）算法，該算法可從增量數(shù)據(jù)中有效地挖掘閉合高效用項(xiàng)集（Closed High Utility Itemsets，CHUI）。該算法使用增量式效用列表結(jié)構(gòu)，根據(jù)最佳排序順序?qū)α斜磉M(jìn)行重組，使用TWU 快速構(gòu)造增量效用列表，并消除未更新的候選對(duì)象。最后該算法提出一種有效的基于散列的方法來更新或插入找到的新閉合項(xiàng)集。吳倩等［37］提出了挖掘top-k高效用模式算法TOPK-HUP-INS（INcremental Top-KHigh Utility Pattern mining），使用效用列表存儲(chǔ)事務(wù)信息。該算法需要兩次數(shù)據(jù)集掃描來構(gòu)建所有的1 項(xiàng)集，并使用深度優(yōu)先擴(kuò)展策略使得topkUti 快速增長，刪除了大量低效用模式。Lin 等［38］提出了PRE-HAUIMI（Incremental updating the High Average-Utility Itemset Mining with PRE-large concept）算法在動(dòng)態(tài)數(shù)據(jù)上挖掘高平均效用項(xiàng)集，該算法使用效用列表結(jié)構(gòu)AUL（Average-Utility-List）并應(yīng) 用HAUIM（High Average-Utility Itemset Mining）的預(yù)大（Pre-Large）概念加快挖掘性能，減少了重復(fù)的數(shù)據(jù)集掃描并獲得了正確的HAUI（High Average-Utility Itemset）。此外，建立了枚舉樹來確定是否應(yīng)探索樹節(jié)點(diǎn)的超集，減少了對(duì)沒有希望的候選項(xiàng)集的AUL 結(jié)構(gòu)執(zhí)行的連接操作。

張春硯等［39］提出了CIHUM（Compact Incremental High Utility Mining）算法，采用緊湊的效用列表CUL（Compact Utility List）和HUI-trie（High Utility Itemset trie）從增量數(shù)據(jù)集中挖掘高效用模式。HUI-trie 可以及時(shí)更新和存儲(chǔ)高效用項(xiàng)集的效用信息。Nguyen 等［40］提出了CHUI-Mine（Closed High Utiltiy Itemset Mine）算法的優(yōu)化版本，直接從動(dòng)態(tài)利潤數(shù)據(jù)中挖掘MHUI（Maximal High Utility Itemsets），使 用EUCS（Estimated Utility Co-occurrence Structure）和EUCP 剪枝技術(shù)減少候選項(xiàng)集。該算法還進(jìn)一步使用了CUIP（Continuous Unpromising Item Pruning）來減少搜索空間中的候選項(xiàng)集和MHUIs 的挖掘時(shí)間。CUIP 通 過FUCS（First Utility Cooccurrence Structure）不斷更新項(xiàng)的TWU 值。Nguyen 等［40］將P-set、EUCS 和EUCP、FCUS 和CUIP 合并到了CHUI-Power 算法的最終版本中，獲得了較好的性能。Ishita 等［41］認(rèn)為現(xiàn)有的算法并未考慮模式的規(guī)律性，故提出了在增量序列數(shù)據(jù)上挖掘規(guī)律的高效用序列模式的算法RIncHusp（Regular High utility sequential pattern mining in Incremental databases），使用列表結(jié)構(gòu)來存儲(chǔ)信息包括HS（High utility Sequences）和SHS（Semi-High utility Sequences）列表，并使用模式的效用和剩余效用來剪枝搜索空間。如果模式P的效用大于或等于最大剩余效用，將作為規(guī)則的半高效用序列存儲(chǔ)在SHS 中；否則將被剪枝。效用列表的算法總結(jié)如圖3 所示。

圖3 基于效用列表的HUPM算法Fig.3 Utility list-based HUPM algorithms

2.3 其他數(shù)據(jù)結(jié)構(gòu)

除了使用樹與列表結(jié)構(gòu)存儲(chǔ)效用信息，仍然存在使用預(yù)大（Pre-Large）概念、兩階段等方式存儲(chǔ)效用信息的算法。本節(jié)對(duì)這些算法進(jìn)行了總結(jié)。

Hong 等［42］提出了一種兩階段算法在增量數(shù)據(jù)上挖掘高平均效用項(xiàng)集。在第一階段，使用平均效用上邊界高估項(xiàng)集，在第二階段，計(jì)算高平均效用項(xiàng)集上邊界的實(shí)際平均效用值；但其運(yùn)行時(shí)間和內(nèi)存消耗等性能較低。Lin 等［43］提出了FUP-HUI（Fast UPdate High Utility Itemset），該算法根據(jù)項(xiàng)集是否屬于原始數(shù)據(jù)集以及新數(shù)據(jù)集中的高TWU 項(xiàng)集將它們劃分為四個(gè)部分，然后處理每個(gè)部分，以自己的方式更新發(fā)現(xiàn)的高效用項(xiàng)集。Lin 等［44］進(jìn)一步提出了FUP-HU（Fast UPdate High Utility），該算法比兩階段批量挖掘算法具有更好的性能；但是，如果某些項(xiàng)集在原始數(shù)據(jù)集中較小，而在新插入的事務(wù)中較大，則仍需要重新掃描數(shù)據(jù)集，耗費(fèi)時(shí)間。

Lin 等［45］提出了PRE-HUIDE 的兩階段算法以有效地維護(hù)基于預(yù)大概念發(fā)現(xiàn)的高效用項(xiàng)集。該算法結(jié)合且修改了兩階段算法和預(yù)大概念。項(xiàng)集首先分為三個(gè)部分，然后對(duì)每部分執(zhí)行單獨(dú)的操作，定義了上邊界和下邊界來區(qū)分高（大）和預(yù)大效用項(xiàng)集。預(yù)大概念用于通過確定新插入的事務(wù)數(shù)來減少對(duì)原始數(shù)據(jù)集的重新掃描，僅當(dāng)插入的事務(wù)數(shù)大于安全范圍時(shí)才需要重新掃描原始數(shù)據(jù)集，使用向下閉包屬性減少候選項(xiàng)集的數(shù)量和掃描數(shù)據(jù)集的時(shí)間。但以上算法仍然需要額外的數(shù)據(jù)集掃描且產(chǎn)生了大量的候選項(xiàng)集。為了解決以上問題，Lee 等［46］提出了一個(gè)更高效的基于Pre-large 概念的PIHUP（Pre-large Incremental High Utility Patterns）算法，提出了更適用Pre-large 概念構(gòu)造樹來存儲(chǔ)和維護(hù)數(shù)據(jù)，使用兩個(gè)閾值Su和Sl，有效地減少了冗余操作和內(nèi)存空間，但該算法使用了高估原則來保證向下閉包屬性，產(chǎn)生了無用的候選模式。Nguyen 等［24］提出了在動(dòng)態(tài)利潤數(shù)據(jù)上挖掘高效用項(xiàng)集的算法MEFIM（Modified EFficient high-utility Itemset Mining），重新定義了效用度量，還提出了MEFIM 算法的改進(jìn)版 本 iMEFIM（incremental Modified EFficient high-utility Itemset Mining）。iMEFIM 引入了 一種稱 為P-set（TIDs（Transactions IDs）Projection of an itemset on a database）的新穎數(shù)據(jù)結(jié)構(gòu)，事務(wù)標(biāo)識(shí)符（TID）在數(shù)據(jù)集上投影項(xiàng)集的概念可用于減少在投影數(shù)據(jù)庫中需要確定哪些項(xiàng)可以附加到項(xiàng)集，以生成潛在的高效用項(xiàng)集進(jìn)行掃描的事務(wù)數(shù)量，使用事務(wù)合并以及局部效用和子樹效用上限來修剪搜索空間。

空間數(shù)據(jù)挖掘［47］可以用來從空間數(shù)據(jù)中發(fā)現(xiàn)有趣的和未知的模式，空間共處同一位置表示一組經(jīng)常在附近區(qū)域觀察到的空間特征，其應(yīng)用包括：生物種群，如西尼羅河病毒，它經(jīng)常出現(xiàn)在蚊子多的地區(qū)；交通問題，如交通擁堵與車禍之間的關(guān)系。Wang 等［48］提出了在增量空間數(shù)據(jù)集中挖掘空間高效用的基本算法，但是不夠高效，進(jìn)而提出了PUCP（Part Update of Co-location Patterns）算法更高效地更新高效用共處模式。更新空間模式是一個(gè)復(fù)雜的過程，因?yàn)樾聰?shù)據(jù)會(huì)增加新的鄰居關(guān)系，該算法只計(jì)算新變換的鄰居關(guān)系的值，鄰居數(shù)量的增加可能會(huì)影響到高效用協(xié)同托管挖掘的結(jié)果。Wang 等［49］提出了UUOC（Utility Update Of Co-locations）算法，該算法解決了當(dāng)空間數(shù)據(jù)集通過增加和減少數(shù)據(jù)點(diǎn)而不斷變化時(shí)進(jìn)行增量式高效用協(xié)同定位挖掘的問題，使用變化的共置位實(shí)例有效地更新已經(jīng)變化的共置位模式的效用值，只需要處理變化后的模式。該算法將更改后的共處位置分為四種情況，并利用變更后的共處位置的性質(zhì)和引理來減少UUOC 的計(jì)算成本。

2.4 算法性能評(píng)估

為了更清晰地觀察算法的性能，本文采用定量分析的方法對(duì)同一數(shù)據(jù)集上的不同算法的運(yùn)行時(shí)間和內(nèi)存消耗進(jìn)行了對(duì)比。此外，還對(duì)部分增量數(shù)據(jù)上的高效用模式挖掘算法的時(shí)間復(fù)雜度進(jìn)行了分析比較。

本文選取了密集數(shù)據(jù)集Chess、Accident 和稀疏數(shù)據(jù)集Retail 比較算法的性能。在Chess 數(shù)據(jù)集上，CHUI-Mine 算法［13］在最小效用閾值為0.62 時(shí)，運(yùn)行時(shí)間為580 s 左右，而兩階段算法的運(yùn)行時(shí)間高于8 000 s，CHUI-Mine 使用了基于樹的修剪策略，減少了候選項(xiàng)集的數(shù)量。CIHUM［39］在相同的條件下，運(yùn)行時(shí)間比CHUI-Mine 更少，原因在于該算法使用效用列表結(jié)構(gòu)。在Retail 數(shù)據(jù)集上LIHUP［33］優(yōu)于HUPIDGrowth［27］，IIHUM 優(yōu) 于LIHUP。HUPID-Growth 使用了樹結(jié)構(gòu)，很難具有節(jié)點(diǎn)共享的結(jié)果，故隨著數(shù)據(jù)量的增大需要更多的內(nèi)存。而LIHUP 使用列表結(jié)構(gòu)，消耗的內(nèi)存較少。隨著數(shù)據(jù)量的增大，IIHUP 也表現(xiàn)出了較穩(wěn)定的運(yùn)行時(shí)間的增加。IIHUM 算法在稀疏數(shù)據(jù)集上優(yōu)于HUPID-Growth 與LIHUP。HUPID-Growth 在相對(duì)較小的數(shù)據(jù)集上有較好的性能，但是隨著最小效用閾值的降低，HUPID-Growth 算法的運(yùn)行時(shí)間急劇增加，在Accident 數(shù)據(jù)集上當(dāng)最小效用閾值由30%變?yōu)?0%時(shí)，HUPID、LIHUP 比IIHUP 的運(yùn)行時(shí)間分別增加了44.49%、4.49%和1.5%。HUPID-Growth 算法運(yùn)行時(shí)間劇增的主要原因是需要構(gòu)造大量的本地樹結(jié)構(gòu)并且產(chǎn)生了許多候選項(xiàng)集，而IIHUP 使用了更有效的列表結(jié)構(gòu)無需產(chǎn)生候選項(xiàng)集。此時(shí)的內(nèi)存消耗也在增加，但是增加速度較為緩慢。IIHUP 在稀疏數(shù)據(jù)集及密集數(shù)據(jù)集上的性能都要優(yōu)于其他兩種算法。

算法的時(shí)間復(fù)雜度和空間復(fù)雜度表明了算法的性能。iCHUM算法［14］構(gòu)建iCHUM-Tree的空間復(fù)雜度為O()，其中mp表示有希望的項(xiàng)數(shù)；更新的時(shí)間復(fù)雜度為O()，其中n表示事務(wù)數(shù)，在最壞的情況下，它需要對(duì)mp個(gè)條目進(jìn)行n次冒泡排序。挖掘iCHUM-Tree的時(shí)間復(fù)雜度為O()，其中h是iCHUM-Tree的高度，mp表示有希望的項(xiàng)數(shù)。HUPID-Growth算法［27］的時(shí)間復(fù)雜度由樹的構(gòu)造、重構(gòu)樹以及挖掘過程三部分組成。令No和Ni分別為原始數(shù)據(jù)集和從原始數(shù)據(jù)集遞增的數(shù)據(jù)集中的事務(wù)數(shù)，Nm為數(shù)據(jù)集最長事務(wù)中的項(xiàng)數(shù)，需要O((No+Ni)×(Ni+1))的執(zhí)行時(shí)間，將原始數(shù)據(jù)集中的事務(wù)和增量增加的數(shù)據(jù)集插入到樹中。算法花費(fèi)O(No×(Nm+2))的執(zhí)行時(shí)間通過提取、排序和重新插入所有路徑來重構(gòu)樹，再次重組樹需要O((No+Ni)×(Nm+2))的時(shí)間，挖掘過程的復(fù)雜度O(No×(Nm+1))。算法總的時(shí)間復(fù)雜度為

對(duì)于IMHAUI 算法［28］，設(shè)n為增量數(shù)據(jù)集中包含的不同的項(xiàng)數(shù)，l為從數(shù)據(jù)集生成的項(xiàng)集的最大長度。該算法在整個(gè)增量挖掘過程中掃描數(shù)據(jù)集的時(shí)間復(fù)雜度為O(n2+n)，即O(3n2)。計(jì)算候選項(xiàng)的實(shí)際平均效用需要O((l+1)×n)的執(zhí)行時(shí)間。在挖掘過程中對(duì)AUUB 降序重構(gòu)的時(shí)間復(fù)雜度最壞情況為O(n2)。在IHAUI-Tree 中為n個(gè)項(xiàng)構(gòu)造局部樹需要O(2×m×n)的時(shí)間復(fù)雜度。整個(gè)挖掘過程的時(shí)間復(fù)雜度為。由于隨著遞歸模式增長操作的深度增加，本地樹的遞歸模式增長操作的時(shí)間逐漸變少，因此整個(gè)挖掘過程的時(shí)間復(fù)雜度可以簡(jiǎn)化為O(n2)。

在LIHUP［33］中令No和Ni為分別由Nm個(gè)項(xiàng)組成的原始數(shù)據(jù)集和增加的數(shù)據(jù)集中的事務(wù)數(shù)，Nc為候選項(xiàng)數(shù)。該算法用于增加的數(shù)據(jù)集的時(shí)間復(fù)雜度相較于原始數(shù)據(jù)集為O(No×Nm×Nc) 或O((No+Ni)×Nm×Nc)。LIMHAUP 算法［34］中，令事務(wù)數(shù)為m，項(xiàng)的個(gè)數(shù)為n，讀取數(shù)據(jù)集并構(gòu)建HAUP-List 需要O(m×n)，對(duì)HAUP-List 排序需要O(nlbn)，重構(gòu)HAUP-Lists 的復(fù)雜度為O(m×n)，重構(gòu)步驟總的時(shí)間復(fù)雜度表示為O(t×(nlbn+m×n))，t表示相同數(shù)據(jù)集插入的次數(shù)，挖掘過程的復(fù)雜度為O((2n-n)×m)。LIMHAUP 算法的總復(fù)雜度為O(m×n+t×(nlbn+m×n)+(2n-n)×m)。IncCHUI 算法［36］的時(shí)間復(fù)雜度由全局?jǐn)?shù)據(jù)結(jié)構(gòu)的構(gòu)建和更新與模式搜索組成。令nd與nn分別為原始數(shù)據(jù)集與增加部分的事務(wù)數(shù)，w為平均事務(wù)長度，m為不同的項(xiàng)的數(shù)目。全局?jǐn)?shù)據(jù)結(jié)構(gòu)構(gòu)建和更新的時(shí)間復(fù)雜度為O(nd×w+2 lg(m)+m×w)或者為O(nn×w+2mlg(m)+m×w)，分別大致為O((nd+m)×w)或O((nn+m)×w)，因?yàn)榕判蛑粓?zhí)行一次。搜索過程的時(shí)間復(fù)雜度為O(2m-1)。PRE-HAUIMI算法［38］中，設(shè)n是數(shù)據(jù)集中的事務(wù)數(shù)，數(shù)據(jù)集中最大事務(wù)的項(xiàng)數(shù)是m，因此在最壞的情況下，第一次數(shù)據(jù)集掃描需要O(m×n)的時(shí)間。計(jì)算數(shù)據(jù)集中事務(wù)效用總和需要O(n)，在最壞情況下建立AUL 結(jié)構(gòu)需要O(m)。設(shè)原始數(shù)據(jù)集中每個(gè)案例有k個(gè)項(xiàng)集，簡(jiǎn)單的操作將兩個(gè)AUL 結(jié)構(gòu)連接操作需要O(k×N)的時(shí)間，其中N是維護(hù)案例數(shù)。PRE-HAUIMI 算法中AUL 結(jié)構(gòu)的維護(hù)部分最多計(jì)算為O(m×n+n+m+k×N)。根據(jù)以上4 個(gè)基于效用列表的算法可以看出其根本區(qū)別在于構(gòu)造數(shù)據(jù)結(jié)構(gòu)與挖掘過程的復(fù)雜度。此外，不同挖掘不同的模式，其搜索過程的復(fù)雜度也大不相同，可從高平均效用項(xiàng)集挖掘算法LIMHAUP 與閉合高效用模式挖掘算法IncCHUI 挖掘過程的復(fù)雜度看出。

3 數(shù)據(jù)流

大部分研究高效用模式挖掘的算法都集中在靜態(tài)數(shù)據(jù)集上。隨著新應(yīng)用的出現(xiàn)，處理的數(shù)據(jù)可能在連續(xù)的數(shù)據(jù)流中，例如網(wǎng)絡(luò)流量分析、網(wǎng)絡(luò)入侵檢測(cè)和在線分析。數(shù)據(jù)流不僅連續(xù)、速度高而且不受限制，因此流中的每個(gè)項(xiàng)只能檢查一次，并需要盡快地生成挖掘結(jié)果。傳統(tǒng)的高效用模式挖掘需要多次掃描數(shù)據(jù)集，不適用于處理數(shù)據(jù)流上的數(shù)據(jù)。數(shù)據(jù)流上的高效用模式挖掘已經(jīng)成為一個(gè)重要的研究主題。本章按照在數(shù)據(jù)流上HUIM 所使用的不同類型的滑動(dòng)窗口來描述算法，如滑動(dòng)窗口（sliding window）［16］、衰減窗 口（damped window）［17］和界標(biāo)窗口（landmark window）［18］。

3.1 滑動(dòng)窗口模式的高效用算法

滑動(dòng)窗口并未明確定義窗口的起始與結(jié)束位置，僅定義了窗口的大小N。令Tnew表示新事物，Tnew-N+1表示歷史事務(wù)，即算法處理Tnew-N+1和Tnew之間的最新事務(wù)數(shù)據(jù)。當(dāng)Tnew+1到達(dá)時(shí)，Tnew-N+1會(huì)被移出窗口。處在窗口內(nèi)的事務(wù)具有相同的重要性，窗口以固定大小在數(shù)據(jù)流上進(jìn)行滑動(dòng)，不斷輸出結(jié)果。數(shù)據(jù)流挖掘使用較多的窗口模型便是滑動(dòng)窗口模型（Sliding Window Model，SWM）［50］。

Tsai［16］提出了一種基于加權(quán)滑動(dòng)窗口模型的HUIM 一階段算法HUI_W，使用TWU 減少搜索空間，重復(fù)使用存儲(chǔ)的信息，從而可以有效地發(fā)現(xiàn)數(shù)據(jù)流中所有的高加權(quán)效用項(xiàng)集；但該算法產(chǎn)生了大量錯(cuò)誤的候選項(xiàng)集，消耗了大量的內(nèi)存。Chu 等［51］提出了第一個(gè)從數(shù)據(jù)流中挖掘臨時(shí)高效用模式的算法THUI（Temporal High Utility Itemset）-Mine。該算法是兩階段算法，使用滑動(dòng)窗口過濾技術(shù)。該算法在每個(gè)分區(qū)中采用過濾閾值來處理生成的事務(wù)加權(quán)效用項(xiàng)集（Transaction Weighted Utilization Itemsets，TWUI）。Li 等［52］提出了兩種一階段算法MHUI-BIT（Mining High Utility Itemsets based on BITvector）和MHUI-TID（Mining High Utility Itemsets based on TIDlist）從事務(wù)敏感的滑動(dòng)窗口中挖掘高效用模式。該算法利用事務(wù)加權(quán)效用的向下閉包屬性，并使用位向量和TIDlist存儲(chǔ)項(xiàng)的信息，構(gòu)造字典樹挖掘HUI，有效減少了候選項(xiàng)的數(shù)量、處理時(shí)間和內(nèi)存使用，優(yōu)于THUI-Mine。Li 等［53］進(jìn)一步提出在數(shù)據(jù)流上挖掘帶有和不帶負(fù)效用的高效用模式，使用相同的數(shù)據(jù)結(jié)構(gòu)提高算法的效率。字典樹結(jié)構(gòu)只存儲(chǔ)候選2 項(xiàng)集，每個(gè)項(xiàng)的信息都能夠在當(dāng)前的窗口中獲得且不需要重復(fù)掃描，但逐級(jí)生成候選模式方法，使得算法在時(shí)間和存儲(chǔ)效率方面性能較低。

Li 等［54］提出了MHUI-max，使用TID 列表和基于字典樹的數(shù)據(jù)結(jié)構(gòu)LexTree-maxHTU 存儲(chǔ)來自當(dāng)前事務(wù)敏感滑動(dòng)窗口中的最大高效用模式，產(chǎn)生了較少的候選項(xiàng)集。與MHUIBIT 相比，該算法在最后一階段產(chǎn)生的候選項(xiàng)集所需內(nèi)存較少。以上算法都不具有一次構(gòu)建多次挖掘（Build Once Mine Many）［55］的特性。Ahmed 等［55］提出了使用HUS-tree（High Utility Stream tree）的HUPMS（High Utility Pattern Mining over Stream data）算法進(jìn)行增量式和交互式HUPM。該算法使用模式增長方式減少了大量的候選項(xiàng)集。此外，HUS-tree 的一次構(gòu)建挖掘多次的性能對(duì)交互式挖掘非常有效，減少了內(nèi)存的消耗。Shie 等［56］提出了GUIDE（Generation of maximal high Utility Itemsets from Data strEams）框架，從數(shù)據(jù)流中挖掘最大高效用模式，使用基于時(shí)間敏感的滑動(dòng)窗口GUIDESW算法，利用MUIsw-Tree 維護(hù)效用信息，是一種一階段算法，且使用事務(wù)投影技術(shù)，并對(duì)事務(wù)進(jìn)行排序以更新樹結(jié)構(gòu)。Feng等［57］提出了HUM-UT（High Utility itemsets Mining based on UT-Tree）算法，使用滑動(dòng)窗口過濾方法UT-Tree（Utility on Tail Tree）來維護(hù)項(xiàng)集的效用信息，效用信息僅存儲(chǔ)在尾節(jié)點(diǎn)上。HUM-UT 算法僅需一次數(shù)據(jù)集掃描，且不產(chǎn)生候選項(xiàng)集。

Zihayat 等［58］提出了T-HUDS 算法在數(shù)據(jù)流的滑動(dòng)窗口上挖掘top-k的高效用模式，使用更緊湊的樹結(jié)構(gòu)HUDS-tree存儲(chǔ)事務(wù)信息。T-HUDS 使用前綴效用模型剪枝搜索空間，產(chǎn)生了較少的候選項(xiàng)集，使用模式增長的方式有效地剪枝搜索空間。該算法提出了幾種初始化和動(dòng)態(tài)調(diào)整最小效用閾值的策略，但是該算法是兩階段算法，耗費(fèi)時(shí)間。慕歡歡等［59］提出了HUIDE（High-Utility Itemsets over Data Streams）算法，提出了一種有效的效用度量方法，采用基于時(shí)間的滑動(dòng)窗口技術(shù)并構(gòu)建HUI-tree（High Utility Itemsets tree）來存儲(chǔ)效用信息。該算法僅需一次數(shù)據(jù)集掃描，減少了候選項(xiàng)集的數(shù)量和時(shí)間、空間的消耗。Ryang 等［60］提出了SHU-Growth（Sliding window based High Utility Growth）算法，該算法基于HUPMS 提出了SHU-Tree（Sliding window based High Utility Tree）結(jié)構(gòu)，提出了通過減少高估的效用來減少搜索空間和候選項(xiàng)集的技術(shù)RGE（Reducing Global Estimated utilities）和RLE（Reducing Local Estimated utilities），通過減少高估的效用強(qiáng)調(diào)最新數(shù)據(jù)，并應(yīng)用滑動(dòng)窗口模型有效地挖掘。Yun等［61］提出了SHUPM（Sliding window based High Utility Pattern Mining）算法和列表結(jié)構(gòu)SHUP-List（Sliding window based High Utility Pattern List）用于在滑動(dòng)窗口模式的基礎(chǔ)上找到數(shù)據(jù)流上的高效用模式，使用SHUP-List 無需產(chǎn)生候選項(xiàng)集，并使用psum 來剪枝搜索空間。謝志軒等［62］提出了IHUM-UT（Improved High Utility Mining based on Utility Tree）算法。該算法使用全局頭表Global_HT 和全局樹UT-Tree 來存儲(chǔ)效用信息。Jaysawal 等［63］提出了一階段算法SOHUPDS（Single-pass One-phase algorithm for mining High Utility Patterns over a Data Stream），使用了投影數(shù)據(jù)庫方法和滑動(dòng)窗口技術(shù)；此外，還使用IUDataListSW 作為數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)了當(dāng)前滑動(dòng)窗口中各項(xiàng)的效用和上邊界。IUDataListSW 存儲(chǔ)項(xiàng)在事務(wù)中的位置，有效地初始投影數(shù)據(jù)庫并使用局部效用剪枝搜索空間。為了更有效地發(fā)現(xiàn)高效用模式，設(shè)置了兩個(gè)布爾值將節(jié)點(diǎn)分為了四種情況，能夠有效地更新當(dāng)前滑動(dòng)窗口中的高效用模式?；诨瑒?dòng)窗口的高效用模式算法如表6 所示。

表6 基于滑動(dòng)窗口的高效用模式算法Tab.6 Sliding window-based high utility pattern algorithms

數(shù)據(jù)流上高效用模式挖掘算法的性能比較實(shí)驗(yàn)包括運(yùn)行時(shí)間、內(nèi)存消耗和可擴(kuò)展性等。其中每個(gè)性能需要進(jìn)行的實(shí)驗(yàn)包括不同最小效用閾值下的實(shí)驗(yàn)，不同窗口大小下進(jìn)行的實(shí)驗(yàn)，在同一窗口下包含的批事務(wù)數(shù)也存在不同情況，以上情況均反映著算法的性能。由于目前數(shù)據(jù)流上的高效用模式挖掘算法不多，本文以3 個(gè)較新的算法為例，對(duì)其在Chainstore 數(shù)據(jù)集［63］上，在窗口大小為6 的條件下進(jìn)行對(duì)比。HUPMS［55］的執(zhí)行時(shí)間超過2 500 s，SOHUPDS［63］的執(zhí)行時(shí)間在100 s 之內(nèi)，SHUPM［61］的運(yùn)行時(shí)間介于兩者之間。其內(nèi)存使用情況也是如此，SOHUPDS 內(nèi)存消耗少于SHUPM，SHUPM 少于HUPMS。HUPMS 使用了樹結(jié)構(gòu)，SHUPM 使用了列表結(jié)構(gòu)，可見列表結(jié)構(gòu)的性能優(yōu)于樹結(jié)構(gòu)的性能，數(shù)據(jù)庫投影方法對(duì)算法的性能有更明顯的提升，SOHUPDS 使用了數(shù)據(jù)庫投影的方法，使用IUDataListSW 存儲(chǔ)當(dāng)前窗口的效用和項(xiàng)的上界，還存儲(chǔ)了項(xiàng)在事務(wù)中的位置，能夠有效地獲取有希望的項(xiàng)，進(jìn)行下一步的擴(kuò)展。隨著窗口數(shù)目的增大，算法的執(zhí)行時(shí)間及內(nèi)存消耗也會(huì)不斷增加。

3.2 其他窗口模式的高效用算法

窗口模式還有衰減窗口與界標(biāo)窗口。此外，高效用模式挖掘僅考慮了項(xiàng)的數(shù)量和單位利潤，為了使高效用模式挖掘算法進(jìn)一步適用于現(xiàn)實(shí)生活場(chǎng)景，研究者進(jìn)一步提出了數(shù)據(jù)流上的高效用序列模式、平均高效用模式和top-k高效用模式等算法。本節(jié)總結(jié)了使用其他窗口模式在數(shù)據(jù)流上挖掘融合高效用模式的算法。

Shie 等［56］提出了GUIDE 框架，從數(shù)據(jù)流中挖掘最大高效用模式，提出了基于衰減窗口的GUIDETF算法。該算法使用MUITF-Tree 維護(hù)效用信息，使用事務(wù)投影技術(shù)，并對(duì)事務(wù)進(jìn)行排序以更新樹結(jié)構(gòu)，是一階段算法。Manike 等［64］提出了使用時(shí)間衰減窗口在不確定數(shù)據(jù)流上挖掘高效用模式的算法，該算法使用樹結(jié)構(gòu)LHUI-Tree（Landmark window High Utility Itemset Tree）和SHUI-Tree（Sliding window High Utility Itemset Tree），該算法在時(shí)間和內(nèi)存消耗方法有較好的性能，但仍可進(jìn)一步提升。Kim 等［65］提出了基于樹的算法GENHUI（GENerate recent High Utility Itemsets）挖掘最近的高效用項(xiàng)集RHUIs（Recent High Utility Itemsets），通過時(shí)間衰減模型，根據(jù)事務(wù)的到達(dá)時(shí)間來逐漸減少事務(wù)的效用。此外，該算法定期更新樹結(jié)構(gòu)RHUI-Tree 中的效用信息，用DTWU（Decayed TWU）作為高估的效用值，減小搜索空間。Yun等［17］提出了在數(shù)據(jù)流中挖掘高平均效用項(xiàng)集的算法MPM（Mining significance utility Pattern information from streaM data）。該算法基于時(shí)間衰減窗口，提出了新的數(shù)據(jù)結(jié)構(gòu)DAT（Damped Average utility Tree）和TUL（Transaction Utility List）來存儲(chǔ)效用信息，為了減少搜索空間使用dub（damped average utility upper-bound）作為剪枝策略。Nam 等［66］提出了一種基于索引列表DUI list（Damped Utility Indexed list）的算法ILDHUP（Indexed List Damped High Utility Pattern mining），從時(shí)間敏感的數(shù)據(jù)流來挖掘最近高效用模式，使用索引值快速搜索效用信息。該算法只需掃描數(shù)據(jù)集一次，使用dub 作為模式的上邊界，該算法在連續(xù)存儲(chǔ)新數(shù)據(jù)的環(huán)境中考慮插入數(shù)據(jù)的到達(dá)時(shí)間來挖掘最近的高效用模式。

Yun 等［67］提出了SHAU（Sliding window based High Average Utility pattern mining）算法來挖掘數(shù)據(jù)流上最近出現(xiàn)的高平均效用模式，基于滑動(dòng)窗口模型，將流數(shù)據(jù)分為多個(gè)批次，并且僅將最近的批次保留在窗口中。該算法使用

SHAU-Tree（Sliding window based High Average Utility pattern Tree）存儲(chǔ)最近流數(shù)據(jù)中的效用信息，并提出RUG（Reducing average utility Upper bound in the Global）策略最小化平均效用上界，減少產(chǎn)生候選項(xiàng)的數(shù)目，但算法的內(nèi)存占用和運(yùn)行時(shí)間仍可進(jìn)一步減少。Lu 等［68］提出了基于滑動(dòng)窗口的top-k的HUI 挖掘算法TOPK-SW（Top-KHUIs mining based on Sliding Window）。將事務(wù)項(xiàng)集和有效信息存儲(chǔ)在樹結(jié)構(gòu)HUI-Tree（High Utility Itemsets Tree）中，確保有效檢索效用值而無需重新掃描數(shù)據(jù)集，且無需生成候選項(xiàng)集。Dawar等［69］提出了從數(shù)據(jù)流中挖掘top-k高效用模式的一階段的算法Vert_top-k_DS。該算法使用iList（inverted-List）作為數(shù)據(jù)結(jié)構(gòu)，iList 的構(gòu)建需要掃描數(shù)據(jù)集兩次，第二次數(shù)據(jù)集掃描需要按照TWU 遞增排序，該算法無需生成候選項(xiàng)集。Zihayat 等［70］提出了HUSP-Stream（High Utility Sequential Pattern Stream）算法挖掘高效用序列模式。該算法使用樹結(jié)構(gòu)HUSP-Tree（High Utility Sequential Pattern Tree）和效用列表ItemUtilLists（Item UtiityLists）來維護(hù)HUSP 的基本信息，使用TSWU（Transaction based Sequence-Weighted Utility）與SFU（Sequence-suFfix Utility）來剪枝搜索空間。Hackman等［71］提出了在數(shù)據(jù)流上挖掘短暫出現(xiàn)的高效用模式，定義了NHUI（Nearest High Utility Itemset），利用經(jīng)過驗(yàn)證的預(yù)測(cè)模型來評(píng)估即將出現(xiàn)的高效用模式，該功能具有捕獲和存儲(chǔ)潛在高效用項(xiàng)集信息的能力。Tang 等［72］提出了一種基于樹的數(shù)據(jù)流的高效用序列項(xiàng)集挖掘算法HUSP-UT（mining HUSPs based UT-tree）。該算法使用UT-tree 作為數(shù)據(jù)結(jié)構(gòu)，使用普通節(jié)點(diǎn)、尾節(jié)點(diǎn)以及尾指針表存儲(chǔ)事務(wù)的效用，能夠快速計(jì)算項(xiàng)中的效用和新的swu（Sequential Utility of the current Window of the data stream）值，減少了運(yùn)行時(shí)間。該樹結(jié)構(gòu)能夠保證算法不產(chǎn)生候選項(xiàng)集，有效減少了內(nèi)存的消耗。程浩東等［73］提出了在數(shù)據(jù)流上挖掘閉合高效用模式的算 法 CHUI_DS（sliding-window-model-based Closed High Utility Itemsets mining on Data Stream）。該算法使用效用列表結(jié)構(gòu)CH-List，快速地執(zhí)行批次的插入和刪除，利用滑動(dòng)窗口技術(shù)在有限的內(nèi)存資源下從連續(xù)數(shù)據(jù)中發(fā)現(xiàn)最新的無冗余項(xiàng)集。該算法不產(chǎn)生候選項(xiàng)集，此外，還提出了基于BRU_table（Batch based Remaining Utility Table）的公共批次事務(wù)重組方法和減少閉包計(jì)算的剪枝技術(shù)，減少搜索空間。Shie 等［56］提出了GUIDELM（Generation of maximal high Utility Itemsets from Data strEams）框架，從數(shù)據(jù)流中挖掘最大高效用模式，使用MUILM-Tree 維護(hù)效用信息，是一階段算法。Manike 等［74］在GUIDELM的基礎(chǔ)上提出了MGUIDELM算法。該算法使用MMUI-Tree，提出的算法比其他算法產(chǎn)生的候選項(xiàng)集少。Zihayat 等［18］提出了MAHUSP（Memory Adaptive High Utility Sequential Pattern mining over data streams）算法，采用內(nèi)存自適應(yīng)機(jī)制使用內(nèi)存，以便有效地發(fā)現(xiàn)數(shù)據(jù)流上的HUSP。該算法提出了一種緊湊的數(shù)據(jù)結(jié)構(gòu)MAS-Tree，并運(yùn)用界標(biāo)窗口技術(shù)在數(shù)據(jù)流上存儲(chǔ)潛在的HUSP；此外，該算法還提出了兩種有效的內(nèi)存自適應(yīng)機(jī)制LBMA（Leaf Based Memory Adaptation）和 SBMA（Sub-tree Based Memory Adaptation）來處理可用內(nèi)存不足以向MAS-Tree 添加新的潛在HUSP 的情況?；诖翱谀Ｊ降母咝в媚Ｊ酵诰蛩惴偨Y(jié)如表7 所示。

表7 基于窗口模式的HUPM算法Tab.7 HUPM algorithms based on window pattern

在MPM［17］中，數(shù)據(jù)結(jié)構(gòu)DAT 的時(shí)間復(fù)雜度由以下部分組成：令給定數(shù)據(jù)集中的事務(wù)數(shù)為T，事務(wù)的平均長度為L，構(gòu)造DAT 的時(shí)間復(fù)雜度為O(T×L)，更新節(jié)點(diǎn)的平均效用的時(shí)間復(fù)雜度為O(T×L)。在包含I項(xiàng)的頭表中提取項(xiàng)的條件模式基的時(shí)間復(fù)雜度為O(I×L)。然后構(gòu)造條件樹，在最壞的情況下是所有的項(xiàng)都滿足剪枝條件，保留條件樹中的項(xiàng)。使用RI表示具有I項(xiàng)的樹的遞歸模式增長操作的時(shí)間復(fù)雜度，RI為O(I×T+RI-1)，因此遞歸挖掘過程的總時(shí)間復(fù)雜度為。計(jì)算挖掘出的候選者數(shù)C的實(shí)際平均效用花費(fèi)的時(shí)間復(fù)雜度為O(C×T)。在最壞的情況下，構(gòu)建DAT總的時(shí)間復(fù)雜度。

MPM 的空間復(fù)雜度表示如下，主要的樹結(jié)構(gòu)DAT 由頭表和前綴樹組成，表包含兩個(gè)類型的數(shù)據(jù)，Item 與該項(xiàng)的dub；樹有多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)存儲(chǔ)了項(xiàng)標(biāo)簽、支持度和dub。設(shè)K為數(shù)據(jù)集中不同項(xiàng)的數(shù)量，在最壞的情況下，構(gòu)建DAT的空間成本為O(2×K+3×T×L)。若K為最大值，代價(jià)可表示為O(2×T×L+3×T×L)=O(5×T×L)。令C為DAT 生成的條件樹中的節(jié)點(diǎn)數(shù)，D為條件樹中不同項(xiàng)的數(shù)量，條件樹的空間成本表示為O(2×D+3×C)。令O(R)為生成的所有可能條件樹的空間成本，然后總空間復(fù)雜度表示為O(5×T×L+R)，其中最高階項(xiàng)為T×L。因此，最終結(jié)果變?yōu)镺(5×T×L)。

4 動(dòng)態(tài)刪除和動(dòng)態(tài)修改數(shù)據(jù)方面的高效用算法

除了增量數(shù)據(jù)和數(shù)據(jù)流上的高效用模式挖掘算法，仍然有動(dòng)態(tài)刪除和動(dòng)態(tài)修改數(shù)據(jù)方面的高效用模式挖掘算法。本章對(duì)該數(shù)據(jù)類型上的算法進(jìn)行了總結(jié)。

4.1 動(dòng)態(tài)刪除數(shù)據(jù)

目前已經(jīng)有不少算法在增量數(shù)據(jù)上挖掘高效用模式，但是，事務(wù)刪除在實(shí)際應(yīng)用中也是常見的。研究者已經(jīng)提出了在動(dòng)態(tài)刪除事務(wù)數(shù)據(jù)集中挖掘高效用模式的算法。

Lin 等［75］提出了在動(dòng)態(tài)刪除的事務(wù)數(shù)據(jù)集中挖掘高效用項(xiàng)集的算法FUP-HUI-DEL（Fast UPdated High Utility Itemsets for transaction DELetion），使用兩階段算法和FUP（Fast UPdated）概念減少了候選項(xiàng)集的數(shù)量和數(shù)據(jù)集掃描次數(shù)，使用TWU 和項(xiàng)集的真實(shí)效用來減少候選項(xiàng)集的數(shù)量。Lin等［76］提出了PRE-HUI-DEL（PRE-large High Utiltiy Itemsets for transaction DELetion）算法，使用事務(wù)刪除的預(yù)大概念挖掘高效用項(xiàng)集。該算法根據(jù)TWU 項(xiàng)集在原始數(shù)據(jù)集和已刪除的事務(wù)中是否具有較大（高）、預(yù)大型或較小的事務(wù)加權(quán)利用率，使用預(yù)大的概念將事務(wù)加權(quán)的利用率項(xiàng)集劃分為三組（有9 種情況）；然后將特定過程應(yīng)用于每種情況，以維護(hù)和更新發(fā)現(xiàn)的高效用項(xiàng)集；定義上邊界效用和下邊界效用得出高（大）事務(wù)和預(yù)大事務(wù)加權(quán)效用的有效閾值，減少了數(shù)據(jù)集掃描次數(shù)，只存儲(chǔ)了少數(shù)極有可能的項(xiàng)集，減少了內(nèi)存的使用。

以上兩種算法都為兩階段算法，且兩種算法都需要進(jìn)行大量計(jì)算，此外還需要多次掃描數(shù)據(jù)集確定項(xiàng)集的實(shí)際效用。Lin 等［77］提出了HUI-list-DEL 算法，使用效用列表結(jié)構(gòu)，并使用項(xiàng)集的效用與剩余效用之和與EUCP 剪枝搜索空間。該算法避免了多次數(shù)據(jù)集掃描并且重新使用效用列表結(jié)構(gòu)。Lin 等［78］提出了FUP-HAUIMD 挖掘高平均效用項(xiàng)集。該算法無需一直掃描數(shù)據(jù)集即可輕易找到更新的HAUIs，使用平均效用列表（AU-List）存儲(chǔ)必要的分支用于之后的挖掘操作保證正確性和挖掘信息的完整性。Yun 等［79］提出了HUIPRED 算法。該算法使用樹結(jié)構(gòu)HUIPREDL-tree 并且應(yīng)用了預(yù)大概念，能夠更有效地分析動(dòng)態(tài)數(shù)據(jù)集，提出的數(shù)據(jù)結(jié)構(gòu)和兩個(gè)閾值有效減少了數(shù)據(jù)集掃描的次數(shù)。

4.2 動(dòng)態(tài)修改數(shù)據(jù)

現(xiàn)實(shí)生活中事務(wù)修改也是常見操作，在將收集的數(shù)據(jù)輸入到數(shù)據(jù)集中時(shí)，可能會(huì)出現(xiàn)錯(cuò)誤，致使一些信息變得無效或者加入了新的信息［80］。因此有效地維護(hù)事務(wù)修改是一個(gè)關(guān)鍵問題，本節(jié)總結(jié)了事務(wù)修改的高效用模式挖掘算法。

Lin 等［80］提出了基于預(yù)大策略來維護(hù)和更新已發(fā)現(xiàn)的HUIM 以處理事務(wù)修改，當(dāng)事務(wù)修改時(shí)，該算法將發(fā)現(xiàn)的HTWUI（High Transaction Weight Utiltiy Itemsets）分為三個(gè)部分，設(shè)計(jì)了一個(gè)安全范圍來減少事務(wù)修改時(shí)數(shù)據(jù)集重新掃描的計(jì)算量。Lin 等［81］提出了PRE-HUI-MOD（PRE-large-based HUIs for ransaction MODification）算法。當(dāng)原始數(shù)據(jù)集進(jìn)行修改時(shí)，將發(fā)現(xiàn)的信息分為3 個(gè)部分9 種情況，同樣設(shè)置了安全范圍可以大大減少多次數(shù)據(jù)集掃描的計(jì)算量方法。使用生成和測(cè)試機(jī)制的兩階段算法逐級(jí)挖掘HUI，需要額外的內(nèi)存。Lin 等［82］提出了FUP-HUP-tree-MOD（Fast UPdated High Utility Pattern tree for transaction MODification）算 法，使 用HUP tree 結(jié)構(gòu)來保存效用信息，減少了數(shù)據(jù)集重新掃描的計(jì)算。當(dāng)原始數(shù)據(jù)集修改了事務(wù)時(shí)，算法將發(fā)現(xiàn)的高事務(wù)加權(quán)效用1 項(xiàng)集分為2 個(gè)部分4 種情況方便之后的處理。Lin等［83］提出了FUP-HUI-MOD 算法在事務(wù)修改的數(shù)據(jù)集上挖掘高效用模式，提出了FUP 概念，通過TWU 將1 項(xiàng)集分為兩個(gè)部分。

5 下一步的研究方向

通過對(duì)動(dòng)態(tài)數(shù)據(jù)上的高效用模式挖掘算法的描述及總結(jié)可以看出現(xiàn)有的方法仍然存在許多不足，可以從以下幾點(diǎn)進(jìn)行下一步的研究。

1）動(dòng)態(tài)利潤數(shù)據(jù)集［24］上的緊湊高效用模式挖掘算法。

商品的效用會(huì)隨著季節(jié)、政策等因素不斷變化，促使同一商品產(chǎn)生不同的利潤。目前大多數(shù)算法都以靜態(tài)商品效用為前提來挖掘高效用模式，這種假設(shè)并不成立，導(dǎo)致許多算法并不能應(yīng)用于實(shí)際生活中。此外，在高效用模式挖掘算法中挖掘出的模式往往很多，可對(duì)模式進(jìn)一步精簡(jiǎn)，挖掘緊湊高效用模式如最大高效用模式、閉合高效用模式以及topk的高效用模式。為了發(fā)現(xiàn)更有趣的模式，在動(dòng)態(tài)利潤數(shù)據(jù)上挖掘緊湊高效用模式有很大的現(xiàn)實(shí)意義，我們下一步的研究方向是使用列表結(jié)構(gòu)存儲(chǔ)效用信息，在動(dòng)態(tài)利潤數(shù)據(jù)集中挖掘緊湊高效用模式，進(jìn)一步提升算法的性能。

2）不確定數(shù)據(jù)流上的高效用模式挖掘算法。

在復(fù)雜的實(shí)際生活中，數(shù)據(jù)來源嘈雜、數(shù)據(jù)傳輸失敗或數(shù)據(jù)丟失會(huì)引發(fā)數(shù)據(jù)的不確定性［84］。目前，大多數(shù)高效用模式挖掘算法均基于精確的數(shù)據(jù)集，很難用于處理不確定數(shù)據(jù)集。并且，現(xiàn)存的兩階段的、基于樹結(jié)構(gòu)、列表結(jié)構(gòu)的不確定數(shù)據(jù)集上的高效用模式挖掘算法僅用于靜態(tài)數(shù)據(jù)，現(xiàn)實(shí)場(chǎng)景的數(shù)據(jù)往往到達(dá)速度快，數(shù)量大。因此，在不確定數(shù)據(jù)流上挖掘高效用模式具有一定的研究意義。

3）數(shù)據(jù)流上的定量高效用模式挖掘算法。

目前存在的大多數(shù)高效用模式挖掘算法僅挖掘出了高效用的項(xiàng)集，并未給出所挖掘項(xiàng)集關(guān)于數(shù)量的信息，項(xiàng)的數(shù)量信息有利于做出更準(zhǔn)確的營銷策略。現(xiàn)階段，定量高效用模式［85-86］挖掘的算法較少，且都應(yīng)用于靜態(tài)數(shù)據(jù)上，算法的運(yùn)行時(shí)間、內(nèi)存消耗等性能亦可進(jìn)一步提升。在數(shù)據(jù)流上挖掘定量高效用模式對(duì)現(xiàn)實(shí)生活場(chǎng)景具有重要作用，使用滑動(dòng)窗口并運(yùn)用數(shù)據(jù)庫投影技術(shù)的定量高效用模式挖掘、提高算法性能為一個(gè)可參考的方式。

4）分布式的高模糊效用模式挖掘算法［87］。

HUIM 通過涉及模式表示的數(shù)量來顯示關(guān)鍵信息，不能提出諸如“大量購買尿布的人意味著少數(shù)人購買啤酒”之類的關(guān)系，此外，其基于預(yù)定義的最小效用閾值的二元模型來確定項(xiàng)集，不適用于當(dāng)前的大數(shù)據(jù)環(huán)境的現(xiàn)實(shí)場(chǎng)景。為了解決以上限制，可以使用模糊集理論和Spark 及MapReduce，來挖掘更靈活、有效且數(shù)量龐大的知識(shí)；還可以考慮將分布式框架與深度學(xué)習(xí)架構(gòu)結(jié)合處理更復(fù)雜的模式如模糊高效用模式挖掘。

6 結(jié)語

本文總結(jié)了動(dòng)態(tài)數(shù)據(jù)上的高效用模式挖掘算法，包括在增量數(shù)據(jù)、數(shù)據(jù)流、動(dòng)態(tài)刪除和動(dòng)態(tài)修改數(shù)據(jù)上挖掘高效用模式的算法。本文從數(shù)據(jù)結(jié)構(gòu)、剪枝策略、優(yōu)缺點(diǎn)等角度對(duì)增量數(shù)據(jù)上的算法進(jìn)行了分析，并通過算法實(shí)驗(yàn)數(shù)據(jù)與復(fù)雜度對(duì)算法的性能進(jìn)行了進(jìn)一步的分析，還從算法使用的窗口模型介紹了數(shù)據(jù)流上的高效用模式挖掘算法，且對(duì)不同窗口的算法的性能進(jìn)行了對(duì)比。此外，還介紹了動(dòng)態(tài)刪除和動(dòng)態(tài)修改數(shù)據(jù)的高效用模式挖掘算法。除了介紹了高效用模式算法，還介紹了高平均效用模式、高效用序列模式，top-k高效用模式等挖掘算法。

動(dòng)態(tài)數(shù)據(jù)上的高效用模式挖掘更適用于現(xiàn)實(shí)場(chǎng)景，但仍有不足，提出了動(dòng)態(tài)利潤數(shù)據(jù)集上的緊湊高效用模式挖掘算法、不確定數(shù)據(jù)流上的高效用模式挖掘算法、數(shù)據(jù)流上的定量高效用模式挖掘算法以及分布式的高模糊效用模式挖掘算法作為進(jìn)一步的研究方向。