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

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

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

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

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

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

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

試探法

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

聚類準則函數(shù)法

聚類就是將樣本進行組合分類以使類別可分性為最大，因此聚類準則應是反映類別間相似性（或可分性）的函數(shù)；同時，類別又由一個個樣本組成，因此類別的可分性與樣本間的差異性直接相關(guān)?；诖?，聚類準則函數(shù)J，應是模式樣本集{x}和模式類別{Sj,j=1,2,…,c}的函數(shù)，即J代表了分屬于c個聚類類別的全部模式樣本與其對應類別模式均值之間的誤差平方和；對于不同的聚類形式，J值是不同的，聚類的目的是：使J值達到極?。挥纱丝梢姡壕垲惙治鲛D(zhuǎn)化為尋找準則函數(shù)極值的最優(yōu)化問題；此種聚類方法通常稱為最小方差劃分，適用于各類樣本密集且數(shù)目相差不多，而不同類間的樣本又明顯分開的情況（圖例解釋）—把握類內(nèi)距離與類間距離的問題；聚類準則函數(shù)有許多其他形式?！?.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é)果。在實際中，對于高維模式樣本很難獲得準確的先驗知識，因此只能選用不同的閾值和起始點來試探，并對結(jié)果進行驗證。這種方法在很大程度上依賴于以下因素：第一個聚類中心的位置（初始化問題）待分類模式樣本排列次序（聚類樣本的選擇問題）距離閾值T的大?。ㄅ袥Q準則問題）樣本分布的幾何性質(zhì)（樣本的固有特性問題）二、最大最小距離算法基本思想：根據(jù)實際問題選擇距離函數(shù)，以試探類間距離為最大作為預選出聚類中心的條件。核心就是：最大類間距離，最小類內(nèi)距離。算法過程描述：先按照距離最大最小的方法預選出聚類中心，在按照按最鄰近規(guī)則將模式分類到聚類中心。對于N個待分類的模式樣本，要求按最大最小距離法分類到聚類中心。Step1：選任意一模式樣本xi作為第一聚類中心z1Step2：選離z1最遠距離的樣本xj作為第二聚類中心z2Step3：逐個計算各模式樣本與之間的距離，并選出其中的最小距離。Step4：在所有模式樣本的最小值中選出最大距離，若該最大值達到的一定分數(shù)比值以上，則將相應的樣本取為第三聚類中心。Stepi：………算法性能分析：算法復雜度增加，在選聚類中心過程中消耗較大的資源?！?.4系統(tǒng)聚類系統(tǒng)聚類：先把每個樣本作為一類，然后根據(jù)它們間的相似性或相鄰性聚合，類別由多到少，直到獲得合適的分類要求為止；相似性、相鄰性用距離表示。聚合的關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計算，不同的距離函數(shù)會得到不同結(jié)果。兩類間距離計算準則：(注意理解）1.最短距離：兩類中相距最近的兩樣本間的距離

2.最長距離：兩類中相距最遠的兩個樣本間的距離。

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

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

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

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

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