4．2．1　k均值分類

k均值算法能使聚類域中所有樣本到聚類中心的距離平方和最小。其主要步驟如下:

第一步:任選k個(gè)初始聚類中心:(上角標(biāo)記載為尋找聚類中的迭代運(yùn)算次數(shù))。用數(shù)組classp［6*clsnumber］來存儲(chǔ)類中心的值，一般可選定樣品集的前k個(gè)樣品作為初始聚類中心。但是考慮到這樣做不太有利于后面的算法收斂。因此采用了最大最小距離選心法。該法的原則是使各初始類別之間，盡可能地保持遠(yuǎn)離。

任意選取50個(gè)初始中心，將其值存入iGrayValue［6*50］中，將第一個(gè)點(diǎn)X₁作為第一個(gè)初始類別的中心Z₁。

計(jì)算X₁與其他各抽樣點(diǎn)的距離D。取與之距離最遠(yuǎn)的那個(gè)抽樣點(diǎn)(例如X₇)為第二個(gè)初始類別中心Z₂，則第二個(gè)初始類中心Z₂=X₇。

對(duì)剩余的每個(gè)抽樣點(diǎn)，計(jì)算它到已有各初始類別中心的距離D_ij(i，j=1，2，…，已知有初始類別數(shù)m)，并取其中的最小距離作為該點(diǎn)的代表距離D_j:

D_j=min(D_1j，D_2j，…，D_mj)

在此基礎(chǔ)上，再對(duì)所有各剩余點(diǎn)的最小距離D_j進(jìn)行相互比較，取其中最大者，并選擇與該最大的最小距離相應(yīng)的抽樣點(diǎn)(如X₁₁)作為新的初始類中心點(diǎn)，即Z₃=X₁₁，此時(shí)m=m+1。

如此迭代直到m≥clsnumber，即m=0，1，2，…，clsnumber。

第三步:計(jì)算各聚類中心的新向量值classo［i］;

式中:n_j為S_j中所包含的樣品數(shù);classo1［i］表示所有屬于第i類的像素的值的累加;NL［i］表示屬于第i類的像素總數(shù);classo［i］為重新分類后的聚類中心值。

因?yàn)樵谶@一步要計(jì)算k個(gè)聚類中心的樣品均值，故稱為k均值算法。

就可以結(jié)束算法。

k均值算法的特點(diǎn)是:k均值算法的結(jié)果受到所選聚類中心的個(gè)數(shù)k及初始聚類中心選擇的影響，也受到樣品的幾何性質(zhì)及排列次序的影響。實(shí)際上，需試探不同的k值和選擇不同的初始聚類中心。如果樣品的幾何特性表明它們能形成幾個(gè)相距較遠(yuǎn)的小塊孤立區(qū)，則算法多能收斂。圖4-2給出聚類類別數(shù)為5、最大改變閾值為5、最大迭代次數(shù)為5時(shí)的k均值分類效果圖。

圖4-2　k均值分類算法效果圖