數學實驗05聚類分析.ppt

《數學實驗05聚類分析.ppt》由會員分享，可在線閱讀，更多相關《數學實驗05聚類分析.ppt（52頁珍藏版）》請在裝配圖網上搜索。

聚類分析,俗話說：“物以類聚，人以群分”，在自然科學和社會科學中，存在著大量的分類問題。所謂類，通俗地說，就是指相似元素的集合。聚類分析又稱群分析，它是研究（樣品或指標）分類問題的一種統(tǒng)計分析方法。聚類分析起源于分類學，在古老的分類學中，人們主要依靠經驗和專業(yè)知識來實現分類，很少利用數學工具進行定量的分類。隨著人類科學技術的發(fā)展，對分類的要求越來越高，以致有時僅憑經驗和專業(yè)知識難以確切地進行分類，于是人們逐漸地把數學工具引用到了分類學中，形成了數值分類學，之后又將多元分析的技術引入到數值分類學形成了聚類分析。聚類分析內容非常豐富，有系統(tǒng)聚類法、有序樣品聚類法、動態(tài)聚類法、模糊聚類法、圖論聚類法、聚類預報法等。,第一節(jié)聚類分析方法第二節(jié)聚類統(tǒng)計量第三節(jié)數據變換方法第四節(jié)系統(tǒng)聚類法第五節(jié)k-均值聚類法,第一節(jié)聚類分析方法,聚類分析是根據“物以類聚”的道理，對樣品或指標進行分類的一種多元統(tǒng)計分析方法，它們討論的對象是大量的樣品，要求能合理地按各自的特性來進行合理的分類，沒有任何模式可供參考或依循，即是在沒有先驗知識的情況下進行的。基本思想是根據事物本身的特性研究個體分類的方法；聚類原則是同一類中的個體有較大的相似性，不同類中的個體差異很大。,基本程序：是根據一批樣品的多個觀測指標，具體地找出一些能夠度量樣品或指標之間相似程度的統(tǒng)計量，然后利用統(tǒng)計量將樣品或指標進行歸類。具體進行聚類時，由于目的、要求不同，因而產生各種不同的聚類方法：由小類合并到大類的方法由大類分解為小類的方法靜態(tài)聚類法、動態(tài)聚類法按樣本聚類（Q）、按指標聚類（R）,飲料數據,16種飲料的熱量、咖啡因、鈉及價格四種變量,第二節(jié)聚類統(tǒng)計量,一、概述二、Q型聚類統(tǒng)計量三、R型聚類統(tǒng)計量,概述,設有n個樣本單位，每個樣本測得p項指標（變量），原始資料陣為：Q型聚類一般以距離作為統(tǒng)計量，R型聚類一般以相似系數作為統(tǒng)計量。,Q型聚類統(tǒng)計量（距離）,把n個樣本點看成p維空間的n個點1、絕對距離（Block距離）2、歐氏距離(Euclideandistance),3、明考斯基距離(Minkowski)4、蘭氏距離5、馬氏距離6、切比雪夫距離(Chebychev),R型聚類統(tǒng)計量,對兩個指標之間的相似程度用相似系數來刻劃，相似系數的絕對值越接近于1，表示指標間的關系越密切，絕對值越接近于0，表示指標間的關系越疏遠。,1、夾角余弦2、相關系數,距離和相似系數選擇的原則一般說來，同一批數據采用不同的親疏測度指標，會得到不同的分類結果。產生不同結果的原因，主要是由于不同的親疏測度指標所衡量的親疏程度的實際意義不同，也就是說，不同的親疏測度指標代表了不同意義上的親疏程度。因此我們在進行聚類分析時，應注意親疏測度指標的選擇。通常，選擇親疏測度指標時，應注意遵循的基本原則主要有：,(2)親疏測度指標的選擇要綜合考慮已對樣本觀測數據實施了的變換方法和將要采用的聚類分析方法。如在標準化變換之下，夾角余弦實際上就是相關系數；又如若在進行聚類分析之前已經對變量的相關性作了處理，則通常就可采用歐氏距離，而不必選用斜交空間距離。此外，所選擇的親疏測度指標，還須和所選用的聚類分析方法一致。,(1)所選擇的親疏測度指標在實際應用中應有明確的意義。如在經濟變量分析中，常用相關系數表示經濟變量之間的親疏程度。,(3)適當地考慮計算工作量的大小。如對大樣本的聚類問題，不適宜選擇斜交空間距離，因采用該距離處理時，計算工作量太大。樣品間或變量間親疏測度指標的選擇是一個比較復雜且?guī)е饔^性的問題，我們應根據研究對象的特點作具體分折，以選擇出合適的親疏測度指標。實踐中，在開始進行聚類分析時，不妨試探性地多選擇幾個親疏測度指標，分別進行聚類，然后對聚類分析的結果進行對比分析，以確定出合適的親疏測度指標。,第三節(jié)數據變換方法,所謂數據變換（無量綱化）處理，是將原始數據矩陣中每個元素按照某種特定的運算把它變成一個新值，且是數值的變化不依賴于原始數據中其它數據的新值。,1、中心化變換中心化變換是一種坐標軸平移處理方法，它是先求出每個變量的樣本平均值，再從原始數據中減去該變量的均值，就得到中心化變換后的數據。設原始觀測數據矩陣為：,中心化變換的結果是使每列數據之和均為0，即每個變量的均值為0，而且每列數據的平方和是該列變量樣本方差的(n—1)倍，任何不同兩列數據之交叉乘積之和是這兩列變量樣本協方差的n倍，所以這是一種很方便地計算方差與協方差的變換。,2、極差規(guī)格化變換規(guī)格化變換是從數據矩陣的每一個變量中找出其最大值和最小值，這兩者之差稱為極差，然后從每個變量的每個原始數據中減去該變量中的最小值，再除以極差，就得到規(guī)格化數據。即有：,經過規(guī)格化變換后，數據矩陣中每列即每個變量的最大數值為1，最小數值為0，其余數據取值均在0－1之間；并且變換后的數據都不再具有量綱，便于不同的變量之間的比較。,3、標準化變換標準化變換也是對變量的數值和量綱進行類似于規(guī)格化變換的一種數據處理方法。首先對每個變量進行中心化變換，然后用該變量的標準差進行標準化。即有：,經過標準化變換處理后，每個變量即數據矩陣中每列數據的平均值為0，方差為1，且也不再具有量綱，同樣也便于不同變量之間的比較。變換后，數據短陣中任何兩列數據乘積之和是兩個變量相關系數的n倍，所以這是一種很方便地計算相關矩陣的變換。,4．對數變換對數變換是將各個原始數據取對數，將原始數據的對數值作為變換后的新值。即：,例：某年我國部分省市經濟效益情況用以上幾種方法對其進行數據變換。,第四節(jié)系統(tǒng)聚類法,系統(tǒng)聚類法（層次聚類法）：在聚類分析的開始，每個樣本自成一類；然后，按照某種方法度量所有樣本之間的親疏程度，并把最相似（近）的樣本首先聚成一小類；接下來，度量剩余的樣本和小類間的親疏程度，并將當前最接近的樣本或小類再聚成一類；再接下來，再度量剩余的樣本和小類間的親疏程度，并將當前最接近的樣本或小類再聚成一類；如此反復，直到所有樣本聚成一類為止。越是后來合并的類，距離就越遠。,步驟：,1、對數據進行變換處理，消除量綱2、構造n個類，每個類只包含一個樣本計算3、n個樣本兩兩間的距離{dij}4、合并距離最近的兩類為一新類5、計算新類與當前各類的距離，重復（4）6、畫聚類圖7、決定類的個數和類,1、對數據進行變換處理，消除量綱2、構造n個類，每個類只包含一個樣本計算3、n個樣本兩兩間的距離{dij}4、合并距離最近的兩類為一新類5、計算新類與當前各類的距離，重復（4）6、畫聚類圖7、決定類的個數和類,類與類間距離的確定,一、最短距離法二、最長距離法三、中間距離法四、重心距離法五、類平均法六、離差平方和,最短距離法(NearestNeighbor),以當前某個樣本與已經形成的小類中的各樣本距離中的最小值作為當前樣本與該小類之間的距離。,,例1：為了研究遼寧省等5省區(qū)某年城鎮(zhèn)居民生活消費的分布規(guī)律，根據調查資料做類型劃分,,,C1={遼寧}，C2={浙江}，C3={河南}，C4={甘肅}，C5={青海}d12=[(7.9-7.68)2+(39.77-50.37)2+(8.49-11.35)2+(12.94-13.3)2+(19.27-19.25)2+(11.05-14.59)2+(2.04-2.75)2+(13.29-14.87)2]0.5=11.67d13=13.80d14=13.12d15=12.80d23=24.63d24=24.06d25=23.54d34=2.2d35=3.51d45=2.2112345D1=10211.670313.8024.630413.1224.062.200512.8023.543.512.210,,,河南與甘肅的距離最近，先將二者（3和4）合為一類C6={C2，C4},,,,d61=d(3,4)1=min{d13,d14}=13.12d62=d(3,4)2=min{d23,d24}=24.06d65=d(3,4)5=min{d35,d45}=2.21612560D2=113.120224.0611.67052.2112.8023.540d71=d(3,4,5)1=min{d13,d14,d15}=12.80d72=d(3,4,5)2=min{d23,d24,d25}=23.54712D3=70112.800223.5411.670,,,河南、甘肅與青海并為一新類C7={C6，C5}={C3，C4，C6},,,C8={C1,C2},,,,,d78=min{d71,d72}=12.8078D4=70812.80河南3甘肅4青海5遼寧1浙江2,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,最長距離法(furthestneighbor),以當前某個樣本與已經形成的小類中的各樣本距離中的最大值作為當前樣本與該小類之間的距離。,,例2：對例1的數據以最長距離法聚類。,,d13=13.80d14=13.12d15=12.80d23=24.63d24=24.06d25=23.54d34=2.2d35=3.51d45=2.2112345D1=10211.670313.8024.630413.1224.062.200512.8023.543.512.210d61=d(3,4)1=max{d13,d14}=13.80d62=d(3,4)2=max{d23,d24}=24.63d65=d(3,4)5=max{d35,d45}=3.51612560D2=113.800224.6311.67053.5112.8023.540,,,,,,河南與甘肅的距離最近，先將二者（3和4）合為一類C6={C3，C4},河南、甘肅與青海并為一新類C7={C6，C5}={C3，C4，C6},,,,d71=d(3,4,5)1=max{d13,d14,d15}=13.80d72=d(3,4,5)2=max{d23,d24,d25}=24.63712D3=70113.800224.6311.670d78=max{d71,d72}=24.6378D4=70824.630,,,C8={C1,C2},,,中位數法（Medianclustering),用兩個類的中位數間的距離作為兩類的距離,,,,,,,,,,Gt,Gl,Gm,重心法,用兩類的重心間的距離作為兩類的距離,,,,,,,,,,,,,Gr,Gt,離差平方和法（Ward’smethodword),使小類內各樣本的歐氏距離總平方和增加最小的兩小類合并為一類。將q固定時，要選擇使S達到極小的分類，一切可能的分法有：,Ward尋找到一個局部最優(yōu)解的方法。先將n個樣本各成一類，然后每次縮小一類，每縮小一類離差平方和就要增大，選擇使離差平方和S增加最小的兩類合并，直至所有樣本歸為一類為止。,飲料數據,16種飲料的熱量、咖啡因、鈉及價格四種變量,對于飲料聚類。輸出為,確定類的個數,在聚類分析過程中類的個數如何來確定才合適呢？這是一個十分困難的問題，人們至今仍未找到令人滿意的方法。但是這個問題又是不可回避的。簡單的做法是根據實際問題給定一個特定的閾值。,給定閾值——通過觀測聚類圖，給出一個合適的閾值T。要求類與類之間的距離不要超過T值。,系統(tǒng)聚類可以不事先確定有多少類；但是這里的k-均值聚類（k-meanscluster，也叫快速聚類，quickcluster）卻要求事先說好要分多少類。看起來有些主觀！假定要分3類，這個方法還進一步要求事先確定3個點為“聚類種子”(凝聚點)；也就是說，把這3個點作為三類中每一類的基石。,第五節(jié)k-均值聚類——事先確定分多少類,然后，根據和這三個點的距離遠近，把所有點分成三類。再把這三類的中心(均值)作為新的基石或種子(原來“種子”就沒用了)，再重新按照距離分類。如此疊代下去，直到達到停止疊代的要求（比如，各類最后變化不大了，或者疊代次數太多了）。顯然，前面的聚類種子的選擇并不必太認真，它們很可能最后還會分到同一類中。下面用飲料例的數據來做k-均值聚類。,第五節(jié)k-均值聚類——事先確定分多少類,K-均值（快速）聚類步驟,1、選擇分析變量2、指定聚類數目3、選擇k個樣本作為凝聚點4、按照距初始類中心最小的原則將各觀察量分到聚類中心所在的類中去，形成第一步迭代的k類5、計算每類中所有變量的均值，作為第二次迭代的中心6、重復4、5步，直至指定的迭代次數或達到終止的條件,飲料數據,16種飲料的熱量、咖啡因、鈉及價格四種變量,假定要把這16種飲料分成3類。利用SPSS，只疊代了三次就達到目標了。這樣就可以得到最后的三類的中心以及每類有多少點,根據需要，可以輸出哪些點分在一起。結果是：第一類為飲料：1、10；第二類為飲料：2、4、8、11、12、13、14；第三類為剩下的飲料：3、5、6、7、9、15、16。,凝聚點的選擇,1、經驗選擇2、對樣本人為或隨機分類，以每類的重心作為凝聚點3、最小最大距離法。如果欲將n個樣本點分為q類，先選取距離最大的兩點xi1,xi2為前兩個凝聚點，然后選取第3個凝聚點xi3，由于其余所有點與前兩個凝聚點都有最短距離，在全部最短距離中選擇最長距離，這個距離的兩端一個是xi1或xi2，而另一個就是我們要選擇的xi3.,聚類結果主要受所選擇的變量影響。如果去掉一些變量，或者增加一些變量，結果會很不同。相比之下，聚類方法的選擇則不那么重要了。因此，聚類之前一定要目標明確。,聚類要注意的問題,聚類要注意的問題,另外就分成多少類來說，也要有道理。只要你高興，從分層聚類的計算機結果中可以得到任何可能數量的類。但是，聚類的目的是要使各類之間的距離盡可能地遠，而類中點的距離盡可能的近，并且分類結果還要有令人信服的解釋。這一點就不是數學可以解決的了。,根據美國等20個國家和地區(qū)的信息基礎設施的發(fā)展狀況進行分類。Call—每千人擁有的電話線數；movel—每千人戶居民擁有的蜂窩移動電話數；fee—高峰時期每三分鐘國際電話的成本；comp—每千人擁有的計算機數；mips—每千人計算機功率（每秒百萬指令）；net—每千人互聯網絡戶主數。,作業(yè)1：分別用系統(tǒng)聚類和K-均值聚類法對下面問題進行分類。,作業(yè)2我國經濟發(fā)展的總目標是到2000年人民生活達到小康標準，因此，了解各地區(qū)目前對小康生活質量的實現程度。對各地區(qū)實現小康生活質量的狀況進行綜合評價，對各級政府部門具有重要意義。數據是1990年全國30個省在經濟（jj）、教育（jy）、健康（jk）和居住環(huán)境（jz）四個方面對小康標準已經實現的程度，1表示已經達到或超過小康水平，0表示低于或剛達到溫飽水平。希望利用該數據對15個地區(qū)進行分類研究。,