基于正負(fù)效用劃分的高效用模式挖掘方法綜述

張 妮，韓 萌，王 樂，李小娟，程浩東

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

0 引言

傳統(tǒng)的高效用模式挖掘（High Utility Pattern Mining，HUPM）算法假定數(shù)據(jù)集中的項(xiàng)效用值均為正，但在實(shí)際生活中，事務(wù)數(shù)據(jù)庫可能會(huì)包含負(fù)項(xiàng)。例如，某些零售店為了提高某產(chǎn)品銷售量，或者為了刺激其他商品的消費(fèi)，可能會(huì)存在虧本銷售現(xiàn)象，這時(shí)，項(xiàng)目的效用值就變成了負(fù)的。

當(dāng)前，關(guān)于處理僅含正項(xiàng)的HUPM 算法，主要分為兩階段算法與一階段算法。兩階段算法可以分為兩類：基于Apriori和基于FP-Growth（Frequent Pattern Growth）演變而來的算法?；贏priori 的兩階段算法采用層次搜索挖掘高效用項(xiàng)集（High Utility Itemsets，HUIs），在挖掘階段需要對(duì)數(shù)據(jù)庫進(jìn)行多次掃描，同時(shí)產(chǎn)生大量的候選模式。而基于FPGrowth 的兩階段算法如UP-Growth（Utility Pattern Growth）、HUP-Growth（High UP-Growth）則采用模式增長的方式進(jìn)行高效用模式挖掘。相較于兩階段算法，一階段算法可以立即計(jì)算出搜索空間中每個(gè)模式的效用，因此，一階段算法不需要生成候選項(xiàng)。盡管已設(shè)計(jì)出多種算法來挖掘高效用模式，但它們都假定事務(wù)數(shù)據(jù)庫是靜態(tài)的，但實(shí)際上數(shù)據(jù)會(huì)隨時(shí)間變化。因此，有學(xué)者提出了增量挖掘方法及數(shù)據(jù)流上的模式挖掘方法。IHUP（Incremental High Utility Pattern）是一種基于FP-Growth 的算法，無需對(duì)數(shù)據(jù)庫進(jìn)行多次掃描即可生成高效用模式，將所有事務(wù)插入到IHUP-tree 數(shù)據(jù)結(jié)構(gòu)中執(zhí)行增量的挖掘操作。但是這種方法效率不高，因?yàn)樗鼤?huì)由于高估而生成許多候選模式。HUPID（High Utility Patterns in Incremental Databases）是一種基于樹的算法，它使用稱為HUPID-Tree 和TIList（Tail-node Information List）的數(shù)據(jù)結(jié)構(gòu)以分治法執(zhí)行挖掘操作。HUI-LIST-INS（mining High Utility Itemsets based on the utility-LIST with transaction INSertion）是一種基于列表的算法，利用EUCS（Estimated Utility Cooccurrence Structure）結(jié)構(gòu)縮減搜索空間，可快速從增量數(shù)據(jù)庫中找到高效用模式。LIHUP（List-based Incremental High Utility Pattern mining）和IIHUM（Indexed list based Incremental High Utility pattern Mining）僅需掃描增量數(shù)據(jù)庫一次，其中，LIHUP 使用列表結(jié)構(gòu)，而IIHUM 使用索引列表結(jié)構(gòu)來完善現(xiàn)有列表結(jié)構(gòu)。MEFIM（Modified version of the EFficient high-utility Itemset Mining）是一種基于樹的方法，用于從動(dòng)態(tài)利潤數(shù)據(jù)庫中查找HUIs，iMEFIM（improved version of the MEFIM）使用P-set（Pex-set）結(jié)構(gòu)提高M(jìn)EFIM 性能的技術(shù)。

為了正確挖掘含負(fù)項(xiàng)的高效用模式而不丟失某些可能的結(jié)果集，Chu 等提出HUINIV（High Utility Itemsets with Negative Item Values）-Mine 算法，它可以挖掘包含負(fù)項(xiàng)的HUIs，是第一個(gè)考慮帶有負(fù)效用的HUPM 算法。該算法在兩階段算法的基礎(chǔ)上擴(kuò)展而來，但同時(shí)也具有兩階段模型的所有限制。Lin 等提出FHN（Faster High-utility itemset miner with Negative unit profits）算法，利用效用列表和EUCS 結(jié)構(gòu)來有效地挖掘HUIs，同時(shí)利用事務(wù)加權(quán)效用（Transaction-Weighted Utilization，TWU）和剩余效用來修剪搜索空間；但該算法可能會(huì)生成不在數(shù)據(jù)庫中的模式集。

在現(xiàn)有的高效用模式挖掘綜述中，Singh 等發(fā)表了帶有負(fù)效用的高效用模式挖掘方法綜述，介紹了與負(fù)項(xiàng)相關(guān)的概念和術(shù)語，給出了考慮負(fù)效用的挖掘算法。隨后，F(xiàn)ournier-Viger 等發(fā)表了高效用模式挖掘綜述，文中以算法的提出時(shí)間為順序，介紹了常見高效用模式挖掘方法。目前為止，相關(guān)綜述或者從正效用、或者從負(fù)效用角度來闡述高效用模式挖掘方法，且現(xiàn)有的關(guān)于正效用模式挖掘的綜述都是從常規(guī)角度分類，例如基于先驗(yàn)、基于投影，或者基于階段數(shù)等角度進(jìn)行分類。

不同于以上綜述，本文將從一個(gè)新穎的角度總結(jié)高效用模式挖掘算法，主要工作如下：

1）以正與負(fù)為角度對(duì)高效用模式挖掘方法進(jìn)行劃分，內(nèi)容較為全面。

2）依據(jù)數(shù)據(jù)庫的動(dòng)與靜對(duì)正效用模式挖掘進(jìn)行分類，角度新穎；同時(shí)對(duì)負(fù)效用模式挖掘以各種關(guān)鍵技術(shù)進(jìn)行劃分，例如基于先驗(yàn)、基于樹、基于效用列表和基于數(shù)組。

3）從算法的關(guān)鍵技術(shù)、數(shù)據(jù)結(jié)構(gòu)以及算法的優(yōu)缺點(diǎn)等角度對(duì)HUPM 算法進(jìn)行了深入的分析和總結(jié)。

1 基本概念

設(shè)

I

是項(xiàng)的有限集合，

I

={

i

，

i

，…，

i

}，其中每個(gè)項(xiàng)目

i

都有一個(gè)正的數(shù)量

q

和與之相關(guān)的利潤

p

(

i

)。事務(wù)數(shù)據(jù)庫

D

={

T

，

T

，…，

T

}由一組事務(wù)組成，其中每條事務(wù)包含一組項(xiàng)

i

∈

I

，并與唯一的事務(wù)標(biāo)識(shí)符

T

相關(guān)聯(lián)。表1 中列出了一個(gè)示例數(shù)據(jù)庫，事務(wù)包含項(xiàng)及其數(shù)量，即內(nèi)部效用。表2 列出了每一項(xiàng)的利潤（又稱為外部效用，可為負(fù)），一個(gè)項(xiàng)目的效用是數(shù)量和利潤的乘積，即內(nèi)部效用和外部效用的乘積。挖掘高效用模式的問題可以描述為找到效用值大于或等于用戶定義的最小效用閾值（minimum utility，minutil）的所有項(xiàng)集。

表1 事務(wù)數(shù)據(jù)庫Tab 1 Transaction database

表2 項(xiàng)目效用值Tab 2 Item utility value

定義1

項(xiàng)目的效用。事務(wù)

T

中項(xiàng)目

z

的效用值如式（1）所示：

例如，在示例數(shù)據(jù)庫中，項(xiàng)目

A

在事務(wù)

T

中的效用為：

U

(

A

，

T

)=

p

(

A

)*

q

(

A

，

T

)=2 × 1=2；項(xiàng)目

B

在事務(wù)

T

中 的效用為：

U

(

B

，

T

)=

p

(

B

)*

q

(

B

，

T

)=-2 × 2=-4。

定義2

項(xiàng)集在事務(wù)中的效用。如果項(xiàng)集

X

∈

T

，則項(xiàng)集

X

在事務(wù)

T

中的效用值為：

例如，在示例數(shù)據(jù)庫中，項(xiàng)集｛

AB

｝在

T

中的效用為：

U

(

AB

，

T

)=

U

(

A

，

T

)+

U

(

B

，

T

)=2×1+（-2）×2=2+（-4）=-2。

定義3

項(xiàng)集的效用。項(xiàng)集

X

的效用如式（3）所示，其中

g

（

X

）是包含

X

的事務(wù)集：

例如，在示例數(shù)據(jù)庫中，項(xiàng)集｛

AB

｝出現(xiàn)在事務(wù)

T

和

T

中，則項(xiàng)集｛

AB

｝的效用為：

U

(

AB

，

T

)+

U

(

AB

，

T

)=(-2) +(-2)=-4。同理，項(xiàng)集｛

AC

｝的效用為：

U

(

AC

，

T

)+

U

(

AC

，

T

)=11+5=16。

定義4

事務(wù)效用（Transaction Utility，TU）。事務(wù)

T

的事務(wù)效用定義為：

例如在示例數(shù)據(jù)庫中，事務(wù)

T

的事務(wù)效用為

TU

(

T

)=

U

(

A

，

T

)+

U

(

C

，

T

)+

U

(

E

，

T

)+

U

(

F

，

T

)=2+3+2+9=16；事務(wù)

T

的事務(wù)效用為

TU

(

T

)=

U

(

A

，

T

)+

U

(

B

，

T

)+

U

(

C

，

T

)+

U

(

D

，

T

)=2+（-4）+9+（-12）=-5。

定義5

TWU。項(xiàng)集

X

的TWU 定義為：

例如在示例數(shù)據(jù)庫中，項(xiàng)目

A

的事務(wù)加權(quán)效用為

TWU

(

A

)=

TU

(

T

)+

TU

(

T

)+

TU

(

T

)=(-5)+4+16=15，項(xiàng)目

B

的事務(wù)加權(quán)效用為

TWU

(

B

)=

TU

(

T

)+

TU

(

T

)+

TU

(

T

)=(-5)+4+5=4。

定義6

高效用項(xiàng)集。如果

U

(

X

) ≥

minutil

，

minutil

是用戶設(shè)置的最小效用閾值，則項(xiàng)目集

X

是高效用模式；否則，

X

是低效用模式。

在實(shí)際生活中，事務(wù)數(shù)據(jù)庫中的項(xiàng)是可以帶有負(fù)效用值的，含負(fù)項(xiàng)的高效用模式挖掘問題是要在數(shù)據(jù)庫中發(fā)現(xiàn)外部效用值可能為正或?yàn)樨?fù)的所有高效用項(xiàng)集。為了不丟失候選項(xiàng)集，用于挖掘正效用的挖掘算法不能直接應(yīng)用于挖掘帶有負(fù)效用的HUIs。為了解決該問題，重新定義了事務(wù)效用和事務(wù)加權(quán)效用，如下所述：

定義7

重新定義的事務(wù)效用（Redefined TU，RTU）。事務(wù)

T

的重新定義的事務(wù)效用被定義為

T

中具有正外部效用的項(xiàng)的效用值之和，即

例如在示例數(shù)據(jù)庫中，事務(wù)

T

的重新定義的事務(wù)效用

RTU

(

T

)=

U

(

A

，

T

)+

U

(

C

，

T

)=2+9=11，其中不包括項(xiàng)目

B

和

D

的效用值，因?yàn)樗鼈兊耐獠啃в弥禐樨?fù)。

定義8

重新定義的事務(wù)加權(quán)效用（Redefined TWU，RTWU）。項(xiàng)目集

X

的重新定義的事務(wù)加權(quán)效用定義為：

例如在示例數(shù)據(jù)庫中，

RTWU

(

A

)=

RTU

(

T

)+

RTU

(

T

)+

RTU

(

T

)=11+10+16=37。

2 帶有正效用的模式挖掘方法

挖掘高效用模式，即找到效用值不小于用戶定義的閾值的所有模式，是效用挖掘中一項(xiàng)至關(guān)重要的任務(wù)，目前已取得了大量的研究成果。本文將選取其中一些最新的、具有代表性的算法進(jìn)行分析總結(jié)。

2.1 靜態(tài)模式挖掘

靜態(tài)高效用模式挖掘算法依據(jù)是否產(chǎn)生候選模式可將其分為兩階段算法和一階段算法。它們的主要區(qū)別為：前者會(huì)生成大量候選模式，由于候選模式并不一定都是高效用模式，所以算法必須再次掃描數(shù)據(jù)集計(jì)算候選模式的效用值，才能斷定其是否為HUIs；而一階段算法則不會(huì)產(chǎn)生候選模式，在算法挖掘的過程中就可以得到全部模式的效用值。

2.1.1 兩階段算法

Two-Phase算法分兩個(gè)階段發(fā)現(xiàn)高效用模式，它首先找到候選HUIs，即TWU 值不小于

minutil

的項(xiàng)集；然后再次掃描數(shù)據(jù)庫以計(jì)算每個(gè)候選對(duì)象的確切效用，并選擇效用值大于或等于

minutil

的項(xiàng)目集。盡管Two-Phase 可以在事務(wù)數(shù)據(jù)庫中找到完整的HUIs，但在挖掘過程中必須多次掃描數(shù)據(jù)庫且產(chǎn)生大量候選項(xiàng)集，導(dǎo)致出現(xiàn)內(nèi)存占用過多和時(shí)間運(yùn)行過長等問題。

為了解決上述問題，Tseng 等提出了UP-Growth 算法，算法將高效用項(xiàng)集的信息保存在名為UP-Tree（Utility Patterns Tree）的特殊數(shù)據(jù)結(jié)構(gòu)中，僅需掃描數(shù)據(jù)庫兩次就可以從UP-Tree 生成潛在的高效用項(xiàng)集。算法還使用以下策略來減小搜索空間：丟棄全局無用項(xiàng)目；丟棄全局節(jié)點(diǎn)效用；丟棄局部無用項(xiàng)目和減少局部節(jié)點(diǎn)效用。隨后，提出了一種名為IUPG（Improved UP-Growth）的算法，這是UP-Growth的改進(jìn)版本，它采用了兩種新穎的策略，即丟棄局部無用的項(xiàng)及其估計(jì)的節(jié)點(diǎn)效用和減少局部UP-Tree 的節(jié)點(diǎn)效用。

隨 后PB（Projection-Based indexing approach for mining high utility itemsets）算法被提出，該算法利用索引機(jī)制來加速挖掘過程，同時(shí)降低挖掘過程中所需要的內(nèi)存。索引機(jī)制是模仿傳統(tǒng)的投影算法，達(dá)到投影以挖掘子數(shù)據(jù)庫的目的，可以快速查找數(shù)據(jù)庫中各項(xiàng)集的事務(wù)，不會(huì)為每個(gè)項(xiàng)集復(fù)制原始數(shù)據(jù)庫來挖掘HUIs；相反，它們是直接通過索引結(jié)構(gòu)提取信息的。因此，所消耗的內(nèi)存比直接復(fù)制原始數(shù)據(jù)庫來進(jìn)行挖掘所需的內(nèi)存要少得多。

2.1.2 一階段算法

兩階段算法的性能良好，但它們都有一個(gè)局限：必須進(jìn)行兩次數(shù)據(jù)庫掃描，才能判斷候選模式是否為HUIs。為了解決這一局限性問題，有學(xué)者提出了一階段算法，一階段算法和兩階段算法的優(yōu)越之處在于時(shí)間性能的大幅提升。

HUI-Miner（High Utility Itemsets Miner）算法通過使用一種名為效用列表（Utility-list）的新穎結(jié)構(gòu)引入了一階段算法的概念，此結(jié)構(gòu)存儲(chǔ)了項(xiàng)集的效用，以此來減小搜索空間所需的信息，而無需重復(fù)掃描數(shù)據(jù)庫。HUI-Miner 算法首先掃描數(shù)據(jù)庫為每個(gè)項(xiàng)目構(gòu)造一個(gè)效用列表；然后，通過將子集的效用列表合并來遞歸地構(gòu)建較大項(xiàng)集的效用列表，而無需再次掃描數(shù)據(jù)庫。HUI-Miner 算法是一種完整的算法，因?yàn)樗梢允褂眯в昧斜斫Y(jié)構(gòu)列舉所有高效用項(xiàng)集及其效用值，但缺點(diǎn)為可能會(huì)生成不存在數(shù)據(jù)庫中的項(xiàng)集。

隨后，F(xiàn)ournier-Viger 等提出了FHM（Fast High-utility Miner）算法，引入了EUCS 結(jié)構(gòu)以及相應(yīng)的估計(jì)效用共現(xiàn)修剪技術(shù)，以減少需要執(zhí)行的連接操作的數(shù)量，提高挖掘HUIs的速度。

Zida 等提出了EFIM（EFficient high-utility Itemset Mining）算法，算法依靠兩個(gè)名為子樹效用和局部效用的上限來有效地修剪搜索空間。此外，為了減少數(shù)據(jù)庫掃描的成本，EFIM 還提出了高效數(shù)據(jù)庫投影和高效事務(wù)合并技術(shù)。

基于效用列表的算法主要局限在于：創(chuàng)建和維護(hù)效用列表非常耗時(shí)，并且會(huì)占用大量內(nèi)存，原因是建立了大量效用列表，并且列表相交/合并操作成本很高。為了解決此問題，ULB-Miner（Utility-List Buffer for high utility itemset Miner）算法被提出，通過應(yīng)用一種稱為效用列表緩沖區(qū)的改進(jìn)的效用列表結(jié)構(gòu)來減少內(nèi)存消耗并加快聯(lián)接操作，在緩沖區(qū)中記錄了每個(gè)項(xiàng)目在數(shù)據(jù)中的索引位置，因此可以快速查找項(xiàng)目信息。

2.2 動(dòng)態(tài)模式挖掘

高效用模式挖掘算法在靜態(tài)數(shù)據(jù)庫中表現(xiàn)優(yōu)異，但是現(xiàn)實(shí)生活中大部分?jǐn)?shù)據(jù)庫都是處于動(dòng)態(tài)增長的狀態(tài)。在動(dòng)態(tài)數(shù)據(jù)庫中，數(shù)據(jù)庫更新一次，都必須要重新進(jìn)行一次高效用模式挖掘。但是，重新進(jìn)行高效用模式挖掘并沒有用到上次在數(shù)據(jù)庫中挖掘出來的有效信息，更為致命的是，若一次插入少量數(shù)據(jù)就需要重新對(duì)整個(gè)數(shù)據(jù)庫掃描，成本非常昂貴并且效率極低。為了克服這個(gè)問題，在動(dòng)態(tài)數(shù)據(jù)庫中的高效用模式挖掘算法IHUP 被提出，該算法可重用其先前挖掘的結(jié)果，從而在更新數(shù)據(jù)庫時(shí)提高發(fā)現(xiàn)高效用項(xiàng)集的速度。

2.2.1 基于增量數(shù)據(jù)庫的模式挖掘

為了解決在處理動(dòng)態(tài)數(shù)據(jù)庫時(shí)所面對(duì)的沒有利用之前挖掘出的有效信息的問題，提出了增量高效用模式挖掘算法。

Ahmed 等提出了IHUP 算法，這是第一個(gè)在高效用模式挖掘中考慮增量數(shù)據(jù)集的算法，當(dāng)更新數(shù)據(jù)庫或更改最小效用閾值時(shí)，算法將重用先前的數(shù)據(jù)結(jié)構(gòu)并開始在新增數(shù)據(jù)中挖掘HUIs。算法包括三種新穎的樹結(jié)構(gòu)來有效執(zhí)行增量挖掘：1）IHUP 詞典樹，按照項(xiàng)目的詞典序列排列，可以獲得增量數(shù)據(jù)而不必重組；2）IHUP 事務(wù)頻率樹，依據(jù)項(xiàng)目的事務(wù)頻率（降序）排列項(xiàng)目來得到緊湊的大?。?）IHUP 事務(wù)加權(quán)效用樹，按項(xiàng)目的TWU 值降序排序。盡管IHUP 在查找高事務(wù)加權(quán)項(xiàng)集（High TWU Itemsets，HTWUI）時(shí)并未生成任何候選，并且比兩階段具有更好的性能，但它在第一階段仍會(huì)產(chǎn)生過多的HTWUI。Lin 等提出了FUP-HUI（Fast-UPdate HUI mining）算法，使用FUP（Fast-UPdate）概念和兩階段模型來更新增量HUIs 集。但是，使用FUP-HUI 進(jìn)行增量模式挖掘是一個(gè)很耗時(shí)的過程，因?yàn)樗惴ㄊ褂昧酥鸺?jí)挖掘方式。為了克服FUP-HUI 算法的局限性，Lin 等提出了一種改進(jìn)的預(yù)大型概念和算法PRE-HUI（based on PRE-large concept HUI mining），基于預(yù)大型概念的屬性保留預(yù)大型事務(wù)加權(quán)效用項(xiàng)目集以避免數(shù)據(jù)庫重新掃描，直到所插入事務(wù)的累積總效用達(dá)到安全范圍為止。由于FUP-HUI 和PRE-HUI 算法使用兩階段模型，因此仍需要執(zhí)行多次數(shù)據(jù)庫掃描，此外，它們還需要以基于模式增長的方法尋找HTWUI。Yun 等提出了HUPID 算法，該算法使用PID-Tree 掃描構(gòu)建一個(gè)樹結(jié)構(gòu)，并使用一種名為TIList 的新型數(shù)據(jù)結(jié)構(gòu)來重構(gòu)方法，以處理增量數(shù)據(jù)。

采用兩階段的算法都面臨兩個(gè)問題：1）生成大量候選對(duì)象；2）重復(fù)數(shù)據(jù)庫掃描，導(dǎo)致可伸縮性和效率瓶頸。

后來的增量算法采用一階段，Lin 等提出了一種基于FHM 的增量算法HUI-LIST-INS 來維護(hù)和更新已建立的效用列表結(jié)構(gòu)，通過事務(wù)插入來挖掘HUIs?；谛в昧斜斫Y(jié)構(gòu)，原始數(shù)據(jù)庫中的相關(guān)信息可以被壓縮，所提出的算法還應(yīng)用EUCS，從而加快了計(jì)算速度。隨后，F(xiàn)ournier-Viger 等設(shè)計(jì)了EIHI（Efficient Incremental High-utility Itemset miner）算法，EIHI 是一種高效的、基于列表的維護(hù)算法，它使用名為HUItrie 的結(jié)構(gòu)來插入和維護(hù)關(guān)于HUIs 的信息，利用了HUILIST-INS 中沒有用到的幾個(gè)重要屬性，在更新效用的過程中對(duì)搜索空間進(jìn)行了修剪。EIHI 中集成的新的剪枝條件旨在減少執(zhí)行時(shí)間，而不是減少內(nèi)存使用。盡管這些方法更適合從動(dòng)態(tài)環(huán)境中挖掘高效用模式，但它們?cè)谕诰蜻^程中會(huì)生成候選模式，并且需要特別的過程來識(shí)別是否為高效用模式，因?yàn)樗鼈儜?yīng)用了高估概念。換句話說，即使已經(jīng)提出了增量效用模式挖掘方法，無論采用樹結(jié)構(gòu)還是列表結(jié)構(gòu)，以前的方法都需要至少兩次掃描以進(jìn)行增量高效用模式挖掘。但是，具有多次掃描的方法實(shí)際上不適用于流環(huán)境。為了解決這個(gè)問題，Yun 等提出了LIHUP 算法，該算法可應(yīng)用基于列表的數(shù)據(jù)結(jié)構(gòu)，在不生成候選對(duì)象的情況下，通過一次數(shù)據(jù)庫掃描就可以從增量數(shù)據(jù)庫中挖掘HUIs。該算法僅掃描一次新添加的事務(wù)，將其反映到先前構(gòu)造的結(jié)構(gòu)中，并通過重組過程優(yōu)化更新的結(jié)構(gòu)。EIHI、HUI-LIST-INS 和LIHUP 仍然存在效率瓶頸，其根本原因是它們都對(duì)效用列表使用了大量低效的聯(lián)接操作結(jié)構(gòu)。為了解決這個(gè)問題，通過改進(jìn)dHUP（direct discovery of High Utility Patterns）算法提出了一種新的增量算法IdHUP（Improved dHUP），該算法通過改進(jìn)基于相關(guān)性的修剪和基于上限的修剪來減小搜索空間，并使用哈希表來快速合并事務(wù)，從而適應(yīng)了一階段；提出了兩種修剪策略：基于缺席的修剪和基于遺留的修剪，這些策略專門用于增量高效用模式挖掘。Yun 等提出了基于索引列表的增量高效用模式挖掘IIHUM 算法，通過防止候選模式的提取，提高了增量高效用模式挖掘的性能，此外，還提出了一種重組技術(shù)，以便在索引列表結(jié)構(gòu)中更有效地處理增量數(shù)據(jù)。DHUPL（Damped High Utility Pattern mining based List）用于從增量非二進(jìn)制數(shù)據(jù)庫中發(fā)現(xiàn)高效用模式，通過掃描增量數(shù)據(jù)庫一次并在基于列表的數(shù)據(jù)結(jié)構(gòu)中管理它們來有效地執(zhí)行挖掘操作，而無需生成候選模式。DHUPL還使用衰減因子根據(jù)每個(gè)數(shù)據(jù)的到達(dá)時(shí)間來處理數(shù)據(jù)的重要性，因此，通過增加最近輸入數(shù)據(jù)的重要性和降低舊數(shù)據(jù)的重要性而獲得了優(yōu)異的結(jié)果。

2.2.2 基于數(shù)據(jù)流的模式挖掘

當(dāng)今社會(huì)是信息技術(shù)快速發(fā)展的社會(huì)，數(shù)據(jù)規(guī)格也在急速增長，而目前所面臨的主要挑戰(zhàn)是如何在海量的數(shù)據(jù)中獲得潛在的、有價(jià)值的信息。因此，在數(shù)據(jù)流上挖掘高效用模式已經(jīng)成為了數(shù)據(jù)挖掘中的一個(gè)熱點(diǎn)和難點(diǎn)問題。

數(shù)據(jù)流的特點(diǎn)決定了之前討論的HUPM 算法無法直接用在數(shù)據(jù)流上。為了能夠從數(shù)據(jù)流中獲得數(shù)據(jù)，通常利用窗口技術(shù)處理數(shù)據(jù)流，窗口技術(shù)應(yīng)用采樣的方法，把數(shù)據(jù)流劃分成若干部分，一般來說窗口技術(shù)有三種常見模型：界標(biāo)窗口模型、時(shí)間衰減窗口模型和滑動(dòng)窗口模型。第一種界標(biāo)窗口模型不適用于數(shù)據(jù)流挖掘；時(shí)間衰減窗口模型是在界標(biāo)窗口模型的基礎(chǔ)上給數(shù)據(jù)流中的數(shù)據(jù)項(xiàng)設(shè)置了不同的權(quán)值，該模型比界標(biāo)窗口模型更常用；滑動(dòng)窗口模型不同于上述兩種模型，它的窗口大小是固定的，是在數(shù)據(jù)流上挖掘高效用模式時(shí)使用最多的模型。

2008 年，Chu 等首次提出數(shù)據(jù)流上的高效用模式挖掘算法THUI（Temporal HUI）-Mine，該算法使用滑動(dòng)窗口模型，進(jìn)行挖掘時(shí)，先把窗口分成幾個(gè)區(qū)，然后從各個(gè)分區(qū)中獲得加權(quán)高效用項(xiàng)集，采用與先驗(yàn)算法相似的候選項(xiàng)產(chǎn)生策略，找到所有的候選項(xiàng)集，然后再進(jìn)行一次滑動(dòng)窗口數(shù)據(jù)的掃描，推算這些候選項(xiàng)集在窗口中的效用，以此來證實(shí)這些候選項(xiàng)集是否是高效用模式。Ahmed 等提出的算法HUPMS（HUPM over Stream data），是一種基于滑動(dòng)窗口模型的算法，采用HUS-tree（High Utility Stream tree）來保存滑動(dòng)窗口中的項(xiàng)集和高估效用值，并且采用模式增長的方式來剪枝。

以上所討論的算法都是兩階段算法，兩階段算法最大缺點(diǎn)是在第一階段會(huì)產(chǎn)生許多候選項(xiàng)集，還要在第二階段重新校驗(yàn)候選項(xiàng)集的效用，時(shí)間性能較差。

王樂提出了一種一階段算法HUM-UT（High Utility pattern Mining based on Utility Tree），算法采用滑動(dòng)窗口模型，將數(shù)據(jù)項(xiàng)的TWU 視為估算效用值。窗口讀入新批次數(shù)據(jù)后，為這批數(shù)據(jù)建造全局效用樹，當(dāng)窗口數(shù)據(jù)填充完成的時(shí)候，為窗口中的數(shù)據(jù)構(gòu)建全局頭表，最后利用全局頭表和全局效用樹進(jìn)行高效用模式挖掘。當(dāng)數(shù)據(jù)已經(jīng)把窗口填滿，并且到達(dá)了一批新的數(shù)據(jù)的時(shí)候，窗口可以自動(dòng)“滑動(dòng)”，也就是移除在這個(gè)窗口中停留時(shí)間最長的一批數(shù)據(jù)，然后把新到達(dá)的一批數(shù)據(jù)放到剛移除的一批數(shù)據(jù)的位置，同時(shí)要更新全局效用樹。該算法的缺點(diǎn)為全局頭表包含了和當(dāng)前需要處理數(shù)據(jù)無關(guān)的冗余數(shù)據(jù)項(xiàng)；在算法挖掘的時(shí)候，對(duì)全局效用樹中的低效用數(shù)據(jù)項(xiàng)執(zhí)行了沒有用的操作，這樣做會(huì)大大降低算法的運(yùn)行效率。隨后，郭世明等在2018 年提出了HUISW（HUI mining over a Siding Window）算法，該算法將數(shù)據(jù)信息保存在樹結(jié)構(gòu)HUIL-Tree（HUI Tree which arranges items according to Lexicographic order）上，將數(shù)據(jù)的效用信息保存在全局效用數(shù)據(jù)庫上，通過利用HUIL-Tree 的信息，再利用全局效用數(shù)據(jù)庫就能夠進(jìn)行挖掘。該算法存在的問題是數(shù)據(jù)及其效用信息必須重復(fù)存儲(chǔ)在全局效用數(shù)據(jù)庫和條件效用數(shù)據(jù)庫中。受靜態(tài)數(shù)據(jù)庫上的Top-

k

高效用模式挖掘算法的啟發(fā)，有學(xué)者把問題延伸到數(shù)據(jù)流上，提出了T-HUDS（Top-

k

High Utility itemset mining over Data Streams）算法，該算法采用了滑動(dòng)窗口模型，利用HUDS-Tree（High Utility Data Stream Tree）來維護(hù)事務(wù)和效用信息，利用上一窗口中的Top-

k

高效用項(xiàng)集初始化新窗口的效用下限值，然后再進(jìn)行Top-

k

高效用模式挖掘。Tsai提出了一種基于加權(quán)滑動(dòng)窗口模型的、單遍掃描算法HUI_W（HUI based on the weighted sliding Windows），該算法利用了重復(fù)使用存儲(chǔ)信息的優(yōu)勢(shì)，可以有效地發(fā)現(xiàn)數(shù)據(jù)流中的所有高效用項(xiàng)集。Jaysawal 等提出了SOHUPDS（Single-pass One-phase algorithm for mining High Utility Patterns over a Data Stream），該算法利用投影技術(shù)，并且使用了滑動(dòng)窗口模型，以此在數(shù)據(jù)流上挖掘高效用模式。此外，提出了一個(gè)數(shù)據(jù)結(jié)構(gòu)IUDataListSW，它存儲(chǔ)了當(dāng)前滑動(dòng)窗口中各項(xiàng)的效用和上限值，保存事務(wù)中每個(gè)項(xiàng)目的位置，這樣可以快速地獲得項(xiàng)目的原始數(shù)據(jù)庫；還提出了一種更新策略，利用從先前滑動(dòng)窗口中挖掘的HUIs 來更新當(dāng)前滑動(dòng)窗口中的高效用項(xiàng)集。

2.2.3 其他

盡管已設(shè)計(jì)出多種算法來列舉所有HUIs，但重要的問題是它們假定商品的效用（單位利潤）是恒定的，但是這種假設(shè)在現(xiàn)實(shí)生活中是不合理的。例如，由于供應(yīng)成本和促銷活動(dòng)的波動(dòng)，零售商店中商品的單位利潤通常會(huì)隨時(shí)間變化，忽略這一重要特征使得當(dāng)前的HUIs 挖掘算法無法應(yīng)用于更多現(xiàn)實(shí)應(yīng)用中。

為了解決當(dāng)前HUPM 算法的這一關(guān)鍵限制，學(xué)者們研究了在具有動(dòng)態(tài)單位利潤的數(shù)據(jù)庫中挖掘HUIs 的新問題，提出了一種新穎的MEFIM算法，算法依賴于一種新穎的緊湊型數(shù)據(jù)庫格式來有效地發(fā)現(xiàn)所有模式；還提出了MEFIM算法的改進(jìn)版本，稱為iMEFIM，算法采用一種稱為P

-

set 的結(jié)構(gòu)，以減少事務(wù)掃描的次數(shù)并加快挖掘過程。為了在動(dòng)態(tài)利潤數(shù)據(jù)庫中挖掘HUIs，MEFIM 中對(duì)EFIM進(jìn)行了兩個(gè)重要修改：第一個(gè)修改是將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為緊湊格式；第二個(gè)修改是同時(shí)考慮項(xiàng)目的動(dòng)態(tài)單位利潤。

2.3 小結(jié)

正效用模式挖掘算法中，因不同算法采用的數(shù)據(jù)結(jié)構(gòu)和關(guān)鍵技術(shù)不同，算法的特征和性能也不同。例如基于兩階段模型的算法由于生成了過多的候選項(xiàng)并多次掃描數(shù)據(jù)庫，導(dǎo)致算法效率較低；而一階段算法因其不生成候選項(xiàng)的特點(diǎn)，解決了兩階段算法的局限性，算法性能大幅提升。在表3 中對(duì)正效用模式挖掘算法以多種角度進(jìn)行了分析，并給出了算法的優(yōu)缺點(diǎn)。

表3 正效用模式挖掘算法的對(duì)比Tab 3 Comparison of positive utility pattern mining algorithms

續(xù)表

靜態(tài)HUPM 算法不能處理動(dòng)態(tài)數(shù)據(jù)庫，即當(dāng)有事務(wù)插入時(shí)，靜態(tài)HUPM 算法不能利用先前挖掘出的結(jié)果而導(dǎo)致效率低下，針對(duì)此缺陷學(xué)者們提出了動(dòng)態(tài)數(shù)據(jù)庫中的HUPM 算法。在動(dòng)態(tài)HUPM 算法中，基于增量的模式挖掘算法可在插入增量數(shù)據(jù)時(shí)有效利用先前挖掘出的結(jié)果；數(shù)據(jù)流模式挖掘算法中的滑動(dòng)窗口不僅考慮事務(wù)的增加，還同時(shí)考慮了事務(wù)刪除的情況。圖1 中列出了關(guān)于正效用模式挖掘算法下的各類方法總結(jié)，包括提出背景，解決問題和優(yōu)缺點(diǎn)等方面。

圖1 正效用模式挖掘各類方法的優(yōu)缺點(diǎn)Fig.1 Advantages and disadvantages of different methods with positive utility pattern mining

3 帶有負(fù)效用的模式挖掘方法

傳統(tǒng)高效用模式挖掘算法假定所有項(xiàng)的效用值均為正，但是在實(shí)際應(yīng)用中，數(shù)據(jù)庫通常包含帶有負(fù)效用值的項(xiàng)。例如，在零售商店的交易數(shù)據(jù)庫中，通常會(huì)發(fā)現(xiàn)單位利潤為負(fù)的項(xiàng)目（即外部效用為負(fù)），原因是某些商品經(jīng)常在交易中虧本出售以吸引顧客。經(jīng)學(xué)者研究證明，如果數(shù)據(jù)庫中出現(xiàn)帶有負(fù)效用值的項(xiàng)，則傳統(tǒng)的HUPM 算法會(huì)發(fā)現(xiàn)一組不完整的高效用項(xiàng)集，具體原因如下：當(dāng)處理帶有效用值的項(xiàng)目時(shí)，諸如TWU 之類的上限不再是項(xiàng)目效用的上限，因此，高效用項(xiàng)集可能會(huì)被錯(cuò)誤地修剪。為了解決這一問題，含負(fù)項(xiàng)的HUPM 算法被提出。由于此類算法能處理更多貼近實(shí)際應(yīng)用中的數(shù)據(jù)庫，隨后在各種高效用擴(kuò)展模式中也提出了可以處理負(fù)項(xiàng)的挖掘方法。本章將以各種關(guān)鍵技術(shù)對(duì)含負(fù)項(xiàng)的高效用模式挖掘方法進(jìn)行劃分。

3.1 基于先驗(yàn)

第一個(gè)考慮負(fù)效用的HUPM算法為Chu等提出的HUINIV-Mine 算法，在算法中提出了基于RTWU 的高估和修剪策略。但是，它基于兩階段模型，需要進(jìn)行多次數(shù)據(jù)集掃描才能找到HUIs，并生成過多的候選對(duì)象。

Lan 等提出了TS-HOUN（Three Scan-High On-shelf Utility itemsets with Negative profit values）算法，是第一個(gè)同時(shí)考慮負(fù)效用和貨架時(shí)間段的HUPM 算法。使用貨架時(shí)間段，可以準(zhǔn)確地評(píng)估時(shí)間數(shù)據(jù)集中項(xiàng)集的實(shí)際效用值。大多數(shù)算法都認(rèn)為商品具有相同的貨架時(shí)間，即所有商品都在同一時(shí)間段內(nèi)出售，但在現(xiàn)實(shí)生活中，某些商品僅在較短的時(shí)間段內(nèi)（例如夏季）出售。TS-HOUN 掃描數(shù)據(jù)集三次，使用基于TWU 修剪策略來修剪搜索空間，是兩階段方法的擴(kuò)展，因此，它需要大量的運(yùn)行時(shí)間和內(nèi)存空間才能完成挖掘任務(wù)并生成大量候選對(duì)象。算法在密集或大型數(shù)據(jù)集上表現(xiàn)不佳，因它在每個(gè)時(shí)間段分別挖掘項(xiàng)集，然后對(duì)挖掘出的項(xiàng)集執(zhí)行昂貴的合并操作，可能必須在不同的時(shí)期內(nèi)多次生成相同的項(xiàng)集，有著基于兩階段模型算法的所有限制。

3.2 基于樹

Subramanian 等提出了一種不生成候選項(xiàng)的基于樹的挖掘方法UP-GNIV（Utility Pattern-Growth approach for Negative Item Values）來挖掘含有負(fù)項(xiàng)的HUIs，它是UPGrowth 算法的負(fù)效用版本。算法提出了去除負(fù)項(xiàng)效用和PNI（Pruning Negative Itemsets）兩種策略，并使用前者計(jì)算TU。

Xu 等提出了算法HUSP-NIV（High Utility Sequential Patterns with Negative Item Values），它是第一個(gè)挖掘包含負(fù)項(xiàng)的高效用序列模式的算法，使用了詞典量化序列樹，它的工作方式如下：1）使用詞典順序樹（Lexicographic Quantitative Sequence tree，LQS-tree）提取完整的高效用序列集，并使用I-級(jí)聯(lián)和S-級(jí)聯(lián)機(jī)制生成新的級(jí)聯(lián)序列；2）使用三種修剪方法來減小LQS-tree 中的搜索空間；3）遍歷LQStree 并輸出所有高效用序列模式。

Singh 等提出了一種利用模式生長樹挖掘負(fù)效用HUIs的算法EHIN（Efficient High-utility Itemsets mining with Negative utility），通過合并相同的事務(wù)來降低數(shù)據(jù)集掃描成本，使用基于投影數(shù)據(jù)集的事務(wù)合并技術(shù)進(jìn)一步降低數(shù)據(jù)集掃描成本，是第一項(xiàng)遵循基于模式增長的方法來挖掘含有負(fù)項(xiàng)HUIs 的工作。

3.3 基于效用列表

FHN算法引入了幾種應(yīng)對(duì)負(fù)項(xiàng)的策略，是FHM 算法的擴(kuò)展，使用效用列表和EUCS 結(jié)構(gòu)來有效地挖掘HUIs，利用TWU 和剩余效用來修剪搜索空間。FHN 在單個(gè)階段中挖掘HUIs，雖然避免了候選項(xiàng)集的生成，但是可能會(huì)生成數(shù)據(jù)集中沒有的候選項(xiàng)。

GHUM（Generalized High Utility Mining）提出了一種簡化的、基于效用列表的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)項(xiàng)集的信息，它不使用單獨(dú)的效用列表來存儲(chǔ)項(xiàng)目，按照項(xiàng)目的支持度升序?qū)ω?fù)項(xiàng)排序，從而有效地生成候選項(xiàng)。GHUM 采用并修改了現(xiàn)有的修剪策略U-Prune 和LA-Prune；同時(shí)，基于效用列表的算法需要執(zhí)行連接操作來評(píng)估候選項(xiàng)集，因此，它提出了一種新的剪枝策略N-Prune（Novel Pruning strategy），由此顯著減少了候選項(xiàng)總數(shù)；最后，提出了一種基于屬性的反單調(diào)剪枝策略A-Prune（Anti-monotonic property based Pruning strategy）。

Fournier-Viger 等提出了FOSHU（Faster On-Shelf High Utility itemset mining）算法，用于從貨架數(shù)據(jù)集中挖掘包含負(fù)項(xiàng)的HUIs，它是FHN 算法的擴(kuò)展，利用效用列表結(jié)構(gòu)來存儲(chǔ)項(xiàng)目信息。FOSHU 在不生成候選對(duì)象的情況下在一個(gè)階段中挖掘項(xiàng)集，并且同時(shí)挖掘所有時(shí)間段，而不是分別挖掘每個(gè)時(shí)間段；避免了對(duì)每個(gè)時(shí)間段中發(fā)現(xiàn)的項(xiàng)集進(jìn)行昂貴的合并操作。

呂存?zhèn)サ忍岢隽撕?fù)項(xiàng)的高效用序列模式挖掘（Efficiently mining High Utility Sequential pattern with Negative unit profits，EHUSN）算法，采用效用列表快速構(gòu)建非候選序列，進(jìn)而提升算法的時(shí)間空間效率，存在的問題為算法的剪枝效果受閾值大小的影響。

陳麗娟等提出了EHINM（Efficient High utility Itemsets with Negative items values Mining）算法，在算法中介紹了一種改良的效用列表結(jié)構(gòu)，并用來存儲(chǔ)效用信息。所提出的效用列表結(jié)構(gòu)是一種三元組結(jié)構(gòu)，可以縮小存儲(chǔ)空間，同時(shí)也可以依據(jù)結(jié)構(gòu)中保存的信息來縮小搜索空間。

THN（Top-

k

High utility itemsets with Negative items）是第一種在Top-

k

模式挖掘中考慮負(fù)項(xiàng)的算法，算法提出了一種自動(dòng)提升

minutil

的策略，同時(shí)使用事務(wù)合并和數(shù)據(jù)集投影技術(shù)和減少掃描數(shù)據(jù)集成本，并使用重新定義的子樹效用值和重新定義的本地效用值來修剪搜索空間。

3.4 基于數(shù)組

先前討論的HUINIV-Mine 和FHN 算法挖掘出的規(guī)則包括非常多的微小項(xiàng)集，EHNL（Efficient High utility itemsets mining with Negative utility and Length constraints）通過在包含負(fù)效用值的項(xiàng)集中結(jié)合長度約束的概念克服了這個(gè)缺陷。算法使用模式增長方法來挖掘包含負(fù)項(xiàng)的HUIs，僅考慮那些出現(xiàn)在數(shù)據(jù)集中的候選項(xiàng)集。算法引入了最小長度約束，以刪除大量細(xì)小的項(xiàng)目集，還使用最大長度約束來限制太長的項(xiàng)目集。為了降低數(shù)據(jù)集掃描成本，還利用數(shù)據(jù)集投影和事務(wù)合并技術(shù)。為了提高效率，算法利用子樹修剪策略來減小搜索空間，但是面臨的主要問題是如何將子樹修剪策略、長度約束與負(fù)效用項(xiàng)集挖掘結(jié)合在一起。為了解決這些問題，算法根據(jù)事務(wù)的效用值以非遞增順序?qū)κ聞?wù)中的項(xiàng)目進(jìn)行排序，并借助偏移指針將負(fù)項(xiàng)目保留在已排序項(xiàng)目的末尾；另一個(gè)問題是如何有效地計(jì)算項(xiàng)目集的效用，為了解決這個(gè)問題，算法使用基于數(shù)組的效用計(jì)數(shù)技術(shù)來計(jì)算線性時(shí)間和可忽略的存儲(chǔ)空間中的效用值。

3.5 小結(jié)

將帶有負(fù)效用的模式挖掘方法以各種關(guān)鍵技術(shù)為角度進(jìn)行分類，包括基于先驗(yàn)、基于樹、基于列表和基于數(shù)組。其中基于先驗(yàn)的HUPM 算法需要多次掃描數(shù)據(jù)集導(dǎo)致時(shí)空性能較低；基于樹的HUPM 算法使用結(jié)構(gòu)較為緊湊，但在處理樹結(jié)構(gòu)時(shí)會(huì)耗費(fèi)較多的時(shí)間并占用更多內(nèi)存；基于列表的HUPM 算法結(jié)構(gòu)易為實(shí)現(xiàn)，缺點(diǎn)為列表合并時(shí)的昂貴操作依舊會(huì)導(dǎo)致算法效率變低；基于數(shù)組的HUPM 算法可以處理大量數(shù)據(jù)，但在插入、刪除等情況下表現(xiàn)不佳，不適合動(dòng)態(tài)存儲(chǔ)。表4 對(duì)帶有負(fù)效用的高效用模式挖掘算法進(jìn)行了分析，其中各類方法的總結(jié)如圖2 所示。

表4 含負(fù)項(xiàng)的模式挖掘算法對(duì)比Tab 4 Comparison of pattern mining algorithms with negative items

圖2 含負(fù)項(xiàng)的模式挖掘算法下的各類方法優(yōu)缺點(diǎn)Fig.2 Advantages and disadvantages of different methods with pattern mining algorithms with negative items

4 不同類型的高效用模式挖掘

4.1 Top-k高效用模式挖掘

傳統(tǒng)HUPM 算法的另一個(gè)局限性在于如何設(shè)置

minutil

，其值會(huì)極大地影響執(zhí)行時(shí)間、內(nèi)存使用率以及向用戶顯示的模式數(shù)量。一方面，如果用戶將

minutil

閾值設(shè)置得太低，則可能會(huì)發(fā)現(xiàn)大量模式，并且算法可能會(huì)變慢并消耗大量內(nèi)存；另一方面，如果用戶將

minutil

閾值設(shè)置得太高，可能會(huì)發(fā)現(xiàn)很少或沒有模式。為了解決這個(gè)問題，引入了Top-

k

高效用項(xiàng)集（Top-

k

HUI，THUI）挖掘問題。THUI 挖掘問題主要是HUIs 挖掘問題的一種變體，它允許決策者指定所需數(shù)量的HUIs，而不是最小效用閾值。TKU（Top-

K

Utility itemsets mining）是從事務(wù)數(shù)據(jù)庫中挖掘Top-

k

高效用模式的最早算法之一。該算法分兩個(gè)階段挖掘HUIs，在第一階段構(gòu)建UP-Tree，并生成潛在的前

K

個(gè)HUI；在第二階段數(shù)據(jù)庫掃描之后，從其中確定Top-

k

HUIs。REPT（Raising threshold with Exact and Pre-calculated utilities for Top-

k

high utility pattern mining）是挖掘THUI 的另一種兩階段方法，該算法的整體功能類似于前面所述的TKU 算法。在數(shù)據(jù)庫的第一次掃描期間，REPT 算法將構(gòu)造效用降序的預(yù)評(píng)估矩陣（Pre-evaluation Matrix with Utility Descending order，PMUD），PMUD 類似于TKU 算法中使用的PE（Pre-Evaluation）矩陣，關(guān)鍵區(qū)別在于矩陣中維護(hù)的二項(xiàng)集的性質(zhì)。TKEH（Efficient algorithm for mining Top-

K

High utility itemsets）算法降低數(shù)據(jù)集掃描成本的技術(shù)為：事務(wù)合并和數(shù)據(jù)集投影技術(shù)，當(dāng)探索更大的項(xiàng)目時(shí)，這些技術(shù)會(huì)減少計(jì)算項(xiàng)目和上限的效用。PTM（Prefix-partitioning-based Top-

k

high utility itemset Mining）算法能夠在海量數(shù)據(jù)中挖掘Top-

k

模式，PTM 將事務(wù)數(shù)據(jù)庫維護(hù)為一組基于前綴的分區(qū)，項(xiàng)集的效用則通過一個(gè)特定分區(qū)中的事務(wù)來計(jì)算；使用了基于全后綴效用的子樹剪枝規(guī)則，有效地減小了集合枚舉樹的探索空間。

4.2 高平均模式挖掘

在傳統(tǒng)的HUPM 算法中，項(xiàng)集的效用值定義為項(xiàng)集在所出現(xiàn)在事務(wù)中的效用值之和，此定義的一個(gè)重要問題是它沒有考慮項(xiàng)集長度。由于較大項(xiàng)目集的效用通常大于較小項(xiàng)集的效用，因此傳統(tǒng)的HUPM 算法傾向于查找一組大型項(xiàng)目集，證明了該定義不是效用的最合理的衡量。為了更好地評(píng)估每個(gè)項(xiàng)集的效用，提出了高平均效用項(xiàng)集挖掘（High Average Utility Itemset Mining，HAUIM）的任務(wù)，它同時(shí)考慮了項(xiàng)目集的長度及其效用，因此更適合實(shí)際情況，為此任務(wù)設(shè)計(jì)了幾種算法。

Lin 等提出了一種平均效用列表結(jié)構(gòu)AU（Average-Utility）-list，該結(jié)構(gòu)只保留挖掘過程所需的信息，從而將非常大的數(shù)據(jù)庫壓縮。提出了一種有效的修剪策略，通過及早修剪沒有希望的候選項(xiàng)來減小搜索空間，避免在枚舉樹中構(gòu)建處理節(jié)點(diǎn)的擴(kuò)展AU-list，以減少計(jì)算量。

Lin 等設(shè)計(jì)了一個(gè)高平均效用模式樹結(jié)構(gòu)（High Average Utility Pattern-tree，HAUP-tree）來更有效地挖掘HAUI。Lan 等開發(fā)了一種基于投影的平均效用挖掘（Projection-Based approach for mining high AU itemsets，PBAU）算法來挖掘HAUI。Lan 等還擴(kuò)展了PBAU 算法，并設(shè)計(jì)了一種使用改進(jìn)的策略來挖掘HAUI 的PAI（uses the Prefix concept to create tighter upper bounds of Average-utility values for Itemsets）方法。Lu 等開發(fā)了一種HAUI-tree 結(jié)構(gòu)來挖掘沒有候選生成的HAUI。

LMHAUP（List-based Mining of HAUP）采用了兩個(gè)新的上限：事務(wù)最大平均效用上限和最大剩余平均效用上限，利用這兩個(gè)上限可以極大地減小查找高平均效用模式的搜索空間，而無需多次掃描數(shù)據(jù)庫。在算法中設(shè)計(jì)了一種基于列表的結(jié)構(gòu)，稱為TA-List，其中只存儲(chǔ)提取高平均效用模式的必要信息，旨在最小化加入過程的成本，這是列表結(jié)構(gòu)的缺點(diǎn)之一。因此，與使用列表結(jié)構(gòu)的最先進(jìn)的高平均效用模式挖掘算法相比，LMHAUP 花費(fèi)更少的內(nèi)存和運(yùn)行時(shí)間。

4.3 高效用序列模式挖掘

高效用序列模式挖掘（High Utility Sequential Pattern Mining，HUSPM）的問題旨在在定量序列數(shù)據(jù)庫中發(fā)現(xiàn)具有高效用的子序列，要考慮項(xiàng)目及其效用之間的順序排序（根據(jù)購買數(shù)量和單位利潤等標(biāo)準(zhǔn)）。高效用序列挖掘已被應(yīng)用于多種應(yīng)用中，由于序列的效用度量不滿足向下閉包屬性，因此比一般高效用模式挖掘更具挑戰(zhàn)性。

已經(jīng)設(shè)計(jì)了許多算法來發(fā)現(xiàn)序列數(shù)據(jù)庫中的序列模式。最受歡迎的是GSP（discovers these Generalized Sequential Patterns）、PSP（Projection-based，Sequential Pattern-growth approach）、SPAM（Sequential PAttern Mining）。所有這些序列模式挖掘算法都將序列數(shù)據(jù)庫和最小支持閾值作為輸入，并輸出高效的序列模式集。對(duì)于序列模式挖掘任務(wù)，始終只有一個(gè)正確答案，因此，如果所有序列模式挖掘算法在相同的數(shù)據(jù)庫上以相同的參數(shù)運(yùn)行，則它們將返回相同的序列模式集。所以各種算法之間的差異不是它們的輸出，而是每種算法如何發(fā)現(xiàn)序列模式，各種算法利用不同的策略和數(shù)據(jù)結(jié)構(gòu)來有效地搜索順序模式。

4.4 其他高效用模式挖掘

傳統(tǒng)的高效用項(xiàng)集挖掘算法不認(rèn)為項(xiàng)集的效用值可能隨時(shí)間變化，因此無法找到只在特定時(shí)間段內(nèi)為高效用項(xiàng)集的模式，發(fā)現(xiàn)這樣的項(xiàng)集很有用，因?yàn)槟撤N產(chǎn)品在特定時(shí)間段可能會(huì)賣得特別好，但是在一年中的其余時(shí)間則不會(huì)。通過定義挖掘局部高效用項(xiàng)集（Local HUI，LHUI）的問題和挖掘高峰高效用項(xiàng)集（Peak HUI，PHUI）的問題來解決HUPM的這一局限。

Fournier-Viger 等提出了名為LHUI-Miner（Local HUI Miner）和PHUIMiner（Peak HUI Miner）的算法來挖掘這些模式，它依賴于名為LU-list（Local Utility-list）的新型數(shù)據(jù)結(jié)構(gòu)，并擴(kuò)展了HUI-Miner 算法的基本搜索過程和效用列表數(shù)據(jù)結(jié)構(gòu)。算法將挖掘LHUI 的問題擴(kuò)展到挖掘PHUI 問題，它包括查找項(xiàng)集具有高效用的時(shí)間段。由于PHUI 的集合可能很大，并且PHUI 中出現(xiàn)的某些項(xiàng)目對(duì)其峰值的貢獻(xiàn)不大，因此提出了第三個(gè)問題，即挖掘一個(gè)較小的模式集，稱為非冗余峰值高效用項(xiàng)集（Non redundant Peak HUI，NPHUI），針對(duì)此問題設(shè)計(jì)了一種名為NPHUI-Miner（Non redundant Peak HUI Miner）的算法。與傳統(tǒng)的HUPM 算法相比，該算法為用戶提供了更多的信息，因?yàn)樵撍惴梢宰R(shí)別模式具有較高效用的時(shí)間間隔，而不僅僅是在整個(gè)數(shù)據(jù)庫中檢查模式是否具有較高的效用。實(shí)際上，此問題證明了傳統(tǒng)的HUIs 挖掘問題是LHUI 挖掘問題的特例。

4.5 小結(jié)

考慮到傳統(tǒng)HUPM 算法的一些局限性，學(xué)者們提出了多種高效用衍生模式。因傳統(tǒng)HUPM 算法無法設(shè)置合適的

minutil，

所以提出了Top-

k

高效用模式挖掘算法，解決了傳統(tǒng)HUPM 方法對(duì)

minutil

設(shè)置比較敏感的問題，在算法中只需設(shè)置

k

值，避免了閾值對(duì)模式數(shù)量的影響。高平均效用模式挖掘算法則考慮了項(xiàng)集的長度及其效用，解決了傳統(tǒng)HUPM 算法沒有考慮項(xiàng)集長度的問題，因此更適合實(shí)際情況。實(shí)際生活中的數(shù)據(jù)庫中大多項(xiàng)目是有順序性的，高效用序列模式的提出考慮到了項(xiàng)目及其效用之間的順序排序，更加適用于處理現(xiàn)實(shí)生活中的數(shù)據(jù)集。而局部高效用模式可以挖掘出只在特定時(shí)間段為高效用的模式，在此基礎(chǔ)上擴(kuò)展而來的峰值高效用模式挖掘方法可以查找項(xiàng)集具有高效用的時(shí)間段。

5 下一步工作

盡管高效用模式挖掘的問題已經(jīng)研究了十多年，并且已經(jīng)發(fā)表了許多有關(guān)該主題的算法和概述，但是仍然有許多研究機(jī)會(huì)：

1）含負(fù)項(xiàng)的HUPM 方法在現(xiàn)階段主要應(yīng)用于靜態(tài)模式挖掘中，但在大數(shù)據(jù)環(huán)境下已不能滿足現(xiàn)實(shí)要求。對(duì)此，下一步將研究在動(dòng)態(tài)數(shù)據(jù)庫中挖掘含負(fù)項(xiàng)HUIs 的算法，將FHN 算法中處理負(fù)項(xiàng)時(shí)用到的屬性、剪枝條件等應(yīng)用在性能優(yōu)異的增量模式挖掘算法中，以此來解決現(xiàn)有動(dòng)態(tài)模式挖掘算法只能處理正項(xiàng)的局限性。

2）盡管已經(jīng)設(shè)計(jì)了一些算法來從增量數(shù)據(jù)庫中挖掘高效用模式，但在挖掘過程中它們?nèi)匀挥行阅芟拗?。IIHUM 算法可以在不生成任何候選對(duì)象的情況下提取高效用模式，今后將其中的增量數(shù)據(jù)處理技術(shù)應(yīng)用于不同類型的流模式挖掘領(lǐng)域，如基于滑動(dòng)窗口和阻尼窗口模型的數(shù)據(jù)挖掘環(huán)境。

3）滑動(dòng)窗口中最重要的參數(shù)之一為窗口大小，其大小直接影響著模式挖掘時(shí)的性能。今后將設(shè)計(jì)定義一種方法來自動(dòng)設(shè)置窗口大小參數(shù)；但是動(dòng)態(tài)地調(diào)整窗口大小是很有挑戰(zhàn)性的，因?yàn)樗枰x新的上界，這些上界對(duì)于不同的窗口長度都是有效的，同時(shí)又不會(huì)過于寬松，以致無法有效地減小搜索空間和挖掘模式。

6 結(jié)語

近年來，高效用模式挖掘已經(jīng)引起了人們的廣泛關(guān)注和研究，并已取得大量研究成果。本文對(duì)高效用模式挖掘進(jìn)行了系統(tǒng)綜述，首先以效用值的正負(fù)為角度對(duì)高效用模式進(jìn)行了劃分；之后進(jìn)一步對(duì)帶有正效用的HUPM 方法以數(shù)據(jù)庫的動(dòng)靜為標(biāo)準(zhǔn)進(jìn)行劃分，而帶有負(fù)效用的模式挖掘算法則以各種關(guān)鍵技術(shù)進(jìn)行了分類，同時(shí)從多種角度對(duì)HUPM 算法進(jìn)行了分析和總結(jié)；隨后，介紹了幾種經(jīng)典的高效用衍生模式，包括模式的提出背景及解決問題；最后，提出高效用模式挖掘算法的下一步研究方向，包括在大數(shù)據(jù)環(huán)境下用于處理負(fù)項(xiàng)的關(guān)鍵技術(shù)與動(dòng)態(tài)模式挖掘算法的結(jié)合，增量挖掘技術(shù)與數(shù)據(jù)流環(huán)境的結(jié)合，數(shù)據(jù)流中窗口參數(shù)的動(dòng)態(tài)調(diào)整等問題，動(dòng)態(tài)模式挖掘?qū)?huì)是以后的工作之重。