王常武，尹松林，劉文遠，魏小梅，鄭紅軍，楊繼萍

1(燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004)

2(北京聯(lián)合大學(xué) 機器人學(xué)院，北京 100101)

E-mail：wcw@ysu.edu.cn

1 引 言

頻繁項集挖掘(Frequent Itemset Minging，F(xiàn)IM)的任務(wù)是挖掘出事務(wù)數(shù)據(jù)庫中的頻繁項集[1]，即挖掘出交易數(shù)據(jù)庫中頻繁出現(xiàn)的項目組合.頻繁項集挖掘是許多應(yīng)用的基礎(chǔ)，其中最經(jīng)典的應(yīng)用是購物籃分析問題[2].人們對頻繁項集挖掘已經(jīng)做了很多工作，頻繁項集挖掘需要滿足兩個假設(shè)：1)每個項目在每次交易中不會出現(xiàn)多次；2)所有項目具有相同的重要性(單位利潤或價值).在實際生活中，這兩個假設(shè)卻經(jīng)常得不到滿足.例如考慮客戶交易數(shù)據(jù)庫，客戶通常會購買同一商品的幾個單位(例如，客戶可能會購買幾瓶果汁)，并且商品具有各不相同的單位利潤(例如，銷售鉆石比銷售一瓶果汁產(chǎn)生更多的利潤).頻繁項集挖掘算法不能同時考慮到商品的購買數(shù)量和單位利潤，只能找到頻繁出現(xiàn)的商品組合，而不是那些能夠產(chǎn)生高利潤的商品組合[3].

考慮到購買數(shù)量和單位利潤，人們進一步提出了高效用項集挖掘(High Utility Itemset Mining，HUIM)[4].高效用項集挖掘的目標(biāo)是發(fā)現(xiàn)具有高效用(例如，高利潤)的項集，即高效用項集(High Utility Itemset，HUI).高效用項集的傳統(tǒng)挖掘算法都會面臨項集的搜索空間呈“指數(shù)增長”的趨勢[5].

生物啟發(fā)計算能通過迭代不斷改進候選解決方案，從而優(yōu)化問題.2014年，Kannimuthu和Premalatha提出了基于遺傳算法(Genetic Algorithm，GA)的高效用項集挖掘算法—HUPE-GARM算法[6，7].由于每一次迭代中隨機選擇和變異生成的新項集會明顯不同于上一代的結(jié)果，算法的收斂速度會很慢.因此HUPE-GARM算法在一定的迭代次數(shù)中只能挖掘出少量的高效用項集.2017年，Lin等人提出了一種基于粒子群優(yōu)化(Particle Swarm Optimization，PSO)的高效用項集挖掘算法—HUIM-BPSO算法[8，9].高效用項集挖掘問題不同于只有少量最優(yōu)值的問題，它需要挖掘出所有效用值不小于效用閾值的項集.由于高效用項集在數(shù)據(jù)集中的分布是不均勻的，粒子群優(yōu)化算法將上一代種群的最優(yōu)值作為下一代種群的優(yōu)化值進行搜索可能會導(dǎo)致在一定次數(shù)的迭代次數(shù)中遺漏一些高效用項集.

本文提出了一個改進的粒子群優(yōu)化(Improved Particle Swarm Optimization，IPSO) HUIM-IPSO算法.算法(1)通過輪盤賭選擇法在當(dāng)前代種群的高效用項集中，以一定概率選擇下一代種群的優(yōu)化值，增加了種群的多樣性；(2)使用位圖矩陣來表示事務(wù)數(shù)據(jù)庫和非期望編碼向量修剪策略去除事務(wù)數(shù)據(jù)庫中不存在的項集，加快了算法挖掘高效用項集的速度.實驗結(jié)果顯示，HUIM-IPSO算法比HUPE-GRAM算法和HUIM-BPSO算法有更高的挖掘效率和更快的收斂速度.

2 高效用項集挖掘和粒子群優(yōu)化

2.1 高效用項集挖掘

令I(lǐng)={i1，i2，…，in}是一個有限的項目集合.事務(wù)數(shù)據(jù)庫DB由1個事務(wù)表和1個外部效用表構(gòu)成.事務(wù)表由多個事務(wù){(diào)T1，T2，…，Tn}構(gòu)成，其中每個事務(wù)Tc?I，同時每一個事務(wù)Tc都有唯一的標(biāo)識符Tid.外部效用表則保存了每個項目的單位利潤或者重要度.

定義1.由若干個項目構(gòu)成的一個集合，稱為項集.包含k個項目的集合一般稱為k-項集.

定義2.對于每個事務(wù)Tc中的每個項目i∈Tc都會對應(yīng)一個表示項目購買數(shù)量或者出現(xiàn)頻次的正整數(shù)iu(i，Tc)，稱為項目的內(nèi)部效用.每個項目還會對應(yīng)一個表示單位利潤或者重要度的正整數(shù)eu(i)，稱為項目的外部效用.

表1和表2給出了一個事務(wù)數(shù)據(jù)庫示例.數(shù)據(jù)庫包含10條互不相同的事務(wù)(T1，T2，…，T10).在事務(wù)T2中包含項目(b，d，e，f)，項目對應(yīng)的內(nèi)部效用值分別為(6，1，1，1).其中，事務(wù)T2中項目b對應(yīng)的內(nèi)部效用為6，表示事務(wù)T2中b出現(xiàn)了6次.從表2可得，事務(wù)T2中這些項目的外部效用為(9，5，6，1)，其中項目b對應(yīng)的外部效用為9，表示項目b的重要度為9.

定義3.在事務(wù)中項目的外部效用與內(nèi)部效用的乘積，稱為項目效用.記為u(i，Tc)，如式(1)所示.

u(i，Tc)=eu(i)×iu(i，Tc)

(1)

式中，i表示事務(wù)Tc中的項目；eu(i)表示項目i的外部效用；iu(i，Tc)表示事務(wù)Tc中項目i的內(nèi)部效用.

由定義3容易得到事務(wù)Tc中項集X的效用如式(2)所示.

u(X，Tc)=∑i∈X∧X?Tcu(i，Tc)

(2)

它表示項集X中每個項目i的效用加和.

例如在表1和表2的示例中，事務(wù)數(shù)據(jù)庫中事務(wù)T2中項目b的效用為u(b，T2)=6×9=54.在事務(wù)T2中項集{b，e}的效用為u({b，e}，T2)=u(b，T2)+u(e，T2)=54+6=60.

定義4.在事務(wù)數(shù)據(jù)庫中項集的總效用，稱為項集總效用.記為u(X)，如式(3)所示.

u(X)=∑Tc∈DBu(X，Tc)

(3)

式中，X表示事務(wù)Tc中的項集.

例如在表1和表2的示例中，事務(wù)數(shù)據(jù)庫中項集{a，c}的總效用u({a，c})=u({a，c}，T1)+u({a，c}，T3)+u({a，c}，T8)=21+7+34=62.

表1 事務(wù)信息

表2 項目的外部效用

定義5.在事務(wù)數(shù)據(jù)庫中項集總效用大于等于效用閾值的項集，稱為高效用項集.記為HUI，如式(4)所示.

HUI={X|u(X)≥minutil}

(4)

式中，minutil表示效用閾值.

例如在表1和表2的示例中，如果minutil= 115.項集{b，f}，{b，e，f}，{b，d}，{b，d，e}，，{b，e}都是高效用項集，它們的效用分別為135，131，154，166，216和222.

能夠證明項集的效用既不是單調(diào)的，也不是反單調(diào)的.由此可知，一個項集可能有低效用的、相等效用的或者高效用的子集[10].因此，在頻繁項集挖掘問題中使用的修剪項集搜索空間的方法，在高效用項集挖掘問題中不能直接使用.

為了解決項集效用值既不是單調(diào)的，又不是反單調(diào)的這個問題，一些高效用項集挖掘算法中提出了事務(wù)加權(quán)效用，而它是反單調(diào)的[11].

定義6.事務(wù)數(shù)據(jù)庫中事務(wù)的效用，稱為事務(wù)效用.記為TU(Tc)，如式(5)所示.

TU(Tc)=∑i∈Tcu(i，Tc)

(5)

式中，u(i，Tc)表示在事務(wù)Tc中項目i的項目效用.

表3給出了事務(wù)T1，T2，…，T10的事務(wù)效用.

表3 事務(wù)效用

定義7.事務(wù)數(shù)據(jù)庫中，經(jīng)常會出現(xiàn)多個事務(wù)包含某個項集，這些事務(wù)的效用加和稱為某項集的事務(wù)加權(quán)效用.記為TWU(X)，如式(6)所示.

TWU(X)=∑Tc∈DB∧X?TcTU(Tc)

(6)

定義8.設(shè)項集X，如果TWU(X)≥minutil，則X稱為高事務(wù)加權(quán)效用項集，記為HTWUI；反之，稱X為低事務(wù)加權(quán)效用項集，記為LTWUI，如式(7)和式(8)所示.

HTWUI={X|TWU(X)≥minutil}

(7)

LTWUI={X|TWU(X)

(8)

式中，minutil表示效用閾值.包含k個項目的HTWUI和LTWUI分別記為k-HTWUI和k-LTWUI.

事務(wù)加權(quán)效用具有3個重要的性質(zhì).

性質(zhì)1.令項集X，則有TWU(X) ≥u(X)，說明項集的事務(wù)加權(quán)效用是它本身效用值的向上估計.

性質(zhì)2.設(shè)項集X、Y，如果X?Y，那么有TWU(X)≥TWU(Y).這說明事物加權(quán)效用是反單調(diào)的.

根據(jù)定義2，性質(zhì)1和性質(zhì)2是顯然成立的.

性質(zhì)3.設(shè)項集X，如果TWU(X)

性質(zhì)3可以使用性質(zhì)1和性質(zhì)2進行證明，同時該性質(zhì)在高效用項集挖掘算法中經(jīng)常被用來修剪項集的搜索空間.

2.2 粒子群優(yōu)化

1995年，Eberhart和Kennedy提出了粒子群優(yōu)化算法.

粒子群優(yōu)化采用公式(9)和公式(10)對粒子的位置進行更新.

(9)

(10)

式中，i= 1，2，…，m；w是大于等于0的數(shù)，稱為慣性因子；加速常數(shù)c1和c2也是大于等于0的數(shù)；r1和r2是范圍在[0，1]內(nèi)的隨機數(shù).

迭代終止的條件根據(jù)具體問題設(shè)定，一般是迭代次數(shù)達到預(yù)定的最大值或者是粒子群優(yōu)化所能夠搜索到的最優(yōu)值滿足了目標(biāo)函數(shù)的最小容許誤差.

基于粒子群優(yōu)化的高效用項集挖掘算法中，項集用來表示粒子，項集總效用用來表示適應(yīng)值.然后選擇一個合適的迭代次數(shù)就可以進行高效用項集的挖掘了.

3 改進的粒子群優(yōu)化高效用項集挖掘算法

3.1 算法總體思想

算法輸入為效用閾值和需要挖掘的事務(wù)數(shù)據(jù)庫.用位圖矩陣表示事務(wù)數(shù)據(jù)庫.通過輪盤賭選擇法和非期望編碼向量修剪策略初始化種群.粒子適應(yīng)值通過公式(3)計算，保留適應(yīng)值不小于效用閾值的粒子作為高效用項集.通過輪盤賭選擇法在當(dāng)前代種群的高效用項集中選擇下一代種群的初始優(yōu)化值.當(dāng)前代種群中第i個高效用項集被選中的概率記為Si，如公式(11)所示.

(11)

式中，SHUI表示當(dāng)前代種群中所有高效用項集的集合，|SHUI|表示集合SHUI中元素的數(shù)量，fitnessi表示發(fā)現(xiàn)的第i個高效用項集的適應(yīng)值.通過粒子位置更新公式(9)和公式(10)以及非期望編碼向量修剪策略生成下一代種群.每次迭代中都有適應(yīng)值的計算、高效用項集的識別和下一代種群的生成，直到達到最大迭代次數(shù).

3.2 事務(wù)表示、項集修剪及種群初始化

3.2.1 位圖表示法

定義9.設(shè)Veci和Vecj是兩個長度為len的編碼向量，編碼向量是由0或1構(gòu)成的向量，則這兩個向量中具有不同值的位置集合，稱為編碼向量的異位集.記為BitDiff(Veci，Vecj)，如公式(12)所示.

BitDiff(Veci，Vecj)=

{num|1≤num≤len，bnum(Veci)⊕bnum(Vecj)=1}

(12)

式中，bnum(Veci)表示Veci第num個位置的值；⊕表示異或運算.

定義10.將事務(wù)數(shù)據(jù)庫表示成矩陣的形式稱為事務(wù)數(shù)據(jù)庫的位圖矩陣.已知DB={T1，T2，…，TN}是一個事務(wù)數(shù)據(jù)庫，M為事務(wù)數(shù)據(jù)庫DB中項目的總數(shù)，則DB的位圖矩陣記為B(DB).B(DB)是一個N×M的布爾型矩陣，其中B(DB)中每一個元素要么是1，要么是0.B(DB)第j行、第k列元素表示事務(wù)Tj是否包含項目ik，如公式(13)所示.

(13)

在公式(13)中，如果項目ik在事務(wù)Tj中，那么DB中第j行，第k列為1.否則，該位置的元素為0.

定義11.位圖矩陣中包含指定項目的某一列稱為該項目的位圖覆蓋.位圖矩陣B(DB)中項目ik的位圖覆蓋記為Bit(ik)，即位圖矩陣的第k列.這個概念容易擴展到項集，項集X的位圖覆蓋記為Bit(X)，如公式(14)所示.

Bit(X)=∩i∈X(Bit(i))

(14)

在公式(14)中項集X的位圖覆蓋是一個編碼向量，即項集X中的每一個項目的位圖覆蓋Bit(i)通過按位與運算得到.同樣，對于兩個項集X和Y，Bit(X∪Y)可由Bit(X)∩Bit(Y)計算得到.

表1和表2的示例中，設(shè)置效用閾值minutil=115.如表4所示，給出了由位圖矩陣表示的整理之后的事務(wù)數(shù)據(jù)庫.

表4 事務(wù)數(shù)據(jù)庫的位圖表示

3.2.2 項集修剪策略

改進的粒子群優(yōu)化算法中將每個粒子編碼成向量.編碼向量由0或1組成的，表示粒子中某個項目不出現(xiàn)或者出現(xiàn).如果在一個粒子中對應(yīng)的第j位為1，就表示第j個位置對應(yīng)的項目出現(xiàn)在項集中.否則，就表示第j個位置對應(yīng)的項目沒有出現(xiàn)在項集中.同時，每個粒子對應(yīng)的編碼向量的長度由事務(wù)數(shù)據(jù)庫中高事務(wù)加權(quán)效用項集的數(shù)量決定.為了加速高效用項集的挖掘過程，需要修剪掉事務(wù)數(shù)據(jù)庫中不存在的項集.

定義12.項集的編碼向量的位圖覆蓋如果只由0元素構(gòu)成，則該向量稱為非期望編碼向量(unpromising encoding vector，UPEV).反之，稱為期望編碼向量(promising encoding vector，PEV).項集的編碼向量若為非期望編碼向量，則該向量不可能是高效用項集.在高效用項集挖掘算法中去除非期望編碼向量的項集，稱為非期望編碼向量修剪策略(unpromising encoding vector cut strategy，UPEVC).非期望編碼向量修剪的偽代碼由算法1給出.

算法1.非期望編碼向量修剪策略

輸入：表示粒子的編碼向量Vec

輸出：期望編碼向量PEV

BEGIN

1. 計算Vec中1的數(shù)量，記為VN

2. 用i1，i2，…，iVN表示Vec中包含的項目

3. RV = Bit(i1)

4. FORk從2到VNDO

5. | RV′ = RV∩Bit(ik)

6. | IF RV′是一個UPEV THEN

7. | | RV′ = RV

8. | | 將Vec中對應(yīng)的ik從1變成0

9. | END IF

10.| RV = RV′

11.END FOR

12.RETURN RV

END

算法1的輸入為一個粒子的Vec，輸出為一個PEV.第1行計算出Vec中1的個數(shù).第2行識別出Vec中1代表哪些項目.第3行用第1個項目的位圖覆蓋初始化最終結(jié)果.第4-11行進入循環(huán)，在循環(huán)中執(zhí)行非期望編碼向量的修剪.第12行返回最終結(jié)果.如果Vec是一個UPEV，通過算法1將會得到一個PEV，并且它是原始Vec的一部分.否則，原始Vec保持不變.在HUIM-IPSO算法(詳見算法4)中，一旦生成新的粒子，就會使用算法1修剪該粒子，確保該粒子在事務(wù)數(shù)據(jù)庫中真實存在.

3.2.3 輪盤賭選擇法

輪盤賭選擇法的基本思想是個體被選中的概率與其適應(yīng)值的大小成正比，算法2給出了輪盤賭選擇法的整體流程.

算法2以種群中所有的個體作為輸入，輸出被選中的個體.第1行算出每個個體的適應(yīng)值.第2行根據(jù)公式(11)算出每個個體被選中的概率.第3行初始化一個空集RES.第4行算出每個個體的累積概率qk.第5-10行選出SN個個體保存在RES中.第11行返回選出個體的集合RES.

算法2.輪盤賭選擇法

輸入：種群中的每個粒子

輸出：被選中的粒子RES

BEGIN

1. 計算出種群中個體的適應(yīng)值fitnessi

2. 根據(jù)公式(11)算出每個個體被選到下一輪的概率Si

3.RES=Φ

5. FORk從1到種群規(guī)模SNDO

6. | 在[0，1]區(qū)間內(nèi)產(chǎn)生一個服從均勻分布的隨機數(shù)r

7. | IFqk-1

8. | | 個體k→RES

9. | END

10.END

11.RETURNRES

END

3.2.4 種群初始化

種群初始化的主要功能是隨機生成若干個粒子，詳細的初始化過程由算法3給出.

在種群初始化流程中，第1行掃描一遍事務(wù)數(shù)據(jù)庫保留1-HTWUI.第2行將修剪后的事務(wù)數(shù)據(jù)庫用位圖矩陣表示.第4行隨機生成一個數(shù)numi，并且1≤numi≤|1-HTWUI|.第5行設(shè)置Vec中有numi個1，其余都為0.項目ij被設(shè)為1的概率由公式(15)給出.

(15)

式中，HN表示高事務(wù)加權(quán)1-項集的個數(shù)，即HN=|1-HTWUI|.由公式(15)計算出1-HTWUI的事務(wù)加權(quán)效用.該值越大的1-HTWUI在初始種群中被選中的概率就越大.第6-8行非期望編碼向量修剪策略只會修剪numi>1的Vec.Vec中的每個位都表示一個1-HTWUI，所以這些1-項集一定被1個或多個事務(wù)所包含，這種類型的編碼向量顯然都是期望編碼向量.

算法3.種群初始化

輸入：事務(wù)數(shù)據(jù)庫DB；種群包含的粒子個數(shù)SN；

輸出：初始種群

BEGIN

1. 掃描事務(wù)數(shù)據(jù)庫DB，去除1-LTWUI

2. 將調(diào)整后的事務(wù)數(shù)據(jù)庫轉(zhuǎn)為位圖表示法的位圖矩陣

3. FORi從1到SNDO

4. | 生成一個隨機數(shù)numi

5. | 生成一個編碼向量Veci并通過算法2將向量中numi個位設(shè)置為1

6. | IFnumi>1 THEN

7. | | 調(diào)用算法1生成新的編碼向量Veci

8. | END IF

9. END FOR

10.RETURN 初始種群

END

3.3 HUIM-IPSO算法設(shè)計及演示

3.3.1 算法設(shè)計

算法4第1行調(diào)用種群初始化算法3.第2行將初始迭代次數(shù)iter設(shè)為1.第3行將所有粒子經(jīng)歷過的最好的位置gbest設(shè)為空集.第4行將所有高效用項集的集合SHUI設(shè)為空集.第5-22行在循環(huán)中通過一個種群到下一個種群的迭代挖掘所有的高效用項集.第6-17行，種群中所有的粒子都需要進行效用值的檢查.第7-9行，當(dāng)?shù)螖?shù)為1，種群中的粒子pi會被賦值給pbesti.第10行確定粒子pi對應(yīng)的項集.函數(shù)IS通過項目i在粒子pi中對應(yīng)的位置是否為1，返回相應(yīng)的項集.第11-13行，產(chǎn)生的粒子表示的是高效用項集并且該高效用項集還沒有被發(fā)現(xiàn)過，就記錄下這個高效用項集.第14-16行更新當(dāng)前粒子經(jīng)歷過的最好的位置.第18行記錄下當(dāng)前種群經(jīng)歷過的最好的位置.第19行通過算法2在當(dāng)前種群的SHUI中選擇下一代種群的初始優(yōu)化值.第20行通過調(diào)用算法5來生成下一個種群.第21行更新迭代次數(shù).最后，在第23行輸出SHUI.

算法4.HUIM-IPSO算法

輸入：事務(wù)數(shù)據(jù)庫DB；效用閾值minutil；最大迭代次數(shù)max_iter

輸出：高效用項集HUI

BEGIN

1.調(diào)用算法3，得到初始種群

2.iter=1

3.gbest=Φ

4.SHUI=Φ

5.WHILEiter

6.| FORi從1到SNDO

7.| | IFiter==1 THEN

8.| | |pbesti=pi

9.| | END IF

10.| |X=IS(pi) //粒子pi對應(yīng)的項集X

11.| | IFu(X)≥minutil∧X?SHUITHEN

12.| | |X→SHUI

13.| | END IF

14.| | IFu(X)>u(pbesti) THEN

15.| | |pbesti=pi

16.| | END IF

17.| END FOR

18.| 將SN個粒子中效用值最大的添加到gbest

19.| 用算法2在SHUI中選擇下一代種群的初始優(yōu)化值

20.| 調(diào)用算法5

21.|iter++

22.END WHILE

23.RETURNSHUI

END

生成下一個種群時，HUIM-IPSO算法將公式(9)改為公式(16)來生成編碼向量中需要改變的位置.

vi=vi1+vi2+vi3

(16)

式中，vi1總是設(shè)為1；vi2和vi3分別由公式(17)和公式(18)給出.

vi2=?|BitDiff(pi，pbesti)|·r1」

(17)

vi3=?|BitDiff(pi，gbesti)|·r2」

(18)

公式(17)和公式(18)中，r1和r2是兩個隨機數(shù)；vi1表示隨機接近最優(yōu)值；vi2表示根據(jù)粒子pi和它之前經(jīng)歷過的最好位置的差異接近最優(yōu)值；vi3表示根據(jù)粒子pi和所有粒子經(jīng)歷過的最好位置的差異接近最優(yōu)值.其中兩個編碼向量之間的差異BitDiff，由公式(12)給出.

算法5描述了生成下一個種群的流程.第2-6行，首先通過反碼運算隨機改變粒子pi的編碼向量中一個位置；然后通過反碼運算隨機改變粒子pi的編碼向量中vi2個位置；最后通過反碼運算隨機改變粒子pi的編碼向量中vi3個位置.第7行，調(diào)用子算法1確保生成的粒子真實存在.

算法5.生成下一代種群

輸入：種群

輸出：下一個種群

BEGIN

1.FOR 種群中的每一個粒子piDO

2.| 隨機選擇粒子pi的編碼向量中一個位置，對其進行反碼運算

3.| 通過公式(16)計算粒子pi的vi2

4.| 隨機選擇粒子pi的編碼向量中vi2個位置，對其進行反碼運算

5.| 通過公式(17)計算粒子pi的vi3

6.| 隨機選擇粒子pi的編碼向量中vi3個位置，對其進行反碼運算

7.| 調(diào)用算法1生成新的編碼向量pi

8.END FOR

9.RETURN 下一個種群

END

3.3.2 算法演示

使用表1和表2的事務(wù)數(shù)據(jù)庫來演示HUIM-IPSO算法.假設(shè)效用閾值minutil=115，表4給出了去除1-LTWUI并轉(zhuǎn)化為位圖矩陣的事務(wù)數(shù)據(jù)庫.同時，假設(shè)種群的規(guī)模SN為3.由于1-HTWUI的個數(shù)為5，粒子經(jīng)過編碼得到編碼向量有5個比特位.首先，將SHUI初始化為空集.為了生成第1個粒子，先隨機生成一個數(shù)表示粒子的編碼向量中1的個數(shù).其次，使用公式(15)確定粒子的編碼向量中哪些位置設(shè)為1.再次，假設(shè)第1個粒子對應(yīng)的編碼向量為“11110”，使用同樣的方式可以得到另外兩個粒子對應(yīng)的編碼向量.最后，假設(shè)第1個種群的三個粒子的編碼向量如圖1所示.

從圖1中，得到第一個粒子對應(yīng)的項集為{b，c，d，e}.根據(jù)算法3，RV被初始化為Bit(b).RV∩Bit(c)=0100011011∩1010100101=0000000001，由于結(jié)果是期望編碼向量，RV更新為0000000001.下一步，RV∩Bit(d)=0000000000，結(jié)果為非期望編碼向量，所以從p1中刪除項目d，同時RV保留原來的值0000000001.接下來，RV∩Bit(e)=0000000001，由于結(jié)果是一個期望編碼向量，最終RV=0000000001.最后，p1變成11010代表項集{b，c，e}被包含在事務(wù)T10中.因為u({b，c，e})=68

圖1 初始粒子的編碼向量 圖2 第1個種群

Fig.1 Encoding vector of initial particles Fig.2 First population

類似的，p2也是期望編碼向量，表示項集{b，d，e}.項集{b，d，e}出現(xiàn)在事務(wù)T2和T7，同時u({b，d，e})=166≥minutil，得到SHUI={{b，d，e}：166}，其中冒號后面的數(shù)字表示項集的效用值.最后，p3代表項集{c，e}且不是一個高效用項集，SHUI保持不變.到目前為止，得到的第一個種群如圖2所示.

由于是第1個種群，pbesti和粒子pi是一樣的，即pbest1=11010，pbest2=10110，pbest3=01010.接下來，gbest是所有粒子中效用值最大的那個，這里gbest就是10110.

通過考慮粒子p1，演示如何生成下一個種群.隨機選擇粒子中的第5位，讓它從0變成1，p1變成11011.假設(shè)隨機數(shù)r1為0.5，BitDiff(p1，pbest1)={5}，進一步v12=?1·0.5」=0，p1仍然保留11011.接下來，隨機生成r2為0.8，BitDiff(p1，gbest)={2，3，5}，進一步v13=?3·0.8」=2.因此，需要使用反碼運算隨機改變p1的兩個位值.假設(shè)隨機選擇了p1的第2位和第3位，那么第2位從1變到0，第3位從0變到1，得到新的p1為101111，表示項集{b，d，e，f}.由于p1是一個期望編碼向量，并且u({b，d，e，f})=66

使用同樣的方法，也可以得到p2和p3的值.經(jīng)過第2次迭代，假設(shè)SHUI={{b，d，e}：166，{b，e}：222}，pbest1=11010，pbest2=10110，pbest3=10010，而gbest=10010.

在標(biāo)準(zhǔn)粒子群優(yōu)化算法中，由于項集{b，e}是效用值最大的項集，它的編碼向量10010會作為下一代種群的初始優(yōu)化值.HUIM-IPSO算法中，項集{b，d，e}的編碼向量10110也可能被選為下一代種群的初始優(yōu)化值，并且它被選中的概率為166 /(166 + 222)≈0.428.

最后上面的過程一直重復(fù)直到達到最大迭代次數(shù).

3.4 時間復(fù)雜度和收斂性分析

HUIM-IPSO算法的時間復(fù)雜度，與傳統(tǒng)的PSO算法時間復(fù)雜度一致.假設(shè)PSO算法中粒子的數(shù)量為m，迭代次數(shù)為N，每個粒子每一次迭代需要的運算時間為T.算法總的運行時間為m×N×T.

算法通過輪盤賭選擇法在當(dāng)前代種群的高效用項集中以一定概率選擇下一代種群的初始優(yōu)化值.該方法增加了種群的多樣性，使得算法在每一次迭代中能夠挖掘出更多的高效用項集.同時，算法通過非期望編碼向量修剪策略刪除了在數(shù)據(jù)庫中不存在的項集，避免了算法去探索這些項集，進一步提高了算法挖掘出高效用項集的概率.因此在有限的時間內(nèi)，算法能夠挖掘出更多的高效用項集，算法挖掘高效用項集的收斂速度更快.

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

4.1 實驗環(huán)境配置及編程語言

實驗在Windows10操作系統(tǒng)，CPU AMD FX-8300八核 @3.3GH和內(nèi)存 8GB下用JAVA語言實現(xiàn).

4.2 實驗數(shù)據(jù)集

實驗中，共使用了4個公開的真實數(shù)據(jù)集retail[12]，foodmart[13]，mushroom[14]和chess[15].真實數(shù)據(jù)集的有關(guān)信息如表5所示.其中，事務(wù)數(shù)據(jù)庫的密度表示事務(wù)平均包含的項目數(shù)量與數(shù)據(jù)庫項目總數(shù)的比值.事務(wù)數(shù)據(jù)庫的密度也代表數(shù)據(jù)的稀疏性.

表5 幾個真實事務(wù)數(shù)據(jù)庫的數(shù)據(jù)統(tǒng)計

retail是稀疏的數(shù)據(jù)集，它來自比利時的一個匿名零售商店.這個數(shù)據(jù)集中包含了88162個不同的事務(wù)和16470個不同的項目.foodmart是稀疏的數(shù)據(jù)集，包含零售商店4141個顧客的交易記錄，具有1559個不同的項目.mushroom是一個來自奧杜邦協(xié)會北美蘑菇野外指南的數(shù)據(jù)集，包含8124個記錄和119個不同的項目.chess是University of California Irvine(UCI)中的chess數(shù)據(jù)集經(jīng)過改進得到的，共包含了3196個事務(wù)和46086個不同的項目.

4.3 HUIM-IPSO算法挖掘高效用項集的對比實驗

本小節(jié)共進行了兩組實驗.第1組實驗，測試了HUIM-IPSO算法、HUIM-BPSO算法和HUPE-GRAM算法在不同數(shù)據(jù)集上挖掘出的高效用項集數(shù)量.第2組實驗，測試了HUIM-IPSO算法、HUIM-BPSO算法和HUPE-GRAM算法在不同數(shù)據(jù)集上挖掘高效用項集的收斂速度.

4.3.1 挖掘出的高效用項集數(shù)量

實驗1中的相關(guān)參數(shù)由表6給出.在所有數(shù)據(jù)集上不斷減小效用閾值，運行HUIM-IPSO算法、HUIM-BPSO算法和HUPE-GRAM算法.各算法挖掘出的高效用項集數(shù)量由表7-表10給出.

表6 實驗1算法參數(shù)

表7 在chess數(shù)據(jù)集上挖掘出的高效用項集數(shù)量

表8 在mushroom數(shù)據(jù)集上挖掘出的高效用項集數(shù)量

表9 在foodmart數(shù)據(jù)集上挖掘出的高效用項集數(shù)量

表10 在retail數(shù)據(jù)集上挖掘出的高效用項集數(shù)量

觀察表7-表10，發(fā)現(xiàn)在各個效用閾值下，HUIM-IPSO算法挖掘出高效用項集的數(shù)目都是最多的，HUIM-BPSO算法次之，最后是HUPE-GRAM算法.表9中發(fā)現(xiàn)在foodmart數(shù)據(jù)集上HUIM-BPSO算法和HUPE-GRAM算法都不能在有效時間內(nèi)挖掘出任何高效用項集，HUIM-IPSO算法仍然能挖掘出大量高效用項集.表10中發(fā)現(xiàn)所有的算法都不能挖掘出任何高效用項集.因此HUIM-IPSO算法相較于HUPE-GRAM算法和HUIM-BPSO算法，能夠在規(guī)定的時間內(nèi)挖掘出更多的高效用項集.

4.3.2 挖掘高效項集的收斂性

實驗2比較了不同算法的收斂速度.實驗2設(shè)定使用相同的效用閾值來挖掘同一數(shù)據(jù)集中的高效用項集，迭代次數(shù)從200-2000次不斷增大.實驗參數(shù)由表11和表12給出.實驗2結(jié)果如圖3所示.

表11 實驗2算法參數(shù)

表12 實驗2不同數(shù)據(jù)集使用的效用閾值

圖3 挖掘不同數(shù)據(jù)集的收斂性

通過觀察圖3，發(fā)現(xiàn)HUIM-IPSO算法能夠通過較少的迭代次數(shù)，挖掘出更多的高效用項集.其他算法挖掘高效用項集的數(shù)量要么一直很小，要么隨著迭代次數(shù)的增加挖掘高效用項集的數(shù)量會產(chǎn)生較大波動.該組實驗結(jié)果說明，HUIM-IPSO算法能夠在各種數(shù)據(jù)集上很好地挖掘出高效用項集并且具有很好的收斂性.

4.4 實驗小結(jié)

實驗顯示HUIM-IPSO算法能夠通過較少的迭代次數(shù)挖掘出更多的高效用項集，算法有很好的收斂性.算法使用了輪盤賭選擇法選擇下一代種群的優(yōu)化值.說明隨機選擇種群的初始優(yōu)化值，能更加有效地遍歷搜索空間.因此該方法提高了粒子群優(yōu)化中種群的多樣性，使得算法能夠在更少的迭代次數(shù)中挖掘出更多的高效用項集.

5 結(jié) 論

本文針對基于粒子群優(yōu)化的高效用項集挖掘算法在實際應(yīng)用中存在的問題和不足，針對性地提出了一些新的思路和方法.本文的主要貢獻如下.

提出了一種改進粒子群優(yōu)化的高效用項集挖掘算法—HUIM-IPSO算法.算法使用了位圖矩陣來表示事務(wù)數(shù)據(jù)庫，使用了非期望編碼向量修剪策略去除在事務(wù)數(shù)據(jù)庫中不存在的項集，加快了項集的挖掘速度.算法還通過輪盤賭選擇法在當(dāng)前代種群的高效用項集中以一定概率選擇下一代種群的優(yōu)化值，增加了種群的多樣性.這些策略最終使得算法相比HUPE-GRAM算法和HUIM-BPSO算法有更高的挖掘效率和更快的收斂速度.