模式識別-1-非監(jiān)督學(xué)習(xí)方法：聚類分析 (邊肇祺 第二版)

第一章非監(jiān)督學(xué)習(xí)方法：聚類分析基本概念相似性測度與聚類準(zhǔn)則基于試探的聚類搜索算法系統(tǒng)聚類分解聚類動態(tài)聚類§1.1基本概念分類與聚類的區(qū)別分類：用已知類別的樣本訓(xùn)練集來設(shè)計分類器（監(jiān)督學(xué)習(xí)）聚類（集群）：用事先不知樣本的類別，而利用樣本的先驗知識來構(gòu)造分類器（無監(jiān)督學(xué)習(xí)）舉例：小孩區(qū)分桔子和蘋果相似性與距離聚類相似性：模式之間具有一定的相似性，這既表現(xiàn)在實物的顯著特征上，也表現(xiàn)在經(jīng)過抽象以后特征空間內(nèi)的特征向量的分布狀態(tài)上。聚類分析定義：對一批沒有標(biāo)出類別的模式樣本集，按照樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，這種分類稱為聚類分析，也稱為無監(jiān)督分類。分類依據(jù)：一個樣本的特征向量相當(dāng)于特征空間中的一點，整個模式樣本集合的特征向量可以看成特征空間的一些點，點之間的距離函數(shù)可以作為模式相似性的度量，并以此作為模式的分類依據(jù)。聚類分析是按不同對象之間的差異，根據(jù)距離函數(shù)的規(guī)律進(jìn)行模式分類的。距離函數(shù)的定義特征向量的特性

聚類分析的有效性：聚類分析方法是否有效，與模式特征向量的分布形式有很大關(guān)系。若向量點的分布是一群一群的，同一群樣本密集（距離很近），不同群樣本距離很遠(yuǎn)，則很容易聚類；若樣本集的向量分布聚成一團(tuán)，不同群的樣本混在一起，則很難分類；對具體對象做聚類分析的關(guān)鍵是選取合適的特征。特征選取得好，向量分布容易區(qū)分，選取得不好，向量分布很難分開。特征空間維數(shù)特征信息的冗余性：在對象分析和特征提取中，往往會提取一些多余的特征，以期增加對象識別的信息量。高維特征空間分析的復(fù)雜性：特征空間維數(shù)越高，聚類分析的復(fù)雜性就越高高維特征空間降維降維方法：相關(guān)分析：特征向量的相關(guān)矩陣R，分析相關(guān)性主成分分析：以正交變換為理論基礎(chǔ)獨立成分分析：以獨立性為基礎(chǔ)特征的表示數(shù)值表示：對于實際問題，為了便于計算機分析和計算，特征必須進(jìn)行量化。對不同的分析對象，量化方法是不一樣的。連續(xù)量的量化：用連續(xù)量來度量的特征，只需取其量化值，如長度、重量等。分級量的量化：度量分析對象等級的量，用有序的離散數(shù)字進(jìn)行量化，比如學(xué)生成績的優(yōu)，良，中，差可用1，2，3，4等量化表示。定性量的量化：定性指標(biāo)，沒有數(shù)量關(guān)系，也沒有次序要求。比如，性別特征：男和女，可用0和1來進(jìn)行表示。兩類模式分類的實例區(qū)分一攤黑白圍棋子選顏色作為特征進(jìn)行分類，用“1”代表白，“0”代表黑，則很容易分類；選大小作為特征進(jìn)行分類，則白子和黑子的特征相同，不能分類?！?.2相似性測度和聚類準(zhǔn)則

一、相似性的測度歐氏距離:

表征兩個模式樣本在特征空間中的Euclid距離，模式X和Z間的距離愈小，則愈相似注意：X和Z的量綱必須一致

消除量綱不一致對聚類的影響：特征數(shù)據(jù)的正則化（也稱標(biāo)準(zhǔn)化、歸一化），使特征變量與量綱無關(guān)。馬氏距離：表征模式向量X與其均值向量m之間的距離平方，C是模式總體的協(xié)方差矩陣，引入?yún)f(xié)方差矩陣，排除了樣本之間的相關(guān)性。歐式距離中，如果特征向量中某一分量的值非常大，那么就會掩蓋值小的項所起到的作用，這是歐式距離的不足；當(dāng)采用馬氏距離，就可以屏蔽這一點。因為相關(guān)性強的一個分量，對應(yīng)于協(xié)方差矩陣C中對角線上的那一項的值就會大一些。再將這一項取倒數(shù)，減小該影響。當(dāng)協(xié)方差為對角矩陣時，各特征分量相互獨立；當(dāng)協(xié)方差為單位矩陣時，馬氏距離和歐氏距離相同。其中分別是樣本向量的第k個分量；當(dāng)m＝2時，明氏距離就是歐氏距離；當(dāng)m＝1時，就是街坊（cityblock)距離：

一般化的明氏距離角度相似性函數(shù)：表征了模式向量x和z之間夾角的余弦，反映了幾何上的相似性，當(dāng)坐標(biāo)系旋轉(zhuǎn)或者尺度變換，夾角余弦測度均保持不變（對位移和線性變換不成立）如果x和z的分量用二值來表示，0表示不具有某種特征，1表示具有某種特征，則夾角余弦測度表示x和z具有共有特征數(shù)目的相似性測度。二、聚類準(zhǔn)則的確定

試探法

憑直觀和經(jīng)驗，針對實際問題選擇相似性測度并確定此相似性測度的閾值，然后選擇一定的訓(xùn)練樣本來檢驗測度和閾值的可靠程度，最后按最近鄰規(guī)則指定某些模式樣本屬于某一個聚類類別。舉例：對于歐氏距離，它反映了樣本間的近鄰性，但將一個樣本分到不同類別時，還必須規(guī)定一距離測度的閾值準(zhǔn)則作為聚類的判別準(zhǔn)則

聚類準(zhǔn)則函數(shù)法

聚類就是將樣本進(jìn)行組合分類以使類別可分性為最大，因此聚類準(zhǔn)則應(yīng)是反映類別間相似性（或可分性）的函數(shù)；同時，類別又由一個個樣本組成，因此類別的可分性與樣本間的差異性直接相關(guān)?；诖耍垲悳?zhǔn)則函數(shù)J，應(yīng)是模式樣本集{x}和模式類別{Sj,j=1,2,…,c}的函數(shù)，即J代表了分屬于c個聚類類別的全部模式樣本與其對應(yīng)類別模式均值之間的誤差平方和；對于不同的聚類形式，J值是不同的，聚類的目的是：使J值達(dá)到極小；由此可見：聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問題；此種聚類方法通常稱為最小方差劃分，適用于各類樣本密集且數(shù)目相差不多，而不同類間的樣本又明顯分開的情況（圖例解釋）—把握類內(nèi)距離與類間距離的問題；聚類準(zhǔn)則函數(shù)有許多其他形式。§1.3基于試探的聚類搜索算法一、按最鄰近規(guī)則的簡單試探法

給N個待分類的模式樣本，要求按距離閾值T分類到聚類中心算法過程：Step1：取任意的樣本xi作為一聚類中的初始值，如令z1=x1，計算若D21＞T，確定一新的聚類中心z2=x2否則x2∈以z1為中心的聚類；Step2：假如已有聚類中心z1和z2，計算若D31＞T和D32＞T，則確定一新的聚類中心z3=x3；Stepi：………討論這種方法的優(yōu)點：計算簡單，若模式樣本的集合分布的先驗知識已知，則可獲得較好的聚類結(jié)果。在實際中，對于高維模式樣本很難獲得準(zhǔn)確的先驗知識，因此只能選用不同的閾值和起始點來試探，并對結(jié)果進(jìn)行驗證。這種方法在很大程度上依賴于以下因素：第一個聚類中心的位置（初始化問題）待分類模式樣本排列次序（聚類樣本的選擇問題）距離閾值T的大?。ㄅ袥Q準(zhǔn)則問題）樣本分布的幾何性質(zhì)（樣本的固有特性問題）二、最大最小距離算法基本思想：根據(jù)實際問題選擇距離函數(shù)，以試探類間距離為最大作為預(yù)選出聚類中心的條件。核心就是：最大類間距離，最小類內(nèi)距離。算法過程描述：先按照距離最大最小的方法預(yù)選出聚類中心，在按照按最鄰近規(guī)則將模式分類到聚類中心。對于N個待分類的模式樣本，要求按最大最小距離法分類到聚類中心。Step1：選任意一模式樣本xi作為第一聚類中心z1Step2：選離z1最遠(yuǎn)距離的樣本xj作為第二聚類中心z2Step3：逐個計算各模式樣本與之間的距離，并選出其中的最小距離。Step4：在所有模式樣本的最小值中選出最大距離，若該最大值達(dá)到的一定分?jǐn)?shù)比值以上，則將相應(yīng)的樣本取為第三聚類中心。Stepi：………算法性能分析：算法復(fù)雜度增加，在選聚類中心過程中消耗較大的資源。§1.4系統(tǒng)聚類系統(tǒng)聚類：先把每個樣本作為一類，然后根據(jù)它們間的相似性或相鄰性聚合，類別由多到少，直到獲得合適的分類要求為止；相似性、相鄰性用距離表示。聚合的關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計算，不同的距離函數(shù)會得到不同結(jié)果。兩類間距離計算準(zhǔn)則：(注意理解）1.最短距離：兩類中相距最近的兩樣本間的距離

2.最長距離：兩類中相距最遠(yuǎn)的兩個樣本間的距離。

3.中間距離：最短距離和最長距離都有片面性，因此有時用中間距離。設(shè)ω1類和ω23類間的最短距離為d12，最長距離為d13，ω

23類的長度為d23，則中間距離為：上式推廣為一般情況：4.重心距離：均值間的距離5.類平均距離：兩類中各個元素兩兩之間的距離平方相加后取平均值6.離差平方和：設(shè)N個樣本原分q類，則定義第i類的離差平方和為：離差平方和增量：設(shè)樣本已分成ωp,ωq兩類，若把ωp,ωq合為ωr類，則定義離差平方增量：算法過程描述：

Step1：初始距離矩陣的計算D(0)說明：（1）距離矩陣元素的值是類與類之間的距離，距離的定義有多種。（2）距離矩陣，是對稱矩陣。對角上線的元值表示同類之間的距離，即為0。Step2：對于第n次迭代的距離矩陣D(n)進(jìn)行聚合

說明：距離矩陣中選擇距離最小的，如果有相同的可以任選其中一個，要忽略對角線上的元素；也可以把相同的全部聚合。Step3：根據(jù)第n次聚合結(jié)果，計算合并后的新類別之間的距離矩陣D(n+1)

說明：合并類的距離計算應(yīng)該符合距離的運算規(guī)則。若距離反映的是兩類的重心距離，那么合并后，應(yīng)該仍然反映的重心的距離。Step4：收斂性判決（距離閾值D的設(shè)定）說明：算法的收斂條件判斷準(zhǔn)則的確定。例1：如下圖所示（簡單的一維情況）1、設(shè)全部樣本分為6類，2、計算距離矩陣D(0)Ω1Ω2Ω3Ω4Ω5Ω6Ω10Ω290Ω31160Ω44916640Ω52543640Ω66425811903、求最小元素：4、把Ω1,Ω3合并Ω7=(1,3)Ω4,Ω6合并Ω8=(4,6)5、作距離矩陣D(1)，按最小距離準(zhǔn)則Ω7Ω2Ω8Ω5Ω70Ω290Ω849160Ω5254406、若合并的類數(shù)沒有達(dá)到要求，轉(zhuǎn)3。否則停止。3、求最小元素：4、Ω8,Ω5,Ω2合并,ω9=（2,5,4,6）§1.5分解聚類分解聚類：把全部樣本作為一類，然后根據(jù)相似性、相鄰性分解。目標(biāo)函數(shù)為：兩類均值方差N：總樣本數(shù)，：ω1類樣本數(shù)：ω2類樣本數(shù)，分解聚類框圖初始分類調(diào)整分類方案最終結(jié)果目標(biāo)函數(shù)達(dá)到最優(yōu)？例2：已知21個樣本，每個樣本取二個特征，原始資料矩陣如下表：樣本號12345678910