论文研究-基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析.pdf

所需积分/C币:5 2019-09-20 12:29:42 479KB .PDF

论文研究-基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析.pdf,  对基于摄动的模糊聚类算法进行深入研究.给出一个模糊相似矩阵的实例,存在与该矩阵距离相同且都是最小的两个不相等的模糊等价矩阵,从而证明了全局最优模糊等价矩阵不具有唯一性.对基于摄动的模糊聚类算法求出的可行解的不同情况进行分析,给出了每种情况下可行解个数的计算表达式.完善了基于摄动的模糊聚类算法的相关理论.
240 系统工程理论与实践 第30卷 4)每块的行数大于等于列数; 5)下三角被分成m-1块 由标准分解过程的定义可知,标准参数系中的参数满足一定的不等式关系 例1满足下面不等式关系的参数t(1≤i≤6)构成的如下矩阵是一系列等价标准型 1 te t2 t1 t1 t2 1 t3 t1 t2 t3 1 t tttt 111 titI t1 544 t41t6 t4t61 参数系T={t1,t2,t3,t4,ts,t6}满足不等式关系:0≤t<t<t≤1,0≤t<t4<t≤1, 0≤t<t4<t6≤1.注意标准参数系中参数值变化得到的不同等价标准型不是置换等价的 特别地,下面是一个具体的等价标准型 10.20.20.10.10.10. 0.210.40.10.10.10 0.20.410.10.10.10.1 0.10.10.110.50.30.3 0.10.10.10.510.30.3 0.10.10.10.30.310.7 0.10.10.10.30.30.71 命题31设X∈Xn,如果X有一个标准分解构造(X(Im),X(1m),X(Im,Im),X(,Lm),那么以下 结论成立: 1)三a∈Sn,满足X,有以下分块形式 X(Im.) X(Im, IS X(Im. Im) X(Im) = =(1)(n-m)×m 3)如果t=1,那么X=(1)mxm; 如果t<1,那么 b)X(Im)>(t)mxm X(I)>() 定理21对于任意的X∈Xn,存在σ∈Sn,使得X。为等价标准型 定理3设X为一个等价标准型,对其按标准分解过程分块设X0=(to)m0x为X的下三角矩阵 中任意一个子矩阵,则有以下结论 1)若X1,X2,…,X。为Xo的所有右方相邻子矩阵,其行数分别为m1,m2 m 0=m1+ m2+…+m8+1.特别地,当X0无石方相邻子矩阵时,m0=1 2)若X1,X2,…,X。为X0的所有上方相邻子矩阵其列数分别为m1,n2,……,ma,则m0=m1+m2+ 十ns+1.特别地,当X0无上方相邻子矩阵时,m0=1 给定一个等价标准型,我们可以写出其标准参数系.反过来,已知一个标准参数系,根据定理3,可以自 末端的参数开始,逐步推出每个参数对应子矩阵的行数和列数,最后赋值得到下三角阵,再由对称性,可写出 整个等价标准型.所以,标准参数系和等价标准型是一一对应的 定理4(给定一个等价标准型X,由Ⅹ可以得到标准参数系T;反过来,由标准参数系T可以得到 与其对应的等价标准型X 定理51]对于任意的X,y∈Xn,X~Y分X和y有相同的等价标准型 设X∈Xn,记[x]为X的置换等价类则[x可由等价标准型表示 定理611如果X∈Xn,那么X~Y兮X和Y有相同的标准参数系 第7期 赵卫中,等:基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析 1241 在Xn和全体参数系集合J中引入另一种关系“≈”:X≈Y分X和Y有图相同但数值未必相同的参 数系,这是等价关系,称ⅹ与Y平移等价,称对应的标准参数系为相似标准参数系.所有等价标准型的集合 记作Xn.显然“≈”在Xn中也是等价关系,所以得到商集Xn/≈记J≈为相似标准参数系的等价类全 体,X(S)为与标准参数系S对应的等价标准型,则有以下结论: 定理71 ∪∪∪{X(5)a} c∈S T∈J/≈S∈T 记C(T)-{S:S和T有相同的参数图,S中参数满足非严格不等关系},X-X(T),C(X)-{X(S) S∈C(T)}为C(T)对应的模糊等价矩阵全体. 定理81Xn=∪∪ HX(Sa1 d∈SnT∈J/≈s∈C(⑦) 记模糊相似矩阵A和B之间的距离为4,B)=√∑=1∑=+1(-by)2A,BCYn 定理91对于任意的B∈Yn,存在#∈Xn,满足d(P#,B)-,infd(X,B 称与给定的模糊相似矩阵距离最小的模糊等价矩阵为最优模糊等价矩阵.显然,最优模糊等价矩阵是相 对给定的模糊相似矩阵“失真”最小的模糊等价矩阵,因此用它聚类更合适 推论11对于任意的R∈Y1,R#是R的最优模糊等价矩阵,则R∈Xn1台R#=B台(R,R#)=0 推论21对于任意的R∈Yn,R#是R的最优模糊等价矩阵,P*为R的传递闭包,则d(R,R4)≤ d(r, r 推论3对于任意的R∈Y,B是R的最优模糊等价矩阵,R"为R的传递闭包,则R∈Xn分 R*=R#=R 定理101假设R∈Yn,如果存在R#∈C(X)cXn满足d(R.,R#)=infd(X,R),那么 X∈C(X) t1=如++m(=1,…,n-1,其中t,t,…,tn-1是P#的参数,b1,b2,…,bm,是中对应 于R#中的t(2=1.2,…,7-1)的元素 根据以上理论基础就可以给岀求解最优模糊等价矩阵的 FCMBP算法 Step1建立一个有序存放所有n阶模糊等价标准型的平移等价类的数据库Xn/≈以及相应相似标准 参数系的等价类数据库J≈ Step2取R∈Yn Step3取 step4取E∈Xn/ Step5计算R Step6找出R中对应于E中参数t的元素b;1,b2,,bm,其中i=1,2,…,m-1 step7计算l=2 ba1+b2+…+b:m Sep8验证t是否符合由E所确定的标准参数系中的不等式关系.若不符合则转向Step4;若符合, 则转下一步 step9由t构造等价标准型E,计算并记录矩阵E和Ro之间的距离d(E",Rn) Sep10重复Step4到Step9直到E遍历平移等价类的数据库Xn/≈,找出使dE,Rn)最小的E 转回Step3 Step11重复Step3到Stcp10直到σ遍历Sn中所有元素找出E#,#使得d(E#,Rn#) inf inf d(E, Ro) E∈X step12计算R#=F (o#)-1,n d(r#, r)= inf d(X, r) X∈Xn 3全局最优模糊等价矩阵唯一性讨论 关于全局最优模糊等价矩阵的唯一性间题、文献⑧8-1]中都指出“全局最优模糊等价矩阵并不总是唯一 的”,但是既没有给出理论证明,也没有举出实例来证明该结论.下面是我们首次给出这方面的实例证明全局 最优模糊等价矩阵不具有唯一性. 1242 系统工程理论与实践 第30卷 1.00.7150.520.2320.115 0.7151.009880.5990.085 例2对于模糊相似矩阵R=0.520.9881008690318,对R利用 FCMBP算法求出 0.2320.5990.8691.00.807 0.1150.0850.3180.8071.0 1.00.4890.4890.4890.331 0.4891.00.9880.7340.331 的两个最优模糊等价矩阵,第一个最优模糊等价矩阵R=04890.98100.7340.33;第二 0.4890.7340.7341.00.331 0.3310.3310.3310.3311.0 1.00.6170.6170.370.37 0.6171.00.9880.370.37 个最优模糊等价矩阵=0617098100837037.满足(R,R)=(R,)=097 0.370.370.371.0807 0370.370.3708071.0 且R和R#都是距离R最小的模糊等价矩阵,即和f都是全局最优模糊等价矩阵.图1和图2分 别是R1和R对应的动态聚类图 图1最优模糊等价矩阵R#对应的动态聚类图 图2最优模糊等价矩阵P对应的动态聚类图 由图1和图2可知,虽然P和P都是最优模糊等价矩阵,但是P和B#对应的同一层次上聚类 结果有差异.例如对P取A=0.734得到分类:{1},{2,3,4},{5}.对P取A=0.807得到分类{1}, {2,3}.{4,5}.它们都把5个元素分为3类,但是聚类结果不同.这个例子证明全局最优模糊等价矩阵不具 有唯一性,并且每个全局最优模糊等价矩阵对应的同一层次上的聚类结果也有差异. 1.00.7150.7150.7150.715 0.7151.00.9880.8690.807 对R求传递闭包得到矩阵R*=0.7150.9881.00.690.807,此时d2(R,R)=2.929.与 0.7150.8690.8691.0O.807 0.7150.8070.8070.8071.0 R和P相比,R的传递闭包矩阵的失真”很严重,再用其进行聚类已经不合适了 虽然我们给出实例证眀全局最优模糊等价矩阵不具有唯一性,但是这并不影响 FCMBP算法的性能.对 于绝大部分模糊相似矩阵来说,全局最优模糊等价矩阵都是唯一的.我们做了20次实验,每次实验中随机产 生一百万个模糊相似矩阵,然后用 FCMBP算法求解其全局最优模糊等价矩阵.实验结果表明:每一百万个 模糊相似矩阵中,全局最优模糊等价矩阵不唯一的矩阵平均有30个,占总数的0.003%;20次实验中,全局最 优模糊等价矩阵不唯一的矩阵最多的一次有43个,占总数的0.0043%.并且,一个模糊相似矩阵的全局最优 模糊等价矩阵是否唯一是由矩阵夲身决定的.如果给定旳模糊相似矩阵存在两个或多个全局最优模糊等价矩 阵,则 FCMBP算法能够求出所有的全局最优模糊等价矩阵,可根据实际情况选择最合适的一个用于聚类. 4 FCMBP算法可行解的个数 为了方便分析 FCMBP算法所求可行解的个数,我们先给出几个基本的定义 第7期 赵卫中,等:基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析 1243 41基本定义及相关说明 定义5对于ⅹ∈Kn,置换σ∈S,称σ为关于X的不变置换,如果它满足X=X.关于X的所有 不变置换的个数,称为X的不变置换数,记作丌(X) 再定义一个n阶等价标准型集合Xn上的二元关系 定义6对于ⅹ1∈Kn,Ⅺ2∈Xn,我们称等价标准型X1、X2满足置换相等关系⊙,如果X1≈X2并 且存在一个置换a,使(X1)o=X2.记作X1⊙X2 显然二元关系⊙满足自反性,对称性和传递性,即⊙是一个等价关系.由等价标准型X形成的⊙等价 类记作[X⊙.可以看出,同一个⊙等价类中两个不同的等价标准型有相同的参数图,并且经过某个置换操 作后,二者是相等的 例3如下所示的等价标准型以及对应的标准参数系 t. 1 t1 t1 t1 t ti t1 l t4 t3 t3 t4 F ti t ta 1 t3 t3 titi t3t3 t5 1 经过置换 123456 后,变为 125634 t2 1 ti t1 tI t1 t1 t1 1 ts t3 t3 ti ti t5 1 t3 t t1 ti ts t ti t1 tsts t4 1 Eo和E的参数图相同,即E≈E,由定义6可知,E⊙E 42 FCMBP算法可行解个数分析 FCMBP算法求出的可行解由三部分得到:等价标准型E#,置换σ和最优模糊等价矩阵R#,其中最 优模糊等价矩阵#由等价标准型B#和置换确定满足R#=E1,根据各部分的不同, FCMBP 算法求出的可行解分为三种情况: 1)等价标准型E相同,置换σ#不同,最优模糊等价矩阵R#相等 对于这种情况, FCMBP算法求出的多个可行解中,不同的置换a#都是关于等价标准型E#的不变置 换,所以最优模糊等价矩阵R#相等. 10.20.10.50.4 0.210.40.60.2 例4对于模糊相似矩阵R 01041030.3, FCMBP算法求出的可行解中,等价 0.50.60.310.8 0.40.20.30.8 0.4000.2830.2830.283 0.40010.2830.2830.283 标准型E# 2345 0.2830.28310.4500.450,置换a 置换 31245 0.2830.2830.45010.800 0.2830.2830.4500.8001 12345 ,最优模糊等价矩阵B种=B1=B·其中和都是关于E#的 3124 不变置换 一般地,有如下结论: 1244 系统工程理论与实践 第30卷 定理11如果 FCMBP算法求出的可行解中等价标准型E*相同,置换σ*不同,最优模糊等价矩阵 R≠相等,则 FCMBP算法所求可行解的个数m等于标准型E#的不变置换数丌(E#) 证明由定义5和最优模糊等价矩阵满足R#=B学1,可知定理成立 例4中的等价标准型E#,其不变置换数(E#)=4E≠其他两个不变置换为=(12345 321 o4 12345 ,满足E() E 即 FCMBP算法所求可行解的 32145 个数m=丌(E#)=4 2)等价标准型E#不同,置换σ#不同,最优模糊等价矩阵R#相等 对于这种情况, FCMBP算法求出多个可行解是因为等价标准型E形成的⊙等价类[E#⊙中包含多 个等价标准型,不同的等价标准型绎过不同的置换后,得到相等的最优模糊等价矩阵. 0.4230.3030.6850.473 0.4231.008260.0550.73 例5对于模糊相似矩阵R=0.3030.826100.9920.588,算法求出的两个可行解,等价 0.6850.0550.9921.00.606 0.4730.730.5880.6061.0 标准型 1.00.4710.4710.4710.471 0.4711.00.9920.5190.519 04710992100.5190.519,对应的置换 12345 15234 等价标准型 0.4710.5190.5191.00.73 0.4710.5190.5190.731.0 1.00.4710.4710.4710.471 0.4711.00.730.5190.519 0.4710.731005190.519,对应的置换a2 12345 0.4710.5190.5191.00.992 543),最优模糊等价矩 0.4710.5190.5190.9921.0 阵R=(E)()1=(E)()一 可知.E和E4有相同的参数图,并且存在置换 l2345 1452),使(E1)n=E,所以 一般地,有结论: 定理12如果 FCMBP算法求出的可行解中等价标准型E*不同,置换σ#不同,最优模糊等价矩阵 R#相等,则 FCMBP算法所求可行解的个数m=∑丌(E) E∈[E 证明由定理11的结论, FCMBP算法所求可行解中,等价标准型相同的解的个数等于该等价标准型的 不变置换数.由E产生的⊙等价类[E]中不同的等价标准型经过不同的置换斤,可以得到相等的最优 模糊等价矩阵.故有结论: FCMBP算法所求可行解的个数m=∑π(E).定理得证 E∈[E#]⊙ 3)等价标准型#不同,置換σ#不同,最优模糊等价矩阵B#不等 对于这种情况,由于模糊相似矩阵本身的原因,存在两个不等的最优模糊等价矩阵潢足与该模糊相似矩 阵的距离都是最小的,这也说明了全局最优模糊等价矩阵不具有唯一性. 如例2中的矩阵R, FCMBP算法求出的两个可行解,第一个可行解等价标准型 1.00.3310.3310.3310.331 0.3311.00.4890.4890.489 E=0:3104901007340.734,置换 12345 24531 0.3310.4890.7341.00.988 0.3310.4890.7340.9881.0 第7期 赵卫中,等:基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析 1245 最优模糊等价矩阵R(例2中给出),第二个可行解等价标准型 1.00.8070.370.370.37 0.8071.00.370.370.37 E 0.370.371.00.6170.617 0.370.370.6171.00.98 0.370.370.6170.9881.0 置换o 1 345 34512 最优模糊等价矩阵艺(例2中给出,其中R和B2都是全局最优模糊 等价矩阵 一般地,有结论 定理13如果 FCMBP算法求出的可行解中等价标准型E不同,置换σ#不同,最优模糊等价矩阵 R*不等,则 FCMBP算法所求可行解的个数m=∑∑π(E),其中s是不等最优模糊等价矩阵的个 E∈E]⊙ 数,E#(k=1,2,…,5)是每个不等最优模糊等价矩阵对应的等价标准型 证明由定理11和定理12,可得结论 5结论 在本文中,我们对基于摄动的模糊聚类算法进一步深入研究.首次给岀一个模糊相似短阵的实例,并找 到与该模糊相似矩阵的距离相等且都是最小的两个不相等的最优模糊等价矩阵,从而证明了全局最优模糊等 价矩阵不具有唯一性. FCMBP算法求岀的可行解包括三部分:等价标准型E≠,置换σ#和最优模糊等价矩 阵R其中最优模糊等价矩阵P由等价标准型E和置换确定,满足B#=E)根据算法求 出可行解的不同情况,给出每种情况下可行解个数的计算表达式.通过本文的工作,完善了 FCMBP算法的 相关理论 参考文献 1 Ruspini E H. A new approach to clustering[J]. Information and Control, 1969, 15(1): 22-32 2 Zadeh L A. Fuzzy setsJ. Information and Control. 1965, 8: 338-353 3罗承忠.模糊集引论(上册)[M].北京:北京师范大学出版社,1989 Luo C Z. Introduction to Fuzzy Sets(Vol. 1M. Beijing: Beijing Normal University Press, 1989 4]李相镐,李洪兴,陈世权,等模糊聚类分析及其应用[M].贵阳:贵州科学技术出版社,194 Li X H, Li H X, Chen s Q: ct aL. Fuzzy Clustcring Analysis and Applications[ M. Guiyang: Guizhou Scicncc nd Technology Press, 1994 5]肖奚安.求Fzzy可传闭包的升值法J.模糊数学,1985,4(5):71-73 XiaoX A. Ascending approach to fuzzy transitive closure[J. Fuzzy Mathematics, 1985, 4(5 :71-73 6]朱剑英.应月模糊聚类法应注意的若干关键问题可.模糊系统与数学,1987、1(1):104-111 Zhu Y. Some important questions in application of fuzzy clustering method J. Fuzzy Systems and Mathematics 1987,1(1):104-11 7 LiH X Fuzzy clustering methods based on perturbation[J. Fuzzy Sets and Systems, 1989, 33(3): 291 302 8]何清,李洪兴.Fuzy相似矩阵方程ⅹ2=X与最优模糊等价矩阵的存在性J.模糊系统与数学,199,183(3):7786 He Q, Li H X Fuzzy similar mat rix equation X=X and the existence of optima.l fuzzy equivalence mat rix[J] F Syst d Mathematics, 1999, 13 3 :77-86 ⑨]何清,李洪兴.模糊聚类中的模糊等价矩阵卩.系统工程理论与实践,199,194):8-1 He Q, LiH X. Fuzzy equivalent matrices in fuzzy clustering. Systems Engineering- Theory Practice, 1999 10]何清,徐树富,王加银,等 FCMBP聚类法在语音识別和模糊控制中的应用小.系统工程学报,2001,16(6):430437 He Q, Xu sf, Wang JY, et al. FCMBP clustering methods and its applications in speech recognition and fuzzy controlJ] Journal of Systems Engineering, 2001, 16(6):430-437 11 He Q, Li H X, Shi Z Z, ct al. Fuzzy clustcring mcthod based on perturbation J. International Journal of Computers and Mathematics with Applications, 2003, 40: 929-946

...展开详情
试读 8P 论文研究-基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析.pdf 5积分/C币 立即下载
    1/8
    论文研究-基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析.pdf第1页
    论文研究-基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析.pdf第2页
    论文研究-基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析.pdf第3页

    试读已结束,剩余5页未读...

    5积分/C币 立即下载 >