模糊关系的传递闭包
• 定义9.2.1 设RF(XX). 若R1F(XX)是传递的 且满足：1) RR1,
• 2) 若S是X上的模糊传递关系且RS, 必有R1S.
• 则称R1为R的传递闭包, 记为t(R). • 根据上述定义, 模糊关系R的传递闭包是包含R 的最小传递关系。 • 定理9.2.2 设RF(XX). 则 t(R)=∪n=1 R . • 证明：容易验证A, BiF(XX), • A∪i=1 Bi=∪i=1 (ABi),
基于模糊关系的聚类分析
• 数据规格化的方法有： • (1) 标准化方法: 对特性指标矩阵X*的第j列, 计 算均值和方差, 然后作变换
xij
xij x j σj
,
i 1, 2,, n; j 1, 2, , m.
1 n 其中 x j xij , n i 1 1 n σ 2 ( xij x j )2 , j 1, 2, , m j n i 1
模糊聚类分析(一)
1 聚类分析的基本概念
• “聚类”就是按照一定的要求和规律对事物进行 区分和分类的过程, 在这一过程中没有任何关于 分类的先验知识, 仅靠事物间的相似性作为类属 划分的准则, 属于无监督分类的范畴。 • “聚类分析”是指用数学的方法研究和处理给 定对象的分类。 • “人以群分, 物以类聚”, 聚类是一个古老的问 题,它伴随着人类社会的产生和发展而不断深化, 人类要认识世界就必须区别不同的事物并认识 事物间的相似性。
聚类分析的基本概念
• 聚类分析是多元统计分析的一种, 它把一个没有 类别标记的样本集按某种准则划分成若干个子 集(类), 使相似的样本尽可能归为一类, 而不相 似的样本尽量划分到不同的类中。
• 传统的聚类分析是一种硬划分, 它把每个待辨识 的对象严格地划分到某类中, 具有非此即彼的性 质, 因此这种类别划分的界限是分明的。而实际 上大多数对象并没有严格的属性, 它们在性态和 类属方面存在着中介性, 具有亦此亦彼的性质, 因此适合进行软划分。
相似关系)。依次计算R2, R4, R8知: R8=R4 R4=R4 (参见下页计算结果), 所以R的传递闭包 t(R)=R4.
1 0.1 R 0.8 0.5 0.3 1 0.4 4 R 0.8 0.5 0.5
0.1 0.8 0.5 0.3 1 0.1 0.2 0.4 0.1 1 0.3 0.1 0.2 0.3 1 0.6 0.4 0.1 0.6 1 0.4 0.8 0.5 0.5 1 0.4 0.4 0.4 0.4 1 0.5 0.3 0.4 0.5 1 0.6 0.4 0.3 0.6 1
模糊关系的传递闭包
1 0.1 0.8 0.5 0.1 1 0.1 0.2 R 0.8 0.1 1 0.3 0.5 0.2 0.3 1 0.3 0.4 0.1 0.6
•解
0.3 0.4 0.1 0.6 1
容易看出R是自反的对称模糊关系 (即模糊
9.3 基于模糊关系的聚类分析
• (2) 夹角余弦法
rij
xi x j xi x j
m 2 xi xik , i 1, 2,, n k 1
xi x jk x j ( x jk x j ) 2
k 1 m
1 2
• (3) 相关系数法
rij
9.3 基于模糊关系的聚类分析
• 对于相似程度(相似系数)的确定, 有多种方法, 常用的有： i j 1 • (1) 数量积法
rij 1 M xi x j i j
xi x j xik x jk
k 1
m
• 其中M>0为适当选择的参数且满足Mmax{xixj | i j}. 这里, xixj为xi与xj的数量积.
• (4) 最大值规格化方法: 对特性指标矩阵X*的第j 列, 计算最大值 Mj=max{x1j, x2j, , xnj} , j=1, 2, , m. 然后作变换 xij =xij /Mj, i=1, 2, , n, j=1, 2, , m.
9.3 基于模糊关系的聚类分析
• 步骤二：构造模糊相似矩阵 • 聚类是按某种标准来鉴别X中元素间的接近程 度, 把彼此接近的对象归为一类。为此, 用[0, 1] 中的数rij 表示X中的元素xi 与xj 的接近或相似程 度。经典聚类分析中的相似系数以及模糊集之 间的贴近度, 都可作为相似程度(相似系数)。 • 设数据xij(i=1, 2, , n, j=1, 2, , m)均已规格化, xi=(xi1, xi2, , xim)与xj=(xj1, xj2, , xjm)之间的 相似程度记为rij[0, 1], 于是得到对象之间的模 糊相似矩阵R=(rij)n×n.
基于模糊关系的聚类分析
x11 x21 X* x n1 x12 x22 xn 2 x1m x2 m xnm
• 步骤一：数据规格化 • 由于m个特性指标的量纲和数量级不一定相同, 故在运算过程中可能突出某数量级特别大的特 性指标对分类的作用, 而降低甚至排除了某些数 量级很小的特性指标的作用。数据规格化使每 一个指标值统一于某种共同的数值特性范围。
0.5 0.7 0.1 0.1 0.1 0 0.2 0.8
模糊关系的传递闭包
• 设RF(XX). 称R是传递的, 如果对任意[0, 1] 及任意 x, y , zX 成立: • R(x, y), R(y, z) R(x, z). • 若R是X上的自反、对称、传递的模糊关系, 则 称R是X上的模糊等价关系。 • 设RF(XX). 则 • (1) R是自反的 IR , 这里I是恒等关系, 即当 x=y时I(x, y)=1, 当xy时I(x, y)=0. • (2) R是对称的 R=R1.
聚类分析的基本概念
• 常用的模糊聚类分析方法大致可分为两大类：
其一是基于模糊关系(矩阵)的聚类分析方法, 而
作为其中核心步骤的模糊分类,有下述的主要方 法：模糊传递闭包法、直接聚类法、最大树法 和编网法; 其二是基于目标函数的聚类分析方法, 称 为 模 糊 C 均 值 (FCM) 聚 类 算 法 ( 或 称 为 模 糊
• 若R是X上的自反、对称的模糊关系, 则称R是X 上的模糊相似关系。
模糊关系
• 某家庭子女和父母外貌相像关系为R, 父母和祖 父母、外祖父母相像关系为S, 它们分别用以下 模糊矩阵确定, 计算其ma祖母 外祖父 外祖母
0.8 0.2 0.1 0.7
• (3) R是传递的 R2R.
模糊关系的传递闭包
• 设RF(XX). 则R是模糊等价关系当且仅当对 任意[0, 1], R是等价关系。 • 论域X上的经典等价关系可以导出X的一个分类。 论域X上的一个模糊等价关系R对应一族经典等 价关系{R: [0, 1]}. 这说明模糊等价关系给出 X的一个分类的系列。这样, 在实际应用问题中 可以选择“某个水平”上的分类结果, 这就是模 糊聚类分析的理论基础。 • 实际问题中建立的模糊关系常常不是等价关系 而是相似关系, 这就需要将模糊相似关系改造为 模糊等价关系, 传递闭包正是这样一种工具。
x
k 1 m k 1
m
ik
1 m xi xik m k 1 1 m x j x jk m k 1
( xik xi ) 2
9.3 基于模糊关系的聚类分析
• (4) 贴近度法 • 当对象xi的特性指标向量xi=(xi1, xi2, , xim)为模 糊向量, 即xik[0, 1] (i=1,2, ,n ; k=1,2, ,m) 时, xi与xj的相似程度rij可看作模糊子集xi与xj的 贴近度。在应用中, 常见的确定方法有：最大最 小法、算术平均最小法、几何平均最小法。
基于模糊关系的聚类分析
• (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.
n (∪i=1 Bi)A=∪i=1 (Bi A). n
• 据此可以证明∪n=1 R 是传递的：
模糊关系的传递闭包
• 计算有限论域上自反模糊关系R的传递闭包的 方法：从R出发, 反复自乘, 依次计算出R2, R4, …, k k k k 当第一次出现R R =R 时得t(R)=R .
1 0.3 R 2 0.8 0.5 0.5 1 0.4 R8 0.8 0.5 0.5
0.3 0.8 0.5 0.5 1 0.2 0.4 0.4 0.2 1 0.5 0.3 0.4 0.5 1 0.6 0.4 0.3 0.6 1 0.4 0.8 0.5 0.5 1 0.4 0.4 0.4 0.4 1 0.5 0.3 0.4 0.5 1 0.6 0.4 0.3 0.6 1
基于模糊关系的聚类分析
• 基于模糊关系的聚类分析的一般步骤: (1) 数据 规格化; (2) 构造模糊相似矩阵; (3) 模糊分类。 • 上述第三步又有不同的算法, 以下先介绍利用模 糊传递闭包进行模糊分类的方法。 • 设被分类对象的集合为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的特性指标矩阵。