摘 要：傳統(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è)體之間的信息交換,，算法的搜索過程不依賴于目標(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í)等問題中也尤為重要^[2]。數(shù)據(jù)挖掘技術(shù)是機(jī)器學(xué)習(xí),、人工智能,、數(shù)據(jù)系統(tǒng)等領(lǐng)域的研究方向。數(shù)據(jù)挖掘就是從大型數(shù)據(jù)庫的大量原始數(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è)種群,，再在該種群與不同種群之間通過雜交、變異產(chǎn)生新一代個(gè)體群,，同時(shí)采用預(yù)選擇機(jī)制,、排擠機(jī)制或共享機(jī)制完成選擇操作。也就是說讓個(gè)體在一個(gè)特定的生存環(huán)境中進(jìn)化,，形成多個(gè)小生境，最終達(dá)到小生境內(nèi)的峰值,，從而找到全局最優(yōu)解,。受此啟發(fā)，近年來人們將小生境現(xiàn)象引入到遺傳算法中,，實(shí)踐證明,，這一技術(shù)對(duì)于改善遺傳算法全局收斂性能具有良好的效果^[10]。
2.2 自適應(yīng)小生境遺傳算法原理
　　為解決傳統(tǒng)遺傳算法種群多樣性低的問題，自適應(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ù)問題的特征預(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ù)庫數(shù)字化
　　為了易于表示起見,，將數(shù)據(jù)庫中重要字段取值數(shù)字化。
　　腫瘤種類劃分：肺癌,；胃癌,；乳腺癌；大腸癌,；口腔癌,；肝癌；宮頸癌；食管癌,；其他,。
　　診療計(jì)劃劃分：手術(shù)；放療,；化療,；生物免疫治療；中醫(yī)中藥治療,。
　　治療效果：治愈（5年存活）,；好轉(zhuǎn)；惡化,；死亡,；自動(dòng)出院。
　　國際分期劃分：1（I）,；2（IIa）,；3（IIb）；4（III）,，5（IV）,。
3.3 關(guān)聯(lián)規(guī)則的提取
　　為挖掘數(shù)據(jù)庫中蘊(yùn)涵數(shù)字化屬性間的關(guān)聯(lián)規(guī)則，根據(jù)以上數(shù)字化步驟,，將4個(gè)屬性分別劃分為9,、5、5,、5個(gè)屬性等級(jí),。設(shè)X={腫瘤種類、國際分期},，Y={診療方案,、治療效果}，給定最小支持度和最小置信度都為0.02,，表2列出部分有意義的所得到的優(yōu)化語言值關(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]?陳國良.遺傳算法及其應(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）.