結(jié)合變異機制和量子PSO的關(guān)聯(lián)規(guī)則挖掘算法

(1.廣東科貿(mào)職業(yè)學(xué)院 信息與自動化學(xué)院，廣東 廣州 510640；2.廣東技術(shù)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，廣東 廣州 510665；3.華南理工大學(xué) 數(shù)學(xué)學(xué)院，廣東 廣州 510641)

關(guān)聯(lián)規(guī)則挖掘是一種用來查找數(shù)據(jù)庫中的頻繁項或?qū)傩约g相關(guān)性和因果關(guān)聯(lián)的數(shù)據(jù)挖掘方法[1]。從數(shù)據(jù)庫中執(zhí)行關(guān)聯(lián)規(guī)則挖掘是一個NP完全問題，其取決于數(shù)據(jù)庫、機器學(xué)習(xí)和優(yōu)化算法的研究。

目前已有的多種關(guān)聯(lián)規(guī)則挖掘算法可以分為兩類：一是精確算法[2]，這類算法一定程度上可以獲得最優(yōu)解，但需要多次掃描數(shù)據(jù)庫，產(chǎn)生大量候選項集，對候選項集進行模式匹配時需花費大量時間[3]，如Apriori和FP-Growth算法。二是智能進化算法[4]，這類算法也能夠給出很好的解，且執(zhí)行時間會明顯縮短，例如遺傳算法、模擬退火算法等。

大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘是一個復(fù)雜的過程，使用精確算法非常昂貴，而智能進化算法在這個領(lǐng)域提供了很大的幫助。其中量子進化算法(quantum-inspired evolutionary algorithm，QEA)[5]使用量子比特作為信息的最小單元[6]進行概率表示。量子比特個體為量子比特組成的串，稱為多量子比特。量子比特個體的優(yōu)點是可以在搜索空間中以概率表示狀態(tài)的線性疊加。因此，量子比特表示法比遺傳算法中的染色體表示法具有更好的群體多樣性特征[7]。QEA中的量子門為一種變體運算符，用來使個體轉(zhuǎn)向更好的解，并最終收斂到單一最優(yōu)解[8]。量子粒子群優(yōu)化(quantum-behaved particle swarm optimization，QPSO)[9]是QEA和粒子群優(yōu)化(PSO)的混合算法，采用一種新的稱為量子角度的量子比特表達機制。并利用PSO中的位置更新機制來更新QEA中的量子比特，使其尋優(yōu)能力優(yōu)于傳統(tǒng)QEA。

基于上述分析，提出一種基于改進QPSO的關(guān)聯(lián)規(guī)則挖掘方法，并在UCI和課程成績數(shù)據(jù)集上進行了實驗驗證，結(jié)果表明，提出的方法在執(zhí)行時間和挖掘規(guī)則質(zhì)量上都具有一定的優(yōu)勢。提出方法的主要創(chuàng)新點在于：將數(shù)據(jù)實例以量子比特形式表示，構(gòu)建一個基于QEA的關(guān)聯(lián)規(guī)則挖掘基礎(chǔ)框架；使用QPSO代替QEA實現(xiàn)關(guān)聯(lián)規(guī)則挖掘，并融入變異機制和動態(tài)慣性權(quán)重形成IQPSO，以加快其收斂速度和跳出局部最優(yōu)的能力。

1 關(guān)聯(lián)規(guī)則挖掘問題描述

1.1 問題定義

關(guān)聯(lián)規(guī)則挖掘中，令I(lǐng)={i1,i2,…,im}為一組布爾型屬性，稱為項目；S={s1，s2，…,sn}為多組數(shù)據(jù)實例記錄，其中每個數(shù)據(jù)實例si∈S由I中的不同屬性構(gòu)成。數(shù)據(jù)實例si中若存在某個布爾屬性，則意味著其值為1，如果不存在，則其值為0。例如，令I(lǐng)={A,B,C}為一組布爾型屬性，S={〈A,B〉,〈C〉,〈C〉}為多組數(shù)據(jù)實例，那么多組S可以重寫為：

S={〈A=1，B=1，C=1〉,〈A=0，B=0，C=1〉,〈A=0，B=0，C=1〉}。

(1)

一個關(guān)聯(lián)規(guī)則可表示為：如果C成立，則為P。其中C為條件，P為預(yù)測，C、P?1并且C∩P=?。

本研究連接關(guān)聯(lián)規(guī)則，其中C是一個或多個條件的連接，P是一個或多個預(yù)測的連接。文中所涉及的符號有：|C|—規(guī)則C包含的數(shù)據(jù)實例數(shù)量；|P|—規(guī)則P包含的數(shù)據(jù)實例數(shù)量；|C&P|—規(guī)則C和P同時包含的數(shù)據(jù)實例數(shù)量；N—要挖掘的數(shù)據(jù)實例總數(shù)。

1.2 規(guī)則適應(yīng)度函數(shù)

關(guān)聯(lián)規(guī)則的性能通常由置信度和支持度表示，為了更好地量化規(guī)則質(zhì)量，采用文獻[10]提出的適應(yīng)度函數(shù)F來評估候選規(guī)則的質(zhì)量。定義規(guī)則支持度為滿足規(guī)則中C的數(shù)據(jù)實例的百分比，置信度b為滿足規(guī)則(IFC, THENP)的數(shù)據(jù)實例的百分比。該適應(yīng)度函數(shù)是基于信息論推導(dǎo)的，綜合考慮了置信度和支持度。定義一個J-度量Jm，計算表達式為：

(2)

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

(3)

式中:npu為潛在有用屬性的數(shù)量。如果至少存在一個數(shù)據(jù)實例在C部分和預(yù)測屬性中具有指定的A值，則認為該屬性A是潛在有用的；nr為規(guī)則中C包含的屬性總數(shù)；w1、w2為用戶自定義權(quán)重，這里分別設(shè)置為0.6和0.4；F的取值在0～1之間，值越大說明規(guī)則的質(zhì)量越好。

2 基于QEA的關(guān)聯(lián)規(guī)則挖掘

量子進化算法(QEA)與經(jīng)典進化算法(EA)類似，只是采用了量子個體來代替?zhèn)鹘y(tǒng)個體進行迭代。量子個體中使用基于量子比特的編碼方式[11-12]，即用一對復(fù)數(shù)定義一個量子比特位。這種表示方法可以表征任意的線性疊加狀態(tài)。另外，在種群更新中，根據(jù)量子的疊加特性和變遷理論，通過量子門變換來產(chǎn)生新的個體。在數(shù)據(jù)集中應(yīng)用QEA進行規(guī)則挖掘時，必須將數(shù)據(jù)實例通過量子來表示?；赒EA算法的關(guān)聯(lián)規(guī)則挖掘過程如算法1描述。

算法1：QEA關(guān)聯(lián)規(guī)則挖掘算法

輸入：實例數(shù)據(jù)集，最小置信度，支持度閾值，種群數(shù)量，最大迭代次數(shù)

輸出：一組最佳關(guān)聯(lián)規(guī)則

begin

t←0；

初始化包含多個量子比特個體Q(t)的種群；

把Q(t)投影到二進制解P(t)中；

計算P(t)的適應(yīng)度函數(shù)；

If存在關(guān)聯(lián)規(guī)則

Then從每個P(t)上生成關(guān)聯(lián)規(guī)則；

endif

存儲P(t)中的最佳解；

while(結(jié)束條件)do

t←t+1；

把Q(t-1)投影到二進制解P(t)中；

計算P(t)的適應(yīng)度函數(shù)；

If存在關(guān)聯(lián)規(guī)則

Then從每個P(t)上生成關(guān)聯(lián)規(guī)則；

使用量子門更新Q(t)；

endif

存儲P(t)中的最佳解；

enddo

end

QEA算法主要包含4個部分：

(4)

3)計算P(t)的適應(yīng)度函數(shù)：通過適應(yīng)度函數(shù)F對每個二進制解P(t)進行評估。

4)使用量子門更新Q(t)：通過量子旋轉(zhuǎn)門來更新個體角增量。

量子門U(Δθ)是一個可變運算符，可以根據(jù)具體問題進行選擇。本研究使用的量子門定義為：

(5)

式中:ξ(Δθi)=s(αi,βi)×Δθi；s(αi,βi)和Δθi分別表示旋轉(zhuǎn)方向和角度。

3 基于改進QPSO的關(guān)聯(lián)規(guī)則挖掘

3.1 QPSO算法

由于傳統(tǒng)QEA中通過量子旋轉(zhuǎn)門來更新量子角增量，操作復(fù)雜且更新角度固定，使其容易陷入局部最優(yōu)[13]。為此，Sun等[14]引入了PSO算法中的位置更新公式替代QEA中的量子旋轉(zhuǎn)門來更新角增量，形成QPSO算法。

|sin(θ)|2+|cos(θ)|2=1。

(6)

量子旋轉(zhuǎn)門變?yōu)椋?/p>

(7)

QPSO使用PSO的群智能概念，將群體中的所有多量子比特視為智能種群，即量子群。首先，QPSO找到局部最佳量子角，并從局部最佳量子角中找到全局最佳量子角。然后根據(jù)這些值，用量子角更新公式更新量子角。

基于QEA的QPSO步驟如下：

2)通過|cos(θ)2|觀察Q(t)的狀態(tài)，把Q(t)投影到二進制解P(t)。對于多量子比特中的每一比特xj，其由量子角θ與0和1之間的隨機變量得到：如果rand(0,1)>|cos(θ)|2，則生成1；否則生成0，即：

(8)

3)使用以下PSO位置更新公式替換傳統(tǒng)“量子門更新Q(t)”步驟：

(9)

3.2 改進QPSO算法(IQPSO)

為了提高QPSO算法的收斂性和跳出局部最優(yōu)的能力，分別引入動態(tài)慣性權(quán)重和變異操作對其進行改進。

3.2.1 動態(tài)慣性權(quán)重

從式(9)可以看出，慣性權(quán)重w決定了對當(dāng)前量子角度的繼承程度，傳統(tǒng)PSO中將其設(shè)置為恒定值。然而，恒定的w不能適應(yīng)動態(tài)的收斂過程。在算法搜索的前期，較大的w有利于跳出局部最優(yōu)；在搜索后期，較小的w有利于局部尋優(yōu)[15]。為此，引入了動態(tài)慣性權(quán)重，使w隨著迭代數(shù)量的增加而遞減，表示為：

(10)

式中：wmax和wmin為w的上限值和下限值，通常設(shè)定為0.9和0.4；Tmax為算法的最大迭代輪數(shù)，ite為當(dāng)前迭代輪數(shù)。

3.2.2 變異操作

QPSO算法雖然引入了PSO中的角度更新機制和動態(tài)慣性權(quán)重，但其在迭代后期的角度變化幅度越來越小，仍有可能陷入局部最優(yōu)。為此，本研究融入了一個變異機制來改進QPSO算法：當(dāng)判斷其迭代解停止不前時，啟動變異過程。

首先，建立一種機制來判斷QPSO尋優(yōu)過程是否處于停止不前狀態(tài)。本研究以全局最佳值Fgbest與平均個體最佳值Fpbest的比例關(guān)系kg-p作為判斷依據(jù)，其中設(shè)定取N=20次連續(xù)迭代中的個體最佳值來取平均。表達式如下：

(11)

如果連續(xù)N次迭代后，量子的個體最佳角度幾乎沒有改變，即kg-p趨于1，那么判斷此時的尋優(yōu)過程處于停止不前狀態(tài)。

然后，建立一種變異機制。選擇一些量子進行變異操作，根據(jù)粒子與全局最優(yōu)角度的距離作為變異概率，將遠離最優(yōu)角度的量子進行大概率變異，以提高種群跳出局部最優(yōu)的能力。其中，距離用適應(yīng)度值來表示。假設(shè)量子種群數(shù)量為M，那么各量子的變異概率

(12)

最后，通過隨機函數(shù)rand(0,1)為每個量子產(chǎn)生一個隨機值，若該值小于該量子的變異概率pi，則通過量子非門實現(xiàn)量子中1/2個量子位的變異，量子非門變異操作表示如下：

(13)

3.3 關(guān)聯(lián)規(guī)則挖掘過程

基于上述IQPSO算法，最終得到關(guān)聯(lián)規(guī)則挖掘過程如算法2所示。

算法2：IQPSO關(guān)聯(lián)規(guī)則挖掘算法

輸入：實例數(shù)據(jù)集，最小置信度，支持度閾值，種群數(shù)量M，最大迭代次數(shù)Tmax，學(xué)習(xí)因子，權(quán)重w的上限和下限值，變異概率pi

輸出：一組最佳關(guān)聯(lián)規(guī)則

begin

t←0；

初始化包含多個量子比特個體Q(t)的種群，并使用量子角編碼量子比特；

把Q(t)投影到二進制解P(t)中；

計算P(t)的適應(yīng)度函數(shù)；

If存在關(guān)聯(lián)規(guī)則

Then從每個P(t)上生成關(guān)聯(lián)規(guī)則；

endif

存儲P(t)中的最佳解；

while(結(jié)束條件)do

t←t+1；

把Q(t-1)投影到二進制解P(t)中；

計算P(t)的適應(yīng)度函數(shù)；

If存在關(guān)聯(lián)規(guī)則

Then從每個P(t)上生成關(guān)聯(lián)規(guī)則；

endif

使用包含動態(tài)w的式(12)更新Q(t)中量子角；

存儲P(t)中的最佳解；

IfN次迭代后尋優(yōu)過程處于停止不前狀態(tài)

Then計算量子變異概率，通過量子非門進行變異操作；

endif

enddo

end

4 實驗及分析

4.1 實驗設(shè)置

將提出的IQPSO關(guān)聯(lián)規(guī)則挖掘算法與文獻[16]提出的Apriori規(guī)則挖掘算法進行比較。為了體現(xiàn)IQPSO的改進效果，將其與傳統(tǒng)QPSO[9]的關(guān)聯(lián)規(guī)則算法進行比較。所有實驗均在配備Intel Core i7處理器(3.4 GHz主頻、8 G內(nèi)存)和Windows 10的PC電腦上進行。使用MATLAB編程。其中，IQPSO算法的種群數(shù)量為30，最大迭代次數(shù)設(shè)置為200次，變異概率pi=0.01。Apriori和QPSO的參數(shù)設(shè)置分別參考文獻[16]和文獻[9]。

為了驗證本文算法的有效性，選擇了一個由加州大學(xué)建立的國際標(biāo)準(zhǔn)機器學(xué)習(xí)數(shù)據(jù)庫(UCI)中的幼兒園數(shù)據(jù)集作為實驗數(shù)據(jù)集。幼兒園數(shù)據(jù)庫最初是為幼兒園入學(xué)申請排名而設(shè)計的分層數(shù)據(jù)模型,包含12 960個實例和9個屬性，以及各自的分類。另外，為了將本算法應(yīng)用到實際的高校教學(xué)管理系統(tǒng)中，更好服務(wù)于課程設(shè)置和教學(xué)改革，收集了學(xué)校幾屆計算機應(yīng)用技術(shù)專業(yè)的200名大學(xué)生的10門課程成績，構(gòu)建了一個課程成績數(shù)據(jù)集，按成績分為優(yōu)、良、中、及格和不及格5類。從學(xué)生各門課程的成績中挖掘關(guān)聯(lián)規(guī)則，為學(xué)校合理安排課程和教師了解學(xué)生情況提供幫助。兩個數(shù)據(jù)集的屬性如表1所示。

表1 數(shù)據(jù)庫屬性

4.2 算法收斂速度分析

為了驗證IQPSO算法在收斂速度方面的優(yōu)勢，采用標(biāo)準(zhǔn)的最優(yōu)化問題測試函數(shù)-Sphere函數(shù)，該函數(shù)是一個理論最小值為0的非線性對稱的單峰函數(shù)，用于測試尋優(yōu)速度，表達式為：

(14)

設(shè)置各種算法的種群數(shù)量為30，最大迭代次數(shù)為250，Sphere 函數(shù)的維度為20。三種算法對Sphere 函數(shù)進行極小值搜索的收斂曲線如圖1所示?？梢钥吹?，三種算法都能收斂，但IQPSO算法的收斂速度最快，大約在80次迭代后就收斂到0，而PSO和QPSO算法分別需要約180次和120次迭代。這是因為，IQPSO中融入了變異機制和動態(tài)權(quán)重機制，這些操作的計算量很低，不會增加算法單次運行的時間。然而，這些改進可有效避免算法嵌入局部最優(yōu)，減少無效搜索的次數(shù)，提高算法的收斂速度。

圖1 20維Sphere函數(shù)的收斂曲線

4.3 規(guī)則挖掘的執(zhí)行時間比較

為了驗證提出的算法在關(guān)聯(lián)規(guī)則挖掘應(yīng)用上的實際性能，在幼兒園數(shù)據(jù)庫上進行了相關(guān)實驗。在實例數(shù)目和置信度閾值一定時，對不同支持度閾值下的算法在運行時間方面進行比較。其中，選擇4 000個實例進行實驗，最小置信度為0.7，支持度閾值為0.5～0.75。當(dāng)各種算法挖掘的規(guī)則達到最小支持度閾值時停止，并統(tǒng)計執(zhí)行時間。實驗結(jié)果如圖2所示。

從圖2可以看到，隨著支持度閾值的增加，算法所運行的時間逐漸減少。這是因為當(dāng)支持度閾值比較小時，能夠滿足條件的關(guān)聯(lián)規(guī)則較多，算法的運行時間較長。其中，QPSO算法的性能優(yōu)于Apriori算法，這是因為QPSO算法是一種高效的智能優(yōu)化算法，能夠快速收斂到最優(yōu)解。而IQPSO算法執(zhí)行時間最短，且對于傳統(tǒng)QPSO算法有明顯提高。這是因為，IQPSO中融入了變異機制和動態(tài)權(quán)重機制，提高算法的收斂速度，縮短了挖掘關(guān)聯(lián)規(guī)則的執(zhí)行時間。

接著，在固定最小置信度和最小支持度下，在不同數(shù)量的實例數(shù)據(jù)集上進行實驗，比較各種算法的執(zhí)行時間。其中，置信度設(shè)置為0.7，最小支持度設(shè)置為0.65，數(shù)據(jù)集實例數(shù)量為4 000到8 000，結(jié)果如圖3所示?？梢钥闯?，隨著實例數(shù)目的增加，算法的運行時間均逐漸增加。在各種情況下，IQPSO的運行時間都是最短的，且隨著實例數(shù)量的增加，改善效果更加明顯。

圖2 不同支持度閾值下各種算法的執(zhí)行時間

圖3 不同實例數(shù)量下各種算法的執(zhí)行時間

另外，對于課程成績數(shù)據(jù)集，由于實例數(shù)量較少，各種算法的運行時間都比較短(3 s以內(nèi))且差距很小，不像在幼兒園數(shù)據(jù)庫上能看出明顯差異。

4.4 規(guī)則挖掘質(zhì)量比較

從包含4 000個實例的幼兒園數(shù)據(jù)庫中進行規(guī)則挖掘來比較所挖掘的規(guī)則質(zhì)量。這里指定一個目標(biāo)屬性，即“推薦”，將IQPSO算法與文獻[16]的Apriori算法和文獻[17]基于遺傳算法(GA)的挖掘算法進行對比。

對于目標(biāo)“推薦=不推薦”，利用三種算法發(fā)現(xiàn)的最佳規(guī)則如表2所示。對比發(fā)現(xiàn)，相比其他兩種算法，提出的IQPSO算法發(fā)現(xiàn)的規(guī)則更加有價值。例如：

IF “幼兒園=適合”、“孩子=2”、“住房=不方便”、“金融=不方便”、“社會=沒有問題”并且“身體=不健康”；

THEN “推薦=不推薦”。

該規(guī)則的支持度|C&P|為446，置信度b為0.97，適應(yīng)度為0.436。

對于目標(biāo)“推薦=特別優(yōu)先”，利用三種算法發(fā)現(xiàn)的最佳規(guī)則如表3所示。Apriori規(guī)則的置信度b為0.94，適應(yīng)度為0.411。GA規(guī)則的置信度和適應(yīng)度要比Apriori規(guī)則高，因為GA是一種群體智能算法，收斂效果較好。類似表2，除了GA、Apriori發(fā)現(xiàn)的規(guī)則外，IQPSO算法還發(fā)現(xiàn)了其他更有趣的規(guī)則，如表3，其支持度|C&P|為348，置信度b為1.00，適應(yīng)度=0.438。

上述兩個規(guī)則挖掘?qū)嶒灲Y(jié)果表明了IQPSO關(guān)聯(lián)規(guī)則挖掘算法所挖掘的規(guī)則具有更高的價值。這是因為GA算法的全局搜索能力較弱，容易陷入局部最優(yōu)。IQPSO算法通過融入變異機制和動態(tài)慣性權(quán)重，對QPSO進行了更深層次的改進，提高了算法性能，所以能夠挖掘到最優(yōu)的規(guī)則。

表2 幼兒園數(shù)據(jù)庫目標(biāo)“推薦=不推薦”的規(guī)則挖掘結(jié)果

表3 幼兒園數(shù)據(jù)庫目標(biāo)“推薦=特別優(yōu)先”的規(guī)則挖掘結(jié)果

然后，在學(xué)生成績數(shù)據(jù)集中進行同樣的實驗，三種算法挖掘出來的前兩個規(guī)則分別如表4所示。這里舉例分析本方法挖掘出的第一條關(guān)聯(lián)規(guī)則：

IF “EE>=良好”并且“CUE>=及格”；THEN “CMU>=中等”。

這條規(guī)則的意思是，一個學(xué)生的電裝實習(xí)(EE)成績優(yōu)良且計算機硬件原理(CUE)及格，通常計算機維護與升級(CMU)的成績也會中等以上。這就說明電裝實習(xí)與計算機維護與升級之間存在很大的相關(guān)性，電裝實習(xí)優(yōu)秀的學(xué)生通常動手能力較好，加上一定的硬件原理基礎(chǔ)，就會使其在計算機維護與升級中獲得好成績。所以在今后教學(xué)中可以加強對學(xué)生電路組裝等方面動手能力提升的關(guān)注。

表4可見，在三種算法中，IQPSO算法獲得規(guī)則的適應(yīng)度最高，說明了本文方法的有效性。

表4 學(xué)生成績數(shù)據(jù)集中規(guī)則挖掘結(jié)果舉例

在關(guān)聯(lián)規(guī)則挖掘應(yīng)用中，算法會挖掘出很多條規(guī)則，通常只需要選取一些高質(zhì)量的規(guī)則來分析和指導(dǎo)實踐。為了更加全面地評測各種算法的性能，通過上文描述的適應(yīng)度函數(shù)來表征規(guī)則質(zhì)量。在2個數(shù)據(jù)集上分別選擇出前10條高質(zhì)量規(guī)則，然后計算平均適應(yīng)度值，結(jié)果如表5所示。從表5可以看出，IQPSO算法不僅能夠挖掘出最優(yōu)關(guān)聯(lián)規(guī)則，在前10條規(guī)則的平均性能方面也具有一定的優(yōu)越性。

表5 前10條規(guī)則的平均適應(yīng)度

5 結(jié)束語

為了提高QPSO算法的性能，融入了變異機制和動態(tài)慣性權(quán)重形成IQPSO。在UCI和課程成績數(shù)據(jù)集上，將提出的IQPSO與QPSO、Apriori規(guī)則挖掘算法進行比較，證明IQPSO算法具有快速收斂的能力，且所挖掘的規(guī)則比Apriori算法更為合理。

未來會將提出的算法應(yīng)用于更大規(guī)模的數(shù)據(jù)集中，通過對算法進行優(yōu)化進一步提高執(zhí)行效率。此外，通過結(jié)合其他的機器學(xué)習(xí)算法，進一步提高挖掘到的規(guī)則的價值。