第七章模糊聚类分析课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一、模糊聚类分析,聚类分析：按照一定要求和原则对事物进行分类。,聚类：普通分类,清晰事物,模糊分类,带有模糊性的事物,三种模糊聚类方法：,传递闭包法,基于模糊等价关系；,直接聚类法,基于模糊相似关系；,模糊聚类法,基于模糊划分,.,一、模糊聚类分析聚类分析：按照一定要求和原则对事物进行分类。,1,二、模糊聚类分析的步骤,1.,选取特征指标,特征要有明确的意义，要有较强的分辨力，有代表性，并确定描述特征的变量。,分类事物的特征指标选择的如何，对分类结果有直接的影响。,二、模糊聚类分析的步骤1.选取特征指标,2,2.,数据标准化（正规化）,令,其中，,x,i,为原始数据；,是原始数据的均值；,是原始数据的标准差；,是数据处理后的数据。,2.数据标准化（正规化）令其中，xi 为原始数据；是原始数据,3,3.,标定,设,为待分类的对象，,u,j,有,m,个刻划其特征的,数据，,就是根据实际情况，按一个准则或某一种方法，给论域,U,中的元素两两之间都赋以区间,0,1,内的一个数，叫做,相似系数,。它的大小表征两个元素彼此接近或相似的程度。,，然后对于,u,i,与,u,j,，用,r,ij,表示,u,i,与,u,j,的,当,r,ij,0时，表示,u,i,与,u,j,截然不同；,当,r,ij,1时，表示,u,i,与,u,j,可以等同(不能说是完全相同);,r,ij,可根据具体问题来选取。方法有：,的相似程度，要求,3.标定 设为待分类的对象，uj有m个刻划其特征,4,（1）数量积法,，其中,显然,如果,r,ij,中出现负值，可采用下面方法,将全体,r,ij,进行重新调整,方法1 令,，则,方法2 令,其中,于是,（1）数量积法，其中显然如果 rij 中出现负值，可采用下,5,（2）夹角余弦法,如果,r,ij,中出现负值，也可采用上面方法调整,（3）相关系数法,其中,（2）夹角余弦法如果rij中出现负值，也可采用上面方法调整,6,（4）最大最小法,（5）算术平均最小法,（6）几何平均最小法,（4）最大最小法（5）算术平均最小法（6）几何平均最小法,7,（8）指数相似系数法,其中,s,k,适当选择.,（9）绝对值倒数法,M,适当选取使,r,ij,在 0,1 中且分散开,（7）绝对值指数法,（8）指数相似系数法其中 sk 适当选择.（9）绝对值倒数法,8,（11）非参数法,中正数个数，,中负数个数，,令,则,（10）绝对值减数法,（11）非参数法中正数个数，中负数个数，令则（10）绝对值减,9,（12）贴近度法,如果特征,则,u,i,u,j,可看作模糊向量,以它们的贴近度,D,(,u,i,u,j,),为其相似程度.,i),格贴近度,其中,ii)距离贴近度,其中,c,a,为适当选择参数值，,d,(,u,i,u,j,),为模糊集各种距离.,iii)算术平均最小贴近度,（12）贴近度法如果特征则 ui,uj 可看作模糊向量,10,（13）主观评定法,请有实际经验者直接对,u,i,，u,j,的相似程度评分，作为,r,ij,的值.,通过标定求出相似系数后，便可得到以,r,ij,为元素的模糊相似矩阵,R,(,r,ij,).,4.,聚类,选择一种合适的聚类方法，便可得到分类结果.,（13）主观评定法 请有实际经验者直接对 ui，uj,11,三、传递闭包法,1.,传递闭包法,根据标定所得模糊矩阵,R,，求出其传递闭包,为模糊等价矩阵，对,，,令,从1降到0得到,，根据,进行分类：,归为一类.,2.最佳阈值,的选取,聚类图给出各,值对应的分类，形成一种动态聚类，便于全面了解元素聚类，然后根据实际需要选择其阈值,，,便可确定元素的一种分类，至于如何选择阈值,，,使分类更加合理，除了凭经验外，还可用,F-,统计量来选取.,三、传递闭包法1.传递闭包法根据标定所得模糊矩阵R，求出其,12,F,-统计量,：,为待分类事物的全体，,设,x,jk,为描述元素,u,j,第,k,个特征的数据,.设,c,为,对应于,值的类数，,n,i,为第,i,类元素的个数，第,i,类元素记为,记,为第,i,类元素的第,k,个特征的平均值,而称,为第,i,类的聚类中心向量；,为全体元素的中,心向量，而,F-统计量：为待分类事物的全体，设xjk 为描述元素 uj,13,于是，称,为,F,-,统计量，其中,为第,i,类中元素,与中心,的距离.,可见,，,F,-统计量的分子表征类与类间的距离，分母表征类内元素间的距离.因此，,F,值越大，说明分类越合理，与此分类相对应的,F,-统计量最大的阈值,为最佳值.,于是，称为F-统计量，其中为第i类中元素与中心的距离.,14,求传递闭包的简便方法,设,为模糊相似矩阵，求,t,(,A,).,(1)求,假定,把,A,中的,a,1,m,a,m,1,a,11,a,mm,用圆圈,圈起来，并记,(2)在,A,中第一行、第,m,行中剩下,的元素中,找最大元素,即,.且设,在第,p,列.用,即分别代替,a,1,p,与,a,mp,以及它们的对称元素，,最后用圆圈将它们及 圈起来.,求传递闭包的简便方法设为模糊相似矩阵，求 t(A).(1),15,(3)假定,A,中有圈的,k,行,是,行.而,所在的列是,i,j,列，在这些行中剩下的元素中,找最大元,并设 在第,l,行，用,分别代替,继续此过程，到,k,=,n,-1,得到,t,(,A,),.,还有逐步平方法,：,及其对称矩阵，并把,a,ll,圈起来,(3)假定 A 中有圈的 k 行是行.而所在的列是 i,16,四、基于模糊相似关系的直接聚类法,1.,最大树法,聚类原则,是：,u,i,与,u,j,在,水平同类当且仅当在相似矩阵,R,的图中，存在一条权重不低于,的路联结,u,i,与,u,j,.,画出以被分类元素为结点，以相似矩阵,R,的元素,r,ij,为权重的一颗最大树；,(2)取定 ，砍断权重低于,的枝，得到一个不连通图，各连通分支变构成了在,水平上的分类.,四、基于模糊相似关系的直接聚类法1.最大树法 聚类原则,17,2.编网法,对给定的模糊相似矩阵,R,，取定水平,作,截矩阵,R,，,在,R,的主对角线上填入元素的符号，在对角线下方以结点号“*”代替 1，而“0”则略去不写，由结点向主对角线上引经线和纬线，称之为编网，通过经线和纬线能互相连接起来的元素，属于同类，从而实现了分类.,2.编网法对给定的模糊相似矩阵R，取定水平,作截矩阵R,18,五、基于模糊划分的模糊聚类法,1.,c-,划分,(1)普通,c-,划分,如果划分把普通集合分成,c,类，则此划分就叫,普通,c,-划分,，,即：若设,的特征可表为,，,那么,U,的普通,c,-划分是指,U,的,c,个子集,满足,:(1),(2),五、基于模糊划分的模糊聚类法1.c-划分(1)普通,19,其中,且满足 (1),(2),(表示每个,u,j,必属于且仅属于一类)；,(表示每类,A,i,至少有一个元素)；,反过来，任一满足条件(1)、(2)、(3)的矩阵对应着,U,的一个分类.,(1),(2),(3),这样的分类结果可以用一个,c,n,矩阵(称为,c,-,划分)来表示.,其中且满足 (1)(2)(表示每个uj必属于且仅属于一类),20,例如，设,U,=,u,1,u,2,u,3,u,4,若分类结果为,u,1,u,2,u,3,u,4,则对应的分类矩阵为,如果分类矩阵为,则对应着,U,的,分类为,u,1,u,2,u,3,u,4,.,例如，设 U=u1,u2,u3,u4,若分类结,21,记,V,为,c,n,实矩阵的集合，且,显然，对于给定的,U,及分类数,c,，类的分法不是唯一的.,M,c,包含了,U,的所有可能,c,类划分的结果，,M,c,称为将,U,分成,c,类的分类空间.这样的分类是通常的分类，称为,硬分类,.,记 V 为 cn 实矩阵的集合，且 显然，,22,(2)模糊,c-,划分,设,一个,c,n,模糊矩阵,若满足 (1),(2),(表示每个,u,j,属于,c,个模糊子集,A,i,的程度总和为,1,)；,(表示每类,A,i,不等于空集或,U,)；,则称,A,称为,U,的,模糊,c,-,划分矩阵,.,(2)模糊 c-划分设,一个 cn 模糊矩阵若满足,23,记,M,fc,称为,U,的,c,类,软分类空间,.显然,若将,M,c,和,M,fc,定义中的条件：,放宽为,则这样的分类空间分别称为退化的硬分类空间和退化的软分类空间.分别记为,M,co,和,M,fco,显然,记Mfc 称为 U 的 c 类软分类空间.显然若将 Mc,24,2.目标函数聚类法和硬,c-,均值算法划分,(1)目标函数法,目标函数是对给定的,c,的所有候选类进行度量，最优的类就是使目标函数达到局部最小值的类.对于硬分类情形，通常所选取的目标函数是总体组内误差平方和，其定义为,这里将每类,A,i,中元素各特征分别取平均值，所得的聚类中心向量记为,v,i,，也称为,A,i,的聚类中心.由于,A,i,类中元素个数,A,i,类中元素向量和为,因此聚类中心向量,2.目标函数聚类法和硬 c-均值算法划分(1)目标函数,25,记,V,称为聚类中心矩阵.若,则,u,j,到聚类中心,v,i,的距离为,A,i,中全体元素到中心距离平方和为,而,V,中所有元素到其所在类中心距离平方和为,最理想的,c,-划分显然是使,J,(,A,V,)取极小的,A,.,记V 称为聚类中心矩阵.若,则uj到聚类中心vi的距离为,26,(2),硬,c-,均值算法,步骤1：假设给出,n,个数据点,其中,.取定,并初始化,步骤2：当迭代次数为,时,计算聚类中心向量,其中,步骤3：用下式将,A,(,l,),更新为,(2)硬 c-均值算法步骤1：假设给出 n 个数据点,其,27,步骤4：比较,A,(,l,)和,A,(,l,+1),若,则停止算,法,；,否则，令,l,=,l,+1,，返回步骤2.,直观上看，硬,c,-均值算法：猜想,c,的硬分类（步骤1），寻找各分类的中心（步骤2），重新分配类的隶属度以减少数据和当前中心的误差平方（步骤3），当循环不再能显著的降低,J,(,A,V,),时，停止算法（步骤4）.,步骤4：比较 A(l)和 A(l+1),若,则停止算,28,3.模糊,c-,均值算法,定义目标函数,其中 是一个加权指数.,模糊,c,-均值算法的目标在于找到,和,使得,J,m,(,A,V,)最小,下面，首先建立这个最小化问题的必要条件，然后根据此条件提出模糊,c,-均值算法.,3.模糊 c-均值算法定义目标函数其中 是,29,定理,令,为一给,定数据集.设定,，假设对所有,，则仅当,和,时，,才是,J,m,(,A,V,),的局部最小值.,定理 令为一给定数据集.设定，假设对所有，则仅当和时，才,30,模糊,c-,均值算法(ISODATA方法)步骤：,步骤1：给定数据集,设定,并初始化,步骤2：当迭代次数为,时,计算聚类中心向量,步骤3：用下式将,，,更新为,模糊 c-均值算法(ISODATA方法)步骤：步骤1,31,步骤4：若,则停止算法；否则令,l=l,+1,，,返回步骤2.,注意,：本方法要求,因此取初始分类,A,(0),时,遇到,只有一个样本的类，要在聚类前先排除，待聚类后再加上该类，而参数,r,一般常取,r,2,.,步骤4：若,则停止算法；否则令 l=l+1，返回步骤2.注,32,4.模糊划分清晰化,在实际问题中，最后的分类结果都要求是明确的，因此，在使用模糊,c,-,划分分类后，都必须将模糊划分清晰化，可用下述方法进行.,方法1,对,若,则将,u,j,归入,A,i,类.,方法2,对,若,则将,u,j,归入,A,i,类.,4.模糊划分清晰化 在实际问题中，最后的分类结,33,