鐘倩漪，錢 謙，伏云發(fā)，馮 勇

昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明650500

數(shù)據(jù)挖掘（database mining，DM）又稱數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（knowledge discovery in database，KDD），是從大量數(shù)據(jù)中提取出可信、新穎、有效并能被人理解的模式的高級(jí)處理過程[1]。關(guān)聯(lián)規(guī)則挖掘（association rule mining，ARM）是一種尋找數(shù)據(jù)庫(kù)中的頻繁項(xiàng)或?qū)傩约g相關(guān)性和因果關(guān)聯(lián)的數(shù)據(jù)挖掘方法[2]，由Agrawal 等人[3]于1993 年針對(duì)購(gòu)物籃問題首次提出，主要用于發(fā)現(xiàn)數(shù)據(jù)之間隱藏的關(guān)聯(lián)關(guān)系。目前，關(guān)于關(guān)聯(lián)規(guī)則挖掘的相關(guān)研究較為成熟，一般使用精確算法或智能算法對(duì)之進(jìn)行求解，如Apriori 算法[3]、FP-growth（frequent pattern growth）算法[4]、Eclat算法[5]等都是典型的精確算法。精確算法首先從事務(wù)集合中找出頻繁項(xiàng)集，然后從頻繁項(xiàng)集中挖掘出強(qiáng)關(guān)聯(lián)規(guī)則，但在處理大量數(shù)據(jù)候選項(xiàng)集和復(fù)雜數(shù)據(jù)時(shí)會(huì)帶來嚴(yán)重的時(shí)間、存儲(chǔ)開銷[6]，且大部分算法需要人為設(shè)置支持度和置信度的閾值，導(dǎo)致結(jié)果易產(chǎn)生冗余規(guī)則及忽略重要規(guī)則。因此，部分學(xué)者轉(zhuǎn)而研究智能算法在關(guān)聯(lián)規(guī)則挖掘中的應(yīng)用。Minaei-Bidgoli等人[7]提出了一種基于粗糙模式的多目標(biāo)遺傳算法進(jìn)行數(shù)值關(guān)聯(lián)規(guī)則挖掘，該方法使用由上限和下限間隔定義的粗略值來表示一個(gè)范圍或一組值，同時(shí)使用帕累托最優(yōu)思想解決多目標(biāo)優(yōu)化問題，有效提高了算法性能。Thangavel等人[8]提出了TACO-Miner（threshold ant colony optimization miner）方法，該方法是一種用于挖掘分類關(guān)聯(lián)規(guī)則的改進(jìn)蟻群優(yōu)化算法，可以挖掘出具有更高預(yù)測(cè)精度及更為簡(jiǎn)單的分類規(guī)則。Wang 等人[9]提出了一種基于粒子群優(yōu)化算法的關(guān)聯(lián)規(guī)則挖掘方法，在分類數(shù)據(jù)上與傳統(tǒng)Antminer算法相比具有更高的預(yù)測(cè)精度和更精簡(jiǎn)的規(guī)則集合。以上研究表明，智能算法具有良好的可擴(kuò)展性，與一些精確算法相比執(zhí)行速度較快，挖掘結(jié)果更具有價(jià)值。其中，粒子群優(yōu)化算法因其實(shí)現(xiàn)簡(jiǎn)單、收斂速度快、搜索能力強(qiáng)等優(yōu)點(diǎn)受到諸多學(xué)者關(guān)注，被廣泛應(yīng)用于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域，并取得了大量具有重要意義的研究成果。

現(xiàn)有研究表明，使用粒子群優(yōu)化算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘較遺傳算法有更好的運(yùn)算效率，能夠生成更有效的規(guī)則[9]。目前還沒有專門針對(duì)粒子群優(yōu)化算法解決關(guān)聯(lián)規(guī)則挖掘問題進(jìn)行介紹的相關(guān)綜述，因此，為方便相關(guān)研究者對(duì)該領(lǐng)域有更為清晰的理解，本文概述了粒子群優(yōu)化算法在關(guān)聯(lián)規(guī)則挖掘中的相關(guān)研究和應(yīng)用，并總結(jié)了未來的潛在研究方向。

1 相關(guān)概念及原理

1.1 粒子群優(yōu)化算法基本原理

粒子群優(yōu)化（particle swarm optimization，PSO）算法[10]是一種基于群體的隨機(jī)搜索算法，由Kennedy 和Eberhart 于1995 年提出，其思想主要源于鳥類和魚類群體的社會(huì)行為。標(biāo)準(zhǔn)PSO（standard particle swarm optimization，SPSO）算法[11]中，每一個(gè)粒子表示問題的一個(gè)候選解，具有速度和位置兩個(gè)屬性，粒子通過個(gè)體最優(yōu)解（Pbesti）和全局最優(yōu)解（Gbest）不斷調(diào)整自身的飛行方向和速度，從而改進(jìn)候選解。假設(shè)第t次迭代時(shí)粒子群p(t)中包含N個(gè)粒子，第i個(gè)粒子在K維解空間中的位置向量表示為=(xi1,xi2,…,xiK)，速度向量表示為=(vi1,vi2,…,viK)，Pbesti表示為Pi=(Pi1,Pi2,…,PiK)，Gbest表示為G=(G1,G2,…,GK)。第i個(gè)粒子在下一次迭代中的速度及位置更新公式如下：

其中，ω為慣性權(quán)重，ω∈[0,1]；c1為自我學(xué)習(xí)因子，c2為社會(huì)學(xué)習(xí)因子，一般情況下c1=c2=2；r1、r2為分布在[0,1]區(qū)間上的隨機(jī)數(shù)。

1.2 關(guān)聯(lián)規(guī)則基本概念

在關(guān)聯(lián)規(guī)則問題中，設(shè)項(xiàng)集I={i1,i2,…,ik}為k個(gè)不同數(shù)據(jù)項(xiàng)的集合，k為數(shù)據(jù)項(xiàng)的長(zhǎng)度，長(zhǎng)度為k的數(shù)據(jù)項(xiàng)稱為k-項(xiàng)集，數(shù)據(jù)集D={t1,t2,…,tn}為n個(gè)不同事務(wù)的集合，且tn≠?，每個(gè)事務(wù)tn對(duì)應(yīng)I中的一個(gè)子集，即tn?I。設(shè)X?I，Y?I，且X?Y=?，則X→Y為一條關(guān)聯(lián)規(guī)則，其中X被稱為規(guī)則的前件，Y被稱為規(guī)則的后件，X→Y的支持度和置信度定義如下：

定義1（支持度）關(guān)聯(lián)規(guī)則X→Y的支持度是指包含X和Y的事務(wù)占所有事務(wù)的比例，即事務(wù)X和Y同時(shí)出現(xiàn)在數(shù)據(jù)集D中的概率。

定義2（置信度）關(guān)聯(lián)規(guī)則X→Y的置信度是指事務(wù)X包含事務(wù)Y的比例，即事務(wù)Y出現(xiàn)在事務(wù)X中的概率。

若support(X→Y)和confidence(X→Y)均滿足最小支持度和置信度閾值，則認(rèn)為關(guān)聯(lián)規(guī)則X→Y為一條強(qiáng)關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則挖掘最早用于分析超市商品的購(gòu)買情況，其中，沃爾瑪超市的“尿布和啤酒”是最為經(jīng)典的例子，其商品交易的數(shù)據(jù)示例如表1 所示。

Table 1 Supermarket commodity sales data表1 超市商品銷售數(shù)據(jù)

表1 中包含商品面包、牛奶、尿布、啤酒、雞蛋、可樂，可具體表示為i1、i2、i3、i4、i5、i6，即項(xiàng)集I=(i1,i2,…,i6)。表中共有5 個(gè)事務(wù)，其中同時(shí)包含尿布和啤酒的事務(wù)總數(shù)為3 個(gè)，則規(guī)則i3→i4的支持度計(jì)算如下：

結(jié)合表1 中的數(shù)據(jù)，包含尿布的事務(wù)總數(shù)為4個(gè)，則規(guī)則i3→i4的置信度計(jì)算如下：

2 PSO 算法的研究現(xiàn)狀

傳統(tǒng)PSO 算法自提出以來，眾多學(xué)者從參數(shù)、收斂性、運(yùn)動(dòng)軌跡、拓?fù)浣Y(jié)構(gòu)等角度進(jìn)行研究，并針對(duì)其不足進(jìn)行改進(jìn)，以提高算法性能。2002 年Clerc 和Kennedy[12]提出帶有收縮因子χ的PSO 算法，避免粒子速度和位置增長(zhǎng)到無窮大時(shí)發(fā)生的“爆炸”或“隨機(jī)游走”情況，在確保算法收斂的同時(shí)擴(kuò)大粒子的探索范圍，其速度更新公式如下所示：

其中，k為分布在(0,1]區(qū)間上的隨機(jī)數(shù)，一般情況下k=1，c1=c2=2.05，χ=0.729 8。

運(yùn)動(dòng)軌跡的調(diào)整在一定程度上影響整個(gè)粒子群的搜索趨勢(shì)，一些學(xué)者將變異算子、量子力學(xué)及混沌思想引入PSO 算法，如2003 年Higashi和Iba[13]將高斯分布、變異算子與PSO 算法相結(jié)合，通過高斯分布的概率改變粒子的軌跡，改進(jìn)后的粒子位置更新公式如下所示：其中，變異概率σ由1.0 線性遞減至0，在算法前期粒子進(jìn)行廣泛搜索，中后期進(jìn)行加速搜索，因此，引入高斯變異機(jī)制的算法在單峰和多峰函數(shù)上的測(cè)試結(jié)果均優(yōu)于GA（genetic algorithm）及PSO 算法。2004年，Ratnaweera 等人[14]同樣將變異算子引入到PSO 算法中以保證群體多樣性，Juang[15]將精英選擇、交叉、變異算子結(jié)合在一起，對(duì)適應(yīng)度排名前50%的粒子進(jìn)行交叉、變異操作后生成剩余粒子，實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法搜索精度更高。Sun 等人[16]受量子力學(xué)啟發(fā)提出量子粒子群優(yōu)化（quantum-behaved particle swarm optimization，QPSO）算法，有效改進(jìn)了PSO 算法中易陷入局部最優(yōu)的缺陷。該算法參考量子不確定性原理，每個(gè)量子空間中的粒子速度和位置不能同時(shí)確定，即可對(duì)解空間中的任意位置進(jìn)行搜索，加強(qiáng)了算法的尋優(yōu)能力。QPSO 算法的位置更新公式如下所示：

其中，μ為控制參量，μ∈[0,4]。

迄今為止，針對(duì)PSO 算法定義了許多不同的拓?fù)浣Y(jié)構(gòu)，包括星型拓?fù)洌╯tar topology）、環(huán)型拓?fù)洌╮ing topology）、輪式拓?fù)洌╳heel topology）及金字塔型拓?fù)洌╬yramid topology）結(jié)構(gòu)等，每種結(jié)構(gòu)存在不同優(yōu)缺點(diǎn)[18-19]。拓?fù)浣Y(jié)構(gòu)實(shí)際上決定了粒子間的關(guān)聯(lián)方式，如SPSO 算法屬于全局最優(yōu)算法，該算法采用星型拓?fù)浣Y(jié)構(gòu)，每個(gè)粒子均與全局最優(yōu)粒子相關(guān)聯(lián)。除了眾所周知的拓?fù)浣Y(jié)構(gòu)，一些學(xué)者提出了其他拓?fù)浣Y(jié)構(gòu)，如：Janson 和Middendorf[20]于2005 年提出了基于樹型拓?fù)涞姆謱恿Ｗ尤簝?yōu)化（hierarchical particle swarm optimization，HPSO）算法；Zhang 和Yi[21]于2011年提出了基于自適應(yīng)拓?fù)涞臒o標(biāo)度全信息粒子群優(yōu)化（scale-free fully informed particle swarm optimization，SFIPSO）算法；Jiang 等人[22]于2013 年提出了一種基于年齡組拓?fù)涞牧Ｗ尤簝?yōu)化（particle swarm optimization with age-group topology，PSOAG）算法。

3 PSO 算法在關(guān)聯(lián)規(guī)則挖掘中的研究

3.1 數(shù)據(jù)轉(zhuǎn)換

數(shù)據(jù)庫(kù)中的數(shù)據(jù)類型一般分為連續(xù)型和離散型，連續(xù)型數(shù)據(jù)可直接存儲(chǔ)為實(shí)數(shù)格式，而離散型數(shù)據(jù)需對(duì)數(shù)據(jù)進(jìn)行二進(jìn)制轉(zhuǎn)換。在關(guān)聯(lián)規(guī)則挖掘中，大部分?jǐn)?shù)據(jù)為離散型，需將每條事務(wù)數(shù)據(jù)記錄和存儲(chǔ)為0 或1[23]，這種處理方式能加速數(shù)據(jù)庫(kù)的掃描操作，且便于計(jì)算置信度和支持度。根據(jù)表1所描述的商品交易數(shù)據(jù)集實(shí)例，對(duì)其數(shù)據(jù)的二進(jìn)制變換如圖1所示。

圖1 中，數(shù)據(jù)集包含5 條交易記錄T1至T5，共有6個(gè)不同項(xiàng)即6 個(gè)不同商品，每條交易記錄包含一定數(shù)量的商品，若商品存在于交易記錄中則存儲(chǔ)為1，若不存在則為0。以事務(wù)T1為例，在這條交易記錄中僅購(gòu)買商品I1和I2，因此二進(jìn)制變換后的交易數(shù)據(jù)為110000。

Fig.1 Binary transformation of data圖1 數(shù)據(jù)的二進(jìn)制變換

傳統(tǒng)PSO 算法一般只適用于解決連續(xù)型數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘，針對(duì)離散型數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘需使用改進(jìn)后的PSO 算法。Kennedy 和Eberhart[24]于1997 年對(duì)PSO 算法進(jìn)行改進(jìn)，提出了二進(jìn)制粒子群優(yōu)化（binary particle swarm optimization，BPSO）算法，該算法用于解決離散或組合優(yōu)化問題。為了將粒子限制在{0,1}空間內(nèi)，BPSO 算法的位置更新方式不同于傳統(tǒng)PSO 算法，該算法使用sigmoid 函數(shù)作為變換函數(shù)，將粒子速度轉(zhuǎn)換為[0,1]區(qū)間上的概率，通過概率決定粒子的位置為0 或1。二進(jìn)制粒子位置更新的公式如下所示：

其中，rand為分布在[0,1]區(qū)間上的隨機(jī)數(shù)。

3.2 編碼方式

PSO 算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)主要采用兩種方法對(duì)規(guī)則進(jìn)行編碼：第一種方法為匹茲堡方法（Pittsburgh approach），該方法關(guān)注所有規(guī)則的特征，每個(gè)粒子表示為一組規(guī)則，需對(duì)數(shù)據(jù)中包含的所有規(guī)則進(jìn)行編碼，因此該方法計(jì)算量較大、可移植性差[25]，比較適用于解決分類規(guī)則挖掘問題；第二種方法為密西根方法（Michigan approach），該方法關(guān)注單條規(guī)則的質(zhì)量，每個(gè)粒子表示為一條規(guī)則，只需對(duì)數(shù)據(jù)中的部分規(guī)則進(jìn)行編碼，與匹茲堡方法相比，編碼方式簡(jiǎn)單直接，具有更短的規(guī)則語法，在計(jì)算上更為高效[26]?；谏鲜鲈?，大部分涉及PSO 算法解決關(guān)聯(lián)規(guī)則挖掘問題的文獻(xiàn)中均使用密西根方法，能更為有效地挖掘出高質(zhì)量預(yù)測(cè)規(guī)則及罕見規(guī)則。以密西根方法為例，假設(shè)數(shù)據(jù)庫(kù)中存在N個(gè)項(xiàng)目，每個(gè)項(xiàng)目包含兩個(gè)部分VN1和VN2，VN1的取值表示該項(xiàng)目是否出現(xiàn)在規(guī)則中，VN2的取值表示該項(xiàng)目為規(guī)則前件或規(guī)則后件，根據(jù)圖1 中的商品交易數(shù)據(jù)集隨機(jī)生成的一條規(guī)則編碼如圖2 所示。

Fig.2 Encoding with Michigan approach圖2 使用密西根方法進(jìn)行編碼

圖2 中，I1的編碼為11，表示該項(xiàng)目存在于規(guī)則中且為規(guī)則前件，I2的編碼為10，表示該項(xiàng)目為規(guī)則后件，因此，該編碼表示為一條I1→I2的關(guān)聯(lián)規(guī)則。

3.3 規(guī)則評(píng)估

在經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法中，一般通過支持度和置信度衡量關(guān)聯(lián)規(guī)則的好壞，但高支持度的項(xiàng)會(huì)直接產(chǎn)生高置信度的規(guī)則，與項(xiàng)之間的關(guān)聯(lián)關(guān)系無關(guān)，僅考慮支持度和置信度容易挖掘出無效規(guī)則。因此隨著相關(guān)研究的深入，一些用于衡量規(guī)則質(zhì)量的新標(biāo)準(zhǔn)被提出，包括興趣度、理解度、相似度等。

3.3.1 興趣度

文獻(xiàn)[27]和文獻(xiàn)[28]指出大部分具有高置信度的規(guī)則并不會(huì)讓人感興趣，此類規(guī)則是重復(fù)且無意義的規(guī)則，如購(gòu)物籃問題中挖掘出的“牙膏→牙刷”規(guī)則，此類規(guī)則容易被用戶預(yù)測(cè)，是無趣的規(guī)則，而關(guān)聯(lián)規(guī)則挖掘的主要目的是為了獲取具有意外及隱含特性的規(guī)則，此類規(guī)則的支持度或置信度普遍較低，因此，僅考慮支持度和置信度兩個(gè)標(biāo)準(zhǔn)難以針對(duì)用戶的需求找到其真正感興趣的規(guī)則。李呈林等人[29]引入基于差異思想的興趣度標(biāo)準(zhǔn)，從規(guī)則的置信度與后件的支持度差異定義興趣度，幫助用戶在眾多規(guī)則中選擇更有意義的關(guān)聯(lián)規(guī)則，節(jié)省大量分析規(guī)則的時(shí)間，其計(jì)算公式如下所示：

式（14）中，max{fconf(X→Y),fsup(Y)}表示標(biāo)準(zhǔn)化因子，其作用為將興趣度的絕對(duì)值限制在[0,1]范圍內(nèi)，fconf(X→Y)-fsup(Y)表示為后件Y在前件X影響下發(fā)生的概率與自身發(fā)生概率的差異。規(guī)則X→Y的置信度與后件Y的支持度差距越大，表明該規(guī)則越新奇，即X→Y大概率為一條包含重要信息的隱含關(guān)聯(lián)規(guī)則，更容易讓人感興趣。

基于差異思想的興趣度標(biāo)準(zhǔn)主要是為了避免具有高支持度的后件Y直接產(chǎn)生高置信度的規(guī)則這一問題，從而消除用戶不感興趣、甚至錯(cuò)誤的規(guī)則，但該標(biāo)準(zhǔn)應(yīng)用領(lǐng)域有限，較難適用于分類數(shù)據(jù)問題。由于分類數(shù)據(jù)集要將規(guī)則后件中的每個(gè)屬性進(jìn)行劃分，即后件部分可能包含比較多的項(xiàng)，使用式（14）計(jì)算發(fā)現(xiàn)此類規(guī)則都為低興趣度規(guī)則。因此，文獻(xiàn)[30]提出基于概率思想的興趣度標(biāo)準(zhǔn)，文獻(xiàn)[31-34]引入該興趣度標(biāo)準(zhǔn)對(duì)規(guī)則進(jìn)行評(píng)估，其計(jì)算公式如下所示：

式（15）使用規(guī)則前件和后件的置信度及支持度去評(píng)估興趣度，主要分為三部分：第一部分表示基于規(guī)則前件的置信度；第二部分表示基于規(guī)則后件的置信度；第三部分表示可能無法根據(jù)整個(gè)數(shù)據(jù)集生成規(guī)則的概率。該評(píng)估標(biāo)準(zhǔn)對(duì)規(guī)則前件X與后件Y的置信度及規(guī)則的支持度進(jìn)行綜合度量，由于低支持度及高置信度規(guī)則容易產(chǎn)生高興趣度規(guī)則，因此能挖掘出一些具有實(shí)際應(yīng)用價(jià)值且難以被用戶預(yù)測(cè)的關(guān)聯(lián)規(guī)則。

3.3.2 理解度

支持度和置信度標(biāo)準(zhǔn)依據(jù)規(guī)則在整個(gè)數(shù)據(jù)庫(kù)中的出現(xiàn)次數(shù)來評(píng)估其質(zhì)量，若規(guī)則出現(xiàn)的次數(shù)越多則認(rèn)為這是一條有效規(guī)則，但僅考慮這兩個(gè)標(biāo)準(zhǔn)生成的規(guī)則可能包含大量屬性，難以被用戶理解[35]，從而此類規(guī)則被使用的概率非常低?；谏鲜鲈颍斫舛葮?biāo)準(zhǔn)被提出且廣泛應(yīng)用于規(guī)則的衡量之中，該標(biāo)準(zhǔn)從規(guī)則的簡(jiǎn)潔性和包含的信息量進(jìn)行綜合度量，規(guī)則越簡(jiǎn)潔、信息量越大，則越容易被人理解。文獻(xiàn)[31-34，36]引入一種使用較多的理解度標(biāo)準(zhǔn)，其計(jì)算公式如下所示：

式（16）中，|Y|、|X∪Y|分別表示規(guī)則后件和總的規(guī)則中包含的屬性數(shù)量，ln 函數(shù)用于標(biāo)準(zhǔn)化函數(shù)值的范圍，若規(guī)則包含的總屬性數(shù)量較少且規(guī)則后件包含的屬性較多，則該評(píng)估標(biāo)準(zhǔn)能夠挖掘出易被理解的規(guī)則。

3.3.3 相似度

實(shí)際應(yīng)用中，使用PSO 算法或其他智能算法可以產(chǎn)生一組具有高適應(yīng)度值的關(guān)聯(lián)規(guī)則集合，但其中部分規(guī)則存在相似度過高的情況[37]。相似的規(guī)則容易造成規(guī)則庫(kù)的冗余，不利于用戶決策，因此相似度標(biāo)準(zhǔn)被提出且用于衡量規(guī)則的有效性。若一條規(guī)則的前件和后件包含另一條規(guī)則的前件和后件，則兩條規(guī)則存在相似關(guān)系，例如存在關(guān)聯(lián)規(guī)則集合D={AR1,AR2,…,ARn}，關(guān)聯(lián)規(guī)則AR1:X→Y，AR2:X→(Y,Z)，AR3:Y→Z，則AR1與AR2存在相似關(guān)系，AR1與AR3不存在相似關(guān)系。Kou等人[36]引入一種衡量規(guī)則的相似度標(biāo)準(zhǔn)，其計(jì)算公式如下所示：

式（17）中，support(ARi,ARj)為ARi及ARj包含的事務(wù)在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)，support(ARi)為ARi包含的事務(wù)在數(shù)據(jù)庫(kù)出現(xiàn)的次數(shù)，若規(guī)則ARi與ARj不存在相似關(guān)系，則Simi[i,j]=0。該評(píng)估標(biāo)準(zhǔn)綜合考慮規(guī)則ARi及ARj支持度概率分布的相似程度，對(duì)挖掘出的相似規(guī)則進(jìn)行篩選，能夠挖掘出更為有效的規(guī)則。

上述文獻(xiàn)均考慮多種評(píng)估標(biāo)準(zhǔn)對(duì)規(guī)則質(zhì)量進(jìn)行衡量，從而避免僅考慮支持度和置信度所造成的缺陷。

3.4 PSO 算法與其他關(guān)聯(lián)規(guī)則挖掘算法對(duì)比

本文選取了5 個(gè)在關(guān)聯(lián)規(guī)則挖掘領(lǐng)域中被廣泛應(yīng)用的算法與PSO 算法進(jìn)行對(duì)比，結(jié)果如表2 所示。

關(guān)聯(lián)規(guī)則挖掘算法可大致分為精確算法和智能算法兩類[38]，其最大不同之處在于精確算法需要獲取頻繁項(xiàng)集，而智能算法可以忽略該步驟直接獲取關(guān)聯(lián)規(guī)則，且能生成包含不同項(xiàng)集長(zhǎng)度的規(guī)則。

精確算法包含Apriori算法、FP-growth算法、Eclat算法等。Apriori 算法作為經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法，其核心思想是通過候選集逐層搜索生成頻繁項(xiàng)集，有效降低對(duì)非頻繁項(xiàng)的掃描時(shí)間。假設(shè)數(shù)據(jù)集中包含n個(gè)項(xiàng)目，項(xiàng)集長(zhǎng)度為k，則Apriori 算法的時(shí)間復(fù)雜度為O(2n)+O(2k)，在運(yùn)行過程中候選集數(shù)量呈指數(shù)形式增長(zhǎng)，需要消耗大量?jī)?nèi)存和運(yùn)算時(shí)間。同時(shí)，隨著數(shù)據(jù)維度和數(shù)量的增大，該算法容易產(chǎn)生大量候選集，對(duì)數(shù)據(jù)的重復(fù)掃描次數(shù)過多，特別是在產(chǎn)生的頻繁項(xiàng)集過大時(shí)，算法運(yùn)行時(shí)間顯著增加。因此，Apriori 算法適用于頻繁項(xiàng)集小的數(shù)據(jù)，即小規(guī)模稀疏數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘。FP-growth 算法和Eclat 算法分別使用不同挖掘方法對(duì)Apriori 算法進(jìn)行改進(jìn)。FP-growth 算法使用模式增長(zhǎng)挖掘方法，提出一種FPtree 結(jié)構(gòu)對(duì)數(shù)據(jù)高度壓縮，與Apriori 算法相比無需產(chǎn)生候選集，直接通過FP-tree 挖掘頻繁項(xiàng)集。文獻(xiàn)[4]表明，當(dāng)生成的FP-tree 足夠小或路徑重疊較多時(shí)，在算法的運(yùn)行效率上，F(xiàn)P-growth 算法遠(yuǎn)優(yōu)于Apriori 算法，但當(dāng)數(shù)據(jù)集規(guī)模大、維度高時(shí)，遞歸構(gòu)造FP-tree的子節(jié)點(diǎn)過多，產(chǎn)生大量?jī)?nèi)存開銷，導(dǎo)致算法效率大幅度下降。因此，F(xiàn)P-growth 算法適用于低維布爾關(guān)聯(lián)規(guī)則挖掘。Eclat 算法使用深度優(yōu)先挖掘方法，與FP-growth 和Apriori 算法不同，該算法將數(shù)據(jù)轉(zhuǎn)換為垂直格式，只需掃描一次數(shù)據(jù)庫(kù)，極大地降低了I/O消耗，運(yùn)行效率較高。但垂直數(shù)據(jù)格式對(duì)于內(nèi)存的依賴較大，在大規(guī)模數(shù)據(jù)集中，項(xiàng)目出現(xiàn)的頻率變高，構(gòu)建的頻繁項(xiàng)集過大，處理交集運(yùn)算需要消耗大量?jī)?nèi)存，從而導(dǎo)致算法運(yùn)行效率降低。

Table 2 Comparison of association rule mining algorithms表2 關(guān)聯(lián)規(guī)則挖掘算法比較

智能算法包含遺傳算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法等，此類算法主要是對(duì)數(shù)據(jù)集D中的部分?jǐn)?shù)據(jù)進(jìn)行操作，無需掃描全體事務(wù)，能有效減少數(shù)據(jù)的讀取時(shí)間[39]。遺傳算法[40]（GA）通過種群個(gè)體間的選擇、交叉及變異操作逐步獲取最優(yōu)解，具有良好的全局搜索能力，尋優(yōu)精度較高，但個(gè)體沒有記憶，遺傳操作盲目無方向，所需收斂時(shí)間長(zhǎng)[41]。在處理高維數(shù)據(jù)時(shí)，該算法編碼后的染色體規(guī)模龐大，因此交叉及變異等操作需要大量I/O 消耗，導(dǎo)致算法的運(yùn)行效率低，不易收斂。蟻群優(yōu)化（ant colony optimization，ACO）算法[42]受蟻群覓食行為的啟發(fā)，最初被應(yīng)用于求解旅行商問題，具有良好的魯棒性和全局搜索能力。螞蟻系統(tǒng)使用信息素決定移動(dòng)方向，只需掃描一次數(shù)據(jù)集[43]，但在分配周期中需消耗大量時(shí)間用于解的構(gòu)造，搜索時(shí)間過長(zhǎng)。當(dāng)處理的數(shù)據(jù)規(guī)模過大時(shí)，該算法迭代次數(shù)較多、效率較低，容易發(fā)生停滯現(xiàn)象，存在陷入局部最優(yōu)的可能。粒子群優(yōu)化算法易于實(shí)現(xiàn)、收斂速度較快，文獻(xiàn)[44]表明該算法在較大規(guī)模數(shù)據(jù)中的關(guān)聯(lián)規(guī)則挖掘效率高于GA。但對(duì)于高維數(shù)據(jù)，該算法缺少類似GA 中的交叉、變異操作，搜索空間有限，粒子不能很好地處理探索（全局搜索）和開發(fā)（局部搜索）之間的關(guān)系，容易收斂到局部最優(yōu)解。

4 改進(jìn)PSO 算法在關(guān)聯(lián)規(guī)則挖掘中的研究

4.1 基于參數(shù)的改進(jìn)

使用智能算法尋找到問題中最優(yōu)或近似最優(yōu)解的概率很大程度上取決于參數(shù)的選取[45]，同樣，PSO算法中參數(shù)的設(shè)置對(duì)其性能產(chǎn)生很大影響，設(shè)置合適的參數(shù)值能優(yōu)化算法的性能。PSO 算法包含三個(gè)重要參數(shù)，分別為慣性權(quán)重ω、自我學(xué)習(xí)因子c1和社會(huì)學(xué)習(xí)因子c2，c1和c2為加速度參數(shù)，通常為兩個(gè)常數(shù)。ω控制粒子歷史速度對(duì)新速度的影響，c1和c2用于保持群體的多樣性，c2用于增加算法收斂到全局最優(yōu)的概率。其中，ω是決定PSO 算法收斂的關(guān)鍵，ω越大，算法的全局搜索能力越強(qiáng)，但可能會(huì)在最優(yōu)解附近發(fā)生震蕩，導(dǎo)致算法無法收斂；ω越小，算法的局部搜索能力越強(qiáng)，但粒子對(duì)解空間的探索能力較弱，容易陷入局部最優(yōu)。因此，合適的慣性權(quán)重能平衡粒子的局部搜索和全局搜索能力，合適的自我學(xué)習(xí)因子和社會(huì)學(xué)習(xí)因子能降低算法陷入局部最優(yōu)解的概率。

Mangat 等人[46]提出一種基于動(dòng)態(tài)自適應(yīng)PSO 算法的關(guān)聯(lián)規(guī)則挖掘分類器，即動(dòng)態(tài)自適應(yīng)聯(lián)想分類器，該分類器試圖在保持規(guī)則集合較小的同時(shí)最大化預(yù)測(cè)精度，使用自適應(yīng)參數(shù)、區(qū)域動(dòng)態(tài)重建和速度更新等改進(jìn)，為粒子提供每個(gè)維度的最佳值。其中，PSO 算法使用基于平均理想速度概念對(duì)ω進(jìn)行非線性調(diào)整，當(dāng)粒子速度過大時(shí)，使用較小的ω；當(dāng)粒子速度過小時(shí)，使用較大ω。同時(shí)，c1線性減少，c2線性增加，以上改進(jìn)避免了算法過早收斂及陷入局部最優(yōu)，平衡了粒子對(duì)解空間的探索和開發(fā)。關(guān)聯(lián)規(guī)則的挖掘依賴于數(shù)據(jù)集中的項(xiàng)目和它們之間的關(guān)系，增加或降低參數(shù)值對(duì)算法性能的提升有限，因此，Indira等人[47]考慮數(shù)據(jù)依賴的自適應(yīng)策略對(duì)PSO 算法進(jìn)行改進(jìn)，該算法根據(jù)數(shù)據(jù)集和生成的適應(yīng)度值設(shè)置參數(shù)，通過歐幾里德距離計(jì)算粒子之間的相似度，使用進(jìn)化估計(jì)因子e和適應(yīng)度對(duì)粒子狀態(tài)進(jìn)行估計(jì)，ω、c1和c2均使用自適應(yīng)方式，ω基于適應(yīng)度的變化動(dòng)態(tài)調(diào)整，避免粒子陷入局部最優(yōu)，整體呈線性下降，在收斂后期取值經(jīng)常在0.461 左右波動(dòng)。在粒子的探索前期和開發(fā)后期，c1值增加，c2值減少，允許粒子探索盡可能多的最佳區(qū)域；在粒子的收斂后期，c1和c2值均進(jìn)行小幅度增加，幫助粒子盡可能尋找到全局最優(yōu)解，加快算法的收斂。實(shí)驗(yàn)結(jié)果表明自適應(yīng)PSO 算法在五個(gè)UCI（University of California Irvine）數(shù)據(jù)集上能挖掘出精度更高、數(shù)量更多的關(guān)聯(lián)規(guī)則，但進(jìn)化因子和參數(shù)自適應(yīng)機(jī)制增加了算法的復(fù)雜度，與PSO 算法相比執(zhí)行時(shí)間更長(zhǎng)，且改進(jìn)后的算法主要是與PSO 算法、SAPSO（self adaptive PSO）算法、ACO 算法進(jìn)行對(duì)比，缺乏與精確算法的比較。

PSO 算法中的隨機(jī)數(shù)參數(shù)r1、r2用于增加粒子飛行時(shí)的隨機(jī)性，該參數(shù)的調(diào)整同樣也能影響算法的性能。Alatas 等人[48]引入多目標(biāo)混沌PSO 算法作為一種搜索策略來挖掘數(shù)據(jù)集中的分類規(guī)則，混沌映射的遍歷性能加快算法的全局收斂，該算法中隨機(jī)數(shù)r1、r2使用Zaslavskii 混沌映射[49]公式生成的序列進(jìn)行替換，其公式如下所示：

一般情況下v=400，r=3，a=12，Yn+1∈[-1.051 2,1.051 2]，Xn+1∈[0,1]，此時(shí)變量X表現(xiàn)出良好的動(dòng)態(tài)混沌性。Zaslavskii 映射產(chǎn)生的序列與傳統(tǒng)Logistic 映射相比分布更為均勻，確保算法可以搜索到整個(gè)解空間，有助于粒子跳出局部最優(yōu)解從而提高算法的全局搜索能力。但在大空間、多變量問題的優(yōu)化搜索上，Zaslavskii映射的調(diào)用會(huì)增加PSO 算法的運(yùn)行時(shí)間。

4.2 基于變異機(jī)制的改進(jìn)

變異機(jī)制來源于自然選擇中發(fā)生的基因突變，即生物染色體的基因在遺傳過程中有一定概率發(fā)生改變，好的變異結(jié)果能增加種群的多樣性。因此，針對(duì)傳統(tǒng)PSO 算法的相關(guān)缺陷，變異機(jī)制的引入能增加算法的全局搜索能力，避免算法過快“早熟”。文獻(xiàn)[50]引入變異算子，在PSO 算法的初始化階段隨機(jī)選擇粒子進(jìn)行變異操作，更新粒子的位置，避免其陷入局部最優(yōu)的可能，然后使用改進(jìn)后的PSO 算法對(duì)關(guān)聯(lián)規(guī)則進(jìn)行優(yōu)化，能夠挖掘出更為有效的規(guī)則。

普通變異算子對(duì)滿足一定條件的粒子進(jìn)行單次變異[51]，僅拓展了有限的搜索空間，因此王飛等人[52]提出一種多變異粒子群優(yōu)化（multi-mutation PSO，MmPSO）算法，該算法將多變異算子與粒子群優(yōu)化算法結(jié)合，通過設(shè)置多個(gè)維度的變異概率，對(duì)較差粒子進(jìn)行多次單維變異和一次多維隨機(jī)變異，從而提高粒子跳出局部最優(yōu)解的幾率，避免粒子由于收斂到局部最優(yōu)而導(dǎo)致粒子群萎縮的情況，實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法一定程度上提高了關(guān)聯(lián)規(guī)則挖掘的準(zhǔn)確率，但實(shí)驗(yàn)數(shù)據(jù)中包含的樣本數(shù)量較少，且缺乏單獨(dú)對(duì)多變異算子有效性的相關(guān)驗(yàn)證。文獻(xiàn)[39]同樣引入多變異算子，將其與粒子遷移策略結(jié)合提出MsPMmPSO（multi-swarm parallel MmPSO）算法，增加粒子種群的多樣性，同時(shí)幫助粒子跳出局部最優(yōu)解。

吳嶸等人[53]提出一種基于改進(jìn)量子粒子群優(yōu)化（improved QPSO，IQPSO）算法的關(guān)聯(lián)規(guī)則挖掘方法，將數(shù)據(jù)實(shí)例以量子比特形式表示，構(gòu)建一個(gè)基于QPSO 算法的關(guān)聯(lián)規(guī)則挖掘基礎(chǔ)框架，算法在迭代后期的角度變化幅度越來越小，有很大幾率陷入局部最優(yōu)。當(dāng)算法后期量子個(gè)體最佳角度幾乎沒有改變時(shí)，引入變異算子，選擇一些量子進(jìn)行變異操作，把粒子與全局最優(yōu)角度的距離作為變異概率，將遠(yuǎn)離最優(yōu)角度的量子進(jìn)行大概率變異，提高算法的全局搜索能力。

文獻(xiàn)[54]指出基于PSO 算法的關(guān)聯(lián)規(guī)則挖掘的最大缺點(diǎn)是用戶必須指定生成最佳規(guī)則的數(shù)量，以及該算法在迭代次數(shù)過多情況下的時(shí)間復(fù)雜度高于Apriori 算法，處理大型數(shù)據(jù)集時(shí)效率較慢?；谏鲜隹紤]，Tahyudin 等人[32]將PSO 算法和柯西分布相結(jié)合求解數(shù)值關(guān)聯(lián)規(guī)則挖掘問題，利用柯西變異進(jìn)行跳躍搜索獲得全局最優(yōu)解，避免算法陷入局部最優(yōu)，擴(kuò)展粒子的搜索空間及增強(qiáng)粒子的進(jìn)化能力?？挛髯儺惒呗阅軒椭Ｗ釉诖筻徲騼?nèi)尋找其最優(yōu)解，使算法具有魯棒性，因此也適用于大型數(shù)據(jù)集的關(guān)聯(lián)規(guī)則挖掘。大部分變異粒子圍繞柯西分布中心進(jìn)行分散，雖然減緩了粒子向局部最優(yōu)位置聚集的趨勢(shì)，但不能完全避免其陷入局部最優(yōu)。

4.3 混合PSO 算法

PSO 算法與其他優(yōu)化算法相結(jié)合可以充分發(fā)揮不同算法的優(yōu)點(diǎn)，彌補(bǔ)各自算法的不足?；旌螾SO 算法主要分為三種類型：第一類將PSO 算法與精確算法進(jìn)行混合；第二類將PSO 算法與其他智能算法進(jìn)行混合；第三類將PSO 算法與神經(jīng)網(wǎng)絡(luò)進(jìn)行混合。

4.3.1 混合精確算法

PSO 算法能有效優(yōu)化數(shù)據(jù)，因此被應(yīng)用于優(yōu)化精確算法中的閾值或挖掘出的規(guī)則。曾本沖等人[55]提出一種改進(jìn)PSO-Apriori 算法，使用PSO 算法優(yōu)化Apriori 算法的支持度和置信度閾值，避免閾值需人為設(shè)置且不同數(shù)據(jù)需設(shè)置不同閾值的缺陷，PSO 算法的適應(yīng)度函數(shù)為支持度和置信度的加權(quán)和，同時(shí)，該算法對(duì)優(yōu)化后的多值屬性關(guān)聯(lián)規(guī)則進(jìn)行改進(jìn)，即在Apriori 算法的連接步驟中加入對(duì)特定維度的判斷，能夠挖掘出更為有效的關(guān)聯(lián)規(guī)則。經(jīng)典Apriori 算法使用逐層迭代的方式通過低維頻繁項(xiàng)集得到高維頻繁項(xiàng)集，在執(zhí)行過程中需要頻繁掃描數(shù)據(jù)庫(kù)[56]，因此在挖掘大量數(shù)據(jù)中的關(guān)聯(lián)規(guī)則時(shí)運(yùn)行效率過低，陳建國(guó)[57]將PSO 算法與改進(jìn)Apriori 算法結(jié)合用于處理大型數(shù)據(jù)集的關(guān)聯(lián)規(guī)則挖掘，首先引入K-均值聚類思想，使用PSO 算法對(duì)大型數(shù)據(jù)庫(kù)進(jìn)行優(yōu)化劃分，形成多個(gè)子數(shù)據(jù)庫(kù)，再在子數(shù)據(jù)庫(kù)基礎(chǔ)上采用改進(jìn)后的Apriori 算法進(jìn)行局部挖掘，最后合并各個(gè)局部頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則，從而解決海量數(shù)據(jù)挖掘的時(shí)間和空間復(fù)雜度過高的難點(diǎn)。雖然PSO 算法與Apriori 算法按先后順序進(jìn)行尋優(yōu)，前期PSO 算法提高了運(yùn)行效率，但算法精度仍有較大的提升空間。

FP-growth 算法使用分治策略構(gòu)建頻繁模式樹（FP-tree）后進(jìn)行頻繁項(xiàng)集挖掘，與Apriori 算法相比挖掘效率更高。因此，越來越多的學(xué)者將PSO 算法與FP-growth 算法混合，如Mishra 等人[58]將PSO 算法與FP-growth 算法進(jìn)行結(jié)合用于處理模糊頻繁項(xiàng)集挖掘問題。首先使用FP-growth 算法構(gòu)建模糊FPtree 挖掘出頻繁項(xiàng)集，之后將PSO 算法應(yīng)用于挖掘出的頻繁項(xiàng)集，使用均方冗余（mean squared residue，MSR）分值作為適應(yīng)度函數(shù)進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明，基于PSO 算法的模糊FP-growth 算法能挖掘出數(shù)量更多、結(jié)果更好的頻繁項(xiàng)集，且運(yùn)行效率較高。之后，考慮到PSO 算法容易早熟收斂，Mishra 等人[59]在之前研究基礎(chǔ)上又引入了CLPSO（comprehensive learning PSO）算法[60]，該算法使用一種綜合學(xué)習(xí)策略，利用所有粒子的個(gè)體最優(yōu)位置更新粒子的速度，保持粒子群體的多樣性，防止算法過早收斂。CLPSO 算法對(duì)模糊FP-growth 算法生成的頻繁項(xiàng)集進(jìn)行優(yōu)化，生成的最佳頻繁項(xiàng)具有較低的MSR 分值，優(yōu)于標(biāo)準(zhǔn)PSO 算法。

Eclat 算法是一種頻繁項(xiàng)集挖掘算法，與Apriori算法及FP-growth 算法相比，該算法無需重復(fù)掃描數(shù)據(jù)庫(kù)，提高了規(guī)則的挖掘效率。Sathya 等人[61]提出一種IEPSO-ARM（integrated Eclat and PSO based ARM）算法進(jìn)行高效關(guān)聯(lián)規(guī)則挖掘，該算法將Eclat 算法挖掘出的規(guī)則作為PSO 算法的部分初始化粒子，隨機(jī)初始化剩余的粒子，粒子的適應(yīng)度函數(shù)用于衡量規(guī)則的有效性，因此，通過PSO 算法的優(yōu)化能獲得更為有效的規(guī)則。之后利用垂直布局格式來優(yōu)化基于相關(guān)性度量生成的規(guī)則，即規(guī)則不僅基于相關(guān)性度量生成，同時(shí)基于相關(guān)性度量的強(qiáng)度生成。

4.3.2 混合智能算法

針對(duì)使用單一PSO 算法在解決問題時(shí)具有的收斂精度不足、局部搜索能力差等缺點(diǎn)[62]，文獻(xiàn)[63]提出一種混合遺傳粒子群優(yōu)化（hybrid GA/PSO，GPSO）算法，將GA 與PSO 算法在同一個(gè)群體上并行運(yùn)行，保證PSO 和GA 在互不影響的情況下共同迭代尋優(yōu)，在迭代前期充分利用GA 的隨機(jī)性擴(kuò)大探索范圍，迭代后期利用PSO 算法的快速收斂能力，實(shí)現(xiàn)算法探索與開發(fā)之間的平衡。雖然GPSO 算法較PSO 算法消耗時(shí)間更多，但挖掘出的關(guān)聯(lián)規(guī)則更為精準(zhǔn)。然而GPSO 算法僅考慮支持度和置信度兩個(gè)指標(biāo)，不能挖掘出更為有效的高質(zhì)量規(guī)則，因此Agarwal 等人[64]提出一種NSGA-II-MPSO（nondominated sorting genetic algorithm II and multi-objective PSO）算法對(duì)購(gòu)物籃數(shù)據(jù)進(jìn)行多目標(biāo)關(guān)聯(lián)規(guī)則挖掘，該算法將帶精英策略的非支配排序的遺傳算法[65]（nondominated sorting genetic algorithm II，NSGA-II）與多目標(biāo)粒子群優(yōu)化（multiobjective PSO，MOPSO）算法[66]進(jìn)行混合，平衡對(duì)規(guī)則的探索和開發(fā)。該算法將初始化中適應(yīng)度較高的一半規(guī)則視為染色體，使用NSGA-II 進(jìn)行優(yōu)化，另外一半規(guī)則被視為粒子群體，使用快速收斂MOPSO算法進(jìn)行增強(qiáng)，將使用不同算法的輸出結(jié)果重新組合，生成新的群體進(jìn)行下一代傳播。NSGA-II 的精英策略保留了全局最優(yōu)解，且通過交叉和變異操作能產(chǎn)生帶有新染色體的子代，將遺傳算法用于適應(yīng)度較高的個(gè)體避免算法陷入早熟收斂[63]，而MOPSO算法借助個(gè)體反饋機(jī)制和基本的群體交互作用，增強(qiáng)適應(yīng)度較低的個(gè)體，幫助其尋找到最優(yōu)解，改進(jìn)后的算法收斂速度更快、算法性能更高，但實(shí)驗(yàn)只與單目標(biāo)算法進(jìn)行了對(duì)比，且未考慮包含負(fù)相關(guān)項(xiàng)的規(guī)則。Zhou 等人[67]提出A_PSOGSA（adaptive PSO gravitational search algorithm）用于解決關(guān)聯(lián)規(guī)則挖掘問題，該算法混合了自適應(yīng)粒子群優(yōu)化[68]（adaptive PSO，APSO）算法、GA 及引力搜索算法[69]（gravitational search algorithm，GSA）。GSA 具有較好的全局尋優(yōu)能力，通過粒子的慣性質(zhì)量、在每個(gè)方向的引力、加速度等信息，增加粒子群的記憶能力和粒子間的交流，加強(qiáng)粒子間的相互作用。混合后算法在每次迭代更新中考慮所有粒子的適應(yīng)度，任何粒子都可以感知全局最優(yōu)解，并與之保持接近，因此能提高算法的局部搜索能力。同時(shí)，該算法保存每次迭代后產(chǎn)生的全局最優(yōu)解，有利于關(guān)聯(lián)規(guī)則挖掘。最后，該算法在進(jìn)化過程中利用種群分布信息動(dòng)態(tài)控制加速系數(shù)，能更好地平衡全局和局部搜索能力。佘雅莉等人[70]混合了PSO 算法與ACO 算法對(duì)危險(xiǎn)源原因進(jìn)行關(guān)聯(lián)規(guī)則挖掘，先使用PSO 算法挖掘出數(shù)據(jù)集中的頻繁項(xiàng)集，從而確定ACO 算法的初始信息素濃度，避免蟻群運(yùn)動(dòng)的盲目性，同時(shí)增加算法的搜索能力。當(dāng)螞蟻完成一次搜索后，對(duì)本次迭代中的最優(yōu)頻繁項(xiàng)集中的點(diǎn)所構(gòu)成的邊進(jìn)行信息素更新，直至挖掘出最大頻繁項(xiàng)集，生成質(zhì)量較好的強(qiáng)關(guān)聯(lián)規(guī)則，實(shí)驗(yàn)結(jié)果表明使用混合后的算法更容易對(duì)危險(xiǎn)源原因進(jìn)行分析。

4.3.3 混合神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)（artificial neural network，ANN）具有自學(xué)習(xí)、自組織、自適應(yīng)和非線性動(dòng)態(tài)處理等特性，PSO 算法與ANN 的結(jié)合能更有效解決實(shí)際問題。Dhanalaxmi 等人[71]使用分類關(guān)聯(lián)規(guī)則挖掘方法對(duì)軟件缺陷進(jìn)行分類，避免軟件缺陷的產(chǎn)生，而軟件缺陷數(shù)量越少則表明軟件質(zhì)量越高。該方法在挖掘關(guān)聯(lián)規(guī)則之前，使用自適應(yīng)PSO 算法對(duì)規(guī)則進(jìn)行優(yōu)化，提供更具體的聚類結(jié)果，避免挖掘到大量無效規(guī)則。之后，使用前饋反向傳播神經(jīng)網(wǎng)絡(luò)（feed forward back propagation neural network，F(xiàn)FBNN）分類器對(duì)確定的實(shí)際缺陷進(jìn)行分類，改進(jìn)后的分類關(guān)聯(lián)規(guī)則挖掘方法精確度達(dá)到99.5%。

PSO算法也適用于優(yōu)化人工神經(jīng)網(wǎng)絡(luò)的權(quán)值，Ma等人[72]使用加權(quán)模糊神經(jīng)網(wǎng)絡(luò)（weighted fuzzy neural network，WFNN）進(jìn)行模糊關(guān)聯(lián)規(guī)則挖掘，將PSO 算法應(yīng)用于WFNN 的優(yōu)化，尋找合適的可變閾值wb，可變權(quán)重wc、we和wf。WFNN 中權(quán)重we的值象征一個(gè)模糊規(guī)則，當(dāng)其值很小時(shí)，該規(guī)則為模糊冗余規(guī)則，需要進(jìn)行裁剪。之后再根據(jù)有效規(guī)則確定模糊神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)。Boomilingam 等人[73]引入邊緣灰度共生矩陣和人工神經(jīng)網(wǎng)絡(luò)對(duì)圖像增強(qiáng)特征進(jìn)行關(guān)聯(lián)規(guī)則挖掘，使用改進(jìn)的PSO 算法優(yōu)化人工神經(jīng)網(wǎng)絡(luò)的權(quán)值，把經(jīng)典Apriori 算法挖掘出的規(guī)則作為FFBNN 的輸入類別，使用改進(jìn)PSO 算法的ANN 在精度、召回率和準(zhǔn)確率等方面都有提高，檢索準(zhǔn)確率從90%提高到95%。

PSO 算法能直接與人工神經(jīng)網(wǎng)絡(luò)進(jìn)行混合，Kuo等人[74]混合了TD-FP-growth（top-down FP-growth）算法[75]、最佳人工免疫網(wǎng)絡(luò)[76]（optimiz ation artificial immune network，Opt-aiNet）和PSO 算法解決供應(yīng)商選擇與訂單分配問題。TD-FP-growth 算法對(duì)現(xiàn)有供應(yīng)商數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，確定每個(gè)供應(yīng)商的重要性，選擇出關(guān)鍵供應(yīng)商，aiNet-PSO（Opt-aiNet PSO）方法以最小成本為關(guān)鍵供應(yīng)商分配訂單量。OptaiNet 具有產(chǎn)生抗體、克隆抗體及變異等特性，不易陷入局部最優(yōu)，同時(shí)PSO 算法對(duì)Opt-aiNet 中的每組抗體進(jìn)行優(yōu)化，加快算法的收斂。

5 PSO 算法在關(guān)聯(lián)規(guī)則挖掘中的應(yīng)用

在處理復(fù)雜的現(xiàn)實(shí)優(yōu)化問題時(shí)，智能算法引導(dǎo)群體方向進(jìn)行逐步搜索直至獲得解決方案，此類算法在搜索過程中不受優(yōu)化函數(shù)形態(tài)的約束，適應(yīng)性強(qiáng)、運(yùn)行效率高，因此被應(yīng)用于各種領(lǐng)域，并且在解決大多數(shù)高度非線性和多模態(tài)的優(yōu)化問題方面表現(xiàn)良好[27]。與精確算法相比，智能算法在解決關(guān)聯(lián)規(guī)則挖掘問題時(shí)由于隨機(jī)搜索的特性可能不會(huì)獲取全部解決方案，但能在合理的時(shí)間內(nèi)獲得足夠好的解決方案。

隨著智能算法在關(guān)聯(lián)規(guī)則挖掘中的不斷發(fā)展，PSO 算法被廣泛應(yīng)用于不同領(lǐng)域。購(gòu)物籃問題是一類超市商品交易問題，通過對(duì)顧客的交易信息進(jìn)行分析從而對(duì)商品進(jìn)行決策，關(guān)聯(lián)規(guī)則挖掘算法主要針對(duì)購(gòu)物籃問題被提出，同時(shí)也被廣泛用于解決購(gòu)物籃問題。文獻(xiàn)[77]對(duì)超市購(gòu)物數(shù)據(jù)進(jìn)行動(dòng)態(tài)關(guān)聯(lián)規(guī)則挖掘，提出一種改進(jìn)PSO 算法的灰色模型，通過增加緩沖算子，引入二次搜索機(jī)制對(duì)PSO 算法進(jìn)行改進(jìn)，優(yōu)化求解灰色模型不同時(shí)刻的背景值，以提高PSO 算法的局部搜索能力，從而提高灰色模型的預(yù)測(cè)精度。文獻(xiàn)[78]考慮到傳統(tǒng)頻繁項(xiàng)集挖掘算法主要用于尋找頻繁出現(xiàn)的商品組合，而不關(guān)注商品的其他屬性，比如銷量、銷售價(jià)和進(jìn)貨價(jià)等。為了進(jìn)一步獲取具有高利潤(rùn)的商品組合，發(fā)現(xiàn)具有高效用（例如，高利潤(rùn)）的項(xiàng)集，提出一種基于高效用項(xiàng)集挖掘[79]（high utility itemset mining，HUIM）的HUIM-IPSO 算法，實(shí)驗(yàn)表明該算法具有更高的挖掘效率和更快的收斂速度。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。

近些年，PSO 算法由于其實(shí)現(xiàn)簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)被成功應(yīng)用于金融領(lǐng)域，其中股票走勢(shì)分析需要綜合分析各股票漲跌情況、現(xiàn)金流入量、相關(guān)政策和GDP 等多種數(shù)據(jù)信息。傳統(tǒng)數(shù)學(xué)統(tǒng)計(jì)分析方法主要針對(duì)單一股票信息進(jìn)行預(yù)測(cè)，而股票走勢(shì)往往與同行業(yè)中其他公司甚至其他行業(yè)的經(jīng)營(yíng)情況密切相關(guān)，因此對(duì)于股票的走勢(shì)預(yù)測(cè)準(zhǔn)確率不高。同時(shí)，股票預(yù)測(cè)數(shù)據(jù)具有規(guī)模大、維度高、價(jià)值密度低和實(shí)時(shí)性要求高等特點(diǎn)，使用Apriori 算法需要花費(fèi)大量時(shí)間多次掃描數(shù)據(jù)，容易造成對(duì)股票走勢(shì)的誤判與延時(shí)，無法適用于實(shí)時(shí)性極高的股票關(guān)聯(lián)預(yù)測(cè)分析?；谏鲜鲈?，文獻(xiàn)[80]提出一種使用協(xié)同粒子群優(yōu)化的股票關(guān)聯(lián)規(guī)則挖掘方法用于預(yù)測(cè)股票走勢(shì)，主要針對(duì)傳統(tǒng)數(shù)據(jù)分析方法對(duì)股票走勢(shì)進(jìn)行預(yù)測(cè)時(shí)具有準(zhǔn)確率不高，時(shí)效性不強(qiáng)的缺陷，該方法分別使用PSO 算法對(duì)支持度與置信度進(jìn)行挖掘優(yōu)化，較Apriori 算法和PSO 算法在準(zhǔn)確率與挖掘速率上有了很大的提高。文獻(xiàn)[81]同樣對(duì)股票信息進(jìn)行挖掘，主要針對(duì)投資者的股票交易數(shù)據(jù)，首先使用PSO 算法優(yōu)化支持度和置信度的閾值，之后通過閾值篩選出合適的粒子即關(guān)聯(lián)規(guī)則，基于PSO 算法的關(guān)聯(lián)規(guī)則挖掘方法能挖掘出投資者與購(gòu)買股票間的關(guān)聯(lián)規(guī)則，有利于投資者進(jìn)行決策。

對(duì)于醫(yī)療領(lǐng)域，使用傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法生成的規(guī)則目標(biāo)單一、數(shù)量巨大，需要剪枝、過濾才能獲取重要規(guī)則，因此，一些學(xué)者開始使用PSO 算法進(jìn)行醫(yī)療信息關(guān)聯(lián)規(guī)則挖掘。醫(yī)學(xué)影像和計(jì)算機(jī)視覺的快速發(fā)展，從龐大的數(shù)據(jù)庫(kù)中管理和檢索醫(yī)學(xué)影像變得越來越困難。文獻(xiàn)[73]使用PSO 算法及人工神經(jīng)網(wǎng)絡(luò)對(duì)醫(yī)學(xué)圖像進(jìn)行關(guān)聯(lián)規(guī)則挖掘，提出一種改進(jìn)后的醫(yī)學(xué)圖像檢索系統(tǒng)，能有效支持醫(yī)生的診斷任務(wù)，方便對(duì)圖像數(shù)據(jù)庫(kù)進(jìn)行檢查及搜索，具有很強(qiáng)的實(shí)用價(jià)值。文獻(xiàn)[82]提出一種基于PSO 算法、支持向量機(jī)[83]（support vector machine，SVM）及Apriori算法的模型用于診斷紅斑鱗狀疾病。該模型使用Apriori 算法從原始特征集中分離冗余疾病特征，降低數(shù)據(jù)集維度，之后使用PSO 算法優(yōu)化SVM 模型，對(duì)多個(gè)患者的疾病特征進(jìn)行分類，由于PSO 算法能有效確定SVM 的參數(shù)值，有利于提高SVM 模型的分類精度，即對(duì)疾病的診斷準(zhǔn)確度。

工業(yè)產(chǎn)品在生產(chǎn)過程中包含大量設(shè)計(jì)、工藝、制造和裝配信息等歷史數(shù)據(jù)，對(duì)產(chǎn)品知識(shí)的挖掘與重用已成為企業(yè)所使用的重要手段之一，關(guān)聯(lián)規(guī)則挖掘也常被應(yīng)用于工業(yè)生產(chǎn)領(lǐng)域，包括產(chǎn)品族設(shè)計(jì)知識(shí)的挖掘，產(chǎn)品設(shè)計(jì)與制造的映射關(guān)系識(shí)別，生產(chǎn)過程中質(zhì)量控制規(guī)則的挖掘，以及工藝序列知識(shí)等。文獻(xiàn)[84]使用BPSO 算法對(duì)衛(wèi)星典型件工藝知識(shí)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，主要針對(duì)衛(wèi)星典型件在工藝設(shè)計(jì)過程中設(shè)計(jì)任務(wù)量大、重復(fù)性工作多且其歷史工藝數(shù)據(jù)未能充分有效利用的問題，通過建立工藝知識(shí)的關(guān)聯(lián)規(guī)則模型，引入BPSO 算法對(duì)規(guī)則進(jìn)行處理，有效提高工藝知識(shí)的挖掘效率。文獻(xiàn)[36]對(duì)機(jī)床加工零件進(jìn)行關(guān)聯(lián)規(guī)則挖掘，使用基于BPSO 的關(guān)聯(lián)規(guī)則挖掘方法，從數(shù)據(jù)中提取有用的工藝知識(shí)反映產(chǎn)品設(shè)計(jì)與制造的映射關(guān)系，且引入相似度指標(biāo)以消除無效規(guī)則。

對(duì)于風(fēng)險(xiǎn)評(píng)估領(lǐng)域，關(guān)聯(lián)規(guī)則挖掘方法適用于分析各事件間存在的內(nèi)在聯(lián)系，為風(fēng)險(xiǎn)預(yù)測(cè)、響應(yīng)及防范提供決策依據(jù)，但隨著社會(huì)的發(fā)展該領(lǐng)域包含了大量復(fù)雜數(shù)據(jù)，具有時(shí)間、地點(diǎn)、原因、造成的傷亡和損失等多個(gè)屬性，僅單獨(dú)使用傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法效率較低，因此文獻(xiàn)[85]對(duì)社會(huì)安全事件進(jìn)行關(guān)聯(lián)規(guī)則挖掘，提出PSOFP-growth 算法，該算法使用PSO 算法獲得最優(yōu)支持度，通過5 000 個(gè)包含時(shí)間、地點(diǎn)、攻擊目標(biāo)和死亡人數(shù)屬性的社會(huì)安全事件數(shù)據(jù)構(gòu)造FP-tree，以信息熵為興趣度指標(biāo)用于衡量關(guān)聯(lián)規(guī)則的有效性，消除無效關(guān)聯(lián)規(guī)則。文獻(xiàn)[55]采用改進(jìn)PSO-Apriori算法尋找數(shù)據(jù)庫(kù)中所有具有強(qiáng)內(nèi)在關(guān)聯(lián)特征的恐怖組織信息，篩除不滿足要求的頻繁項(xiàng)集，通過對(duì)挖掘出的恐怖組織關(guān)聯(lián)特征進(jìn)行分析發(fā)現(xiàn)中東和北非、南亞和撒哈拉以南的非洲地區(qū)的恐怖組織具有較強(qiáng)的關(guān)聯(lián)關(guān)系。關(guān)聯(lián)規(guī)則挖掘同樣是洪災(zāi)風(fēng)險(xiǎn)分析的重要方法之一，用于減輕洪水帶來的災(zāi)害損失與影響[86]。洪災(zāi)風(fēng)險(xiǎn)評(píng)價(jià)涉及自然、技術(shù)、社會(huì)經(jīng)濟(jì)等諸多影響因素且國(guó)內(nèi)外尚無統(tǒng)一的評(píng)價(jià)指標(biāo)體系和評(píng)價(jià)標(biāo)準(zhǔn)，因而洪災(zāi)風(fēng)險(xiǎn)評(píng)價(jià)一直是國(guó)內(nèi)外災(zāi)害學(xué)研究的難點(diǎn)和熱點(diǎn)。文獻(xiàn)[87]提出了一種基于PSO 規(guī)則挖掘算法（PSO-Miner）的洪災(zāi)風(fēng)險(xiǎn)評(píng)價(jià)模型，對(duì)北江流域進(jìn)行洪災(zāi)風(fēng)險(xiǎn)評(píng)價(jià)，該算法使用實(shí)數(shù)型編碼方式，每個(gè)粒子對(duì)應(yīng)一條路徑，相應(yīng)產(chǎn)生一條評(píng)價(jià)規(guī)則，規(guī)則為評(píng)價(jià)指標(biāo)節(jié)點(diǎn)和洪災(zāi)風(fēng)險(xiǎn)等級(jí)節(jié)點(diǎn)的連線。由文獻(xiàn)[85]、[55]和[87]可知，基于PSO 算法的關(guān)聯(lián)規(guī)則挖掘方法可能搜索不到所有有效關(guān)聯(lián)規(guī)則，而且當(dāng)粒子個(gè)數(shù)和迭代次數(shù)較大時(shí)算法運(yùn)行時(shí)間相對(duì)較長(zhǎng)，但為風(fēng)險(xiǎn)領(lǐng)域的智能化評(píng)價(jià)提供了一種新的解決思路。

6 總結(jié)與展望

PSO 算法在關(guān)聯(lián)規(guī)則挖掘中的研究作為一個(gè)較新領(lǐng)域，通過學(xué)者們的探索與深入，在算法的設(shè)計(jì)及優(yōu)化方面日趨成熟，并廣泛應(yīng)用于購(gòu)物籃分析、金融、醫(yī)療、工業(yè)生產(chǎn)及社會(huì)安全等領(lǐng)域。本文總結(jié)了關(guān)聯(lián)規(guī)則挖掘中針對(duì)PSO 算法的改進(jìn)研究，改進(jìn)方法主要有以下幾種：（1）基于參數(shù)的改進(jìn)，對(duì)慣性權(quán)重、社會(huì)學(xué)習(xí)因子及自我學(xué)習(xí)因子等參數(shù)進(jìn)行改進(jìn)；（2）基于變異策略的改進(jìn)，粒子有一定概率進(jìn)行改變；（3）將PSO 算法與其他算法混合，避免使用單一算法而形成的缺陷。

隨著數(shù)據(jù)的爆炸增長(zhǎng)，從中挖掘到有效關(guān)聯(lián)規(guī)則越來越困難，因此，該領(lǐng)域在未來研究中仍是具有挑戰(zhàn)性的方向，未來的研究工作重點(diǎn)可能主要在以下方面：

（1）PSO 算法是一種隨機(jī)搜索算法，解決包含大量高維數(shù)據(jù)的問題時(shí)效率較低，僅使用單臺(tái)計(jì)算機(jī)無法滿足運(yùn)算的需求，而分布式、并行運(yùn)算的關(guān)聯(lián)規(guī)則挖掘算法能顯著提高運(yùn)行效率。目前關(guān)于這方面的研究較少，大部分研究都是并行化經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法，如：基于Hadoop Map-Reduce 模型的Apriori 算法[88]和FP-growth 算法[89]，基于Spark RDD框架的Eclat 算法[90]等，而PSO 算法具有本質(zhì)并行性，每個(gè)粒子都是獨(dú)立個(gè)體，其適應(yīng)度值計(jì)算及運(yùn)動(dòng)過程都是并行的[91]。因此，設(shè)計(jì)并行化PSO 算法更為有效地處理海量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘是值得深入研究的課題。

（2）目前，針對(duì)PSO 的關(guān)聯(lián)規(guī)則挖掘算法的缺陷已經(jīng)提出了許多改進(jìn)算法，但對(duì)粒子初始化方法進(jìn)行改進(jìn)的相關(guān)研究較少，大部分文獻(xiàn)中使用隨機(jī)初始化，這種初始化方法容易導(dǎo)致粒子分布不均勻，產(chǎn)生的粒子質(zhì)量不高，大部分粒子可能遠(yuǎn)離最優(yōu)解，影響算法的全局收斂。一般而言，初始粒子群應(yīng)在有限的數(shù)量?jī)?nèi)最大限度地表征解空間包含的信息，在迭代早期粒子能深入探索尋找最優(yōu)解，實(shí)現(xiàn)算法收斂性和快速性的協(xié)調(diào)統(tǒng)一。目前在傳統(tǒng)PSO 算法領(lǐng)域中運(yùn)用較為廣泛的初始化改進(jìn)方式有混沌初始化[92]、聚類初始化[93]及非線性單純體法（nonlinear simplex method，NSM）初始化[94]?；煦绯跏蓟没煦缧蛄械谋闅v性，產(chǎn)生大量初始群體，從中挑選出優(yōu)秀粒子，優(yōu)化初始群體的質(zhì)量，同時(shí)增加粒子遍布整個(gè)解空間的可能性，但不能確保其完全均勻分布。聚類初始化利用聚類算法挖掘初始粒子群的信息，從每個(gè)子群的聚類中心中篩選出具有代表性的粒子，進(jìn)而縮小了初始種群的規(guī)模，提高了粒子質(zhì)量，但沒有徹底解決初始粒子在解空間中分布不均勻的問題。非線性單純體法克服了隨機(jī)初始化不能保證粒子合理分布的缺點(diǎn)，通過反射、擴(kuò)張等運(yùn)算，使其產(chǎn)生的各個(gè)頂點(diǎn)可充分體現(xiàn)函數(shù)解空間中的峰谷特性，對(duì)提高初始粒子質(zhì)量，加速PSO 算法的收斂速度起到了有效的作用，但該方法復(fù)雜性較高，需要較多的運(yùn)算時(shí)間。關(guān)聯(lián)規(guī)則挖掘領(lǐng)域涉及各種數(shù)據(jù)類型及函數(shù)形態(tài)，與傳統(tǒng)PSO 算法領(lǐng)域使用的統(tǒng)一基準(zhǔn)測(cè)試函數(shù)不同，因此針對(duì)不同類型設(shè)置初始化方式是一項(xiàng)較為困難的工作。同時(shí)作為未來研究的一個(gè)方向，關(guān)于粒子群初始化改進(jìn)可以參考上述提及的初始化方法思想，設(shè)計(jì)更為優(yōu)秀的種群初始化方式，提高算法的運(yùn)行效率。

（3）現(xiàn)有研究中，基于PSO 的關(guān)聯(lián)規(guī)則挖掘算法雖已被成功運(yùn)用于多種領(lǐng)域，但涉及現(xiàn)實(shí)生活中的應(yīng)用領(lǐng)域仍然有限，針對(duì)大部分領(lǐng)域的應(yīng)用還處于初步階段，相關(guān)研究較少。因此，研究新的關(guān)聯(lián)規(guī)則應(yīng)用領(lǐng)域，在應(yīng)用的廣度和深度上進(jìn)行拓展都是很有價(jià)值的工作。