大二下大禮包-模式識(shí)別chapter

模式識(shí)別

PatternRecognition

2015Wuhan,Hubei,ChinaTel.:+86-27-68771218Email:Mobile:8Web:Dr.Prof.JianYao

（姚劍）SchoolofRemoteSensingandInformationEngineering

WuhanUniversity,Wuhan,Hubei,P.R.China第一章概論第二章貝葉斯決策理論第三章判別函數(shù)與確定性分類器第四章聚類分析第五章模式特征分析與選取第六章模糊集合理論在模式識(shí)別中的應(yīng)用第七章句法模式識(shí)別第八章神經(jīng)網(wǎng)絡(luò)在模式識(shí)別中的應(yīng)用教學(xué)綱要模式識(shí)別§4.1相關(guān)概念§4.2模式相似性測(cè)度與聚類準(zhǔn)則§4.3聚類算法§4.4聚類結(jié)果評(píng)價(jià)第四章聚類分析

第四章聚類分析第四章聚類分析

第四章聚類分析引言

§4.1相關(guān)概念沒有訓(xùn)練樣本存在，屬于非監(jiān)督分類。目的是將一批數(shù)據(jù)（模式）組成一些“有意義”的集合（聚類）。這個(gè)思想在生物學(xué)、社會(huì)學(xué)、醫(yī)學(xué)、地球科學(xué)等學(xué)科都是很常見的。下面舉一個(gè)生物學(xué)中的例子：假設(shè)我們有下列動(dòng)物：羊，狗，貓，麻雀，海鷗，小毒蛇，金魚，紅色mullet（一種小海魚，可以吃），藍(lán)色鯊魚和青蛙。將為它們分成不同的類別，我們需要一定的規(guī)則。如果我們用不同的準(zhǔn)則來聚類，可以形成不同的結(jié)果，如下面所示。引言

§4.1相關(guān)概念麻雀、青蛙、海鷗、小毒蛇鯊魚金魚、紅mullet羊、狗、貓以產(chǎn)后代的方式和是否有肺聯(lián)合標(biāo)準(zhǔn)來分羊、狗、貓、鯊魚麻雀、海鷗、小毒蛇、金魚、青蛙、紅mullet以產(chǎn)后代的方式分金魚、鯊魚、紅mullet羊、麻雀、狗、海鷗……以肺是否存在分金魚、鯊魚、紅mullet羊、麻雀、狗、海鷗……以生活環(huán)境分引言

§4.1相關(guān)概念這個(gè)例子說明兩個(gè)問題：1）聚類在生物分類中很常見；2）不同的準(zhǔn)則結(jié)果有很大差別。人類總是將獲取的信息再聚類，否則，不可能處理每個(gè)信息后根據(jù)每個(gè)類的共同特征來表征這個(gè)類。比如當(dāng)我們看見草地上一條狗的時(shí)候，我們會(huì)推斷它的叫聲，因?yàn)楣返慕新暿且粋€(gè)共同特征。聚類過程如下：特征的選擇相似性度量聚類準(zhǔn)則聚類算法聚類評(píng)價(jià)聚類結(jié)果的解譯定義：

對(duì)一批沒有標(biāo)出類別的模式樣本集，按照樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，這種分類稱為聚類分析，也稱為無監(jiān)督分類。相關(guān)概念

§4.1相關(guān)概念分類與聚類的區(qū)別：分類：用已知類別的樣本訓(xùn)練集來設(shè)計(jì)分類器（監(jiān)督學(xué)習(xí)）。聚類（集群）：用事先不知樣本的類別，而利用樣本的先驗(yàn)知識(shí)來構(gòu)造分類器（無監(jiān)督學(xué)習(xí)）?！?.1相關(guān)概念相關(guān)概念

模式相似/分類的依據(jù)：

把整個(gè)模式樣本集的特征向量看成是分布在特征空間中的一些點(diǎn)，點(diǎn)與點(diǎn)之間的距離即可作為模式相似性的測(cè)量依據(jù)。 聚類分析是按不同對(duì)象之間的差異，根據(jù)距離函數(shù)的規(guī)律（大?。┻M(jìn)行模式分類的?！?.1相關(guān)概念相關(guān)概念

聚類分析的有效性：聚類分析方法是否有效，與模式特征向量的分布形式有很大關(guān)系。若向量點(diǎn)的分布是一群一群的，同一群樣本密集（距離很近），不同群樣本距離很遠(yuǎn)，則很容易聚類；若樣本集的向量分布聚成一團(tuán)，不同群的樣本混在一起，則很難分類；對(duì)具體對(duì)象做聚類分析的關(guān)鍵是選取合適的特征。特征選取得好，向量分布容易區(qū)分，選取得不好，向量分布很難分開?！?.1相關(guān)概念相關(guān)概念

兩類模式分類的實(shí)例：一攤黑白圍棋子選顏色作為特征進(jìn)行分類，用“1”代表白，“0”代表黑，則很容易分類；選大小作為特征進(jìn)行分類，則白子和黑子的特征相同，不能分類（把白子和黑子分開）?！?.1相關(guān)概念相關(guān)概念

特征選擇的維數(shù)在特征選擇中往往會(huì)選擇一些多余的特征，它增加了維數(shù)，從而增加了聚類分析的復(fù)雜度，但對(duì)模式分類卻沒有提供多少有用的信息。在這種情況下，需要去掉相關(guān)程度過高的特征（進(jìn)行降維處理）。降維方法：結(jié)論：若rij->1，則表明第i維特征與第j維特征所反映的特征規(guī)律接近，因此可以略去其中的一個(gè)特征，或?qū)⑺鼈兒喜橐粋€(gè)特征，從而使維數(shù)降低一維數(shù)?！?.1相關(guān)概念相關(guān)概念

模式對(duì)象特征測(cè)量的數(shù)字化計(jì)算機(jī)只能處理離散的數(shù)值，因此根據(jù)識(shí)別對(duì)象的不同，要進(jìn)行不同的數(shù)據(jù)化處理。連續(xù)量的量化：用連續(xù)量來度量的特性，如長(zhǎng)度、重量、面積等等，僅需取其量化值；量級(jí)的數(shù)量化：度量時(shí)不需要詳盡的數(shù)值，而是相應(yīng)地劃分成一些有次序的量化等級(jí)的值。病人的病例名義尺度：指定性的指標(biāo)，即特征度量時(shí)沒有數(shù)量關(guān)系，也沒有明顯的次序關(guān)系，如黑色和白色的關(guān)系，男性和女性的關(guān)系等，都可將它們分別用“0”和“1”來表示。超過2個(gè)狀態(tài)時(shí)，可用多個(gè)數(shù)值表示?！?.1相關(guān)概念相關(guān)概念

按最小距離聚類的概念特征向量：標(biāo)準(zhǔn)模式：能代表模式類別的模式或模式集合。距離聚類：n個(gè)樣本，m個(gè)類別，標(biāo)準(zhǔn)模式為Z1,Z2…Zm。聚類準(zhǔn)則（最小距離準(zhǔn)則）:

§4.1相關(guān)概念相關(guān)概念

第四章聚類分析第四章聚類分析

§4.1相關(guān)概念§4.2模式相似性測(cè)度與聚類準(zhǔn)則§4.3聚類算法§4.4聚類結(jié)果評(píng)價(jià)目的：為了能將模式集劃分成不同的類別，必須定義一種相似性的測(cè)度，來度量同一類樣本間的類似性和不屬于同一類樣本間的差異性。歐氏距離馬氏距離一般化的明氏距離（Minkowaki）漢明距離（Hamming）角度相似性函數(shù)§4.2模式相似性測(cè)度與聚類準(zhǔn)則相似性測(cè)度

歐氏距離：量綱對(duì)分類的影響§4.2模式相似性測(cè)度與聚類準(zhǔn)則相似性測(cè)度

當(dāng)采用某一相似性測(cè)度如歐式距離對(duì)所有模式進(jìn)行判別時(shí)，將距離數(shù)值計(jì)算出來，必須確定一個(gè)閾值，在小于此閾值時(shí)，判為同類，否則在大于它時(shí)，定為異類。怎樣確定閾值才比較正確、合理，這就是聚類準(zhǔn)則問題。一般有兩種方式來確定這一準(zhǔn)則試探方法聚類準(zhǔn)則函數(shù)法§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

試探方法根據(jù)經(jīng)驗(yàn)和直觀，確定相似性度量中的閾值，或在確定這些閾值后試行分類，視結(jié)果對(duì)尚不夠合理的閾值加以整理、修正，直至滿意為止。這就是所謂經(jīng)驗(yàn)法，或稱為試探法。

§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

聚類準(zhǔn)則函數(shù)法依據(jù)：由于聚類是將樣本進(jìn)行分類以使類別間可分離性為最大，因此聚類準(zhǔn)則應(yīng)是反映類別間相似性或分離性的函數(shù)；由于類別是由一個(gè)個(gè)樣本組成的，因此一般來說類別的可分離性和樣本的可分離性是直接相關(guān)的；可以定義聚類準(zhǔn)則函數(shù)為模式樣本集{x}和模式類別{Sj,j=1,2,…,c}的函數(shù)，從而使聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問題。這是根據(jù)理論分析確定閾值的方法，它采用聚類準(zhǔn)則函數(shù)進(jìn)行分析?！?.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

一種聚類準(zhǔn)則函數(shù)J的定義J代表了屬于c個(gè)聚類類別的全部模式樣本與其相應(yīng)類別模式均值之間的誤差平方和。對(duì)于不同的聚類形式，J值是不同的。目的：求取使J值達(dá)到最小的聚類形式。三種常見的準(zhǔn)則函數(shù)：誤差平方和準(zhǔn)則與最小方差有關(guān)的準(zhǔn)則散布準(zhǔn)則§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

1）誤差平方和準(zhǔn)則對(duì)于c類模式，準(zhǔn)則函數(shù)為是類的均值向量當(dāng)J最小時(shí)，認(rèn)為聚類合理。在各類樣本密集，類別間距明顯時(shí)，最宜采用這一準(zhǔn)則。§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

2）與最小方差有關(guān)的準(zhǔn)則式中，

是類的樣本數(shù)，是相似性算子：它是類中所有點(diǎn)間距離平方的均值，相似性算子

也可以由其它形式取代，如夾角余弦算子。這一準(zhǔn)則也是以J最小作為判斷聚類合理的依據(jù)?！?.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

3）散布準(zhǔn)則若類的均值向量為：所有向量（不論它屬于哪一類）的均值向量為其中，則類的散布矩陣為由此定義類內(nèi)散布矩陣為§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

并定義類間散布矩陣為總體散布矩陣為可以推導(dǎo)出：§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

推導(dǎo)過程如下：§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

所以，§4.2模式相似性測(cè)度與聚類準(zhǔn)則聚類準(zhǔn)則

準(zhǔn)則函數(shù)根據(jù)各種散布矩陣的“大小”來定義。度量矩陣“大小”可按矩陣跡（矩陣對(duì)角線元素之和）進(jìn)行。例如當(dāng)J最小時(shí)，也就是類內(nèi)散步矩陣跡最小時(shí)，認(rèn)為聚類合理。同樣可以定義：當(dāng)J最大時(shí)，即類間散布矩陣跡最大時(shí)，認(rèn)為聚類合理。§4.1相關(guān)概念§4.2模式相似性測(cè)度與聚類準(zhǔn)則§4.3聚類算法§4.4聚類結(jié)果評(píng)價(jià)第四章聚類分析

第四章聚類分析§4.3聚類算法聚類算法

在選擇了某一聚類準(zhǔn)則函數(shù)J之后，需要對(duì)模式總體進(jìn)行分類，并計(jì)算J值。對(duì)于不同的閾值，各種可能的分類結(jié)果，都要計(jì)算J值，以求達(dá)到最優(yōu)。這樣做需要大量計(jì)算，實(shí)際上是不可能的。一般采取一些被認(rèn)為是可以達(dá)到最優(yōu)結(jié)果的聚類算法。一、基于試探的聚類搜索算法二、系統(tǒng)聚類法三、動(dòng)態(tài)聚類法§4.3聚類算法聚類算法

1.按最近鄰規(guī)則的簡(jiǎn)單試探法（簡(jiǎn)單搜索算法）算法：1.n個(gè)樣本，任選一個(gè)作為第一個(gè)聚類中心z1，并確定一個(gè)非負(fù)閾值T。2.計(jì)算xi到zc距離,若則確定一個(gè)新的聚類中心，否則按最小距離聚類。3.依此方式繼續(xù)搜索，直至得到n個(gè)樣本的所有聚類中心。

討論：這種方法的優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單，若模式樣本的集合分布的先驗(yàn)知識(shí)已知，則可獲得較好的聚類結(jié)果?！?.3聚類算法基于試探的聚類搜索算法

討論（續(xù)）在實(shí)際中，對(duì)于高維模式樣本很難獲得準(zhǔn)確的先驗(yàn)知識(shí)，因此只能選用不同的閾值和起始點(diǎn)來試探，因此這種方法在很大程度上依賴于以下因素：第一個(gè)聚類中心的位置待分類模式樣本的排列次序距離閾值T的大小樣本分布的幾何性質(zhì)§4.3聚類算法基于試探的聚類搜索算法

討論（續(xù)）距離閾值T對(duì)聚類結(jié)果的影響§4.3聚類算法基于試探的聚類搜索算法

2.最大最小距離算法基本思想：以試探類間歐氏距離為最大作為預(yù)選出聚類中心的條件。算法：1.任選一模式樣本作為第一聚類中心z1。2.確定離z1距離最遠(yuǎn)的樣本作為第二聚類中z2。3.逐一計(jì)算各樣本與z1z2間的距離，即§4.3聚類算法基于試探的聚類搜索算法

算法（續(xù)）3.計(jì)算： 上述條件不滿足時(shí)則轉(zhuǎn)5。4.有z3存在，計(jì)算若此最大值大于

則z4存在，否則聚類中心的搜尋計(jì)算結(jié)束。5.對(duì)所有模式樣本，逐一計(jì)算它們到各聚類中心的距離，按最小距離法則進(jìn)行聚類?！?.3聚類算法基于試探的聚類搜索算法

最大最小距離法-算法實(shí)例取:=0.5z1=x1

1(x1,x3,x4)z2=x6

2(x2,x6)z3=x73(x5,x7,x8,x9,x10)基于試探的聚類搜索算法

§4.3聚類算法一、基于試探的聚類搜索算法二、系統(tǒng)聚類法三、動(dòng)態(tài)聚類法§4.3聚類算法聚類算法

基本思想：

先把每個(gè)樣本各作為一類，然后將模式樣本按距離準(zhǔn)則逐步聚類，類別由多到少，直到獲得合適的分類要求為止?！?.3聚類算法系統(tǒng)聚類法

算法：1.樣本{x1,x2,…,xn}自成一類，即:

G1(0),G2(0),…Gn(0)，計(jì)算各類間距離矩陣:Dnn(0)2.求Dnn(0)中的最小元素，其對(duì)應(yīng)的類別合并，建立新的分類:G1(1),G2(1),…Gn-1(1)。3.重復(fù)：求D(N)，建新的分類:G1(N+1),G2(N+1),…。當(dāng)D(N)中的最小值大于閾值T或類別數(shù)等于K,迭代結(jié)束，輸出分類結(jié)果?！?.3聚類算法系統(tǒng)聚類法

距離準(zhǔn)則函數(shù)：

進(jìn)行聚類合并的一個(gè)關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計(jì)算，采用不同的距離函數(shù)會(huì)得到不同的計(jì)算結(jié)果。§4.3聚類算法系統(tǒng)聚類法

主要的距離計(jì)算準(zhǔn)則：1、最短距離法：兩類中相距最近的兩樣本間的距離。2、最長(zhǎng)距離法：兩類中相距最遠(yuǎn)的兩樣本間的距離。3、中間距離法：最短距離和最長(zhǎng)距離都有片面性，因此有時(shí)用中間距離。設(shè)ω1類與ω2

和ω3類間的最短距離為d12，最長(zhǎng)距離為d13，ω2

和ω3類間的距離為d23，則中間距離為：推廣形式：§4.3聚類算法系統(tǒng)聚類法

主要的距離計(jì)算準(zhǔn)則：4、重心距離法：均值間的距離。5、類平均距離法：兩類中各個(gè)元素兩兩之間的距離平方相加后取平均值§4.3聚類算法系統(tǒng)聚類法

系統(tǒng)聚類法—算法實(shí)例：例：如下圖所示

用系統(tǒng)聚類法按最小距離分成二類。§4.3聚類算法系統(tǒng)聚類法—例子11、設(shè)全部樣本分為6類，作距離矩陣D(0)G1（０）G２（０）G３（０）G４（０）G５（０）G６（０）G1（０）０G２（０）３０G３（０）1４０G４（０）７４８０G５（０）５２６２０G６（０）８５９1３０§4.3聚類算法系統(tǒng)聚類法—例子12、求最小元素：把G1,G3合并，G4,G6合并，作距離矩陣D(1)若合并的類數(shù)沒有達(dá)到要求，轉(zhuǎn)3。否則輸出結(jié)果。G2G5G1,G3G4,G6G2(5)0G5(7)20G1,G3(2,1)350G4,G6(9,10)4270§4.3聚類算法系統(tǒng)聚類法—例子13、求最小元素：，G2,G5,(G4G6)合并。滿足二類條件，分類結(jié)果為：1(G1,G3),2(G2,G4,G5,G6)樹狀圖：X3=112X1=2X2=5X5=7X4=9X6=10§4.3聚類算法系統(tǒng)聚類法—例子1

模式樣本的選取和初始聚類中心的確定：待識(shí)別分類的模式集合有時(shí)是一個(gè)很大的集合，如遙感數(shù)字影像等。而在采取聚類分析方法時(shí)，大都進(jìn)行迭代計(jì)算，若將所有模式反復(fù)進(jìn)行迭代計(jì)算，是不經(jīng)濟(jì)的。為此，需要進(jìn)行抽樣，在樣本集合中先實(shí)施迭代，以確定各類中心，然后對(duì)模式集合的全體進(jìn)行分類。另一方面，迭代計(jì)算的初始聚類中心的確定往往具有一定的盲目性，如何盡可能地減少這種盲目性的程度，也成為一個(gè)課題。下面以法國(guó)國(guó)家地理研究院自動(dòng)分類軟件中的一種作法為例，說明在解決上述兩方面問題過程中的進(jìn)展?！?.3聚類算法系統(tǒng)聚類法—例子2

模式樣本的選取和初始聚類中心的確定：以二維遙感影像數(shù)據(jù)為例。在二維灰度平面角分線上選取50個(gè)點(diǎn)作為初始聚類中心（如圖a），然后在此平面上7像元7像元的格網(wǎng)點(diǎn)（圖b）上進(jìn)行迭代聚類，迭代次數(shù)限值為10，最后的類別中心限值為20，迭代完畢，即轉(zhuǎn)入對(duì)所有像元的分類。

圖a圖b§4.3聚類算法系統(tǒng)聚類法—例子2

可以將法國(guó)的方法加以改善，即首先確定二維分布范圍，這是比較容易做到的（如圖c）。然后在這一分布空間內(nèi)等間隔地確定一些點(diǎn)（圖c中處）作為初始聚類中心，開始對(duì)某一確定的格網(wǎng)上的點(diǎn)進(jìn)行迭代運(yùn)算。

圖c§4.3聚類算法系統(tǒng)聚類法—例子2畫出給定迭代次數(shù)為n的系統(tǒng)聚類法的算法流程框圖。對(duì)如下5個(gè)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§4.3聚類算法作業(yè)作業(yè)提交Deadline：2015年5月4日一、基于試探的聚類搜索算法二、系統(tǒng)聚類法三、動(dòng)態(tài)聚類法§4.3聚類算法聚類算法基本思想:首先選擇若干個(gè)樣本點(diǎn)作為聚類中心，再按某種聚類準(zhǔn)則（通常采用最小距離準(zhǔn)則）使樣本點(diǎn)向各中心聚集，從而得到初始聚類；然后判斷初始分類是否合理，若不合理，則修改分類；如此反復(fù)進(jìn)行修改聚類的迭代算法，直至合理為止。 1、K-均值算法 2、ISODATA算法（迭代自組織數(shù)據(jù)分析算法）§4.3聚類算法動(dòng)態(tài)聚類法思想：

基于使聚類性能指標(biāo)最小化，所用的聚類準(zhǔn)則函數(shù)是聚類集中每一個(gè)樣本點(diǎn)到該類中心的距離平方之和，并使其最小化?！?.3聚類算法K-均值算法算法：（1）任選K個(gè)初始聚類中心。一般以開頭K個(gè)樣本作為初始中心。（2）將模式樣本集的每一樣本按最小距離原則分配給K個(gè)聚類中心，即在第m次迭代時(shí)，若:則，表示第m次迭代時(shí)，以第j個(gè)聚類中心為代表的聚類域?！?.3聚類算法K-均值算法算法：（3）由步驟（2），計(jì)算新的聚類中心，即:

式中Ni為第i個(gè)聚類域中的樣本個(gè)數(shù)。其均值向量作為新的聚類中心，因?yàn)檫@樣可以使誤差平方和準(zhǔn)則函數(shù):達(dá)到最小值。（4）若，算法收斂，計(jì)算完畢。否則返回到步驟（2），進(jìn)行下一次迭代?！?.3聚類算法K-均值算法例：已知有20個(gè)樣本，每個(gè)樣本有2個(gè)特征，數(shù)據(jù)分布如下圖：樣本序號(hào)x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899§4.3聚類算法K-均值算法—例子§4.3聚類算法K-均值算法—例子第一步：令K=2，選初始聚類中心為§4.3聚類算法K-均值算法—例子第二步：§4.3聚類算法K-均值算法—例子第三步：根據(jù)新分成的兩類建立新的聚類中心第四步：判斷是否終止？

因?yàn)椋?/p>

所以，轉(zhuǎn)第二步。第二步：重新計(jì)算到z1(2),z2(2)的距離，

把它們歸為最近聚類中心，重新分為兩類?！?.3聚類算法K-均值算法—例子第三步，更新聚類中心§4.3聚類算法K-均值算法—例子第四步，判斷是否終止？第二步，第三步，更新聚類中心§4.3聚類算法K-均值算法—例子討論K-均值算法的結(jié)果受如下選擇的影響：所選聚類的數(shù)目模式樣本的幾何性質(zhì)聚類中心的初始分布讀入次序在實(shí)際應(yīng)用中，需要試探不同的K值和選擇不同的聚類中心的起始值。如果模式樣本可以形成若干個(gè)相距較遠(yuǎn)的小塊孤立的區(qū)域分布，一般都能得到較好的收斂效果。K-均值算法比較適合于分類數(shù)目已知的情況。§4.3聚類算法K-均值算法

（選k=2, z1(1)=x1, z2(1)=x10,

用K-均值算法 進(jìn)行聚類分析）§4.3聚類算法作業(yè)作業(yè)提交Deadline：2015年5月4日編寫K-均值聚類算法程序，對(duì)下圖所示數(shù)據(jù)進(jìn)行聚類分析（選k=2）：§4.3聚類算法編程練習(xí)作業(yè)提交Deadline：2015年5月4日ISODATA（IterativeSelforganizingDataAnalysisTechniquesAlgorithm）-迭代自組織數(shù)據(jù)分析算法

ISODATA算法是在k-均值算法的基礎(chǔ)上，增加對(duì)聚類結(jié)果的“合并”和“分裂”兩個(gè)操作，并設(shè)定算法運(yùn)行控制參數(shù)的一種聚類算法。迭代次數(shù)會(huì)影響最終結(jié)果，迭代參數(shù)選擇很重要?！昂喜ⅰ辈僮鳎寒?dāng)聚類結(jié)果某一類中樣本數(shù)太少，或兩個(gè)類間的距離太近時(shí)，進(jìn)行合并?！胺至选辈僮鳎寒?dāng)聚類結(jié)果某一類中樣本某個(gè)特征類內(nèi)方差太大，將該類進(jìn)行分裂§4.3聚類算法ISODATA算法與K-均值算法的比較K-均值算法通常適合于分類數(shù)目已知的聚類，而ISODATA算法則更加靈活；從算法角度看，ISODATA算法與K-均值算法相似，聚類中心都是通過樣本均值的迭代運(yùn)算來決定的；ISODATA算法加入了一些試探步驟，并且可以結(jié)合人機(jī)交互的結(jié)構(gòu)，使其能利用中間結(jié)果所取得的經(jīng)驗(yàn)更好地進(jìn)行分類?！?.3聚類算法ISODATA算法基本步驟（1） 選擇某些初始值?？蛇x不同的指標(biāo)，也可在迭代過程中人為修改，以將N個(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)過多次迭代后，若結(jié)果收斂，則運(yùn)算結(jié)束?！?.3聚類算法ISODATA算法詳細(xì)步驟：該算法需要確定并在計(jì)算中可以調(diào)整的參數(shù)有：K:所要求的聚類中心數(shù)。:一個(gè)類別至少應(yīng)具有的樣本數(shù)目。:一個(gè)類別樣本標(biāo)準(zhǔn)差閾值。:聚類中心之間距離的閾值，即歸并系數(shù)。L:在一次迭代中可以歸并的類別的最多對(duì)數(shù)。I:允許迭代的最多次數(shù)。第一步：對(duì)于N個(gè)模式樣本的集合，確定C個(gè)初始聚類中心，C不一定等于K。這些聚類中心可為模式集合中的任意樣本。第二步：確定上述六個(gè)參數(shù)，即。

§4.3聚類算法ISODATA算法第三步：將N個(gè)樣本按最小距離分類，即若

第四步：若對(duì)于某一聚類域fj，其樣本數(shù)目則取消該子集fj和Zj，并且C=C-1，即類別數(shù)減少1。第五步：修正各聚類中心值：第六步：對(duì)每一聚類域fj，計(jì)算其所有樣本到其聚類中心的距離的平均值。§4.3聚類算法ISODATA算法第七步：計(jì)算所有樣本到其相應(yīng)聚類中心的距離的平均值。第八步：①若迭代次數(shù)達(dá)到I次，置，轉(zhuǎn)入第十二步，運(yùn)算結(jié)束；②若，即聚類中心數(shù)目等于或不到規(guī)定數(shù)目的二分之一，則轉(zhuǎn)入第九步，以對(duì)現(xiàn)有類別進(jìn)行分裂；③若迭代次數(shù)為偶次，或，不進(jìn)行分裂處理，跳到第十二步，否則進(jìn)行分裂處理?！?.3聚類算法ISODATA算法第九步：計(jì)算每一類別中樣本與聚類中心距離的標(biāo)準(zhǔn)差向量：

其中每一分量為：

n為模式樣本的維數(shù)，xil是fj中第l個(gè)樣本的第i分量，zij是zj的第i分量。第十步：對(duì)每一標(biāo)準(zhǔn)差向量，求其最大分量，以表示，用S記下它是第幾分量?！?.3聚類算法ISODATA算法第十一步：在最大分量集中，若有并且滿足下列條件之一：和，即該類中樣本到聚類中心的平均

距離大于總體平均距離且該類樣本總數(shù)超過規(guī)定數(shù)目二倍。則將分裂成兩個(gè)新的聚類中心和，去掉，且令C=C+1。的確定方法是對(duì)應(yīng)于的zj的分量即第S分量加上,其它分量不變，構(gòu)成。第S分量減去，其它分量不變，構(gòu)成。分裂完畢，轉(zhuǎn)入第三步。如果沒有可分裂的類別，則繼續(xù)進(jìn)行?！?.3聚類算法ISODATA算法第十三步：將每一值與值比較，凡有，均取出以組成一個(gè)集合。

第十二步：計(jì)算每?jī)蓚€(gè)聚類中心之間的距離：這里：§4.3聚類算法ISODATA算法第十四步：從開始，逐一合并的類別和，每一類別只能歸并一次，合并后新的類別以新的聚類中心作為標(biāo)志：第十五步：如果是最后一次迭代計(jì)算（即第I次），

算法結(jié)束。否則，如果需要改變參數(shù)則轉(zhuǎn)入第二步，

不需要改變參數(shù)則轉(zhuǎn)入第三步?！?.3聚類算法ISODATA算法例：對(duì)如圖模 式樣本用

ISODATA

算法進(jìn)行 分類§4.3聚類算法ISODATA算法—例子第一步，取初值C=1，令。第二步，確定參數(shù)K=2，

這是在假設(shè)沒有樣本先驗(yàn)知識(shí)可利用的情況下任意取值確定的。在迭代過程中，這些參數(shù)還可以視情況加以修正。第三步，因只一個(gè)聚類中心，無從分析所謂最小距離，故第四步，因，無子集可取消。第五步，修改聚類中心，第六步，計(jì)算?！?.3聚類算法ISODATA算法—例子第七步，計(jì)算:

第十一步，因，且，可將分裂成兩個(gè)新的聚類中心。設(shè)，則第八步，由于不是最后一次迭代，且，故進(jìn)入第九步。第九步，求中的標(biāo)準(zhǔn)差向量。第十步，中最大分量為1.99，故。

為方便起見，將和改名為和，C亦增加1，然后返回第三步?！?.3聚類算法ISODATA算法—例子第六步，計(jì)算:第三步，計(jì)算每一樣本到和的距離，按最小距離進(jìn)行分類，得到兩個(gè)聚類域：第四步，因和均大于，故無可取消之類別。第五步，修改聚類中心:§4.3聚類算法ISODATA算法—例子第十四步，根據(jù)第十三步比較的情況，無可進(jìn)行合并的類別對(duì)。第七步，計(jì)算:第八步，因?yàn)檫@是偶數(shù)次迭代，滿足第八步第③項(xiàng)條件，故進(jìn)入第十二步第十二步，計(jì)算聚類中心之間的距離。第十三步，比較與，有。§4.3聚類算法ISODATA算法—例子第三—第七步，與前一次迭代計(jì)算結(jié)果相同。第八步，條件均不能滿足，故繼續(xù)下一步。第十五步，因?yàn)檫@還不是最后一次迭代，需要判斷是否需要修改給定的參數(shù)。由于：①已獲得所要求的聚類數(shù)目；②聚類之間的分離度（兩聚類中心之間的距離）大于類別之間樣本分離的標(biāo)準(zhǔn)差③每一聚類子集的樣本數(shù)目都具有樣本總數(shù)中的足夠大的百分比。因此，可以認(rèn)為兩聚類中心能代表各子集樣本。返回第三步。第九步，計(jì)算