HHUIM：一種新的啟發式高效用項集挖掘方法

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

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

關鍵詞：哈里斯鷹優化算法； 高效用項集挖掘； 啟發式算法； 智能優化算法

中圖分類號：TP311?? 文獻標志碼：A?? 文章編號：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 引言

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

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

所有的這些算法都能夠在較短的時間內快速找到很多高效用項集。然而這些算法因智能優化算法具有較強的隨機性，或者由于其算法本身的特性很容易達到局部最優而不會繼續探索下去，從而丟失一定的項集。比如基于遺傳算法的HUIM具有交叉率和突變率，這是種群保持多樣性的關鍵，而同時也會給算法帶來一定的隨機性，因此設置一個合適的突變率和交叉率是十分重要的，若設置不當，很容易導致算法陷入局部最優，進而導致算法不能繼續挖掘出新的HUI。基于粒子群的算法在進行粒子的初始化時，要隨機初始化粒子的速度以及位置，進行種群更新時，會根據輪盤賭選擇法或者基于sigmoid函數，然而這兩種算法都具有隨機性。同樣地，蝙蝠、人工蜂群、人工魚群等群智能算法同粒子群一樣，在種群初始化以及進行種群更新時，都具有隨機性，因此會遺漏一定數量的高效用項集。所以，基于智能優化算法的HUIM在所有數據集中以及所有的閾值下，在一定的迭代次數內都能找到所有的高效用項集是十分困難且沒有必要的。因此，怎樣減少項集的丟失是一個研究重點。

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

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

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

1 基本概念

1.1 高效用項集挖掘基本概念

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

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

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

定義3［3］ 事務T中項i的效用，表示為u（i，T），是項i在事務T中的內部效用與項i的外部效用的乘積，即iu（i，T）和eu（i）的乘積，被定義為

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

例如，事務T1中項a的效用，計算為u（a，T1）=iu（a，T1）×eu（a）=4×1=4。

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

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

定義5［4］ 項集X的效用，表示為u（X），是數據庫DB中所有包含X的事務T中項集X的效用之和，被定義為

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

定義6［4］ 事務T的效用（utility of transaction），表示為tu（T），是T中所有項的效用之和，其中，數據庫DB的總效用是DB中所有事務的效用之和，被定義為

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

定義7［2］ DB中項集X的事務加權效用（transaction weighted utility），表示為twu（X），是數據庫DB中包含項集X的所有事務的效用之和，定義為

例如，項集{a}的事務加權效用被計算為twu（{a}）=tu（T1）+tu（T3）=28+27=55。數據庫中所有1-項集的twu如表3所示。

定義8［23］ 若在數據庫DB中，項集X的事務加權效用不小于minutil，則項集X是高事務加權效用項集（high transaction weighted utilization itemset，HTWUI）。

定義9［23］ 若在數據庫DB中，項集X的事務加權效用小于minutil，則項集X是低事務加權效用項集（low transaction weighted utilization itemset，LTWUI）。

例如，若minutil=50，則數據庫DB中的1-HTWUI一共有5個，分別為{a}，{b}，{c}，g0gggggg，{f}，而1-LTWUI僅有{e}。

1.2 哈里斯鷹優化算法

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

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

1）探索階段

在探索階段，鷹的位置通過式（8）進行更新。其中：X是鷹的位置;Xk是隨機選擇的一只鷹的位置;Xr是獵物的位置（全局最優解gbest）;ub和lb是搜索空間的上界和下界;r1、r2、r3、r4以及q是五個［0，1］的隨機數。Xm是當前鷹群的平均位置，可以用式（9）來計算。Xn是鷹群的第n只鷹，Num是鷹的個數（種群大小）。

2）開發階段

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

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

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

J=2（1－r5）（12）

b）硬圍攻狀態。當r≥0.5且|E|<0.5時，進入硬圍攻狀態。在此狀態下，通過式（13）進行鷹位置的更新。

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

c）漸進式快速俯沖的軟包圍。當r < 0.5且|E| ≥ 0.5時，執行漸進式快速俯沖的軟包圍，鷹的位置通過式（14）進行更新。

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

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

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

其中：μ、 ν是由正態分布生成的兩個獨立隨機數;σ定義為式（18）;β為常量，設置為1.5。

d）漸進式快速俯沖硬包圍。當r<0.5且|E|<0.5時，HHO執行漸進式快速俯沖硬包圍。在此狀態，利用式（19）進行鷹的位置更新。

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

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

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

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

2 HHUIM算法

與許多基于智能優化的HUIM類似，本文算法HHUIM是一種迭代算法，在每次迭代中產生大量的項集，并且通過計算項集所對應個體的適應度函數值來判斷其是否為HUIs。

2.1 基于位圖的項集擴展策略

HHUIM使用位圖進行編碼。如圖1所示，每一只鷹用一個向量來表示。鷹的總長度為數據庫中1-HTWUI的數量。以表2中的數據庫為例，假設最小效用閾值為50，則1-HTWUI一共有5個，分別為{a}，{b}，{c}，g0gggggg，{f}。鷹的每一個維度分別代表一個獨立的項，若鷹的第i個位置設置為1，說明第i個項被選擇組成一個項集，否則說明該項未被選擇。如圖1所示的向量X1=〈10100〉表示項集{a，c}。此外，表2中的數據庫可以轉換為圖2的位圖形式。

HHUIM使用位圖來編碼項集，項集X被表示為一個二進制的向量。假設向量最后一個1的后面有num0個0，隨機選擇k個0使其變為1，得到的新向量所對應的項集即為項集X的超集，其中k不大于num0。例如，圖3為項集{a，c}的超集形成過程。項集{a，c}用向量可以表示為〈10100〉，最后的1在第3位，其后有兩個0。若將第一個0變成1，此時向量變為〈10110〉，代表超集{a，c，d}；若將最后一個0變成1，則向量變為〈10101〉，代表項集{a，c，f}；若將項集{a，c，d}所對應向量的最后一個0變成1，形成〈10111〉，代表超集{a，c，d，f}。

2.2 鷹的替換策略

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

定義10 鷹hawki的適應度函數值為其所對應項集Xi的效用值，記為fitness（hawki），定義為

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

例如，如表2所示的數據集，假設鷹hawk3=〈110000〉，其所對應的項集為{a，b}，則鷹hawk3的適應度函數值fitness（hawk3）=u（{a，b}）=21。

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

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

定義12 鷹的局部突變（hawk local mutations）。在鷹的位圖向量的第1到第temp個位置，隨機選擇1個位置進行比特變換，即將此位置的0變成1，或將此位置的1變為0。

定義13 鷹的超突變（hawk hypermutation）。在鷹的位圖向量的第temp+1到第L個位置，隨機選擇k個位置進行比特變換，即此位置的0變成1，或將此位置的1變為0。其中1

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

算法1 鷹的替換策略

輸入：鷹hawki。

輸出：新的鷹hawki+1。

a） if fitness（hawki）≥minutil

b）? ?SHUI←hawki+1所對應的項集

c） else if fitness（hawki）

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

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

f）???? 進行鷹的超突變，形成鷹hawki+1

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

h）???? 算法進行鷹的局部突變，形成鷹hawki+1

i）? ?end if

j） end if

例如，假設當前鷹hawki的位圖向量為〈10100〉，圖4顯示了鷹的替換過程。首先計算hawki的適應度函數值fitness（hawki），若fitness（hawki）≥minutil，則將其所對應的項集輸出為HUIs。若fitness（hawki）

2.3 存儲回溯策略

為了防止算法因收斂過快容易陷入局部最優，提出存儲回溯策略，以保持種群的多樣性，使算法能夠挖掘更多的HUIs。如圖5所示，橫坐標表示迭代次數，縱坐標表示所挖掘的高效用項集的數量，實線表示HUIs的數量隨著迭代次數而變化的趨勢。可以看出，HUIs的數量隨著算法的迭代逐漸收斂。P點為HUIs的數量增長速率最快的點，此時種群的多樣性是最大的。將P點的鷹群放入存儲池中。當某次迭代挖掘出的HUIs的數量較小時，到達Q點。此時鷹群的多樣性較低，算法接近收斂。將Q點的鷹群替換為存儲池中的鷹群，使算法跳出局部最優，沿著虛線繼續運行。存儲回溯策略的偽代碼如算法2所示。

算法2 存儲回溯策略

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

輸出：新的鷹群hawki+1。

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

b）lastHUI=SHUI.size（）;

c）if ΔHUI>maxHUI

d）? maxHUI=ΔHUI

e）? Pc←populationt //將此時的鷹群放入存儲池中

f）else if ΔHUI

g）? ?populationt←Pc //用存儲池中的鷹群替換當前種群

h） end if

2.4 算法描述

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

第一個部分是數據初始化部分，包括對數據庫的掃描以及重組數據庫。步驟a）掃描數據庫，計算所有1-項集的twu，若1-項集的twu小于minutil，說明這是沒有希望的項，其超集不可能是HUIs，因此將該項從數據庫中刪除。步驟b）將重組后的數據庫轉換為如圖2所示的位圖形式。

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

第三部分為種群更新部分（步驟g）～t）），對于當前種群中的每一只鷹，利用哈里斯鷹優化算法進行位置更新，形成新的種群。

第四部分是高效用項集的識別部分。步驟u）對更新位置后的鷹計算其適應度函數值，若適應度函數值不小于minutil，說明當前鷹所對應的項集為HUI，則將其放入SHUI集合中。然后更新gbest，算法迭代繼續進行，直到達到最大的迭代次數。最后輸出SHUI中所有的高效用項集以及項集的個數。

算法3 HHUIM

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

輸出：一組高效用項集。

a） 掃描數據庫DB，計算所有1-項集的twu，將所有的1-LTWUI從DB中刪除。

b） 將數據庫轉換為位圖的形式。

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

d） 種群初始化。

e） t=1 to T

f） 對于當前種群中的每一只鷹hawk（i）。

g） 生成一個隨機數r，分別使用式（7）（12）計算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）進行位置的更新。

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

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

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

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

s）? ?end if

t） end if

u） if fitness（hawki）≥minutil

v）? ?SHUI←hawki所對應的項集。

w） end if

x） 更新gbest。

y） 算法循環迭代，直到達到最大的迭代次數。

z） 輸出所有的高效用項集。

2.5 舉例說明

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

首先進行數據的處理。數據集中1-項集有{a}，{b}，{c}，g0gggggg，{e}，{f}，其twu分別為55，101，73，78，46，50，均大于31，因此該窗口內所有的1-項集均為1-HTWUI。與此同時，將數據集轉換為位圖的形式，其中位圖的長度為數據集中1-HTWUI的數量，即為6。

隨后進入利用哈里斯鷹優化挖掘高效用項集階段，其迭代過程如圖6所示。首先初始化種群，即隨機生成3個長度為6的向量，代表種群中3只鷹的位置，分別為Hawk01〈000100〉、Hawk02〈101001〉、Hawk03〈111100〉。接下來以Hawk02為例說明鷹Hawk02如何通過哈里斯鷹優化更新為Hawk12。

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

因為|E|=0.64<1，且r=0.7≤0.5，所以進入軟圍攻階段。根據式（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〉

此時ΔX12=〈-1.64，0，-1.64，0.104，0，-1.64〉是連續變量，需要將其轉換為布爾變量。根據式（23）可得

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

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

3 實驗

本章從HUIs的數量、算法運行時間、內存等方面進行了大量的對比實驗，將HHUIM與目前較為先進的啟發式高效用項集挖掘算法HUIM-BPSO［11］、HUIM-SPSO［25］、Bio-HUIF-PSO［23］、HUIM-AF［13］、Bio-HUIF-BA［23］以及Bio-HUIF-GA［23］進行對比。實驗運行環境為16.0 GB可用RAM，Intel Core-i5-1235U@1.30 GHz CPU以及Windows 11操作系統。其中對比實驗的源碼以及數據集均下載于SPMF平臺。因為智能優化算法具有極強的隨機性，導致結果的偏差很大，本章所有實驗數據均為運行10次取平均得到。實驗所使用的數據集為chess、connect、mushroom、accidents、foodmart以及retail，其參數如表4所示。為了測試所提出策略的有效性，將鷹的替換策略與存儲回溯策略分別加入HHUIM中，命名為HHUIM-R和HHUIM-S，并將其作為對比實驗與HHUIM一起比較。

啟發式HUIM因其迭代次數由用戶指定，具有可隨時獲得結果的優點；此外，種群大小對實驗結果的影響也很大。因此啟發式HUIM大多數比較的是在相同迭代次數和相同種群大小的前提下，算法的運行時間以及能夠挖掘出來HUIs的數量。而傳統確定性算法需等待算法全部運行結束后才可以獲得結果，且挖掘的項集是全部的HUIs，因此確定性算法比較的是時空效率。啟發式HUIM與確定性算法是沒有可比性的，因此本章未將確定性算法作為對比算法。

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

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

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

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

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

4 結束語

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

為了測試本文算法的性能，在真實數據集中進行大量的實驗，結果表明，本文算法優于目前最先進的啟發式高效用項集挖掘算法。同時，鷹的替換策略和存儲回溯策略也能夠有效提高算法所挖掘出來的HUIs的數量，鷹的替換策略在密集數據集中，以及存儲回溯策略在稀疏數據集中均能夠減少內存的使用。

未來，本研究組將繼續開發更加高效的高效用項集挖掘算法，并對鷹的替換策略進行優化。

參考文獻：

[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］.計算機應用研究，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]孫蕊，韓萌，張春硯，等.精簡高效用模式挖掘綜述［J］.計算機應用研究，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]張春硯，韓萌，孫蕊，等.高效用模式挖掘關鍵技術綜述［J］.計算機應用研究，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.