聚類(lèi)分析及其應(yīng)用研究.pdf

1、模式識(shí)別，也被稱(chēng)為分類(lèi)或者是統(tǒng)計(jì)分類(lèi)，模式識(shí)別學(xué)科的研究目的就是為了構(gòu)建能夠自動(dòng)判別輸入數(shù)據(jù)類(lèi)別信息的分類(lèi)系統(tǒng)。聚類(lèi)分析是一種無(wú)監(jiān)督的模式識(shí)別方法，是模式識(shí)別研究中的一個(gè)重要領(lǐng)域。無(wú)監(jiān)督的聚類(lèi)分析算法能夠探索輸入數(shù)據(jù)的內(nèi)部群組結(jié)構(gòu)，目前已經(jīng)被廣泛應(yīng)用于各種數(shù)據(jù)分析場(chǎng)合，包括計(jì)算機(jī)視覺(jué)分析，統(tǒng)計(jì)分析，圖像處理，醫(yī)療信息處理，生物科學(xué)，社會(huì)科學(xué)和心理科學(xué)等。聚類(lèi)分析的基本原理就是將輸入數(shù)據(jù)分成不同的群組，同一組中的成員擁有相似的特性，相反不

2、同組中的成員特性相異。
　　 本文主要針對(duì)聚類(lèi)分析算法及其應(yīng)用進(jìn)行研究，本文研究的聚類(lèi)分析算法主要應(yīng)用于生物信息學(xué)數(shù)據(jù)分析，大規(guī)模選址問(wèn)題，數(shù)據(jù)不規(guī)則形狀分布聚類(lèi)分析問(wèn)題。主要的工作和取得的成果概括如下：
　　 （1）基因表達(dá)序列分析技術(shù)（Serial.Analysis of gene expression，SAGE）是一種快速詳細(xì)的分析數(shù)以千計(jì)轉(zhuǎn)錄（transcripts）的最佳方法，這項(xiàng)技術(shù)最開(kāi)始由Victor Ve

3、lculescu博士于1995年提出。聚類(lèi)分析算法是一種非常有用的SAGE數(shù)據(jù)分析方法，被用于發(fā)現(xiàn)SAGE數(shù)據(jù)集中潛在的新的或隱含的轉(zhuǎn)錄或者是基因組，因此已經(jīng)被用于分析SAGE數(shù)據(jù)。盡管研究人員已經(jīng)給出了多種用于SAGE數(shù)據(jù)分析的聚類(lèi)分析算法，但是這些算法通常都需要結(jié)合一些用戶自己設(shè)定的參數(shù)，并且聚類(lèi)分析的結(jié)果對(duì)參數(shù)選擇有很強(qiáng)的依賴(lài)性。本文基于SAGE數(shù)據(jù)的Poisson統(tǒng)計(jì)特性和最近提出的仿射消息傳播聚類(lèi)分析算法提出一種自適應(yīng)的聚類(lèi)分

4、析算法，在該算法中引入了一個(gè)聚類(lèi)結(jié)果校驗(yàn)測(cè)度，并以該測(cè)度為代價(jià)函數(shù)對(duì)聚類(lèi)結(jié)果進(jìn)行優(yōu)化調(diào)整以獲得優(yōu)化的聚類(lèi)結(jié)果，該算法被命名為PoissonAPS。在多個(gè)實(shí)際生命數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果表明本文給出的方法能夠?qū)AGE數(shù)據(jù)進(jìn)行很好的聚類(lèi)分析，并且產(chǎn)生有意義的可解釋的分類(lèi)結(jié)果。
　　 （2）隨著高通量測(cè)序技術(shù)的發(fā)展，目前在生物信息數(shù)據(jù)庫(kù)中已經(jīng)累積了大量的蛋白質(zhì)序列數(shù)據(jù)。但是由于實(shí)驗(yàn)確定蛋白質(zhì)序列功能的速度無(wú)法趕上新序列測(cè)序的速度，因此

5、造成大量的新測(cè)序的蛋白質(zhì)序列尚未通過(guò)實(shí)驗(yàn)的方式來(lái)確定它們的生物功能和家族信息。由于實(shí)驗(yàn)驗(yàn)證過(guò)程非常耗時(shí)并且昂貴，因此理想情況下希望僅僅依賴(lài)序列之間的相似性來(lái)探測(cè)未知功能序列和已知功能序列之間的同源關(guān)系，進(jìn)而確定未知功能序列的信息。聚類(lèi)分析方法能夠通過(guò)將蛋白質(zhì)序列分類(lèi)到不同的蛋白質(zhì)家族獲得有意義的信息。最近幾年研究人員已經(jīng)提出了多種用于蛋白質(zhì)序列分析的聚類(lèi)算法。面對(duì)眾多的蛋白質(zhì)序列聚類(lèi)分析算法，有必要進(jìn)行一個(gè)對(duì)比研究分析，分析的結(jié)果將有利

6、于生命科學(xué)研究人員考察不同的算法并且選擇合適的用于特定實(shí)驗(yàn)分析場(chǎng)合的算法。本文比較了四種典型的蛋白質(zhì)序列分析算法，在多個(gè)數(shù)據(jù)集上考察算法的以下幾方面的性能：缺省參數(shù)條件下的聚類(lèi)算法性能分析；算法對(duì)蛋白質(zhì)序列在數(shù)據(jù)集中所處位置是否敏感；數(shù)據(jù)集自身的真實(shí)類(lèi)分布對(duì)聚類(lèi)算法結(jié)果的影響；調(diào)節(jié)算法的參數(shù)，觀察參數(shù)對(duì)聚類(lèi)結(jié)果的影響。本文給出的實(shí)驗(yàn)結(jié)果能夠幫助研究人員選擇合適的分析算法。并且實(shí)驗(yàn)結(jié)果還表明蛋白質(zhì)序列聚類(lèi)分析算法還有很大的改進(jìn)空間。

7、>　　 （3）隨著大量的未知功能的蛋白質(zhì)序列數(shù)據(jù)的累積，目前已經(jīng)無(wú)法通過(guò)實(shí)驗(yàn)的手段來(lái)標(biāo)注未知功能的蛋白質(zhì)序列。聚類(lèi)分析方法通過(guò)將蛋白質(zhì)序列分類(lèi)到不同的同源組來(lái)確定未知功能的蛋白質(zhì)序列的信息。本文引入了一種用于大數(shù)據(jù)量蛋白質(zhì)序列分析的無(wú)比對(duì)的在線聚類(lèi)分析方法，命名為OmineCAPS。該方法具有速度快，可在有限內(nèi)存環(huán)境下運(yùn)行等優(yōu)點(diǎn)，此外該方法還可以被部署在WEB服務(wù)器上。實(shí)驗(yàn)結(jié)果表明該方法能夠快速的分析大數(shù)據(jù)量的蛋白質(zhì)序列，并且獲得的聚

8、類(lèi)結(jié)果的質(zhì)量接近于其它算法。
　　 （4）選址布局問(wèn)題是一個(gè)廣泛研究的運(yùn)籌學(xué)問(wèn)題。通過(guò)將選址布局問(wèn)題看作聚類(lèi)問(wèn)題，結(jié)合聚類(lèi)分析算法并且將候選地址的信息映射為特征向量，本文提出了兩種求解選址布局問(wèn)題的方法：基于塊劃分的選址布局方法；基于道路網(wǎng)絡(luò)的選址布局方法。文中使用模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集來(lái)評(píng)估這兩種方法，實(shí)驗(yàn)結(jié)果表明兩種方法都能夠求解設(shè)施資源受限和不受限情況下的選址布局問(wèn)題，而且可以很好的解決大規(guī)模的選址布局問(wèn)題。
　　

9、 （5）探測(cè)數(shù)據(jù)不規(guī)則形狀分布的自然類(lèi)簇分布是模式識(shí)別研究領(lǐng)域的一個(gè)困難的任務(wù)。本文給出了一種有效的數(shù)據(jù)不規(guī)則形狀分布聚類(lèi)分析算法，該算法結(jié)合了譜聚類(lèi)和仿射消息傳播聚類(lèi)算法的優(yōu)點(diǎn)，能夠很好的分析數(shù)據(jù)不規(guī)則形狀分布的類(lèi)簇結(jié)構(gòu)。與此同時(shí)，文中給出了一種新的基于鄰居離散分析的相似度測(cè)度。本文給出的方法簡(jiǎn)單有效，在多個(gè)模擬數(shù)據(jù)和實(shí)際數(shù)據(jù)上檢驗(yàn)了方法的性能。實(shí)驗(yàn)結(jié)果表明本文給出的方法能夠探測(cè)數(shù)據(jù)中的自然類(lèi)簇分布，并且聚類(lèi)分析的結(jié)果和人的自然判斷相