衍生高效用模式挖掘算法綜述

劉淑娟 韓萌 高智慧 穆棟梁 李昂

摘要：在數據挖掘領域中，高效用模式挖掘任務具有較高的理論研究價值和廣泛的實際應用場景。針對多變的應用場合，提出了一系列衍生高效用模式。首先從關鍵技術的角度對高平均效用模式挖掘算法進行了分類論述，主要包括基于先驗、基于樹、基于列表、基于投影和基于數據格式的方法。其次，分析討論了基于全集、精簡集以及融合模式的含有負效用的高效用模式挖掘算法。再次，從模糊高效用模式、相關高效用模式和其他新興高效用模式三個方面概述和總結了擴展高效用模式算法。最后，針對現階段研究方向的不足，給出下一步的研究方向。

關鍵詞：衍生高效用模式；高平均效用模式；負效用；模糊高效用模式；相關高效用模式；綜述

中圖分類號： TP311.13文獻標識碼： ADOI：10.3969/j.issn.1007-791X.2024.02.005

0引言

頻繁模式挖掘[1]（Frequent Pattern Mining， FPM）假設數據庫中所有項目具有相同的重要性，主要通過其二進制屬性（該項目是否在事務中出現）從數據庫中尋找頻繁發生的項集。然而，現實生活中，特別是在市場數據庫中，每條事務都包含了項目的內在價值，因此僅考慮項集的頻率對于找出高利潤的項集意義不大。例如，{香煙，紅酒}是一個頻繁項集，這僅體現了香煙常與紅酒同時銷售，并未體現其數量和價值信息。為解決其局限性，提出了高效用模式挖掘[2]（High Utility Pattern Mining， HUPM）， 通過定義項目的單位利潤和數量來發現具有高效用（如產生高利潤）的項集。例如，{香煙：2， 紅酒：1， 紙巾：1}表示顧客購買2包香煙、1瓶紅酒和1包紙巾，以上單件商品利潤分別為25元、200元和1元。經計算，此項集產生251元的利潤，銷售者可根據自身制定的標準來判斷此項集是否為一個高效用項集（High Utility Itemsets， HUIs）。在購物籃數據分析中，這能有效幫助決策者制定營銷計劃。

盡管HUPM通過考慮效用度量揭示了有意義的高效用模式，由于實際應用的多變性，面對復雜的需求，傳統的HUPM無法普遍適用于多元化的生活場景。針對特定某一類問題，研究者們提出了更加精確的解決方案。于是，以高效用模式為基礎，衍生出一系列較為復雜的模式。傳統HUPM忽略了項集長度對效用值的影響[3-4]，因此會產生大量無意義的長模式，即長項集中可能會包含大量低于效用平均值的項。例如，銷售者將利潤高于200元的商品稱為HUIs，由于紅酒利潤較高，故其與任意商品組合均為HUIs，如{紅酒，紙巾}、{紅酒，紙巾，尿布，口香糖，…}等，即使HUIs中存在如紙巾這樣的低利潤項，但項集的利潤隨著物品組合數的增加而增加，此時，效用度量更偏向于長項集。為解決此問題，TPAU[3-4]算法引入平均效用度量以挖掘高平均效用項集（High Average Utility Itemsets，HAUIs），即單位效用較高的項集，首次提出高平均效用模式挖掘（High Average Utility Pattern Mining， HAUPM）方法刪除大量長度較長但含有低利潤項的HUIs。由于其具有兩階段算法[5]的局限性，隨后PBAU[6]算法采用投影技術縮小數據庫規模。HAUP-growth[7]算法通過樹結構存儲信息減少數據庫掃描次數。HAUI-Miner[8]算法設計緊湊的垂直列表結構高效挖掘HAUIs。為提高挖掘效率，MHAI[9]算法和FHAUI[10]等算法通過設計緊湊上界來減少候選項集數量，進一步豐富該模式領域。

此外，HUPM的局限性還在于未考慮項效用為負的情況[11]。實際上，負項存在于生活的方方面面，如商家的銷售虧損和消費者的欠費行為等，例如，香煙降價促銷，出現虧本的情況，其利潤為-1元，即虧損1元處理，但商家可通過將香煙紅酒捆綁銷售的策略保證收益為正。由于HUPM的方法僅考慮了項效用為正的情況，則無法直接應用于負項存在的場景。HUINIV-Mine[12]算法首次引入了負效用的概念并挖掘含有負項的高效用模式，克服了HUPM僅適用于正項的局限。隨后，人們還研究了其它問題，如基于Top-k的TopHUI[13]算法、增量數據庫上的HUPM算法ITPAU[14]、數據流上的HUPM算法HND以及不確定數據庫上的HUPNU[16]算法等，使得模式挖掘的任務進一步廣泛應用。

近年來，學者們仍致力于對高效用模式的創新研究工作。一些新興的衍生HUPM方法逐漸出現在大眾視線，如模糊高效用模式[17]、相關高效用模式[18]、占用高效用模式[19]和跨層級的高效用模式[20]等。針對傳統高效用模式在定量數據庫上挖掘會產生大量冗余項集的缺陷，HUFI-Miner[17]算法首次提出模糊高效用模式挖掘方法，引入模糊集概念，將難以表達的數量或利潤關系轉化為易于理解的語言表達。相關高效用模式挖掘任務解決了高效用模式挖掘結果中項集之間相關性較低的問題。Fournier-Viger等人[18]首次引入相關度量，同最小效用閾值共同約束挖掘過程，刪減了大量項之間相關性較弱的模式。為進一步挖掘有用高效的模式，文獻[19]結合效用和占用率概念，提出了占用高效用模式挖掘（High Utility Occupancy Pattern Mining， HUOPM）方法。通過比較模式和包含該模式的事務效用占比情況，判斷該模式的重要程度以提取出更具代表性的有趣模式。此外，傳統的高效用模式忽略了項目的分類信息，從而丟失了部分有意義信息，故跨層級的高效用模式[20]引入分類法概念，為模式中的每個項目設置相對應的類別。這種結合分類信息的模式發現為分析用戶行為提供了新思路。

以上模式均衍生自高效用模式，故命名為衍生高效用模式；不同點在于針對特定問題提出的衍生高效用模式各有特點。此外，有學者研究了這些模式的融合以處理較復雜的問題。例如，紅酒和紙巾的購買組合并不常見，故項目之間的相關性較弱，這種購買關系的推薦是無意義的。結合模式長度的影響，挖掘出單位利潤較高的商品組合，Sethi等人提出CoHAI-Miner[21]算法挖掘相關高平均效用模式。此外，為克服現有HAUPM方法只能處理正效用的問題和在含負效用的數據庫中模式發現不完全的局限，提出融合模式算法MHAUIPNU[22]挖掘含負效用的高平均效用模式。現階段仍不斷產生較為復雜的衍生高效用模式以處理傳統高效用模式中存在的不足，模式之間可根據需求彼此結合更加精準地提供解決方案。為便于后續進一步研究和豐富內容，現總結分析衍生高效用模式挖掘的算法是必要且有意義的。本文將對以上模式的算法進行全面綜述。

在現有的相關綜述中，Singh等人[23]從數據結構的角度總結了帶負項的高效用挖掘問題。隨后，又從靜態、動態和序列數據方面闡述并分析了HAUPM[24]算法的最新信息。張妮等人[25]首次從正負效用劃分角度總結了HUPM算法。Almoqbily等人[26]根據時間順序和算法采用的度量類型總結了相關高效用模式挖掘算法。以上文獻僅對一類高效用模式算法進行介紹，此外，只簡單涉及其余新興高效用模式。李慕航等人[27]首次從高效用融合模式和衍生模式角度闡述歸納算法，但主要分析融合模式，僅涉及四種衍生模式，并未對近期新出現的高效用模式進行總結分析。

因此，本文從不同的角度切入，對多種衍生高效用模式進行全面分析總結并進行優缺點對比。衍生高效用模式分類框架如圖1所示。本文貢獻如下：

1） 全面總結了多種衍生高效用模式，包括高平均效用模式、含有負效用的高效用模式和最近提出的新興高效用模式。

2） 首次從關鍵技術的角度對HAUPM算法進行分類總結和優缺點對比；從全集、精簡集以及融合模式的角度對含有負效用模式進行分類總結和優缺點對比；最后，對擴展高效用模式挖掘算法進行分析歸納。

3） 根據目前研究不足，給出下一步研究方向，包括智能優化算法在衍生高效用模式挖掘中應用、結合項目分類法的跨層級模式挖掘和并行分布式挖掘等。

1相關概念和定義

為了清楚地描述部分衍生模式挖掘問題，給出一個事務數據庫和一個效用表，如表1和表2所示。事務數據庫是一組事務的集合，定義為D={T1，T2，…，Tn}，I={i1，i2，…，im}為一組項的集合，其中對于每個事務TC，TC∈I且具有唯一的標識TID。每一個項目i均有一個購買數量in（i，TC）（內部效用）和效用表（其中存儲了項目到單位利潤的映射）中項i的單位利潤ex（i）（外部效用），即表1和表2中數字。

定義1（事務中的項/項集的效用）[2] 項i在事務TC中的效用記為u（i，TC），定義為u（i，TC）=in（i，TC）·ex（i）。項集X在事務TC中效用記為 u（X，TC），定義為

例：項A在事務T1中的效用為u（A，T1）=in（A，T1）·ex（A）=1×3=3。項集{AB}在事務T1中的效用為u（{AB}，T1）=u（A，T1）+u（B，T1）=13。

例：事務T2的效用tu（T2）=1×10+3×（－1）=7。

例：數據庫中有6條事務， TU=tu（T1）+tu（T2）+tu（T3）+tu（T4）+tu（T5）+tu（T6）=84。

定義5（最小平均效用閾值）[2]δ∈[0，1]，最小平均效用閾值定義為minutil=δ·TU。

例： δ=0.7，minutil=0.7×84=58.8。

定義6（事務中項/項集的平均效用）[4]項i在事務TC中的平均效用記為au（i，TC），定義為au（i，TC）=u（i，TC）。

例：項集{AC}在事務T6中的平均效用為au（AC，T6）=2。

定義8（事務最大效用）[4]事務TC的最大效用記為tmu（TC），定義為tmu（TC）=max{u（i，TC）|i∈TC}。

例： tmu（T2）=max{u（A，T2），u（B，T2），u（C，T2），u（D，T2），u（E，T2）}=max{0，10，0，-3，0}=10。

定義10（高平均效用上限項集）[4]如果auub（X）≥minutil，項集X為高平均效用上限項集，記為HAUUBI。

定義11（高平均效用項集）[4]如果au（X）≥minutil，項集X為高平均效用項集，記為HAUI。

例： 設最小效用閾值minutil=10，

auub（{AC}）=tmu（T1）+tmu（T6）=10+10=20，

au（{AC}）=au（{AC}，T1）+au（{AC}，T6）=5.5，

auub（{AE}）=tmu（T5）+tmu（T6）=20+10=30，

au（{AE}）=au（{AE}，T5）+au（{AE}，T6）=13。

由定義10，項集{AC}和{AE}均為HAUUBI。由定義11，項集{AC}不是HAUI，{AE}是HAUI。

例： RTWU（{AE}）=RTU（T5）+RTU（T6）=57。

2高平均效用模式

由于項集的效用是項的效用之和，長項集會產生很高的利潤，因此，傳統HUPM傾向于尋找更長的項集，故在相同的閾值下，短模式不易被發現，其效用度量無法保證公平性。為解決HUPM的不足，HAUPM算法通過長度規范了項集的效用來發現單位效用較高的項集，因此刪除了大量無意義的包含低效用項的高效用長模式。本節從關鍵技術對高平均效用模式挖掘的算法進行總結，包括基于先驗、基于樹、基于列表、基于投影和基于數據格式的方法。

2.1基于先驗的方法

Apriori算法[30]是最早出現在關聯規則挖掘中的算法，通過逐層水平迭代搜索的方式生成候選項集進而形成規則。其原理是利用Apriori性質，又稱向下閉包屬性（Downward Closure， DC） ，來限制候選項集產生來發現頻繁項集，即若某個項集是頻繁的，其所有的子集都是頻繁的；若某個項集不是頻繁的，其所有的超集也是非頻繁的。隨著用于克服FPM局限性的HUPM出現，Apriori性質也被用于效用挖掘中，如Two-phase算法[5]結合TWU模型和Apriori性質在兩個階段內挖掘HUIs。

然而，在效用挖掘中，項集的實際效用隨著項數量的增加而增加。Hong等人首次在HUPM中引入平均效用概念并提出了一個兩階段挖掘算法TPAU[3-4]，算法利用auub度量高估項集的平均效用，篩選出auub值大于minutil的候選項集，通過再次掃描數據庫計算候選項集的實際平均效用找到HAUIs。針對算法僅考慮單一最小效用閾值的局限性，HAUIM-MMAU[31]算法可為每個項目指定不同閾值，為挖掘具有多個最小效用閾值的HAUIs提供了一個基礎框架，引入最小平均效用（Least Minimum Average Utility， LMAU）解決auub屬性無法直接應用該框架的問題，并設計改進的估計效用共現剪枝（Improved Estimated Utility Co-occurrence Pruning， IEUCP） 策略和計算前剪枝策略（Pruning Before Calculation Strategy， PBCS）來盡早剪枝無希望的項集，從而加快HAUIs的發現。

當前的大部分 HUPM 或 HAUPM 算法均基于靜態數據庫，故不適用于動態數據的處理。 隨后，ITPAU[14]算法引入快速更新（Fast Update， FUP）概念以處理增量數據挖掘的復雜情況，將新事務中挖掘出的新結果與原事務庫中挖掘出的信息結合，通過重用部分有效信息來加速挖掘過程。但在某些情況下，該算法仍需重新掃描數據庫來獲取新的信息，知識維護的效率低下。Wu等人引入預大的概念來設置Sl和Su兩個閾值以用于知識維護工作，并進一步提出APHAUIM[32]算法。該算法為避免多次掃描數據庫，在緩存區內存儲預大平均效用上限項集，因此節約了大量時間成本。

2.2基于樹的方法

由于基于先驗的算法需多次掃描數據庫生成候選項集并驗證，因此花費高昂的時空成本。故研究者們提出了基于樹的挖掘算法，即通過數據庫掃描構建存儲項集相關內容信息的樹[33]，隨后挖掘過程中只需迭代遍歷樹而無需掃描數據庫。

本小節將基于樹的方法分為在靜態數據上和在動態數據（增量數據、數據流）上的挖掘算法。

在靜態數據上，Lin等人提出的HAUP-growth[7]算法中設計了新穎的壓縮樹結構HAUP-tree，樹路徑末端的每個節點存儲項的auub以及路徑中前項的數量，該結構結合模式增長方法導出模式。姜玫等人提出了一種不需要產生候選項集HAUI-Mine[34]算法，樹中尾節點存有路徑中的最大效用、路徑中條件模式基的效用以及路徑的效用列表。算法依據HAUI-Tree中的項，通過產生的條件模式基依次遞歸構建條件模式樹以挖掘HAUIs。該算法的對比實驗表明，在稀疏數據集上優于HAUP-growth算法。Lu等人[35]設計類似于索引表的項集結構以快速計算該項集的au和auub，并采用新的數據結構HAUI-Tree存儲。該結構可根據項集屬性直接計算出下一階段中項集的效用值，提高了算法執行效率。

以上算法均基于靜態數據庫，由于現實應用程序中，數據往往以流的形式產生，數據庫會隨著事務的增加或刪除而發生變化，此時，靜態數據的挖掘方法將無法滿足應用需求[33]。下面將總結動態數據上基于樹的挖掘方法。

在增量數據庫上，Kim等人提出IMHAUI[36]算法和新的數據結構IHAUI-Tree，IHAUI-tree上的每個結點N存儲從根到N的路徑重疊事務信息，通過結點的共享效應維護增量數據庫的信息。Lin等人提出基于改進FUP概念的IHAUPM[37]算法以處理有事務插入的增量數據庫，采用HAUP-Tree結構保存來自原始數據庫的必要信息，將原始數據庫和新添加的事務劃分為四種情況進行維護。此外，該算法僅關注增量部分，利用部分內存就可以快速實現對HAUIs的更新。

在數據流上，姜玫等人提出一種不產生候選項集的挖掘算法ITR-Mine[34]，設計ITR-Tree結構維護窗口內數據信息，依次更新當前窗口內的數據并遞歸構建條件模式基和條件模式樹，實現在數據流上的挖掘任務。SHAU[38]算法提出SHAU-Tree結構，其中每個結點用批量列表保存最近流數據中的平均效用信息以此挖掘最新的重要模式。此外，通過平均效用上界最小化剪枝策略提高算法的性能。由于最新數據可能比舊數據具有更高的影響，Yun等人首次應用平均效用因子和數據流衰減概念以處理敏感數據流上的事務，提出了基于阻尼窗口的MPM[39]算法，通過設計阻尼平均效用樹（Damped Average utility Tree， DAT）維持事務的阻尼平均效用，為管理事務效用信息并確定無效事務，通過事務效用列表（Transaction Utility List， TUL）信息判斷下一步候選驗證。

HAOP-Miner[40]算法將HAUPM方法同一次性序列模式結合，采用反向填充策略計算支持度避免冗余節點的創建，此外，為解決枚舉樹生成大量候選模式，提出支持度下界方法并結合模式連接策略剪枝候選模式，從而實現了模式的高效剪枝。HANP-Miner[41]算法將HAUPM方法與非重疊序列模式挖掘結合，采用了基于簡化Nettree結構的深度優先搜索和回溯策略計算模式的支持度，結合基于平均效用上限的模式連接策略減少候選模式的生成。

2.3基于列表的方法

由于先前已有的算法均需要大量計算來找到符合條件的項集。為此，研究人員還積極探索了基于列表的方法。效用列表結構內存占用較小且無需重復數據庫掃描，此外，項集間的連接操作方便，k-項集（k>1）的列表結構可通過其子集的（k－1）列表結構連接操作構造。因此，受效用列表啟發，HAUI-Miner[8]算法提出了平均效用列表（Average Utility List， AU-List）結構。與效用列表結構不同在于，三元組中剩余效用被替換為事務最大效用。該算法利用項集的平均效用與事務最大效用之和及早識別無希望項集。

為加快算法執行速度，解決上界松散問題， Yun等人提出MHAI[9]算法和新的數據結構HAI-List。在此基礎上，設計了基于最大平均概念的預剪枝技術。FHAUI[10]算法提出了新穎列表結構IAU-List，該算法在首次數據庫掃描后重新計算項集的tmu值以得到更加緊湊的平均效用上界。此外，引入估計平均效用共現剪枝結構 （Estimated Average Utility Co-occurrence Structure， EAUCS）減少項集間的比較連接次數。FHAUPM[42]算法提出一個較為松散的上界lubau，該上界在早期階段有效淘汰候選項集，但當項集不相關時，性能提高不明顯，隨后，還引入更嚴格的上界tubau以縮小搜索空間。EHAUPM[43]算法開發了新的效用列表MAU-List結構，包含四元組（tid，iutil，rmu，remu），其中rmu為修正事務的最大效用，remu為事務剩余最大效用。在此基礎上，引入lub和rtub兩個更緊湊的上界。 TUB-HAUPM[44]算法應用兩個新的更嚴格上界mfuub和krtmuub，同時對傳統的全局事務上界進行改進，比較事務的兩個上界值，選擇較小值作為該事務上界實現快速緊化。LMHAUP[45]算法提出TA-List結構，其中，具有相同事務標識的元組在構造過程中相互鏈接以減少列表連接成本。此外，提出兩個新的緊湊上界tmaub和mrau。

由于單一的最小閾值可能會導致項集過少或冗余的狀況，且存在不公平因素，因此MEMU[46]算法利用多個最小效用閾值挖掘。為解決HAUIM-MMAU使用生成測試方式耗時的問題，該算法采用緊湊效用列表CAU-List和表示搜索空間的排序樹挖掘HAUIs，根據列表中存儲的rmu可快速得到rtub緊湊上界值。上述基于多最小閾值的算法均是按照最小平均效用閾值的升序處理項目以保留auub的DC特性，而傳統HAUPM算法均是基于auub升序，因此不能直接采用HAUIM-MMAU和MEMU框架。針對此問題，GHAIM[47]算法引入后綴最小平均效用（Suffix Minimum Average Utility， SMAU）概念保持auub模型的DC特性和幾種剪枝方法，使得所有修剪方法通用并且獨立于項集的排序。

在增量數據庫中，基于AU-List結構和FUP概念，Wu等人提出在事務插入更新時挖掘HAUIs的方法[48]，將原數據庫和新事務中的HAUUBIs分為四種情況，更新數據集和AU-List，同時刪除AU-List中的非HAUUBIs，從而有效維護HAUIs。FUP-HAUIMI[49]算法維護事務插入情況下的數據庫，FUP-HAUIMD[50]是一種通過事務刪除來更新發現的HAUP的算法。兩者均引入改進版的FUP概念減少增量挖掘中候選模式數量， 僅在特定情況下進行原始數據庫掃描。

隨著研究的不斷深入，HAUPM方法也同其它模式融合。Sethi等人將相關性度量引入HAUPM中，提出CoHAI-Miner[21]算法，使用垂直的列表結構保存效用和相關信息。通過與EHAUPM算法的實驗分析對比，該算法能發現更多有意義的模式。MHAUIPNU[22]算法為挖掘具有正負效用的HAUIs，提出新穎數據結構TUBPNUL，引入嚴格上界tubpn并提出三種剪枝策略。

2.4基于投影的方法

在HAUPM中，投影技術和索引機制可加快算法執行速度，投影相關子數據庫能有效縮小原始數據庫的大小，從而只保留在挖掘過程中必要的項集信息，避免不必要的檢查從而降低挖掘過程中的內存需求。

為了提高HAUPM的效率，Lan等人提出了PBAU[6]算法，該算法利用索引表結構模擬投影技術，投影當前前綴所需要的事務數據。隨后，PAI[51]算法利用前綴映射方法，據項集持續變化更新投影事務的最大效用值以緊化上界。FIMHAUI[52]算法結合數據庫投影和事務合并技術高效發現HAUIs，提出IHAUI-Tree結構的改進版本，僅在葉子結點中存儲事務信息，用該結構來獲取有希望項集的投影數據庫，而無需生成條件模式基和局部樹。

Thilagu等人提出一種基于平均效用的Web遍歷模式挖掘算法[53]，該算法利用投影序列計算模式的事務加權效用，無需考慮整個序列中項的效用，這極大地減少了候選模式的數量。在不確定數據庫中，李霆提出PrefixMUHAUSP[54]算法挖掘出高平均效用序列模式，通過投影數據庫的方法，縮小數據庫規模并生成更少的候選序列。

2.5基于數據格式的方法

為解決算法性能的不足，研究人員們提出了基于垂直數據結構和基于索引結構的挖掘算法。由于基于水平數據結構的挖掘方法需要額外的數據庫掃描，HAUI-Miner算法設計了一種垂直表結構存儲項集的效用信息，通過遞歸生成擴展項集的效用列表來提高挖掘速度。隨后，在AU-list的基礎上，許多算法引入更為緊湊的上界模型和剪枝策略，但仍花費大量時間成本浪費在評估不必要的模式上。

通常，研究者認為基于垂直表示法的上界與水平表示法（如auub和lub）相比表現良好。為解決

此外，基于索引結構的算法也可在一定程度上提高算法執行效率。類似于PBAU算法中使用的索引表，HAUI-Tree[35]算法中使用了一種特殊的項目結構快速計算項集效用，從而優化內存使用。EHAUI-Tree[57]算法利用索引表快速計算項集的平均效用上界，引入位數組結構保存項集信息，從而最大限度地減少內存的使用并提高計算效率。

2.6小結

本節首次將高平均效用模式挖掘方法按關鍵技術角度分類總結，分別為基于先驗、基于樹、基于列表、基于投影和基于數據格式的算法。如表3所示，從關鍵技術角度總結并對比了HAUPM算法。

本小結采用定量分析的方法在同一數據集上進行算法的時空消耗對比，并分析了此類方法的共同特點和仍普遍存在的缺陷。此外，對部分HAUPM算法的時間復雜度進行了分析比較。以TPAU[3-4]算法為代表，基于先驗的算法采用生成和測試的方法挖掘，雖然剪枝策略能減少比較連接的次數和平均效用的計算成本，但仍需進行多次數據庫掃描并在內存中生成大量候選項集，這極大影響了算法的時空效率；基于樹的方法通過構建樹結構存儲原始數據庫信息，在一定程度上克服了多次掃描數據庫的弊端。在相同的最小閾值下，基于樹的HAUP-growth[7]算法比TPAU算法快近一倍，但該算法內存消耗較大且隨著樹的高度的增長大大增加。此外，這類算法普遍存在的問題在于樹的結構較為復雜且不利于算法擴展；基于列表的算法使用垂直壓縮結構保留挖掘過程中所需信息，結構簡單易實現。在Mushroom數據集上，當minutil為4%時，HAUP-Growth算法的執行時間為233.7 s，而基于列表結構的HAUI-Miner[8]算法僅需1.3 s，比HAUP-Growth算法快1～2個數量級，此外，在內存消耗方面同樣優于HAUP-Growth算法，但這類算法的缺陷在于昂貴的列表比較和連接操作；基于投影的算法通過縮小原數據庫規模減少掃描數據庫的成本，例如PAI[51]算法，在BMS-POS和Chess數據集上，其生成的候選項數量遠小于TPAU生成的，且運行速度比TPAU算法快得多。但其依賴于投影機制，在內存消耗方面不如HAUI-Miner算法。這類算法仍未克服生成大量候選項集的局限性；基于數據格式的算法主要指基于垂直數據結構的或者索引結構的挖掘方法，基于垂直數據庫表示的算法在運行速度和列表連接次數方面性能較優，基于索引的方法在一定程度上提高了計算效率。在實驗中，基于垂直挖掘的dHAUIM[55]算法比HAUI-Miner等算法快1～2個數量級，在Chess數據集上的實驗結果顯示，隨著minutil的不斷調整，該算法速度為HAUI-Miner算法的32～239倍。由于算法設計的上界比HAUI-Miner使用的傳統auub上界模型更加嚴格，因此可在早期刪除大量無希望的候選項來降低列表的連接次數。

此外，對部分HAUPM算法的時間復雜度進行了分析比較。ITPAU[14]算法是兩階段的算法，時間主要消耗在候選項集的生成和測試階段，設Lk為生成k-項集的數量，kCi為i個元素組中k個元素的組合數，數據集中項的數量為n，則生成項集數為nC1+nC2+…+nCn=2n－1，故時間復雜度為O（2n）。基于樹的IMHAUI[36]算法主要分為掃描數據庫、插入新事務更新IHAUI-Tree、重構IHAUI-Tree、遞歸挖掘局部樹等階段。其中，設n是在新事務（n/2個不同項）插入之后，增量數據庫具有的不同項數量。故掃描數據庫以及更新樹的時間復雜度為O（3n/2），該算法在挖掘過程中需按auub降序重構樹，在使用冒泡排序調整路徑的情況下，最壞時間復雜度為O（n2）。為n個結點構建局部條件樹的時間復雜度為O（2np），其中p為參與構建局部條件樹的結點個數，令Tz是z的局部樹的遞歸模式增長操作時間。故整個挖掘過程

3含有負效用的高效用模式

傳統高效用項集挖掘中，默認項的效用值為正。但在應用場合下，存在效用值為負的情況。例如，超市臨期處理商品時，往往降價促銷，存在虧本的情況。超市決策者可以通過指定捆綁銷售措施來稍微挽回損失，故需要提出能同時處理正負效用的HUPM方法。有研究者提出含有負效用的高效用模式挖掘方法。本節根據模式劃分方法進行分類總結，包括基于全集、精簡和融合的模式。

3.1全集模式

全集模式是指傳統意義上的高效用模式挖掘結果，即找到所有滿足效用值大于等于最小效用閾值的所有項集。Chu等人首次提出基于兩階段的含有負效用的模式挖掘算法HUINIV-Mine[12]，算法利用重定義事務加權效用上界高估含有負效用的項集效用，保證項集中最少含有一個外部效用為正的項，并通過再次數據庫掃描驗證，故存在一定時空局限性。

3.1.1基于模式增長的方法

為解決基于候選生成-測試方法的局限性且避免生成數據集中實際不存在的候選項集提出了基于模式增長的方法。UP-GNIV[11]算法僅需兩次數據庫掃描，引入兩種過濾策略刪除負項效用（Removing Negative item Utilities， RNU）和剪枝負項集（Pruning Negative Itemsets， PNI）以去除含有負效用的項來提高挖掘效率。實驗結果表明，該算法在執行時間和擴展性方面優于算法HUINIV-Mine[12]。EHIN[29]算法為減少內存消耗，采用事務庫投影和事務合并技術，另外引入效用數組來計算重定義的本地效用（Redefined Local Utility， RLU）和重定義的子樹效用（Redefined Subtree Utility， RSU）的新上界。基于此，運用RLU-Prune和RSU-Prune策略剪枝搜索空間。為挖掘出數量較少且更有意義的模式。EHNL[58]算法引入長度約束的概念，利用最小長度約束刪除大量短項目集，最大長度約束來限制過長的項集，從而使得生成的關聯規則更具代表性，此外，結合事務合并技術降低算法計算成本。

在動態數據庫上，Li等人提出了兩種基于滑動窗口的挖掘含有負效用的高效用項集算法，即MHUI-BIT-NIP[59]和MHUI-TID-NIP[59]，兩者分別采用了BITvector和TIDlist的項目表示法以加快當前滑動窗口內項集的挖掘速度，同時，開發LexTree-2HTU結構維護窗口內2-項集的高事務加權效用。

3.1.2基于列表的方法

單階段算法FHN[60]是FHM[2]算法的一種擴展，開發新的列表結構PNU-List應對負項的出現，且項的正負效用值采用單獨的列表結構存儲。此外，應用基于估計效用共現剪枝結構（Estimated Utility Co-occurrence Structure， EUCS）的剪枝策略和剩余效用剪枝策略。經實驗證明，該算法在時空效率上均優于HUINIV-Mine[12]。隨后，在FHN的擴展版本[28]中添加LA-Prune剪枝策略再次縮小搜索空間。GHUM[61]算法開發了一個簡化效用列表結構，同時，基于項集效用反單調特性提出了A-Prune和N-Prune剪枝策略來降低列表連接成本。陳麗娟提出EHINM[62] 算法，該算法應用了改進的列表結構，包含三元組（tid，rutil，rpnu），其中rpnu為重新定義的剩余效用值。考慮到負效用在項集擴展時對事務效用的影響，引入RPNU和RTWU兩種緊湊上界并提出三種剪枝策略。

面對不確定事務數據庫，HUPNU[16]算法采用新的垂直列表結構PU±-list存儲正負項并提出六種修剪策略提前修剪無希望的項。此外，張妮等人首次提出在數據流中挖掘含有負項的HUPM算法HND[15]。受ULB-Miner算法啟發，開發出新的列表索引結構（List Index Structure， LIS）。不同于傳統效用列表，此結構通過內存重用策略降低內存消耗成本，大大提升了挖掘性能。

3.2精簡模式

因全集模式具有產生大量候選集導致項集冗余和最小效用閾值設置困難的問題，精簡高效用模式應運而生，主要包括最大高效用模式、閉合高效用模式和Top-k高效用模式等。本小節將從這一角度總結含有負效用的模式挖掘方法。

Top-k模式不需要設置最小效用閾值，僅需用戶提供生成具體高效用模式數量。Gan等人提出了一種挖掘具有正負效用的HUIs的通用算法TopHUI[13]，設計了PNU-List結構存儲正負項信息，采用四種自動提升最小效用閾值方法，分別為基于項的實際效用提升最小閾值（Raising threshold based on real Item Utilities， RIU）策略、基于事務效用提升閾值（Raising threshold based on Transaction Utilities， RTU）策略、基于重定義的事務加權效用提高閾值（Raising threshold based on Redefined Transaction Weighted Utility， RRTWU）策略和基于候選項效用提高閾值（Raising the threshold by the Utilities of Candidates， RUC）策略，還引入數據庫投影和事務合并技術減少數據庫掃描成本，并應用基于數組的效用計數技術快速計算項集上界值，同時采用了RTWU-Prune、RU-Prune、LA-Prune和Leaf-Prune剪枝策略提高挖掘效率。Sun等人提出基于模式增長的THN[63]算法，該算法基于RLU和RSU提出兩種剪枝策略并引入一種基于重定義事務加權效用上界的最小效用閾值提升策略找到模式的前K項，此外，結合數據庫合并和投影技術降低數據庫掃描成本。TKN[64]算法調整LIU結構存儲正負效用，引入正項的實際效用（Positive Real Item Utility， PRIU）提升策略、基于LIU結構的正項（Positive LIU-Exact， LIU-E）提升策略以及基于LIU結構的正項下邊界（Positive LIU-Lower Bound， LIU-LB）提升策略來快速提高最小效用閾值，泛化本地效用和子樹效用關鍵剪枝屬性并提出兩種新的剪枝策略。

Singh等人提出CHN[65]算法挖掘含有負效用的閉合高效用項集，算法利用RSU-Prune縮小搜索空間并且利用雙向擴展技術對搜索空間進行閉包檢查。

3.3融合模式

為處理不同應用場合下的問題，含有負效用的模式與其他模式融合。On-shelf高效用模式除了考慮商品數量和利潤外，同時引入了商品的上架時間周期。TS-HOUN[66]算法首次結合負效用概念和上架時間，通過三次數據庫掃描，從時間數據庫中挖掘出含有負效用的貨架HUIs。由于該算法是兩階段算法的擴展，故挖掘效率并不高。Fournier-Viger等人提出基于效用列表的FOSHU[67]算法，該算法避免了為每個時間段挖掘結果合并，同時挖掘所有時間段以減少模式連接開銷。實驗結果表明，該算法比TS-HOUN[66]算法快近3個數量級，內存占用也大幅度降低。針對貨架上的Top-k HUIs挖掘問題，Dam等人提出基于效用列表和估計共現最大周期率結構（Estimated co-occurrence Maximum Period Rate Structure， EMPRS）的KOSHU[68]算法，引入實際1-項集的相關效用閾值提升策略（the Real 1-Itemset Relative Utilities threshold raising strategy， RIRU）和實際2-項集的相關效用閾值提升策略（The Real 2-itemset Relative Utilities Threshold raising strategy， RIRU2），并應用估計最大周期率剪枝（Estimated Maximum Period Rate Pruning， EMPRP）策略、2-項集的共現剪枝（Concurrence Existing of a pair 2-itemset Pruning， CE2P）策略和周期效用剪枝（Period Utility Pruning， PUP）策略減少列表連接次數。針對動態數據庫，Radkar等人提出FUPT-HOUIN[69]算法，引入FUP概念構造效用樹挖掘含負項的貨架HUIs。

Xu等人提出挖掘含有負項值的高效用序列模式算法HUSP-NIV[70]。采用LQS-Tree存儲高效用序列并通過I-級聯和S-級聯方法生成候選序列。MHAUIPNU[22]算法從具有正負效用數據庫中挖掘HAUIs，提出更嚴格的tubpn上界模型和新的列表結構TUBPNU-List，基于上界和負效用相關屬性設計三種剪枝策略。

3.4小結

本節從模式劃分的角度分析并總結了含有負效用的HUPM方法，包含全集模式、精簡模式和融合模式的算法。圖2從模式劃分角度總結分析了含有負效用的模式挖掘算法。

此外，本小結比較了各種劃分類別中具有代表性的算法，并在數據集上分析了部分算法的時空效率。全集模式旨在挖掘出所有滿足最小效用閾值的項集，本節將其分為基于模式增長的和基于列表的算法。基于模式增長的算法可降低數據庫掃描成本，以UP-GNIV[11]算法為代表，在運行時間和擴展性方面均優于基于先驗的HUINIV-Mine[12]算法，但遞歸構造條件模式樹挖掘項集仍需花費大量時間；基于列表的算法引入了垂直的表結構加快了挖掘速度。例如，FHN[60]算法在時空效率均優于UP-GNIV算法，但其局限性在于仍需要大量內存維護列表信息。針對全集模式生成的候選項集數量大、項集冗余和最小效用閾值設置困難的問題，提出了精簡模式。本節將其分為Top-k模式和閉合模式。TopHUI[13]算法首次在Top-k模式中考慮負項，解決了最小效用閾值設置困難的問題。閉合模式通過去除冗余項集克服了傳統HUPM的局限性，CHN[65]算法首次在閉合模式中考慮負項，經實驗，該算法在密集和大部分稀疏數據集上均優于FHN[60]算法，速度提升了約44.8倍且內存需求為FHN算法的7.4%。此外，含有負效用的模式還與其它模式結合，例如On-shelf高效用模式、序列高效用模式和高平均效用模式等。

以上算法在實際應用中，時空效率尤為重要，但其通常受數據集的影響。實驗中常見的通用數據集大致分為密集和稀疏兩類，密集數據集包含Mushroom、Accidents和Chess等，稀疏數據集包含Retail和Kosarak等。在密集數據集Chess上，FHN[60]算法的執行速度是HUINIV-Mine[12]算法的500倍，內存消耗為HUINIV-Mine算法的0.4%，其主要原因為在于HUINIV-Mine算法多次掃描數據庫，而FHN算法僅需兩次掃描數據庫且應用更嚴格的上界，此外，該方法不產生候選項集，故無需花費大量內存維護候選項集；EHIN[29]算法在Chess數據集上的表現優于FHN算法，在minutil=120k時，算法速度比為25∶1，主要原因在于密集數據集中存在大量重復項集，該算法采用投影合并技術能有效縮減數據庫規模，而FHN算法通過組合較小的項目集來探索項目集的搜索空間，故性能不佳。在稀疏數據集Retail上，FHN算法優于THN[63]算法和CHN[65]算法，由于零售數據集包含大量不同的項，事務合并需要花費大量時間來合并事務，故THN[63]和CHN[65]算法在高度稀疏的數據集上表現不佳，但內存消耗依然很少。

最后，以經典算法FHN為例，分析含有負效用的高效用模式挖掘算法的時間復雜度，它的時間復雜度主要體現在數據庫掃描、1-項集列表構建、EUCS的構建以及遞歸搜索方面。設n為數據庫中的事務總數，m為不同項的個數，w為平均事務長度。首次掃描數據庫的時間復雜度為O（nw），此后進行單個項的排序，時間復雜度為O（mlog2m）。第二次掃描數據的過程中，同時構建所有1-項集效用列表和EUCS結構，設l為項的個數，時間復雜度分別為O（ln）和O（nl（l－1）/2）。挖掘項集的時間復雜度為O（2l－1－l），故總的時間復雜度為以上各個階段的時間復雜度之和，即O（2l）。由于EUCS結構占用少量內存空間，空間復雜度為O（l2）。

4擴展高效用模式

隨著研究不斷深入，效用挖掘領域也產生了大量新興高效用模式。本節主要介紹模糊高效用模式、相關高效用模式、占用高效用模式和跨層級高效用模式。

4.1模糊高效用模式

效用挖掘是指在事務數據庫中找到HUIs，由于無法反映項目之間的數量關系和利潤的模糊程度，引入定量數據庫和模糊集理論。例如通過模式{牛奶：1， 面包：5}，用戶難以理解商品售賣情況的好壞。通過引入模糊概念將數量關系對應于語言的模糊程度，分別將牛奶和面包的售賣情況視為“低”量水平和“中”量水平，這有利于營銷者理解并制定銷售計劃。本節總結了模糊高效用模式，包括基于傳統的和基于智能優化的算法。HUFI-Miner[17]算法將量化值轉化為模糊區域并利用外部效用信息表計算模糊項集效用以找到模糊高效用項集（High Fuzzy Utility Itemsets， HFUIs）。同時，利用隸屬函數對應語言域值和隸屬度值評價項集的模糊效用。TPFU[71]算法引入模糊效用上界模型來維持模糊集的DC屬性，同時引入模糊集的最小算子概念來評估項集的模糊效用，在兩個階段中尋找所有的HFUIs。FUIM[72]算法設計了一個模糊效用列表以實現快速挖掘，并利用實際模糊效用與剩余效用之和約束搜索空間。Hong等人提出基于樹挖掘算法[73]，引入FP-Tree結構來維護候選項集信息。經過實驗表明，該方法在時間和內存消耗上均優于TP-TFU。

上述方法通過改變數據結構或設計剪枝策提高挖掘性能，而面對大數據環境，仍存在局限性。研究者們結合智能優化算法提出了一些新穎的挖掘方法。Wu等人將進化計算引入該領域，首次提出了基于遺傳算法框架的HUFI-GA[74]算法，該算法對模糊項編碼來表示為遺傳空間的染色體，通過選擇、交叉和變異運算并引入蒸發策略以發現更多潛在的HFUIs。EA-HUFIM[75]算法引入大型數據庫最大效用的模糊項目集（High Database-max utility Fuzzy Itemset， HDFI）概念和精英學習策略。在突變運算中，向理想的方向產生候選項并刪除不必要的后代，此外，該算法還應用了模糊映射和事務映射避免多余運算。

4.2相關高效用模式

由于在HUPM中主要考慮項集的效用，而很少關注項目之間的相關性，故挖掘結果中存在大量無意義的模式。以購物籃數據為例，項集中某項具有較高的利潤會使得項集整體是高利潤的，但這種罕見購買現象的出現不足以推薦與其一起購買的商品，故此時的銷售決策和推銷建議往往是無效的。例如{電腦，面包}是一個HUI，由于電腦的價格較高，則與任何商品組合都可能成為HUI。此時向買電腦的客戶推薦面包是不合適的，因為它們很少一起出售。為解決這類問題，結合項集效用和相關性，研究者們提出了相關高效用模式，其中既是HUIs且相關性度量值不小于最小效用閾值的項集被定義為相關高效用項集（Correlated High Utility Itemsets， CoHUIs）。常見的相關性度量有All-confidence[76]、Bond[77]和Kulc[78]等。本節依據相關高效用挖掘算法采用的關鍵技術，分為基于列表的和其他的技術。

在現有的相關高效用模式挖掘算法中，大多為基于效用列表的方法。Fournier-Viger等人提出FCHM[18]算法來挖掘CoHUIs，并衍生出FCHMall-confidence[79]和FCHMbond[79]兩個算法版本，該算法集成了多種策略以有效地發現CoHUIs。實驗證明，算法比FHM快兩個數量級以上且舍棄掉大量弱相關的HUIs。Gan等人提出基于Kulc度量的CoUPM[80]算法，采用含有支持度計數的效用列表計算相關性。基于此結構，引入基于Kulc值的有序向下閉包屬性的修剪策略（pruning strategy using the Sorted downward closure Property of Kulc value， SPK）和基于效用上界的剪枝策略（pruning strategy using the Upper Bound on Utility， UBU）。ULB-CHMiner[81]算法引入效用列表緩沖區結構，通過內存重用策略降低內存消耗。單階段算法CoHAI-miner[21]結合平均效用度量，提出SAU-list結構存儲項集信息并設計三種剪枝策略挖掘相關的HAUIs。此外，考慮項集數量對效用挖掘的影響，Nouioua等人提出CHUQI-Miner[82]算法挖掘相關的定量高效用項目集，構建基于Q-項集的事務加權效用共現結構（Transaction weighted utility of Q-items Co-occurrence based Structure， TQCS），同時，開發出用于修剪非相關Q-項集的其它策略，在一定程度上刪減了弱相關的模式且保留了HUIs之間的數量關系。

除了上述方法外，還有基于投影、樹等其它技術的方法。基于數據庫投影技術，Gan等人提出CoHUIM[83]算法挖掘非冗余的CoHUIs，該算法依據Kulc的排序向下閉包特性和剩余效用剪枝。Saeed等人提出了一種基于效用樹結構的ECoHUPM[84]算法以挖掘具有強相關性項的高效用模式，該算法提出兩種剪枝策略，基于效用與路徑效用之和的上界屬性（Upper Bound property based on summation of Utility and the Path Utilities， UBUPU）剪枝策略和基于節點效用的下界屬性（Lower Bound property based on the Node Utility， LBNU）剪枝策略減少搜索空間并提高挖掘性能。

4.3其他新興高效用模式

占用率度量用于評估模式在事務中的占比狀況，從而得到代表性模式。傳統的HUPM未評估模式占用情況，例如，即使模式X出現在多個事務中，但是在單個事務中并未占用該事務大部分效用，故無法真正代表這些事務。此時進行模式推薦可能是誤導性的。為解決上述問題，結合占用度量和效用度量，提出效用占用概念和高效用占用模式挖掘。

OCEAN[19]算法首次引入效用占用度量評估模式對事務總效用的貢獻，主要使用每個事務中的模式相對效用比率來描述用戶習慣。但模式挖掘不完整且效率不高。HUOPM[85]算法結合用戶興趣、模式頻率和效用占用率提取模式，引入效用-占用列表（Utility-Occupancy List， UO-List）和頻率-效用表（Frequency-Utility Table， FU-Table）兩種緊湊結構，無需生成候選就能得到模式的實際效用占用，有效找到完整的占用高效用模式。

UHUOPM[86]算法考慮不確定的復雜數據，提出概率效用占用列表（Probability-Utility-Occupancy List， PUO-List）和概率頻率效用表（Probability-Frequency-Utility Table， PFU-List）降低數據庫掃描成本，首次在不確定數據庫中挖掘占用高效用模式。

隨著研究的不斷深入，有研究者將分類法與高效用項集挖掘任務相結合。例如，藥酒和參茸都屬于營養保健品，巧克力和果凍等都屬于糖果，且營養保健品和糖果均為食品的子類別。分類法的引入可以在語義上將項目泛化產生廣義項集（如例子中的食品、營養保健品和糖果）。由于傳統的HUPM沒有考慮項目的分類法，只能挖掘分類樹中的最低層項集（藥酒、參茸、巧克力和果凍），即使營養保健品和糖果這些項是HUI，也無法被發現，故提出了在多個項目級別上挖掘高效用項集的新任務，稱為跨層級的高效用模式挖掘。

ML-HUI Miner[87]算法在多個抽象層級上挖掘，將提取高效用的不同粒度級別的項集定義為廣義高效用項集（Generalized High Utility Itemset， GHUIs）。但此算法只能找到相同抽象級別上的HUIs，無法找到分布在不同級別上的有意義模式且未利用分類關系縮小搜索空間。為解決上述問題，Fournier-Viger等人定義了更一般的跨層級的HUPM問題，并提出名為CLH-Miner[20]的算法。該算法允許挖掘結果中混合不同層級的項。同時在連接擴展的基礎上，引入項集分類擴展方式并提出分類效用列表結構保存項集X的效用信息以及指向分類法X的孩子結點指針。此外，采用剩余效用剪枝策略減少項集的分類擴展連接。TKC[88]算法無需設置固定的最小效用閾值，通過提升最小效用閾值輸出前K個符合條件的模式。隨后，Tung等人提出了FEACP[89]算法，該算法擴展了緊湊的上界，通過本地效用和子樹效用來縮小搜索空間并將主要項集和次要項集的概念擴展到廣義項集以挖掘跨層級的項集。

4.4小結

近年來，大量新穎的高效用模式類型涌現，針對現實生活中不同應用場景，學者們還提出了多種擴展高效用模式。為解決傳統HUPM在定量數據集上挖掘無法用語言模糊程度表達數量關系的問題，故提出了模糊高效用模式，主要采用模糊隸屬函數處理項集效用，將交易中每個項目的數量也被轉換為更適合人類思維的語言區域，通過語言的模糊程度評價項集的模糊效用。相關高效用模式解決了傳統HUPM結果集中項之間弱相關的問題，通過采用不同的相關度量，有效刪減弱相關的項集并降低銷售決策中的誤導性風險。占用高效用模式結合效用度量和占用度量，刪減模式占用率較低的事務，因此有效評估了模式的占用情況并從中提取更加有意義的模式。此外，結合分類法信息，在多個抽象級別上挖掘HUIs，提出跨層級的高效用模式。

5結束語

本文對現有衍生高效用模式挖掘算法進行了系統綜述，概述了衍生高效用模式所解決的問題和發展現狀，歸納了各類衍生高效用模式并通過圖表詳細地給出算法的數據結構、剪枝算法、對比算法以及優缺點等。由于數據的多態性和需求的復雜性，衍生高效用模式在不斷發展和完善以適應現階段的需求，未來該領域仍存在諸多研究機會。

1） 基于智能優化算法的衍生高效用模式

隨著項的多樣性和數據集大小不斷增加，在先前的工作中存在“組合爆炸問題”，因此發現所需信息的搜索空間是巨大的，故先前方法很難在具有大量記錄和項目的數據庫中應用。而面對龐大的數據量，智能優化算法能根據適應度函數在一定時間內快速找到最優解或近似最優解，為突破傳統HUPM挖掘算法的性能瓶頸提供新的解決思路，現已在HUPM問題上初見成效，而對于更為復雜的應用場景和龐大的數據量，有必要在衍生模式中引入智能優化算法提高挖掘效率。在未來的工作中，考慮到智能優化算法快速挖掘的特性，可將其引入以挖掘高平均效用模式、含負效用的高效用模式等復雜的衍生模式。

2） 跨層級的模式挖掘

現階段跨層級模式針對多種數據形態（如增量數據、數據流、序列等）和不同應用場景（如隱私保護等）的研究較少，該領域仍有很大發展潛力。此外，挖掘出的跨層級項集，雖然包含有用的分類信息，但面對較深的分類樹，結果集中會出現過于模糊的項集，這同樣不利于決策和推薦。在未來的工作中，應設計一種方法來約束跨層級數，從而減少冗余信息的挖掘，同時將分類法與其它模式結合用于處理更為復雜的問題，并在動態數據中搜索有趣的跨層級模式。

3） 并行分布式的高效用模式挖掘

目前大多數挖掘算法均集中于單個機器，處理大型數據集的能力有限，從而影響算法執行效率。而并行計算允許多個任務同時執行，多核并行計算架構能極大提升HUPM算法性能。隨著商業數據集的快速增長，基于分布式的挖掘可以進一步擴大挖掘任務以適應大數據環境，因此有必要利用Hadoop或者Spark等分布式平臺開發有效的挖掘算法來揭示決策所需的知識，使得算法能在大型數據集上實現更深層次的并行。

參考文獻

[1] AGRAWAL R， IMIELIN＇SKI T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data， Washington， USA， 1993： 207-216.

[2] FOURNIER-VIGER P， WU C W， ZIDA S， et al. FHM： faster high-utility itemset mining using estimated utility co-occurrence pruning[C]//Proceedings of the International Symposium on Methodologies for Intelligent Systems， Roskilde， Denmark， 2014： 83-92.

[3] HONG T P， LEE C H， WANG S L. Effective utility mining with the measure of average utility[J]. Expert Systems with Applications， 2011， 38（7）： 8259-8265.

[4] HONG T P， LEE C H， WANG S L. Mining high average-utility itemsets[C]//Proceedings of the 2009 IEEE International Conference on Systems， Man and Cybernetics， San Antonio， USA， 2009： 2526-2530.

[5] LIU Y， LIAO W K， CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets[C]//Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining， Hanoi， Vietnam， 2005： 689-695.

[6] LAN G C， HONG T P， TSENG V S. A projection-based approach for discovering high average-utility itemsets[J]. Journal of Information Science and Engineering， 2012， 28（1）： 193-209.

[7] LIN C W， HONG T P， LU W H. Efficiently mining high average utility itemsets with a tree structure[C]//Proceedings of the Asian Conference on Intelligent Information and Database Systems， Hue City， Vietnam， 2010： 131-139.

[8] LIN J C W， LI T， FOURNIER-VIGER P， et al. An efficient algorithm to mine high average-utility itemsets[J]. Advanced Engineering Informatics， 2016， 30（2）： 233-243.

[9] YUN U， KIM D. Mining of high average-utility itemsets using novel list structure and pruning strategy[J]. Future Generation Computer Systems， 2017， 68： 346-360.

[10] 王敬華， 羅相洲， 吳倩. 基于效用表的快速高平均效用挖掘算法[J]. 計算機應用， 2016， 36（11）： 3062-3066.

WANG J H， LUO X Z，WU Q. Fast high average-utility itemset mining algorithm based on utility-list structure[J]. Journal of Computer Applications， 2016， 36（11）： 3062-3066.

[11] SUBRAMANIAN K， KANDHASAMY P. UP-GNIV： an expeditious high utility pattern mining algorithm for itemsets with negative utility values[J]. International Journal of Information Technology and Management， 2015， 14（1）： 26-42.

[12] CHU C J， TSENG V S， LIANG T. An efficient algorithm for mining high utility itemsets with negative item values in large databases[J]. Applied Mathematics and Computation， 2009， 215（2）： 767-778.

[13] GAN W， WAN S， CHEN J， et al. TopHUI： top-k high-utility itemset mining with negative utility[C]//Proceedings of the 2020 IEEE International Conference on Big Data， Atlanta， USA，2020： 5350-5359.

[14] HONG T P， LEE C H， WANG S L. An incremental mining algorithm for high average-utility itemsets[C]//Proceedings of the 2009 10th International Symposium on Pervasive Systems， Algorithms， and Networks， Kaohsiung， China， 2009： 421-425.

[15] 張妮， 韓萌， 王樂， 等. 基于滑動窗口的含負項高效用模式挖掘方法[J]. 鄭州大學學報（理學版）， 2022， 54（4）： 55-63.

ZHANG N， HAN M， WANG L，et al. Mining high utility patterns with negative utility over data stream[J]. Journal of Zhengzhou University（Natural Science Edition）， 2022， 54（4）： 55-63.

[16] GAN W， LIN J C W， FOURNIER-VIGER P， et al. Mining high-utility itemsets with both positive and negative unit profits from uncertain databases[C]//Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining， Jeju， Korea， 2017： 434-446.

[17] WANG C M， CHEN S H， HUANG Y F. A fuzzy approach for mining high utility quantitative itemsets[C]//Proceedings of the 2009 IEEE International Conference on Fuzzy Systems， Jeju， Korea，2009： 1909-1913.

[18] FOURNIER-VIGER P， LIN J C W， DINH T， et al. Mining correlated high-utility itemsets using the bond measure[C]//Proceedings of the International Conference on Hybrid Artificial Intelligence Systems， Seville， Spain， 2016： 53-65.

[19] SHEN B， WEN Z， ZHAO Y， et al. Ocean： fast discovery of high utility occupancy itemsets[C]//Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining， Auckland， New Zealand， 2016： 354-365.

[20] FOURNIER-VIGER P， WANG Y， LIN J C W， et al. Mining cross-level high utility itemsets[C]//Proceedings of the International Conference on Industrial， Engineering and Other Applications of Applied Intelligent Systems， Kitakyushu， Japan， 2020： 858-871.

[21] SETHI K K， RAMESH D. Correlated high average-utility itemset mining[C]//Proceedings of the International Conference on? Evolution in Computational Intelligence，Surathkal， India， 2021： 485-497.

[22] YILDIRIM I， CELIK M. Mining high-average utility itemsets with positive and negative external utilities[J]. New Generation Computing， 2020， 38（1）： 153-186.

[23] SINGH K， SINGH S S， KUMAR A， et al. High utility itemsets mining with negative utility value：a survey[J]. Journal of Intelligent & Fuzzy Systems， 2018， 35（6）： 6551-6562.

[24] SINGH K， KUMAR R， BISWAS B. High average-utility itemsets mining： a survey[J]. Applied Intelligence， 2022， 52（4）： 3901-3938.

[25] 張妮， 韓萌， 王樂， 等. 基于正負效用劃分的高效用模式挖掘方法綜述[J]. 計算機應用， 2022， 42（4）： 999-1010.

ZHANG N， HAN M， WANG L， et al. Survey of high utility pattern mining methods based on positive and negative utility division[J]. Journal of Computer Applications， 2022， 42（4）： 999-1010.

[26] ALMOQBILY R S， RAUF A， QURADAA F H. A survey of correlated high utility pattern mining[J]. IEEE Access， 2021， 9： 42786-42800.

[27] 李慕航， 韓萌， 陳志強， 等. 面向復雜高效用模式的挖掘算法綜述[J]. 廣西師范大學學報（自然科學版）， 2022， 40（3）： 13-30.

LI M H， HAN M， CHEN Z Q， et al. Survey of algorithms oriented to complex high utility pattern mining[J]. Journal of Guangxi Normal University （Natural Science Edition）， 2022， 40（3）： 13-30.

[28] LIN J C W， FOURNIER-VIGER P， GAN W. FHN： an efficient algorithm for mining high-utility itemsets with negative unit profits[J]. Knowledge-Based Systems， 2016， 111： 283-298.

[29] SINGH K， SHAKYA H K， SINGH A， et al. Mining of high-utility itemsets with negative utility[J]. Expert Systems， 2018， 35（6）： e12296.

[30] AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules in large databases[C]//Proceedings of the 20th International Conference on Very Large Data Bases， Santiago de Chile， Chile， 1994： 487-499.

[31] LIN J C W， LI T， FOURNIER-VIGER P， et al. Efficient mining of high average-utility itemsets with multiple minimum thresholds[C]//Proceedings of the Industrial Conference on Data Mining， New York， USA， 2016： 14-28.

[32] WU J M T， TENG Q， LIN J C W， et al. Updating high average-utility itemsets with pre-large concept[J]. Journal of Intelligent & Fuzzy Systems， 2020， 38（5）： 5831-5840.

[33] 任家東， 王倩， 王蒙. 一種基于頻繁模式有向無環圖的數據流頻繁模式挖掘算法[J]. 燕山大學學報， 2011， 35（2）： 115-120.

REN J D， WANG Q， WANG M. An algorithm based on frequent patterns directed acyclic graph for mining frequent patterns from data stream[J]. Journal of Yanshan University， 2011， 35（2）： 115-120.

[34] 姜玫. 平均高效用項集挖掘算法研究[D]. 大連： 大連理工大學， 2013.

JIANG M. Research on average high utility itemsets mining algorithm[D]. Dalian： Dalian University of Technology， 2013.

[35] LU T， VO B， NGUYEN H T， et al. A new method for mining high average utility itemsets[C]//Proceedings of the IFIP International Conference on Computer Information Systems and Industrial Management， Ho Chi Minh City， Vietnam， 2015： 33-42.

[36] KIM D， YUN U. Efficient algorithm for mining high average-utility itemsets in incremental transaction databases[J]. Applied Intelligence， 2017， 47（1）： 114-131.

[37] LIN J C W， REN S， FOURNIER-VIGER P， et al. Efficiently updating the discovered high average-utility itemsets with transaction insertion[J]. Engineering Applications of Artificial Intelligence， 2018， 72： 136-149.

[38] YUN U， KIM D， RYANG H， et al. Mining recent high average utility patterns based on sliding window from stream data[J]. Journal of Intelligent & Fuzzy Systems， 2016， 30（6）： 3605-3617.

[39] YUN U， KIM D， YOON E， et al. Damped window based high average utility pattern mining over data streams[J]. Knowledge-Based Systems， 2018， 144： 188-205.

[40] WU Y， LEI R， LI Y， et al. HAOP-Miner： self-adaptive high-average utility one-off sequential pattern mining[J]. Expert Systems with Applications， 2021， 184： 115449.

[41] WU Y， GENG M， LI Y， et al. HANP-Miner： high average utility nonoverlapping sequential pattern mining[J]. Knowledge-Based Systems， 2021， 229： 107361.

[42] LIN J C W， REN S， FOURNIER-VIGER P， et al. A fast algorithm for mining high average-utility itemsets[J]. Applied Intelligence， 2017， 47（2）： 331-346.

[43] LIN J C W， REN S， FOURNIER-VIGER P， et al. EHAUPM： efficient high average-utility pattern mining with tighter upper bounds[J]. IEEE Access， 2017， 5： 12927-12940.

[44] WU J M T， LIN J C W， PIROUZ M， et al. TUB-HAUPM： tighter upper bound for mining high average-utility patterns[J]. IEEE Access， 2018， 6： 18655-18669.

[45] KIM H， YUN U， BAEK Y， et al. Efficient list based mining of high average utility patterns with maximum average pruning strategies[J]. Information Sciences， 2021， 543： 85-105.

[46] LIN J C W， REN S， FOURNIER-VIGER P. MEMU： more efficient algorithm to mine high average-utility patterns with multiple minimum average-utility thresholds[J]. IEEE Access， 2018， 6： 7593-7609.

[47] SETHI K K， RAMESH D. High average-utility itemset mining with multiple minimum utility threshold： a generalized approach[J]. Engineering Applications of Artificial Intelligence， 2020， 96： 103933.

[48] WU T Y， LIN J C W， SHAO Y， et al. Updating the discovered high average-utility patterns with transaction insertion[C]//Proceedings of the International Conference on Genetic and Evolutionary Computing， Kaohsiung， China， 2017： 66-73.

[49] ZHANG B， LIN J C W， SHAO Y， et al. Maintenance of discovered high average-utility itemsets in dynamic databases[J]. Applied Sciences， 2018， 8（5）： 769.

[50] LIN J C W， SHAO Y， FOURNIER-VIGER P， et al. Maintenance algorithm for high average-utility itemsets with transaction deletion[J]. Applied Intelligence， 2018， 48（10）： 3691-3706.

[51] LAN G C， HONG T P， TSENG V S. Efficiently mining high average-utility itemsets with an improved upper-bound strategy[J]. International Journal of Information Technology & Decision Making， 2012， 11（5）： 1009-1030.

[52] YILDIRIM I， CELIK M. FIMHAUI： fast incremental mining of high average-utility itemsets[C]//Proceedings of the 2018 International Conference on Artificial Intelligence and Data Processing， Malatya， Turkey， 2018： 1-9.

[53] THILAGU M， NADARAJAN R. Efficiently mining of effective web traversal patterns with average utility[J]. Procedia Technology， 2012， 6： 444-451.

[54] 李霆. 基于不確定數據的高平均效用序列模式挖掘算法的研究[D]. 深圳： 哈爾濱工業大學， 2016.

LI T. Ming high average utility sequential patterns from uncertain databases[D]. Shenzhen： Herbin Institute of Technology， 2016.

[55] TRUONG T， DUONG H， LE B， et al. Efficient vertical mining of high average-utility itemsets based on novel upper-bounds[J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 31（2）： 301-314.

[56] TRUONG T， DUONG H， LE B， et al. Efficient high average-utility itemset mining using novel vertical weak upper-bounds[J]. Knowledge-Based Systems， 2019， 183： 104847.

[57] PHUONG N， DUY N D. Constructing a new algorithm for high average utility itemsets mining[C]//Proceedings of the 2017 International Conference on System Science and Engineering， Ho Chi Minh City， Vietnam， 2017： 273-278.

[58] SINGH K， KUMAR A， SINGH S S， et al. EHNL： an efficient algorithm for mining high utility itemsets with negative utility value and length constraints[J]. Information Sciences， 2019， 484： 44-70.

[59] LI H F， HUANG H Y， LEE S Y. Fast and memory efficient mining of high-utility itemsets from data streams： with and without negative item profits[J]. Knowledge and Information Systems， 2011， 28（3）： 495-522.

[60] FOURNIER-VIGER P. FHN： efficient mining of high-utility itemsets with negative unit profits[C]//Proceedings of the International Conference on Advanced Data Mining and Applications， Guilin， China， 2014： 16-29.

[61] KRISHNAMOORTHY S. Efficiently mining high utility itemsets with negative unit profits[J]. Knowledge-Based Systems， 2018， 145： 1-14.

[62] 陳麗娟. 含有負項值的高效用項集挖掘算法研究[D]. 福州： 福州大學， 2018.

CHEN L J. Research on algorithm for mining high utility itemset with negative item values[D]. Fuzhou： Fuzhou University， 2018.

[63] SUN R， HAN M， ZHANG C， et al. Mining of top-k high utility itemsets with negative utility[J]. Journal of Intelligent & Fuzzy Systems， 2021， 40（3）： 5637-5652.

[64] ASHRAF M， ABDELKADER T， RADY S， et al. TKN： an efficient approach for discovering top-k high utility itemsets with positive or negative profits[J]. Information Sciences， 2022， 587： 654-678.

[65] SINGH K， SINGH S S， KUMAR A， et al. CHN： an efficient algorithm for mining closed high utility itemsets with negative utility[J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 1（1）： 99-113.

[66] LAN G C， HONG T P， HUANG J P， et al. On-shelf utility mining-with negative item values[J]. Expert Systems with Applications， 2014， 41（7）： 3450-3459.

[67] FOURNIER-VIGER P， ZIDA S. FOSHU： faster on-shelf high utility itemset mining--with or without negative unit profit[C]//Proceedings of the the 30th Annual ACM Symposium on Applied Computing， Salamanca， Spain， 2015： 857-864.

[68] DAM T L， LI K， FOURNIER-VIGER P， et al. An efficient algorithm for mining top-k on-shelf high utility itemsets[J]. Knowledge and Information Systems， 2017， 52（3）： 621-655.

[69] RADKAR A N， PAWAR S. Mining high on-shelf utility itemsets with negative values from dynamic updated database[J]. International Journal of Advanced Studies in Computer Science and Engineering， 2015， 5（6）： 27-33.

[70] XU T， DONG X， XU J， et al. Mining high utility sequential patterns with negative item values[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2017， 31（10）： 1750035.

[71] LAN G C， HONG T P， LIN Y H， et al. Fuzzy utility mining with upper-bound measure[J]. Applied Soft Computing， 2015， 30： 767-777.

[72] WAN S， GAN W， GUO X， et al. FUIM： fuzzy utility itemset mining [EB/OL].（2021-10-31）[2022-09-05].https：//arxiv.org/abs/2111.00307.

[73] HONG T P， LIN C Y， HUANG W M， et al. Mining temporal fuzzy utility itemsets by tree structure[C]//Proceedings of the 2019 IEEE International Conference on Big Data， Los Angeles， USA， 2019： 2659-2663.

[74] WU J M T， LIN J C W， FOURNIER-VIGER P， et al. A ga-based framework for mining high fuzzy utility itemsets[C]//Proceedings of the 2019 IEEE International Conference on Big Data， Los Angeles，USA， 2019： 2708-2715.

[75] YANG F， MU N， LIAO X， et al. EA-HUFIM： Optimization for fuzzy-based high-utility itemsets mining[J]. International Journal of Fuzzy Systems， 2021， 23（6）： 1652-1668.

[76] OMIECINSKI E R. Alternative interest measures for mining associations in databases[J]. IEEE Transactions on Knowledge and Data Engineering， 2003， 15（1）： 57-69.

[77] BOUASKER S， BEN YAHIA S. Key correlation mining by simultaneous monotone and anti-monotone constraints checking[C]//Proceedings of the Proceedings of the 30th Annual ACM Symposium on Applied Computing， Salamanca， Spain，2015： 851-856.

[78] WU T， CHEN Y， HAN J. Re-examination of interestingness measures in pattern mining： a unified framework[J]. Data Mining and Knowledge Discovery， 2010， 21（3）： 371-397.

[79] FOURNIER-VIGER P， ZHANG Y， LIN J C W， et al. Mining correlated high-utility itemsets using various measures[J]. Logic Journal of the IGPL， 2020， 28（1）： 19-32.

[80] GAN W， CHUN WEI J， CHAO H C， et al. CoUPM： Correlated utility-based pattern mining[C]//Proceedings of the 2018 IEEE International Conference on Big Data， Seattle， USA， 2018： 2607-2616.

[81] WU L， XIE G. Mining correlated high utility itemsets from MOOC data[C]//Proceedings of the 2021 6th International Conference on Big Data and Computing，Shenzhen， China， 2021： 49-54.

[82] NOUIOUA M， FOURNIER-VIGER P， QU J F， et al. CHUQI-Miner： mining correlated quantitative high utility itemsets[C]//Proceedings of the 2021 International Conference on Data Mining Workshops， Auckland， New Zealand， 2021： 599-606.

[83] GAN W， LIN J C W， FOURNIER-VIGER P， et al. Extracting non-redundant correlated purchase behaviors by utility measure[J]. Knowledge-Based Systems， 2018， 143： 30-41.

[84] SAEED R， RAUF A， QURADAA F H， et al. Efficient utility tree-based algorithm to mine high utility patterns having strong correlation[J]. Complexity， 2021， 2021： 7310137.

[85] GAN W， LIN J C W， FOURNIER-VIGER P， et al. HUOPM： high-utility occupancy pattern mining[J]. IEEE Transactions on Cybernetics， 2019， 50（3）： 1195-1208.

[86] CHEN C M， CHEN L， GAN W， et al. UHUOPM： High utility occupancy pattern mining in uncertain data[C]//Proceedings of the 2020 IEEE International Conference on Systems， Man， and Cybernetics， Toronto， Canada， 2020： 3066-3071.

[87] CAGLIERO L， CHIUSANO S， GARZA P， et al. Discovering high-utility itemsets at multiple abstraction levels[C]//Proceedings of the European Conference on Advances in Databases and Information Systems， Nicosia， Cyprus， 2017： 224-234.

[88] NOUIOUA M， WANG Y， FOURNIER-VIGER P， et al. Tkc： Mining top-k cross-level high utility itemsets[C]//Proceedings of the 2020 International Conference on Data Mining Workshops， Sorrento， Italy， 2020： 673-682.

[89] TUNG N， NGUYEN L T， NGUYEN T D， et al. Efficient mining of cross-level high-utility itemsets in taxonomy quantitative databases[J]. Information Sciences， 2022， 587： 41-62.

Survey of derived high utility pattern mining algorithms

Abstract： In the field of data mining， the task of high utility pattern mining has a high theoretical research value and a wide range of practical application scenarios. A series of derived high utility patterns are proposed for variable applications. Firstly， the high average utility pattern mining algorithms are discussed from the perspective of key technologies， mainly including Apriori-based， tree-based， list-based， projection-based and data structure-based algorithms. Secondly， high utility pattern mining algorithms containing negative utility based on complete set， concise set and integrated pattern are analytically discussed. Then， the extended high utility pattern algorithms are outlined and summarized from three aspects， including fuzzy high utility patterns， correlated high utility patterns and other emerging high utility patterns. Finally， in view of the shortcomings of the current research direction， the next research directions are given.

Keywords： derived high utility pattern; high average utility pattern; negative utility; fuzzy high utility pattern; correlated high utility pattern; survey