【碩士論文】基于遺傳算法的分類規(guī)則挖掘研究.pdf

《【碩士論文】基于遺傳算法的分類規(guī)則挖掘研究.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、摘要數(shù)據(jù)挖掘是近年來興起的一個新的研究領(lǐng)域。它涉及多學(xué)科技術(shù)的集成，包括數(shù)據(jù)庫和數(shù)據(jù)倉庫技術(shù)、統(tǒng)計學(xué)、機(jī)器學(xué)習(xí)、人工智能等，目標(biāo)是從大量的數(shù)據(jù)資料中發(fā)現(xiàn)隱藏的有價值的信息和知識，以便為科學(xué)決策提供支持。分類規(guī)則挖掘則是通過對訓(xùn)練樣本數(shù)據(jù)集的學(xué)習(xí)，構(gòu)造分類規(guī)則的過程，是數(shù)據(jù)挖掘、知識發(fā)現(xiàn)的一個重要方面，其實質(zhì)是希望得到準(zhǔn)確性高、易于理解的和有趣的分類規(guī)則。論文介紹了數(shù)據(jù)挖掘的基本理論以及遺傳算法的基本原理，在此基礎(chǔ)上，重點(diǎn)研究了遺傳算法在分類規(guī)則挖掘中的應(yīng)用問題。為了克服簡單遺傳算法“早熟”收斂的問題，引入了“非隨機(jī)

2、初始種群"和“均勻算子’’思想，提出基于非隨機(jī)初始種群遺傳算法的分類規(guī)則挖掘算法，并利用乳腺癌和皮膚病數(shù)據(jù)集對其進(jìn)行了算法測試。根據(jù)實際應(yīng)用的需要，用多目標(biāo)遺傳算法改進(jìn)基本遺傳算法在分類規(guī)則挖掘中的應(yīng)用，提出基于多目標(biāo)遺傳算法的分類規(guī)則挖掘算法，并利用adult數(shù)據(jù)集和ZOO數(shù)據(jù)集對其進(jìn)行了算法測試。試驗結(jié)果表明，所用算法能消除遺傳算法在分類挖掘任務(wù)中收斂于局部最優(yōu)的局限性，且能快速挖掘出易于理解的分類規(guī)則，提高對知識的理解力。關(guān)鍵詞：數(shù)據(jù)挖掘；遺傳算法；分類規(guī)則；均勻算子；多目標(biāo)遺傳算法第一章緒論第一章緒論1．1

3、課題背景近年來，隨著數(shù)據(jù)庫技術(shù)和計算機(jī)網(wǎng)絡(luò)的廣泛應(yīng)用和發(fā)展，人類使用先進(jìn)的自動數(shù)據(jù)生成和采集工具，擁有的數(shù)據(jù)量急劇增大。在這些大量的數(shù)據(jù)背后隱藏著許多重要的信息，不同領(lǐng)域的人們都期待著從這些數(shù)據(jù)中得到自己想要的答案，將信息變?yōu)橛杏玫闹R，從雜亂無章的數(shù)據(jù)“礦山”中找到蘊(yùn)藏的知識“金塊”。但是，傳統(tǒng)的方法很難對數(shù)據(jù)進(jìn)行深層次的分析和處理，它不僅費(fèi)時費(fèi)力，而且效果往往很難令人滿意。因此，出現(xiàn)了一門新的技術(shù)：數(shù)據(jù)挖掘技術(shù)11】。數(shù)據(jù)挖掘(DataMining)是計算機(jī)科學(xué)中的一個重要研究領(lǐng)域，其目標(biāo)是從數(shù)據(jù)中抽取知識12

4、J。目前，該技術(shù)被越來越多的領(lǐng)域所采用并取得了一定的成效，達(dá)到了在一定程度上為人們的正確決策提供輔助的目的。分類規(guī)則是數(shù)據(jù)挖掘的主要研究內(nèi)容之一，通過分析訓(xùn)練集數(shù)據(jù)，產(chǎn)生關(guān)于類別的精確描述131。這種類別描述常由分類規(guī)則組成，可以用來對未來的數(shù)據(jù)進(jìn)行分類預(yù)測，有著廣泛的應(yīng)用前景。實際上，分類是一個兩步的過程。第一步，通過分析訓(xùn)練集建立一個模型，描述指定的數(shù)據(jù)類集或概念集；第二步，評估模型的預(yù)測準(zhǔn)確率，如果模型的準(zhǔn)確率可以接受，就可以使用模型進(jìn)行分類了。對于分類規(guī)則的挖掘，目前主要有以下方法：決策樹方法、貝葉斯方法、

5、人工神經(jīng)網(wǎng)絡(luò)方法、遺傳算法以及粗糙集方法等，不同的算法適合于不同特征的數(shù)據(jù)集。遺傳算法(GeneticAlgorithms，GA)是模仿自然界生物遺傳進(jìn)化過程中“物競天澤、適者生存”原理的一種全局優(yōu)化隨機(jī)搜索算法，是由美國J．Holland教授于1975年在其論文“自然系統(tǒng)和人工系統(tǒng)的適配”中提出的、具有應(yīng)用廣泛、使用簡單、魯棒性強(qiáng)等特點(diǎn)的方法【4】【51。它借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、交叉、變異等遺傳操作，一代代不斷繁殖進(jìn)化，最后收斂到一批最適應(yīng)環(huán)境的個體上，從而求得最優(yōu)分類規(guī)則剿6。。但是，傳統(tǒng)遺傳算

6、法存在著易于陷入局部最優(yōu)而達(dá)不到全局最優(yōu)，致使得到的分類規(guī)則概括性不強(qiáng)的問題。為了提高分類規(guī)則挖掘效率、準(zhǔn)確性和易理解性，許多研究人員將簡單遺傳算法運(yùn)用到分類規(guī)則挖掘中去，并取得了一些成果。但是，總存在“早熟”收斂和局部最優(yōu)等問題。本論文提出的基于非隨機(jī)初始種群遺傳算法的分類規(guī)則挖掘算法能夠有效地解決上述問題，提高分類規(guī)則挖掘的效率和準(zhǔn)確性。1．2研究現(xiàn)狀分類挖掘有多種方法，常用的有決策樹歸納分類、貝葉斯分類、神經(jīng)網(wǎng)絡(luò)分類、1青島大學(xué)碩士學(xué)位論文基于遺傳算法的分類、粗糙集方法分類和模糊集方法分類等。決策樹(Deci

7、sionTree)歸納是從具有類標(biāo)號的訓(xùn)練元組學(xué)習(xí)決策樹。決策樹是一種類似于流程圖的樹結(jié)構(gòu)，其中，每個內(nèi)部節(jié)點(diǎn)表示在一個屬性上的測試，每個分支代表一個測試輸出，而每個葉節(jié)點(diǎn)存放一個類標(biāo)號，樹的最頂層節(jié)點(diǎn)為根節(jié)點(diǎn)。有些決策樹算法只能產(chǎn)生二叉樹，而另外一些決策樹算法可以產(chǎn)生非二叉樹。在20世紀(jì)70年代后期和80年代初期，機(jī)器學(xué)習(xí)研究者J．RossQuinlan開發(fā)了決策樹算法，稱作ID3(IterativeDichotomiscr，迭代的二分器)。這項工作擴(kuò)展了E．B．Hunt，J．Marin和P．T．Stonc的概念

8、學(xué)習(xí)系統(tǒng)。1984年幾位統(tǒng)計學(xué)家(LBrciman，J．Friedman，R．Olshen和C．Stone)出版了分類與回歸樹一書(CART,ClassficationandRegressionTrees)，介紹了二叉決策樹的產(chǎn)生。ID3和CART大約同時分別發(fā)明，但是從訓(xùn)練元組學(xué)習(xí)決策樹卻采用了類似的方法。這兩個基礎(chǔ)算法激發(fā)了決策樹歸納研究的熱潮。1993