摘 要：傳統(tǒng)的遺傳算法存在早熟收斂和易于陷入局部搜索最優(yōu)等缺陷；根據(jù)關(guān)聯(lián)規(guī)則挖掘的要求和特點(diǎn)，提出一種應(yīng)用于關(guān)聯(lián)規(guī)則挖掘的自適應(yīng)小生境遺傳算法。
　　關(guān)鍵詞：關(guān)聯(lián)規(guī)則；自適應(yīng)小生境遺傳算法；選擇；雜交

?

　　遺傳算法（GA）是一種基于生物界適者生存理論的自適應(yīng)搜索技術(shù)，其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，算法的搜索過(guò)程不依賴于目標(biāo)函數(shù)的梯度信息^[1-4]，目前它已經(jīng)成功地應(yīng)用于組合優(yōu)化、自動(dòng)控制等眾多領(lǐng)域^[5-6]。由于基本遺傳算法所具有的特性，用它進(jìn)行優(yōu)化時(shí)的結(jié)果將使群體中的個(gè)體集中到目標(biāo)函數(shù)值最大的一個(gè)峰值上，存在局部搜索能力不強(qiáng)，易陷入局部最優(yōu)和早熟等缺陷，使得傳統(tǒng)的GA在進(jìn)行查詢優(yōu)化時(shí)效果不理想。在實(shí)際應(yīng)用中有時(shí)希望最終搜索到的優(yōu)化點(diǎn)不是只在一個(gè)峰值上，而是在多個(gè)峰值上都有分布，而且分布的多少與峰值的高低成正比。這就要求種群保持一定的個(gè)體多樣性。這點(diǎn)在基于遺傳的機(jī)器學(xué)習(xí)等問(wèn)題中也尤為重要^[2]。數(shù)據(jù)挖掘技術(shù)是機(jī)器學(xué)習(xí)、人工智能、數(shù)據(jù)系統(tǒng)等領(lǐng)域的研究方向。數(shù)據(jù)挖掘就是從大型數(shù)據(jù)庫(kù)的大量原始數(shù)據(jù)中提取出人們感興趣的、具有潛在應(yīng)用價(jià)值的指示和信息。其中關(guān)聯(lián)規(guī)則是最有用的信息之一，它用于發(fā)現(xiàn)大量數(shù)據(jù)項(xiàng)集合之間的關(guān)聯(lián)^[7]。本文提出一種自適應(yīng)小生境遺傳算法應(yīng)用于關(guān)聯(lián)規(guī)則挖掘技術(shù)。
1 關(guān)聯(lián)規(guī)則的描述
　　令I(lǐng) = {i₁,i₂ , ... ,i_d}是事務(wù)中所有項(xiàng)目的集合，而T={t₁ , t₂, ... , t_n }是所有事務(wù)的集合。每個(gè)事務(wù)ti包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)分析中，包含0個(gè)或多個(gè)項(xiàng)的集合被稱為項(xiàng)集。關(guān)聯(lián)規(guī)則(Association Rule)是形如X→Y的蘊(yùn)涵表達(dá)式，其中X和Y是互不相交的項(xiàng)集。關(guān)聯(lián)規(guī)則可以用它的支持度(support)和可信度(confidence)度量。支持度確定規(guī)則中給定數(shù)據(jù)集的頻繁程度，而可信度確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。給定事務(wù)的集合T，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于minsup并且可信度大于minconf的所有規(guī)則，其中minsup和minconf是對(duì)應(yīng)的支持度和可信度閾值^[8]。研究表明，支持度閾值隨著項(xiàng)集長(zhǎng)度的增加而遞減，因此用參考文獻(xiàn)[9]針對(duì)支持度閾值設(shè)置懲罰函數(shù)可表示為：
　　
　　其中 l為相繼長(zhǎng)度，ω= ( 0，1]。
2 自適應(yīng)小生境遺傳算法原理
2.1 小生境技術(shù)的生物學(xué)基礎(chǔ)
　　在自然界，“物以類聚，人以群分”的小生境現(xiàn)象普遍存在，生物總是喜歡同自己形狀、習(xí)性相似的生物在一起，并與同類交配繁衍后代，在生物學(xué)中，把某種特定環(huán)境及其在此環(huán)境中生存的組織稱為小生境。小生境的形成在生物學(xué)上有著積極的意義，為新物種的形成提供了可能性^[6]。
　　在具體的工程應(yīng)用中，小生境技術(shù)演變?yōu)椋簩⒚恳淮鷤€(gè)體劃分為若干類，每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群，再在該種群與不同種群之間通過(guò)雜交、變異產(chǎn)生新一代個(gè)體群，同時(shí)采用預(yù)選擇機(jī)制、排擠機(jī)制或共享機(jī)制完成選擇操作。也就是說(shuō)讓個(gè)體在一個(gè)特定的生存環(huán)境中進(jìn)化，形成多個(gè)小生境，最終達(dá)到小生境內(nèi)的峰值，從而找到全局最優(yōu)解。受此啟發(fā)，近年來(lái)人們將小生境現(xiàn)象引入到遺傳算法中，實(shí)踐證明，這一技術(shù)對(duì)于改善遺傳算法全局收斂性能具有良好的效果^[10]。
2.2 自適應(yīng)小生境遺傳算法原理
　　為解決傳統(tǒng)遺傳算法種群多樣性低的問(wèn)題，自適應(yīng)小生境遺傳算法提出：首先將初時(shí)種群中的個(gè)體按適值排序，然后相似的若干個(gè)體進(jìn)入一個(gè)小生境即子種群中獨(dú)立進(jìn)化。子種群的規(guī)模是隨著大種群的多樣性的變化而自適應(yīng)變化的。設(shè)大種群的規(guī)模為N，子種群規(guī)模為K，則有：?????
　　
　　其中，D是大種群個(gè)體的方差，f(D)是關(guān)于D的一個(gè)函數(shù)，可根據(jù)問(wèn)題的特征預(yù)先設(shè)置；σ為一常數(shù)。
　　當(dāng)大種群個(gè)體多樣性降低時(shí)，D就減小，當(dāng)D小于某一閾值σ時(shí)，子種群規(guī)模K降低到最低限度2。
　　在小生境技術(shù)中，插用（μ＋λ）選擇機(jī)制，它被認(rèn)為是集中流行進(jìn)化算法的選擇機(jī)制中選擇率最高的一種。交叉操作采用均勻模板交叉算子。當(dāng)交叉結(jié)束后，立即進(jìn)入（μ＋λ）選擇，以生成子種群的新一代個(gè)體。
　　新產(chǎn)生的個(gè)體進(jìn)行隨機(jī)變異，當(dāng)變異的個(gè)體為子種群中的最佳個(gè)體時(shí)，應(yīng)該對(duì)該最佳個(gè)體及其變異所得到的新個(gè)體進(jìn)行（1＋ l）選擇，以保證最優(yōu)個(gè)體以概率 l保留到下一代^[11]。
算法描述如圖1所示。

?

3.2? 數(shù)據(jù)庫(kù)數(shù)字化
　　為了易于表示起見，將數(shù)據(jù)庫(kù)中重要字段取值數(shù)字化。
　　腫瘤種類劃分：肺癌；胃癌；乳腺癌；大腸癌；口腔癌；肝癌；宮頸癌；食管癌；其他。
　　診療計(jì)劃劃分：手術(shù)；放療；化療；生物免疫治療；中醫(yī)中藥治療。
　　治療效果：治愈（5年存活）；好轉(zhuǎn)；惡化；死亡；自動(dòng)出院。
　　國(guó)際分期劃分：1（I）；2（IIa）；3（IIb）；4（III），5（IV）。
3.3 關(guān)聯(lián)規(guī)則的提取
　　為挖掘數(shù)據(jù)庫(kù)中蘊(yùn)涵數(shù)字化屬性間的關(guān)聯(lián)規(guī)則，根據(jù)以上數(shù)字化步驟，將4個(gè)屬性分別劃分為9、5、5、5個(gè)屬性等級(jí)。設(shè)X={腫瘤種類、國(guó)際分期}，Y={診療方案、治療效果}，給定最小支持度和最小置信度都為0.02，表2列出部分有意義的所得到的優(yōu)化語(yǔ)言值關(guān)聯(lián)規(guī)則。

?

　　根據(jù)關(guān)聯(lián)規(guī)則的特點(diǎn)和要求，提出了基于自適應(yīng)小生境遺傳算法的關(guān)聯(lián)規(guī)則挖掘算法。試驗(yàn)顯示，該方法快速有效。

參考文獻(xiàn)
[1]?RUDOLPH? G.Convergence analysis of canonical genertic algorithme[J].IEEE Trans on Neural Network,1994,5(1) ：96-101.
[2]?田盛豐.人工智能原理與應(yīng)用[M].北京：北京立功大學(xué)出版社，1993.
[3]?FOGEL.An introduction to simulated evolutuionary ptionization[J]. IEEE Trans on Neural Network,1994,5(1): 3-14.
[4]?陳國(guó)良.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.
[5]?SONG? S? K,GORLA? N. Agenetic algorithm for vertical fragmentation and access path selection[J].The Computer Journal,2000,43(1):81-92.
[6]?JACK? L? B,NANDI? A? K. Genetic algorithms for feature selection in machine condition monitoring with vibration signals[J].IEEE Proceedings Vision,Image and Signal Processing，2000，47（3）：205－212.
[7]?TAN Ping? Ning ,STEINBACH M,KUMAR V.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社，2006.
[8]?潘舒，吳陳.基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘[J].現(xiàn)代電子技術(shù)， 2008，265（2）：90－92.
[9]?趙連朋，金喜子，孫亮，等.基于小生境遺傳算法的關(guān)聯(lián)規(guī)則挖掘方法[J] .計(jì)算機(jī)工程，2008，34（10）：163-165.
[10]? 王小平，曹立明.遺傳算法.理論、應(yīng)用于軟件實(shí)現(xiàn)[M].西安： 西安交通大學(xué)出版社，2000.
[11]? 郟宣耀，王芳.一種改進(jìn)的小生境遺傳算法[J].重慶郵電學(xué)院 學(xué)報(bào)（自然科學(xué)報(bào)），2005（2）.