模糊ISODATA聚类.pptx
- 文档编号:18756633
- 上传时间:2023-10-31
- 格式:PPTX
- 页数:22
- 大小:388.45KB
模糊ISODATA聚类.pptx
《模糊ISODATA聚类.pptx》由会员分享,可在线阅读,更多相关《模糊ISODATA聚类.pptx(22页珍藏版)》请在冰点文库上搜索。
主讲:
周润景教授单位:
电子信息工程学院,模糊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的函数如下:
functionX,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)聚类函数functionZ,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)类别调整函数functionZ,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聚类分析方法对特性比较复杂而人们又缺少认识的对象进行分类,可以有效地实施人工干预,加入人脑思维信息,使分类结果更符合客观实际,可以给出相对的最优分类结果,因而具有一定的实用性。
然而由于该方法在计算中需要人为选择和确定不同的参数,使该方法在数学理论上显得不够严谨。
参数的选取也缺乏理论依据,选取最合适的参数也非常困难。
这些参数的设定问题,直接影响到模糊分类的分类精度和算法实现,使FuzzyISODATA算法在实际应用中受到限制。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模糊 ISODATA 聚类