數(shù)學(xué)建模-聚類分析

聚類分析

聚類分析概述

系統(tǒng)聚類法

k-means聚類法什么是“聚類”？

根據(jù)同類事物應(yīng)具有相近特性，而不同類在這些事物上的差異較大的假定，將所研究的事物進(jìn)行分類，這種研究方法叫做聚類（Cluster）。聚類方法廣泛應(yīng)用于經(jīng)濟(jì)社會研究當(dāng)中，如自然區(qū)域類型劃分、經(jīng)濟(jì)區(qū)域類型劃分和地區(qū)系統(tǒng)影響因子的劃分等等。

聚類的應(yīng)用（1）對一維特征向量的分組：根據(jù)地面的某些特征分類，如水。一旦這樣分組以后，分析人員就可以通過每一組中的樣本點(diǎn)和地面數(shù)據(jù)的參考信息相聯(lián)系來識別地面類型。聚類的應(yīng)用聚類分析概述

對大量未知標(biāo)注的數(shù)據(jù)集，按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個(gè)類別，使處理后的數(shù)據(jù)具有如下特征：

類間相似度小、類內(nèi)相似度大從統(tǒng)計(jì)學(xué)的觀點(diǎn)看，聚類分析是通過數(shù)學(xué)建模簡化數(shù)據(jù)的一種方法。

聚類分析的分類

根據(jù)對象的不同可分為：

R型：對變量進(jìn)行分類處理

Q型：對樣品進(jìn)行分類處理根據(jù)聚類的方法可分為：模糊聚類法圖論聚類法聚類預(yù)報(bào)法聚類分析的分類

系統(tǒng)聚類法

K-means聚類法有序樣品聚類法聚類分析的分類

系統(tǒng)聚類法：開始每個(gè)對象自成一類，然后每次將最相似的兩類合并，合并后重新計(jì)算新類與其他類之間的距離或相似系數(shù)。

K-means聚類法：首先對n個(gè)對象初步分類，然后根據(jù)分類的損失函數(shù)盡可能小的原則對分類進(jìn)行調(diào)整，直到分類合理為止。又稱為動態(tài)聚類法、逐步聚類法.

K

有序樣品聚類法：開始將所有樣品看成一類，然后根據(jù)某種最優(yōu)準(zhǔn)則將它們分割為二類、三類，一直分到K類為止。這種方法適用于有序樣品的分類問題。又稱為最優(yōu)分割法。

模糊聚類法：利用模糊集理論來處理分類問題，它對經(jīng)濟(jì)領(lǐng)域中具有模糊特征的兩態(tài)數(shù)據(jù)或多態(tài)數(shù)據(jù)具有明顯的分類效果。

聚類分析的分類

圖論聚類法：利用圖論中最小支撐樹的概念來處理分類問題，創(chuàng)造了獨(dú)具風(fēng)格的方法。

聚類預(yù)報(bào)法：利用聚類方法處理預(yù)報(bào)問題，在多元統(tǒng)計(jì)分析中，可以用來做預(yù)報(bào)的方法很多，如回歸分析，判別分析。但對一些異常數(shù)據(jù)，如氣象中的災(zāi)害性天氣的預(yù)報(bào)，回歸或判別分析處理的效果不好，而聚類預(yù)報(bào)彌補(bǔ)了這一不足。聚類分析的分類我們最常用的是：定量數(shù)據(jù)的Q型聚類分析問題系統(tǒng)聚類法基本思想：開始每個(gè)對象自成一類，然后每次將最相似的兩類合并，合并后重新計(jì)算新類與其他類之間的距離或相似系數(shù)。步驟：（1）數(shù)據(jù)變換；（2）樣品間距離：計(jì)算n個(gè)樣品兩兩之間的距離，得出樣品間的距離矩陣D(0);（3）類間距離：首先n個(gè)樣品各自構(gòu)成一類，即共有k=n類注：此時(shí)類間距離就是樣品之間的距離；（4）分類處理：每次合并類間距離最小的兩類為一新類；滿足，輸出；不滿足，則：（5）重復(fù)：計(jì)算新類與其它類間的距離，得到新的距離矩陣（1）成數(shù)化法：

（2）中心化變換：數(shù)據(jù)變換數(shù)據(jù)變換（3）標(biāo)準(zhǔn)化變換：（4）極差標(biāo)準(zhǔn)化變換數(shù)據(jù)變換（5）極差正規(guī)化變換:

（6）對數(shù)變換:k樣品間的距離

（1）絕對值距離：（2）歐氏距離：

樣品間的距離（3）切比雪夫距離（4）蘭氏距離：（5）馬氏距離、斜交空間距離…類間距離的計(jì)算

聚類原則決定于樣品間的距離（或相似系數(shù)）、類間距離的定義，類間距離的不同定義就產(chǎn)生了不同的聚類方法。（1）最短距離法：類與類之間的距離定義為兩類中最近樣品之間的距離即類與類之間的距離定義為：注：Gp表示Gp

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

（2）最長距離法：類與類之間的距離定義為兩類最遠(yuǎn)樣品間的距離，即類與類之間的距離定義為

以此類推，當(dāng)某步類與類合并為后，按最長距離法計(jì)算新類與其它類間距離，遞推公式為最短距離最遠(yuǎn)距離a1a2Ab1b2B

類與類之間最短距離與最長距離的關(guān)系可表示為：

（3）中心距離法：類與類之間既不采用最短距離法也不采用最長距離法，而是采用介于兩者之間的距離的方法。當(dāng)某一步類與類合并為后，按中間距離法計(jì)算新類與其它類的類間距離,遞推公式為β一般取中心距離法圖示：

（4）重心法將兩類間的距離定義為兩重心間的距離。每一類的重心就是該類樣品的均值。設(shè)某一步將類與類合并為后，它們所包含的樣品個(gè)數(shù)分別為、和，。重心分別為、和,顯然有：設(shè)某一類的重心為,它與新類的距離是：

重心法圖示:

設(shè)將個(gè)樣品分成類，，…，。用表示中的第個(gè)樣品,表示中樣品的個(gè)數(shù)，是的重心，則的樣品離差平方和為(5)離差平方和法如果分類正確，同類樣品的離差平方和應(yīng)當(dāng)較小，類與類之間的離差平方和較大。K-means系統(tǒng)聚類如果和合并為新類類內(nèi)離差平方和分別為ClusterKClusterLClusterM離差平方和法圖示：例1假設(shè)有5個(gè)產(chǎn)品，分別對每個(gè)產(chǎn)品測得一項(xiàng)質(zhì)量指標(biāo)X，其值如下：1，2，4.5，6，8.試對這5個(gè)產(chǎn)品按質(zhì)量指標(biāo)進(jìn)行分類。舉例應(yīng)用解：設(shè)樣品間距離取歐氏距離，類間距離取最短距離。并設(shè)樣品分別為1）計(jì)算距離如下表k=5步驟：（1）數(shù)據(jù)變換；（2）樣品間距離;(3)類間距離;(4)分類處理；2)將第一和第二合并為新類如下,k=43)將與合并為新類如下,k=34）可將和合并為新類如下，k=25)最后將剩下的兩類合并成一類，并類過程結(jié)束6）畫譜系結(jié)構(gòu)圖返回

K-means聚類法基本思想

步驟：（1）數(shù)據(jù)變換；（2）確定初始類的個(gè)數(shù)；（3）聚類中心的選擇;（4）樣品與類中心的距離；（5）歸類：按順序計(jì)算各樣品與k個(gè)凝聚點(diǎn)的距離，根據(jù)類間距離的定義將所有樣品逐個(gè)歸入k個(gè)凝聚點(diǎn)，得到初始分類結(jié)果。（6）重新計(jì)算每個(gè)類的中心：重新各類的每個(gè)類的中心，作為新的凝聚點(diǎn)。當(dāng)所有樣品歸類后才計(jì)算該類的類中心。注：每個(gè)樣品一歸類，立即計(jì)算該類的類中心。滿足輸出；不滿足循環(huán)；（7）重復(fù)；初始聚類中心的選擇

初始聚類中心的選取決定著計(jì)算的迭代次數(shù)，甚至決定著最終的解是否為全局最優(yōu)，所以選擇一個(gè)好的初始聚類中心是很有必要的。

（1）方法一：選取前k個(gè)樣品作為初始凝聚點(diǎn)。(2)方法二：選擇第一個(gè)樣本點(diǎn)作為第一個(gè)聚類中心。然后選取距離第一個(gè)點(diǎn)最遠(yuǎn)的點(diǎn)作為第二個(gè)聚類中心。……

第j個(gè)聚類中心要遠(yuǎn)離第1~j-1個(gè)聚類中心重新計(jì)算每個(gè)類的中心

異同點(diǎn)有：k-均值算法和k-中心算法都屬于聚類分析中的分類方法；k-均值算法是將類中對象的均值作為類的中心，可以是一個(gè)虛點(diǎn)，計(jì)算其他點(diǎn)與各個(gè)類中心距離，歸入距離最近的類中；k-中心算法是找類中最中心的點(diǎn)作為類中心，是一個(gè)實(shí)際存在數(shù)據(jù)點(diǎn)。這只是均值與中心區(qū)別，兩種算法具體流程還是不同的。返

（1）k均值算法，其中每個(gè)類都用該類中對象的均值來表示。（2）k中心點(diǎn)算法，其中每個(gè)類用接近類中心的一個(gè)對象來表示。中國男足近幾年到底在亞洲處于幾流水平？下圖是采集的亞洲15只球隊(duì)在2005年-2010年間大型杯賽的戰(zhàn)績舉例應(yīng)用

對數(shù)據(jù)做了如下預(yù)處理：對于世界杯，進(jìn)入決賽圈則取其最終排名，沒有進(jìn)入決賽圈的，打入預(yù)選賽十強(qiáng)賽賦予40，預(yù)選賽小組未出線的賦予50。對于亞洲杯，前四名取其排名，八強(qiáng)賦予5，十六強(qiáng)賦予9，預(yù)選賽沒出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。處理后的數(shù)據(jù)如下：數(shù)據(jù)變換：進(jìn)行[0,1]規(guī)格化得到

設(shè)k=3，即將這15支球隊(duì)分成三個(gè)集團(tuán)。現(xiàn)抽取日本、巴林和泰國的值作為三個(gè)類的種子，即初始化三個(gè)類的中心為A：{0.3,0,0.19}；B：{0.7,0.76,0.5}；C：{1,1,0.5}；初始類個(gè)數(shù)的選擇；初始類中心的選擇；

計(jì)算所有球隊(duì)分別對三個(gè)中心點(diǎn)的歐氏距離。下面是用程序求取的結(jié)果：第一次聚類結(jié)果：A：日本，韓國，伊朗，沙特；B：烏茲別克斯坦，巴林，朝鮮；C：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼。樣品到類中心的距離；歸類；下面根據(jù)第一次聚類結(jié)果，采用k-均值法調(diào)整各個(gè)類的中心點(diǎn)。A類的新中心點(diǎn)為：{(0.3+0+0.24+0.3)/4=0.21,(0+0.15+0.76+0.76)/4=0.4175,(0.19+0.13+0.25+0.06)/4=0.1575}={0.21,0.4175,0.1575}（算術(shù)平均數(shù)。）用同樣的方法計(jì)算得到B和C類的新中心點(diǎn)分別為B：{0.7,0.7333,0.4167}，C:{1,0.94,0.40625}。重新計(jì)算類中心；

用調(diào)整后的中心點(diǎn)再次進(jìn)行聚類，得到：第二次迭代后的結(jié)果為：A類：日本，韓國，伊朗，沙特；B類：烏茲別克斯坦，巴林，朝鮮；C類：伊拉克，卡塔爾，阿聯(lián)酋，中國，泰國，越南，阿曼，印尼；結(jié)果無變化，說明結(jié)果已收斂，于是給出最終聚類結(jié)果：亞洲一流：日本，韓國，伊朗，沙特亞洲二流：烏茲別克斯坦，巴林，朝鮮亞洲三流：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼看來數(shù)據(jù)告訴我們，說國足近幾年處在亞洲三流水平真的是沒有冤枉他們，至少從國際杯賽戰(zhàn)績是這樣的。其實(shí)上面的分析數(shù)據(jù)不僅告訴了我們聚類信息，還提供了一些其它有趣的信息，例如從中可以定量分析出各個(gè)球隊(duì)之間的差距，例如，在亞洲一流隊(duì)伍中，日本與沙特水平最接近，而伊朗則相距他們較遠(yuǎn)，這也和近幾年伊朗沒落的實(shí)際相符。

系統(tǒng)聚類法:需要計(jì)算出不同樣品或變量的距離，還要在聚類的每一步都要計(jì)算“類間距離”，