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

摘 要：針對(duì)基于啟發(fā)式的高效用項(xiàng)集挖掘算法在挖掘過(guò)程中可能丟失大量項(xiàng)集的問(wèn)題，提出一種新的啟發(fā)式高效用項(xiàng)集挖掘算法HHUIM。HHUIM利用哈里斯鷹優(yōu)化算法進(jìn)行種群更新，能夠有效減少項(xiàng)集丟失。提出并設(shè)計(jì)了鷹的替換策略，解決了搜索空間較大的問(wèn)題，降低了適應(yīng)度函數(shù)值低于最小效用閾值的鷹的數(shù)量。此外，提出存儲(chǔ)回溯策略，可有效防止算法因收斂過(guò)快陷入局部最優(yōu)。大量的實(shí)驗(yàn)表明，所提算法優(yōu)于目前最先進(jìn)的啟發(fā)式高效用項(xiàng)集挖掘算法。

關(guān)鍵詞：哈里斯鷹優(yōu)化算法； 高效用項(xiàng)集挖掘； 啟發(fā)式算法； 智能優(yōu)化算法

中圖分類號(hào)：TP311?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號(hào)：1001-3695（2024）01-015-0094-08

doi：10.19734/j.issn.1001-3695.2023.05.0198

HHUIM： new heuristic high utility itemset mining method

Abstract：In response to the problem of potentially losing a large number of itemsets during the mining process of heuristic-based high utility itemset mining algorithms， this paper proposed a new heuristic-based high utility itemset mining algorithm， called HHUIM. HHUIM utilized the Harris hawk optimization algorithm for population update， effectively reducing the loss of itemsets. This paper also introduced and designed a hawk replacement strategy to solve the problem of a large search space by decreasing the number of hawks with fitness values below the minimum utility threshold. Furthermore， this paper proposed a storage backtracking strategy to prevent premature convergence to local optima. Extensive experiments demonstrate that the proposed algorithm outperforms the state-of-the-art heuristic-based high utility itemset mining algorithms.

Key words：Harris eagle optimization algorithm; high utility itemset mining; heuristics; intelligent optimization algorithms

0 引言

高效用項(xiàng)集挖掘（HUIM）是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要課題［1］，并受到廣泛關(guān)注。已經(jīng)提出了許多確定性的算法來(lái)有效地挖掘高效用項(xiàng)集（high utility itemsets，HUIs）［2～5］，然而這些算法的性能會(huì)隨著數(shù)據(jù)集的增大以及不同項(xiàng)總數(shù)的增大而降低［6，7］。此外，高效用項(xiàng)集往往分散在搜索空間中，這就要求傳統(tǒng)的確定性算法要花費(fèi)許多時(shí)間和空間來(lái)判斷大量的候選項(xiàng)集是否為高效用項(xiàng)集。而啟發(fā)式算法具有解決復(fù)雜、線性和高度非線性問(wèn)題的能力，可以探索大型問(wèn)題空間，根據(jù)適應(yīng)度函數(shù)找到最優(yōu)或接近最優(yōu)的解決方案。因此，啟發(fā)式算法與高效用項(xiàng)集挖掘的結(jié)合可以很好地解決上述問(wèn)題，即可以在較短的時(shí)間內(nèi)快速找到很多的HUIs。

Kannimuthu等人［8］將遺傳算法（genetic algorithm，GA）應(yīng)用于HUIM，提出需要指定最小效用閾值的HUPEUMU-GARM算法和不需要指定最小效用閾值的HUPEWUMU-GARM算法，這是啟發(fā)式算法在高效用項(xiàng)集挖掘中的首次應(yīng)用，能夠在指數(shù)搜索空間中快速有效地挖掘HUIs，但是會(huì)丟失大量的項(xiàng)集。與基于GA的HUIM方法相比，基于粒子群優(yōu)化（particle swarm optimization，PSO）的技術(shù)需要的參數(shù)更少［9］，無(wú)須多次實(shí)驗(yàn)以找到合理的交叉和變異率，可以很容易實(shí)現(xiàn)［10］。Lin等人［11］首次將PSO應(yīng)用于HUIM，在粒子更新過(guò)程中采用sigmoid函數(shù)，并開(kāi)發(fā)了OR/NOR-tree結(jié)構(gòu)，通過(guò)早期修剪粒子的無(wú)效組合來(lái)避免數(shù)據(jù)庫(kù)的多次掃描。但由于限制了搜索空間，導(dǎo)致種群的多樣性降低，會(huì)造成項(xiàng)集的大量丟失。Song等人［12］從人工蜂群（artificial bee colony，ABC）算法的角度對(duì)HUIM問(wèn)題進(jìn)行建模，利用位圖進(jìn)行信息表示和搜索空間剪枝，加速了HUIs的發(fā)現(xiàn)。Song等人［13］從人工魚(yú)群（artificial fish swarm，AF）算法的角度研究了HUIs挖掘問(wèn)題，并提出一種名為HUIM-AF的高效用項(xiàng)集挖掘算法。Pazhaniraja等人［14］提出一種基于灰狼優(yōu)化和海豚回聲定位優(yōu)化的方法DE-BGWO來(lái)尋找高效用項(xiàng)集。此外，啟發(fā)式算法還可以用于挖掘高效用項(xiàng)集的復(fù)雜模式，例如：Song等人［15］提出了基于標(biāo)準(zhǔn)PSO方法的HAUI-PSO算法來(lái)挖掘高平均效用項(xiàng)集（high average utility itemsets，HAUI）;Pramanik等人［16］提出了挖掘CHUI-AC方法，首次使用自啟發(fā)的蟻群算法挖掘閉合高效用項(xiàng)集（closed high utility itemsets，CHUIs）;Lin等人［17］提出了一種基于GA的算法DcGA，在有限的時(shí)間內(nèi)高效地挖掘CHUIs;Song等人［18］提出了基于交叉熵的算法TKU-CE+，用于啟發(fā)式地挖掘top-k高效用項(xiàng)集;Luna等人［19］提出用于挖掘top-k高效用項(xiàng)集的TKHUIM-GA算法，通過(guò)考慮每個(gè)項(xiàng)的效用來(lái)生成初始解，并相應(yīng)地組合解決方案來(lái)指導(dǎo)搜索過(guò)程，可以減少運(yùn)行時(shí)間和內(nèi)存。

所有的這些算法都能夠在較短的時(shí)間內(nèi)快速找到很多高效用項(xiàng)集。然而這些算法因智能優(yōu)化算法具有較強(qiáng)的隨機(jī)性，或者由于其算法本身的特性很容易達(dá)到局部最優(yōu)而不會(huì)繼續(xù)探索下去，從而丟失一定的項(xiàng)集。比如基于遺傳算法的HUIM具有交叉率和突變率，這是種群保持多樣性的關(guān)鍵，而同時(shí)也會(huì)給算法帶來(lái)一定的隨機(jī)性，因此設(shè)置一個(gè)合適的突變率和交叉率是十分重要的，若設(shè)置不當(dāng)，很容易導(dǎo)致算法陷入局部最優(yōu)，進(jìn)而導(dǎo)致算法不能繼續(xù)挖掘出新的HUI?；诹Ｗ尤旱乃惴ㄔ谶M(jìn)行粒子的初始化時(shí)，要隨機(jī)初始化粒子的速度以及位置，進(jìn)行種群更新時(shí)，會(huì)根據(jù)輪盤(pán)賭選擇法或者基于sigmoid函數(shù)，然而這兩種算法都具有隨機(jī)性。同樣地，蝙蝠、人工蜂群、人工魚(yú)群等群智能算法同粒子群一樣，在種群初始化以及進(jìn)行種群更新時(shí)，都具有隨機(jī)性，因此會(huì)遺漏一定數(shù)量的高效用項(xiàng)集。所以，基于智能優(yōu)化算法的HUIM在所有數(shù)據(jù)集中以及所有的閾值下，在一定的迭代次數(shù)內(nèi)都能找到所有的高效用項(xiàng)集是十分困難且沒(méi)有必要的。因此，怎樣減少項(xiàng)集的丟失是一個(gè)研究重點(diǎn)。

值得注意的是，遺傳算法、粒子群優(yōu)化算法、蟻群算法、人工魚(yú)群算法、人工蜂群算法等啟發(fā)式算法對(duì)初始解的選擇非常敏感。不同的初始解可能導(dǎo)致不同的搜索軌跡和最終結(jié)果。如果初始解選擇不當(dāng)，可能會(huì)導(dǎo)致算法陷入局部最優(yōu)解或搜索效率低下。而哈里斯鷹優(yōu)化算法（HHO）［20］對(duì)初始解的選擇相對(duì)不敏感，能夠處理不同類型的問(wèn)題，并且對(duì)問(wèn)題空間中的噪聲和不確定性具有一定的魯棒性，這使得它在處理高效用項(xiàng)集挖掘問(wèn)題中表現(xiàn)良好。其次，由于遺傳算法的強(qiáng)項(xiàng)是全局搜索，對(duì)于問(wèn)題的局部?jī)?yōu)化可能相對(duì)較弱。遺傳算法通過(guò)種群的多樣性來(lái)探索解空間，但在確定局部最優(yōu)解時(shí)可能需要更多的迭代和調(diào)整。人工魚(yú)群算法在局部搜索中表現(xiàn)良好，通過(guò)覓食和尾隨行為進(jìn)行局部搜索；然而，在全局優(yōu)化方面，算法可能受到限制，并且可能需要更多的迭代和調(diào)整才能找到全局最優(yōu)解。而HHO具有探索性強(qiáng)、收斂性能好的優(yōu)點(diǎn)，能夠在較少的迭代次數(shù)內(nèi)快速尋找最優(yōu)解或近似最優(yōu)解，是高效用項(xiàng)集挖掘問(wèn)題的一個(gè)較優(yōu)選擇。

本文提出基于哈里斯鷹優(yōu)化的高效用項(xiàng)集挖掘算法HHUIM（Harris hawks optimization-based high utility itemsets mi-ning）。為了有效表示項(xiàng)集的超集形成，本文提出并設(shè)計(jì)了基于位圖的項(xiàng)集擴(kuò)展策略。其次，為了解決搜索空間較大的問(wèn)題，提出了鷹的替換策略，降低了適應(yīng)度函數(shù)值低于最小效用閾值的鷹的數(shù)量。此外，為了防止算法因收斂過(guò)快陷入局部最優(yōu)，提出存儲(chǔ)回溯策略。

本文的主要貢獻(xiàn)如下：a）首次提出基于哈里斯鷹優(yōu)化的高效用項(xiàng)集挖掘方法HUIM-HHO，能夠在較少的迭代次數(shù)內(nèi)快速挖掘出較多的結(jié)果集;b）本文研究并設(shè)計(jì)了基于位圖的項(xiàng)集擴(kuò)展策略，基于此提出鷹的替換策略，有效縮減了搜索空間;c）為了避免算法因收斂過(guò)快陷入局部最優(yōu)，本文提出存儲(chǔ)回溯策略，保持了種群的多樣性;d）在密集數(shù)據(jù)集和稀疏數(shù)據(jù)集中進(jìn)行了大量的對(duì)比實(shí)驗(yàn)，結(jié)果表明，本文算法在時(shí)空效率、所挖掘出來(lái)的高效用項(xiàng)集的數(shù)量等方面優(yōu)于目前最先進(jìn)的算法。

1 基本概念

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

本節(jié)介紹高效用項(xiàng)集挖掘的相關(guān)定義。令I(lǐng)={i1，i2，i3，…，in}是由一組項(xiàng)組成的集合，令DB是一個(gè)數(shù)據(jù)庫(kù)，這個(gè)數(shù)據(jù)庫(kù)中有一個(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)［21］。若一個(gè)項(xiàng)集是I的子集，且包含k個(gè)項(xiàng)，則稱之為k-項(xiàng)集［22］。

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

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

定義3［3］ 事務(wù)T中項(xiàng)i的效用，表示為u（i，T），是項(xiàng)i在事務(wù)T中的內(nèi)部效用與項(xiàng)i的外部效用的乘積，即iu（i，T）和eu（i）的乘積，被定義為

u（i，T）=iu（i，T）×eu（i）（1）

例如，事務(wù)T1中項(xiàng)a的效用，計(jì)算為u（a，T1）=iu（a，T1）×eu（a）=4×1=4。

定義4［3］ 事務(wù)T中項(xiàng)集X的效用，表示為u（X，T），是項(xiàng)集X中所有項(xiàng)的效用之和，其中X包含于T，被定義為

例如，事務(wù)T1中項(xiàng)集{a，b}的效用，u（{a，b}，T1）=u（a，T1）+u（b，T1）=4×1+4×3=16。事務(wù)T3中項(xiàng)集{a，b}的效用，u（{a，b}，T3）=u（a，T3）+u（b，T3）=2×1+1×3=5。

定義5［4］ 項(xiàng)集X的效用，表示為u（X），是數(shù)據(jù)庫(kù)DB中所有包含X的事務(wù)T中項(xiàng)集X的效用之和，被定義為

例如，項(xiàng)集{a，b}的效用為其在事務(wù)T1中的效用加上{a，b}在事務(wù)T3中的效用，即u（{a，b}）=u（{a，b}，T1）+u（{a，b}，T3）=16+5=21。

定義6［4］ 事務(wù)T的效用（utility of transaction），表示為tu（T），是T中所有項(xiàng)的效用之和，其中，數(shù)據(jù)庫(kù)DB的總效用是DB中所有事務(wù)的效用之和，被定義為

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

定義7［2］ DB中項(xiàng)集X的事務(wù)加權(quán)效用（transaction weighted utility），表示為twu（X），是數(shù)據(jù)庫(kù)DB中包含項(xiàng)集X的所有事務(wù)的效用之和，定義為

例如，項(xiàng)集{a}的事務(wù)加權(quán)效用被計(jì)算為twu（{a}）=tu（T1）+tu（T3）=28+27=55。數(shù)據(jù)庫(kù)中所有1-項(xiàng)集的twu如表3所示。

定義8［23］ 若在數(shù)據(jù)庫(kù)DB中，項(xiàng)集X的事務(wù)加權(quán)效用不小于minutil，則項(xiàng)集X是高事務(wù)加權(quán)效用項(xiàng)集（high transaction weighted utilization itemset，HTWUI）。

定義9［23］ 若在數(shù)據(jù)庫(kù)DB中，項(xiàng)集X的事務(wù)加權(quán)效用小于minutil，則項(xiàng)集X是低事務(wù)加權(quán)效用項(xiàng)集（low transaction weighted utilization itemset，LTWUI）。

例如，若minutil=50，則數(shù)據(jù)庫(kù)DB中的1-HTWUI一共有5個(gè)，分別為{a}，，{c}，syggg00，{f}，而1-LTWUI僅有{e}。

1.2 哈里斯鷹優(yōu)化算法

在HHO中，候選解由鷹來(lái)表示，最優(yōu)解（或近似最優(yōu)解）被稱之為獵物。HHO分為探索階段和開(kāi)發(fā)階段，其中在開(kāi)發(fā)階段，鷹根據(jù)獵物的逃逸能量來(lái)改變自己的行為。獵物的逃逸能量E如式（6）所示。

其中：t是當(dāng)前的迭代次數(shù);T是最大的迭代次數(shù);E0是獵物的初始逃逸能量（由式（7）可得）;r是［0， 1］的隨機(jī)數(shù)。

1）探索階段

在探索階段，鷹的位置通過(guò)式（8）進(jìn)行更新。其中：X是鷹的位置;Xk是隨機(jī)選擇的一只鷹的位置;Xr是獵物的位置（全局最優(yōu)解gbest）;ub和lb是搜索空間的上界和下界;r1、r2、r3、r4以及q是五個(gè)［0，1］的隨機(jī)數(shù)。Xm是當(dāng)前鷹群的平均位置，可以用式（9）來(lái)計(jì)算。Xn是鷹群的第n只鷹，Num是鷹的個(gè)數(shù)（種群大?。?。

2）開(kāi)發(fā)階段

a）軟圍攻狀態(tài)。當(dāng)r≥0.5且|E|<0.5時(shí)，進(jìn)入軟圍攻狀態(tài)，利用式（10）更新鷹的位置。其中，ΔX是獵物和當(dāng)前鷹之間的距離，J是跳躍能量，計(jì)算如式（11）（12）所示。r5是每次迭代產(chǎn)生的［0，1］隨機(jī)數(shù)。

X（t+1）=ΔX（t）－E|JXr（t）－X（t）|（10）

ΔX（t）=Xr（t）－X（t）（11）

J=2（1－r5）（12）

b）硬圍攻狀態(tài)。當(dāng)r≥0.5且|E|<0.5時(shí)，進(jìn)入硬圍攻狀態(tài)。在此狀態(tài)下，通過(guò)式（13）進(jìn)行鷹位置的更新。

X（t+1）=Xr（t）－E|ΔX（t）|（13）

c）漸進(jìn)式快速俯沖的軟包圍。當(dāng)r < 0.5且|E| ≥ 0.5時(shí)，執(zhí)行漸進(jìn)式快速俯沖的軟包圍，鷹的位置通過(guò)式（14）進(jìn)行更新。

其中：F（·）為適應(yīng)度函數(shù);Y和Z為新生成的兩只鷹，分別由式（15）（16）所得。式（16）中：D表示鷹的維度;α是一個(gè)D維的隨機(jī)向量;Levy是萊維飛行函數(shù)（式（17））。

Y=Xr（t）－E|JXr（t）－X（t）|（15）

Z=Y+α×Levy（D）（16）

其中：μ、 ν是由正態(tài)分布生成的兩個(gè)獨(dú)立隨機(jī)數(shù);σ定義為式（18）;β為常量，設(shè)置為1.5。

d）漸進(jìn)式快速俯沖硬包圍。當(dāng)r<0.5且|E|<0.5時(shí)，HHO執(zhí)行漸進(jìn)式快速俯沖硬包圍。在此狀態(tài)，利用式（19）進(jìn)行鷹的位置更新。

其中：F（·）為適應(yīng)度函數(shù);Y和Z分別是最近生成的兩只鷹，分別由式（20）（21）所得。

Y=Xr（t）－E|JXr（t）－Xm（t）|（20）

Z=Y+α×Levy（D）（21）

Too等人［24］提出了二進(jìn)制哈里斯鷹優(yōu)化算法BHHO用于特征選擇。第t次迭代時(shí)，第i只鷹的第d維度的位置是Xdi（t），利用HHO得到的t+1次迭代時(shí)的位置為ΔXdi（t+1），此時(shí)ΔXdi（t+1）為連續(xù)變量，BHHO利用式（22）（23）將連續(xù)變量轉(zhuǎn)換為布爾變量。

2 HHUIM算法

與許多基于智能優(yōu)化的HUIM類似，本文算法HHUIM是一種迭代算法，在每次迭代中產(chǎn)生大量的項(xiàng)集，并且通過(guò)計(jì)算項(xiàng)集所對(duì)應(yīng)個(gè)體的適應(yīng)度函數(shù)值來(lái)判斷其是否為HUIs。

2.1 基于位圖的項(xiàng)集擴(kuò)展策略

HHUIM使用位圖進(jìn)行編碼。如圖1所示，每一只鷹用一個(gè)向量來(lái)表示。鷹的總長(zhǎng)度為數(shù)據(jù)庫(kù)中1-HTWUI的數(shù)量。以表2中的數(shù)據(jù)庫(kù)為例，假設(shè)最小效用閾值為50，則1-HTWUI一共有5個(gè)，分別為{a}，，{c}，syggg00，{f}。鷹的每一個(gè)維度分別代表一個(gè)獨(dú)立的項(xiàng)，若鷹的第i個(gè)位置設(shè)置為1，說(shuō)明第i個(gè)項(xiàng)被選擇組成一個(gè)項(xiàng)集，否則說(shuō)明該項(xiàng)未被選擇。如圖1所示的向量X1=〈10100〉表示項(xiàng)集{a，c}。此外，表2中的數(shù)據(jù)庫(kù)可以轉(zhuǎn)換為圖2的位圖形式。

HHUIM使用位圖來(lái)編碼項(xiàng)集，項(xiàng)集X被表示為一個(gè)二進(jìn)制的向量。假設(shè)向量最后一個(gè)1的后面有num0個(gè)0，隨機(jī)選擇k個(gè)0使其變?yōu)?，得到的新向量所對(duì)應(yīng)的項(xiàng)集即為項(xiàng)集X的超集，其中k不大于num0。例如，圖3為項(xiàng)集{a，c}的超集形成過(guò)程。項(xiàng)集{a，c}用向量可以表示為〈10100〉，最后的1在第3位，其后有兩個(gè)0。若將第一個(gè)0變成1，此時(shí)向量變?yōu)椤?0110〉，代表超集{a，c，d}；若將最后一個(gè)0變成1，則向量變?yōu)椤?0101〉，代表項(xiàng)集{a，c，f}；若將項(xiàng)集{a，c，d}所對(duì)應(yīng)向量的最后一個(gè)0變成1，形成〈10111〉，代表超集{a，c，d，f}。

2.2 鷹的替換策略

因啟發(fā)式算法的隨機(jī)性，出現(xiàn)在挖掘過(guò)程中的鷹hawki有可能是有效鷹也有可能是無(wú)效鷹，即hawki的適應(yīng)度函數(shù)值可能大于minutil也可能小于minutil。因此本文提出鷹的替換策略，以縮小算法的搜索空間，加快算法的收斂，從而增加獲得HUIs的概率，使算法以更少的迭代次數(shù)挖掘出較多的HUIs。在介紹鷹的替換策略之前，先進(jìn)行一些定義。

定義10 鷹hawki的適應(yīng)度函數(shù)值為其所對(duì)應(yīng)項(xiàng)集Xi的效用值，記為fitness（hawki），定義為

fitness（hawki）=u（Xi）（24）

例如，如表2所示的數(shù)據(jù)集，假設(shè)鷹hawk3=〈110000〉，其所對(duì)應(yīng)的項(xiàng)集為{a，b}，則鷹hawk3的適應(yīng)度函數(shù)值fitness（hawk3）=u（{a，b}）=21。

定義11 記鷹hawki所對(duì)應(yīng)的位圖為Biti，若鷹hawkk的位圖滿足式（25），則被稱為鷹hawki的相反鷹，記為rehawki。

其中：Bitkj為鷹hawkk位圖的第j維;temp為Biti的最后一個(gè)1所在的位置。例如，若鷹hawk1的位圖為〈10100〉，則其相反鷹為〈00011〉。

定義12 鷹的局部突變（hawk local mutations）。在鷹的位圖向量的第1到第temp個(gè)位置，隨機(jī)選擇1個(gè)位置進(jìn)行比特變換，即將此位置的0變成1，或?qū)⒋宋恢玫?變?yōu)?。

定義13 鷹的超突變（hawk hypermutation）。在鷹的位圖向量的第temp+1到第L個(gè)位置，隨機(jī)選擇k個(gè)位置進(jìn)行比特變換，即此位置的0變成1，或?qū)⒋宋恢玫?變?yōu)?。其中1

鷹的替換策略偽代碼如算法1所示。在算法運(yùn)行的過(guò)程中，會(huì)判斷當(dāng)前hawki是否為有效鷹（步驟a））。若當(dāng)前hawki的適應(yīng)度函數(shù)值不小于minutil，則為有效鷹，將其所對(duì)應(yīng)的項(xiàng)集輸出為HUIs（步驟b））。若hawki為無(wú)效鷹，此時(shí)進(jìn)入鷹的替換策略（步驟c）～j））。首先形成hawki的相反鷹rehawki（步驟d））。判斷hawki的適應(yīng)度函數(shù)值加上其相反鷹的適應(yīng)度函數(shù)值是否大于minutil（步驟e））。若不小于minutil，則進(jìn)行鷹的超突變，形成新的鷹hawki+1來(lái)替換鷹hawki（步驟f））。若小于minutil，則進(jìn)行鷹的局部突變，形成新的鷹hawki+1來(lái)替換鷹hawki（步驟g）h））。

算法1 鷹的替換策略

輸入：鷹hawki。

輸出：新的鷹hawki+1。

a） if fitness（hawki）≥minutil

b）? ?SHUI←hawki+1所對(duì)應(yīng)的項(xiàng)集

c） else if fitness（hawki）

d）? ?形成hawki+1的相反鷹rehawki+1

e）? ?if fitness（hawki）+fitness（rehawki）≥minutil

f）???? 進(jìn)行鷹的超突變，形成鷹hawki+1

g）? ?else if fitness（hawki）+fitness（rehawki）

h）???? 算法進(jìn)行鷹的局部突變，形成鷹hawki+1

i）? ?end if

j） end if

例如，假設(shè)當(dāng)前鷹hawki的位圖向量為〈10100〉，圖4顯示了鷹的替換過(guò)程。首先計(jì)算hawki的適應(yīng)度函數(shù)值fitness（hawki），若fitness（hawki）≥minutil，則將其所對(duì)應(yīng)的項(xiàng)集輸出為HUIs。若fitness（hawki）

2.3 存儲(chǔ)回溯策略

為了防止算法因收斂過(guò)快容易陷入局部最優(yōu)，提出存儲(chǔ)回溯策略，以保持種群的多樣性，使算法能夠挖掘更多的HUIs。如圖5所示，橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示所挖掘的高效用項(xiàng)集的數(shù)量，實(shí)線表示HUIs的數(shù)量隨著迭代次數(shù)而變化的趨勢(shì)?？梢钥闯?，HUIs的數(shù)量隨著算法的迭代逐漸收斂。P點(diǎn)為HUIs的數(shù)量增長(zhǎng)速率最快的點(diǎn)，此時(shí)種群的多樣性是最大的。將P點(diǎn)的鷹群放入存儲(chǔ)池中。當(dāng)某次迭代挖掘出的HUIs的數(shù)量較小時(shí)，到達(dá)Q點(diǎn)。此時(shí)鷹群的多樣性較低，算法接近收斂。將Q點(diǎn)的鷹群替換為存儲(chǔ)池中的鷹群，使算法跳出局部最優(yōu)，沿著虛線繼續(xù)運(yùn)行。存儲(chǔ)回溯策略的偽代碼如算法2所示。

算法2 存儲(chǔ)回溯策略

輸入：鷹群populationt；存放HUIs的集合SHUI;上次迭代產(chǎn)生的HUIs數(shù)量lastHUI;本次迭代產(chǎn)生的HUIs數(shù)量ΔHUI;ΔHUI的最大值maxHUI;存放在存儲(chǔ)池內(nèi)的鷹群Pc;種群大小pop_size。

輸出：新的鷹群hawki+1。

a）ΔHUI=SHUI.size（）-lastHUI;

b）lastHUI=SHUI.size（）;

c）if ΔHUI>maxHUI

d）? maxHUI=ΔHUI

e）? Pc←populationt //將此時(shí)的鷹群放入存儲(chǔ)池中

f）else if ΔHUI

g）? ?populationt←Pc //用存儲(chǔ)池中的鷹群替換當(dāng)前種群

h） end if

2.4 算法描述

本文HHUIM的偽代碼如算法3所示。該方法的輸入為事務(wù)數(shù)據(jù)集DB、最小效用閾值minutil以及最大的迭代次數(shù)T。算法一共分為數(shù)據(jù)初始化部分、種群初始化部分、種群更新部分以及高效用項(xiàng)集的識(shí)別部分四個(gè)部分。

第一個(gè)部分是數(shù)據(jù)初始化部分，包括對(duì)數(shù)據(jù)庫(kù)的掃描以及重組數(shù)據(jù)庫(kù)。步驟a）掃描數(shù)據(jù)庫(kù)，計(jì)算所有1-項(xiàng)集的twu，若1-項(xiàng)集的twu小于minutil，說(shuō)明這是沒(méi)有希望的項(xiàng)，其超集不可能是HUIs，因此將該項(xiàng)從數(shù)據(jù)庫(kù)中刪除。步驟b）將重組后的數(shù)據(jù)庫(kù)轉(zhuǎn)換為如圖2所示的位圖形式。

第二個(gè)部分是種群初始化部分（步驟d）），隨機(jī)初始化Num只鷹。其中鷹的大小為原始數(shù)據(jù)庫(kù)中1-HTWUL的數(shù)量。分別計(jì)算每只鷹的適應(yīng)度函數(shù)值，若適應(yīng)度函數(shù)值不小于minutil，說(shuō)明這個(gè)鷹所對(duì)應(yīng)的項(xiàng)集是HUI，則將其放入SHUI中，并尋找適應(yīng)度函數(shù)最高的那只鷹，作為gbest。

第三部分為種群更新部分（步驟g）～t）），對(duì)于當(dāng)前種群中的每一只鷹，利用哈里斯鷹優(yōu)化算法進(jìn)行位置更新，形成新的種群。

第四部分是高效用項(xiàng)集的識(shí)別部分。步驟u）對(duì)更新位置后的鷹計(jì)算其適應(yīng)度函數(shù)值，若適應(yīng)度函數(shù)值不小于minutil，說(shuō)明當(dāng)前鷹所對(duì)應(yīng)的項(xiàng)集為HUI，則將其放入SHUI集合中。然后更新gbest，算法迭代繼續(xù)進(jìn)行，直到達(dá)到最大的迭代次數(shù)。最后輸出SHUI中所有的高效用項(xiàng)集以及項(xiàng)集的個(gè)數(shù)。

算法3 HHUIM

輸入：事務(wù)數(shù)據(jù)集DB;最小效用閾值minutil;最大的迭代次數(shù)T。

輸出：一組高效用項(xiàng)集。

a） 掃描數(shù)據(jù)庫(kù)DB，計(jì)算所有1-項(xiàng)集的twu，將所有的1-LTWUI從DB中刪除。

b） 將數(shù)據(jù)庫(kù)轉(zhuǎn)換為位圖的形式。

c） SHUI=null。 // 將存放HUIs的集合初始化為空

d） 種群初始化。

e） t=1 to T

f） 對(duì)于當(dāng)前種群中的每一只鷹hawk（i）。

g） 生成一個(gè)隨機(jī)數(shù)r，分別使用式（7）（12）計(jì)算E0和J，利用式（6）更新能量E。

h） if （|E|≥1）

i）? ?搜索階段，利用式（8）（17）更新鷹的位置。

j） ?else if （|E|<1）

k）? ?if （r≥0.5且|E|≥0.5）

l）?? ?軟圍攻階段，利用式（10）（22）更新鷹的位置。

m）? ?else if （r≥0.5且|E|<0.5）

n）?? ?硬圍攻階段，使用式（13）（22）進(jìn)行位置的更新。

o）? ?else if （r<0.5且|E|≥0.5）

p）?? ?漸進(jìn)式快速俯沖的軟包圍，使用式（14）（22）更新位置。

q）? ?else if （r<0.5且|E|<0.5）

r）?? ?漸進(jìn)式快速俯沖的硬包圍。使用式（19）（22）更新位置。

s）? ?end if

t） end if

u） if fitness（hawki）≥minutil

v）? ?SHUI←hawki所對(duì)應(yīng)的項(xiàng)集。

w） end if

x） 更新gbest。

y） 算法循環(huán)迭代，直到達(dá)到最大的迭代次數(shù)。

z） 輸出所有的高效用項(xiàng)集。

2.5 舉例說(shuō)明

為了演示算法HHUIM的挖掘過(guò)程，本節(jié)將舉例說(shuō)明，以表2中數(shù)據(jù)庫(kù)為示例，并假設(shè)用戶定義的最小效用閾值minutil=31，種群大小為3，最大迭代次數(shù)為5。挖掘過(guò)程如圖6所示。

首先進(jìn)行數(shù)據(jù)的處理。數(shù)據(jù)集中1-項(xiàng)集有{a}，，{c}，syggg00，{e}，{f}，其twu分別為55，101，73，78，46，50，均大于31，因此該窗口內(nèi)所有的1-項(xiàng)集均為1-HTWUI。與此同時(shí)，將數(shù)據(jù)集轉(zhuǎn)換為位圖的形式，其中位圖的長(zhǎng)度為數(shù)據(jù)集中1-HTWUI的數(shù)量，即為6。

隨后進(jìn)入利用哈里斯鷹優(yōu)化挖掘高效用項(xiàng)集階段，其迭代過(guò)程如圖6所示。首先初始化種群，即隨機(jī)生成3個(gè)長(zhǎng)度為6的向量，代表種群中3只鷹的位置，分別為Hawk01〈000100〉、Hawk02〈101001〉、Hawk03〈111100〉。接下來(lái)以Hawk02為例說(shuō)明鷹Hawk02如何通過(guò)哈里斯鷹優(yōu)化更新為Hawk12。

在初始種群中，適應(yīng)度函數(shù)值最高的鷹為Hawk01〈000100〉，所以將Hawk01視為全局最優(yōu)，用Xr來(lái)表示，此時(shí)Xr=Hawk01=〈000100〉。首先計(jì)算獵物的初始逃逸能量E0、逃逸能量E以及跳躍能量J。假設(shè)隨機(jī)數(shù)r=0.7，r5=0.3，則根據(jù)式（6）（7）和（12）可得

因?yàn)閨E|=0.64<1，且r=0.7≤0.5，所以進(jìn)入軟圍攻階段。根據(jù)式（10）（11）可得

ΔX12=X（t+1）=ΔX（t）－E|JXr（t）－X（t）|=Xr（t）－X（t）－E|JXr（t）－X（t）|=

〈000100〉－〈101001〉－0.64|1.4〈000100〉－〈101001〉|=

〈－1.64，0，－1.64，0.104，0，－1.64〉

此時(shí)ΔX12=〈-1.64，0，-1.64，0.104，0，-1.64〉是連續(xù)變量，需要將其轉(zhuǎn)換為布爾變量。根據(jù)式（23）可得

假設(shè)rand0=0.1，rand1=0.3，rand2=0.7，rand3=0.4，rand4=0.6，rand5=0.1，根據(jù)式（22）可得X12=〈110101〉，即Hawk12=〈110101〉。

以第一次迭代為例，對(duì)于新種群中的每一只鷹，計(jì)算其適應(yīng)度函數(shù)值。鷹Hawk11〈010100〉，Hawk12〈110101〉，Hawk13〈001100〉的適應(yīng)度函數(shù)值分別為52，21，30。其中fitness（Hawk11）=52>31，說(shuō)明Hawk11對(duì)應(yīng)的項(xiàng)集X11={b，d}為高效用項(xiàng)集，則將項(xiàng)集{b，d}存入SHUI中。第一次迭代結(jié)束后，此時(shí)所有的HUIs只有{b，d}。算法進(jìn)行迭代時(shí)，每當(dāng)鷹的位置更新后，都需要判斷其適應(yīng)度函數(shù)值是否大于minutil，如果大于，則將其所對(duì)應(yīng)的項(xiàng)集輸出為HUIs。當(dāng)達(dá)到最大的迭代次數(shù)時(shí)，算法結(jié)束，此時(shí)的高效用項(xiàng)集有7個(gè)，分別為{b，d}，{a，b，d}，，{b，c}，{b，c，f}，{b，c，d}和{b，c，e}。

3 實(shí)驗(yàn)

本章從HUIs的數(shù)量、算法運(yùn)行時(shí)間、內(nèi)存等方面進(jìn)行了大量的對(duì)比實(shí)驗(yàn)，將HHUIM與目前較為先進(jìn)的啟發(fā)式高效用項(xiàng)集挖掘算法HUIM-BPSO［11］、HUIM-SPSO［25］、Bio-HUIF-PSO［23］、HUIM-AF［13］、Bio-HUIF-BA［23］以及Bio-HUIF-GA［23］進(jìn)行對(duì)比。實(shí)驗(yàn)運(yùn)行環(huán)境為16.0 GB可用RAM，Intel Core-i5-1235U@1.30 GHz CPU以及Windows 11操作系統(tǒng)。其中對(duì)比實(shí)驗(yàn)的源碼以及數(shù)據(jù)集均下載于SPMF平臺(tái)。因?yàn)橹悄軆?yōu)化算法具有極強(qiáng)的隨機(jī)性，導(dǎo)致結(jié)果的偏差很大，本章所有實(shí)驗(yàn)數(shù)據(jù)均為運(yùn)行10次取平均得到。實(shí)驗(yàn)所使用的數(shù)據(jù)集為chess、connect、mushroom、accidents、foodmart以及retail，其參數(shù)如表4所示。為了測(cè)試所提出策略的有效性，將鷹的替換策略與存儲(chǔ)回溯策略分別加入HHUIM中，命名為HHUIM-R和HHUIM-S，并將其作為對(duì)比實(shí)驗(yàn)與HHUIM一起比較。

啟發(fā)式HUIM因其迭代次數(shù)由用戶指定，具有可隨時(shí)獲得結(jié)果的優(yōu)點(diǎn)；此外，種群大小對(duì)實(shí)驗(yàn)結(jié)果的影響也很大。因此啟發(fā)式HUIM大多數(shù)比較的是在相同迭代次數(shù)和相同種群大小的前提下，算法的運(yùn)行時(shí)間以及能夠挖掘出來(lái)HUIs的數(shù)量。而傳統(tǒng)確定性算法需等待算法全部運(yùn)行結(jié)束后才可以獲得結(jié)果，且挖掘的項(xiàng)集是全部的HUIs，因此確定性算法比較的是時(shí)空效率。啟發(fā)式HUIM與確定性算法是沒(méi)有可比性的，因此本章未將確定性算法作為對(duì)比算法。

哈里斯鷹優(yōu)化算法的時(shí)間復(fù)雜度主要取決于種群初始化、適應(yīng)度值的計(jì)算以及鷹的位置更新。在本文中，面向高效用項(xiàng)集挖掘問(wèn)題，對(duì)于N只鷹，初始化的時(shí)間復(fù)雜度為O（N），計(jì)算適應(yīng)度函數(shù)值并尋找最優(yōu)解的時(shí)間復(fù)雜度為O（T×N），假設(shè)數(shù)據(jù)集中1-HTWUI的數(shù)量為D，最大迭代次數(shù)為T(mén)，則鷹進(jìn)行位置更新的時(shí)間復(fù)雜度為O（T×N×D）。因此，在HUIM中，影響時(shí)間復(fù)雜度的主要參數(shù)為迭代次數(shù)、種群大小以及數(shù)據(jù)集中1-HTWUI的數(shù)量D。但是D對(duì)于每一個(gè)數(shù)據(jù)集是固定不變的，無(wú)法人工設(shè)置，因此，T和N越大，算法的運(yùn)行時(shí)間越長(zhǎng)。然而，若T和N過(guò)小，則會(huì)丟失大量的項(xiàng)集。因此，需要根據(jù)經(jīng)驗(yàn)以及多次的實(shí)驗(yàn)和分析，找到最優(yōu)的參數(shù)組合。表5為先前算法的參數(shù)設(shè)置。本文根據(jù)以往經(jīng)驗(yàn)，利用二分法將種群大小設(shè)置為20～500，迭代次數(shù)設(shè)置為100～10 000。實(shí)驗(yàn)中，在算法的運(yùn)行時(shí)間以及查全率之間進(jìn)行權(quán)衡，得到最終參數(shù)為：種群大小100，最大迭代次數(shù)1 000。

圖7展示了隨著閾值變化，算法挖掘出來(lái)的HUIs數(shù)量變化趨勢(shì)。可以看出，HUIs的數(shù)量與閾值大小成反比，且隨著閾值的增加，各算法所挖掘出來(lái)的HUIs數(shù)量達(dá)到了接近的水平。在chess數(shù)據(jù)集中（圖7（a）），HHUIM及其變體HHUIM-R和HHUIM-S能夠挖掘出最多的HUIs，當(dāng)閾值為27%時(shí)，所挖掘出來(lái)的HUIs的數(shù)量是HUIM-BPSO、HUIM-SPSO以及HUIM-AF的兩倍多。同樣地，在connect（圖7（b））以及mushroom（圖7（c））數(shù)據(jù)集中，本文算法同樣能夠挖掘出最多的HUIs。圖7（d）是在accidents數(shù)據(jù)集中挖掘出來(lái)的HUIs的數(shù)量，值得注意的是，在12%的效用閾值下，各算法均未能挖掘出所有高效用項(xiàng)集。這是因?yàn)閷?shí)驗(yàn)參數(shù)設(shè)置種群大小為100，最大迭代次數(shù)為1 000，當(dāng)達(dá)到最大迭代次數(shù)時(shí)，部分算法尚未收斂。如果能延長(zhǎng)最大迭代次數(shù)，所能挖掘出的HUIs數(shù)量將進(jìn)一步增加。將1 000次作為最大迭代次數(shù)是因?yàn)閱l(fā)式算法的HUIM具有可以隨時(shí)停止的優(yōu)點(diǎn)，所以取1 000次作為最大迭代次數(shù)是完全合理的，即使此時(shí)算法尚未收斂。在稀疏數(shù)據(jù)集中，算法HUIM-SPSO和HUIM-AF的執(zhí)行時(shí)間超過(guò)20 h仍未獲得結(jié)果，因此不在圖中顯示。在foodmart中（圖7（e）），本文算法挖掘到的HUIs數(shù)量略少于算法Bio-HUIF-PSO和Bio-HUIF-BA，這是因?yàn)閒oodmart數(shù)據(jù)集的平均事務(wù)長(zhǎng)度最短，而HHO具有探索性較強(qiáng)的特點(diǎn)，所以挖掘出來(lái)的HUIs數(shù)量可能會(huì)有所丟失。在retail數(shù)據(jù)集中（圖7（f）），本文算法能夠挖掘到最多的高HUIs。Bio-HUIF-PSO和Bio-HUIF-BA算法的表現(xiàn)則會(huì)隨著minutil的減小而出現(xiàn)HUIs數(shù)量減少的趨勢(shì)。這是因?yàn)樵趯?shí)驗(yàn)過(guò)程中，這兩個(gè)算法往往會(huì)產(chǎn)生空值，即挖掘出的HUIs數(shù)量為0。即使有時(shí)它們能夠挖掘到更多的HUIs，但求平均后仍會(huì)出現(xiàn)此類現(xiàn)象。此外，從圖中可以看出，HHUIM-R以及HHUIM-S能夠有效提高稀疏數(shù)據(jù)集中算法能夠挖掘出來(lái)的HUIs的數(shù)量。

圖8展示了各算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間。在chess數(shù)據(jù)集中，HHUIM和HHUIM-S的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于其他對(duì)比算法，其中HUIM-AF的運(yùn)行時(shí)間是其3.5倍。在connect和mushroom數(shù)據(jù)集中，HHUIM以及HHUIM-S的運(yùn)行時(shí)間最短，其中HHUIM-S比HHUIM更快一些。在connect數(shù)據(jù)集中，除算法HUIM-SPSO外，HHUIM、HHUIM-S以及HHUIM-R的運(yùn)行時(shí)間遠(yuǎn)小于其他對(duì)比算法。圖8（e）（f）為兩個(gè)稀疏數(shù)據(jù)集，其中在foodmart數(shù)據(jù)集中，算法HHUIM和HHUIM-S的運(yùn)行時(shí)間在18 s左右，在retail數(shù)據(jù)集中，運(yùn)行時(shí)間為41 s左右。算法HHUIM-R需花費(fèi)大量時(shí)間進(jìn)行鷹的替換策略，因此所花費(fèi)的時(shí)間大于算法HHUIM和HHUIM-S。

圖9展示了算法在不同數(shù)據(jù)集上的內(nèi)存占用對(duì)比。圖9（a）（b）分別為數(shù)據(jù)集chess和connect，其密度分別為49.33%和33.33%，是相對(duì)密集的數(shù)據(jù)。HHUIM-R所占用的內(nèi)存明顯小于HHUIM和HHUIM-S，這是因?yàn)辁椀奶鎿Q策略中，若當(dāng)前鷹的適應(yīng)度函數(shù)值小于最小效用閾值，則不將其作為下一次迭代初始種群中的個(gè)體，而是進(jìn)行替換，相當(dāng)于對(duì)搜索空間進(jìn)行了剪枝，所以鷹的替換策略可以有效減少內(nèi)存的使用。未來(lái)，可以將鷹的替換策略擴(kuò)展為種群中個(gè)體的替換，以在密集數(shù)據(jù)集中降低內(nèi)存消耗。在mushroom數(shù)據(jù)集中，本文算法所占用的內(nèi)存仍然是最少的，而在最大的數(shù)據(jù)集accidents中，所占用的內(nèi)存相對(duì)較多。在稀疏數(shù)據(jù)集retail中，算法HHUIM-S的內(nèi)存占用要小于算法HHUIM和HHUIM-R，這是因?yàn)閿?shù)據(jù)集retail為極度稀疏的數(shù)據(jù)集，大部分搜索空間是未被搜索到的，鷹的存儲(chǔ)回溯策略在保持種群多樣性的同時(shí)，可以幫助算法存儲(chǔ)并追蹤已經(jīng)訪問(wèn)過(guò)的搜索空間位置，從而有效減少內(nèi)存的使用。

經(jīng)過(guò)綜合比較算法執(zhí)行時(shí)間、內(nèi)存以及所挖掘出來(lái)的HUIs的數(shù)量，本文算法在性能方面表現(xiàn)最佳。其中，鷹的替換策略和存儲(chǔ)回溯策略是有效的，它們可以在一定程度上增加算法所能夠挖掘出來(lái)的HUIs的數(shù)量。此外，在密集型數(shù)據(jù)集上，鷹的替換策略能夠有效減少內(nèi)存的使用；而在稀疏數(shù)據(jù)集上，存儲(chǔ)回溯策略能夠有效降低內(nèi)存的占用。需要注意的是，算法的性能受到數(shù)據(jù)集特征、參數(shù)配置等多方面因素的影響，所以使用時(shí)需要綜合考慮不同因素的影響，并進(jìn)行適當(dāng)優(yōu)化。

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

高效用項(xiàng)集挖掘旨在挖掘出事務(wù)數(shù)據(jù)庫(kù)中具有重要意義的項(xiàng)集。近年來(lái)，啟發(fā)式算法得到了快速發(fā)展和廣泛應(yīng)用，并成為許多復(fù)雜問(wèn)題求解的有效策略。其中，啟發(fā)式算法與HUIM的結(jié)合能夠有效提高海量數(shù)據(jù)中高效用項(xiàng)集的挖掘效率，因此這也成為了一個(gè)新興的研究方向。然而，目前基于啟發(fā)式的HUIM存在著容易丟失大量項(xiàng)集的問(wèn)題，因此本文提出了一種新的基于哈里斯鷹優(yōu)化的啟發(fā)式高效用項(xiàng)集挖掘算法HHUIM。此外，本文提出了鷹的替換策略，該策略可大大縮小算法的搜索空間，降低適應(yīng)度函數(shù)值低于最小效用閾值的鷹的數(shù)量；同時(shí)，針對(duì)算法因多樣性下降而導(dǎo)致的收斂過(guò)快和大量項(xiàng)集丟失問(wèn)題，提出了存儲(chǔ)回溯策略。

為了測(cè)試本文算法的性能，在真實(shí)數(shù)據(jù)集中進(jìn)行大量的實(shí)驗(yàn)，結(jié)果表明，本文算法優(yōu)于目前最先進(jìn)的啟發(fā)式高效用項(xiàng)集挖掘算法。同時(shí)，鷹的替換策略和存儲(chǔ)回溯策略也能夠有效提高算法所挖掘出來(lái)的HUIs的數(shù)量，鷹的替換策略在密集數(shù)據(jù)集中，以及存儲(chǔ)回溯策略在稀疏數(shù)據(jù)集中均能夠減少內(nèi)存的使用。

未來(lái)，本研究組將繼續(xù)開(kāi)發(fā)更加高效的高效用項(xiàng)集挖掘算法，并對(duì)鷹的替換策略進(jìn)行優(yōu)化。

參考文獻(xiàn)：

[1]Lin J C W， Djenouri Y， Srivastava G， et al. Efficient evolutionary computation model of closed high-utility itemset mining［J］.Applied Intelligence，2022，52（9）：10604-10616.

［2]Liu Mengchi， Qu Junfeng. Mining high utility itemsets without candidate generation［C］//Proc of the 21st ACM International Conference on Information and Knowledge Management.New York：ACM Press，2012：55-64.

［3]Zida S， Fournier-Viger P， Lin J C W， et al. EFIM： a fast and memory efficient algorithm for high-utility itemset mining［J］.Knowledge and Information Systems，2017，51（2）：595-625.

［4]Fournier-Viger P， Wu C W， Zida S， et al. FHM：faster high-utility itemset mining using estimated utility co-occurrence pruning［M］//Andreasen T， Christiansen H， Cubero J C， et al. Foundations of Intelligent Systems.Cham：Springer，2014：83-92.

［5]Cheng Zaihe， Fang Wei， Shen Wei， et al. An efficient utility-list based high-utility itemset mining algorithm［J］.Applied Intelligence，2023，53（6）：6992-7006.

［6]Nawaz M S， Fournier-Viger P， Yun U， et al. Mining high utility itemsets with hill climbing and simulated annealing［J］.ACM Trans on Management Information System，2021，13（1）：1-22.

［7]Fang Wei， Li Chongyang， Zhang Qiang， et al. An efficient biobjective evolutionary algorithm for mining frequent and high utility itemsets［J］.Applied Soft Computing，2023，140：110233.

［8]Kannimuthu S， Premalatha K. Discovery of high utility itemsets using genetic algorithm with ranked mutation［J］.Applied Artificial Intelligence，2014，28（4）：337-359.

［9]吳大飛，楊光永，樊康生，等.多策略融合的改進(jìn)粒子群優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2022，39（11）：3358-3364.（Wu Dafei， Yang Guangyong， Fan Kangsheng， et al. Improved particle swarm optimization algorithm with multi-strategy fusion［J］.Application Research of Computers，2022，39（11）：3358-3364.）

［10]Lin J C W， Yang Lu， Fournier-Viger P， et al. A binary PSO approach to mine high-utility itemsets［J］.Soft Computing，2017，21：5103-5121.

［11]Lin J C W， Yang Lu， Fournier-Viger P， et al. Mining high-utility itemsets based on particle swarm optimization［J］.Engineering Applications of Artificial Intelligence，2016，55：320-330.

［12]Song Wei， Huang Chaoming. Discovering high utility itemsets based on the artificial bee colony algorithm［M］//Phung D，Tseng V， Webb G， et al. Advances in Knowledge Discovery and Data Mining.Cham：Springer，2018：3-14.

［13]Song Wei， Li Junya， Huang Chaoming. Artificial fish swarm algorithm for mining high utility itemsets［M］//Tan Ying， Shi Yuhui.Advances in Swarm Intelligence.Cham：Springer，2021：407-419.

［14]Pazhaniraja N， Sountharrajan S， Suganya E， et al. Optimizing high-utility item mining using hybrid dolphin echolocation and Boolean grey wolf optimization［J］.Journal of Ambient Intelligence and Huma-nized Computing，2023，14（3）：2327-2339.

［15]Song Wei， Huang Chaoming. Mining high average-utility itemsets based on particle swarm optimization［J］.Data Science and Pattern Recognition，2020，4（2）：19-32.

［16]Pramanik S， Goswami A. Discovery of closed high utility itemsets using a fast nature-inspired ant colony algorithm［J］.Applied Intelligence，2022，52（8）：8839-8855.

［17]Lin J C W， Djenouri Y， Srivastava G， et al. A predictive GA-based model for closed high-utility itemset mining［J］.Applied Soft Computing，2021，108：107422.

［18]Song Wei， Zheng Chuanlong， Huang Chaomin， et al. Heuristically mining the top-k high-utility itemsets with cross-entropy optimization［J］.Applied Intelligence，2022，52：17026-17041.

［19]Luna J M， Kiran R U， Fournier-Viger P， et al. Efficient mining of top-k high utility itemsets through genetic algorithms［J］.Information Sciences，2023，624：529-553.

［20]Heidari A A， Mirjalili S， Faris H， et al. Harris hawks optimization：algorithm and applications［J］.Future Generation Computer Systems，2019，97：849-872.

［21]孫蕊，韓萌，張春硯，等.精簡(jiǎn)高效用模式挖掘綜述［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（4）：975-981.（Sun Rui， Han Meng， Zhang Chunyan， et al. Survey of algorithms for concise high utility pattern mining［J］.Application Research of Computers，2021，38（4）：975-981.）

［22]張春硯，韓萌，孫蕊，等.高效用模式挖掘關(guān)鍵技術(shù)綜述［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（2）：330-340.（Zhang Chunyan， Han Meng， Sun Rui. Survey of key technologies for high utility patterns mining［J］.Application Research of Computers，2021，38（2）：330-340.）

［23]Song Wei， Huang Chaomin. Mining high utility itemsets using bio-inspired algorithms：a diverse optimal value framework［J］.IEEE Access，2018，6：19568-19582.

［24]Too J， Abdullah A R， Mohd Saad N. A new quadratic binary Harris hawk optimization for feature selection［J］.Electronics，2019，8（10）：1130.

［25]Song Wei， Li Junya. Discovering high utility itemsets using set-based particle swarm optimization［M］//Yang Xiaochun， Wang Changdong， Islam M S， et al. Advanced Data Mining and Applications.Cham：Springer，2020：38-53.

［26]Wu J M T， Zhan J， Lin J C W. An ACO-based approach to mine high-utility itemsets［J］.Knowledge-Based Systems，2017，116：102-113.

［27]Arunkumar M S， Suresh P， Gunavathi C. High utility infrequent itemset mining using a customized ant colony algorithm［J］.International Journal of Parallel Programming，2020，48：833-849.

［28]Pazhaniraja N， Sountharrajan S， Sathis Kumar B. High utility itemset mining： a Boolean operators-based modified grey wolf optimization algorithm［J］.Soft Computing，2020，24：16691-16704.