粒子群優化算法在關聯規則挖掘中的研究綜述

鐘倩漪，錢 謙，伏云發，馮 勇

昆明理工大學信息工程與自動化學院云南省計算機技術應用重點實驗室，昆明650500

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

現有研究表明，使用粒子群優化算法進行關聯規則挖掘較遺傳算法有更好的運算效率，能夠生成更有效的規則[9]。目前還沒有專門針對粒子群優化算法解決關聯規則挖掘問題進行介紹的相關綜述，因此，為方便相關研究者對該領域有更為清晰的理解，本文概述了粒子群優化算法在關聯規則挖掘中的相關研究和應用，并總結了未來的潛在研究方向。

1 相關概念及原理

1.1 粒子群優化算法基本原理

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

其中，ω為慣性權重，ω∈[0,1]；c1為自我學習因子，c2為社會學習因子，一般情況下c1=c2=2；r1、r2為分布在[0,1]區間上的隨機數。

1.2 關聯規則基本概念

在關聯規則問題中，設項集I={i1,i2,…,ik}為k個不同數據項的集合，k為數據項的長度，長度為k的數據項稱為k-項集，數據集D={t1,t2,…,tn}為n個不同事務的集合，且tn≠?，每個事務tn對應I中的一個子集，即tn?I。設X?I，Y?I，且X?Y=?，則X→Y為一條關聯規則，其中X被稱為規則的前件，Y被稱為規則的后件，X→Y的支持度和置信度定義如下：

定義1（支持度）關聯規則X→Y的支持度是指包含X和Y的事務占所有事務的比例，即事務X和Y同時出現在數據集D中的概率。

定義2（置信度）關聯規則X→Y的置信度是指事務X包含事務Y的比例，即事務Y出現在事務X中的概率。

若support(X→Y)和confidence(X→Y)均滿足最小支持度和置信度閾值，則認為關聯規則X→Y為一條強關聯規則。

關聯規則挖掘最早用于分析超市商品的購買情況，其中，沃爾瑪超市的“尿布和啤酒”是最為經典的例子，其商品交易的數據示例如表1 所示。

Table 1 Supermarket commodity sales data表1 超市商品銷售數據

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

結合表1 中的數據，包含尿布的事務總數為4個，則規則i3→i4的置信度計算如下：

2 PSO 算法的研究現狀

傳統PSO 算法自提出以來，眾多學者從參數、收斂性、運動軌跡、拓撲結構等角度進行研究，并針對其不足進行改進，以提高算法性能。2002 年Clerc 和Kennedy[12]提出帶有收縮因子χ的PSO 算法，避免粒子速度和位置增長到無窮大時發生的“爆炸”或“隨機游走”情況，在確保算法收斂的同時擴大粒子的探索范圍，其速度更新公式如下所示：

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

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

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

迄今為止，針對PSO 算法定義了許多不同的拓撲結構，包括星型拓撲（star topology）、環型拓撲（ring topology）、輪式拓撲（wheel topology）及金字塔型拓撲（pyramid topology）結構等，每種結構存在不同優缺點[18-19]。拓撲結構實際上決定了粒子間的關聯方式，如SPSO 算法屬于全局最優算法，該算法采用星型拓撲結構，每個粒子均與全局最優粒子相關聯。除了眾所周知的拓撲結構，一些學者提出了其他拓撲結構，如：Janson 和Middendorf[20]于2005 年提出了基于樹型拓撲的分層粒子群優化（hierarchical particle swarm optimization，HPSO）算法；Zhang 和Yi[21]于2011年提出了基于自適應拓撲的無標度全信息粒子群優化（scale-free fully informed particle swarm optimization，SFIPSO）算法；Jiang 等人[22]于2013 年提出了一種基于年齡組拓撲的粒子群優化（particle swarm optimization with age-group topology，PSOAG）算法。

3 PSO 算法在關聯規則挖掘中的研究

3.1 數據轉換

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

圖1 中，數據集包含5 條交易記錄T1至T5，共有6個不同項即6 個不同商品，每條交易記錄包含一定數量的商品，若商品存在于交易記錄中則存儲為1，若不存在則為0。以事務T1為例，在這條交易記錄中僅購買商品I1和I2，因此二進制變換后的交易數據為110000。

Fig.1 Binary transformation of data圖1 數據的二進制變換

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

其中，rand為分布在[0,1]區間上的隨機數。

3.2 編碼方式

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

Fig.2 Encoding with Michigan approach圖2 使用密西根方法進行編碼

圖2 中，I1的編碼為11，表示該項目存在于規則中且為規則前件，I2的編碼為10，表示該項目為規則后件，因此，該編碼表示為一條I1→I2的關聯規則。

3.3 規則評估

在經典關聯規則挖掘算法中，一般通過支持度和置信度衡量關聯規則的好壞，但高支持度的項會直接產生高置信度的規則，與項之間的關聯關系無關，僅考慮支持度和置信度容易挖掘出無效規則。因此隨著相關研究的深入，一些用于衡量規則質量的新標準被提出，包括興趣度、理解度、相似度等。

3.3.1 興趣度

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

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

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

式（15）使用規則前件和后件的置信度及支持度去評估興趣度，主要分為三部分：第一部分表示基于規則前件的置信度；第二部分表示基于規則后件的置信度；第三部分表示可能無法根據整個數據集生成規則的概率。該評估標準對規則前件X與后件Y的置信度及規則的支持度進行綜合度量，由于低支持度及高置信度規則容易產生高興趣度規則，因此能挖掘出一些具有實際應用價值且難以被用戶預測的關聯規則。

3.3.2 理解度

支持度和置信度標準依據規則在整個數據庫中的出現次數來評估其質量，若規則出現的次數越多則認為這是一條有效規則，但僅考慮這兩個標準生成的規則可能包含大量屬性，難以被用戶理解[35]，從而此類規則被使用的概率非常低。基于上述原因，理解度標準被提出且廣泛應用于規則的衡量之中，該標準從規則的簡潔性和包含的信息量進行綜合度量，規則越簡潔、信息量越大，則越容易被人理解。文獻[31-34，36]引入一種使用較多的理解度標準，其計算公式如下所示：

式（16）中，|Y|、|X∪Y|分別表示規則后件和總的規則中包含的屬性數量，ln 函數用于標準化函數值的范圍，若規則包含的總屬性數量較少且規則后件包含的屬性較多，則該評估標準能夠挖掘出易被理解的規則。

3.3.3 相似度

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

式（17）中，support(ARi,ARj)為ARi及ARj包含的事務在數據庫中出現的次數，support(ARi)為ARi包含的事務在數據庫出現的次數，若規則ARi與ARj不存在相似關系，則Simi[i,j]=0。該評估標準綜合考慮規則ARi及ARj支持度概率分布的相似程度，對挖掘出的相似規則進行篩選，能夠挖掘出更為有效的規則。

上述文獻均考慮多種評估標準對規則質量進行衡量，從而避免僅考慮支持度和置信度所造成的缺陷。

3.4 PSO 算法與其他關聯規則挖掘算法對比

本文選取了5 個在關聯規則挖掘領域中被廣泛應用的算法與PSO 算法進行對比，結果如表2 所示。

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

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

Table 2 Comparison of association rule mining algorithms表2 關聯規則挖掘算法比較

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

4 改進PSO 算法在關聯規則挖掘中的研究

4.1 基于參數的改進

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

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

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

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

4.2 基于變異機制的改進

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

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

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

文獻[54]指出基于PSO 算法的關聯規則挖掘的最大缺點是用戶必須指定生成最佳規則的數量，以及該算法在迭代次數過多情況下的時間復雜度高于Apriori 算法，處理大型數據集時效率較慢。基于上述考慮，Tahyudin 等人[32]將PSO 算法和柯西分布相結合求解數值關聯規則挖掘問題，利用柯西變異進行跳躍搜索獲得全局最優解，避免算法陷入局部最優，擴展粒子的搜索空間及增強粒子的進化能力。柯西變異策略能幫助粒子在大鄰域內尋找其最優解，使算法具有魯棒性，因此也適用于大型數據集的關聯規則挖掘。大部分變異粒子圍繞柯西分布中心進行分散，雖然減緩了粒子向局部最優位置聚集的趨勢，但不能完全避免其陷入局部最優。

4.3 混合PSO 算法

PSO 算法與其他優化算法相結合可以充分發揮不同算法的優點，彌補各自算法的不足。混合PSO 算法主要分為三種類型：第一類將PSO 算法與精確算法進行混合；第二類將PSO 算法與其他智能算法進行混合；第三類將PSO 算法與神經網絡進行混合。

4.3.1 混合精確算法

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

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

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

4.3.2 混合智能算法

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

4.3.3 混合神經網絡

人工神經網絡（artificial neural network，ANN）具有自學習、自組織、自適應和非線性動態處理等特性，PSO 算法與ANN 的結合能更有效解決實際問題。Dhanalaxmi 等人[71]使用分類關聯規則挖掘方法對軟件缺陷進行分類，避免軟件缺陷的產生，而軟件缺陷數量越少則表明軟件質量越高。該方法在挖掘關聯規則之前，使用自適應PSO 算法對規則進行優化，提供更具體的聚類結果，避免挖掘到大量無效規則。之后，使用前饋反向傳播神經網絡（feed forward back propagation neural network，FFBNN）分類器對確定的實際缺陷進行分類，改進后的分類關聯規則挖掘方法精確度達到99.5%。

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

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

5 PSO 算法在關聯規則挖掘中的應用

在處理復雜的現實優化問題時，智能算法引導群體方向進行逐步搜索直至獲得解決方案，此類算法在搜索過程中不受優化函數形態的約束，適應性強、運行效率高，因此被應用于各種領域，并且在解決大多數高度非線性和多模態的優化問題方面表現良好[27]。與精確算法相比，智能算法在解決關聯規則挖掘問題時由于隨機搜索的特性可能不會獲取全部解決方案，但能在合理的時間內獲得足夠好的解決方案。

隨著智能算法在關聯規則挖掘中的不斷發展，PSO 算法被廣泛應用于不同領域。購物籃問題是一類超市商品交易問題，通過對顧客的交易信息進行分析從而對商品進行決策，關聯規則挖掘算法主要針對購物籃問題被提出，同時也被廣泛用于解決購物籃問題。文獻[77]對超市購物數據進行動態關聯規則挖掘，提出一種改進PSO 算法的灰色模型，通過增加緩沖算子，引入二次搜索機制對PSO 算法進行改進，優化求解灰色模型不同時刻的背景值，以提高PSO 算法的局部搜索能力，從而提高灰色模型的預測精度。文獻[78]考慮到傳統頻繁項集挖掘算法主要用于尋找頻繁出現的商品組合，而不關注商品的其他屬性，比如銷量、銷售價和進貨價等。為了進一步獲取具有高利潤的商品組合，發現具有高效用（例如，高利潤）的項集，提出一種基于高效用項集挖掘[79]（high utility itemset mining，HUIM）的HUIM-IPSO 算法，實驗表明該算法具有更高的挖掘效率和更快的收斂速度。HUIM-IPSO 算法的時間復雜度與傳統PSO 算法的時間復雜度一致，假設PSO 算法中粒子的數量為m，迭代次數為N，每個粒子每一次迭代需要的運算時間為T，算法總的運行時間為m×N×T。

近些年，PSO 算法由于其實現簡單、收斂速度快等優點被成功應用于金融領域，其中股票走勢分析需要綜合分析各股票漲跌情況、現金流入量、相關政策和GDP 等多種數據信息。傳統數學統計分析方法主要針對單一股票信息進行預測，而股票走勢往往與同行業中其他公司甚至其他行業的經營情況密切相關，因此對于股票的走勢預測準確率不高。同時，股票預測數據具有規模大、維度高、價值密度低和實時性要求高等特點，使用Apriori 算法需要花費大量時間多次掃描數據，容易造成對股票走勢的誤判與延時，無法適用于實時性極高的股票關聯預測分析。基于上述原因，文獻[80]提出一種使用協同粒子群優化的股票關聯規則挖掘方法用于預測股票走勢，主要針對傳統數據分析方法對股票走勢進行預測時具有準確率不高，時效性不強的缺陷，該方法分別使用PSO 算法對支持度與置信度進行挖掘優化，較Apriori 算法和PSO 算法在準確率與挖掘速率上有了很大的提高。文獻[81]同樣對股票信息進行挖掘，主要針對投資者的股票交易數據，首先使用PSO 算法優化支持度和置信度的閾值，之后通過閾值篩選出合適的粒子即關聯規則，基于PSO 算法的關聯規則挖掘方法能挖掘出投資者與購買股票間的關聯規則，有利于投資者進行決策。

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

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

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

6 總結與展望

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

隨著數據的爆炸增長，從中挖掘到有效關聯規則越來越困難，因此，該領域在未來研究中仍是具有挑戰性的方向，未來的研究工作重點可能主要在以下方面：

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

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

（3）現有研究中，基于PSO 的關聯規則挖掘算法雖已被成功運用于多種領域，但涉及現實生活中的應用領域仍然有限，針對大部分領域的應用還處于初步階段，相關研究較少。因此，研究新的關聯規則應用領域，在應用的廣度和深度上進行拓展都是很有價值的工作。