第七章模糊聚类分析ppt课件.ppt

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