第十二章 聚類分析課件

第十二章聚類分析第十三章聚類分析第十二章聚類分析聚類分析是研究分類問題的一種多元統(tǒng)計(jì)方法。所謂類，就是指相似元素的集合聚類分析的研究目的把相似的東西歸成類，根據(jù)相似的程度將研究目標(biāo)進(jìn)行分類。第一節(jié)認(rèn)識(shí)聚類分析第十二章聚類分析距離：測(cè)度樣品之間的親疏程度。將每一個(gè)樣品看作p維空間的一個(gè)點(diǎn)，并用某種度量測(cè)量點(diǎn)與點(diǎn)之間的距離，距離較近的歸為一類，距離較遠(yuǎn)的點(diǎn)應(yīng)屬于不同的類。相似系數(shù)：測(cè)度變量之間的親疏程度距離和相似系數(shù)第十二章聚類分析聚類分析的研究對(duì)象R型分析----對(duì)變量進(jìn)行分類Q型分析----對(duì)樣品進(jìn)行分類聚類分析研究的主要內(nèi)容如何度量事物之間的相似性?怎樣構(gòu)造聚類的具體方法以達(dá)到分類的目的?第十二章聚類分析2、常用的距離(1)明氏距離設(shè)原始數(shù)據(jù)為第十二章聚類分析第十二章聚類分析123452018104471055325.236.328.911.517歐氏距離切比雪夫距離第十二章聚類分析明考夫斯基距離有以下兩個(gè)缺點(diǎn)：①明氏距離的數(shù)值與指標(biāo)的量綱有關(guān)。當(dāng)各變量的測(cè)量值相差懸殊時(shí)，常發(fā)生“大數(shù)吃小數(shù)”的現(xiàn)象，為消除量綱的影響，通常先將每個(gè)變量進(jìn)行標(biāo)準(zhǔn)化。②明氏距離的定義沒有考慮各個(gè)變量之間相關(guān)性的影響。年齡收入家庭人口數(shù)甲3030001乙4032003第十二章聚類分析(2)標(biāo)準(zhǔn)化的歐氏距離設(shè)原始數(shù)據(jù)為

第十二章聚類分析

第十二章聚類分析(3)馬氏距離

由印度著名統(tǒng)計(jì)學(xué)家馬哈拉諾比斯(Mahalanobis)所定義的一種距離，其計(jì)算公式為：

=第十二章聚類分析馬氏距離又稱為廣義歐氏距離。馬氏距離考慮了觀測(cè)變量之間的相關(guān)性。如果假定各變量之間相互獨(dú)立，即觀測(cè)變量的協(xié)方差矩陣是對(duì)角矩陣，此時(shí)馬氏距離就是標(biāo)準(zhǔn)化的歐氏距離。馬氏距離不受指標(biāo)量綱及指標(biāo)間相關(guān)性的影響第十二章聚類分析

二、變量間相似系數(shù)的算法（2）夾角余弦（1）相關(guān)系數(shù)第十二章聚類分析系統(tǒng)聚類法直觀，易懂?？焖倬垲惙ǎ▌?dòng)態(tài)聚類法）快速，動(dòng)態(tài)。有序聚類法保序(時(shí)間順序或大小順序)。各種聚類方法第十二章聚類分析第二節(jié)系統(tǒng)聚類法系統(tǒng)聚類法的基本思想

先將n個(gè)樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個(gè)新類，計(jì)算新類和其它類（各當(dāng)前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都?xì)w成一類為止。

第十二章聚類分析系統(tǒng)聚類法的基本步驟：1.

計(jì)算n個(gè)樣品兩兩間的距離，記作D=。2.

構(gòu)造n個(gè)類，每個(gè)類只包含一個(gè)樣品。3.

合并距離最近的兩類為一新類。4.

計(jì)算新類與各當(dāng)前類的距離。5.

重復(fù)步驟3、4，合并距離最近的兩類為新類，直到所有的類并為一類為止。6.

畫聚類譜系圖。7.

決定類的個(gè)數(shù)和類。第十二章聚類分析最短距離法最長(zhǎng)距離法中間距離法重心法類平均法離差平方和法（Ward法）系統(tǒng)聚類方法：

上述6種方法歸類的基本步驟一致，只是類與類之間的距離有不同的定義。第十二章聚類分析定義類p與q之間的距離為兩類最近樣品的距離，即xq1?xp2?xq2?xp1?xq3?一、最短距離法第十二章聚類分析設(shè)類p與q合并成一個(gè)新類，記為k，則k與任一類r的距離是pqkr第十二章聚類分析例

最短距離法

設(shè)抽取5個(gè)樣品，每個(gè)樣品觀察2個(gè)指標(biāo)，：您每月大約喝多少瓶啤酒，：您對(duì)“飲酒是人生的快樂”這句話的看法如何？觀察數(shù)據(jù)如下，對(duì)這5個(gè)樣品分類。1234520181044710553第十二章聚類分析

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

2計(jì)算5個(gè)樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝第十二章聚類分析3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

3.6

10.216.129.4314.876第十二章聚類分析為最小，⑦=⑥⑦③⑥

6

9.4314.874、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、第十二章聚類分析6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個(gè)數(shù)與類。

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。第十二章聚類分析???x11?x21????二、最長(zhǎng)距離法定義類p與q之間的距離為兩類最遠(yuǎn)樣品的距離，即第十二章聚類分析設(shè)類p與q合并成一個(gè)新類，記為k，則k與任一類r的距離是pqkr第十二章聚類分析

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

2計(jì)算5個(gè)樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝例最長(zhǎng)距離法

第十二章聚類分析3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

3.6

10.216.499.4315.656.32第十二章聚類分析為最小，⑦=⑥⑦③⑥6.32

10.216.494、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、第十二章聚類分析6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個(gè)數(shù)與類。

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。第十二章聚類分析三、中間距離法定義類與類之間的距離既不采用兩類之間最近的距離，也不采用兩類之間最遠(yuǎn)的距離，而是采用介于兩者之間的距離，故稱為中間距離法。???rpqk第十二章聚類分析

②③④⑤①②③④13104260272892212453640

4計(jì)算5個(gè)樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝例中間距離法

第十二章聚類分析3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

13

1042658923237第十二章聚類分析為最小，⑦=⑥⑦③⑥

37

93.25245.254、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、第十二章聚類分析6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個(gè)數(shù)與類。

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。第十二章聚類分析四、重心法（Centroid)??和類與類之間的距離就考慮用重心之間的距離表示。設(shè)p與q的重心分別是，則類p和q的距離為第十二章聚類分析將p和q合并為k，則k類的樣品個(gè)數(shù)為它的重心是某一類r的重心是，它與新類k的距離是經(jīng)推導(dǎo)可以得到如下遞推公式：設(shè)聚類到某一步，類p與q分別有樣品

、個(gè)，第十二章聚類分析

②③④⑤①②③④13104260272892212453640

4計(jì)算5個(gè)樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝例重心法

第十二章聚類分析3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

13

1042658923237第十二章聚類分析為最小，⑦=⑥⑦③⑥

37

93.25245.254、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、第十二章聚類分析6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個(gè)數(shù)與類。

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。第十二章聚類分析五、類平均法（Average)定義兩類之間的距離平方為這兩類元素兩兩之間距離平方的平均?????pq第十二章聚類分析將p和q合并為k，則k類的樣品個(gè)數(shù)為設(shè)聚類到某一步，類p與q分別有樣品、個(gè)，k類與任一類r的距離為第十二章聚類分析

②③④⑤①②③④13104260272892212453640

4計(jì)算5個(gè)樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝例類平均法

第十二章聚類分析3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

13

1042668923338第十二章聚類分析為最小，⑦=⑥⑦③⑥

38

96.5249.54、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、第十二章聚類分析6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個(gè)數(shù)與類。

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。第十二章聚類分析六、差平方和法（Ward法）

反映樣品之間的差異程度設(shè)變量X的n個(gè)樣品觀察值為：n個(gè)樣品的離差平方和為：第十二章聚類分析???????????q?????????????pk設(shè)類p和q分別含有np、nq個(gè)樣品，其離差平方和分別記為和第十二章聚類分析直觀上容易想到把兩群樣品聚為一大群，大群的離差平方和將超過原來兩個(gè)群的離差平方和之和。

如果將p和q并類得到新類k，則類k的離差平方和為把增加的量記為定義類p和q之間的距離為：設(shè)類p和q分別含有np、nq個(gè)樣品，其離差平方和分別記為和第十二章聚類分析可以推得新類k與任一類r的距離：第十二章聚類分析

②③④⑤①②③④6.55213013644.5110.5122.51820

2計(jì)算5個(gè)樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝例離差平方和法（Ward法）

兩樣品間的距離的平方恰為它們之間歐氏距離平方的一半。第十二章聚類分析3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

6.5

52176.6744.5154.6724.67第十二章聚類分析為最小，⑦=⑥⑦③⑥

24.67

62.17245.264、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、第十二章聚類分析6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個(gè)數(shù)與類。

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。第十二章聚類分析最短距離法最長(zhǎng)距離法中間距離法重心法類平均法離差平方和法第十二章聚類分析Procclustermethod=選項(xiàng)

data=文件名outtree=文件名1

standard;varvariable-list;idvariable;run;Proctreedata=文件名1

horizontalgraphics;idvariable;run;Method＝選項(xiàng)single最短距離法complete最長(zhǎng)距離法median中間距離法centroid重心法average類平均法ward離差平方和法（Ward法）SAS程序第十二章聚類分析系統(tǒng)聚類分析案例第十二章聚類分析

根據(jù)第三產(chǎn)業(yè)國(guó)內(nèi)生產(chǎn)總值的9項(xiàng)指標(biāo)，對(duì)華東地區(qū)6省1市進(jìn)行分類，原始數(shù)據(jù)如下表：交通貿(mào)易金融房服務(wù)

衛(wèi)生文教科研黨政

X1X2X3X4X5X6X7X8X9上海江蘇浙江安徽福建江西山東244.42412.04459.63512.21160.4543.5189.9348.5548.63435.77724.85376.04381.81210.3971.82150.6423.74188.28321.75665.80157.94172.19147.1652.4478.1610.9093.50152.29258.6083.4285.1075.7426.7563.475.8947.02347.25332.59157.32172.48115.1633.8077.278.6979.01145.40143.5497.40100.5043.2817.7151.035.4162.03442.20665.33411.89429.88115.0787.45145.2521.39187.77第十二章聚類分析福建江西安徽浙江山東江蘇上海AverageDistanceBetweenClusters012第十二章聚類分析福建江西安徽浙江山東江蘇上海DistanceBetweenClusterCentroids012第十二章聚類分析

為了解我國(guó)城鎮(zhèn)居民的生活質(zhì)量，對(duì)全國(guó)各地區(qū)（除內(nèi)蒙古和西藏）進(jìn)行聚類分析。選用了4個(gè)指標(biāo)：X1：全年人均消費(fèi)支出X2：全年人均可支配收入X3：人均居住面積X4：人均公共綠地面積第十二章聚類分析甘肅青海陜西河南吉林江西黑龍江寧夏山西重慶福建云南江蘇四川廣西湖南山東湖北海南安徽貴州遼寧新疆河北浙江天津廣東上海北京MedianDistance012第十二章聚類分析由聚類譜系圖，29個(gè)地區(qū)可分四類：

第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北、江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差。第十二章聚類分析重慶四川廣西湖南山東福建云南江蘇甘肅青海陜西河南吉林江西黑龍江寧夏山西湖北海南安徽貴州遼寧新疆河北浙江天津廣東上海北京DistanceBetweenClusterCentroids012第十二章聚類分析29個(gè)地區(qū)可分為四類：第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北、山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差

第十二章聚類分析第十二章聚類分析29個(gè)地區(qū)可分為四類：第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北、山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差

第十二章聚類分析

綜合以上分析結(jié)果和實(shí)際情況，29個(gè)地區(qū)城鎮(zhèn)居民的生活質(zhì)量分為五類比較合適：第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北｝，生活質(zhì)量較差。第五類：｛山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差。第十二章聚類分析

根據(jù)美國(guó)等20個(gè)國(guó)家和地區(qū)的信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r進(jìn)行分類。Call—每千人擁有的電話線數(shù)；movecall—每千人戶居民擁有的蜂窩移動(dòng)電話數(shù)；fee—高峰時(shí)期每三分鐘國(guó)際電話的成本；computer—每千人擁有的計(jì)算機(jī)數(shù)；mips—每千人計(jì)算機(jī)功率（每秒百萬指令）；net—每千人互聯(lián)網(wǎng)絡(luò)戶主數(shù)。

數(shù)據(jù)摘自《世界競(jìng)爭(zhēng)力報(bào)告——1997》數(shù)據(jù)見sasuser.cluli01第十二章聚類分析第Ⅰ類：美國(guó)、瑞典、丹麥，發(fā)達(dá)國(guó)家，信息基礎(chǔ)設(shè)施發(fā)展良好第Ⅱ類：日本、中國(guó)臺(tái)灣、韓國(guó)、德國(guó)、法國(guó)、瑞士、新加坡、英國(guó)，新興工業(yè)化國(guó)家，信息基礎(chǔ)設(shè)施發(fā)展較好第Ⅲ類：巴西、墨西哥、波蘭、匈牙利、馬來西亞、智利、俄羅斯、泰國(guó)、印度，發(fā)展中國(guó)家，基礎(chǔ)設(shè)施薄弱第十二章聚類分析某公司下屬30個(gè)企業(yè)，公司為了考核下屬企業(yè)的經(jīng)濟(jì)效益，設(shè)計(jì)了8個(gè)指標(biāo)。為了避免重復(fù)，需要對(duì)這8個(gè)指標(biāo)進(jìn)行篩選，建立一個(gè)恰當(dāng)?shù)慕?jīng)濟(jì)效益指標(biāo)體系。通過計(jì)算30個(gè)企業(yè)8個(gè)指標(biāo)的相關(guān)系數(shù)距離，數(shù)據(jù)是1-r2。得如下表:

x1x2

x3

x4x5

x6

x7

x8

x10

0.600

0.430.460

0.470.450.120

0.570.450.230.220

0.380.400.210.290.220

0.310.790.650.700.800.660

0.450.450.270.230.140.190.770

試將它們聚類。x2

x3x4x5

x6

x7

x8對(duì)變量聚類第十二章聚類分析第十二章聚類分析第四節(jié)簡(jiǎn)單聚類方法簡(jiǎn)單聚類方法的基本思想簡(jiǎn)單聚類方法的計(jì)算過程簡(jiǎn)單聚類方法的特點(diǎn)簡(jiǎn)單聚類方法的改進(jìn)返回第十二章聚類分析簡(jiǎn)單聚類方法的基本思想計(jì)算樣本到聚類中心的距離并和門限T比較，決定歸屬哪類或作為新的一類中心。通常使用歐氏距離。返回第十二章聚類分析簡(jiǎn)單聚類方法的計(jì)算過程將待分類的樣本記為{X1,X2,…,XN}，選定類內(nèi)距離門限T；取任意一個(gè)樣本作為第一個(gè)聚類中心。例如，令

1類的中心Z1=X1；計(jì)算下一個(gè)樣本X2到Z1的距離d21；若d21>T，則建立新的一類

2，其中心Z2=X2；若d21

T，則X2

1；假設(shè)已有聚類中心Z1,Z2,…,Zk，計(jì)算尚未確定類別的樣本Xi到各聚類中心Zj（j=1,2,…,k）的距離dij。如果dij>T（j=1,2,…,k），則Xi作為新的一類的中心Zk+1=Xi；否則，如果，則指判Xi

l；檢查是否所有的樣本都分劃類別，如果是則結(jié)束；否則返回到第4步。返回第十二章聚類分析簡(jiǎn)單聚類方法的特點(diǎn)類心選定后在聚類過程中就不再改變。樣本指判類別后在聚類過程中也不再改變。聚類結(jié)果很大程度上依賴于距離門限T的選取和待分類樣本參與分類的次序。當(dāng)有樣本分布的先驗(yàn)知識(shí)來指導(dǎo)門限T及初始中心Z1的選取時(shí)，可以獲得較合理的結(jié)果。返回第十二章聚類分析距離門限和樣本次序的影響示意圖返回第十二章聚類分析簡(jiǎn)單聚類方法的改進(jìn)選用不同的門限及模式輸入次序來嘗試分類，并對(duì)聚類結(jié)果進(jìn)行檢驗(yàn)。最后對(duì)各種方案的劃分結(jié)果進(jìn)行比較，選取最好的一種聚類結(jié)果。第十二章聚類分析最大最小距離算法最大最小距離算法的基本思想最大最小距離算法的計(jì)算過程最大最小距離算法的特點(diǎn)最大最小距離算法舉例返回第十二章聚類分析最大最小距離算法的基本思想在樣本集中以最大距離原則選取新的聚類中心，以最小距離原則進(jìn)行模式歸類。通常使用歐氏距離。返回第十二章聚類分析最大最小距離算法的計(jì)算過程1.

選定比例系數(shù)

和初始聚類中心Z1和Z22.

計(jì)算各樣本Xi到Z1和Z2的距離最小值di3.計(jì)算{di}的最大值dl并判斷Xl的歸屬4.計(jì)算各樣本Xi到當(dāng)前所有聚類中心的距離最小值di及{di}最大值dl并判斷Xl的歸屬5.計(jì)算聚類結(jié)果返回第十二章聚類分析最大最小距離算法的第1步將待分樣本記為{X1,X2,…,XN}，選定比例系數(shù)

；選取任一模式特征矢量作為第一個(gè)聚類中心Z1，例如Z1=X1；從待分類矢量集中選出距離Z1最遠(yuǎn)的特征矢量作為第二個(gè)聚類中心Z2。返回第十二章聚類分析最大最小距離算法的第2步計(jì)算各樣本Xi與Z1和Z2之間的距離，并求出它們之中的最小值，即：返回第十二章聚類分析最大最小距離算法的第3步計(jì)算{di}的最大值若，則相應(yīng)的樣本Xl作為第三個(gè)聚類中心Z3=Xl，然后轉(zhuǎn)至第4步；否則，轉(zhuǎn)至第5步。返回第十二章聚類分析最大最小距離算法的第4步設(shè)存在k個(gè)聚類中心Z1,Z2,…,

Zk,計(jì)算各樣本Xi到各聚類中心的距離：計(jì)算出dij的最小值：計(jì)算{di}的最大值如果，則Zk+1=Xl并轉(zhuǎn)至第4步；否則轉(zhuǎn)至第5步。返回第十二章聚類分析最大最小距離算法的第5步在不再有新的聚類中心之后，將各樣本X1,X2,…,XN按最小距離原則分到各類中去，即計(jì)算：如果，則判斷。返回第十二章聚類分析最大最小距離算法的特點(diǎn)聚類結(jié)果與參數(shù)

以及第一個(gè)聚類中心Z1的選取有關(guān)。如果沒有先驗(yàn)知識(shí)指導(dǎo)

和Z1的選取，可適當(dāng)調(diào)整

和Z1，比較多次試探分類結(jié)果，選取最合理的一種聚類。返回第十二章聚類分析最大最小距離算法舉例Z1=X1Z2=X6Z3=X7返回第十二章聚類分析第三節(jié)聚類求解計(jì)算第十二章聚類分析求解過程第1步令k=0,m=N,每個(gè)樣本自成一類，即：返回第十二章聚類分析求解過程第2步按歐氏距離計(jì)算矩陣D(0)

如下：返回

0

0

0

0

0

0第十二章聚類分析求解過程第3步D(0)中最小陣元為，它是與之間的距離，將它們合并為一類，得一新的分類為：返回第十二章聚類分析求解過程第4步計(jì)算合并后的距離矩陣D(1)

如下:返回

0

0

0

0

0第十二章聚類分析求解過程第5步D(1)中距離最小者為，它是與間的距離，合并它們得新的分類：返回第十二章聚類分析求解過程第6步計(jì)算合并后的距離矩陣D(2)如下:返回

0

0

0

0第十二章聚類分析求解過程第7步D(2)中距離最小者為，它是與間的距離，合并它們得新的分類：

返回第十二章聚類分析求解過程第8步計(jì)算合并后的距離矩陣D(3)如下:返回

0

0

0第十二章聚類分析求解過程第9步距離矩陣D(3)可知，、和距離相同，所以有兩種合并方式：或返回第十二章聚類分析求解過程第10步最終聚類結(jié)果為：

{{{{X1,X2},X4},X3},{X5,X6}}或：

{{{X1,X2},X4},{X3,{X5,X6}}}試對(duì)上述兩個(gè)結(jié)果劃出樹圖。返回第十二章聚類分析第五節(jié)ISODATA迭代自組織數(shù)據(jù)分析算法第十二章聚類分析ISODATA算法的完整名稱IterativeSelf-OrganizingDataAnalysisTechniquesAlgorithm迭代自組織數(shù)據(jù)分析算法第十二章聚類分析ISODATA算法的基本思想在迭代過程中，通過不斷計(jì)算類內(nèi)及類間有關(guān)參數(shù)，并和設(shè)定的門限比較，確定是兩類合并為一類還是一類分裂為兩類，從而不斷地“自組織”，以達(dá)到在各參數(shù)滿足設(shè)計(jì)要求條件下，使各樣本到其類心的距離平方和最小。第十二章聚類分析ISODATA算法的計(jì)算過程第1步.預(yù)置初始條件第2步.按最小距離原則歸類第3步.依據(jù)

n判斷合并條件第4步.計(jì)算分類后的參數(shù)第5步.依據(jù)Ip,Nc判斷停止條件或選擇路徑第6步.計(jì)算類內(nèi)距離的標(biāo)準(zhǔn)差矢量

j第7步.計(jì)算類內(nèi)距離標(biāo)準(zhǔn)差矢量的最大分量

jmax第8步.依據(jù)

jmax判斷分裂條件第9步.計(jì)算各類心間的距離第10步.依據(jù)

D判斷合并條件第11步.判斷結(jié)束條件返回第十二章聚類分析ISODATA算法的第1步設(shè)定聚類控制參數(shù)選定初始聚類中心返回第十二章聚類分析設(shè)定聚類控制參數(shù)c=預(yù)期的類數(shù)Nc=聚類中心個(gè)數(shù)（可以不等于c）

n=每一類中允許的最少樣本數(shù)目

s=類內(nèi)各分量分布的標(biāo)準(zhǔn)差上限

D=兩類中心間的最小距離下限L=在每次迭代中可合并類的最多對(duì)數(shù)I=允許的最多迭代次數(shù)返回第十二章聚類分析選定初始聚類中心讀入待分類樣本X1,X2,…,XN從{Xi}中任選Nc個(gè)樣本作為初始聚類中心zj

(j=1,2,…,Nc)返回第十二章聚類分析ISODATA算法的第2步按最小距離原則將樣本集{Xi}中每個(gè)樣本分到某一類中，即：如果,則判Xi

l

其中返回第十二章聚類分析ISODATA算法的第3步如果類

j中樣本數(shù)nj

<

n，則取消該類的中心，Nc=Nc-1,轉(zhuǎn)至第2步；否則轉(zhuǎn)至第4步。返回第十二章聚類分析ISODATA算法的第4步計(jì)算各類的中心：計(jì)算各類樣本到類心的平均距離：計(jì)算樣本到其類心的總體平均距離返回第十二章聚類分析ISODATA算法的第5步5.1若迭代次數(shù)Ip=I，則置

D=0，轉(zhuǎn)到第9步，否則轉(zhuǎn)5.2；5.2若Nc

c/2則轉(zhuǎn)到第6步，否則轉(zhuǎn)5.3；5.3若Nc2c，則轉(zhuǎn)至第9步，否則轉(zhuǎn)5.4；5.4若c/2<Nc<2c，當(dāng)Ip是奇數(shù)時(shí)轉(zhuǎn)至第6步，否則轉(zhuǎn)至第9步。返回第十二章聚類分析ISODATA算法的第6步計(jì)算各類類內(nèi)距離的標(biāo)準(zhǔn)差矢量其中k為分量編號(hào)，j為類的編號(hào)，n為矢量維數(shù)，Xki是Xi的第k個(gè)分量，zkj是zj的第k個(gè)分量。返回第十二章聚類分析ISODATA算法的第7步計(jì)算各類類內(nèi)距離標(biāo)準(zhǔn)差矢量

j中的最大分量:返回第十二章聚類分析ISODATA算法的第8步若某

jmax>

s，且滿足下面兩個(gè)條件之一：（1）（2）則將該類

j分裂為兩個(gè)聚類，取消zj且令Nc=Nc+1，同時(shí)選擇實(shí)數(shù)k產(chǎn)生兩個(gè)新的聚類中心，其中

或如果分裂，則Ip=Ip+1，轉(zhuǎn)至第2步，否則轉(zhuǎn)第9步；返回第十二章聚類分析ISODATA算法的第9步計(jì)算各類對(duì)中心間的距離返回第十二章聚類分析ISODATA算法的第10步將Dij與

D比較，并將小于

D的那些Dij按遞增次序排列，取前L個(gè)。從最小的Dij開始，將相應(yīng)的兩類合并。若原來的兩個(gè)類心為zi和zj，則合并后的聚類中心為其中每類最多只能被合并一次,合并后有:Nc=Nc-已并掉的類數(shù)返回

第十二章聚類分析ISODATA算法的第11步如果迭代次數(shù)Ip=I次或過程收斂，則結(jié)束。否則，Ip=Ip+1，若需要調(diào)整參數(shù)，則轉(zhuǎn)至第1步；若不改變參數(shù)，則轉(zhuǎn)至第2步返回第十二章聚類分析ISODATA算法的特點(diǎn)具有啟發(fā)性推理、分析監(jiān)督、控制聚類結(jié)構(gòu)及人機(jī)交互等特點(diǎn)，是較好的聚類方法之一。返回第十二章聚類分析ISODATA算法舉例已知樣本集如右圖試用ISODATA算法聚類求解過程返回第十二章聚類分析求解過程第1步，第2步，第3步第4步，第5步，第6步第7步，第8步，第9步返回第十二章聚類分析求解過程第1步樣本數(shù)N=8,樣本維數(shù)n=2設(shè)定參數(shù)和初始值如下：

c=2，Nc=1，

n=2，

s=1

D=4，L=1，I=4,z1=(0,0)T令I(lǐng)p=1返回第十二章聚類分析求解過程第2步因只有一個(gè)聚類中心，故

1={X1,X2,…,X8}，n1=8因n1>

n，故無合并返回第十二章聚類分析求解過程第3步計(jì)算聚類中心計(jì)算內(nèi)類平均距離計(jì)算總的類內(nèi)平均距離返回第十二章聚類分析求解過程第4步因不是最后一步迭代，且,故計(jì)算

1的標(biāo)準(zhǔn)差矢量標(biāo)準(zhǔn)差矢量

1的最大分量為

1max=1.99返回第十二章聚類分析求解過程第5步因

1max=1.99>

s且，將1分裂成兩類，取k=0.5,0.51max1.0,則返回第十二章聚類分析求解過程第6步令I(lǐng)p=Ip+1=2，Nc=Nc+1=2，按最小距離原則對(duì)樣本重新歸類：

1={X4,X5,X6,X7,X8}，n1=5

2={X1,X2,X3}，n2=3因nj>

n(j=1,2)，故無合并。返回第十二章聚類分析求解過程第7步計(jì)算聚類中心計(jì)算內(nèi)類平均距離計(jì)算總的類內(nèi)平均距離返回第十二章聚類分析求解過程第8步計(jì)算類間距離得D12=4.72，由D12>

D，類不能合并因Ip=2<I=4，令I(lǐng)p=Ip+1=3，判斷是否修改參數(shù)。由上面結(jié)果可知，已獲得所要求類別數(shù)目，類間距離大于類內(nèi)距離，每類樣本數(shù)都有樣本總數(shù)的足夠大的百分比，因此不改變參數(shù)。返回第十二章聚類分析求解過程第9步計(jì)算

1={X4,X5,X6,X7,X8}和

2={X1,X2,X3}的標(biāo)準(zhǔn)差矢量所以1max=0.75，2max=0.82因

jmax<

s，故分裂條件不滿足因D12=4.72>

D=4，故合并條件不滿足令I(lǐng)p=Ip+1=4，計(jì)算無變化，停止。返回第十二章聚類分析近鄰函數(shù)法該方法特別適合于類的樣本分布是條狀或線狀的情況。算法細(xì)節(jié)可查閱有關(guān)資料自學(xué)。返回第十二章聚類分析條狀或線狀分布樣本示意圖返回第十二章聚類分析自組織特征映射該方法可將任意維數(shù)的輸入樣本映射為一維或二維分布，并且可以較好地保持原樣本分布的拓?fù)浣Y(jié)構(gòu)。演化示意圖1，演化示意圖2。算法細(xì)節(jié)可查閱有關(guān)資料自學(xué)。返回第十二章聚類分析自組織特征映射演化示意圖1返回第十二章聚類分析自組織特征映射演化示意圖2返回第十二章聚類分析第六節(jié)動(dòng)態(tài)聚類第十二章聚類分析動(dòng)態(tài)聚類法

系統(tǒng)聚類法是一種比較成功的聚類方法。然而當(dāng)樣本點(diǎn)數(shù)量十分龐大時(shí)，則是一件非常繁重的工作，且聚類的計(jì)算速度也比較慢。比如在市場(chǎng)抽樣調(diào)查中，有4萬人就其對(duì)衣著的偏好作了回答，希望能迅速將他們分為幾類。這時(shí)，采用系統(tǒng)聚類法就很困難，而動(dòng)態(tài)聚類法就會(huì)顯得方便，適用。動(dòng)態(tài)聚類使用于大型數(shù)據(jù)。第十二章聚類分析動(dòng)態(tài)聚類法

基本思想：選取若干個(gè)樣品作為凝聚點(diǎn)，計(jì)算每個(gè)樣品和凝聚點(diǎn)的距離，進(jìn)行初始分類，然后根據(jù)初始分類計(jì)算其重心，再進(jìn)行第二次分類，一直到所有樣品不再調(diào)整為止。第十二章聚類分析選擇凝聚點(diǎn)分類修改分類分類是否合理分類結(jié)束YesNo第十二章聚類分析

用一個(gè)簡(jiǎn)單的例子來說明動(dòng)態(tài)聚類法的工作過程。例如我們要把圖中的點(diǎn)分成兩類?？焖倬垲惖牟襟E：