高效用模式產生策略綜述

高 曼，韓 萌，雷冰冰

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

1 引言

傳統的模式挖掘主要考慮頻率，假定每個項集出現在一個事務中的頻次是一次，且具有同等的重要性，在很多實際生活中不具有使用性。如：商店銷售中，面包與鉆石被認為同等重要，這樣就會出現利潤高的項集沒有被挖掘。因此基于上述問題提出高效用模式挖掘，高效用模式挖掘把鉆石銷售的利潤很好地體現出來。

高效用模式挖掘是數據挖掘領域的一個重要研究內容，由于其計算過程包含對模式的內、外效用值的處理，計算復雜度較大，因此高效用模式挖掘算法的主要研究熱點問題就是提高算法的時空效率。

在高效用項集挖掘的初期，基于先驗方法[1]，設計了兩階段算法[2]，從具有高效用信息的數據庫中尋找高效用項集。針對傳統頻繁項集挖掘中的向下閉包屬性在高效用項集挖掘中不存在的問題，提出了事務加權效用（Transaction Weighted Utilization，TWU），利用TWU以減少挖掘高效用項集的搜索空間。雖然兩階段算法可以通過TWU 向下閉包屬性減少搜索空間，但是這種算法由于生成和測試方法導致執行時間和內存使用過多，生成和計算候選對象和實際效用需要大量的數據庫掃描。為此，提出了基于樹的算法來克服兩階段算法的不足，如生成最近的高效用程序項集（GENerate recent High Utility Itemsets-Mine，GENHUI）[3]、增量數據庫中挖掘高平均效用項集（Incremental Mining of High Average-Utility Itemsets，IMHAUI）[4]、壓縮高效用項集挖掘（Compact High Utility Itemset-Mine，CHUI-Mine）[5]。因為產生候選項集會隨著數據規模增大導致算法效率降低，所以進一步提出不產生候選項集的算法，如基于滑動窗口模型的數據流加權最大頻繁模式挖掘（Weighted Maximal Frequent Pattern Mining over data streams based on Sliding Window model，WMFP-SW）[6]、基于模式增長方式的高效用模式挖掘算法（High Utility Pattern Mining based on Frequent Pattern growth，HUPM-FP）[7]、HUITWU（High-Utility Itemset Mining in Transaction Databases）[8]、用于事務修改的快速更新的高效用模式樹（Fast Updated High Utility Pattern tree for transaction MODification，FUP-HUP-tree-MOD）[9]。

為了進一步提高算法的效率，將數據庫進行投影以減少訪問空間，如有效的高效用項集挖掘（EFficient high-utility Itemset Mining，EFIM）[10]、挖掘Top-k高效用項集的有效算法（efficient algorithm for mining Top-kHigh utility itemsets，TKEH）[11]、基于選擇數據庫投影挖掘高效用項集（Selective database Projection-based HUI Mining，SPHUI-Miner）[12]，還利用一些剪枝策略將不滿足性質的子樹進行剪枝，如算法EFIM、TKEH，利用兩個上界子樹效用性質來減少訪問的空間，提高算法的時間與空間效率。

本文的主要貢獻：

（1）從算法使用數據結構的角度分析兩階段算法和一階段算法。

（2）分析基于樹結構的高效用算法在計算過程是否產生候選項集。

（3）分析高效用模式算法用到的縮減搜索空間的策略。

2 一階段與兩階段算法

最早的兩階段高效用算法是基于Apriori 將TWU這一概念應用于挖掘過程的算法。在第一階段中生成候選對象的高估效用值應當不小于給定的閾值，然后再進行數據庫掃描，計算它們的效用值，從而甄別出實際的高效用模式。因為兩階段算法產生大量的候選項集且掃描數據庫多次，所以提出基于樹的算法。本文主要介紹基于樹的兩階段算法。基于樹的算法減少了候選集產生的數量，也減少了數據庫掃描次數，但是生成候選的數量還是比較大，進而提出了基于列表的一階段算法來改善算法的時空效率。以下對基于樹的兩階段算法和基于列表的一階段算法進行比較分析。

2.1 基于樹的兩階段算法

基于樹的算法主要是根據數據庫建立樹結構，然后根據樹結構得到高效用項集。兩階段算法首先產生候選項集，然后測試候選項集是否是真正的高效用項集。

為了解決基于Apriori 所帶來的生成大量候選項集及數據庫掃描次數較多的問題，提出了一種基于模式增長的算法UPTP[13]。該算法分為三個步驟：（1）掃描數據庫兩次，并構造全局效用模式樹，降低節點的估計效用并對數據庫中的事務進行調整；（2）采用效用模式增長算法，從全局效用模式樹中，構造條件模式樹，并根據前一個步驟記錄的極小節點效用，降低路徑效用，然后從條件效用模式樹中遞歸地生成候選高效用項集；（3）從候選高效用項集中確定高效用項集，不需要掃描原始的數據庫，高效地生成高效用項集。其中，前兩個步驟為第一階段，第三個步驟為第二階段。UP-Growth（Utility Pattern Growth）[14]算法高效用項集的信息在一個效用模式樹（Utility Pattern Tree，UP-Tree）中，在基于樹的數據結構中進行維護，算法只需對數據庫進行兩次掃描就可以高效地生成候選項集。

上述算法挖掘的是全部的高效用項集，因為在生活中不需要進行完全挖掘，只需要找出用戶所需要的個數即可，所以提出Top-k策略來實現。此類算法的主要特點是用戶需要幾個項集就設置k的值為多少。第一個基于Top-k算法的挖掘HUIs 是TKU（Top-kUtility itemset）[15]，是UP-Growth[14]的延伸算法。TKU遵循兩階段模型，并繼承了兩階段的有用特性。在第一個階段，生成潛在的Top-k高效用項集（Potential Top-kHigh Utility Patterns，PKHUIs），算法使用 PE（Pre-Evaluation）、MD（MIU of Descendants）、NU（Node Utilities）和 MC（MUIof Candidate）四種策略來提高內部最小效用閾值，并修剪搜索空間。在第二階段，從第一階段發現的PKHUIs集合中識別出Top-kHUIs。TKU 使用第五個策略SE（Sorting candidates and raising threshold by Exact utility of candidates）對候選項集進行排序，并提高內部閾值，TKU不僅要花費大量時間來查找Top-k高效用項集，而且它的一些提高閾值的策略也需要大量的內存。為了提高TKU 的性能，Ryang 和Yun 提出了一種名為REPT（Raising threshold with Exact and Pre-calculated utilities for Top-khigh utility pattern mining）[16]的算法。REPT 依賴于UP-Tree 結構，通過應用PUD（Preevaluation with Utility Descending order）、RIU（Real Item Utilities）來快速提高邊界最小效用，從而提升TKU的性能。REPT通過各種策略（預效用降序、真實項集效用等）來縮小搜索空間，進而產生候選集，再通過支持降序等策略篩選高效用項集，因為REPT所提出的剪枝策略更加有效減少了搜索空間，所以算法性能比TKU好。

基于樹的結構不僅適用于靜態數據，還適用于動態數據，Ahmed 等人提出了類似于UP-Tree 的HUPMS（High Utility Pattern Mining over Stream Data）[17]來挖掘數據庫為流數據的高效用模式。基于樹狀數據結構的滑動窗口模型，通過三個步驟從流數據中發現高效用模式。在第一步中，算法將事務插入到全局的HUSTree（High Utility Stream Tree）中，并計算它們的效用。在此階段，每個插入的事務中項的節點效用按事務的效用添加。換句話說，HUS-Tree 中的節點使用了高估效用。在構建全局樹之后，在第二步中，HUPMS通過使用模式增長的方法生成候選模式，其TWU 值不小于用戶指定的最小效用閾值。在最后一步中，算法通過附加掃描計算候選對象的真實效用，生成高效用模式。對于基于滑動窗口模型的數據流，節點效用以逐批方式存儲。雖然HUPMS解決了以前基于Apriori算法的問題，但是由于高估了效用，它仍然產生了大量的候選對象。因此提出SHU-Growth（Sliding window based High Utility Growth）[18]算法，通過減少生成的候選模式的數量來改進基于滑動窗口的高效用模式挖掘性能。算法通過引入減少全局估計效用（Reducing Global Estimated utilities，RGE）和減少局部估計效用（Reducing Local Estimated utilities，RLE）來減少過高估效用，從而減少搜索空間與候選模式。此算法總共包含三步：在第一步中，通過對數據流中當前窗口的單次掃描來構造全局樹。在這個階段，應用RGE 技術來減少頭表中的高估效用和樹中節點的高估效用。第二步，從構建的樹中生成候選模式。當局部樹直接從全局樹中進行計算時，使用RLE技術來減少高估效用。在最后一步中，算法從候選對象中識別出一組高效用模式。與此同時，只要窗口已滿且有新批到達，就可以通過刪除最舊的批并反映新到達數據批來更新全局樹。

現有的大部分高效用項集挖掘（High Utility Itemsets Mining，HUIM）算法都沒有考慮事務的添加和刪除。當數據庫更新時，它們需要掃描整個數據庫來重建數據結構。針對這一問題，提出了一種高效的樹結構IHUP-Tree（Incremental High Utility Pattern Tree）[19]。構建初始的樹，當新數據到達時需要將新到達的數據存儲在樹中，根據構建的樹來挖掘模式，若數據獲取已達到峰值且同時要刪除舊數據，因為挖掘的是最近數據中的模式，所以之前的數據可以刪除，這樣既保證了內存中可以存儲構建的樹，又保證了有效挖掘模式，構建的IHUP-Tree 可以有效挖掘增量數據庫的模式，當事務被添加到數據庫或從數據庫中刪除時，通過調整IHUPTree來有效挖掘。基于IHUP-Tree可以高效地實現增量HUIM。IHUP-Tree也可以應用在交互式HUIM中。基于IHUP-Tree 的算法分兩個階段發現高效用項集（High Utility Itemsets，HUIs）。在階段一中，采用了一種高估的技術來設置數據庫中項目集的效用上限。被高估的效用不小于用戶指定的最小效用閾值的項集被選為候選項。在第二階段，候選項集通過再次掃描數據庫進行驗證。但是基于IHUP-Tree 的算法產生的候選對象太多，驗證起來比較耗時。GENHUI[3]算法通過時間衰減模型來挖掘流數據上最近的高效用項目集，在此基礎上設計了一種新的基于樹的數據結構。該算法定期更新其樹，將最近的效用信息反映到樹中，無論何時執行更新過程，算法都會從樹中刪除過時的節點，只保留對挖掘結果有很大影響的信息。因此，當流數據在樹狀數據結構中不斷累積時，該算法可以保持合理的內存使用界限。同時，該算法利用DTWU（Decayed Transaction Weighted Utilization）作為被高估的效用值，減少了搜索空間，從而有效地挖掘出一組潛在的HUIs。IMHAUI[4]算法使用模式增長方法，允許算法生成一組必要的候選項集。為了使算法在整個增量挖掘過程中始終保持樹結構的緊湊性，采用了一種重構技術。

上述動態算法都需要設置最小閾值，因為新的數據到達時效用可能會產生變化，所以設置固定的閾值不是很合理，若閾值設置太低，則會產生大量結果使得用戶難以選擇，若設置太高，則會使得產生結果太少，沒有真正想要的結果。因此提出在算法運行過程中動態地設置最小閾值，使得閾值設置更具有合理性。在動態算法運行過程中選取哪一個參數作為最小閾值是一個難點，因此提出多種策略提高最小閾值。為了解決閾值難以設置的問題，Zihayat 等人提出了一種基于數據流挖掘HUIs的算法T-HUDS（Top-kHigh Utility itemset mining over Data Stream）[20]，它解決了需要用戶設置閾值的困難，將第k個項集的效用作為最小效用閾值，動態地更新最小效用閾值，使得最小效用閾值更加合理，進一步提高算法的效率。T-HUDS 提出了一種新的高估效用模型 PrefixUtil（Prefifix Utility of itemset）來減少候選項集的生成，因為PrefixUti 比TWU 更接近真實效用。此算法采用類似于FP-Tree 的壓縮結構，稱作HUDSTree（High Utility Data Stream Tree）結構，且使用max-UtilList（Maximum Utility List）和 MIUList（Minimum Itemset Utility List）兩個輔助列表。列表用于存儲計算前綴和初始化且動態調整閾值所需的信息，使用最小Top-k效用在第二階段用于設置閾值。

根據對上述兩階段算法的分析，可以得出兩階段算法的缺點是需要產生候選項集，然后對候選項集進行測試，從候選項集中選取出真正的高效用項集，此外，算法對于原始數據庫需要進行多次掃描。為了減少候選項集的產生并減少數據庫掃描次數提出一階段算法，因為一階段算法不需要進行測試，所以同等條件下數據庫掃描次數少于兩階段算法。

2.2 基于列表的一階段算法

基于列表的一階段算法很多，按照產生的結果集進行分類可分為完全和壓縮，壓縮包括Top-k、閉合高效用等。

基于列表的完全高效用算法特點就是只要是高效用項集就會挖掘出，最早是由Liu等人提出的HUI-Miner[21]（High Utility Itemset Miner）。算法挖掘的是全部的高效用項集，不丟失任何一個高效用項集。HUI-Miner使用效用列表來存儲項集的效用信息，用于修剪HUIMiner搜索空間的啟發式信息。通過避免大量候選項集的生成和效用計算的開銷，HUI-Miner可以有效地從構造的效用列表中挖掘高效用項集。因為HUI-Miner 算法的連接操作降低了該算法的性能，所以提出HUPMiner（High Utility Pattern Miner）[22]算法和 FHM（Fast High-Utility Miner）[23]算法改進HUI-Miner算法。HUPMiner 算法使用了一種新的數據結構，稱為分區效用列表（Partitioned Utility List，PUL），它在分區級別維護效用信息。算法使用的修剪策略（LA-prune）主要旨在限制在PUL 構建過程中生成的事務標識符列表的總數。算法同時使用PU-prune 來減少搜索空間，提高算法效率。相比較HUI-Miner算法，FHM算法通過共現剪枝策略來減少連接操作。為了進一步減少連接操作，提出了IMHUP（Indexed list-based Mining of High Utility Patterns）算法。該算法使用索引效用列表（Indexed Utility list，IU-list）減少比較和鏈接操作，且不產生候選項集。IMHUP 算法掃描兩遍數據庫，第一遍計算TWU，根據TWU值對數據庫進行修改，刪除沒有希望的項，對數據庫中的項按升序排序，第二遍掃描修改后的數據庫，建立全局IU-list。其中，列表按TWU升序排序，相同事務的列表中的條目通過索引信息鏈接。按照TWU 順序，并與當前所選列表的后續列表進行連接操作，以創建二項集的局部IU-list，根據二項集創建三項集局部IU-list，類似地進行創建更長項集的操作。通過使用RUI（Reducing Upper-bound utilities in IU-lists）減少數據結構中的上界效用來減少搜索空間。為了進一步提高算法的效率，Deng 提出了一種新的數據結構PUN-list（PU-tree-Node list）[24]，該結構既保留了項目集的效用信息，又保留了項目集的效用上限，便于挖掘高效用項集。MIP（Mining high utility Itemset using PUN-lists）的效率主要通過三種技術來實現。首先，項目集由一個高度壓縮的數據結構表示，稱為PUN-list，這避免了昂貴重復的效用計算。其次，通過掃描項目集的PUN-list，可以有效地計算項目集的效用，利用短項目集的PUN-list 可以有效地構造長項目集的PUN-list。第三，通過使用位于PUN-list 中的效用上界作為剪枝策略，MIP直接從搜索空間中發現高效用項集，而不生成大量候選項。相比較其他的算法，如HUI-Miner，需要將效用列表中部分信息再次計算才可以獲得效用上界，這使得MIP運行時間較優。

Top-k高效用算法是為了解決最小閾值難以設置的問題而提出的，除了Top-k，其他算法都需要用戶自行設置最小閾值，該類算法的主要特點就是不需要用戶設置最小閾值，主要難點是如何在算法運行過程中提高最小閾值，最小閾值的初始值為0。現有的很多算法是基于模式增長，算法需要產生候選，為了提高算法效率提出 TKUL-Miner（Top-kUtility List Miner）[25]，它是一種高效挖掘Top-k高效用項集的新算法。它利用一種新的效用列表結構，在搜索樹的每個節點上存儲必要的信息，以便挖掘項集。該算法利用特定區域的搜索順序快速提高邊界最小效用閾值。此外，還提出了另外兩種計算較小的高估效用策略，以有效地修剪沒有希望的項集。該算法采用多種策略，快速提高最小效用，有效地縮減了搜索空間。kMHC（Top-kHigh utility itemset Mining using Co-occurrence pruning）[26]是 Duong 等人提出的一種基于效用列表結構的一階段算法，是FHM算法的擴展。kHMC 使用RIU、CUD、COV（Coverage）來提高算法的最小效用閾值，它使用EUCPT（Estimated Utility Co-occurrence Pruning Strategy with Threshold）和傳遞擴展剪枝策略（Transitive Extension Pruning，TEP）。EUCPT 可以避免在FHM 中計算項目集效用的連接操作。kHMC 提出了一種新的剪枝策略TEP，TEP策略通過對項目集效用使用新的上限來減少搜索空間。Dawar等人[27]提出了一種從數據流中挖掘Top-k高效用項集的數據結構和算法。該算法是一個單一的階段，不產生任何候選，不像許多算法工作在兩個階段，然后生成候選驗證。KOSHU（Top-kOn-Shelf High Utility itemset miner）[28]是一種高效開采貨架上的高效用項集的工具，它對商品上架時間、單位利潤正負值進行考慮。KOSHU 引入了三種新的策略，即有效估計共現最大周期率剪枝、周期效用剪枝和一對二項集剪枝的并發剪枝，以減少搜索空間。KOSHU 是FOSHU[29]算法的Top-k版本。

閉合高效用算法的提出主要是解決結果集過大，使得用戶無法快速準確地找到想要結果的問題。該類方法最大的特點就是沒有丟失必要的信息。因為兩階段CHUD（Closed High Utility Itemset Discovery）產生大量的候選項集，所以提出一階段算法CHUI-Miner[5]，其不需要產生候選項集，直接生成閉合高效用項集。CHUI-Miner提出EU-list（Extended Utility list）結構，且提出效用單位數組，使用TWU 和保留效用上界來減少搜索空間，提高算法效率。盡管CHUI-Miner 提高了算法效率，但是算法需要多次掃描數據集，降低了算法的效率，因此提出了EFIM-closed[30]，在一定程度上提高了算法效率。EFIM-closed 是基于投影和合并技術，采用基于深度優先的方法挖掘閉合高效用項集。算法提出兩種不同的剪枝策略，分別是LU 和SU，減少搜索空間與運行時間。第一次提出投影與合并技術的算法是EFIM。投影與合并技術是一種非常有效的減少數據的掃描與存儲的技術，此技術大大降低了算法的時間復雜度與空間復雜度。CHUI-Mine[5]用來發現閉合的HUIs和最大的HUIs，它們是HUIs 的緊湊表示。CHUI-Mine的主要優點在于兩方面：首先，在效率方面，不像現有算法在挖掘過程中往往產生大量的候選項，CHUI-Mine直接計算項目集的效用，而不生成候選項。其次，在無損方面，與現有算法提供不完整的結果不同，CHUI-Mine可以在沒有遺漏的情況下發現完全閉合的或最大的HUIs。將CLS-Miner[31]更有效地引入到CHUIs 中。與CHUD 不同，它是一個依賴于效用列表結構來發現CHUIs 的單階段算法。從這個角度來看，CLS-Miner 類似于CHUI-Miner，但是有一些關鍵的區別：首先，CLSMiner 與CHUI-Miner 使用不同的搜索空間剪枝策略。一個重要的特性是，CLS-Miner的策略可以在搜索空間中完全構造效用列表之前刪除項集，從而大大降低了挖掘CHUIs的成本。其次，CLS-Miner引入了一個高效的預檢查方法，快速確定一個項集是否是另一個項集的子集。使用這種方法優化閉包計算和包含檢查的操作，這些操作通常由閉合模式挖掘算法執行。但是需要注意的是，這兩個操作在閉合模式挖掘算法中重復執行，因此這種預檢查方法大大縮短了發現CHUIs 的時間。EFIM-closed 在密集數據集上有很多限制，由于這個算法需要多次掃描數據庫，為了解決在稀疏與密集數據集上運行時間與內存上的有效性，提出了Hminer-closed[32]算法，使用修改的緊湊效用列表存儲結構（Modified Compact Utility List，MCUL），只需要掃描一次數據庫，在處理候選項時，根據CHUIs 對候選項進行向后檢查，從而減少搜索空間，節省重建后向集合進行匹配的時間。在下一步中結合前向檢查和構建候選項，以減少運行時間，合并類似的事務，以減少存儲空間，修剪MCUL 后，立即更新 LA-prune 和 C-prune 的值，使得剪枝策略更有效。

平均高效用項集挖掘通過考慮項目集的長度（項目的數量）來更公平地度量項目集的效用。現有的很多方法可分為水平增長方法和模式增長方法。但是這兩種方法都需要大量的計算才能找到實際的高平均效用項目集，因此提出基于列表的方法。FHAUI（Fast High Average Utility Itemset）[33]算法將效用信息保存到效用列表中，通過效用列表的連接挖掘出所有的具有高平均效用值的項集，同時FHAUI 算法還采用二維矩陣來有效減少二項效用值的連接比較次數。該算法屬于一階段算法，可以在不產生候選項集的情況下挖掘出所有的高平均效用項集，并且只需要掃描兩次數據庫。同時，給出改進效用列表結構IAU-list 和平均效用，采用二維矩陣來有效地減少效用列表之間比較連接的次數。Lin 等人[34]提出了一種平均效用（Average Utility，AU）列表結構來更有效地發現HAUIs（High Average-Utility Itemsets），提出了基于深度優先搜索算法HAUIMiner（High Average-Utility Itemset Miner），在不生成候選對象的情況下搜索空間，并提出了有效的剪枝策略來減少搜索空間，加快挖掘速度。目前很多平均高效用算法使用單一的高平均效用最小閾值，這限制了它們分析真實數據的有效性。因為不同的項目對用戶來說并不同等重要。為解決這一問題，HAUIM-MMAU（High Average-Utility Itemset Mining with Multiple Minimum Average-Utility Thresholds）[35]算法提出多個最小效用閾值，使用產生和測試的方法挖掘HAUI，降低了算法效率。MEMU[36]提出了一種新穎的MAU-list 結構和一種排序枚舉樹（Sort Enumerate Tree，SE-Tree），在減少搜索空間的同時挖掘HAUIs。此外，還設計了一個更緊密的上限模型RTUB（Revised Tighter Upper-Bound）來修剪沒有前途的項目集。模型RTUB 與傳統AUUB（Average-Utility Upper Bound）模型相比較值更小。提出了三種基于RTUB 模型的剪枝策略，以減少搜索空間，更有效地挖掘HAUIs。

基于樹的方法，主要是通過效用上界來減少候選項集。基于列表的方法，通過效用上界和剪枝策略來減少搜索空間。基于列表的方法的缺點主要是算法過程中構建效用列表花費大量的代價且算法連接操作代價較大，主要優點是不需要對原始數據庫進行多次掃描，且通過降低效用上界提高算法的效率。與兩階段算法相比較，一階段算法可以直接挖掘高效用項集，不需要產生候選項集，也不需要掃描一遍原始數據庫來測試候選項集，通過混合搜索機制有效地挖掘高效用項集，通過多種機制有效地存儲效用信息，從而提高算法的效率。一階段算法首先通過減少數據庫的掃描來提高算法效率，因為掃描多次數據庫需要花費大量的時間，將數據庫的信息存儲在列表中從而不需要多次掃描數據庫；然后通過減少列表的連接操作來提高算法的效率，由于構建新的列表花費較大，通過構建更緊湊的效用列表來減少搜索空間，因為更緊湊的列表可以減少算法運行過程中的搜索，再通過更小的效用上界來減少搜索空間，從而提高一階段算法的效率。

上述主要從一階段、兩階段算法使用的數據結構角度進行分析，此外從算法使用的搜索方式進行劃分，還可以劃分為水平方式和深度優先。使用水平方式的兩階段算法最有代表性的就是Two-Phase[2]，使用深度優先搜索方式兩階段算法很多，如TKU、REPT等，一階段算法都使用深度優先的方式進行搜索。與水平方式算法相比，深度優先算法性能更好。因為水平方式算法產生大量候選項集，且需要測試，需要多次掃描數據庫，而深度優先的方式主要是構建數據結構來減少數據庫的掃描次數，使得算法的效率得到有效的提升。

一階段、兩階段算法的分析結果如表1所示。

表1 階段算法

3 有無候選集

現如今，數據的數量與種類越來越多，由于目前的存儲技術不能滿足大量增長的數據全部保存的需求，多數的數據不能直接存儲，因此需要通過挖掘動態數據得到有趣的模式。以下主要對基于樹結構是否產生候選項集算法進行分析。

3.1 產生候選項集

靜態數據產生候選項集的算法有TKU[15]、REPT[16]。TKU 算法使用UP-Tree 來維護高效用項目集的信息，UP-Tree 是在兩次數據庫掃描中構造的。UP-Tree 數據結構中計算事務加權效用，以提高查找高效用項目集的效率，UP-Tree 使用各種策略從事務數據庫中刪除不相關的信息。REPT 算法也是基于UP-Tree 的兩階段算法，產生大量的候選項集，且需要測試候選項集是否為高效用項集，該過程需要大量的時間。為了節約時間，提出了一種策略提高最小閾值，更有效準確和預先計算效用，在第二階段確定實際的Top-k高效用模式。此外，有效提高閾值大大減少了搜索空間和生成的候選模式的數量，這使得此算法能夠更快、更有效地挖掘Top-k高效用模式。

上述算法是基于靜態數據庫的兩階段模型算法。為了使算法更好運用于動態數據庫，提出了基于樹結構的增量算法，名為IHUP[19]。該算法提高了生成候選項集的效率及減少了數據庫掃描的次數，使用樹結構來記錄項的效用信息。但是，IHUP 算法在第一階段同樣會產生大量的候選項集，嚴重影響了第二階段的效用。雖然提出了增量式高效用模式（IHUP）挖掘算法，但其樹結構IHUP-Tree 是冗余的，因此IHUP 算法的效率相對較低。為了解決這個問題，提出了一種增量壓縮的高效用挖掘算法（incremental Compressed High Utility Mining，iCHUM）[37]。iCHUM 算法利用 TWU 構造樹結構，即iCHUM-Tree。當新數據庫添加到原始數據庫時，iCHUM算法將更新iCHUM-Tree。高效用項集的信息保存在iCHUM-Tree 中，從而可以通過挖掘過程生成候選項集。為了提高算法性能，提出了基于時間衰減模型的增量算法GENHUI[3]。GENHUI 算法通過構建RHUI-Tree（Recent High Utility Itemsets Tree）與更新RHUI-Tree來挖掘高效用項集。RHUI-Tree由兩部分組成，一部分是header table，另一部分是樹。RHUI-Tree頭表結構由兩部分組成，一部分是項，另一部分是DTWU。算法將數據通過處理計算DTWU，再通過樹的構建以及約束DTWU 來尋找高效用項集，GENHUI 需要產生候選。為了更有效地挖掘高效用項集，提出平均高效用項集。IMHAUI[4]算法采用了模式增長方法，允許算法生成必要的候選項集。采用的樹結構是IHAUITree（Incremental High Average Utility Itemset Tree）。IHAUI-Tree 是由兩部分組成，這兩部分與RHUI-Tree[3]頭表的組成類似，但是表中的內容不一樣，只是IHAUITree[4]用到的是AUUB而不是DTWU。

Ahmed 等人提出HUPMS[17]算法，使用模式增長方法挖掘當前窗口中的所有高效用模式。此外，HUS-Tree對于交互式挖掘是非常有效的。該算法對于數據流上的增量式和交互式HUP 挖掘非常有效，并且顯著優于很多的基于滑動窗口的HUP 挖掘算法。雖然HUPMS解決了以前基于Apriori 算法的問題，但是由于高估了效用，它仍然產生了大量的候選對象。因此提出SHUGrowth[18]，在構建全局 SHU-Tree（Sliding window based High Utility Tree）時使用RGE 技術減少頭表和節點的高估效用，從而減少搜索空間和候選項集的數量。用項的高估效用大于最小窗口效用來判斷項是否可以作為候選模式，若可以作為候選模式，則創建項的條件模式基，進一步確定候選模式。

慕歡歡等人提出一個數據流高效用項集挖掘算HUIDE[38]。算法首先綜合考慮數據的信息特征，提出一種有效的效用度量方法，然后采用基于時間的滑動窗口技術更加準確地描述數據分布，構建一種高效用項集樹（HUI-Tree）。最后遍歷構建的樹HUI-Tree挖掘高效用項集，減少了候選項集的產生及時間和空間的消耗。Yun等人提出了一種稱為HUPID-Growth[39]（High Utility Patterns in Incremental Databases Growth）的算法來挖掘增量數據庫中的高效用模式。此外，為了提高增量數據庫的處理效率，提出了一種基于單次數據庫掃描的HUPID-Tree（High Utility Patterns in Incremental Databases Tree）結構和一種新TIList（Tail-node Information List）數據結構。

3.2 不產生候選項集

一階段算法并不都是不產生候選的算法，不產生候選的算法指的是沒有候選項集的產生直接挖掘的是高效用項集，一階段算法可能產生候選。

Lee等人提出了一種基于滑動窗口模型的數據流加權最大頻繁模式（WMFPs）[6]挖掘算法，并給出了查找WMFPs 所需的數據結構，即滑動窗口最大頻繁模式樹和滑動窗口最大頻繁數組。滑動窗口最大頻繁模式樹反映窗口更新和重構，滑動窗口最大頻繁數組減少樹掃描、挖掘單路徑策略等，有效地反映數據流上最新信息的WMFP。

D2HUP[40]可以在不生成候選模式的情況下找到高效用模式，新穎之處在于使用高效用模式增長方法、前瞻性策略和線性數據結構。具體來說，通過模式增長方法去搜索一個反向集枚舉樹，并通過效用上邊界來修剪搜索空間，在線性數據結構能夠計算一個緊密的邊界來進行強大的剪枝，并以一種高效和可伸縮的方式直接識別高效用模式。D2HUP 使用反向枚舉樹挖掘高效用模式，提出更緊湊的上界和不相關的項進行剪枝來提高算法的時間效率。使用CAUL（Chain of Accurate Utility List）結構維護每個枚舉模式的原始效用信息，使人們能夠有效地計算效用并估計嚴格的效用上限。

HUITWU[12]是一種新的HUITWU-Tree，用模式增長的方式尋找高效用項集，直接有效地計算數據庫中項集的效用。HUPM-FP[7]是一個基于模式增長方式的高效用模式挖掘算法，可以從全局樹上挖掘高效用模式，避免產生候選項集。該算法主要采用模式增長的方式來直接挖掘高效用模式，而不是從樹上先得到候選項集，因此算法的時空效率都得到了提升。

基于事務修改是一種快速更新高效用模式樹的算法（FUP-HUP-tree-MOD）[13]，可以有效地維護和更新構建的HUP-Tree，從而在不生成候選項的情況下動態挖掘數據庫中的高效用項集。HUP-Tree保證從中計算到每個模式的效用值，不需要再掃描數據集來計算模式的效用值，從而使挖掘算法的時空效率得到較大的提高。

兩階段算法產生候選項集策略且需要對候選項集進行測試，一階段算法直接生成高效用項集，因此產生候選項集的算法相較于不產生候選項集的算法性能更好。

基于樹結構的高效用挖掘算法的分析結果如表2所示。

4 縮減空間策略

在數據庫尋找高效用模式，無論是用樹結構還是其他結構，如列表結構，都需要減少搜索空間，以降低算法的時間復雜度和空間復雜度。剪枝策略有很多，不同特征使用不同的剪枝策略。減少對數據庫掃描次數的方法就是存儲后續算法需要用到的信息，如構建樹、列表、投影數據庫來存儲后續需要用到的信息，也就是數據庫中重要的信息。

表2 基于樹結構的高效用挖掘

4.1 剪枝策略

根據算法的結構不同使用不同剪枝技術。雖然使用的剪枝策略不同，但是剪枝的目的是相同的，就是減少搜索空間。

基于樹剪枝策略有很多，剪枝策略的主要方式是降低高估效用上界來減少可擴展的項，現有的子樹效用和局部效用很好地減少了可擴展項的數量。EFIM[14]依賴于兩個上界，采用子樹效用和局部效用有效地修剪搜索空間，該算法的剪枝策略是對枚舉樹進行剪枝。EFIM-closed[30]與EFIM不同的是添加了閉合屬性，也使用子樹效用和局部效用對搜索空間進行縮減。MEFIM（Modified Efficient high-utility Itemset Mining）[41]是一種基于EFIM 的算法，該算法考慮到單位利潤隨著時間的變化可能不同，因此單位利潤是動態變化的。該算法重新定義了效用的計算，為了提升算法的效率，使用子樹效用和局部效用進行剪枝，剪枝策略與EFIM相同。EHNL（Efficient High utility itemsets mining with Negative utility and Length constraints）[42]克服了效用值為負值的局限，使用子樹效用來減少搜索空間。但目前面臨的主要問題是如何結合子樹剪枝策略和負效用項集挖掘長度約束。為了解決這些問題，根據事務的效用值按非遞增順序對事務項進行排序，并在偏移指針的幫助下將負項保留在排序后的項的末尾。為了進一步減少可擴展項集，提高算法效率，提出DMHUPS（Discovering Multiple High Utility Patterns Simultaneously）[43]。DMHUPS也使用了局部剪枝，且該算法提出了更接近于真實效用的上界extUB（Extension Upper-Bound），更有效地減少了可擴展項的數量。

基于列表結構的剪枝策略主要是減少建立列表所需的計算，下面所述是在二項集計算時進行剪枝。FHM[23]提出剪枝策略EUCP（Estimated Utility Co-occurrence Pruning），它可以在不需要執行連接的情況下剪枝項集。CHUM（Closed+High Utility Itemset Mining）[44]、FDHUP（Fast algorithm for mining Discriminative High Utility Patterns）[45]、PHM（Mining Periodic High-Utility Itemsets）[46]、TKUL-Miner[25]用 EUCP 減少搜索空間，這些算法是提前計算項集對應的TWU，將效用存儲在EUCS結構。TKEH[11]采用EUCP 和SUP 策略來有效地搜索空間。kHMC[26]使用EUCPT可以避免在FHM中計算項目集效用的連接操作。FHAUI[33]算法將效用信息保存到效用列表中，通過效用列表的比較來挖掘出所有的高平均效用值，同時FHAUI 算法還采用了一個二維矩陣（EUCS）來有效減少二項效用值的連接比較次數。

除了上述的基于列表的策略外，還有保留效用策略也使用廣泛。HUI-Miner[21]構建效用列表，與CHUIMine 不同的是，它構建的列表第三部分的組成是RU（Remaining Utility），CHUI-Mine第三部分的組成是PU（Pivot-based remaining Utility），HUI-Miner縮減搜索空間的策略是所有IU（Itemset Utility）與RU 的和不小于給定的閾值則保留。為了解決HUI-Miner[21]昂貴的連接執行的操作，提出FHM（Fast High-Utility Miner）算法[23]。該算法提出共現剪枝策略來減少連接操作，并且還使用保留效用來減少搜索空間策略。

上述的剪枝策略不影響結果的完整性，因為上述的效用值都大于或等于實際的效用值，不會將實際的高效用模式忽略。子樹效用、局部效用、判斷二項集使用的效用值TWU、保留效用，都大于或等于實際效用，因此不會影響結果集的完整性。

4.2 投影策略

隨著高效用模式挖掘算法在實際應用中的重要性逐步顯著，其得到了越來越多的關注和研究，但是已知的一些算法存在著多遍數據集掃描以及產生大量候選項集、時效性不高等問題。這些問題使得高效用模式的挖掘效率大大降低，故提出基于投影的高效用項集挖掘算法。

EFIM[14]算法通過將數據庫相關項進行投影來減少數據庫的整體大小，還提出兩種有效的剪枝策略（局部剪枝和子樹剪枝）。子樹剪枝策略有效地減小了效用上界，使得進一步擴展項集減少，從而減少搜索空間。與之前的其他數據結構（樹結構與列表結構）相比，數據庫投影是一個簡單且非常有效的技術，如UP-Growth+[47]使用樹結構進行挖掘，HUP-Miner[22]、HUI-Miner[21]和FHM[23]都使用列表進行挖掘，這些算法與EFIM 進行比較，無論是在執行時間、內存使用和訪問節點的數量來看，都沒有優于EFIM。算法為了能夠挖掘效用值動態變化的情況，提出MEFIM[41]，它基于EFIM進行改進，同樣用到了數據庫的投影技術，使得數據庫的規模減小，進而提高算法的時間效率和空間效率。iMEFIM 是MEFIM的改進，該算法提出p-set結構，不需要掃描全部的投影數據庫，從而提高了算法的效率。EFIM 算法的缺點是需要多次掃描數據庫，為了解決這個問題提出了DMHUPS[43]。DMHUPS 也使用了數據庫投影的技術，且算法用到了IUData 列表，有效地獲得初始的投影數據庫。IUData列表的數據結構，用于存儲長度為1的項目集及其在事務中的位置信息，從而有效地獲取投影數據庫。此結構可以避免多次掃描數據庫，進而提高算法的效率。除了DMHUPS 算法還提出SPHUI-Miner[16]來改進EFIM 算法。SPHUI-Miner 是一種基于選擇數據庫投影的HUI 挖掘算法。該算法提出了一種高效的數據結構，稱為HUI-RTPL（High Utility Itemset-Reduced Transaction Pattern List），它是一種對內存要求低的數據進行優化和緊湊表示的格式。還提出了兩種新的數據結構，即選擇性數據庫投影效用列表和尾數列表，以縮減HUI 挖掘的搜索空間。數據庫的選擇性投影減少了數據庫的掃描時間，使得提出的方法更加有效。它為維度更小的數據創建了獨特的數據實例和新的投影，從而加快了HUI 挖掘的速度。投影技術不僅可以應用到挖掘完全高效用項集，還可以應用到閉合、Top-k高效用項集等。可以應用到閉合如EFIM-closed[30]算法，該算法在EFIM 的基礎上進行改進，將EFIM 中用到的挖掘技術延伸至挖掘閉合項集中。應用到Top-k中如TKEH，該算法沿用了EFIM 中的技術挖掘項集，但是在EFIM的基礎上不需要設置最小閾值，而是使用提高閾值的策略來初始化閾值。

4.3 其他

針對Top-k算法的策略與其他算法不同，Top-k的優點是不需要額外設置算法的最小閾值，主要策略是如何提高算法最小閾值。一般算法需要多種策略提高最小閾值。

REPT 通過PUD、RIU、RSD（Raising threshold with items in Support Descending order）、NU、MC、SEP（Sorting candidates and raising threshold by Exact and Pre-calculated utilities of candidates）提高最小效用閾值的方法有效地減少搜索空間。TKEH、kHMC 通過RIU、CUD、COV 來提高最小閾值，減少搜索空間。TKUL-Miner[25]是一種高效挖掘Top-k高效用項集的新算法。它利用一種新的效用列表結構，在搜索樹的每個節點上存儲必要的信息，以便挖掘項集。該算法利用特定區域的搜索順序快速提高邊界最小效用閾值。此外，還提出了另外兩種計算較小的高估效用的程序策略，以有效地修剪沒有希望的項集。該算法采用FSD（Firstlevel Search in TWU Decreasing-order）、RUZ（Reducing overestimated Utility by Sum_Zrutils）、FCU（First child pruning by using Sum_Cutil）等策略，快速提高了搜索的最小效用，有效地縮減了搜索空間。TKO（Top-kutility itemsets in One phase）[48]利用了 HUI-Miner 中的效用列表結構，提出了RUC、RUZ和EPB三種新的剪枝策略，提高了剪枝效率。TKU不僅使用TKO中的策略，還使用第五個策略（SE）對候選項集進行排序，并提高內部閾值。

通過對上述算法的描述，可以得出不同類型的算法使用的縮減搜索空間的方式不同，且大部分算法都使用多種策略，通過多種策略更大程度地減少搜索空間使得算法的效率更好。使用多種策略比使用單一策略的算法效果更好。

5 下一步工作

面對日益增長的海量數據和種類繁雜的數據，研究者可以深入探索以下幾方面。

（1）迭代和交互。數據挖掘成為一個交互的過程是可取的，因此算法被設計來支持交互挖掘。增量的高效用項集挖掘（increment High Utility Itemset Mining，iHUIM）中使用的一些數據結構不適合交互式挖掘。為了解決現有算法的這些局限性，研究人員需要采用增量方法來支持迭代和交互式增量HUIM。有很多可能性，例如對最新的HUIs 進行增量挖掘，使用固定最小效用閾值的交互式HUIs 挖掘，以及不設置最小效用閾值的迭代式增量HUIs挖掘。

（2）大規模的數據。增量地挖掘大型數據庫可能會導致較高的計算成本和較大的內存消耗。在批處理模型中，當插入新數據時，需要重復使用傳統的HUIM 算法來獲得更新的結果。然而，在大數據時代，漸進地處理數據并考慮先前分析的結果是至關重要的。iHUIM在處理大型數據庫方面存在一些研究機會：如何設計一個并行的iHUIM 算法，如何基于現有的大數據技術開發一個iHUIM 算法。此外，其他有前途的領域可以考慮，如設計并行、分布式、多核和基于GPU的算法。

（3）非均質性。傳統的關系或非關系數據庫系統通常使用具有同類格式的單一模式或文件。在大數據時代，需要處理大量的異構數據。傳統的數據挖掘技術旨在發現結構化數據中的有用知識。非結構化和/或半結構化數據中語義和異構模式的提取是數據挖掘和iHUIM 面臨的主要挑戰。因此，在調整iHUIM 以處理同類數據方面存在一些機會，包括逐步發現結構化數據、非結構化數據（可能包括文檔、音頻、視頻、圖像）和半結構化數據（即XML、JSON）。如何擴展現有的iHUIM算法來處理同構數據是一個重要的課題。

（4）動態復雜的數據。雖然已經開發了幾種增量式HUIM算法，但在如何處理復雜數據等方面仍存在許多挑戰。所有的iHUIM算法都是為了處理精確的數據而設計的，因此不適合處理不確定的數據。到目前為止，在動態序列數據中挖掘高實用模式的增量方法還沒有被開發出來。因此，增量式高實用程序順序模式挖掘也是一個有趣的主題。由于現實生活中的數據是動態的而不是靜態的，因此大規模復雜數據的應用范圍很廣。這個原理很簡單，但是在數據挖掘算法的設計中集成起來肯定是困難和復雜的。與靜態環境相比，發現動態數據的環境比較復雜，而且更難處理。

（5）iHUIM在運行時間和內存方面的計算開銷非常大。對于密集的數據庫，或者包含大量條目或長事務的數據庫，這取決于用戶設置的最小高效用閾值。雖然目前的增量挖掘算法比以前的算法要快得多，但仍有改進的空間，例如開發出更緊湊的數據結構（如樹、列表、圖）、更有效的剪枝策略以及自適應挖掘方法。

6 總結

本文主要從算法的實現階段進行分析，一階段算法在時間與空間效率方面都要優于兩階段算法，主要原因是，兩階段算法需要產生候選項集，然后再驗證候選項集是否為高效用項集。為了提高算法效率，提出一階段算法直接挖掘高效用項集，不需要生成候選項集，從而節省了時間與空間，針對不同的問題采用不同的算法，將算法劃分之后再進行分析。然后從算法的實現過程來看，針對是否產生候選項集進行分析，通過數據庫采用的數據結構不同，使用的剪枝策略不同來分析廣泛使用的策略。下一步研究的主要工作是如何進一步提高算法的效率。主要方法是進一步縮小效用上界，提出更緊湊的結構存儲信息，減少數據庫掃描次數等。