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

1,第六章模糊聚类分析,6.1普通分类(分类是硬性的，非此即彼)一、集合的划分对集合X的一个划分，是指把X分成若干个子集X1,X2,Xn，使得满足下列二个条件：X1X2Xn=X，且对ij，XiXj=，(i,j=1,2,n)二、普通等价关系设R(XX)，称R是X上一个等价关系，若R满足下列三个条件：自反性：xX，有(x,x)R；对称性：x,yX，若(x,y)R，有(y,x)R；传递性：x,yX，若(x,y)R，(y,z)R，有(x,z)R。例6-1对集合(论域)X=人，则关系R=“年龄相同”就是X上的一个普通等价关系，因为满足下列三个条件：自反性：任何人与自己是“年龄相同”的；对称性：我与你年龄相同，你与我年龄也相同；传递性：我与你年龄相同，你与他年龄相同，我与他年龄也相同。三、普通分类一个普通等价关系决定一个普通分类。,2,一、建立X=X1,X2,Xn上的模糊关系矩阵R(叫标定),其中rij0,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是个适当的正常数，使得0rij1,11.绝对值减数法：,其中C是个适当的正常数，使得0rij1,二、进行聚类分模糊等价关系(矩阵)与模糊相似关系(矩阵)二种情况进行。,7,6.3模糊等价关系(矩阵)与聚类分析一、原理因为:模糊矩阵R是模糊等价矩阵对0,1，R的截矩阵R均是普通等价矩阵。所以:可通过R对X上的元素进行聚类。二、定理若水平1,2满足0121，则按2分出的每一类必是按1分出的一类的子类。,例6-2设论域X=X1,X2,X3,X4,X5，经过标定后得模糊关系矩阵为,易证R是X上的模糊等价矩阵，因此可从R出发对X中的元素进行模糊聚类。解：方法(一)：直接分类,8,取0.850.9，得：,按该水平，r35=r53=1，可将X3,X5归为一类，其余元素各自成一类，共分成四类：X=X1X2X3,X5X4,取0.80.85，得：,按该水平，r23=r32=r25=r52=r35=r53=1，可将X2,X3,X5归为一类，其余元素各自成一类，共分成三类：X=X1X2,X3,X5X4,取0.91，得：,可将X1,X2,X3,X4,X5各自成一类，共分成五类：X=X1X2X3X4X5,9,取0.20.8，得：,按该水平，r12=r21=r13=r31=r15=r51=r23=r32=r25=r52=r35=r53=1，可将X1,X2,X3,X5归为一类，其余元素各自成一类，共分成二类：X=X1,X2,X3,X5X4,取00.2，得：,按该水平，可将X1,X2,X3,X4,X5归为一类，共分成一类：X=X1,X2,X3,X4,X5,模糊聚类过程是一个动态过程，随水平由小到大，集合X的分类越来越细。,10,方法(二)：编网分类,取0.850.9，得：,按该水平，可将X3,X5归为一类，其余元素各自成一类，共分成四类：X=X1X2X3,X5X4,取0.91，得：,按该水平，可将X1,X2,X3,X4,X5各自成一类各自成一类，共分成五类：X=X1X2X3X4X5,11,取0.80.85，得：,按该水平，可将X2,X3,X5归为一类，其余元素各自成一类，共分成三类：X=X1X2,X3,X5X4,取0.20.8，得：,按该水平，可将X1,X2,X3,X5归为一类，其余元素各自成一类，共分成二类：X=X1,X2,X3,X5X4,12,取00.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.61，得：,可知X=X1X2X3在该水平上分类时，不十分注重商品销售额、购销费用、零售利润之间的相互影响关系，而是各自独立研究他们。,取0.40.6，得：,可知X=X1,X3X2在该水平上分类时，比较注重商品销售额和零售利润之间的相互影响关系，而不大注重他们和购销费用间的关系。,取00.4，得：,可知X=X1,X2,X3在该水平上分类时，对三者的相互关系之间都比较注重。,14,6.4模糊相似关系(矩阵)与聚类分析一、原理经标定得的模糊关系(矩阵)R不是模糊等价关系(矩阵)，它只具备自反性和对称性，不具备传递性，即R只是模糊相似关系(矩阵)。要利用R对X中的元素进行聚类，须将R改造成模糊等价关系(矩阵)。二、定理设R是模糊相似矩阵，进行如下复合运算：RR2=RRR4=R2R2R2k=RkRk若存在正整数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.80.9，得：,X=X1,X3X2X4X5,取0