基于遺傳算法的關聯(lián)規(guī)則挖掘
2008-04-12 00:00:00潘舒吳陳
現(xiàn)代電子技術 2008年2期
摘 要：數(shù)據(jù)挖掘是關聯(lián)規(guī)則中一個重要的研究方向。對關聯(lián)規(guī)則的數(shù)據(jù)挖掘和遺傳算法進行概述，闡述關聯(lián)規(guī)則數(shù)據(jù)挖掘的意義，提出一種采用改進型遺傳算法的關聯(lián)規(guī)則的提取算法，并從編碼方法、適應度函數(shù)的構造和變異、選擇、交叉算子設計方面進行討論和分析，最后結合一個具體實例進行應用。實驗證明這種算法是有效的。
關鍵詞：數(shù)據(jù)挖掘；關聯(lián)規(guī)則；遺傳算法；知識發(fā)現(xiàn)
中圖分類號：TP311 文獻標識碼：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年代中期興起的一項新技術，他是知識發(fā)現(xiàn)（KDD）過程中的關鍵步驟。
數(shù)據(jù)收集和數(shù)據(jù)存儲技術的快速進步使得各組織機構可以積累海量數(shù)據(jù)。然而提取有用的信息已經(jīng)成為巨大的挑戰(zhàn)。有時，由于數(shù)據(jù)量過大或數(shù)據(jù)本身非傳統(tǒng)的特點，使得無法使用傳統(tǒng)的數(shù)據(jù)分析工具和技術處理他們，這個時候就需要新的技術[CD2]數(shù)據(jù)挖掘，其將傳統(tǒng)的數(shù)據(jù)分析方式與處理大量數(shù)據(jù)的傳統(tǒng)算法相結合，為探查和分析新的數(shù)據(jù)類型以及用新方法分析已有數(shù)據(jù)類型提供令人振奮的機會［1］。
關聯(lián)規(guī)則是當前數(shù)據(jù)挖掘的主要模式之一，是發(fā)現(xiàn)數(shù)據(jù)庫中不同項目之間的聯(lián)系［2］。
1 關聯(lián)規(guī)則
1.1 數(shù)據(jù)挖掘的定義及相關知識
數(shù)據(jù)挖掘（data mining）是從大型數(shù)據(jù)庫中的數(shù)據(jù)中提取人們感興趣的知識，這些知識是隱含的、事先未知的潛在的有用的信息。提取的知識表示為概念、規(guī)則、規(guī)律、模式等形式［3］。數(shù)據(jù)挖掘所能發(fā)現(xiàn)的知識有如下幾種：廣義型知識，反映同類性質(zhì)的知識；特征型知識，反映事務各方面的特征知識；差異型知識，反映不同事務之間屬性差別的知識；關聯(lián)型知識，反映事務之間依賴或關聯(lián)關系的知識；預測型知識，根據(jù)歷史和當前的數(shù)據(jù)推測未來數(shù)據(jù)；偏離型知識，揭示事務常規(guī)的異?，F(xiàn)象。知識發(fā)現(xiàn)的工具和方法，常用的有分類、聚類、關聯(lián)、模式識別、可視化、決策樹、遺傳算法、不確定處理等［4］。
1.2 關聯(lián)規(guī)則的形式及定義
令I＝{i1，i2，…，id}是事務中所有項目的集合，而T={t1，t2，…，tN}是所有事務的集合。每個事務ti包含的項集都是I的子集。在關聯(lián)分析中，包含0個或多個項的集合被稱為項集。關聯(lián)規(guī)則（Association Rule）是形如X→Y的蘊涵表達式，其中X和Y是不相交的項集。關聯(lián)規(guī)則可以用他的支持度（support）和可信度（confidence）度量。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而可信度確定Y在包含X的事務中出現(xiàn)的頻繁程度。給定事務的集合T，關聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于minsup并且可信度大于minconf的所有規(guī)則，其中minsup和minconf是對應的支持度和可信度閾值。
1.3 關聯(lián)規(guī)則挖掘任務
大多數(shù)關聯(lián)規(guī)則的挖掘算法通常采用的一種策略是：將關聯(lián)規(guī)則挖掘任務分解為2個子任務：
（1） 頻繁項集的產(chǎn)生，其目標是發(fā)現(xiàn)滿足最小支持度閾值的所有項集，這些項集稱作頻繁項集；
（2） 規(guī)則的產(chǎn)生，其目標是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高可信度的規(guī)則。
Apriori算法是第一個關聯(lián)規(guī)則挖掘算法，他開創(chuàng)性地使用基于支持度的剪枝技術，系統(tǒng)的控制候選項集指數(shù)增長，Apriori算法的計算復雜度主要受支持度閾值、項數(shù)、事務數(shù)、事務的平均寬度等因素影響。
2 基于遺傳算法的關聯(lián)規(guī)則
遺傳算法（Genetic Algorithms，GAs），是模擬生物在自然環(huán)境中遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索算法。他在解決大空間、多峰值、非線性、全局優(yōu)化等高復雜度問題時顯示了獨特的優(yōu)勢[5]。他有如下的優(yōu)勢：智能式搜索、漸進式優(yōu)化、全局最優(yōu)解、黑箱式結構、通用性強和并行式算法。
2.1 編碼
本文采用實數(shù)數(shù)組的方法進行編碼，實數(shù)數(shù)組的元素個數(shù)與事務數(shù)據(jù)中對應的字段的格式相對應，實數(shù)數(shù)組的元素代表了字段的屬性值。經(jīng)此操作后，對個體的交叉、變異等操作就變成對數(shù)組的操作。
2.2 適應度函數(shù)
遺傳算法采用適應度這個概念度量群體中個體在優(yōu)化算法計算中可能達到、接近于或有利于找到最優(yōu)解的優(yōu)良程度，適應度是遺傳算法選擇操作的惟一依據(jù)。支持度是關聯(lián)規(guī)則重要性的衡量標準，有些關聯(lián)規(guī)則可信度高，但是支持度較低，說明該規(guī)則使用的機會很少，所以本文考慮使用關聯(lián)規(guī)則的至支持度作為定義他的適應度函數(shù)。規(guī)則的適應度可以定義如下：
式中的S′為經(jīng)過遺傳操作所形成的一條新規(guī)則的支持度;S為用戶給定支持度的閾值，若Ri符合要求，則適應度大于1，否則適應度小于1。
2.3 改進型遺傳算法
習慣上將J#8226;H#8226;Holland提出的遺傳算法稱為簡單遺傳算法（Simple Genetic Algorithm，SGA），這種算法有一定片面性，并且簡單的遺傳算法在任何情況下都是收斂的，即不能搜索到最優(yōu)解[6]。本文提出一種改進的遺傳算法。該算法能夠加快遺傳進化速度，而且能增強算法的全局收斂性能、從而得到滿意的全局最優(yōu)解。
(1) 選擇算子
一般簡單遺傳算法選用的都是賭輪選擇，然而賭輪算法容易早熟，并容易使遺傳算法失去進化能力，并且對于關聯(lián)規(guī)則，2個適應度高的個體，未必繁殖出一個高適應度的個體，相反兩個適應度不高的個體可能繁殖出一個適應度高的個體。本文采用的是只要適應度大于“1”的規(guī)則都采用下來，也就是只要滿足規(guī)則的要求都保留下來
(2)交叉算子
隨機選擇父本、母本，按照交叉方法進行n交叉，產(chǎn)生2n后代，在其中選擇出最好的2個進入下一代。既保存父本、母本的基因，又提高了種群的整體性能。
(3)換異算子
變異概率是一個重要參數(shù)，本文利用自適應來確定他，當群體最大適應度值和平均適應度值相近時，說明群體趨于收斂，則要增大Pm ；反之則說明群體趨于多樣性，則要減少Pm。這樣可以避免近親雜交引起的過早收斂和降低收斂速度。
2.4 規(guī)則的提取
根據(jù)遺傳算法搜索出規(guī)則，最后根據(jù)設定的可信度提取規(guī)則，符合可信度要求的規(guī)則輸出，反之不輸出。
3 實例應用
本文利用上述方法對某醫(yī)院某段時間骨科住院病人情況進行了挖掘總結。
3.1 編碼
這里略去沒有必要的病人姓名及編號，把表1中所有屬性都轉(zhuǎn)化為數(shù)值型值。
4 結 語
本文對關聯(lián)規(guī)則的挖掘算法進行研究，并將改進型遺傳算法運用于關聯(lián)規(guī)則的提取，以某醫(yī)院骨科病人住院情況為例，進行關聯(lián)規(guī)則挖掘，取得了一定的效果。基于遺傳算法的關聯(lián)規(guī)則挖掘還可以應用在如學生信息分析等其他領域，具有良好的研究和應用價值。
參 考 文 獻
［1］吉根林.遺傳算法在數(shù)據(jù)挖掘中的應用［J］.信息技術，2001，22（21）：5-9.
［2］孫曉健.數(shù)據(jù)挖掘技術在經(jīng)營分析系統(tǒ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］李敏強，寇紀淞，李丹，等.遺傳算法的基本理論與應用［Ｍ］.北京:科學出版社，2003.
［6］王禮剛，左源瑞，李盛瑜.基于改進型遺傳算法關聯(lián)規(guī)則的提取算法及其應用［J］.重慶師范大學學報，2006，6(3):42-45.
［7］郭嗣琮.信息科學中的軟計算方法［M］.沈陽:東北大學出版社，2001.
［8］譚建輝.一種基于遺傳算法的數(shù)據(jù)挖掘技術[J].現(xiàn)代電子技術，2005，28(19):60-62.
注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。
