遺傳算法在數(shù)據(jù)挖掘中的研究與應(yīng)用

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

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

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

4、(4)對(duì)提出的基于遺傳算法與關(guān)聯(lián)規(guī)則算法相結(jié)合的混合分類方法進(jìn)行了全面的分析。關(guān)鍵詞 遺傳算法；數(shù)據(jù)挖掘；分類；關(guān)聯(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ù)挖掘的產(chǎn)生和研究目標(biāo)近年來隨著數(shù)據(jù)庫技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)的廣泛應(yīng)用，加上使用先進(jìn)的自動(dòng)數(shù)據(jù)生成和采集工具，人們所擁有的數(shù)據(jù)量急劇增大。激增的數(shù)據(jù)背后隱藏著許多重要的信息，如何從大量的數(shù)據(jù)中提取并找到有用的信息以指導(dǎo)決策，是迫切需要解決的問題。在這種情況下，數(shù)據(jù)挖掘1新型的數(shù)據(jù)分析技術(shù)于 1995 年誕生了。目前，數(shù)據(jù)挖掘的研究重點(diǎn)轉(zhuǎn)向多種發(fā)現(xiàn)策略和技術(shù)的集成，以及多種學(xué)科之間的相互滲透。其他內(nèi)容的專題會(huì)議也把數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)列為議題之一，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、e的取值域?yàn)閖sjkx、jsjtx、zdh、xxaq,分別代表計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、計(jì)算機(jī)通訊專業(yè)、自動(dòng)化專業(yè)、信息安全專業(yè);特征屬性Gender的取值域?yàn)閙ale、female;特征屬性Mtermrate的取值域?yàn)锳、B、C、D;特征屬性Coursetype的取值域?yàn)閞equired、。ptionnal;特征屬性coursedif經(jīng)過離散化處理后的取值域?yàn)閑asy、midd、diff、vdiff;特征屬性flunkratio經(jīng)過離散化處理后的取值域?yàn)閚o、low、high、vhigh;類別屬性的取值范圍為vgood、good、paSS、faiz;5.2關(guān)聯(lián)規(guī)則挖掘結(jié)果取群體初始規(guī)模為100,

35、適應(yīng)度函數(shù):F(r)= a*S(r)+b*A(r)+c*C(r),其中a=b=c=l。對(duì)1000個(gè)數(shù)據(jù)記錄實(shí)施AGA算法,挖掘結(jié)果如表所示。表5-2中每條規(guī)則后賦有相應(yīng)的適應(yīng)度值、支持度、置信度和覆蓋度。5.3與簡(jiǎn)單遺傳算法(SGA)的性能比較簡(jiǎn)單遺傳算法(SGA)采用賭輪方式選擇交配組，即根據(jù)個(gè)體的適應(yīng)度與平均適應(yīng)度的比例來確定該個(gè)體的復(fù)制比例。通常SGA算法中的交叉操作,是隨機(jī)取兩個(gè)染色體進(jìn)行單點(diǎn)交叉操作。在SGA算法中適應(yīng)函數(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ù)需要調(diào)整,使進(jìn)化沿著用戶期望的方向進(jìn)。SGA中參數(shù)設(shè)置如下表5-3所示：在遺傳代數(shù)100/200/300/400/500的情況,對(duì)提出的AGA算法與傳統(tǒng)的簡(jiǎn)單遺傳算法在平均出錯(cuò)率方面進(jìn)行了對(duì)比,實(shí)驗(yàn)結(jié)果如圖5-3示:圖5-3 AGA性能測(cè)試圖由圖5-3可以看出,由于AGA算法是在Apriori算法的基礎(chǔ)上進(jìn)行的,在遺傳代數(shù)較小的情況下,出錯(cuò)率要比簡(jiǎn)單遺傳算法小得多,隨著遺傳代數(shù)的增大,平均出錯(cuò)次數(shù)也會(huì)線性減少,但減少率明顯下降。如圖5-3中遺傳代數(shù)為50,100時(shí),執(zhí)行AGA算法的出錯(cuò)率比執(zhí)行一般遺傳算法所產(chǎn)生的出錯(cuò)次數(shù)要小得多。當(dāng)遺傳代數(shù)較大時(shí),基于Apri

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

38、則。目前，興趣度的研究是數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘的一個(gè)重要方向。 本文采用遺傳算法進(jìn)行數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的挖掘。文中詳細(xì)討論了遺傳算法在關(guān)聯(lián)規(guī)則提取方面的應(yīng)用，針對(duì)于事務(wù)型數(shù)據(jù)庫的特點(diǎn)，提出了使用實(shí)數(shù)數(shù)組的編碼方法，并在此基礎(chǔ)上，討論了適應(yīng)度函數(shù)的構(gòu)造，對(duì)選擇、交叉和變異算子進(jìn)行了改進(jìn)，最后通過一個(gè)高職學(xué)院外聘教師基本信息與測(cè)評(píng)結(jié)果關(guān)聯(lián)規(guī)則挖掘的實(shí)例給出了算法的具體實(shí)現(xiàn)，不僅驗(yàn)證了算法的有效性和可行性，而且對(duì)數(shù)據(jù)挖掘技術(shù)在教育領(lǐng)域的應(yīng)用進(jìn)行了初步的嘗試。參考文獻(xiàn)1朱明，數(shù)據(jù)挖掘M，中國(guó)科技大學(xué)出版社2002 2林杰斌，劉明德，陳湘，數(shù)據(jù)挖掘與OLAP理論與實(shí)務(wù)M，清華大學(xué)出版社2003 3鐘曉，馬少平，張鈸等，數(shù)據(jù)挖掘綜述，模式識(shí)別與人工智能，2001，14(1)：4855 4許國(guó)艷，史宇清，遺傳算法在關(guān)聯(lián)規(guī)則挖掘中的應(yīng)用，計(jì)算機(jī)工程，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