1、遺傳算法在數(shù)據(jù)挖掘中的研究與應用 學院： 計算機學院 班級： 計研-14 學號： 2deeeeeeeeeee 姓名： 笑嘻嘻 2015年1月遺傳算法在數(shù)據(jù)挖掘中的研究與應用摘 要 遺傳算法(genectialgoritlllnn,GA)是一種模擬生物進化過程的自適應全局優(yōu)化算法，是解決現(xiàn)代非線性優(yōu)化問題的一種重要方法。對于大量數(shù)據(jù)的嘈雜無序的特征，遺傳算法是有效解決此類問題的方法之一。它模擬自然選擇和生物遺傳機制，利用遺傳算子產生后代,通過群體的迭代，使個體的適應性不斷提高，最終群體中適應值最高的個體即是優(yōu)化問題的最優(yōu)或次優(yōu)解。數(shù)據(jù)挖掘(DataMining,DM)就是從大量的、不完全的、有噪

2、聲的、模糊的、隨機的數(shù)據(jù)中,提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。它借助了多年來數(shù)理統(tǒng)計技術和人工智能以及知識工程等領域的研究成果構建自己的理論體系,是一個交叉學科領域,集成了數(shù)據(jù)庫、人工智能、數(shù)理統(tǒng)計、可視化、并行計算等技術。關聯(lián)規(guī)則作為數(shù)據(jù)挖掘領域的一個重要研究分支，針對關聯(lián)規(guī)則挖掘中經(jīng)典算法-Aprior算法的局限性,在劃分技術的基礎上提出了一種基于遺傳算法的關聯(lián)規(guī)則挖掘模型。分類是數(shù)據(jù)挖掘中最重要的方法之一，決策樹作為發(fā)現(xiàn)分類模型的常用技術現(xiàn)已被廣泛研究并取得了很大的進展。然而，在決策樹的構造過程中采用貪心算法，造成了決策樹容易過分擬合、規(guī)模過大、產生的

3、規(guī)則長度過長等缺點。針對這些缺陷，提出了一種基于遺傳算法與關聯(lián)規(guī)則算法的混合分類挖掘方法。本論文主要圍繞著遺傳算法應用于數(shù)據(jù)挖掘研究展開,基本上分為四部分：(1)對KDD(Knowledge Discovery in Database)技術進行了總體上的概述，包括KDD的含義、一般過程、主要方法和技術、研究的現(xiàn)狀及存在的問題等，為在這一領域進行更為深入的研究打下初步基礎。在此基礎之上對發(fā)現(xiàn)分類模型的各種技術以及關聯(lián)規(guī)則挖掘算法進行了較為全面的研究。(2)對遺傳算法的編碼方法、適應度函數(shù)、遺傳操作算子、參數(shù)的選擇作了全面且深入的研究。(3)對提出的基于遺傳算法的關聯(lián)規(guī)則挖掘方法進行了全面的描述。

4、(4)對提出的基于遺傳算法與關聯(lián)規(guī)則算法相結合的混合分類方法進行了全面的分析。關鍵詞 遺傳算法；數(shù)據(jù)挖掘；分類；關聯(lián)規(guī)則Research and Application on Data Mining based on Genetic AlgorithmAbstract Genetic Algorithm is a kind of global optimization algorithm which simulates the process of biological evolution, it's a important method to settle modern nonlin

5、ear optimization problems. For the chaos of the vest data, Genetic Algorithm is one of the effective methods that can solve this kind of question. It simulates natural selection and biological genetic mechanism and generates the offspring by genetic operators. Through the iterativeness of population

6、, the fitnesses of the individuals is improved and finally the individual with the highest fitness just is the optimal solution or suboptimal solution of the optimization problem.Data Mining(DM) is a process that pick previously unknown and potentially useful information and technology from large vo

7、lumes of incomplete, fuzzy and stochastic data with noise. It made use research achievements of many years in the areas of statistical and mathematical techniques, artificial intelligence and knowledge engineering etc. to form its theory system. It is a Cross-Discipline Field which integrated the te

8、chnology such as database, artificial intelligence, statistical and mathematical techniques, Description and Visualization, Parallel Computing etc.Associate rule is an important theme in the data mining. In view of the Apriori algorithm's limitation,an improved Apriori algorithm based on partiti

9、on technology is proposed in this paper. Classification is one of the important themes in Data mining. Decision Tree is a method of Data mining that is used widely to mining classification model. It has studied widely and made a great progress. However, Decision Tree always leads to be over-fitting,

10、 to have large scales and induce longer classification rules if it adopts greedy algorithm. According to these shortcomings, an approach to data mining which integrates genetic algorithm and association rule algorithm is proposed in this paper. There are four main points in this thesis as follows:1.

11、The conception in data mining, basic process, main technology and the development of the Situation are described in this theme. And the same time, some useful classification algorithms are discussed such as decision tree, genetic algorithm, and neural networks.2.Biological principle, mathematic prin

12、ciple, search principle and the feature are completely described in the paper.3.The approach to association which integrates genetic algorithm is described in the paper.4.The approach to classification which integrates genetic algorithm and association rule algorithm is described in the paper.Keywor

13、ds Genetic algorithm; Data mining; Classification; Association rules1. 數(shù)據(jù)挖掘1.1數(shù)據(jù)挖掘的產生和研究目標近年來隨著數(shù)據(jù)庫技術和計算機網(wǎng)絡的廣泛應用，加上使用先進的自動數(shù)據(jù)生成和采集工具，人們所擁有的數(shù)據(jù)量急劇增大。激增的數(shù)據(jù)背后隱藏著許多重要的信息，如何從大量的數(shù)據(jù)中提取并找到有用的信息以指導決策，是迫切需要解決的問題。在這種情況下，數(shù)據(jù)挖掘1新型的數(shù)據(jù)分析技術于 1995 年誕生了。目前，數(shù)據(jù)挖掘的研究重點轉向多種發(fā)現(xiàn)策略和技術的集成，以及多種學科之間的相互滲透。其他內容的專題會議也把數(shù)據(jù)挖掘和知識發(fā)現(xiàn)列為議題之一，

14、成為當前計算機科學界的一大熱點。數(shù)據(jù)挖掘是一門新興的數(shù)據(jù)處理技術,涉及數(shù)據(jù)庫技術、人工智能、機器學習、神經(jīng)網(wǎng)絡等學科。遺傳算法作為一種模擬自然進化思想的啟發(fā)式全局尋優(yōu)算法，是進化計算的杰出代表，也是機器學習的重要方法。將遺傳算法引入數(shù)據(jù)挖掘領域越來越引起學術界的重視，國外己經(jīng)有不少成功的范例。國內主要集中在遺傳算法理論與數(shù)據(jù)挖掘領域的探討上,建立了一些基本的數(shù)據(jù)挖掘問題計算模型,如在分類和關聯(lián)規(guī)則挖掘過程中采用遺傳計算技術。隨著數(shù)據(jù)挖掘應用領域的不斷拓展，將遺傳算法引入數(shù)據(jù)挖掘中，為數(shù)據(jù)挖掘提供了一個嶄新的思考模式,指出了一個新的研究方向。本文的研究工作主要源于上述背景，將遺傳算法應用于數(shù)據(jù)挖

15、掘中關聯(lián)規(guī)則的提取，并結合教師測評系統(tǒng)，將數(shù)據(jù)挖掘技術引入教育領域，實現(xiàn)了基于遺傳算法的關聯(lián)規(guī)則數(shù)據(jù)挖掘的應用實現(xiàn)。本文的主要研究內容有：l 數(shù)據(jù)挖掘技術的分析研究 在數(shù)據(jù)挖掘相關概念基礎上，對數(shù)據(jù)挖掘的目的與功能、分析方法、挖掘過程與工具、挖掘方法與技術做了詳細的歸納和總結。同時，對數(shù)據(jù)挖掘的發(fā)展和應用狀況也進行了客觀的分析。 l 關聯(lián)規(guī)則的分析研究 全面研究了關聯(lián)規(guī)則的相關知識，對其核心算法Apriori算法進行了分析；在對關聯(lián)規(guī)則的價值衡量標準進行研究的基礎上，重點探討了本文應用實例中使用到的有關興趣度的內容。 l 遺傳算法的分析研究 介紹了遺傳算法的基本概念和基本思想，分析了遺傳算法中

16、染色體編碼方案、適應度函數(shù)構造及遺傳算子的設計和改進方法，同時對遺傳算法的應用流程和算法也做了分析研究。 l 基于遺傳算法的關聯(lián)規(guī)則挖掘的應用研究 通過對數(shù)據(jù)挖掘、關聯(lián)規(guī)則和遺傳算法的分析研究，提出一種基于遺傳算法的關聯(lián)規(guī)則數(shù)據(jù)挖掘模型，并將其應用于教育領域中的教師測評系統(tǒng)，給出了該應用的實現(xiàn)技術和算法。通過實驗證明了算法的有效性和可行性，實驗效果良好。1.2數(shù)據(jù)挖掘基本概念隨著數(shù)據(jù)庫技術的不斷發(fā)展及數(shù)據(jù)庫管理系統(tǒng)的廣泛應用，數(shù)據(jù)庫中存儲的數(shù)據(jù)量急劇增大，在大量的數(shù)據(jù)背后隱藏著許多重要的信息，如果能把這些信息從數(shù)據(jù)庫中抽取出來，將創(chuàng)造很多潛在的利潤，而這種從海量數(shù)據(jù)庫中挖掘信息的技術，就稱之為

17、數(shù)據(jù)挖掘(Data Mining-DM)。數(shù)據(jù)挖掘是從一個新的角度將數(shù)據(jù)庫技術、機器學習、統(tǒng)計學等領域結合起來，從更深層次發(fā)掘存在于數(shù)據(jù)內部的、有效的、新穎的、具有潛在效應的乃至最終可理解的模式2。數(shù)據(jù)挖掘能預測未來趨勢和行為，使商務活動具有前瞻性，有助于企業(yè)做出基于知識驅動的決策。數(shù)據(jù)挖掘所提供的自動預期分析，已經(jīng)遠遠超出了由典型的決策支持系統(tǒng)工具對過去實踐所做的回顧性分析范圍。數(shù)據(jù)挖掘可以解決傳統(tǒng)上需花費很多時間解決的商務問題，它能搜索整個數(shù)據(jù)庫并查找隱藏的模式，找出那些專家可能錯過的預測信息3。理解數(shù)據(jù)挖掘需要從技術和應用兩個層面進行。從技術層面上看，數(shù)據(jù)挖掘是利用多種分析工具從海量數(shù)據(jù)

18、中發(fā)現(xiàn)模型和數(shù)據(jù)間關系的過程，其基于機器學習、統(tǒng)計學、神經(jīng)網(wǎng)絡、數(shù)據(jù)庫系統(tǒng)和信息科學等技術。從應用層面上看，數(shù)據(jù)挖掘是一個決策過程，基于多種技術，分析企業(yè)商務數(shù)據(jù)，為企業(yè)做出正確的市場預測等提供支持。數(shù)據(jù)挖掘的一般過程如圖1-1所示：圖 1-1 數(shù)據(jù)挖掘的一般過程1.3 數(shù)據(jù)挖掘中的關聯(lián)規(guī)則 關聯(lián)規(guī)則的提取是數(shù)據(jù)挖掘技術研究的一個重要課題。由于符合人類認知世界的思維模式，關聯(lián)規(guī)則的提取廣泛應用于商業(yè)、保險等行業(yè)。在實際的大型數(shù)據(jù)庫（如超級市場的交易事務數(shù)據(jù)庫）中發(fā)現(xiàn)了如“購買物品A和B的客戶中85同時也購買C和D”這樣的規(guī)則，對于分類設計、商店布局、市場分析等方面都大有幫助。目前關聯(lián)規(guī)則的挖掘

19、研究大都以這種商用事務數(shù)據(jù)庫為主要對象，其屬性域局限于布爾類型，因而也稱為布爾相關問題。而普通關系數(shù)據(jù)庫中屬性類型較為豐富，它可以包含數(shù)量屬性（如年齡、工資等）和類別屬性（如性別、教育程度等），布爾類型可以看成是類別屬性的一個特例。如何發(fā)現(xiàn)普通數(shù)據(jù)庫中各屬性之間的關聯(lián)，也稱為數(shù)量相關問題，具有更為普遍的意義，目前該方面的研究工作開始增多。本文的關聯(lián)規(guī)則挖掘就是關于數(shù)值關聯(lián)規(guī)則的挖掘。1.4數(shù)據(jù)挖掘的分析方法9數(shù)據(jù)挖掘的目的是發(fā)現(xiàn)有意義的知識以便為決策支持等具體業(yè)務提供幫助。數(shù)據(jù)挖掘的分析方法一般包括以下幾種： （1）關聯(lián)分析 關聯(lián)分析的目的是發(fā)現(xiàn)數(shù)據(jù)集中所隱含的若干項目之間的相互關系10,11

20、。比如，超市記錄了每次交易的商品清單，通過對顧客購物行為進行關聯(lián)分析，從而可以獲取各個商品在銷售上的關聯(lián)程度。關聯(lián)分析往往以關聯(lián)規(guī)則的形式表達，并以支持度、置信度等參數(shù)來描述關聯(lián)規(guī)則。 （2）數(shù)據(jù)分類 數(shù)據(jù)分類是發(fā)現(xiàn)數(shù)據(jù)集中各個對象的一般特征，并按照不同的分類模型將這些對象劃分成不同的類12-14。對數(shù)據(jù)進行分類時，假定數(shù)據(jù)集中的每個對象事先已知屬于某一個類，而分類則是生成這些類的描述。因此，分類分析需要事先對每個對象加上標記以區(qū)分出所屬的類。數(shù)據(jù)分類方法指的是或者導出區(qū)分所有類的規(guī)則集合，或者僅僅獲得某一個類區(qū)別于其它類的區(qū)分規(guī)則集合，這兩者的側重點是不同的。 （3）聚類分析 聚類是一個過程

21、，它將數(shù)據(jù)集中的對象進行分組，生成相似對象的類15,16。聚類分析是無導師的學習過程。聚類分析目的是將大量數(shù)據(jù)的對象集合分成若干個有意義的類，使得每個類的內部對象具有較高的相似程度，而不同類的對象之間具有較小的相似程度。 （4）序列模式分析 序列模式分析側重于分析數(shù)據(jù)之間的前后因果關系17,18。比如對于超市，序列模式分析可用于發(fā)現(xiàn)顧客購物模式的次序，如先購買商品X，再購買商品Y。對于股票市場，序列模式分析可用于發(fā)現(xiàn)股票價格變化的先后關系，如股票A上漲一定幅度后，股票B也將上漲一定幅度。可見，序列模式分析與關聯(lián)分析不同，關聯(lián)分析僅考慮數(shù)據(jù)間的聯(lián)系，而并不關心先后順序。在實際的決策支持等具體業(yè)務

22、過程中，則往往需要綜合應用上面的各種數(shù)據(jù)挖掘的分析方法，以便獲得更好的效果。2. 遺傳算法2.1遺傳算法的基本思想遺傳算法的基本思想可歸為兩點：第一，將物種進化的理論用于求問題的解，物種的進化又可分為遺傳和變異兩個方面；第二，只有最適合環(huán)境的物種才能保留下來，因而需經(jīng)反復求解后才可以得到最佳的解。遺傳算法按照一定的規(guī)則生成經(jīng)過基因編碼的初始群體，然后從這些代表問題的可能潛在解的初始群體出發(fā)，挑選適應度強的個體進行交叉（或稱交配、交換）和變異，以期發(fā)現(xiàn)適應度更佳的個體，如此一代代地演化，得到一個最優(yōu)個體，將其解碼，該最佳個體編碼則對應問題的最優(yōu)解或近似最優(yōu)解。遺傳算法主要由六個部分組成:染色體編

23、碼、初始群體產生方法、個體適應度評價、遺傳操作(選擇算子，交叉算子，變異算子)、算法終止條件以及遺傳參數(shù)的設置。2.2遺傳算法的構成要素（1）染色體編碼最常用的是二進制編碼，即將問題域參數(shù)空間中的一個點映射到個體的染色體上，二進制每一位即為染色體上的一個基因，字母表為0，1。對于離散型變量直接編碼，對于連續(xù)型變量先離散化后再編碼。（2）適應度函數(shù)在遺傳算法的討論中，一般希望適應度越大越好，且要求適應度非負，因此要對適應度函數(shù)進行一些變換，以適應上述的要求。（3）遺傳算子包括選擇算子、交叉算子、變異算子。選擇算子最常用的是基于適應度比例的選擇，最常用的是賭輪選擇。選擇是從種群中選擇生命力強的染色

24、體產生新種群的過程。選擇的依據(jù)是每個染色體的適應度大小。適應度越大，被選中的概率就越大，其子孫在下一代產生的個數(shù)就越多。它在很大程度上決定著遺傳算法的收斂速度和收斂效果。常用的適應度計算方法有以下兩種： 按比例的適應度計算（proportional fitness assignment）；基于排序的適應度計算（rank-based fitness assignment）； 接著，在適應度計算之后是實際的選擇，按照適應度進行父代個體的選擇。可以挑選以下的算法： 賭輪盤選擇（roulette wheel selection）；隨機遍歷抽樣（stochastic universal sampling

25、）；局部選擇（local selection）；截斷選擇（truncation selection）；錦標賽選擇（tournament selection）。交叉算子又稱重組(recombination) 、配對(breeding)算子。當許多染色體相同或后代的染色體與上一代沒有多大差別時，就利用交叉算子來產生新一代染色體，所以交叉算子可以產生新的個體。染色體交叉分兩個步驟進行：首先，在新復制的群體中隨機選取兩個染色體，每個染色體由多個位(基因)組成；然后，沿著這兩個染色體的基因隨機取一個位置，二者互換從該位置起至末尾的部分基因。 根據(jù)交叉點的數(shù)目不同，可以將交叉分為單點交叉和兩點交叉。在單點

26、交叉中，交叉點之后的所有字符全部參加交換。在兩點交叉中，只有兩個交叉點之間的字符才參加交換。進一步推廣，也可以進行多點交叉。在這里，我們介紹一下單點交叉的作用過程： 首先產生一個在1到L-1之間的整型隨機數(shù)i；然后配對的兩個串相互交換從i+1到L的對應位段。假設從交配池中選擇編號為1和2的兩個串為配對串，且交叉點選在2，則交叉算子作用的結果為: 遺傳算法的有效性主要來自選擇和交叉操作，尤其是交叉操作，在遺傳算法中起著核心作用。變異就是以很小的概率，隨機改變字符串某個位置上的值。在二進制編碼中，就是將0變成1，將1變成0，它本身是一種隨機搜索，但與選擇、交叉算子結合在一起，在保證遺傳算法的有效性

27、和局部隨機搜索能力的同時，使遺傳算法保持種群的多樣性，以防止出現(xiàn)未成熟而過早收斂。2.3設置控制參數(shù)遺傳算法是一種弱方法，對所要求解決的問題數(shù)學要求不是太高，但它卻要求人們在使用該方法時，事先確定若干個控制參數(shù)，這些參數(shù)的選擇對遺傳算法的性能和效率的影響都比較大。其中，主要的控制參數(shù)有以下幾種：（1）編碼串的長度 L: 編碼長度 L 與所用的編碼方法有關。本文使用實數(shù)數(shù)組的編碼方案，編碼長度等于數(shù)據(jù)庫中我們希望得到的相關字段的個數(shù)。根據(jù)上述分析，本例中編碼長度為 10。 （2）群體規(guī)模：如果群體規(guī)模大，可提供大量模式，使遺傳算法進行啟發(fā)式搜索，防止早熟發(fā)生，但會降低效率；如果群體規(guī)模小，可提高

28、速度，但卻會降低效率。一般取值范圍在20100之間。（3）遺傳算法的終止進化代數(shù)：一般取100500。 （4）交叉率（Pc）：在每次迭代中，要求有Pc×N個個體進行交叉操作。它影響著交叉算子的使用頻率，交叉率越高，可以越快地收斂到全局最優(yōu)解，因此一般選擇較大的交叉率。一般取值范圍在0.40.9之間。 （5）變異率（Pm）：在每次迭代中，群體中每個個體的任一位置的基因按變異率隨機改變，大約發(fā)生Pm次變異操作。變異率控制著變異算子的使用頻率，它的大小將影響群體的多樣性及成熟前的收斂性能。變異率的選取一般受種群大小、染色體長度等因素影響，通常選取很小的值。2.4遺傳算法的框架算法過程：(1

29、)隨機產生一個由確定長度的特征串組成的初始化群體。(2)對串群體迭代進行下面的（i）和（ii），知道滿足停止準則：（i）計算群體中每個個體的適應值；（ii）應用選擇、交叉、變異算子產生下一代群體。(3)把在任一代中出現(xiàn)的最好個體串指定為遺傳算法的執(zhí)行結果，這個結果可以表示問題的一個解（或近似解）。圖2-1 遺傳算法的過程3. 遺傳算法與數(shù)據(jù)挖掘遺傳算法是數(shù)據(jù)挖掘的主要算法之一。遺傳算法作為一種有效的全面并行優(yōu)化搜索工具,早被眾多應用領域所接受,在數(shù)據(jù)挖掘方面的應用也得到了極高的重視。遺傳算法應用于決策樹、分類器、模糊規(guī)則獲取等方面的文獻不斷涌現(xiàn)，是數(shù)據(jù)挖掘領域的一個重要研究課題4。 遺傳算法以

30、其解決問題的混沌、隨機和非線性為典型特征，它為其它科學技術無法解決或難以解決的復雜問題提供了新的計算模型。對于數(shù)據(jù)嘈雜無序的特征，遺傳算法是有效解決此類問題的方法之一5。許多知識發(fā)現(xiàn)的問題可以看成是搜索問題，數(shù)據(jù)庫可以看作是搜索空間，發(fā)現(xiàn)算法可以看作是搜索策略，而遺傳算法是模擬自然進化的全局搜索算法。應用遺傳算法在數(shù)據(jù)庫中進行搜索，對隨機產生的一組規(guī)則進行進化，直到數(shù)據(jù)庫能夠被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。遺傳算法避免了搜索過程中的局部最優(yōu)解，用在規(guī)則發(fā)現(xiàn)方面有希望發(fā)現(xiàn)真正有用的規(guī)則。4. 基于遺傳算法的數(shù)據(jù)挖掘4.1利用遺傳算法進行關聯(lián)規(guī)則挖掘基于遺傳算法的方法是運用遺傳算法

31、的自適應尋優(yōu)及智能搜索技術，獲取與客觀事實最相容的問題解，即使用遺傳算法進行了關聯(lián)規(guī)則的挖掘38。 目前，廣泛使用的關聯(lián)規(guī)則挖掘算法是Aprior算法或其改進算法。這些算法的基本思想是將關聯(lián)規(guī)則的挖掘分解為兩步：首先找到所有支持度大于用戶最小支持度的項集，這些項集稱為頻集；然后從找到的頻集中構造其可信度大于用戶最小可信度的關聯(lián)規(guī)則。算法思想的核心問題是找到頻集，這個過程其實是一個全局搜索的過程，而遺傳算法就是一種全局優(yōu)化算法，它可以有效地避免搜索過程的局部最優(yōu)解。因此，將遺傳算法用于關聯(lián)規(guī)則的發(fā)現(xiàn)和提取方面能夠找到有價值的規(guī)則。例如，Sunil已經(jīng)成功地開發(fā)了一個基于遺傳算法的知識發(fā)現(xiàn)工具，結

32、果表明遺傳算法是進行知識發(fā)現(xiàn)的有效方法之一。4.2 規(guī)則的提取與評價 根據(jù)適應度函數(shù)和遺傳算子選擇出的規(guī)則所表示出的是所有具有關聯(lián)的屬性，但是無法分辨出規(guī)則是如何關聯(lián)的。比如，挖掘出0152003這樣一條規(guī)則，我們只能知道 1523 這幾個屬性是關聯(lián)的，但究竟是如何關聯(lián)的，可能是 15=>23，也可能是 152=>3，還可能是 23=>15 等等。這一條規(guī)則中共包含了 24 條關聯(lián)規(guī)則，但未必每一條都符合可信度的要求，并且都是用戶感興趣的規(guī)則。所以，必須對所挖掘出來的規(guī)則進行提取，找出符合要求和用戶感興趣的關聯(lián)規(guī)則。本文的提取標準是：滿足用戶給定的可信度和興趣度要求的規(guī)則才輸

33、出，否則舍去。 規(guī)則提取算法步驟如下： （1）從侯選集中取出一條侯選規(guī)則； （2）計算該規(guī)則的可信度 C和興趣度 I； （3）if C> C then 計算該規(guī)則的興趣度 I； if I>I then 輸出該規(guī)則； 轉到（4）； else if I<- I then 輸出該規(guī)則的反面規(guī)則； 轉到（4）； else 轉到（4）； （4）如果侯選集為空，則結束提取，否則轉到（1）。5. 應用實例分析5.1實例中變量設計通過采用一所大學的學生信息的數(shù)據(jù)集對基于AGA算法的挖掘結果和基于簡單遺傳算法的挖掘性能進行了測試。模型系統(tǒng)中的變量如表5-1所示:其中特征屬性Depart一cod

34、e的取值域為jsjkx、jsjtx、zdh、xxaq,分別代表計算機科學與技術專業(yè)、計算機通訊專業(yè)、自動化專業(yè)、信息安全專業(yè);特征屬性Gender的取值域為male、female;特征屬性Mtermrate的取值域為A、B、C、D;特征屬性Coursetype的取值域為required、。ptionnal;特征屬性coursedif經(jīng)過離散化處理后的取值域為easy、midd、diff、vdiff;特征屬性flunkratio經(jīng)過離散化處理后的取值域為no、low、high、vhigh;類別屬性的取值范圍為vgood、good、paSS、faiz;5.2關聯(lián)規(guī)則挖掘結果取群體初始規(guī)模為100,

35、適應度函數(shù):F(r)= a*S(r)+b*A(r)+c*C(r),其中a=b=c=l。對1000個數(shù)據(jù)記錄實施AGA算法,挖掘結果如表所示。表5-2中每條規(guī)則后賦有相應的適應度值、支持度、置信度和覆蓋度。5.3與簡單遺傳算法(SGA)的性能比較簡單遺傳算法(SGA)采用賭輪方式選擇交配組，即根據(jù)個體的適應度與平均適應度的比例來確定該個體的復制比例。通常SGA算法中的交叉操作,是隨機取兩個染色體進行單點交叉操作。在SGA算法中適應函數(shù)為:F(r)=aS(r)+bA(r)+cC(r),其中:r為規(guī)則變量;a,b,c為常數(shù)且0a,b,c1;S(r)為規(guī)則支持度;A(r)為規(guī)則的可信度;C(r)為規(guī)則

36、的覆蓋度。a,b,c的值由用戶根據(jù)需要調整,使進化沿著用戶期望的方向進。SGA中參數(shù)設置如下表5-3所示：在遺傳代數(shù)100/200/300/400/500的情況,對提出的AGA算法與傳統(tǒng)的簡單遺傳算法在平均出錯率方面進行了對比,實驗結果如圖5-3示:圖5-3 AGA性能測試圖由圖5-3可以看出,由于AGA算法是在Apriori算法的基礎上進行的,在遺傳代數(shù)較小的情況下,出錯率要比簡單遺傳算法小得多,隨著遺傳代數(shù)的增大,平均出錯次數(shù)也會線性減少,但減少率明顯下降。如圖5-3中遺傳代數(shù)為50,100時,執(zhí)行AGA算法的出錯率比執(zhí)行一般遺傳算法所產生的出錯次數(shù)要小得多。當遺傳代數(shù)較大時,基于Apri

37、ori算法的初始化結果對搜索的加速作用會變得越來越小。當遺傳代數(shù)大到一定程度時,基于Apriori初始化結果相當于一組隨機的規(guī)則,AGA算法轉變成簡單遺傳算法。由圖5-3可以看出隨著遺傳代數(shù)的增加,執(zhí)行AGA算法所產生的平均出錯次數(shù)越來越接近執(zhí)行簡單遺傳算法,這說明AGA算法適用于遺傳代數(shù)較小的情況。但由于一般情況下遺傳代數(shù)比較少,因此該算法具有實用性。6. 總結本文講述的是數(shù)據(jù)挖掘中關聯(lián)規(guī)則的挖掘。針對于傳統(tǒng)關聯(lián)規(guī)則的數(shù)據(jù)挖掘算法中只考慮支持度和置信度所存在的問題，將基于差異的興趣度引入到關聯(lián)規(guī)則的提取和評價中，過濾掉一些常規(guī)的、實用價值不是很高的規(guī)則，真正挖掘出用戶感興趣的、實用價值高的規(guī)

38、則。目前，興趣度的研究是數(shù)據(jù)挖掘中關聯(lián)規(guī)則挖掘的一個重要方向。 本文采用遺傳算法進行數(shù)據(jù)挖掘中關聯(lián)規(guī)則的挖掘。文中詳細討論了遺傳算法在關聯(lián)規(guī)則提取方面的應用，針對于事務型數(shù)據(jù)庫的特點，提出了使用實數(shù)數(shù)組的編碼方法，并在此基礎上，討論了適應度函數(shù)的構造，對選擇、交叉和變異算子進行了改進，最后通過一個高職學院外聘教師基本信息與測評結果關聯(lián)規(guī)則挖掘的實例給出了算法的具體實現(xiàn)，不僅驗證了算法的有效性和可行性，而且對數(shù)據(jù)挖掘技術在教育領域的應用進行了初步的嘗試。參考文獻1朱明，數(shù)據(jù)挖掘M，中國科技大學出版社2002 2林杰斌，劉明德，陳湘，數(shù)據(jù)挖掘與OLAP理論與實務M，清華大學出版社2003 3鐘曉，馬少平，張鈸等，數(shù)據(jù)挖掘綜述，模式識別與人工智能，2001，14(1)：4855 4許國艷，史宇清，遺傳算法在關聯(lián)規(guī)則挖掘中的應用，計算機工程，2002，28（7）：122124 5 D.E Goldberg，Genetic Algorithms and Walsh Functions：Part ，Deception and its Analysis，Complex Systems 1989 vol(3)：153171 6J.Han，J.pei，ect. Frequent pattern projected sequential pattern miningIn