文章目录

• ISODATA聚类算法
• • 一、 K均值算法
  • • 1、K均值算法概述
    • 2、K均值算法步骤
    • • 步骤一：
      • 步骤二：
      • 步骤三：
      • 步骤四：
    • 3、K均值算法动态演示
    • 4、K均值算法优缺点
    • • 优点：
      • 缺点：
  • 二、ISODATA聚类算法
  • • 1、ISODATA算法概述
    • 2、ISODATA算法步骤
    • • 步骤一：
      • 步骤二：
      • 步骤三：
      • 步骤四：
      • 步骤五：
      • 步骤六：
      • 步骤七：
      • 步骤八：
    • 3、ISODATA优缺点：
    • • 优点：
      • 缺点：

ISODATA聚类算法

一、 K均值算法

ISODATA算法是在k-均值算法的基础上，增加对聚类结果的“合并”和“分裂”两个操作

1、K均值算法概述

k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法

2、K均值算法步骤

步骤一：

预将数据分为K组，则随机选取K个对象作为初始的聚类中心。

步骤二：

计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。
可以根据实际需要选择一种距离作为相似性度量，其中最常用的是欧氏距离：X中的样本用d个描述属性A1,A2…Ad来表示，并且d个描述属性都是连续型属性。数据样本xi=(xi1,xi2,…xid), xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分别是样本xi和xj对应d个描述属性A1,A2,…Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi,xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。

步骤三：

每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。
各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。

步骤四：

上述过程将不断重复直到满足某个终止条件（准则函数）。
k-means聚类算法使用误差平方和准则函数来评价聚类性能。误差平方和准则函数公式为：

3、K均值算法动态演示

动画演示

4、K均值算法优缺点

优点：

1.算法快速、简单;
2.对大数据集有较高的效率并且是可伸缩性的;
3.时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(nkt) ,其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目。

缺点：

① 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。
② 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。

二、ISODATA聚类算法

1、ISODATA算法概述

ISODATA算法是在k-均值算法的基础上，增加对聚类结果的“合并”和“分裂”两个操作，并设定算法运⾏控制参数的⼀种聚类算法。迭代次数会影响最终结果，迭代参数选择很重要。

2、ISODATA算法步骤

步骤一：

初始化
设定控制参数：
c：预期的类数；
Nc：初始中心个数 (可以不等于c) ；
TN：每⼀类中允许的最少样本数目 (若少于此数， 就不能单独成为⼀类) ；
TE：类内各特征分量分布的相对标准差上限 (大于此数就分裂) ；
TC：两类中心间的最小距离下限 (若小于此数， 这两类应合并) ；
NT：在每次 中最多可以进行“合并”操作的次数；
NS：允许的最多迭代次数。
选定初始中心

步骤二：

按最近邻规则将样本集{xi}中每个样本分到某⼀类中（此处与K均值算法相似）

步骤三：

依据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， 同时又满足下面两个条件之⼀：
a、 > 且
>2(TN+1)
b、Nc ≤ c/2
则将该类ωj分裂为两个类， 原zj取消且令Nc=Nc+1。
两个新类的中⼼zj+和zj-分别是在原zj中相应于 的分量加上和减去 分裂后， Ip=Ip+1, 转⾄②。

步骤七：

合并操作
计算各类中⼼间的距离Dij， i=1,2, … ,Nc- 1 ; j=1,2, … ,Nc， ⽽起它分量不变， 其中0<k≤1。
依据TC判断合并。将Dij与TC⽐较， 并将⼩于TC的那些Dij按递增次序排列， 取前NT个。
从最⼩的Dij开始， 将相应的两类合并， 并计算合并后的 中⼼。
在⼀次迭代 中， 某⼀类最多只能合并⼀次。
Nc=Nc- 已并掉的类数。

步骤八：

如果迭代次数Ip=NS或过程收敛， 则算法结束。否则， Ip=Ip+1， 若需要调整参数， 则转⾄①；若不改变参数， 则转⾄②；

3、ISODATA优缺点：

优点：

ISODATA 可以在聚类过程中自动调整类别个数和类别中心，使聚类结果能更加靠近客观真实的聚类结果。避免了K均值算法事先很难去确定待分类的集合（样本）中到底有多少类别这一缺点 。

缺点：

ISODATA算法需要设置的参数比较多，参数值不好确定。
不同的参数之间相互影响
可以通过多次设置不同的值进行不同的实验，然后取一些已知的样本来检验聚类结果的精度，以最后取得更好的分类结果的那次实验为准；或者考虑和其他方法相结合来得到更好的分类结果。

总结

以上是生活随笔为你收集整理的ISODATA聚类算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。