建模培訓(xùn)講座第四講聚類分析及

第一頁，共一百一十八頁，2022年，8月28日第一節(jié)引言“物以類聚，人以群分”。對事物進(jìn)行分類，是人們認(rèn)識(shí)事物的出發(fā)點(diǎn)，也是人們認(rèn)識(shí)世界的一種重要方法。因此，分類學(xué)已成為人們認(rèn)識(shí)世界的一門基礎(chǔ)科學(xué)。在生物、經(jīng)濟(jì)、社會(huì)、人口等領(lǐng)域的研究中，存在著大量量化分類研究。例如：在生物學(xué)中，為了研究生物的演變，生物學(xué)家需要根據(jù)各種生物不同的特征對生物進(jìn)行分類。在經(jīng)濟(jì)研究中，為了研究不同地區(qū)城鎮(zhèn)居民生活中的收入和消費(fèi)情況，往往需要?jiǎng)澐植煌念愋腿パ芯?。在地質(zhì)學(xué)中，為了研究礦物勘探，需要根據(jù)各種礦石的化學(xué)和物理性質(zhì)和所含化學(xué)成分把它們歸于不同的礦石類。在人口學(xué)研究中，需要構(gòu)造人口生育分類模式、人口死亡分類狀況，以此來研究人口的生育和死亡規(guī)律。第二頁，共一百一十八頁，2022年，8月28日但歷史上這些分類方法多半是人們主要依靠經(jīng)驗(yàn)作定性分類，致使許多分類帶有主觀性和任意性，不能很好地揭示客觀事物內(nèi)在的本質(zhì)差別與聯(lián)系；特別是對于多因素、多指標(biāo)的分類問題，定性分類的準(zhǔn)確性不好把握。為了克服定性分類存在的不足，人們把數(shù)學(xué)方法引入分類中，形成了數(shù)值分類學(xué)。后來隨著多元統(tǒng)計(jì)分析的發(fā)展，從數(shù)值分類學(xué)中逐漸分離出了聚類分析方法。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，利用數(shù)學(xué)方法研究分類不僅非常必要而且完全可能，因此近年來，聚類分析的理論和應(yīng)用得到了迅速的發(fā)展。聚類分析就是分析如何對樣品（或變量）進(jìn)行量化分類的問題。通常聚類分析分為Q型聚類和R型聚類。Q型聚類是對樣品進(jìn)行分類處理，R型聚類是對變量進(jìn)行分類處理。第三頁，共一百一十八頁，2022年，8月28日第二節(jié)相似性的量度

一樣品相似性的度量

二變量相似性的度量

第四頁，共一百一十八頁，2022年，8月28日一、樣品相似性的度量在聚類之前，要首先分析樣品間的相似性。Q型聚類分析，常用距離來測度樣品之間的相似程度。每個(gè)樣品有p個(gè)指標(biāo)（變量）從不同方面描述其性質(zhì)，形成一個(gè)p維的向量。如果把n個(gè)樣品看成p維空間中的n個(gè)點(diǎn)，則兩個(gè)樣品間相似程度就可用p維空間中的兩點(diǎn)距離公式來度量。兩點(diǎn)距離公式可以從不同角度進(jìn)行定義，令dij

表示樣品Xi與Xj的距離，存在以下的距離公式：

1．明考夫斯基距離

(5.1)

明考夫斯基距離簡稱明氏距離，按的取值不同又可分成：第五頁，共一百一十八頁，2022年，8月28日第六頁，共一百一十八頁，2022年，8月28日歐氏距離是常用的距離，大家都比較熟悉，但是前面已經(jīng)提到，在解決多元數(shù)據(jù)的分析問題時(shí)，歐氏距離就顯示出了它的不足之處。一是它沒有考慮到總體的變異對“距離”遠(yuǎn)近的影響，顯然一個(gè)變異程度大的總體可能與更多樣品近些，既使它們的歐氏距離不一定最近；另外，歐氏距離受變量的量綱影響，這對多元數(shù)據(jù)的處理是不利的。為了克服這方面的不足，可用“馬氏距離”的概念。第七頁，共一百一十八頁，2022年，8月28日

2．馬氏距離設(shè)Xi與Xj是來自均值向量為，協(xié)方差為∑

=（＞0）的總體

G中的p維樣品，則兩個(gè)樣品間的馬氏距離為

(5.5)

馬氏距離又稱為廣義歐氏距離。顯然，馬氏距離與上述各種距離的主要不同就是它考慮了觀測變量之間的相關(guān)性。如果各變量之間相互獨(dú)立，即觀測變量的協(xié)方差矩陣是對角矩陣，則馬氏距離就退化為用各個(gè)觀測指標(biāo)的標(biāo)準(zhǔn)差的倒數(shù)作為權(quán)數(shù)的加權(quán)歐氏距離。馬氏距離還考慮了觀測變量之間的變異性，不再受各指標(biāo)量綱的影響。將原始數(shù)據(jù)作線性變換后，馬氏距離不變。第八頁，共一百一十八頁，2022年，8月28日

3．蘭氏距離

(5.6)

它僅適用于一切Xij>0的情況，這個(gè)距離也可以克服各個(gè)指標(biāo)之間量綱的影響。這是一個(gè)自身標(biāo)準(zhǔn)化的量，由于它對大的奇異值不敏感，它特別適合于高度偏倚的數(shù)據(jù)。雖然這個(gè)距離有助于克服明氏距離的第一個(gè)缺點(diǎn)，但它也沒有考慮指標(biāo)之間的相關(guān)性。第九頁，共一百一十八頁，2022年，8月28日

4．距離選擇的原則一般說來，同一批數(shù)據(jù)采用不同的距離公式，會(huì)得到不同的分類結(jié)果。產(chǎn)生不同結(jié)果的原因，主要是由于不同的距離公式的側(cè)重點(diǎn)和實(shí)際意義都有不同。因此我們在進(jìn)行聚類分析時(shí)，應(yīng)注意距離公式的選擇。通常選擇距離公式應(yīng)注意遵循以下的基本原則：（1）要考慮所選擇的距離公式在實(shí)際應(yīng)用中有明確的意義。如歐氏距離就有非常明確的空間距離概念。馬氏距離有消除量綱影響的作用。（2）要綜合考慮對樣本觀測數(shù)據(jù)的預(yù)處理和將要采用的聚類分析方法。如在進(jìn)行聚類分析之前已經(jīng)對變量作了標(biāo)準(zhǔn)化處理，則通常就可采用歐氏距離。（3）要考慮研究對象的特點(diǎn)和計(jì)算量的大小。樣品間距離公式的選擇是一個(gè)比較復(fù)雜且?guī)в幸欢ㄖ饔^性的問題，我們應(yīng)根據(jù)研究對象的特點(diǎn)不同做出具體分折。實(shí)際中，聚類分析前不妨試探性地多選擇幾個(gè)距離公式分別進(jìn)行聚類，然后對聚類分析的結(jié)果進(jìn)行對比分析，以確定最合適的距離測度方法。第十頁，共一百一十八頁，2022年，8月28日二、變量相似性的度量多元數(shù)據(jù)中的變量表現(xiàn)為向量形式，在幾何上可用多維空間中的一個(gè)有向線段表示。在對多元數(shù)據(jù)進(jìn)行分析時(shí)，相對于數(shù)據(jù)的大小，我們更多地對變量的變化趨勢或方向感興趣。因此，變量間的相似性，我們可以從它們的方向趨同性或“相關(guān)性”進(jìn)行考察，從而得到“夾角余弦法”和“相關(guān)系數(shù)”兩種度量方法。

1、夾角余弦 兩變量Xi與Xj看作p維空間的兩個(gè)向量，這兩個(gè)向量間的夾角余弦可用下式進(jìn)行計(jì)算

(5.7)

顯然，∣cos

ij∣1。第十一頁，共一百一十八頁，2022年，8月28日

2．相關(guān)系數(shù) 相關(guān)系數(shù)經(jīng)常用來度量變量間的相似性。變量Xi與Xj的相關(guān)系數(shù)定義為

(5.8)

顯然也有，∣rij∣1。第十二頁，共一百一十八頁，2022年，8月28日無論是夾角余弦還是相關(guān)系數(shù)，它們的絕對值都小于1，作為變量近似性的度量工具，我們把它們統(tǒng)記為cij。當(dāng)∣cij∣

=1時(shí)，說明變量Xi與Xj完全相似；當(dāng)∣cij∣近似于1時(shí)，說 明變量Xi與Xj非常密切；當(dāng)∣cij∣=0時(shí)，說明變量Xi與Xj完 全不一樣；當(dāng)∣cij∣近似于0時(shí)，說明變量Xi與Xj差別很大。 據(jù)此，我們把比較相似的變量聚為一類，把不太相似的變量歸到不同的類內(nèi)。在實(shí)際聚類過程中，為了計(jì)算方便，我們把變量間相似性的度量公式作一個(gè)變換為

dij

=1∣cij∣(5.9)

或者

dij2

=1cij2(5.10)

用表示變量間的距離遠(yuǎn)近，小則與先聚成一類，這比較符合人們的一般思維習(xí)慣。第十三頁，共一百一十八頁，2022年，8月28日第三節(jié)系統(tǒng)聚類分析法

一系統(tǒng)聚類的基本思想

二類間距離與系統(tǒng)聚類法

三類間距離的統(tǒng)一性

第十四頁，共一百一十八頁，2022年，8月28日一、系統(tǒng)聚類的基本思想系統(tǒng)聚類的基本思想是：距離相近的樣品（或變量）先聚成類，距離相遠(yuǎn)的后聚成類，過程一直進(jìn)行下去，每個(gè)樣品（或變量）總能聚到合適的類中。系統(tǒng)聚類過程是：假設(shè)總共有n個(gè)樣品（或變量），第一步將每個(gè)樣品（或變量）獨(dú)自聚成一類，共有n類；第二步根據(jù)所確定的樣品（或變量）“距離”公式，把距離較近的兩個(gè)樣品（或變量）聚合為一類，其它的樣品（或變量）仍各自聚為一類，共聚成n

1類；第三步將“距離”最近的兩個(gè)類進(jìn)一步聚成一類，共聚成n

2類；……，以上步驟一直進(jìn)行下去，最后將所有的樣品（或變量）全聚成一類。為了直觀地反映以上的系統(tǒng)聚類過程，可以把整個(gè)分類系統(tǒng)畫成一張譜系圖。所以有時(shí)系統(tǒng)聚類也稱為譜系分析。除系統(tǒng)聚類法外，還有有序聚類法、動(dòng)態(tài)聚類法、圖論聚類法、模糊聚類法等，限于篇幅，我們只介紹系統(tǒng)聚類方法。第十五頁，共一百一十八頁，2022年，8月28日二、類間距離與系統(tǒng)聚類法在進(jìn)行系統(tǒng)聚類之前，我們首先要定義類與類之間的距離，由類間距離定義的不同產(chǎn)生了不同的系統(tǒng)聚類法。常用的類間距離定義有8種之多，與之相應(yīng)的系統(tǒng)聚類法也有8種，分別為最短距離法、最長距離法、中間距離法、重心法、類平均法、可變類平均法、可變法和離差平方和法。它們的歸類步驟基本上是一致的，主要差異是類間距離的計(jì)算方法不同。以下用dij表示樣品Xi與Xj之間距離，用Dij表示類Gi與Gj

之間的距離。第十六頁，共一百一十八頁，2022年，8月28日

1.最短距離法 定義類與之間的距離為兩類最近樣品的距離，即為

(5.11)

設(shè)類與合并成一個(gè)新類記為，則任一類與的距離為

(5.12)第十七頁，共一百一十八頁，2022年，8月28日最短距離法進(jìn)行聚類分析的步驟如下： （1）定義樣品之間距離，計(jì)算樣品的兩兩距離，得一距離陣記為D（0）

，開始每個(gè)樣品自成一類，顯然這時(shí)Dij

=

dij。 （2）找出距離最小元素，設(shè)為Dpq，則將Gp和Gq合并成一個(gè) 新類，記為Gr，即Gr

=

｛Gp，Gq｝。 （3）按（5.12）計(jì)算新類與其它類的距離。（4）重復(fù)（2）、（3）兩步，直到所有元素。并成一類為止。如果某一步距離最小的元素不止一個(gè)，則對應(yīng)這些最小元素的類可以同時(shí)合并。第十八頁，共一百一十八頁，2022年，8月28日【例5.1】設(shè)有六個(gè)樣品，每個(gè)只測量一個(gè)指標(biāo)，分別是1，2，5，7，9，10，試用最短距離法將它們分類。 （1）樣品采用絕對值距離，計(jì)算樣品間的距離陣D（0），見表5.1表5.1第十九頁，共一百一十八頁，2022年，8月28日 （2）D（0）中最小的元素是D12＝D56＝1，于是將G1和G2合 并成G7，G5和G6合并成G8，并利用（5.12）式計(jì)算新類與其 它類的距離D（1），見表5.2表5.2第二十頁，共一百一十八頁，2022年，8月28日 （3）在D（1）中最小值是D34＝D48＝2，由于G4與G3合并， 又與G8合并，因此G3、G4、G8合并成一個(gè)新類G9，其與其 它類的距離D（2），見表5.3表5.3第二十一頁，共一百一十八頁，2022年，8月28日 （4）最后將G7和G9合并成G10，這時(shí)所有的六個(gè)樣品聚為一類，其過程終止。 上述聚類的可視化過程見圖5.1所示，橫坐標(biāo)的刻度表示并類的距離。這里我們應(yīng)該注意，聚類的個(gè)數(shù)要以實(shí)際情況所定，其詳細(xì)內(nèi)容將在后面討論。圖5.1最短距離聚類法的過程第二十二頁，共一百一十八頁，2022年，8月28日第二十三頁，共一百一十八頁，2022年，8月28日再找距離最小兩類并類，直至所有的樣品全歸為一類為止。可以看出最長距離法與最短距離法只有兩點(diǎn)不同：一是類與類之間的距離定義不同；另一是計(jì)算新類與其它類的距離所用的公式不同。第二十四頁，共一百一十八頁，2022年，8月28日

3.中間距離法 最短、最長距離定義表示都是極端情況，我們定義類間距離可以既不采用兩類之間最近的距離也不采用兩類之間最遠(yuǎn)的距離，而是采用介于兩者之間的距離，稱為中間距離法。 中間距離將類Gp與Gq類合并為類Gr，則任意的類Gk和Gr的距離公式為

(1／40)(5.15)

設(shè)Dkq＞Dkp，如果采用最短距離法，則Dkr

=

Dkp，如果采用 最長距離法，則Dkr

=

Dkq。如圖5.2所示，(5.15)式就是取它們（最長距離與最短距離）的中間一點(diǎn)作為計(jì)算Dkr的根據(jù)。第二十五頁，共一百一十八頁，2022年，8月28日特別當(dāng)

=

1／4，它表示取中間點(diǎn)算距離，公式為

(5.16)

圖5.2中間距離法第二十六頁，共一百一十八頁，2022年，8月28日第二十七頁，共一百一十八頁，2022年，8月28日

第二十八頁，共一百一十八頁，2022年，8月28日第二十九頁，共一百一十八頁，2022年，8月28日

第三十頁，共一百一十八頁，2022年，8月28日【例5.2】針對例5.1的數(shù)據(jù)，試用重心法將它們聚類。（1）樣品采用歐氏距離，計(jì)算樣品間的平方距離陣D2（0），見表5.4所示。表5.4第三十一頁，共一百一十八頁，2022年，8月28日 （2）D2（0）中最小的元素是D212＝D256＝1，于是將G1和G2合 并成G7，G5和G6合并成G8，并利用（5.18）式計(jì)算新類與 其它類的距離得到距離陣D2（1），見表5.5： 其中， 其它結(jié)果類似可以求得第三十二頁，共一百一十八頁，2022年，8月28日 （3）在D2（1）中最小值是D234＝4，那么G3與G4合并一個(gè)新類G9，其與與其它類的距離D2（2），見表5.6：表5.6第三十三頁，共一百一十八頁，2022年，8月28日 （4）在中最小值是＝12.5，那么與合并一個(gè)新類，其與與 其它類的距離，見表5.7：表5.7第三十四頁，共一百一十八頁，2022年，8月28日（5）最后將G7和G10合并成G11，這時(shí)所有的六個(gè)樣品聚為一類，其過程終止。 上述重心法聚類的可視化過程見圖5.3所示，橫坐標(biāo)的刻度表示并類的距離。圖5.3重心聚類法的過程第三十五頁，共一百一十八頁，2022年，8月28日第三十六頁，共一百一十八頁，2022年，8月28日

6.可變類平均法 由于類平均法中沒有反映出Gp和Gq之間的距離Dpq的影響， 因此將類平均法進(jìn)一步推廣，如果將Gp和Gq合并為新類Gr，類Gk與新并類Gr的距離公式為： （5.22） 其中是可變的且<1，稱這種系統(tǒng)聚類法為可變類平均法。第三十七頁，共一百一十八頁，2022年，8月28日第三十八頁，共一百一十八頁，2022年，8月28日

8.離差平方和法 該方法是Ward提出來的，所以又稱為Ward法。該方法的基本思想來自于方差分析，如果分類正確，同類樣品的離差平方和應(yīng)當(dāng)較小，類與類的離差平方和較大。具體做法是先將n個(gè)樣品各自成一類，然后每次縮小一類，每縮小一類，離差平方和就要增大，選擇使方差增加最小的兩類合并，直到所有的樣品歸為一類為止。 設(shè)將n個(gè)樣品分成k類G1，G2，…，Gk，用Xit表示Gt中的第I

個(gè)樣品，nt表示Gt中樣品的個(gè)數(shù)，是Gt的重心，則Gt的樣品離差平方和為第三十九頁，共一百一十八頁，2022年，8月28日

第四十頁，共一百一十八頁，2022年，8月28日

這種系統(tǒng)聚類法稱為離差平方和法或Ward方法。下面論證離差平方和法的距離遞推（5.26）式。第四十一頁，共一百一十八頁，2022年，8月28日由于第四十二頁，共一百一十八頁，2022年，8月28日第四十三頁，共一百一十八頁，2022年，8月28日

第四十四頁，共一百一十八頁，2022年，8月28日第四十五頁，共一百一十八頁，2022年，8月28日三、類間距離的統(tǒng)一性上述八種系統(tǒng)聚類法的步驟完全一樣，只是距離的遞推公式不同。蘭斯（Lance）和威廉姆斯（Williams）于1967年給出了一個(gè)統(tǒng)一的公式。

(5.28)

其中ap、aq、、是參數(shù)，不同的系統(tǒng)聚類法，它們?nèi)〔?同的數(shù)，詳見表5.8。這里應(yīng)該注意，不同的聚類方法結(jié)果不一定完全相同，一般只是大致相似。如果有很大的差異，則應(yīng)該仔細(xì)考查，找到問題所在；另外，可將聚類結(jié)果與實(shí)際問題對照，看哪一個(gè)結(jié)果更符合經(jīng)驗(yàn)。第四十六頁，共一百一十八頁，2022年，8月28日表5.8系統(tǒng)聚類法參數(shù)表第四十七頁，共一百一十八頁，2022年，8月28日第四節(jié)K均值聚類分析系統(tǒng)聚類法需要計(jì)算出不同樣品或變量的距離，還要在聚類的每一步都要計(jì)算“類間距離”，相應(yīng)的計(jì)算量自然比較大；特別是當(dāng)樣本的容量很大時(shí)，需要占據(jù)非常大的計(jì)算機(jī)內(nèi)存空間，這給應(yīng)用帶來一定的困難。而K—均值法是一種快速聚類法，采用該方法得到的結(jié)果比較簡單易懂，對計(jì)算機(jī)的性能要求不高，因此應(yīng)用也比較廣泛。K均值法是麥奎因（MacQueen，1967）提出的，這種算法的基本思想是將每一個(gè)樣品分配給最近中心（均值）的類中，具體的算法至少包括以下三個(gè)步驟：

1．將所有的樣品分成K個(gè)初始類；

2．通過歐氏距離將某個(gè)樣品劃入離中心最近的類中，并對獲得樣品與失去樣品的類，重新計(jì)算中心坐標(biāo)；

3．重復(fù)步驟2，直到所有的樣品都不能再分配時(shí)為止。第四十八頁，共一百一十八頁，2022年，8月28日K均值法和系統(tǒng)聚類法一樣，都是以距離的遠(yuǎn)近親疏為標(biāo)準(zhǔn)進(jìn)行聚類的，但是兩者的不同之處也是明顯的：系統(tǒng)聚類對不同的類數(shù)產(chǎn)生一系列的聚類結(jié)果，而K—均值法只能產(chǎn)生指定類數(shù)的聚類結(jié)果。具體類數(shù)的確定，離不開實(shí)踐經(jīng)驗(yàn)的積累；有時(shí)也可以借助系統(tǒng)聚類法以一部分樣品為對象進(jìn)行聚類，其結(jié)果作為K—均值法確定類數(shù)的參考。下面通過一個(gè)具體問題說明K均值法的計(jì)算過程。第四十九頁，共一百一十八頁，2022年，8月28日【例5.3】假定我們對A、B、C、D四個(gè)樣品分別測量兩個(gè)變量和得到結(jié)果見表5.9。 試將以上的樣品聚成兩類。表5.9樣品測量結(jié)果第五十頁，共一百一十八頁，2022年，8月28日 第一步：按要求取K=2，為了實(shí)施均值法聚類，我們將這些樣品隨意分成兩類，比如（A、B）和（C、D），然后計(jì)算這兩個(gè)聚類的中心坐標(biāo)，見表5.10所示。 表5.10中的中心坐標(biāo)是通過原始數(shù)據(jù)計(jì)算得來的，比如（A、

B）類的，等等。表5.10中心坐標(biāo)第五十一頁，共一百一十八頁，2022年，8月28日 第二步：計(jì)算某個(gè)樣品到各類中心的歐氏平方距離，然后將該樣品分配給最近的一類。對于樣品有變動(dòng)的類，重新計(jì)算它們的中心坐標(biāo)，為下一步聚類做準(zhǔn)備。先計(jì)算A到兩個(gè)類的平方距離： 由于A到（A、B）的距離小于到（C、D）的距離，因此A不用重新分配。計(jì)算B到兩類的平方距離：第五十二頁，共一百一十八頁，2022年，8月28日由于B到（A、B）的距離大于到（C、D）的距離，因此B要分配給（C、D）類，得到新的聚類是（A）和（B、C、D）。更新中心坐標(biāo)如表5.11所示。表5.11更新后的中心坐標(biāo)第五十三頁，共一百一十八頁，2022年，8月28日第三步：再次檢查每個(gè)樣品，以決定是否需要重新分類。計(jì)算各樣品到各中心的距離平方，得結(jié)果見表5.12。到現(xiàn)在為止，每個(gè)樣品都已經(jīng)分配給距離中心最近的類，因此聚類過程到此結(jié)束。最終得到K=2的聚類結(jié)果是A獨(dú)自成一類，B、C、D聚成一類。表5.12樣品聚類結(jié)果第五十四頁，共一百一十八頁，2022年，8月28日第五節(jié)有序樣品的聚類分析法

一有序樣品可能的分類數(shù)目

二費(fèi)希爾最優(yōu)求解法三一個(gè)典型例子第五十五頁，共一百一十八頁，2022年，8月28日以上的系統(tǒng)聚類和K—均值聚類中，樣品的地位是彼此獨(dú)立的，沒有考慮樣品的次序。但在實(shí)際應(yīng)用中，有時(shí)樣品的次序是不能變動(dòng)的，這就產(chǎn)生了有序樣品的聚類分析問題。例如對動(dòng)植物按生長的年齡段進(jìn)行分類，年齡的順序是不能改變的，否則就沒有實(shí)際意義了；又例如在地質(zhì)勘探中，需要通過巖心了解地層結(jié)構(gòu)，此時(shí)按深度順序取樣，樣品的次序也不能打亂。如果用X（1），

X（2），

…，X（n）表示n個(gè)有序的樣品，則每一類必須是這樣的形式，即X（i），X（i+1)，…，X（j），其中1rn，且jn，簡記為Gi

=

｛i，i+1，…，j｝。在同一類中的樣品是次序相鄰的。這類問題稱為有序樣品的聚類分析。第五十六頁，共一百一十八頁，2022年，8月28日一、有序樣品可能的分類數(shù)目n個(gè)有序樣品分成k類，則一切可能的分法有種。實(shí)際上，n個(gè)有序樣品共有（n

1）個(gè)間隔，分成k類相當(dāng)于在這（n

1）個(gè)間隔中插入k

1根“棍子”。由于不考慮棍子的插入順序，是一個(gè)組合問題，共有種插法。 圖5.4有序樣品的分類法這就是n個(gè)有序樣品分成k類的一切可能分法。因此，對于有限的n和k，有序樣品的所有可能分類結(jié)果是有限的，可以在某種損失函數(shù)意義下，求得最優(yōu)解。所以有序樣品聚類分析又稱為最優(yōu)分割，該算法是費(fèi)希爾（Fisher）最先提出來的，故也稱之為費(fèi)希爾最優(yōu)求解法。第五十七頁，共一百一十八頁，2022年，8月28日二、費(fèi)希爾最優(yōu)求解法

第五十八頁，共一百一十八頁，2022年，8月28日第五十九頁，共一百一十八頁，2022年，8月28日這里需要注意，若要尋找將n個(gè)樣品分為k類的最優(yōu)分割，則對于任意的j（k

j

n）,先將前面j

1個(gè)樣品最優(yōu)分割為k1類，得到p（j1，k1），否則從j到n這最后一類就不可能構(gòu)成k類的最優(yōu)分割，參見圖5.6。再考慮使L[b（n，k）]最小的j＊，得到p（n，k）。因此我們得到費(fèi)希爾最優(yōu)求解法的遞推公式為（5.23）圖5.6最優(yōu)分割第六十頁，共一百一十八頁，2022年，8月28日第六十一頁，共一百一十八頁，2022年，8月28日

第六十二頁，共一百一十八頁，2022年，8月28日三、一個(gè)典型例子【例5.4】為了了解兒童的生長發(fā)育規(guī)律，今隨機(jī)抽樣統(tǒng)計(jì)了男孩從出生到11歲每年平均增長的重量數(shù)據(jù)表5.13，試問男孩發(fā)育可分為幾個(gè)階段？在分析這是一個(gè)有序樣品的聚類問題時(shí)，我們通過圖形可以看到男孩增重隨年齡順序變化的規(guī)律，從圖5.6中發(fā)現(xiàn)男孩發(fā)育確實(shí)可以分為幾個(gè)階段。表5.131－11歲兒童每年平均增長的重量第六十三頁，共一百一十八頁，2022年，8月28日圖5.7兒童成長階段分析第六十四頁，共一百一十八頁，2022年，8月28日下面通過有序樣品的聚類分析確定男孩發(fā)育分成幾個(gè)階段較合適。步驟如下：第六十五頁，共一百一十八頁，2022年，8月28日表5.14直徑D（i，j）

第六十六頁，共一百一十八頁，2022年，8月28日第六十七頁，共一百一十八頁，2022年，8月28日

第六十八頁，共一百一十八頁，2022年，8月28日 （3）分類個(gè)數(shù)的確定。如果能從生理角度事先確定k當(dāng)然最好；有時(shí)不能事先確定k時(shí)，可以從L[p（l，k）]隨k的變化趨勢圖中找到拐點(diǎn)處，作為確定k的根據(jù)。當(dāng)曲線拐點(diǎn)很平緩時(shí)，可選擇的k很多，這時(shí)需要用其它的辦法來確定，比如均方比和特征根法，限于篇幅此略，有興趣的讀者可以查看其它資料。本例從表5.15中的最后一行可以看出k

=3，4處有拐點(diǎn)，即分成3類或4類都是較合適的，從圖5.8中可以更明顯看出這一點(diǎn)。第六十九頁，共一百一十八頁，2022年，8月28日第七十頁，共一百一十八頁，2022年，8月28日第七十一頁，共一百一十八頁，2022年，8月28日第六節(jié)實(shí)例分析與計(jì)算機(jī)實(shí)現(xiàn)一在SAS中利用系統(tǒng)聚類法進(jìn)行聚類分析

二在SAS中利用K均值法進(jìn)行聚類分析

第七十二頁，共一百一十八頁，2022年，8月28日例為了研究遼寧等5省1991年城鎮(zhèn)居民生活消費(fèi)情況的分布規(guī)律，根據(jù)調(diào)查資料做類型分類，用最短距離做類間分類。數(shù)據(jù)如下：x1x2x3x4x5x6x7x8遼寧17.9039.778.4912.9419.2711.052.0413.29浙江27.6850.3711.3513.3019.2514.592.7514.87河南39.4227.938.208.1416.179.421.559.76甘肅49.1627.989.019.3215.999.101.8211.35青海510.0628.6410.5210.0516.188.391.9610.81第七十三頁，共一百一十八頁，2022年，8月28日將每一個(gè)省區(qū)視為一個(gè)樣本，先計(jì)算5個(gè)省區(qū)之間的歐式距離，用D0表示距離矩陣（對稱陣，故給出下三角陣）因此將3.4合并為一類，為類6，替代了3、4兩類類6與剩余的1、2、5之間的距離分別為：

d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12d(3,4)2=min(d32,d42)=min(24.63,24.06)=24.06d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21第七十四頁，共一百一十八頁，2022年，8月28日得到新矩陣合并類6和類5，得到新類7類7與剩余的1、2之間的距離分別為：

d(5,6)1=min(d51,d61)=min(12.80,13.12)=12.80d(5,6)2=min(d52,d62)=min(23.54,24.06)=23.54第七十五頁，共一百一十八頁，2022年，8月28日得到新矩陣合并類1和類2，得到新類8此時(shí)，我們有兩個(gè)不同的類：類7和類8。它們的最近距離d(7,8)

=min(d71,d72)=min(12.80,23.54)=12.80第七十六頁，共一百一十八頁，2022年，8月28日得到矩陣最后合并為一個(gè)大類。這就是按最短距離定義類間距離的系統(tǒng)聚類方法。最長距離法類似！第七十七頁，共一百一十八頁，2022年，8月28日3.重心法(CENtroidmethod)第七十八頁，共一百一十八頁，2022年，8月28日4.類平均法(AVEragemethod)第七十九頁，共一百一十八頁，2022年，8月28日中間距離第八十頁，共一百一十八頁，2022年，8月28日5.離差平方和法(WARD)基本思想來源于方差分析。它認(rèn)為：如果分類正確，同類間的類差平方和應(yīng)較小，類與類之間的離差平方和應(yīng)較大.具體做法是，先將n個(gè)樣本分成一類,然后每次縮小一類,每縮小一類離差平方和就要增大.第八十一頁，共一百一十八頁，2022年，8月28日離差平方和法(WARD)第八十二頁，共一百一十八頁，2022年，8月28日⒍系統(tǒng)聚類方法的統(tǒng)一

第八十三頁，共一百一十八頁，2022年，8月28日⒎系統(tǒng)聚類法參數(shù)表

第八十四頁，共一百一十八頁，2022年，8月28日類的個(gè)數(shù)的確定由適當(dāng)?shù)拈撝荡_定；根據(jù)數(shù)據(jù)點(diǎn)的散布直觀地確定類的個(gè)數(shù)；根據(jù)統(tǒng)計(jì)量確定分類個(gè)數(shù)；第八十五頁，共一百一十八頁，2022年，8月28日類的個(gè)數(shù)的確定根據(jù)譜系圖確定分類個(gè)數(shù)的準(zhǔn)則：各類重心間的距離必須很大；類中保包含的元素不要太多；類的個(gè)數(shù)必須符合實(shí)際應(yīng)用；如果采用幾種不同的聚類方法處理，則在各種聚類圖中應(yīng)該發(fā)現(xiàn)相同的類。第八十六頁，共一百一十八頁，2022年，8月28日四、系統(tǒng)聚類的參數(shù)選擇㈠聚類類別：㈡統(tǒng)計(jì)㈢圖：樹型譜系圖冰柱譜系圖㈣聚類方法1.Between-groupslinkage類間平均法兩類距離為兩類元素兩兩之間平均平方距離2.Within-groupslinkage類內(nèi)平均法兩類距離為合并后類中可能元素兩兩之間平均平方距離3.Nearestneighbor最短距離法4.Furthestneighbor最長距離法5.Centroidclustering重心法(歐式距離)6.Medianclustering中間距離法(歐式距離)7.WardMethod離差平方法(歐式距離)第八十七頁，共一百一十八頁，2022年，8月28日五、系統(tǒng)聚類法之例：地區(qū)按經(jīng)濟(jì)效益分類某年全國28個(gè)省區(qū)經(jīng)濟(jì)效益指標(biāo)表，演示第八十八頁，共一百一十八頁，2022年，8月28日類間平均法第八十九頁，共一百一十八頁，2022年，8月28日類內(nèi)平均法第九十頁，共一百一十八頁，2022年，8月28日最短距離法第九十一頁，共一百一十八頁，2022年，8月28日最長距離法第九十二頁，共一百一十八頁，2022年，8月28日重心法第九十三頁，共一百一十八頁，2022年，8月28日中間距離法第九十四頁，共一百一十八頁，2022年，8月28日離差平方法第九十五頁，共一百一十八頁，2022年，8月28日六、快速聚類法快速聚類法的聚類數(shù)由用戶指定，分類是唯一的。1.分類數(shù)2.聚類方法:method:iterateandclussifyclussifyonly3.聚類中心:centers4.迭代次數(shù):iterate5.保存分類結(jié)果:save第九十六頁，共一百一十八頁，2022年，8月28日8.2判別分析8.2.1判別分析的基本概念8.2.2SAS中作判別分析的過程8.2.3分析實(shí)例第九十七頁，共一百一十八頁，2022年，8月28日8.2.1判別分析的基本概念1.距離判別法距離判別的基本思想是：樣品和哪個(gè)總體的距離最近，就判斷它屬于哪個(gè)總體。(1)兩總體情況設(shè)有兩個(gè)總體G1和G2，若定義樣品x到G1和G2的距離分別為d2(x,G1)和d2(x,G2)，則距離判別的判別規(guī)則是：即未知所屬總體的樣品x離哪個(gè)總體較近，就判x屬于哪個(gè)總體。第九十八頁，共一百一十八頁，2022年，8月28日當(dāng)總體G1和G2為正態(tài)總體，距離選用馬氏距離，公式為：式中，μ1，μ2，1，2分別為總體G1和G2的均值和協(xié)差陣。當(dāng)1=2=時(shí)，可以證明：d2(x,G1)–d2(x,G2)=–2[x–(μ1+μ2)/2]'–1(μ1–μ2)第九十九頁，共一百一十八頁，2022年，8月28日令于是判別規(guī)則可表示為稱W(x)為判別函數(shù)。由于它是x的線性函數(shù)，因此又稱為線性判別函數(shù)。線性判別的應(yīng)用最為廣泛。如果1與2不等，則判別函數(shù)W(x)為：W(x)=d2(x，G1)–d2(x，G2)=即W(x)是x的二次函數(shù)。，第一百頁，共一百一十八頁，2022年，8月28日(2)多總體情況設(shè)有m個(gè)總體：G1，G2，…，Gm（m>2），它們的均值、協(xié)差陣分別為μi，i，(i=1，2，…，m)。對任意給定的樣品x，要判斷它來自哪個(gè)總體。多總體按距離最近的準(zhǔn)則對x進(jìn)行判別歸類時(shí)，首先計(jì)算樣品x到m個(gè)總體的馬氏距離di2(x)（i=1,2,…,m），然后進(jìn)行比較，把x判歸距離最小的那個(gè)總體。即若dh2(x)=min{di2(x)|i=1,2,…,m}，則x

Gh。計(jì)算馬氏距離di2(x)（i=1,2,…,m）時(shí)，類似地可考慮1=2=…=m或i不全相等的兩種情況，并用樣本統(tǒng)計(jì)量作為μi和i的估計(jì).第一百零一頁，共一百一十八頁，2022年，8月28日2.費(fèi)歇爾判別（Fisher）下面以兩個(gè)總體為例說明費(fèi)歇爾判別的思想。設(shè)有兩個(gè)總體G1、G2，其均值分別為1和2，協(xié)方差陣分別1和2，并假定1=2=，考慮線性組合：y=L'x。通過尋求合適的L向量，使得來自兩個(gè)總體的數(shù)據(jù)間的距離較大，而來自同一個(gè)總體數(shù)據(jù)間的差異較小。為此，可以證明，當(dāng)選L=c–1(1–2)，其中c0時(shí)，所得的投影即滿足要求。從而稱c=1時(shí)的線性函數(shù)：y=L'x=(1–2)'–1x為費(fèi)歇爾線性判別函數(shù)。第一百零二頁，共一百一十八頁，2022年，8月28日其判別規(guī)則為：其中，m為兩個(gè)總體均值在投影方向上的中點(diǎn)，即當(dāng)1、2和未知時(shí)，可由總體G1和G2中分別抽出n1和n2個(gè)樣品，計(jì)算相應(yīng)的樣本均值和協(xié)方差陣作為1、2和的估計(jì)。第一百零三頁，共一百一十八頁，2022年，8月28日3.貝葉斯判別（Bayes）

(1)貝葉斯判別法設(shè)有m個(gè)總體G1,…,Gm，假定它們各自的分布密度分別為f1(x)，f2(x)，…，fm(x)，各自的先驗(yàn)概率（可以根據(jù)經(jīng)驗(yàn)事先給出或估出）分別為q1,q2,…,qm，顯然貝葉斯判別的方法是：當(dāng)抽取了一個(gè)未知總體的樣品x，要判斷它屬于哪個(gè)總體，可用著名的貝葉斯公式計(jì)算x屬于第j個(gè)總體的后驗(yàn)概率：第一百零四頁，共一百一十八頁，2022年，8月28日當(dāng)時(shí)，判斷x屬于第h個(gè)總體?；蛘哂?jì)算按先驗(yàn)概率加權(quán)的誤判平均損失：然后再比較這m個(gè)誤判平均損失的h1(x)，h2(x)，…，hm(x)的大小，選取其中最小的，就可以判定樣品x來自該總體。上式中C(j|i)為假定本來屬于Gi的樣品被判為屬于Gj時(shí)造成的損失。當(dāng)然C(i|i)=0，C(j|i)0（i，j=1，…，m）。第一百零五頁，共一百一十八頁，2022年，8月28日在實(shí)際問題中，錯(cuò)判的損失可以給出定性的分析，但很難用數(shù)值來表示，但應(yīng)用貝葉斯判別的方法時(shí)，要求定量給出C(j|i)，C(j|i)的賦值常用以下兩種方法：●根據(jù)經(jīng)驗(yàn)人為賦值；●假定各種錯(cuò)判的損失都相等。第一百零六頁，共一百一十八頁，2022年，8月28日(2)錯(cuò)判概率當(dāng)樣品xGi，用判別法D判別時(shí)，把x判歸Gj(i≠j)，出現(xiàn)錯(cuò)判。用P(j|I;D)（或簡記為P(j|i)）表示實(shí)屬Gi的樣品錯(cuò)判為Gj的概率，錯(cuò)判概率的估計(jì)方法有下面幾種：●利用訓(xùn)練樣本作為檢驗(yàn)集，即用判別方法對已知樣品進(jìn)行回判，統(tǒng)計(jì)錯(cuò)判的個(gè)數(shù)以及錯(cuò)判的比率，作為錯(cuò)判率的估計(jì)。此法得出的估計(jì)一般較低。●當(dāng)訓(xùn)練樣本的大小足夠大時(shí)，可留出一些已知類別的樣品不參加建立判別準(zhǔn)則，而是作為檢驗(yàn)集，并把錯(cuò)判的比率作為錯(cuò)判率的估計(jì)。此法當(dāng)檢驗(yàn)集較小時(shí)估計(jì)的方差大。第一百零七頁，共一百一十八頁，2022年，8月28日●設(shè)一法（或稱為交叉確認(rèn)法），每次留出一個(gè)已知類別的樣品，而用其他n–1個(gè)樣品建立判別準(zhǔn)則，然后對留出的這一個(gè)已知類別的樣品進(jìn)行判別歸類。對訓(xùn)練樣本中n個(gè)樣品逐個(gè)處理后把錯(cuò)判的比率作為錯(cuò)判率的估計(jì)。(3)廣義平方距離判別法在正態(tài)總體的假定下，按貝葉斯判別的思想，在錯(cuò)判造成的損失認(rèn)為相等的情況下得到的判別函數(shù)其實(shí)就是馬氏距離判別在考慮先驗(yàn)概率及協(xié)方差陣是否相等情況下的推廣，故在SAS的DISCRIM過程中稱為廣義平方距離判別法。第一百零八頁，共一百一十八頁，2022年，8月28日4.逐步判別

(1)各變量判別能力的檢驗(yàn)當(dāng)檢驗(yàn)k個(gè)類的均值向量是否全都相等(即檢驗(yàn)H0：1=2=…=k)時(shí)，否定了這個(gè)假設(shè)H0(即表明各總體的均值向量有顯著性差異)，也并不能保證其各分量的均值有顯著差異，若第i個(gè)分量間沒有顯著差異時(shí)，說明相應(yīng)的變量Xi對判別分類不起作用，應(yīng)該剔除。關(guān)于各變量判別能力的檢驗(yàn)問題是篩選判別變量的理論基礎(chǔ)，也是逐步判別的理論基礎(chǔ)。第一百零九頁，共一百一十八頁，2022年，8月28日變量判別能力的度量通常采用刪去該變量后考察判別能力的變化，即考察該變量對區(qū)分k個(gè)類是否能提供更多的附加信息，然后由附加信息構(gòu)造F統(tǒng)計(jì)量進(jìn)行檢驗(yàn)。利用F統(tǒng)計(jì)量對假設(shè)H0(i)(第i個(gè)變量在k個(gè)總體中的均值相等)作統(tǒng)計(jì)檢驗(yàn)。若否定H0(i)，表示變量Xi對區(qū)分k個(gè)總體的判別能力是顯著的(在顯著水平α下)。否則，變量Xi對區(qū)分k個(gè)總體的判別能力不能提供附加信息，這個(gè)變量應(yīng)剔除。第一百一十頁，共一百一十八頁，2022年，8月28日(2)逐步判別法的基本思想前面討論了用全部m個(gè)變量：X1,X2,…,Xm來建立判別函數(shù)對樣品進(jìn)行判別歸類的幾種方法。在這m個(gè)變量中，有的變量對區(qū)分k個(gè)總體的判別能力可能很強(qiáng)，有的可能很弱。如果不加區(qū)別地把m個(gè)變量全部用來建立判別函數(shù)，則必增加大量的計(jì)算，還可能因?yàn)樽兞块g的相關(guān)性引起計(jì)算上的困難(病態(tài)或退化等)及計(jì)算精度的降低。另一方面由于一些對區(qū)分k個(gè)總體的判別能力很小的變量的引入，產(chǎn)生干擾，致使建立的判別函數(shù)不穩(wěn)定，反而影響判別效果，因此自然提出一個(gè)變量的選擇問題。即如何從m個(gè)變量中挑選出對區(qū)分k個(gè)總體有顯著判別能力的變量，來建立判別函數(shù)，用以判別歸類。第一百一十一頁，共一百一十八頁，2022年，8月28日逐步判別的基本思想和逐步回歸是類似的。逐個(gè)引入變量，每次把一個(gè)判別能力最強(qiáng)的變量引入判別式，每引入一個(gè)新變量，對判別式中的老變量逐個(gè)進(jìn)行檢驗(yàn)，如其判別能力因新變量的引入而變得不顯著，應(yīng)把它從判別式中剔除。這種通過逐步篩選變量使得建立的判別函數(shù)中僅保留判別能力顯著的變量的方法，就是逐步判別法。第一百一十二頁，共一百一十八頁，2022年，8月28日(3)逐步判別法的基本步驟

1)逐步篩選變量：根據(jù)各變量對區(qū)分k個(gè)總體的判別能力的大小，按基本思想所介