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

1、聚類分析,分類,俗語說，物以類聚、人以群分。 但什么是分類的根據(jù)呢？ 比如，要想把中國的縣分成若干類，就有很多種分類法； 可以按照自然條件來分， 比如考慮降水、土地、日照、濕度等各方面； 也可以考慮收入、教育水準(zhǔn)、醫(yī)療條件、基礎(chǔ)設(shè)施等指標(biāo)； 既可以用某一項(xiàng)來分類，也可以同時(shí)考慮多項(xiàng)指標(biāo)來分類。,聚類分析,對(duì)于一個(gè)數(shù)據(jù)，人們既可以對(duì)變量（指標(biāo)）進(jìn)行分類(相當(dāng)于對(duì)數(shù)據(jù)中的列分類)，也可以對(duì)觀測(cè)值（事件，樣品）來分類（相當(dāng)于對(duì)數(shù)據(jù)中的行分類）。 比如學(xué)生成績(jī)數(shù)據(jù)就可以對(duì)學(xué)生按照理科或文科成績(jī)（或者綜合考慮各科成績(jī)）分類， 當(dāng)然，并不一定事先假定有多少類，完全可以按照數(shù)據(jù)本身的規(guī)律來分類。 本章要介紹

2、的分類的方法稱為聚類分析（cluster analysis）。對(duì)變量的聚類稱為R型聚類，而對(duì)觀測(cè)值聚類稱為Q型聚類。這兩種聚類在數(shù)學(xué)上是對(duì)稱的，沒有什么不同。,飲料數(shù)據(jù)（drink.sav ）,16種飲料的熱量、咖啡因、鈉及價(jià)格四種變量,如何度量遠(yuǎn)近？,如果想要對(duì)100個(gè)學(xué)生進(jìn)行分類，如果僅僅知道他們的數(shù)學(xué)成績(jī)，則只好按照數(shù)學(xué)成績(jī)來分類；這些成績(jī)?cè)谥本€上形成100個(gè)點(diǎn)。這樣就可以把接近的點(diǎn)放到一類。 如果還知道他們的物理成績(jī)，這樣數(shù)學(xué)和物理成績(jī)就形成二維平面上的100個(gè)點(diǎn)，也可以按照距離遠(yuǎn)近來分類。 三維或者更高維的情況也是類似；只不過三維以上的圖形無法直觀地畫出來而已。在飲料數(shù)據(jù)中，每種飲料

3、都有四個(gè)變量值。這就是四維空間點(diǎn)的問題了。,兩個(gè)距離概念,按照遠(yuǎn)近程度來聚類需要明確兩個(gè)概念：一個(gè)是點(diǎn)和點(diǎn)之間的距離，一個(gè)是類和類之間的距離。 點(diǎn)間距離有很多定義方式。最簡(jiǎn)單的是歐氏距離，還有其他的距離。 當(dāng)然還有一些和距離相反但起同樣作用的概念，比如相似性等，兩點(diǎn)越相似度越大，就相當(dāng)于距離越短。 由一個(gè)點(diǎn)組成的類是最基本的類；如果每一類都由一個(gè)點(diǎn)組成，那么點(diǎn)間的距離就是類間距離。但是如果某一類包含不止一個(gè)點(diǎn)，那么就要確定類間距離， 類間距離是基于點(diǎn)間距離定義的：比如兩類之間最近點(diǎn)之間的距離可以作為這兩類之間的距離，也可以用兩類中最遠(yuǎn)點(diǎn)之間的距離作為這兩類之間的距離；當(dāng)然也可以用各類的中心之間

4、的距離來作為類間距離。在計(jì)算時(shí)，各種點(diǎn)間距離和類間距離的選擇是通過統(tǒng)計(jì)軟件的選項(xiàng)實(shí)現(xiàn)的。不同的選擇的結(jié)果會(huì)不同，但一般不會(huì)差太多。,聚類分析（Cluster Analysis）是研究“物以類聚”的一種多元統(tǒng)計(jì)方法。國內(nèi)有人稱它為群分析、點(diǎn)群分析、簇群分析等。,一、聚類分析的基本概念,3、職能是建立一種能按照樣品或變量的相 似程度進(jìn)行分類的方法。,1、研究對(duì)樣品或指標(biāo)進(jìn)行分類的一種多元統(tǒng)計(jì)方法,是依據(jù)研究對(duì)象的個(gè)體的特征進(jìn)行分類的方法。,2、聚類分析把分類對(duì)象按一定規(guī)則分成若干類，這些類非事先給定的，而是根據(jù)數(shù)據(jù)特征確定的。在同一類中這些對(duì)象在某種意義上趨向于彼此相似，而在不同類中趨向于不相似。

5、,R型聚類分析的主要作用： 不但可以了解個(gè)別變量之間的親疏程度，而且可以了解各個(gè)變量組合之間的親疏程度。 根據(jù)變量的分類結(jié)果以及它們之間的關(guān)系，可以選擇主要變量進(jìn)行Q型聚類分析或回歸分析。（R2為選擇標(biāo)準(zhǔn)） Q型聚類分析的主要作用： 可以綜合利用多個(gè)變量的信息對(duì)樣本進(jìn)行分析。 分類結(jié)果直觀，聚類譜系圖清楚地表現(xiàn)數(shù)值分類結(jié)果。 聚類分析所得到的結(jié)果比傳統(tǒng)分類方法更細(xì)致、全面、合理。,聚類分析的分類,在課堂上主要討論Q型聚類分析.,那么Q型系統(tǒng)聚類法則可以表述為： 把樣本看成n維空間的點(diǎn)，而把變量看成n維空間的坐標(biāo)軸，m個(gè)樣本開始時(shí)自成一類，然后規(guī)定各類之間的距離，將距離最小的一對(duì)并成一類，然后再

6、計(jì)算距離，直到所有單位全部合并為止。,二、距離,用 表示第i個(gè)樣本與第j個(gè)樣本之間的距離。一切距離應(yīng)滿足以下條件：,每個(gè)樣本有p個(gè)指標(biāo)，因此每個(gè)樣本可以看成p維空間中的一個(gè)點(diǎn)，n個(gè)樣本就組成p維空間中的n個(gè)點(diǎn)，這時(shí)很自然想到用距離來度量n個(gè)樣本間的接近程度。,常見的距離有：,minkowski distance （明氏距離）：,當(dāng) q=1 block distance 絕對(duì)值距離:,當(dāng) q=2 squared euclidean distance 平方歐式距離,當(dāng)q= chebychev distance 切比雪夫距離,明氏距離在實(shí)際中應(yīng)用的很多，但也存在一些缺點(diǎn)：,處理辦法：標(biāo)準(zhǔn)化,2、指標(biāo)

7、間的相關(guān)問題；,1、量綱的問題；,Mahalanobis 馬氏距離,改進(jìn)的辦法，采用馬氏距離,相似系數(shù),夾角余弦,相關(guān)系數(shù), 夾角余弦 兩變量的夾角余弦定義為：, 相關(guān)系數(shù) 兩變量的相關(guān)系數(shù)定義為：,18,四、樣本數(shù)據(jù)與小類、小類與小類之間的度量,1 、最短距離（Nearest Neighbor),19,最長(zhǎng)距離（Furthest Neighbor ）,20,組間平均連接（Between-group Linkage),21,1 、組內(nèi)平均連接法（Within-group Linkage),22,重心法（Centroid clustering):均值點(diǎn)的距離,23,離差平方和法連接,2，4,1，

8、5,6，5,24,紅綠（2，4，6，5）8.75 離差平方和增加8.752.56.25 黃綠（6，5，1，5）14.75 離差平方和增加14.758.56.25 黃紅（2，4，1，5）10100 故按該方法的連接和黃紅首先連接。,類的個(gè)數(shù)的確定,由適當(dāng)?shù)拈撝荡_定； 根據(jù)數(shù)據(jù)點(diǎn)的散布直觀地確定類的個(gè)數(shù)； 根據(jù)統(tǒng)計(jì)量確定分類個(gè)數(shù)；,類的個(gè)數(shù)的確定,根據(jù)譜系圖確定分類個(gè)數(shù)的準(zhǔn)則： 各類重心間的距離必須很大； 類中保包含的元素不要太多； 類的個(gè)數(shù)必須符合實(shí)際應(yīng)用； 如果采用幾種不同的聚類方法處理，則在各種聚類圖中應(yīng)該發(fā)現(xiàn)相同的類。,聚類分析,1、系統(tǒng)聚類法-（分層聚類）系統(tǒng)聚類法是應(yīng)用最廣泛的一種（H

9、ierarchical Cluster過程） 1）、 聚類原則：都是相近的聚為一類，即距離最近或最相似的聚為 一類。 2）、 分層聚類的方法可以用于樣本聚類（Q）型，也可以用于變量聚類（R型）。 2、非系統(tǒng)聚類法-（快速聚類法-K-均值聚類法）（K-means Cluster) 3、兩步聚類法-一種探索性的聚類方法（TwoStep Cluster）,K-均值聚類分析 K-means Cluster,又稱為快速樣本聚類法，是非系統(tǒng)聚類中最常用的聚類法。 優(yōu)點(diǎn)： 是占內(nèi)存少、計(jì)算量小、處理速度快，特別適合大樣本的聚類分析。 缺點(diǎn)： 應(yīng)用范圍有限，要求用戶制定分類數(shù)目(要告知)，只能對(duì)觀測(cè)量（樣本）

10、聚類，而不能對(duì)變量聚類，且所使用的聚類變量必須都是連續(xù)性變量。,數(shù)據(jù)標(biāo)準(zhǔn)化處理：,存儲(chǔ)中間過程數(shù)據(jù),數(shù)據(jù)標(biāo)準(zhǔn)化處理，并存儲(chǔ)。,指定5類,收斂標(biāo)準(zhǔn)值,存儲(chǔ)最終結(jié)果輸出情況，在數(shù)據(jù)文件中（QCL-1、QCL-2）,初始聚心選項(xiàng)，輸出方差分析表,初始聚類中心表,具體城市看后表,最終聚類中心表,聚類結(jié)果：QCL-1說明聚類結(jié)果，QCL-2說明聚類的長(zhǎng)度情況,系統(tǒng)聚類法 Hierarchical Cluster,系統(tǒng)聚類法優(yōu)點(diǎn)： 既可以對(duì)觀測(cè)量（樣品）也可對(duì)變量進(jìn)行聚類，既可以連續(xù)變量也可以是分類變量，提供的距離計(jì)算方法和結(jié)果顯示方法也很豐富。,系統(tǒng)聚類法基本步驟,7.決定類的個(gè)數(shù)和類。,1. 選擇樣本

11、間距離的定義及類間距離的定義；,2. 計(jì)算n個(gè)樣本兩兩之間的距離，得到距離矩陣；,3. 構(gòu)造個(gè)類，每類只含有一個(gè)樣本,4. 合并符合類間距離定義要求的兩類為一個(gè)新類；,5. 計(jì)算新類與當(dāng)前各類的距離。若類的個(gè)數(shù)為1， 則轉(zhuǎn)到步驟6，否則回到步驟4;,6.畫出聚類圖；,系統(tǒng)聚類分析的方法,以下用dij表示樣品X(i)和X(j)之間的距離，當(dāng)樣品間的親疏關(guān)系采用相似系數(shù)Cij時(shí)，令,系統(tǒng)聚類法的聚類原則決定于樣品間的距離以及類間距離的定義，類間距離的不同定義就產(chǎn)生了不同的系統(tǒng)聚類分析方法。,以下用D(p,q)表示類Gp和Gq之間的距離,例,為了研究遼寧等5省1991年城鎮(zhèn)居民生活消費(fèi)情況的分布規(guī)律

12、，根據(jù)調(diào)查資料做類型分類，用最短距離做類間分類。數(shù)據(jù)如下：,將每一個(gè)省區(qū)視為一個(gè)樣本，先計(jì)算5個(gè)省區(qū)之間的歐式距離，用D0表示距離矩陣（對(duì)稱陣，故給出下三角陣） 因此將3.4合并為一類，為類6，替代了3、4兩類 類6與剩余的1、2、5之間的距離分別為： d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12 d(3,4)2=min(d32,d42)=min(24.63,24.06)=24.06 d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21,得到新矩陣 合并類6和類5，得到新類7 類7與剩余的1、2之間的距離分別為： d(5,6

13、)1=min(d51,d61)=min(12.80,13.12)=12.80 d(5,6)2=min(d52,d62)=min(23.54,24.06)=23.54,得到新矩陣 合并類1和類2，得到新類8 此時(shí)，我們有兩個(gè)不同的類：類7和類8。 它們的最近距離 d(7,8) =min(d71,d72)=min(12.80,23.54)=12.80,得到矩陣 最后合并為一個(gè)大類。這就是按最短距離定義類間距離的系統(tǒng)聚類方法。最長(zhǎng)距離法類似！,主要城市日照時(shí)數(shù),注：連續(xù)變量,SPSS提供不同類間距離的測(cè)量方法 1、組間連接法 2、組內(nèi)連接法 3、最近距離法 4、最遠(yuǎn)距離法 5、重心法 6、中位數(shù)法

14、7、Ward最小偏差平方和法,觀測(cè)量概述表,聚類步驟，與圖結(jié)合看！,研究各種飲料在市場(chǎng)消費(fèi)的分配規(guī)律，試確定各種飲料消費(fèi)類型,聚類分析的第幾步,哪兩個(gè)樣本或小類聚成一類,相應(yīng)的樣本距離或小類距離,指明是樣本(0)還是小類(n),下面第幾步用到,垂直冰柱圖顯示層次聚類分析,從冰柱圖最后一行開始觀察，第一列表示類數(shù),兩步聚類法 TwoStep Cluster,一種探索性的聚類方法，是隨著人工智能的發(fā)展起來的智能聚類方法中的一種。用于解決海量數(shù)據(jù)或具有復(fù)雜類別結(jié)構(gòu)的聚類分析問題。,兩步聚類法特點(diǎn)： 1、同時(shí)處理離散變量和連續(xù)變量的能力 2、自動(dòng)選擇聚類數(shù) 3、通過預(yù)先選取樣本中的部分?jǐn)?shù)據(jù)構(gòu)建聚類模型 4、可以處理超大樣本量的數(shù)據(jù),簡(jiǎn)單介紹基本原理 分兩步進(jìn)行 第一步：預(yù)聚類。對(duì)記錄進(jìn)行初始的歸類，用戶自定義最大類別數(shù)。通過構(gòu)建和修改特征樹（CT Free）完成。 第二步：正式聚類。對(duì)第一步完成的初步聚類進(jìn)行再聚類并確定最終的聚類方案，系統(tǒng)根據(jù)一定的統(tǒng)計(jì)標(biāo)準(zhǔn)確定聚類的類別數(shù)目。 以后，可以通