第四章數(shù)理多元統(tǒng)計(jì)

生物信息學(xué)第四章原核及真核生物

基因組分析§4.2數(shù)理基礎(chǔ)

(Part2)生物信息學(xué)生命科學(xué)統(tǒng)計(jì)分析方法生命現(xiàn)象多樣性重復(fù)性復(fù)雜性隨機(jī)性多元統(tǒng)計(jì)分析方法多元回歸分析方法多元判別分析方法聚類分析方法主成分分析方法相關(guān)性分析方法……生物信息學(xué)復(fù)習(xí)生物統(tǒng)計(jì)學(xué)主要內(nèi)容

3.1統(tǒng)計(jì)和概率的基礎(chǔ)知識(shí)（1）生物統(tǒng)計(jì)學(xué)的概念和內(nèi)容（2）數(shù)據(jù)的搜集與整理（3）特征數(shù)的計(jì)算（4）概率和概率分布

3.2統(tǒng)計(jì)推斷（1）樣本平均數(shù)的檢驗(yàn)（2）樣本頻率的檢驗(yàn)（3）方差同質(zhì)性檢驗(yàn)（4）非參數(shù)檢驗(yàn)（5）卡方檢驗(yàn)生物信息學(xué)

3.3統(tǒng)計(jì)分析方法（1）方差分析（2）直線回歸和相關(guān)分析（3）可直線化的的曲線回歸分析（4）多元回歸與相關(guān)分析（5）逐步回歸分析（6）多項(xiàng)式回歸（7）協(xié)方差分析

3.4抽樣與試驗(yàn)設(shè)計(jì)（1）抽樣誤差估計(jì)（2）抽樣方法（3）抽樣方案制定（4）常見的試驗(yàn)設(shè)計(jì)如對(duì)比設(shè)計(jì)、隨機(jī)區(qū)組設(shè)計(jì)、正交設(shè)計(jì)等生物信息學(xué)多元統(tǒng)計(jì)方法概述運(yùn)用數(shù)理統(tǒng)計(jì)方法研究多變量、多因素問題多元統(tǒng)計(jì)分析理論和方法多元統(tǒng)計(jì)分析研究多元變量的統(tǒng)計(jì)規(guī)律性，是一元統(tǒng)計(jì)學(xué)的推廣，同時(shí)又有多元隨機(jī)變量特有的問題。生物信息學(xué)2、降維問題（簡化數(shù)據(jù)結(jié)構(gòu)）（1）將某些較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)通過變量變換等方法使相互依賴的變量變成互不相關(guān)的變量（2）把高維空間的數(shù)據(jù)投影到低維空間，使問題得到簡化同時(shí)損失的信息不太多。

主成分分析因子分析對(duì)應(yīng)分析3.2多元統(tǒng)計(jì)方法1、歸類問題對(duì)所考察的觀測(cè)樣本（或變量）按照相似程度進(jìn)行分類、歸類聚類分析判別分析生物信息學(xué)3、變量間的相互聯(lián)系（1）相互依賴關(guān)系：分析一個(gè)或幾個(gè)變量的變化是否依賴于另一些變量的變化。建立變量間的定量關(guān)系，并用于預(yù)測(cè)或控制回歸分析（2）變量間的相互關(guān)系：分析兩組變量間的相互關(guān)系典型相關(guān)性分析生物信息學(xué)一、歸類問題條件：已知研究對(duì)象總體的類別數(shù)目及其特征（如：分布規(guī)律，或各類的訓(xùn)練樣本）目的：判斷未知類別的樣本的歸屬類別條件：研究對(duì)象總體的類別數(shù)目未知，也不知總體樣本的具體分類情況目的：通過分析，選定描述個(gè)體相似程度的統(tǒng)計(jì)量、確定總體分類數(shù)目、建立分類方法；對(duì)研究對(duì)象給出合理的分類。(“物以類聚”是聚類分析的基本出發(fā)點(diǎn)

)判別分析(DiscriminantAnalysis)聚類分析(ClusteringAnalysis)生物信息學(xué)1、判別分析用于判別樣品所屬類型的統(tǒng)計(jì)分析方法基因識(shí)別：根據(jù)某一DNA序列的核苷酸組分、功能信號(hào)特征等指標(biāo)，判別是否編碼蛋白序列？醫(yī)學(xué)診斷：某一病人肺部存在陰影，判別:

肺結(jié)核？良性腫瘤？肺癌？人類考古學(xué)：根據(jù)頭蓋骨的特征，判別：民族、性別、生活年代？股票分析預(yù)測(cè)：氣象分析預(yù)測(cè)：自然災(zāi)害分析預(yù)測(cè)：

……生物信息學(xué)判別分析問題的數(shù)學(xué)描述設(shè)有k個(gè)m維的總體G1,G2,…,Gk，

(1).它們的分布特征已知，可以表示為F1(x),F2(x),…,Fk(x)(2).或者知道來自各個(gè)總體的樣本（訓(xùn)練樣本）。

對(duì)于給定的一個(gè)未知樣品X（檢測(cè)樣本），判別X屬于哪個(gè)總體。多元的、復(fù)雜的、高度綜合的統(tǒng)計(jì)分析問題生物信息學(xué)判別準(zhǔn)則學(xué)習(xí)(Learning)檢測(cè)(Test)判別效率評(píng)價(jià)(Evaluation)

Fisher判別法

距離判別法

Bayes判別法逐步判別法

……訓(xùn)練樣本訓(xùn)練集Learningset檢測(cè)樣本檢測(cè)集Testset判別分析的原理生物信息學(xué)1.1Fisher線性判別法Fisher判別的基本思想將

m組n維的數(shù)據(jù)投影到某一個(gè)方向，使得投影后的組與組之間盡可能地分開。生物信息學(xué)平面上兩類數(shù)據(jù)訓(xùn)練樣本的散點(diǎn)圖（兩組數(shù)據(jù)樣本在平面上存在一個(gè)合理的分界線L）x1x2G1G2L:c1x1+c2x2－c=0令：F(x1,x2)=c1x1+c2x2F(x1,x2):判別函數(shù)

c：判別值生物信息學(xué)已知：數(shù)據(jù)屬性有n個(gè)，每個(gè)數(shù)據(jù)點(diǎn)為n維向量X：已知總體數(shù)據(jù)分為兩類：G1和G2

，總體G1有p個(gè)樣本點(diǎn)，總體G2有q個(gè)樣本點(diǎn)。屬性（分量）12…n總體G1(i=1,…,p)1X1(1)x11(1)x12(1)…x1n(1)……………iXi(1)xi1(1)xi2(1)…xin(1)……………pXp(1)xp1(1)xp2(1)…xpn(1)總體G2(i=1,…,q)1X1(2)x11(2)x12(2)…x1n(2)……………iXi(2)xi1(2)xi2(2)…xin(2)……………qXq(2)xq1(2)xq2(2)…xqn(2)目標(biāo)：求解在n維空間中總體G1和總體G2的最優(yōu)分界平面。生物信息學(xué)定義線性判別函數(shù)為：其中Ci

(i=1,2,…,n)為常數(shù)（待定系數(shù)）。若判別值為C

，對(duì)于任何未知數(shù)據(jù)點(diǎn)X(x1,x2,…,xn)，代入判別函數(shù)，依據(jù)F(x1,x2,…,xn)與C值的比較，可以判別點(diǎn)X屬于哪一類。1、確定待定系數(shù)Ci

(i=1,2,…,n)2、確定判別值C生物信息學(xué)將類G1的p個(gè)點(diǎn)、類G2的q個(gè)點(diǎn)分別代入判別函數(shù)：記確定待定系數(shù)Ci生物信息學(xué)令：A與G1和G2兩類點(diǎn)的幾何中心的距離相關(guān)。顯然，判別函數(shù)F(x1,x2,…,xn)應(yīng)該使A值越大越好。令：B與G1和G2兩類點(diǎn)的相對(duì)于各自幾何中心的離差相關(guān)。顯然，判別函數(shù)F(x1,x2,…,xn)應(yīng)該使B值越小越好。生物信息學(xué)構(gòu)造函數(shù)I：選擇合適的待定系數(shù)Ci

(i=1,2,…,n)，使得函數(shù)I(C1,C2,…,Cn)達(dá)到極大值。生物信息學(xué)得到求解待定系數(shù)(C1,C2,…,Cn)的線性方程組：………………生物信息學(xué)確定判別值C判別函數(shù)已知，不妨寫成：將G1的p個(gè)點(diǎn)、G2的q個(gè)點(diǎn)分別代入判別函數(shù)：生物信息學(xué)對(duì)G1、G2的(p+q)個(gè)點(diǎn)的判別函數(shù)值取總體的平均值：顯然，值是兩類點(diǎn)的判別函數(shù)值的加權(quán)平均，處于兩類判別函數(shù)平均值之間，也等價(jià)于兩類點(diǎn)的總體幾何中心的判別函數(shù)值。因此，將判別值C取為值：生物信息學(xué)Fisher線性判別的基本步驟屬性（分量）12…nG1(i=1,…,p)1X1(1)x11(1)x12(1)…x1n(1)……………iXi(1)xi1(1)xi2(1)…xin(1)……………pXp(1)xp1(1)xp2(1)…xpn(1)G2(i=1,…,q)1X1(2)x11(2)x12(2)…x1n(2)……………iXi(2)xi1(2)xi2(2)…xin(2)……………qXq(2)xq1(2)xq2(2)…xqn(2)問題已知數(shù)據(jù)樣本點(diǎn)分為兩類：G1和G2，G1有p個(gè)點(diǎn)，G2有q個(gè)點(diǎn)。求出判別函數(shù)F(x1,x2,…,xn)和判別值C

。對(duì)于任何未知數(shù)據(jù)點(diǎn)X(x1,x2,…,xn)，依據(jù)F(x1,x2,…,xn)與C值的比較，判別點(diǎn)X屬于哪一類。生物信息學(xué)STEP1先對(duì)樣本點(diǎn)數(shù)據(jù)Xi(1)(xi1(1),xi2(1),…,xin(1))（i=1,…,p）、Xi(2)(xi1(2),xi2(2),…,xin(2))（i=1,…,q）分別計(jì)算以下求和以及平均值：生物信息學(xué)STEP2計(jì)算di和Sij，注意對(duì)稱性Sij=Sji

：生物信息學(xué)STEP3解線性代數(shù)方程組：若方程有解，得到判別函數(shù)F：生物信息學(xué)STEP4將平均值代入判別函數(shù)，然后計(jì)算判別值C：生物信息學(xué)STEP5對(duì)未知數(shù)據(jù)X(x1,x2,…,xn)進(jìn)行判別：將數(shù)據(jù)X(x1,x2,…,xn)代入判別函數(shù)F，與判別值進(jìn)行比較，判別其屬于哪一類。生物信息學(xué)Fisher線性判別的應(yīng)用舉例x1x2ORF序號(hào)x1x2類別157124323782486253616251766189629542原核生物DNA序列上最長ORF是否編碼的判別：依據(jù)某兩個(gè)屬性進(jìn)行打分，得到x1,x2，在x1-x2

平面上進(jìn)行Fisher判別分析。生物信息學(xué)生物信息學(xué)生物信息學(xué)逐級(jí)Fisher判別法x1x2G1G2G3生物信息學(xué)Fisher判別法小結(jié)基本思想：投影。使得投影后各組盡可能分開。本質(zhì)上基于微分尋優(yōu)的方法局限

1、可能陷入局部最優(yōu)的判別結(jié)果；

2、對(duì)數(shù)據(jù)屬性各變量的要求較為苛刻，如正態(tài)性、相互獨(dú)立性等；

3、對(duì)于類別數(shù)目太多的判別問題，采用逐級(jí)判別比較麻煩。生物信息學(xué)1.2距離判別法距離判別的基本思想樣品與哪一類總體的距離最近，就判別它屬于哪一類總體。因此我們首先考慮的是是否能夠構(gòu)造一個(gè)恰當(dāng)?shù)木嚯x函數(shù)，通過樣本與某類別之間距離的大小，判別其所屬類別。

距離的定義絕對(duì)距離相對(duì)距離生物信息學(xué)馬氏（Mahalanobis）距離則對(duì)于任一點(diǎn)X(x1,x2,…,xn)

，定義它與總體G的Mahalanobis距離為：定義：Mahalanobis距離設(shè)總體G為n維變量，即含有n個(gè)屬性指標(biāo)(x1,x2,…,xn)。已知總體G中的t個(gè)樣品Xk

(xk1,xk2,…,xkn)，k=1,2,…,t?？傮w均值可用樣本均值估計(jì)：生物信息學(xué)其中，矩陣S＝(sij)n×n為：矩陣S稱為協(xié)方差矩陣（covariancematrix），反映總體G的屬性指標(biāo)中第i個(gè)分量與第j個(gè)分量的相關(guān)性。特別地，當(dāng)n=1時(shí)，Mahalanobis距離為：生物信息學(xué)馬氏距離和歐式距離之間的差別

馬氏距離歐氏距離生物信息學(xué)xp(x)xp(x)|x-|G1:N(,1)G2:N(,2)生物信息學(xué)兩類總體的Mahalanobis距離判別方法已知：考慮具有n個(gè)屬性的兩類總體G1、G2，已知G1的p個(gè)訓(xùn)練樣本，G2的q個(gè)訓(xùn)練樣本：問題：對(duì)于未知樣本點(diǎn)X(x1,x2,…,xn)，判別其類型？生物信息學(xué)G1、G2的總體均值根據(jù)樣本均值估計(jì)得到：分別求出總體G1、G2的協(xié)方差矩陣S(1)、S(2)：生物信息學(xué)對(duì)于任一新樣本X(x1,x2,…,xn)，分別計(jì)算它到總體G1、G2的Mahalanobis距離：生物信息學(xué)構(gòu)造判別函數(shù)W(X)：判別準(zhǔn)則為：生物信息學(xué)1.3判別效果的評(píng)價(jià)錯(cuò)判損失N(G1|G2)N(G2|G1)生物信息學(xué)P(G1|G2)P(G2|G1)p(x)xG1:N(1,1)G2:N(2,2)12*錯(cuò)判率生物信息學(xué)檢驗(yàn)判別效果的方法訓(xùn)練集的回判

訓(xùn)練集（Learningset）：訓(xùn)練樣本集檢測(cè)集（Testset）：檢測(cè)樣本集（類別未知）利用訓(xùn)練集作為檢測(cè)集：用判別方法對(duì)已知類型的樣本進(jìn)行回判，統(tǒng)計(jì)判錯(cuò)的個(gè)數(shù)以及占樣本總數(shù)的比例，作為錯(cuò)判率的估計(jì)。特點(diǎn)：容易低估錯(cuò)判率。

生物信息學(xué)從訓(xùn)練集中構(gòu)造檢測(cè)集已知數(shù)據(jù)集判別效率訓(xùn)練集50％檢測(cè)集50％判別準(zhǔn)則學(xué)習(xí)檢測(cè)評(píng)價(jià)生物信息學(xué)刀切法（Jack-knifeMethod）“舍一法（Leaveone-out）”“Lachenbruch刪除法”“交叉確認(rèn)法(Cross-validation)”基本思想：(1).每次從訓(xùn)練樣本集中剔除1個(gè)樣本X'；(2).利用其余的樣本（數(shù)量為p＋q－1）作為訓(xùn)練集來訓(xùn)練得到判別準(zhǔn)則;(3).根據(jù)判別準(zhǔn)則對(duì)樣本X'進(jìn)行判別；(4).對(duì)訓(xùn)練樣本中的每個(gè)樣本依次重復(fù)進(jìn)行，記錄判別對(duì)錯(cuò)的個(gè)數(shù)；(5).計(jì)算錯(cuò)判率。生物信息學(xué)

檢測(cè)結(jié)果實(shí)際歸類Predicted

G1(P)PredictedG2(N)合計(jì)(T)RealG1N(G1|G1)(TP)N(G2|G1)(TN)Nreal1(F)RealG2N(G1|G2)(FP)N(G2|G2)(FN)Nreal2合計(jì)Npred1Npred2定義錯(cuò)判率（貌似錯(cuò)判率）為：檢驗(yàn)判別效果的幾個(gè)指標(biāo)生物信息學(xué)定義敏感性（sensitivity，Sn）為：Sn=TP/(TP+FN)定義特異性（specificity，Sp）為：Sp=TN/(TN+FP)

馬修相關(guān)系數(shù)(Matthewscorrelationcoefficient,MCC)生物信息學(xué)2.聚類分析方法(Clusteringmethod)

聚類分析：（群分析）是實(shí)用多元統(tǒng)計(jì)分析的一個(gè)新分支，正處于發(fā)展階段。理論上尚未完善，但應(yīng)用十分廣泛。實(shí)質(zhì)上是一種分類問題，目的是建立一種分類方法，將一批數(shù)據(jù)按照特征的親疏、相似程度進(jìn)行分類。定性、經(jīng)驗(yàn)的分類的局限分類較粗、數(shù)據(jù)量小、憑借經(jīng)驗(yàn)計(jì)算生物學(xué)中的聚類分析問題：

根據(jù)DNA芯片獲得的基因表達(dá)數(shù)據(jù)進(jìn)行基因聚類（數(shù)據(jù)量龐大）蛋白質(zhì)相互作用網(wǎng)絡(luò)的分類根據(jù)不同物種的大分子序列進(jìn)行相似性比較并構(gòu)建系統(tǒng)發(fā)育樹

……生物信息學(xué)分類問題條件：已知研究對(duì)象總體的類別數(shù)目及其特征（如：分布規(guī)律，或各類的訓(xùn)練樣本）目的：判斷未知類別的樣本的歸屬類別條件：研究對(duì)象總體的類別數(shù)目未知，也不知總體樣本的具體分類情況目的：通過分析，選定描述個(gè)體相似程度的統(tǒng)計(jì)量、確定總體分類數(shù)目、建立分類方法；對(duì)研究對(duì)象給出合理的分類。(“物以類聚”是聚類分析的基本出發(fā)點(diǎn)

)判別分析(DiscriminantAnalysis)聚類分析(ClusteringAnalysis)生物信息學(xué)聚類分析建立合適的分類方法：(1).將一批樣本按照親疏程度進(jìn)行分類（Q型聚類）(2).將樣本的多個(gè)變量按照相似程度進(jìn)行分類（R型聚類）系統(tǒng)聚類法(譜系聚類法)動(dòng)態(tài)聚類法最優(yōu)分割法(有序樣本聚類法)模糊聚類法圖論聚類法生物信息學(xué)2.1樣品間的距離距離的定義

用dij表示樣品X(i)與X(j)之間的距離，有

dij0;且dij=0X(i)=X(j);

dij=dji;

三角不等式：dijdik+dkj…………xtn…xtjxt1X(t)…………xin…xijxi1X(i)………x1n…x1jx11X(1)Xn…XjX1已知樣品數(shù)目為t，每個(gè)樣品測(cè)得n項(xiàng)屬性指標(biāo)，得到觀察數(shù)據(jù)xij(i=1,…,t;j=1,…,n)。生物信息學(xué)1）Minkowski（明氏）距離(課本P286)q=1時(shí)，得到一階Minkowski度量：稱為絕對(duì)值距離。絕對(duì)值距離生物信息學(xué)q=2時(shí)，得到二階Minkowski度量：稱為歐氏距離。歐氏距離是聚類分析中使用最為廣泛的距離，與各變量的量綱有關(guān)。歐氏距離Chebyshev（切比雪夫）距離生物信息學(xué)2）Lance（蘭氏）距離Lance距離是無量綱的距離對(duì)大的奇異值不敏感，適合處理高度偏倚的數(shù)據(jù)沒有考慮變量間的相關(guān)性生物信息學(xué)3）Mahalanobis（馬氏）距離

無量綱的距離考慮變量間的相關(guān)性生物信息學(xué)4）斜交空間距離稱為斜交空間距離。其中kl是變量Xk與Xl之間的相關(guān)系數(shù)（即表示變量的夾角）。生物信息學(xué)1）夾角余弦——相似系數(shù)用兩變量夾角來衡量二者的相似程度。顯然：當(dāng)i=j時(shí)，夾角ij=0，cij(1)=1，表明兩變量完全相似；當(dāng)夾角ij=2，cij(1)=0，表明兩變量正交，不相關(guān)。2.2變量間的相似系數(shù)生物信息學(xué)2）相關(guān)系數(shù)用兩變量夾角來衡量二者的相似程度。顯然：當(dāng)i=j時(shí)，cij(2)=1，表明兩變量完全相似；|cij(2)|1對(duì)數(shù)據(jù)作標(biāo)準(zhǔn)化處理后的夾角余弦：生物信息學(xué)2.3聚類分析方法之一：譜系聚類法(hierachicalclusteranalysis)植物形態(tài)分類問題根據(jù)植物種類間形態(tài)的相似程度，得到按相似性大小組合的譜系關(guān)系譜系聚類法基因聚類問題根據(jù)DNA芯片獲得的基因表達(dá)比的相似程度，得到按相似性大小組合的譜系關(guān)系物種基因分類問題根據(jù)不同物種某一基因序列的相似程度，得到按相似性大小組合的譜系關(guān)系生物信息學(xué)X1X2X3X4X5X6X1X2X4X3X5X6譜系關(guān)系圖生物信息學(xué)X1…Xj…XnX(1)x11…x1j…x1n………X(i)xi1…xij…xin…………X(t)xt1…xtj…xtn條件：已知樣本數(shù)目為t，每個(gè)樣本測(cè)得n項(xiàng)屬性指標(biāo)，得到觀察數(shù)據(jù)xij(i=1,…,t;j=1,…,n)。目的：給出t樣本的譜系聚類關(guān)系。數(shù)學(xué)問題生物信息學(xué)2.3.1基本思想和步驟譜系聚類法的基本步驟對(duì)數(shù)據(jù)進(jìn)行變換；定義樣品間的距離（如歐氏距離）、類別之間的距離（如最短距離）；首先將t個(gè)樣品各自視為一類：得到初始的分類G(1)（含有t類），計(jì)算t個(gè)樣品兩兩之間的距離，它們等價(jià)于初始的類間距離，得到初始的距離矩陣D(1)

；將距離最近的兩類合并為一新類，得到新的分類G(2)（含有t-1類），并計(jì)算新類與其它類的類間距離，得到新的類間距離矩陣D(2)

，再按照最小距離準(zhǔn)則并類，得到G(3)（含有t-2類）、D(3),…。直到所有樣品都并成一類；畫出譜系聚類圖，決定分類的個(gè)數(shù)及各類的成員。生物信息學(xué)譜系聚類法舉例已知：根據(jù)5種靈長類動(dòng)物朊粒蛋白的氨基酸序列比較，得到它們之間的距離矩陣（已經(jīng)過數(shù)據(jù)變換處理）。X(1)：Gibbon（長臂猿）；X(2)：Symphalangus（猩猩）；X(3)

：Human（人）；X(4)

：Gorilla（大猩猩）；X(5)

：Chimpanzee（黑猩猩）構(gòu)造：樣品間距離——?dú)W氏距離；類間距離——最短距離；X(1)X(2)X(3)X(4)X(5)X(1)013.557X(2)02.546X(3)01.53.5X(4)02X(5)0生物信息學(xué)Step15個(gè)物種各自構(gòu)成1類，得到5類，有：初始分類G(1)={X(i)}(i=1,2,3,4,5)初始類別數(shù)目m=5初始類間距離矩陣D(1)X(1)X(2)X(3)X(4)X(5)X(1)013.557X(2)02.546X(3)01.53.5X(4)02X(5)0D(1)C(4)生物信息學(xué)X(3)X(4)X(5)C(4)X(3)01.53.52.5X(4)024X(5)06C(4)0Step2由D(1)知，合并X(1)和X(2)為一新類C(4)={X(1),X(2)}，有：新的G(2)={X(3),

X(4),

X(5),

C(4)}新的類別數(shù)目m=4新的類間距離矩陣D(2)D(2)C(3)生物信息學(xué)Step3由D(2)知，合并X(3)和X(4)為一新類C(3)={X(3),X(4)}，有：新的G(3)={

X(5),

C(4),

C(3)}新的類別數(shù)目m=3新的類間距離矩陣D(3)X(5)C(4)C(3)X(5)062C(4)02.5C(3)0D(3)C(2)生物信息學(xué)Step4由D(3)知，合并X(5)和C(3)為一新類C(2)={X(5),C(3)}，有：新的G(4)={C(4),

C(2)}新的類別數(shù)目m=2新的類間距離矩陣D(4)C(4)C(2)C(4)02.5C(2)0D(4)C(1)生物信息學(xué)Step5由D(4)知，最后合并C(4)和C(2)為一新類C(1)={C(4),C(2)}，有：新的G(5)={C(4),

C(2)}新的類別數(shù)目m=1新的類間距離矩陣D(5)C(1)C(1)0D(5)生物信息學(xué)X(1)X(2)X(3)X(4)X(5)Step6畫譜系聚類圖1230GibbonSymphalangusHumanGorillaChimpanzee生物信息學(xué)Step7確定類別的數(shù)目以及各類的成員。X(1)X(2)X(3)X(4)X(5)1230GibbonSymphalangusHumanGorillaChimpanzee生物信息學(xué)2.3.2類間距離的定義影響聚類結(jié)果的主要因素樣品間距離的定義dij類間距離的定義Dij用Gp和Gq表示兩個(gè)類，它們所包含的樣品數(shù)目分別為tp和tq，類Gp和Gq之間的距離用Dpq表示。生物信息學(xué)1）最短距離定義：Gp和Gq中最鄰近的兩個(gè)樣品的距離為這兩個(gè)類之間的距離。討論（遞推公式）：設(shè)Gr是由Gp和Gq合并得到的新類，考慮Gr與Gs（s

p,q）的類間距離（最短距離）Drs

，有：生物信息學(xué)2）最長距離定義：Gp和Gq中相距最遠(yuǎn)的兩個(gè)樣品的距離為這兩個(gè)類之間的距離。討論（遞推公式）：設(shè)Gr是由Gp和Gq合并得到的新類，考慮Gr與Gs（s

p,q）的類間距離（最長距離）Drs

，有：生物信息學(xué)3）類平均距離定義：用Gp和Gq中每兩兩樣品間平方距離的平均值作為兩個(gè)類之間的距離。討論（遞推公式）：設(shè)Gr是由Gp和Gq合并得到的新類，考慮Gr與Gs（s

p,q）的類間距離（類平均距離）Drs

，有：生物信息學(xué)4）幾何中心距離定義：用Gp和Gq兩類幾何中心的距離為兩個(gè)類之間的距離。討論（遞推公式）：設(shè)Gr是由Gp和Gq合并得到的新類，考慮Gr與Gs（s

p,q）的類間距離（幾何中心距離）Drs

，有：生物信息學(xué)2.3.3類別數(shù)目的確定1）由臨界值確定問題：譜系聚類圖僅僅反映樣品間的親疏、遠(yuǎn)近關(guān)系，本身并沒有給出分類關(guān)系。X(1)X(2)X(3)X(4)X(5)120Dcr1Dcr2Dcr3Dcr4Dcr5生物信息學(xué)2）由數(shù)據(jù)散點(diǎn)圖直觀確定二維散點(diǎn)圖三維散點(diǎn)圖高維散點(diǎn)圖3）由統(tǒng)計(jì)量確定（略）生物信息學(xué)4）確定類別數(shù)目的基本原則1、各類幾何中心之間的距離應(yīng)該盡可能地大；2、確定的類中，各類所包含的元素不宜太多；3、類別數(shù)目應(yīng)該符合實(shí)用目的；4、若采用幾種不同的聚類方法，在不同的譜系聚類圖中應(yīng)該發(fā)現(xiàn)相同的類。生物信息學(xué)2.4聚類分析方法之二：動(dòng)態(tài)聚類法靜態(tài)：一次分類計(jì)算量大不適合處理大樣本問題譜系聚類法動(dòng)態(tài)：逐步分類計(jì)算量較小適合處理大樣本問題動(dòng)態(tài)聚類法基本思想首先粗略分類，然后按照某種最優(yōu)原則修改不合理的分類，直至分類合理。生物信息學(xué)選取聚類種子點(diǎn)(Clusterseeds)初始分類分類是否合理？修改分類最終分類是否動(dòng)態(tài)聚類法的基本過程生物信息學(xué)2.4.1選取聚類種子點(diǎn)聚類種子點(diǎn)（Clusterseeds）：準(zhǔn)備形成類的中心，是一批有代表性的點(diǎn)。聚類種子點(diǎn)選取的重要性：直接決定初始分類初始分類的重要性：影響最終分類結(jié)果生物信息學(xué)（2）人為分類、選取幾何中心條件：對(duì)所分類問題有一定的了解根據(jù)經(jīng)驗(yàn)，預(yù)先將數(shù)據(jù)人為地分為k類，計(jì)算每一類的幾何中心，選取這些中心作為聚類種子點(diǎn)。（1）人為選擇條件：對(duì)所分類問題有一定的了解根據(jù)經(jīng)驗(yàn)，預(yù)先確定分類的數(shù)目、初始分類，并從每類中選擇有代表性的一個(gè)點(diǎn)作為種子點(diǎn)。生物信息學(xué)（3）密度法以d(d>0)為半徑，以某個(gè)樣品X為球心，落在小球內(nèi)的全部樣品數(shù)就是樣本X的密度。計(jì)算所有樣品點(diǎn)的密度，首先選取密度最大的樣品點(diǎn)作為第一種子點(diǎn)；在所有與第一種子點(diǎn)距離大于D(一般D=2d)的樣品點(diǎn)中，選取密度最大的樣品點(diǎn)作為第二種子點(diǎn)；在所有與第一、第二種子點(diǎn)距離大于D的樣品點(diǎn)中，選取密度最大的樣品點(diǎn)作為第三種子點(diǎn)；依次考察全部樣品點(diǎn)，得到全部聚類種子點(diǎn)。半徑d的選擇要合理生物信息學(xué)（4）選取總體幾何中心首先以所有樣品的幾何中心為第一種子點(diǎn)。然后依次考察每個(gè)樣品點(diǎn)，若某一點(diǎn)與已有種子點(diǎn)距離均大于d值，則選取該點(diǎn)為新的種子點(diǎn)。（5）隨機(jī)選取隨機(jī)選取聚類種子點(diǎn)。假設(shè)分為k類，則用前k個(gè)樣品作為聚類種子點(diǎn)。生物信息學(xué)2.4.2確定初始分類（1）人為分類條件：對(duì)所分類問題有一定的了解根據(jù)經(jīng)驗(yàn)，預(yù)先確定分類的數(shù)目、初始分類。（2）最近距離歸類條件：已經(jīng)選定聚類種子點(diǎn)選定聚類種子點(diǎn)后，每個(gè)樣品點(diǎn)按照與其距離最近的種子點(diǎn)分類。生物信息學(xué)（3）動(dòng)態(tài)調(diào)整種子點(diǎn)選定初始聚類種子點(diǎn)后，依次將每個(gè)樣品點(diǎn)歸入與其距離最近的種子點(diǎn)所在的類，并重新計(jì)算該類的幾何中心，以中心代替該類的種子點(diǎn)。直到考察完所有的樣品點(diǎn)。（4）部分抽樣分類樣本量太大時(shí)：抽取部分樣本，按照前面幾種方法得到初始分類。生物信息學(xué)2.4.3按批修改動(dòng)態(tài)聚類法基本步驟(1).選擇聚類種子點(diǎn)，選定距離的定義；(2).將所有樣品點(diǎn)按照最近距離原則歸入種子點(diǎn)所在的類；(3).計(jì)算每一類的幾何中心，將幾何中心點(diǎn)作為新的聚類種子點(diǎn)；(4).對(duì)所有樣品點(diǎn)按照最近距離原則重新歸類；(5).轉(zhuǎn)到(3)，若聚類種子點(diǎn)與前一次聚類種子點(diǎn)重合，或者滿足給定的收斂條件，迭代過程結(jié)束。生物信息學(xué)分類函數(shù)與修改原則修改原則：使分類函數(shù)的值達(dá)到最小。假設(shè)全部t個(gè)樣品點(diǎn)為X(i)(i=1,2,…,t)，初始分為k類：G(1),G(2),…,G(k)，每類樣品點(diǎn)數(shù)為ti

(i=1,2,…,k)。用n(i)表示樣品點(diǎn)X(i)到所屬類的標(biāo)號(hào)，則分類函數(shù)定義為：分類函數(shù)實(shí)際上就是離差平方和。生物信息學(xué)例1.04.05.07.011.0X(1)X(2)X(3)X(4)X(5)（1）用密度法選取聚類種子點(diǎn)：取d=2,D=2d=4；采用歐氏距離X(1)X(2)X(3)X(4)X(5)密度12321得到第一種子點(diǎn)：X(3)

第二種子點(diǎn)：X(1)

第三種子點(diǎn)：X(5)生物信息學(xué)（2）初始分類：按照最小距離原則將所有樣品點(diǎn)歸類。結(jié)果是（3）修改分類：首先計(jì)算各類的幾何中心：5.333，1.0，11.0以它們作新的聚類種子點(diǎn)，按照最小距離原則重新歸類：再次計(jì)算各類的幾何中心：5.333，1.0，11.0與前一次重合，迭代過程終止。生物信息學(xué)（4）最終分類：1.04.05.07.011.0X(1)X(2)X(3)X(4)X(5)生物信息學(xué)2.4.4、k-means法（逐點(diǎn)修改動(dòng)態(tài)聚類法）基本步驟(1).給定3個(gè)參數(shù)：

K——分類的數(shù)目（初步估計(jì)）

Dmin——類間距離的最小值

dmax——類內(nèi)樣品點(diǎn)距離的最大值(2).選擇聚類種子點(diǎn)

通常選擇前K個(gè)樣品點(diǎn)作為聚類種子點(diǎn)或者選取有代表性的K個(gè)樣品點(diǎn)作為聚類種子點(diǎn)生物信息學(xué)(3).調(diào)整聚類種子點(diǎn)

計(jì)算這K個(gè)種子點(diǎn)兩兩之間的距離：將距離小于Dmin的兩個(gè)種子點(diǎn)合并，以它們的中心點(diǎn)作為新的種子點(diǎn)；保證所有的種子點(diǎn)兩兩之間距離大于或等于Dmin。(4).逐點(diǎn)調(diào)整將剩下的t－K個(gè)樣品點(diǎn)逐個(gè)歸類：若某樣品與所有種子點(diǎn)的距離均大于dmax

，則將該樣品點(diǎn)視為新的聚類種子點(diǎn)添加進(jìn)來；否則，歸為與之距離最近的種子點(diǎn)所在類別，同時(shí)計(jì)算該類的幾何中心，以中心點(diǎn)作為新的聚類種子點(diǎn)；返回（3），調(diào)整聚類種子點(diǎn)，保證所有的種子點(diǎn)兩兩之間距離大于或等于Dmin?？紤]下一個(gè)樣品點(diǎn)。生物信息學(xué)(5).對(duì)所有樣品點(diǎn)重新歸類將所有樣品點(diǎn)重新逐個(gè)歸類：若某樣品的分類與原來不同，則要重新計(jì)算它所涉及的兩類的幾何中心，并調(diào)整它們的聚類種子點(diǎn)。然后調(diào)整所有的聚類種子點(diǎn)，保證所有的種子點(diǎn)兩兩之間距離大于或等于Dmin。(6)