定义
ISODATA算法(Iterative Self Organizing Data Analysis Techniques Algorithm,迭代自组织数据分析方法)与K-Means算法相似,均属于无监督的聚类分析方法,但ISODATA针对K-Means算法中的一些不足进行了改进。
传统的K-Means算法中主要存在以下不足:
- K值需要预先设定
- 随机的初始中心选择对计算结果和迭代次数有较大的影响
而ISODATA算法在运行过程中能够根据各个类别的实际情况进行两种操作来调整聚类中心数K:(1)分裂操作,对应着增加聚类中心数;(2)合并操作,对应着减少聚类中心数。
ISODATA算法具体流程如下:
Step1:预期的聚类中心数目Ko:虽然在ISODATA运行过程中聚类中心数目是可变的,但还是需要由用户指定一个参考标准。事实上,该算法的聚类中心数目变动范围也由Ko决定。具体地,最终输出的聚类中心数目范围是 [Ko/2, 2Ko]。
Step2:每个类所要求的最少样本数目Nmin:用于判断当某个类别所包含样本分散程度较大时是否可以进行分裂操作。如果分裂后会导致某个子类别所包含样本数目小于Nmin,就不会对该类别进行分裂操作。
Step3:最大方差Sigma:用于衡量某个类别中样本的分散程度。当样本的分散程度超过这个值时,则有可能进行分裂操作(注意同时需要满足[2]中所述的条件)。
Step4:两个类别对应聚类中心之间所允许最小距离dmin:如果两个类别靠得非常近(即这两个类别对应聚类中心之间的距离非常小),则需要对这两个类别进行合并操作。是否进行合并的阈值就是由dmin决定。
ISODATA算法的原理非常直观,但由于其依赖于更多的参数,且这些参数的初始化具有一定的难度,这影响了该算法在实际应用中的效果。
参考文献
[1] http://www.wu.ece.ufl.edu/books/EE/communications/UnsupervisedClassification.html