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

?

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

?

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

?

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

參考文獻
[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] .計算機工程,，2008，34（10）：163-165.
[10]? 王小平,，曹立明.遺傳算法.理論,、應(yīng)用于軟件實現(xiàn)[M].西安： 西安交通大學(xué)出版社，2000.
[11]? 郟宣耀,，王芳.一種改進的小生境遺傳算法[J].重慶郵電學(xué)院 學(xué)報（自然科學(xué)報）,，2005（2）.