基于MATLAB的模糊ISODATA算法设计.docx

1、基于MATLAB的模糊ISODATA算法设计基于MATLAB勺模糊ISODAT算法设计一、前言 1二、 模糊ISODAT算法的基本原理 1三、 模糊ISODATA算法的基本步骤 3四、 模糊ISODATA算法MATLA程序实现 7（一） 模糊ISODATAf法MATLA程序流程图 7（二） 模糊ISODATAf法程序运行结果及分析 71 、初始化数据 82、 修改初始化数据e,其他同1 143、 修改初始化数据m其他同1 16五、 后 22 组样本的聚类结果 19六、 结论 20参考文献 21程序 23、八 、, 亠、刖言G. H. Ball 与D. J. Hall 于1965年提出的ISOD

2、AT算法是一个通过逐步修改聚类中 心的个数与位置来达到分类目的的集群算法，后来不断有人提出它的各种改进算法，其中 包括Ball和Hall 1967年提出的改进算法、CLASS Asp等。1974年J. C. Dunn首次提出 应用模糊数学判据的 ISODATA集群算法Fuzzy ISODATA (Iterative Self-Organizing Data Analysis Technique )。算法通过每样本点对各类的隶属度矩阵表示分类结果。通过 不断修改聚类中心的位置来进行分类。1976年J. C. Bezdek把Dunn的方法推广到更一般 的情形，并得到了一些有益的结论，其中包括新的判

3、据，隶属度函数与聚类中心的计算公 式。Bezdek于1979年用 W. Zangwill的理论证明了 Fuzzy ISODATA的收敛性。该方法已 在行星跟踪系统，心脏病分析和天气预报等方面得到了应用。 1、模糊ISODATA算法的基本原理J. C. Bezdek在普通分类基础上,利用模糊集合的概念提出了模糊分类问题。认为被 分类对象集合X中的样本Xi以一定的隶属度属于某一类，即所有的样本都分别以不同的 隶属度属于某一类。2因此,每一类就被认为是样本集X上的一个模糊子集，于是,每一种这 样的分类结果所对应的分类矩阵,就是一个模糊矩阵。模糊ISODATA聚类方法从选择的初 始聚类中心出发，根据目

4、标函数，用数学迭代计算的方法反复修改模糊矩阵和聚类中心 ，并对类别进行合并、分解和删除等操作，直到合理为止。 3设有限样本集(论域)X =X1,X2,.,Xn，每一个样本有s个特征Xj =(Xj1,Xj2,.,Xjs) , (j =1,2,., N)。即样本的特征的矩阵:X11X12X y/A1sXn瘙=X21111X211111X221111 7入2si ii ii ii iXN1XN2 v入Ns /欲把它分为K类(2兰K兰N)，则N个样本划分为K类的模糊分类矩阵为:其满足下列三个条件:I、0 s =乙1111=Z211111Z221111一 Z2s1 11 11 11 1lZK丿ZK1ZK

5、2ZKs丿第i类的中心乙即人为假想的理想样本，它对应的s个指标值是该类样本所对应的指标 值的平均值:N 送（气k）mXkjZij = , i =1,2,.,K；j =1,2,s送（片Jk *构造准则函数:K N 2j 八-rj（L 1）m Xj-Zii =1 j =1其中，Xj -Zi表示第j个样本与第i类中心之间的欧式距离；J表示所有待聚类样本与所 属类的聚类中心之间距离的平方和。56为了确定最佳分类结果，就是寻求最佳划分矩阵 U和对应的聚类中心 乙使j达到极小。Dunn证明了求上述泛函的极小值的问题可解。三、模糊ISODATA算法的基本步骤(1)选择初始聚类中心乙(0)。例如，可以将全体样

6、本的均值作为第一个聚类中心，然后在每个特征方向上加和减一个均方差，共得 (2n 1)个聚类中心，n是样本的维数(特征数)。也可以用其他方法选择初始聚类中心。(2)若已选择了 K个初始聚类中心，接着利用模糊 K-均值算法对样本进行聚类。由于 现在得到的不是初始隶属度矩阵U(0)，而是各类聚类中心，所以算法应从模糊K-均值算法 的第四步开始，即直接计算下一步的隶属度矩阵 U(0)。继续K-均值算法直到收敛为止，最终得到隶属度矩阵U和K个聚类中心Z二乙,Z2,Zj。然后进行类别调整。1计算初始隶属度矩阵U(0)，矩阵元素的计算方法为式中，dj是第j个样本到第i类初始聚类中心 乙(0)的距离。为避免分

7、母为零，特规定：若dj =0，则吟(0)=1，pj(0) =0 ( p 门);可见,dj 越大，Jj(0)越小。2求各类的新的聚类中心Zi(L)，L为迭代次数。Na Lj(L)mXjZi (L)二咼 ,i =1,2,., K迟%(L)mj m式中，参数m2，是一个控制聚类结果模糊程度的常数。可以看出各聚类中心的计算必须 用到全部的N个样本，这是与非模糊的K-均值算法的区别之一。在K-均值算法中，某一类 的聚类中心仅由该类样本决定，不涉及其他类。 3计算新的隶属度矩阵U(L 1)，矩阵元素的计算方法为式中，dj是第L次迭代完成时，第j个样本到第i类聚类中心Zj(L)的距离。为避免分母为 零，特规

8、定：若 dj =0，则 j(L 1) =1，pj(L 1) =0(p =i);可见，dj 越大，j(L 1)越 小。4回到第步，重复至收敛。收敛条件为 max j(L TRML)乞；，其中，：为规i,j定的参数。9(3)类别调整。调整分三种情形：1合并。假定各聚类中心之间的平均距离为 D,则取合并阈值为Md 二D1-F(K)其中，F(K)是人为构造的函数， 0乞F(K)叮，而且F(K)应是K的减函数，通常取F(K)=1/K：，a是一个可选择的参数。可见，若 D确定，则K越大时也越大，即合并越容易发生。若聚类中心乙和Zj间的距离小于Mind，则合并这两个点而得到新的聚类中心 Zl，Zl为N Nr

9、 Jip)Zi r Jip)ZjZ _ pm p 吕 zl = N N . ip jpp =1 p =1式中，N为样本个数。可见，Zl是乙和Zj的加权平均，而所用的权系数便是全体样本对 i 和J两类的隶属度。102分解。首先计算各类在每个特征方向上的“模糊化方差”。对于类的第j个特征，模糊化方N :匚(X. ip pjp=1差的计算公式为2 Zj) , j =1,2,., n;i =1,2,., K式中1是参数，通常选=1。Xpj，Zj分别表示样本Xp和聚类中心乙的第j个特征值Sj二, Si2，全体Sj的平均值记作S，然后求阈值Fstd 二 S1 G(K)G（K）是类数K的增函数，通常取G（K

10、）二K , 是参数。上式表明，当S确定时，类数K 越大，越不易分解。下面分两步进行分解：11N第一步，检查各类的“聚集程度”。对于任一类-i，取Sum hp%,p=1Ci表示i类的聚集程度。上两式的含义是对于每一类 i，首先舍去那些对它的隶属度太小的样本，然后计算其他各样本对该类的平均隶属度 Ci O 12若Ci -Avms（ Avms为参数），则表示类的聚集程度较高，不必进行分解；否则考虑下一步。第二步，分解。对于任一不满足Ci Avms的J类考虑其每个Sj ,若Sj Fstd，便在第j 个特征方向上对聚类中心Zi加和减kSj （k为分裂系数，Ovk兰1）,得到两个新的聚类中心。注意，这里每

11、个量的计算都考虑到了全体样本对各类的隶属度。3删除。删除某个类或聚类中心乙的条件有两个。条件1: T N/K ,是参数，Ti见上式，它表示对类隶属度超过二的点数。这一 条件表示对类隶属度高的点很少，应该删除。条件2: G乞Avms，但J类不满足分解条件，即对所有的j , Sj *+*半 a04-口 口n 13000标准答案征特 2500第20005001000200025001500第一特征3000O十+O*h 0 OQ口 口口 20002500300025002000150050010001500第一特征3000程序运行结果I二35003000n25002000150010002000100

12、0250020003000第特征特征50003000 3500第二1.3、初始Nc=6 7、8时聚类结果如下:3200must结果：已经聚类为4类，但是无法画出图，MATLAB!示“ ？?？ SWITCHexpression be a scalar or stri ng con sta nt. ”1个。原因：隶属度矩阵U中最大值个数、各样本到聚类中心的距离矩阵 Dpc中最小值个数大于尚未找到解决办法。1.4、初始Nc=3时聚类结果如下：+ O* cC口 口n I20002500300025002000150050010001500第一特征1.5、初始Nc=2时聚类结果如下:3500300030

13、002500200015005001000200025001500第一特征+ +半Q+ 4*0 O程序运行结果3000原因：分解算法中的参数选取不合适。未找到合适的参数1.6、分析初始聚类中心数目的选取对聚类结果有较大的影响，初步分析是由于程序设计不够完 善，参数设置不够合理。2、修改初始化数据 e，其他同12.1、收敛参数e = 0.5 时，聚类结果如下:3500卜+0 1 的前提下 , 它的值越小越好；另外 m-1 作为分 母, 故 m 值又不能太接近于 1 , 否则会引起计算溢出。实际应用中发现，m值的选取应注意:m值越小，迭代次数越少，分类速度越快，分类矩阵 U的值越趋向于0,1两极,

14、最优分类矩阵的模糊性越小，聚类效果较好；m的取值过大，会使 运算的复杂度增加 ,使得运算的时间增加 , 并且造成聚类矩阵的发散。显然 , 参数 m 的引入 在数学理论上不够严密 , 实际上如何取定 m 就缺乏依据 , 从而引入一定的主观任意性。为 此,Bezdek对参数m的确定进行了模拟试验研究，试验结果表明，参数m以采用2为优。问五、后22组样本的聚类结果340044 On0口 程序运行结果32003000280026002400220020001800160050010002500140020001500第一特征3000第二3500程序运行结果30002500200015001000020

15、0040003000200015001000500特征第特征500征特三第P 口ioo* *1, o*142500六、结论模糊ISODATA聚类分析方法对特性比较复杂而人们又缺少认识的对象进行分类，可以 有效地实施人工干预，加入人脑思维信息，使分类结果更符合客观实际，可以给出相对的最 优分类结果，因而具有一定的实用性。20然而由于该方法在计算中需要人为选择和确定不同的参数 ，使该方法在数学理论上显得不够严谨。参数的选取也缺乏理论依据，选取最合适的参数也非常困难。 这些参数的设定 问题,直接影响到模糊分类的分类精度和算法实现，使 Fuzzy ISODATA?法在实际应用中受 到限制。旳参考文献1

16、齐敏. 模式识别导论 . 北京：清华大学出版社 , 2009.2陈平.模糊ISODATA集群算法TFI.北京工业大学学报.1983. 9(2). 89-97.3钱夕元.模糊ISODATAK类分析算法的实现及其应用研究.计算机工程与应用.2004. 15. 70-71.4洪军 . Fuzzy ISODATA 聚类分析方法的设计 . 计算机与数字工程 . 2009. 37(236).19-20. 宓为建.动态模糊ISODATAR类方法及其在故障诊断中的应用.同济大学学报.1997. 25(1). 66-70.6孙国强 . 改进迭代自组织数据分析法德不良数据辨识 . 中国电机工程学报 . 2006.

17、 26(11). 162-1667武俊德.关于模糊ISODATA?法极值点的判定定理.大庆石油学院学报.1994. 18(1). 101-106.8沈照庆.基于改进模糊ISODATA?法的遥感影像非监督聚类研究.理论研究.2008. 5.28-32.9皋军. 基于模糊聚类的属性加权算法 . 淮阴工学院学报 . 2007. 16(3). 31-35.10郝方平 . 基于模糊聚类算法的备件需求辨识模型 . 计算机与现代化 . 2009. 11.30-32.11何敏.模糊 ISODATAi在 CRM中 的应用.计算机应用.2005. 25(6). 1455-1457.12黄健元. 模糊 ISODATA 聚类分析方法的改进 . 南京航空航天大学学报 . 2000. 32(2).179-183.13汪永成.模糊聚类算法研究及在 Web日志挖掘中的应用.辽宁工程技术大学.2008.16-27.14洪恒令. 模糊目标函数聚类算法及其应用 . 长春地质学院学报 . 1985. 3. 95-102.15李爱国. 一种基于属性加权模