10206.一種新的混合遺傳的基因聚類方法

1、碩士學位論文一種新的混合遺傳的基因聚類方法ANewHybridGeneticGeneClusteringMethod作者姓名：王化植學科、專業(yè)：i土箕數(shù)堂學號：21101067完成日期：2014428大連理工大學DalianUniversityofTechnology大連理工大學碩士學位論文摘要隨著基因芯片技術的不斷發(fā)展，已經(jīng)獲取了海量的基因表達數(shù)據(jù)。從已有的基因數(shù)據(jù)中挖掘有價值的信息，對于探討基因的功能甚至某些細胞過程都有重大意義。聚

2、類方法廣泛的應用于此類數(shù)據(jù)的分析，特別是當前的研究熱點——基因聚類問題。利用聚類算法找出相似基因，進而可以通過已知基因的信息去推斷大量未知基因的功能。在眾多聚類算法中，KMeans算法是最受歡迎的劃分方式。它采用經(jīng)典的梯度下降策略，以迭代的重定位方式分割數(shù)據(jù)集，快速給出聚類結果。然而KMeans算法有兩大缺點：對初始質心敏感和易陷入局部極小，導致處理大規(guī)模、高維數(shù)據(jù)時聚類結果不理想。運用遺傳算法(GA)在整個解空間搜索基因聚類問題的最優(yōu)

3、劃分可以明顯改善最終的聚類效果。但傳統(tǒng)的交叉操作會產(chǎn)生非法分割即空類，導致大量的重復計算。因此直接利用GA處理基因聚類問題會付出高昂的計算代價，特別是針對大規(guī)?；虮磉_數(shù)據(jù)，各個聚類質心的收斂速度非常緩慢。遺傳K均值算法(GKA)在保持遺傳框架的前提下，采用KMeans算法代替交叉操作進行局部更新，算法融合后顯著的改善了GA處理低維基因聚類時收斂過緩的缺陷，獲得了給定基因表達數(shù)據(jù)集的全局意義下的最優(yōu)分割。然而對于某些高維基因數(shù)據(jù)，GKA

4、的收斂速度仍不盡如人意。為了得到更全面的基因聚類算法，我們嘗試了添加擾動項的XKMeans算法，并且通過補類的策略避免了選取合理擾動邊界帶來的大量計算，得到了改進算法——IXKMeans。更進一步，效仿GKA的混合方式，將IXK—Means引入到遺傳框架中，提出了一種新的收斂到全局最優(yōu)的基因聚類算法——G)(】A。本文首先介紹了基本的劃分聚類算法及遺傳框架下的聚類方法，接著在第三章中敘述了GXKA的計算流程及其算法細節(jié)，最后在第四章中，

5、利用有限Markov鏈原理給出了GXKA的收斂性證明，并且進行了真實基因表達數(shù)據(jù)的實驗。通過這些理論及實驗的分析，我們得到了如下結論：(1)滿足一定條件下，GXKA以概率l收斂到全局最優(yōu)劃分；(2)在相同的停機條件下，就三個評價聚類指標(MSE、類緊度日和類分離度D，)而言，IXKMeans優(yōu)于XKMeans的聚類效果；(3)GXKA的收斂速度相比GKA有了質的提高，大致只要GKA一半的進化時間就可以收斂到GKA的MSE穩(wěn)態(tài)，有效的緩解