模糊关系与聚类分析.ppt

1、1,3. F关系与聚类分析,3.1 F关系的定义和性质 3.2 F矩阵 3.3 F关系的自反性与对称性 3.4 截集 3.5 F关系合成,2,3. F关系与聚类分析,3.6 F关系的传递性 3.7 F等价关系及聚类图 3.8 F相似关系 3.9 F聚类分析,3,三、 模糊关系合成运算性质： (1) 合成运算满足结合律 ( Q R ) S = Q ( R S ) ， 特别地 Rm Rn = Rm+n 。 (2) 合成运算关于并 “” 满足分配律 ( Q R ) S = ( Q S ) ( R S ) , (1) S ( Q R ) = ( S Q ) ( S R )。 (2),4,证明 只证(1

2、)。设 Q，RF (UV), SF (VW), 故有 ( Q R ) S = ( Q S ) ( R S )。,5,第二式证明相似。 应注意的是，1) 合成运算不满足交换律， 即 Q R R Q。如设 则 因此， Q R R Q。,6,2) 合成运算对交“”不满足分配律，即有下列二式： ( Q R ) S ( Q S ) ( R S ) , S ( Q R ) ( S Q ) ( S R )。 ( Q R ) S ( Q S ) ( R S ) , S ( Q R ) ( S Q ) ( S R )。 例如： 则,7,因此 ( Q R ) S ( Q S ) ( R S )。 同样可以举出反例

3、来说明第二个式子。 R = R = , ( UV ) R = R (UV ) = R 。 (4) 若 Q R，则 Q S R S ， P Q P R , Q n R n,8,定义 9 : 设 RF ( UV ) ，定义 R-1F ( V U ) 的隶属函数为 R-1( v，u) = R( u，v) ( ( v，u)V U), 称 V 到 U 的模糊关系 RT 为 R 的转置关系。 命题 4 :转置关系有下述性质： 设 R，R1，R2 F ( UV)， Rt | tT F ( UV), S F ( VW ) ,则 (1) 若 R1 R2 R1T R2T 。 (2) ( RT )T = R。,9,

4、推论 (1) 设 R F ( U U )，则 ( Rn )T = ( R T )n 。 (2) 设 R，QF (U U ) 且 R Q, 则 R n Q n ( n 为正整数)。,10,3.6 F等价关系 定义 10 : 设 R F ( U U ) (1) 称 R 是自反的 uU，R(u, u) =1 。 (2) 称 R 是对称的 u, v X ， R(u, v)= R(v, u) 。 (3) 若 R 是 U 上的自反、对称关系，则称 R 是 U 上的模糊相似关系，简称相似关系。,11,命题 5 设 R F ( U U ) ， 则 (1) R 是自反的 I R。 (2) R 是自反的 Rn R

5、n+1( n 1) 且 Rn 也是自反的。 证明 (1) 显然。,12,(2) 用归纳法证明包含式 Rn Rn+1。(u, v) UU, 有 故 R R2。设 Rn-1 Rn，由（7）式可得 Rn-1 R Rn R , 即 Rn Rn+1 。 因 I R Rn ( n 1)，由(1)知 Rn 是自反的。,13,命题 6 设 R，R1，R2 F ( U U )，则有 (1) R 是对称的 R = RT 。 (2) 若 R1、R2 都是对称的，则 R1 R2 对称 R1 R2 = R2 R1 ( 即 R1、R2 是可以交换的）。 (3) R 是对称的 Rn 是对称的 ( n 1)。 证明 (1)

6、由对称关系的定义可得。,14,(2) 先证()：若 R1 R2 是对称的，因 R1、R2 也对称，故 R1 R2 = (R1 R2)-1 = R2-1 R1-1= R2 R1 。 再证()：若 R1 R2 = R2 R1 ，则 (R1 R2)-1 = R2-1 R1-1 = R2 R1= R1 R2 由 (1) 知， R1 R2 是对称的。 (3) 若 R 对称，则有 ( Rn )-1 = ( R-1 )n = Rn 。 由 (1) 知， Rn 是对称的。,15,推论 (1) 若 R 是 U上的相似关系，则 Rn 也是 U上的相似关系。 (2) 设 RF ( UU) 是任一模糊关系，则 R R

7、T 是 U上的对称关系。 证明 因 (R RT)T = ( RT )T RT = R RT，由命题 (1) 知， R RT 是对称的。,16,定义 11 设 R F ( U U )， R 为传递的 0，1，u，v，w U， R (u, v) ，R(v, w) ，则 R (u, w) 。 命题 7 设 R，R1，R2 F ( U U )，则 (1) R 是传递的 R2 R。 (2) 若 R 是传递的 Rn 是传递的( n 1)。 (3) R1、R2 是传递的 R1 R2 是传递的。,17,证明 (1) 先证()：设 u，vU，tU，令 t = R(u, t) R(t, v) ， 则 R(u，t)

8、 t ，R(t，v) t 。由于 R 是传递的, 故R(u, v)t (tU)，于是,18,由 u，v 的任意性知 R2 R 再证()：若 R2 R 且 R(u，v) ，R(v，w) 于是 由定义 11 知 R 是传递的。,19,(2) 若 R 是传递的，则由 (1) 有 R2 R ，进一步由(7) 右边一式得 (R2)n Rn 又由 (Rn)2 = (R2)n ， 联合上面两式，得 (Rn)2 = (R2)n Rn， 最后由 (1) 知 Rn 是传递的。,20,(3) 我们可以用 两 式证明 ( Q R ) S ( Q S ) ( R S ) , S ( Q R ) ( S Q ) ( S

9、R )。 应用上面两式，得 (R1 R2 )2 = (R1 R2 ) (R1 R2 ) ( R1 (R1 R2) ) ( R2 (R1 R2) ) (R1 R1) (R1 R2) (R2 R1) (R2 R2),21, R12 R22 。 因为，R1、R2 是传递的，即 R12 R1、R22 R2，则有 (R1 R2 )2 R1 R2 ， 所以，R1 R2 是传递的。,22,模糊传递闭包和等价闭包 通常的模糊关系，不一定具有传递性，因而不是模糊等价关系。对这种模糊关系直接进行分类显然是不合理的。为此，我们希望寻求一种方法，能将不是等价的模糊关系进行改造，以便分类使用。,23,定义 13 设 R

10、F ( U U )，称 t(R) 为 R 的传递闭包，如果 t(R) 满足: (1) 传递性：(t(R)2 t(R) ； (2) 包容性：R t(R) ； (3) 最小性：若 R是 U 上的模糊传递关系，且 R R t(R) R， 即 R 的传递闭包是包含 R 的最小的传递关系。,24,定理 2 : 设 RF ( U U )，则 证明：(1) 首先证明 是传递的，即要证明,25,由传递性定义知， 是传递的。,26,(2) 显然有 (3) 若有 R 使 R R且 R是传递的，则由 R R 有 R2 (R)2 R, R3 = R R2 R R (R)2 R, 一般有 Rn R, 从而,27,即 含

11、于任一包含 R 的传递关系中。 综上所述， 是包含 R 的最小传递关系，因而是 R 的传递闭包，即,28,在论域为有限集的情况下，传递闭包的计算变得很简捷。 命题 8 设 | U| = n，RF ( U U ) ，则 证明略。,29,推论 设 | U | = n， RF ( U U ) ，且 R 是自反关系，则存在正整数 m ( n ) ，使 t(R) = Rm，且 l m 有 Rl = t(R) 。 证明 因为 | U| = n，所以 又因为 R 是自反的，由命题 (2) 知 R R2 R3 ,30,因而 在做上述合成运算时，若做到 m ( n ) 次时，出现了 Rm+1 = Rm，则有 R

12、m+2 = Rm，进而，t(R) = Rm。这时，若我们取正整数 l m，则有,31,即有 Rl = t(R) 。 上述推论说明，在计算有限论域上自反的模糊关系 R 的传递闭包时，可以从 R 开始，反复自乘，依次计算出 R， R2，R4， ，当第一次出现 RkRk = Rk 时，就有 t(R) = Rk 。,32,命题 9 模糊关系的传递闭包 t(R) 有以下性质： (1) 若 I R，则 I t(R) 。 (2) ( t(R) )T = t(R T ) 。 (3) 若 R T = R，则 ( t(R) )T = t(R) 。 证明 (1) 由定理 2 可得。 (2) 由定理 2 、命题 4

13、(3) 及推论 (1)，有,33,(3) 由 (2) 即得。 上述命题中的 (1) 说明自反关系的传递闭包还是自反的， (3) 表明对称关系的传递闭包还是对称的。,34,定义 14: 设 RF ( U U )，称 e(R) 为 R 的等价闭包，若 e(R) 满足下述条件： (1) 等价性：e(R) 是 X 上的模糊等价关系。 (2) 包容性：R e(R)。 (3) 最小性：若 R 是 X 上的模糊等价关系，且 R R e(R) R 。 显然，R 的等价闭包是包含 R 的最小的等价关系。,35,例 8 给定有限论域上的模糊关系 R 如下： 则 由于模糊矩阵 R2 的元素不超过 R 对应位置上的元

14、素,36,因而模糊关系 R2 R，故 R 是传递的。 命题: 设 R 是 U 上的一个自反的和传递的模糊关系，则有 R = R2 。 证明 因为 R 是自反的，则有，R R2。又因为 R 是传递的，则 有，R2 R，故有 R = R2 。,37,定义 12 设 RF ( U U )，若 R 满足下列三个条件，则称 R 是 U上的一个模糊等价关系： (1) 自反性： u U，R(u，u) =1 。 (2) 对称性： u，v U，R(u，v)= R(v，u)。 (3) 传递性： R2 R，即 u，w U U，有,38,若 U = u1, u2, , un 为有限论域时，U上的模糊等价关系 R 是一

15、个矩阵（称为模糊等价矩阵），它满足下述三个条件： (1) 自反性：rii=1, i =1, 2, , n。 (2) 对称性：rij= rji， i，j =1, 2, , n。 (3) 传递性： R R R，即,39,条件 (1) 说明模糊矩阵的对角线元素都是 1 ； 条件 (2) 意味着模糊等价矩阵是对称矩阵。,40,定理 3: 设 R F ( U U )，则 R 是模糊等价关系 0，1， R 是经典等价关系， 这里 R = (u, v) U U | R (u, v) 为 R 的 截关系。且对于 ， 0，1， ，有等价类 R u R u ( u U )。 证明略。,41,本定理说明，若 R 是

16、 U 上的模糊等价关系，则其 截关系是经典等价关系，它们都可将 U 作一个划分，当 从 1 下降到 0 时，就得到一个划分族，而且由于 时， R u R u ，即 R 给出的分类结果中的每类，是 R 给出的分类结果的子类，所以 R 给出的分类结果比 R 给出的分类结果更细。随着的下降， R 给出的分类越来越粗，这样就得到一个动态的聚类图，我们可以根据实际情况的需要，选择某个水平上的分类结果。这是模糊聚类分析的一大优越性,42,例 : 设 U= x1，x2，x3，x4，x5，R 是 U上的一个模糊关系，其对应的模糊矩阵为 在上面的矩阵中，对角线元素为 1，即 rii=1，所以 R 是自反的。又因

17、 R 与其转置矩阵相同，故,3.7 F动态聚类图,43,rij= rji，R = R-1，即 R 是对称的。由于 即 RR= R2 R，R是传递的，故R是模糊等价关系。,44,依次取 截关系 R ，R 是经典等价关系，它诱导出 U 上的一个划分 U/ R ，将 U 分成一些等价类。 当 =1 时， R1 诱导的分类为五类：x1, x2, x3, x4, x5。,45,当 = 0.8 时， R0.8 诱导的分类为四类：x1，x3, x2, x4, x5。,46,当 = 0.6 时， R0.6 诱导的分类为三类：x1, x3, x2, x4, x5。,47,当 = 0.5 时， R0.5 诱导的分

18、类为两类：x1, x3, x4, x5, x2。,48,最后，当 = 0.4 时， R0.4 将 X 分成一类：x1, x2, x3, x4, x5。,49,随 由大到小，分类由细到粗，形成一个动态的分类图，如图 所示： x1 x3 x4 x5 x2 =1 0.8 0.6 0.5 0.4 图 动态聚类图,50,教材 P75 用归并相似类法给出了同样的分类。 求模糊相似关系的等价类有以下三种方法： 等价闭包法 (e(R) 间接法 归并相似类法 最大树法,直接法,51,3.9 模糊聚类分析 模糊聚类分析在实际问题中有广泛的应用，这是由于实际问题中，一组事物是否属于某一类常带有模糊性，也就是问题的界

19、限不是十分清晰的。我们不能明确地回答 “是” 或 “否”， 而是只能作出 “在某种程度上“是” 或 “否” 的回答，这就是模糊聚类分析。 本节主要讨论基于模糊等价关系的动态聚类的实际应用。,52,1. 特征抽取 假设待分类对象的集合为 U= U1, U2, , Un ，集合中的每个元素具有 m 个特征，设第 i 个对象 Ui 的第 j ( j = 1, 2, , m ) 个特征为 xij，则 Ui 就可以用这 m 个特征的取值来描述，记 Ui = ( xi1, xi2, , xim) ( i =1，2，n ),53,为了计算简便，并使特征仅具有相对的意义，我们要首先对特征的观测值进行预先处理，

20、使各特征值的取值在单位区间 0, 1 中。 设 Ui 的观测值为 Xi 0， Ui0 = ( xi10，xi20，xim0 ) ( i=1, 2, n) 所以用下列各公式对 Ui 0 进行 “规格化” 的预处理。,54,(1) xij = cxij0 ( i =1, , n； j =1, , m) c 是一个常数，选择 c 使任何 xij 在 0, 1 中。 (2) xij = cxij0 / max(xij0) ( i =1, , n; j =1, , m) 即选择所有的特征中的最大值作分母。 (3) 当特征值中出现负值时，则用下式压缩到 0,1：,55,当特征值不是负值时，当然也可以用上式

21、来“规格化” 式中 是全部特征值的均值，分子是特征值与均值的距离。用此式 “规格化” 时应注意：只要与均值的距离相等，特征值的大小的方向性就被“湮灭”。,56,2. 建立 U上的模糊关系（模糊相似矩阵） 设待分类对象的全体是 U= U1, U2, , Un ，我们首先要鉴别 U中的元素 Ui 与 Uj 的接近程度（相似程度）。用 0, 1 中的数 rij 来表示 Ui 与 Uj 的相似程度，称为相似系数。相似系数组成一个矩阵 (rij)nn 称为相似系数矩阵，它是 U上的模糊相似关系。我们对此关系矩阵求其等价闭包或等价类，就能对 U 中的元素进行聚类。,57,为了确定相似系数，必须使相似系数符

22、合自反、对称的要求，可根据实际情况选用下列方法之一。 1）数量积法 其中,58,2）夹角余弦法 3）相关系数法 其中,59,4）指数相似系数法 其中 sk 与 m 为常数。 5）绝对值指数法,60,6）绝对值倒数法 其中 M 为适当选择的常数，M 的选择使 rij0, 1。,61,7) 非参数法 令 是 xik 与 xjk 的均值），nij+= xi1 xj1, xi2 xj2, , xim xjm 中正数个数，nij= xi1 xj1, xi2 xj2, , xim xjm 中负数个数，,62,8）贴近度法 贴近度表示两个模糊向量之间接近的程度，它符合自反、对称的要求，所以可以用来表示相似系

23、数。我们将 U中的元素 Ui，Uj 看成是各自特征的模糊向量，便可以用贴近度来表示相似系数 rij， rij = ( Ui, Uj ),63,(1) 当 取内外积贴近度时 或,64,(2) 最大最小法，当 取 上式时 (3) 算术平均最小法，当 取 前 式时,65,(4) 几何平均最小法，当 取 前式时 (5) 绝对值减数法，当 取距离贴近度时 rij = 1c (dp ( Xi，Xj ) 式中 c， 为常数，p 为各种距离的代码系数。,66,当 p =1 时，dp 就是海明距离，此时求相似系数的方法称绝对值减数法，其相似系数为 当 p = 2 时， dp 就是欧氏距离，此时有,67,9）经验

24、法 请有经验的人来分别对 Ui 与 Uj 的相似性打分，设有 s 个人参加评分，若第 k 个人 (1 k s) 认为 Ui 与 Uj 相似的程度为 aij(k) （在 0，1 中），他对自己评分的自信度也打分，若自信度分值是 bij(k) ，则可以用下式来计算相似系数:,68,在以上确定相似系数的诸多方法中，究竟选用哪一种合适，需要根据问题的具体性质来决定。,69,3、例举 环境单元分类 每个环境单元可以包括空气、水分、土壤、作物等四个要素。环境单元的污染状况由污染物在四要素中含量的超限度来描写。 假设有五个单元 x1, x2, x3, x4, x5，它们的污染数据如表 3.13 所示。,70

25、,取论域 U = x1, x2, x3, x4, x5，按 上式 “规格化”，取 c = 0.1，再按前式求相似系数（取 c = 1)，,表13 污染数据,71,得到模糊相似矩阵,72,聚类方法 可以有三种方法来对模糊相似矩阵聚类。 1）传递闭包法（平方法） 求出模糊相似矩阵的传递闭包 t (R) ，它就是 R 的等价闭包 e (R) = t (R) ，然后求其 截关系 e(R) 。 它是经典等价关系，让 从 1 降至 0，当 变化时，它们给出一个动态的分类结果。 求 R 的传递闭包 t(R) 时，可以用平方法，即求 R2, R4, , Rk，若有 Rk Rk = Rk，则 t(R) = Rk

26、。,73,经计算可知,74,当 = 1 时，分成五类：x1, x2 , x3, x4, x5 当 = 0.8 时，分成四类：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,75,其动态分类如下图 所示： =1 x1 x3 x4 x5 x2 0.8 0.6 0.5 0.4,图 动态聚类图,76,2）直接聚类法 根据模糊相似矩阵 来直接由相似类求等价类。 当 =1 时，该矩阵只有对角线上的元素为 1

27、，所以不许归并相似类，所得到的 e(R)1 的等价类为 x1，x2，x3，x4，x5。 当 = 0.8 时，先求经典矩阵 R0.8，有此求得它的相似类是,77,R0.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,

28、x2 , x4, x5。,78,当 =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 = 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 的等价类。,79,3）最大树法（ Kr

29、uskal） 在模糊相似矩阵 中，从 =1 开始逐步做连通图，直到 = 0 时为止，每作一条边，就在边上写出 rij 之值（连通强度）。注意不要做回路。从原则上来说，可以选择任一元素（顶点）作为起始点，但一般总是选有相似类的元素开始。例如在本例中当 = 0.8 时，就有相似类 x1, x3，于是就把 x1 选为起始顶点，先作出强度为,80,0.8 的边，然后再作强度为 0.6 的边及强度为 0.5 和 0.4 的边，这样就得到最大树，如下图 所示。,图 3 最大树,81,在不同 水平上的分类，就是在最大树中砍去那些强度小于 的边，再分类。例如 = 0.8 时，砍掉最大树右边的各枝，就得到分类： x1, x3, x2 , x4, x5；而在 = 0.6 时，只砍掉强度为 0.5 和 0.4 的边，于是得到的分类就是： x1, x3 , x2 , x4, x5 。,82,*经济区的模糊分类法 在经济学理论研究中，有一种观点认为经济结构相似的区域，应该生产或销售相近的产品，研究如何给出这些区域的划分问题就称为经济区的分类问