聚類分析

1、第三章 聚類分析,§3.1 聚類分析的思想§3.2 相似性度量§3.3 類和類的特征§3.4 系統(tǒng)聚類法§3.5 模糊聚類分析（選學(xué)）§3.6 K-均值聚類和有序樣本聚類§3.7 計算步驟與上機(jī)實現(xiàn)§3.8 社會經(jīng)濟(jì)案例研究,第三章 聚類分析,人們往往會碰到通過劃分同種屬性的對象很好地解決問題的情形，而不論這些對象是個體、公司、

2、產(chǎn)品甚至行為。如果沒有一種客觀的方法，基于在總體內(nèi)區(qū)分群體的戰(zhàn)略選擇，比如市場細(xì)分將不可能，其他領(lǐng)域也會遇到類似的問題，研究者都在基于一個多維剖面的觀測中尋找某種“自然”結(jié)構(gòu)。為此最常用的技巧是聚類分析，聚類分析將個體或?qū)ο蠓诸?，使得同一類中的對象之間的相似性比與其他類的對象的相似性更強(qiáng)。目的在于使類內(nèi)對象的同質(zhì)性最大化和類與類間對象的異質(zhì)性最大化。本章將介紹聚類分析的性質(zhì)和目的，并且引導(dǎo)研究者使用各種聚類分析方法。,§3.

3、1 聚類分析的思想,3.1.1 導(dǎo)言在古老的分類學(xué)中，人們主要靠經(jīng)驗和專業(yè)知識，很少利用數(shù)學(xué)方法。隨著生產(chǎn)技術(shù)和科學(xué)的發(fā)展，分類越來越細(xì)，以致有時僅憑經(jīng)驗和專業(yè)知識還不能進(jìn)行確切分類，于是數(shù)學(xué)這個有用的工具逐漸被引進(jìn)到分類學(xué)中，形成了數(shù)值分類學(xué)。近些年來，數(shù)理統(tǒng)計的多元分析方法有了迅速的發(fā)展，多元分析的技術(shù)自然被引用到分類學(xué)中，于是從數(shù)值分類學(xué)中逐漸的分離出聚類分析這個新的分支。,§3.1 聚類分析的思想,我們認(rèn)為，所研

4、究的樣品或指標(biāo)（變量）之間是存在著程度不同的相似性（親疏關(guān)系）。于是根據(jù)一批樣品的多個觀測指標(biāo)，具體找出一些能夠度量樣品或指標(biāo)之間的相似程度的統(tǒng)計量，以這些統(tǒng)計量為劃分類型的依據(jù)，把一些相似程度較大的樣品（或指標(biāo)）聚合為一類，把另外一些彼此之間相似程度較大的樣品（或指標(biāo)）又聚合為另外一類，…。關(guān)系密切的聚合到一個小的分類單位，關(guān)系疏遠(yuǎn)的聚合到一個大的分類單位，直到把所有的樣品（或指標(biāo)）都聚合完畢，把不同的類型一一劃分出來，形成一個由小到

5、大的分類系統(tǒng)。最后再把整個分類系統(tǒng)畫成一張分群圖（又稱譜系圖），用它把所有的樣品（或指標(biāo)）間的親疏關(guān)系表示出來。,§3.1 聚類分析的思想,在經(jīng)濟(jì)、社會、人口研究中，存在著大量分類研究、構(gòu)造分類模式的問題。過去人們主要靠經(jīng)驗和專業(yè)知識，作定性分類處理，致使許多分類帶有主觀性和任意性，不能很好的提示客觀事物內(nèi)在的本質(zhì)差別和聯(lián)系，特別是對于多因素、多指標(biāo)的分類問題，定性分類更難以實現(xiàn)準(zhǔn)確分類。 為了克服定性分類時存在的不足，數(shù)

6、學(xué)這個有用的工具逐漸被引進(jìn)到分類學(xué)中，形成數(shù)值分類學(xué)。后來隨著多元分析的引進(jìn)，聚類分析可以用來對案例進(jìn)行分類，也可以用來對變量進(jìn)行分類。對樣品的分類常稱為Q型聚類分析，對變量的分類常稱為R型聚類分析。,§3.1 聚類分析的思想,與多元分析的其他方法相比，聚類分析的方法是很粗糙的，理論上還不完善，但由于它能解決許多實際問題，很受人們的重視，和回歸分析、判別分析一起被稱為多元分析的三大方法。,§3.1 聚類分析的思

7、想,3.1.2 聚類的目的在一些社會、經(jīng)濟(jì)問題中，我們面臨的往往是比較復(fù)雜的研究對象，如果能把相似的樣品（或指標(biāo)）歸成類，處理起來就大為方便，聚類分析的目的就是把相似的研究對象歸成類。 【例3.1】若我們需要將下列11戶城鎮(zhèn)居民按戶主個人的收入進(jìn)行分類，對每戶作了如下的統(tǒng)計，結(jié)果列于表3.1。在表中，“標(biāo)準(zhǔn)工資收入” 、“職工獎金” 、“職工津貼” 、“性別” 、“就業(yè)身份”等稱為指標(biāo)，每戶稱為樣品。若對戶主進(jìn)行分類，還可以采用其他

8、指標(biāo)，如“子女個數(shù)” 、“政治面貌” 等，指標(biāo)如何選擇取決于聚類的目的。,§3.1 聚類分析的思想,§3.1 聚類分析的思想,例3.1中的8個指標(biāo)，前6個是定量的，后2個是定性的。定量變量通常是具有數(shù)值特征的連續(xù)變量，例如長度、重量、人口等這類變量。（間隔尺度）定性變量沒有數(shù)量上的變化，而是性質(zhì)上的差異。（有序尺度、名義尺度）,§3.1 聚類分析的思想,分得更細(xì)一些，指標(biāo)的類型有三種尺度間隔尺

9、度（定距尺度、定比尺度）。變量用連續(xù)的量來表示。有序尺度（定序尺度）。指標(biāo)用有序的等級來表示，有次序關(guān)系，但沒有數(shù)量表示。名義尺度（定類尺度）。指標(biāo)用一些類來表示，這些類之間沒有等級關(guān)系也沒有數(shù)量關(guān)系。不同類型的指標(biāo)，在聚類分析中，處理的方式是大不一樣的?？偟膩碚f，提供給間隔尺度的指標(biāo)的方法較多，對另兩種尺度的變量處理的方法不多。,§3.1 聚類分析的思想,第一位重要的問題是“什么是類”？粗糙地講，相似樣品（或指標(biāo)）的

10、集合稱作類。由于經(jīng)濟(jì)問題的復(fù)雜性，欲給類下一個嚴(yán)格的定義是困難的，在§3.3中，我們將給類一些待探討的定義。 聚類分析給人們提供了豐富多采的方法進(jìn)行分類，這些方法大致可歸納為：(1) 系統(tǒng)聚類法。(2)模糊聚類法。(3) K-均值法。(4) 有序樣品的聚類。(5) 分解法。(6) 加入法。我們重點學(xué)習(xí)系統(tǒng)聚類法、 K-均值聚類。,§3.2 相似性度量,從一組復(fù)雜數(shù)據(jù)產(chǎn)生一個相當(dāng)簡單的類結(jié)構(gòu)，必然要求進(jìn)行“相關(guān)性

11、”或“相似性“度量。在相似性度量的選擇中，常常包含許多主觀上的考慮，但是最重要的考慮是指標(biāo)（包括離散的、連續(xù)的和二態(tài)的）性質(zhì)或觀測的尺度（名義的、次序的、間隔的和比率的）以及有關(guān)的知識。當(dāng)對樣品進(jìn)行聚類時，“靠近”往往由某種距離來刻畫。另一方面，當(dāng)對指標(biāo)聚類時，根據(jù)相關(guān)系數(shù)或某種關(guān)聯(lián)性度量來聚類。,表3-2 數(shù)據(jù)矩陣在表3-2中，每個樣品有p個指標(biāo)，故每個樣品可以看成p維空間中的一個點，

12、n個樣品就組成p維空間中n個點，此時自然想用距離來度量樣品之間的接近程度。,§3.2 相似性度量,§3.2 相似性度量,§3.2.1 距離條件設(shè) 表示一個點集， 表示距離，它是 到 的函數(shù)，距離的四條基本公理：（1） ；（2） ，當(dāng)且僅當(dāng) ；（3）

13、 ；（4） 。,§3.2 相似性度量,用 表示第i個樣品的第j個指標(biāo)，數(shù)據(jù)矩陣見表3.2，第j個指標(biāo)的均值和標(biāo)準(zhǔn)差記作 和 。用 表示第i個樣品與第j個樣品之間的距離，作為距離當(dāng)然以下公理。（1） ；（2）

14、 ，當(dāng)且僅當(dāng) ； 各指標(biāo)相等，則在空間上完全重合；（3） ；（4） ；（5） ；不一定滿足極端距離。,§3.2 相似性度量,§3.2.2 距離(Distance)（1）絕對值(Block)距離 ；（2）歐氏(Euclidean)

15、距離（3）明考斯基(Minkwski)距離 ； 當(dāng)q=1和2時就是上述的兩個距離，絕對值距離和歐氏距離統(tǒng)一成明考斯基距離。（4）切比雪夫(Chebychey)距離 （當(dāng)q趨向于無窮時，明考斯基(Minkwski)距離就是切比雪夫距離。）,§3.2 相似性度量,但就

16、大部分統(tǒng)計問題而言，歐氏距離是不能令人滿意的。這里因為，每個坐標(biāo)對歐氏距離的貢獻(xiàn)是同等的。當(dāng)坐標(biāo)軸表示測量值時，它們往往帶有大小不等的隨機(jī)波動，在這種情況下，合理的辦法是對坐標(biāo)加權(quán)，使得變化較大的坐標(biāo)比變化小的坐標(biāo)有較小的權(quán)系數(shù)，這就產(chǎn)生了各種距離。歐氏距離還有一個缺點，這就是當(dāng)各個分量為不同性質(zhì)的量時，“距離”的大小竟然與指標(biāo)的單位有關(guān)。,§3.2 相似性度量,明考斯基距離在實際應(yīng)用中缺點：一是是距離的大小受到各指標(biāo)觀測

17、值單位的影響；二是沒有考慮到指標(biāo)之間的相關(guān)性，所以通常的改進(jìn)辦法有下面兩個：首先，各指標(biāo)的測量值相差懸殊時，先對數(shù)據(jù)標(biāo)準(zhǔn)化，然后用標(biāo)準(zhǔn)化后的數(shù)據(jù)計算距離。或者使用蘭氏距離。 （5）蘭氏距離(蘭斯Lance和威廉姆斯Willams) 當(dāng) 時， 蘭氏距離克服了指標(biāo)的單位影響，但是沒有克服相關(guān)性。,§3

18、.2 相似性度量,其次，一種改進(jìn)的馬氏距離。 （6）馬氏距離 設(shè)X、Y從均值向量為μ，協(xié)方差陣為∑的總體G中抽取的兩個樣品，定義X、Y兩點之間的馬氏距離為 它對一切線性變換是不變的，不受指標(biāo)量綱的影響。它對指標(biāo)的相關(guān)性也作了考慮，我們僅用書上的例3-2來說明。 注意：以上各各種距離只適用于間隔尺度的度量。,§3.2 相似性度量,但在聚類分析之前，我們預(yù)先對研究對象有多

19、少個不同類型的情況一無所知，則馬氏距離公式中的 值如何計算呢？如果用全部數(shù)據(jù)計算的均值和協(xié)方差陣來計算馬氏距離，效果也不是很理想。因此，通常人們還是喜歡應(yīng)用歐氏距離聚類。,§3.2 相似性度量,如果指標(biāo)是有序尺度或名義尺度時，也有一些靈活的定義距離的方法。（7）不一致性系數(shù)設(shè)兩個樣品 p個指標(biāo)的取值，配合的指標(biāo)數(shù)為 ，不配合的指標(biāo)數(shù)為 ，定義他們之間的距離為,§3.2

20、 相似性度量,在聚類分析中不僅需要將樣品分類，也需要將指標(biāo)分類，在指標(biāo)之間也可以定義距離，要常用的是相似系數(shù)。對于間隔尺度，常用的相似系數(shù)有：(1) 夾角余弦。這是受相似形的啟發(fā)而來，圖3.1中的曲線AB和CD盡管長度不一，但形狀相似，當(dāng)長度不是主要矛盾時，應(yīng)定義一種相似系數(shù)使AB和CD呈現(xiàn)出比較密切的關(guān)系。而夾角余弦適合這一要求。,§3.2 相似性度量,用 表示指標(biāo)i與指標(biāo)j之間的相似系數(shù)， 的絕對值越接

21、近于1，表示指標(biāo)i與指標(biāo)j之間的關(guān)系越密切，反之亦然。 它的定義是 它是指標(biāo)向量 和 之間的夾角余弦。,§3.2 相似性度量,(2) 相關(guān)系數(shù)。這是大家最熟悉的統(tǒng)計量，它是將數(shù)據(jù)標(biāo)準(zhǔn)化后的夾角余弦。名義尺度之間也可以定義相似系數(shù)，本書不做介紹。,§3.2 相似性度量,有時指標(biāo)之間也可用距離

22、來描述它們的接近程度。實際上距離和相似系數(shù)之間可以互相轉(zhuǎn)化。若 是一個距離，則 為相似系數(shù)。若 為相似系數(shù)且非負(fù)，則 看成是距離（不一定符合距離的定義），或 看成距離，如果指標(biāo)均為取兩值的名義尺度指標(biāo)，也可定義相關(guān)系數(shù)。,§3.3 類和類的特征,我們的目的是聚類，那么什么叫類呢？由于客

23、觀事物的千差萬別，在不同的問題中類的含義是不盡相同的。給類下一個嚴(yán)格的定義，決非易事。下面給出類的適用于不同的場合幾個定義。 用G表示類，設(shè)G中有K個元素，這些元素用i，j等表示。定義3.1 T為一給定的閥值，如果對任意的i，j∈G，有 ( 為i和j的距離)，則稱G為一個類。定義3.2 對閥值T，如果對每個i∈G ，有 ，則稱G為一個類。

24、定義3.3 對閥值T、V，如果 ，對一切i，j∈G ，則稱G為一個類。,§3.3 類和類的特征,定義3.4 對閥值T，若對任意一個i∈G ，一定存j∈G ，使得 ，則稱G為一個類。易見，定義3.1的要求是最高的，凡符合它的類，一定也是符合后三種定義的類。此外，凡符合定義3.2的類，也一定是符合定義3.3的類。現(xiàn)在類

25、G的元素用 表示，m為G內(nèi)的樣品數(shù)（或指標(biāo)數(shù)），可以從不同的角度來刻畫G的特征，常用的特征有下面三種。（1）均值 （或稱為G的重心）：,§3.3 類和類的特征,（2）樣本散布陣及協(xié)差陣：（3） G的直徑。它有多種定義，例如：在聚類分析中，不僅要考慮各個類的特征，而且要計算類與類之間的距離。由于類的形狀是多種多樣的，所以類與類之間的距離也有多種計算方法。,§3.3

26、 類和類的特征,令 和 中分別有k個和m個樣品，它們的重心分別為 和 ，它們之間的距離分別用 表示。下面是一些常用的定義：(1) 最短距離法 (nearest neighbor或single linkage method) 它等于類 和 中最鄰近的兩個樣品的距離，該準(zhǔn)則下類的合并過程在圖3.2種概要說明。,§3.3 類和類的特征,(2) 最長距離法（farthe

27、st neighbor或complete linkage method）它等于類 和 中最遠(yuǎn)的兩個樣品的距離，該準(zhǔn)則下類的合并過程在圖3.3種概要說明。,§3.3 類和類的特征,(3) 類平均法(group average method)它等于類 和類 中任兩個樣品的距離的平均，該準(zhǔn)則下類的合并過程在圖3.4種概要說明。,§3.3 類和類的特征,(4) 重心法(Centroi

28、d method)它等于兩個重心 和 間的距離。(5) 離差平方和法（Sum of Squares method） 若采用直徑的第一種定義方法（a），用 和 分別表示類 和類 的直徑，用 表示大類 的直徑 ，則,§3.3 類和類的特征,式中： 。用離差平方和法定義類 和 類之間的

29、距離平方為 ：可以證明這種定義是有意義的，證明見文獻(xiàn)[7]，如果樣品的距離采用歐氏距離，同樣可以證明下式成立：這表明，離差平方和法定義類間距離與重心法定義的距離只差1個常數(shù)倍，這個倍數(shù)與兩類的樣品數(shù)有關(guān)。,§3.4 系統(tǒng)聚類法,系統(tǒng)聚類法(hierarchical clustering method)在聚類分析中諸方法中用的最多，包含下列步驟：,§3.4 系統(tǒng)聚類法,不同的距離定義方式用到系統(tǒng)

30、聚類程序中，得到不同的系統(tǒng)聚類法。3.4.1 最短距離法和最長距離法 最短距離法就是類與類之間的距離采用最短距離的系統(tǒng)聚類方法。 最長距離法是類與類之間的距離采用最長距離的系統(tǒng)聚類法。選擇最大的距離作為新類與其他類之間的距離，然后將類間距離最小的兩類進(jìn)行合并，一直合并到只有一類為止。上述兩方法中，主要的不同是計算新類與其他類的距離的遞推公式不同。,,例 1 設(shè)有六個樣本，每個只測量一個指標(biāo)，分別為1,2,5,7,9,10，試用最

31、短距離法分類。（1）樣本采用絕對值距離,,（2）第一類和第二類合并成第七類 第五類和第六類合并成第8類,,（3）第3,4,8合為第9類（4）最后第7和第9 合成第10類。,§3.4 系統(tǒng)聚類法,最短距離法也可用于對指標(biāo)的分類，分類時可以用距離也可以用相似系數(shù)。但用相似系數(shù)時應(yīng)找最大的元素并類，計算新類與其他類的距離采用最長距離法。最短距離法的主要缺點是它有鏈接聚合的趨勢，因為類與類之

32、間的距離為所有距離中的最短者，兩類合并以后，它與其他類的距離縮小了，這樣容易形成一個比較大的類，大部分樣品都被聚在一類中，在樹狀聚類圖中，會看到一個延伸的鏈狀結(jié)構(gòu)，所以最短距離法的聚類效果并不好，實際中不提倡使用。最長距離法克服了最短距離法鏈接聚合的缺陷，兩類合并以后與其他類的距離是原來兩個類中的距離最大者，加大了合并后的類與其他類的距離。,§3.4 系統(tǒng)聚類法,3.4.2 重心法和類平均法從物理的觀點看，一個類用它

33、的重心（該類樣品的均值）做代表比較合理，類與類之間的距離就用重心之間的距離來代表。若樣品之間采用歐氏距離，設(shè)某一步將類 和類 合并成 ，它們各有 、 、 （ ）個樣品，它們的重心用 、 、 表示，顯然某一類 的重心為 ，它與新類 的距離是,,續(xù)例 1 設(shè)有六個樣本，每個只測量一個指標(biāo)，分別為1,2,5,7,9,10，試用重心法聚類類

34、。（1）樣本采用歐氏平方距離,,（2）第一類和第二類合并成第七類 第五類和第六類合并成第8類,,（3）第3,4合為第9類（4）第8和第9 合成第10類。,,（4）第8，9合為第10類（）最后第7和第10 合成第11類。,§3.4 系統(tǒng)聚類法,重心法雖有很好的代表性，但并未充分利用各樣本的信息，有人建議將兩類之間的距離平方定義為這兩類元素兩兩之間的平均平方距離，即：

35、上式也可以記為：,§3.4 系統(tǒng)聚類法,類平均法是聚類效果較好、應(yīng)用比較廣泛的一種聚類方法。它有兩種形式，一種是組間聯(lián)結(jié)法（Between-groups linkage），另一種是組內(nèi)聯(lián)結(jié)法（Within-groups linkage）。組間聯(lián)結(jié)法在計算距離時只考慮兩類之間樣品之間距離的平均，組內(nèi)聯(lián)結(jié)法在計算距離時把兩組所有個案之間的距離都考慮在內(nèi)。還有一種類平均法，它定義類與類之間的距離為：用同樣的方法可以導(dǎo)出這

36、種定義下的距離遞推公式如下：有人認(rèn)為類平均法是系統(tǒng)聚類法中比較好的方法之一。,§3.4 系統(tǒng)聚類法,3.4.3 離差平方和法（或稱Ward方法）離差平方和方法是由Ward提出來的，許多資料上稱做Ward法。他的思想是來于方差分析，如果類分得正確，同類樣品的離差平方和應(yīng)當(dāng)較小，類與類之間的離差平方和應(yīng)當(dāng)較大。設(shè)將n個樣品分成k類 ，用 表示類 中的第i個樣品（注意 是P維

37、向量）， 表示類 的樣品個數(shù)， 是類 的重心，則在類 中的樣品的離差平方和是,§3.4 系統(tǒng)聚類法,整個類內(nèi)平方和是：當(dāng)固k定時，要選擇使L達(dá)到極小的分類，n個樣品分成k類，一切可能的分法有：當(dāng)n，k很大時， 就達(dá)到了天文數(shù)字，因此，要比較這么多分類來選擇最小的L ，即使高速計算機(jī)也難以完成，于是，只好放棄在一切分類中求L的極小值的要求，而是設(shè)計出某種規(guī)格，找到一個局部

38、最優(yōu)解。,§3.4 系統(tǒng)聚類法,Ward法就是找局部最優(yōu)解的一個方法。其思想是先將n個樣品各自成一類，然后每次縮小一類，每縮小一類離差平方和就要增大，選擇使增加最小的兩類合并，直到所有的樣品歸為一類為止。 若將某類 和類 合并成 ，它們各有 、 、 個樣品（ ），它們的重心用 、 和 表示，某一新類 的重心為 ，它與新類的距離遞

39、推公式：需要指出的是，離差平方和法只能得到局部最優(yōu)解。至今還沒有較好的方法以較少的計算的得到精確的最優(yōu)解。,§3.4 系統(tǒng)聚類法,【例3-4】 為了研究遼寧等5省份2000年城鎮(zhèn)居民消費支出的分布規(guī)律，根據(jù)調(diào)查資料作類型劃分。指標(biāo)名稱及原始數(shù)據(jù)見表3-5。SPSS實現(xiàn)五種系統(tǒng)聚類方法。,§3.4 系統(tǒng)聚類法,現(xiàn)在將表3-5中的每個省份看成是一個樣品，先計算五省份之間的歐氏距離。用SPSS

40、軟件可以實現(xiàn),詳細(xì)步驟如下：(1) 打開數(shù)據(jù)。使用菜單中File→Open命令，然后選中要分析的數(shù)據(jù)3-4.sav。(2)在菜單中的選項中選擇Analyze→Classify命令，Classify命令下有兩個聚類分析命令，一是K-means cluster（K­-均值聚類），二是Hierarchical cluster（系統(tǒng)聚類法）。這里我們選擇系統(tǒng)聚類法。(3) 在系統(tǒng)聚類法中，我們看到Cluster下有兩個選項，Ca

41、ses（樣品聚類或Q型聚類）和Variables (變量聚類或R型聚類)。這里我們選擇對樣品進(jìn)行聚類。,§3.4 系統(tǒng)聚類法,(4) Display下面有兩個選項，分別是Statistics (統(tǒng)計量)、Plots (輸出圖形) ，我們可以選擇所需要輸出的統(tǒng)計量和圖形。(5) 在系統(tǒng)聚類法中底下有四個按紐，分別是Statistics、Plots、Method、Save。（a）在Statistics中，有Agglome

42、ration schedule（每一階段聚類的結(jié)果），Proximity matrix（樣品間的相似性矩陣）。由Cluster membership可以指定聚類的個數(shù)，none選項不指定聚類個數(shù)，Single solution指定一個確定類的個數(shù)，Range of solution指定類的個數(shù)的范圍（如從分3類到分5類）。,§3.4 系統(tǒng)聚類法,(b)在Plots中，有Dendrogram（譜系聚類圖，也稱樹狀聚類圖）、

43、Icicle(冰柱圖)、Orientation指冰柱圖的方向（Horizontal 水平方向、Vertical垂直方向）。(c)在Method中， Cluster可以選擇聚類方法，Measure中可以選擇計算的距離。(d)在Save中，可以選擇保存聚類結(jié)果。 選好每個選項后，點“OK”就可以執(zhí)行了。根據(jù)結(jié)果距離矩陣可以分析。距離矩陣各元素數(shù)值的大小反映了5個省份間消費水平的接近程度。例如青海省和遼寧省之間的歐氏距離最小，反映了這

44、兩個省份城鎮(zhèn)居民的消費水平最接近。,例3-4 樣品與樣品歐氏距離，類于類最短距離法,,例1 樣品之間歐氏距離（絕對值距離），類于類之間最短距離法,§3.4 系統(tǒng)聚類法,3.4.4 分類數(shù)的確定如何選擇分類數(shù)是各種聚類方法中的主要問題之一。在K均值聚類法中聚類之前需要指定分類數(shù)，譜系聚類法（系統(tǒng)聚類法）中我們最終得到的只是一個樹狀結(jié)構(gòu)圖，從圖中可以看出存在很多類，但問題是如何確定類的最佳個數(shù)

45、。確定分類數(shù)的問題是聚類分析中迄今為止尚未完全解決的問題之一，主要的障礙是對類的結(jié)構(gòu)和內(nèi)容很難給出一個統(tǒng)一的定義，這樣就給不出從理論上和實踐中都可行的虛無假設(shè)。實際應(yīng)用中人們主要根據(jù)研究的目的，從實用的角度出發(fā)，選擇合適的分類數(shù)。,§3.4 系統(tǒng)聚類法,Demir-men曾提出了根據(jù)樹狀結(jié)構(gòu)圖來分類的準(zhǔn)則：準(zhǔn)則1：任何類都必須在鄰近各類中是突出的，即各類重心之間距離必須大。準(zhǔn)則2：各類所包含的元素都不要過分地多。

46、準(zhǔn)則3：分類的數(shù)目應(yīng)該符合使用的目的。準(zhǔn)則4：若采用幾種不同的聚類方法處理，則在各自的聚類圖上應(yīng)發(fā)現(xiàn)相同的類。,§3.4 系統(tǒng)聚類法,系統(tǒng)聚類中每次合并的類與類之間的距離也可以作為確定類數(shù)的一個輔助工具。首先把離得近的類合并，在并類過程中聚合系數(shù)呈增加趨勢，聚合系數(shù)小，表示合并的兩類的相似程度較大，兩個差異很大的類合到一起，會使該系數(shù)很大。 如果以y軸為聚合系數(shù)，x軸表示分類數(shù)，畫出聚合系數(shù)隨分類數(shù)的變化曲線，會得到

47、類似于因子分析中的碎石圖，可以在曲線開始變得平緩的點選擇合適的分類數(shù)。,§3.4 系統(tǒng)聚類法,3.4.5 系統(tǒng)聚類法的統(tǒng)一上面介紹的五種系統(tǒng)聚類法，并類的原則和步驟是完全一樣的，所不同的是類與類之間的距離有不同的定義，從而得到不同的遞推公式，如果能將它們統(tǒng)一為一個公式，將大大有利于編制計算機(jī)程序。Lance和Williams于1967年給出了一個統(tǒng)一的公式其中， 對于不同的方法有不

48、同的取值。,§3.4 系統(tǒng)聚類法,表3-6列出了不同方法四參數(shù)的取值。表中除了上述五種方法以外，還列舉了另三種系統(tǒng)聚類法，由于它們用得較少，不再詳述。,§3.4 系統(tǒng)聚類法,一般而言，不同的方法聚類的結(jié)果不完全相同。最短距離法適用于條形的類。最長距離法、重心法、類平均法、離差平方和法適用于橢圓形的類。由于上述的聚類方法得到的結(jié)果是不完全相同的。于是產(chǎn)生一個問題：我們應(yīng)當(dāng)選擇哪一個結(jié)果為好？ 為了解決這

49、個問題，需要研究系統(tǒng)聚類法的性質(zhì)，現(xiàn)簡要介紹如下。1.單調(diào)性。最短距離法、最長距離法、類平均法、離差平方和法、可變法和可變類平均法都具有單調(diào)性，只有重心法和中間距離法不具有單調(diào)性。,§3.4 系統(tǒng)聚類法,2.空間的濃縮和擴(kuò)張。對同一問題作距離圖時，橫坐標(biāo)（并類距離）的范圍相差很遠(yuǎn)。最短距離法的范圍較小，而最長距離法的范圍較大，而類平均法則介于兩者之間。范圍小的方法區(qū)別類的靈敏度差，但范圍太大的方法，靈敏度過高會使支流來

50、淹沒主流，要適中為好。有關(guān)系統(tǒng)聚類法的性質(zhì)，還可從其他角度提出了比較優(yōu)與劣的原則。將n個樣品，欲分為k類，有人定義一個分類函數(shù)（或叫損失函數(shù)），然后尋找這個函數(shù)的最優(yōu)解，在某些條件下，最短距離法的解是最優(yōu)的，而系統(tǒng)聚類法的其他方法都不具有這個性質(zhì)。故最短距離法在實際中也很被推崇。,§3.5 模糊聚類分析,模糊集的理論是二十世紀(jì)六十年代中期美國的自動控制專家查德(L.A.Zadeh)教授首先提出的。模糊集的理論已廣泛應(yīng)用于

51、許多領(lǐng)域，將模糊集概念用到聚類分析中便產(chǎn)生了模糊聚類分析。模糊聚類法就是將模糊數(shù)學(xué)的思想觀點應(yīng)用到聚類分析中產(chǎn)生的方法。該方法多用于定性變量的分類。此方法作為選學(xué)內(nèi)容。,§3.6 K-均值聚類和有序樣品的聚類,3.6.1 K-均值法(快速聚類法)非譜系聚類法是把樣品（而不是變量）聚集成K個類的集合。類的個數(shù)K可以預(yù)先給定，或者在聚類過程中確定。例如可以事先指定樣本的分類數(shù)，或者指定使聚類過程中止的判據(jù)或迭代次數(shù)等。非

52、譜系方法可應(yīng)用于比系統(tǒng)聚類法大得多的數(shù)據(jù)組。非譜系聚類法或者一開始就對元素分組，或者從一個構(gòu)成各類核心的“種子”集合開始。選擇好的初始構(gòu)形，將能免除系統(tǒng)的偏差。一種方法是從所有項目中隨機(jī)地選擇“種子”點或者隨機(jī)地把元素分成若干個初始類。我們討論的是最特殊的非譜系過程，即K-均值法。,§3.6 K-均值聚類和有序樣品的聚類,K-均值法, 又叫快速聚類法，是Macqueen于1967年提出的。K-均值法的思想是把每個樣品聚集

53、到其最近形心（均值）類中去。在它的最簡單說明中，這個過程由下列三步所組成：（1）把樣品粗略分成K個初始類；（2）進(jìn)行修改，逐個分派樣品到其最近均值的類中去（通常用標(biāo)準(zhǔn)化數(shù)據(jù)或非標(biāo)準(zhǔn)化數(shù)據(jù)計算歐氏距離）。重新計算接受新樣品的類和失去樣品的類的形心（均值）；（3）重復(fù)第2步，直到各類無元素進(jìn)出。,§3.6 K-均值聚類和有序樣品的聚類,若不在一開始就粗略地把樣品分到K個預(yù)先指定的類（第1步），那我們也可以指定K個最初形心（

54、種子點），然后進(jìn)行第2步。樣品的最終聚類在某種程度上依賴于最初的劃分，或種子點的選擇。為了檢驗聚類的穩(wěn)定性，可用一個新的初始分類重新檢驗整個聚類算法。如最終分類與原來一樣，則不必再行計算；否則，須另行考慮聚類算法。K-均值法仍是利用距離作為變量個體之間關(guān)系變量密切程度的指標(biāo)，并通過制定分類數(shù)而求的聚類結(jié)果。,§3.6 K-均值聚類和有序樣品的聚類,基本步驟如下：首先，選擇聚類分析的變量、標(biāo)識變量和參數(shù)； 注意

55、：參與聚類分析的變量必須是數(shù)值型變量。 為了標(biāo)識各觀測量最終所屬于哪一類，指定一個表明觀測量特征的變量作為標(biāo)識變量。指定的聚類數(shù)必須大于等于2，但不能大于觀測次數(shù)。其次，確定K個初始類中心。在給定聚類數(shù)為K的條件下，首先需指定K個具有代表性的觀測量作為聚類的種子。K個事先指定的觀測量就是K個聚類中心點，也成為初始類中心?？梢赃x擇自己指定或或系統(tǒng)指定方式確定中心點。,§3.6 K-均值聚類和有序樣品的聚類,第三，根據(jù)距離最近

56、原則進(jìn)行分類。按照距離這K個類中心距離最近原則，把觀測量分配到各類中心所在的類中，形成第一次迭代的K個分類。第四，根據(jù)聚類終止條件進(jìn)行迭代。根據(jù)組成每一類的觀測量計算各變量均值，每一類中的各個均值在n維空間又形成k個點，這就是第二次迭代的類中心,按照這種方法依次迭代下去，直到達(dá)到指定的迭代次數(shù)或中止迭代的判據(jù)要求時，迭代停止，聚類結(jié)束。從上述分析過程可以看出， K-mean不僅是快速聚類分析方法，而且是一種逐步聚類分析（是先將聚

57、類對象進(jìn)行初始分類，然后逐步調(diào)整得到最終分類）。,,例 假定對A、B、C、D四個樣本分布觀測兩個變量X1和X2得到如下表格,將以上樣本聚成兩類,,第一步，K=2，將樣本隨意分成兩類（A,B）和（C,D），計算兩個類的中心坐標(biāo),,第二步，計算某個樣本到各類中心的歐式平方距離,更新后的中心坐標(biāo)為,,第三步，再次檢查每個樣本，決定是否重新分類,§3.6 K-均值聚類和有序樣品的聚類,K-均值聚類的SPSS實現(xiàn)現(xiàn)在將3-5中的每個

58、地區(qū)看成是一個樣品，用SPSS軟件可以實現(xiàn)K-均值法，SPSS軟件操作：（1）打開數(shù)據(jù)。使用菜單中File→Open命令，然后選中要分析的數(shù)據(jù)3-5.sav。（2）Analyze→Classify → K-means cluster命令，（3）選擇聚類分析的變量Variables和Label Cases。在Number of Clusters文本框中輸入聚類的類數(shù)，該數(shù)應(yīng)小于個案總數(shù)。（4）點擊OK,§3.6 K-

59、均值聚類和有序樣品的聚類,關(guān)于K-均值法的幾點評注：對于預(yù)先不固定類數(shù)K這一點有很大的爭論，其中包括下面幾點：（1）如果有兩個或多個“種子”點無意中跑到一個類內(nèi)，則其聚類結(jié)果將很難區(qū)分。（2）局外干擾的存在將至少產(chǎn)生一個樣品非常分散的類。（3）即使已知總體由K個類組成，抽樣方法也可造成屬于最稀疏類數(shù)據(jù)不出現(xiàn)在樣本中。強(qiáng)行將這些數(shù)據(jù)分成K個類會導(dǎo)致無意義的聚類。提示：許多聚類算法都要求給定K，而選擇幾種算法進(jìn)行反復(fù)檢驗，對于結(jié)果

60、的分析也許是有好處的。,快速聚類 例題,,例3-4,,§3.6 K-均值聚類和有序樣品的聚類,3.6.2 有序樣品的聚類在前幾節(jié)的討論中，分類的樣品是相互獨立的，分類時彼此是平等的。但在有些實際問題中，要研究的現(xiàn)象與時間的順序密切相關(guān)。例如我們想要研究，從1949年到2011年以來，國民收入或者GDP可以劃分為幾個階段，階段的劃分必須以年份順序為依據(jù)，總的想法是要將國民收入或者GDP接近的年份劃分到一個段內(nèi)，要完成類似

61、這樣的問題的研究，用前幾節(jié)分類的方法顯然是不行了。,§3.6 K-均值聚類和有序樣品的聚類,對于這類有序樣品的分類，實質(zhì)上是需要找出一些分點，將它們劃分成幾個分段，每個分段看作一類，稱這種分類為分割。顯然，分點在不同位置可以得到不同的分割。這樣就存在一個如何決定分點，使達(dá)到所謂最優(yōu)分割的問題。即要求一個分割能使各段內(nèi)部樣品間的差異最小，而各段之間樣品的差異最大。這就是決定分割點的依據(jù)。假設(shè)用

62、表示n個有順序的樣品，有序樣品的分類結(jié)果要求每一類必須呈 ，由于增加了有序這個約束條件，對分類有什么影響？,§3.6 K-均值聚類和有序樣品的聚類,1、可能的分類數(shù)目n個樣品分成k類，如果樣品是彼此相等的，則一切可能的分法有對于有序樣品，n個樣品分成k類的一切可能的分法有：,§3.6 K-均值聚類和有序樣品的聚類,2、最優(yōu)分割法

63、最優(yōu)分割法用來分類的依據(jù)是離差平方和，但由于 比 小得多，因此和系統(tǒng)聚類法中的離差平方和法有有所不同，前者可以求得精確最優(yōu)解，而后者只能久的局部最優(yōu)解。這個方法首先是由Fisher提出的，許多書上又稱為Fisher算法。設(shè)樣品依次 （每個是n維向量），最優(yōu)分割法的步驟大致如下：（1）定義類的直徑 設(shè)某一類 是

64、 ，它們的均值記為 ：,§3.6 K-均值聚類和有序樣品的聚類,的直徑用 表示，常用的直徑是 當(dāng)m=1時，有時用直徑 ，其中 是 的中位數(shù)。（2）定義目標(biāo)函數(shù) 將n個樣品分成k類，設(shè)某一種分法是： 或簡記為：,§3.6 K-均值聚類和有序

65、樣品的聚類,其中分點為： 定義這種分類的目標(biāo)函數(shù)為： 當(dāng)n,K固定時， 越小表示各類的離差平方和最小，分類是合理的。 因此，要找一種分法 使目標(biāo)函數(shù)達(dá)到極小，以下 一般表示使 達(dá)到極小的分類。,§3.6 K-均值聚類和有序樣品的聚類,（3）精確最優(yōu)解的求法 容易驗證有以下遞推公式： 當(dāng)我們要分

66、成k類時，首先找 使 達(dá)到最小 ，即 。,§3.6 K-均值聚類和有序樣品的聚類,于是 ，然后找 使它滿足 得到類 ，類似的方法得到所有的類

67、 ，這就是我們欲求得最優(yōu)解。,§3.7 計算步驟與上機(jī)實踐,本書以SPSS15.0和S-Plus2000兩種軟件來說明前面講述的幾種聚類法的實現(xiàn)過程。具體步驟如下：分析所需要研究的問題，確定聚類分析所需要的多元變量；選擇對樣品聚類還是對指標(biāo)聚類；選擇合適的聚類方法；選擇所需的輸出結(jié)果。我們將實現(xiàn)過程用邏輯框圖表示為圖3.8。,§3.7 計算步驟與上機(jī)實踐,§

68、;3.7 計算步驟與上機(jī)實踐,3.7.1 系統(tǒng)聚類法一個實例分析。根據(jù)各個國家信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r，用SPSS軟件對各地區(qū)進(jìn)行聚類分析。 詳細(xì)步驟如下：（1） 打開數(shù)據(jù)。File→Open →選中要分析的數(shù)據(jù)。（2）Analyze→Classify，Classify命令下有兩個聚類分析命令，一是K-means cluster（K­-均值聚類），二是Hierarchical cluster（系統(tǒng)聚類法）。這里我們選擇

69、系統(tǒng)聚類法。,§3.7 計算步驟與上機(jī)實踐,（3）在系統(tǒng)聚類法中，我們看到Cluster下有兩個選項，Cases（樣品聚類或Q型聚類）和Variables (變量聚類或R型聚類)。這里我們選擇對樣品進(jìn)行聚類。（4） Display下面有兩個選項，分別是Statistics (統(tǒng)計量)、Plots（輸出圖形），我們可以選擇所需要輸出的統(tǒng)計量和圖形。 （5） 在系統(tǒng)聚類法中底下有四個按紐，分別是Statistics、Plot

70、s、Method、Save。,§3.7 計算步驟與上機(jī)實踐,（a）在Statistics中，有Agglomeration schedule（每一階段聚類的結(jié)果），Proximity matrix（樣品間的相似性矩陣）。由Cluster membership可以指定聚類的個數(shù)，none選項不指定聚類個數(shù)，Single solution指定一個確定類的個數(shù)，Range of solution指定類的個數(shù)的范圍（如從分3類到分5類