《模糊数学精品讲义3.6模糊关系与聚类分析2.ppt》由会员分享，可在线阅读，更多相关《模糊数学精品讲义3.6模糊关系与聚类分析2.ppt（136页珍藏版）》请在三一办公上搜索。
1、1,3.6.4 模糊传递闭包和等价闭包 通常的模糊关系，不一定有传递性，因而不是模糊等价关系，对这种模糊关系直接进行上述分类显然是不合理的。为此，我们希望寻求一种方法，能将不是等价的模糊关系进行改造，以便分类使用,2,定义 3.6.13 设 RF(X X)，称 t(R)为 R 的传递闭包，如果 t(R)满足:(1)传递性：(t(R)2 t(R)；(2)包容性：R t(R)；(3)最小性：若 R是 X 上的模糊传递关系，且 R R t(R)R，即 R 的传递闭包是包含 R 的最小的传递关系。,3,定理 3.6.2 设 RF(X X)，则证明：(1)首先证明 是传递的，即要证明,4,由传递性定义知
2、，是传递的。,5,(2)显然有(3)若有 R 使 R R且 R是传递的，则由 R R 有 R2(R)2 R,R3=R R2 R R(R)2 R,一般有 Rn R,从而,6,即 含于任一包含 R 的传递关系中。综上所述，是包含 R 的最小传递关系，因而是 R 的传递闭包，即,7,在论域为有限集的情况下，传递闭包的计算变得很简捷。命题 3.6.8 设|X|=n，RF(X X)，则 证明略。,8,推论 设|X|=n，RF(X X)，且 R 是自反关系，则存在正整数 m(n)，使 t(R)=Rm，且 l m 有 Rl=t(R)。证明 因为|X|=n，所以又因为 R 是自反的，由命题 3.6.5(2)知
3、R R2 R3,9,因而 在做上述合成运算时，若做到 m(n)次时，出现了 Rm+1=Rm，则有 Rm+2=Rm，进而，t(R)=Rm。这时，若我们取正整数 l m，则有,10,即有Rl=t(R)。上述推论说明，在计算有限论域上自反的模糊关系 R 的传递闭包时，可以从 R 开始，反复自乘，依次计算出 R，R2，R4，当第一次出现 RkRk=Rk 时，就有 t(R)=Rk。,11,命题 3.6.9 模糊关系的传递闭包 t(R)有以下性质：(1)若 I R，则 I t(R)。(2)(t(R)-1=t(R-1)。(3)若 R-1=R，则(t(R)-1=t(R)。证明(1)由定理 3.6.2 可得。(
4、2)由定理 3.6.2、命题 3.6.4(3)及推论(1)，有,12,(3)由(2)即得。上述命题中的(1)说明自反关系的传递闭包还是自反的，(3)表明对称关系的传递闭包还是对称的。,13,定义 3.6.14 设 RF(X X)，称 e(R)为 R 的等价闭包，若 e(R)满足下述条件：(1)等价性：e(R)是 X 上的模糊等价关系。(2)包容性：R e(R)。(3)最小性：若 R 是 X 上的模糊等价关系，且 R R e(R)R。显然，R 的等价闭包是包含 R 的最小的等价关系。,14,定理 3.6.3 设 RF(X X)是相似关系(即 R 是自反、对称模糊关系)，则e(R)=t(R),即模
5、糊相似关系的传递闭包就是它的等价闭包。证明 因为 R 是自反和对称的，由命题 3.6.9 知，R 的传递闭包 t(R)也是自反和对称的。又 t(R)作为传递闭包本身是传递的，且包含 R，因此 t(R)是,15,包含 R 的模糊等价关系。若 R 也是模糊等价关系，且包含 R。由于 R 是传递的，t(R)是最小传递闭关系，故有 t(R)R。综上所述，当 R 是相似关系时，t(R)是包含 R 的最小等价关系，因而 t(R)是 R 的等价闭包，即e(R)=t(R)。,16,引理 设 Rnm，Qml 是两个模糊矩阵，则对 0，1 有(RQ)=RQ。证明 记 R=(rij)、Q=(qij)、RQ=Snl=
6、(sij)，类似地，又记 R=(rij)、Q=(qij)、S=(sij)。由于,17,sij=1 sij t1，2，m，使 rit qtj t1，2，m，使 rit，qtj t1，2，m，使 rit=1，qtj=1又注意到rik、qkj、sij只取0和1，故(RQ)=RQ。,18,由此引理可得，(Rl)=(R)l。推论 设|X|=n，R 是 X 上的模糊相似关系，则(1)m n，使 e(R)=Rm，且 l m 时有 e(R)=Rl。0,1，(e(R)=e(R)。证明(1)由命题 3.6.8 的推论及定理 3.6.3 可得。(2)0,1，由于 R 也是 X 上的相似关系，,19,则由(1)，m2
7、 n，使 e(R)=，且 l m2 有 e(R)=(R)l。又由(1)，m1 n，使 e(R)=，且 l m1 有 e(R)=Rl。令 l=max(m1，m2)，则 e(R)=Rl，从而(e(R)=(Rl)，且 e(R)=(R)l。由引理可知(Rl)=(R)l，从而(e(R)=e(R)。,20,在实际问题中建立的模糊关系，多数情况下都是相似关系，定理 3.6.3 给我们提供了一个求相似关系的等价闭包的方法。当论域为有限集时，此法很简便，即对相似矩阵 R，求 R2，R4，当 RkRk=Rk 时，便有 e(R)=t(R)=Rk。,21,例 3.6.10 已知一个模糊相似矩阵 R求 e(R)。,22
8、,解：,23,R8=R4 R4=R4，故 e(R)=t(R)=R4。,24,对等价矩阵 e(R)=R4 进行动态聚类，其结果如图3.39 所示 x1 x6 x2 x4 x7 x5 x3 1 0.9 0.8 0.7图 3.39 动态聚类图,25,从上例中可以看出，(1)对于相似矩阵每作一次平方合成运算，模糊矩阵中的元素值便增大一次，也就是 R R2 R4。(2)我们还可以看到，若对原来的相似矩阵 R，先作其 截集，则我们便得到一个经典的相似矩阵 R，由于从定理 3.6.3 的推论(2)可知(e(R)=e(R)，这样要对 e(R)作动态聚类时，可以先对相似矩阵作,26,截集，得到经典的相似矩阵，然
9、后再求经典相似矩阵的等价闭包 e(R)。由于经典相似矩阵中的元素仅有 1 与 0（即非此即彼）两种，找出所有元素相关值为 1 的元素，加以归并，就可以找出该元素的等价类，从而可以用简单的方法来求 e(R)。以上所述的理论，在以下的定理中详细说明。,27,若 R 不是相似关系，R 的等价闭包是否存在？又如何求得其传递闭包？下面的定理回答了这个问题。定理 3.6.4 设 R F(X X)，则 R 的等价闭包 e(R)必存在，且 e(R)=t(R*)，式中 R*=R R-1 I。证明 先证 R*是包含 R 的相似关系。因为 R R*，,28,I R*，故 R*是包含 R 的自反关系。又有(R*)-1
10、=(R R-1 I)-1=R-1(R-1)-1 I 1=R-1 R I=R R-1 I=R*（对称性得证），故 R*是包含 R 的相似关系。又由定理 3.6.3，t(R*)是模糊等价关系，且,29,R R*t(R*)。次证 t(R*)是 X 上包含 R 的最小等价关系。设 RF(X X)，R 是等价关系，且 R R，R-1(R)-1=R，从而R*=R R-1 I R。于是(R*)2(R)2 R，(R*)3=(R*)2 R*R R R。,30,一般地(R*)n R，从而 综上所述，t(R*)是包含 R 的最小等价关系，故 t(R*)是 R 的等价闭包。当然 R 的等价闭包是存在的。,31,3.6
11、.5 求相似矩阵的等价类的直接方法定理 3.6.5 设|X|=n，R 是 X 上的经典相似关系，x X 时，记 R x=y X|(x,y)R，并称 Rx 为 X 的相似类。记=e(R)=t(R)。设 x0 X，于是(1)令 P1(x0)=Rx|Rx Rx0（相交不空的相似类之集），则,32,(2)令 P2(x0)=Rx|Rx P1(x0)，则(3)设 P1(x0)P2(x0)Pm(x0),且 Pm(x0)满足条件：若Rx Pm(x0)Rx Pm(x0)=(3.6.24)则证明略。,33,定理 3.6.5 表明：对于一个经典相似关系，可以通过归并相似类的办法，得到它的等价类，所有等价类的并就是它
12、的等价闭包。这样，我们就得到一个求等价类的直接方法，即先用不同的 值作相似矩阵 R 的截矩阵 R，因 R 是一个经典相似阵，于是便可用本定理的方法通过归并相似类来求等价类。,34,例 3.6.11 设 X=x1,x2,x7，R 是 X 上的模糊相似关系试以 R 为依据将 X 中的元素分类。,35,解:先用平方法，求 R 的等价闭包 e(R)。,36,再平方再平方，得 R8=R4。由命题 3.6.8 及定理 3.6.3 知 e(R)=R4，依次取 截关系 R，R 是经典等价关系，它诱导出 X 上的一个划分 X/R,将 X 分成一些等价类,37,当=1 时，有e(R)1 诱导的分类为 x1,x4,
13、x5,x7,x2,x3,x6。,38,当=0.8 时，有e(R)0.8 诱导的分类为 x1,x4,x5,x7,x2,x6,x3。,39,当=0.7 时，有e(R)0.7 诱导的分类为 x1,x4,x5,x7,x2,x3,x6。,40,当=0.5 时，有 e(R)0.5=E，即 e(R)0.5 将 X 分成一类 x1，x2，x3，x4，x5，x6，x7。随 由大到小，分类由细到粗，形成一个动态的分类图，如图 3.40 所示.,41,x1 x4 x5 x7 x2 x6 x3 1 0.8 0.7 0.5图 3.40 动态聚类图,42,现在用直接法，由相似类的归并而求等价类。先求关于 e(R)1=e(
14、R1)的等价类，为此先列出关于 1=1 的相似类。由于,43,故 R1 的相似类是R1x1=x1，x4（对应于 r14=1）R1x2=x2（对应于 r22=1）R1x3=x3 R1x4=x1，x4，x5 R1x5=x5，x7 R1x6=x6。在上述相似类中寻找相交不空的类，然后归并。,44,因为x1，x4 R1 x1 R1 x4，于是归并得到P1(x1)=R1 x1 R1 x4=x1，x4，x5，又因为有x5 P1(x1)R1 x5，再次归并得到P2(x1)=R1x1 R1x4 R1x5=x1，x4，x5，x7。,45,由于不含于 P2(x1)的 R1 的相似类(在本例中即 R1x2,R1 x
15、3,R1 x6)与 P2(x1)不相交，所以以 x1 为代表的关于 e(R1)=e(R)1 的等价类就是 P2(x1)。其余类似。在本例中，因其余的相似类两两不相交，不需归并，它们就是相应的等价类，因而我们最终得到关于e(R)1 的等价类为x1，x4，x5，x7，x2，x3，x6（3.6.25）,46,其次，取 2=0.8。由于,47,故 R0.8 的相似类是R0.8x1=x1，x4（对应于 r14=1）R0.8x2=x2，x6（对应于 r26=1）R0.8x3=x3 R0.8x4=x1，x4，x5 R0.8x5=x5，x7在上述相似类中寻找相交不空的类，然后归并。,48,P2(x1)=R1x
16、1 R1x4 R1x5=x1，x4，x5，x7。因其余的相似类两两不相交，不需归并，它们就是相应的等价类，因而我们最终得到关于 e(R)0.8 的等价类为x1，x4，x5，x7，x2，x6，x3(3.6.26),49,或：当 2=0.8 时，此时，由于 r26=0.8，应将 e(R)1x2（即R1 x2）与 e(R)1 x6（即 R1 x6）归并，即将(3.6.25)中 x2 所在的等价类与 x6 所在的等价类归并（若还有另外的 rij=0.8，类似进行），归并后得到关于 e(R)的等价类为 x1，x4，x5，x7，x2，x6，x3(3.6.26),50,再次，取 3=0.7，由于,51,故
17、R0.7 的相似类是 R0.7x1=x1，x4R0.7x2=x2，x3，x6 R0.7x4=x1，x4，x5 R0.7x5=x5，x7 在上述相似类中寻找相交不空的类，然后归并，于是得到关于 e(R0.7)=e(R)0.7 的等价类如下x1，x4，x5，x7，x2，x3，x6。(3.6.27),52,取 4=0.6，由于这时没有给出新的分类结果，即由 e(R)0.6 得到的等价类与 e(R)0.7 的等价类相同。,53,取 5=0.5，由于,54,故 R0.5 的相似类是 R0.5x1=x1，x4，x5，x6，x7R0.5x2=x2，x3，x6 将上述相似类归并后，得到关于 e(R0.5)=e
18、(R)0.5 的等价类是将全部元素归入一类的结果。综上所述，最后所得的聚类结果亦如图 3.40 所示。,55,3.6.6 直接聚类的最大树法 用图形来直接进行聚类，更为方便。设 R=(rij)nn 是 X=x1，x2，xn 上的模糊相似关系，rij=R(xi，xj)表示 X 内元素 xi 与 xj 的相关程度。在图形上，用顶点表示元素 xi，xj，连接 xi 与 xj 的线段称为边，边旁标明的数字为 rij，称为该边的强度，由边依次连接 k 个顶点：xi1,xi2,xik,56,称为链。顶点不相同的链称为通道，记为 L(xi1,xik)。通道中各边强度的最小值为该通道的强度，即通道 L(xi1
19、,xik)的强度=ri1i2 rik-1ik 任意点间都有通道的图形称为连通图，起点与终点重合的链称为回路，无回路的连通图称为树（参见图 3.41）,57,xi rij xj rjk xk 图 3.41 通道与链,58,用图形法来进行直接聚类时，是把相似类归并为关于e(R)的等价类。归并时，使阈值 逐步从大到小，依次把强度为 的边连接有关的顶点，但注意不连回路，也就得到若干边的强度为 的通道。对0,1，在不同 水平上将若干通道相连，就得到若干互不相连的树。每棵树中任意两顶点间通道的强度大于等于，这些互不相连的树就给出了分类的结果：同一棵树的顶点归于同一类。从大到小，直至得到最大的树的过程，给出
20、论域 X 中元素的一个动态分类结果。,59,例3.6.12 用最大树法对例 3.6.11 直接聚类。=1 时的图形如图 3.42 x1 x3 1 x2 x4 1 x6 x5 1 x7图 3.42=1 时的连通图对应的分类为 x1,x4,x5,x7,x2,x3,x6。,60,=0.8 时的图形如图 3.43 x1 x3 1 x2 x4 0.8 1 x6 x5 1 x7图 3.43=0.8 时的连通图对应的分类为x1,x4,x5,x7,x2,x6,x3。,61,=0.7 时的图形如图3.44 x1 x3 0.7 1 x2 x4 0.8 1 x6 x5 1 x7图 3.44=0.7 时的连通图对应的
21、分类为 x1,x4,x5,x7,x2,x6，x3。,62,=0.5 时的图形如图 3.45，是最大树，0.5 x1 x3 1 0.7 x2 x4 0.8 1 x6 x5 1 x7图 3.45=0.5 时的连通图对应的分类为 x1,x2,x3,x4,x5,x6，x7。,63,注：从最大树图中可以看出，若去掉那些强度小于 的边，就把最大树截成互不相连的几棵子树，这就是对应 水平上的一种分类结果，同一棵树上的顶点属于同一等价类。,64,例 3.6.13 用直接法求例 3.6.10 给出的模糊相似矩阵 R 的等价类，并作出最大树图。即求 R 的等价类。,65,解=1 时的图形如下：,x6,66,解=0
22、.9 时的图形如下：,67,解=0.8 时的图形如下：,68,解=0.7 时的图形如下：,69,我们用最大树法给出问题的动态聚类。当=1 时，由最大树得对应的分类为：x1，x6,x2，x4，x7,x3，x5。当=0.9 时，由最大树得对应的分类为：x1，x2，x4，x6，x7,x3，x5。当=0.8 时，由最大树得对应的分类为：x1，x2，x4，x5，x6，x7,x3。当=0.7 时，由最大树得对应的分类为：x1，x2，x3，x4，x5，x6，x7。,70,教材 P133 用归并相似类法给出了同样的分类。求模糊相似关系的等价类有以下三种方法：等价闭包法(e(R)间接法 归并相似类法 最大树法,
23、直接法,71,3.6.7 模糊聚类分析 模糊聚类分析在实际问题中有广泛的应用，这是由于实际问题中，一组事物是否属于某一类常带有模糊性，也就是问题的界限不是十分清晰的。我们不能明确地回答“是”或“否”，而是只能作出“在某种程度上是”的回答，这就是模糊聚类分析。本节主要讨论基于模糊等价关系的动态聚类的实际应用。,72,1.特征抽取 假设待分类对象的集合为 X=X1,X2,Xn，集合中的每个元素具有 m 个特征，设第 i 个对象 Xi 的第 j(j=1,2,m)个特征为 xij，则 Xi 就可以用这 m 个特征的取值来描述，记Xi=(xi1,xi2,xim)(i=1，2，n)(3.6.28),73,
24、为了计算简便，并使特征仅具有相对的意义，我们要首先对特征的观测值进行预先处理，使各特征值的取值在单位区间 0,1 中。设 Xi 的观测值为 Xi 0，Xi0=(xi10，xi20，xim0)(i=1,2,n)(3.6.29)所以用下列各公式对 Xi 0 进行“规格化”的预处理。,74,(1)xij=cxij0(i=1,n；j=1,m)(3.6.30)c 是一个常数，选择 c 使任何 xij 在 0,1 中。(2)xij=cxij0/max(xij0)(i=1,n;j=1,m)(3.6.31)即选择所有的特征中的最大值作分母。(3)当特征值中出现负值时，则用下式压缩到 0,1：,75,当特征值不
25、是负值时，当然也可以用上式来“规格化”式中 是全部特征值的均值，分子是特征值与均值的距离。用此式“规格化”时应注意：只要与均值的距离相等，特征值的大小的方向性就被“湮灭”。,76,2.建立 X 上的模糊关系（模糊相似矩阵）设待分类对象的全体是 X=X1,X2,Xn，我们首先要鉴别 X 中的元素 Xi 与 Xj 的接近程度（相似程度）。用 0,1 中的数 rij 来表示 Xi 与 Xj 的相似程度，称为相似系数。相似系数组成一个矩阵(rij)nn 称为相似系数矩阵，它是 X 上的模糊相似关系。我们对此关系矩阵求其等价闭包或等价类，就能对 X 中的元素进行聚类。,77,为了确定相似系数，必须使相似
26、系数符合自反、对称的要求，可根据实际情况选用下列方法之一。1）数量积法其中,78,2）夹角余弦法3）相关系数法其中,79,4）指数相似系数法其中 sk 与 m 为常数。5）绝对值指数法,80,6）绝对值倒数法其中 M 为适当选择的常数，M 的选择使 rij0,1。,81,7)非参数法令 是 xik 与 xjk 的均值），nij+=xi1 xj1,xi2 xj2,xim xjm 中正数个数，nij=xi1 xj1,xi2 xj2,xim xjm 中负数个数，,82,8）贴近度法 贴近度表示两个模糊向量之间接近的程度，它符合自反、对称的要求，所以可以用来表示相似系数。我们将 X 中的元素 Xi，X
27、j 看成是各自特征的模糊向量，便可以用贴近度来表示相似系数 rij，rij=(Xi,Xj),83,(1)当 取内外积贴近度时或,84,(2)最大最小法，当 取(3.5.47)式时(3)算术平均最小法，当 取(3.5.48)式时,85,(4)几何平均最小法，当 取(3.5.51)式时(5)绝对值减数法，当 取距离贴近度时rij=1c(dp(Xi，Xj)式中 c，为常数，p 为各种距离的代码系数。,86,当 p=1 时，dp 就是海明距离，此时求相似系数的方法称绝对值减数法，其相似系数为 当 p=2 时，dp 就是欧氏距离，此时有,87,9）经验法请有经验的人来分别对 Xi 与 Xj 的相似性打分
28、，设有 s 个人参加评分，若第 k 个人(1 k s)认为 Xi 与 Xj 相似的程度为 aij(k)（在 0，1 中），他对自己评分的自信度也打分，若自信度分值是 bij(k)，则可以用下式来计算相似系数:,88,在以上确定相似系数的诸多方法中，究竟选用哪一种合适，需要根据问题的具体性质来决定。,89,例3.6.14 环境单元分类每个环境单元可以包括空气、水分、土壤、作物等四个要素。环境单元的污染状况由污染物在四要素中含量的超限度来描写。假设有五个单元 x1,x2,x3,x4,x5，它们的污染数据如表 3.13 所示。,90,取论域 X=x1,x2,x3,x4,x5，按(3.6.30)式“规
29、格化”，取 c=0.1，再按（3.6.46）式求相似系数（取 c=1)，,表3.13 污染数据,91,得到模糊相似矩阵,92,3.聚类 可以有三种方法来对模糊相似矩阵聚类。1）传递闭包法（平方法）求出模糊相似矩阵的传递闭包 t(R)，它就是 R 的等价闭包 e(R)=t(R)，然后求其 截关系 e(R)。它是经典等价关系，让 从 1 降至 0，当 变化时，它们给出一个动态的分类结果。求 R 的传递闭包 t(R)时，可以用平方法，即求 R2,R4,Rk，若有 Rk Rk=Rk，则 t(R)=Rk。,93,经计算可知,94,当=1 时，分成五类：x1,x2,x3,x4,x5当=0.8 时，分成四类
30、：x1,x3,x2,x4,x5当=0.6 时，分成三类：x1,x3,x2,x4,x5当=0.5 时，分成二类：x1,x3,x4,x5,x2当=0.4 时，分成一类：x1,x2,x3,x4,x5,95,其动态分类如图 3.47 所示：=1 x1 x3 x4 x5 x2 0.8 0.6 0.5 0.4,图 3.47 动态聚类图,96,2）直接聚类法 根据模糊相似矩阵(3.6.49)来直接由相似类求等价类。当=1 时，该矩阵只有对角线上的元素为 1，所以不许归并相似类，所得到的 e(R)1 的等价类为x1，x2，x3，x4，x5。当=0.8 时，先求经典矩阵 R0.8，有此求得它的相似类是,97,R
31、0.8x1=x1,x3，R0.8x2=x2，R0.8x4=x4，R0.8x5=x5。在归并时，找不到与 x1,x3 相交的其它等价类，于是 e(R)0.8 的等价类为：x1,x3,x2,x4,x5。同样=0.6 时，相似类为 R0.6x1=x1,x3,R0.6x2=x2,R0.6x4=x4,x5，也无法再进一步归并，于是 e(R)0.6 的等价类为：x1,x3,x2,x4,x5。,98,当=0.5 时，相似类为 R0.5x1=x1,x3,x4，R0.5x2=x2,R0.5x4=x1,x4,x5，因此可以把相似类 R0.5x1 与 R0.5x4 归并，得 P1(x1)=R0.5x1 R0.5x4
32、=x1,x3,x4,x5，最终得到的 e(R)0.5 的等价类为x1,x3,x4,x5,x2。当=0.4 时，得到 R0.4x2=x2，x5，于是可以和 P1(x1)归并，即 P2(x1)=x1,x2,x3,x4,x5，这就是 e(R)0.4 的等价类。,99,3）最大树法（Kruskal）在模糊相似矩阵(3.6.49)中，从=1 开始逐步做连通图，直到=0 时为止，每作一条边，就在边上写出 rij 之值（连通强度）。注意不要做回路。从原则上来说，可以选择任一元素（顶点）作为起始点，但一般总是选有相似类的元素开始。例如在本例中当=0.8 时，就有相似类 x1,x3，于是就把 x1 选为起始顶点
33、，先作出强度为,100,0.8 的边，然后再作强度为 0.6 的边及强度为 0.5 和 0.4 的边，这样就得到最大树，如图 3.48 所示。,图 3.48 最大树,101,在不同 水平上的分类，就是在最大树中砍去那些强度小于 的边，再分类。例如=0.8 时，砍掉最大树右边的各枝，就得到分类：x1,x3,x2,x4,x5；而在=0.6 时，只砍掉强度为 0.5 和 0.4 的边，于是得到的分类就是：x1,x3,x2,x4,x5。,102,经济区的模糊分类法在经济学理论研究中，有一种观点认为经济结构相似的区域，应该生产或销售相近的产品，研究如何给出这些区域的划分问题就称为经济区的分类问题。下面我
34、们用模糊聚类的方法来讨论这一问题，因此将其称为经济区的模糊分类法。,103,例 一家企业主要生产和销售六类产品，记为C=c1，c2，c3，c4，c5，c6，已知该企业有七个市场，记为X=x1，x2，x3，x4，x5，x6，x7。为了便于管理和获得更好的经济效益，该企业对适合于不同区域的产品类别这一商业结构进行了研究。,104,假设各类产品对不同区域的适应情况可以用 0,1区间中的数值来确定(估计)，这时我们可以对每个区域 xi（i=1，2，7）给出一个模糊集 xi，如,105,106,用绝对值减数法来确定它们的相似系数，为,于是我们得到 X 上的一个模糊相似关系，其对应的模糊相似矩阵 R 为：
35、,i，j=1，2，3，4，5，6，7。,107,108,其传递闭包为,109,如果将前面的模糊相似矩阵 R 中的数据行、列互换，我们立即可以得到对每类产品 ci（i=1，2，6）给出的模糊集 ci，,110,111,仍用绝对值减数法来确定它们的相似系数，得,于是我们得到 C 上的一个模糊相似关系，其对应的模糊相似矩阵 R 为：,i，j=1，2，3，4，5，6。,112,113,其传递闭包为,传递闭包对应的动态分类如下表：,114,115,应该指出，用模糊等价关系矩阵来分类（或用等价类分类），所依据的矩阵已经不是原来的矩阵了，这样分类必然带来误差。作者在 1983 年提出求相似矩阵 R 的最小距
36、离的传递矩阵 Rmin，再依据 Rmin 来分类。经过 15 年的努力，今年已有报导，此问题已获解决，但论文尚待发表20。,116,3.6.8 模糊 ISODATA Interactive Self-Organizing Data 法以上介绍的方法，都是基于模糊等价关系的聚类方法，这种聚类方法的优点是聚类灵活，可以根据不同的阈值来聚类。但在聚类前必须作模糊相似矩阵；在聚类过程中，没有充分利用人们已有的分类经验；分类后不知道每一类别的聚类中心的信息。,117,为此人们希望能有一种可以充分利用人们已有的分类经验,且能知道聚类中心信息的软化分。模糊等价关系聚类法,最后是按 截关系组成的经典矩阵来划分
37、的，实质上还是一种硬化分，只不过增加了动态划分。我们希望知道各类样本隶属于某类的隶属度，这样就知道有多大的把握将这些样本划分在某类。以下介绍的模型 ISODATA 法就具有这样的优点。,118,1.问题的数学模型1）已知条件设已知 n 个待分类的样本，我们可以将它们视为论域 X 中的元素：X=X1,Xk,Xn,每个样本(元素)Xk 有 m 个特征：Xk=(xk1,xkj,xkm)(k=1,n)。,119,n 个样本(元素)的特征组成一个特征矩阵式中 xkj 为第 k 个样本的第 j 个特征(值)。,120,2）需要求解(1)设分成 s 类，求各类的聚类中心，即求 10 s 个聚类中心V=V1,
38、Vi,Vs；20 各聚类中心的特征Vi=(vi1,vij,vim)(i=1,2,s)；,121,30 各聚类中心组成的特征矩阵式中 vij 为第 i 聚类中心的第 j 特征(值)。,122,(2)设分成 s 类，求各样本(n 个)隶属于各类(s 类)的隶属度。10 s 个隶属度U=U1,Ui,Us；20 各样本属于第 i 类的隶属度Ui=(ui1,uik,uin)(i=1,2,s)；,123,30 n 个样本隶属于 s 类的隶属度矩阵式中 uik 为第 k 个样本属于第 i 类的隶属度,124,2.解法用迭代法来求解此问题。设某类聚类中心是 Vi，待分类的样本是 Xk，此样本愈接近聚类中心 V
39、i，则此样本隶属于第 i 类的隶属度愈大；若 Vj 是其它各类的聚类中心，此样本愈远离 Vj，则此样本愈不应被分在其它各类中。也就是说，下式说明了 Xk 与第 i 类的相对隶属关系（相对距离关系）：,125,式中 r 是正整数，通常取 r=2，k=1,2,n。易知，d(Xk,Vi)愈小，Xk 愈应划分在第 i 类，也就是说，样本 Xk 隶属于第 i 类的隶属度应愈大。综合对各个 Vj 的关系，于是便有,126,式中Xk=(xk1，xk2，xkm)，Vi=(vi1，vi2，vim)，Vj=(vj1，vj2，vjm)，i，j=1，2，s，k=1，2，n，通常 r=2。,127,若已知第 k 样本的
40、第 j 特征 xkj，又知第 k 样本隶属于第 i 类的隶属度 uik，那么下列乘积 fkij=(uik)r xkj(3.6.55)就表示了第 k 个样本特征值 xkj 在第 i 类的聚类中心相应的特征值中所占的比例，综合各类样本，就可以求得第 i 类聚类中心的第 j 个特征值 vij，,128,式中 通常 r=2，i=1，2，s，j=1，2，m。,129,130,公式(3.6.54)与(3.6.56)是一组迭代公式，vij 是第 i 个聚类中心的第 j 个特征，uik 是第 k 个样本隶属于第 i 类的隶属度，|是距离。给定(任意小数)，当 uik 多次迭代后与前一次的 uik 的差值小于
41、时，就认为迭代可以终止，此时的 uik 与 vij 就是求得的结果。全部迭代过程如图 3.49 所示。,131,图 3.49 模糊 ISODATA 法流程图,132,在解具体问题时，初始划分矩阵 Usn0 要按照经验来给定，uik 的取值愈接近各样本在不同类别中的隶属度，迭代收敛愈快，分类也愈精确，聚类中心值也愈接近实际情况。事实说明：若 Usn0 中各元素取相同的值，则迭代一定不收敛，所以初始划分矩阵不能任意选取，否则会出现振荡和发散的情况。,133,此外，模糊划分矩阵 Usn(包括初始、中间及最终的矩阵)还必须满足以下条件：(1)uik 0,1（归一性）；(2)k（划分性）；(3)i（非空
42、性）。,134,关于如何选取初始值的问题，至今尚未见有人作过系统的研究，作者曾在 1984 年的中美双边模糊数学学术讨论会上就此问题与模糊 ISODATA 法的创始人 J.C.Bezdek 18 博士作过讨论，他也认为这是一个未解决的理论难题。作者此后在 1987 年的模糊系统与数学创刊号上发表过一文17，特别对模糊等价关系法及模糊 ISODATA 法在理论上,135,存在的问题作了综述。当时作者在文中指出：“研究模糊 ISODATA 法迭代收敛问题的目的，就是要为迭代寻求收敛的准则。收敛与初始值及范数（距离）的关系如何？怎样用数学形式来描述收敛的指标？收敛性如何受到类别 C 及指数 r 的影响？改善收敛性、提高收敛速度应采取什么措施？这些都是为达到目的所必须搞清楚的理论问题。”所幸，经过 15 年的研究，我国学者已就这些问题获得不少进展。,136,1998 年何清在模糊系统与数学第 12 卷第 2 期上对十多年来我国及国际上模糊聚类分析的理论及应用研究的进展作了总结，指出：“朱剑英教授所提出的寻求失真最小的最优模糊等价矩阵问题在理论上已得到系统、圆满地解决。”但“朱剑英教授关于ISODATA 方法提出的几个问题尚未获得系统圆满地回答。”20,
