优化ISODATA算法的文章标题

在大多数图像处理软件中，还有一种最常用的非监督分类算法，即迭代自组织数据分析算法（Iterative Self-Organizing Data Analysis Techniques Algorithm，ISODATA）。ISODATA算法与K-均值算法有两点不同：第一，它不是每调整一个样本的类别就重新计算一次各类样本的均值，而是在每次把所有样本都调整完毕之后才重新计算一次各类样本的均值，前者称为逐个样本修正法，后者称为成批样本修正法。第二，ISODATA算法不仅可以通过调整样本所属类别完成样本的聚类分析，而且可以自动地进行类别“合并”和“分裂”，从而得到类数比较合理的聚类结果。

在ISODATA算法中，类别的“合并”和“分裂”很有意义。这说明在迭代过程中类别总数是可以改变的，克服了K-means算法的缺点。类别合并，意味着这两个类别相似程度很高，或者是某类的像元数太少，该类就要合并到最相近的类中去。类别的分裂也有两种情况：某一类的像元数太多，该类就要分裂成两类；或者类别总数太少，就要将离散型最大的一类分成两个类别。

ISODATA算法描述如下：

第一步：给出下列控制参数：

K：希望得到的类别数；

θN：所希望的一个类中样本的最小数目；

：关于类的分散相度的参数，如用标准差来判断；

：关于类之间的距离参数，如用最小距离来设定；

L：每次允许合并的类的对数；

I：允许迭代的次数。

第二步：适当地选取Nc个类的初始中心。

第三步：把所有样本X按如下的方法分到Nc个类别中的某一类中去：

即如果，则X∊Sj，其中Sj是以Zj为中心的类。

第四步：如果Sj类中的样本数小于θN，则去掉该类，Nc=Nc-1，返回第三步。

第五步：按下面公式，重新计算各类的中心。

第六步：计算Sj类内的平均距离

第七步：计算所有样本离开其相应的聚类中心的平均距离。(www.xing528.com)

式中：N为样本总数。

第八步：如果迭代次数大于允许迭代的次数I，则转向第十二步，检查类间最小距离，判断是否进行合并。

如果Nc<K/2，则转向第九步，检查每类中各分量的标准差（分裂）。

如果迭代次数为偶数，或者Nc>2K，则转向第十二步，检查类间最小距离，判断是否进行合并。否则则转向第九步。

第九步：计算每类中各分量的标准差。

上式中：i为样本X的维数；j为类别数；k为Sj类中的样本数；xik为第k个样本的第i个分量；zij为第j个聚类中心Zj的第i个分量。

第十步：对每一个聚类Sj，找出标准差最大的分量δjmax：

第十一步：如果下述条件1和条件2有一个成立，则把Sj分裂成两个聚类，两个新类的中心分别是和。原来的Zj取消，使Nc=Nc+1，然后转向第三步，重新分配样本。其中

条件1：，且；

条件2：，且；，k是人为给定的常数，且0<k≤1。

第十二步：计算所有聚类中心两两之间的距离。

第十三步：比较Dij和θc，把小于θc的Dij按由小到大的顺序排列。

，其中L为每次允许合并的类的对数

第十四步：按照l=1，2，…，L的顺序，把Diljl所对应的两个聚类中心Zil，和Zjl合并成一个新的聚类中心，并使

在对Diljl所对应的两个聚类中心Zil和Zjl进行合并时，如果其中至少有一个聚类中心已经被合并过，则越过该项，继续进行后面的合并处理。

第十五步：若迭代次数大于I，或者迭代中的参数的变化在差限以内，则迭代结束。否则转向第三步继续进行迭代处理。