基于ＧＥＰ與小生境的關(guān)聯(lián)規(guī)則挖掘的研究

(華中科技大學(xué) 圖像識(shí)別與人工智能研究所 圖像信息處理與智能控制教育部重點(diǎn)實(shí)驗(yàn)室， 武漢 430074)



摘 要：如何高效而正確地挖掘關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究方向。在現(xiàn)有工作的基礎(chǔ)上結(jié)合基因表達(dá)式編程進(jìn)化算法提出了一種新的挖掘強(qiáng)關(guān)聯(lián)規(guī)則的算法框架；提出并實(shí)現(xiàn)了基于小生境技術(shù)的基因表達(dá)式編程算法(nichegene expression programming，NGEP)以用于挖掘關(guān)聯(lián)規(guī)則。與同類算法的對比實(shí)驗(yàn)結(jié)果表明，NGEP不但能更快地收斂，還進(jìn)一步提高了挖掘的正確率。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則； 基因表達(dá)式編程； 進(jìn)化算法； 小生境

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)01005603



Research on GEPbased algorithm and niche technology inassociation rule mining

HUANG Gang， YANG Jie， LI Dehua， PAN Ying



(State Commission Research Laboratory of Image Processing Intelligent Control， Institute of Pattern Recognition Artificial Intelligence， Huazhong University of Science Technology， Wuhan 430074， China)



Abstract:Mining association rules in large databases efficiently and effectively is becoming one of the most important and popular ways of knowledge discovery. Combine with the technology of data mining and gene expression programming and niche technology， this paper put forword a new arithmetic NGEP(michegene expression programming). Compared with GAAA， NGEP can gain faster convergence and better solutions.

Key words：association rule; gene expression programming; genetic algorithm; niche



數(shù)據(jù)挖掘在最近幾年里已被業(yè)界廣泛研究，關(guān)聯(lián)規(guī)則的挖掘就是其中一個(gè)重要的研究熱點(diǎn)。近年來相關(guān)的工作有了長足的發(fā)展，如文獻(xiàn)[1~8]，大致可分為以下兩類：一類是在經(jīng)典Apriori算法的基礎(chǔ)上進(jìn)行改進(jìn)[1~3]，但由于需要多次搜索數(shù)據(jù)庫以形成頻繁集(frequent itemsets)而導(dǎo)致計(jì)算量巨大，面對海量數(shù)據(jù)庫時(shí)算法效率銳減；另一類結(jié)合人工智能的方法(如仿生學(xué)或神經(jīng)網(wǎng)絡(luò)等)直接從實(shí)驗(yàn)樣本中抽取關(guān)聯(lián)規(guī)則[4，8]。但是應(yīng)用遺傳算法進(jìn)行挖掘時(shí)可能存在收斂速度慢或漏報(bào)規(guī)則的問題，其主要原因是規(guī)則平面極不光滑，是一個(gè)復(fù)雜的多峰值搜索問題。在文獻(xiàn)[9，10]的基礎(chǔ)上結(jié)合小生境技術(shù)，提出并實(shí)現(xiàn)了基于小生境的基因表達(dá)式編程算法(NGEP)。NGEP充分利用小生境技術(shù)便于多目標(biāo)多峰值搜索的特點(diǎn)，結(jié)合基因表達(dá)式編程算法(GEP)操作簡單、魯棒性強(qiáng)的優(yōu)勢對解空間進(jìn)行搜索，既保證了解集分布的均勻性和多樣性，又加快了收斂的快速。

1 相關(guān)概念和描述

1.1 關(guān)聯(lián)規(guī)則

設(shè)I={i1，i2，…，im}是m個(gè)不同項(xiàng)目的一個(gè)集合。關(guān)聯(lián)規(guī)則可以表示為R：XY。其中：XI，YI，且X∩Y=。

關(guān)聯(lián)規(guī)則具有如下兩個(gè)重要的屬性：支持度sup(XY)和置信度conf(XY)。同時(shí)滿足最小支持度min_sup和置信度min_conf的規(guī)則被稱為強(qiáng)規(guī)則。在本文中，簡記為

supx，y=sup(XY)， confx，y=conf(XY)。

1.2 GEP算法

GEP算法是一種新的基于基因型和表現(xiàn)型的自適應(yīng)演化算法。它的主要特點(diǎn)是利用定長的線性串(基因型組)表達(dá)不定長度和形態(tài)的非線性實(shí)體(表達(dá)式樹)。采用GEP算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘的優(yōu)勢在于：

a)線性編碼，遺傳操作簡單；解碼后對應(yīng)的規(guī)則樹具有靈活的表示能力，降低了誤報(bào)率和漏報(bào)率。

b)收斂速度快。實(shí)驗(yàn)證明至少比GA和GP快兩個(gè)數(shù)量級(jí)[8，11]。

c)利用表達(dá)式樹描述關(guān)聯(lián)規(guī)則，在形式上更加直觀，使規(guī)則易于理解。

初始群體由眾多初始個(gè)體組成。初始個(gè)體為所要解決問題的各種可能的符號(hào)表達(dá)式(算法樹)，它通過隨機(jī)方法產(chǎn)生。個(gè)體是用功能符號(hào)集和終止符號(hào)集對問題的自然描述。個(gè)體的功能符號(hào)集由OR、AND 和NOT三個(gè)邏輯符號(hào)組成；終止符號(hào)集是數(shù)據(jù)各種屬性名及其對應(yīng)模糊值的集合，表示方法為：屬性名=屬性值。

評(píng)價(jià)一條關(guān)聯(lián)規(guī)則優(yōu)劣的標(biāo)準(zhǔn)是以其實(shí)際的支持度和置信度來決定的，多數(shù)文獻(xiàn)[5，6，8]采取如下的計(jì)算方法：

fitness(XY)=s×(supx，y-min_sup)

+c×(confx，y-min_conf)(1)

其中：s、c為支持度和置信度的懲罰系數(shù)。然而在實(shí)際應(yīng)用中發(fā)現(xiàn)，按照如上函數(shù)評(píng)價(jià)染色體易產(chǎn)生偽規(guī)則，即存在

supx，y-min_sup＜0

(confx，y-min_conf)≥(supx，y-min_sup)(2)

或

conf(XY)-min_conf＜0

(supx，y-min_sup)≥(confx，y-min_conf)(3)

的情況，依然有fitness(XY)≥0，而這樣的個(gè)體顯然不符合強(qiáng)關(guān)聯(lián)規(guī)則的定義。為此對評(píng)價(jià)函數(shù)進(jìn)行了修改，首先定義一個(gè)“或乘”運(yùn)算。

定義1 假設(shè)兩個(gè)實(shí)數(shù)x，y∈(-1，1)，用科學(xué)計(jì)數(shù)法表示為x=a×10m，y=b×10n。其中：a，b∈(-1，1)；m，n∈(-∞，0)，則有

xy=a+b＞0ifa＞0，b＞00else(4)

由此定義新的適應(yīng)度函數(shù)為

fitness*(XY)=100×[s×(supx，y-min_sup)][c×(confx，y-min_conf)](5)

1.3 小生境技術(shù)

小生境技術(shù)的具體思想就是把整個(gè)種群分解成若干小生境，在初始條件下它們具有相同的群體規(guī)模。然而隨著進(jìn)化的深入，規(guī)模的大小隨著平均適應(yīng)度自適應(yīng)地發(fā)生動(dòng)態(tài)調(diào)整。當(dāng)然每個(gè)小生境通過設(shè)置其最大規(guī)模max和最小規(guī)模min控制子種群上小限；染色體的各種遺傳操作僅限于小生境內(nèi)部發(fā)生。這樣極大地豐富了種群的多樣性，也使搜索的范圍更加寬泛。詳細(xì)的技術(shù)流程可參看文獻(xiàn)[9，10]。

2 基于小生境的GEP算法

2.1 小生境融合

考慮到每代進(jìn)化后可能出現(xiàn)某些小生境的優(yōu)秀個(gè)體同構(gòu)的現(xiàn)象，為維持種群的多樣性，防止冗余規(guī)則的出現(xiàn)，有必要對該小生境進(jìn)行融合操作。不失一般性，以n個(gè)小生境為例(n≥2)。

算法1 小生境融合

a)n個(gè)將要融合的小生境（假設(shè)為nich1，nich2，…，nichn，融合前兩者規(guī)模分別為S1，…，Sn）個(gè)體全部歸入nich1中；

b)對nichi（1≤i＜n）進(jìn)行相似度檢查(執(zhí)行同構(gòu)互斥操作)剔除同構(gòu)染色體以進(jìn)行融合，得到修改后的nichi規(guī)模s′i；

c)如果s′i大于max，則用輪盤賭法選出多余的個(gè)體，調(diào)整s′i，執(zhí)行小生境演化算法；

d)如果s′i小于min，則引入新個(gè)體直到滿足最小規(guī)模，調(diào)整s′i；

e)隨機(jī)構(gòu)造子小生境nichi+1，使規(guī)模數(shù)滿足s′i+1=s1+s2+…+sn-s′1-…-s′i；如果(1≤i

2.2 小生境演化

記當(dāng)前父代P(t)演化得到的子代為S，則P(t+1)=P(t)∪S，只要∪P(t+1)保持在R的均勻分布，則從統(tǒng)計(jì)的角度上看，∪P(t+1)的非劣集合將極大地逼近非劣集合OP(R，)，即將∪(OP(P(t+1)，))作為OP(R，)的極限逼近。

算法2 小生境演化

a)所有小生境內(nèi)部執(zhí)行傳統(tǒng)的交叉與變異等遺傳操作以得到子代S，將后代S并入父代小生境群體得到P(t+1)=P(t)∪S；

b)在集合P(t+1)上執(zhí)行算法1，對得到的所有小生境解進(jìn)行Cartesian product以此獲得非劣集合OP(P(t+1)，)，將它作為本代小生境的輸出結(jié)果；

c)采用精英保留策略，取子代最優(yōu)的5%個(gè)體替換父代等數(shù)的差個(gè)體。

2.3 NGEP算法流程

a)確定個(gè)體的頭部長度、各種操作的概率，隨機(jī)產(chǎn)生初始種群，并將種群中的個(gè)體平均分配到各小生境中；

b)執(zhí)行算法2；

c)檢查各小生境中的優(yōu)秀個(gè)體，如果個(gè)體出現(xiàn)冗余，執(zhí)行算法1；

d)對于產(chǎn)生的相識(shí)個(gè)體，去除其中適應(yīng)度較差的個(gè)體，并加入相應(yīng)數(shù)目的隨機(jī)個(gè)體；

e)判斷是否滿足收斂條件，如果滿足，則停止程序并輸出結(jié)果；否則繼續(xù)執(zhí)行b)。

3 實(shí)驗(yàn)

本文引用一個(gè)衡量生態(tài)環(huán)境壓力的問題用于檢驗(yàn)NGEP算法的有效性。實(shí)驗(yàn)平臺(tái)配置如下：AMD Sempron(TM) 2500+(64位，1.41 GHz)CPU，512 MB內(nèi)存，Windows XP Professional Service Pack2。文獻(xiàn)[6]提出了一種基于遺傳算法(GA)與螞蟻算法(AA)相結(jié)合的規(guī)則挖掘算法GAAA。由于綜合遺傳和螞蟻算法共有的全局搜索能力，顯示出了優(yōu)于單個(gè)遺傳算法或螞蟻算法的求解性能。本文特將NGEP與GAAA進(jìn)行比較。兩者定義相同的適應(yīng)度函數(shù)，NGEP的參數(shù)設(shè)置參照表1，GAAA則引自文獻(xiàn)[6]，所有實(shí)驗(yàn)均獨(dú)立進(jìn)行100次。此外引入在線性能、離線性能評(píng)價(jià)算法的有效性，并給出了一個(gè)評(píng)價(jià)規(guī)則集多樣性的定量分析函數(shù)。

定義2 群體(規(guī)則集)多樣性性能指標(biāo)為

DIVpop=(∑Nm=1∑Nn=1dm，n)/N2(6)

其中：N為群體規(guī)模；dm，n表示個(gè)體m與個(gè)體n之間的海明距離。

人工模擬數(shù)據(jù)庫（ASD）。數(shù)據(jù)庫D由200個(gè)數(shù)據(jù)事務(wù)組成，而項(xiàng)目屬性集合An含有八個(gè)二值屬性{a1，a2，…，a7，a8}。其中{a7，a8}作為干擾屬性存在。數(shù)據(jù)庫按照以下三條規(guī)則形成：

(a1∧a2)∨(a3)→a4

(a1∨a2)∧a3→a5

(a1)∧(a2∨a3)→a6

取min_sup=0.1，min_conf=0.8，實(shí)驗(yàn)結(jié)果如表2及圖1、2所示。

由上面的實(shí)驗(yàn)結(jié)果可知，與GAAA相比，NGEP不但增加了發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則數(shù)目，還極大地提高了精度。不過相比于GAAA，NGEP迭代的次數(shù)仍然較多。由圖2可見，GAAA在算法的最后階段也能找到較好的解。不過，NGEP的平均預(yù)測精度（72.4）要遠(yuǎn)高于GAAA（53.6）。

4 結(jié)束語

眾所周知，關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘很難找到單一的優(yōu)化解。而本文提出的基于GEP和小生境技術(shù)的算法能搜索較大的解空間。NGEP算法使用小生境演化并根據(jù)最佳個(gè)體的相似性融合小生境，嵌套在小生境核中的笛卡爾積能產(chǎn)生較好的結(jié)果。實(shí)驗(yàn)表明，NGEP算法能較快地收斂并能獲得較好的結(jié)果。

不過，本文算法仍需要在以下兩方面進(jìn)行改進(jìn)：a)在關(guān)聯(lián)規(guī)則挖掘中，適應(yīng)度函數(shù)只考慮了支持度和置信度兩個(gè)因素，并沒有考慮理解度以及興趣度的影響[5，7]。b)僅僅考慮了一般關(guān)聯(lián)規(guī)則的挖掘情況，而沒有考慮模糊關(guān)聯(lián)規(guī)則的挖掘。

參考文獻(xiàn)：

［1］AGRAWAL R， IMIELINSKI T， SWANI A. Mining association rules between sets of items in large databases[C]//Proc of ACM SIGMOD Conference on Management of Data.New York: ACM Press， 1993:207216.

[2]AGRAWAL R， SRIKANT R. Fast algorithms for mining association for mining association rules [C]//Proc of the 20th International Conference on Very Large Database. San Francisco: Morgan Kaufman Publisher， 1994:487499.

[3]CRISTIAN A，MITICA C. Grid implementation of the Apriori algorithm[J]. Advances in Engineering Software，2007，38(5):295300.

[4]FREITAS A A. A survey of evolutionary algorithms for data mining and knowledge discovery[M]//GHOSH A，TSUTSUI S. Advances in Evolutionary Computing.London: SpringerVerlag， 2003:819845.

[5]ROMAO W， FREITAS A A， GIMENES I M S. Discovering interesting knowledge from a science and technology database with a genetic algorithm[J]. Applied Soft Computing，2004，4(2):121137.

[6]沈國強(qiáng)，覃征. 一種新的多維關(guān)聯(lián)規(guī)則挖掘算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27(2):291294.

[7]NODA E，F(xiàn)REITAS A A，LOPES H S，et al. Discoveringinteresting prediction rules with a genetic algorithm[C]//Proc of Congress on Evolutionary Computation. Washington DC: IEEE Computer Society， 1999:13221329.

[8]FREITAS A A. Data mining and knowledge discovery with evolutionary algorithms[M].London:SpringerVerlag，2002.

[9] ZHANG Jun， HUANG Deshuang， LOK T M， et al. A novel adaptive sequential niche technique for multimodal function optimization[J]. Neurocomputing，2006，69(1618):23962401.

[10]WEI Wei， WANG Qi， WANG Hua， et al. The feature extraction of nonparametric curves based on niche genetic algorithms and multipopulation competition[J]. Pattern Recognition Letters， 2005，26(10):14831497.

[11]MUTATION F C. Transposition and recombination:an analysis of the evolutionary dynamics[C]//Proc of the 6th Joint Conference on Information Sciences，the 4th International Workshop on Frontiers in Evolutionary Algorithms. North Carolina: [s.n.]， 2002:614617.

[12]FERREIRA C.Genetic representation and genetic neutrality in gene expression programming[J]. Advances in Complex Systems， 2002，5(4):389408.