鄭玉柱 李 建 李 珂

(西南石油大學(xué)計(jì)算機(jī)科學(xué)學(xué)院， 成都 610500)

?

基于改進(jìn)遺傳算法的關(guān)聯(lián)挖掘方法研究

鄭玉柱 李 建 李 珂

(西南石油大學(xué)計(jì)算機(jī)科學(xué)學(xué)院， 成都 610500)

數(shù)值型關(guān)聯(lián)規(guī)則挖掘是最優(yōu)化問(wèn)題而不是簡(jiǎn)單的離散問(wèn)題，在大型數(shù)據(jù)庫(kù)中挖掘數(shù)值型屬性的關(guān)聯(lián)規(guī)則具有一定的難度。為解決該問(wèn)題，提出一種基于改進(jìn)遺傳算法的數(shù)據(jù)挖掘方法。針對(duì)數(shù)值型屬性和布爾型屬性的混合數(shù)據(jù)，設(shè)計(jì)一種分類并分界的編碼方法；適應(yīng)度函數(shù)采取范圍收縮的策略，使屬性邊界向更精確的方向逼近；在此基礎(chǔ)上設(shè)計(jì)出相應(yīng)的交叉和變異算法，避免遺傳算法的局部收斂和早熟問(wèn)題；最后通過(guò)實(shí)例檢驗(yàn)該算法的可行性。

數(shù)據(jù)挖掘； 關(guān)聯(lián)規(guī)則； 數(shù)值型屬性； 遺傳算法； 適應(yīng)度函數(shù)

數(shù)據(jù)挖掘(data mining, 簡(jiǎn)稱DM)是一個(gè)新興的人工智能與機(jī)器學(xué)習(xí)技術(shù)的研究領(lǐng)域，旨在通過(guò)發(fā)現(xiàn)隱藏在大量數(shù)據(jù)中的有用知識(shí)模式和有效信息，幫助人們進(jìn)一步認(rèn)識(shí)數(shù)據(jù)[1]，數(shù)據(jù)挖掘在決策系統(tǒng)、數(shù)據(jù)分析等方面有著廣闊的應(yīng)用前景。數(shù)據(jù)挖掘的一個(gè)研究方向是在數(shù)據(jù)庫(kù)大量的數(shù)據(jù)中發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則，即關(guān)聯(lián)挖掘，最早由Agrawal等人提出，現(xiàn)在是數(shù)據(jù)挖掘領(lǐng)域中非常流行的研究熱點(diǎn)。

遺傳算法(genetic algorithm,簡(jiǎn)稱GA)是一種基于生物進(jìn)化理論的隨機(jī)搜索算法，由于其具有很強(qiáng)的魯棒性、適應(yīng)性和隱式并行性，能夠快速有效地進(jìn)行全局優(yōu)化，在數(shù)據(jù)挖掘技術(shù)中占有很重要的地位，早就被應(yīng)用于人工智能領(lǐng)域的多個(gè)方面，是進(jìn)行數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的重要方法之一[2- 3]。該算法是一種全局優(yōu)化算法，一般應(yīng)用于在一個(gè)問(wèn)題集中查找最優(yōu)解的情況，特別適合解決多目標(biāo)優(yōu)化問(wèn)題。借鑒生物進(jìn)化論，遺傳算法將要解決的問(wèn)題模擬成為一個(gè)生物進(jìn)化的過(guò)程，使用適應(yīng)度值標(biāo)識(shí)個(gè)體的進(jìn)化能力，通過(guò)選擇交叉和變異等操作產(chǎn)生下一代的解，并在進(jìn)化過(guò)程中逐步淘汰適應(yīng)度函數(shù)值較低的解，增加適應(yīng)度函數(shù)值高的解。經(jīng)過(guò)多次遞歸循環(huán)，進(jìn)化一定階段后就很有可能會(huì)進(jìn)化出適應(yīng)度函數(shù)值最高的個(gè)體。在這個(gè)方面，遺傳算法體現(xiàn)了自然界中“物盡天擇、適者生存”的進(jìn)化過(guò)程。

設(shè)I={i1,i2,…,iM}是一組項(xiàng)目集合，又稱項(xiàng)集。令與業(yè)務(wù)相關(guān)的數(shù)據(jù)庫(kù)事務(wù)為集合D，其中包括了事務(wù)項(xiàng)T(T≠?)，且T?I。設(shè)A是一個(gè)項(xiàng)集，當(dāng)且僅當(dāng)A?T時(shí)，事務(wù)T包含A。關(guān)聯(lián)規(guī)則便是形如A?B的事務(wù)關(guān)系，其中A?I，B?I，A≠?，B≠?且A∪B=?[5]。一般地，形如A?B的關(guān)聯(lián)規(guī)則中左邊的部分A被稱為先導(dǎo)(Antecedent)，右邊的部分B被稱為后繼(Consequence)[6]。在數(shù)據(jù)D中，規(guī)則A?B包含以下度量：

支持度(Support)是在數(shù)據(jù)D中包含A∪B集合的概率，表示為

Support(A?B)=P{A∪B}

(1)

置信度(Confidence)是在數(shù)據(jù)集D中包含A的同時(shí)又包含B的條件概率，表示為

Confidence(A?B)=P{B|A}

(2)

即

(3)

關(guān)聯(lián)規(guī)則有2個(gè)評(píng)價(jià)指標(biāo)：最小支持度(Suppmin)，最小置信度(Confmin)。如果某條規(guī)則滿足：(1)支持度大于最小支持度閾值，(2)置信度大于最小置信度閾值，則這條關(guān)聯(lián)規(guī)則就被認(rèn)為是強(qiáng)關(guān)聯(lián)規(guī)則，而關(guān)聯(lián)挖掘中的主要工作，便是挖掘出數(shù)據(jù)集D中的強(qiáng)關(guān)聯(lián)規(guī)則[7]。

本次研究提出一種基于遺傳算法的關(guān)聯(lián)挖掘算法，針對(duì)數(shù)據(jù)庫(kù)中布爾型和數(shù)值型數(shù)據(jù)進(jìn)行改進(jìn)，為避免群體早熟和局部收斂做了適當(dāng)優(yōu)化。

1 基于改進(jìn)遺傳算法的關(guān)聯(lián)挖掘方法設(shè)計(jì)

基于已有研究成果，本次研究提出一種基于改進(jìn)遺傳算法的關(guān)聯(lián)挖掘方法(簡(jiǎn)稱GAMAR)。與一般關(guān)聯(lián)挖掘算法不同，關(guān)聯(lián)規(guī)則直接由算法得出，而不用先尋找所有頻繁項(xiàng)集。算法的流程圖如圖1所示。

圖1 GAMAR算法流程圖

在準(zhǔn)備階段的時(shí)候?yàn)樵撍惴ㄔO(shè)置初始運(yùn)行參數(shù)，參數(shù)的設(shè)定對(duì)本算法的運(yùn)行性能有非常大的影響。初始參數(shù)包括傳統(tǒng)遺傳算法中的種群大小、交叉概率、變異概率、終止代數(shù)，以及關(guān)聯(lián)挖掘技術(shù)中的最小支持度Suppmin和最小置信度Confmin。

(1)種群大小(PopSize)。群體大小表示的是群體中所含個(gè)體的數(shù)量，也叫種群規(guī)模。當(dāng)種群大小的取值較小時(shí)，可以提高遺傳算法的運(yùn)算速度，但同時(shí)降低了群體的多樣性，造成遺傳算法的早熟現(xiàn)象；當(dāng)種群大小的取值較大時(shí)，遺傳算法的運(yùn)算效率便會(huì)降低。所以在選取種群大小的時(shí)候，需要綜合考慮這2個(gè)方面。

(2)交叉概率(CrossoverRate)。遺傳算法中新個(gè)體的產(chǎn)生主要靠交叉操作，若取值較小，產(chǎn)生新個(gè)體的速度會(huì)變慢，所以一般情況下交叉概率選取的值都比較大。但也應(yīng)注意，若取值過(guò)大，就會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算產(chǎn)生不良影響。

(3)變異概率(MutateRate)。變異概率決定了物種的多樣性。若取值過(guò)大，雖然能產(chǎn)生較多的新個(gè)體，但很有可能會(huì)破壞掉很多較好的模式，使遺傳算法的性能近似于完全隨機(jī)搜索算法的性能；若取值較小，則變異操作產(chǎn)生新個(gè)體與抑制早熟現(xiàn)象的能力就較差。

(4)終止代數(shù)(Iterations)。本算法的終止條件是種群進(jìn)化至指定的終止代數(shù)，并將當(dāng)前群體中的最佳個(gè)體作為最優(yōu)解輸出。當(dāng)終止代數(shù)取值較小時(shí)，算法運(yùn)算結(jié)束時(shí)種群中還未進(jìn)化出最優(yōu)個(gè)體；當(dāng)終止代數(shù)取值較大時(shí)，運(yùn)算到一定階段種群進(jìn)化已經(jīng)趨于停滯，此時(shí)繼續(xù)運(yùn)算已沒(méi)有必要。

1.2 編碼方法

在確定了目標(biāo)數(shù)據(jù)庫(kù)之后，首先對(duì)數(shù)據(jù)庫(kù)中采集到的數(shù)據(jù)進(jìn)行編碼，使數(shù)據(jù)離散化且便于進(jìn)行數(shù)據(jù)挖掘，可根據(jù)具體問(wèn)題選擇采用二進(jìn)制或者十進(jìn)制編碼方法，編碼方法確定后便確定了個(gè)體的編碼長(zhǎng)度。鑒于需要挖掘的數(shù)據(jù)既有數(shù)值型數(shù)值，又有布爾型數(shù)值，所以挖掘目標(biāo)是包含2種數(shù)值屬性的混合型關(guān)聯(lián)規(guī)則。鑒于此，本算法采用十進(jìn)制編碼方法。

在種群中的每一條染色體均表示一條確定的規(guī)則，規(guī)則中包含了確定的條件屬性(先導(dǎo)，antecedent)和決策屬性(后繼，consequent)。在染色體中的每一個(gè)基因段表示一個(gè)確定屬性，在每一個(gè)基因段中包含3個(gè)與屬性相關(guān)聯(lián)的信息：第一部分指示了該屬性的類型，可以有3個(gè)可能的取值，分別為0,1,2，0表示該屬性為前驅(qū)，1表示該屬性為結(jié)果，2表示該屬性不參與算法運(yùn)算過(guò)程，不用考慮[9]；第二部分指示基因段的下限；第三部分指示基因段的上限。因此第二和第三部分可以看成是一個(gè)整體，在表示數(shù)值型屬性時(shí)，2個(gè)部分大小不同的值表示該屬性取值的上下限；在表示布爾型數(shù)值屬性時(shí)，2個(gè)部分取相同的值，以指示該屬性的真實(shí)取值。1條染色體的編碼規(guī)則如圖2所示。

圖2 染色體編碼規(guī)則圖

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

適應(yīng)度函數(shù)決定了種群中每個(gè)個(gè)體的適應(yīng)度值的大小，也指引著種群進(jìn)化的方向，由適應(yīng)度函數(shù)確定的每一條染色體的適應(yīng)度值，區(qū)分了普通染色體與最優(yōu)染色體之間的差距。在關(guān)聯(lián)挖掘中，設(shè)計(jì)出的適應(yīng)度函數(shù)需要能表現(xiàn)最小支持度和最小置信度的限制作用，所以本次研究希望挖掘出支持度和置信度均大于各自閥值的強(qiáng)關(guān)聯(lián)規(guī)則，即：

Support(A?B)≥Suppmin

(4)

且

Confidence(A?B)≥Confmin

(5)

由式(1)和式(3)，式(5)可轉(zhuǎn)變?yōu)椋?/p>

(6)

進(jìn)而有：

Support(A?B)-Confmin·Support(A)≥0

(7)

所以在規(guī)則的置信度大于最小置信度閥值時(shí)，式(7)的左式可作為種群的適應(yīng)度函數(shù)，這樣設(shè)計(jì)是為了整合規(guī)則的置信度和支持度值，并且也是為滿足適應(yīng)度函數(shù)必須為正數(shù)的要求，即：

FitnessFunction(A?B)=Supp(A?B)-

Confmin·Support(A)

(8)

利用式(8)便可以求出染色體的適應(yīng)度值，但是在評(píng)價(jià)某條規(guī)則時(shí)，還需要滿足式(4)。為了保持適應(yīng)度函數(shù)的獨(dú)立，本次研究對(duì)支持度小于最小支持度閥值的規(guī)則做懲罰，使得不滿足規(guī)則的更容易被淘汰。此外，對(duì)于數(shù)值型屬性，數(shù)值的取值范圍越狹小，規(guī)則越精確。因此需要提高這類規(guī)則的適應(yīng)度值，使得其更容易在進(jìn)化過(guò)程中生存下來(lái)。

由此，設(shè)計(jì)出的適應(yīng)度函數(shù)算法FitnessFunction的偽代碼如算法1所示。

1.4 遺傳算子

1.4.1 交叉算子

在傳統(tǒng)的遺傳算法中，交叉算子將2個(gè)同源染色體通過(guò)交叉算法，例如單點(diǎn)交叉，重組形成新的染色體。在單點(diǎn)交叉中，交叉算子隨機(jī)選擇2個(gè)待交叉染色體，通過(guò)隨機(jī)確定的交叉點(diǎn)，互換2個(gè)個(gè)體的一部分基因。在本算法中，交叉算子隨機(jī)確定2個(gè)染色體，在每個(gè)基因處，根據(jù)交叉概率隨機(jī)地交換父代的2個(gè)基因的上下限，生成2個(gè)新的基因段，新生成基因段中的上下限有4種可能的取值。算法的交叉過(guò)程如圖3所示。

圖3 交叉操作過(guò)程圖

1.4.2 變異算子

為防止種群出現(xiàn)局部收斂或者早熟的現(xiàn)象，同時(shí)為了保證種群一定程度的多樣性，需要變異算子對(duì)某個(gè)染色體上某個(gè)基因位的基因進(jìn)行變異操作。對(duì)于二進(jìn)制編碼來(lái)說(shuō)，變異操作只需將隨機(jī)的基因位上的二進(jìn)制基因值取反即可。針對(duì)本算法所采用的混合型編碼方法，首先在種群中隨機(jī)確定一個(gè)染色體，在每一個(gè)基因段上分別根據(jù)變異概率隨機(jī)進(jìn)行變異操作，基因段的上下限單邊地增大或者減小隨機(jī)寬度，但不超過(guò)基因段取值范圍的領(lǐng)域邊界值(Uppermax,Lowermin)，最后生成一個(gè)新的基因段。算法的變異過(guò)程如圖4所示。

圖4 變異操作過(guò)程圖

1.4.3 選擇算子

遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選擇哪些個(gè)體遺傳到下一代群體中。為了保障群體能夠收斂到最優(yōu)個(gè)體，本算法采用精英選擇方法，該方法的思路是將每一代最佳的一部分個(gè)體，直接復(fù)制到下一代，替代下一代群體中最差的相應(yīng)數(shù)量的個(gè)體。從遺傳算法的選擇策略考慮，精英選擇是群體收斂到最優(yōu)解的一種基本保障[10]。

1.5 初始種群設(shè)置

初始種群作為原始的搜索空間，是整個(gè)算法的開(kāi)端。為了使得算法的搜索目標(biāo)在一個(gè)較大的領(lǐng)域內(nèi)，按照如下方式生成初始種群：染色體的每個(gè)基因段各自覆蓋該屬性的取值范圍，即上限取最大邊界值(Ui=Uppermax)，下限取最小邊界值(Li=Lowermin)。這樣設(shè)置會(huì)使得初始種群擁有足夠的多樣性，避免進(jìn)化早熟現(xiàn)象。隨著進(jìn)化代數(shù)的增大，染色體中基因段的覆蓋范圍會(huì)趨于狹小，直到規(guī)則滿足最小支持度的要求，最后得到更精確的關(guān)聯(lián)規(guī)則。

1.6 規(guī)則模板的設(shè)置

利用遺傳算法進(jìn)行關(guān)聯(lián)挖掘時(shí)，期望得到形如A?B的關(guān)聯(lián)規(guī)則，而算法自身并不知道哪部分屬性屬于規(guī)則的先導(dǎo)，哪部分屬性屬于后繼。此外，在確定了先導(dǎo)和后繼的范圍后，才可以由式(1)和式(2)求取規(guī)則的支持度和置信度。因此，在挖掘階段之前，需要人為設(shè)置一個(gè)規(guī)則模板(Ruletemplate)，模板指定規(guī)則的格式，如式(9)所示：

Ruletemplate={屬性1，屬性2}?{屬性3，屬性4}

(9)

模板確定后將作為算法的一個(gè)輸入條件，伴隨整個(gè)算法的運(yùn)行。

1.7 數(shù)據(jù)挖掘階段

本次設(shè)計(jì)的GAMAR算法可以根據(jù)用戶指定的規(guī)則模板，隨機(jī)搜索目標(biāo)數(shù)據(jù)集，挖掘出滿足最小置信度和最小支持度的關(guān)聯(lián)規(guī)則。

在運(yùn)行之前，需要在目標(biāo)數(shù)據(jù)庫(kù)中查詢出必要的數(shù)據(jù)，并對(duì)查詢結(jié)果做相關(guān)的數(shù)據(jù)清洗處理，使待挖掘數(shù)據(jù)集中的各屬性值為布爾型或者數(shù)值型數(shù)據(jù)，以便于進(jìn)行關(guān)聯(lián)規(guī)則的挖掘。

GAMAR算法的偽代碼如算法2所示。

2 數(shù)據(jù)挖掘?qū)嵗?/h2>

本次研究利用中國(guó)石油天然氣集團(tuán)公司某鉆探隊(duì)現(xiàn)場(chǎng)施工數(shù)據(jù)進(jìn)行關(guān)聯(lián)挖掘?qū)嶒?yàn)，從數(shù)據(jù)庫(kù)中獲得的數(shù)據(jù)經(jīng)過(guò)數(shù)據(jù)清洗及預(yù)處理后，得到表1所示的數(shù)據(jù)表結(jié)構(gòu)。

表1 事故隱患元數(shù)據(jù)表

表1記錄了各項(xiàng)隱患指標(biāo)(A1～A32)在一段時(shí)間內(nèi)每天發(fā)生的次數(shù)(0～n)，均為數(shù)值型數(shù)據(jù)。在此基礎(chǔ)上進(jìn)行關(guān)聯(lián)挖掘，希望找到各項(xiàng)指標(biāo)之間發(fā)生次數(shù)的關(guān)系。

為了使算法能更有效地得到強(qiáng)關(guān)聯(lián)規(guī)則，經(jīng)過(guò)多次實(shí)驗(yàn)對(duì)比參數(shù)選擇，算法的各項(xiàng)輸入?yún)?shù)選擇如下：PopSize=500,CrossoverRate=0.5,MutateRate=0.3,Iterations=100，Suppmin=0.1,Confmin=0.4。為找到對(duì)施工影響最大的指標(biāo)A32與其他指標(biāo)的關(guān)系，設(shè)置規(guī)則模板如下：

{A1,A2,…,A31}?{A32}

對(duì)于此元數(shù)據(jù)，挖掘出的結(jié)果可能會(huì)出現(xiàn)某個(gè)指標(biāo)值的上下標(biāo)均為0的情況，表示該項(xiàng)指標(biāo)不影響結(jié)果發(fā)生，在最終關(guān)聯(lián)規(guī)則中將這種模式的指標(biāo)值忽略不考慮。

經(jīng)過(guò)100次種群進(jìn)化，最終得到如表2所示的強(qiáng)關(guān)聯(lián)規(guī)則(取最優(yōu)2條)。

表2 算法挖掘結(jié)果

3 結(jié) 語(yǔ)

基于遺傳算法的關(guān)聯(lián)挖掘算法首先改進(jìn)了原有的數(shù)據(jù)編碼方式，能夠更準(zhǔn)確地表示元數(shù)據(jù)中數(shù)值類型的結(jié)構(gòu)；其次提出了適應(yīng)新編碼形式的交叉和變異算法，在提高算法挖掘關(guān)聯(lián)規(guī)則能力的同時(shí)，能夠更好地避免遺傳算法的局部收斂和早熟現(xiàn)象；最后提出了使用模板來(lái)指導(dǎo)數(shù)據(jù)挖掘的搜索方向，使得用戶可以指定挖掘規(guī)則的模式。該方法可以有效地解決大數(shù)據(jù)量下挖掘數(shù)值型屬性關(guān)聯(lián)規(guī)則的問(wèn)題。

[1] Zhang S C, Wu X D. Fundamentals of Association Rules in Data Mining and Knowledge Discovery [J]. Wiley Interdiscip Rev-Data Mining Knowl Discov, 2011, 1(2): 97-116.

[2] Nedic V, Cvetanovic S, Despotovic D, et al. Data Mining with Various Optimization methods [J]. Expert Syst Appl, 2014, 41(8): 3993-3999.

[3] Tan J S, He W, Qing Y. Application of Genetic Algorithm in Data Mining [C].Proceedings of the Education Technology and Computer Science, 2009 ETCS '09 First International Workshop on, 2009: 353-356.

[4] Goren H G, Tunali S, Jans R. A Review of Applications of Genetic Algorithms in Lot Sizing [J]. J Intell Manuf, 2010, 21(4): 575-590.

[5] Han J, Kamber M, Pei J. Data Mining: Concepts and Techniques, Third Edition [M].[s.l.]: Morgan Kaufmann, 2011.

[6] Shah R A, Asghar S. Privacy Preserving in Association Rules Using a Genetic Algorithm [J]. Turk J Electr Eng Comput Sci, 2014, 22(2): 434-450.

[7] Alhajj R, Kaya M. Multi-objective Genetic Algorithms Based Automated Clustering for Fuzzy Association Rules Mining [J]. Journal of Intelligent Information Systems, 2008, 31(3): 243-264.

[8] Kotsiantis S, Kanellopoulos D. Association Rules Mining: A Recent Overview [J]. GESTS International Transactions on Computer Science and Engineering, 2006, 32(1): 71-82.

[9] Alatas B, Akin E, Karci A. Modenar: Multi-objective Differential Evolution Algorithm for Mining Numeric Association Rules [J]. Appl Soft Comput, 2008, 8(1): 646-656.

[10] Gosselin L, Tye-Gingras M, Mathieu-Potvin F. Review of Utilization of Genetic Algorithms in Heat Transfer Problems [J]. Int J Heat Mass Transf, 2009, 52(910): 2169-2188.

Association Mining Method Based on Improved Genetic Algorithm

ZHENGYuzhuLIJianLIKe

(School of Computer Science, Southwest Petroleum University, Chengdu 610500, China)

In this paper a genetic-based association rule mining algorithm is proposed to deal with the problem of mining quantitative association rule in large database, because it is an optimization problem rather than a simple discretization one. First, we designed an encoding method for classification and division based on the blended data from boolean and quantitative attributes. Then the attributes′ amplitudes are shortened by the search strategy of fitness function when the boundary is droven more accurate. It is designed to avoid the local convergence and premature problems with appropriate crossover and mutate methods. Finally, the efficiency of the algorithm is validated by the test upon real database.

data mining; association rules; quantitative (numeric) attributes; genetic algorithm; fitness function

2015-01-30

國(guó)家科技重大專項(xiàng)“鉆井工程設(shè)計(jì)和工藝軟件”(2011ZX05021-006)

鄭玉柱(1989 — )，男，西南石油大學(xué)2012級(jí)在讀碩士研究生，研究方向?yàn)閿?shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘。

TP311

A

1673-1980(2015)05-0072-05