數(shù)學(xué)建模聚類(lèi)分析PPT課件

1、 一、聚類(lèi)分析（Cluster Analysis）簡(jiǎn)介 聚類(lèi)分析是直接比較各事物之間的性質(zhì)，將性質(zhì)相近的歸為一類(lèi)，將性質(zhì)差別較大的歸入不同的類(lèi)的分析技術(shù)。 數(shù)理統(tǒng)計(jì)中的數(shù)值分類(lèi)有兩種問(wèn)題： ：已知分類(lèi)情況，將未知個(gè)體歸入正確類(lèi)別 ：分類(lèi)情況未知，對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類(lèi)第1頁(yè)/共52頁(yè)基本思想基本思想 聚類(lèi)分析的基本思想: 對(duì)所研究的樣品或指標(biāo)(變量)之間存在著程度不同的相似性(或親疏關(guān)系)。（1）根據(jù)一批樣品的多個(gè)指標(biāo), 具體找出一些能夠度量樣品或指標(biāo)之間的相似程度的統(tǒng)計(jì)量。（2）以這些統(tǒng)計(jì)量為分類(lèi)的依據(jù), 把一些相似程度較大的樣品(或指標(biāo))聚合為一類(lèi)。 把另一些彼此之間相似程度較大的樣品(或指標(biāo)

2、)聚合為另一類(lèi)。 第2頁(yè)/共52頁(yè)基本思想基本思想 按相似程度的大小把關(guān)系密切的樣品聚合到一個(gè)小的分類(lèi)單位, 關(guān)系疏遠(yuǎn)的樣品聚合到一個(gè)大的分類(lèi)單位, 直到把所有的樣品(或指標(biāo))都聚合完畢。 把不同的類(lèi)型一一劃分出來(lái), 形成一個(gè)由小到大的分類(lèi)系統(tǒng)。再把整個(gè)分類(lèi)系統(tǒng)畫(huà)成一張分群圖(又稱(chēng)譜系圖), 用它把所有樣品(或指標(biāo))間的親疏關(guān)系表示出來(lái)。第3頁(yè)/共52頁(yè) 要做聚類(lèi)分析，首先得按照我們聚類(lèi)的目的，從對(duì)象中提取出能表現(xiàn)這個(gè)目的的特征指標(biāo)；然后根據(jù)親疏程度進(jìn)行分類(lèi)。聚類(lèi)分析根據(jù)分類(lèi)對(duì)象的不同可分為Q型和R型兩大類(lèi)Q型是對(duì)樣本進(jìn)行分類(lèi)處理，其作用在于:1.具有共同特點(diǎn)的樣本聚在一起2.所得結(jié)果比傳統(tǒng)的

3、定性分類(lèi)方法更細(xì)致、全面、合理二、聚類(lèi)對(duì)象第4頁(yè)/共52頁(yè)R型是對(duì)變量進(jìn)行分類(lèi)處理，其作用在于：1.可以了解變量間及變量組合間的親疏關(guān)系2.可以根據(jù)變量的聚類(lèi)結(jié)果及它們之間的關(guān)系，選擇主要變量進(jìn)行回歸分析或Q型聚類(lèi)分析第5頁(yè)/共52頁(yè) 2 相似性度量 進(jìn)行“相關(guān)性”或“相似性”度量。在相似性度量中常常包含有許多主觀上的考慮，但是最重要的是考慮指標(biāo)性質(zhì)或觀測(cè)的尺度。 當(dāng)樣品進(jìn)行聚類(lèi)時(shí)，“靠近”往往是距離。同時(shí)對(duì)指標(biāo)進(jìn)行聚類(lèi)時(shí)，根據(jù)相關(guān)系數(shù)或某種關(guān)聯(lián)性度量來(lái)聚類(lèi)。第6頁(yè)/共52頁(yè)Q型樣品間的樣品間的“相似性相似性”度量度量距離距離 設(shè)每個(gè)樣品有 p 個(gè)指標(biāo), 觀察值記為nixxxxTpiiii,

4、2 , 1,),(21(1)每個(gè)樣品 可看成是 p 維空間的一個(gè)點(diǎn)。于是, 可用各點(diǎn)之間的距離來(lái)衡量各樣品點(diǎn)之間的接近程度。 樣品 和 之間的距離 , 一般應(yīng)滿足如下條件: () , 且 時(shí)當(dāng)且僅當(dāng) ; () ; () ; 有時(shí)所用的距離不滿足(), 但在廣義的角度上仍稱(chēng)為距離。常用的距離有如下幾種:ixixjx),(jixxd0),(jixxd0),(jixxdjixx ),(),(ijjixxdxxd),(),(),(jkkijixxdxxdxxd第7頁(yè)/共52頁(yè)pkjkikijxxd12112)(pkjkikijxxd 3、明考斯基距離(Minkowski)1、絕對(duì)距離（Block距離）

5、2、歐氏距離(Euclidean distance)qpkqjkikijxxd11)(4、切比雪夫距離(Chebychev)jkikpkijxxd1max)(第8頁(yè)/共52頁(yè)6.馬氏距離5.數(shù)據(jù)的標(biāo)準(zhǔn)化,ijjijjxxxS jjxSj其中 和是第 個(gè)指標(biāo)的均值和樣本標(biāo)準(zhǔn)差以上距離與各變量的量綱有關(guān)，為了消除量綱的影響，可對(duì)數(shù)據(jù)標(biāo)準(zhǔn)化。21( )( )( )( )()()()ijijijdMxxSxx第9頁(yè)/共52頁(yè) 例1 歐洲各國(guó)的語(yǔ)言有許多相似之處，有的十分相似。為了研究這些語(yǔ)言的歷史關(guān)系，也許通過(guò)比較他們數(shù)字的表達(dá)式比較恰當(dāng)。表列舉出英語(yǔ)，挪威語(yǔ)，丹麥語(yǔ)，荷蘭語(yǔ)，德語(yǔ)，法語(yǔ)，西班牙語(yǔ)，意

6、大利語(yǔ)，波蘭語(yǔ)，匈牙利語(yǔ)和芬蘭語(yǔ)的1,2,10的拼法，希望計(jì)算這11種語(yǔ)言之間的語(yǔ)言的距離.第10頁(yè)/共52頁(yè)11種歐洲語(yǔ)言的數(shù)詞第11頁(yè)/共52頁(yè)選擇適用的距離選擇適用的距離 在聚類(lèi)分析中通常要結(jié)合實(shí)際問(wèn)題來(lái)選擇適用的距離, 有時(shí)應(yīng)根據(jù)實(shí)際問(wèn)題定義新的距離, 顯然，本例無(wú)法直接用上述公式來(lái)計(jì)算距離。但可以發(fā)現(xiàn)前三種文字(英、挪、丹)很相似, 特別是每個(gè)單詞的第一個(gè)字母?？梢杂?0個(gè)數(shù)詞中第一個(gè)字母不同的個(gè)數(shù)來(lái)定義兩種語(yǔ)言之間的距離。例如：英語(yǔ)和挪威語(yǔ)中只有1和8的第一個(gè)字母不同, 則它們之間的距離為2。第12頁(yè)/共52頁(yè)E N Da Du G Fr Sp I P H Fi E 0 N 2 0

7、Da 2 1 0Du 7 5 6 0G 6 4 5 5 0Fr 6 6 6 9 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第13頁(yè)/共52頁(yè)2112121nkkjnkkinkkjkiijxxxxCnknkjkjikinkjkjikiijxxxxxxxxr11221)()()(1、夾角余弦2、相關(guān)系數(shù)R型聚類(lèi)統(tǒng)計(jì)量 對(duì)兩個(gè)指標(biāo)之間的相似程度用相似系數(shù)來(lái)刻劃，相似系數(shù)絕對(duì)對(duì)值越接近于1，表示指標(biāo)間的關(guān)系越密切，絕對(duì)值越接近于0，表示

8、指標(biāo)間的關(guān)系越疏遠(yuǎn).第14頁(yè)/共52頁(yè) 三 系統(tǒng)聚類(lèi)分析1. 系統(tǒng)聚類(lèi)分析的基本思想是： 距離相近的樣品（或變量）先聚成類(lèi)，距離相遠(yuǎn)的后聚成類(lèi)，過(guò)程一直下去，每個(gè)樣品（或變量）總能聚到合適的類(lèi)中。 系統(tǒng)聚類(lèi)分析過(guò)程是： 假設(shè)總共有n個(gè)樣品（或變量），第一步將每個(gè)樣品（或變量）獨(dú)自聚成一類(lèi)，共有n類(lèi)； 第15頁(yè)/共52頁(yè)第二步根據(jù)所確定的樣品（或變量）“距離”公式， 將距離較近的兩個(gè)樣品（或變量）聚合為一類(lèi)，其他樣品（或變量）仍各自聚為一類(lèi)，共有n1類(lèi)； 第三步將“距離”最近的兩個(gè)類(lèi)進(jìn)一步聚成一類(lèi)，共聚成n2類(lèi)；以上步驟一直進(jìn)行下去，最后將所有的樣品或變量）聚成一類(lèi)。 將整個(gè)分類(lèi)系統(tǒng)地畫(huà)成一張譜

9、系圖，所以有時(shí)系統(tǒng)聚類(lèi)分析也叫譜系聚類(lèi)分析。第16頁(yè)/共52頁(yè)2. 類(lèi)間距離 首先定義類(lèi)與類(lèi)之間地距離，又類(lèi)間的距離定義 不同產(chǎn)生不同的系統(tǒng)聚類(lèi)分析。常見(jiàn)的類(lèi)間的距離有法。它們的歸類(lèi)步驟基本是一致的。8種之多，與之相應(yīng)的系統(tǒng)聚類(lèi)分析也有8種之多、分別為最短距離法、最長(zhǎng)距離法、中間距離法、重心法、類(lèi)平均法、可變類(lèi)平均法、可變法和離差平方和第17頁(yè)/共52頁(yè) 用 i , j 表示樣品 。用 表示 與 之間的距離, 用 與 表示兩個(gè)類(lèi), 所包含的樣品數(shù)分別為 與 之間的距離用 表示。下面給出四種最常用的類(lèi)與類(lèi)之間距離的定義。jixx ,ixijdjxqGpGpGqGpnqn),(qpGGD第18頁(yè)/

10、共52頁(yè)1 、最短距離（Nearest Neighbor)x21x12x22x1113d第19頁(yè)/共52頁(yè)qpijqppqGjGidGGDD,min),(即定義 與 之間的距離為 與 中最近的兩個(gè)樣品的距離。 類(lèi)與類(lèi)之間的最短距離有如下的遞推公式。設(shè) 由 與 合并而成, 則 與其它類(lèi) 的最短距離為pGqGpGqGpGrGqGrG),(qpkGkkqijkpijkrijkrGjGidGjGidGjGidGGD,min,minmin,min),(),(),(minkqkpGGDGGD第20頁(yè)/共52頁(yè) 1、根據(jù)樣品的特征，規(guī)定樣品之間的距離 ，共有 個(gè)。將所有列表，記為D（0）表，該表是一張對(duì)稱(chēng)表

11、。所有的樣本點(diǎn)各自為一類(lèi)。 2、選擇D（0）表中最小的非零數(shù)，不妨假設(shè) ，于是將 和 合并為一類(lèi)，記為 。pqdpGqGqprGGG，2nCijd開(kāi)始各樣本自成一類(lèi)最短距離法進(jìn)行聚類(lèi)分析的步驟如下：第21頁(yè)/共52頁(yè) 3、利用遞推公式計(jì)算新類(lèi)與其它類(lèi)之間的距離。分別刪除D（0）表的第p，q行和第p，q列，并新增一行和一列添上的結(jié)果，產(chǎn)生D（1）表。第22頁(yè)/共52頁(yè) 4、在D（1）表再選擇最小的非零數(shù)，其對(duì)應(yīng)的兩類(lèi)有構(gòu)成新類(lèi)，再利用遞推公式計(jì)算新類(lèi)與其它類(lèi)之間的距離。分別刪除D（1）表的相應(yīng)的行和列，并新增一行和一列添上的新類(lèi)和舊類(lèi)之間的距離。結(jié)果，產(chǎn)生D（2）表。類(lèi)推直至所有的樣本點(diǎn)歸為一類(lèi)

12、為止。第23頁(yè)/共52頁(yè)最短距離法進(jìn)行聚類(lèi)分析的步驟如下：（1)定義樣品之間的距離 （2)找出距離最小元素，設(shè)為，則將 pqDpqGG與合并成一新類(lèi)記為 rG,記為 ,rpqGGG（3） 按上式計(jì)算新類(lèi)與其他類(lèi)之間的距離。 （4） 重復(fù)（2），（3）的步驟，直到將所有元素并成一類(lèi)為止。 (如果某一步距離最小的元素不止一個(gè)，則將對(duì)應(yīng)這些最小元素的類(lèi)可以同時(shí)合并）第24頁(yè)/共52頁(yè) 例2 設(shè)有6個(gè)樣品，每個(gè)只測(cè)一個(gè)指標(biāo)，分別是1，2，5，7，9，10，試采用絕對(duì)值距離用最短距離法將它們進(jìn)行分類(lèi)。第25頁(yè)/共52頁(yè) 解 （1）樣品首先采用絕對(duì)值距離，計(jì)算樣品之間的距離陣為D(0).G1G2G3G4G

13、5G6G10G210G3430G46520G587420G6985210 D(0)第26頁(yè)/共52頁(yè)G2=2G1=1G3=5G4=7G5=9G6=10G7G8G9G10123D第27頁(yè)/共52頁(yè)2.最長(zhǎng)距離（Furthest Neighbor ）x11x2112d第28頁(yè)/共52頁(yè)qpijqpGjGidGGD,max),(即定義 與 之間的距離為 與 中最遠(yuǎn)的兩個(gè)樣品的距離。 類(lèi)與類(lèi)之間的最長(zhǎng)距離有如下的遞推公式。設(shè) 由 與合并而成, 則 到 的最長(zhǎng)距離為pGqGpGqGpGrGqGrG),(qpkGkkqijkpijkrijkrGjGidGjGidGjGidGGD,max,maxmax,ma

14、x),(),(),(maxkqkpGGDGGD2.最長(zhǎng)距離（Furthest Neighbor ）第29頁(yè)/共52頁(yè)991dd組間平均連接（Between-group Linkage)3.類(lèi)平均距離第30頁(yè)/共52頁(yè)組內(nèi)平均連接法（Within-group Linkage)1234566ddddddx21x12x22x113.類(lèi)平均距離第31頁(yè)/共52頁(yè)4.重心法（Centroid clustering):均值點(diǎn)的距離11,x y22,xy第32頁(yè)/共52頁(yè)qpknnnqqppkkxnxnnx1rkrkkrxxxxd22222pqkqkpqrkqprkpkrdnnnndnndnnd將p和q合并

15、為k，則k類(lèi)的樣品個(gè)數(shù)為它的重心是rx某一類(lèi) r 的重心是，它與新類(lèi)k的距離是經(jīng)推導(dǎo)可以得到如下遞推公式：pnqn設(shè)聚類(lèi)到某一步，類(lèi)p與 q分別有樣品 、個(gè)，第33頁(yè)/共52頁(yè) 例2 設(shè)有6個(gè)樣品，每個(gè)只測(cè)一個(gè)指標(biāo)，分別是1，2，5，7，9，10，試采用歐氏距離的平方,試用重心法將它們進(jìn)行分類(lèi)。G1G2G3G4G5G6G10G210G31690G4362540G564491640G6816425910D2(0)第34頁(yè)/共52頁(yè)G7G3G4G8G70G312.250G430.2540G86420.256.250D2(1)其中2222373132121111222211111691222212.

16、25DDDD 第35頁(yè)/共52頁(yè)D2(2)G7G9G8G70G920.250G86412.250D2(3)G7G10G70G1039.06250第36頁(yè)/共52頁(yè)G1=1G2=2G3=5G4=7G5=9G6=102412.5D1G9G7G8G10G11第37頁(yè)/共52頁(yè)5.5.動(dòng)態(tài)聚類(lèi)法（快速聚類(lèi)法）動(dòng)態(tài)聚類(lèi)法（快速聚類(lèi)法） 系統(tǒng)聚類(lèi)法是一種比較成功的聚類(lèi)方法。然而當(dāng)樣本點(diǎn)數(shù)量十分龐大時(shí)，則是一件非常繁重的工作，且聚類(lèi)的計(jì)算速度也比較慢。 比如在市場(chǎng)抽樣調(diào)查中，有4萬(wàn)人就其對(duì)衣著的偏好作了回答，希望能迅速將他們分為幾類(lèi)。 這時(shí)，采用系統(tǒng)聚類(lèi)法就很困難，而動(dòng)態(tài)聚類(lèi)法就會(huì)顯得方便，適用。 動(dòng)態(tài)聚類(lèi)

17、使用于大型數(shù)據(jù)。第38頁(yè)/共52頁(yè)基本思想：選取若干個(gè)樣品作為凝聚點(diǎn)，計(jì)算每個(gè)樣品和凝聚點(diǎn)的距離，進(jìn)行初始分類(lèi)，然后根據(jù)初始分類(lèi)計(jì)算其重心，再進(jìn)行第二次分類(lèi)，一直到所有樣品不再調(diào)整為止。第39頁(yè)/共52頁(yè)選擇凝聚點(diǎn)分 類(lèi)修改分類(lèi)分類(lèi)是否合理分類(lèi)結(jié)束YesNo第40頁(yè)/共52頁(yè) 用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明動(dòng)態(tài)聚類(lèi)法的工作過(guò)程。例如我們要把圖中的點(diǎn)分成兩類(lèi)?？焖倬垲?lèi)的步驟： 1、隨機(jī)選取兩個(gè)點(diǎn) 和 作為凝聚點(diǎn)。 2、對(duì)于任何點(diǎn) ，分別計(jì)算 3、若 ，則將 劃為第一類(lèi)，否則劃給第二類(lèi)。 4、分別計(jì)算兩個(gè)類(lèi)的重心，則得 和 ，以其為新的凝聚點(diǎn)，對(duì)空間中的點(diǎn)進(jìn)行重新分類(lèi)，得到新分類(lèi)。)2(1x)2(2x)1

18、 (1x)1 (2xkx),(),()1(2)1(1xxdxxdkk和),(),()1(2)1(1xxdxxdkkkx第41頁(yè)/共52頁(yè) (b) 任取兩個(gè)凝聚點(diǎn) (c) 第一次分類(lèi) (d) 求各類(lèi)中心 （a）空間的群點(diǎn)第42頁(yè)/共52頁(yè) (e) 第二次分類(lèi)第43頁(yè)/共52頁(yè)動(dòng)態(tài)聚類(lèi)法 優(yōu)點(diǎn)：計(jì)算量小，方法簡(jiǎn)便，可以根據(jù)經(jīng)驗(yàn)，先作主觀分類(lèi)。缺點(diǎn)：結(jié)果受選擇凝聚點(diǎn)好壞的影響，分類(lèi)結(jié)果不穩(wěn)定。 第44頁(yè)/共52頁(yè)第一，選擇凝聚點(diǎn)；第二，初始分類(lèi)； 對(duì)于取定的凝聚點(diǎn)，視每個(gè)凝聚點(diǎn)為一類(lèi)，將每個(gè)樣品根據(jù)定義的距離向最近的凝聚點(diǎn)歸類(lèi)。第三，修改分類(lèi) 得到初始分類(lèi)，計(jì)算各類(lèi)的重心，以這些重心作為新的凝聚點(diǎn)，重新進(jìn)行分類(lèi)，重復(fù)步驟2，3，直到分類(lèi)的結(jié)果與上一步的分類(lèi)結(jié)果相同，表明分類(lèi)已經(jīng)合理為止。動(dòng)態(tài)聚類(lèi)法的基本步驟：第45頁(yè)/共52頁(yè)例3：某商店5位售貨員的銷(xiāo)售量和教育程度如下表：售貨員售貨員