高级运筹学-第6章：模糊聚类分析.ppt

1 第六章模糊聚类分析 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上的一个普通等价关系 因为满足下列三个条件 自反性 任何人与自己是 年龄相同 的 对称性 我与你年龄相同 你与我年龄也相同 传递性 我与你年龄相同 你与他年龄相同 我与他年龄也相同 三 普通分类一个普通等价关系决定一个普通分类 2 一 建立X X1 X2 Xn 上的模糊关系矩阵R 叫标定 其中rij 0 1 表示元素Xi与Xj间的相似程度 i j 1 2 n 6 2模糊聚类 分类是有弹性的 亦此亦彼 方法 一 评定打分法 请专家或有经验的专业人员组成评定小组进行打分评定获得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上的模糊关系矩阵为 3 方法 二 统计指标法 一个模糊等价关系决定一个模糊分类 叫聚类 分类的集合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项统计指标值 将每个元素各项统计指标标准化 常用极值标准化公式 4 经过上步标准化后的Xi与Xj的各统计指标按下列方法中的任一种计算rij 1 欧氏距离法 2 数量积法 其中M是个适当选择的常数 3 夹角余弦法 5 4 相关系数法 5 指数相似系数法 其中sk是个适当的正常数 6 最大最小法 7 算术平均最小法 8 几何平均最小法 6 9 绝对值数法 10 绝对值倒数法 其中M是个适当的正常数 使得0 rij 1 11 绝对值减数法 其中C是个适当的正常数 使得0 rij 1 二 进行聚类分模糊等价关系 矩阵 与模糊相似关系 矩阵 二种情况进行 7 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 经过标定后得模糊关系矩阵为 易证R是X上的模糊等价矩阵 因此可从R出发对X中的元素进行模糊聚类 解 方法 一 直接分类 8 取0 85 0 9 得 按该水平 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 取0 9 1 得 可将X1 X2 X3 X4 X5各自成一类 共分成五类 X X1 X2 X3 X4 X5 9 取0 2 0 8 得 按该水平 r12 r21 r13 r31 r15 r51 r23 r32 r25 r52 r35 r53 1 可将X1 X2 X3 X5归为一类 其余元素各自成一类 共分成二类 X X1 X2 X3 X5 X4 取0 0 2 得 按该水平 可将X1 X2 X3 X4 X5归为一类 共分成一类 X X1 X2 X3 X4 X5 模糊聚类过程是一个动态过程 随水平由小到大 集合X的分类越来越细 10 方法 二 编网分类 取0 85 0 9 得 按该水平 可将X3 X5归为一类 其余元素各自成一类 共分成四类 X X1 X2 X3 X5 X4 取0 9 1 得 按该水平 可将X1 X2 X3 X4 X5各自成一类各自成一类 共分成五类 X X1 X2 X3 X4 X5 11 取0 8 0 85 得 按该水平 可将X2 X3 X5归为一类 其余元素各自成一类 共分成三类 X X1 X2 X3 X5 X4 取0 2 0 8 得 按该水平 可将X1 X2 X3 X5归为一类 其余元素各自成一类 共分成二类 X X1 X2 X3 X5 X4 12 取0 0 2 得 按该水平 可将X1 X2 X3 X4 X5归为一类 共分成一类 X X1 X2 X3 X4 X5 13 例6 3设论域X 销售额 购销费用 零售利润 X1 X2 X3 且X1 X2 X3相互影响的模糊矩阵为 易证R是X上的模糊等价矩阵 因此可从R出发对X中的元素进行模糊聚类 取0 6 1 得 可知X X1 X2 X3 在该水平上分类时 不十分注重商品销售额 购销费用 零售利润之间的相互影响关系 而是各自独立研究他们 取0 4 0 6 得 可知X X1 X3 X2 在该水平上分类时 比较注重商品销售额和零售利润之间的相互影响关系 而不大注重他们和购销费用间的关系 取0 0 4 得 可知X X1 X2 X3 在该水平上分类时 对三者的相互关系之间都比较注重 14 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上的模糊关系矩阵为 显然R具备自反性和对称性 15 因此R不具备传递性 即R只是模糊相似矩阵 不能直接利用R对X中的元素进行聚类 须对R进行改造 改造成模糊等价矩阵 再利用改造后的模糊等价矩阵 对X中的元素进行聚类 16 由定理知R16是模糊等价矩阵 利用R16对X中的元素进行聚类 用编网法 17 取0 8 0 9 得 X X1 X3 X2 X4 X5 取0 9 1