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

第十二章聚類分析

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

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

=第十二章聚類分析馬氏距離又稱為廣義歐氏距離。馬氏距離考慮了觀測變量之間的相關性。如果假定各變量之間相互獨立，即觀測變量的協方差矩陣是對角矩陣，此時馬氏距離就是標準化的歐氏距離。馬氏距離不受指標量綱及指標間相關性的影響第十二章聚類分析

二、變量間相似系數的算法（2）夾角余弦（1）相關系數第十二章聚類分析系統聚類法直觀，易懂。快速聚類法（動態聚類法）快速，動態。有序聚類法保序(時間順序或大小順序)。各種聚類方法第十二章聚類分析第二節系統聚類法系統聚類法的基本思想

先將n個樣品各自看成一類，然后規定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個新類，計算新類和其它類（各當前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都歸成一類為止。

第十二章聚類分析系統聚類法的基本步驟：1.

計算n個樣品兩兩間的距離，記作D=。2.

構造n個類，每個類只包含一個樣品。3.

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

計算新類與各當前類的距離。5.

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

畫聚類譜系圖。7.

決定類的個數和類。第十二章聚類分析最短距離法最長距離法中間距離法重心法類平均法離差平方和法（Ward法）系統聚類方法：

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

最短距離法

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

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

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

3.6

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

6

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

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

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

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

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

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

3.6

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

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

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

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

②③④⑤①②③④13104260272892212453640

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

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

13

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

37

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

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

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

、個，第十二章聚類分析

②③④⑤①②③④13104260272892212453640

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

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

13

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

37

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

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

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

②③④⑤①②③④13104260272892212453640

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

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

13

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

38

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

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

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

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

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

②③④⑤①②③④6.55213013644.5110.5122.51820

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

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

6.5

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

24.67

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

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

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

data=文件名outtree=文件名1

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

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

根據第三產業國內生產總值的9項指標，對華東地區6省1市進行分類，原始數據如下表：交通貿易金融房服務

衛生文教科研黨政

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第十二章聚類分析

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

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

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

第十二章聚類分析

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

根據美國等20個國家和地區的信息基礎設施的發展狀況進行分類。Call—每千人擁有的電話線數；movecall—每千人戶居民擁有的蜂窩移動電話數；fee—高峰時期每三分鐘國際電話的成本；computer—每千人擁有的計算機數；mips—每千人計算機功率（每秒百萬指令）；net—每千人互聯網絡戶主數。

數據摘自《世界競爭力報告——1997》數據見sasuser.cluli01第十二章聚類分析第Ⅰ類：美國、瑞典、丹麥，發達國家，信息基礎設施發展良好第Ⅱ類：日本、中國臺灣、韓國、德國、法國、瑞士、新加坡、英國，新興工業化國家，信息基礎設施發展較好第Ⅲ類：巴西、墨西哥、波蘭、匈牙利、馬來西亞、智利、俄羅斯、泰國、印度，發展中國家，基礎設施薄弱第十二章聚類分析某公司下屬30個企業，公司為了考核下屬企業的經濟效益，設計了8個指標。為了避免重復，需要對這8個指標進行篩選，建立一個恰當的經濟效益指標體系。通過計算30個企業8個指標的相關系數距離，數據是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對變量聚類第十二章聚類分析第十二章聚類分析第四節簡單聚類方法簡單聚類方法的基本思想簡單聚類方法的計算過程簡單聚類方法的特點簡單聚類方法的改進返回第十二章聚類分析簡單聚類方法的基本思想計算樣本到聚類中心的距離并和門限T比較，決定歸屬哪類或作為新的一類中心。通常使用歐氏距離。返回第十二章聚類分析簡單聚類方法的計算過程將待分類的樣本記為{X1,X2,…,XN}，選定類內距離門限T；取任意一個樣本作為第一個聚類中心。例如，令

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

2，其中心Z2=X2；若d21

T，則X2

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

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

選定比例系數

和初始聚類中心Z1和Z22.

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

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

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

以及第一個聚類中心Z1的選取有關。如果沒有先驗知識指導

和Z1的選取，可適當調整

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

如下：返回

0

0

0

0

0

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

如下:返回

0

0

0

0

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

0

0

0

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

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

0

0

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

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

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

n判斷合并條件第4步.計算分類后的參數第5步.依據Ip,Nc判斷停止條件或選擇路徑第6步.計算類內距離的標準差矢量

j第7步.計算類內距離標準差矢量的最大分量

jmax第8步.依據

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

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

n=每一類中允許的最少樣本數目

s=類內各分量分布的標準差上限

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

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

l

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

j中樣本數nj

<

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

D=0，轉到第9步，否則轉5.2；5.2若Nc

c/2則轉到第6步，否則轉5.3；5.3若Nc2c，則轉至第9步，否則轉5.4；5.4若c/2<Nc<2c，當Ip是奇數時轉至第6步，否則轉至第9步。返回第十二章聚類分析ISODATA算法的第6步計算各類類內距離的標準差矢量其中k為分量編號，j為類的編號，n為矢量維數，Xki是Xi的第k個分量，zkj是zj的第k個分量。返回第十二章聚類分析ISODATA算法的第7步計算各類類內距離標準差矢量

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

jmax>

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

j分裂為兩個聚類，取消zj且令Nc=Nc+1，同時選擇實數k產生兩個新的聚類中心，其中

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

D比較，并將小于

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

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

c=2，Nc=1，

n=2，

s=1

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

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

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

1的標準差矢量標準差矢量

1的最大分量為

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

1max=1.99>

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

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

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

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

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

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

2={X1,X2,X3}的標準差矢量所以1max=0.75，2max=0.82因

jmax<

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

D=4，故合并條件不滿足令Ip=Ip+1=4，計算無變化，停止。返回第十二章聚類分析近鄰函數法該方法特別適合于類的樣本分布是條狀或線狀的情況。算法細節可查閱有關資料自學。返回第十二章聚類分析條狀或線狀分布樣本示意圖返回第十二章聚類分析自組織特征映射該方法可將任意維數的輸入樣本映射為一維或二維分布，并且可以較好地保持原樣本分布的拓撲結構。演化示意圖1，演化示意圖2。算法細節可查閱有關資料自學。返回第十二章聚類分析自組織特征映射演化示意圖1返回第十二章聚類分析自組織特征映射演化示意圖2返回第十二章聚類分析第六節動態聚類第十二章聚類分析動態聚類法

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

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

用一個簡單的例子來說明動態聚類法的工作過程。例如我們要把圖中的點分成兩類。快速聚類的步驟：