基于智能優化算法的高效用項集挖掘方法綜述

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

（北方民族大學 計算機科學與工程學院，銀川 750021）

0 引言

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

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

Kannimuthu 等［17］將遺傳算法（Genetic Algorithm，GA）應用于 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）方法，這是智能優化算法在HUIM中的首次應用，能夠在指數搜索空間中快速有效地挖掘HUI。與基于GA 的HUIM 方法相比，基于粒子群優化（Particle Swarm Optimization，PSO）的技術需要更少的參數，無需設置合理的交叉和變異率，可以很容易實現［18］。Lin等［19-20］首次將PSO 應用于HUIM，在粒子更新過程中采用sigmoid 函數，并開發了OR/NOR-tree 結構［18］，通過提前修剪粒子的無效組合避免對數據庫的多次掃描。Song 等［21］從人工蜂群（Artificial Bee Colony，ABC）算法的角度對HUIM 問題進行建模，利用位圖進行信息表示和搜索空間剪枝，加速了HUI 的發現。Song 等［22］從人工魚群（Artificial Fish swarm，AF）算法的角度研究了HUIM 問題，并提出一種名為HUIM-AF（HUIM methods based on AF algorithm）的HUIM 方法。此外，智能優化算法還可以用于挖掘HUI 的復雜模式，例 如，Song 等［23］提出了 基于標 準PSO 方法的HAUI-PSO（mining High Average-Utility Itemsets based on PSO）算法挖掘高平均效用項集（High Average Utility Itemsets，HAUI）；Lin等［24］提出了一種基于GA 的算法DcGA（Decomposition based on a compact GA），在有限的時間內高效地挖掘閉合高效用項集（Closed HUI，CHUI）；Song 等［25］提出了基于交叉熵的方法 TKU-CE+（Top-Khigh-Utility itemset mining based on Cross-Entropy method），用于啟發式地挖掘top-k高效用項集。

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

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

本文的主要工作如下：

1）首次把基于智能優化算法的HUIM 方法分為基于群智能優化算法、基于進化算法（Evolutionary Algorithm，EA）和基于其他算法的HUIM，并作了全面的分析與總結。

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

3）分析總結了現有的基于智能優化算法的HUIM 的優點和不足，從數據流、自適應、剪枝策略和復雜模式等角度給出下一步的研究方向以供參考。

1 背景介紹

1.1 高效用項集挖掘概念

令I={i1，i2，…，in}是由一組項組成的集合，令DB是一個數據庫，這個數據庫中有一個效用列表（表1）和一個事務列表（表2）。效用列表中的每個項I都有一個效用值。事務列表中的每個事務T都有一個唯一的標識符tid，且T是I的一個子集，其中每個項都與一個計數值相關聯。若一個項是I的子集，且包含k個項，則稱之為k-項集［8］。

表1 效用列表Tab.1 Utility list

表2 事務列表Tab.2 Transaction list

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

定義2 事務T中項i的內部效用［8］表示為iu（i，T），是DB的事務表中與T中i相關聯的計數值。例如在表2 中，事務T1中項a的內部效用iu（a，T1）=5。

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

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

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

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

其中數據庫DB的總效用是DB中所有事務的效用之和。

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

定義7DB中項集X的事務加權效用（transactionweighted utility）［9］記為twu（X），是數據庫DB中包含項集X的所有事務的效用之和（如式（2）所示）。如表1 所示，項集｛a｝的事務加權效用twu（｛a｝）=

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

1.2 智能優化算法

1.2.1 PSO 算法

PSO 算法是針對連續優化問題提出的［30-31］，但通過二進制編碼可以得到離散變量的PSO 形式，因此也可用于離散系統中組合優化問題的求解。PSO 算法實現步驟如圖2 所示。

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

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

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

接著，計算并更新每個粒子的最好位置（pbest）和整個群體或鄰域內的最好位置（gbest），根據式（4）（5）更新粒子的速度或位置，即更新候選項集，這也是相應HUIM 各算法之間的不同之處（將在2.1 節詳細闡述）。若達到終止條件，即產生的HUI 在一定的時間內是重復的（即算法收斂）或者達到了一定的循環次數，算法停止；否則，算法進入循環，直到滿足停止條件為止。

其中i=1，2，…，M（M為粒子群體規模）；d=1，2，…，N（N為待求解的優化問題維數）；c1、c2為學習因子；t為迭代次數；r1和r2是在［0，1］上服從均勻分布的隨機數；ω是權重慣性系數，能夠實現PSO 全局探索和局部開發能力的平衡。

1.2.2 遺傳算法

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

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

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

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

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

2 基于群智能優化算法

2.1 基于粒子群優化算法

粒子群優化算法具有模型簡單、控制參數少、易于實現、運行速度快等優點，因此被廣泛用于HUI 的挖掘工作中，并取得了可觀的效果。本節從粒子更新策略的角度對基于粒子群優化算法的HUIM 方法進行了綜述。

傳統的粒子更新策略僅使用式（4）（5）對粒子進行速度和位置的更新。Pears 等［33］提出WARM SWARM（Weighted Association Rule Mining using particle SWARM optimization）方法，將粒子群優化與加權關聯規則挖掘相結合，使用粒子群優化為關聯規則挖掘分配有意義的項目權重。實驗結果表明，雖然使用粒子群優化進行權重擬合有一定的開銷，但該方法也明顯快于標準Apriori，且可以產生有趣和有意義的規則，當數據集的大小增加時，這一點尤其明顯。Sivamathi等［34］提出了SCE-PSO（Shuffled Complex Evolution of PSO）方法，首先在可行空間中隨機抽取一組粒子，然后將種群劃分為若干個復合體，在每個復合體中使用PSO 算法挖掘HUI。

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

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

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

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

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

圖5 OR/NOR-tree結構Fig.5 OR/NOR-tree structure

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

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

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

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

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

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

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

其中：fitnessi表示第i個粒子的適應度函數值，|SHAUI|是所發現的HAUI 數，PLi為該粒子被選擇的概率。

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

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

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

2.2 基于蟻群算法

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

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

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

圖6 路由圖Fig.6 Route map

其中：twuij為項集｛i，j｝的事務加權效用；etwuij為項集｛i，j｝的估計事務加權效用。etwuij如式（22）所示：

其中：Ti是下一個候選項集的子集，Ti中的每一個項y在之前都已經被計算過其事務加權效用值。

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

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

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

2.3 基于其他群智能優化算法

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

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

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

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

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

如式（28）（29）所示，蝙蝠在尋優過程中，通過調節脈沖發生率和響度促使蝙蝠朝著最優解方向移動。

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

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

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

2.4 小結

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

表3 數據集參數Tab.3 Parameters of datasets

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

表4 基于群智能優化算法的HUIM方法總結Tab.4 Summary of HUIM methods based on swarm intelligence optimization algorithms

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

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

3 基于進化算法

本章把基于進化算法（EA）的高效用項集挖掘方法分為基于遺傳算法和基于仿生算法的HUIM 進行總結分析。

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

其中：Pmu為突變概率，為最大的變異率，為最小變異率，Di為當前迭代次數，T為最大迭代次數，Rank為當前的等級，R為總的等級數。

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

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

其中：k=1，2，…，n，n為數據庫中項集的個數；winner［k］為向量winner的第k維。

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

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

4 基于其他智能優化算法

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

在HUIM 中，項集的效用和支持度經常存在著沖突，換句話說，頻繁項集的效用可能會很低，效用較高的項集往往不頻繁。MOEA 具有同時優化多個目標的特性［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），首次將挖掘頻繁高效用項集的問題轉化為同時最大化支持度和效用的多目標優化問題，且不需要指定最小支持度閾值minsup和最小效用閾值minutil等先驗參數。該方法提出了一種特定的種群初始化策略。假設種群的大小為N，利用式（32），以概率Pt選擇N/2 個事務，利用式（33），以概率Pi選擇N/2 個1-項集。通過MOEA/D 框架來進化種群，得到最終的結果。在進化過程中，能夠達到種群的收斂性和多樣性之間的平衡。

其中：Tj為原始數據庫中的事務，u（Tj）為事務Tj的效用，| |

DB為數據庫中事務的數目，i為原始數據庫中的1-項集，supp（i）為項i的支持度，|I|為數據庫中1-項集的個數。

Ahmed 等［62］提 出MOEA-HEUPM（High Expected Utility Patterns in a limit tiMe based on the Multi-Objective EvolutionAry framework）方法，采用多目標進化框架從不確定的數據庫中發現有趣的高期望效用模式（High Expected Utility Patterns，HEUPs）。該方法不需要最小效用閾值和最小不確定閾值，利用基于權重的（Tchebycheff）算法來快速獲得基于多目標（效用和不確定性）機制的非主導解決方案。Cao 等［63］提 出 CP-MOEA（Closed itemset Property based Multi-Objective Evolutionary Approach），采用與NSGA-Ⅱ類似的框架，同時優化支持度和效用兩個目標，用于挖掘頻繁高效用項集。基于閉合項集的性質，設計了兩種個體更新策略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），采用改進的多目標進化算法，利用式（34）對種群進行進化，挖掘事務數據庫中同時滿足高支持度、高占用率、高效用的模式。

其中：occu（X）為項集X的占用率，u(X)為X的效用，twu()為事務加權效用。

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

為了解決算法運行時間長可能會錯過許多HUI 的問題，Nawaz 等［13］基于爬山法和模擬退火（Simulated Annealing，SA）提出了兩種方法，即HUIM-HC（HUIM based on Hill Climbing）和HUIM-SA（HUIM based on SA）。將數據庫轉換為位圖的形式以進行高效的效用計算和搜索空間的修剪。在迭代過程中發現的HUI 被用作下一個種群的目標值，提高了種群的多樣性。

5 結語

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

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

1）在數據流上用智能優化算法挖掘HUI。

目前的基于智能優化算法的HUIM 方法僅在靜態數據中挖掘，而對數據流中的高效用項集的關注較少。由于傳感器數據、社交網絡服務數據、Web 訪問日志數據等各種流數據已經成為獲取現實世界中有價值信息的重要數據，流模式已經成為關聯規則挖掘中的一項重要技術［65］。下一步，將嘗試把智能優化算法應用于數據流中的HUI 的挖掘，通過應用滑動窗口技術和樹結構分批次處理和存儲數據流中的項集，然后選擇合適的智能優化算法挖掘HUI。

2）改進基于智能優化算法的HUIM 的剪枝策略。

基于智能優化算法的HUIM 中，具有剪枝策略的算法屈指可數，可以以優化剪枝策略的方式，進一步加快挖掘速度。現有的剪枝策略會對沒有希望的項集提前剪枝，但這樣會降低種群多樣性。因此，如何在剪枝與多樣性之間去做一個折中是一個具有挑戰性的任務。此外，智能優化算法具有較強隨機性，在稀疏數據集中的表現欠佳。針對以上問題，作者將改進基于智能優化算法的HUIM 的剪枝策略，提高算法在稀疏數據集中的性能。

3）自適應地挖掘HUI。

算法中參數的不同會對結果造成很多的影響［66］，同樣，智能優化算法中的參數設置也會影響最終的挖掘結果。在挖掘過程中，初始設置的最優參數可能在挖掘一段時間后會陷入局部最優，從而導致丟失HUI。未來的研究中，將設計一種自適應變換參數的基于智能優化算法的HUIM。

4）智能優化算法在HUIM 上的更廣泛應用。

在現有的基于智能優化的HUIM 算法中，所應用的智能優化算法的種類較少。目前僅應用了蟻群算法、遺傳算法、粒子群優化算法、蝙蝠算法等少數算法。另外，基于智能優化算法的HUIM 具有速度快、啟發式挖掘的特點，非常適合挖掘各種復雜的高效用項集。下一步，會將多種類型的智能優化算法應用于挖掘更多復雜類型的高效用項集中。