高效用模式產(chǎn)生策略綜述

高 曼，韓 萌，雷冰冰

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

1 引言

傳統(tǒng)的模式挖掘主要考慮頻率，假定每個(gè)項(xiàng)集出現(xiàn)在一個(gè)事務(wù)中的頻次是一次，且具有同等的重要性，在很多實(shí)際生活中不具有使用性。如：商店銷(xiāo)售中，面包與鉆石被認(rèn)為同等重要，這樣就會(huì)出現(xiàn)利潤(rùn)高的項(xiàng)集沒(méi)有被挖掘。因此基于上述問(wèn)題提出高效用模式挖掘，高效用模式挖掘把鉆石銷(xiāo)售的利潤(rùn)很好地體現(xiàn)出來(lái)。

高效用模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究?jī)?nèi)容，由于其計(jì)算過(guò)程包含對(duì)模式的內(nèi)、外效用值的處理，計(jì)算復(fù)雜度較大，因此高效用模式挖掘算法的主要研究熱點(diǎn)問(wèn)題就是提高算法的時(shí)空效率。

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

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

本文的主要貢獻(xiàn)：

（1）從算法使用數(shù)據(jù)結(jié)構(gòu)的角度分析兩階段算法和一階段算法。

（2）分析基于樹(shù)結(jié)構(gòu)的高效用算法在計(jì)算過(guò)程是否產(chǎn)生候選項(xiàng)集。

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

2 一階段與兩階段算法

最早的兩階段高效用算法是基于Apriori 將TWU這一概念應(yīng)用于挖掘過(guò)程的算法。在第一階段中生成候選對(duì)象的高估效用值應(yīng)當(dāng)不小于給定的閾值，然后再進(jìn)行數(shù)據(jù)庫(kù)掃描，計(jì)算它們的效用值，從而甄別出實(shí)際的高效用模式。因?yàn)閮呻A段算法產(chǎn)生大量的候選項(xiàng)集且掃描數(shù)據(jù)庫(kù)多次，所以提出基于樹(shù)的算法。本文主要介紹基于樹(shù)的兩階段算法。基于樹(shù)的算法減少了候選集產(chǎn)生的數(shù)量，也減少了數(shù)據(jù)庫(kù)掃描次數(shù)，但是生成候選的數(shù)量還是比較大，進(jìn)而提出了基于列表的一階段算法來(lái)改善算法的時(shí)空效率。以下對(duì)基于樹(shù)的兩階段算法和基于列表的一階段算法進(jìn)行比較分析。

2.1 基于樹(shù)的兩階段算法

基于樹(shù)的算法主要是根據(jù)數(shù)據(jù)庫(kù)建立樹(shù)結(jié)構(gòu)，然后根據(jù)樹(shù)結(jié)構(gòu)得到高效用項(xiàng)集。兩階段算法首先產(chǎn)生候選項(xiàng)集，然后測(cè)試候選項(xiàng)集是否是真正的高效用項(xiàng)集。

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

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

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

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

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

根據(jù)對(duì)上述兩階段算法的分析，可以得出兩階段算法的缺點(diǎn)是需要產(chǎn)生候選項(xiàng)集，然后對(duì)候選項(xiàng)集進(jìn)行測(cè)試，從候選項(xiàng)集中選取出真正的高效用項(xiàng)集，此外，算法對(duì)于原始數(shù)據(jù)庫(kù)需要進(jìn)行多次掃描。為了減少候選項(xiàng)集的產(chǎn)生并減少數(shù)據(jù)庫(kù)掃描次數(shù)提出一階段算法，因?yàn)橐浑A段算法不需要進(jìn)行測(cè)試，所以同等條件下數(shù)據(jù)庫(kù)掃描次數(shù)少于兩階段算法。

2.2 基于列表的一階段算法

基于列表的一階段算法很多，按照產(chǎn)生的結(jié)果集進(jìn)行分類(lèi)可分為完全和壓縮，壓縮包括Top-k、閉合高效用等。

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

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

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

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

基于樹(shù)的方法，主要是通過(guò)效用上界來(lái)減少候選項(xiàng)集?；诹斜淼姆椒?，通過(guò)效用上界和剪枝策略來(lái)減少搜索空間?；诹斜淼姆椒ǖ娜秉c(diǎn)主要是算法過(guò)程中構(gòu)建效用列表花費(fèi)大量的代價(jià)且算法連接操作代價(jià)較大，主要優(yōu)點(diǎn)是不需要對(duì)原始數(shù)據(jù)庫(kù)進(jìn)行多次掃描，且通過(guò)降低效用上界提高算法的效率。與兩階段算法相比較，一階段算法可以直接挖掘高效用項(xiàng)集，不需要產(chǎn)生候選項(xiàng)集，也不需要掃描一遍原始數(shù)據(jù)庫(kù)來(lái)測(cè)試候選項(xiàng)集，通過(guò)混合搜索機(jī)制有效地挖掘高效用項(xiàng)集，通過(guò)多種機(jī)制有效地存儲(chǔ)效用信息，從而提高算法的效率。一階段算法首先通過(guò)減少數(shù)據(jù)庫(kù)的掃描來(lái)提高算法效率，因?yàn)閽呙瓒啻螖?shù)據(jù)庫(kù)需要花費(fèi)大量的時(shí)間，將數(shù)據(jù)庫(kù)的信息存儲(chǔ)在列表中從而不需要多次掃描數(shù)據(jù)庫(kù)；然后通過(guò)減少列表的連接操作來(lái)提高算法的效率，由于構(gòu)建新的列表花費(fèi)較大，通過(guò)構(gòu)建更緊湊的效用列表來(lái)減少搜索空間，因?yàn)楦o湊的列表可以減少算法運(yùn)行過(guò)程中的搜索，再通過(guò)更小的效用上界來(lái)減少搜索空間，從而提高一階段算法的效率。

上述主要從一階段、兩階段算法使用的數(shù)據(jù)結(jié)構(gòu)角度進(jìn)行分析，此外從算法使用的搜索方式進(jìn)行劃分，還可以劃分為水平方式和深度優(yōu)先。使用水平方式的兩階段算法最有代表性的就是Two-Phase[2]，使用深度優(yōu)先搜索方式兩階段算法很多，如TKU、REPT等，一階段算法都使用深度優(yōu)先的方式進(jìn)行搜索。與水平方式算法相比，深度優(yōu)先算法性能更好。因?yàn)樗椒绞剿惴óa(chǎn)生大量候選項(xiàng)集，且需要測(cè)試，需要多次掃描數(shù)據(jù)庫(kù)，而深度優(yōu)先的方式主要是構(gòu)建數(shù)據(jù)結(jié)構(gòu)來(lái)減少數(shù)據(jù)庫(kù)的掃描次數(shù)，使得算法的效率得到有效的提升。

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

表1 階段算法

3 有無(wú)候選集

現(xiàn)如今，數(shù)據(jù)的數(shù)量與種類(lèi)越來(lái)越多，由于目前的存儲(chǔ)技術(shù)不能滿足大量增長(zhǎng)的數(shù)據(jù)全部保存的需求，多數(shù)的數(shù)據(jù)不能直接存儲(chǔ)，因此需要通過(guò)挖掘動(dòng)態(tài)數(shù)據(jù)得到有趣的模式。以下主要對(duì)基于樹(shù)結(jié)構(gòu)是否產(chǎn)生候選項(xiàng)集算法進(jìn)行分析。

3.1 產(chǎn)生候選項(xiàng)集

靜態(tài)數(shù)據(jù)產(chǎn)生候選項(xiàng)集的算法有TKU[15]、REPT[16]。TKU 算法使用UP-Tree 來(lái)維護(hù)高效用項(xiàng)目集的信息，UP-Tree 是在兩次數(shù)據(jù)庫(kù)掃描中構(gòu)造的。UP-Tree 數(shù)據(jù)結(jié)構(gòu)中計(jì)算事務(wù)加權(quán)效用，以提高查找高效用項(xiàng)目集的效率，UP-Tree 使用各種策略從事務(wù)數(shù)據(jù)庫(kù)中刪除不相關(guān)的信息。REPT 算法也是基于UP-Tree 的兩階段算法，產(chǎn)生大量的候選項(xiàng)集，且需要測(cè)試候選項(xiàng)集是否為高效用項(xiàng)集，該過(guò)程需要大量的時(shí)間。為了節(jié)約時(shí)間，提出了一種策略提高最小閾值，更有效準(zhǔn)確和預(yù)先計(jì)算效用，在第二階段確定實(shí)際的Top-k高效用模式。此外，有效提高閾值大大減少了搜索空間和生成的候選模式的數(shù)量，這使得此算法能夠更快、更有效地挖掘Top-k高效用模式。

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

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

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

3.2 不產(chǎn)生候選項(xiàng)集

一階段算法并不都是不產(chǎn)生候選的算法，不產(chǎn)生候選的算法指的是沒(méi)有候選項(xiàng)集的產(chǎn)生直接挖掘的是高效用項(xiàng)集，一階段算法可能產(chǎn)生候選。

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

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

HUITWU[12]是一種新的HUITWU-Tree，用模式增長(zhǎng)的方式尋找高效用項(xiàng)集，直接有效地計(jì)算數(shù)據(jù)庫(kù)中項(xiàng)集的效用。HUPM-FP[7]是一個(gè)基于模式增長(zhǎng)方式的高效用模式挖掘算法，可以從全局樹(shù)上挖掘高效用模式，避免產(chǎn)生候選項(xiàng)集。該算法主要采用模式增長(zhǎng)的方式來(lái)直接挖掘高效用模式，而不是從樹(shù)上先得到候選項(xiàng)集，因此算法的時(shí)空效率都得到了提升。

基于事務(wù)修改是一種快速更新高效用模式樹(shù)的算法（FUP-HUP-tree-MOD）[13]，可以有效地維護(hù)和更新構(gòu)建的HUP-Tree，從而在不生成候選項(xiàng)的情況下動(dòng)態(tài)挖掘數(shù)據(jù)庫(kù)中的高效用項(xiàng)集。HUP-Tree保證從中計(jì)算到每個(gè)模式的效用值，不需要再掃描數(shù)據(jù)集來(lái)計(jì)算模式的效用值，從而使挖掘算法的時(shí)空效率得到較大的提高。

兩階段算法產(chǎn)生候選項(xiàng)集策略且需要對(duì)候選項(xiàng)集進(jìn)行測(cè)試，一階段算法直接生成高效用項(xiàng)集，因此產(chǎn)生候選項(xiàng)集的算法相較于不產(chǎn)生候選項(xiàng)集的算法性能更好。

基于樹(shù)結(jié)構(gòu)的高效用挖掘算法的分析結(jié)果如表2所示。

4 縮減空間策略

在數(shù)據(jù)庫(kù)尋找高效用模式，無(wú)論是用樹(shù)結(jié)構(gòu)還是其他結(jié)構(gòu)，如列表結(jié)構(gòu)，都需要減少搜索空間，以降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度。剪枝策略有很多，不同特征使用不同的剪枝策略。減少對(duì)數(shù)據(jù)庫(kù)掃描次數(shù)的方法就是存儲(chǔ)后續(xù)算法需要用到的信息，如構(gòu)建樹(shù)、列表、投影數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)后續(xù)需要用到的信息，也就是數(shù)據(jù)庫(kù)中重要的信息。

表2 基于樹(shù)結(jié)構(gòu)的高效用挖掘

4.1 剪枝策略

根據(jù)算法的結(jié)構(gòu)不同使用不同剪枝技術(shù)。雖然使用的剪枝策略不同，但是剪枝的目的是相同的，就是減少搜索空間。

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

基于列表結(jié)構(gòu)的剪枝策略主要是減少建立列表所需的計(jì)算，下面所述是在二項(xiàng)集計(jì)算時(shí)進(jìn)行剪枝。FHM[23]提出剪枝策略EUCP（Estimated Utility Co-occurrence Pruning），它可以在不需要執(zhí)行連接的情況下剪枝項(xiàng)集。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 減少搜索空間，這些算法是提前計(jì)算項(xiàng)集對(duì)應(yīng)的TWU，將效用存儲(chǔ)在EUCS結(jié)構(gòu)。TKEH[11]采用EUCP 和SUP 策略來(lái)有效地搜索空間。kHMC[26]使用EUCPT可以避免在FHM中計(jì)算項(xiàng)目集效用的連接操作。FHAUI[33]算法將效用信息保存到效用列表中，通過(guò)效用列表的比較來(lái)挖掘出所有的高平均效用值，同時(shí)FHAUI 算法還采用了一個(gè)二維矩陣（EUCS）來(lái)有效減少二項(xiàng)效用值的連接比較次數(shù)。

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

上述的剪枝策略不影響結(jié)果的完整性，因?yàn)樯鲜龅男в弥刀即笥诨虻扔趯?shí)際的效用值，不會(huì)將實(shí)際的高效用模式忽略。子樹(shù)效用、局部效用、判斷二項(xiàng)集使用的效用值TWU、保留效用，都大于或等于實(shí)際效用，因此不會(huì)影響結(jié)果集的完整性。

4.2 投影策略

隨著高效用模式挖掘算法在實(shí)際應(yīng)用中的重要性逐步顯著，其得到了越來(lái)越多的關(guān)注和研究，但是已知的一些算法存在著多遍數(shù)據(jù)集掃描以及產(chǎn)生大量候選項(xiàng)集、時(shí)效性不高等問(wèn)題。這些問(wèn)題使得高效用模式的挖掘效率大大降低，故提出基于投影的高效用項(xiàng)集挖掘算法。

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

4.3 其他

針對(duì)Top-k算法的策略與其他算法不同，Top-k的優(yōu)點(diǎn)是不需要額外設(shè)置算法的最小閾值，主要策略是如何提高算法最小閾值。一般算法需要多種策略提高最小閾值。

REPT 通過(guò)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 通過(guò)RIU、CUD、COV 來(lái)提高最小閾值，減少搜索空間。TKUL-Miner[25]是一種高效挖掘Top-k高效用項(xiàng)集的新算法。它利用一種新的效用列表結(jié)構(gòu)，在搜索樹(shù)的每個(gè)節(jié)點(diǎn)上存儲(chǔ)必要的信息，以便挖掘項(xiàng)集。該算法利用特定區(qū)域的搜索順序快速提高邊界最小效用閾值。此外，還提出了另外兩種計(jì)算較小的高估效用的程序策略，以有效地修剪沒(méi)有希望的項(xiàng)集。該算法采用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 中的效用列表結(jié)構(gòu)，提出了RUC、RUZ和EPB三種新的剪枝策略，提高了剪枝效率。TKU不僅使用TKO中的策略，還使用第五個(gè)策略（SE）對(duì)候選項(xiàng)集進(jìn)行排序，并提高內(nèi)部閾值。

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

5 下一步工作

面對(duì)日益增長(zhǎng)的海量數(shù)據(jù)和種類(lèi)繁雜的數(shù)據(jù)，研究者可以深入探索以下幾方面。

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

（2）大規(guī)模的數(shù)據(jù)。增量地挖掘大型數(shù)據(jù)庫(kù)可能會(huì)導(dǎo)致較高的計(jì)算成本和較大的內(nèi)存消耗。在批處理模型中，當(dāng)插入新數(shù)據(jù)時(shí)，需要重復(fù)使用傳統(tǒng)的HUIM 算法來(lái)獲得更新的結(jié)果。然而，在大數(shù)據(jù)時(shí)代，漸進(jìn)地處理數(shù)據(jù)并考慮先前分析的結(jié)果是至關(guān)重要的。iHUIM在處理大型數(shù)據(jù)庫(kù)方面存在一些研究機(jī)會(huì)：如何設(shè)計(jì)一個(gè)并行的iHUIM 算法，如何基于現(xiàn)有的大數(shù)據(jù)技術(shù)開(kāi)發(fā)一個(gè)iHUIM 算法。此外，其他有前途的領(lǐng)域可以考慮，如設(shè)計(jì)并行、分布式、多核和基于GPU的算法。

（3）非均質(zhì)性。傳統(tǒng)的關(guān)系或非關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)通常使用具有同類(lèi)格式的單一模式或文件。在大數(shù)據(jù)時(shí)代，需要處理大量的異構(gòu)數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)旨在發(fā)現(xiàn)結(jié)構(gòu)化數(shù)據(jù)中的有用知識(shí)。非結(jié)構(gòu)化和/或半結(jié)構(gòu)化數(shù)據(jù)中語(yǔ)義和異構(gòu)模式的提取是數(shù)據(jù)挖掘和iHUIM 面臨的主要挑戰(zhàn)。因此，在調(diào)整iHUIM 以處理同類(lèi)數(shù)據(jù)方面存在一些機(jī)會(huì)，包括逐步發(fā)現(xiàn)結(jié)構(gòu)化數(shù)據(jù)、非結(jié)構(gòu)化數(shù)據(jù)（可能包括文檔、音頻、視頻、圖像）和半結(jié)構(gòu)化數(shù)據(jù)（即XML、JSON）。如何擴(kuò)展現(xiàn)有的iHUIM算法來(lái)處理同構(gòu)數(shù)據(jù)是一個(gè)重要的課題。

（4）動(dòng)態(tài)復(fù)雜的數(shù)據(jù)。雖然已經(jīng)開(kāi)發(fā)了幾種增量式HUIM算法，但在如何處理復(fù)雜數(shù)據(jù)等方面仍存在許多挑戰(zhàn)。所有的iHUIM算法都是為了處理精確的數(shù)據(jù)而設(shè)計(jì)的，因此不適合處理不確定的數(shù)據(jù)。到目前為止，在動(dòng)態(tài)序列數(shù)據(jù)中挖掘高實(shí)用模式的增量方法還沒(méi)有被開(kāi)發(fā)出來(lái)。因此，增量式高實(shí)用程序順序模式挖掘也是一個(gè)有趣的主題。由于現(xiàn)實(shí)生活中的數(shù)據(jù)是動(dòng)態(tài)的而不是靜態(tài)的，因此大規(guī)模復(fù)雜數(shù)據(jù)的應(yīng)用范圍很廣。這個(gè)原理很簡(jiǎn)單，但是在數(shù)據(jù)挖掘算法的設(shè)計(jì)中集成起來(lái)肯定是困難和復(fù)雜的。與靜態(tài)環(huán)境相比，發(fā)現(xiàn)動(dòng)態(tài)數(shù)據(jù)的環(huán)境比較復(fù)雜，而且更難處理。

（5）iHUIM在運(yùn)行時(shí)間和內(nèi)存方面的計(jì)算開(kāi)銷(xiāo)非常大。對(duì)于密集的數(shù)據(jù)庫(kù)，或者包含大量條目或長(zhǎng)事務(wù)的數(shù)據(jù)庫(kù)，這取決于用戶設(shè)置的最小高效用閾值。雖然目前的增量挖掘算法比以前的算法要快得多，但仍有改進(jìn)的空間，例如開(kāi)發(fā)出更緊湊的數(shù)據(jù)結(jié)構(gòu)（如樹(shù)、列表、圖）、更有效的剪枝策略以及自適應(yīng)挖掘方法。

6 總結(jié)

本文主要從算法的實(shí)現(xiàn)階段進(jìn)行分析，一階段算法在時(shí)間與空間效率方面都要優(yōu)于兩階段算法，主要原因是，兩階段算法需要產(chǎn)生候選項(xiàng)集，然后再驗(yàn)證候選項(xiàng)集是否為高效用項(xiàng)集。為了提高算法效率，提出一階段算法直接挖掘高效用項(xiàng)集，不需要生成候選項(xiàng)集，從而節(jié)省了時(shí)間與空間，針對(duì)不同的問(wèn)題采用不同的算法，將算法劃分之后再進(jìn)行分析。然后從算法的實(shí)現(xiàn)過(guò)程來(lái)看，針對(duì)是否產(chǎn)生候選項(xiàng)集進(jìn)行分析，通過(guò)數(shù)據(jù)庫(kù)采用的數(shù)據(jù)結(jié)構(gòu)不同，使用的剪枝策略不同來(lái)分析廣泛使用的策略。下一步研究的主要工作是如何進(jìn)一步提高算法的效率。主要方法是進(jìn)一步縮小效用上界，提出更緊湊的結(jié)構(gòu)存儲(chǔ)信息，減少數(shù)據(jù)庫(kù)掃描次數(shù)等。