第6章：模糊聚类分析(高级运筹学-中南大学 徐选

第六章 模糊聚类分析6.1 普通分类(分类是硬性的，非此即彼)对集合 X 的一个划分，是指把 X 分成若干个子集 X1,X2,…,Xn,使得满足下列二个条件： ① X1∪X2∪…∪Xn = X,且对 i≠j , ② Xi∩Xj = ,( i,j=1,2,…,n )

一、集合的划分

二、普通等价关系设 R∈ ( X×X ),称 R 是 X 上一个等价关系，若 R 满足下列三个条件： ① 自反性： x∈X,有( x,x )∈R ; ② 对称性： x,y∈X,若( x,y )∈R,有( y,x )∈R ; ③ 传递性： x,y∈X,若( x,y )∈R,( y,z )∈R,有( x,z )∈R 。 例6-1 对集合(论域) X = {人} ,则关系 R = “年龄相同” 就是 X 上的一个普通等价关系， 因为满足下列三个条件： ① 自反性：任何人与自己是“年龄相同”的 ； ② 对称性：我与你年龄相同，你与我年龄也相同； ③ 传递性：我与你年龄相同，你与他年龄相同，我与他年龄也相同。

三、普通分类一个普通等价关系决定一个普通分类。

6.2

模糊聚类(分类是有弹性的，亦此亦彼) r11 r R ( rij ) 21 rn1 r12 r21 rn 2 r1n r2 n rnn

一、建立 X = { X1,X2,…,Xn } 上的模糊关系矩阵 R (叫标定)

其中 rij [0,1] ,表示元素 Xi 与 Xj 间的相似程度，i,j=,1,2,…,n, 方法(一).评定打分法： 请专家或有经验的专业人员组成评定小组进行打分评定获得 rij 。 例：组成一个100人的评比小组，对X={X1,X2,X3}上的3个元素的相似性进行评价。结果是： 认为X1与X1“相似”的有100人,占100%,r11=1;认为X1与X2“相似”的有81人,占81%=1,r12=0.81; 认为X1与X3“相似”的有53人,占53%,r13=0.53;认为X2与X3“相似”的有24人,占24%,r23=0.24; 此时r22=1,r33=1,r21=0.81,r31=0.53,r32=0.24。从而X上的模糊关系矩阵为：

1 0.81 0.53 R ( rij ) 0 . 81 1 0 . 24 0.53 0.24 1 2

方法(二).统计指标法： 一个模糊等价关系决定一个模糊分类 --- 叫聚类。 分类的集合 X = { X1,X2,…,Xn },由 n 个元素组成， 对其中每一个元素 ，采用不同的 m 个统计指标： 对元素 X1 ,采用统计指标 x1 = ( x11,x12,…,x1m ) ; 对元素 X2 ,采用统计指标 x2 = ( x21,x22,…,x2m ) ; ………………………………………………… 对元素 Xn ,采用统计指标 xn = ( xn1,xn2,…,xnm ) ; ( xij为第 i 个元素 Xi 的笫 j 项统计指标值 ) 将每个元素各项统计指标标准化：常用极值标准化公式

x ' ij

x ij x i , Min

x i , Max x i , Min x1 j x1, Min ' x1 j , x1, Max x1, Min x 2 j x 2, Min ' x2 j , x 2, Max x 2, Min

[0,1]

=

0, x ij x i , Min时 1, x ij x i , Max 时

, 仍记为 x ij .

x ' nj

x nj x n, Min

x n, Max x n, Min

,

经过上步标准

化后的 Xi 与 Xj 的各统计指标按下列方法中的任一种计算 rij 。1. 欧氏距离法：

rij 1 M,

1 m ( x ik x jk ) 2 m k 1i j其中 M 是个适当选择的常数，

2. 数量积法：

rij

1 m x ik x jk , i j m k 1

且M Max{ x ik x jk }0 i , j m k 1

m

3. 夹角余弦法：

rij

xk 1 m 2 k 1

m

ik

x jkm

( x ik ) ( x jk ) 2k 1

4. 相关系数法：

rij

[( xk 1

m

ik

x i ) ( x jk x j )]2 m

(xk 1

m

ik

x i ) ( x jk x j )k 12 3 ( x ik x jk ) 2 4 sk

, 其中2

1 m xi x ik m k 1 1 m x j x jk m k 1

5. 指数相似系数法：

1 rij mm k 1 m

ek 1ik

m

,

其中 sk 是个适当的正常数

6. 最大最小法：

rij

Min{ xk 1

, x jk } , x jk }8.几何平均最小法：

Max{ x

ik

7.算术平均最小法：

rij

Min{ xk 1

m

ik

, x jk }

1 m ( x ik x jk ) 2 k 1

rij

Min{ xk 1

m

ik

, x jk }

1 m ( x ik x jk ) 2 k 15

9.绝对值数法：

rij e1,m

| xik x jk |k 1

m

i j

10.绝对值倒数法： rij

M

| xk 1

ik

x jk |

, i ji j

其中 M 是个适当的正常数，使得 0≤rij≤1

1,11.绝对值减数法： rij

1 C | x ik x jk |,k 1

m

i j

其中 C 是个适当的正常数，使得 0≤rij≤1

二、进行聚类分模糊等价关系(矩阵)与模糊相似关系(矩阵)二种情况进行。

6.3

模糊等价关系(矩阵)与聚类分析因为: 模糊矩阵 R 是模糊等价矩阵 对 ∈[0,1],R 的 截矩阵 R 均是 普通等价矩阵。 所以: 可通过 R 对 X 上的元素进行聚类。

一、原理

二、定理若水平 1, 2 满足 0≤ 1≤ 2≤1,则按 2 分出的每一类必是按 1 分出的一类的子类。

例6-2 设论域 X = { X1,X2,X3 ,X4,X5 },经过标定后得模糊关系矩阵为

0 .8 0. 8 1 0. 8 1 0.85 R 0.8 0.85 1 0. 2 0 . 2 0 .2 0.8 0.85 0.9

0 .8 0.2 0.85 0 . 2 0 .9 1 0 .2 0 .2 1 0 .2

易证 R 是 X 上的模糊等价矩阵，因此可从 R 出发对 X 中的元素进行模糊聚类。 解：方法(一):直接分类

① 取 0.9 < ≤ 1,得：

1 0 R 0 0 0

0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

可将 X1,X2,X3 ,X4,X5 各自成一类， 共分成五类： X = { X1 }∪{ X2 }∪{ X3 }∪{ X4 }∪{ X5 }

② 取 0.85 < ≤ 0.9,得：

1 0 R 0 0 0 1 0 R 0 0 0

0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 1

按该水平，r35=r53=1, 可将 X3,X5 归为一类，其余元素各

自成一类， 共分成四类： X = { X1 }∪{ X2 }∪{ X3 ,X5 }∪{ X4 }

③ 取 0.8 < ≤ 0.85 ,得： 按该水平， r23= r32= r25= r52= r35=r53=1, 可将 X2,X3,X5 归为一类，其余元素各自成一类， 共分成三类： X = { X1 }∪{ X2 ,X3,X5 }∪{ X4 }8

④ 取 0.2 < 1 1 1 1 R 1 1 0 0 1 1⑤ 取 0 ≤ 1 1 R 1 1 1

≤ 0.8 ,得： 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1

按该水平， r12= r21= r13= r31= r15= r51= r23= r32= r25= r52= r35=r53=1, 可将 X1,X2,X3,X5 归为一类，其余元素各自成一类， 共分成二类： X = { X1,X2 ,X3,X5 }∪{ X4 }

≤ 0.2 ,得： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

按该水平， 可将 X1,X2,X3 ,X4,X5 归为一类，共分成一类： X = { X1,X2,X3 ,X4,X5 }

模糊聚类过程是一个动态过程，随水平由小到大，集合 X 的分类越来越细。

方法(二):编网分类 ① 取 0.9 < ≤ 1 ,得： 1 0 0 0 0 , 1

1 0 0 0 1 0 0 1 0

R0.9

X1 X

X2 X3 X4

X5

按该水平，可将 X1,X2,X3 ,X4,X5 各自成一类各自成一类，共分成五类： X = { X1 }∪{ X2 }∪{ X3 }∪{ X4 }∪{ X5 } ② 取 0.85 < ≤ 0.9 ,得：

R0.9

1 0 0 0 0

1 0 0 0

, 1 0 1 1 0 1

X1 X

X2 X3 * X4

X5

按该水平，可将 X3,X5 归为一类，其余元素各自成一类，共分成四类： X = { X1 }∪{ X2 }∪{ X3 ,X5 }∪{ X4 }10

③ 取 0.8 < 1 0 1 R0.85 0 1 0 0 0 1

≤ 0.85 ,得： X1 , X 1 0 1 1 0 1

X2 * * X3 * X4

X5

按该水平，可将 X2,X3,X5 归为一类，其余元素各自成一类，共分成三类： X = { X1 }∪{ X2 ,X3,X5 }∪{ X4 }④ 取 0.2 < 1 1 1 R0.8 1 1 0 0 1 1 ≤ 0.8 ,得： X1 * , 1 X * 0 1 1 0 1 *

X2 * * X3 * X4

X5

按该水平，可将 X1,X2,X3,X5 归为一类，其余元素各自成一类，共分成二类： X = { X1,X2 ,X3,X5 }∪{ X4 }

⑤ 取 0 ≤ ≤ 0.2 ,得：

R 0 .2

1 1 1 1 1

1 1 1 1

, 1 1 1 1 1 1

X1 * X * * *

X2 * * * X3 * * X4 *

X5

按该水平，可将 X1,X2,X3 ,X4,X5 归为一类，共分成一类： X = { X1,X2,X3 ,X4,X5 }

例6-3 设论域 X = { 销售额,购销费用,零售利润 } ={ 且 X1,X2,X3 相互影响的模糊矩阵为

X1,X2,X3 },

1 0.4 0.6 R

0 . 4 1 0 . 4 0.6 0.4 1 易证 R 是 X 上的模糊等价矩阵，因此可从 R 出发对 X 中的元素进行模糊聚类。① 取 0.6 < ≤ 1 ,得：

1 0 0 , R 0 1 0 0 0 1

可知 X = { X1 }∪{ X2 }∪{ X3 } 在该水平上分类时，不十分注重商品销售额、购销费用、 零售利润之间的相互影响关系，而是各自独立研究他们。

② 取 0.4 < ≤ 0.6 ,得：

1 0 1 , R 0 1 0 1 0 1 ③ 取 0 ≤ ≤ 0.4 ,得：

可知 X = { X1, X3 }∪{ X2 } 在该水平上分类时，比较注重商品销售额和零售利润之 间的相互影响关系，而不大注重他们和购销费用间的关系。

1 1 1 , R 1 1 1 1 1 1

可知 X = { X1, X2, X3 } 在该水平上分类时，对三者的相互关系之间都比较注重。13

6.4

模糊相似关系(矩阵)与聚类分析经标定得的模糊关系(矩阵) R 不是模糊等价关系(矩阵), 它只具备自反性和对称性，不具备传递性，即 R 只是模糊相似关系(矩阵)。 要利用 R 对 X 中的元素进行聚类，须将 R 改造成模糊等价关系(矩阵)。

一、原理

二、定理设 R 是模糊相似矩阵，进行如下复合运算： R R2 = R R R4 = R2 R2 …… R2k = Rk Rk …… 若存在正整数 k,使得： R2k = Rk,则 R2k 是模糊等价矩阵， 这样: 可通过 R2k 对 X 上的元素进行聚类。 例6-4 对以下五种物质进行模糊聚类， 设论域 X = { 白色乒乓球 X1,面包 X2,黄色排球 X3 ,白犁 X4,黄橙 X5 }, 用评定打分法标定 X 上的模糊关系矩阵为：

1 0 . 1 0 .9 0 . 5 0 .1 1 0 .2 0 .7 R 0 . 9 0 .2 1 0 .1 0 . 5 0 .7 0 .1 1 0 . 3 0 .8 0 .6 0 .7

0 .3 0 .8 0 .6 0 .7 1 14

显然 R 具备自反性和对称性，

1 0.1 2 R R R 0.9 0.5 0.3 1 0.5 0.9 0.5 0.6

0.1 1 0.2 0.7 0.8

0. 9 0. 2 1 0.1 0. 6

0.5 0. 7 0.1 1 0. 7

0.3 1 0. 1 0.8 0.6 0.9 0.7 0.5 1 0.3 1 0 .1 0. 9 0. 5 0. 3

0.1 1 0. 2 0. 7 0. 8

0.9 0.2 1 0. 1 0.6

0. 5 0.7 0.1 1 0.7

0.3 0.8 0.6 0.7 1

0.1 0.9 0.5 0.6 1 0.3 0.7 0.8 0.3 1 0.5 0.6 0.7 0.6 1 0.7 0.8 0.5 0.7 1

0 . 1 0 .9 0 . 5 0 .3 1 0 .2 0 .7 0 .8 0 .2 1 0 . 1 0 .6 R 0 .7 0 .1 1 0 .7 0 .8 0 .6 0 .7 1

因此 R 不具备传递性，即 R 只是模糊相似矩阵，不能直接利用 R 对 X 中的元素进行聚类， 须对 R 进行改造，改造成模糊等价矩阵，再利用改造后的模糊等价矩阵，对 X 中的元素进行 聚类：

1 0.5 4 2 2 R R R 0.9 0.5 0.6

0 .5 1 0 .3 0

.7 0 .8

0 .9 0 .3 1 0 .6 0 .6

0.5 0 .7 0.6 1 0 .7

0 .6 0 .8 0 .6 0 .7 1

1 0 .5 0 .9 0 .5 0 .6

0.1 0.9 0.5 0.6 1 0.3 0.7 0.8 0.3 1 0.5 0.6 R 2 0.7 0.6 1 0.7 0.8 0.5 0.7 1 15

1 0.6 8 4 4 R R R 0.9 0.6 0.6 1 0.6 8 8 R R 0.9 0.6 0.6

0. 6 1 0. 6 0. 7 0. 8 0.6 1 0.6 0.7 0.8

0.9 0.6 1 0.6 0.6 0.9 0.6 1 0.6 0.6

0.6 0.7 0.6 1 0.7 0.6 0.7 0.6 1 0.7

0. 6 0. 8 0. 6 0. 7 1

1 0 .5 0 .9 0 .5 0 .6

0.5 1 0.3 0 .7 0.8 0.6 1 0.6 0 .7 0.8

0.9 0.3 1 0.6 0.6 0.9 0.6 1 0.6 0.6

0.5 0.7 0.6 1 0.7 0.6 0.7 0.6 1 0.7

0. 6 0. 8 0. 6 R 4 0. 7 1 0. 6 0. 8 0. 6 R 8 0. 7 1

R 16

0.6 1 0 .6 0.8 0.6 0.9 0.7 0 .6 1 0 .6

由定理知 R16 是模糊等价矩阵，利用 R16 对 X 中的元素进行聚类，用编网法：

① 取 0.9 < ≤ 1 ,得：

1 0 R 0 0 0

1 0 0 0

, 1 0 1 0 0 1

X1 X

X2 X3 X4

X5

X = { X1 }∪{ X2 }∪{ X3 }∪{ X4 }∪{ X5 } ② 取 0.8 < ≤ 0.9 ,得：

1 0 R 1 0 0

1 0 0 0

, 1 0 1 0 0 1

X1 X *

X2 X3 X4

X5

X = { X1, X3 }∪{ X2 }∪{ X4 }∪{ X5 }

② 取 0.7 < ≤ 0.8 ,得： 1 0 R 1 0 0 1 0 0 1 , 1 X1 X * X2 * X3 X4 X5

1 0 0

1 0

X = { X1 ,X3 }∪{ X2,X5 }∪{ X4 } ③ 取 0.6 < ≤ 0.7 ,得： 1 0 R 1 0 0 1 0 1 1 , 1

1 0 0

1 1

X1 X *

X2 * * X3 X4 *

X5

X = { X1 ,X3 }∪{ X2,X4 ,X5 } ④ 取 0 ≤ ≤ 0.6 ,得： 1 1 R 1 1 1 1 1 1 1 , 1

1 1 1

1 1

X1 * X * * *

X2 * * * X3 * * X4 *

X5 18

X = { X1 ,X2,X3,X4 ,X5 }

习 题 六一、标定 X = ( X1,X2,X3,X4,X5 )上的模糊相似矩阵为

1 0. 2 R 0. 8 0. 6 0. 4试对其进行模糊聚类？

0 .2 1 0 .3 0 .7 0 .9

0 .8 0 .3 1 0 .2 0 .5

0. 6 0 .7 0. 2 1 0 .7

0 .4 0 .9 0 .5 0 .7 1