基于非隨機(jī)初始種群遺傳算法的分類規(guī)則挖掘

《基于非隨機(jī)初始種群遺傳算法的分類規(guī)則挖掘》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第9卷第2期2009年1月科學(xué)技術(shù)與工程Vo1．9No．2Jan．20091671—1819(2009)2-0283—06ScienceTechnologyandEngineering@2009Sci．Tech．Engng．基于非隨機(jī)初始種群遺傳算法的分類規(guī)則挖掘阮家港馬金平呂曉慧(青島大學(xué)國(guó)際商學(xué)院，青島266071)摘要數(shù)據(jù)挖掘中分類問題一直是數(shù)據(jù)挖掘領(lǐng)域中研究的熱點(diǎn)問題，先后提出了各種分類算法；其中遺傳算法被認(rèn)為是一種高效的分類算法。但是，傳統(tǒng)的GA存在著易于陷入局部最優(yōu)，致使得到的分類規(guī)則概括性不強(qiáng)的問題。提出了一種基于非隨機(jī)初始種群的遺傳算法分類規(guī)則挖掘算法。算法利用均勻種群方

2、法生成非隨機(jī)的初始種群，并通過均勻算子確保連續(xù)迭代過程中種群的多樣性，從而達(dá)到防止GA早熟的目的。采用兩個(gè)標(biāo)準(zhǔn)的公共領(lǐng)域的數(shù)據(jù)集驗(yàn)證了算法的有效性。實(shí)驗(yàn)結(jié)果表明，該算法能消除遺傳算法在分類挖掘任務(wù)中收斂于局部最優(yōu)的局限性，且能快速挖掘出易于理解的分類規(guī)則，提高對(duì)知識(shí)的理解力。關(guān)鍵詞數(shù)據(jù)挖掘分類規(guī)則遺傳算法均勻種群中圖法分類號(hào)TP301．6；文獻(xiàn)標(biāo)志碼A數(shù)據(jù)挖掘(DataMining)是計(jì)算機(jī)科學(xué)中的一得最優(yōu)分類規(guī)則集]。但是，傳統(tǒng)遺傳算法存在著個(gè)重要研究領(lǐng)域，其目標(biāo)是從數(shù)據(jù)中抽取知識(shí)．2J。易于陷入局部最優(yōu)而達(dá)不到全局最優(yōu)，致使得到的分類規(guī)則是數(shù)據(jù)挖掘的主要研究?jī)?nèi)容之一，通過分分類規(guī)則概

3、括性不強(qiáng)的問題。析訓(xùn)練集數(shù)據(jù)，產(chǎn)生關(guān)于類別的精確描述。這種本文提出了一種基于非隨機(jī)初始種群的遺傳類別描述常由分類規(guī)則組成，可以用來對(duì)未來的數(shù)算法分類規(guī)則挖掘算法。利用均勻種群方法生成據(jù)進(jìn)行分類預(yù)測(cè)，有著廣泛的應(yīng)用前景。非隨機(jī)的初始種群，通過均勻算子確保連續(xù)迭代過分類規(guī)則的挖掘目前主要有以下方法：決策樹程中種群的多樣性并防止遺傳算法的早熟，挖掘易方法、貝葉斯方法、人工神經(jīng)網(wǎng)絡(luò)方法、粗糙集方法于理解的分類規(guī)則，提高規(guī)則的簡(jiǎn)單性和對(duì)知識(shí)的等。這些方法追求的是較高的分類正確率，但往往理解力。不能抽取出使人易于理解的分類規(guī)則HJ。遺傳算法是一種基于生物進(jìn)化論和分子遺傳學(xué)的全局隨1基于非隨機(jī)初始種群

4、GA分類規(guī)則挖掘機(jī)搜索算法，具有應(yīng)用廣泛、使用簡(jiǎn)單、魯棒性強(qiáng)等算法特點(diǎn)。遺傳算法在分類中應(yīng)用的基本思想是將分類規(guī)則按某種形式進(jìn)行編碼，形成染色體。再隨機(jī)1．1染色體編碼選取N個(gè)染色體構(gòu)成初始種群，然后根據(jù)預(yù)定的評(píng)一條分類規(guī)則可以看作是由合取范式構(gòu)成的價(jià)函數(shù)對(duì)每個(gè)染色體計(jì)算適應(yīng)值。通過遺傳操作邏輯公式，規(guī)則左部的每個(gè)合取項(xiàng)對(duì)應(yīng)一個(gè)特征屬(選擇、交叉、變異)來產(chǎn)生一群新的更適應(yīng)環(huán)境的性，一個(gè)合取項(xiàng)又可由表示概念的析取式組成，表染色體，形成新的種群。這樣一代代不斷繁殖進(jìn)示特征屬性的不同取值；規(guī)則的右部表示滿足規(guī)則化，最后收斂到一批最適應(yīng)環(huán)境的個(gè)體上，從而求左部合取式的實(shí)例應(yīng)歸屬的類別。如IF(

5、buying=vhighorhigh)AND(maint=vhighorhigh)THEN2008年l0月7日收到unacceptable就是一條由2個(gè)合取項(xiàng)包含了內(nèi)部析第一作者簡(jiǎn)介：阮家港(1980一)，男，青島大學(xué)管理科學(xué)與工程系取式組成的分類規(guī)則，其中buying和maint為特征碩士研究生。E—mail：ruanjiashuai@sina．corn。屬性，分別表示汽車的購(gòu)買價(jià)格和維修價(jià)格；unac—284科學(xué)技術(shù)與工程8卷ceptable為類標(biāo)號(hào)屬性，表示不可接受。設(shè)凡是所挖的基因集(盡可能等長(zhǎng))，如圖2所示。掘數(shù)據(jù)中類標(biāo)號(hào)屬性的個(gè)數(shù)。則一個(gè)染色體由n個(gè)C可以看作是C。的補(bǔ)集，其

6、它的染色體基于基因組成，其中每個(gè)基因?qū)?yīng)于一個(gè)特征屬性。第iC。和c產(chǎn)生。本文以二進(jìn)制編碼的形式為例來解個(gè)基因劃分成三個(gè)部分：標(biāo)記(F)，關(guān)系算子(RO)釋該方法，此法同樣適用與其它的編碼形式。在均和屬性值(vi)，如圖1所示。染色體表示一條規(guī)則勻種群方法中，從一個(gè)隨機(jī)產(chǎn)染色體中產(chǎn)生2一1的整個(gè)IF語句部分并不包含此規(guī)則所預(yù)測(cè)的類標(biāo)個(gè)新的染色體。因此，如果種群規(guī)模固定，將以系號(hào)屬性。在GA每一次迭代中，算法搜索具有同一統(tǒng)的方法產(chǎn)生2一2個(gè)新的染色體。設(shè)IPI是固定類標(biāo)號(hào)的所有染色體。因此，對(duì)于每一個(gè)預(yù)測(cè)類標(biāo)的種群規(guī)模數(shù)，最大的r值要使不等式2≤lPl成號(hào)GA至少運(yùn)行一次。立。然后讓r以1

7、遞減從而根據(jù)新的r值產(chǎn)生出標(biāo)記字段(F)是區(qū)間范圍內(nèi)的一個(gè)二進(jìn)制值2一2個(gè)新的染色體。依此類推直至新的r值遞減變量，表示其對(duì)應(yīng)的屬性是否在規(guī)則中為2。在以上過程中，產(chǎn)生染色體的總數(shù)會(huì)大于種出現(xiàn)，1表示該屬性出現(xiàn)，0表示不出現(xiàn)。盡管群規(guī)模數(shù)，在此情況下，我們僅選擇它們中的部分每個(gè)染色體有一個(gè)固定的長(zhǎng)度，以這種方式表示的染色體來確保固定的種群規(guī)模數(shù)?；虼馕吨?guī)則長(zhǎng)度可變。因此，不同的染色體為簡(jiǎn)便起見，取lP}=54，新染色體的產(chǎn)生過