中科院模式識(shí)別第二章黃慶明

1、第二章 聚類分析第二章 聚類分析2.1 聚類分析的相關(guān)概念2.2 模式相似性的測(cè)度和聚類準(zhǔn)則2.3 基于試探的聚類搜索算法2.4 系統(tǒng)聚類法2.5 動(dòng)態(tài)聚類法2.6 聚類結(jié)果的評(píng)價(jià)2.1 聚類分析的相關(guān)概念 定義對(duì)一批沒(méi)有標(biāo)出類別的模式樣本集，按照樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，這種分類稱為聚類分析，也稱為無(wú)監(jiān)督分類。2.1 聚類分析的相關(guān)概念 模式相似/分類的依據(jù)把整個(gè)模式樣本集的特征向量看成是分布在特征空間中的一些點(diǎn)，點(diǎn)與點(diǎn)之間的距離即可作為模式相似性的測(cè)量依據(jù)。聚類分析是按不同對(duì)象之間的差異，根據(jù)距離函數(shù)的規(guī)律（大?。┻M(jìn)行模式分類的。2.1 聚類分析的相關(guān)概念

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

3、數(shù)在特征選擇中往往會(huì)選擇一些多余的特征，它增加了維數(shù)，從而增加了聚類分析的復(fù)雜度，但對(duì)模式分類卻沒(méi)有提供多少有用的信息。在這種情況下，需要去掉相關(guān)程度過(guò)高的特征（進(jìn)行降維處理）。 降維方法 結(jié)論：若rij-1，則表明第i維特征與第j維特征所反映的特征規(guī)律接近，因此可以略去其中的一個(gè)特征，或?qū)⑺鼈兒喜橐粋€(gè)特征，從而使維數(shù)降低一維。2.1 聚類分析的相關(guān)概念 模式對(duì)象特征測(cè)量的數(shù)字化計(jì)算機(jī)只能處理離散的數(shù)值，因此根據(jù)識(shí)別對(duì)象的不同，要進(jìn)行不同的數(shù)據(jù)化處理。 連續(xù)量的量化：用連續(xù)量來(lái)度量的特性，如長(zhǎng)度、重量、面積等等，僅需取其量化值； 量級(jí)的數(shù)量化：度量時(shí)不需要詳盡的數(shù)值，而是相應(yīng)地劃分成一些有次

4、序的量化等級(jí)的值。 病人的病程 名義尺度：指定性的指標(biāo)，即特征度量時(shí)沒(méi)有數(shù)量關(guān)系，也沒(méi)有明顯的次序關(guān)系，如黑色和白色的關(guān)系，男性和女性的關(guān)系等，都可將它們分別用“0”和“1”來(lái)表示。 超過(guò)2個(gè)狀態(tài)時(shí)，可用多個(gè)數(shù)值表示。2.2 模式相似性的測(cè)度和聚類準(zhǔn)則2.2.1 相似性測(cè)度 目的：為了能將模式集劃分成不同的類別，必須定義一種相似性的測(cè)度，來(lái)度量同一類樣本間的類似性和不屬于同一類樣本間的差異性。 歐氏距離 量綱對(duì)分類的影響（下頁(yè)圖例） 馬氏距離 特點(diǎn)：排除了模式樣本之間的相關(guān)性 問(wèn)題：協(xié)方差矩陣在實(shí)際應(yīng)用中難以計(jì)算 一般化的明氏距離 角度相似性函數(shù) 特點(diǎn)：反映了幾何上相似形的特征，對(duì)于坐標(biāo)系的旋

5、轉(zhuǎn)、放大和縮小等變化是不變的。 當(dāng)特征的取值僅為(0,1)兩個(gè)值時(shí)的特例量綱對(duì)分類的影響（圖例）2.2 模式相似性的測(cè)度和聚類準(zhǔn)則2.2.2 聚類準(zhǔn)則有了模式的相似性測(cè)度，還需要一種基于數(shù)值的聚類準(zhǔn)則，能將相似的模式樣本分在同一類，相異的模式樣本分在不同的類。 試探方法 聚類準(zhǔn)則函數(shù)法2.2 模式相似性的測(cè)度和聚類準(zhǔn)則2.2.2 聚類準(zhǔn)則 試探方法憑直觀感覺(jué)或經(jīng)驗(yàn)，針對(duì)實(shí)際問(wèn)題定義一種相似性測(cè)度的閾值，然后按最近鄰規(guī)則指定某些模式樣本屬于某一個(gè)聚類類別。 例如對(duì)歐氏距離，它反映了樣本間的近鄰性，但將一個(gè)樣本分到不同類別中的哪一個(gè)時(shí)，還必須規(guī)定一個(gè)距離測(cè)度的閾值作為聚類的判別準(zhǔn)則。2.2 模式相

6、似性的測(cè)度和聚類準(zhǔn)則2.2.2 聚類準(zhǔn)則 聚類準(zhǔn)則函數(shù)法 依據(jù)：由于聚類是將樣本進(jìn)行分類以使類別間可分離性為最大，因此聚類準(zhǔn)則應(yīng)是反映類別間相似性或分離性的函數(shù)； 由于類別是由一個(gè)個(gè)樣本組成的，因此一般來(lái)說(shuō)類別的可分離性和樣本的可分離性是直接相關(guān)的； 可以定義聚類準(zhǔn)則函數(shù)為模式樣本集x和模式類別Sj, j=1,2,c的函數(shù)，從而使聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問(wèn)題。2.2 模式相似性的測(cè)度和聚類準(zhǔn)則2.2.2 聚類準(zhǔn)則 聚類準(zhǔn)則函數(shù)法 一種聚類準(zhǔn)則函數(shù)J的定義 J代表了屬于c個(gè)聚類類別的全部模式樣本與其相應(yīng)類別模式均值之間的誤差平方和。 對(duì)于不同的聚類形式，J值是不同的。 目的：求取使

7、J值達(dá)到最小的聚類形式。2.3 基于試探的聚類搜索算法2.3.1 按最近鄰規(guī)則的簡(jiǎn)單試探法 算法 討論 這種方法的優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單，若模式樣本的集合分布的先驗(yàn)知識(shí)已知，則可通過(guò)選取正確的閾值和起始點(diǎn)，以及確定樣本的選取次序等獲得較好的聚類結(jié)果。2.3 基于試探的聚類搜索算法2.3.1 按最近鄰規(guī)則的簡(jiǎn)單試探法 討論（續(xù)） 在實(shí)際中，對(duì)于高維模式樣本很難獲得準(zhǔn)確的先驗(yàn)知識(shí)，因此只能選用不同的閾值和起始點(diǎn)來(lái)試探，所以這種方法在很大程度上依賴于以下因素： 第一個(gè)聚類中心的位置 待分類模式樣本的排列次序 距離閾值T的大小 樣本分布的幾何性質(zhì)2.3 基于試探的聚類搜索算法2.3.1 按最近鄰規(guī)則的簡(jiǎn)單試探

8、法 討論（續(xù)） 距離閾值T對(duì)聚類結(jié)果的影響2.3 基于試探的聚類搜索算法2.3.2 最大最小距離算法 基本思想：以試探類間歐氏距離為最大作為預(yù)選出聚類中心的條件。2.3 基于試探的聚類搜索算法2.3.2 最大最小距離算法 算法（實(shí)例）2.4 系統(tǒng)聚類法基本思想將模式樣本按距離準(zhǔn)則逐步分類，類別由多到少，直到獲得合適的分類要求為止。算法2.4 系統(tǒng)聚類法距離準(zhǔn)則函數(shù)進(jìn)行聚類合并的一個(gè)關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計(jì)算，采用不同的距離函數(shù)會(huì)得到不同的計(jì)算結(jié)果。主要的距離計(jì)算準(zhǔn)則：最短距離法最長(zhǎng)距離法中間距離法重心法類平均距離法2.4 系統(tǒng)聚類法 舉例 設(shè)有6個(gè)五維模式樣本

9、如下，按最小距離準(zhǔn)則進(jìn)行聚類分析：x1: 0, 3, 1, 2, 0 x2: 1, 3, 0, 1, 0 x3: 3, 3, 0, 0, 1x4: 1, 1, 0, 2, 0 x5: 3, 2, 1, 2, 1x6: 4, 1, 1, 1, 02.4 系統(tǒng)聚類法 舉例 系統(tǒng)聚類的樹(shù)狀表示作業(yè)畫(huà)出給定迭代次數(shù)為n的系統(tǒng)聚類法的算法流程框圖對(duì)如下5個(gè)6維模式樣本，用最小聚類準(zhǔn)則進(jìn)行系統(tǒng)聚類分析：x1: 0, 1, 3, 1, 3, 4x2: 3, 3, 3, 1, 2, 1x3: 1, 0, 0, 0, 1, 1x4: 2, 1, 0, 2, 2, 1x5: 0, 0, 1, 0, 1, 02.4

10、 系統(tǒng)聚類法 練習(xí) 對(duì)如下6個(gè)五維模式樣本，按最大距離準(zhǔn)則進(jìn)行聚類分析（直到分成三個(gè)類別為止）：x1: 0, 3, 1, 2, 0 x2: 1, 3, 0, 1, 0 x3: 3, 3, 0, 0, 1x4: 1, 1, 0, 2, 0 x5: 3, 2, 1, 2, 1x6: 4, 1, 1, 1, 02.5 動(dòng)態(tài)聚類法 基本思想 首先選擇若干個(gè)樣本點(diǎn)作為聚類中心，再按某種聚類準(zhǔn)則（通常采用最小距離準(zhǔn)則）使樣本點(diǎn)向各中心聚集，從而得到初始聚類； 然后判斷初始分類是否合理，若不合理，則修改分類； 如此反復(fù)進(jìn)行修改聚類的迭代算法，直至合理為止。 K-均值算法 ISODATA算法（迭代自組織數(shù)據(jù)分

11、析算法）2.5.1 K-均值算法 思想：基于使聚類性能指標(biāo)最小化，所用的聚類準(zhǔn)則函數(shù)是聚類集中每一個(gè)樣本點(diǎn)到該類中心的距離平方之和，并使其最小化。 算法2.5.1 K-均值算法 舉例 對(duì)如圖模式樣本用K-均值算法進(jìn)行分類2.5.1 K-均值算法 討論K-均值算法的結(jié)果受如下選擇的影響： 所選聚類的數(shù)目 聚類中心的初始分布 模式樣本的幾何性質(zhì) 讀入次序 在實(shí)際應(yīng)用中，需要試探不同的K值和選擇不同的聚類中心的起始值。 如果模式樣本可以形成若干個(gè)相距較遠(yuǎn)的孤立的區(qū)域分布，一般都能得到較好的收斂效果。 K-均值算法比較適合于分類數(shù)目已知的情況。2.5.1 K-均值算法 作業(yè)/練習(xí) （選k=2,z1(1

12、)=x1,z2(1)=x10,用K-均值算法進(jìn)行聚類分析）計(jì)算機(jī)編程 編寫(xiě)K-均值聚類算法程序，對(duì)下圖所示數(shù)據(jù)進(jìn)行聚類分析(選k=2)：2.5.2 ISODATA算法 與K-均值算法的比較 K-均值算法通常適合于分類數(shù)目已知的聚類，而ISODATA算法則更加靈活； 從算法角度看， ISODATA算法與K-均值算法相似，聚類中心都是通過(guò)樣本均值的迭代運(yùn)算來(lái)決定的； ISODATA算法加入了一些試探步驟，并且可以結(jié)合成人機(jī)交互的結(jié)構(gòu)，使其能利用中間結(jié)果所取得的經(jīng)驗(yàn)更好地進(jìn)行分類。2.5.2 ISODATA算法基本步驟和思路（1） 選擇某些初始值?？蛇x不同的參數(shù)指標(biāo)，也可在迭代過(guò)程中人為修改，以將N

13、個(gè)模式樣本按指標(biāo)分配到各個(gè)聚類中心中去。（2） 計(jì)算各類中諸樣本的距離指標(biāo)函數(shù)。（3）（5）按給定的要求，將前一次獲得的聚類集進(jìn)行分裂和合并處理（4）為分裂處理，（5）為合并處理），從而獲得新的聚類中心。（6） 重新進(jìn)行迭代運(yùn)算，計(jì)算各項(xiàng)指標(biāo)，判斷聚類結(jié)果是否符合要求。經(jīng)過(guò)多次迭代后，若結(jié)果收斂，則運(yùn)算結(jié)束。2.5.2 ISODATA算法 算法 舉例 對(duì)如圖模式樣本用ISODATA算法進(jìn)行分類2.6 聚類結(jié)果的評(píng)價(jià) 迅速評(píng)價(jià)聚類結(jié)果，在上述迭代運(yùn)算中是很重要的，特別是具有高維特征向量的模式，不能直接看清聚類效果，因此，可考慮用以下幾個(gè)指標(biāo)來(lái)評(píng)價(jià)聚類效果： 聚類中心之間的距離 距離值大，通常可考慮分為不同類 聚類域中的樣本數(shù)目 樣本數(shù)目少且聚類中心距離遠(yuǎn)，可考慮是否為噪聲 聚類域內(nèi)樣本的距離方差 方差過(guò)大的樣本可考慮是否屬于這一類 討論：模式聚類目前還沒(méi)有一種通用的放之四海而皆準(zhǔn)的準(zhǔn)則，往往需要根據(jù)實(shí)際應(yīng)用來(lái)選擇合適的方法。作業(yè)畫(huà)出ISODATA算法的流程框圖試用ISODATA算法對(duì)如下模式分布進(jìn)行聚類分析：x