PPT《*》

* * 第4章 模糊关系与聚类分析 * * 本章内容 4.

1 模糊关系4.2 模糊等价关系4.3 聚类分析 * * 模糊关系的三个性质 自反性对称性传递性 * * 自反性 若模糊关系R满足R(u,u)=1或I?R,则称R具有自反性模糊自反矩阵rii = 1例如: * * 自反矩阵的定理 定理. 设模糊矩阵 A ∈Mn*n是自反矩阵,则有I ? A?A2 ? A3 ?…? An-1 ?An?…证明: * * 对称性 若模糊关系R满足R(u,v)=R(v,u),则称R具有对称性模糊对称矩阵rij = rji例如: * * 传递性 若模糊关系R满足RоR?R,则称R具有传递性模糊传递矩阵 * * 模糊传递矩阵――例**模糊传递矩阵的定理 定理. 设模糊矩阵 Q ∈Mn*n是传递矩阵,则有Q ?Q2 ? Q3 ?… ?Qn-1 ?Qn ?…证明: * * 模糊等价关系 定义. 模糊关系R∈F(U*U) , 满足(1)自反性:R (u,u)=1;

(2)对称性:R(u,v)=R(v,u);

(3)传递性:R2 ?R则称R为模糊等价关系 * * 模糊等价矩阵 若论域U是有限论域,则U上的模糊等价关系R可表示为模糊等价矩阵模糊等价矩阵自反性 rii = 1对称性 rij = rji传递性 * * R是否为模糊等价矩阵? * * 等价布尔关系 一个布尔矩阵具有如下特性,则称其为等价的布尔矩阵,对应一个普通的等价关系自反性对称性传递性 * * 模糊等价矩阵的性质 若R为模糊等价矩阵,则R= R2 = R3 = … = Rn-1 = Rn 证明:自反性: R?R2 ?…? Rn-1 ?Rn传递性: R?R2?…?Rn-1?Rn * * 模糊等价矩阵的定理1 定理1. R是模糊等价矩阵?对于任何λ∈[0,1],Rλ是等价布尔矩阵.证明:对称性、自反性显然传递性 * * 定理1的意义 模糊等价矩阵?普通等价矩阵普通等价矩阵?普通等价关系普通等价关系可以分类当λ在[0,1]上变动时,得到不同的Rλ, 从而得到不同的分类 * * 模糊等价矩阵分类――例设X={x1, x2, x3 ,x4, x5 }求当λ =1, 0.8, 0.6, 0.5, 0.4时的聚类结果. * * λ =1 利用λ =1时的截关系,将X分成5个等价类:{x1}, {x2}, {x3}, {x4}, {x5} * * λ =0.8 利用λ =0.8时的截关系,将X分成4个等价类:{x1, x3}, {x2}, {x4}, {x5} * * λ =0.6 利用λ =0.6时的截关系,将X分成3个等价类:{x1, x3}, {x2}, {x4, x5} * * λ =0.5 利用λ =0.5时的截关系,将X分成2个等价类:{x1, x3, x4, x5}, {x2} * * λ =0.4 利用λ =0.4时的截关系,将X分成1个等价类:{x1, x2, x3, x4, x5} * * 动态聚类图 λ由1变到0,Rλ的分类由细到粗 x1 x2 x3 x4 x5 λ =1 λ =0.8 λ =0.4 λ =0.6 λ =0.5 * * 模糊等价矩阵的定理2 定理2. R ∈ μn*n是模糊等价矩阵,则对于任何λ,μ ∈[0,1],且λ I ? R?R2 ?… ?Rnt(R)=Rn ?Rm ? ∪k=1∞ Rk=t(R) 传递闭包的定理4 * * 模糊相似矩阵?模糊等价矩阵 将相似矩阵改造成等价矩阵只需求相似矩阵的传递闭包 * * 定理5. 设R∈μn*n 是模糊相似矩阵,则存在一个最小自然数k (k≤n),使得传递闭包t(R)=Rk,对于任何自然数b≥k,都有Rb=Rk,此时,t(R)是模糊等价矩阵. 传递闭包的定理5 * * 平方法求传递闭包 从模糊相似矩阵R出发,依次求平方:当第一次出现Rk ?Rk =Rk时, Rk就是所求的传递闭包t(R) * * 时间复杂度 * * 课堂作业 * * 课堂作业4-1 设请问至多几次平方可以到达传递闭包?请给出传递闭包t(R) * * 课堂作业4-2 证明:若Q,R是传递的,则Q∩R也是传递的. * * 本章内容 4.1 模糊关系4.2 模糊等价关系4.3 聚类分析 * * 4-3 聚类分析 * * 聚类分析是把对象自动划分成多个类簇,使得同类簇内对象相近、异类簇间对象相异;

聚类分析对于发现数据的隐含模式、获取知识、预测数据的功能或行为等,具有十分重要的意义. 移动通信网客户聚类 图像像素点聚类 蛋白质聚类 聚类分析 * * 聚类分析与模式分类的区别: 模式分类是已知若干模式,要求我们正确判断当前的新样本属于哪个模式;

聚类分析所讨论的对象是一大批样本,事先没有给定任何模式供参考,要求我们按样本各自的属性值加以分类.从机器学习的角度来看,分类是有监督学习,聚类是无监督学习. * * 聚类分析方法 简单说,聚类分析就是用数学方法对事物进行分类.通过适当聚类,事物便于研究,事物的内部规律容易为人类所掌握.现有方法主要有:(1)层次聚类算法:通过数据的分裂或聚合,以形成层次类簇.适用于小规模数据集.(2)划分式聚类:事先指定类簇数或类簇中心,通过反复迭代,逐步降低目标函数的值.当目标函数收敛时,得到最终类簇.(3)基于密度和网格的聚类:通过密度或网格发现类簇.适用于大规模数据集. * * 模糊聚类分析 模糊数学产生之前,聚类分析是数理统计多元分析的一个分支.现实分类问题往往具有模糊性,例如 环境污染分类 、 临床症状资料分类 、 岩石分类 等等,因此,用模糊数学语言进行模糊聚类分析更为自然. * * 基于模糊等价矩阵的聚类分析方法 * * 基于模糊等价矩阵的聚类分析步骤 第一步:建立模糊矩阵 ;

第二步:建立模糊等价矩阵;

第三步:聚类(求动态聚类图) * * 第一步:建立模糊矩阵 设U ={u1, u2, …, un }为待分类的全体对象,其中每个待分类对象由一组数据表征如下:问题转化为:如何建立对象ui与uj之间的相似关系 * * 例1――环境污染 例如,要对一些环境单元进行聚类,判断它们的污染程度每个环境单元包括四个要素:空气、水分、土壤、作物环境单元的污染状况由污染物在四个要素中含量的超限度来描述 * * 现有5个污染单元,U=它们的污染数据如下:Ⅰ=(5,5,3,2),Ⅱ=(2,3,4,5),Ⅲ=(5,5,2,3),Ⅳ=(1,5,3,1),Ⅴ=(2,4,5,1) * * 建立模糊矩阵 如何建立对象ui与uj之间的相似关系?有许多方法,应用时根据实际情况,选择一种方法来求ui与uj的相似关系R(ui, uj)=rij在 环境污染 的例子中,如何给出模糊相似矩阵? * * 建立模糊相似矩阵 建立模糊相似矩阵的注意事项:rij∈[0,1]自反对称 环境 例中,采用 绝对值减数法 问:得到的相似矩阵的维数是多少? * * 模糊相似矩阵 * * 步骤2:相似关系?等价关系 步骤1得到的矩阵一般满足自反性和对称性将模糊相似矩阵改造成模糊等价矩阵平方法求传递闭包 * * 至多计算多少次? 模糊相似矩阵5*5k=[log25]+1=2+1=3最坏情况下,R?R2?R4?R8,计算到R8 * * * * 模糊等价矩阵 * * 步骤3:聚类 R的传递闭包t(R)=R4对于t(R),依次取截关系 * * λ =1 利用λ =1时的截关系,将X分成5个等价类:{x1}, {x2}, {x3}, {x4}, {x5} * * λ =0.8 利用λ =0.8时的截关系,将X分成4个等价类:{x1, x3}, {x2}, {x4}, {x5} * * λ =0.6 利用λ =0.6时的截关系,将X分成3个等价类:{x1, x3}, {x2}, {x4, x5} * * λ =0.5 利用λ =0.5时的截关系,将X分成2个等价类:{x1, x3, x4, x5}, {x2} * * λ =0.4 利用λ =0.4时的截关系,将X分成1个等价类:{x1, x2, x3, x4, x5} * * 动态聚类图 λ由1变到0,Rλ的分类由细到粗 x1 x2 x3 x4 x5 λ =1 λ =0.8 λ =0.4 λ =0.6 λ =0.5 * * 讨论 * * 讨论1:建立相似矩阵的其他方法 非常多!主要分为3类相似系数法距离法(绝对值减数法就是距离法之一)主观法在后面给出 * * 讨论2:直接基于相似矩阵聚类?? 建立模糊相似矩阵R后,求其传递闭包t(R)计算量较大.若直接从R出发,进行聚类,会怎么样? * * 取λ=1(最大值),对每个xi,确定其相似类[xi]1将满足rij =1的xi和xj放在一类,构成相似类{x1}, {x2}, {x3}, {x4}, {x5} * * 取λ=0.8(次大值),对每个xi,确定其相似类[xi]R {x1, x3}, {x2}, {x4}, {x5} * * 依次取λ=0.

6、0.4等,确定其相似类. {x1, x3}, {x2}, {x4, x5} {x1, x3 ,x4 }, {x2 , x5}, {x1, x3 },{x1, x4 ,x5},{x2 , x4, x5} * * 相似矩阵直接聚类vs.等价矩阵聚类 对于一个固定的λ,等价矩阵聚类得到的等价类没有公共元素!相似矩阵聚类得到的相似类则有公共元素,这是因为不具有 传递性 * * 讨论3:如何选取λ?? 在实际应用中,需要选择适当的λ,从而给出一个较明确的分类.1)由具有丰富经验的领域专家结合领域知识确定λ,从而得到λ水平上的等价分类.2)用统计学中的F检验方法,刷掉不合格的类,使分类变得较清晰. * * 最佳阈值确定――F统计量 F统计量:分子表示类间平均距离,分母表示类内样本间的距离,F值越大,表示类与类间的差异越大,分类越好. * * 讨论1:模糊相似矩阵的建立 * *

1、数据预处理――数据标准化 设论域U ={x1, x2, …, xn }为待聚类对象,每个对象由m个指标表示其性状:将原始数据矩阵中的元素通过适当的变换压缩到[0,1]上. * * 程序3:玉米螟 1:7~8月平均气温2:上年12~2月平均气温3: 4月份温湿系数4: 4月份雨日数5: 4月份日照数6: 4月份平均风速7: 5月上旬温湿系数8: 5月田间调查的玉米螟卵数 * * 数据标准化 数据标准化常用的两种变换:平移-极差变换平移-标准差变换 * * 数据标准化 平移-极差变换(变换至0-1区间): 请计算:Ⅰ=(5,5,3,2),Ⅱ=(2,3,4,5),Ⅲ=(5,5,2,3),Ⅳ=(1,5,3,1),Ⅴ=(2,4,5,1) * * 数据标准化 平移-标准差变换(消除量纲): * *

2、模糊相似矩阵的建立 相似系数法 距离法其它方法:主观评分法 * * 1)相似系数法 (1) 数量积法|rij|∈[0,1],若为负,要将其压缩到[0,1],压缩方法:平移-极差变换或r'

ij=(rij+1)/2 * * 1)相似系数法 (2)夹角余弦法:(3)相关系数法: * 1)相似系数法 (4)指数相似系数法: * * 1)相似系数法 (5)最大最小法:(6)算数平均最小法:(7)几何平均最小法: 上述三种方法要求xij>

0,否则也要作适当变换. * * 2)距离法 (1)绝对值倒数法:(2)绝对值指数法: * * 2)距离法 (3)直接距离法:rij=1-c*d(xi,xj)海明距离:欧式距离:切比雪夫距离: * * 3)主观评分法 专家直接给出相似度,专家数为N,rij(k)表示第k个专家给出的i与j的相似度,aij(k)为专家的自信度. * * 程序演示 * * 程序1:环境 第4章数据文件编辑E.exe 打开 环境.dat 第4章模糊聚类E.exe * * 程序1:环境 程序1:环境 * * * * 程序2:家族 论域U = {x1, x2, x3, x4, x5}表示来自2个家族的5个人,已经利用某种方法建立了相似矩阵:第4章数据文件编辑E.exe 打开 家族.dat 用模糊聚类分析确定他们的家族关系.第4章模糊聚类E.exe * * 程序2:家族 * * 程序3:玉米螟 第4章数据文件编辑E.exe 打开 玉米螟.dat 用模糊聚类分析确定各年份间关系,以应用于害虫预报.第4章模糊聚类E.exe * * 程序3:玉米螟 * * 程序3:玉米螟 * * 程序4:土壤 第4章数据文件编辑E.exe 打开 土壤.dat 21个土壤样本,每个样本9个量化指标:含氮百分比、含磷百分比、有机质、PH值、耕层厚度、持水量等.第4章模糊聚类E.exe 分析结果为进一步做土壤分类提供参考. * * 程序4:土壤 * * 课后作业 * *

1、著名聚类的例子 日本学者Tamura给出,在模糊数学中广泛使用有三个家庭,共16人.每个家庭人数为4-7人.每人提供一张照片,共计16张由若干素不相识的中学生对照片两两进行比较,按相貌相似程度进行评分,分数在[0,1]上.每对照片的相似程度由所有人对他们的评分的平均值确定.要求:把三个家庭区分开来(即对这16个人进行聚类),可使用直接聚类法 * * 得到相似矩阵 * * 作业2 要建立下面四个对象的相似矩阵,请给出合理的建立公式,并用传递闭包法进行模糊聚类. ........