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,若需要调整参数,则转至①
;若不改变参数,则转至②;
