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

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

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

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

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

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

6、大利語，波蘭語，匈牙利語和芬蘭語的1,2,10的拼法，希望計算這11種語言之間的語言的距離.第10頁/共52頁11種歐洲語言的數(shù)詞第11頁/共52頁選擇適用的距離選擇適用的距離 在聚類分析中通常要結(jié)合實際問題來選擇適用的距離, 有時應(yīng)根據(jù)實際問題定義新的距離, 顯然，本例無法直接用上述公式來計算距離。但可以發(fā)現(xiàn)前三種文字(英、挪、丹)很相似, 特別是每個單詞的第一個字母。可以用10個數(shù)詞中第一個字母不同的個數(shù)來定義兩種語言之間的距離。例如：英語和挪威語中只有1和8的第一個字母不同, 則它們之間的距離為2。第12頁/共52頁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頁/共52頁2112121nkkjnkkinkkjkiijxxxxCnknkjkjikinkjkjikiijxxxxxxxxr11221)()()(1、夾角余弦2、相關(guān)系數(shù)R型聚類統(tǒng)計量 對兩個指標(biāo)之間的相似程度用相似系數(shù)來刻劃，相似系數(shù)絕對對值越接近于1，表示指標(biāo)間的關(guān)系越密切，絕對值越接近于0，表示

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

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

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

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

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

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

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

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

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

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

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