數(shù)學(xué)建模聚類(lèi)分析馬莎莎

1、聚聚 類(lèi)類(lèi) 分分 析析 一、聚類(lèi)分析（一、聚類(lèi)分析（Cluster Analysis）簡(jiǎn)介）簡(jiǎn)介 聚類(lèi)分析是直接比較各事物之間的性質(zhì)，將性質(zhì)聚類(lèi)分析是直接比較各事物之間的性質(zhì)，將性質(zhì)相相近近的歸為一類(lèi)，將性質(zhì)的歸為一類(lèi)，將性質(zhì)差別較大差別較大的歸入不同的類(lèi)的分析的歸入不同的類(lèi)的分析技術(shù)。技術(shù)?；舅枷牖舅枷?聚類(lèi)分析的基本思想聚類(lèi)分析的基本思想: : 所研究的所研究的樣品或指標(biāo)樣品或指標(biāo)( (變變量量) )之間存在著之間存在著程度不同的相似性程度不同的相似性( (或親疏關(guān)系或親疏關(guān)系) )。（1 1）根據(jù)一批樣本的多個(gè)指標(biāo)）根據(jù)一批樣本的多個(gè)指標(biāo), , 具體找出一些能夠具體找出一些能夠度量度

2、量樣本或指標(biāo)之間的樣本或指標(biāo)之間的相似程度相似程度的的統(tǒng)計(jì)量統(tǒng)計(jì)量。（2 2）以這些統(tǒng)計(jì)量為分類(lèi)的）以這些統(tǒng)計(jì)量為分類(lèi)的依據(jù)依據(jù), , 把一些相似程度把一些相似程度較大較大的樣本的樣本( (或指標(biāo)或指標(biāo)) )聚合為一類(lèi)。聚合為一類(lèi)。 基本思想基本思想 按相似程度的大小按相似程度的大小把關(guān)系把關(guān)系密切密切的樣本聚合到一個(gè)的樣本聚合到一個(gè)小小的分類(lèi)單位的分類(lèi)單位, , 關(guān)系關(guān)系疏遠(yuǎn)疏遠(yuǎn)的樣本聚合到一個(gè)的樣本聚合到一個(gè)大大的分類(lèi)單位的分類(lèi)單位, , 直到把所有的樣本直到把所有的樣本( (或指標(biāo)或指標(biāo)) )都聚合完畢。都聚合完畢。 把不同的類(lèi)型一一劃分出來(lái)把不同的類(lèi)型一一劃分出來(lái), , 形成一個(gè)由小到

3、大形成一個(gè)由小到大的分類(lèi)系統(tǒng)。再把整個(gè)分類(lèi)系統(tǒng)畫(huà)成一張分群圖的分類(lèi)系統(tǒng)。再把整個(gè)分類(lèi)系統(tǒng)畫(huà)成一張分群圖( (又又稱(chēng)稱(chēng)譜系譜系圖圖), ), 用它把所有樣本用它把所有樣本( (或指標(biāo)或指標(biāo)) )間的親疏關(guān)系間的親疏關(guān)系表示出來(lái)。表示出來(lái)。 一個(gè)事物常常需要用多個(gè)變量來(lái)刻畫(huà)，如果對(duì)于一一個(gè)事物常常需要用多個(gè)變量來(lái)刻畫(huà)，如果對(duì)于一群有待分類(lèi)的樣本點(diǎn)需用群有待分類(lèi)的樣本點(diǎn)需用p個(gè)變量描述，則這個(gè)樣本點(diǎn)個(gè)變量描述，則這個(gè)樣本點(diǎn)可以看成是可以看成是 空間中的一個(gè)點(diǎn)?？臻g中的一個(gè)點(diǎn)。聚類(lèi)分析根據(jù)分類(lèi)對(duì)象的不同可分為聚類(lèi)分析根據(jù)分類(lèi)對(duì)象的不同可分為Q型和型和R型兩大類(lèi)型兩大類(lèi)Q型是對(duì)型是對(duì)樣本樣本進(jìn)行分類(lèi)處理

4、，其作用在于進(jìn)行分類(lèi)處理，其作用在于:1. 具有共同特點(diǎn)的樣本聚在一起具有共同特點(diǎn)的樣本聚在一起2. 所得結(jié)果比傳統(tǒng)的定性分類(lèi)方法更細(xì)致、全面、所得結(jié)果比傳統(tǒng)的定性分類(lèi)方法更細(xì)致、全面、合理合理二、聚類(lèi)對(duì)象：二、聚類(lèi)對(duì)象：樣本、變量樣本、變量pRR型是對(duì)型是對(duì)變量變量進(jìn)行分類(lèi)處理，其作用在于：進(jìn)行分類(lèi)處理，其作用在于：1. 可以了解變量間及變量組合間的親疏關(guān)系可以了解變量間及變量組合間的親疏關(guān)系2. 可以根據(jù)變量的聚類(lèi)結(jié)果及它們之間的關(guān)系，可以根據(jù)變量的聚類(lèi)結(jié)果及它們之間的關(guān)系，選擇主要變量進(jìn)行回歸分析或選擇主要變量進(jìn)行回歸分析或Q型聚類(lèi)分析型聚類(lèi)分析相似性度量相似性度量 進(jìn)行進(jìn)行“相關(guān)性相關(guān)

5、性”或或“相似性相似性”度量。在相似性度量。在相似性度量中常常包含有許多主觀上的考慮，但是最重要度量中常常包含有許多主觀上的考慮，但是最重要的是考慮指標(biāo)性質(zhì)或觀測(cè)的尺度。的是考慮指標(biāo)性質(zhì)或觀測(cè)的尺度。對(duì)對(duì)樣本進(jìn)行聚類(lèi)時(shí)，樣本進(jìn)行聚類(lèi)時(shí)，“靠近靠近”往往是往往是距離距離。對(duì)指標(biāo)進(jìn)行聚類(lèi)時(shí)，根據(jù)對(duì)指標(biāo)進(jìn)行聚類(lèi)時(shí)，根據(jù)相關(guān)系相關(guān)系數(shù)數(shù)或某種或某種關(guān)聯(lián)性關(guān)聯(lián)性度量度量來(lái)來(lái)聚類(lèi)。聚類(lèi)。Q型型樣本間樣本間的的“相似性相似性”度量度量距離距離 設(shè)每個(gè)樣本有 p 個(gè)指標(biāo), 觀察值記為nixxxxTpiiii, 2 , 1,),(21(1)每個(gè)樣本 可看成是 p 維空間的一個(gè)點(diǎn)。于是, 可用各點(diǎn)之間的距離來(lái)衡量

6、各樣本點(diǎn)之間的接近程度。 樣本 和 之間的距離 , 一般應(yīng)滿足如下條件: () , 且 時(shí)當(dāng)且僅當(dāng) ; () ; () ; 有時(shí)所用的距離不滿足(), 但在廣義的角度上仍稱(chēng)為距離。常用的距離有如下幾種:ixixjx),(jixxd0),(jixxd0),(jixxdjixx ),(),(ijjixxdxxd),(),(),(jkkijixxdxxdxxdpkjkikijxxd12112)(pkjkikijxxd 1、閔氏距離、閔氏距離(Minkowski)2、絕對(duì)距離（、絕對(duì)距離（Block距離）距離）3、歐氏距離、歐氏距離(Euclidean distance)qpkqjkikijxxd11

7、)(4、切比雪夫距離、切比雪夫距離(Chebychev)jkikpkijxxd1max)(6.馬氏距離馬氏距離5.數(shù)據(jù)的標(biāo)準(zhǔn)化數(shù)據(jù)的標(biāo)準(zhǔn)化ijjijjxxxS jjxSj其中 和是第 個(gè)指標(biāo)的均值和樣本標(biāo)準(zhǔn)差以上距離與各變量的量綱有關(guān)，為了消除量綱的以上距離與各變量的量綱有關(guān)，為了消除量綱的影響，可對(duì)數(shù)據(jù)標(biāo)準(zhǔn)化。影響，可對(duì)數(shù)據(jù)標(biāo)準(zhǔn)化。21( )( )( )( )()()()ijijijdMxxSxx 例例1 歐洲各國(guó)的語(yǔ)言有許多相似之處，有的十分歐洲各國(guó)的語(yǔ)言有許多相似之處，有的十分相似。為了研究這些語(yǔ)言的歷史關(guān)系，也許通過(guò)比較相似。為了研究這些語(yǔ)言的歷史關(guān)系，也許通過(guò)比較他們數(shù)字的表達(dá)式比較

8、恰當(dāng)。表格列舉出英語(yǔ)，挪威他們數(shù)字的表達(dá)式比較恰當(dāng)。表格列舉出英語(yǔ)，挪威語(yǔ)，丹麥語(yǔ)，荷蘭語(yǔ)，德語(yǔ)，法語(yǔ)，西班牙語(yǔ)，意大語(yǔ)，丹麥語(yǔ)，荷蘭語(yǔ)，德語(yǔ)，法語(yǔ)，西班牙語(yǔ)，意大利語(yǔ)，波蘭語(yǔ)，匈牙利語(yǔ)和芬蘭語(yǔ)的利語(yǔ)，波蘭語(yǔ)，匈牙利語(yǔ)和芬蘭語(yǔ)的1,2,10的拼法，的拼法，希望計(jì)算這希望計(jì)算這11種語(yǔ)言之間的語(yǔ)言的距離種語(yǔ)言之間的語(yǔ)言的距離.11種歐洲語(yǔ)言的數(shù)詞選擇適用的距離選擇適用的距離 在聚類(lèi)分析中通常要結(jié)合實(shí)際問(wèn)題來(lái)選擇在聚類(lèi)分析中通常要結(jié)合實(shí)際問(wèn)題來(lái)選擇適用適用的的距離距離, , 有時(shí)應(yīng)根據(jù)實(shí)際問(wèn)題定義新的距離有時(shí)應(yīng)根據(jù)實(shí)際問(wèn)題定義新的距離, , 顯然，本例無(wú)法直接用上述公式來(lái)計(jì)算距離。但顯然，本例無(wú)法

9、直接用上述公式來(lái)計(jì)算距離。但可以發(fā)現(xiàn)可以發(fā)現(xiàn)前三種文字前三種文字( (英、挪、丹英、挪、丹) )很相似很相似, , 特別是每個(gè)單詞的第特別是每個(gè)單詞的第一一個(gè)字母?？梢杂脗€(gè)字母?？梢杂?010個(gè)數(shù)詞個(gè)數(shù)詞中中第一個(gè)第一個(gè)字母字母不同不同的的個(gè)數(shù)個(gè)數(shù)來(lái)定義兩種語(yǔ)言之間的距離。來(lái)定義兩種語(yǔ)言之間的距離。例如：英語(yǔ)和挪威語(yǔ)中只有例如：英語(yǔ)和挪威語(yǔ)中只有1 1和和8 8的第一個(gè)字母不同的第一個(gè)字母不同, , 則它們之間的距離為則它們之間的距離為2 2。E N Da Du G Fr Sp I P H Fi E 0 N 2 0Da 2 1 0Du 7 5 6 0G 6 4 5 5 0Fr 6 6 6 9

10、7 0Sp 6 6 5 9 7 2 0I 6 6 5 9 7 1 1 0P 7 7 6 10 8 5 3 4 0H 9 8 8 8 9 10 10 10 10 0Fi 9 9 9 9 9 9 9 9 9 8 0首先定義類(lèi)與類(lèi)之間的距離，由類(lèi)間距離的定義首先定義類(lèi)與類(lèi)之間的距離，由類(lèi)間距離的定義 不同產(chǎn)生不同的系統(tǒng)聚類(lèi)分析。常見(jiàn)的類(lèi)間的距離不同產(chǎn)生不同的系統(tǒng)聚類(lèi)分析。常見(jiàn)的類(lèi)間的距離有有法。它們的歸類(lèi)步驟基本是一致的。法。它們的歸類(lèi)步驟基本是一致的。8種之多，與之相應(yīng)的系統(tǒng)聚類(lèi)分析也有種之多，與之相應(yīng)的系統(tǒng)聚類(lèi)分析也有8種之多、種之多、分別為最短距離法、最長(zhǎng)距離法、中間距離法、重心分別為最短距離

11、法、最長(zhǎng)距離法、中間距離法、重心法、類(lèi)平均法、可變類(lèi)平均法、可變法和離差平方和法、類(lèi)平均法、可變類(lèi)平均法、可變法和離差平方和Q型型類(lèi)與類(lèi)類(lèi)與類(lèi)間間的的“相似性相似性”度量度量 說(shuō)明：說(shuō)明： 用 i , j 表示樣本 。用 表示 與 之間的距離, 用 與 表示兩個(gè)類(lèi), 所包含的樣本數(shù)分別為 與 之間的距離用 表示。下面給出四種最常用的類(lèi)與類(lèi)之間距離的定義。jixx ,ixijdjxqGpGpGqGpnqn),(qpGGD1 、最短距離（、最短距離（Nearest Neighbor)x21x12x22x1112dqpijqppqGjGidGGDD,min),(即定義 與 之間的距離為 與 中最近的

12、兩個(gè)樣本的距離。 pGqGpGqGn最短距離法進(jìn)行聚類(lèi)分析的步驟如下：最短距離法進(jìn)行聚類(lèi)分析的步驟如下：（1）定義樣品之間距離，計(jì)算樣品的兩兩距離，得一距離）定義樣品之間距離，計(jì)算樣品的兩兩距離，得一距離 陣記為陣記為D（0） ，開(kāi)始每個(gè)樣品自成一類(lèi)，顯然這時(shí)，開(kāi)始每個(gè)樣品自成一類(lèi)，顯然這時(shí)Dij = dij。（2）找出距離最小元素，設(shè)為）找出距離最小元素，設(shè)為Dpq，則將，則將Gp和和Gq合并成一個(gè)合并成一個(gè) 新類(lèi)，記為新類(lèi)，記為Gr，即，即Gr = Gp，Gq。（3）按（）按（5.12）計(jì)算新類(lèi)與其它類(lèi)的距離。）計(jì)算新類(lèi)與其它類(lèi)的距離。 （4）重復(fù)（）重復(fù)（2）、（）、（3）兩步，直到所有

13、元素。并成一類(lèi)為）兩步，直到所有元素。并成一類(lèi)為 止。如果某一步距離最小的元素不止一個(gè)，則對(duì)應(yīng)這些止。如果某一步距離最小的元素不止一個(gè)，則對(duì)應(yīng)這些 最小元素的類(lèi)可以同時(shí)合并。最小元素的類(lèi)可以同時(shí)合并。n【例例2】設(shè)有六個(gè)樣品，每個(gè)只測(cè)量一個(gè)指標(biāo)，分別是設(shè)有六個(gè)樣品，每個(gè)只測(cè)量一個(gè)指標(biāo)，分別是1，2，5，7，9，10，試用最短距離法將它們分類(lèi)。，試用最短距離法將它們分類(lèi)。（1）樣品采用絕對(duì)值距離，計(jì)算樣品間的距離陣）樣品采用絕對(duì)值距離，計(jì)算樣品間的距離陣D（0） ，見(jiàn)，見(jiàn)表表1表表1 G1G2G3G4G5G6G1 0G2 10G3 430G4 6520G5 8742 0G6 9852 10 D(

14、0)（2）D（0）中最小的元素是中最小的元素是D12D561，于是將，于是將G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，并利用（，并利用（5.12）式計(jì)算新類(lèi)與其）式計(jì)算新類(lèi)與其它類(lèi)的距離它類(lèi)的距離D（1） ，見(jiàn)表，見(jiàn)表2表表2 （3）在）在D（1）中最小值是中最小值是D34D482，由于，由于G4與與G3合并，合并，又與又與G8合并，因此合并，因此G3、G4、G8合并成一個(gè)新類(lèi)合并成一個(gè)新類(lèi)G9，其與其，其與其它類(lèi)的距離它類(lèi)的距離D（2） ，見(jiàn)表，見(jiàn)表3表表3 （4）最后將）最后將G7和和G9合并成合并成G10，這時(shí)所有的六個(gè)樣品聚為一，這時(shí)所有的六個(gè)樣品聚為一類(lèi)，其過(guò)程終止

15、。類(lèi)，其過(guò)程終止。上述聚類(lèi)的可視化過(guò)程見(jiàn)圖上述聚類(lèi)的可視化過(guò)程見(jiàn)圖1所示，橫坐標(biāo)的刻度表示并類(lèi)所示，橫坐標(biāo)的刻度表示并類(lèi)的距離。這里我們應(yīng)該注意，聚類(lèi)的個(gè)數(shù)要以實(shí)際情況所定，的距離。這里我們應(yīng)該注意，聚類(lèi)的個(gè)數(shù)要以實(shí)際情況所定，其詳細(xì)內(nèi)容將在后面討論。其詳細(xì)內(nèi)容將在后面討論。圖圖1 最短距離聚類(lèi)法的過(guò)程最短距離聚類(lèi)法的過(guò)程G2=2G1=1G3=5G4=7G5=9G6=10G7G8G9G10123D2.最長(zhǎng)距離（最長(zhǎng)距離（Furthest Neighbor ）x11x21n再找距離最小兩類(lèi)并類(lèi)，直至所有的樣品全歸為一類(lèi)為止。再找距離最小兩類(lèi)并類(lèi)，直至所有的樣品全歸為一類(lèi)為止?？梢钥闯鲎铋L(zhǎng)距離法與

16、最短距離法只有兩點(diǎn)不同：可以看出最長(zhǎng)距離法與最短距離法只有兩點(diǎn)不同：一是類(lèi)與類(lèi)之間的距離定義不同；一是類(lèi)與類(lèi)之間的距離定義不同；另一是計(jì)算新類(lèi)與其它類(lèi)的距離所用的公式不同。另一是計(jì)算新類(lèi)與其它類(lèi)的距離所用的公式不同。n【例例2】針對(duì)例針對(duì)例1的數(shù)據(jù)，試用重心法將它們聚類(lèi)。的數(shù)據(jù)，試用重心法將它們聚類(lèi)。（1）樣品采用歐氏距離，計(jì)算樣品間的平方距離陣）樣品采用歐氏距離，計(jì)算樣品間的平方距離陣D2（0），見(jiàn)，見(jiàn)表表4所示。所示。 表表4 （2）D2（0）中最小的元素是中最小的元素是D212D2561，于是將，于是將G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，并利用（，并利用（5.18

17、）式計(jì)算新類(lèi)與）式計(jì)算新類(lèi)與其它類(lèi)的距離得到距離陣其它類(lèi)的距離得到距離陣D2（1） ，見(jiàn)表，見(jiàn)表5： 其中，其中，其它結(jié)果類(lèi)似可以求得其它結(jié)果類(lèi)似可以求得 （3）在）在D2（1）中最小值是中最小值是D2344，那么，那么G3與與G4合并一個(gè)新合并一個(gè)新類(lèi)類(lèi)G9，其與與其它類(lèi)的距離，其與與其它類(lèi)的距離D2（2） ，見(jiàn)表，見(jiàn)表6： 表表6 （4）在中最小值是）在中最小值是12.5，那么與合并一個(gè)新類(lèi)，其與與，那么與合并一個(gè)新類(lèi)，其與與其它類(lèi)的距離，見(jiàn)表其它類(lèi)的距離，見(jiàn)表7：表表7 （5）最后將）最后將G7和和G10合并成合并成G11，這時(shí)所有的六個(gè)樣品聚為一類(lèi)，這時(shí)所有的六個(gè)樣品聚為一類(lèi)，其過(guò)程終

18、止。其過(guò)程終止。上述重心法聚類(lèi)的可視化過(guò)程見(jiàn)圖上述重心法聚類(lèi)的可視化過(guò)程見(jiàn)圖3所示，橫坐標(biāo)的刻度表所示，橫坐標(biāo)的刻度表示并類(lèi)的距離。示并類(lèi)的距離。圖圖3 重心聚類(lèi)法的過(guò)程重心聚類(lèi)法的過(guò)程G1=1G2=2G3=5G4=7G5=9G6=102412.5D1G9G7G8G10G115. 離差平方和法離差平方和法該方法是該方法是Ward提出來(lái)的，所以又稱(chēng)為提出來(lái)的，所以又稱(chēng)為Ward法。該方法的基法。該方法的基本思想來(lái)自于方差分析，如果分類(lèi)正確，同類(lèi)樣品的離差平本思想來(lái)自于方差分析，如果分類(lèi)正確，同類(lèi)樣品的離差平方和應(yīng)當(dāng)較小，類(lèi)與類(lèi)的離差平方和較大。具體做法是先將方和應(yīng)當(dāng)較小，類(lèi)與類(lèi)的離差平方和較大。

19、具體做法是先將n個(gè)樣品各自成一類(lèi)，然后每次縮小一類(lèi)，每縮小一類(lèi)，離個(gè)樣品各自成一類(lèi)，然后每次縮小一類(lèi)，每縮小一類(lèi)，離差平方和就要增大，選擇使方差增加最小的兩類(lèi)合并，直到差平方和就要增大，選擇使方差增加最小的兩類(lèi)合并，直到所有的樣品歸為一類(lèi)為止。所有的樣品歸為一類(lèi)為止。設(shè)將設(shè)將n個(gè)樣品分成個(gè)樣品分成k類(lèi)類(lèi)G1，G2，Gk，用，用Xit表示表示Gt中的第中的第I個(gè)樣品，個(gè)樣品，nt表示表示Gt中樣品的個(gè)數(shù)，中樣品的個(gè)數(shù)， 是是Gt的重心，則的重心，則Gt的樣品的樣品離差平方和為離差平方和為2112121nkkjnkkinkkjkiijxxxxCnknkjkjikinkjkjikiijxxxxxxxxr11221)()()(1、夾角余弦、夾角余弦2、相關(guān)系數(shù)、相關(guān)系數(shù)R型聚類(lèi)統(tǒng)計(jì)量型聚類(lèi)統(tǒng)計(jì)量 對(duì)兩個(gè)指標(biāo)之間的相似程度用對(duì)兩個(gè)指標(biāo)之間的相似程度用相關(guān)系數(shù)相關(guān)系數(shù)來(lái)刻劃，來(lái)刻劃，相關(guān)系數(shù)相關(guān)系數(shù)絕對(duì)