基于馬爾可夫優(yōu)化的高效用項集挖掘算法

鐘新成，劉昶，趙秀梅

基于馬爾可夫優(yōu)化的高效用項集挖掘算法

鐘新成1，2*，劉昶2，趙秀梅1

（1.長治學(xué)院 計算機(jī)系，山西 長治 046000； 2.中國科學(xué)院 沈陽自動化研究所，沈陽 110169）（?通信作者電子郵箱cy12016596@czc.edu.cn）

基于樹型和鏈表結(jié)構(gòu)的高效用項集挖掘（HUIM）算法通常需要指數(shù)量級的搜索空間，而基于進(jìn)化類型的挖掘算法未能充分考慮變量間的相互作用，因此提出一種基于馬爾可夫優(yōu)化的HUIM算法（HUIM-MOA）。首先，采用位圖矩陣表示數(shù)據(jù)庫和使用期望向量編碼，以實現(xiàn)對數(shù)據(jù)庫的快速掃描和效用值的高效計算；其次，通過計算優(yōu)勢個體間的互信息估計馬爾可夫網(wǎng)絡(luò)（MN）結(jié)構(gòu)，并根據(jù)它們的局部特性使用吉布斯采樣以產(chǎn)生新的種群；最后，為防止算法過快陷入局部最優(yōu)和減少高效用項集的缺失，分別采用種群多樣性保持策略和精英策略。在真實數(shù)據(jù)集上的實驗結(jié)果表明，相較于次優(yōu)的基于粒子群優(yōu)化（PSO）的生物啟發(fā)式HUI框架（Bio-HUIF-PSO）算法，在給定較大最小閾值的情況下，HUIM-MOA可以找到全部的高效用項集（HUI），收斂速度平均提升12.5%，挖掘HUI數(shù)平均提高2.85個百分點，運(yùn)行時間平均減少14.6%。HUIM-MOA較進(jìn)化型HUIM算法有更強(qiáng)的搜索性能，能有效減少搜索時間和提高搜索質(zhì)量。

高效用項集挖掘；馬爾可夫網(wǎng)絡(luò)；位圖矩陣；吉布斯采樣；精英策略

0 引言

數(shù)據(jù)挖掘旨在從數(shù)據(jù)庫提取有用的模式或訓(xùn)練模型，以理解過去或預(yù)測未來。頻繁項集挖掘（Frequent Itemset Mining， FIM）是一項被研究廣泛的數(shù)據(jù)挖掘任務(wù)，且應(yīng)用于許多領(lǐng)域。它可以被視為分析數(shù)據(jù)庫的一般任務(wù)，以查找一組事務(wù)數(shù)據(jù)庫中同時出現(xiàn)的項［1］。盡管頻繁模式挖掘有用，但假設(shè)它依賴頻繁模式雖有趣卻并不適用于許多應(yīng)用程序。比如，在事務(wù)數(shù)據(jù)庫中，模式｛牛奶，面包｝可能是頻繁的，但該模式是無趣的，因為該模式在日常生活中常見且不會帶來太多的利潤。另一方面，模式｛茅臺，魚子醬｝可能是非頻繁的，但它有著豐厚的利潤。因此，為了在數(shù)據(jù)庫中找到更多有趣的模式，可以考慮其他方面的因素，如利潤或效用。若項集在數(shù)據(jù)庫中的效用不小于用戶指定的最小效用閾值，則稱該項集為高效用項集（High Utility Itemset， HUI）。高效用項集挖掘（High Utility Itemset Mining， HUIM）在現(xiàn)實生活中應(yīng)用廣泛，如在購物超市中挖掘高利潤商品組合模式、在電商平臺產(chǎn)生的數(shù)據(jù)流中挖掘購物者的高消費模式和在移動通信數(shù)據(jù)中挖掘高消費客戶群體的消費規(guī)律等。

HUIM算法大致可分為精確算法和進(jìn)化算法（Evolutionary Algorithm， EA）兩種類型［2］。前者致力于找到所有的HUI，但同時承受指數(shù)量級的搜索空間，隨著問題規(guī)模增大，此類算法的運(yùn)行時間變得不可接受；后者致力于快速找到大部分的HUI，但不能保證找到所有的HUI。日常生活中，找到所有HUI并非必要，若能在較短的時間內(nèi)找到大部分HUI，對指導(dǎo)商家作出決策也非常有意義。

已有學(xué)者提出了幾種EA實現(xiàn)HUIM。Kannimuthu等［3］等提出一種基于遺傳算法（Genetic Algorithm，GA）的HUIM算法，首次使用EA研究HUIM；但是它沒有考慮HUI是挖掘更多滿足最小效用閾值的項集而非簡單地尋找最優(yōu)的HUI，所以在一些數(shù)據(jù)集上的挖掘效果不理想。Zhang等［4］改進(jìn)了基于GA的高效用算法，提出了基于個體改善、鄰域探索和種群多樣性保持等策略的挖掘算法，實驗結(jié)果表明在這些策略的綜合作用下，在不同數(shù)據(jù)集上的各項指標(biāo)都有較大改善。Lin等［5-6］提出一種基于粒子群優(yōu)化（Particle Swarm Optimization， PSO）的HUIM算法，該算法提出粒子編碼長度由高事務(wù)加權(quán)效用1項集決定，在此種編碼下能有效地縮小搜索空間并提高搜索效率。Song等［7-8］和Wu等［9］提出基于人工魚群［7］、人工蜂群［8］和蟻群［9］的HUIM算法，這些算法都模擬群體智能以進(jìn)化種群，挖掘質(zhì)量各有所長。Pazhaniraja等［10］提出一種基于布爾代數(shù)的灰狼算法挖掘HUI，在運(yùn)行時間、收斂速度和挖掘數(shù)量上都有較好表現(xiàn)。Song等［11］提出了基于生物進(jìn)化啟發(fā)的HUIM框架，包含GA、PSO算法和蝙蝠算法，這些算法采用通用框架，只在具體編碼和操作上略有差異，其中位圖表示、位圖操作和非期望向量剪枝策略都提高了遍歷解空間的速度，并且在各數(shù)據(jù)集上都有良好的表現(xiàn)，基于該框架的算法大幅提高了挖掘效率。然而，基于EA的HUIM算法挖掘所有滿足最小效用閾值的HUI仍然耗時較長：一方面EA通常沿著上一代最優(yōu)值的方向搜索，這可能使某些HUI在迭代過程中被遺漏；另一方面，基于EA的HUIM算法相較于搜索新的HUI通常效率較低。

馬爾可夫優(yōu)化算法（Markovian Optimization Algorithm，MOA）［12］是分布估計算法（Estimation of Distribution Algorithm， EDA）［13］的一個分支。該類算法是一種基于概率論的優(yōu)化算法，主要思想是分析優(yōu)勢群體的分布模型，并用它影響新一代群體的分布，可以更有效地處理非線性、高維復(fù)雜問題［14］。此外，EDA還有其他EA不具備的優(yōu)勢，如自適應(yīng)算子、問題結(jié)構(gòu)和先驗知識的利用等［15］。

目前，較少有學(xué)者將MOA應(yīng)用于HUI的相關(guān)挖掘工作。為提高挖掘效率，本文提出一種基于馬爾可夫優(yōu)化的HUIM算法（HUIM Algorithm based on Markovian Optimization， HUIM-MOA），主要特點有：1）使用位圖表示、位圖操作和非期望編碼檢驗策略加速HUI的挖掘；2）通過計算變量間的互信息估計馬爾可夫網(wǎng)絡(luò)（Markov Network， MN）結(jié)構(gòu)并構(gòu)建各變量的條件概率模型［16-17］；3）通過吉布斯采樣法產(chǎn)生新的個體；4）通過種群多樣性保持策略防止算法陷入局部最優(yōu)，采用精英策略減少HUI的缺失。

1 相關(guān)工作

1.1　HUIM

表1事務(wù)信息

Tab.1　Transaction information

表2外部效用

Tab.2　External utility

其中：（）表示內(nèi)部效用，（）表示外部效用。

例如：（｛，｝，10）=（，10）×（）+（，10）×（）=2×6+4×1=16。

定義2 項集在數(shù)據(jù)庫中的效用記為（），如式（3）所示，式（3）也作為HUIM的目標(biāo)函數(shù)：

例如：（｛，，｝）=（｛，，｝，1）+（｛，，｝，3）=（，1）+（，1）+（，1）+（，3）+（，3）+（，3）=3+18+6+6+1+6=40。

定義4 事務(wù)數(shù)據(jù)庫中項集經(jīng)常出現(xiàn)在多個事務(wù)中，將各事務(wù)效用進(jìn)行累加得到的效用稱為事務(wù)加權(quán)效用，記做（），如式（5）所示：

例如：（｛，｝）=（1）+（3）+（5）+（8）+（10）=27+13+16+55+72=183。

定義5 根據(jù)用戶偏好，將最小效用閾值系數(shù)設(shè)為，如果項集的效用值不小于最小效用值，記為，則稱項集是HUI。定義如式（6）所示：

例如：假設(shè)=25%，則=（27+66+13+11+16+10+101+55+15+72）×25%=386×25%=96.5。由于（｛，｝）=183>96.5，所以｛，｝是HUI；由于（｛，，｝）=60<96.5，所以｛，，｝不是HUI。

定義6 如果項集滿足（）>，則稱為高事務(wù)加權(quán)效用項集，記為HTWUI。包含個項目的HTWUI記為-HTWUI。例如：假設(shè)=115，則高事務(wù)加權(quán)效用1項集（1-HTWUI）的挖掘結(jié)果如表3所示。

表3高事務(wù)加權(quán)效用1項集的挖掘結(jié)果

Tab.3　Mining results for 1-HTWUI

注：NO（）表示非高事務(wù)加權(quán)效用1項集，YES（）表示是高事務(wù)加權(quán)效用1項集，（）里面的數(shù)字是事務(wù)加權(quán)效用值。

事務(wù)加權(quán)效用具有3個重要性質(zhì)，尤其當(dāng)某1項集為低事務(wù)加權(quán)效用項集時，可以對搜索空間進(jìn)行大范圍剪枝，從而縮小搜索空間，這也是基于EA的HUIM算法經(jīng)常采用的一個初始挖掘手段。

性質(zhì)1 對于某項集總有（）>（），表明項集的事務(wù)加權(quán)效用是對本身效用值的向上估計。

性質(zhì)3 若（）<，則項集和它的超集都是低效用項集。

1.2　MOA

MOA是EDA的一個分支。有別于EA利用群體智能引導(dǎo)種群進(jìn)化，EDA通過捕捉變量間的相互依賴關(guān)系構(gòu)建概率模型，從而獲得先驗概率以引導(dǎo)種群進(jìn)化。局部馬爾可夫特性強(qiáng)調(diào)了由MN結(jié)構(gòu)編碼的條件概率可以直接用于采樣，而不需要建立復(fù)雜的聯(lián)合概率分布模型。此外，MOA采用吉布斯抽樣法進(jìn)行采樣并包含了溫度參數(shù)，該參數(shù)可以平衡對搜索空間的探索和利用，并允許算法處理由循環(huán)表示的相互作用。局部馬爾可夫特性被定義為變量之間的鄰域關(guān)系，如式（7）所示：

其中N是節(jié)點x的相鄰節(jié)點集。式（7）表明節(jié)點x的條件概率可以由它的鄰域節(jié)點集N定義，N有時也被稱為馬爾可夫毯?；隈R爾可夫特性的EDA工作流程如下所示：

步驟1 隨機(jī)生成含個解的總體。

步驟3 用中數(shù)據(jù)估計MN結(jié)構(gòu)。

步驟5 用新的種群替代舊種群，然后返回步驟2，直到滿足終止條件。

從上述流程可以看出，MOA的關(guān)鍵步驟為確定MN結(jié)構(gòu)和根據(jù)局部馬爾可夫條件概率進(jìn)行采樣。通?？捎貌煌椒ù_定一個無向圖結(jié)構(gòu)，MOA采樣一種基于熵的互信息方法確定MN結(jié)構(gòu)，即估計解中每對變量的互信息以創(chuàng)建一個互信息矩陣。若每對變量間的互信息高于某一設(shè)定的閾值，則它們可成為相鄰節(jié)點；另外，為了防止網(wǎng)絡(luò)結(jié)構(gòu)過于復(fù)雜，任一節(jié)點的相鄰節(jié)點數(shù)應(yīng)設(shè)置一個上限。兩個變量和之間的互信息由式（8）給出：

估計網(wǎng)絡(luò)結(jié)構(gòu)后，再估計每一節(jié)點的條件概率，最后根據(jù)條件概率采樣新的種群。吉布斯抽樣法是MOA中的一類蒙特卡洛采樣方法，它始于一個隨機(jī)解和一個固定的迭代次數(shù)，然后隨機(jī)選擇解中的某一變量并計算它在MN結(jié)構(gòu)下的條件概率以得到該變量的某一新的取值，接著用輪盤賭的方法采樣其他變量的新值，當(dāng)達(dá)到迭代次數(shù)時，輸出新解。在吉布斯抽樣法中，條件概率一般估計為：

假設(shè)變量是二值變量，一般只需計算變量取值為1的概率，因為取0的概率可以根據(jù)互斥性給出，式（9）可寫為：

為了實現(xiàn)MOA中基于溫度的吉布斯抽樣法，式（9）的條件概率可估計為：

對于二值變量，則x取1的條件概率可由它的相鄰節(jié)點估計為：

2 本文算法

本文提出的HUIM-MOA依賴于位圖數(shù)據(jù)庫表達(dá)并涉及以下幾個主要步驟：種群初始化、選擇優(yōu)勢個體、構(gòu)建概率模型、吉布斯采樣、種群多樣性保持策略和精英策略。本章首先介紹兩個重要的準(zhǔn)備工作：位圖表示和期望向量編碼。

2.1　位圖表示和期望向量編碼

表4展示了表1對應(yīng)數(shù)據(jù)庫的位圖表示。

表4對應(yīng)事務(wù)信息的位圖表示

Tab.4　Bitmap representation of corresponding transaction information

定義7 若項集編碼向量的位圖覆蓋全為0，則稱該向量為非期望編碼向量（UnPromising Encoding Vector， UPEV），反之則稱為期望編碼向量（Promising Encoding Vector， PEV）。UPEV表示該編碼向量對應(yīng)的項集在數(shù)據(jù)庫中不存在，不可能成為HUI，刪除UPEV的過程稱為非期望編碼向量修剪策略（UPEV Cut strategy， UPEVC）。UPEVC的偽代碼如算法1所示。

算法1 PEV_Check（）。

輸入 編碼向量；

輸出 期望編碼向量。

1）計算中1的位數(shù)

3）=（1）

4） for=2 todo

8） 改變中的一位i狀態(tài)

9） end if

11） end for

12） return

HUIM-MOA中使用了兩種策略修剪搜索空間：其一是使用事務(wù)加權(quán)向下閉包屬性刪除低效用項集以有效減小搜索空間和提高計算速度［11］；其二是使用UPEV修剪事務(wù)數(shù)據(jù)庫中不存在的項集。在上述兩種策略下，MOA編碼的長度完全由1-HTWUI決定。例如，假設(shè)=115，則1-HTWUI有｛，，，，｝，相應(yīng)編碼長度為5。每個編碼位置對應(yīng)一個項，編碼為1表示該項出現(xiàn)在該位置；編碼為0則表示不出現(xiàn)。圖1表示項集｛，｝是一個潛在的解。

圖1　編碼示例

在種群初始化階段，每個個體根據(jù)1-HTWUI的TWU初始化，若某1-HTWUI的TWU較高，則它被選中的概率相應(yīng)也更高。算法2展示了這個初始化過程。在算法2中，每個個體各編碼位置初始被指派為0，接著根據(jù)每個1-HTWUI的TWU的大小采用輪盤賭的形式確定該位置1出現(xiàn)的概率。每個位置取1的概率由式（14）決定：

若一個個體生成完畢，則加入種群，如此反復(fù)，最后返回初始種群。

算法2 Pop_Init（）。

輸入 數(shù)據(jù)集，種群規(guī)模；

輸出 第一代種群。

1）遍歷數(shù)據(jù)集，并刪除1?LTWUI

2）將數(shù)據(jù)集表示為bitmap

3） for=1 todo

4） 產(chǎn)生隨機(jī)數(shù)num

5） 運(yùn)用輪盤賭方式產(chǎn)生一個位向量

6） ifnum>1 then

7）=PEV_Check（）

8） 改變中的一位i狀態(tài)

9） end if

10） end for

2.2　構(gòu)建概率模型

種群初始化后計算相應(yīng)項集的效用值，若高于設(shè)定閾值，則加入HUI，并對該種群按照效用值從高到低進(jìn)行排序，按設(shè)定比例截取前面的優(yōu)良個體組成新的數(shù)據(jù)集。接著使用數(shù)據(jù)集估計MN結(jié)構(gòu)。構(gòu)建概率模型的偽代碼如算法3所示。

算法3 Pro_Model（）。

輸入 優(yōu)勢個體組成的種群，重要系數(shù)，最大相鄰節(jié)點數(shù)；

輸出 MN結(jié)構(gòu)。

1）=len（［0］）

2）0

3） for=1 to，=+1 todo

4） 用式（8）估計變量x和x的互信息m

5） end for

6）計算平均互信息

7） for=1 to，=+1 todo

8） ifm>then

9） 在變量x和x間創(chuàng)建一條邊

10） end if

11） end for

12） for=1 todo

13） if NB>then

14） 保留x的互信息排名前個相鄰節(jié)點

15） end if

16） end for

2.3　吉布斯采樣

算法4 Gibbs_sample（）。

輸入 MN結(jié)構(gòu)，種群規(guī)模，冷卻系數(shù)，迭代系數(shù)；

輸出 新一代種群。

2）=1

4） 隨機(jī)產(chǎn)生一個解=（1，2，…，x）

6） 從中隨機(jī)選擇一個x

7） 以概率P（1|NB）置x為1；←用式（12）

8） end for

9）=PEV_Check（）

11） end while

12） return

2.4　精英策略和種群多樣性保持策略

2.5　HUIM-MOA算法總體設(shè)計及實例演示

HUIM-MOA的偽代碼如算法5所示。步驟1）～4）是算法的初始化，5）～21）是整個算法的迭代過程，其中6）～12）是篩選HUI的過程，13）是按效用值由高到低進(jìn)行排序，14）是按設(shè)定比例選擇優(yōu)勢個體，15）是構(gòu)建概率模型，16）是執(zhí)行吉布斯采樣，17）～18）是執(zhí)行精英策略和種群多樣性保持策略。

算法5 HUIM-MOA。

輸入 事務(wù)數(shù)據(jù)集，最小效用閾值；

輸出 所有的高效用項集。

1） Pop_Init（）

2）=1

5） while≤_do

6） for each individualdo

7） 確定與位圖向量對應(yīng)的項集

11） end if

12） end for

13）按的第一元素進(jìn)行排序

14）按比例截取的第二元素組成新種群

15） Pro_Model（）

16） Gibbs_Sample（）

17）執(zhí)行精英策略

18）執(zhí)行多樣性保持策略

19）++

20） end while

21） return

根據(jù)前述數(shù)據(jù)庫、效用表和位圖舉例。假設(shè)=115，被挖掘的1-HTWUI如表3所示，則個體編碼長度為5，表5展示了種群初始化所得的10個個體，經(jīng)過HUI篩選后，將項集：166，：216，：131分別加入高效用項集。接著按效用值排序并按1∶2選取優(yōu)勢個體，得到新的位圖如表6所示。

表5初始種群

Tab.5　Initial population

表6截斷后優(yōu)勢個體組成的種群

Tab.6　Population composed of dominant individuals after truncation

首先，計算各變量兩兩間的互信息。設(shè)定=1.2，經(jīng)計算平均互信息為0.117 8，其中有、、、、間互信息大于平均互信息，分別為0.5、0.118 5、0.118 5、0.118 5、0.118 5，故這些變量之間可以分別連一邊，于是可以估計MN結(jié)構(gòu)如圖2所示。

圖2　MN結(jié)構(gòu)

其次進(jìn)行吉布斯采樣。該采樣從一個隨機(jī)解=（1，0，1，0，1）開始，隨機(jī)選定一維變量4==0；接著用變量的條件概率采樣新的，此時的鄰邊集為｛｝，且此時=1。設(shè)定=4，于是在=1的情況下取1的概率計算為：

由式（15）計算結(jié)果可知，此時以0.524 8的概率取1。令的新值為1，新的個體變?yōu)?（1，0，1，1，1），再隨機(jī)取一維變量2==0，的鄰邊集為｛，｝，且此時=1，=1。于是在此情況下取1的概率可計算為：

令的新值取0，新的個體變量為=（1，0，1，1，1），依此繼續(xù)采樣，直到迭代完畢獲得一個新個體。假設(shè)最終新個體是=（1，0，1，1，1），經(jīng)PEVC檢測后存在，則不用修改；若不存在，則作相應(yīng)修改。如此下去，便得到了新的種群。

最后，執(zhí)行精英策略和種群多樣性保持策略，這里不再贅述。

3 實驗與結(jié)果分析

將HUIM-MOA和目前最先進(jìn)的基于EA的HUIM算法進(jìn)行實驗對比以綜合評估算法性能。這些算法包括基于PSO的生物啟發(fā)式HUI框架（Bio-inspired HUI Framework based on PSO，Bio-HUIF-PSO）、基于GA的生物啟發(fā)式HUI框架（Bio-inspired HUI Framework based on GA，Bio-HUIF-GA）、基于或/非樹結(jié)構(gòu)PSO的HUIM算法（HUIM algorithm based on PSO with a OR/NOR tree structure，HUIM-PSO_tree）、基于人工魚群的HUIM算法（HUIM algorithm based on Artificial Fish swarm， HUIM-AF）。性能指標(biāo)包括收斂速度、挖掘的HUI數(shù)、挖掘全部或不同比例HUI所需要的運(yùn)行時間。

3.1　實驗環(huán)境和數(shù)據(jù)集

實驗所用電腦配置如下：Intel Core i5-6402P CPU 2.8 GHz，16 GB內(nèi)存，64位Windows 7操作系統(tǒng)，編程語言為Java。用Mushroom、Connect、Foodmart和Chainstore這4個數(shù)據(jù)集進(jìn)行實驗對比，4個數(shù)據(jù)集均來自開源社區(qū)SPMF［18］。Foodmart數(shù)據(jù)集包含了消費者在商店的購物記錄；Connect數(shù)據(jù)集記錄了游戲步數(shù)；Chainstore數(shù)據(jù)集記錄了美國加州一家大型連鎖雜貨店的客戶交易數(shù)據(jù)；Mushroom數(shù)據(jù)集包含了各類蘑菇及其相應(yīng)特征，如氣味、形狀等。各數(shù)據(jù)集詳情如表7所示。

表7數(shù)據(jù)集詳情

Tab.7　Details of datasets

對于Chainstore數(shù)據(jù)集上的對比實驗，最大迭代次數(shù)設(shè)置為2 000；其他數(shù)據(jù)集上的對比實驗，最大迭代次數(shù)設(shè)置為1 200，種群規(guī)模統(tǒng)一設(shè)置為40。Chainstore數(shù)據(jù)集上的迭代次數(shù)設(shè)置更大的原因是它為大型稀松數(shù)據(jù)集，在給定最小閾值下找到全部或絕大多數(shù)HUI需要更多的迭代次數(shù)。HUIM-MOA的相關(guān)參數(shù)設(shè)置如下：平均互信息重要系數(shù)設(shè)為1.5，溫度冷卻速率系數(shù)設(shè)為4，種群截斷比例設(shè)置為1∶2。

3.2　收斂性對比

用每個算法在10次獨立運(yùn)行后獲得的平均結(jié)果比較收斂性能。5個算法在各數(shù)據(jù)集相應(yīng)閾值上的收斂效果如圖3所示。從圖3可見，HUIM-MOA在各數(shù)據(jù)集上都達(dá)到最高的收斂速度，Bio-HUIF-PSO次之。HUIM-MOA的收斂速度較Bio-HUIF-PSO平均提升了12.5%，主要原因是采用的種群多樣性保持策略能有效防止算法陷入局部最優(yōu)；此外，吉布斯采樣溫度系數(shù)的合理設(shè)置也能讓算法在探索和開發(fā)中取得平衡，因此，HUIM-MOA算法始終保持探索新的HUI的能力。由于HUIM-PSO_tree、HUIM-AF在數(shù)據(jù)集Chainstore上的運(yùn)行時間超過3 h，對比它們的收斂性已無意義，故圖3（d）中沒有它們的收斂曲線。

圖3　各算法在給定閾值下的收斂情況

3.3　運(yùn)行時間

圖4展示了5個算法在各數(shù)據(jù)集不同閾值下的運(yùn)行時間?？梢钥闯?，HUIM-MOA在4個數(shù)據(jù)集上的運(yùn)行時間都是最少的，Bio-HUIF-PSO的運(yùn)行時間次之。HUIM-MOA在各數(shù)據(jù)集上的運(yùn)行時間較Bio-HUIF-PSO平均減少了14.6%。HUIM-PSO_tree、HUIM-AF整體運(yùn)行時間都較長，在Chainstore這樣的大型稀松數(shù)據(jù)集上運(yùn)行時間超過3 h；HUIM-PSO_tree雖然采用OR/NOR tree的結(jié)構(gòu)避免了不必要項集的產(chǎn)生，但相較于位圖表示和期望向量編碼依然更費時。

3.4　挖掘到的HUI數(shù)

在稠密數(shù)據(jù)集上閾值一般設(shè)置得較高，而在稀松數(shù)據(jù)集上閾值一般設(shè)置得較低，這是由于在稠密數(shù)據(jù)集上若設(shè)置較低閾值，則滿足要求的HUI會大幅增加，在設(shè)定的迭代過程中難以找到絕大多數(shù)的HUI；若在稀松數(shù)據(jù)集上設(shè)置較高閾值，則可能導(dǎo)致沒有滿足要求的HUI，如在稀松數(shù)據(jù)集Foodmart上，當(dāng)閾值設(shè)定為0.22%時，則沒有滿足要求的HUI。表8展示了5個算法在各數(shù)據(jù)集不同閾值下挖掘的HUI數(shù)的百分比。

圖4　各算法在給定閾值下的運(yùn)行時間

表8對比算法在各數(shù)據(jù)集不同閾值下挖掘的HUIs的百分比 單位：%

Tab.8　Percentage of HUIs mined by comparative algorithms with different thresholds for each dataset unit：%

可以看出，當(dāng)給定閾值較大時，HUIM-MOA可以挖掘所有的HUI，相較于次優(yōu)的Bio-HUIF-PSO，它挖掘的HUI平均數(shù)的百分比在4個數(shù)據(jù)集上提高了2.85個百分點。這是由于HUIM-MOA采樣了MN結(jié)構(gòu)的局部特性，它充分利用變量間的依賴關(guān)系，從而能找到更多的HUI；此外，種群多樣性保持策略和精英策略也能在一定程度上防止算法陷入局部最優(yōu)，實現(xiàn)更廣泛的搜索，使得算法在后期也能持續(xù)搜索新的HUI。值得注意地，在稀松數(shù)據(jù)集Foodmart上，當(dāng)閾值設(shè)定為0.06%時，兩個基于BIO-HUIF框架的算法都只能找到近一半的HUI，HUIM-PSO_tree、HUIM-AF表現(xiàn)則更差，而HUIM-MOA能找到93.84%的HUI，這也充分體現(xiàn)了HUIM-MOA處理高維稀松數(shù)據(jù)集的優(yōu)越性。在大型稀松數(shù)據(jù)集Chainstore上，各算法能找到的HUI的比例都大幅降低，這表明進(jìn)化型算法處理大型稀松數(shù)據(jù)集存在一定的劣勢。由于HUIM-PSO_tree、HUIM-AF的運(yùn)行時間超過3 h，對比它們的挖掘數(shù)已無意義，故表8中未顯示它們的挖掘百分比。

4 結(jié)語

本文算法（HUIM-MOA）通過分析優(yōu)勢個體間的互信息估計MN結(jié)構(gòu)，并用MN的局部特性估計每個變量的條件概率，使得MOA相較于基于全局特性的算法更易實現(xiàn)；接著使用帶溫度下降的吉布斯采樣法生成新的種群；為提高算法的運(yùn)行效率，采用了位圖表示法和期望向量編碼；為使種群不過快陷入局部最優(yōu)和減少HUI的缺失，分別采用了種群多樣性保持策略和精英策略，加強(qiáng)HUIM-MOA的搜索能力；同時，互信息重要系數(shù)和溫度冷卻系數(shù)的恰當(dāng)設(shè)定也使算法在開發(fā)和探索上達(dá)到一個平衡。從4個真實數(shù)據(jù)集上的實驗結(jié)果可以看出，無論是在稠密集還是稀松集上，HUIM-MOA在收斂速度上比其他4個算法更高、運(yùn)行時間更少，挖掘HUI數(shù)也最多。

未來將進(jìn)一步優(yōu)化基于MN的概率建模和采樣過程，使算法的運(yùn)行時間更少，同時還將嘗試用其他類型的EDA與EA進(jìn)行結(jié)合的方法挖掘HUI。當(dāng)然，其他更合理更有效的剪枝策略、搜索策略也是下一步要重點研究的問題。

[1] CHEE C-H， JAAFAR J， AZIZ I A， et al. Algorithms for frequent itemset mining： a literature review［J］. Artificial Intelligence Review， 2019， 52： 2603-2621.

[2] FOURNIER-VIGER P， LIN J C-W， TRUONG-CHI T， et al. A survey of high utility itemset mining［M］// High Utility Pattern Mining. Cham： Springer， 2019： 1-45.

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

[4] ZHANG Q， FANG W， SUN J， et al. Improved genetic algorithm for high-utility itemset mining ［J］. IEEE Access， 2019， 7： 176799-176813.

[5] LIN J C-W， YANG L， FOURNIER-VIGER P， et al. Mining high-utility itemsets based on particle swarm optimization［J］. Engineering Applications of Artificial Intelligence， 2016， 55： 320-330.

[6] LIN J C-W， YANG L， FOURNIER-VIGER P， et al. A binary PSO approach to mine high-utility itemsets ［J］. Soft Computing， 2017， 21： 5103-5121.

[7] SONG W， LI J， HUANG C. Artificial fish swarm algorithm for mining high utility itemsets ［C］// Proceedings of the 12th International Conference on Swarm Intelligence. Cham： Springer， 2021： 407-419.

[8] SONG W， HUANG C. Discovering high utility itemsets based on the artificial bee colony algorithm ［C］// Proceedings of the 2018 Pacific-Asia Conference on Knowledge Discovery and Data Mining. Cham： Springer， 2018： 3-14.

[9] WU J M-T， ZHAN J， LIN J-W. Mining of high-utility itemsets by ACO algorithm ［C］// Proceedings of the 3rd Multidisciplinary International Social Networks Conference on SocialInformatics 2016， Data Science 2016. Cham： Springer， 2016： Article No. 44.

[10] PAZHANIRAJA N， SOUNTHARRAJAN S， KUMAR B S. High utility itemset mining： a Boolean operators-based modified grey wolf optimization algorithm ［J］. Soft Computing， 2020， 24（21）： 16691-16704.

[11] SONG W， HUANG C. Mining high utility itemsets using bio-inspired algorithms： a diverse optimal value framework［J］. IEEE Access， 2018， 6： 19568-19582.

[12] SHAKYA S， SANTANA R. MOA-Markovian optimisation algorithm［M］// Markov Networks in Evolutionary Computation. Berlin： Springer， 2012： 39-53.

[13] 王圣堯，王凌，方晨，等. 分布估計算法研究進(jìn)展［J］. 控制與決策， 2012， 27（7）： 961-966，974.（WANG S Y， WANG L， FANG C， et al. Advances in estimation of distribution algorithms ［J］. Control and Decision， 2012， 27（7）： 961-966，974.）

[14] SEBAG M， DUCOULOMBIER A. Extending population-based incremental learning to continuous search spaces ［C］// Proceedings of the 1998 International Conference on Parallel Problem Solving from Nature. Cham： Springer， 1998： 418-427.

[15] LARRA?AGA P， ETXEBERRIA R， LOZANO J A， et al. Optimization in continuous domains by learning and simulation of Gaussian networks ［C］// Proceedings of the 2th Genetic and Evolutionary Computation Conference. San Mateo：Morgan Kaufmann， 2000：201-204.

[16] SANTANA R. A Markov network based factorized distribution algorithm for optimization ［C］// Proceedings of the 2003 European Conference on Machine Learning. Cham： Springer， 2003： 337-348.

[17] SHAKYA S， McCALL J. Optimization by estimation of distribution with DEUM framework based on Markov random fields［J］. International Journal of Automation and Computing， 2007， 4： 262-272.

[18] FOURNIER-VIGER P， LIN J C-W， GOMARIZ A， et al. The SPMF open-source data mining library version 2 ［C］// Proceedings of the 2016 Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham： Springer， 2016：36-40.

High utility itemset mining algorithm based on Markov optimization

ZHONG Xincheng1，2*， LIU Chang2， ZHAO Xiumei1

（1，，046000，；2，，110169，）

To address the problems that the High Utility Itemset Mining （HUIM） algorithms based on tree and link table structures often consume search spaces of orders of magnitude， and the evolutionary type-based mining algorithms fail to fully consider the interactions between variables， an HUIM algorithm based on Markov Optimization （HUIM-MOA） was proposed. Firstly， a bitmap matrix for expressing database and expectation vector encoding were used to achieve fast scanning of the database and efficient computation of utility values， respectively. Then， the Markov Network （MN） structure was estimated by computing the mutual information among dominant individuals and new populations were generated by using Gibbs sampling according to their local characteristics. Finally， population diversity preservation strategy and elite strategy were used to prevent the algorithm from falling into local optimum too quickly and to reduce the missing of high utility itemsets， respectively. Experimental results on real datasets show that compared with Bio-inspired High Utility Itemset Framework based on Particle Swarm Optimization （Bio-HUIF-PSO）algorithm， HUIM-MOA can find all the High Utility Itemsets （HUIs） when given a larger minimum threshold， with on average 12.5% improvement in convergence speed， 2.85 percentage point improvement in mined HUI number， and 14.6% reduction in running time. It can be seen that HUIM-MOA has stronger search performance than the evolutionary HUIM algorithm， which can effectively reduce the search time and improve the search quality.

High Utility Itemset Mining (HUIM); Markov network; bitmap matrix; Gibbs sampling; elite strategy

This work is partially supported by Science and Technology Innovation Project of Colleges and Universities in Shanxi Province in 2022 （2022L517）.

ZHONG Xincheng， born in 1987， M. S.， lecturer. His research interests include data mining， reinforcement learning.

LIU Chang， born in 1973， Ph. D.， associate research fellow. Her research interests include data mining， schedule optimization.

ZHAO Xiumei， born in 1970， M. S.， lecturer. Her research interests include software testing.

TP301.6

A

1001-9081（2023）12-3764-08

10.11772/j.issn.1001-9081.2022121844

2022?12?09；

2023?02?28；

2023?03?03。

2022年度山西省高等學(xué)校科技創(chuàng)新項目（2022L517）。

鐘新成（1987—），男，湖南長沙人，講師，碩士，主要研究方向：數(shù)據(jù)挖掘、強(qiáng)化學(xué)習(xí)；劉昶（1973—），女，遼寧沈陽人，副研究員，博士，主要研究方向：數(shù)據(jù)挖掘、調(diào)度優(yōu)化；趙秀梅（1970—），女，山西高平人，講師，碩士，主要研究方向：軟件測試。