HUIM-IPSO：一個改進的粒子群優化高效用項集挖掘算法

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

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

2(北京聯合大學 機器人學院，北京 100101)

E-mail：wcw@ysu.edu.cn

1 引 言

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

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

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

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

2 高效用項集挖掘和粒子群優化

2.1 高效用項集挖掘

令I={i1，i2，…，in}是一個有限的項目集合.事務數據庫DB由1個事務表和1個外部效用表構成.事務表由多個事務{T1，T2，…，Tn}構成，其中每個事務Tc?I，同時每一個事務Tc都有唯一的標識符Tid.外部效用表則保存了每個項目的單位利潤或者重要度.

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

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

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

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

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

(1)

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

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

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

(2)

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

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

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

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

(3)

式中，X表示事務Tc中的項集.

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

表1 事務信息

表2 項目的外部效用

定義5.在事務數據庫中項集總效用大于等于效用閾值的項集，稱為高效用項集.記為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.

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

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

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

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

(5)

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

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

表3 事務效用

定義7.事務數據庫中，經常會出現多個事務包含某個項集，這些事務的效用加和稱為某項集的事務加權效用.記為TWU(X)，如式(6)所示.

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

(6)

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

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

(7)

LTWUI={X|TWU(X)

(8)

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

事務加權效用具有3個重要的性質.

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

性質2.設項集X、Y，如果X?Y，那么有TWU(X)≥TWU(Y).這說明事物加權效用是反單調的.

根據定義2，性質1和性質2是顯然成立的.

性質3.設項集X，如果TWU(X)

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

2.2 粒子群優化

1995年，Eberhart和Kennedy提出了粒子群優化算法.

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

(9)

(10)

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

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

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

3 改進的粒子群優化高效用項集挖掘算法

3.1 算法總體思想

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

(11)

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

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

3.2.1 位圖表示法

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

BitDiff(Veci，Vecj)=

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

(12)

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

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

(13)

在公式(13)中，如果項目ik在事務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的示例中，設置效用閾值minutil=115.如表4所示，給出了由位圖矩陣表示的整理之后的事務數據庫.

表4 事務數據庫的位圖表示

3.2.2 項集修剪策略

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

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

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

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

輸出：期望編碼向量PEV

BEGIN

1. 計算Vec中1的數量，記為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中對應的ik從1變成0

9. | END IF

10.| RV = RV′

11.END FOR

12.RETURN RV

END

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

3.2.3 輪盤賭選擇法

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

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

算法2.輪盤賭選擇法

輸入：種群中的每個粒子

輸出：被選中的粒子RES

BEGIN

1. 計算出種群中個體的適應值fitnessi

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

3.RES=Φ

5. FORk從1到種群規模SNDO

6. | 在[0，1]區間內產生一個服從均勻分布的隨機數r

7. | IFqk-1

8. | | 個體k→RES

9. | END

10.END

11.RETURNRES

END

3.2.4 種群初始化

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

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

(15)

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

算法3.種群初始化

輸入：事務數據庫DB；種群包含的粒子個數SN；

輸出：初始種群

BEGIN

1. 掃描事務數據庫DB，去除1-LTWUI

2. 將調整后的事務數據庫轉為位圖表示法的位圖矩陣

3. FORi從1到SNDO

4. | 生成一個隨機數numi

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

6. | IFnumi>1 THEN

7. | | 調用算法1生成新的編碼向量Veci

8. | END IF

9. END FOR

10.RETURN 初始種群

END

3.3 HUIM-IPSO算法設計及演示

3.3.1 算法設計

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

算法4.HUIM-IPSO算法

輸入：事務數據庫DB；效用閾值minutil；最大迭代次數max_iter

輸出：高效用項集HUI

BEGIN

1.調用算法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對應的項集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中選擇下一代種群的初始優化值

20.| 調用算法5

21.|iter++

22.END WHILE

23.RETURNSHUI

END

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

vi=vi1+vi2+vi3

(16)

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

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

(17)

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

(18)

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

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

算法5.生成下一代種群

輸入：種群

輸出：下一個種群

BEGIN

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

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

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

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

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

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

7.| 調用算法1生成新的編碼向量pi

8.END FOR

9.RETURN 下一個種群

END

3.3.2 算法演示

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

從圖1中，得到第一個粒子對應的項集為{b，c，d，e}.根據算法3，RV被初始化為Bit(b).RV∩Bit(c)=0100011011∩1010100101=0000000001，由于結果是期望編碼向量，RV更新為0000000001.下一步，RV∩Bit(d)=0000000000，結果為非期望編碼向量，所以從p1中刪除項目d，同時RV保留原來的值0000000001.接下來，RV∩Bit(e)=0000000001，由于結果是一個期望編碼向量，最終RV=0000000001.最后，p1變成11010代表項集{b，c，e}被包含在事務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}出現在事務T2和T7，同時u({b，d，e})=166≥minutil，得到SHUI={{b，d，e}：166}，其中冒號后面的數字表示項集的效用值.最后，p3代表項集{c，e}且不是一個高效用項集，SHUI保持不變.到目前為止，得到的第一個種群如圖2所示.

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

通過考慮粒子p1，演示如何生成下一個種群.隨機選擇粒子中的第5位，讓它從0變成1，p1變成11011.假設隨機數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的兩個位值.假設隨機選擇了p1的第2位和第3位，那么第2位從1變到0，第3位從0變到1，得到新的p1為101111，表示項集{b，d，e，f}.由于p1是一個期望編碼向量，并且u({b，d，e，f})=66

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

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

最后上面的過程一直重復直到達到最大迭代次數.

3.4 時間復雜度和收斂性分析

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

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

4 實驗結果與分析

4.1 實驗環境配置及編程語言

實驗在Windows10操作系統，CPU AMD FX-8300八核 @3.3GH和內存 8GB下用JAVA語言實現.

4.2 實驗數據集

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

表5 幾個真實事務數據庫的數據統計

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

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

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

4.3.1 挖掘出的高效用項集數量

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

表6 實驗1算法參數

表7 在chess數據集上挖掘出的高效用項集數量

表8 在mushroom數據集上挖掘出的高效用項集數量

表9 在foodmart數據集上挖掘出的高效用項集數量

表10 在retail數據集上挖掘出的高效用項集數量

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

4.3.2 挖掘高效項集的收斂性

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

表11 實驗2算法參數

表12 實驗2不同數據集使用的效用閾值

圖3 挖掘不同數據集的收斂性

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

4.4 實驗小結

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

5 結 論

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

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