ISODATA算法是在 k-均值算法 的基礎上,增加對聚類結果的'合并'和'分裂'兩個操作,并

設定算法運行控制參數的一種聚類算法. 全稱:Iterative Selforganizing Data Analysis Techniques Algorithm 即:迭代自組織數據分析算法 '合并'操作:當聚類結果某一類中樣本數太少,或兩個類間的距離太近時,進行合并. '分裂'操作:當聚類結果某一類中樣本某個特征類內方差太大,將該類進行分裂

算法特點

使用誤差平方和作為基本聚類準則 設定指標參數來決定是否進行'合并'或'分裂' 設定算法控制參數來決定算法的運算次數 具有自動調節最優類別數k的能力 算法規則明確,便于計算機實現

算法思想

Isodata,迭代自組織分析,通過設定初始參數而引入人機對話環節,并使用歸并與分裂

的機制,當某兩類聚類中心距離小于某一閾值時,將它們合并為一類,當某類標準差大于

某一閾值或其樣本數目超過某一閾值時,將其分為兩類.在某類樣本數目少于某閾值時,

需將其取消.如此,根據初始聚類中心和設定的類別數目等參數迭代,最終得到一個比較

理想的分類結果.

算法步驟

算法步驟如下: ①初始化 ?設定控制參數: ??c:預期的類數; ??Nc:初始聚類中心個數(可以不等于c); ??TN:每一類中允許的最少樣本數目(若少于此數,就不能單獨成為一類

); ??TE:類內各特征分量分布的相對標準差上限(大于此數就分裂); ??TC:兩類中心間的最小距離下限(若小于此數,這兩類應合并); ??NT:在每次迭代中最多可以進行'合并'操作的次數; ??NS:允許的最多迭代次數. ??選定初始聚類中心 ②按最近鄰規則將樣本集{xi}中每個樣本分到某一類中 ③依據TN判斷合并:如果類ωj中樣本數nj< TN,則取消該類的中心zj,Nc=Nc-1,轉至② . ④計算分類后的參數:各類重心:類內平均距離及總體平均距離 ⑤判斷停止:分裂或合并. ?a:若迭代次數Ip =NS,則算法結束; ?b:若Nc ≤c/2,則轉到⑥ (將一些類分裂); ?c:若Nc ≥2c,則轉至⑦ (跳過分裂處理); ?d:若c/2< Nc<2c,當迭代次數Ip是奇數時轉至⑥ (分裂處理);迭代次數Ip是偶

數時轉至⑦ (合并處理). ⑥分裂操作 ?計算各類內樣本到類中心的標準差向量 σj=(σ1j, σ2j,…., σnj)T , j=1,2,…

..,Nc ?計算其各個分量. ?求出每一類內標準差向量σj中的最大分量 ?若有某一類中最大分量大于TE,同時又滿足下面兩個條件之一則將該類ωj分裂

為兩個類,原zj取消且令Nc=Nc+1. ?兩個新類的中心zj+和zj-分別是在原zj中相應于的分量加上和減去,而起它分

量不變,其中0<k≤1. ?分裂后,Ip=Ip+1, 轉至②. ⑦合并操作 ?計算各類中心間的距離Dij,i=1,2,…,Nc-1; j=1,2,…,Nc ?依據TC判斷合并.將Dij與TC比較,并將小于TC的那些Dij按遞增次序排列,取前

NT個. ?從最小的Dij開始,將相應的兩類合并,并計算合并后的聚類中心. ?在一次迭代中,某一類最多只能合并一次. ?Nc=Nc-已并掉的類數. ⑧如果迭代次數Ip=NS或過程收斂,則算法結束.否則,Ip=Ip+1,若需要調整參數,則轉至①

;若不改變參數,則轉至②;

ISODATA算法