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

摘要：在數(shù)據(jù)挖掘領(lǐng)域中，高效用模式挖掘任務(wù)具有較高的理論研究?jī)r(jià)值和廣泛的實(shí)際應(yīng)用場(chǎng)景。針對(duì)多變的應(yīng)用場(chǎng)合，提出了一系列衍生高效用模式。首先從關(guān)鍵技術(shù)的角度對(duì)高平均效用模式挖掘算法進(jìn)行了分類論述，主要包括基于先驗(yàn)、基于樹、基于列表、基于投影和基于數(shù)據(jù)格式的方法。其次，分析討論了基于全集、精簡(jiǎn)集以及融合模式的含有負(fù)效用的高效用模式挖掘算法。再次，從模糊高效用模式、相關(guān)高效用模式和其他新興高效用模式三個(gè)方面概述和總結(jié)了擴(kuò)展高效用模式算法。最后，針對(duì)現(xiàn)階段研究方向的不足，給出下一步的研究方向。

關(guān)鍵詞：衍生高效用模式；高平均效用模式；負(fù)效用；模糊高效用模式；相關(guān)高效用模式；綜述

中圖分類號(hào)： TP311.13文獻(xiàn)標(biāo)識(shí)碼： ADOI：10.3969/j.issn.1007-791X.2024.02.005

0引言

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

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

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

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

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

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

因此，本文從不同的角度切入，對(duì)多種衍生高效用模式進(jìn)行全面分析總結(jié)并進(jìn)行優(yōu)缺點(diǎn)對(duì)比。衍生高效用模式分類框架如圖1所示。本文貢獻(xiàn)如下：

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

2） 首次從關(guān)鍵技術(shù)的角度對(duì)HAUPM算法進(jìn)行分類總結(jié)和優(yōu)缺點(diǎn)對(duì)比；從全集、精簡(jiǎn)集以及融合模式的角度對(duì)含有負(fù)效用模式進(jìn)行分類總結(jié)和優(yōu)缺點(diǎn)對(duì)比；最后，對(duì)擴(kuò)展高效用模式挖掘算法進(jìn)行分析歸納。

3） 根據(jù)目前研究不足，給出下一步研究方向，包括智能優(yōu)化算法在衍生高效用模式挖掘中應(yīng)用、結(jié)合項(xiàng)目分類法的跨層級(jí)模式挖掘和并行分布式挖掘等。

1相關(guān)概念和定義

為了清楚地描述部分衍生模式挖掘問題，給出一個(gè)事務(wù)數(shù)據(jù)庫(kù)和一個(gè)效用表，如表1和表2所示。事務(wù)數(shù)據(jù)庫(kù)是一組事務(wù)的集合，定義為D={T1，T2，…，Tn}，I={i1，i2，…，im}為一組項(xiàng)的集合，其中對(duì)于每個(gè)事務(wù)TC，TC∈I且具有唯一的標(biāo)識(shí)TID。每一個(gè)項(xiàng)目i均有一個(gè)購(gòu)買數(shù)量in（i，TC）（內(nèi)部效用）和效用表（其中存儲(chǔ)了項(xiàng)目到單位利潤(rùn)的映射）中項(xiàng)i的單位利潤(rùn)ex（i）（外部效用），即表1和表2中數(shù)字。

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

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

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

例：數(shù)據(jù)庫(kù)中有6條事務(wù)， 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（事務(wù)中項(xiàng)/項(xiàng)集的平均效用）[4]項(xiàng)i在事務(wù)TC中的平均效用記為au（i，TC），定義為au（i，TC）=u（i，TC）。

例：項(xiàng)集{AC}在事務(wù)T6中的平均效用為au（AC，T6）=2。

定義8（事務(wù)最大效用）[4]事務(wù)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（高平均效用上限項(xiàng)集）[4]如果auub（X）≥minutil，項(xiàng)集X為高平均效用上限項(xiàng)集，記為HAUUBI。

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

例： 設(shè)最小效用閾值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，項(xiàng)集{AC}和{AE}均為HAUUBI。由定義11，項(xiàng)集{AC}不是HAUI，{AE}是HAUI。

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

2高平均效用模式

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

2.1基于先驗(yàn)的方法

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

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

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

2.2基于樹的方法

由于基于先驗(yàn)的算法需多次掃描數(shù)據(jù)庫(kù)生成候選項(xiàng)集并驗(yàn)證，因此花費(fèi)高昂的時(shí)空成本。故研究者們提出了基于樹的挖掘算法，即通過數(shù)據(jù)庫(kù)掃描構(gòu)建存儲(chǔ)項(xiàng)集相關(guān)內(nèi)容信息的樹[33]，隨后挖掘過程中只需迭代遍歷樹而無需掃描數(shù)據(jù)庫(kù)。

本小節(jié)將基于樹的方法分為在靜態(tài)數(shù)據(jù)上和在動(dòng)態(tài)數(shù)據(jù)（增量數(shù)據(jù)、數(shù)據(jù)流）上的挖掘算法。

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

以上算法均基于靜態(tài)數(shù)據(jù)庫(kù)，由于現(xiàn)實(shí)應(yīng)用程序中，數(shù)據(jù)往往以流的形式產(chǎn)生，數(shù)據(jù)庫(kù)會(huì)隨著事務(wù)的增加或刪除而發(fā)生變化，此時(shí)，靜態(tài)數(shù)據(jù)的挖掘方法將無法滿足應(yīng)用需求[33]。下面將總結(jié)動(dòng)態(tài)數(shù)據(jù)上基于樹的挖掘方法。

在增量數(shù)據(jù)庫(kù)上，Kim等人提出IMHAUI[36]算法和新的數(shù)據(jù)結(jié)構(gòu)IHAUI-Tree，IHAUI-tree上的每個(gè)結(jié)點(diǎn)N存儲(chǔ)從根到N的路徑重疊事務(wù)信息，通過結(jié)點(diǎn)的共享效應(yīng)維護(hù)增量數(shù)據(jù)庫(kù)的信息。Lin等人提出基于改進(jìn)FUP概念的IHAUPM[37]算法以處理有事務(wù)插入的增量數(shù)據(jù)庫(kù)，采用HAUP-Tree結(jié)構(gòu)保存來自原始數(shù)據(jù)庫(kù)的必要信息，將原始數(shù)據(jù)庫(kù)和新添加的事務(wù)劃分為四種情況進(jìn)行維護(hù)。此外，該算法僅關(guān)注增量部分，利用部分內(nèi)存就可以快速實(shí)現(xiàn)對(duì)HAUIs的更新。

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

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

2.3基于列表的方法

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

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

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

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

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

2.4基于投影的方法

在HAUPM中，投影技術(shù)和索引機(jī)制可加快算法執(zhí)行速度，投影相關(guān)子數(shù)據(jù)庫(kù)能有效縮小原始數(shù)據(jù)庫(kù)的大小，從而只保留在挖掘過程中必要的項(xiàng)集信息，避免不必要的檢查從而降低挖掘過程中的內(nèi)存需求。

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

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

2.5基于數(shù)據(jù)格式的方法

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

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

此外，基于索引結(jié)構(gòu)的算法也可在一定程度上提高算法執(zhí)行效率。類似于PBAU算法中使用的索引表，HAUI-Tree[35]算法中使用了一種特殊的項(xiàng)目結(jié)構(gòu)快速計(jì)算項(xiàng)集效用，從而優(yōu)化內(nèi)存使用。EHAUI-Tree[57]算法利用索引表快速計(jì)算項(xiàng)集的平均效用上界，引入位數(shù)組結(jié)構(gòu)保存項(xiàng)集信息，從而最大限度地減少內(nèi)存的使用并提高計(jì)算效率。

2.6小結(jié)

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

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

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

3含有負(fù)效用的高效用模式

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

3.1全集模式

全集模式是指?jìng)鹘y(tǒng)意義上的高效用模式挖掘結(jié)果，即找到所有滿足效用值大于等于最小效用閾值的所有項(xiàng)集。Chu等人首次提出基于兩階段的含有負(fù)效用的模式挖掘算法HUINIV-Mine[12]，算法利用重定義事務(wù)加權(quán)效用上界高估含有負(fù)效用的項(xiàng)集效用，保證項(xiàng)集中最少含有一個(gè)外部效用為正的項(xiàng)，并通過再次數(shù)據(jù)庫(kù)掃描驗(yàn)證，故存在一定時(shí)空局限性。

3.1.1基于模式增長(zhǎng)的方法

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

在動(dòng)態(tài)數(shù)據(jù)庫(kù)上，Li等人提出了兩種基于滑動(dòng)窗口的挖掘含有負(fù)效用的高效用項(xiàng)集算法，即MHUI-BIT-NIP[59]和MHUI-TID-NIP[59]，兩者分別采用了BITvector和TIDlist的項(xiàng)目表示法以加快當(dāng)前滑動(dòng)窗口內(nèi)項(xiàng)集的挖掘速度，同時(shí)，開發(fā)LexTree-2HTU結(jié)構(gòu)維護(hù)窗口內(nèi)2-項(xiàng)集的高事務(wù)加權(quán)效用。

3.1.2基于列表的方法

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

面對(duì)不確定事務(wù)數(shù)據(jù)庫(kù)，HUPNU[16]算法采用新的垂直列表結(jié)構(gòu)PU±-list存儲(chǔ)正負(fù)項(xiàng)并提出六種修剪策略提前修剪無希望的項(xiàng)。此外，張妮等人首次提出在數(shù)據(jù)流中挖掘含有負(fù)項(xiàng)的HUPM算法HND[15]。受ULB-Miner算法啟發(fā)，開發(fā)出新的列表索引結(jié)構(gòu)（List Index Structure， LIS）。不同于傳統(tǒng)效用列表，此結(jié)構(gòu)通過內(nèi)存重用策略降低內(nèi)存消耗成本，大大提升了挖掘性能。

3.2精簡(jiǎn)模式

因全集模式具有產(chǎn)生大量候選集導(dǎo)致項(xiàng)集冗余和最小效用閾值設(shè)置困難的問題，精簡(jiǎn)高效用模式應(yīng)運(yùn)而生，主要包括最大高效用模式、閉合高效用模式和Top-k高效用模式等。本小節(jié)將從這一角度總結(jié)含有負(fù)效用的模式挖掘方法。

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

Singh等人提出CHN[65]算法挖掘含有負(fù)效用的閉合高效用項(xiàng)集，算法利用RSU-Prune縮小搜索空間并且利用雙向擴(kuò)展技術(shù)對(duì)搜索空間進(jìn)行閉包檢查。

3.3融合模式

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

Xu等人提出挖掘含有負(fù)項(xiàng)值的高效用序列模式算法HUSP-NIV[70]。采用LQS-Tree存儲(chǔ)高效用序列并通過I-級(jí)聯(lián)和S-級(jí)聯(lián)方法生成候選序列。MHAUIPNU[22]算法從具有正負(fù)效用數(shù)據(jù)庫(kù)中挖掘HAUIs，提出更嚴(yán)格的tubpn上界模型和新的列表結(jié)構(gòu)TUBPNU-List，基于上界和負(fù)效用相關(guān)屬性設(shè)計(jì)三種剪枝策略。

3.4小結(jié)

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

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

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

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

4擴(kuò)展高效用模式

隨著研究不斷深入，效用挖掘領(lǐng)域也產(chǎn)生了大量新興高效用模式。本節(jié)主要介紹模糊高效用模式、相關(guān)高效用模式、占用高效用模式和跨層級(jí)高效用模式。

4.1模糊高效用模式

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

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

4.2相關(guān)高效用模式

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

在現(xiàn)有的相關(guān)高效用模式挖掘算法中，大多為基于效用列表的方法。Fournier-Viger等人提出FCHM[18]算法來挖掘CoHUIs，并衍生出FCHMall-confidence[79]和FCHMbond[79]兩個(gè)算法版本，該算法集成了多種策略以有效地發(fā)現(xiàn)CoHUIs。實(shí)驗(yàn)證明，算法比FHM快兩個(gè)數(shù)量級(jí)以上且舍棄掉大量弱相關(guān)的HUIs。Gan等人提出基于Kulc度量的CoUPM[80]算法，采用含有支持度計(jì)數(shù)的效用列表計(jì)算相關(guān)性?；诖私Y(jié)構(gòu)，引入基于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]算法引入效用列表緩沖區(qū)結(jié)構(gòu)，通過內(nèi)存重用策略降低內(nèi)存消耗。單階段算法CoHAI-miner[21]結(jié)合平均效用度量，提出SAU-list結(jié)構(gòu)存儲(chǔ)項(xiàng)集信息并設(shè)計(jì)三種剪枝策略挖掘相關(guān)的HAUIs。此外，考慮項(xiàng)集數(shù)量對(duì)效用挖掘的影響，Nouioua等人提出CHUQI-Miner[82]算法挖掘相關(guān)的定量高效用項(xiàng)目集，構(gòu)建基于Q-項(xiàng)集的事務(wù)加權(quán)效用共現(xiàn)結(jié)構(gòu)（Transaction weighted utility of Q-items Co-occurrence based Structure， TQCS），同時(shí)，開發(fā)出用于修剪非相關(guān)Q-項(xiàng)集的其它策略，在一定程度上刪減了弱相關(guān)的模式且保留了HUIs之間的數(shù)量關(guān)系。

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

4.3其他新興高效用模式

占用率度量用于評(píng)估模式在事務(wù)中的占比狀況，從而得到代表性模式。傳統(tǒng)的HUPM未評(píng)估模式占用情況，例如，即使模式X出現(xiàn)在多個(gè)事務(wù)中，但是在單個(gè)事務(wù)中并未占用該事務(wù)大部分效用，故無法真正代表這些事務(wù)。此時(shí)進(jìn)行模式推薦可能是誤導(dǎo)性的。為解決上述問題，結(jié)合占用度量和效用度量，提出效用占用概念和高效用占用模式挖掘。

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

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

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

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

4.4小結(jié)

近年來，大量新穎的高效用模式類型涌現(xiàn)，針對(duì)現(xiàn)實(shí)生活中不同應(yīng)用場(chǎng)景，學(xué)者們還提出了多種擴(kuò)展高效用模式。為解決傳統(tǒng)HUPM在定量數(shù)據(jù)集上挖掘無法用語(yǔ)言模糊程度表達(dá)數(shù)量關(guān)系的問題，故提出了模糊高效用模式，主要采用模糊隸屬函數(shù)處理項(xiàng)集效用，將交易中每個(gè)項(xiàng)目的數(shù)量也被轉(zhuǎn)換為更適合人類思維的語(yǔ)言區(qū)域，通過語(yǔ)言的模糊程度評(píng)價(jià)項(xiàng)集的模糊效用。相關(guān)高效用模式解決了傳統(tǒng)HUPM結(jié)果集中項(xiàng)之間弱相關(guān)的問題，通過采用不同的相關(guān)度量，有效刪減弱相關(guān)的項(xiàng)集并降低銷售決策中的誤導(dǎo)性風(fēng)險(xiǎn)。占用高效用模式結(jié)合效用度量和占用度量，刪減模式占用率較低的事務(wù)，因此有效評(píng)估了模式的占用情況并從中提取更加有意義的模式。此外，結(jié)合分類法信息，在多個(gè)抽象級(jí)別上挖掘HUIs，提出跨層級(jí)的高效用模式。

5結(jié)束語(yǔ)

本文對(duì)現(xiàn)有衍生高效用模式挖掘算法進(jìn)行了系統(tǒng)綜述，概述了衍生高效用模式所解決的問題和發(fā)展現(xiàn)狀，歸納了各類衍生高效用模式并通過圖表詳細(xì)地給出算法的數(shù)據(jù)結(jié)構(gòu)、剪枝算法、對(duì)比算法以及優(yōu)缺點(diǎn)等。由于數(shù)據(jù)的多態(tài)性和需求的復(fù)雜性，衍生高效用模式在不斷發(fā)展和完善以適應(yīng)現(xiàn)階段的需求，未來該領(lǐng)域仍存在諸多研究機(jī)會(huì)。

1） 基于智能優(yōu)化算法的衍生高效用模式

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

2） 跨層級(jí)的模式挖掘

現(xiàn)階段跨層級(jí)模式針對(duì)多種數(shù)據(jù)形態(tài)（如增量數(shù)據(jù)、數(shù)據(jù)流、序列等）和不同應(yīng)用場(chǎng)景（如隱私保護(hù)等）的研究較少，該領(lǐng)域仍有很大發(fā)展?jié)摿?。此外，挖掘出的跨層?jí)項(xiàng)集，雖然包含有用的分類信息，但面對(duì)較深的分類樹，結(jié)果集中會(huì)出現(xiàn)過于模糊的項(xiàng)集，這同樣不利于決策和推薦。在未來的工作中，應(yīng)設(shè)計(jì)一種方法來約束跨層級(jí)數(shù)，從而減少冗余信息的挖掘，同時(shí)將分類法與其它模式結(jié)合用于處理更為復(fù)雜的問題，并在動(dòng)態(tài)數(shù)據(jù)中搜索有趣的跨層級(jí)模式。

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

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

參考文獻(xiàn)

[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]. 計(jì)算機(jī)應(yīng)用， 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] 張妮， 韓萌， 王樂， 等. 基于滑動(dòng)窗口的含負(fù)項(xiàng)高效用模式挖掘方法[J]. 鄭州大學(xué)學(xué)報(bào)（理學(xué)版）， 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] 張妮， 韓萌， 王樂， 等. 基于正負(fù)效用劃分的高效用模式挖掘方法綜述[J]. 計(jì)算機(jī)應(yīng)用， 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] 李慕航， 韓萌， 陳志強(qiáng)， 等. 面向復(fù)雜高效用模式的挖掘算法綜述[J]. 廣西師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 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] 任家東， 王倩， 王蒙. 一種基于頻繁模式有向無環(huán)圖的數(shù)據(jù)流頻繁模式挖掘算法[J]. 燕山大學(xué)學(xué)報(bào)， 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] 姜玫. 平均高效用項(xiàng)集挖掘算法研究[D]. 大連： 大連理工大學(xué)， 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] 李霆. 基于不確定數(shù)據(jù)的高平均效用序列模式挖掘算法的研究[D]. 深圳： 哈爾濱工業(yè)大學(xué)， 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] 陳麗娟. 含有負(fù)項(xiàng)值的高效用項(xiàng)集挖掘算法研究[D]. 福州： 福州大學(xué)， 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