一種改進的基于關聯規則挖掘的遺傳算法

摘要：針對傳統的遺傳算法容易導致算法的過早收斂而陷于局部最優困境，或收斂時間過長而消耗大量的搜索時間的缺陷，該文提出了一種改進的遺傳算法，該算法采用一種自適應變異率和改進的個體選擇方法，并且將這種改進遺傳算法應用于關聯規則的挖掘，實驗結果證明這種算法是有效的。

關鍵詞：數據挖掘；遺傳算法；關聯規則

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)35-2504-03

A Kind of Improved Genetic Algorithm Based on Association Rules Mining

LAI Wan-qin， LEI Xiao-zhen

(Fujian Communications Technology College， FuZhou 350007， China)

Abstract: To the traditional genetic algorithm easily lead to premature convergence of the algorithm and into the plight of local optimum， or Convergence too much time and consume a large amount of time to search for flaws，this text proposed a kind of improved genetic algorithm， The algorithm adopts an adaptive mutation rate and improve the methods of individual choice， and this will improve the genetic algorithm used in the data mining association rules. The experimental results show that the efficiency of the algorithm for database.

Key words: data mining; genetic algorithm; association rule

1 引言

遺傳算法是一種基于生物進化論和分子遺傳學的全局隨機搜索算法，具有很強的隨機性、魯棒性和隱含并行性，能快速、有效地進行全局優化搜索，是處理大規模數據項目集的有效方法。目前基于遺傳算法的數據挖掘方法有了一定的進展，基于遺傳算法的關聯規則研究也取得了一些成果。但是，傳統的遺傳算法存在一定的缺陷，容易導致算法的過早收斂而陷于局部最優困境，或收斂時間過長而消耗大量的搜索時間。因此，本文提出了一種改進的遺傳算法，該算法采用一種自適應變異率和改進的個體選擇方法，用來克服上述問題，并且將這種改進遺傳算法應用于關聯規則的挖掘。

2 遺傳算法原理

遺傳算法（GeneticA lgorithms，GAs），是模擬生物在自然環境中遺傳和進化過程而形成的一種自適應全局優化概率搜索算法。他在解決大空間、多峰值、非線性、全局優化等高復雜度問題時顯示了獨特的優勢[1]。把待解決問題的參數編成二進制碼或十進制碼（也可編成其他進制碼）即基因，若干基因組成一個染色體（個體），許多染色體進行類似于自然選擇、配對交叉和變異的運算，經過多次重復迭代（即世代遺傳）直至得到最后的優化結果[2]。使用遺傳算法解決問題時涉及到以下七個主要因素[3]。

1) 編碼

將待求解問題的解根據約束條件、選擇合適的編碼方法（比如二進制、整數、實數編碼方法、格雷碼編碼、多參數級聯編碼、多參數交叉編碼等），編碼成通過位串表示的染色體。不同的編碼，有不同的特點，使用時應根據需要選擇[4]。

2) 適應度函數

遺傳算法采用適應度這個概念度量群體中個體在優化算法計算中可能達到、接近于或有利于找到最優解的優良程度，適應度是遺傳算法選擇操作的惟一依據。

3) 選擇算子

遺傳算法中最重要的就是選擇、交叉、變異這三個基本算子。選擇算子一般采用輪盤賭選擇，在這種選擇算法中，每條染色體的適應度函數值占所有染色體適應度函數值總和的比例即為該染色體被選擇的概率，根據這個概率，從原有的染色體中挑選出染色體放入交配池中，新的染色體可以有重復。

4) 交叉算子

交叉是指每對染色體選擇一個隨機位置，其后的二進制串進行交換即可。常見的交叉方法有單點交叉、多點交叉等等，一般采用單點交叉。

5) 變異算子

變異算子有利于增加群體多樣性，變異方法也有很多，但最常用的就是基本位變異算法。

6) 控制參數

遺傳算法中控制參數的選擇也是很重要的，一般參數取值范圍如下:

種群大小N:即群體中所含個體的數量。種群大小影響GA的有效性，N太小，GA會很差或根本找不出問題的解，因為太小的種群數目不能提供足夠的采樣點;N太大，會增加計算量，使收斂時間增長。一般取為20~100;

遺傳代數T:控制著遺傳算法的終止代數。一般取為100~500;

交叉概率Pc:控制著交叉操作的頻率，Pc太大，會使高適應值的結構很快被破壞掉，Pc太小搜索就會停止不前。一般Pc取0.4~0.99;

變異概率Pm:是增大種群多樣性的第二個因素，Pm太小不會產生新的基因塊，Pm太大，會使GA變成隨機搜索。一般Pm取0.0001~0.10

7) 終止條件

終止條件可以設定為規定的進化代數，也可以設定為當群體中某個解的適應值達到某一預先規定的范圍內時停止，還可以迭代若干代直至群體中的個體不再發生變化。

3 關聯規則定義

設I={i1，i2，.....im}是個m不同項目的集合，D是一組事務的集合，D中每一事務T是I的子集，并且有一個標識符TID。設A是一個項集，事務T包含A當且僅當A#8838;T，關聯規則是形如A#8658;B.的蘊涵式，其中A#8838;I， B#8838;I，且A∩B=#981;，其意義在于一個事務中的某些項的出現，可以推測出另一個項在同一事務集中出現。規則A#8658;B在事務集D中成立，具有支持度S，其中S是D中事務包含A∪B的百分比，即概率P(A∪B)；規則A#8658;B在事務D中具有置信度C，C是指如果D中包含A的事務同時也包含B的百分比，也就是條件概率P (A/B)：

Support(A#8658;B)=P(A∪B) （1）

Confidence (A#8658;B)=P (A/B) （2）

關聯規則可以理解為一個命題，即如果一個事務支持項目集A，則它也有一定的可能性支持項目集B，這一可能性稱這為規則的可信度，記為conf (R)或C (R)。

規則R的可信度為支持項目集A的事務T也支持項目集B的條件概率。一個關聯規則必須具備足夠大的支持度和可信度。對于給定最小可信度minconf和最小支持度minsup，如果conf(R)≥minconf ， supp(R)≥minsupp，則稱關聯規則R關于數據庫成立，規則稱為強規則。

4 改進的遺傳算法用于關聯規則挖掘

早熟問題是遺傳算法中不可忽視的現象，其具體表現為：1) 群體中所有的個體都陷于同一極值而停止進化；2) 接近最優解的個體總是被淘汰，進化過程不收斂。

為了解決這二個問題：1) 提出了一種自適應變異率方法，可以避免過度變異造成不收斂，或陷入局部最優解；2) 提出了一種基于排序的個體選擇方法，將其應用于遺傳算法進化后期，從而防止適應度高的個體數量迅速增長造成個體差異過小而提前收斂。

4.1 自適應變異率

在遺傳算法進化的早期階段，如采用固定的變異概率Pm，則當Pm取值很小時，變異算子對群體不會產生影響，不利于新的基因的引入;當Pm取值很大時，有可能破壞群體中的優良基因，使得算法收斂速度變慢甚至不收斂。在這里提出一種自適應變異率方法，應用于進化的早期階段，變異率表示如下:

（3）

其中，Pm(n)是第n代的變異率，Pm(n+1)是第n+1代的變異率，初始變異率為Pm(0)，fi(n)為第n代種群個體i的適應度，fmax(n)是第n代種群最高適應度，fi(n+1)是第n+1代個體i的適應度，fmax(n+1)是第n+1代種群最高適應度，m為種群個體數量，λ為調整系數。

這樣就使得種群優良基因不會過度變異被破壞而造成收斂時間過長，又有利于新基因的引入，避免早熟而陷入局部最優，從而提高了遺傳算法的性能。

4.2 改進的個體選擇方法

采用一種改進的選擇淘汰方法，應用于遺傳算法的后期:

1) 適應度大小對待篩選個體排序；

2) 前1/4個體復制2份，前1/4至2/4部分個體復制1份，進入下一輪選擇；

3) 前2/4至3/4部分個體保留，進入下一輪選擇；

4) 前3/4至4/4部分個體淘汰，不再進入下一輪選擇。

4.3 改進的遺傳算法用于關聯規則挖掘

4.3.1 遺傳算法編碼

遺傳算法最基本的問題是編碼問題。一個好的編碼方法，會使交叉、變異等遺傳操作更方便實現。

當我們找到了一條形如A1∧A2∧…∧An#8658;B1∧B2∧…∧Bn的關聯規則時，實質上是在事務數據庫中找到了這樣一條規則: A1∧A2∧…∧An和B1∧B2∧…∧Bn。同時為真時在整個事務集中所占的百分比大于用戶給定支持度，且B1∧B2∧…∧Bn為真在條件A1∧A2∧…∧An為真條件下的概率大于用戶給定的可信度。其中(A1，A2，…An;B1，B2，…Bn)為事務數據庫中的一個個字段。

本文采用實數組方法進行編碼，實數數組中元素的個數與事務數據庫中的字段個數相對應，元素值代表了元素的屬性值，如表1所示的數據庫。

用一個長度為N的數組來表示表1所表示的事務數據庫的個體編碼，A[1]表示字段1， A[2]表示字段2， ....，A[R]表示字段R;將屬性值用數值型的值表示，例如:用數值1表示屬性值11，數值2表示屬性值12，…，數值MR表示屬性值MR，這樣就可以用數組A[N]的元素值來表示相對應字段的屬性值。另外用值0表示此屬性與其它的屬性無關聯。表1所示的數據庫的編碼如圖1所示。

用實數數組編碼，不僅編碼簡單，易于實現，而且也便于遺傳算子的操作。進行這樣的編碼后，交叉、變異等的操作就變成了對數組的操作。

4.3.2 適應度函數的構造

綜合考慮可信度和支持度，把其適應度定義為如下形式：

F(X#8658;Y)=αS(X#8658;Y) +βC(X#8658;Y)

其中，α，β分別為支持度和可信度在評價規則時所占的份額，當某一個個體不能解釋成合法的規則時，則認為該個體是無用規則(違反了實際)，記其適應度為：

Fitness=0

根據上面定義的適應度函數，能夠搜索出高支持度和置信度的個體，也即規則。

4.3.3 規則評價和提取

為了評價一條規則是否滿足發現目標，可以通過一個規則評價函數來計算給定個體的支持度和置信度，然后據此判定該個體是否是想要的規則。在算法的運行中，對任意適應度高于某一指定值的個體，都調用規則評價函數對它進行評價。如果該個體滿足規則要求，假設支持度大于0. 1且可信度大于0. 8，則將其存入規則庫。在算法結束后，還要對規則庫進行冗余規則的淘汰，最后留在規則庫中的規則就是本次發現過程的最終規則。

4.3.4 算法描述

step 1：初始種群P(0)；獲取用戶給定的支持度S，可信度C；

step 2：對當前種群P(t)中的每一個個體計算適應值；

step 3：對當前種群P(t)進行改進個體選擇的選擇操作；

step 4：對當前種群P(t)進行交叉操作；

step 5：對當前種群P(t)進行變異操作；

step 6：生成新的種群P(t+1)；

step 7：同終止代數T進行對比，如果達到終止條件，則終止并輸出規則，否則轉步驟2。

5 仿真實驗及分析

在用戶填寫上網活動的數據庫的數據挖掘中采用本文提出的改進遺傳算法，目的是發現用戶網上各種活動的關聯規則。

用戶上網活動的取值表屬性（字段）如表2。

根據實際情況，活動名屬性取值分別為股票=1、網上購物=2、在線游戲=3、娛樂=4、新聞=5、在線影視=6、郵件=7、聊天=8。

對每項活動屬性取值分別為喜歡=1、一股=2、偶爾=3、從不=0，因此用戶上網絡活動的情況用8位的十進制數字來表示，處理后的數據映射結果如表3。

如王小華“03311022”表示用戶“王小華”喜歡網上購物和玩在線游戲，偶爾會瀏覽娛樂或新聞內容網頁，上網一般會聊天、觀看在線影視和收發郵件，但從不在網上進行股票交易活動。

實驗中，根據以上算法，我們選擇了有效的調查問卷500份，隨機生成N=20表示關聯規則的初始種群，適應度函數中α =2.5，β=0.5。初始變異率Pm(0) =0.05，自適應變異率公式中λ=1.5，交叉概率Pc=0.7進化終止條件為fmax-fmin<0.05或進化300代。

對運行結果進行合并相似規則的最終處理，發現以下規則：

1) <喜歡玩在線游戲>(支持度20%，可信度85%)=><喜歡上網聊天>

2) <上網從事股票交易>(支持度15%，可信度80%)=><工作中會使用郵件>

3) <喜歡網上購物>(支持度10%，可信度90%)=><喜歡上網瀏覽新聞>

從以上規則可以看出該算法根據指定的支持度閉值0. 10和可信度閉值0. 8而發現的規則與實際情況比較吻合。

6 結論

本文在闡述關聯規則的挖掘算法的基礎上，對傳統遺傳算法進行了一些改進并將改進的遺傳算法運用于關聯規則的提取，結合上網活動調查表，給出了改進的遺傳算法進行關聯規則挖掘的實例。仿真實驗證明了算法的有效性和可行性。

參考文獻：

[1] 李敏強，寇紀淞，李丹，等.遺傳算法的基本理論與應用[M].北京:科學出版社，2003.

[2] 陳根社，陳新海.遺傳算法的研究與進展[J].信息與控制，1994，23(4):215-222.

[3] 席裕庚.遺傳算法綜述[J].控制理論及應用，1996，13(6).

[4] 劉勇，康立山.非數值并行算法(第二冊)一遺傳算法[M].北京:科學出版社，1995.