10206.一種新的混合遺傳的基因聚類(lèi)方法

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

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

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

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

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