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

楊光軍

德州學(xué)院 機(jī)電工程系，山東 德州 253023

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

楊光軍

德州學(xué)院 機(jī)電工程系，山東 德州 253023

1 引言

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

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

2 免疫克隆算法

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

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

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

3 文化算法

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

圖1 文化算法基本結(jié)構(gòu)

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

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

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

4.1 種群空間設(shè)計(jì)

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

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

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

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

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

4.2 信念空間設(shè)計(jì)

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

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

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

4.3 接受操作

該算法用接受操作將種群空間的免疫克隆算法的優(yōu)秀個(gè)體更新信念空間。在種群空間的免疫克隆算法的演化過(guò)程中，每運(yùn)行ΑcceptStep代時(shí)，用記憶細(xì)胞群中當(dāng)前的最優(yōu)個(gè)體來(lái)替換信念空間中最差的個(gè)體。本文取ΑcceptStep=8。

4.4 影響操作

4.5 算法流程

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

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

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

（3）通過(guò)Update（）來(lái)更新信念空間的狀況知識(shí)和歷史知識(shí)。

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

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

5 實(shí)驗(yàn)結(jié)果及分析

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

表2 實(shí)驗(yàn)結(jié)果

從表2的實(shí)驗(yàn)數(shù)據(jù)可以看出，基于文化免疫克隆算法的關(guān)聯(lián)規(guī)則挖掘算法MAR-CICA用時(shí)少而規(guī)則提取率高。這是因?yàn)樵谖幕惴ǖ男拍羁臻g各種知識(shí)結(jié)構(gòu)的指導(dǎo)下，減弱了免疫克隆算法在計(jì)算過(guò)程中的盲目性和隨機(jī)性，提高了收斂速度和搜索效率，從而促進(jìn)進(jìn)化過(guò)程。特別是在數(shù)據(jù)集較大的時(shí)候，這種優(yōu)勢(shì)更加明顯。

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

6 結(jié)論

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

（1）將免疫克隆算法與文化算法相結(jié)合，采用雙層進(jìn)化機(jī)制，利用免疫克隆算法的智能搜索能力和文化算法信念空間知識(shí)的指導(dǎo)來(lái)挖掘規(guī)則。

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

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

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

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

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

[3]朱玉，張虹，孔令東.基于人工免疫的多維關(guān)聯(lián)規(guī)則挖掘及其應(yīng)用研究[J].計(jì)算機(jī)科學(xué)，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ù)挖掘與知識(shí)發(fā)現(xiàn)[M].西安：西安電子科技大學(xué)出版社，2006.

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

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

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

[9]郭一楠，王輝，程健.自適應(yīng)免疫克隆選擇文化算法[J].電子學(xué)報(bào)，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]羌亮.基于人工免疫的關(guān)聯(lián)規(guī)則挖掘算法的研究[D].南京：東南大學(xué)，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

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

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

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—），男，講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)技術(shù)，數(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