簡述isodata算法的原理_ISODATA算法的實作與分析

摘要：ISODATA算法是目前應用比較廣泛的，通過引入參數而進行人機互動不斷進行分裂與合并的非監督分類算法。本文介紹了ISODATA基本原理與具體實作的過程，并用對參數設定的影響進行了試驗和分析。

關鍵詞：ISODATA 非監督分類 算法 模式識别

一、原理介紹

Isodata，疊代自組織分析，通過設定初始參數而引入人機對話環節，并使用歸并與分裂的機制，當某兩類聚類中心距離小于某一門檻值時，将它們合并為一類，當某類标準差大于某一門檻值或其樣本數目超過某一門檻值時，将其分為兩類。在某類樣本數目少于某門檻值時，需将其取消。如此，根據初始聚類中心和設定的類别數目等參數疊代，最終得到一個比較理想的分類結果。

二、算法設計

第一步：将 個模式樣本{ ,i=1,2,3,…,

}讀入，确定C個初始聚類中心和6個初始參數(K，θN，θc，θs，L，I)。

第二步：将N個模式樣本分給最近的聚類，假如Dj=min(‖x-zj‖,i=1,2,…,), 即‖x-zj‖的距離最小，則x∈Sj。

第三步：如果Sj中的樣本數Nj

第四步：修正聚類中心值

j=1,2,…,

第五步：計算各聚類域Sj中諸聚類中心間的平均距離：

第六步：計算全部模式樣本對其相應聚類中心的總平均距離：

第七步：判别分裂、合并及疊代運算等步驟：

①如疊代運算次數已達I次，即最後一次疊代，置θc = 0,跳到第十一步，運算結束。

②如≤K/2，即聚類中心的數目等于或不到規定值的一半，則進入第八步，将已有的聚類分裂。

③如疊代運算的次數是偶次，或≥2K，不進行分裂處理，跳到第十一步；如不符合以上兩個條件(即既

不是偶次疊代，也不是≥2K)，則進入第八步，進行分裂處理。

分裂處理：

第八步：計算聚類樣本距離的标準差向量：

第九步：求每一标準差向量{，σj=1,2, …，}中的最大分量，以{σj=1,2, …，}代表。

第十步：在任一最大分量集{σj=1,2,

…，}中，如有>θS(該值給定)，同時又滿足以下二條件中之一：

(a) ，即Sj中樣本總數超過規定值一倍以上，

(b)Nc≤K/2，

則将Zj分裂為兩個新的聚類中心 ,且類别數加1。 中相當于 的分量，可加上k* σjmax，其中k=0.5； 中相當于

的分量，可減去k*σjmax。如果本步完成了分裂運算，則跳回第二步；否則，繼續。

第十一步：計算全部聚類中心的距離：

,i=1,2, …, -1

j=i+1, …,

第十二步：比較 與θc值，将

{ , , …, }

式中， < < …< 。

第十三步：如将距離為Di1j1的兩個聚類中心zi1和zj1合并，得新中心為

l=1,2,…，L

式中，被合并的兩個聚類中心向量，分别以其聚類域内的樣本數權重，使 為真正的平均向量。

第十四步：如果是最後一次疊代運算(即第I次)，算法結束。否則GOTO第一步——如果需由操作者改變輸入參數；或GOTO第二步——如果輸入參數不變。

三、實作方法與過程

1．過程：

(1)該算法需要設定的六個參數為：

K：所想要分成的類别數

θN：一個類别至少應該具有的類别數

θc：聚類中心之間距離的最小值

θs：一個類别中樣本标準差最大值

L：每次疊代最多可歸并對數

I：最大疊代次數

六個參數預設值為ENVI軟體上預設值(K為5，θN為1，θs為0.01，θc為5，I為7，L為1)，另設對話框可改變參數。

(2)讀入三個波段的bmp影像，其中每個像素即為一個樣本，每個波段灰階即為一個特征值。樣本數為影像的高度乘以寬度。采用連結清單記錄聚類中心，初始聚類中心設為一類，取第一個像素。

(3)動态申請記憶體儲存對應标号像素目前屬于的類别号和每類中樣本數，标準差向量，距離等。疊代次數加一。

(4)根據馬氏距離按最小距離準則，将像素劃分到距其聚類中心最近的一類，将其類别号存入對應數組中。

(5)循環檢查每個類别中樣本數目是否少于θs，如果是，則将此聚類中心删除，并重新做一次分類；否則繼續往下進行。

(6)統計每一類中像素灰階的平均值，作為修正後的聚類中心存傳入連結表。

(7)計算每類中樣本到聚類中心距離的平均值和所有樣本到相應聚類中心距離的平均值，存入數組。

(8)判斷：如果目前疊代次數已到達I次，置θc為0，轉入合并，結束。

否則如果目前類别數大于等于2*K或目前疊代次數為偶數，進入合并，否則進入分裂步驟。

(9)按照算法進行判斷，如果合符條件，則進行分裂，并跳入第三步，否則往下進行。

(10)計算每兩類聚類中心間距離，并記錄下其類别編号，然後對聚類中心進行排序(此過程中記錄編号的數組也要跟着一起變動)。記錄其小于θc對數nL，如nL大于L，則置nL等于L，然後從數組中取nL對類進行合并。

(11)如果是最後一次疊代，結束，按照類别等級賦予不同灰階寫成bmp檔案；否則，跳至第三步。

2.流程圖

輸入參數

按最小距離分類

修正聚類中心，計算距離

最後一次

偶數次疊代

分裂運算

合并運算

最後一次

Θc=0

是

否

是

否

是

否

完成

不完成

完成

否

是

四、實驗與分析

按照初始參數得到三個波段分類影像：

實驗1一個波段分類影像：

分析：一個波段特征太少，隻能勉強将長江分出來，其他的地方效果都不明顯。

實驗2(改變疊代次數)：

疊代8次影像：

疊代9次：

疊代10次：

分析：從圖中可以看出，随着疊代次數的增加，圖中地物分得越來越細，直到第10次疊代水庫才與居民區分開。但是疊代次數增加的影響，應該是跟我設定的其他參數相關的，因為此次設定的θs比較小(0.01)，是以随着疊代次數增加分裂不斷進行。疊代次數太小往往沒有将分類進行完全，但設定太多又浪費資源和時間。

實驗3(修改K)：

分類7類影像：

分為8類影像：

分為9類影像：

分析：從圖中可以看出，長江與水庫，居民區被合并了，K的修改最大的影響應該在第7步判斷分裂合并的時候，K增大應該會促使分裂的進行。但是圖上的結果，隻有長江上遊有顆粒出現，由此可見，盲目地增加類别數并不會增強分類效果。

實驗4(修改θs):

Θs=0.009:

Θs=0.1

Θs=0.7：

Θs=0.9:

Θs=1:

改變θc為4(初始值為5)：

分析：θs的增大，應該會減少分裂的趨勢(從θs為0.009到0.01)，但是當θs從0.01往後加，卻并沒有對分類結果産生影響，而且将θc改為4和6時也沒有多大變化，是以，這些參數的改變産生的作用，往往不是由這一個參數而決定，而取決于跟其他參數作為一個整體産生的效果。

五、結束語

遙感分類，雖然出現了很多算法，但是從Isodata的算法看起來效果仍然不盡如人意，即使用很多國際上的知名軟體，也未必取得一個很滿意的效果，原因是影響分類效果的因素太複雜了，而且分類隻能以圖像所獲得的灰階為依據，這個灰階是否準确，以及是否可以考慮像素之間的關系，或者從另一個角度來解譯圖像(比如頻域)，都是可以考慮的問題。

參考文獻

【1】 曾江源 《ISODATA算法的原理與實作》

【2】 楊曉明 羅雲 《ISODATA算法的實作與分析》

【3】 萬建 王建成 《基于ISODATA的彩色圖像分割》