模式識別第二章

第二章聚類分析整理ppt第二章聚類分析2.1聚類分析的相關(guān)概念2.2模式相似性的測度和聚類準(zhǔn)則2.3基于試探的聚類搜索算法2.4系統(tǒng)聚類法2.5動態(tài)聚類法2.6聚類結(jié)果的評價整理ppt2.1聚類分析的相關(guān)概念定義 對一批沒有標(biāo)出類別的模式樣本集，按照樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，這種分類稱為聚類分析，也稱為無監(jiān)督分類。整理ppt2.1聚類分析的相關(guān)概念模式相似/分類的依據(jù) 把整個模式樣本集的特征向量看成是分布在特征空間中的一些點，點與點之間的距離即可作為模式相似性的測量依據(jù)。

聚類分析是按不同對象之間的差異，根據(jù)距離函數(shù)的規(guī)律（大?。┻M(jìn)行模式分類的。整理ppt2.1聚類分析的相關(guān)概念聚類分析的有效性

聚類分析方法是否有效，與模式特征向量的分布形式有很大關(guān)系。若向量點的分布是一群一群的，同一群樣本密集（距離很近），不同群樣本距離很遠(yuǎn)，則很容易聚類；若樣本集的向量分布聚成一團(tuán)，不同群的樣本混在一起，則很難分類；對具體對象做聚類分析的關(guān)鍵是選取合適的特征。特征選取得好，向量分布容易區(qū)分，選取得不好，向量分布很難分開。整理ppt2.1聚類分析的相關(guān)概念兩類模式分類的實例：一攤黑白圍棋子選顏色作為特征進(jìn)行分類，用“1”代表白，“0”代表黑，則很容易分類；選大小作為特征進(jìn)行分類，則白子和黑子的特征相同，不能分類（把白子和黑子分開）。整理ppt2.1聚類分析的相關(guān)概念特征選擇的維數(shù)

在特征選擇中往往會選擇一些多余的特征，它增加了維數(shù)，從而增加了聚類分析的復(fù)雜度，但對模式分類卻沒有提供多少有用的信息。在這種情況下，需要去掉相關(guān)程度過高的特征（進(jìn)行降維處理）。降維方法結(jié)論：若rij->1，則表明第i維特征與第j維特征所反映的特征規(guī)律接近，因此可以略去其中的一個特征，或?qū)⑺鼈兒喜橐粋€特征，從而使維數(shù)降低一維。整理ppt2.1聚類分析的相關(guān)概念模式對象特征測量的數(shù)字化 計算機(jī)只能處理離散的數(shù)值，因此根據(jù)識別對象的不同，要進(jìn)行不同的數(shù)據(jù)化處理。連續(xù)量的量化：用連續(xù)量來度量的特性，如長度、重量、面積等等，僅需取其量化值；量級的數(shù)量化：度量時不需要詳盡的數(shù)值，而是相應(yīng)地劃分成一些有次序的量化等級的值。病人的病程名義尺度：指定性的指標(biāo)，即特征度量時沒有數(shù)量關(guān)系，也沒有明顯的次序關(guān)系，如黑色和白色的關(guān)系，男性和女性的關(guān)系等，都可將它們分別用“0”和“1”來表示。超過2個狀態(tài)時，可用多個數(shù)值表示。整理ppt2.2模式相似性的測度和聚類準(zhǔn)則2.2.1相似性測度目的：為了能將模式集劃分成不同的類別，必須定義一種相似性的測度，來度量同一類樣本間的類似性和不屬于同一類樣本間的差異性。歐氏距離量綱對分類的影響（下頁圖例）馬氏距離特點：排除了模式樣本之間的相關(guān)性問題：協(xié)方差矩陣在實際應(yīng)用中難以計算一般化的明氏距離角度相似性函數(shù)特點：反映了幾何上相似形的特征，對于坐標(biāo)系的旋轉(zhuǎn)、放大和縮小等變化是不變的。當(dāng)特征的取值僅為(0,1)兩個值時的特例整理ppt量綱對分類的影響（圖例）整理ppt2.2模式相似性的測度和聚類準(zhǔn)則2.2.2聚類準(zhǔn)則 有了模式的相似性測度，還需要一種基于數(shù)值的聚類準(zhǔn)則，能將相似的模式樣本分在同一類，相異的模式樣本分在不同的類。試探方法聚類準(zhǔn)則函數(shù)法整理ppt2.2模式相似性的測度和聚類準(zhǔn)則2.2.2聚類準(zhǔn)則試探方法 憑直觀感覺或經(jīng)驗，針對實際問題定義一種相似性測度的閾值，然后按最近鄰規(guī)則指定某些模式樣本屬于某一個聚類類別。例如對歐氏距離，它反映了樣本間的近鄰性，但將一個樣本分到不同類別中的哪一個時，還必須規(guī)定一個距離測度的閾值作為聚類的判別準(zhǔn)則。整理ppt2.2模式相似性的測度和聚類準(zhǔn)則2.2.2聚類準(zhǔn)則聚類準(zhǔn)則函數(shù)法依據(jù)：由于聚類是將樣本進(jìn)行分類以使類別間可分離性為最大，因此聚類準(zhǔn)則應(yīng)是反映類別間相似性或分離性的函數(shù)；由于類別是由一個個樣本組成的，因此一般來說類別的可分離性和樣本的可分離性是直接相關(guān)的；可以定義聚類準(zhǔn)則函數(shù)為模式樣本集{x}和模式類別{Sj,j=1,2,…,c}的函數(shù)，從而使聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問題。整理ppt2.2模式相似性的測度和聚類準(zhǔn)則2.2.2聚類準(zhǔn)則聚類準(zhǔn)則函數(shù)法一種聚類準(zhǔn)則函數(shù)J的定義J代表了屬于c個聚類類別的全部模式樣本與其相應(yīng)類別模式均值之間的誤差平方和。對于不同的聚類形式，J值是不同的。目的：求取使J值達(dá)到最小的聚類形式。整理ppt2.3基于試探的聚類搜索算法2.3.1按最近鄰規(guī)則的簡單試探法算法討論這種方法的優(yōu)點：計算簡單，若模式樣本的集合分布的先驗知識已知，則可通過選取正確的閾值和起始點，以及確定樣本的選取次序等獲得較好的聚類結(jié)果。整理ppt2.3基于試探的聚類搜索算法2.3.1按最近鄰規(guī)則的簡單試探法討論（續(xù)）在實際中，對于高維模式樣本很難獲得準(zhǔn)確的先驗知識，因此只能選用不同的閾值和起始點來試探，所以這種方法在很大程度上依賴于以下因素：第一個聚類中心的位置待分類模式樣本的排列次序距離閾值T的大小樣本分布的幾何性質(zhì)整理ppt2.3基于試探的聚類搜索算法2.3.1按最近鄰規(guī)則的簡單試探法討論（續(xù)）距離閾值T對聚類結(jié)果的影響整理ppt2.3基于試探的聚類搜索算法2.3.2最大最小距離算法基本思想：以試探類間歐氏距離為最大作為預(yù)選出聚類中心的條件。整理ppt2.3基于試探的聚類搜索算法2.3.2最大最小距離算法算法（實例）整理ppt2.4系統(tǒng)聚類法基本思想 將模式樣本按距離準(zhǔn)則逐步分類，類別由多到少，直到獲得合適的分類要求為止。算法整理ppt2.4系統(tǒng)聚類法距離準(zhǔn)則函數(shù) 進(jìn)行聚類合并的一個關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計算，采用不同的距離函數(shù)會得到不同的計算結(jié)果。主要的距離計算準(zhǔn)則：最短距離法最長距離法中間距離法重心法類平均距離法整理ppt2.4系統(tǒng)聚類法[舉例]設(shè)有6個五維模式樣本如下，按最小距離準(zhǔn)則進(jìn)行聚類分析：x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0整理ppt2.4系統(tǒng)聚類法[舉例]系統(tǒng)聚類的 樹狀表示整理ppt作業(yè)畫出給定迭代次數(shù)為n的系統(tǒng)聚類法的算法流程框圖對如下5個6維模式樣本，用最小聚類準(zhǔn)則進(jìn)行系統(tǒng)聚類分析： x1:0,1,3,1,3,4 x2:3,3,3,1,2,1 x3:1,0,0,0,1,1 x4:2,1,0,2,2,1 x5:0,0,1,0,1,0整理ppt2.4系統(tǒng)聚類法練習(xí)對如下6個五維模式樣本，按最大距離準(zhǔn)則進(jìn)行聚類分析（直到分成三個類別為止）：x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0整理ppt2.5動態(tài)聚類法基本思想首先選擇若干個樣本點作為聚類中心，再按某種聚類準(zhǔn)則（通常采用最小距離準(zhǔn)則）使樣本點向各中心聚集，從而得到初始聚類；然后判斷初始分類是否合理，若不合理，則修改分類；如此反復(fù)進(jìn)行修改聚類的迭代算法，直至合理為止。K-均值算法ISODATA算法（迭代自組織數(shù)據(jù)分析算法）整理ppt2.5.1K-均值算法思想：基于使聚類性能指標(biāo)最小化，所用的聚類準(zhǔn)則函數(shù)是聚類集中每一個樣本點到該類中心的距離平方之和，并使其最小化。算法整理ppt2.5.1K-均值算法[舉例]對如圖模式 樣本用K-均 值算法進(jìn)行 分類整理ppt2.5.1K-均值算法討論 K-均值算法的結(jié)果受如下選擇的影響：所選聚類的數(shù)目聚類中心的初始分布模式樣本的幾何性質(zhì)讀入次序在實際應(yīng)用中，需要試探不同的K值和選擇不同的聚類中心的起始值。如果模式樣本可以形成若干個相距較遠(yuǎn)的孤立的區(qū)域分布，一般都能得到較好的收斂效果。K-均值算法比較適合于分類數(shù)目已知的情況。整理ppt2.5.1K-均值算法作業(yè)/練習(xí)（選k=2, z1(1)=x1, z2(1)=x10, 用K-均值算法 進(jìn)行聚類分析）整理ppt計算機(jī)編程編寫K-均值聚類算法程序，對下圖所示數(shù)據(jù)進(jìn)行聚類分析(選k=2)：整理ppt2.5.2ISODATA算法與K-均值算法的比較K-均值算法通常適合于分類數(shù)目已知的聚類，而ISODATA算法則更加靈活；從算法角度看，ISODATA算法與K-均值算法相似，聚類中心都是通過樣本均值的迭代運算來決定的；ISODATA算法加入了一些試探步驟，并且可以結(jié)合成人機(jī)交互的結(jié)構(gòu)，使其能利用中間結(jié)果所取得的經(jīng)驗更好地進(jìn)行分類。整理ppt2.5.2ISODATA算法基本步驟和思路（1） 選擇某些初始值?？蛇x不同的參數(shù)指標(biāo)，也可在迭代過程中人為修改，以將N個模式樣本按指標(biāo)分配到各個聚類中心中去。（2） 計算各類中諸樣本的距離指標(biāo)函數(shù)。（3）~（5）按給定的要求，將前一次獲得的聚類集進(jìn)行分裂和合并處理（（4）為分裂處理，（5）為合并處理），從而獲得新的聚類中心。（6） 重新進(jìn)行迭代運算，計算各項指標(biāo)，判斷聚類結(jié)果是否符合要求。經(jīng)過多次迭代后，若結(jié)果收斂，則運算結(jié)束。整理ppt2.5.2ISODATA算法算法[舉例]對如圖模 式樣本用 ISODATA 算法進(jìn)行 分類整理ppt2.6聚類結(jié)果的評價迅速評價聚類結(jié)果，在上述迭代運算中是很重要的，特別是具有高維特征向量的模式，不能直接看清聚類效果，因此，可考慮用以下幾個指標(biāo)來評價聚類效果：聚類中心之間的距離距離值大，通?？煽紤]分為不同類聚類域中的樣本數(shù)目樣本數(shù)目少且聚類中心距離遠(yuǎn)，可考慮是否為噪聲聚類域內(nèi)樣本的距離方差方差過大的樣本可考慮是否屬于這一類討論：模式聚類目前還沒有一種通用的放之四海而皆準(zhǔn)的準(zhǔn)則，往往需要根據(jù)實際應(yīng)用來選擇合適的方法。整理ppt作業(yè)畫出ISODATA算法的流程框圖試用ISODATA算法對如下模式分布進(jìn)行聚類分析： {x1(0,0),x2(3,8),x3(2,2),x4(1,1),