基于MATLAB的模糊ISODATA算法设计.docx
《基于MATLAB的模糊ISODATA算法设计.docx》由会员分享，可在线阅读，更多相关《基于MATLAB的模糊ISODATA算法设计.docx（59页珍藏版）》请在冰点文库上搜索。
基于MATLAB的模糊ISODATA算法设计
基于MATLAB勺模糊ISODAT算法设计
一、前言1
二、模糊ISODAT算法的基本原理1
三、模糊ISODATA算法的基本步骤3
四、模糊ISODATA算法MATLA程序实现7
（一）模糊ISODATAf法MATLA程序流程图7
（二）模糊ISODATAf法程序运行结果及分析7
1、初始化数据8
2、修改初始化数据e,其他同114
3、修改初始化数据m其他同116
五、后22组样本的聚类结果19
六、结论20
参考文献21
程序23
、八、,亠、刖言
G.H.Ball与D.J.Hall于1965年提出的ISODAT算法是一个通过逐步修改聚类中心的个数与位置来达到分类目的的集群算法，后来不断有人提出它的各种改进算法，其中包括Ball和Hall1967年提出的改进算法、CLASSAsp等。
1974年J.C.Dunn首次提出应用模糊数学判据的ISODATA集群算法——FuzzyISODATA（IterativeSelf-OrganizingDataAnalysisTechnique）。
算法通过每样本点对各类的隶属度矩阵表示分类结果。
通过不断修改聚类中心的位置来进行分类。
1976年J.C.Bezdek把Dunn的方法推广到更一般的情形，并得到了一些有益的结论，其中包括新的判据，隶属度函数与聚类中心的计算公式。
Bezdek于1979年用W.Zangwill的理论证明了FuzzyISODATA的收敛性。
该方法已在行星跟踪系统，心脏病分析和天气预报等方面得到了应用。
⑴
1、模糊ISODATA算法的基本原理
J.C.Bezdek在普通分类基础上,利用模糊集合的概念提出了模糊分类问题。
认为被分类对象集合X中的样本Xi以一定的隶属度属于某一类，即所有的样本都分别以不同的隶属度属于某一类。
[2]因此,每一类就被认为是样本集X上的一个模糊子集，于是,每一种这样的分类结果所对应的分类矩阵,就是一个模糊矩阵。
模糊ISODATA聚类方法从选择的初始聚类中心出发，根据目标函数，用数学迭代计算的方法反复修改模糊矩阵和聚类中心，并
对类别进行合并、分解和删除等操作，直到合理为止。
[3]
设有限样本集（论域）X={X1,X2,...,Xn}，每一个样本有s个特征
Xj=（Xj1,Xj2,...,Xjs）,（j=1,2,...,N）。
即样本的特征的矩阵:
X11
X12
X
y/
A1s
Xn瘙=
X2
1
1
1
1
—
X21
1
1
1
1
X22
1
1
1
1
7
入2s
ii
ii
ii
ii
XN2
v
入Ns/
欲把它分为K类（2兰K兰N），则N个样本划分为K类的模糊分类矩阵为:
其满足下列三个条件:
I、0N
u、'叫j=1,j=1,2,...,N
i1
N
in、0八"j：
：
：
N,i=1,2,...,K
j4
1；条件n表明每一类模糊集不可能是空
条件u表明每一样本属于各类的隶属度之和为集合，即总有样本不同程度的隶属于某类。
⑷
定义K个聚类中心Z「.Z1,Z2,...,Zj。
其中：
乙•z1,Zi2,...,Zs?
i=1,2,...,K
GJ
匕1
Z12
—Ns'
ZK>s=
乙
1
1
1
1
=
Z21
1
1
1
1
Z22
1
1
1
1
…一Z2s
11
11
11
11
lZK丿
ZK2
ZKs丿
第i类的中心乙即人为假想的理想样本，它对应的s个指标值是该类样本所对应的指标值的平均值:
N送（气k）mXkj
Zij=,i=1,2,...,K；j=1,2,…,s
送（片J
k*
构造准则函数:
KN2
j八-r\j（L1）]mXj-Zi
i=1j=1
其中，Xj-Zi表示第j个样本与第i类中心之间的欧式距离；J表示所有待聚类样本与所属类的聚类中心之间距离的平方和。
[5]
[6]
为了确定最佳分类结果，就是寻求最佳划分矩阵U和对应的聚类中心乙使j达到极
小。
Dunn证明了求上述泛函的极小值的问题可解。
三、模糊ISODATA算法的基本步骤
（1）选择初始聚类中心乙（0）。
例如，可以将全体样本的均值作为第一个聚类中心，然
后在每个特征方向上加和减一个均方差，共得（2n1）个聚类中心，n是样本的维数（特征
数）。
也可以用其他方法选择初始聚类中心。
（2）若已选择了K个初始聚类中心，接着利用模糊K-均值算法对样本进行聚类。
由于现在得到的不是初始隶属度矩阵U（0），而是各类聚类中心，所以算法应从模糊K-均值算法的第四步开始，即直接计算下一步的隶属度矩阵U（0）。
⑺继续K-均值算法直到收敛为止，
最终得到隶属度矩阵U和K个聚类中心Z二「乙,Z2,…,Zj。
然后进行类别调整。
1
计算初始隶属度矩阵U（0），矩阵元素的计算方法为
式中，dj是第j个样本到第i类初始聚类中心乙（0）的距离。
为避免分母为零，特规定：
若
dj=0，则吟（0）=1，」pj（0）=0（p门）;可见,dj越大，Jj（0）越小。
2求各类的新的聚类中心Zi（L），L为迭代次数。
N
aLj（L）]mXj
Zi（L）二咼,i=1,2,...,K
迟[%（L）]m
jm
式中，参数m—2，是一个控制聚类结果模糊程度的常数。
可以看出各聚类中心的计算必须用到全部的N个样本，这是与非模糊的K-均值算法的区别之一。
在K-均值算法中，某一类的聚类中心仅由该类样本决定，不涉及其他类。
⑹
3计算新的隶属度矩阵U（L1），矩阵元素的计算方法为
式中，dj是第L次迭代完成时，第j个样本到第i类聚类中心Zj（L）的距离。
为避免分母为零，特规定：
若dj=0，则^j（L1）=1，」pj（L•1）=0（p=i）;可见，dj越大，^j（L1）越小。
4回到第③步，重复至收敛。
收敛条件为max{j（LTR’ML）}乞；，其中，：
为规
i,j
定的参数。
[9]
（3）类别调整。
调整分三种情形：
1合并。
假定各聚类中心之间的平均距离为D,则取合并阈值为
M^d二D[1-F（K）]
其中，F（K）是人为构造的函数，0乞F（K）叮，而且F（K）应是K的减函数，通常取
F（K）=1/K：
，a是一个可选择的参数。
可见，若D确定，则K越大时也越大，即合
并越容易发生。
若聚类中心乙和Zj间的距离小于Mind，则合并这两个点而得到新的聚类中心Zl，Zl为
NN
rJip）ZirJip）Zj
Z_pmp吕
zl=NN
■—.ip•jp
p=1p=1
式中，N为样本个数。
可见，Zl是乙和Zj的加权平均，而所用的权系数便是全体样本对'i和J两类的隶属度。
[10]
2分解。
首先计算各类在每个特征方向上的“模糊化方差”。
对于「类的第j个特征，模糊化方
N:
匚"（X.
—ippj
p=1
差的计算公式为
2
—Zj）,j=1,2,....,n;i=1,2,...,K
式中1是参数，通常选]=1。
Xpj，Zj分别表示样本Xp和聚类中心乙的第j个特征值
Sj二■,Si2，全体Sj的平均值记作S，然后求阈值
Fstd二S[1G（K）]
G（K）是类数K的增函数，通常取G（K）二K,是参数。
上式表明，当S确定时，类数K越大，越不易分解。
下面分两步进行分解：
[11]
N
第一步，检查各类的“聚集程度”。
对于任一类-i，取Sumhp%,
p=1
Ci表示i类的聚集程度。
上两式的含义是对于每一类i，首先舍去那些对它的隶属度太小
的样本，然后计算其他各样本对该类的平均隶属度CiO[12]若Ci-Avms（Avms为参数），则表
示「类的聚集程度较高，不必进行分解；否则考虑下一步。
第二步，分解。
对于任一不满足CiAvms的J类考虑其每个Sj,若Sj■Fstd，便在第j个特征方向上对聚类中心Zi加和减kSj（k为分裂系数，Ovk兰1）,得到两个新的聚类中心。
注意，这里每个量的计算都考虑到了全体样本对各类的隶属度。
3删除。
删除某个类「或聚类中心乙的条件有两个。
条件1:
T—N/K,是参数，Ti见上式，它表示对「类隶属度超过二的点数。
这一条件表示对「类隶属度高的点很少，应该删除。
条件2:
G乞Avms，但J类不满足分解条件，即对所有的j,Sj这个条件表明,
在乙的周围存在着一批样本点，它们的聚集程度不高，但也不是非常分散。
这时，我们认为乙也不是一个理想的聚类中心。
[13]
符合以上两个条件之一者，将被删除。
如果在第（3）步类别调整中进行了合并、分解或删除，则在每次处理后都应进行下面
所指出的讨论，并在全部处理结束后做出一个选择：
停止在某个结果上，或者转到第
（2）
步重新迭代。
如果在第（3）步中没有进行任何类别调整，则表示已经不需要改进结果，计
（4）关于最佳类数或最佳结果的讨论
上述所得为预选定分类数K时的最优解，为局部最优解。
最优聚类数K可借助下列判定聚类效果的指标值得到：
1KN
分类系数：
F（R）二-二二：
，F越接近1,聚类效果越好;
ni2j4
1KN
平均模糊熵：
H（R）=-77In（叫j），H越接近于0，聚类效果越好
ni=ij=i
由此，可以分别选定K（2兰K兰N），计算其所得聚类结果的聚类指标值并进行比较，求得最优聚类个数K,即满足F最接近1或H最接近0的K值。
[15]
（5）分类清晰化。
两种方法
①Xj与哪一类的聚类中心最接近，就将Xj归到哪一类。
即：
-Xj•X，若
②Xj对哪一类的隶属度最大，就将它归于哪一类。
即：
在U的第j列中，若
j1）=max，pjK⑪，1,n,.则Xj「类。
当算法结束时，就得到了各类的聚类中心以及表示各样本对各类隶属程度的隶属度矩
KN2
阵，模糊聚类到此结束。
这时，准则函数J[%（L1）]mXj-Zi达到最小。
[16]
i3jT
四、模糊ISODATA算法MATLAB程序实现
（一）模糊ISODATA算法MATLAB程序流程图
（二）模糊ISODATA算法程序运行结果及分析
以前29组数据样本为参考,调节参数
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;%删除条件参数
3500
3000
2500
2000
O
十
G
*
*
蜡
*
'口□
□¥
1
标准答案
500
1000
2500
1500
15002000
第一特征
3000
1.1、
在上述初始化数据条件下程序运行结果如下:
3500
O
+十
+
O
7
°0O
jF
0
口口
口¥
1
程序运行结果
2500
3000
2500
2000
1500
500
1000
15002000
第一特征
3000
1500
征特三第
1.2、初始Nc=5时聚类结果如下:
3500
1500
0
O
十
o
>
*
■+
*半a
0
■4-
口口
n¥
1
3000
标准答案
征
特2500
第
2000
500
1000
2000
2500
1500
第一特征
3000
O
十
+
O
*
h
°0O
Q
口口
口¥
2000
2500
3000
2500
2000
1500
500
1000
1500
第一特征
3000
程序运行结果
—I■■二
3500
—
3000
n
2500
2000
□
1500
1000
2000
1000
2500
2000
3000
第
特征
特征
500
0
30003500
第二
1.3、初始Nc=67、8时聚类结果如下:
3200
must
结果：
已经聚类为4类，但是无法画出图，MATLAB!
示“？
?
？
SWITCHexpressionbeascalarorstringconstant.”
1个。
原因：
隶属度矩阵U中最大值个数、各样本到聚类中心的距离矩阵Dpc中最小值个数大于
尚未找到解决办法。
1.4、初始Nc=3时聚类结果如下：
+O
*
□
□c
]
C
口口
n¥
I
2000
2500
3000
2500
2000
1500
500
1000
1500
第一特征
1.5、初始Nc=2时聚类结果如下:
3500
3000
3000
2500
2000
1500
500
1000
2000
2500
1500
第一特征
¥
++
半
Q
+4
*
0O
程序运行结果
3000
原因：
分解算法中的参数选取不合适。
未找到合适的参数
1.6、分析
初始聚类中心数目的选取对聚类结果有较大的影响，初步分析是由于程序设计不够完善，参数设置不够合理。
2、修改初始化数据e，其他同1
2.1、
收敛参数e=0.5时，聚类结果如下:
3500
卜
+
+
+
0
<
?
00
程序运行结果
3000
2500
2000
500
2500
100015002000
第一特征
1500
3000
迭代次数:
34次
2.2、收敛参数
e=0.00005
时，聚类结果如下:
O
十
+
O
*
h
°00
Q
口口
口¥
2000
2500
3000
2500
2000
1500
500
1000
1500
第一特征
迭代次数：
21次
2.3、收敛参数e=0.000000005时，聚类结果如下:
3500
3000
O
+十
+
O
7
°0O
0
口口
口¥
1
程序运行结果
2000
2500
3000
2500
2000
1500
500
1000
1500
第一特征
3000
迭代次数：
34次
2.4、分析
e的取值是精度要求，对于整个聚类结果有一定影响,e太大时，聚类结果不精确；e的取值越小则迭代的次数越大。
为了保证聚类结果的可靠性,e的取值一般为10-4〜10-6。
口
3、修改初始化数据m,其他同1
3.1、控制聚类结果模糊程度参数m=1.5时，聚类结果如下:
迭代次数：
14次
3.2、控制聚类结果模糊程度参数m=2时，聚类结果如下:
O
十
+
O
*
h
°00
Q
口口
口¥
2500
3000
2500
2000
1500
500
1000
15002000
第一特征
3000
迭代次数：
21次
3.3、控制聚类结果模糊程度参数m=3时，聚类结果如下:
3200
3000
2800
2600
2400
2200
2000
1800
1600
500
1000
1500
C：
0
2000
2500
结果：
已经聚类为5类，但是无法画出图，MATLAB^示“？
?
？
SWITC陆xpressionmustbeascalarorstringconstant.”
迭代次数：
71次
原因：
隶属度矩阵U中最大值个数、各样本到聚类中心的距离矩阵Dpc中最小值个数大于1个。
尚未找到解决办法。
3.4、分析
加权指数m控制着模糊类间的分享程度,m值的选取对整个聚类过程和聚类结果有较大影响。
参数m越接近1,分类的模糊性越小，当m=1时，分类变成硬分类；参数m越大，分类的模糊性越大,它的意义也更不明确。
[18]由于m出现在泛函J中作为一个指数,它的值不宜太大,否则会引起失真,因而在m>1的前提下,它的值越小越好；另外m-1作为分母,故m值又不能太接近于1,否则会引起计算溢出。
实际应用中发现，m值的选取应注意:
m值越小，迭代次数越少，分类速度越快，分类矩阵U的值越趋向于0,1两极,最优分类矩阵的模糊性越小，聚类效果较好；m的取值过大，会使运算的复杂度增加,使得运算的时间增加,并且造成聚类矩阵的发散。
显然,参数m的引入在数学理论上不够严密,实际上如何取定m就缺乏依据,从而引入一定的主观任意性。
为此,Bezdek对参数m的确定进行了模拟试验研究，试验结果表明，参数m以采用2为优。
问
五、后22组样本的聚类结果
3400
4
4
□
□
□
□O
□
n
0
□
口□
程序运行结果
3200
3000
2800
2600
2400
2200
2000
1800
1600
500
1000
2500
1400
2000
1500
第一特征
3000
第二
3500
程序运行结果
3000
2500
2000
1500
1000
0
2000
4000
3000
2000
1500
1000
500
特征
第
特征
500
征特三第
P口
□
◎
io
o
**
1—
■——
o
*
1
4
2500
六、结论
模糊ISODATA聚类分析方法对特性比较复杂而人们又缺少认识的对象进行分类，可以有效地实施人工干预，加入人脑思维信息，使分类结果更符合客观实际，可以给出相对的最优分类结果，因而具有一定的实用性。
[20]
然而由于该方法在计算中需要人为选择和确定不同的参数，使该方法在数学理论上显
得不够严谨。
参数的选取也缺乏理论依据，选取最合适的参数也非常困难。
这些参数的设定问题,直接影响到模糊分类的分类精度和算法实现，使FuzzyISODATA?
法在实际应用中受到限制。
旳
参考文献
[1]齐敏.模式识别导论.北京：
清华大学出版社,2009.
[2]陈平.模糊ISODATA集群算法TFI.北京工业大学学报.1983.9
（2）.89-97.
[3]钱夕元.模糊ISODATAK类分析算法的实现及其应用研究.计算机工程与应用.2004.15.70-71.
[4]洪军.FuzzyISODATA聚类分析方法的设计.计算机与数字工程.2009.37（236）.
19-20.
⑸宓为建.动态模糊ISODATAR类方法及其在故障诊断中的应用.同济大学学报.1997.25
（1）.66-70.
[6]孙国强.改进迭代自组织数据分析法德不良数据辨识.中国电机工程学报.2006.26（11）.162-166
[7]武俊德.关于模糊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]李爱国.一种基于属性加权模
升级会员 