楊光軍

德州學院 機電工程系，山東 德州 253023

基于文化免疫克隆算法的關聯(lián)規(guī)則挖掘研究

楊光軍

德州學院 機電工程系，山東 德州 253023

1 引言

關聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘的重要任務之一，其目的是在數(shù)據(jù)集中發(fā)現(xiàn)項集之間關聯(lián)性。主要的關聯(lián)規(guī)則發(fā)現(xiàn)算法有Apriori算法及其改進算法、FP-growth等[1]，這些方法計算復雜度高、效率非常低。許多研究人員致力于將智能算法如遺傳算法[2]、免疫算法[3]等應用于關聯(lián)規(guī)則挖掘。其中人工免疫算法是一種多點和隨機的搜索策略，為關聯(lián)規(guī)則挖掘問題提供了一種新穎的解決方法，但其在進化過程中交叉變異的盲目性和隨機性導致收斂速度較慢。而文化算法[4]可以將其他的群體算法融合在文化的框架內，能夠使群體以一定的速度進化和適應環(huán)境，并互相彌補各傳統(tǒng)算法的不足。

本文采用文化算法的框架結構，將免疫克隆算法嵌入其中，利用免疫克隆算法在數(shù)據(jù)庫中迅速搜索關聯(lián)規(guī)則，利用文化算法形成的公共認知信念指導和加速搜索。實驗表明，該模型具有較快的收斂速度，所得關聯(lián)規(guī)則的準確率較高。

2 免疫克隆算法

人工免疫是近幾年在智能技術學科方面的研究較多的領域之一。免疫克隆算法[5]是諸多免疫優(yōu)化算法之一，模擬人的免疫應答原理，具有免疫應答的基本特征，而且克隆操作使算法具有獨特的收斂性，從而提高了算法的收斂速度。

免疫克隆算法的克隆算子包括：克隆、克隆交叉、克隆變異和克隆選擇?？贵w群的狀態(tài)轉移情況可以表示成如下的隨機過程：

克隆算子能有效擴大群體的規(guī)模，每個抗體與抗原的親合度越大，抗體的克隆規(guī)模也就越大?？寺〗徊媸侵赴褍蓚€抗體的部分結構加以替換重組而生成新抗體的操作。克隆變異對種群實施高頻變異，提高種群中個體的多樣性?？寺∵x擇是從變異后的抗體中選擇優(yōu)秀的個體，形成新的種群。

3 文化算法

在人類社會中，個體所獲得的知識以一種公共認知的形式影響著社會中其他的個體，加速社會整體的進化，幫助個體更加適應環(huán)境，從而形成文化。1994年Reynolds等人提出了文化算法[4]，模擬人類社會的文化進化過程，采用雙層進化機制，在傳統(tǒng)的基于種群的進化算法基礎上，構建信念空間來提取隱含在進化過程中的各類信息，并以知識的形式加以存儲，最終用于指導進化過程，后來學者們對文化算法進行了更系統(tǒng)的研究[6-7]。其基本結構如圖1所示。

圖1 文化算法基本結構

種群空間用于實現(xiàn)任何基于種群的進化算法，一方面通過objective（）函數(shù)對個體實現(xiàn)評價，使用generate（）函數(shù)生成下一代個體，select（）函數(shù)選擇個體作為下一代群體，另一方面將優(yōu)良個體作為樣本通過accept（）函數(shù)傳遞到信念空間。信念空間在update（）函數(shù)的作用下提取樣本個體所攜帶的隱含信息，以知識的形式加以描述和儲存，再通過influence（）函數(shù)對種群空間中個體的行為規(guī)則進行修改，以使個體空間得到更高的進化效率。文化算法雖然增加了維護信念空間以及兩空間信息映射和交互的開銷，但其利用在進化過程中積累的知識指導進化，增強了搜索的目的性，其整體搜索效率高于單純基于生物進化的優(yōu)化算法[8]。

4 基于文化免疫克隆算法的關聯(lián)規(guī)則挖掘算法設計

文化算法可以將其他的種群算法融合在文化的框架內，能夠使種群以一定的速度進化和適應環(huán)境，將免疫克隆算法與文化算法相結合具有更穩(wěn)定的全局收斂性能及較快的收斂速度[8-9]。本文基于文化算法的模型，建立免疫克隆算法的種群空間與信念空間的雙重演化及互相影響，構成基于文化免疫克隆算法的關聯(lián)規(guī)則挖掘算法MAR-CICA（Mining Association Rules based on Cultured Immune Clone Algorithm）。具體構造如下。

4.1 種群空間設計

種群空間進化操作采用免疫克隆算法。使用免疫克隆算法進行關聯(lián)規(guī)則挖掘時，將數(shù)據(jù)庫中的所有記錄作為抗原，候選模式作為抗體。將抗體與抗原作比較，與較多抗原匹配程度高的抗體將獲得更大的存活和克隆變異的機會。免疫學習的過程，便是個體親合度提高的過程，同時也是頻繁模式生成并通過免疫記憶機制得以保存的過程。最后，關聯(lián)規(guī)則由記憶細胞群所代表的頻繁模式生成。

（1）編碼方案：該算法中采用二進制編碼。在二進制串中1表示該值被選中，0表示該值未被選中。

（2）親合度計算：親合度函數(shù)f是評價抗體與抗原聯(lián)系的量化反映，它的選取對于挖掘結果具有舉足輕重的作用。親合度函數(shù)定義為：f(X?Y)=supp(X?Y)+conf(X?Y)，其中supp(X?Y)表示X?Y的支持度，conf(X?Y)表示X?Y的置信度。

f(X?Y)表明只有支持度和置信度都高才有可能生存下來。

（3）進化操作過程：①隨機在解空間產(chǎn)生N個抗體形成初始抗體群Α0。種群的規(guī)模為N。初始記憶細胞群為空。進化代數(shù)k=0。②計算抗體親合度。從數(shù)據(jù)庫中隨機抽取M條記錄，根據(jù)公式計算抗體群Α中的抗體和M條記錄的親合度。從種群中根據(jù)親合度的大小選取親合度較大S個抗體組成作為記憶細胞加入記憶細胞群Pk。③根據(jù)親合度和抗體規(guī)模，進行克隆操作，錯位交叉操作，高頻變異操作，選擇操作，獲得新的抗體群Αk+1。④判斷循環(huán)條件，若條件滿足，終止循環(huán)；不然，k=k+1，轉入步驟②。

4.2 信念空間設計

隨著文化算法的發(fā)展，研究人員先后提出五類信念空間的知識描述方式[6]，包括標準知識、狀況知識、拓撲知識、領域知識和歷史知識。這五類知識記錄的信息不同，對算法具有不同的引導作用，適用于不同場合。本文算法需要保存進化過程中的較優(yōu)個體，并且為了加快收斂速度，該算法需要監(jiān)控算法的搜索過程，所以該算法的信念空間采用狀況知識和歷史知識，即信念空間的結構采用 ＜E，H＞結構，其中E=＜E1，E2，…，En＞為狀況知識，Ei為第i個較優(yōu)個體，n為狀況知識容量；H=＜H1，H2，…，Hm＞為歷史知識，Hj表示記錄的第j個重要事件，m為歷史知識容量。

（1）狀況知識：在該算法中，狀況知識用于記錄進化過程中的較優(yōu)個體，而進化過程中的優(yōu)秀個體保存在免疫克隆算法的記憶細胞群中，因此狀況知識就是免疫克隆算法的記憶單元，即狀況知識的結構為＜X1，X2，…，Xn＞，其中Xi是記憶細胞群中的優(yōu)秀個體。狀況知識的更新規(guī)則為：

（2）歷史知識：免疫克隆算法在進化過程中常出現(xiàn)的問題是早熟，陷入局部最優(yōu)解，該算法利用歷史知識監(jiān)控算法的收斂情況，設計一種變異算子，自適應調節(jié)變異的尺度，引導算法的搜索方向。

4.3 接受操作

該算法用接受操作將種群空間的免疫克隆算法的優(yōu)秀個體更新信念空間。在種群空間的免疫克隆算法的演化過程中，每運行ΑcceptStep代時，用記憶細胞群中當前的最優(yōu)個體來替換信念空間中最差的個體。本文取ΑcceptStep=8。

4.4 影響操作

4.5 算法流程

本文提出的基于文化免疫克隆算法的關聯(lián)規(guī)則挖掘算法MAR-CICA的算法流程如下：

（1）初始化種群空間和信念空間，并設置最大進化代數(shù)、選擇概率、交叉概率、變異概率、狀況知識容量和歷史知識容量等參數(shù)。

（2）種群空間演化：計算親合度、克隆、交叉、變異和選擇。

（3）通過Update（）來更新信念空間的狀況知識和歷史知識。

（4）根據(jù)信念空間的個體通過Influence（）影響種群空間。

（5）判斷是否滿足終止條件，若條件滿足則終止；否則k=k+1，轉入步驟（2）。本文設定最大進化代數(shù)Gmax作為判斷條件，當進化代數(shù)大于Gmax時終止程序。

5 實驗結果及分析

本文分別選用通用的人工合成標準數(shù)據(jù)庫（IBM QUESΤ[10]中的代碼生成，記為D1）和UCI機器學習數(shù)據(jù)庫中的mushroom數(shù)據(jù)集（http：//archive.ics.uci.edu/ml/datasets.html，記為D2）仿真實驗，在數(shù)據(jù)集上分別實現(xiàn)了基于免疫克隆的關聯(lián)規(guī)則挖掘算法[11]和本文算法MAR-CICA，以檢驗所提出算法的性能。取支持度為0.2%，置信度為60%。實驗數(shù)據(jù)集特性和實驗結果分別如表1和表2所示。

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

表2 實驗結果

從表2的實驗數(shù)據(jù)可以看出，基于文化免疫克隆算法的關聯(lián)規(guī)則挖掘算法MAR-CICA用時少而規(guī)則提取率高。這是因為在文化算法的信念空間各種知識結構的指導下，減弱了免疫克隆算法在計算過程中的盲目性和隨機性，提高了收斂速度和搜索效率，從而促進進化過程。特別是在數(shù)據(jù)集較大的時候，這種優(yōu)勢更加明顯。

通過實驗的結果分析，可以發(fā)現(xiàn)基于文化免疫克隆算法的關聯(lián)規(guī)則挖掘算法具有收斂速度快的特點，具有較好的全局及局部搜索能力，還可以得到更多的符合條件的關聯(lián)規(guī)則。

6 結論

針對傳統(tǒng)關聯(lián)規(guī)則挖掘過程中出現(xiàn)的計算量大，效率低下的問題，本文提出了一種基于文化算法和免疫克隆算法的關聯(lián)規(guī)則挖掘算法，這種方法有以下特點：

（1）將免疫克隆算法與文化算法相結合，采用雙層進化機制，利用免疫克隆算法的智能搜索能力和文化算法信念空間知識的指導來挖掘規(guī)則。

（2）根據(jù)免疫克隆算法的特點，重新給出了文化算法中狀況知識和歷史知識的描述，并設計了一種變異算子，能夠自適應調節(jié)變異尺度。

（3）挖掘過程也不需生成大量的頻繁項目集，提高了關聯(lián)規(guī)則挖掘的效率。

但如何設置各種參數(shù)使免疫克隆算法與文化算法有效結合起來，真正獲得對種群進化起促進作用的“文化”，以便于更好地進行關聯(lián)規(guī)則挖掘是今后進一步研究的工作。

[1]Han J W，Kamber M.數(shù)據(jù)挖掘：概念與技術[M].北京：機械工業(yè)出版社，2006.

[2]符保龍.基于混合遺傳克隆算法的關聯(lián)規(guī)則挖掘[J].計算機工程，2009，35（22）：216-220.

[3]朱玉，張虹，孔令東.基于人工免疫的多維關聯(lián)規(guī)則挖掘及其應用研究[J].計算機科學，2009，36（8）：239-242.

[4]Reynolds R G.An introduction to cultural algorithms[C]//Proc of the 3rd Annual Conf on Evolution Programming.[S.l.]：World Scientific Publishing，1994：131-136.

[5]焦李成，劉芳，緱水平，等.智能數(shù)據(jù)挖掘與知識發(fā)現(xiàn)[M].西安：西安電子科技大學出版社，2006.

[6]劉純青.文化算法及其應用研究[D].哈爾濱：哈爾濱工程大學，2007.

[7]Peng B.Knowledge and population swarms in cultural algorithms for dynamic environments[D].USA：Wayne State University，2005.

[8]覃暉，周建中，李英海，等.基于文化克隆選擇算法的梯級水電站聯(lián)合優(yōu)化調度[J].系統(tǒng)仿真學報，2010，22（10）：2342-2346.

[9]郭一楠，王輝，程健.自適應免疫克隆選擇文化算法[J].電子學報，2010，38（4）：966-972.

[10]Agrawal R，Imielinski Τ，Swami A.Mining association rules between sets of items in large databases[C]//Proceedings of the ACM SIGMOD，Washington D.C.，1993.

[11]羌亮.基于人工免疫的關聯(lián)規(guī)則挖掘算法的研究[D].南京：東南大學，2006.

YANG Guangjun

Mechanical Electronic Engineering Department,Dezhou University,Dezhou,Shandong 253023,China

For the association rules mining,a method of mining association rules based on cultured immune clone algorithm is proposed.Τhis method uses two-layer evolutionary mechanism and embeds the immune clone algorithm in the culture algorithm framework.It uses the intelligent searching ability of the immune clone algorithm and the commonly accepted knowledge in the culture algorithm to guide the rules mining.Τhe situational knowledge and history knowledge in the culture algorithm are redefined,and a new mutation operator is put forward.Τhis operator has the adaptive adjustment of mutation measure to improve the global search ability of immune clone algorithm.Τhe experiments show that the new algorithm is superior to immune clone algorithm in performance speed and the rules’accuracy.

association rules;immune clone algorithm;culture algorithm;self-adaptive mutation operator;two-layer evolutionary mechanism

針對關聯(lián)規(guī)則挖掘問題，給出一種基于文化免疫克隆算法的關聯(lián)規(guī)則挖掘方法，該方法將免疫克隆算法嵌入到文化算法的框架中，采用雙層進化機制，利用免疫克隆算法的智能搜索能力和文化算法信念空間形成的公共認知信念的引導挖掘規(guī)則。該方法重新給出了文化算法中狀況知識和歷史知識的描述，設計了一種變異算子，能夠自適應調節(jié)變異尺度，提高免疫克隆算法全局搜索能力。實驗表明，該算法的運行速度和所得關聯(lián)規(guī)則的準確率優(yōu)于免疫克隆算法。

關聯(lián)規(guī)則；免疫克隆算法；文化算法；自適應變異算子；雙層進化機制

A

ΤP311

10.3778/j.issn.1002-8331.1112-0043

YANG Guangjun.Mining association rules based on cultured immune clone algorithm.Computer Engineering and Applications,2013,49（15）：113-115.

楊光軍（1977—），男，講師，主要研究領域為數(shù)據(jù)庫技術，數(shù)據(jù)挖掘。E-mail：guangjun_yang@126.com

2011-12-05

2012-01-13

1002-8331（2013）15-0113-03

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120521.1142.086.html