五 模式識別-聚類

模式識別的理論與方法

——聚類分析

信息工程學(xué)院

田玉剛主要內(nèi)容

數(shù)據(jù)預(yù)處理距離與相似系數(shù)算法分析實例分析

聚類分析又稱群分析，它是研究（樣本/樣品/模式）分類問題的一種多元統(tǒng)計方法，所謂類，通俗地說，就是指相似元素的集合。嚴(yán)格的數(shù)學(xué)定義是較麻煩的，在不同問題中類的定義是不同的。聚類分析起源于分類學(xué)，在考古的分類學(xué)中，人們主要依靠經(jīng)驗和專業(yè)知識來實現(xiàn)分類。隨著生產(chǎn)技術(shù)和科學(xué)的發(fā)展，人類的認(rèn)識不斷加深，分類越來越細(xì)，要求也越來越高，有時光憑經(jīng)驗和專業(yè)知識是不能進(jìn)行確切分類的，往往需要定性和定量分析結(jié)合起來去分類，于是數(shù)學(xué)工具逐漸被引進(jìn)分類學(xué)中，形成了數(shù)值分類學(xué)。后來隨著多元分析的引進(jìn)，聚類分析又逐漸從數(shù)值分類學(xué)中分離出來而形成一個相對獨立的分支。在社會經(jīng)濟(jì)領(lǐng)域中存在著大量分類問題，比如對我國大陸31個省市自治區(qū)獨立核算工業(yè)企業(yè)經(jīng)濟(jì)效益進(jìn)行分析，一般不是逐個省市自治區(qū)去分析，而較好地做法是選取能反映企業(yè)經(jīng)濟(jì)效益的代表性指標(biāo)，如百元固定資產(chǎn)實現(xiàn)利稅、資金利稅率、產(chǎn)值利稅率、百元銷售收入實現(xiàn)利潤、全員勞動生產(chǎn)率等等，根據(jù)這些指標(biāo)對31個省市自治區(qū)進(jìn)行分類，然后根據(jù)分類結(jié)果對企業(yè)經(jīng)濟(jì)效益進(jìn)行綜合評價，就易于得出科學(xué)的分析。又比如若對某些大城市的物價指數(shù)進(jìn)行考察等等?？傊枰诸惖膯栴}很多，因此聚類分析這個有用的數(shù)學(xué)工具越來越受到人們的重視，它在許多領(lǐng)域中都得到了廣泛的應(yīng)用。

值得提出的是將聚類分析和其它方法聯(lián)合起來使用，如判別分析、主成分分析、回歸分析等往往效果更好;并且沒有哪一種聚類方法具有絕對優(yōu)勢，如果有優(yōu)勢，也只是相對于具體的數(shù)據(jù)特征而言。聚類分析內(nèi)容非常豐富，有簡單聚類法、層次聚類法、動態(tài)聚類法、模糊聚類法、圖論聚類法、聚類預(yù)報法等。這里主要介紹常用的聚類算法：簡單聚類法、層次聚類法、動態(tài)聚類法、模糊聚類法。數(shù)據(jù)預(yù)處理

一般地，設(shè)某一分類問題共有n個樣本，m個特性指標(biāo)，則原始數(shù)據(jù)矩陣為由于m個特性指標(biāo)的量綱和數(shù)量級都不同，所以直接利用原始數(shù)據(jù)式（1）進(jìn)行聚類，就可能會突出那些數(shù)量級特別大的特性指標(biāo)對聚類的作用，而降低甚至排斥某些數(shù)量級較小的特性指標(biāo)對聚類的作用，從而導(dǎo)致一個指標(biāo)只要一改變度量單位就會完全改變聚類結(jié)果。為了克服這一缺點，必須先對原始數(shù)據(jù)矩陣進(jìn)行無量綱化處理，使每一指標(biāo)統(tǒng)一在某一共同的數(shù)據(jù)特性范圍內(nèi)。這個處理過程稱為數(shù)據(jù)標(biāo)準(zhǔn)化。目前較常用的數(shù)據(jù)標(biāo)準(zhǔn)化方法一般有6種。（1）數(shù)據(jù)預(yù)處理1、標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化是先將原始數(shù)據(jù)按列取平均，并計算各列的標(biāo)準(zhǔn)差。然后按下式計算標(biāo)準(zhǔn)化數(shù)據(jù)矩陣的元素數(shù)據(jù)預(yù)處理2、極大值標(biāo)準(zhǔn)化極大值標(biāo)準(zhǔn)化是將原始數(shù)據(jù)矩陣中的元素分別除以所在列的最大值，其商即為標(biāo)準(zhǔn)化數(shù)據(jù)矩陣的元素

數(shù)據(jù)預(yù)處理3、極差標(biāo)準(zhǔn)化極差標(biāo)準(zhǔn)化是將原始數(shù)據(jù)矩陣中的元素減去該列的極小值后除以該列最大值與最小值之差，其商即為標(biāo)準(zhǔn)化數(shù)據(jù)矩陣的元素

數(shù)據(jù)預(yù)處理4、均值標(biāo)準(zhǔn)化均值標(biāo)準(zhǔn)化是將原始數(shù)據(jù)矩陣中的元素除以所在列的平均值，其商即為標(biāo)準(zhǔn)化數(shù)據(jù)矩陣的元素數(shù)據(jù)預(yù)處理5、中心標(biāo)準(zhǔn)化中心標(biāo)準(zhǔn)化是將原始數(shù)據(jù)矩陣中的元素減去該列的的平均值，其商即為標(biāo)準(zhǔn)化數(shù)據(jù)矩陣的元素

6、對數(shù)標(biāo)準(zhǔn)化對數(shù)標(biāo)準(zhǔn)化是將原始數(shù)據(jù)矩陣中的元素取常用對數(shù)后作為標(biāo)準(zhǔn)化數(shù)據(jù)矩陣的元素

數(shù)據(jù)預(yù)處理

由上述標(biāo)準(zhǔn)化方法可知，中心標(biāo)準(zhǔn)化法（方法5）和對數(shù)標(biāo)準(zhǔn)化法（方法6）達(dá)不到無量綱目的。一個好的變換方法，應(yīng)在實現(xiàn)無量綱的同時，保持原有各指標(biāo)的分辨率，即變異性的大小?，F(xiàn)將方法1（標(biāo)準(zhǔn)差）、方法2（極大值）

、方法3（極差）和方法4（均值）變換后數(shù)據(jù)的特征列于表1。表1由表1知，方法1變換后，個指標(biāo)的均值和標(biāo)準(zhǔn)差完全相同，分辨率已被完全同化；方法3一般也縮小了各指標(biāo)之間的變異程度差異的作用，分辨率已被部分完全同化；方法2和方法4沒有改變原始數(shù)據(jù)的變異程度，但方法2易受個別極端值的影響。綜上，采用方法4也即均值標(biāo)準(zhǔn)化進(jìn)行原始數(shù)據(jù)標(biāo)準(zhǔn)化效果較好。數(shù)據(jù)預(yù)處理距離與相似系數(shù)為了將樣本進(jìn)行分類，就需要研究樣本之間關(guān)系。目前用得最多的方法有兩個：一種方法是將一個樣本看作m維空間的一個點，并在空間定義距離，距離越近的點歸為一類，距離較遠(yuǎn)的點歸為不同的類。另一種方法是用相似系數(shù)，性質(zhì)越接近的樣本，它們的相似系數(shù)的絕對值越接近1；而彼此無關(guān)的樣本，它們的相似系數(shù)的絕對值越接近于零。比較相似的樣本歸為一類，不怎么相似的樣本歸為不同的類。但相似系數(shù)和距離有各種各樣的定義，而這些定義與變量的類型關(guān)系極大，因此先介紹變量的類型。距離與相似系數(shù)由于實際問題中，遇到的指標(biāo)有的是定量的（如長度、重量等），有的是定性的（如性別、職業(yè)等），因此將變量（指標(biāo)）的類型按以下三種尺度劃分：間隔尺度：變量是用連續(xù)的量來表示的，如長度、重量、壓力、速度等等。在間隔尺度中，如果存在絕對零點，又稱比例尺度，這里并不嚴(yán)格區(qū)分比例尺度和間隔尺度。有序尺度：變量度量時沒有明確數(shù)量表示，而是劃分一些等級，等級之間有次序關(guān)系，如某產(chǎn)品分上、中、下三等，此三等有次序關(guān)系，但沒有數(shù)量表示。名義尺度：變量度量時沒有數(shù)量表示，也沒有次序關(guān)系，如某物體有紅、黃、白三種顏色，又如醫(yī)學(xué)化驗中的陰性與陽性，市場供求中的“產(chǎn)”和“銷”等。不同類型的變量，在定義距離和相似系數(shù)時，其方法有很大差異，使用時必須注意。研究比較多的是間隔尺度，因此這里主要給出間隔尺度的距離和相似系數(shù)的定義。距離與相似系數(shù)

設(shè)有n個樣本，每個樣本有m項指標(biāo)（變量），經(jīng)標(biāo)準(zhǔn)化處理的數(shù)據(jù)矩陣為其中為第i個樣本的第j個指標(biāo)的觀測數(shù)據(jù)。第i個樣本Xi為矩陣X的第i行所描述，所以任何兩個樣本XK與

XL之間的相似性，可以通過矩陣X中的第K行與第L行的相似程度來刻劃；任何兩個變量與之間的相似性，可以通過第K列與第L列的相似程度來刻劃。距離與相似系數(shù)1、對樣本分類常用的距離和相似系數(shù)定義距離與相似系數(shù)

明氏距離特別是其中的歐氏距離是人們較為熟悉的也是使用最多的距離。但明氏距離存在不足之處，主要表現(xiàn)在兩個方面：第一，它與各指標(biāo)的量綱有關(guān)；第二，它沒有考慮指標(biāo)之間的相關(guān)性，歐氏距離也不例外。除此之外，從統(tǒng)計的角度上看，使用歐氏距離要求一個向量的n個分量是不相關(guān)的且具有相同的方差，或者說各坐標(biāo)對歐氏距離的貢獻(xiàn)是同等的且變差大小也是相同的，這時使用歐氏距離才合適，效果也較好，否則就有可能不能如實反映情況，甚至導(dǎo)致錯誤結(jié)論。因此一個合理的做法，就是對坐標(biāo)加權(quán)，這就產(chǎn)生了“統(tǒng)計距離”。

距離與相似系數(shù)所加的權(quán)是，即用樣本方差除相應(yīng)坐標(biāo)。當(dāng)取時，就是點P到原點O的距離。若時，就是歐氏距離。

比如設(shè)，，且Q的坐標(biāo)是固定的，點P的坐標(biāo)相互獨立地變化。用s11,s12,…,smm表示m個變量的n次觀測的樣本方差，則可以義P到Q的統(tǒng)計距離為：距離與相似系數(shù)距離與相似系數(shù)

以上三種距離的定義是適用于間隔尺度變量的，如果變量是有序尺度或名義尺度時，也有一些定義距離的方法。距離與相似系數(shù)（2）相似系數(shù)研究樣本之間的關(guān)系，除了用距離表示外，還有相似系數(shù)，顧名思義，相似系數(shù)是描寫樣本相似程度的一個量，常用的相似系數(shù)有：i）夾角余弦這是受相似形的啟發(fā)而來的，下圖曲線AB和CD盡管長度不一，但形狀相似。當(dāng)長度不是主要矛盾時，要定義一種相似系數(shù)，使AB和CD呈現(xiàn)出比較密切的關(guān)系，則夾角余弦就適合這個要求。它的定義是：距離與相似系數(shù)距離與相似系數(shù)距離與相似系數(shù)2、對指標(biāo)分類常用的距離和相似系數(shù)定義距離與相似系數(shù)距離與相似系數(shù)算法分析-簡單聚類一、根據(jù)相似性閾值和最小距離原則的簡單聚類方法1、條件及約定設(shè)待分類的模式為，選定類內(nèi)距離閾值T。2、算法思想計算模式特征矢量到聚類中心的距離并和閾值比較而決定歸屬該類或作為新的一類中心。3、算法原理步驟⑴取任意的一個模式特征矢量作為第一個聚類中心。例如，令第一類⑵計算下一個模式特征矢量到的距離。若，則建立新的一類，其中心

算法分析-簡單聚類算法分析-層次聚類二、層次聚類效果較好、是常用方法之一1、條件及約定設(shè)待分類的模式特征矢量為，表示第k次合并時的第i類。2、基本思想首先將N個模式視作各自成為一類，然后計算類與類之間的距離，選擇距離最小的一對合并成一個新類，計算在新產(chǎn)生的類別分劃下各類之間的距離，再將距離最近的兩類合并，直至所有模式聚成兩類為止。

算法分析-層次聚類算法分析-層次聚類停止條件

以類間距離門限作為停止條件，即取距離門限，當(dāng)中最小陣元小于時，聚類過程停止；

以預(yù)定的類別數(shù)目作為停止條件，當(dāng)類別合并過程中，類數(shù)等于預(yù)定值時，聚類過程停止。類間距離的定義與遞推在該算法中所采用的類間距離定義不同，聚類過程及結(jié)果是不一樣的。上述算法在歸并的每次迭代過程中，距離矩陣的最小元素值不斷地改變，如果有單調(diào)不減關(guān)系則稱類間距離對并類具有單調(diào)性。最近距離法、最遠(yuǎn)距離法、平均法及離差平方和法等定義的類間距離都具有這個性質(zhì)，而重心法沒有這個性質(zhì)。算法分析-層次聚類算法特點聚類過程中類心不斷地調(diào)整，但某一模式一旦分劃到某一類中就不再改變。從粗到細(xì)的層次聚類這類技術(shù)的另一個算法和上述算法過程相反，依據(jù)類的離差平方和遞推公式按1類至N類進(jìn)行層次分解，這里不作介紹了。聚類過程可以表示成一個樹圖。算法分析-動態(tài)聚類

三、ISODATA(迭代自組織數(shù)據(jù)分析)算法特點：具有啟發(fā)性推理、分析監(jiān)督、控制聚類結(jié)構(gòu)及人機(jī)交互。

1、條件及約定設(shè)待分類的模式特征矢量為，算法運行前需設(shè)定7個初始參數(shù)。

2、算法思想在每輪迭代過程中，樣本重新調(diào)整類別之后計算類內(nèi)及類間有關(guān)參數(shù)，并和設(shè)定的門限比較，確定是兩類合并為一類還是一類分裂為兩類，不斷地“自組織”，以達(dá)到在各參數(shù)滿足設(shè)計要求條件下，使各模式到其類心的距離平方和最小。算法分析-動態(tài)聚類算法分析-動態(tài)聚類算法分析-動態(tài)聚類算法分析-動態(tài)聚類算法分析-動態(tài)聚類算法分析-動態(tài)聚類算法分析-動態(tài)聚類算法分析-動態(tài)聚類算法分析-模糊聚類四、模糊ISODATA算法是較常用的模糊聚類方法算法分析-模糊聚類算法分析-模糊聚類算法分析-模糊聚類分類標(biāo)準(zhǔn)的確定

為了能判斷分類數(shù)的恰當(dāng)與否和分類的結(jié)果是好還是不好，在此定義類間分辨率。對某一個聚類中心，它與其它聚類中心的距離的最小值是；在屬于該聚類中心的所有原始數(shù)據(jù)中，每個原始數(shù)據(jù)與該聚類中心都有一個距離，這個距離中最大的距離記為，這個距離的平均值記為。則類間分辨率的好壞由如下兩個公式的值來判斷：算法分析-模糊聚類如果數(shù)據(jù)分布的較為合理，則每個聚類中心周圍都匯聚集著一定數(shù)量的原始數(shù)據(jù)，且應(yīng)該小于,即應(yīng)該大于1；同時也要比小，越大，則說明那些屬于某一類的數(shù)據(jù)點越接近聚類中心。當(dāng)分類數(shù)從小變大時，也會從小變大，直到達(dá)到一個極大值，也就是此時的分類效果最好。然后由于受分類數(shù)C的