基于改進(jìn)的BPSO算法的關(guān)聯(lián)規(guī)則挖掘

（江南大學(xué) 無錫 214122）

1 引言

關(guān)聯(lián)規(guī)則指數(shù)據(jù)庫中超過指定最小支持度和最小置信度的項目的集合，作為數(shù)據(jù)挖掘的重要組成部分它一直是學(xué)者的研究熱點［1］。隨著挖掘問題變得越來越復(fù)雜，諸如Apriori算法與FP-growth算法等傳統(tǒng)算法出現(xiàn)了缺點，其中最典型的是由大量候選項集和復(fù)雜的數(shù)據(jù)結(jié)構(gòu)所造成的時間和內(nèi)存的成本，導(dǎo)致挖掘效率較低［2］。因此許多學(xué)者開始使用啟發(fā)式算法，粒子群優(yōu)化算法（PSO）是應(yīng)用較為廣泛的算法之一［3］。

有許多研究將啟發(fā)式算法應(yīng)用于關(guān)聯(lián)規(guī)則挖掘。例如，Chen等使用PSO算法從高維數(shù)據(jù)集中挖掘關(guān)聯(lián)規(guī)則［4］，Rom提出的基于遺傳算法的關(guān)聯(lián)規(guī)則可避免挖掘過程中發(fā)現(xiàn)的無用個體［5］，BADA等融合了PSO算法和蟻群算法（ACO），將事務(wù)數(shù)據(jù)轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)后，從數(shù)據(jù)集中挖掘頻繁項集［6］，Kuo等使用PSO算法快速有效計算出關(guān)聯(lián)規(guī)則的最小支持和置信度［7］。

然而，大多數(shù)改進(jìn)的PSO算法重點考慮粒子全局和局部搜索能力，而忽略了粒子種群和搜索范圍帶來的影響。因此，本文提出了一種改進(jìn)的二進(jìn)制粒子群優(yōu)化算法（GRBPSO），根據(jù)適應(yīng)度函數(shù)對粒子初始種群進(jìn)行預(yù)處理，并以頻繁項集的性質(zhì)為依據(jù)對粒子搜索空間進(jìn)行縮減，減少算法運行時間。

2 基本概念

2.1 頻繁項集

頻繁項集的有關(guān)定義為I={i1,i2,…,im}是m個不同項目的集合，每個ik稱為一個項目［8］。數(shù)據(jù)集D={t1,t2,…,tn}是n個不同事務(wù)的集合，每個tk稱為一個事務(wù)，其中tk?I。集合X?I稱為項集，|X|表示項集中的項目數(shù)，長度為1的項集稱為1項集。項集X的支持度表示為sup（X），其含義是項集X在數(shù)據(jù)集D中出現(xiàn)的實際頻率，若sup(X)≥最小支持度(min_sup)，則稱項集X是頻繁項集。

頻繁項集挖掘的目標(biāo)是根據(jù)給定的最小支持度（min_sup）挖掘出所有的頻繁項集。根據(jù)以上描述，可推出性質(zhì)1。如下所示：

性質(zhì)1：?Xi?X?sup(Xi)≥sup(X)

因此，當(dāng)Xi?X時，若Xi不是k維頻繁項集的子集，則項集X也不是k維頻繁項集的子集。

2.2 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是形如A?B的蘊含式［10］，其中A?I，B?I，并且A∩B=?。

一般使用三個指標(biāo)來度量關(guān)聯(lián)規(guī)則，分別是支持度（support）、置信度（confidence）和提升度（lift）［11］。根據(jù)這三個指標(biāo)可以篩選出滿足條件的關(guān)聯(lián)規(guī)則。

以A?B這個關(guān)聯(lián)規(guī)則為例來說明：

支持度（support）：表示同時使用A、B的人數(shù)占所有用戶數(shù)的比例。如果用P（A）表示使用A的用戶比例，那么support=P（A&B）。

置信度（confidence）：表示使用A的用戶中同時使用B的比例，即同時使用A和B的人占使用A的人的比例，即confidence=P（A&B）/P（A）。

提升度（lift）：表示“使用A的用戶中同時使用B的比例”與“使用B的用戶比例”的比值，即：lift=（P（A&B）/P（A））/P（B），提升度反映了關(guān)聯(lián)規(guī)則中的A與B的相關(guān)性，提升度大于1且越高表明正相關(guān)性越高，提升度小于1且越低表明負(fù)相關(guān)性越高，提升度=1表明沒有相關(guān)性［12］。

2.3 二進(jìn)制粒子群優(yōu)化算法（BPSO）

PSO算法在實現(xiàn)過程中隨機(jī)選取一群粒子作為初始粒子群，搜索空間中的每個粒子都是一個可能解，算法通過迭代找到最優(yōu)解。在算法迭代過程中粒子以兩個極值為依據(jù)來更新自己，第一個極值稱為個體極值，是粒子個體找到的最優(yōu)解；第二個極值稱為全局極值，是整個種群目前找到的最優(yōu)解。

離散二進(jìn)制粒子群算法是J.Kennedy和R.C.Eberhart在1997年提出的［13］。PSO算法設(shè)計之初是為了優(yōu)化連續(xù)函數(shù)的，但實際生活中待解決的問題大多是基于離散空間上的組合優(yōu)化問題，因此提出BPSO算法以解決這一問題。

BPSO算法在離散粒子群算法基礎(chǔ)上，約定位置向量、速度向量均由0、1值構(gòu)成［14］。粒子根據(jù)式（1）更新自己的速度，根據(jù)式（2）和式（3）更新自己的位置，式（2）為映射函數(shù)：

其中，Vi為第i粒子的速度，pi為個體極值，G為全局極值，ω為慣性因子，C1,C2為學(xué)習(xí)因子，φ1和φ2為［0，1］之間的隨機(jī)數(shù)。為在d維空間中第i個粒子軌跡當(dāng)前為0的概率，為在d維空間中第i個粒子位置變化的絕對概率，rand（）為［0，1］之間的隨機(jī)數(shù)。

3 GRBPSO算法

3.1 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用來評價給出的候選解即粒子的好壞的［15］。在PSO算法中，適應(yīng)度函數(shù)往往具有驅(qū)動粒子前進(jìn)的作用，在搜索空間中指出粒子的前進(jìn)趨勢。適應(yīng)度函數(shù)的設(shè)計依賴于實際問題，針對不同問題，適應(yīng)度函數(shù)的設(shè)計也不盡相同。

在關(guān)聯(lián)規(guī)則的研究中支持度是評價一組關(guān)聯(lián)規(guī)則是否有效的基礎(chǔ)指標(biāo)。支持度代表了項目重復(fù)出現(xiàn)在一組事務(wù)數(shù)據(jù)庫中的次數(shù)?，F(xiàn)實中數(shù)據(jù)庫內(nèi)的數(shù)據(jù)往往具有多樣性和復(fù)雜性，為了在實際項目中挖掘有意義的關(guān)聯(lián)規(guī)則，本文算法將粒子出現(xiàn)的實際次數(shù)作為其適應(yīng)度值，粒子的適應(yīng)度函數(shù)如式（4）所示：

其中，support(i)為粒子種群中粒子的實際支持度也即實際出現(xiàn)頻率。

在GRBPSO算法中，個體極值指的是粒子群中各個粒子在此次迭代條件下的支持度，全局極值指的是在此次迭代條件下整個種群中全部粒子的最優(yōu)支持度，算法在每次迭代中修改這兩個極值，假設(shè)某個粒子的個體極值不小于最小支持度，則將該粒子列為候選項集。

3.2 初始粒子群預(yù)處理

在頻繁項集挖掘過程中數(shù)據(jù)集中可能存在某些項目出現(xiàn)頻率較低的現(xiàn)象，這就可能導(dǎo)致隨機(jī)選取的粒子種群質(zhì)量不高，進(jìn)而影響挖掘結(jié)果及挖掘效率。在GRBPSO算法中，首先對初始粒子群進(jìn)行預(yù)處理，保證一定比例的粒子具有合理的初始適應(yīng)度。

對初始粒子群進(jìn)行預(yù)處理的方式是將種群中出現(xiàn)頻率較低的粒子位置設(shè)置為0，首先以確保初始粒子群具有適當(dāng)?shù)倪m應(yīng)度，提高初始種群的質(zhì)量；同時在二進(jìn)制數(shù)據(jù)集中也可減少粒子的數(shù)量和空間維數(shù)。在GRBPSO算法中，結(jié)合關(guān)聯(lián)規(guī)則的相關(guān)定義，可根據(jù)用戶設(shè)置的最小支持度值修改對應(yīng)粒子的位置值，修改方式為若粒子的出現(xiàn)頻率即初始適應(yīng)度值小于最小支持度，則將該粒子的位置更新為0。

3.3 縮減搜索空間

利用BPSO算法在大數(shù)據(jù)集中挖掘關(guān)聯(lián)規(guī)則意味著搜索空間較大，而搜索空間對算法運行效率有著重要的影響，因此，本文設(shè)計一種縮減搜索空間的優(yōu)化策略，減少搜索空間，提高算法運行效率。

假設(shè)GRBPSO算法在發(fā)現(xiàn)頻繁項集階段，G為當(dāng)前全局極值。在此期間，任一支持度小于G的項目將會被剪枝，即?i∈I，若sup(i)＜sup(G)，則項目i被剪枝。于是，?i∈I且sup(i)＜sup(G)，從性質(zhì)1可知，?X?I且i∈X，可推出sup(X)＜sup(G) 。也就是說，若項集中含項目i，則需更新該項集，將其中的項目i剪枝。

4 實驗及分析

為了驗證GRBPSO算法的正確性及有效性，本文對大量數(shù)據(jù)集進(jìn)行了實驗，并給出在6個數(shù)據(jù)集上的實驗結(jié)果及分析比較。實驗環(huán)境為2.10GHz AMD R5 CPU，8G內(nèi)存和Windows 10操作系統(tǒng)，算法在VS2015平臺上采用C++語言編程實現(xiàn)。數(shù)據(jù)集分別為Connect、Mushroom、Retail、Pumsb、Ko?sarak、BMS-POS，數(shù)據(jù)集下載地址為http：//fimi.uantwerpen.be/data/。數(shù)據(jù)集展示如表1所示。

表1 實驗數(shù)據(jù)集

4.1 實驗一

在實驗一中，從種群規(guī)模方面對GRBPSO算法與BPSO算法進(jìn)行比較。算法的參數(shù)設(shè)置為最大迭代次數(shù)N=10，慣性因子ω=0.2，學(xué)習(xí)因子C1=C2=1，粒子最大速度為2。算法中的最小支持度設(shè)置為0.3，最小置信度（min_conf）設(shè)置為0.6，最小提升度（lift）設(shè)置為4。實驗結(jié)果如圖1所示。

圖1 算法運行時間對比

圖1表示在種群規(guī)模為可變因素的情況下兩種算法在6個數(shù)據(jù)集上挖掘關(guān)聯(lián)規(guī)則的時間對比。由圖1可知，兩個算法在種群規(guī)模不斷增加的情況下，運行時間也隨之增加，原因是種群規(guī)模的擴(kuò)大導(dǎo)致算法中對適應(yīng)度的計算變得復(fù)雜，進(jìn)而影響算法的運行時間。但由圖1可知本文算法的運行時間始終小于BPSO算法，并隨著規(guī)模變大這種優(yōu)勢愈加明顯，因此充分說明本文算法在種群規(guī)模變化的前提下是高效的。

4.2 實驗二

在實驗二中，從迭代次數(shù)上對GRBPSO算法與BPSO算法進(jìn)行比較。算法的參數(shù)設(shè)置為種群規(guī)模K=80，慣性因子ω=0.2，學(xué)習(xí)因子C1=C2=1，粒子最大速度為2。算法中的最小支持度設(shè)置為0.3，最小置信度（min_conf）設(shè)置為0.6，最小提升度（lift）設(shè)置為4。實驗結(jié)果如圖2所示。

圖2表示在迭代次數(shù)為可變因素的情況下兩種算法在6個數(shù)據(jù)集上挖掘關(guān)聯(lián)規(guī)則的時間對比。由圖2可知，兩個算法在迭代次數(shù)的不斷增加下，運行時間也隨之增加，并由圖2可知本文算法的運行時間始終小于BPSO算法，并隨著迭代次數(shù)的變多在部分?jǐn)?shù)據(jù)集中這種優(yōu)勢愈加明顯，因此充分說明本文算法在迭代次數(shù)變化的前提下是相對高效的。這是因為大數(shù)據(jù)集導(dǎo)致搜索空間變大，GRBPSO算法在對初始種群進(jìn)行預(yù)處理時可一定程度地縮減搜索空間，并同時采用了優(yōu)化策略對搜索空間進(jìn)行裁剪，大大減少粒子的飛行空間，在一定程度上提高了關(guān)聯(lián)規(guī)則挖掘效率。

圖2 算法運行時間對比

4.3 實驗三

在實驗三中，比較GRBPSO算法與同類型算法的挖掘效果。本文以挖掘頻繁項集的數(shù)量作為參考值，同類型算法分別為PSOFIM算法［16］、GA-Apriori算法及PSO-Apriori算法［17］。根據(jù)文獻(xiàn)［17］，表2中的對比算法均為在最優(yōu)參數(shù)下算法挖掘的數(shù)量，本文算法的挖掘結(jié)果具有不確定性，原因是算法在初始種群的選擇上具有隨機(jī)性。為說明本文算法的可行性和穩(wěn)定性，本次實驗在6個數(shù)據(jù)集中均重復(fù)10次，實驗的最終數(shù)據(jù)為10次實驗的平均結(jié)果。算法的參數(shù)設(shè)置為種群規(guī)模K=80，迭代次數(shù)N=20，慣性因子ω=0.4，C1=C2=1，Vmax=3，算法的最小支持度均為0.2，實驗對比結(jié)果如表2所示。

表2 各算法挖掘到的頻繁項集數(shù)量（/個）

由表2可知，以數(shù)據(jù)集Retail為例本文算法的頻繁項集挖掘數(shù)量少于其他同類型的3個算法，但在其他數(shù)據(jù)集中本文算法表現(xiàn)較為優(yōu)越，尤其是在Connect數(shù)據(jù)集和Mushroom數(shù)據(jù)集中表現(xiàn)突出。在Retail數(shù)據(jù)集中本文算法挖掘數(shù)量少于其他3種算法是由Retail數(shù)據(jù)集的特征引起的，在Retail數(shù)據(jù)集中事務(wù)數(shù)據(jù)庫的平均長度較小且數(shù)據(jù)分布較為零散，數(shù)據(jù)集中事務(wù)屬性數(shù)較少，在進(jìn)行頻繁項集挖掘時本文算法對初始粒子群的選擇是具有概率性的，因此在預(yù)處理過程中粒子位置為0的概率變大，導(dǎo)致挖掘結(jié)果不佳。但從整體來看，本文算法在大數(shù)據(jù)上挖掘頻繁項集是可行的，并且挖掘結(jié)果也是可觀的。

5 結(jié)語

本文提出了一種基于改進(jìn)的二進(jìn)制粒子群優(yōu)化算法的關(guān)聯(lián)規(guī)則挖掘方法。首先結(jié)合實際情況，將粒子支持度作為GRBPSO算法的適應(yīng)度函數(shù)；然后根據(jù)最小支持度對初始種群進(jìn)行處理，提高初始種群質(zhì)量；最后根據(jù)優(yōu)化策略對搜索空間進(jìn)行縮減。通過實驗證明，本文提出的GRBPSO算法在挖掘關(guān)聯(lián)規(guī)則上是可行的且高效的。