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

黃毅杰 張藝雪

(1漳州職業(yè)技術(shù)學(xué)院計算機(jī)工程系 福建漳州 363000；

2漳州衛(wèi)生職業(yè)學(xué)院信息技術(shù)部 福建漳州 363000)

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

黃毅杰1張藝雪2

(1漳州職業(yè)技術(shù)學(xué)院計算機(jī)工程系 福建漳州 363000；

2漳州衛(wèi)生職業(yè)學(xué)院信息技術(shù)部 福建漳州 363000)

對在傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法下產(chǎn)生的關(guān)聯(lián)規(guī)則出現(xiàn)的問題進(jìn)行分析，引入興趣度并結(jié)合遺傳算法的特點(diǎn)，提出一種基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘算法，通過遺傳算法的自適應(yīng)尋優(yōu)技術(shù)和興趣度更好地篩選出關(guān)聯(lián)規(guī)則。通過實(shí)驗證明，該算法是有效的。

數(shù)據(jù)挖掘，關(guān)聯(lián)規(guī)則，興趣度，遺傳算法

數(shù)據(jù)挖掘是一種信息分析技術(shù)，數(shù)據(jù)挖掘應(yīng)用算法從大型數(shù)據(jù)庫中提取有用的信息和知識，通過這些算法確定信息項之間的隱性關(guān)系，并且向用戶顯示這些關(guān)聯(lián)[1]。數(shù)據(jù)挖掘?qū)碜匀斯ぶ悄芎湍Ｊ阶R別的一組技術(shù)和系統(tǒng)方法組合在一起，幫助用戶搜索模式。關(guān)聯(lián)規(guī)則挖掘已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域中重要的研究方向[2]。

1 關(guān)聯(lián)規(guī)則概述

關(guān)聯(lián)規(guī)則挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)系和關(guān)聯(lián)以及相關(guān)的分組，關(guān)聯(lián)規(guī)則可以確定數(shù)據(jù)庫中存在的邏輯隱含規(guī)則，確定關(guān)聯(lián)組。1994年， Agrawal等人提出了關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法Apriori，其最常見的例子是購物籃分析[3]。這是對客戶總共購買的產(chǎn)品的分析，它的目標(biāo)是確定產(chǎn)品之間最常見的關(guān)系。如果有記錄一組購買事務(wù)的客戶數(shù)據(jù)庫，并通過購買的特定產(chǎn)品集來描述每個購買事務(wù)，則關(guān)聯(lián)規(guī)則可表示為： X?Y，其中X和Y是產(chǎn)品集，該規(guī)則的直觀含義是包含X中的產(chǎn)品的事務(wù)也傾向于包含Y中的產(chǎn)品。該規(guī)則的評估有用性的度量是支持度(support)和可信度(confidence)。support度量代表同時包含X和Y的事務(wù)的百分比，可以用公式“support(X?Y)=包含X∪Y的事務(wù)數(shù)量/事務(wù)總數(shù)量”表示。confidence度量代表包含X的事務(wù)中也包含Y的事務(wù)的百分比，可以用公式“confidence(X?Y)=包含X∪Y的事務(wù)數(shù)量/包含X的事務(wù)數(shù)量”表示。關(guān)聯(lián)規(guī)則描述如：{買啤酒}?{買炸土豆片}，support=70%，confidence=85%表示85%的購買啤酒的客戶也購買了炸土豆，這種關(guān)聯(lián)只占數(shù)量的的70%。為了找出有用的關(guān)聯(lián)規(guī)則，需要用戶確定兩個閾值，即最小支持度(min_sup)和最小可信度(min_conf)，滿足support(X?Y)> min_sup且confidence(X?Y)> min_conf的規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則。

2 問題的提出

通過一個具體的實(shí)例來說明購買商品與不購買商品的關(guān)系。設(shè)I=(啤酒，炸土豆片)，交易集D，經(jīng)過對D的分析，得到交易集分析，如表1所示。

表1 交易集分析

設(shè)定min_sup =0.2，min_conf =0.8，得到關(guān)聯(lián)規(guī)則： {買炸土豆片} ?{買啤酒}，support =0.2，confidence =0.8即80%的人買了炸土豆片就會買啤酒。但從表1中可以很容易的得到結(jié)論：90%的人肯定會買啤酒，即買炸土豆片這個事件對于買啤酒這個事件的作用并沒有想象中的那么大，反而是規(guī)則：{買啤酒}?{不買炸土豆片}，support =0.7，confidence =0.78，更具有商業(yè)銷售的指導(dǎo)價值。

從上面的例子可以發(fā)現(xiàn)，基于支持度-可信度的關(guān)聯(lián)規(guī)則評估體系存在著問題，其只能挖掘出正屬性項的規(guī)則，不能挖掘出負(fù)屬性項的規(guī)則，而這種知識往往具有更重要的價值[4]。

3 引入興趣度

為了解決上面提出的問題，引入興趣度概念來分析項集A和項集B的關(guān)系程度。興趣度的公式為：

其反映了項集A與項集B的相關(guān)程度[5]。

如果I(A→B)=1，即P(AB)=P(A)P(B)表示項集A出現(xiàn)和項集B出現(xiàn)是相互獨(dú)立的。

如果0

如果I(A→B)>1，表示A出現(xiàn)和B出現(xiàn)是正相關(guān)的，意味著A的出現(xiàn)蘊(yùn)涵B的出現(xiàn)。其中I(A→B)的數(shù)值越大，意味著這條規(guī)則的興趣度越大。

利用興趣度對表1進(jìn)行分析可以得出所有的關(guān)聯(lián)規(guī)則如表2所示。

表2 所有的關(guān)聯(lián)規(guī)則

從表2可以看出屬于正相關(guān)規(guī)則的序號3和序號6的都大于1，可以列入進(jìn)一步考慮的范圍。

4 基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘?qū)崿F(xiàn)過程

4.1編碼方法的選擇

由于二進(jìn)制編碼的的編碼操作和解碼操作比較簡單，本文采用二進(jìn)制編碼。二進(jìn)制編碼是基于確定的二進(jìn)制位串I={0，1}L，若事務(wù)數(shù)據(jù)庫D中的TID001事務(wù)包含I1，13，I6，項集I的項數(shù)為6，則可以用6位的二進(jìn)制位串101001來對染色體進(jìn)行編碼，其中0表示項不存在，1表示項存在事務(wù)中[6]。

4.2適應(yīng)度函數(shù)的確定

為了找到最優(yōu)解，在適應(yīng)度函數(shù)中加入了評估關(guān)聯(lián)規(guī)則有用性的重要標(biāo)準(zhǔn)，即支持度，通過支持度來對適應(yīng)度函數(shù)進(jìn)行定義。首先通過支持度對規(guī)則進(jìn)行篩選，然后判斷篩選出來的規(guī)則是否滿足最小支持度，最后確定這些規(guī)則的適應(yīng)性。關(guān)聯(lián)規(guī)則的適應(yīng)度作如下定義：

式中S′為經(jīng)過遺傳操作所形成的一條新規(guī)則的支持度，S為用戶給定的支持度閾值。

當(dāng)fitness(Ri)>1， Ri保留并進(jìn)入下一代遺傳，當(dāng)fit(Ri)<1， Ri將在下一代遺傳中被淘汰。

4.3遺傳算子的改進(jìn)

(1)選擇算子。 本文的選擇算子采用基于適應(yīng)值比較的方法，即隨機(jī)抽取兩個染色體，適應(yīng)值大的染色體被選擇，適應(yīng)值小的染色體被淘汰，如果兩個染色體的適應(yīng)值相等，則選擇兩個染色體中的任意一個。該方法保證了群體的多樣性，同時又保證了加入配對庫的個體具有較大的適應(yīng)值。

(2)交叉算子。 交叉算子也稱配對算子，同源的染色體可通過染色體交配，重組出新的染色體，本文采用單點(diǎn)交叉的方法，單點(diǎn)交叉是在二進(jìn)制位串中隨機(jī)確定一個交叉位置，在進(jìn)行交叉時，互換相應(yīng)的子串。

(3)變異算子。 本文采用了自適應(yīng)變異算子，該算子是基于基本變異算子的基礎(chǔ)上引入自適應(yīng)變異概率Pm，變異概率Pm隨著群體中個體的多樣性程度而自適應(yīng)改變。變異算子具有局部搜索能力，自適應(yīng)變異概率可以避免出現(xiàn)早熟現(xiàn)象。

4.4規(guī)則提取

由于本文引入了興趣度，提取規(guī)則的標(biāo)準(zhǔn)是此規(guī)則首先要滿足用戶給定的可信度，其次要判斷此規(guī)則的興趣度是否大于1，如果大于1則輸出，否則舍棄。

遺傳算法流程如圖1所示。

圖1 遺傳算法流程圖

5 仿真實(shí)驗和算法分析

某超市用戶的購買的記錄，記錄中的交易記錄有60條，項集數(shù)有6個(I1，I2，I3，I4，I5，I6)。編碼映射表如表3所示。

表3 編碼映射表

設(shè)min_sup=0.3，min_conf=0.6，通過本文提出的挖掘算法挖掘出的關(guān)聯(lián)規(guī)則如表4所示。

表4 發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則

從表4可以看出，興趣度大于1的有序號1，2，4，5，7，9，10，其中序號9和序號10的關(guān)聯(lián)規(guī)則出現(xiàn)了負(fù)屬性項。因為興趣度小于1，可以舍棄序號為3、6、8的關(guān)聯(lián)規(guī)則，序號4和序號10的關(guān)聯(lián)規(guī)則是興趣度最大的兩個，意味著這兩個規(guī)則的利用價值最大。

在測試較大數(shù)據(jù)時，數(shù)據(jù)庫選用KDDCUP 2000的Bule Marrtini Software Inc的數(shù)據(jù)庫BMS-POS，其事務(wù)數(shù)有515 600個，項數(shù)有1 660個，設(shè)交叉概率為60%，變異概率為10%，迭代次數(shù)界限為500，本文提出的算法與Apriori算法的性能比較如圖2所示。

圖2 算法性能比較

通過實(shí)驗分析可以看出本文提出的挖掘算法特點(diǎn)有：

(1)通過把事務(wù)數(shù)據(jù)庫進(jìn)行二進(jìn)制編碼，只存儲0和1，減少了占用的存儲空間，提高了運(yùn)算效率。

(2)在適應(yīng)度函數(shù)中引入了支持度，構(gòu)造一個更適用的適應(yīng)度函數(shù)。

(3)引入自適應(yīng)變異概率，避免出現(xiàn)早熟現(xiàn)象。

(4)引入了興趣度，在規(guī)則提取時舍棄了一些無趣的規(guī)則。

6 結(jié)語

本文結(jié)合遺傳算法的特點(diǎn)挖掘出關(guān)聯(lián)規(guī)則，引入興趣度對關(guān)聯(lián)規(guī)則進(jìn)行篩選，通過遺傳算法的智能搜索技術(shù)，采用二進(jìn)制編碼方法，易于實(shí)現(xiàn)交叉、變異等操作，提高了算法的效率。通過支持度、可信度和興趣度三個度量對關(guān)聯(lián)規(guī)則篩選，使得挖掘出來的關(guān)聯(lián)規(guī)則具有更大的意義和價值。

[1]Matteo Golfarelli，Stefano Rizzi. 戰(zhàn)曉蘇，吳云潔，皮人杰譯.數(shù)據(jù)倉庫設(shè)計：現(xiàn)代原理與方法[M].北京：清華大學(xué)出版社，2010.356.

[2]Paulraj Ponniah. 段云峰，李劍威，韓潔，等譯.數(shù)據(jù)倉庫基礎(chǔ)[M]. 北京：電子工業(yè)出版社，2004.463.

[3]張玉芳，熊忠陽，彭燕，等. 基于興趣度含正負(fù)項目的關(guān)聯(lián)規(guī)則挖掘方法[J].電子科技大學(xué)學(xué)報，2010，39(3)：407.

[4]琚春華，鮑福光，王宗格. 關(guān)聯(lián)規(guī)則的評價方法改進(jìn)與度量框架研究[J].情報學(xué)報，2013，32(6)：584.

[5]梅志芳，王建. 關(guān)聯(lián)規(guī)則興趣度研究問題[J].計算機(jī)工程，2010，36(1)：38.

[6]劉建華，王勇，洪月好. 遺傳算法編碼設(shè)計及其在數(shù)據(jù)挖掘中的應(yīng)用[J].上海電力學(xué)院學(xué)報，2005，21(3)：245.

(責(zé)任編輯李平)

Research on Mining Association Rules Based on Genetic Algorithm

HUANG Yijie1，ZHANG Yixue2

(1.Department of Computer Engineering, Zhangzhou Institute of Technology,

Zhangzhou, Fujian 363000， China; 2.Department of Information Technology,

Zhangzhou Health Vocation College, Zhangzhou, Fujian 363000，China)

In the analysis of the algorithm of mining association rules generated problems in traditional association rules, according to the interest and the feature of genetic algorithm,an algorithm for mining association rules based on genetic algorithm was proposed, and the better association rules were sifted by adaptive genetic algorithm optimization technique and the interest degree. Proved by experiments, the algorithm was effective.

data mining, association rules, interestingness, genetic algorithm

2014-6-9

黃毅杰， 32569528@qq.com。

TP 18

A

1674-9545(2014)03-0045-(04)