協(xié)同進(jìn)化算法在關(guān)聯(lián)規(guī)則挖掘中的研究

潘唯　湯亞玲

摘要：文中結(jié)合遺傳算法和粒子群優(yōu)化算法各自的優(yōu)勢(shì)，采用協(xié)同進(jìn)化的思想，同時(shí)應(yīng)用兩種算法來(lái)遍歷兩個(gè)種群，并引入它們的信息交互機(jī)制。最后，實(shí)驗(yàn)和應(yīng)用證明，在可接受的時(shí)間復(fù)雜度的前提下，協(xié)同進(jìn)化算法不但能繼承傳統(tǒng)遺傳算法的優(yōu)越性，有效地減少掃描數(shù)據(jù)庫(kù)的次數(shù)，和產(chǎn)生小規(guī)模的候選項(xiàng)目集；而且通過(guò)比較協(xié)同進(jìn)化算法，傳統(tǒng)的遺傳算法和粒子群優(yōu)化算法的屬性，在關(guān)聯(lián)規(guī)則挖掘中使用該算法，能避免早熟的現(xiàn)象。采取協(xié)同進(jìn)化算法時(shí)可以發(fā)現(xiàn)高品質(zhì)的關(guān)聯(lián)規(guī)則，尤其是在高維數(shù)據(jù)庫(kù)中。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則挖掘；協(xié)同進(jìn)化算法；遺傳算法；粒子群優(yōu)化算法；概率調(diào)整

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）02-0295-03

關(guān)聯(lián)規(guī)則挖掘是發(fā)現(xiàn)一個(gè)大數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)之間的潛在關(guān)系， 它可以幫助不同的領(lǐng)域決策者確定合適的策略，是數(shù)據(jù)挖掘研究中的一個(gè)重要分支 。而其中最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法當(dāng)屬apriori算法，但隨著研究的發(fā)展，Apriori算法多次掃描數(shù)據(jù)庫(kù)和產(chǎn)生大量候選頻繁項(xiàng)集的兩大缺陷逐漸顯露出來(lái)。針對(duì)Apriori算法的這些問(wèn)題，研究人員已經(jīng)提出了許多改進(jìn)的算法來(lái)彌補(bǔ)其缺點(diǎn)，如FP增長(zhǎng)算法，分區(qū)算法。與Apriori算法相比，這些算法的性能已經(jīng)有顯著的提高，但在某些場(chǎng)合使用這些算法挖掘大規(guī)模高維數(shù)據(jù)仍然是不現(xiàn)實(shí)的。該文是利用協(xié)同進(jìn)化的思想，結(jié)合遺傳算法和粒子群優(yōu)化算法的優(yōu)勢(shì)，從數(shù)據(jù)集中挖掘高質(zhì)量的規(guī)則。

1 協(xié)同進(jìn)化的理論思想

協(xié)同進(jìn)化概念首次是由Ehrlich和Raven提出來(lái)的，其核心思想是：種群的相互作用是彼此生存的不可或缺的條件。在長(zhǎng)期的進(jìn)化過(guò)程中，它們是相互依存的，并提高個(gè)體和整體的性能 。通過(guò)引入這個(gè)概念說(shuō)明，演化不僅是與自己的種群有關(guān)，也影響了與它接觸的種群。協(xié)同進(jìn)化的概念有一個(gè)很寬的范圍，包括多PSO協(xié)同進(jìn)化算法，協(xié)同進(jìn)化遺傳算法等。

在本文中我們使用“GA-PSO”的協(xié)同進(jìn)化，使用GA和PSO相互遍歷。結(jié)合兩種算法的優(yōu)點(diǎn)，巧妙運(yùn)用協(xié)同進(jìn)化的思想，從大型數(shù)據(jù)中挖掘高品質(zhì)的有趣的規(guī)則。為了實(shí)現(xiàn)這樣的想法，我們?cè)O(shè)計(jì)了一個(gè)信息交換機(jī)制。使兩個(gè)種群之間的信息得到交換，能夠?qū)崿F(xiàn)共同進(jìn)化的目的。

2 協(xié)同進(jìn)化算法的搜索策略

2.1 GA搜索策略

GA做了以下改進(jìn)，以確保該信息可以在兩個(gè)種群之間傳遞。

2.1.1 編碼規(guī)則

關(guān)聯(lián)規(guī)則挖掘的搜索空間相當(dāng)于整個(gè)交易的數(shù)據(jù)庫(kù)，該方法以一個(gè)實(shí)數(shù)數(shù)組編碼。在一個(gè)數(shù)組中，元素序號(hào)對(duì)應(yīng)于交易數(shù)據(jù)庫(kù)的字段，元素的值代表該字段的屬性值。

3 協(xié)同進(jìn)化算法

本文使用了協(xié)同進(jìn)化的思想，在傳統(tǒng)遺傳算法用于關(guān)聯(lián)規(guī)則挖掘時(shí)，有助于避免過(guò)早收斂。具體步驟如下所述：

1）首先根據(jù)數(shù)據(jù)集隨機(jī)產(chǎn)生POP1和POP2兩個(gè)初始種群，分別使用PSO和GA算法的搜索策略挖掘關(guān)聯(lián)規(guī)則。兩個(gè)群體使用相同的編碼規(guī)則，適應(yīng)度函數(shù)，種群規(guī)模和最大迭代數(shù)。

2）初始化兩個(gè)種群的各種參數(shù)：慣性因子，最小支持度和最小置信度的閾值，前項(xiàng)集和后項(xiàng)集的約束條件。

3）掃描數(shù)據(jù)庫(kù)，使用適應(yīng)函數(shù)計(jì)算兩個(gè)種群中的個(gè)體適應(yīng)度。然后，保留具有資格的個(gè)體進(jìn)入各自的下代，消除不符合規(guī)定的個(gè)體。比較POP1和POP2中全局最優(yōu)個(gè)體的適應(yīng)度，適應(yīng)度較大的個(gè)體將取代另一個(gè)種群的最佳個(gè)體，成為下一代進(jìn)化的基礎(chǔ)。

4）判斷是否滿足終止條件：如果滿足收斂條件或者迭代次數(shù)已經(jīng)達(dá)到了最大迭代次數(shù)，則算法結(jié)束，切換到第6步。否則，繼續(xù)到下一個(gè)步驟5。

5）根據(jù)式（4）和式（5）更新POP1中的粒子速度和位置，產(chǎn)生下一代。POP2則是通過(guò)遺傳操作來(lái)進(jìn)化、產(chǎn)生下一代。然后跳轉(zhuǎn)到第三步計(jì)算適應(yīng)度。

6）輸出挖掘到的關(guān)聯(lián)規(guī)則。

當(dāng)POP1中的粒子陷入局部最優(yōu)時(shí)，這些個(gè)體將不僅使用當(dāng)前種群的經(jīng)驗(yàn)來(lái)更新位置，還將借鑒POP2中的最佳個(gè)體。利用POP2中的優(yōu)秀個(gè)體，可以引導(dǎo)已經(jīng)陷入局部最優(yōu)值個(gè)體跳出局部極小的困境。因此，有更大的概率得到全局最優(yōu)解。

4 實(shí)驗(yàn)分析和應(yīng)用

在Win7中用MATLAB運(yùn)行協(xié)同進(jìn)化算法。通過(guò)跟蹤，比較GA，PSO，以及協(xié)同進(jìn)化算法的運(yùn)行時(shí)間和種群的平均適應(yīng)度。

實(shí)驗(yàn)數(shù)據(jù)庫(kù)來(lái)源于UCI的植物數(shù)據(jù)集，該數(shù)據(jù)集有22632個(gè)數(shù)據(jù)元素，和 70的維數(shù)。實(shí)驗(yàn)環(huán)境：英特爾處理器I3系列的M350 頻率為2.75GHz 雙核和2 GB的RAM的筆記本電腦。實(shí)驗(yàn)參數(shù)見(jiàn)表1，進(jìn)化結(jié)果如圖1。

5 結(jié)論

本文提出了一種協(xié)同進(jìn)化算法，使用GA和PSO同時(shí)遍歷兩個(gè)種群。引入了一種交換種群之間信息的機(jī)制，使得這兩個(gè)種群可以共同發(fā)展。通過(guò)實(shí)驗(yàn)證明，協(xié)同進(jìn)化算法運(yùn)行時(shí)間比其他兩個(gè)全局優(yōu)化算法稍長(zhǎng)，卻是可以接受的。相比其他兩個(gè)算法，協(xié)同進(jìn)化算法不僅是挖掘質(zhì)量高，還具有顯著跳出局部最優(yōu)解的能力。

參考文獻(xiàn)：

[1] Han J， Kamber M.Data Mining： Concepts and Techniques， 2nd edn.， China Machine Press，2011：146-155.

[2] Agrawal R， Imielinski T， Swami A. Mining Association Rules between Sets of Items in Large Databases[C]//Proc.1993 ACM-SIGMOD Int. Conf. Management of Databases，. ACM Press， Washington， 1993： 20-72.

[3] Han J， Pei J， Yin Y. Mining frequent patterns without candidate generation. In： Proceedings of the 2000 ACM-SIGMOD International Conference on Management of Data， Dallas， Texas， ACM Press ，2000： 1-12.

[4] Savasere A. Omiecinski E， Navathe S. An efficient algorithm for mining association rules in large databases[C]//Dayal U， Gray P M D， Nishio S.Proceedings of the 21th International Conference on Very Large Databases（VLDB 1995）， Zurich， Morgan Kaufmann Publisher ，1995： 432-443.

[5] Wiegand R P. An analysis of cooperative co-evolutionary algorithms. George Mason University， Fairfax，2003.

[6] Sharma S K， Irwin G W.Fuzzy coding of genetic algorithms. IEEE Trans. Evolutionary Computation， 2003： 344-355.

[7] Thierens D.Adaptive mutation rate control schemes in genetic algorithms[C].Proceedings of the 2002 Congress on Evolutionary Computation， CEC 2002， 2002（1）： 980-985.

[8] Shi Y， Eberhart R C.Parameter Selection in Particle Swarm Adaptation[C].Porto V W， Waagen D.EP 1998. LNCS， Springer， Heidelberg ，1998（1447）： 591-600.