聚類分析.doc

。聚類分析專題6.1 引言俗話說，“物以類聚，人以群分”，在自然科學和社會科學等各領(lǐng)域中，存在著大量的分類問題。分類學是人類認識世界的基礎科學，在古老的分類學中，人們主要靠經(jīng)驗和專業(yè)知識進行定性的分類，很少利用數(shù)學工具進行定量的分類。隨著人類科學技術(shù)的發(fā)展，對分類的要求越來越高，以致有時僅憑經(jīng)驗和專業(yè)知識難以確切地進行分類，于是人們逐漸地把數(shù)學工具引用到了分類學中，這便形成了數(shù)值分類學這一學科，之后又將多元分析的技術(shù)引入到數(shù)值分類學，便又從數(shù)值分類學中分離出一個重要分支聚類分析。與多元分析的其它分析方法相比，聚類分析方法較為粗糙，理論上還不夠完善，正處于發(fā)展階段。但是，由于該方法應用方便，分類效果較好，因此越來越為人們所重視。這些年來聚類分析的方法發(fā)展較快，內(nèi)容越來越豐富。判別分析與聚類分析都是研究事物分類的基本方法，它們有著不同的分類目的，彼此之間既有區(qū)別又有聯(lián)系。各種判別分析方法都要求對類有事先的了解，通常是每一類都有一個樣本，據(jù)此得出判別函數(shù)和規(guī)則，進而可對其它新的樣品屬于哪一類作出判斷。對類的事先了解和確定常常可以通過聚類分析得到。聚類分析的目的是把分類對象按一定規(guī)則分成若干類，這些類不是事先給定的，而是根據(jù)數(shù)據(jù)的特征確定的。在同一類里的這些對象在某種意義上傾向于彼此相似，而在不同類里的對象傾向于不相似。聚類分析能夠用來概括數(shù)據(jù)而不只是為了尋找“自然的”或“實在的”分類。例如，在選拔少年運動員時，對少年的身體形態(tài)、身體素質(zhì)、生理功能的各種指標進行測試，據(jù)此對少年進行分類，分在同一類里的少年這些指標較為相近。類確定好之后，可以根據(jù)各類的樣本數(shù)據(jù)得出選材的判別規(guī)則，作為選材的依據(jù)。又如，根據(jù)啤酒中含有的酒精成分、納成分、所含的熱量“卡路里”數(shù)值，可以對啤酒進行分類。聚類分析根據(jù)分類對象不同分為型聚類分析和型聚類分析。型聚類分析是指對樣品進行聚類，型聚類分析是指對變量進行聚類。本章我們主要討論型聚類。6.2 距離和相似系數(shù)在對樣品（或變量）進行分類時，樣品（或變量）之間的相似性是如何度量的呢？這一節(jié)中，我們介紹兩個相似性度量距離和相似系數(shù)，前者常用來度量樣品之間的相似性。后者常用來度量變量之間的相似性。樣品之間的距離和相似系數(shù)有著各種不同的定義，而這些定義與變量的類型有著非常密切的關(guān)系。通常變量按測量尺度的不同可以分為以下三類：（1） 間隔尺度變量：變量用連續(xù)的量來表示，如長度、重量、速度、溫度等。（2） 有序尺度變量：變量度量時不用明確的數(shù)量表示，而是用等級來表示，如某產(chǎn)品分為一等品、二等品、三等品等有次序關(guān)系。（3） 名義尺度變量：變量用一些類表示，這些類之間既無等級關(guān)系也無數(shù)量關(guān)系，如性別、職業(yè)、產(chǎn)品的型號等。我們這里主要討論具有間隔尺度變量的樣品聚類分析方法。一、距離設為第個樣品的第個指標，數(shù)據(jù)矩陣列于表6.1。每個樣品有個變量，故每個樣品都可以看成是中的一個點，個樣品就是中的個點。在中需定義某種距離，第個樣品與第個樣品之間的距離記為，在聚類過程中，距離較近的點傾向于歸為一類，距離較遠的點應歸屬不同的類。所定義的距離一般應滿足如下四個條件：（） ，對一切；（） ，當且僅當?shù)趥€樣品與第個樣品的各變量值相同；（） ，對一切；（） ，對一切。表6.1 數(shù)據(jù)矩陣變量樣品12常用的距離有如下幾種：1明考夫斯基(Minkowski)距離第個樣品與第個樣品間的明考夫斯基距離定義為（6.2.1）這里為某一自然數(shù)，這是一個最常用最直觀的距離。當時，稱為絕對值距離；當時，稱為歐氏距離；當時，稱為切比雪夫距離。當各變量的單位不同或雖單位相同但各變量的測量值相差很大時，不應直接采用明考夫斯基距離，而應先對各變量的數(shù)據(jù)作標準化處理，然后用標準化后的數(shù)據(jù)計算距離。最常用的標準化處理是，令，其中，為第個變量的樣本均值，為第個變量的樣本方差。2馬氏(Mahalanobis)距離第個樣品與第個樣品間的馬氏距離為（6.2.2）其中，為樣本協(xié)方差矩陣。使用馬氏距離的好處是考慮到了各變量之間的相關(guān)性，并且與各變量的單位無關(guān)。不足之處是對馬氏距離公式中的，若始終不變，則往往顯得不妥；若要隨聚類過程而不斷變化，則會有許多不便。3蘭氏(Lance和Williams)距離當，時，則可以定義第個樣品與第個樣品間的蘭氏距離為（6.2.3）這個距離與各變量單位無關(guān)，但沒有考慮變量間的相關(guān)性。由于它對大的異常值不敏感，故適用于高度偏斜的數(shù)據(jù)。4斜交空間距離由于樣品的各個變量之間往往存在不同程度的相關(guān)關(guān)系，因此有時采用歐氏距離顯得不夠理想，有人建議采用斜交空間距離。第個樣品與第個樣品間的斜交空間距離定義為其中是變量與變量間的相關(guān)系數(shù)。當個變量互不相關(guān)時，即斜交空間距離退化為歐氏距離（除相差一個常數(shù)倍外）。以上幾種距離的定義均要求變量是間隔尺度的，如果使用的變量是有序尺度或名義尺度的，則有相應的一些定義距離的方法。下例是對名義尺度變量的一種距離定義。例6.2.1 設有五個變量均為名義尺度變量，取值和，取值和，取值和，取值、和，取值和?，F(xiàn)有兩個樣品，這兩個樣品的第一個變量都取值，稱為配合的，第二個變量一個取，一個取，稱為不配合的。記配合的變量數(shù)為，不配合的變量數(shù)為，定義它們之間的距離為（6.2.5）因此與之間的距離為。二、相似系數(shù)聚類分析方法不僅用來對樣品進行分類，而且可以用來對變量進行分類，在對變量進行分類時，常常采用相似系數(shù)來度量變量之間的相似性。變量之間的關(guān)系越是密切，其相似系數(shù)越接近于1（或-1）；反之，它們的關(guān)系越是疏遠，其相似系數(shù)越是接近于0。聚類時，比較相似的變量傾向于歸為一類，不怎么相似的變量歸屬不同的類。變量與的相似系數(shù)用來表示，它一般應滿足以下三個條件：（），當且僅當，和為常數(shù)；（），對一切；（），對一切。最常用的相似系數(shù)有如下兩種：1夾角余弦變量與的夾角余弦定義為（6.2.6）它是中變量的觀測向量與變量的觀測向量之間夾角的余弦函數(shù)，即。2相關(guān)系數(shù)變量與的相關(guān)系數(shù)定義為（6.2.7）相關(guān)系數(shù)我們曾用來表示，這里表示為是為了與其它相似系數(shù)的符號一致。如果變量與是已標準化了的，則它們間的夾角余弦就是原變量的相關(guān)系數(shù)。變量之間常借助于相似系數(shù)來定義距離，如令（6.2.8）樣品之間有時也用相似系數(shù)來度量樣品間的相似性程度。一般來說，同一批數(shù)據(jù)采用不同的相似性度量，會得到不同的分類結(jié)果。在進行聚類分析的過程中，應根據(jù)實際情況選取好合適的相似性度量。如在經(jīng)濟變量分析中，常采用相關(guān)系數(shù)來描述變量間的相似性程度。一般情況下，相關(guān)系數(shù)比其它的相似系數(shù)有更強的可變性，但分辨力要弱一些。6.3 系統(tǒng)聚類法系統(tǒng)聚類法是聚類分析諸方法中用得最多的一種，其基本思想是：開始將個樣品各自作為一類，并規(guī)定樣品之間的距離和類與類之間的距離，然后將距離最近的兩類合并成一個新類，計算新類與其它類的距離（注：未合并的類之間的距離不用重新計算）；重復進行兩個最近類的合并，每次減少一類，直至所有的樣品合并為一類。本節(jié)介紹常用的八種系統(tǒng)聚類方法，所有這些聚類方法的區(qū)別在于類與類之間距離的計算方法不同。以下我們用表示第個樣品與第個樣品的距離，表示類，表示與的距離。本節(jié)介紹的系統(tǒng)聚類法中，除離差平方和法之外，其余所有的方法因一開始每個樣品自成一類，類與類之間的距離與樣品之間的距離相同，即，所以起初的距離矩陣全部相同，記為。一、最短距離法定義類與類之間的距離為兩類最近的樣品間的距離，即（6.3.1）稱這種系統(tǒng)聚類法為最短距離法。用最短距離法的聚類步驟如下：（1）規(guī)定樣品之間的距離，計算個樣品的距離矩陣，它是一個對稱矩陣。（2）選擇中的最小元素，設為，則將與合并成一個新類，記為，即。（3）計算新類與任一類之間的距離為（6.3.2）將中的行，列用（6.3.2）式并成一個新行新列，新行新列對應，所得矩陣記為。（4）對重復上述對的兩步得，如此下去直至所有元素合并成一類為止。如果某一步中最小的元素不止一個，則對應這些最小元素的類可以同時合并。例6.3.1 設有五個樣品，每個只測量了一個指標，分別為1,2,6,8,11，試用最短距離法將它們分類。（1）樣品間采用絕對值距離（這時它與其它的明考夫斯基距離完全相同），計算樣品間的距離矩陣，列于表6.2。表6.2 0105407620109530（2）中最小的元素是，于是將和合并成，并利用（6.3.2）式計算與其它類的距離，列于表6.3。表6.3 0406209530（3）中最小的元素是，于是將和合并成，并利用（6.3.2）式計算與其它類的距離，列于表6.4。表6.4 040930（4）中最小的元素是，于是將和合并成，并利用（6.3.2）式計算與其它類的距離，列于表6.5。表6.5 040（5）最后將和合并為，這時所有五個樣品聚為一類，過程終止。上述聚類過程可以畫成一張圖，如圖6.1所示。橫坐標的刻度是并類的距離，從圖上看，分兩類較為合適。這只是從直觀上確定了類的個數(shù)為2，關(guān)于確定類的個數(shù)問題我們將在稍后進行討論。二、最長距離法類與類之間的距離定義為兩類最遠樣品間的距離，即（6.3.3）稱這種系統(tǒng)聚類法為最長距離法。最長距離法與最短距離法的并類步驟完全相同，只是類間距離的遞推公式有所不同。設某步將類與合并成一個新類，則與任一類的距離為（6.3.4）對例6.3.1采用最長距離法，與前面相同，將和合并成，計算（）的公式為，的計算結(jié)果列于表6.6。表6.6 05072010530中的最小元素是，合并和成，計算（）的公式為，的計算結(jié)果列于表6.7。表6.7 0701050中的最小元素為，將和合并成，見表6.8。計算的公式為最后將和并為。其聚類圖如圖6.2所示，它與圖6.1有相似的形狀，但并類的距離要比圖6.1大一些，仍分為兩類為宜。表6.8 0100最長距離法可能被異常值嚴重地扭曲，這是值得我們在應用中注意的問題。一個有效的方法是刪去這些異常值之后再進行聚類。三、中間距離法類與類之間的距離既不取兩類最近樣品間的距離，也不取兩類最遠樣品間的距離，而是取介于兩者中間的距離，稱之為中間距離法。設某一步將和合并為，對于任一類，考慮由、和為邊組成的三角形（如圖6.3所示），取邊的中線作為。由初等平面幾何可知，的計算公式為（6.3.5）這就是中間距離法的遞推公式。中間距離法可推廣為更一般的情形，將（6.3.5）式三項的系數(shù)依賴于某個參數(shù)，即（6.3.6）這里，這種方法稱為可變法。四、類平均法類與類之間的平方距離定義為樣品對之間平方距離的平均數(shù)，即（6.3.7）其中和分別為類和的樣品個數(shù)，稱這種系統(tǒng)聚類法為類平均法。容易得到它的一個遞推公式為備注：因為，所以，同理備注完畢。由上所述，有(6.3.8)類平均法較好地利用了所有樣品之間的信息，在很多情況下它被認為是一種比較好的系統(tǒng)聚類法。在遞推公式（6.3.8）式中，的影響沒有被反映出來，為此可將該遞推公式進一步推廣為(6.3.9)其中，稱這種系統(tǒng)聚類法為可變類平均法。對例6.3.1采用類平均法進行聚類。如果我們一開始就將的每個元素都平方，則使用遞推公式會方便許多。（1）計算，見表6.9，它是將表6.2的各數(shù)平方。表6.9 01025160493640100812590（2）找中的最小元素，它是，將和合并為，計算與（）的距離。這時，由（6.3.8）式計算得同樣可算得和，列于表6.10。表6.10 020.5042.54090.52590（3）對重復上述步驟，將和并為，得平方距離矩陣（見表6.11）。表6.11 031.5090.5170將和合并成得（見表6.12），最后將和合并成，聚類過程終止。其聚類圖如圖6.4所示（此處省略）。表6.12 051.170五、重心法類與類之間的距離定義為它們的重心（均值）之間的歐氏距離。設和的重心分別為和，則和之間的平方距離為（6.3.10）這種系統(tǒng)聚類法稱為重心法。重心法在處理異常值方面比其它系統(tǒng)聚類法更穩(wěn)健，但是在別的方面一般不如類平均法或離差平方和法效果好。六、離差平方和法類、和合并成的新類的（類內(nèi)）離差平方和分別是它們反映了各自類內(nèi)樣品的分散程度。如果和這兩類相距較近，則合并后所增加的離差平方和應較??；否則應較大。于是我們定義和之間的平方距離為（6.3.12）這種系統(tǒng)聚類法稱為離差平方和法或Ward法?？梢则炞C，這個距離定義滿足通常定義距離所需滿足的四個條件。我們現(xiàn)在導出的另一簡化表達式。（6.3.13）可見，這個距離與由（6.3.10）式給出的重心法的距離只相差一個常數(shù)倍。重心法的類間距離與兩類的樣品數(shù)無關(guān)，而離差平方和法的類間距離與兩類的樣品數(shù)有較大關(guān)系，兩個大的類傾向于有較大的距離，因而不易合并，這往往符合我們對聚類的實際要求。離差平方和法在許多場合下優(yōu)于重心法，是比較好的一種系統(tǒng)聚類法，但它對異常值很敏感。七、系統(tǒng)聚類法的統(tǒng)一以上我們介紹了常用的八種系統(tǒng)聚類法，所有這些方法的并類原則或過程是完全相同的，不同之處在于類與類之間的距離有不同的定義，因而有不同的距離遞推公式。如果能把它們統(tǒng)一成一個公式，則將大大有利于計算機程序的編制。Lance和Williams于1967年將這些遞推公式統(tǒng)一了起來，統(tǒng)一的公式為：(6.3.15)其中、和是參數(shù)，不同的系統(tǒng)聚類法，它們有不同的取值。對例6.3.1幾種方法的聚類結(jié)果都相同，但一般而言，不同方法的聚類結(jié)果是不完全一樣的。各種方法都有其適用的場合，選用哪種方法需視實際情況和對聚類結(jié)果的要求而定。為了能取得較好的系統(tǒng)聚類，必須對聚類的一些性質(zhì)有較清楚的認識。下面我們介紹系統(tǒng)聚類法的兩個性質(zhì)。1單調(diào)性令是系統(tǒng)聚類法中第次并類時的距離，如例6.3.1中，用最短距離法時，有且有。如果一種系統(tǒng)聚類法能滿足，則稱它具有單調(diào)性。這種單調(diào)性符合系統(tǒng)聚類法的思想，先合并較相似的類，后合并較疏遠的類。可以證明，最短距離法、最長距離法、可變法、類平均法、可變類平均法和離差平方和法都具有單調(diào)性，但中間距離法和重心法不具有單調(diào)性。2空間的濃縮和擴張比較圖6.1和圖6.2可以看到，對同一問題采用不同的系統(tǒng)聚類法作聚類圖時，橫坐標的范圍可以相差很大，最短距離法的范圍，最長距離法的范圍。設和是兩個元素非負的同階矩陣，若（對一切），則記作。這個記號僅在本節(jié)中使用，請勿與通常涉及非負定矩陣的記號相混淆。設有兩種系統(tǒng)聚類法，它們在第步的距離矩陣分別為和，若，則稱第一種方法比第二種方法使空間擴張，或第二種方法比第一種方法使空間濃縮。我們以類平均法為基準，其它方法都與它作比較，可以證明有如下一些結(jié)論：（1）（短）（平），（重）（平），即最短距離法和重心法比類平均法使空間濃縮。（2）（長）（平），即最長距離法比類平均法使空間擴張。（3）當時，（變平）（平），即這時可變類平均法比類平均法使空間濃縮；當時，（變平）（平），即此時可變類平均法比類平均法使空間擴張；當時，可變類平均法退化為類平均法，即（變平）（平）。以上比較的這些方法中，太濃縮的方法不夠靈敏，太擴張的方法靈敏度可能過高而容易失真。類平均法比較適中，它既不太濃縮也不太擴張，因此它被認為是一種比較理想的方法。八、類的個數(shù)在聚類過程中類的個數(shù)如何來確定才是適宜的呢？這是一個十分困難的問題，人們至今仍未找到令人滿意的方法，但這又是一個不可回避的問題。下面我們介紹確定類個數(shù)的幾種常用方法。1給定一個閾值通過觀測聚類圖，給出一個你認為合適的閾值，要求類與類之間的距離要大于，有些樣品可能會因此而歸不了類。這種方法有較強的主觀性，這是它的不足之處。如圖6.1中，取，即在距離為3.3處切一刀，5個樣品分為1，2和6，8，11兩個類。2觀測樣品的散點圖如果樣品只有兩個或三個變量，則可通過觀測數(shù)據(jù)的散點圖來確定類的個數(shù)。對于三個變量，可使用SAS軟件通過旋轉(zhuǎn)三維坐標軸來觀測散點圖。3統(tǒng)計量設總樣品數(shù)為，聚類時把所有樣品合并成個類，類的樣品數(shù)和重心分別是和，則，所有樣品的總