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

摘 要：數(shù)據(jù)挖掘是關(guān)聯(lián)規(guī)則中一個重要的研究方向。對關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘和遺傳算法進行概述，闡述關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的意義，提出一種采用改進型遺傳算法的關(guān)聯(lián)規(guī)則的提取算法，并從編碼方法、適應(yīng)度函數(shù)的構(gòu)造和變異、選擇、交叉算子設(shè)計方面進行討論和分析，最后結(jié)合一個具體實例進行應(yīng)用。實驗證明這種算法是有效的。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；遺傳算法；知識發(fā)現(xiàn)

中圖分類號：TP311 文獻標(biāo)識碼：B 文章編號：1004-373X(2008)02-090-03

Association Rule Discovering Based on Genetic Algorithm

PAN Shu，WU Chen

(School of Electronics and Information，Jiangsu University of Science and Technology，Zhenjiang，212003，China)

Abstract：Association rule mining is very important in application of the data mining.This paper summarizes data mining of association rule and genetic algorithm，clarifies the realistic significance of data mining of association rules，puts forward on an algorithm for mining association rules based on improved genetic algorithm，discusses and analyses the genetic algorithm in detail from coding method，fitness function，mutation operators，selection operators，crossover operators and other aspects.Finally，a case is provided for applying for this algorithm.The experimental results show that the efficiency of the algorithm for database.

Keywords：data mining;association rule;genetic algorithm;KDD

數(shù)據(jù)挖掘是20世紀90年代中期興起的一項新技術(shù)，他是知識發(fā)現(xiàn)（KDD）過程中的關(guān)鍵步驟。

數(shù)據(jù)收集和數(shù)據(jù)存儲技術(shù)的快速進步使得各組織機構(gòu)可以積累海量數(shù)據(jù)。然而提取有用的信息已經(jīng)成為巨大的挑戰(zhàn)。有時，由于數(shù)據(jù)量過大或數(shù)據(jù)本身非傳統(tǒng)的特點，使得無法使用傳統(tǒng)的數(shù)據(jù)分析工具和技術(shù)處理他們，這個時候就需要新的技術(shù)[CD2]數(shù)據(jù)挖掘，其將傳統(tǒng)的數(shù)據(jù)分析方式與處理大量數(shù)據(jù)的傳統(tǒng)算法相結(jié)合，為探查和分析新的數(shù)據(jù)類型以及用新方法分析已有數(shù)據(jù)類型提供令人振奮的機會［1］。

關(guān)聯(lián)規(guī)則是當(dāng)前數(shù)據(jù)挖掘的主要模式之一，是發(fā)現(xiàn)數(shù)據(jù)庫中不同項目之間的聯(lián)系［2］。

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

1.1 數(shù)據(jù)挖掘的定義及相關(guān)知識

數(shù)據(jù)挖掘（data mining）是從大型數(shù)據(jù)庫中的數(shù)據(jù)中提取人們感興趣的知識，這些知識是隱含的、事先未知的潛在的有用的信息。提取的知識表示為概念、規(guī)則、規(guī)律、模式等形式［3］。數(shù)據(jù)挖掘所能發(fā)現(xiàn)的知識有如下幾種：廣義型知識，反映同類性質(zhì)的知識；特征型知識，反映事務(wù)各方面的特征知識；差異型知識，反映不同事務(wù)之間屬性差別的知識；關(guān)聯(lián)型知識，反映事務(wù)之間依賴或關(guān)聯(lián)關(guān)系的知識；預(yù)測型知識，根據(jù)歷史和當(dāng)前的數(shù)據(jù)推測未來數(shù)據(jù)；偏離型知識，揭示事務(wù)常規(guī)的異常現(xiàn)象。知識發(fā)現(xiàn)的工具和方法，常用的有分類、聚類、關(guān)聯(lián)、模式識別、可視化、決策樹、遺傳算法、不確定處理等［4］。

1.2 關(guān)聯(lián)規(guī)則的形式及定義

令I＝{i1，i2，…，id}是事務(wù)中所有項目的集合，而T={t1，t2，…，tN}是所有事務(wù)的集合。每個事務(wù)ti包含的項集都是I的子集。在關(guān)聯(lián)分析中，包含0個或多個項的集合被稱為項集。關(guān)聯(lián)規(guī)則（Association Rule）是形如X→Y的蘊涵表達式，其中X和Y是不相交的項集。關(guān)聯(lián)規(guī)則可以用他的支持度（support）和可信度（confidence）度量。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而可信度確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。給定事務(wù)的集合T，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于minsup并且可信度大于minconf的所有規(guī)則，其中minsup和minconf是對應(yīng)的支持度和可信度閾值。

1.3 關(guān)聯(lián)規(guī)則挖掘任務(wù)

大多數(shù)關(guān)聯(lián)規(guī)則的挖掘算法通常采用的一種策略是：將關(guān)聯(lián)規(guī)則挖掘任務(wù)分解為2個子任務(wù)：

（1） 頻繁項集的產(chǎn)生，其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項集，這些項集稱作頻繁項集；

（2） 規(guī)則的產(chǎn)生，其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高可信度的規(guī)則。

Apriori算法是第一個關(guān)聯(lián)規(guī)則挖掘算法，他開創(chuàng)性地使用基于支持度的剪枝技術(shù)，系統(tǒng)的控制候選項集指數(shù)增長，Apriori算法的計算復(fù)雜度主要受支持度閾值、項數(shù)、事務(wù)數(shù)、事務(wù)的平均寬度等因素影響。

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

遺傳算法（Genetic Algorithms，GAs），是模擬生物在自然環(huán)境中遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。他在解決大空間、多峰值、非線性、全局優(yōu)化等高復(fù)雜度問題時顯示了獨特的優(yōu)勢[5]。他有如下的優(yōu)勢：智能式搜索、漸進式優(yōu)化、全局最優(yōu)解、黑箱式結(jié)構(gòu)、通用性強和并行式算法。

2.1 編碼

本文采用實數(shù)數(shù)組的方法進行編碼，實數(shù)數(shù)組的元素個數(shù)與事務(wù)數(shù)據(jù)中對應(yīng)的字段的格式相對應(yīng)，實數(shù)數(shù)組的元素代表了字段的屬性值。經(jīng)此操作后，對個體的交叉、變異等操作就變成對數(shù)組的操作。

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

遺傳算法采用適應(yīng)度這個概念度量群體中個體在優(yōu)化算法計算中可能達到、接近于或有利于找到最優(yōu)解的優(yōu)良程度，適應(yīng)度是遺傳算法選擇操作的惟一依據(jù)。支持度是關(guān)聯(lián)規(guī)則重要性的衡量標(biāo)準(zhǔn)，有些關(guān)聯(lián)規(guī)則可信度高，但是支持度較低，說明該規(guī)則使用的機會很少，所以本文考慮使用關(guān)聯(lián)規(guī)則的至支持度作為定義他的適應(yīng)度函數(shù)。規(guī)則的適應(yīng)度可以定義如下：

式中的S′為經(jīng)過遺傳操作所形成的一條新規(guī)則的支持度;S為用戶給定支持度的閾值，若Ri符合要求，則適應(yīng)度大于1，否則適應(yīng)度小于1。

2.3 改進型遺傳算法

習(xí)慣上將J#8226;H#8226;Holland提出的遺傳算法稱為簡單遺傳算法（Simple Genetic Algorithm，SGA），這種算法有一定片面性，并且簡單的遺傳算法在任何情況下都是收斂的，即不能搜索到最優(yōu)解[6]。本文提出一種改進的遺傳算法。該算法能夠加快遺傳進化速度，而且能增強算法的全局收斂性能、從而得到滿意的全局最優(yōu)解。

(1) 選擇算子

一般簡單遺傳算法選用的都是賭輪選擇，然而賭輪算法容易早熟，并容易使遺傳算法失去進化能力，并且對于關(guān)聯(lián)規(guī)則，2個適應(yīng)度高的個體，未必繁殖出一個高適應(yīng)度的個體，相反兩個適應(yīng)度不高的個體可能繁殖出一個適應(yīng)度高的個體。本文采用的是只要適應(yīng)度大于“1”的規(guī)則都采用下來，也就是只要滿足規(guī)則的要求都保留下來

(2)交叉算子

隨機選擇父本、母本，按照交叉方法進行n交叉，產(chǎn)生2n后代，在其中選擇出最好的2個進入下一代。既保存父本、母本的基因，又提高了種群的整體性能。

(3)換異算子

變異概率是一個重要參數(shù)，本文利用自適應(yīng)來確定他，當(dāng)群體最大適應(yīng)度值和平均適應(yīng)度值相近時，說明群體趨于收斂，則要增大Pm ；反之則說明群體趨于多樣性，則要減少Pm。這樣可以避免近親雜交引起的過早收斂和降低收斂速度。

2.4 規(guī)則的提取

根據(jù)遺傳算法搜索出規(guī)則，最后根據(jù)設(shè)定的可信度提取規(guī)則，符合可信度要求的規(guī)則輸出，反之不輸出。

3 實例應(yīng)用

本文利用上述方法對某醫(yī)院某段時間骨科住院病人情況進行了挖掘總結(jié)。

3.1 編碼

這里略去沒有必要的病人姓名及編號，把表1中所有屬性都轉(zhuǎn)化為數(shù)值型值。

4 結(jié) 語

本文對關(guān)聯(lián)規(guī)則的挖掘算法進行研究，并將改進型遺傳算法運用于關(guān)聯(lián)規(guī)則的提取，以某醫(yī)院骨科病人住院情況為例，進行關(guān)聯(lián)規(guī)則挖掘，取得了一定的效果。基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘還可以應(yīng)用在如學(xué)生信息分析等其他領(lǐng)域，具有良好的研究和應(yīng)用價值。

參 考 文 獻

［1］吉根林.遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用［J］.信息技術(shù)，2001，22（21）：5-9.

［2］孫曉健.數(shù)據(jù)挖掘技術(shù)在經(jīng)營分析系統(tǒng)中的應(yīng)用［J］.微計算機信息，2007，23(12):169-171.

［3］Ping-Ning Tan，Michael Steinbach，Vipin Kumar.數(shù)據(jù)挖掘?qū)д摚跰］.北京：人民郵電出版社，2006.

［4］邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京：中國水利水電出版社，2003.

［5］李敏強，寇紀淞，李丹，等.遺傳算法的基本理論與應(yīng)用［Ｍ］.北京:科學(xué)出版社，2003.

［6］王禮剛，左源瑞，李盛瑜.基于改進型遺傳算法關(guān)聯(lián)規(guī)則的提取算法及其應(yīng)用［J］.重慶師范大學(xué)學(xué)報，2006，6(3):42-45.

［7］郭嗣琮.信息科學(xué)中的軟計算方法［M］.沈陽:東北大學(xué)出版社，2001.

［8］譚建輝.一種基于遺傳算法的數(shù)據(jù)挖掘技術(shù)[J].現(xiàn)代電子技術(shù)，2005，28(19):60-62.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。