基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘

李廣霞

（石家莊經(jīng)濟(jì)學(xué)院 信息工程學(xué)院，河北 石家莊 050031）

目前，關(guān)聯(lián)規(guī)則挖掘算法一般是指Apriori算法或其改進(jìn)算法［1］.其挖掘過(guò)程主要包含兩個(gè)階段：第一階段必須先從數(shù)據(jù)集合中找出所有支持度大于用戶(hù)最小支持度的項(xiàng)集的頻繁項(xiàng)目集（Frequent Itemsets）；第二階段由這些頻繁項(xiàng)目集構(gòu)造可信度大于用戶(hù)最小可信度的關(guān)聯(lián)規(guī)則 （Association Rules）.它實(shí)際上是一個(gè)全局搜索過(guò)程.遺傳算法是一種全局優(yōu)化算法，它可以有效地避免搜索過(guò)程的局部最優(yōu)解問(wèn)題，因此，將遺傳算法用于關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)和提取有利于找到有價(jià)值的規(guī)則［2］.

1 遺傳算法

遺傳算法（Genetic Algorithms，簡(jiǎn)稱(chēng)GA）是模擬生物進(jìn)化過(guò)程的計(jì)算模型，它是一種以自然選擇和遺傳理論為基礎(chǔ)，將生物進(jìn)化過(guò)程中適者生存規(guī)則與群內(nèi)染色體的隨機(jī)信息交換機(jī)制相結(jié)合的搜索算法［3］.

遺傳算法不能直接處理問(wèn)題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，這一轉(zhuǎn)換操作叫做編碼.編碼有2種方式，即二進(jìn)制編碼和十進(jìn)制編碼.遺傳算法的適應(yīng)度函數(shù)也叫評(píng)價(jià)函數(shù)，是用來(lái)判斷群體中個(gè)體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問(wèn)題的目標(biāo)函數(shù)來(lái)進(jìn)行評(píng)估的［4］，在使用時(shí)，需要隨機(jī)產(chǎn)生一組規(guī)則，對(duì)每一個(gè)規(guī)則應(yīng)用數(shù)據(jù)庫(kù)中給定的例子進(jìn)行判斷，計(jì)算其適應(yīng)度.先應(yīng)用交叉運(yùn)算和變異運(yùn)算對(duì)該組規(guī)則進(jìn)行優(yōu)化，再利用選擇運(yùn)算產(chǎn)生下一代規(guī)則，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過(guò)程.從優(yōu)化搜索的角度而言，遺傳操作可使問(wèn)題的解一代又一代地優(yōu)化，并逼近最優(yōu)解［5］.

1.1 編碼策略

編碼是遺傳算法中最基本的問(wèn)題.對(duì)于規(guī)則項(xiàng)的編碼方式分為二元編碼和實(shí)值編碼.

對(duì)于布爾型的關(guān)聯(lián)規(guī)則挖掘可采取二元編碼，但對(duì)不同類(lèi)型的屬性，編碼方式并不相同.對(duì)于類(lèi)別屬性，如“婚姻狀態(tài)”有四種取值：?jiǎn)紊?、離婚、已婚、喪偶，其編碼長(zhǎng)度為4，那么比特串0100代表的是離婚，0110代表離婚或者已婚；對(duì)于連續(xù)屬性，一般先采用連續(xù)屬性離散化，然后采用類(lèi)別屬性的編碼方式.

對(duì)于非布爾型的關(guān)聯(lián)規(guī)則挖掘可采取實(shí)值編碼的方法.編碼長(zhǎng)度（數(shù)組中元素的個(gè)數(shù)）為n，A［1］存儲(chǔ)項(xiàng)（屬性）I1的值，A［2］存儲(chǔ)項(xiàng)（屬性）I2的值，以此類(lèi)推，A［n］存儲(chǔ)項(xiàng)（屬性）In的值.這種編碼方式簡(jiǎn)單且易于實(shí)現(xiàn)，便于遺傳算子操作.在該方法中，需要對(duì)每個(gè)屬性的所有取值進(jìn)行分析：（1）若某個(gè)屬性的取值是有限的、離散的，則將其從小到大定義為“值1”、“值2”……；否則，將那些連續(xù)的或者無(wú)限個(gè)數(shù)的取值劃分為有限個(gè)取值區(qū)間，定義為“值1”、“值2”…….（2）若A［i］取值為k，則令A(yù)［i］＝k，若某個(gè)項(xiàng)集中沒(méi)有包含屬性Ii，則A［i］＝0.

1.2 種群初始化

遺傳算法中初始群體的個(gè)體是隨機(jī)產(chǎn)生的.初始群體的設(shè)定可采取如下策略：（1）根據(jù)問(wèn)題固有的知識(shí)，設(shè)法把握最優(yōu)解所占空間在整個(gè)問(wèn)題空間中的分布范圍，然后在此分布范圍內(nèi)設(shè)定初始群體.（2）先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑出最好的個(gè)體加到初始群體中.這種過(guò)程不斷迭代，直到初始群體中個(gè)體數(shù)達(dá)到預(yù)先確定的規(guī)模.

對(duì)于二元編碼的關(guān)聯(lián)規(guī)則挖掘，隨機(jī)生成N個(gè)n位由“0”和“1”組成的串作為初始種群；對(duì)于實(shí)值編碼的關(guān)聯(lián)規(guī)則挖掘，隨機(jī)生成N個(gè)由“A［1］，A［2］，… ，A［n］”在定義范圍內(nèi)的值組成的串作為初始種群.

1.3 適應(yīng)度函數(shù)

遺傳算法在搜索進(jìn)化過(guò)程中一般不需要其他的外部信息，僅用評(píng)估函數(shù)來(lái)評(píng)估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù).在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計(jì)要結(jié)合求解問(wèn)題本身的要求而定.關(guān)聯(lián)規(guī)則挖掘中頻繁項(xiàng)集的衡量標(biāo)準(zhǔn)為支持度，它要求項(xiàng)集的支持度大于用戶(hù)所給的最小支持度閾值（Min－Supp）.這是判斷其是否為頻繁項(xiàng)集的唯一標(biāo)準(zhǔn).

因此，設(shè)計(jì)的適應(yīng)度函數(shù)最好能分辨出支持度和MinSupp兩者的大小關(guān)系.為此，定義群體中的個(gè)體X的適應(yīng)度函數(shù)為：

其中，MinSupp′表示個(gè)體X的支持度，當(dāng)Min－Supp′大于MinSupp時(shí)，函數(shù)值大于1，此時(shí)個(gè)體X將在下一代中得以保存；否則，個(gè)體X將被淘汰.

1.4 遺傳操作

遺傳操作包括三個(gè)基本遺傳算子（genetic operator）：選擇（selection）、交叉（crossover）和變異（mutation）.

（1）選擇算子

從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫選擇.選擇的目的是把優(yōu)化的個(gè)體（或解）直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代.選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的.本文選擇的操作是將適應(yīng)度值大于1的規(guī)則留下來(lái)，并復(fù)制到下一代群體中.

（2）交叉算子

遺傳算法中起核心作用的是遺傳操作的交叉算子.所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作.交叉位置的選取是隨機(jī)的.本文采用最簡(jiǎn)單的一點(diǎn)交叉.從交叉概率Pc在當(dāng)前種群生成的交配池中隨機(jī)選取兩個(gè)個(gè)體X1和X2，隨機(jī)確定交叉點(diǎn)，并將交叉點(diǎn)前后的部分進(jìn)行交換，生成兩個(gè)新的個(gè)體X1′和X2′，進(jìn)入當(dāng)前種群.

（3）變異算子

變異算子的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng).由于遺傳算法有局部搜索能力，引入變異可以提高群體中抗體的多樣性并擴(kuò)大搜索范圍，從而搜索更優(yōu)秀的抗體.根據(jù)關(guān)聯(lián)規(guī)則挖掘的特點(diǎn)，變異概率Pm不是固定不變的.當(dāng)種群中適應(yīng)度小于1的個(gè)體數(shù)目M較大時(shí)，Pm取值較大；反之較小.Pm取值如下：

式中，α的值根據(jù)具體情況選取.

另外，參與變異操作的個(gè)體是在適應(yīng)度值小于1的所有個(gè)體中隨機(jī)選擇的.

2 基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘

2.1 算法

在關(guān)聯(lián)規(guī)則挖掘的兩個(gè)階段中，將遺傳算法的思想應(yīng)用于頻繁項(xiàng)集的生成過(guò)程中，從而實(shí)現(xiàn)對(duì)頻繁項(xiàng)集的生成算法的改進(jìn).算法描述如下：

算法，基于遺傳算法的關(guān)聯(lián)規(guī)則算法（Genetic Algorithm for Association Rule）.

輸入，事務(wù)數(shù)據(jù)庫(kù)D，最小支持度MinSupp，種群規(guī)模n，交叉概率Pc，變異概率Pm，迭代次數(shù)T.

輸出，D中頻繁項(xiàng)集.

步驟1，初始化種群P0＝｛A1，A2，…，An｝，進(jìn)行編碼；

步驟2，計(jì)算P0中每個(gè)個(gè)體的適應(yīng)度f(wàn)（Ai）；步驟3，初始化后代種群Pi＋1，Pi＋1＝Ф；

步驟4，選擇，若f（Ai）≥1，則 Pi＋1＝Pi＋1∪｛Ai｝，Pi＝Pi－｛Ai｝；

步驟5，交叉，從當(dāng)前種群中隨機(jī)選擇兩個(gè)個(gè)體A和B，按照給定的交叉概率Pc進(jìn)行交叉，得到兩個(gè)新個(gè)體A′和B′，則Pi＝Pi－｛A 和B｝，Pi＋1＝Pi＋1∪｛A′和B′｝；

步驟6，變異，隨機(jī)從當(dāng)前種群中選取m個(gè)個(gè)體，按照變異概率Pm進(jìn)行編譯操作，編譯后產(chǎn)生的個(gè)體進(jìn)入下一代種群Pi＋1；

步驟7，判斷循環(huán)次數(shù)是否達(dá)到迭代次數(shù)T，如果達(dá)到，進(jìn)入步驟8；如果種群Pi＋1中的個(gè)體數(shù)目Num小于n，則隨機(jī)生成（n－Num）個(gè)個(gè)體進(jìn)入種群Pi＋1，返回步驟2；

步驟8，輸出結(jié)果；

步驟9，進(jìn)行規(guī)則提取.

2.2 試驗(yàn)

為了比較Apriori算法和本文提出的基于遺傳算法的關(guān)聯(lián)規(guī)則算法的性能，設(shè)定數(shù)據(jù)庫(kù)中的事務(wù)數(shù)為10 000，數(shù)據(jù)項(xiàng)集中的數(shù)據(jù)項(xiàng)個(gè)數(shù)為10，需要挖掘的關(guān)聯(lián)規(guī)則最小置信度閾值為0.4，改變挖掘的最小支持度閾值，測(cè)試不同最小支持度閾值下的2種算法的運(yùn)行時(shí)間，如圖1所示.

試驗(yàn)表明，在相同數(shù)據(jù)規(guī)模下，不同支持度下的改進(jìn)算法的執(zhí)行時(shí)間比Apriori算法短.支持度越小，Apriori算法的執(zhí)行時(shí)間越長(zhǎng)，而改進(jìn)的算法所需執(zhí)行時(shí)間的增長(zhǎng)速度低于Arpriori算法.

圖1 不同支持度的運(yùn)行時(shí)間比較圖

3 結(jié)束語(yǔ)

本文分析了遺傳算法在數(shù)據(jù)挖掘中應(yīng)用的可能性，給出了基于遺傳算法的關(guān)聯(lián)規(guī)則算法，并從編碼方法、適應(yīng)度函數(shù)的構(gòu)造、交叉算子和變異算子的設(shè)計(jì)方面進(jìn)行了討論和分析.最后試驗(yàn)表明，改進(jìn)算法的執(zhí)行效率高于Apriori算法.

［1］林倩瑜.關(guān)聯(lián)規(guī)則挖掘算法研究綜述 ［J］.軟件導(dǎo)刊，2012，（6）：31－33.

［2］李陽(yáng)陽(yáng)，焦李成.求解SAT問(wèn)題的量子免疫克隆算法 ［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（2）：176－183.

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

［4］STAKOVIE J.Misconceptions about Real－time Computing：a serious Problem for Next Generation System ［J］.IEEE Computer，1998，21（10）：10－19.

［5］AU W H，CHAN K C C，YAO X.A Novel Evolutionary Da－ta mining Algorithm with Applications to Churn Prediction［J］.IEEE Transactions on Evolutionary Computation，2003，7（6）：532－545.