聚類分析及其應用研究.pdf

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

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

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

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

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

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

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

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

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