單芝慧，韓 萌，韓 強

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

0 引言

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

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

圖1 常見高效用模式的應用Fig.1 Common applications of high utility pattern

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

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

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

2）從樹結構、列表結構和其他結構對高效用模式進行了分類總結，明確了不同結構上算法的特點。

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

1 概念與定義

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

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

定義1內部效用［23］。在事務T中項i的內部效用定義為in(i，T)。

例如：在表1 中，T2中項a的內部效用為in(a，T2)=1。

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

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

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

表2 效用表Tab.2 Utility table

定義3項的效用［23］。事務T中項i的效用定義為：

例如：在表1 中，事務T2中項a的效用為：

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

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

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

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

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

定義7事務效用［23］。事務Tq的事務效用定義為：

定義8事務加權效用［23］。項集X的事務加權效用定義為twu(X)，是項集X包含的所有事務的效用之和：

定義9高事務加權效用項集［23］。對于項集X，如果twu(X) ≥mintuil，則X是高事務加權效用項集。

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

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

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

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

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

在序列S的事件e中，項i的效用是utility(i，e，S)，是其內部效用和外部效用的乘積utility(i，e，S)=intU(i，e，S)×extU(i)。序列S中的模式P的效用為utility(P，S)，可以通過對該序列中出現(xiàn)的所有模式項的效用求和得出。n個序列的序列數(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。

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

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

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

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

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

2.1 基于樹結構

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

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

為了進一步優(yōu)化數(shù)據(jù)結構，Zheng 等［14］提出了iCHUM（incremental Compressed High Utility Mining）算法。該算法利用項的TWU 來構造樹結構iCHUM-Tree，將新增的數(shù)據(jù)附加到原始數(shù)據(jù)集后，iCHUM 算法將更新iCHUM-Tree，無需完全重建樹結構。高效用項集的信息保留在iCHUM 樹中，在頭表中按照TWU 降序排序，自底向上有序遍歷分支，提高挖掘效率。該算法使用模式增長方法挖掘，遞歸挖掘的復雜度由iCHUM-Tree 的高度和節(jié)點數(shù)確定。Yun 等［27］基于樹結構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 挖掘方法減少高估的效用，以此來減少搜索空間和候選項集的數(shù)量。

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

圖2 基于樹結構的HUPM算法Fig.2 Tree structure-based HUPM algorithms

2.2 基于列表結構

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

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

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

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

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

2.3 其他數(shù)據(jù)結構

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

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

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

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

2.4 算法性能評估

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

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

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

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

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

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

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

3.1 滑動窗口模式的高效用算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 下一步的研究方向

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

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

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

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

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

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

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

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

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

6 結語

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

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