基于長度約束的蝙蝠高效用項(xiàng)集挖掘算法

袁 泉，唐成亮*，徐雲(yún)鵬

（1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065）

0 引言

高效用項(xiàng)集挖掘（High Utility Itemset Mining，HUIM）是頻繁項(xiàng)集［1］問題的推廣，主要目標(biāo)是從事物數(shù)據(jù)庫中挖掘出具有高效用（如高利潤）的項(xiàng)集。不同于頻繁項(xiàng)集挖掘，HUIM 綜合考慮了項(xiàng)目出現(xiàn)的次數(shù)和用戶對(duì)于項(xiàng)目的偏好，因此具有更廣泛的應(yīng)用，如零售業(yè)的交叉營銷［2］、網(wǎng)絡(luò)點(diǎn)擊流分析［3］、生物醫(yī)學(xué)應(yīng)用［4］以及物聯(lián)網(wǎng)應(yīng)用［5］等。

高效用項(xiàng)集（High Utility Itemset，HUI）一般由多個(gè)不同的項(xiàng)目組成，因?yàn)榘鄠€(gè)項(xiàng)目的項(xiàng)集更有可能是高效用項(xiàng)集。然而在實(shí)際生活中，包含較多項(xiàng)目的項(xiàng)集通常表示更具體的情況，可能很少見，有時(shí)不如包含較少項(xiàng)目的項(xiàng)集有用。例如，一個(gè)零售商店長在交易數(shù)據(jù)庫中發(fā)現(xiàn)了2 個(gè)高效用項(xiàng)集｛意大利面，雞蛋｝和｛橙子，奶酪，可樂，意大利面，雞蛋｝。如果店長想增加商店的整體利潤，促銷推廣第一套商品比第二套更有效。因?yàn)榍罢咧话瑑煞N商品，在生活中很常見，購買的客戶相對(duì)較多；而第二套包含五種商品，在生活中較少見，客戶購買相對(duì)較少。此外，傳統(tǒng)的HUIM 算法會(huì)返回大量的高效用項(xiàng)集，這可能會(huì)耗盡存儲(chǔ)空間，而且對(duì)用戶而言分析大量的結(jié)果集也非常耗時(shí)。因此，為了給用戶提供更有用的HUI，同時(shí)過濾掉不太有用的項(xiàng)集，在HUIM 中有必要考慮項(xiàng)集長度的影響。

為了挖掘具有長度約束的HUI，一種簡單的方法是挖掘出所有的高效用項(xiàng)集之后再篩選出符合長度需求的項(xiàng)集，但這種方法效率很低，因?yàn)闆]有利用長度約束來縮減搜索空間，且篩選也會(huì)帶來額外的時(shí)間開銷。文獻(xiàn)［6］中提出了MinFHM（Minimal Faster High-utility itemset Mining）算法挖掘最小HUI（各項(xiàng)集不被包含在另外的HUI 中），有效減少了返回結(jié)果集的數(shù)量。文獻(xiàn)［7］中對(duì)FHM（Fast High utility Miner）［8］算法進(jìn)行改進(jìn)，引入了長度約束（Length Constraint）和兩個(gè)關(guān)于長度約束的新上界，提出了FHM+（Faster Highutility itemset Mining plus）算法，該算法可以通過定義不同的長度約束范圍來挖掘具有長度約束的HUI。實(shí)驗(yàn)表明，在時(shí)間和內(nèi)存都充足的條件下，這些算法可以精確找到數(shù)據(jù)庫中所有的HUI。然而，由于傳統(tǒng)的算法遞歸地將項(xiàng)附加到項(xiàng)集中，當(dāng)數(shù)據(jù)集較大或項(xiàng)目數(shù)量較多時(shí)，傳統(tǒng)算法將面臨呈指數(shù)增長的搜索空間，算法挖掘效率變得很低。為探索HUI 巨大的搜索空間，眾多學(xué)者提出采用演化算法來挖掘HUI。如文獻(xiàn)［9］中首次將遺傳算法（Genetic Algorithm，GA）應(yīng)用于HUIM，提出了HUP-GA（High-Utility Pattern extraction using Genetic Algorithm，HUP-GA），該算法利用染色體選擇、交叉、突變的特性尋找HUI；文獻(xiàn)［10］中提出了粒子群優(yōu)化（Particle Swarm Optimization，PSO）和OR/NOR 樹相結(jié)合的

HUIM-BPSO（High-Utility Itemset Mining-Binary Particle Swarm Optimization，HUIM-BPSO）算法，所提出的樹結(jié)構(gòu)可以有效降低無效用項(xiàng)集效用的計(jì)算；文獻(xiàn)［11］中對(duì)HUIM-BPSO 算法進(jìn)行改進(jìn)，提出了HUIM-IPSO（High Utility Itemset Mining-Improved PSO，HUIM-IPSO）算法，該算法通過輪盤賭選擇法在當(dāng)前代種群的HUI 中以一定概率選擇下一代種群的初始優(yōu)化值，提高了種群的多樣性；文獻(xiàn)［12］中采用位圖矩陣來表示事務(wù)數(shù)據(jù)庫并結(jié)合人工蜂群算法（Artificial Bee Algorithm，ABC）提出了HUIM-ABC（High-Utility Itemset Mining-Artificial Bee Algorithm，HUIM-ABC）。實(shí)驗(yàn)結(jié)果表明，位圖矩陣能有效加快數(shù)據(jù)庫的掃描和項(xiàng)集效用的計(jì)算；文獻(xiàn)［13］中基于人工魚群（Artificial Fish，AF）提出了HUIMAF（High-Utility Itemset Mining-Artificial Fish，HUIM-AF）算法；文獻(xiàn)［14］中提出了一個(gè)基于生物啟發(fā)式挖掘HUI 的框架（Biology inspired-High Utility Itemset Framework，Bio-HUIF），該框架對(duì)GA、PSO 和蝙蝠算法（Bat Algorithm，BA）進(jìn)行改進(jìn)與優(yōu)化，提出了Bio-HUIF-GA、Bio-HUIF-PSO 和Bio-HUIFBA，其中Bio-HUIF-BA 相較于另外兩個(gè)改進(jìn)算法在迭代尋優(yōu)方面具有很大優(yōu)勢(shì)，需要調(diào)整的參數(shù)較少，且實(shí)驗(yàn)結(jié)果表明它在收斂性、運(yùn)行時(shí)間、占用內(nèi)存方面都優(yōu)于另外兩種算法。目前，演化算法在HUIM 方面取得了不錯(cuò)的進(jìn)展，但都未考慮項(xiàng)集長度的影響。因此本文選擇目前較優(yōu)的GA 結(jié)合長度約束，提出一種基于長度約束的蝙蝠高效用項(xiàng)集挖掘算法（Bat Algorithm for High Utility Itemset Mining based on Length Constraint，HUIM-LC-BA），以挖掘具有長度約束的HUI。本文主要工作如下：

1）HUIM-LC-BA 將數(shù)據(jù)庫轉(zhuǎn)為位圖矩陣以加快效用計(jì)算和數(shù)據(jù)庫的掃描，并使用重新定義的事務(wù)加權(quán)效用（Redefined Transaction Weighted Utility，RTWU）策略縮減搜索空間，提升HUIM-LC-BA 的效率。

2）提出長度修剪策略，使用輪盤賭注選擇法確定修剪的項(xiàng)目，并使用深度優(yōu)先搜索將項(xiàng)集的長度修剪至用戶定義的范圍。該策略可以很容易集成其他生物啟發(fā)式算法，具有良好的可擴(kuò)展性。

3）在4 個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，HUIM-LC-BA能有效挖掘具有長度約束的HUI，大幅減少了模式的數(shù)量和運(yùn)行時(shí)間。

1 基本概念

1.1 高效用項(xiàng)集

令I(lǐng)={i1，i2，…，iN}是N個(gè)不同項(xiàng)目的集合，其中每個(gè)項(xiàng)目ik∈I(1 ≤k≤N)對(duì)應(yīng)一個(gè)正數(shù)p(ik)，表示該項(xiàng)目的權(quán)重（如單位利潤）。事務(wù)數(shù)據(jù)庫D={T1，T2，…，TM}由M條不同事務(wù)構(gòu)成，其中每個(gè)事務(wù)Tc(1 ≤c≤M) 都是I的子集（即Tc?I），同時(shí)有一個(gè)唯一的Tid來記錄每個(gè)不同的事務(wù)。事務(wù)Tc中每一個(gè)項(xiàng)目ik都有一個(gè)對(duì)應(yīng)的正數(shù)q(i，Tc)，稱為內(nèi)部效用（如購買數(shù)量）。例如表1 共包含5 個(gè)事務(wù)，每個(gè)事物中記錄了不同的項(xiàng)目以及項(xiàng)目出現(xiàn)的次數(shù)，表2 的外部效用表記錄了每個(gè)項(xiàng)目對(duì)應(yīng)的外部效用。

表1 事務(wù)表Tab.1 Transaction table

表2 外部效用Tab.2 External utility

定義1項(xiàng)在事物中的效用［2］。項(xiàng)目ik在事務(wù)Tc中的效用記作u(ik，Tc)，定義為：

定義2項(xiàng)在事物中的效用［2］。項(xiàng)集X在事務(wù)Tc中的效用記作u(X，Tc)，定義為：

定義3項(xiàng)集在數(shù)據(jù)庫中的效用［2］。項(xiàng)集X在數(shù)據(jù)庫D中的效用記作u（X），定義為：

定義4事物效用（Transaction Utility，TU）［2］。事務(wù)Tc的效用記作TU（Tc），定義為：

定義5事物加權(quán)效用（Transaction Weighted Utility，TWU）［2］。項(xiàng)集X在數(shù)據(jù) 庫D中的事務(wù)加權(quán)效用記作TWU(X)，定義為：

定義6高效用項(xiàng)集［2］。用戶定義最小效用閾值min_util，如果項(xiàng)集X的效用值u(X) ≥min_util，則項(xiàng)集X是高效用項(xiàng)集，反之為低效用項(xiàng)集。

1.2 項(xiàng)集長度屬性和定義

定義7lc-HUI（length contrained-HUI）［7］。用戶定義項(xiàng)集的最小長度為lmin、最大長度為lmax。如果項(xiàng)集X是高效用項(xiàng)集，且包含的項(xiàng)目數(shù)量在[lmin，lmax]，則稱項(xiàng)集X為lc-HUI。

嚴(yán)格的上界對(duì)于高效地修剪搜索空間至關(guān)重要，為了進(jìn)一步使用TWU 屬性修剪具有長度約束高效用項(xiàng)集的搜索空間，F(xiàn)HM+算法重新定義了相關(guān)概念。

定義8事物的最大效用［7］。設(shè)事務(wù)Tc={}i1，i2，…，ik，用戶定義最大長度為lmax。事物Tc中的最大效用為集合{u(i1，Tc)，u(i2，Tc)，…，u(ik，Tc) }中最大長度值的集合，記為L(Tc)。

定義9重新定義的事物效用（Redefined Transaction Utility，RTU）［7］。設(shè)事務(wù)Tc={}i1，i2，…，ik，重新定義的事務(wù)效用表示事物Tc在最大長度約束條件下?lián)碛械淖畲笮в?，記作RTU(Tc)，定義為：

例如，令lmax=2，則事物T2重新定義的事物效用RTU(T2)=u(b，T2) +u(d，T2)=14。通過計(jì)算不超過lmax項(xiàng)的最大效用之和來減少事物效用。表3 列出了每條事物的TU 和RTU。

表3 事物效用以及重新定義的事物效用Tab.3 Transaction utility and redefined transaction utility

定義10重新定義的事務(wù)加權(quán)效用（RTWU）［7］。項(xiàng)集X重新定義的事物加權(quán)效用記作RTWU(X)，定義為

定義11如果項(xiàng)集X滿足RTWU(X) ≥min_util，則稱X為高重新定義的事務(wù)加權(quán)效用項(xiàng)集，記為HRTWUI（High Redefined Transaction Weighted Utility Itemset）；反之，則稱X為低重新定義的事務(wù)加權(quán)效用項(xiàng)集LRTWUI（Low Redefined Transaction Weighted Utility Itemset）。

定義12包含k個(gè)項(xiàng)目的HRTWUI 和LRTWUI 分別記為k-HRTWUI 和k-LRTWUI。

重新定義的事物加權(quán)效用具有如下性質(zhì)：

性質(zhì)1 對(duì)于任何一個(gè)項(xiàng)集X，滿足RTWU(X) ≥u(X)。

性質(zhì)2 對(duì)于任何一個(gè)項(xiàng)集X，如果RTWU(X) ＜min_util，那么項(xiàng)集X及其所有超集都不是高效用項(xiàng)集。

性質(zhì)3 對(duì)于任何一個(gè)項(xiàng)集X，滿足RTWU(X) ≤TWU(X)。

由性質(zhì)3 可知，RTWU 有著更嚴(yán)格的上界，因此使用RTWU 來修剪項(xiàng)集的搜索空間，將有效提升算法性能。

1.3 蝙蝠算法

2010 年，Yang 等［15］受到蝙蝠回聲定位特性的啟發(fā)提出了蝙蝠算法（BA）。在BA 中，每個(gè)蝙蝠個(gè)體隨機(jī)生成，通過改變其頻率、速度和位置來接近最優(yōu)解。在每個(gè)種群中，這些值更新表示為：

當(dāng)蝙蝠接近獵物時(shí)，它會(huì)逐漸降低響度并增加脈沖發(fā)射的頻率，以便快速、動(dòng)態(tài)地掌握獵物方位。第i只蝙蝠的聲波響度和頻度的更新表示為：

其中：α∈(0，1)是聲波響度衰減系數(shù)；γ＞0 是脈沖頻度增強(qiáng)系數(shù)表示蝙蝠i初始脈沖頻率。

基于BA 的HUIM 算法［12］中，一個(gè)蝙蝠個(gè)體表示一個(gè)項(xiàng)集，適應(yīng)值表示項(xiàng)集的總效用，通過設(shè)置合適的迭代次數(shù)、聲波響度衰減系數(shù)、脈沖增強(qiáng)系數(shù)，就可以進(jìn)行HUI 的挖掘。

2 HUIM-LC-BA

本章將詳細(xì)介紹HUIM-LC-BA，包括重新定義的事物加權(quán)效用策略、原始事務(wù)數(shù)據(jù)庫位圖的表示、無希望編碼向量的剪枝、項(xiàng)集長度修剪策略、種群初始化以及算法的偽代碼。

2.1 數(shù)據(jù)的位圖表示和剪枝策略

2.1.1 數(shù)據(jù)的位圖表示

設(shè)一個(gè)有限項(xiàng)集I={i1，i2，…，iN}和一個(gè)事務(wù)數(shù)據(jù)庫D={T1，T2，…，TM}，則位圖是一個(gè)M×N的布爾矩陣，定義為B(D)。在事務(wù)Tj(1 ≤j≤N)中，項(xiàng)目ik(1 ≤k≤N)的位置記 為(j，k)，即位于B(D) 的 第j行、第k列。Bj，k的值定 義如下：

即當(dāng)項(xiàng)目ik出現(xiàn)在事務(wù)Tj中，布爾矩陣B(D)中第j行、第k列這個(gè)位置為1，否則該位置為0。

定義13位圖覆蓋。在位圖矩陣中，項(xiàng)目ik的位圖覆蓋是B(D)中的第k列向量，定義為Bit(ik)。同理，項(xiàng)集X的位圖覆蓋定義為Bit(X)=即項(xiàng)集X的位圖覆蓋是通過項(xiàng)集X中每一個(gè)項(xiàng)目的位圖覆蓋按位與運(yùn)算得到。

2.1.2 RTWU剪枝策略

定義14設(shè)項(xiàng)目ij，若RTWU(ij) ＜min_util，則項(xiàng)目ij是低重新定義的事物加權(quán)效用，記為1-LRTWUI。

由性質(zhì)2 可知1-LRTWUI 及其所有的超集都是低效用項(xiàng)集。因此，可以先計(jì)算所有項(xiàng)目的RTWU，然后刪除掉1-LRTWUI 的項(xiàng)目，以有效縮減搜索空間。

在表1 和表2 的事務(wù)表中，設(shè)min_util=30，lmax=3，由于項(xiàng)目f和g是1-LRTWUI，故不會(huì)出現(xiàn)在位圖中，則整理后的事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為位圖如表4 所示。

表4 事務(wù)數(shù)據(jù)的位圖表示Tab.4 Bitmap representation of transaction database

2.1.3 無希望編碼向量剪枝策略

在HUIM-LC-BA 中，每個(gè)蝙蝠個(gè)體就是一個(gè)編碼向量。編碼向量由0 或1 組成，表示個(gè)體中某個(gè)項(xiàng)目出現(xiàn)或不出現(xiàn)。如果一個(gè)個(gè)體中對(duì)應(yīng)的第j位為1，就表示第j位置中對(duì)應(yīng)的項(xiàng)目出現(xiàn)在項(xiàng)集中；反之，則表示第j位置對(duì)應(yīng)的項(xiàng)目沒有出現(xiàn)在項(xiàng)集中。每個(gè)蝙蝠對(duì)應(yīng)的編碼向量的長度為|1-HRTWU|，如項(xiàng)集{a，c，d}的編碼向量如圖1 所示。

圖1 項(xiàng)集{a，c，d}的編碼向量Fig.1 Coding vector of itemset {a，c，d}

定義15設(shè)Vec為只有0 和1 組成的關(guān)于項(xiàng)集X的編碼向量。如果Bit(X)只由0 組成，那么該Vec被稱為無希望編碼向量（Unpromising Encoding Vector，UPEV）；反之，則稱為有希望編碼向量（Promising Encoding Vector，PEV）［10］。

因?yàn)轵饌€(gè)體隨機(jī)生成，不可避免地會(huì)生成一些數(shù)據(jù)庫中不存在的項(xiàng)集，即無希望項(xiàng)集。為了避免無希望項(xiàng)集效用的計(jì)算，需要對(duì)無希望的編碼向量進(jìn)行修剪。無希望編碼向量剪枝策略的偽代碼由算法1 給出。

算法1 無希望編碼向量（UPEV）剪枝策略。

2.1.4 項(xiàng)集長度修剪策略

在文獻(xiàn)［7］中，F(xiàn)HM+算法首先建立一個(gè)存放所有項(xiàng)目對(duì)的三元 組結(jié)構(gòu) EUCS（Estimated Utility Co-occurrence Structure），定義為(a，b，c) ∈I*×I*×R，即RTWU(a，b)=c。FHM+算法從單個(gè)項(xiàng)目開始，通過深度優(yōu)先搜索逐漸追加單個(gè)項(xiàng)目，直到最大長度。在搜索的過程中，當(dāng)EUCS 中不存在元組(x，y，c)滿足c≥min_util，則進(jìn)行修剪，即項(xiàng)集{x，y}及其所有的超集都是低效用項(xiàng)集，不再探索。

在BA 中，由于蝙蝠個(gè)體隨機(jī)生成，故不能直接使用上述EUCS 結(jié)構(gòu)來剪枝。因此本文利用蝙蝠個(gè)體隨機(jī)變化的特性提出一種新的項(xiàng)集長度修剪策略，通過將PEV 添加、刪除若干個(gè)項(xiàng)目，使它的長度l滿足lmin≤l≤lmax。該策略包含以下三種情況：

1）如果l＜lmin，則生成一個(gè)隨機(jī)整數(shù)n，滿足lmin-l≤n≤lmax-l；然后使用深度優(yōu)先搜索增加n個(gè)項(xiàng)目，如算法2所示，首先在只記錄0 索引的zero集合中利用輪盤賭注選擇法確定待增加的項(xiàng)目；第4）行變換一個(gè)項(xiàng)目后就立刻將這個(gè)位置的項(xiàng)目刪除，以避免對(duì)某個(gè)項(xiàng)目的重復(fù)變換和無限的搜索。如果執(zhí)行算法1 后，編碼向量的長度加1，說明成功添加一個(gè)項(xiàng)目，此時(shí)n-1；反之n不變繼續(xù)搜索直到滿足長度約束或者遍歷完所有的項(xiàng)目為止。

2）如果l＞lmax，則生成一個(gè)隨機(jī)整數(shù)n，滿足l-lmax≤n≤l-lmin，然后使用輪盤賭注選擇法確定刪除的n個(gè)項(xiàng)目，將編碼向量中這些位置由1 變?yōu)?。因?yàn)橛邢Ｍ木幋a向量減去部分項(xiàng)集仍是有希望的編碼向量，故無需再使用算法1檢驗(yàn)。

3）如果lmin≤l≤lmax，編碼向量滿足長度約束，故不做改動(dòng)。

算法2 Search。

項(xiàng)集長度修剪策略算法的偽代碼由算法3 給出。

算法3 項(xiàng)集長度約束修剪策略。

2.2 種群初始化

種群初始化的主要作用是隨機(jī)產(chǎn)生若干個(gè)蝙蝠個(gè)體。在算法4 中，首先掃描數(shù)據(jù)庫一次，刪除1-LRTWUI；接著將修剪后的事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為位圖矩陣。第3）～10）行循環(huán)生成初始蝙蝠個(gè)體，其中：第4）行生成一個(gè)隨機(jī)數(shù)n，并且滿足lmin≤l≤lmax+C（C為一個(gè)常數(shù)，可根據(jù)|1-RHTWUI |適應(yīng)性調(diào)整，以大概率生成符合長度約束的項(xiàng)集）；第5）行設(shè)置Vec中n個(gè)位置1，其余全為0。式（14）為項(xiàng)目ij被設(shè)為1的概率。

其中：HN=|1-LRTWUI |表示高重新定義的事務(wù)加權(quán)效用1-項(xiàng)集的個(gè)數(shù)。由式（14）可知項(xiàng)目ij的RTWU 值越大，則在初始化種群中有更大的概率被選中。第6）～8）行修剪初始向量，使該向量是有希望編碼向量并且滿足長度約束條件。

算法4 種群初始化。

2.3 HUIM-LC-BA設(shè)計(jì)

本文提出的HUIM-LC-BA 利用了前面介紹的幾種策略。算法5 為主算法，將事物數(shù)據(jù)庫D、最小閾值min_util、項(xiàng)集的長度范圍以及最大迭代次數(shù)作為輸入，輸出lc-高效用項(xiàng)集。

第1）～4）行分別表示初始化蝙蝠種群，初始化迭代次數(shù)iter為1，gbest表示全局最優(yōu)解初始為空，SHUI（Set of High Utility Itemset）表示高效用項(xiàng)集的集合。第5）～20）行為主循環(huán)，表示通過一個(gè)種群到下一個(gè)種群的迭代逐個(gè)發(fā)現(xiàn)符合長度約束的高效用項(xiàng)集。第6）～14）行循環(huán)遍歷每個(gè)蝙蝠個(gè)體，如果當(dāng)前種群是第一個(gè)種群，則初始化當(dāng)前蝙蝠的Ai和ri；第10）行計(jì)算蝙蝠B(yǎng)i對(duì)應(yīng)數(shù)據(jù)庫中的項(xiàng)集，函數(shù)IS（）通過項(xiàng)目i在蝙蝠B(yǎng)i中對(duì)應(yīng)位置是否為1，返回對(duì)應(yīng)的項(xiàng)集；第11）～13）行查找并記錄還沒有被發(fā)現(xiàn)的符合長度約束的高效用項(xiàng)集；第15）行更新當(dāng)前蝙蝠經(jīng)歷過的最好位置；第16）行使用新的gbest并調(diào)用算法6 生成下一個(gè)種群；第17）行在所有發(fā)現(xiàn)的SHUI使用輪盤賭注選擇法確定下一個(gè)種群的初始gbest；第18）行更新迭代次數(shù)；最后，在第20）行輸出lc-高效用項(xiàng)集。

算法5 HUIM-LC-BA。

生成下一個(gè)種群時(shí)，HUIM-LC-BA 將式（9）改為式（15）：

其中：vi1總是設(shè)為1，vi2由式（16）給出。

其中：vi1表示隨機(jī)接近最優(yōu)值；vi2使用當(dāng)前蝙蝠和當(dāng)前種群的最佳位置之間的差異來接近最優(yōu)值。

生成下一個(gè)種群的步驟由算法6 給出。其中第2）～5）行：首先使用反碼運(yùn)算隨機(jī)改變蝙蝠B(yǎng)i編碼向量的一個(gè)位置；然后繼續(xù)使用反碼運(yùn)算隨機(jī)改變蝙蝠B(yǎng)i的編碼向量中vi2個(gè)位置。第6）行調(diào)用算法1 生成新的編碼向量；第7）行調(diào)用算法3 修剪向量長度；第8）行判斷隨機(jī)數(shù)rand1是否大于ri。第9）～12）行確定與列舉的蝙蝠對(duì)應(yīng)的項(xiàng)目集，如果目前沒有發(fā)現(xiàn)它并且它是一個(gè)lc-高效用項(xiàng)集，則記錄它。第13）行再隨機(jī)改變一位得到一個(gè)新的Bi，第14）～15）行生成新的編碼向量；第17）～21）行更新Ai和ri；第22）行，輸出下一個(gè)種群。

算法6 Next_Gen_BA。

2.4 算法示例

使用表1 和表2 的事務(wù)數(shù)據(jù)庫來演示HUIM-LC-BA，設(shè)效用閾 值min_util=30，種群數(shù) 量SN=3。由 于|1-RHTWUI |=5，所以編碼向量長度為5。首先，通過算法4初始化種群，并設(shè)置初值。假設(shè)第1 個(gè)種群的3 個(gè)蝙蝠的編碼向量如圖2（a）所示。

圖2 算法示例Fig.2 Algorithm example

從圖2（a）中，得到第一個(gè)蝙蝠對(duì)應(yīng)的項(xiàng)集b1={a，b，c，d，e}。根據(jù)算法1，RV首先初始化為Bit(a)=10110。接著RV∩Bit(b)=10110 ∩11001=10000，結(jié)果不全為0，RV更新為10000。接著，RV∩Bit(c)=10000 ∩11111=10000，RV為 10000。下一步RV∩Bit(d)=10000 ∩01100=00000，結(jié)果全為0，是非期望編碼向量，故在b1中刪除項(xiàng)目d，同時(shí)RV保持原來的值10000。接下來RV∩Bit(e)=10000，最終RV=10000。此時(shí)，b1的編碼向量為11101，代表項(xiàng)集{a，b，c，e}被包含在事物T1中。因?yàn)轫?xiàng)集的{a，b，c，e}長度為4 ＞3，故需要修剪。在算法2 中，首先隨機(jī)生成一個(gè)數(shù)n=1，使用輪盤賭注選擇法將第5 位變成0，得到長度為3的項(xiàng)集{a，b，c}，因?yàn)閡({a，b，c})=18 ＜min_util，因此項(xiàng)集{a，b，c}不是一個(gè)lc-高效用項(xiàng)集。類似的，b2代表項(xiàng)集為{a，c，e}，是期望編碼向量且長度為3，在事物T1和T4中，因?yàn)閡({a，c，e})=31 ＞min_util，所以項(xiàng)集{a，c，e}是一個(gè)lc-高效用項(xiàng)集，且SHUI={{a，c，e}：33}，其中冒號(hào)后面表示項(xiàng)集的效用值。同理，b3代表項(xiàng)集｛d，e｝，因 為u({d，e})=18 ＜min_util，所以不是lc-高效用項(xiàng)集，SHUI保持不變。最后，得到第一個(gè)種群如圖2（b）所示。由于是第一個(gè)種群，且SHUI中只有1 個(gè)項(xiàng)集，因此gbest為10101。

接著，生成下一個(gè)蝙蝠種群。首先考慮圖2（b）中b1，假設(shè)選擇第5 位，并將該位從0 更改為1，得到b1=11101。假設(shè)fmin=0，fmax=1，β為0.8，根據(jù)式（8）得到f1=0.8。接著計(jì)算b1的速度，通過BitDiff(b1，gbest)={2}，v12=2× 0.8=2。因此，按位補(bǔ)碼操作隨機(jī)更改b1的兩位。假設(shè)選擇第1 位和第3 位，得到新的b1=01001。然后生成一個(gè)隨機(jī)數(shù)rand1，假設(shè)rand1大于當(dāng)前的r1，當(dāng)前b1=01001 表示項(xiàng)集｛b，e｝。b1是一個(gè)期望的編碼向量，且長度為2，滿足u({b，e})=34 ＞min_util。因此，{b，e}是一個(gè)lc-高效用項(xiàng)集，將它存入SHUI，同時(shí)更新gbest。最后，通過逐位補(bǔ)碼操作隨機(jī)改變以為來進(jìn)一步處理b1。假設(shè)第2 位從1 變?yōu)?，得到新的b1=00001，雖然b1長度為1 且是期望編碼向量，但u({e})=15 ＜min_util，gbest和SHUI保持不變。

類似的，可以通過相同的方法獲得b2、b3的新值。重復(fù)上述步驟，直到達(dá)到最大迭代次數(shù)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)所有程序均用Java 進(jìn)行編寫，實(shí)驗(yàn)環(huán)境為Intel Core i7-11700 @2.5 GHz，8 GB 內(nèi) 存，Windows11 64位操作系統(tǒng)。

本實(shí)驗(yàn)采用了4 個(gè)公開的真實(shí)數(shù)據(jù)集，各個(gè)數(shù)據(jù)集的特征如表5 所示。其中，mushroom 數(shù)據(jù)集包含各種蘑菇種類及特征，如形狀、氣味和棲息地；chess 和 connect 數(shù)據(jù)集來源于游戲步驟；accident_10%數(shù)據(jù)集記錄了某地的交通事故數(shù)據(jù)，與之前的研究相似，本文只取了其中10%。這些數(shù)據(jù)都可以從SPMF 網(wǎng)站上下載。

表5 真實(shí)事務(wù)數(shù)據(jù)集統(tǒng)計(jì)Tab.5 Statistics of real transaction datasets

本文中所有的實(shí)驗(yàn)的最大迭代次數(shù)設(shè)置為6 000，種群的初始大小為100，默認(rèn)最小長度為1。

3.2 高效用項(xiàng)集挖掘?qū)Ρ葘?shí)驗(yàn)

3.2.1 RTWU策略

本節(jié)評(píng)估了RTWU 策略在不同長度約束條件下對(duì)搜索空間的影響，主要考慮編碼向量的長度，即1-HRTWUI 的個(gè)數(shù)，并和包含所有長度的編碼向量作比較。

為了便于觀察和分析，在文獻(xiàn)［7］的基礎(chǔ)上，設(shè)置最大長度約束為2、4、6、8、10 進(jìn)行仿真實(shí)驗(yàn)，并在4 個(gè)數(shù)據(jù)集上不斷增加效用閾值，運(yùn)行HUIM-LC-BA 和傳統(tǒng)的HUIM-BA。在各數(shù)據(jù)集和各約束下的編碼向量長度由表6 給出。其中：lmax表示在HUIM-LC-BA 中設(shè)置的最大長度值；all-len 表示傳統(tǒng)算法HUIM-BA 挖掘所有長度的項(xiàng)集的運(yùn)行情況。觀察表6發(fā)現(xiàn)，在各效用閾值下，具有長度約束的編碼向量的長度都小于包含所有長度的編碼向量，并且隨著長度的減少而減少。尤其是在項(xiàng)數(shù)較多的accident_10%數(shù)據(jù)集中，與all_len情況相比，lmax=2 編碼向量長度平均減少了60%。因此，RTWU 策略能有效減小編碼向量的長度，縮小搜索空間，且在最大長度較小時(shí)效果更好。3.2.2 不同長度約束下挖掘數(shù)量的比較

表6 在不同數(shù)據(jù)集上Vec的長度Tab.6 Length of Vec on different datasets

本節(jié)評(píng)估了在不同長度約束下挖掘模式的數(shù)量。HUIM-LC-BA 和其他的基于演化算法的高效用項(xiàng)集挖掘算法一樣，不能保證在一定的迭代次數(shù)內(nèi)找到所有的高效用項(xiàng)集，而FHM+算法在時(shí)間和內(nèi)存都充足的條件下可以找到所有的高效用項(xiàng)集。因此，為驗(yàn)證HUIM-LC-BA 挖掘的項(xiàng)集數(shù)量，令lmax=6，運(yùn)行FHM+算法和HUIM-LC-BA，計(jì)算HUIMLC-BA 挖掘的項(xiàng)集數(shù)量與FHM+算法挖掘項(xiàng)集數(shù)量的比值，實(shí)驗(yàn)結(jié)果如表7 所示。

表7 挖掘6-HUI的百分比Tab.7 Percentage of mined 6-HUIs

觀察表7 可知，在挖掘數(shù)量方面，各數(shù)據(jù)集平均挖掘百分比都達(dá)到了90%，且在效用閾值較大時(shí)達(dá)到了100%，說明所提出的算法能有效挖掘具有長度約束的高效用項(xiàng)集。為了繼續(xù)比較不同長度約束下算法挖掘的模式數(shù)量，在4 個(gè)數(shù)據(jù)集上運(yùn)行HUIM-LC-BA 和傳統(tǒng)的HUIM-BA，結(jié)果如圖3 所示。在圖3 中觀察到，通過設(shè)置不同長度約束可以大幅減少模式數(shù)量，且在lmax=2 或4 時(shí)，由于項(xiàng)集數(shù)量太少導(dǎo)致無法在圖上正常顯示。在mushroom、chess、connect、accident_10%數(shù)據(jù)集上，當(dāng)最大長度為6 時(shí)，與HUIM-BA 相比，HUIM-LCBA 挖掘的模式數(shù)量減小了91%、98%、99%、97%，并且隨著最大長度的減小模式數(shù)量也不斷減少。觀察圖3（c），在connect 數(shù)據(jù)集中，HUIM-LC-BA 挖掘數(shù)量遠(yuǎn)小于HUIM-BA，并結(jié)合表10 可知此時(shí)挖掘的百分比為100%，說明該數(shù)據(jù)集中長度為5 的高效用項(xiàng)集很少，通過HUIM-LC-BA 明顯減少了無效項(xiàng)集的生成。

圖3 不同長度約束下高效用項(xiàng)集的數(shù)量Fig.3 Number of HUIs under different length constraints

因此，通過HUIM-LC-BA 可過濾掉高效用但不符合長度約束的項(xiàng)集，只輸出少量的lc-高效用項(xiàng)集，有利于用戶的分析和決策。

3.2.3 運(yùn)行時(shí)間

本節(jié)評(píng)估了HUIM-LC-BA 在不同長度約束下運(yùn)行時(shí)間的性能。結(jié)果如圖4 所示，其中l(wèi)max表示最大長度約束。

圖4 不同長度約束下的算法運(yùn)行時(shí)間對(duì)比Fig.4 Comparison of algorithm running time under different length constraints

由圖4 可以看出，由于HUIM-BA 要挖掘所有的高效用項(xiàng)集，所以運(yùn)行時(shí)間不隨長度增加而變化。在圖4 中可以清晰看到HUIM-LC-BA 的運(yùn)行時(shí)間遠(yuǎn)小于HUIM-BA。因?yàn)镠UIM-LC-BA 利用長度約束在蝙蝠種群初始化時(shí)修剪了更多無期望的項(xiàng)目，縮小了搜索空間。在mushroom、connect 和accident_10%數(shù)據(jù)集中，當(dāng)lmax＜6 時(shí)，F(xiàn)HM+算法運(yùn)行時(shí)間遠(yuǎn)小于另外兩種算法，但當(dāng)lmax＞8 時(shí)，F(xiàn)HM+算法運(yùn)行時(shí)間急劇增加，而HUIM-LC-BA 的運(yùn)行時(shí)間增長相對(duì)穩(wěn)定。因?yàn)镕HM+算法從單個(gè)項(xiàng)目開始不斷枚舉增加額外的項(xiàng)目直到達(dá)到最大長度，在lmax較小時(shí)，很容易找到符合長度約束的高效用項(xiàng)集；但當(dāng)lmax逐漸增加，需要組合的項(xiàng)目和項(xiàng)集數(shù)量增多，F(xiàn)HM+面臨指數(shù)的搜索空間導(dǎo)致開銷很大。同樣觀察圖4（b）的chess 數(shù)據(jù)集，由于chess 數(shù)據(jù)集中項(xiàng)目和事物數(shù)量相對(duì)較少，所以在lmax=10 時(shí)FHM+算法仍具有良好的性能，但依然可以看出FHM+算法的運(yùn)行時(shí)間急劇增長。此外，通過觀察HUIM-LC-BA 在每50 次迭代后挖掘的lc-高效用項(xiàng)集數(shù)量發(fā)現(xiàn)，當(dāng)lmax較小時(shí)，HUIM-LC-BA 在較少的迭代次數(shù)就已經(jīng)發(fā)現(xiàn)了所有的lc-高效用項(xiàng)集，但由于HUIM-LC-BA 的隨機(jī)性并不知道已經(jīng)找到了所有的lc-高效用項(xiàng)集，所以會(huì)繼續(xù)迭代下去直到達(dá)到最大迭代次數(shù)，導(dǎo)致HUIM-LC-BA 在lmax較小時(shí)運(yùn)行時(shí)間遠(yuǎn)大于FHM+算法，但實(shí)際找到所有的lc-高效用項(xiàng)集運(yùn)行時(shí)間小于統(tǒng)計(jì)值。因此，HUIM-LC-BA 能有效挖掘出lc-高效用項(xiàng)集，并在數(shù)據(jù)集較大時(shí)仍有較好的性能。

4 結(jié)語

針對(duì)挖掘含長度約束的高效用項(xiàng)集挖掘的問題，提出一種基于長度約束的蝙蝠高效用項(xiàng)集挖掘算法（HUIM-LCBA）。為了更好地壓縮搜索空間，該算法使用重新定義事務(wù)加權(quán)效用，修剪更多的不能產(chǎn)生高效用的項(xiàng)目。為了有效挖掘符合長度約束的高效用項(xiàng)集，該算法提出項(xiàng)集長度修剪策略。在4 個(gè)數(shù)據(jù)集上進(jìn)行大量實(shí)驗(yàn)，結(jié)果表明，本文的HUIM-LC-BA 能夠高效地挖掘具有不同長度約束的高效用項(xiàng)集，減少模式的數(shù)量，并在大數(shù)據(jù)集上仍有較好的性能。由于該算法不能確定是否已經(jīng)找到所有的高效用項(xiàng)集，因此在未來的工作中，可以研究算法是否已經(jīng)找到了所有的高效用項(xiàng)集，從而減少迭代次數(shù)，進(jìn)一步提升算法性能。