王常武，尹松林，劉文遠(yuǎn)，魏小梅，鄭紅軍，楊繼萍

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

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

E-mail：wcw@ysu.edu.cn

1 引 言

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

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

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

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

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

2.1 高效用項(xiàng)集挖掘

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

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

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

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

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

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

(1)

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

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

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

(2)

它表示項(xiàng)集X中每個(gè)項(xiàng)目i的效用加和.

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

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

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

(3)

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

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

表1 事務(wù)信息

表2 項(xiàng)目的外部效用

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

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

(4)

式中，minutil表示效用閾值.

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

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

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

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

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

(5)

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

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

表3 事務(wù)效用

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

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

(6)

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

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

(7)

LTWUI={X|TWU(X)

(8)

式中，minutil表示效用閾值.包含k個(gè)項(xiàng)目的HTWUI和LTWUI分別記為k-HTWUI和k-LTWUI.

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

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

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

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

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

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

2.2 粒子群優(yōu)化

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

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

(9)

(10)

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

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

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

3 改進(jìn)的粒子群優(yōu)化高效用項(xiàng)集挖掘算法

3.1 算法總體思想

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

(11)

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

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

3.2.1 位圖表示法

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

BitDiff(Veci，Vecj)=

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

(12)

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

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

(13)

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

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

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

(14)

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

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

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

3.2.2 項(xiàng)集修剪策略

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

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

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

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

輸出：期望編碼向量PEV

BEGIN

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

2. 用i1，i2，…，iVN表示Vec中包含的項(xiàng)目

3. RV = Bit(i1)

4. FORk從2到VNDO

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

6. | IF RV′是一個(gè)UPEV THEN

7. | | RV′ = RV

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

9. | END IF

10.| RV = RV′

11.END FOR

12.RETURN RV

END

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

3.2.3 輪盤賭選擇法

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

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

算法2.輪盤賭選擇法

輸入：種群中的每個(gè)粒子

輸出：被選中的粒子RES

BEGIN

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

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

3.RES=Φ

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

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

7. | IFqk-1

8. | | 個(gè)體k→RES

9. | END

10.END

11.RETURNRES

END

3.2.4 種群初始化

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

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

(15)

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

算法3.種群初始化

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

輸出：初始種群

BEGIN

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

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

3. FORi從1到SNDO

4. | 生成一個(gè)隨機(jī)數(shù)numi

5. | 生成一個(gè)編碼向量Veci并通過算法2將向量中numi個(gè)位設(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è)計(jì)及演示

3.3.1 算法設(shè)計(jì)

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

算法4.HUIM-IPSO算法

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

輸出：高效用項(xiàng)集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對(duì)應(yīng)的項(xià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個(gè)粒子中效用值最大的添加到gbest

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

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

21.|iter++

22.END WHILE

23.RETURNSHUI

END

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

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

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

算法5.生成下一代種群

輸入：種群

輸出：下一個(gè)種群

BEGIN

1.FOR 種群中的每一個(gè)粒子piDO

2.| 隨機(jī)選擇粒子pi的編碼向量中一個(gè)位置，對(duì)其進(jìn)行反碼運(yùn)算

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

4.| 隨機(jī)選擇粒子pi的編碼向量中vi2個(gè)位置，對(duì)其進(jìn)行反碼運(yùn)算

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

6.| 隨機(jī)選擇粒子pi的編碼向量中vi3個(gè)位置，對(duì)其進(jìn)行反碼運(yùn)算

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

8.END FOR

9.RETURN 下一個(gè)種群

END

3.3.2 算法演示

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

從圖1中，得到第一個(gè)粒子對(duì)應(yīng)的項(xià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中刪除項(xiàng)目d，同時(shí)RV保留原來(lái)的值0000000001.接下來(lái)，RV∩Bit(e)=0000000001，由于結(jié)果是一個(gè)期望編碼向量，最終RV=0000000001.最后，p1變成11010代表項(xiàng)集{b，c，e}被包含在事務(wù)T10中.因?yàn)閡({b，c，e})=68

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

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

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

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

通過考慮粒子p1，演示如何生成下一個(gè)種群.隨機(jī)選擇粒子中的第5位，讓它從0變成1，p1變成11011.假設(shè)隨機(jī)數(shù)r1為0.5，BitDiff(p1，pbest1)={5}，進(jìn)一步v12=?1·0.5」=0，p1仍然保留11011.接下來(lái)，隨機(jī)生成r2為0.8，BitDiff(p1，gbest)={2，3，5}，進(jìn)一步v13=?3·0.8」=2.因此，需要使用反碼運(yùn)算隨機(jī)改變p1的兩個(gè)位值.假設(shè)隨機(jī)選擇了p1的第2位和第3位，那么第2位從1變到0，第3位從0變到1，得到新的p1為101111，表示項(xiàng)集{b，d，e，f}.由于p1是一個(gè)期望編碼向量，并且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)化算法中，由于項(xiàng)集{b，e}是效用值最大的項(xiàng)集，它的編碼向量10010會(huì)作為下一代種群的初始優(yōu)化值.HUIM-IPSO算法中，項(xiàng)集{b，d，e}的編碼向量10110也可能被選為下一代種群的初始優(yōu)化值，并且它被選中的概率為166 /(166 + 222)≈0.428.

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

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

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

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

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

4.1 實(shí)驗(yàn)環(huán)境配置及編程語(yǔ)言

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

4.2 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

4.3 HUIM-IPSO算法挖掘高效用項(xiàng)集的對(duì)比實(shí)驗(yàn)

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

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

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

表6 實(shí)驗(yàn)1算法參數(shù)

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

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

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

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

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

4.3.2 挖掘高效項(xiàng)集的收斂性

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

表11 實(shí)驗(yàn)2算法參數(shù)

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

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

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

4.4 實(shí)驗(yàn)小結(jié)

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

5 結(jié) 論

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

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