在已知類(lèi)別的樣本集基礎(chǔ)上，用確定的或統(tǒng)計(jì)的判別函數(shù)對(duì)模式進(jìn)行分類(lèi)，設(shè)計(jì)分類(lèi)器，這些已知的樣本集稱(chēng)為訓(xùn)練集。根據(jù)判讀好的訓(xùn)練集解決分類(lèi)問(wèn)題，稱(chēng)為有人管理或有教師的分類(lèi)法。

第五章聚類(lèi)分析第五章聚類(lèi)分析第五章聚類(lèi)分析沒(méi)有訓(xùn)練集的情況下的樣本分類(lèi)問(wèn)題，所選用的樣本是預(yù)先不知其所屬的類(lèi)別，需要根據(jù)樣本間的距離或相似性的程度自動(dòng)地進(jìn)行分類(lèi)。這種無(wú)人參預(yù)（或沒(méi)有教師的）識(shí)別問(wèn)題，稱(chēng)為聚類(lèi)或無(wú)人管理的分類(lèi)。第五章聚類(lèi)分析聚類(lèi)分析方法是決定描述一個(gè)經(jīng)驗(yàn)數(shù)據(jù)集的結(jié)構(gòu)類(lèi)型的一種非參數(shù)方法。相似的數(shù)據(jù)被集中在一起，從數(shù)據(jù)集中分離出來(lái)，包含在特征空間中的一個(gè)模式集，其模式的密度比起周?chē)鷧^(qū)域中的密度大，就為一個(gè)聚類(lèi)。第五章聚類(lèi)分析第五章聚類(lèi)分析聚類(lèi)原則：根據(jù)樣本集，找出各點(diǎn)內(nèi)在的相似性進(jìn)行分類(lèi)，相似的分為一類(lèi)。⑴直觀的相似性：從幾何距離考慮，設(shè)閾值T，它是相似性度量的標(biāo)準(zhǔn)，靠經(jīng)驗(yàn)確定，對(duì)分類(lèi)影響很大?？捎糜诖址?。⑵樣本集群性（緊致性）：同一類(lèi)的應(yīng)該群集，不同類(lèi)的應(yīng)該遠(yuǎn)離。第五章聚類(lèi)分析第五章聚類(lèi)分析⑶特征空間量綱標(biāo)尺的選擇：量綱選擇不同，分類(lèi)也有差異。第五章聚類(lèi)分析第五章聚類(lèi)分析為了克服這個(gè)缺點(diǎn)，常使特征數(shù)據(jù)標(biāo)準(zhǔn)化，使它與變量量綱標(biāo)尺沒(méi)有關(guān)系。第五章聚類(lèi)分析第五章聚類(lèi)分析5.1相似性度量和聚類(lèi)準(zhǔn)則一般用歸并相似的模式和分開(kāi)不相似的模式以形成聚類(lèi)。相似性歸并是聚類(lèi)最普通的形式。各式各樣的相似性和距離度量已經(jīng)作為特征空間中模式樣本的聚類(lèi)準(zhǔn)則。第五章聚類(lèi)分析第五章聚類(lèi)分析5.1.1相似性度量(Similaritymeasure)

相似性度量將建立一個(gè)把模式分到一聚類(lèi)中心域的原則。⒈歐氏距離(Euclideandistance)(常用)對(duì)兩個(gè)樣本xi和xj，其歐氏距離定義為若dij小，相似性大。5.1相似性度量和聚類(lèi)準(zhǔn)則第五章聚類(lèi)分析加權(quán)歐氏距離也是一種常用的相似性度量。wk是系數(shù)，其重要，wk大；次要的，wk小。

⒈歐氏距離(Euclideandistance)(常用)5.1.1相似性度量第五章聚類(lèi)分析⒉馬氏距離

(Mahalanobisdistance)(不常用)x是待識(shí)別樣本，m是均值向量，∑是協(xié)方差矩陣。若∑為單位陣，則馬氏距離與歐氏距離相似。馬氏距離的優(yōu)點(diǎn)是排除了模式樣本之間的相關(guān)性的影響。例如取一個(gè)模式特征向量，可能其中九個(gè)分量是反映同一特征A，而只有一個(gè)分量反映另一特征B，這時(shí)如用歐氏距離計(jì)算，主要反映了特征A，而用馬氏距離則可避免這個(gè)缺點(diǎn)。5.1.1相似性度量第五章聚類(lèi)分析⒊明氏距離(Minkowskydistance)m=2時(shí)為歐氏距離；m=1為絕對(duì)距離(用絕對(duì)值)；dij=|xi1－xj1|+…+|xid－xjd|相似性度量不一定只限于距離，可以是下面的形式：5.1.1相似性度量第五章聚類(lèi)分析⒋角度相似性度量函數(shù)sij是向量xi和xj之間夾角的余弦，當(dāng)xi和xj相對(duì)于原點(diǎn)是同一方向時(shí)，函數(shù)值最大。當(dāng)聚類(lèi)區(qū)域有扇形分布時(shí)往往采用這種相似性度量。如圖5.1所示。5.1.1相似性度量第五章聚類(lèi)分析θ2θ10ωiωj圖5.1相似性度量的說(shuō)明從圖中可以看到，由于s(x，x1)比s(x，x2)大，因此x與x1比與x2更相似。x1x2x5.1.1相似性度量第五章聚類(lèi)分析距離和角度相似性函數(shù)作為相似性的測(cè)度各有其局限性。距離對(duì)于坐標(biāo)系的旋轉(zhuǎn)和位移是不變的，對(duì)于放大縮小并不具有不變性的性質(zhì)。角度相似性函數(shù)對(duì)于坐標(biāo)系的旋轉(zhuǎn)放大縮小是不變的，但對(duì)于位移不具有不變性的性質(zhì)。用角度相似性函數(shù)作為相似性的測(cè)度還有一個(gè)缺點(diǎn)，當(dāng)本屬不同類(lèi)的樣本分布在從模式空間原點(diǎn)出發(fā)的一條直線上時(shí)，所有樣本之間角度相似性函數(shù)幾乎都等于l，造成歸為一類(lèi)的錯(cuò)誤。5.1.1相似性度量第五章聚類(lèi)分析⒌Tanimoto度量(常用)

若模式向量取二進(jìn)制值0，1時(shí)有特殊意義，樣本x具有第k個(gè)特征，xiTxj是兩者共同的特征數(shù)；是xi和xj各自具有的特征數(shù)的幾何均值。這種度量稱(chēng)為T(mén)animoto度量。5.1.1相似性度量第五章聚類(lèi)分析⒌Tanimoto度量(常用)

適用于疾病診斷、動(dòng)植物分類(lèi)和情報(bào)檢索等方面。上述介紹的相似性量度不是僅有的形式，而是屬于比較簡(jiǎn)單和典型的。5.1.1相似性度量第五章聚類(lèi)分析距離函數(shù)應(yīng)滿(mǎn)足三個(gè)條件：⑴非負(fù)性：對(duì)于一切i，j，dij(xi，xj)≥0，當(dāng)xi=xj時(shí)，等號(hào)成立。⑵對(duì)稱(chēng)性：對(duì)于一切i，j，dij(xi，xj)=dji(xj，xi)，即距離是標(biāo)量而不是向量。⑶三角不等式：dij(xi，xj)≤djk(xj，xk)+dkj(xk，xj)，即相當(dāng)于三角形兩邊之和必大于第三邊。5.1.1相似性度量第五章聚類(lèi)分析5.1.2聚類(lèi)準(zhǔn)則

假定有一組樣本{x1，x2，…，xN}，要求對(duì)其進(jìn)行確切分成ω1，ω2，…，ωc類(lèi)。同一類(lèi)里的樣本比不同類(lèi)里的樣本相似性高一些，于是可存在多種分類(lèi)，到底何種分類(lèi)方法最好？需要定義一個(gè)準(zhǔn)則函數(shù)，則聚類(lèi)問(wèn)題就變成對(duì)準(zhǔn)則函數(shù)求極值的問(wèn)題。5.1相似性度量和聚類(lèi)準(zhǔn)則第五章聚類(lèi)分析⒈試探方式：針對(duì)具體的實(shí)際問(wèn)題，定義一種相似性度量的閾值T，按最近鄰原則分類(lèi)，須不斷檢驗(yàn)、修正閾值T。這種方法的誤判率受T及起始樣本影響。

5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒉誤差平方和準(zhǔn)則(最小方差劃分)(常用)

誤差平方和準(zhǔn)則是聚類(lèi)問(wèn)題中最簡(jiǎn)單而又廣泛應(yīng)用的準(zhǔn)則。準(zhǔn)則函數(shù)為

c是類(lèi)別數(shù)，Xi是第i類(lèi)聚類(lèi)中心域的樣本集合，mi是第i類(lèi)均值向量(類(lèi)中心)

Ni是Xi中的樣本數(shù)。使J最小化的聚類(lèi)就是最合理的聚類(lèi)。5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒉誤差平方和準(zhǔn)則(最小方差劃分)

此種準(zhǔn)則函數(shù)適用于集群性好，且各類(lèi)容積相近情況。如果類(lèi)間距離小，容積相差懸殊，容易發(fā)生錯(cuò)誤。5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒉誤差平方和準(zhǔn)則(最小方差劃分)如圖(a)中所示的模式分類(lèi)，使用這種準(zhǔn)則進(jìn)行聚類(lèi)可獲得最好的效果。ω1ω2ω3x1x2(a)5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒉誤差平方和準(zhǔn)則(最小方差劃分)而如圖(b)中的模式分布，使用這種準(zhǔn)則得到的效果就不理想。

ω1ω2x1x2(b)5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒉誤差平方和準(zhǔn)則(最小方差劃分)當(dāng)各類(lèi)中的樣本數(shù)相差很大而類(lèi)間距離較小時(shí)，有可能把樣本數(shù)多的一類(lèi)一拆為二，這樣聚類(lèi)的結(jié)果，誤差平方和準(zhǔn)則函數(shù)J比保持完整時(shí)為小(如圖5.3所示)。因此有可能將ω1和ω2分錯(cuò)，發(fā)生錯(cuò)誤聚類(lèi)。5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒉誤差平方和準(zhǔn)則(最小方差劃分)圖5.3把大群拆開(kāi)的問(wèn)題(b)的誤差平方和小于(a)的誤差平方和5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒊與最小方差有關(guān)的準(zhǔn)則經(jīng)過(guò)簡(jiǎn)單的代數(shù)運(yùn)算，可以將上述J的表達(dá)式中均值向量mi消去，得到另一種準(zhǔn)則函數(shù)表示形式式中c是聚類(lèi)數(shù)；Ni是第i個(gè)聚類(lèi)域中的樣本數(shù)；Si是相似性算子。它是第i類(lèi)點(diǎn)間距離平方的平均，是以歐氏距離作為相似性度量。5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒊與最小方差有關(guān)的準(zhǔn)則若以非尺寸的相似性函數(shù)s(x，x’)來(lái)取代相似性算子Si中的歐氏距離并把它代入準(zhǔn)則函數(shù)J的表示式中，可得到準(zhǔn)則函數(shù)的另一種表示形式。5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒋散布準(zhǔn)則（離散度準(zhǔn)則）用多元判別式分析中的散布矩陣可以推出另一種準(zhǔn)則函數(shù)。第i類(lèi)的均值向量(第i類(lèi)的中心)

總平均向量(總體中心)

5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒋散布準(zhǔn)則（離散度準(zhǔn)則）第i類(lèi)的散布矩陣類(lèi)內(nèi)散布矩陣類(lèi)間散布矩陣5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒋散布準(zhǔn)則(離散度準(zhǔn)則)總散布矩陣

根據(jù)上述定義可以證明，總散布矩陣等于類(lèi)內(nèi)散布矩陣與類(lèi)間散布矩陣之和。即：ST

=SW+SB

5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析證明：ST

=SW+SB∵∴

5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析散布準(zhǔn)則(離散度準(zhǔn)則)總散布矩陣與如何劃分類(lèi)別無(wú)關(guān)，僅與全部樣本有關(guān)。但類(lèi)內(nèi)和類(lèi)間散布矩陣都與類(lèi)別劃分有關(guān)。這兩矩陣有一互補(bǔ)關(guān)系，因此使類(lèi)內(nèi)散布矩陣最小就是使類(lèi)間散布矩陣最大。

由于度量矩陣大小的方法有“跡”和行列式，故利用散布矩陣提出以下準(zhǔn)則：

5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒈跡準(zhǔn)則

跡是散布矩陣大小的最簡(jiǎn)單的度量，跡等于散布矩陣的對(duì)角線元素之和，最小化SW的跡準(zhǔn)則使其(J)取最小值，是一種最優(yōu)化的準(zhǔn)則。5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒈跡準(zhǔn)則或最大化SB的跡作為另一種最優(yōu)化的準(zhǔn)則。

5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析⒉行列式準(zhǔn)則散布矩陣的行列式可作為散布矩陣的另一種大小度量。在類(lèi)數(shù)小于或等于維數(shù)時(shí)，SB是奇異的，所以不能選擇SB的行列式作為準(zhǔn)則函數(shù)，一般選擇SW的行列式，行列式準(zhǔn)則函數(shù)為這是因?yàn)榫仃囆辛惺降拇笮≌扔谥鬏S方向方差的乘積。5.1.2聚類(lèi)準(zhǔn)則

第五章聚類(lèi)分析5.2聚類(lèi)算法5.2.1按最近鄰原則試探算法

特點(diǎn)：簡(jiǎn)單、快速。缺點(diǎn)：粗糙。假設(shè)有N個(gè)樣本{x1，x2，…，xN}，x在d維特征空間，類(lèi)別數(shù)未知。

第五章聚類(lèi)分析應(yīng)用于無(wú)訓(xùn)練樣本集，無(wú)教師（或無(wú)人）參與分類(lèi)過(guò)程。第五章聚類(lèi)分析㈠算法步驟(依據(jù)試探性準(zhǔn)則)

⒈選定一個(gè)非負(fù)的閾值T。⒉在{x1，x2，…，xN}中任取xi，i=1，2，…，N，令任一個(gè)樣本xi為第一個(gè)聚類(lèi)中心z1，即z1=xi，例如，可選z1=x1作為第一個(gè)聚類(lèi)中心。⒊取x2計(jì)算(根據(jù)具體問(wèn)題選定計(jì)算方法)5.2.1按最近鄰原則試探算法第五章聚類(lèi)分析㈠算法步驟(依據(jù)試探性準(zhǔn)則)

判斷：①d21＞T，則建立一個(gè)新的聚類(lèi)中心z2，z2=x2。②d21≤T，則x2∈X1，X1是以z1為聚類(lèi)中心的模式的集合。例如，選定歐氏距離作為相似性度量，計(jì)算x2到z1的距離5.2.1按最近鄰原則試探算法第五章聚類(lèi)分析㈠算法步驟(依據(jù)試探性準(zhǔn)則)

⒋取下一個(gè)樣本xj，xj是余下的樣本中的任一個(gè)，計(jì)算dj1=||xj－z1||，dj2=||xj－z2||，…，dj1=||xj－zk||，接著分別計(jì)算x3到z1和z2的距離得d31和d32，如果判斷①d31＞T，d32＞T，則再建立一個(gè)新的聚類(lèi)中心z3，z3=x3。②d31≤d32≤T，則x3∈X1，否則x3∈X2，X2是以z2為聚類(lèi)中心的模式的集合。即將x3分到最近的聚類(lèi)中心的域中。5.2.1按最近鄰原則試探算法第五章聚類(lèi)分析㈠算法步驟(依據(jù)試探性準(zhǔn)則)

⒌所有樣本全部處理完畢否？沒(méi)有處理完，轉(zhuǎn)4。處理完，算法結(jié)束。

若

否則，xj屬于離它最近的聚類(lèi)中心所屬的類(lèi)。判斷：5.2.1按最近鄰原則試探算法第五章聚類(lèi)分析㈡算法討論此算法的聚類(lèi)結(jié)果受閾值T的大小、初始值z(mì)1的選擇、樣本的順序及數(shù)據(jù)的幾何特性等四個(gè)因素的影響。其中T和z1的影響大一些。如圖5.4所示。

(a)(b)T3(c)圖5.4按最近鄰原則試探算法中閾值和起始點(diǎn)的影響T2T2T15.2.1按最近鄰原則試探算法第五章聚類(lèi)分析改進(jìn)措施：①具有待分類(lèi)樣本集的幾何分布的先驗(yàn)知識(shí)，用來(lái)指導(dǎo)選擇T和z1，可以改善聚類(lèi)結(jié)果(在d較小時(shí)，如d=1，2，3等)。②在d較大的高維情況，要進(jìn)行反復(fù)驗(yàn)算、修正T和z1(驗(yàn)算采用誤差平方和等準(zhǔn)則)。否則，此算法只能用于粗糙分類(lèi)，進(jìn)行預(yù)分。5.2.1按最近鄰原則試探算法第五章聚類(lèi)分析5.2.2小中取大距離算法(最大最小距離算法)

此算法以歐氏距離為基礎(chǔ)，選集合中最不相似(距離最大)的點(diǎn)或樣本作為各類(lèi)的聚類(lèi)中心。舉例說(shuō)明如圖所示樣本的此聚類(lèi)算法步驟：5.2.2小中取大距離算法第五章聚類(lèi)分析如圖所示模式：⒈任選一模式樣本x1，令z1=x1為第一個(gè)聚類(lèi)中心。1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的樣本模式5.2.2小中取大距離算法第五章聚類(lèi)分析⒈在圖(b)中由z1標(biāo)志，圖中箭頭上的數(shù)字標(biāo)志了聚類(lèi)中心賦值的步驟。x1x2x3x4x5x6x7x8x9x10z1(1)(b)樣本和種類(lèi)表⒉計(jì)算歐氏距離di1=||xi－z1||，i=1，2，…，N。5.2.2小中取大距離算法第五章聚類(lèi)分析則令z2=xj為新的聚類(lèi)中心。在此例中最大，故z2=x6。

1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的樣本模式判斷：若5.2.2小中取大距離算法第五章聚類(lèi)分析在圖(b)中由z2標(biāo)志x1x2x3x4x5x6x7x8x9x10z1z2z3(1)(2)(b)樣本和種類(lèi)表5.2.2小中取大距離算法第五章聚類(lèi)分析⒊找新的聚類(lèi)中心設(shè)當(dāng)前已有z1，z2，…，zk個(gè)聚類(lèi)中心，分別計(jì)算其余樣本到各聚類(lèi)中心的距離：1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的樣本模式di1=||xi－z1||，di2=||xi－z2||，……，dik=||xi－zk||，i=1，2，…，N5.2.2小中取大距離算法第五章聚類(lèi)分析取，m=1，2，…，k。取，i=1，2，…，N。若djm＞θmax||zi－zl||，i，l=1，2，…k。則令zk+1=xj。此例中，z3=x7，。θ是系數(shù)，。5.2.2小中取大距離算法1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的樣本模式第五章聚類(lèi)分析在圖(b)中由z3標(biāo)志，圖中箭頭上的數(shù)字標(biāo)志了聚類(lèi)中心賦值的步驟。x1x2x3x4x5x6x7x8x9x10z1z2z3(1)(2)(3)(b)樣本和種類(lèi)表5.2.2小中取大距離算法第五章聚類(lèi)分析θ若取得大，劃分的類(lèi)少；θ若取得小，劃分的類(lèi)多。一般根據(jù)經(jīng)驗(yàn)試探選。⒋每確定一個(gè)新的聚類(lèi)中心后，重復(fù)3。若djm≤θmax||zi－zl||，i，l=1，2，…，k。則尋找聚類(lèi)中心的工作結(jié)束。

5.2.2小中取大距離算法1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的樣本模式第五章聚類(lèi)分析⒌計(jì)算距離后分類(lèi)dil=||xi－xl||，i=1，2，…，N；l=1，2，…，k。根據(jù)最近鄰原則分類(lèi)。本例中，X1={x1，x3，x4}，X2={x2，x6}，X3={x5，x7，x8，x9，x10}。5.2.2小中取大距離算法1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的樣本模式第五章聚類(lèi)分析⒍對(duì)每一聚類(lèi)域，取樣本的平均作為新的聚類(lèi)中心。

5.2.2小中取大距離算法第五章聚類(lèi)分析算法討論：本算法相當(dāng)于最近鄰試探法的改進(jìn)，但仍受到z1的選擇、θ的大小的影響，對(duì)于幾何分布集群性比較好的分類(lèi)問(wèn)題，效果較好。5.2.2小中取大距離算法第五章聚類(lèi)分析5.2.3分級(jí)聚類(lèi)方法(層次聚類(lèi)法)

由于聚類(lèi)分析只是把N個(gè)沒(méi)有類(lèi)別標(biāo)簽的樣本分成一些合理的類(lèi)，在極端的情況下，最多可分為N類(lèi)，最少只有一個(gè)類(lèi)，因此可以把問(wèn)題看成是將N個(gè)樣本劃分成c個(gè)類(lèi)的劃分序列。第一個(gè)劃分是把樣本分成N個(gè)類(lèi)，每類(lèi)包含一個(gè)樣本；第二個(gè)劃分是把樣本分成N－1個(gè)類(lèi)；下一個(gè)劃分是把樣本分成N－2個(gè)類(lèi)等等，直到第N個(gè)劃分時(shí)，把樣本僅分成一個(gè)類(lèi)。5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析如果類(lèi)數(shù)c=N－K+l，則稱(chēng)這個(gè)劃分處于K水平。例如1水平就相當(dāng)于分成N類(lèi)，N水平就相當(dāng)于把所有樣本歸為1類(lèi)。任何兩個(gè)樣本xi和xj總會(huì)在某一水平被分為同一類(lèi)。5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析分級(jí)聚類(lèi)就是這樣一種劃分序列。這種劃分序列具有如下的性質(zhì)：只要在K水平時(shí)樣本被歸入同一類(lèi)后，在進(jìn)行更高水平的劃分時(shí)，它們也永遠(yuǎn)屬于同一類(lèi)。

生物分類(lèi)就是分級(jí)聚類(lèi)的一個(gè)例子。先是把許多個(gè)體集合成種，然后種集合成類(lèi)，類(lèi)集合成族等等。如生物界=動(dòng)物，門(mén)=脊索動(dòng)物類(lèi)，綱=脊椎動(dòng)物，類(lèi)=魚(yú)類(lèi)，子類(lèi)=鰭類(lèi)，目=鮭魚(yú)類(lèi)，科=鮭魚(yú)，等等。5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析分級(jí)聚類(lèi)方法的最自然的表示就是樹(shù)。5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析另一種表達(dá)分級(jí)聚類(lèi)的方法是集合，每個(gè)層次上的類(lèi)都可能含有子類(lèi)集合，如圖所示。純符號(hào)的表示方法，如{{x1，{x2，x3}}，{{x4，x5}，{x6，x7}}，x8}}。這些方法雖能夠表達(dá)層次關(guān)系，但無(wú)法定量地體現(xiàn)相似性。樹(shù)圖是較好的方法。5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析層次聚類(lèi)可以通過(guò)合并(agglomerative)和分裂(divisive)兩種方法實(shí)現(xiàn)。合并（自低向上）時(shí)，每個(gè)樣本各成一類(lèi)，通過(guò)合并不同的類(lèi)，減少類(lèi)別數(shù)目。分裂（自頂向下）時(shí)，所有樣本先歸入一類(lèi)，通過(guò)后續(xù)分裂，增加類(lèi)別數(shù)目。下面主要介紹合并的方法。5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析基于合并的分級(jí)聚類(lèi)方法對(duì)于N個(gè)d維未知樣本，其算法步驟為：⒈設(shè)初始的類(lèi)別數(shù)，X={xi}，i=1，2，…，N。計(jì)算類(lèi)間相似性度量距離矩陣D0，D0是xi間的兩兩距離矩陣。⒉找出最相似的兩類(lèi)(相似性度量距離最小)，假設(shè)為Xh，Xk，將其合并，Xj={Xh，Xk}。

5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析⒊計(jì)算合并后的類(lèi)別之間的相似性程度的度量距離矩陣Dl。⒋若給定的類(lèi)別數(shù)是c，，算法結(jié)束。①，算法結(jié)束。若沒(méi)有給定類(lèi)別數(shù)c，則②設(shè)定閾值T，當(dāng)兩類(lèi)之間最小距離＞T時(shí)，算法結(jié)束。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析討論類(lèi)間相似性度量的方法，假定每個(gè)樣本之間用歐氏距離：⒈最近距離屬于近鄰算法，適用于類(lèi)間分布較散，鏈狀聚合。如果Xj={Xh，Xk}，即Xj是由Xh、Xk合并的。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析假設(shè)有三種如圖5.7所示的兩維點(diǎn)集(a)、(b)、(c)。(a)(b)(c)圖5.7在用最近距離作為相似性度量進(jìn)行聚類(lèi)時(shí)，若類(lèi)別數(shù)等于2，則各點(diǎn)集的相應(yīng)聚類(lèi)結(jié)果如圖5.8所示。

----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析(a)(a)----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析(b)(b)----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析(c)(c)----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析圖5.7(a)和(b)點(diǎn)集的唯一差別是(b)中出現(xiàn)了兩個(gè)干擾點(diǎn)。從圖5.8(b)中可見(jiàn)，這種相似性度量的缺點(diǎn)是只要在兩個(gè)各自密集的點(diǎn)集之間存在一些位置互相靠近的點(diǎn)的路徑，那么就很可能會(huì)把兩個(gè)密集的點(diǎn)集(本應(yīng)分屬于兩類(lèi)的點(diǎn)集)聚集成一個(gè)類(lèi)。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析從圖可見(jiàn)，當(dāng)最終類(lèi)別數(shù)為1時(shí)，以最近距離作為相似性度量進(jìn)行樣本點(diǎn)聚類(lèi)的過(guò)程就是一棵最小生成樹(shù)形成的過(guò)程。因此這是一種最小生成樹(shù)算法。如果給出了最小生成樹(shù)，可以根據(jù)它得到最近鄰的聚類(lèi)結(jié)果。只要把最小生成樹(shù)中長(zhǎng)度(距離)最大的一支去掉就得到2類(lèi)的聚類(lèi)結(jié)果，去掉第二長(zhǎng)的分支，數(shù)據(jù)就分為3類(lèi)，如此繼續(xù)下去，就導(dǎo)出了基于分裂的層次聚類(lèi)方法。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析⒉最遠(yuǎn)距離屬于近鄰算法，適用于團(tuán)狀集群。取其中dmax最大的一對(duì)合并。如Xj

={Xh，Xk}，dmax(Xi，Xj)=max{dmax(Xi，Xh)，dmax(Xi，Xk)}----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析在用最遠(yuǎn)距離作為相似性度量時(shí)，可以把聚類(lèi)算法看成是產(chǎn)生一個(gè)圖，圖中同一個(gè)類(lèi)的結(jié)點(diǎn)都是用棱線聯(lián)結(jié)起來(lái)的。用圖論的術(shù)語(yǔ)來(lái)說(shuō)就是每個(gè)類(lèi)構(gòu)成一個(gè)完備子圖。兩個(gè)類(lèi)之間的距離現(xiàn)在是由這兩個(gè)類(lèi)中相距最遠(yuǎn)的結(jié)點(diǎn)來(lái)確定的，對(duì)于圖5.7的三種點(diǎn)集，當(dāng)類(lèi)別數(shù)等于2時(shí)，其相應(yīng)的聚類(lèi)結(jié)果見(jiàn)圖5.9。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析(a)(a)----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析從圖(b)可見(jiàn)，它防止了兩個(gè)密集點(diǎn)集通過(guò)某個(gè)路徑聚為一類(lèi)的可能性。(b)(b)----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析圖(c)的結(jié)果則說(shuō)明了這種相似性度量不能檢出具有長(zhǎng)條形狀的聚類(lèi)。(c)(c)顯然，這種度量將使個(gè)別的遠(yuǎn)離點(diǎn)對(duì)聚類(lèi)結(jié)果產(chǎn)生十分大的影響。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析⒊均值距離

這種相似性度量的效果介于上述兩者之間。中心距離適用于球狀、近似球狀分布。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析例5.1：c=2，N=5，n=2，X={x1=(0,1)T，x2=(7,5)T，x3=(2,2)T，x4=(1,1)T，x5=(5,5)T}。試用分級(jí)聚類(lèi)方法進(jìn)行分類(lèi)。樣本集如圖5.10所示。圖5.1012345678x1x2011023456x2x19x3x4x5----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析解：采用。②l=2，，dmean(X2，X5)最小。則X2={X2，X5}={x2，x5}，，算法結(jié)束。①，l=0，dmean=(X1，X4)最小，X1={X1，X4}={x1，x4}，……X1={x1，x3，x4}，X2={x2，x5}。----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析算法討論：適用于樣本總數(shù)不太多情況。若類(lèi)別數(shù)c未知，受閾值T影響。采用不同相似性度量，會(huì)影響聚類(lèi)結(jié)果。實(shí)際上，可以多選幾種距離度量來(lái)試驗(yàn)。

----基于合并的分級(jí)聚類(lèi)方法5.2.3分級(jí)聚類(lèi)方法第五章聚類(lèi)分析5.2.4k-均值算法和ISODATA算法(動(dòng)態(tài)聚類(lèi)方法)

動(dòng)態(tài)聚類(lèi)方法是一種普遍采用的方法，它具有以下三個(gè)要點(diǎn)：⒈選定某種距離度量作為樣本間的相似性度量。⒉確定某個(gè)評(píng)價(jià)聚類(lèi)結(jié)果質(zhì)量的準(zhǔn)則函數(shù)。⒊給定某個(gè)初始分類(lèi)，然后用迭代算法找出使準(zhǔn)則函數(shù)取極值的最好聚類(lèi)結(jié)果。先討論在誤差平方和準(zhǔn)則基礎(chǔ)上的k-均值算法，然后結(jié)合對(duì)這算法的分析給出一些其它的動(dòng)態(tài)聚類(lèi)算法。第五章聚類(lèi)分析5.2.4k-均值算法和ISODATA算法k-均值算法使聚類(lèi)域中所有樣本到聚類(lèi)中心的距離平方和最小，這是在誤差平方和準(zhǔn)則的基礎(chǔ)上得來(lái)的。k是類(lèi)別數(shù)，已知或任選。相似性度量采用歐氏距離。分類(lèi)準(zhǔn)則采用平方誤差和準(zhǔn)則。

一、k-(或c)均值算法(k-meanAlgorithm)第五章聚類(lèi)分析準(zhǔn)則函數(shù)：

zi是第i類(lèi)的聚類(lèi)中心。樣本集X={x1，x2，…，xN}xi是d維特征向量。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈠算法步驟：⒈任意選擇k個(gè)初始聚類(lèi)中心，z1(1)，z2(1)，…，zk(1)作為初始聚類(lèi)中心。⒉第l次迭代，將待分類(lèi)的N個(gè)樣本按最小距離原則分配到k個(gè)聚類(lèi)中，對(duì)待識(shí)別樣本x，若||x-zj(l)||＜||x-zi(l)||，式中j=1，2，…，k，i≠j，則x∈Xj(l)，Xi(l)是聚類(lèi)中心為zi(l)的樣本集。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈠算法步驟：⒊由第2步結(jié)果，計(jì)算新的聚類(lèi)中心。，i=1，2，…，k

這樣使Xi(l)中的所有樣本點(diǎn)到新的聚類(lèi)中心的距離平方和準(zhǔn)則函數(shù)，i=1，2，…，k最小。

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈠算法步驟：⒋若zi(l+1)=zi(l)，i=1，2，…，k，算法收斂，則檢驗(yàn)J是否最小，并結(jié)束。若zi(l+1)≠zi(l)，令l=l+1，轉(zhuǎn)2，經(jīng)過(guò)多次迭代M次(自己設(shè)定)，停機(jī)，修改參數(shù)，重新計(jì)算或取最小J情況下的聚類(lèi)輸出。

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡算法討論⒈收斂問(wèn)題尚無(wú)證明收斂問(wèn)題與幾何分布有關(guān)，樣本各類(lèi)有類(lèi)超球體分布，各類(lèi)容積相近，易收斂；收斂與否，與k=1時(shí)的z1~zk的選擇有關(guān)，選的好，有可能收斂，否則不然，故要試探。⒉初始聚類(lèi)中心z(1)的選擇①憑先驗(yàn)知識(shí)，將樣本集大致分類(lèi)，取代表點(diǎn)。②將全部樣本人為地分k類(lèi)，取代表點(diǎn)(均值)。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡算法討論③密度法：以每個(gè)樣本為中心，定義某個(gè)正數(shù)r為半徑，在球內(nèi)落入的點(diǎn)的個(gè)數(shù)作為密度，取最大密度點(diǎn)為z1，然后再找出與z1的距離＞r的次大密度做新的聚類(lèi)中心，依次選定。④選擇給定樣本集的前k個(gè)樣本做聚類(lèi)中心。⑤從(k-1)聚類(lèi)劃分解中，產(chǎn)生k類(lèi)劃分代表點(diǎn)。⒊k的確定可采用試探法，令k=2，3，4…，對(duì)應(yīng)算出準(zhǔn)則函數(shù)J做曲線，一般k↑→J↓，k=N，J=0。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡算法討論當(dāng)J下降變慢時(shí)，對(duì)應(yīng)的k較為合適，如果分不清J下降快慢的界限，則應(yīng)試探進(jìn)行。1234567…NkJ0圖5.11如圖5.11所示，從5~6下降較小，認(rèn)為5較合適。故k=5。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析例5.2如圖5.12給出20個(gè)二維的樣本，用k均值算法進(jìn)行聚類(lèi)。

圖5.12k均值算法所用的樣本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x205.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析解：⒈令k=2，選擇z1(1)=x1=(0,0)T，z2(1)=x2(1,0)T。⒉因?yàn)閨|x1-z1(1)||＜||x1-zi(1)||和||x3-z1(1)||＜||x1-zi(1)||，i=2，所以X1(1)={x1，x3}，N1=2。同樣剩余的樣本接近于z2(1)，因此，X2(1)={x2，x4，x5，…，x20}，N2=18。⒊更新聚類(lèi)中心圖5.12k均值算法所用的樣本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20例5.2如圖5.12給出20個(gè)二維的樣本，用k均值算法進(jìn)行聚類(lèi)。

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析例5.2如圖5.12給出20個(gè)二維的樣本，用k均值算法進(jìn)行聚類(lèi)。

5.2.4k-均值算法和ISODATA算法圖5.12k均值算法所用的樣本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20第五章聚類(lèi)分析⒋因?yàn)閦j(2)≠zj(1)，j=1，2，轉(zhuǎn)到第二步。⒌因?yàn)閨|xl-z1(2)||＜||xl–z2(2)||，l=1，2，…，8，所以X1(2)={x1，x2，x3,…，x8}，N1=8。又因?yàn)閨|xl–z2(2)||＜||xl–z1(1)||，l=9，10，11，…，20，因此，X2(2)={x9，x10，x11，…，x20}，N2=12。

⒍更新聚類(lèi)中心例5.2如圖5.12給出20個(gè)二維的樣本，用k均值算法進(jìn)行聚類(lèi)。

5.2.4k-均值算法和ISODATA算法圖5.12k均值算法所用的樣本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20第五章聚類(lèi)分析例5.2如圖5.12給出20個(gè)二維的樣本，用k均值算法進(jìn)行聚類(lèi)。

5.2.4k-均值算法和ISODATA算法圖5.12k均值算法所用的樣本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20第五章聚類(lèi)分析⒎因?yàn)閦j(3)≠zj(2)，j=1，2，轉(zhuǎn)到第二步。⒏與前面一次迭代產(chǎn)生同樣的結(jié)果，X1(4)=X1(3)，X2(4)=X2(3)。⒐也產(chǎn)生同樣的結(jié)果。⒑因?yàn)閦j(4)=zj(3)，j=1，2，故算法收斂。產(chǎn)生的聚類(lèi)中心為例5.2如圖5.12給出20個(gè)二維的樣本，用k均值算法進(jìn)行聚類(lèi)。

5.2.4k-均值算法和ISODATA算法圖5.12k均值算法所用的樣本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20第五章聚類(lèi)分析結(jié)果與觀察給定模式所得的結(jié)果是相符的。

例5.2如圖5.12給出20個(gè)二維的樣本，用k均值算法進(jìn)行聚類(lèi)。

5.2.4k-均值算法和ISODATA算法圖5.12k均值算法所用的樣本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20第五章聚類(lèi)分析二、ISODATA算法ISODATA算法(IterativeSelf-organizingDataAnalysisTechniquesA迭代自組織數(shù)據(jù)分析技術(shù))在k-均值算法基礎(chǔ)上，在迭代過(guò)程中增加了某種產(chǎn)生和消除某些類(lèi)別的方法，具有自動(dòng)合并和分裂類(lèi)，自動(dòng)尋找類(lèi)別數(shù)k的功能。在每一次迭代時(shí)，首先，在不改變類(lèi)別數(shù)目的前提下來(lái)改變分類(lèi)，然后，將樣本平均矢量之差小于某一預(yù)定閾值的每一類(lèi)別對(duì)合并起來(lái)，或根據(jù)樣本協(xié)方差矩陣來(lái)決定其分裂與否，一次一次地迭代，并不斷地進(jìn)行合并和分開(kāi)，這種算法具有人機(jī)交互和啟發(fā)式的特點(diǎn)。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈠

算法參數(shù)

k—要找的聚類(lèi)中心數(shù)；θN

—每一類(lèi)中至少應(yīng)具有的樣本個(gè)數(shù)（少于此值的樣本點(diǎn)集去掉）；θs—類(lèi)內(nèi)的樣本標(biāo)準(zhǔn)差閾值（判別類(lèi)是否太大，若太大分2類(lèi)），取總體分布各個(gè)特征分量軸上標(biāo)準(zhǔn)差σi，取其一部分用ασi表示，0<α<1，i=1，2，…，N；5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈠

算法參數(shù)

L—一次迭代運(yùn)算中可合并的最多對(duì)數(shù)（一般取一對(duì)）；

I—允許迭代的次數(shù)（相當(dāng)于k-均值算法中的M）；θc

—兩類(lèi)中心距的最小距離（＜θc，可合并）。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟基本步驟：

⑴初始化，任意選定c個(gè)聚類(lèi)中心，z1(1)，z2(1)，…，zc(1)，定義算法參數(shù)，k，θN，θs，θc，L，I。

⑵分配N(xiāo)個(gè)樣本到c類(lèi)中，按最近鄰原則計(jì)算，若||x-zi||<||x-zj|，i=1，2，…，c，i≠j，則x∈Xi，其中Xi表示分到聚類(lèi)中心zi的樣本子集，Ni為Xi中的樣本數(shù)。⑶若對(duì)任意的i，Ni<θN，則去除Xi，并使c=c-1，即將樣本數(shù)比θN少的樣本子集去除。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟以下三步計(jì)算距離：⑷修正聚類(lèi)中心zi，，i=1，2，…，c

⑸計(jì)算Xi中樣本與其對(duì)應(yīng)的中心的平均距離，i=1，2，…，c

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟⑹計(jì)算總體的平均距離

其中N為樣本集中的樣本總數(shù)。⑺判斷：①若是最后一次迭代，l=I，置θc

=0，轉(zhuǎn)⑾步算法結(jié)束。②若，直接轉(zhuǎn)到第⑻步，分裂類(lèi)操作。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟③若c≥2k，直接轉(zhuǎn)到⑾步，合并類(lèi)操作。④若②、③類(lèi)不滿(mǎn)足，繼續(xù)。⑻計(jì)算標(biāo)準(zhǔn)差σij

其中d是樣本模式的維數(shù)，xkj是Xj中第k個(gè)樣本的第j個(gè)分量，zij是zi的第j個(gè)分量。j=1，2，…，d；

i=1，2，…，c

的每個(gè)分量表示Xi中樣本沿主要坐標(biāo)軸的標(biāo)準(zhǔn)差。

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟⑽如果σimax>θs，i=1，2，…，c，同時(shí)滿(mǎn)足以下條件之一：⑼找出中的最大分量，i=1，2，…，c。

①且(樣本數(shù)不能太小)；②則將Xi分成兩類(lèi)，出現(xiàn)兩個(gè)新的聚類(lèi)中心和，刪去，并使c=c+1。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟對(duì)應(yīng)于的的分量上加上一個(gè)給定量，而的其它分量保持不變來(lái)構(gòu)成，對(duì)應(yīng)于的的分量上減去，而的其它分量保持不變來(lái)構(gòu)成。規(guī)定是的一部分，，。

選擇的基本要求是，使任意樣本到這兩個(gè)新的聚類(lèi)中心和之間有一個(gè)足夠可檢測(cè)的距離差別，被區(qū)別并能完全將Xi分到和中。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟如果完成分裂，迭代次數(shù)加1，l=l+1。轉(zhuǎn)⑵。否則繼續(xù)進(jìn)行⑾。以下三步為合并：⑾計(jì)算全部的聚類(lèi)中心的兩兩距離dij

dij=||zi-zj||，i≠j，i，j=1，2，…，c

⑿比較：如果dij≥θc，轉(zhuǎn)到第⒁步，否則如果dij<θc，把當(dāng)前L對(duì)聚類(lèi)中心排序，[di1j1，di2j2，…，diLjL]其中di1j1<di2j2<…<diLjL。

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟⒀從di1j1開(kāi)始，逐對(duì)合并，算出新的聚類(lèi)中心：刪去zil和zjl，并使c=c－1。注意：只允許一對(duì)對(duì)合并，并且一個(gè)聚類(lèi)中心只能合并一次。l=1，2，…，L

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡

算法步驟⒁迭代處理：如果是最后一次迭代，l=I，或zi(l+1)=zi(l)，算法結(jié)束。輸出

c個(gè)類(lèi)別：{Xi}，{zi}，i=1，2，…，c。否則①l=l+1，轉(zhuǎn)⑵，不修改參數(shù)(可能l<I)。②人工參與修改參數(shù)l=l+1，轉(zhuǎn)⑴。每次回到算法的第一步或第二步就計(jì)為一次迭代。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析例5.3：如圖5.13所示8個(gè)二維的樣本模式，用ISODATA算法進(jìn)行聚類(lèi)。1123456782345678x1x20x1x2x3x4x5x6x7x8圖5.13ISODATA算法所用的樣本模式5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析解：假設(shè)初始聚類(lèi)中心數(shù)c=1，z1=x1=(0,0)T。㈠第一次迭代⑴規(guī)定算法的參數(shù)：k=2，θN=1，θs=1，θc=4，L=0，I=4。若分析的模式中無(wú)法得到先驗(yàn)信息，則任意選擇這些參數(shù)，然后通過(guò)算法在逐次迭代中進(jìn)行調(diào)整。⑵因?yàn)橹挥幸粋€(gè)聚類(lèi)中心z1，所以X1={x1，x2，…，x8}，N1=8。

5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析⑶由于N1>θN，故無(wú)子類(lèi)要去除。⑷更新聚類(lèi)中心z1⑹計(jì)算，此時(shí)。⑸計(jì)算：⑺因?yàn)檫@不是最后一次迭代且，(k=2，c=1)，所以轉(zhuǎn)第八步。⑻找X1的標(biāo)準(zhǔn)差5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析⑼取的最大值。

⑽因，，則z1分裂成兩個(gè)新的聚類(lèi)中心。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈡第二次迭代⑴將樣本模式重新分配給z1和z2的聚類(lèi)域，現(xiàn)在樣本集為：X1={x4，x5，x6，x7，x8}，X2={x1，x2，x3}，N1=5，N2=3令，則為方便起見(jiàn)，令，分別為z1和z2，c=c+1=2，轉(zhuǎn)第二步I=I+1=2。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析⑶更新聚類(lèi)中心⑷計(jì)算，i=1，2⑸計(jì)算，

5.2.4k-均值算法和ISODATA算法⑵因?yàn)镹1>θN和N2>θN，故無(wú)子集要去除。第五章聚類(lèi)分析⑹因I=2，是偶次迭代，轉(zhuǎn)第十一步。⑺計(jì)算兩兩距離D12：D12=||z1-z2||=4.72⑻D12>θc(θc=4)。⑼由上步結(jié)果表明無(wú)歸并。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析⑽因?yàn)椴皇亲詈笠淮蔚?，所以需要作出是轉(zhuǎn)到第一步還是轉(zhuǎn)到第二步的判別。此例中：①已得到k=2的聚類(lèi)數(shù)；②其可分性比由標(biāo)準(zhǔn)差所指出的平均散布大；③每一個(gè)聚類(lèi)中包括一定量的樣本總數(shù)，因此得出的聚類(lèi)中心z1和z2

具有代表性。下一次迭代不需要更改算法參數(shù)，于是轉(zhuǎn)到第二步，I=3。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析㈢第三次迭代⑴第二步和第六步，象上次迭代一樣，產(chǎn)生同樣的結(jié)果。⑵沒(méi)有滿(mǎn)足條件，繼續(xù)進(jìn)行計(jì)算。⑶計(jì)算X1和X2的標(biāo)準(zhǔn)差：5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析⑹得到與上次迭代時(shí)相同的結(jié)果：D12=||z1-z2||=4.72⑺得到與上次迭代時(shí)相同的結(jié)果。⑷這里和。

⑸，，不滿(mǎn)足分裂條件，繼續(xù)計(jì)算。5.2.4k-均值算法和ISODATA算法第五章聚類(lèi)分析⑻無(wú)歸并。⑼除標(biāo)準(zhǔn)差計(jì)算外，在這次迭代中，無(wú)新的增加，轉(zhuǎn)到第二步，I=4。㈣第四次迭代⑴第二步和第六步，象上次迭代一樣，產(chǎn)生同樣的結(jié)果。⑵因是最后一次迭代，置θc=0，轉(zhuǎn)第十一步。⑶D12=4.72⑷同樣的結(jié)果。⑸無(wú)歸并發(fā)生。⑹因I=4是最