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

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

0 引言

項(xiàng)集挖掘是數(shù)據(jù)挖掘的一個(gè)重要分支［1］，頻繁項(xiàng)集挖掘（Frequent Itemset Mining，F(xiàn)IM）旨在找到客戶的交易中頻繁一起購買的物品［2］，但是忽略了物品的利潤(rùn)信息［3］，為了解決這個(gè)局限性，文獻(xiàn)［4-5］中將物品的單位利潤(rùn)和數(shù)量分別視為外部效用和內(nèi)部效用，進(jìn)而提出了一系列的高效用項(xiàng)集挖掘（High Utility Itemset Mining，HUIM）方法［6-12］。比如在超市銷售中，F(xiàn)IM 認(rèn)為顧客購買3 瓶飲料比購買1 件首飾重要，忽略了1 件首飾的利潤(rùn)要遠(yuǎn)大于3 瓶飲料所帶來的利潤(rùn)；而HUIM 考慮事務(wù)的效用，認(rèn)為顧客購買1 件首飾要比購買3瓶飲料重要。

然而，枚舉數(shù)據(jù)集中所有的高效用項(xiàng)集（High Utility Itemset，HUI）很難實(shí)現(xiàn)，且當(dāng)數(shù)據(jù)集的大小和數(shù)據(jù)集中不同項(xiàng)的總數(shù)增加時(shí)，現(xiàn)有確定性算法的性能會(huì)隨之降低［13］。此外，HUI 往往分散在搜索空間中，這使得挖掘算法必須考慮大量項(xiàng)集才能發(fā)現(xiàn)實(shí)際的HUI。近似算法的使用可以在結(jié)果完整性和算法的性能之間提供良好的平衡［14］，突破了傳統(tǒng)模式挖掘方法的性能瓶頸［15］。智能優(yōu)化算法具有解決復(fù)雜、線性和高度非線性問題的能力，可以探索大型問題空間，根據(jù)適應(yīng)度函數(shù)找到接近最優(yōu)的解決方案［16］，因此基于智能優(yōu)化算法的HUIM 成為一個(gè)新興的研究主題。

Kannimuthu 等［17］將遺傳算法（Genetic Algorithm，GA）應(yīng)用于 HUIM，提出HUPEUMU-GARM（High Utility Pattern Extraction using Genetic Algorithm with Ranked Mutation Using Minimum Utility threshold）方法和不需要指定最小效用閾值的 HUPEWUMU-GARM（High Utility Pattern Extraction using Genetic Algorithm with Ranked Mutation Without Using Minimum Utility threshold）方法，這是智能優(yōu)化算法在HUIM中的首次應(yīng)用，能夠在指數(shù)搜索空間中快速有效地挖掘HUI。與基于GA 的HUIM 方法相比，基于粒子群優(yōu)化（Particle Swarm Optimization，PSO）的技術(shù)需要更少的參數(shù)，無需設(shè)置合理的交叉和變異率，可以很容易實(shí)現(xiàn)［18］。Lin等［19-20］首次將PSO 應(yīng)用于HUIM，在粒子更新過程中采用sigmoid 函數(shù)，并開發(fā)了OR/NOR-tree 結(jié)構(gòu)［18］，通過提前修剪粒子的無效組合避免對(duì)數(shù)據(jù)庫的多次掃描。Song 等［21］從人工蜂群（Artificial Bee Colony，ABC）算法的角度對(duì)HUIM 問題進(jìn)行建模，利用位圖進(jìn)行信息表示和搜索空間剪枝，加速了HUI 的發(fā)現(xiàn)。Song 等［22］從人工魚群（Artificial Fish swarm，AF）算法的角度研究了HUIM 問題，并提出一種名為HUIM-AF（HUIM methods based on AF algorithm）的HUIM 方法。此外，智能優(yōu)化算法還可以用于挖掘HUI 的復(fù)雜模式，例 如，Song 等［23］提出了 基于標(biāo) 準(zhǔn)PSO 方法的HAUI-PSO（mining High Average-Utility Itemsets based on PSO）算法挖掘高平均效用項(xiàng)集（High Average Utility Itemsets，HAUI）；Lin等［24］提出了一種基于GA 的算法DcGA（Decomposition based on a compact GA），在有限的時(shí)間內(nèi)高效地挖掘閉合高效用項(xiàng)集（Closed HUI，CHUI）；Song 等［25］提出了基于交叉熵的方法 TKU-CE+（Top-Khigh-Utility itemset mining based on Cross-Entropy method），用于啟發(fā)式地挖掘top-k高效用項(xiàng)集。

現(xiàn)有的相關(guān)綜述中，Logeswaran 等［26］從模式的角度對(duì)元啟發(fā)式的模式挖掘方法進(jìn)行介紹，并未以智能優(yōu)化算法的類別為角度對(duì)HUIM 進(jìn)行綜述；Djenouri 等［27］從GA、PSO 和蟻群優(yōu)化（Ant Colony Optimization，ACO）算法這3 個(gè)方面對(duì)頻繁模式挖掘和HUIM 的個(gè)別方法進(jìn)行了研究；張妮等［28］從正與負(fù)的角度劃分了高效用模式挖掘方法；單芝慧等［29］從增量數(shù)據(jù)、數(shù)據(jù)流等角度對(duì)高效用模式及融合高效用模式進(jìn)行了較全面的分析總結(jié)。為了使研究者能夠?qū)χ悄軆?yōu)化算法在HUIM 的應(yīng)用有一個(gè)更加清晰的了解，本文從不同類型的智能優(yōu)化算法的角度對(duì)HUIM 方法進(jìn)行分類綜述。本文的總體框架如圖1所示。

圖1 文章框架Fig.1 Framework of the paper

本文的主要工作如下：

1）首次把基于智能優(yōu)化算法的HUIM 方法分為基于群智能優(yōu)化算法、基于進(jìn)化算法（Evolutionary Algorithm，EA）和基于其他算法的HUIM，并作了全面的分析與總結(jié)。

2）首次把基于PSO 的HUIM 算法從粒子更新策略的角度分為5 類進(jìn)行比較，包括：基于傳統(tǒng)更新策略、基于sigmoid函數(shù)、基于貪心、基于輪盤賭和基于集合的HUIM。

3）分析總結(jié)了現(xiàn)有的基于智能優(yōu)化算法的HUIM 的優(yōu)點(diǎn)和不足，從數(shù)據(jù)流、自適應(yīng)、剪枝策略和復(fù)雜模式等角度給出下一步的研究方向以供參考。

1 背景介紹

1.1 高效用項(xiàng)集挖掘概念

令I(lǐng)={i1，i2，…，in}是由一組項(xiàng)組成的集合，令DB是一個(gè)數(shù)據(jù)庫，這個(gè)數(shù)據(jù)庫中有一個(gè)效用列表（表1）和一個(gè)事務(wù)列表（表2）。效用列表中的每個(gè)項(xiàng)I都有一個(gè)效用值。事務(wù)列表中的每個(gè)事務(wù)T都有一個(gè)唯一的標(biāo)識(shí)符tid，且T是I的一個(gè)子集，其中每個(gè)項(xiàng)都與一個(gè)計(jì)數(shù)值相關(guān)聯(lián)。若一個(gè)項(xiàng)是I的子集，且包含k個(gè)項(xiàng)，則稱之為k-項(xiàng)集［8］。

表1 效用列表Tab.1 Utility list

表2 事務(wù)列表Tab.2 Transaction list

定義1 項(xiàng)i的外部效用［8］表示為eu（i），是DB效用表中i的效用值。例如，在表1 中，項(xiàng)a的外部效用eu（a）=9。

定義2 事務(wù)T中項(xiàng)i的內(nèi)部效用［8］表示為iu（i，T），是DB的事務(wù)表中與T中i相關(guān)聯(lián)的計(jì)數(shù)值。例如在表2 中，事務(wù)T1中項(xiàng)a的內(nèi)部效用iu（a，T1）=5。

定義3 事務(wù)T中項(xiàng)i的效用［6］表示為u（i，T），是iu（i，T）和eu（i）的乘積，其中u（i，T）=iu（i，T）×eu（i）。例如，事務(wù)T1中項(xiàng)a的效用，為u（a，T1）=iu（a，T1）×eu（a）=5×9=45。

定義4 事務(wù)T中項(xiàng)集X的效用［6］表示為u（X，T），是項(xiàng)集X中所有項(xiàng)的效用之和，其中X?T。例如，事務(wù)T1中項(xiàng)集｛ab｝的效用，u（｛ab｝，T1）=u（a，T1）+u（b，T1）=5×9+3×7=66；事務(wù)T3中項(xiàng)集｛ab｝的效用，u（｛ab｝，T3）=u（a，T3）+u（b，T3）=9×9+3×7=102。

定義5 項(xiàng)集X的效用［7］表示為u（X），是數(shù)據(jù)庫DB中所有包含X的事務(wù)T中，項(xiàng)集X的效用之和。例如，項(xiàng)集｛ab｝的效用為｛ab｝在事務(wù)T1中的效用加上｛ab｝在事務(wù)T3中的效用，即u（｛ab｝）=u（｛ab｝，T1）+u（｛ab｝，T3）=66+102=168。

定義6 事務(wù)T的效用［7］表示為tu（T），是T中所有項(xiàng)的效用之和（如式（1）所示）。

其中數(shù)據(jù)庫DB的總效用是DB中所有事務(wù)的效用之和。

表2 顯示了每個(gè)事務(wù)的效用，例如，事務(wù)T1的效用為tu（T1）=u（a，T1）+u（b，T1）+u（d，T1）=9×5+7×3+1×1=67。表2中數(shù)據(jù)庫的總效用是409。如果u（X）不小于用戶指定的最小效用閾值（用minutil表示），或者不小于minutil與被挖掘數(shù)據(jù)庫的總效用（如果minutil是一個(gè)百分比）的乘積，則項(xiàng)集X是高效用項(xiàng)集［8］。給定一個(gè)數(shù)據(jù)庫和一個(gè)最小效用閾值minutil，HUIM 問題是從數(shù)據(jù)庫中發(fā)現(xiàn)效用不小于minutil的所有項(xiàng)集［11］。

定義7DB中項(xiàng)集X的事務(wù)加權(quán)效用（transactionweighted utility）［9］記為twu（X），是數(shù)據(jù)庫DB中包含項(xiàng)集X的所有事務(wù)的效用之和（如式（2）所示）。如表1 所示，項(xiàng)集｛a｝的事務(wù)加權(quán)效用twu（｛a｝）=

tu（T1）+tu（T2）+tu（T5）=67+125+74=266。

1.2 智能優(yōu)化算法

1.2.1 PSO 算法

PSO 算法是針對(duì)連續(xù)優(yōu)化問題提出的［30-31］，但通過二進(jìn)制編碼可以得到離散變量的PSO 形式，因此也可用于離散系統(tǒng)中組合優(yōu)化問題的求解。PSO 算法實(shí)現(xiàn)步驟如圖2 所示。

圖2 PSO算法的基本流程Fig.2 Basic flow of PSO algorithm

設(shè)待求解的優(yōu)化問題維數(shù)為N，粒子群體規(guī)模為M。在PSO 中，xi=(xi1，xi2，…，xiN)表示第i個(gè)粒子的位置，vi=（vi1，vi2，…，viN）表示第i個(gè)粒子的速度，pbesti=（pbesti1，pbesti2，…，pbestiN）表示第i個(gè)粒子所搜尋到的最好的位置，gbest=（gbest1，gbest2，…，gbestN）表示整個(gè)群體搜尋到的最好的位置。

首先，隨機(jī)初始化粒群的位置和速度，計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值，一般地，在基于PSO 的HUIM 中，項(xiàng)集X的適應(yīng)度函數(shù)值由其效用值確定［17］，如式（3）所示：

接著，計(jì)算并更新每個(gè)粒子的最好位置（pbest）和整個(gè)群體或鄰域內(nèi)的最好位置（gbest），根據(jù)式（4）（5）更新粒子的速度或位置，即更新候選項(xiàng)集，這也是相應(yīng)HUIM 各算法之間的不同之處（將在2.1 節(jié)詳細(xì)闡述）。若達(dá)到終止條件，即產(chǎn)生的HUI 在一定的時(shí)間內(nèi)是重復(fù)的（即算法收斂）或者達(dá)到了一定的循環(huán)次數(shù)，算法停止；否則，算法進(jìn)入循環(huán)，直到滿足停止條件為止。

其中i=1，2，…，M（M為粒子群體規(guī)模）；d=1，2，…，N（N為待求解的優(yōu)化問題維數(shù)）；c1、c2為學(xué)習(xí)因子；t為迭代次數(shù)；r1和r2是在［0，1］上服從均勻分布的隨機(jī)數(shù)；ω是權(quán)重慣性系數(shù)，能夠?qū)崿F(xiàn)PSO 全局探索和局部開發(fā)能力的平衡。

1.2.2 遺傳算法

遺傳算法可以解決高度復(fù)雜的非線性問題［32］。它用于研究非常大的問題空間，在多重約束下根據(jù)適應(yīng)度函數(shù)找到最佳解決方案。遺傳算法從大量可行的解決方案開始，并通過交叉和變異找到更好的解決方案［17］。

遺傳算法的基本流程如圖3 所示。

圖3 遺傳算法的基本流程Fig.3 Basic flow of genetic algorithm

首先，給出一個(gè)有N個(gè)染色體（解的編碼）的初始群體pop（1），對(duì)群體pop（t）中的每一個(gè)染色體popi（t）計(jì)算它的適應(yīng)度函數(shù)值，與基于PSO 的HUIM 類似，在基于GA 的HUIM中，項(xiàng)集X的適應(yīng)函數(shù)值由其效用值確定，如式（3）所示。若滿足停止規(guī)則，算法停止，此時(shí)的種群即為HUI；否則，根據(jù)式（6）計(jì)算概率Pi，并以概率Pi從pop（t）中隨機(jī)選擇一些染色體（Chromosome）構(gòu)成新的種群pop（t+1）。

以概率Pc進(jìn)行交叉操作得到一個(gè)有Numr個(gè)染色體的crosspop（t+1），以較小的概率Pm，使得一個(gè)染色體的基因發(fā)生變異，形成mutpop（t+1）。根據(jù)式（7）得到一個(gè)新的種群，算法返回，計(jì)算新種群的適應(yīng)度函數(shù)值，直到滿足停止條件。通常，在HUIM 中，算法停止的條件為沒有新的HUI 產(chǎn)生（即算法收斂）或者循環(huán)達(dá)到了一定的次數(shù)。

2 基于群智能優(yōu)化算法

2.1 基于粒子群優(yōu)化算法

粒子群優(yōu)化算法具有模型簡(jiǎn)單、控制參數(shù)少、易于實(shí)現(xiàn)、運(yùn)行速度快等優(yōu)點(diǎn)，因此被廣泛用于HUI 的挖掘工作中，并取得了可觀的效果。本節(jié)從粒子更新策略的角度對(duì)基于粒子群優(yōu)化算法的HUIM 方法進(jìn)行了綜述。

傳統(tǒng)的粒子更新策略僅使用式（4）（5）對(duì)粒子進(jìn)行速度和位置的更新。Pears 等［33］提出WARM SWARM（Weighted Association Rule Mining using particle SWARM optimization）方法，將粒子群優(yōu)化與加權(quán)關(guān)聯(lián)規(guī)則挖掘相結(jié)合，使用粒子群優(yōu)化為關(guān)聯(lián)規(guī)則挖掘分配有意義的項(xiàng)目權(quán)重。實(shí)驗(yàn)結(jié)果表明，雖然使用粒子群優(yōu)化進(jìn)行權(quán)重?cái)M合有一定的開銷，但該方法也明顯快于標(biāo)準(zhǔn)Apriori，且可以產(chǎn)生有趣和有意義的規(guī)則，當(dāng)數(shù)據(jù)集的大小增加時(shí)，這一點(diǎn)尤其明顯。Sivamathi等［34］提出了SCE-PSO（Shuffled Complex Evolution of PSO）方法，首先在可行空間中隨機(jī)抽取一組粒子，然后將種群劃分為若干個(gè)復(fù)合體，在每個(gè)復(fù)合體中使用PSO 算法挖掘HUI。

基于sigmoid函數(shù)的粒子更新策略可以使種群具有較高的多樣性。Lin 等［20］首次采用了二進(jìn)制粒子群優(yōu)化（Binary Particle Swarm Optimization，BPSO）［35］算法有效地挖掘HUI，提出了一種基于PSO 的HUIM-BPSOsig 方法。首先基于事務(wù)加權(quán)效用模型，將發(fā)現(xiàn)的高事務(wù)加權(quán)效用1-項(xiàng)集（High Transaction Weighted Utilization 1-Itemsets，1-HTWUIs）的數(shù)量設(shè)置為粒子的大小，大幅減少了進(jìn)化過程中的組合問題。以表2 中的數(shù)據(jù)庫為例，假設(shè)最小效用閾值為200，根據(jù)表1，將1-項(xiàng)集｛e｝從數(shù)據(jù)庫中刪除，找到的1-HTWUIs有｛a｝、｛b｝、｛c｝、｛d｝，粒子大小即為4。在粒子的編碼階段，利用位圖編碼項(xiàng)集，每個(gè)粒子由一組二進(jìn)制變量組成，如0或1，表示粒子中存在或不存在相應(yīng)的項(xiàng)。例如項(xiàng)集｛b，c｝可以用圖4來表示。

圖4 粒子位圖編碼Fig.4 Particle bitmap encoding

在粒子的更新階段，利用式（1）更新粒子的速度，再采用sigmoid 函數(shù)更新粒子的位置，如式（8）所示：

其中：rand（·）生成（0，1）的隨機(jī)數(shù)；t代表迭代次數(shù)為第i個(gè)粒子的第j個(gè)位置的位置代表第i個(gè)粒子的第j個(gè)位置的速度。

Lin 等［18］設(shè)計(jì)了HUIM-BPSO 方法，在HUIM-BPSOsig 的基礎(chǔ)上添加了OR/NOR-tree 結(jié)構(gòu)，通過提前修剪粒子的無效組合減少多次數(shù)據(jù)庫掃描。例如表2 中的數(shù)據(jù)庫可以用OR/NOR-tree 表示為圖5。

圖5 OR/NOR-tree結(jié)構(gòu)Fig.5 OR/NOR-tree structure

這個(gè)過程可以減少無效粒子（即原始數(shù)據(jù)庫中不存在的粒子）的計(jì)算，進(jìn)而有效地從非常緊湊的數(shù)據(jù)集中識(shí)別完整的HUI。Gunawan 等［36］提出一種無需最小效用閾值挖掘高效用項(xiàng)集的HUIM-BPSO-nomut 方法，基于BPSO 算法將所有項(xiàng)集輸出為按效用排序的列表，最小效用閾值則作為后續(xù)處理步驟施加在此列表之上。將具有最高效用的事務(wù)作為粒子的初始種群，并根據(jù)式（9）更新速度，然后將粒子的最大速度限制為vmax，確保每個(gè)速度分量都保持在特定的范圍內(nèi)，最后利用sigmoid 函數(shù)更新粒子位置（式（8））。

其中k為收縮因子，在全局最佳粒子與局部最佳粒子之間起到平衡作用。k的設(shè)置如式（10）所示：

靳曉樂等［37］對(duì)基本二元粒子群算法進(jìn)行改進(jìn)，提出一種雙重二元粒子群優(yōu)化（Double Binary PSO，DBPSO）算法。運(yùn)用最小相對(duì)效用閾值和效用上界的乘積確定最小效用閾值，然后通過最小效用閾值和適應(yīng)度函數(shù)分散候選子空間，挖掘HUI。

基于貪心的算法傾向于將粒子向最優(yōu)的位置移動(dòng)。Song 等［38］提出了一個(gè)基于仿生算法的HUIM 通用框架Bio-HUIF（Bio-inspired-algorithm-based HUIM framework）以及PEVC（Promising Encoding Vector Check）檢測(cè)策略，基于此提出了Bio-HUIF-PSO 方法。在該方法中，隨機(jī)初始化多個(gè)粒子，利用式（11）更新粒子的速度，每個(gè)粒子向最優(yōu)值移動(dòng)，所有的粒子都重復(fù)更新其速度和位置，直到找到最優(yōu)解或達(dá)到最大的迭代次數(shù)。該算法可以找出90%以上的HUI，比UP-Growth［39］快兩個(gè)數(shù)量級(jí)。

其中vi1始終為1，vi2和vi3由式（12）（13）給出：

其中：BitDiff表示兩個(gè)向量之間的差異；r1和r2與式（4）中設(shè)置相同，為（0，1）內(nèi)的隨機(jī)數(shù)；xi為粒子所在的位置。

輪盤賭選擇法的基本思想是個(gè)體被選中的概率與其適應(yīng)函數(shù)值成正比。Song 等［23］提出了兩種方法用于發(fā)現(xiàn)HAUI：一種是基于標(biāo)準(zhǔn)PSO 的HAUI-PSO 方法，這是PSO 在HAUI 挖掘中的首次應(yīng)用；另一種是基于生物計(jì)算框架的HAUI-PSOD（High Average-Utility Itemset mining based on PSO with the Diverse optimal value framework of Bio-HUIF）方法，使用式（14）對(duì)發(fā)現(xiàn)的HAUI 應(yīng)用輪盤賭選擇以確定全局最佳值，而不是在下一個(gè)種群中保持當(dāng)前最佳值，增加了種群內(nèi)的平均多樣性，并提高了挖掘的效率和質(zhì)量。

其中：fitnessi表示第i個(gè)粒子的適應(yīng)度函數(shù)值，|SHAUI|是所發(fā)現(xiàn)的HAUI 數(shù)，PLi為該粒子被選擇的概率。

王常武等［40］提出HUIM-IPSO（High Utility Itemset Mining algorithm based on Improved PSO），通過輪盤賭選擇機(jī)制在當(dāng)前的HUI 的種群中以一定的概率選擇下一代種群的初始值，增加了種群的多樣性，可以獲得更多的項(xiàng)集。

與BPSO 不同，Chen 等［41］提出了基于集合的粒子群優(yōu)化方法S-PSO（Set-based PSO），根據(jù)速度向量中值更高的元素改變其對(duì)應(yīng)的位置元素，而不是簡(jiǎn)單地通過sigmoid 函數(shù)更新?；赟-PSO，Song 等［42］提出了HUIM-SPSO（High Utility Itemset Mining based on S-PSO）方法。為了衡量整個(gè)種群的多樣性，提出了位編輯距離（Bit Edit Distance，BED）、最大位編輯距離（Maximal BED，Max_BED）和平均位編輯距離（Average BED，Ave_BED），如式（15）～（17）所示。該算法具有更高的多樣性，在相同的迭代次數(shù)內(nèi)可以挖掘出多的高效用項(xiàng)集。

其中：NBits是由位置向量x變化到xt所使用的按位取反操作的次數(shù)；xi=（xi1，xi2，…，xiN）為一個(gè)種群中的位置向量；N為待求解的優(yōu)化問題維數(shù)。

2.2 基于蟻群算法

與GA 和PSO 不同，ACO 算法以建設(shè)性的方式產(chǎn)生可行的解決方案，因而被應(yīng)用于HUIM 中。本節(jié)從所挖掘模式的類型的角度梳理總結(jié)了基于蟻群算法的HUIM。式（18）代表第k只螞蟻在t時(shí)刻從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率，式（19）表示信息素的更新規(guī)則。

其中：allowedk表示第k只螞蟻下一步允許選擇的狀態(tài)；τij為t時(shí)刻狀態(tài)i到狀態(tài)j的信息素強(qiáng)度；ηij（t）為啟發(fā)函數(shù)；α為啟發(fā)式因子，表示軌跡的相對(duì)重要性；β為期望啟發(fā)式因子，表示能見度的相對(duì)重要性；ρ∈［0，1）為信息素?fù)]發(fā)系數(shù)，1-ρ為信息素殘留因子；m表示蟻群的大小。

對(duì)于普通HUIM 問題，Wu 等［43-44］提出了基于ACO 的方法HUIM-ACS 來高效挖掘HUI。算法將原始數(shù)據(jù)庫映射到路由圖中（圖6 為圖2 中數(shù)據(jù)庫的路由圖表示，其中S為源點(diǎn)），采用式（21）作為狀態(tài)i到狀態(tài)j的啟發(fā)式函數(shù)，并采用積極剪枝和遞歸剪枝兩種策略加速算法的收斂，以保證在處理過程中不會(huì)考慮相同的可行解。Seidlova 等［45］討論了蟻群方法的一種變體Ant-Miner，為超大型數(shù)據(jù)庫中的營(yíng)銷和商業(yè)智能提供解決方案。

圖6 路由圖Fig.6 Route map

其中：twuij為項(xiàng)集｛i，j｝的事務(wù)加權(quán)效用；etwuij為項(xiàng)集｛i，j｝的估計(jì)事務(wù)加權(quán)效用。etwuij如式（22）所示：

其中：Ti是下一個(gè)候選項(xiàng)集的子集，Ti中的每一個(gè)項(xiàng)y在之前都已經(jīng)被計(jì)算過其事務(wù)加權(quán)效用值。

不頻繁項(xiàng)集不經(jīng)常出現(xiàn)但會(huì)帶來巨大的利潤(rùn)，因此，高效用不頻繁項(xiàng)集的挖掘工作是非常重要的。Arunkumar等［46］提出了基于自定義蟻群算法的ACHUIIM（Ant Colony based High Utility Infrequent Itemset Mining），有效地發(fā)現(xiàn)高效用的不頻繁項(xiàng)集。

此外，蟻群算法還可以用來挖掘閉合高效用項(xiàng)集。Pramanik 等［47］提出了CHUI-AC（Closed High Utility Itemsets mining using Ant Colony algorithm），首次使用自啟發(fā)的蟻群算法挖掘CHUI。如式（23）所示，算法使用全局信息素更新規(guī)則以增加路徑上的信息素；此外，算法將可行解空間映射到具有二次空間復(fù)雜度的有向圖，以有效地指導(dǎo)搜索。

其中：ubest是特定迭代中效用最高的項(xiàng)集的效用，h是效用閾值。

2.3 基于其他群智能優(yōu)化算法

在群智能優(yōu)化算法中，人工蜂群算法、蝙蝠算法（Bat Algorithm，BA）、灰狼優(yōu)化（Grey Wolf Optimization，GWO）算法［48］、人工魚群算法等也被應(yīng)用于HUIM，并能夠取得較好的挖掘效果。

Song 等［21］提 出HUIM-ABC（HUIM based on the ABC algorithm），使用ABC 算法對(duì)HUIM 問題進(jìn)行建模，利用位圖進(jìn)行信息表示和搜索空間的剪枝，加速HUI 的發(fā)現(xiàn)過程。引領(lǐng)峰根據(jù)采蜜經(jīng)驗(yàn)，在鄰域范圍內(nèi)利用式（24）產(chǎn)生一個(gè)新位置，并利用式（3）計(jì)算當(dāng)前位置的適應(yīng)度函數(shù)值，作為新位置的蜜源質(zhì)量。若蜜源質(zhì)量高于原蜜源質(zhì)量，則新位置代替原位置。該方法采用直接蜜源生成（Direct Nectar Source Generation，DNSG）策略，通過所發(fā)現(xiàn)的HUI 的數(shù)量信息生產(chǎn)新的候選花蜜，從而可以在更少的迭代周期內(nèi)發(fā)現(xiàn)更多的HUI。

其中：vij是新位置；xij是原位置；xkj是隨機(jī)選取的鄰居蜜源位置；φ是［-1，1］上服從均勻分布的隨機(jī)數(shù)；k=｛1，2，…，M｝（M為種群規(guī)模）；j=｛1，2，…，N｝（N表示待求解的優(yōu)化問題的維數(shù)）。

BA 的思想源于對(duì)蝙蝠高級(jí)回聲定位能力的模擬。BA 把蝙蝠個(gè)體看作分布在搜索空間中的解，模擬蝙蝠能夠在復(fù)雜環(huán)境中精確捕獲食物的機(jī)制來解決優(yōu)化問題。應(yīng)用Bio-HUIF框架，Song 等［38］提出Bio-HUIF-BA 方法，將BA 用于HUI 的挖掘中。首先，在搜索空間隨機(jī)分布若干個(gè)蝙蝠，確定種群個(gè)體的初始位置和初始速度，對(duì)種群各個(gè)蝙蝠進(jìn)行適應(yīng)度評(píng)價(jià)，尋找出最優(yōu)個(gè)體位置gbest。然后，利用式（25）～（27），通過調(diào)整頻率產(chǎn)生新的解并修改個(gè)體的飛行速度和位置。

其中：fi為蝙蝠i的發(fā)射頻率；fmin和fmax分別是所有蝙蝠發(fā)出脈沖的最小和最大頻率；β∈［0，1］是一個(gè)隨機(jī)數(shù)；vi（t）和vi（t+1）是第i只蝙蝠在第t次和第t+1 次迭代時(shí)的速度；xi（t）和xi（t+1）是第i只蝙蝠在第t次和t+1 次迭代時(shí)的位置。

如式（28）（29）所示，蝙蝠在尋優(yōu)過程中，通過調(diào)節(jié)脈沖發(fā)生率和響度促使蝙蝠朝著最優(yōu)解方向移動(dòng)。

其中：Ai（t）和Ai（t+1）代表第t次迭代和t+1 次迭代時(shí)的脈沖發(fā)射響度，ri（0）是脈沖發(fā)射率，α（0＜α＜1）為聲波響度衰減系數(shù)，γ（γ＞0）為脈沖頻度增強(qiáng)系數(shù)。所有的蝙蝠反復(fù)更新它們的速度、位置、響度和脈沖發(fā)射率，直到找到最佳解決方案或達(dá)到最大迭代次數(shù)。Bio-HUIF-BA 方法比UP-Growth 快一個(gè)數(shù)量級(jí)，可以找出90%以上的HUI。

GWO 算法［48］模擬自然界中灰狼種群等級(jí)機(jī)制和捕獵行為。通過4 種類型的灰狼（α，β，δ，ω）模擬社會(huì)等級(jí)，并基于狼群跟蹤、包圍、追捕、攻擊獵物等過程模擬狼的捕獵行為，實(shí)現(xiàn)優(yōu)化搜索目的。GWO 因其原理簡(jiǎn)單、并行性、易于實(shí)現(xiàn)、需調(diào)整的參數(shù)少且有較強(qiáng)的全局搜索能力等特點(diǎn)，被修改為使用布爾運(yùn)算符以解決HUIM 問題。Pazhaniraja 等［49］提出了一種基于灰狼生物學(xué)行為的優(yōu)化模型BGWO（Boolean operatorsbased modified GWO algorithm），使用加法器、差分器、多路復(fù)用器、環(huán)形移位器和德摩根與運(yùn)算等5 種不同的布爾運(yùn)算對(duì)連續(xù)GWO 進(jìn)行轉(zhuǎn)換。每個(gè)運(yùn)算符都被重新定義以減少運(yùn)算時(shí)間，從而可以在大型數(shù)據(jù)庫中高效地挖掘HUI。與其他算法類似，BGWO 使用二進(jìn)制位圖編碼項(xiàng)集，使用式（3）計(jì)算其適應(yīng)度函數(shù)。與標(biāo)準(zhǔn)GWO 算法不同，修改后的GWO 算法不具備任何確保整個(gè)搜索在邊界區(qū)域內(nèi)進(jìn)行的邊界檢查程序。

人工魚群算法將動(dòng)物自治體的概念引入優(yōu)化算法，使得該算法的自下而上的尋優(yōu)模式具有良好的全局優(yōu)化能力。由于該算法對(duì)初始值和參數(shù)的選擇不敏感，具有魯棒性強(qiáng)、簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)，Song 等［22］從AF 算法的角度研究了HUIM 問題，并提出了HUIM-AF 方法。用人工魚的跟隨、集群和捕食這3種行為對(duì)HUIM問題進(jìn)行建模，以有效挖掘HUI。

2.4 小結(jié)

基于群智能優(yōu)化算法的HUIM 方法基本上使用相同的數(shù)據(jù)集，為了更好地比較它們的性能，表3 列舉了這些數(shù)據(jù)集的參數(shù)。

表3 數(shù)據(jù)集參數(shù)Tab.3 Parameters of datasets

表4對(duì)基于群智能優(yōu)化算法的HUIM 方法進(jìn)行了比較，其中，ω為權(quán)重慣性系數(shù)，c1與c2為學(xué)習(xí)因子，ND為迭代次數(shù)，M為種群大小，γ是信息素蒸發(fā)參數(shù)，τ為信息素量，ρ是調(diào)整信息素密度的參數(shù)，α和β是決定信息素對(duì)兩個(gè)節(jié)點(diǎn)之間距離的相對(duì)影響的兩個(gè)參數(shù)，q是平衡參數(shù)，Mn為花蜜源的數(shù)量。從表4中可以看出，雖然基于PSO 的HUIM 方法參數(shù)更少，可以很容易地實(shí)現(xiàn)；但在稀疏數(shù)據(jù)集中，由于粒子群是隨機(jī)“跳變”的，得到的粒子很大一部分是數(shù)據(jù)集中不存在的，處理這些粒子會(huì)造成多余計(jì)算，因此PSO算法在稀疏數(shù)據(jù)集中性能普遍較差。

表4 基于群智能優(yōu)化算法的HUIM方法總結(jié)Tab.4 Summary of HUIM methods based on swarm intelligence optimization algorithms

HUIM-BPSOsig 的時(shí)間復(fù)雜度為O(ND×M×m)，其中ND為迭代次數(shù)，M為種群大小，m為每個(gè)粒子的大小，即1-HTWUI的數(shù)量。變量ND和M可以由用戶調(diào)整，1-HTWUI的數(shù)量由最小效用閾值決定。HUIM-BPSO 比HUIM-BPSOsig 多了OR/NOR-tree 結(jié)構(gòu)，在進(jìn)化過程中可以避免無效組合，因此可以大幅改進(jìn)粒子在進(jìn)化過程中的計(jì)算，因此在相同數(shù)據(jù)集條件下，HUIM-BPSO 比HUIM-BPSOsig 更快。在chess 數(shù)據(jù)集上，與HUIM-BPSOsig 相比，HUIM-SPSO 的耗時(shí)減少了66.1%，與HUIM-BPSO 相比減少了60.3%；在mushroom 數(shù)據(jù)集 上，HUIM-BPSOsig 的執(zhí)行時(shí)間 為HUIM-SPSO 的10 倍，HUIM-BPSO 的執(zhí)行 時(shí)間為HUIM-SPSO 的8.01 倍［42］。HUIM-SPSO 傾向于以高速改變位置元素，而不是簡(jiǎn)單地應(yīng)用sigmoid 函數(shù)更新粒子，能夠在保證種群多樣性的前提下，貪心地進(jìn)行收斂。因此，HUIM-SPSO比應(yīng)用sigmoid函數(shù)更新的HUIM-BPSOsig 以及HUIM-BPSO 更快。SCE-PSO 的時(shí)間復(fù)雜度 為O（ND×M×m/p），其 中p為分區(qū) 數(shù)，因 此SCE-PSO 比HUIM-BPSOsig更快。

在基于GA 的方法中，HUPEumu-GRAM 方法需要O（M）時(shí)間通過輪盤賭機(jī)制選擇兩條染色體，需要O（m）時(shí)間對(duì)新染色體執(zhí)行交叉和變異操作。因此，它需要O（M+m）時(shí)間生成新的后代，并且總時(shí)間復(fù)雜度為O（ND×M×（M+m））。從上述分析來看，基于PSO的HUIM方法普遍比基于GA的方法更快。

3 基于進(jìn)化算法

本章把基于進(jìn)化算法（EA）的高效用項(xiàng)集挖掘方法分為基于遺傳算法和基于仿生算法的HUIM 進(jìn)行總結(jié)分析。

Kannimuthu 等［17］提出了HUPEUMU-GARM 方法，使用最小效用閾值進(jìn)行排序變異，利用遺傳算法挖掘HUI。在該方法中，用戶將最小效用閾值與事務(wù)數(shù)據(jù)庫一起輸入，使用式（30）進(jìn)行變異。負(fù)效用在現(xiàn)實(shí)生活中具有重要意義［50］，HUPEUMU-GARM方法首次將遺傳算法應(yīng)用于帶有負(fù)項(xiàng)目值的HUI挖掘中。此外，Kannimuthu 等［17］還提出了HUPEWUMU-GARM 方法，在不使用最小效用閾值的情況下挖掘HUI。

其中：Pmu為突變概率，為最大的變異率，為最小變異率，Di為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)，Rank為當(dāng)前的等級(jí)，R為總的等級(jí)數(shù)。

在隱私 保護(hù)數(shù) 據(jù)挖掘［51］中，Lin 等［52］提出名 為PPUMGAT+（Privacy-Preserving Utility Mining based on GA Technique using Pre-large concept）的方法挖掘敏感的HUI。它不僅可以根據(jù)用戶指定的最小效用閾值生成高質(zhì)量的盈利項(xiàng)集，而且在現(xiàn)實(shí)應(yīng)用中具有保護(hù)隱私和安全信息的能力?；谶M(jìn)化的算法在事務(wù)數(shù)據(jù)庫中找到完整的HUI 仍然很耗時(shí)，為了解決這個(gè)問題，Zhang 等［53］提出HUIM-IGA（HUIM algorithm based on an Improved GA）來有效地挖掘HUI。該算法對(duì)重復(fù)的HUI 采用了鄰域探索策略，從而提高了算法的局部搜索能力。利用種群多樣性維護(hù)策略，以擴(kuò)大搜索空間，提高了種群多樣性，從而避免因局部條件不成熟而導(dǎo)致的HUI 缺失。

Lin 等［24］提出了一種基于GA 的HUIM 方法DcGA，使用一個(gè)緊湊的遺傳算法模型，在有限的時(shí)間內(nèi)挖掘CHUI。該算法用估計(jì)分布策略預(yù)測(cè)種群在解空間的運(yùn)動(dòng)，而不是通過簡(jiǎn)單的交叉和變異操作估計(jì)交叉率和變異率。群體中的每個(gè)個(gè)體都用概率向量進(jìn)行編碼，代表了群體中每個(gè)基因存在的比例。算法找到閉合頻繁項(xiàng)集（Closed Frequent Itemsets，CFIs）之后，將數(shù)據(jù)庫中存在的每個(gè)項(xiàng)的概率pi初始化為0.5，從CFIs 中生成兩個(gè)染色體，利用式（3）計(jì)算其適應(yīng)度函數(shù)值，值較大的為winner，較小的為loser。利用式（31）進(jìn)行概率的更新。

其中：k=1，2，…，n，n為數(shù)據(jù)庫中項(xiàng)集的個(gè)數(shù)；winner［k］為向量winner的第k維。

Pazhaniraja 等［54］利用海 豚回聲 定位優(yōu) 化（Dolphin Echolocation Optimization，DEO）算法在較大的數(shù)據(jù)集中有效地挖掘高效用項(xiàng)集，提出了HUIM-DEO 方法。

差分進(jìn)化長(zhǎng)期以來被成功應(yīng)用于解決高維問題，Krishna等［55］將差分進(jìn)化用于高效用關(guān)聯(lián)規(guī)則挖掘，在此上進(jìn)行延伸，提出了BDE-HUIM（High Utility Itemset Mining using Binary Differential Evolution）算法［56］，利用差分進(jìn)化挖掘HUI。

4 基于其他智能優(yōu)化算法

本章匯總了除基于群智能優(yōu)化算法和進(jìn)化算法以外的其他HUIM 方法，分別是基于多目標(biāo)優(yōu)化算法（Multi-Objective Evolutionary Algorithm，MOEA）、基于交叉熵和基于仿自然優(yōu)化的HUIM。

在HUIM 中，項(xiàng)集的效用和支持度經(jīng)常存在著沖突，換句話說，頻繁項(xiàng)集的效用可能會(huì)很低，效用較高的項(xiàng)集往往不頻繁。MOEA 具有同時(shí)優(yōu)化多個(gè)目標(biāo)的特性［57］，因此可以很好地解決上述問題。常見的MOEA 框架有MOEA/D（Multi-Objective Evolutionary Algorithm based on Decomposition）［58］、NSGA-Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ）［59］、SPEA2（Strength Pareto Evolutionary Algorithm improved version）［60］等。

基 于MOEA/D，Zhang 等［61］提出了MOEA-FHUI（Multi-Objective Evolutionary Approach for mining Frequent and High Utility Itemsets），首次將挖掘頻繁高效用項(xiàng)集的問題轉(zhuǎn)化為同時(shí)最大化支持度和效用的多目標(biāo)優(yōu)化問題，且不需要指定最小支持度閾值minsup和最小效用閾值minutil等先驗(yàn)參數(shù)。該方法提出了一種特定的種群初始化策略。假設(shè)種群的大小為N，利用式（32），以概率Pt選擇N/2 個(gè)事務(wù)，利用式（33），以概率Pi選擇N/2 個(gè)1-項(xiàng)集。通過MOEA/D 框架來進(jìn)化種群，得到最終的結(jié)果。在進(jìn)化過程中，能夠達(dá)到種群的收斂性和多樣性之間的平衡。

其中：Tj為原始數(shù)據(jù)庫中的事務(wù)，u（Tj）為事務(wù)Tj的效用，| |

DB為數(shù)據(jù)庫中事務(wù)的數(shù)目，i為原始數(shù)據(jù)庫中的1-項(xiàng)集，supp（i）為項(xiàng)i的支持度，|I|為數(shù)據(jù)庫中1-項(xiàng)集的個(gè)數(shù)。

Ahmed 等［62］提 出MOEA-HEUPM（High Expected Utility Patterns in a limit tiMe based on the Multi-Objective EvolutionAry framework）方法，采用多目標(biāo)進(jìn)化框架從不確定的數(shù)據(jù)庫中發(fā)現(xiàn)有趣的高期望效用模式（High Expected Utility Patterns，HEUPs）。該方法不需要最小效用閾值和最小不確定閾值，利用基于權(quán)重的（Tchebycheff）算法來快速獲得基于多目標(biāo)（效用和不確定性）機(jī)制的非主導(dǎo)解決方案。Cao 等［63］提 出 CP-MOEA（Closed itemset Property based Multi-Objective Evolutionary Approach），采用與NSGA-Ⅱ類似的框架，同時(shí)優(yōu)化支持度和效用兩個(gè)目標(biāo)，用于挖掘頻繁高效用項(xiàng)集?；陂]合項(xiàng)集的性質(zhì)，設(shè)計(jì)了兩種個(gè)體更新策略USC（Updating Strategy based on Closed itemsets）和USA（Updating Strategy based on Approximate-closed itemset）加速種群收斂，提高種群多樣性。

Fang 等［64］提出MOEA-PM（MOEA for high quality Pattern Mining），采用改進(jìn)的多目標(biāo)進(jìn)化算法，利用式（34）對(duì)種群進(jìn)行進(jìn)化，挖掘事務(wù)數(shù)據(jù)庫中同時(shí)滿足高支持度、高占用率、高效用的模式。

其中：occu（X）為項(xiàng)集X的占用率，u(X)為X的效用，twu()為事務(wù)加權(quán)效用。

Song 等［25］提出了兩種基于交叉熵的方法，分別是TKU-CE 和TKU-CE+，用于啟發(fā)式地挖掘top-kHUI。首先，通過臨界效用值過濾沒有希望的項(xiàng)，避免了額外的數(shù)據(jù)結(jié)構(gòu)和閾值提高策略所帶來的計(jì)算成本；其次，在每次迭代中使用樣本細(xì)化策略，以減少迭代階段的計(jì)算負(fù)擔(dān)；最后，提出了平滑變異，隨機(jī)生成一些新的項(xiàng)集，提高了樣本的多樣性，可以用更少的迭代發(fā)現(xiàn)更多的top-kHUI。

為了解決算法運(yùn)行時(shí)間長(zhǎng)可能會(huì)錯(cuò)過許多HUI 的問題，Nawaz 等［13］基于爬山法和模擬退火（Simulated Annealing，SA）提出了兩種方法，即HUIM-HC（HUIM based on Hill Climbing）和HUIM-SA（HUIM based on SA）。將數(shù)據(jù)庫轉(zhuǎn)換為位圖的形式以進(jìn)行高效的效用計(jì)算和搜索空間的修剪。在迭代過程中發(fā)現(xiàn)的HUI 被用作下一個(gè)種群的目標(biāo)值，提高了種群的多樣性。

5 結(jié)語

本文以智能優(yōu)化算法的類別為角度，把基于智能優(yōu)化算法的HUIM 方法分為基于群智能優(yōu)化算法、基于進(jìn)化算法以及基于其他算法的HUIM，并作了詳細(xì)的分析與總結(jié)；首次從粒子更新策略的角度，把基于粒子群優(yōu)化算法的高效用項(xiàng)集挖掘算法分為五類，包括基于傳統(tǒng)更新策略、基于sigmoid 函數(shù)、基于貪心、基于輪盤賭以及基于集合的HUIM；從項(xiàng)集的角度，把基于蟻群算法的HUIM 分3 個(gè)類別進(jìn)行介紹，包括面向普通高效用項(xiàng)集、面向不頻繁的高效用項(xiàng)集和面向閉合高效用項(xiàng)集的HUIM；把基于進(jìn)化算法的HUIM 分為基于遺傳算法和基于仿生算法的HUIM；最后列舉了其他智能優(yōu)化算法在高效用項(xiàng)集中的應(yīng)用，分別是MOEA、交叉熵和仿自然優(yōu)化算法。

基于智能優(yōu)化算法的高效用項(xiàng)集挖掘雖然已經(jīng)取得了一定的成果，但是現(xiàn)有的方法仍然存在著不足之處，這為研究者提供了下一步的研究方向。

1）在數(shù)據(jù)流上用智能優(yōu)化算法挖掘HUI。

目前的基于智能優(yōu)化算法的HUIM 方法僅在靜態(tài)數(shù)據(jù)中挖掘，而對(duì)數(shù)據(jù)流中的高效用項(xiàng)集的關(guān)注較少。由于傳感器數(shù)據(jù)、社交網(wǎng)絡(luò)服務(wù)數(shù)據(jù)、Web 訪問日志數(shù)據(jù)等各種流數(shù)據(jù)已經(jīng)成為獲取現(xiàn)實(shí)世界中有價(jià)值信息的重要數(shù)據(jù)，流模式已經(jīng)成為關(guān)聯(lián)規(guī)則挖掘中的一項(xiàng)重要技術(shù)［65］。下一步，將嘗試把智能優(yōu)化算法應(yīng)用于數(shù)據(jù)流中的HUI 的挖掘，通過應(yīng)用滑動(dòng)窗口技術(shù)和樹結(jié)構(gòu)分批次處理和存儲(chǔ)數(shù)據(jù)流中的項(xiàng)集，然后選擇合適的智能優(yōu)化算法挖掘HUI。

2）改進(jìn)基于智能優(yōu)化算法的HUIM 的剪枝策略。

基于智能優(yōu)化算法的HUIM 中，具有剪枝策略的算法屈指可數(shù)，可以以優(yōu)化剪枝策略的方式，進(jìn)一步加快挖掘速度?，F(xiàn)有的剪枝策略會(huì)對(duì)沒有希望的項(xiàng)集提前剪枝，但這樣會(huì)降低種群多樣性。因此，如何在剪枝與多樣性之間去做一個(gè)折中是一個(gè)具有挑戰(zhàn)性的任務(wù)。此外，智能優(yōu)化算法具有較強(qiáng)隨機(jī)性，在稀疏數(shù)據(jù)集中的表現(xiàn)欠佳。針對(duì)以上問題，作者將改進(jìn)基于智能優(yōu)化算法的HUIM 的剪枝策略，提高算法在稀疏數(shù)據(jù)集中的性能。

3）自適應(yīng)地挖掘HUI。

算法中參數(shù)的不同會(huì)對(duì)結(jié)果造成很多的影響［66］，同樣，智能優(yōu)化算法中的參數(shù)設(shè)置也會(huì)影響最終的挖掘結(jié)果。在挖掘過程中，初始設(shè)置的最優(yōu)參數(shù)可能在挖掘一段時(shí)間后會(huì)陷入局部最優(yōu)，從而導(dǎo)致丟失HUI。未來的研究中，將設(shè)計(jì)一種自適應(yīng)變換參數(shù)的基于智能優(yōu)化算法的HUIM。

4）智能優(yōu)化算法在HUIM 上的更廣泛應(yīng)用。

在現(xiàn)有的基于智能優(yōu)化的HUIM 算法中，所應(yīng)用的智能優(yōu)化算法的種類較少。目前僅應(yīng)用了蟻群算法、遺傳算法、粒子群優(yōu)化算法、蝙蝠算法等少數(shù)算法。另外，基于智能優(yōu)化算法的HUIM 具有速度快、啟發(fā)式挖掘的特點(diǎn)，非常適合挖掘各種復(fù)雜的高效用項(xiàng)集。下一步，會(huì)將多種類型的智能優(yōu)化算法應(yīng)用于挖掘更多復(fù)雜類型的高效用項(xiàng)集中。