模糊模式识别法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,7,章,模糊模式识别法,1,7.1,模糊数学概述,7.2,模糊集合,7.3,模糊关系与模糊矩阵,7.4,模糊模式分类的直接方法,和间接方法,7.5,模糊聚类分析法,第,7,章 模糊模式识别法,2,7.1,模糊数学概述,1),精确数学方法,忽略对象的一般特性，着重注意对象的数量、空间形式,和几何形状的数学方法。,如：牛顿力学、牛顿和莱布尼茨创立的微积分学等。,7.1.1,模糊数学的产生背景,模糊数学诞生的标志：,1965,年美国加利福尼亚大学控制,论专家,L.A.Zadeh,（查德）发表的文章“,Fuzzy sets”,。,模糊数学（,Fuzzy sets,）又称模糊集合论。,1,精确数学方法及其局限性,3,(2),工程技术方面：用,精确的实验方法,和,精确的测量计算,，,探索客观世界的规律，建立严密的理论体系。,(1),理论研究方面：用,精确定义,的概念和,严格证明,的定理，,描述现实事物的数量关系和空间形式。,2),近代科学的特点,3),精确数学方法的局限性,现实世界中的许多现象，用精确数学方法难以解决。,例如：著名的问题之一,秃头悖论,用精确数学方法判断“秃头”：,方法：首先给出一个精确的,定义,，然后,推理,，最后,结论,。,定义：头发根数,n,时，判决为秃头；否则判决为不秃。,即头发根数,n,为判断秃与不秃的界限标准。,问题：当头发根数恰好为,n,+1,，应判决为秃还是不秃？,4,推理：两种选择,(2),承认生活常识：认为仅一根头发之差不会改变秃与不秃的,结果，即有,n,+1,根头发者也应是秃头。,(1),承认精确方法：判定为不秃。,结论：有,n,根头发的是秃头，有,n,+1,根头发的不是秃头。,头发为,n,根者为秃头，,头发为,n,+1,根者为秃头，,头发为,n,+2,根者为秃头，,头发为,n,+,k,根者为秃头。,那么采用传统的逻辑推理，会得到下面的一些命题：,其中，,k,是一个有限整数，显然,k,完全可以取得很大。,结论：头发很多者为秃头。,类似地：没有头发者不是秃头,均表现出精确方法在这个,问题上与常理对立的情况,显然不合理,5,模糊数学：有关描述和处理模糊性问题的理论和方法的学科。,模糊数学的基本概念：,模糊性,。,2,模糊数学的诞生,1965,年查德（,zadeh,）发表了“模糊集合”论文后，在科学界引,起了爆炸性的反映，他准确地阐述了模糊性的含义，制定了刻画,模糊性的数学方法（隶属度、隶属函数、模糊集合等），为模糊,数学作为一门独立的学科建立了必要的基础。,7.1.2,模糊性,人们在认识事物时，总是根据一定的标准对事物进行分类，,有些事物可以依据某种精确的标准对它们进行界线明确的认识，,有些事物根本,无法找出精确的分类标准,，例如“秃头悖论”中的,头发根数的界线,n,，实际是不存在的。,1,模糊性的基本概念,6,1),清晰性：事物具有的明确的类属特性,(,或是或非,),。,2),模糊性：事物具有的不明确类属特性,(,只能区别程度、等级,),。,3),模糊性的本质：是事物类属的不确定性和对象资格程度的渐,变性。,类属,实例,界限分明,行星、整数、鸡蛋,模糊,高山、优秀、胖子,例：,2,与模糊性容易混淆的几个概念,1),模糊性与近似性,共同点：描述上的不精确性。,区别：不精确性的根源和表现形式不同。,7,a),近似性：问题本身有精确解，描述它时的不精确性源于认,识条件的局限性和认识过程发展的不充分性。,例：薄雾中观远山。,2),模糊性与随机性,共同点：不确定性。,a),模糊性：表现在质的不确定性。是由于概念外延的模糊性,而呈现出的不确定性。,区别：不确定性的性质不同。,b),模糊性：问题本身无精确解，描述的不精确性来源于对象,自身固有的性态上的不确定性。,例：观察一片秋叶。,8,c),排中律：即事件的发生和不发生必居且仅居其一，不存在,第三种现象。随机性遵守排中律，模糊性不遵守，它存在,着多种，甚至无数种中间现象。,3,、模糊性与含混性,共同点：不确定性。,区别：,b),随机性：是外在的不确定性。是由于条件不充分，导致,条件与事件之间不能出现确定的因果关系，而事物本身,的性态和类属是确定的。,例：降雨量：大雨、中雨或小雨，典型的模糊性。,投掷硬币：随机性。,9,a),含混性：由信息不充分（二义性）引起，一个含混的命题,即是模糊的，又是二义的。一个命题是否带有含混性与其应,用对象或上下文有关。,b),模糊性：是质的不确定性。,总之，模糊性：由本质决定。,其 它：由外界条件带来的不确定性引起。,例：命题“张三很高”：对给张三购买什么型号的衣服这个应用对象是含混的。,也是一个模糊性命题。,10,模式识别从模糊数学诞生开始就是模糊技术应用研究,的一个活跃领域，研究内容涉及：计算机图像识别、手书,文字自动识别、癌细胞识别、白血球的识别与分类、疾病,预报、各类信息的分类等。,7.1.3,模糊数学在模式识别领域的应用,研究方法针对一些模糊识别问题设计相应的模糊模式识别系统。,*用模糊数学对传统模式识别中的一些方法进行改进。,11,1,）论域,讨论集合前给出的所研究对象的范围。选取一般不唯一，,根据具体研究的需要而定。,7.2,模糊集合,1.,经典集合论中几个概念,2,）子集,对于任意两个集合,A,、,B,，若,A,的每一个元素都是,B,的元素，,则称,A,是,B,的“子集”，记为；若,B,中存在不属于,A,的元素，则称,A,是,B,的“真子集”，记为。,7.2.1,模糊集合定义,传统经典集合论中的集合称为：,经典集合、普通集合、确定集合、脆集合。,12,3,）幂集,对于一个集合,A,，由其所有子集作为元素构成的集合称,为,A,的“幂集”。,例：论域,X,=1,2,，其幂集为,2,模糊集合的定义,给定论域,X,上的一个模糊子集 ，是指：对于任意,x,X,，,都确定了一个数 ，称 为,x,对 的隶属度，且,。,映射 ：,叫做 的隶属函数，或从属函数。模糊子集常称为模糊集合,或模糊集。,13,说明：,14,15,3,相关的几个概念,正规模糊集：模糊集合的核是非空的；,非正规模糊集：模糊集合的核是空的。,即：是隶属度为,1,的元素组成的经典集合。,16,17,4,模糊集合的表示,有多种表示方法：要求表现出论域中所有元素与其对应的隶属,度之间的关系。,查德的求和表示法和积分表示法：,1,）求和表示法：,适用于离散域论域。,2,）积分表示法：,适合于任何种类的论域，,特别是连续论域。,18,常用的模糊集合表示方法：,注：当某一元素的隶属函数为,0,时，这一项可以不计入。,19,X,是一个连续的实数区间，模糊集合表示为,20,21,7.2.2,隶属函数的确定,隶属函数是模糊集合赖以存在的基石。正确地确定隶属函,数是利用模糊集合恰当地定量表示模糊概念的基础。,常用的形式：,型函数：中间高两边低的函数。,S,型函数：从,0,到,1,单调增长。,隶属函数的确定：,构造一个概念的隶属函数时，结果不唯一。,目前很难找到统一的途径。,几种隶属函数的构造与确定方法：,1,简单正规模糊集合隶属函数的构成,22,隶属函数的构成：,1,）假定：,方法：,并确定 ，有,23,2.,模糊统计法,：利用模糊统计的方法确定隶属函数。,模糊统计试验四要素：,1,）论域,X,，例如人的集合；,2,）,X,中的一个元素,x,0,，例如王平；,3,）,X,中的一个边界可变的普通集合,A,，例如“高个子”；,4,）条件,s,，制约着,A,边界的改变。,方法：,每次试验下，对,x,0,是否属于,A,做出一个确定的判断，有,随着,n,的增大，隶属频率呈现稳定性，所在的稳定值叫隶属度。,24,从两种事物的对比中，做出对某一概念符合程度的判断。,是区别事物的一种重要方法。,1,）择优比较法,例,7.4,求茶花、月季、牡丹、梅花、荷花对“好看的花”的隶,属度。,方法：,10,名试验者逐次对两种花作对比，优胜花得,1,分，失败,者,0,分。,往往不满足数学上对“序”的要求，不具有传递性，出现循环现象。,3.,二元对比排序法,缺点：,25,表,7.2,五种花对“好看的花”的隶属度,名 称,总 得 分,隶 属 度,茶 花,23,0.23,月 季,18,0.18,牡 丹,20,0.20,梅 花,15,0.15,荷 花,24,0.24,失败,优胜,茶花,月季,牡丹,梅花,荷花,得分,茶花,1,0,1,0,2,月季,0,0,1,0,1,牡丹,1,1,1,0,3,梅花,0,0,0,0,0,荷花,1,1,1,1,4,表,7.1,一位测试者的二元对比结果,26,2,）优先关系定序法,27,x,3,为第一优越元素。除去,x,3,得新的优先关系矩阵。,有 ，,x,1,为第二优越元素，排序完毕。,按,x,3,，,x,1,，,x,2,顺序赋予相应的隶属度。,3,）相对比较法,4,）对比平均法,28,根据不同的数学物理知识，设计隶属度函数，然后在实践,中检验调整。,4.,推理法,一般以成功的实例进行借鉴。,例,7.6,笔划类型的隶属函数的确定,根据笔划与水平线的交角确定隶属函数。,29,例,7.7,手写体字符,U,和,V,的区别。,解：用包含的面积与三角形面积作比较。,30,例,7.8,封闭曲线的圆度。,表征圆度的隶属函数：,5.,专家评分法,难免引入个人的主观成份，但对某些难以用上述几种方法,实现的应用来说，仍不失为一种办法。,31,7.2.3,模糊集合的运算,1.,基本运算,两个模糊子集间的运算：,在此过程中，,论域保持不变,。,逐点对隶属函数作相应的运算,，得到新的隶属函数。,32,33,34,35,2.,运算的基本性质,36,37,38,7.2.4,模糊集合与普通集合的相互转化,截集是联系普通集合与模糊集合的桥梁，它们使模糊集合,论中的问题转化为普通集合论的问题来解。,截 集,模糊集合,普通集合,39,根据医生的经验，可将各温度段用“发烧”的隶属度表示如下：,T39.0,隶属度,=1.0,38.5 T39.0,隶属度,0.9,38.0 T38.5,隶属度,=0.7,37.0 T38.0,隶属度,=0.4,T37.0,隶属度,=0.0,40,41,2.,截集的三个性质,42,43,7.3,模糊关系与模糊矩阵,普通关系：二值的，,存在,或者,不存在,关系，,两者必居且仅居其一。,模糊关系：需要用描述关系程度的量补充描述，,关系程度通过隶属度表示。,7.3.1,模糊关系定义,1,基本概念,设,X,、,Y,是两个论域，,笛卡尔积：,又称直积。,由两个集合间元素无约束地搭配成的序偶（,x,，,y,）的全体构成的集合。,44,给无约束搭配施以某种约束,体现了一种特殊关系,接受约束的元素对便构成笛卡尔集中的一个,子集,子集表现了一种关系,如果：,普通集合论：,X,到,Y,的一个关系，定义为,X,Y,的一个子集,R,，记作,模糊关系的定义类似。,序偶中两个元素的排列是有序的：,45,2,模糊关系定义,46,47,48,7.3.2,模糊关系的表示,如：例,7.11,中的模糊,关系对应的模糊矩阵,1,用模糊矩阵表示,49,2,用有向图表示,有向图表示：,50,7.3.3,模糊关系的建立,计算,第一步：正规化。,极值标准化公式：,51,计算,r,ij,的常用方法：,1,）欧式距离法,2,）数量积法,M,：正数，满足,52,3,）相关系数法,其中，,4,）最大最小法,5,）主观评定法,以百分制打分，然后除以,100,得,0,，,1,区间的一个数。,53,7.3.4,模糊关系和模糊矩阵的运算,1,并、交、补运算,1,）模糊关系的并、交、补运算,54,模糊关系并、交、补运算分别与模糊矩阵并、交、补运算对应。,模糊关系和模糊矩阵的运算实际上就是隶属度的运算。,2,）模糊矩阵的并、交、补运算,55,求：,a),关系“,x,比,y,高或比,y,胖”；,b),关系“与,y,相比，,x,又高又胖”；,c),关系“,x,没,y,高”。,56,57,解：,58,2,模糊关系的倒置与模糊矩阵的转置,59,对应的模糊矩阵,对应的模糊矩阵,例,7.15,模糊关系,=“,x,比,y,高”,=“,y,比,x,低”,60,3,截矩阵与截关系,61,4.,模糊关系合成与模糊矩阵合成,幂运算：模糊关系与自身的运算，即：,1,）模糊关系合成,62,2,）模糊矩阵合成,对比,对有限论域：,模糊矩阵乘积运算,普通矩阵乘法运算,加法,求大,乘法,求小,类似,63,，求,Q,对,R,的合成矩阵。,64,7.3.5,模糊关系的三大性质,例：关系“等于”,关系“了解”,具有自反性，,不具有自反性。,1,自反性,2.,对称性,65,3.,传递性,b),S,只有对称性，无自反性。,66,说明：,67,例：“个子高”,“,认 识”,具有传递性，,不具有传递性。,R,是一个传递模糊矩阵。,？,解：,例,7.19,判断 是否是传递模糊矩阵。,68,4.,模糊等价关系和模糊相似关系,定义：,69,7.4,模糊模式分类的直接方法和间接方法,7.4.1,直接方法,隶属原则,直接计算样品的隶属度，根据,隶属度最大,原则进行分类。,用于单个模式的识别,隶属原则：,70,隶属原则是显然的，易于公认的，但其分类效果如果，,十分依赖于建立已知模式类隶属函数的技巧。,71,现有,45,岁、,30,岁、,65,岁、,21,岁各一人，问应分别属于哪一类？,中：,青：,72,73,中年,老年,青年,年龄（岁）,1,0.5,0,45,100,20,70,属于老年人。,74,例,7.21,染色体识别或白血球分类问题。这类问题最终归结为识别三角形。即判断一个三角形属于“等腰三角形,(,I,),、直角三角形,(,R,),、等腰直角三角形,(,IR,),、正三角形,(,E,),、其他三角形,(,T,)”,中的哪一种。,75,76,7.4.2,间接方法,择近原则,适合于模糊集,求模糊集合之间接近程度的问题。,77,1,模糊集合间的距离,聚类分析中,两向量间的明氏距离,78,两种常用的绝对距离公式：,其他：相对距离、加权距离,街坊距离,欧氏距离,79,2.,贴近度,说明两个相同的模糊集的贴近度最大,要求贴近度映射具有对称性,描述了两个较“接近”的模糊集合的贴近度也较大,模糊集合贴近度的具体形式不唯一。,80,两种常用贴近度：,81,2,）格贴近度,内积、外积分别定义为,82,83,84,3.,择近原则,85,86,87,7.5,模糊聚类分析法,7.5.1,基于模式糊等价关系的聚类分析法,只有模糊等价关系才能用模糊等价矩阵进行截矩阵分类。,称为：截矩阵分类法,*,对于模糊等价关系：,可以用模糊等价矩阵的截矩阵直接进行模式分类。,*,对模糊相似关系：,必须由相应的模糊相似矩阵生成模糊等价矩阵，然后对,生成的等价矩阵利用截矩阵的办法分类。,包括：,1,模糊等价关系的截矩阵分类法,88,89,要求按不同,水平分类。,90,91,92,动态聚类图：,93,2,模糊相似关系的截矩阵分类法,必须用模糊相似矩阵生成一个模糊等价矩阵。,直接用模糊相似关系进行分类出现的问题：,例：设有五种矿石，按其颜色、比重等性质得出描述其“相似,程度”的模糊关系矩阵如下：,94,（,1,）判断是什么矩阵：,矩阵,R,的自反性、对称性是明显的，计算传递性：,产生矛盾。,95,给定一个模糊相似矩阵就可以得到一个模糊等价矩阵。,96,7.5.2,模糊相似关系直接用于分类,对于模糊相似关系，需要改造成为模糊等价关系，才能,利用截矩阵的方法进行正确分类。但多次矩阵相乘，计算麻,烦。为此寻找由模糊相似矩阵直接进行聚类的方法，如最大树法。,最大树法：,97,例,7.25,设二个家庭，每家,3-5,人，选每个人的一张照片，共,8,张，混放在一起，将照片两两对照，得出描述其“相似程度”,的模糊关系矩阵。要求按相似程度聚类，希望把二个家庭分开。,98,解：,(1),按模糊相似矩阵，画出被分类的元素集，构造“最大树”。,当全部连通时，检查一下全部元素是否都已出现，即保证所有元素都,是连通的。最大树即构造好。,0.2,0.4,0.4,0.2,0.2,0.5,0.5,0.8,0.8,0.8,0.8,4,6,2,8,7,5,3,1,回路不画,99,0.2,0.4,0.4,0.2,0.2,0.5,0.5,0.8,0.8,0.8,0.8,4,6,2,8,7,5,3,1,回路不画,0.2,0.2,0.5,0.8,0.8,0.8,0.8,4,6,2,8,7,5,3,1,100,0.2,0.2,05,0.8,0.8,0.8,0.8,4,6,2,8,7,5,3,1,101,0.2,0.2,0.5,0.8,0.8,0.8,0.8,4,6,2,8,7,5,3,1,注意：最大树不唯一，但取截集后，所得子树相同。,102,任选,K,个聚类中心；,按最近邻规则聚类；,根据聚类结果计算新的聚类中心，,比较新旧聚类中心是否相等；,新旧中心相等，结束；否则回到。,模糊,K-,均值算法基本思想：,首先设定一些类及每个样本对各类的隶属度；,然后通过迭代，不断调整隶属度至收敛。,K-,均值算法回顾：,7.5.3,模糊,K-,均值算法,由,聚类分析,中,动态聚类法,中的,K-,均值算法,派生出来。,103,(1),确定模式类数,K,，,1,K,N,，,N,为样本个数。,步骤：,104,加权平均,例如，,3,个样本时：,！,105,例当有两个聚类中心时，样本,j,对两个类别隶属度的计算：,类似于相对距离,106,例：,107,由,U,(0),可知，倾向于,X,1,、,X,2,、,X,3,为一类，,X,4,为一类。,108,109,得,如对,X,3,有：,110,类似地，可得到,U,(1),中其它元素，有,111,7.5.4,模糊,ISODATA,算法,ISODATA,算法：源于,K-,均值算法。,模糊,ISODATA,算法：将模糊方法引入,ISODATA,算法。,算法步骤：,例如：将全体样本均值作为第一个聚类中心，在所有,n,个特征,方向上加、减一个均方差。,共,(2,n,+1),个聚类中心,(1),选择初始聚类中心。,ISODATA,算法特点：具有类别调整功能。,合并、分解等操作使聚类过程中类别数可变。,ISODATA,算法的核心：类别调整。,112,(3),类别调整：合并、分解、删除。,(4),最佳类数或最佳结果的讨论。,判定结果好坏的直接依据：隶属度矩阵,U,。,由于计算机存储量的限制，选取了三个评价分类优劣的判据：,最大稳定度,最小相关度,最大聚类度,(2),若已选择了,K,个初始聚类中心，用模糊,K,-,均值算法进行聚类。,由于现在得到的是各聚类中心，所以直接计算下一步的隶,属度矩阵,U,(1),，,继续,K,-,均值算法直到收敛，最终得到隶属度矩阵,U,和,K,个聚类中心。,113,结束,114,