模糊ISODATA聚类.pptx

主讲 周润景教授单位 电子信息工程学院 模糊ISODATA聚类 目录 模糊ISODATA聚类应用背景模糊ISODATA算法的基本原理模糊ISODATA算法的基本步骤模糊ISODATA算法程序实现总结 一 模糊ISODATA聚类应用背景 G H Ball与D J Hall于1965年提出的ISODATA算法是一个通过逐步修改聚类中心的个数与位置来达到分类目的的集群算法 后来不断有人提出它的各种改进算法 其中包括Ball和Hall1967年提出的改进算法 CLASS Asp等 1974年J C Dunn首次提出应用模糊数学判据的ISODATA集群算法 FuzzyISODATA IterativeSelf OrganizingDataAnalysisTechnique 算法通过每样本点对各类的隶属度矩阵表示分类结果 通过不断修改聚类中心的位置来进行分类 1976年J C Bezdek把Dunn的方法推广到更一般的情形 并得到了一些有益的结论 其中包括新的判据 隶属度函数与聚类中心的计算公式 Bezdek于1979年用W Zangwill的理论证明了FuzzyISODATA的收敛性 该方法已在行星跟踪系统 心脏病分析和天气预报等方面得到了应用 二 模糊ISODATA算法的基本原理 J C Bezdek在普通分类基础上 利用模糊集合的概念提出了模糊分类问题 认为被分类对象集合中的样本以一定的隶属度属于某一类 即所有的样本都分别以不同的隶属度属于某一类 因此每一类就被认为是样本集上的一个模糊子集 于是 每一种这样的分类结果所对应的分类矩阵 就是一个模糊矩阵 模糊ISODATA聚类方法从选择的初始聚类中心出发 根据目标函数 用数学迭代计算的方法反复修改模糊矩阵和聚类中心 并对类别进行合并 分解和删除等操作 直到合理为止 二 模糊ISODATA算法的基本原理 设有限样本集 论域 每一个样本有s个特征 即样本的特征的矩阵 欲把它分为类 则N个样本划分为K类的模糊分类矩阵为 二 模糊ISODATA算法的基本原理 其满足下列三个条件 条件 表明每一样本属于各类的隶属度之和为1 条件 表明每一类模糊集不可能是空集合 即总有样本不同程度的隶属于某类 定义K个聚类中心 其中 二 模糊ISODATA算法的基本原理 第i类的中心即人为假想的理想样本 它对应的s个指标值是该类样本所对应的指标值的平均值 构造准则函数 其中 表示第j个样本与第i类中心之间的欧式距离 J表示所有待聚类样本与所属类的聚类中心之间距离的平方和 为了确定最佳分类结果 就是寻求最佳划分矩阵U和对应的聚类中心Z 使J达到极小 Dunn证明了求上述泛函的极小值的问题可解 三 模糊ISODATA算法的基本步骤 1 选择初始聚类中心 2 计算初始隶属度矩阵 3 求各类的新的聚类中心 4 计算新的隶属度矩阵 5 回到第 3 步 重复至收敛 6 类别调整 合并 删除 分解 三 模糊ISODATA算法的基本步骤 6 类别调整 合并假定各聚类中心之间的平均距离为D 则取合并阈值为其中 是人为构造的函数 而且应是K的减函数 通常取 是一个可选择的参数 若聚类中心和间的距离小于 则合并这两个点而得到新的聚类中心 三 模糊ISODATA算法的基本步骤 6 类别调整 分裂对于类的第j个特征 模糊化方差的计算公式为 全体的平均值记作 然后求阈值对于任一不满足的类考虑其每个 若 便在第j个特征方向上对聚类中心加和减 得到两个新的聚类中心 三 模糊ISODATA算法的基本步骤 6 类别调整 删除 条件1 条件2 但 类不满足分解条件 即对所有的j 符合以上两个条件之一者 将被删除 四 模糊ISODATA算法程序实现 四 模糊ISODATA算法程序实现 重要程序代码这里对酒瓶颜色进行分类 下面介绍其重要程序代码 1 调节参数初始化Nc 4 初始聚类中心数目m 2 控制聚类结果模糊程度L 0 迭代次数Lmax 1000 最大迭代次数Nc all ones Lmax 2 各次迭代的分类数Udmax 10 最后一次的隶属度与前一次的隶属度的差值的初始值e 0 00005 收敛参数a 0 33 合并阈值系数b 1 模糊化方差参数 通常取1 r 0 1 分解阈值参数 算法使用者掌握的参数 控制G K 的上升速度 f 0 68 隶属度阈值 一般取值0 0 5之间 Avms 0 83 平均隶属度阈值 一般应大于0 5 0 55 0 6之间取值比较适宜 k divide 0 9 分裂1数 取0 1之间 w 0 2 删除条件参数 四 模糊ISODATA算法程序实现 2 FussyISODATA函数模糊ISODATA的函数如下 function X Z U Nc L Dcc Dccm Mind S Smean Fstd T C k delete Dpc FussyISODATA function data Nc m L Lmax Nc all Udmax e a b r f Avms k divide w data样本特征库 Nc初始聚类中心数目 m控制聚类结果模糊程度 L迭代次数 Lmax最大迭代次数 Nc all各次迭代的分类数 Udmax最后一次的隶属度与前一次的隶属度的差值的初始值 e收敛参数 a合并阈值系数 b模糊化方差参数 r分解阈值参数 四 模糊ISODATA算法程序实现 f隶属度阈值 Avms平均隶属度阈值 k divide分裂系数 w删除条件参数 返回值 X样本结构体数组 样本特征 所属类别 Z聚类中心结构体数组 聚类中心特征 所属类别及其包含的样本数 U隶属度矩阵 Nc聚类中心数目 L迭代次数 Dcc两两聚类中心之间的距离矩阵 Dccm两两聚类中心之间的距离的平均值 Mind合并阈值 S各类在每个特征方向上的模糊化标准差矩阵 Smean模糊化标准差平均值 Fstd分解阈值 T各类超过隶属度阈值f的样本数矩阵 C各类的聚集程度矩阵 k delete删除阈值 Dpc各样本点到各聚类中心的距离矩阵 四 模糊ISODATA算法程序实现 3 聚类函数function Z U Nc Nc all L Dpc FussyISODATA newcentre X Z U Nc Nc all Np Nq e m L Lmax Udmax 名称 FussyISODATA newcentre 参数 X样本结构体数组 样本特征 所属类别 Z聚类中心结构体数组 聚类中心特征 所属类别及其包含的样本数 U隶属度矩阵 Nc聚类中心数目 Nc all各次迭代的分类数 Np样本数目 Nq样本维数 e收敛参数 m控制聚类结果模糊程度 L迭代次数 四 模糊ISODATA算法程序实现 Lmax最大迭代次数 Udmax最后一次的隶属度与前一次的隶属度的差值的初始值 返回值 Z聚类中心结构体数组 聚类中心特征 所属类别及其包含的样本数 U隶属度矩阵 Nc聚类中心数目 Nc all各次迭代的分类数 L迭代次数 Dpc各样本点到各聚类中心的距离矩阵 功能 重复计算新的隶属度矩阵及聚类中心 直至收敛 四 模糊ISODATA算法程序实现 4 类别调整函数function Z U Nc Dcc Dccm Mind S Smean Fstd T C k delete FussyISODATA adjust X Z U Nc Np Nq a f Avms b r k divide w 名称 FussyISODATA adjust 参数 X样本结构体数组 样本特征 所属类别 Z聚类中心结构体数组 聚类中心特征 所属类别及其包含的样本数 U隶属度矩阵 Nc聚类中心数目 Np样本数目 Nq样本维数 a合并阈值系数 f隶属度阈值 Avms平均隶属度阈值 b模糊化方差参数 四 模糊ISODATA算法程序实现 r分解阈值参数 k divide分裂系数 w删除条件参数 返回值 Z聚类中心结构体数组 聚类中心特征 所属类别及其包含的样本数 U隶属度矩阵 Nc聚类中心数目 Dcc两两聚类中心之间的距离矩阵 Dccm两两聚类中心之间的距离的平均值 Mind合并阈值 S各类在每个特征方向上的模糊化标准差矩阵 Smean模糊化标准差平均值 Fstd分解阈值 T各类超过隶属度阈值f的样本数矩阵 C各类的聚集程度矩阵 k delete删除阈值 功能 调整聚类结果 合并 分解 或者删除 四 模糊ISODATA算法程序实现 本文对酒瓶颜色进行分类 以59组数据为对象 程序运行完之后 出现如图所示59组数据分类图 四 模糊ISODATA算法程序实现 MATLAB的运行结果如下 A 1 0e 03 1 74431 75191 94950 31203 21362 25062 29403 15691 00361 25531 83402 9638B 1至27列12142413221223341331132341228至54列22114123312411432321233114455至59列24111其中A为聚类中心 B为分类结果 五 总结 模糊ISODATA聚类分析方法对特性比较复杂而人