基于混合遺傳算法的分類規(guī)則挖掘方法及其并行實(shí)現(xiàn).pdf

1、數(shù)據(jù)分類是按照一組數(shù)據(jù)對(duì)象的特征給出數(shù)據(jù)對(duì)象數(shù)學(xué)劃分的過程，已經(jīng)在統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)以及專家系統(tǒng)中被廣泛研究。近來，它又成為數(shù)據(jù)挖掘的一個(gè)重要研究方面。實(shí)際上，分類是一個(gè)兩步過程，第一步，建立一個(gè)模型，描述指定的數(shù)據(jù)類集或概念集；第二步，評(píng)估模型的預(yù)測(cè)準(zhǔn)確率，如果模型的準(zhǔn)確率可以接受，使用模型進(jìn)行分類。通常，模型可以用分類規(guī)則、判定樹或數(shù)學(xué)公式表示。目前常用的分類規(guī)則挖掘方法有遺傳算法、決策樹方法、神經(jīng)網(wǎng)絡(luò)等?；趥鹘y(tǒng)遺傳算法的

2、分類規(guī)則挖掘方法通常存在以下問題：(1)對(duì)每個(gè)類只能產(chǎn)生一條分類規(guī)則；(2)挖掘出的規(guī)則質(zhì)量不高；(3)優(yōu)化后種群中冗余規(guī)則太多；(4)分類準(zhǔn)確率不高。本文提出的基于混合遺傳算法的分類規(guī)則挖掘方法能夠有效克服上述缺點(diǎn)，提高分類規(guī)則挖掘的準(zhǔn)確性。 本文首先介紹了數(shù)據(jù)挖掘的產(chǎn)生背景、定義和功能，指出預(yù)測(cè)準(zhǔn)確度、計(jì)算復(fù)雜度和模型描述的簡(jiǎn)潔度是評(píng)價(jià)分類模型的三個(gè)尺度，并對(duì)一些常用的分類規(guī)則挖掘方法進(jìn)行了分析和比較。 介紹了遺傳算

3、法和局部搜索算法的基本原理，并分析了遺傳算法和局部搜索算法的優(yōu)缺點(diǎn)。遺傳算法雖然具有很強(qiáng)的全局搜索能力但局部搜索能力較差，另一方面，局部搜索算法具有較強(qiáng)的局部搜索能力，因此可以將兩種算法相結(jié)合，構(gòu)成混合遺傳算法。 分析了分類規(guī)則挖掘原理，指出標(biāo)準(zhǔn)遺傳算法并不太適合分類問題，因此提出了一種基于混合遺傳算法的分類規(guī)則挖掘方法?；旌线z傳算法采用了Michigan方法，每個(gè)染色體代表一條分類規(guī)則。為了使混合遺傳算法能夠產(chǎn)生多條高質(zhì)量的規(guī)

4、則，設(shè)計(jì)了針對(duì)分類問題的編碼方案、適應(yīng)度函數(shù)、個(gè)體生成函數(shù)、遺傳算子和局部搜索算子，并在適應(yīng)度函數(shù)中提出了簡(jiǎn)潔度因子。另外，在優(yōu)化后的種群中存在一些冗余規(guī)則，考慮到規(guī)則集的簡(jiǎn)潔性，提出了一種規(guī)則提取方法。實(shí)驗(yàn)表明，基于混合遺傳算法的分類規(guī)則挖掘方法能夠從數(shù)據(jù)集中發(fā)現(xiàn)一個(gè)簡(jiǎn)潔、準(zhǔn)確、易理解的規(guī)則集。 最后，分析了分類算法的并行性，并在基于Windows2000的PVM并行計(jì)算平臺(tái)上實(shí)現(xiàn)了并行分類算法。此算法采用粗粒度的主/從模型，