0.5 0.4 0.5 1 0.6
0.5 0.4 0.3 0.6 1
7.3 基于模糊关系的聚类分析
• 基于模糊关系的聚类分析的一般步骤: (1) 数据 规格化; (2) 构造模糊相似矩阵; (3) 模糊分类。
• 上述第三步又有不同的算法, 以下先介绍利用模 糊传递闭包进行模糊分类的方法。
• 传统的聚类分析是一种硬划分, 它把每个待辨识 的对象严格地划分到某类中, 具有非此即彼的性 质, 因此这种类别划分的界限是分明的。而实际 上大多数对象并没有严格的属性, 它们在性态和 类属方面存在着中介性, 具有亦此亦彼的性质, 因此适合进行软划分。
• 模糊集理论的提出为软划分提供了有力的分析 工具, 用模糊数学的方法来处理聚类问题, 被称 之为模糊聚类分析。由于模糊聚类得到了样本 属于各个类别的不确定性程度, 表达了样本类属 的中介性, 更能客观地反映现实世界, 从而成为 聚类分析研究的主流。
• 定理 设RF(XX). 则R的传递闭包t(R)具有以下 性质:
• (1) 若IR, 则 I t(R);
• (2) (t(R))1=t(R1); • (3) 若R=R1, 则(t(R))1=t(R). • 上述结论表明：自反关系的传递闭包是自反的,
对称关系的传递闭包是对称的。于是, 模糊相似 关系的传递闭包是模糊等价关系。
k 1
xi

1 m
m k 1
xik
x j

1 m
m k 1
x jk
• (4) 贴近度法
• 当对象xi的特性指标向量xi=(xi1, xi2, , xim)为模 糊向量, 即xik[0, 1] (i=1,2, ,n ; k=1,2, ,m) 时, xi与xj的相似程度rij可看作模糊子集xi与xj的 贴近度。在应用中, 常见的确定方法有：最大最
• 例 设|X|=5, R是X上的模糊关系, R可表示为如下 的5×5模糊矩阵。求R的传递闭包。
1 0.1 0.8 0.5 0.3 0.1 1 0.1 0.2 0.4 R 0.8 0.1 1 0.3 0.1 0.5 0.2 0.3 1 0.6 0.3 0.4 0.1 0.6 1
i1

x
j )2,
j 1, 2,L , m
• (2) 均值规格化方法: 对特性指标矩阵X*的第j列,
计算标准差j, 然后作变换 xij = xij /j, i=1, 2, ,
n, j=1, 2, , m.
• (3) 中心规格化方法: 对特性指标矩阵X*的第j列, 计算平均值xj, 然后作变换 xij =xij xj, i=1, 2, , n, j=1, 2, , m.
X的一个分类的系列。这样, 在实际应用问题中 可以选择“某个水平”上的分类结果, 这就是模 糊聚类分析的理论基础。
• 实际问题中建立的模糊关系常常不是等价关系 而是相似关系, 这就需要将模糊相似关系改造为 模糊等价关系, 传递闭包正是这样一种工具。
• 定义 设RF(XX). 若R1F(XX)是传递的且满足： 1) RR1, 2) 若S是X上的模糊传递关系且RS, 必有R1S. 则称R1为R的传递闭包, 记为t(R). 模糊关系R的传递闭包是包含R的最小传递关系。
• 第一类方法, 作为准备先讲解模糊关系传递闭包 的基本概念。
7.2 模糊关系的传递闭包
• 设RF(XX). 则R是模糊等价关系当且仅当对
任意[0, 1], R是等价关系。
• 论域X上的经典等价关系可以导出X的一个分类。 论域X上的一个模糊等价关系R对应一族经典等
价关系{R: [0, 1]}. 这说明模糊等价关系给出
而是R的传递闭包, 即t(R)=∪n=1Rn. • 在论域有限的情况下, 传递闭包的计算更简捷: • 定理 设|X|=n, RF(XX). 则 t(R)=∪k=1nRk.
• 计算有限论域上自反模糊关系R的传递闭包的 方法：从R出发, 反复自乘, 依次计算出R2, R4, …, 当第一次出现Rk Rk=Rk时得t(R)=Rk.
• 设被分类对象的集合为X={x1, x2, , xn}, 每一 个对象xi有m个特性指标 (反映对象特征的主要 指标), 即xi可由如下m维特性指标向量来表示:
• xi=(xi1, xi1, , xim), i=1, 2, , n • 其中xij表示第i个对象的第j个特性指标。则n个
对 象 的 所 有 特 性 指 标 构 成 一 个 矩 阵 , 记 作 X*= (xij)n×m, 称X*为X的特性指标矩阵。
第七讲 模糊聚类分析
7.1 聚类分析的基本概念
• “聚类”就是按照一定的要求和规律对事物进行 区分和分类的过程, 在这一过程中没有任何关于 分类的先验知识, 仅靠事物间的相似性作为类属 划分的准则, 属于无监督分类的范畴。
• “聚类分析”是指用数学的方法研究和处理给 定对象的分类。
• 聚类分析是多元统计分析的一种, 它把一个没有 类别标记的样本集按某种准则划分成若干个子 集(类), 使相似的样本尽可能归为一类, 而不相 似的样本尽量划分到不同的类中。
x11 x12 L
X
*


x21
x22
L
M M
xn1 xn2 L
x1m
x2m

M
xnm
• 步骤一：数据规格化
• 由于m个特性指标的量纲和数量级不一定相同,故
在运算过程中可能突出某数量级特别大的特性指
标对分类的作用, 而降低甚至排除了某些数量级很
小的特性指标的作用。数据规格化使每一个指标
小法、算术平均最小法、几何平均最小法。
m
xik xjk
m
xik xjk
m
xik xjk
rij

k 1 m
k 1
xik x jk
;
rij

k 1
1m
2 k1
xik xjk
; rij

k 1 m
k 1
. xik x jk
m
xik xjk
p p
( p 1,Minkowski)
k1

• (6) 绝对值倒数法
1
i j
• 如右所示, 其中c是 适当选取的正数, 使 rij[0, 1].
rij


m
c

k 1
xik
x jk
i j
• (7) 主观评定法
• 在一些实际问题中,被分类对象的特性指标是定 性指标, 即特性指标难以用定量数值来表达。这 时, 可请专家和有实际经验的人员用评分的办法 来主观评定被分类对象间的相似程度。
• 步骤三：模糊分类
• 由于由上述各种方法构造出的对象与对象之间 的模糊关系矩阵R=(rij)n×n, 一般说来只是一个 模糊相似矩阵, 而不一定具有传递性。因此, 要 从R出发构造一个新的模糊等价矩阵, 然后以此 模糊等价矩阵作为基础, 进行动态聚类。
∪n=1Rn是包含R的模糊传递关系。
• 若有X上的模糊传递关系S满足RS, 下证
∪n=1Rn S
(即证明∪n=1Rn “最小”)
由RS得 R2S2S, R3= R R2 R S S2S, …
一般地, RnS, nN. 于是∪n=1Rn S. • 综上所述,∪n=1Rn是包含R的最小传递关系, 因
• 模糊聚类已经在诸多领域获得了广泛的应用, 如 模式识别、图像处理、信道均衡、矢量量化编 码、神经网络的训练、参数估计、医学诊断、 天气预报、食品分类、水质分析等。
• 常用的模糊聚类分析方法大致可分为两大类： 其一是基于模糊关系(矩阵)的聚类分析方法, 而 作为其中核心步骤的模糊分类,有下述的主要方 法：模糊传递闭包法、直接聚类法、最大树法 和编网法; 其二是基于目标函数的聚类分析方法, 称 为 模 糊 C 均 值 (FCM) 聚 类 算 法 ( 或 称 为 模 糊 ISODATA聚类分析法)。
• (5) 距离法
• 利用对象xi与xj的距离也可以确定它们的相似程 度rij, 这是因为d(xi, xj)越大, rij就越小。一般地,
取rij = 1 c (d(xi, xj)), 其中c和是两个适当选取
的正数, 使rij[0, 1]. 在实际应用中, 常采用如下 的距离来确定rij.
0.4 1 0.4 0.4 0.4 R4 0.8 0.4 1 0.5 0.3
0.5 0.4 0.5 1 0.6
0.5 0.4 0.3 0.6 1
1 0.4 0.8 0.5 0.5
0.4 1 0.4 0.4 0.4 R8 0.8 0.4 1 0.5 0.3
• (4) 最大值规格化方法: 对特性指标矩阵X*的第j 列, 计算最大值 Mj=max{x1j, x2j, , xnj} , j=1, 2, , m. 然后作变换 xij =xij /Mj, i=1, 2, , n, j=1, 2, , m.
• 步骤二：构造模糊相似矩阵
• 聚类是按某种标准来鉴别X中元素间的接近程 度, 把彼此接近的对象归为一类。为此, 用[0, 1] 中的数rij表示X中的元素xi与xj的接近或相似程 度。经典聚类分析中的相似系数以及模糊集之
值统一于某种共同的数值特性范围。
• 数据规格化的方法有： • (1) 标准化方法: 对特性指标矩阵X*的第j列, 计
算均值和方差, 然后作变换
xij

xij x j σj
,
i 1, 2,L , n; j 1, 2,L , m.
其中
xj

1 n
n
xij ,
i1
σ
2 j

1 n
n
( xij
• 解 容易看出R是自反的对称模糊关系 (即模糊相