模糊聚类分析(一)

模糊聚类分析模糊聚类分析((一一))11111111聚类分析的基本概念聚类分析的基本概念••““““““““聚类聚类””””””””就是按照一定的要求和规律对事物进行就是按照一定的要求和规律对事物进行区分和分类的过程区分和分类的过程,,,,,,,,在这一过程中没有任何关于在这一过程中没有任何关于分类的先验知识分类的先验知识,,,,,,,,仅靠事物间的相似性作为类属仅靠事物间的相似性作为类属划分的准则划分的准则,,,,,,,,属于无监督分类的范畴。属于无监督分类的范畴。••““““““““聚类分析聚类分析””””””””是指用数学的方法研究和处理给定是指用数学的方法研究和处理给定对象的分类。对象的分类。••““““““““人以群分人以群分,,,,,,,,物以类聚物以类聚””””””””,,,,,,,,聚类是一个古老的问题聚类是一个古老的问题,,,,,,,,它伴随着人类社会的产生和发展而不断深化它伴随着人类社会的产生和发展而不断深化,,,,,,,,人人类要认识世界就必须区别不同的事物并认识事类要认识世界就必须区别不同的事物并认识事物间的相似性。物间的相似性。聚类分析的基本概念聚类分析的基本概念••聚类分析是多元统计分析的一种聚类分析是多元统计分析的一种,,,,,,,,它把一个没有它把一个没有类别标记的样本集按某种准则划分成若干个子类别标记的样本集按某种准则划分成若干个子集集((((((((类类),),),),),),),),使相似的样本尽可能归为一类使相似的样本尽可能归为一类,,,,,,,,而不相似而不相似的样本尽量划分到不同的类中。的样本尽量划分到不同的类中。••传统的聚类分析是一种传统的聚类分析是一种硬划分硬划分,,,,,,,,它把每个待辨识它把每个待辨识的对象严格地划分到某类中的对象严格地划分到某类中,,,,,,,,具有非此即彼的性具有非此即彼的性质质,,,,,,,,因此这种类别划分的界限是分明的。而实际因此这种类别划分的界限是分明的。而实际上大多数对象并没有严格的属性上大多数对象并没有严格的属性,,,,,,,,它们在性态和它们在性态和类属方面存在着中介性类属方面存在着中介性,,,,,,,,具有亦此亦彼的性质具有亦此亦彼的性质,,,,,,,,因因此适合进行此适合进行软划分软划分。。聚类分析的基本概念聚类分析的基本概念••模糊集理论的提出为软划分提供了有力的分析模糊集理论的提出为软划分提供了有力的分析工具工具,,,,,,,,用模糊数学的方法来处理聚类问题用模糊数学的方法来处理聚类问题,,,,,,,,被称被称之为模糊聚类分析。由于模糊聚类得到了样本之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度属于各个类别的不确定性程度,,,,,,,,表达了样本类属表达了样本类属的中介性的中介性,,,,,,,,更能客观地反映现实世界更能客观地反映现实世界,,,,,,,,从而成为从而成为聚类分析研究的主流。聚类分析研究的主流。••模糊聚类已经在诸多领域获得了广泛的应用模糊聚类已经在诸多领域获得了广泛的应用,,,,,,,,如如模式识别、图像处理、信道均衡、矢量量化编模式识别、图像处理、信道均衡、矢量量化编码、神经网络的训练、参数估计、医学诊断、码、神经网络的训练、参数估计、医学诊断、天气预报、食品分类、水质分析等。天气预报、食品分类、水质分析等。聚类分析的基本概念聚类分析的基本概念••常用的模糊聚类分析方法大致可分为两大类：常用的模糊聚类分析方法大致可分为两大类：其一是基于模糊关系其一是基于模糊关系((((((((矩阵矩阵))))))))的聚类分析方法的聚类分析方法,,,,,,,,而而作为其中核心步骤的模糊分类作为其中核心步骤的模糊分类,,,,,,,,有下述的主要方有下述的主要方法：法：模糊传递闭包法、直接聚类法模糊传递闭包法、直接聚类法、最大树法、最大树法和编网法和编网法;;;;;;;;其二是基于目标函数的聚类分析方法其二是基于目标函数的聚类分析方法,,,,,,,,称为模糊称为模糊CCCCCCCC均值均值(FCM)(FCM)(FCM)(FCM)(FCM)(FCM)(FCM)(FCM)聚类算法聚类算法((((((((或称为模糊或称为模糊ISODATAISODATAISODATAISODATAISODATAISODATAISODATAISODATA聚类分析法聚类分析法))))))))。。••本讲先介绍第一类方法本讲先介绍第一类方法,,,,,,,,作为准备先讲解模糊关作为准备先讲解模糊关系传递闭包的基本概念。系传递闭包的基本概念。模糊关系的传递闭包模糊关系的传递闭包••设设XXXXXXXX,,,,,,,,YYYYYYYY是非空经典集是非空经典集,,,,,,,,XXXXXXXX到到YYYYYYYY的一个模糊的一个模糊((((((((二元二元))))))))关关系系RRRRRRRR是指是指XXXXXXXX××××××××YYYYYYYY上的一个模糊集上的一个模糊集RRRRRRRR::::::::XXXXXXXX××××××××YYYYYYYY→→→→→→→→[0,1].[0,1].[0,1].[0,1].[0,1].[0,1].[0,1].[0,1].XXXXXXXX到到XXXXXXXX的模糊关系称为的模糊关系称为XXXXXXXX上的模糊关系上的模糊关系。。••设设RRRRRRRR是是XXXXXXXX上的模糊关系上的模糊关系,,,,,,,,即即RRRRRRRR∈∈∈∈∈∈∈∈FFFFFFFF((((((((XXXXXXXX××××××××XXXXXXXX).).).).).).).).称称RRRRRRRR是自反是自反的的,,,,,,,,如果如果RRRRRRRR((((((((xxxxxxxx,,,,,,,,xxxxxxxx)=1,)=1,)=1,)=1,)=1,)=1,)=1,)=1,∀∀∀∀∀∀∀∀xxxxxxxx∈∈∈∈∈∈∈∈XXXXXXXX........称称RRRRRRRR是对称的是对称的,,,,,,,,如果如果RRRRRRRR((((((((xxxxxxxx,,,,,,,,yyyyyyyy)=)=)=)=)=)=)=)=RRRRRRRR((((((((yyyyyyyy,,,,,,,,xxxxxxxx),),),),),),),),∀∀∀∀∀∀∀∀xxxxxxxx,,,,,,,,yyyyyyyy∈∈∈∈∈∈∈∈XXXXXXXX........••若若RRRRRRRR是是XXXXXXXX上的自反、对称的模糊关系上的自反、对称的模糊关系,,,,,,,,则称则称RRRRRRRR是是XXXXXXXX上的上的模糊相似关系模糊相似关系。。模糊关系模糊关系••某家庭子女和父母外貌相像关系为某家庭子女和父母外貌相像关系为RRRRRRRR,,,,,,,,父母和祖父母和祖父母、外祖父母相像关系为父母、外祖父母相像关系为SSSSSSSS,,,,,,,,它们分别用以下它们分别用以下模糊矩阵确定模糊矩阵确定,,,,,,,,计算其计算其max-minmax-minmax-minmax-minmax-minmax-minmax-minmax-min合成。合成。0.80.20.10.7⎡⎤⎢⎥⎣⎦父父母母子子女女0.50.70.10.10.100.20.8⎡⎤⎢⎥⎣⎦祖父祖父祖母祖母外祖父外祖父外祖母外祖母父父母母模糊关系的传递闭包模糊关系的传递闭包••设设RRRRRRRR∈∈∈∈∈∈∈∈FFFFFFFF((((((((XXXXXXXX××××××××XXXXXXXX).).).).).).).).称称RRRRRRRR是是传递的传递的,,,,,,,,如果对任意如果对任意λλλλλλλλ∈∈∈∈∈∈∈∈[0,1][0,1][0,1][0,1][0,1][0,1][0,1][0,1]及任意及任意xxxxxxxx,,,,,,,,yyyyyyyy,,,,,,,,zzzzzzzz∈∈∈∈∈∈∈∈XXXXXXXX成立成立::::::::••RRRRRRRR((((((((xxxxxxxx,,,,,,,,yyyyyyyy))))))))≥≥≥≥≥≥≥≥λλλλλλλλ,,,,,,,,RRRRRRRR((((((((yyyyyyyy,,,,,,,,zzzzzzzz))))))))≥≥≥≥≥≥≥≥λλλλλλλλ⇒⇒⇒⇒⇒⇒⇒⇒RRRRRRRR((((((((xxxxxxxx,,,,,,,,zzzzzzzz))))))))≥≥≥≥≥≥≥≥λλλλλλλλ........••若若RRRRRRRR是是XXXXXXXX上的自反、对称、传递的模糊关系上的自反、对称、传递的模糊关系,,,,,,,,则则称称RRRRRRRR是是XXXXXXXX上的模糊等价关系上的模糊等价关系。。••设设RRRRRRRR∈∈∈∈∈∈∈∈FFFFFFFF((((((((XXXXXXXX××××××××XXXXXXXX).).).).).).).).则则••(1)(1)(1)(1)(1)(1)(1)(1)RRRRRRRR是自反的是自反的⇔⇔⇔⇔⇔⇔⇔⇔IIIIIIII⊆⊆⊆⊆⊆⊆⊆⊆RRRRRRRR,,,,,,,,这里这里IIIIIIII是恒等关系是恒等关系,,,,,,,,即当即当xxxxxxxx========yyyyyyyy时时IIIIIIII((((((((xxxxxxxx,,,,,,,,yyyyyyyy)=1,)=1,)=1,)=1,)=1,)=1,)=1,)=1,当当xxxxxxxx≠≠≠≠≠≠≠≠yyyyyyyy时时IIIIIIII((((((((xxxxxxxx,,,,,,,,yyyyyyyy)=0.)=0.)=0.)=0.)=0.)=0.)=0.)=0.••(2)(2)(2)(2)(2)(2)(2)(2)RRRRRRRR是对称的是对称的⇔⇔⇔⇔⇔⇔⇔⇔RRRRRRRR========RRRRRRRR−−−−−−−−11111111........••(3)(3)(3)(3)(3)(3)(3)(3)RRRRRRRR是传递的是传递的⇔⇔⇔⇔⇔⇔⇔⇔RRRRRRRR22222222⊆⊆⊆⊆⊆⊆⊆⊆RRRRRRRR........模糊关系的传递闭包模糊关系的传递闭包••设设RRRRRRRR∈∈∈∈∈∈∈∈FFFFFFFF((((((((XXXXXXXX××××××××XXXXXXXX).).).).).).).).则则RRRRRRRR是模糊等价关系当且仅当对是模糊等价关系当且仅当对任意任意λλλλλλλλ∈∈∈∈∈∈∈∈[0,1],[0,1],[0,1],[0,1],[0,1],[0,1],[0,1],[0,1],RRRRRRRRλλλλλλλλ是等价关系。是等价关系。••论域论域XXXXXXXX上的经典等价关系可以导出上的经典等价关系可以导出XXXXXXXX的一个分类。的一个分类。论域论域XXXXXXXX上的上的一个模糊等价关系一个模糊等价关系RRRRRRRR对应一族经典等对应一族经典等价关系价关系{{{{{{{{RRRRRRRRλλλλλλλλ::::::::λλλλλλλλ∈∈∈∈∈∈∈∈[0,1]}.[0,1]}.[0,1]}.[0,1]}.[0,1]}.[0,1]}.[0,1]}.[0,1]}.这说明模糊等价关系给出这说明模糊等价关系给出XXXXXXXX的一个分类的系列。这样的一个分类的系列。这样,,,,,,,,在实际应用问题中在实际应用问题中可以选择可以选择““““““““某个水平某个水平””””””””上的分类结果上的分类结果,,,,,,,,这就是模糊这就是模糊聚类分析的理论基础。聚类分析的理论基础。••实际问题中建立的模糊关系常常不是等价关系实际问题中建立的模糊关系常常不是等价关系而是相似关系而是相似关系,,,,,,,,这就需要这就需要将模糊相似关系改造为将模糊相似关系改造为模糊等价关系模糊等价关系,,,,,,,,传递闭包正是这样一种工具。传递闭包正是这样一种工具。模糊关系的传递闭包模糊关系的传递闭包••定义定义9.2.19.2.19.2.19.2.19.2.19.2.1