第七章模糊聚类分析精选文档.ppt

《第七章模糊聚类分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章模糊聚类分析精选文档.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章模糊聚类分析本讲稿第一页，共三十四页一、模糊聚类分析一、模糊聚类分析聚类分析：按照一定要求和原则对事物进行分类。聚类分析：按照一定要求和原则对事物进行分类。聚类：普通分类聚类：普通分类清晰事物清晰事物 模糊分类模糊分类带有模糊性的事物带有模糊性的事物三种模糊聚类方法：三种模糊聚类方法：传递闭包法传递闭包法基于模糊等价关系；基于模糊等价关系；直接聚类法直接聚类法基于模糊相似关系；基于模糊相似关系；模糊聚类法模糊聚类法基于模糊划分基于模糊划分.本讲稿第二页，共三十四页二、模糊聚类分析的步骤二、模糊聚类分析的步骤1.选取特征指标选取特征指标 特征要有明确的意义，要有较强的分辨力，有代表性，并确

2、定描述特征的变量。分类事物的特征指标选择的如何，对分类结果有直接的影响。本讲稿第三页，共三十四页 2.数据标准化（正规化）数据标准化（正规化）令令其中，其中，x xi i 为原始数据；为原始数据；是原始数据的均值；是原始数据的标准差；是数据处理后的数据。本讲稿第四页，共三十四页 3.标定标定 设为待分类的对象，uj有m个刻划其特征的数据，就是根据实际情况，按一个准则或某一种方法，给论域就是根据实际情况，按一个准则或某一种方法，给论域U U中的元中的元素两两之间都赋以区间素两两之间都赋以区间0,10,1内的一个数，叫做内的一个数，叫做相似系数相似系数。它的。它的大小表征两个元素彼此接近或相似的程

3、度。大小表征两个元素彼此接近或相似的程度。，然后对于 ui与 uj，用 rij 表示 ui 与 uj 的当rij0时，表示ui与uj截然不同；当rij1时，表示ui与uj可以等同(不能说是完全相同);rij可根据具体问题来选取。方法有：的相似程度，要求本讲稿第五页，共三十四页（1）数量积法）数量积法，其中显然如果 rij 中出现负值，可采用下面方法将全体 rij 进行重新调整方法1 令，则方法2 令其中于是本讲稿第六页，共三十四页（2）夹角余弦法）夹角余弦法如果rij中出现负值，也可采用上面方法调整（3）相关系数法）相关系数法其中本讲稿第七页，共三十四页（4）最大最小法）最大最小法（5）算术平

4、均最小法）算术平均最小法（6）几何平均最小法）几何平均最小法本讲稿第八页，共三十四页（8）指数相似系数法）指数相似系数法其中 sk 适当选择.（9）绝对值倒数法）绝对值倒数法M 适当选取使 rij 在 0,1 中且分散开（7）绝对值指数法）绝对值指数法本讲稿第九页，共三十四页（11）非参数法）非参数法中正数个数，中负数个数，令则（10）绝对值减数法）绝对值减数法本讲稿第十页，共三十四页（12）贴近度法）贴近度法如果特征则 ui,uj 可看作模糊向量,以它们的贴近度 D(ui,uj)为其相似程度.i)格贴近度,其中ii)距离贴近度其中 c,a 为适当选择参数值，d(ui,uj)为模糊集各种距离.

5、iii)算术平均最小贴近度本讲稿第十一页，共三十四页（13）主观评定法）主观评定法 请有实际经验者直接对 ui，uj 的相似程度评分，作为 rij 的值.通过标定求出相似系数后，便可得到以 rij 为元素的模糊相似矩阵 R(rij).4.聚类聚类选择一种合适的聚类方法，便可得到分类结果.本讲稿第十二页，共三十四页三、传递闭包法三、传递闭包法 1.传递闭包法传递闭包法根据标定所得模糊矩阵R，求出其传递闭包为模糊等价矩阵，对，令从1降到0得到，根据进行分类：归为一类.2.2.最佳阈值最佳阈值最佳阈值最佳阈值的选取的选取的选取的选取 聚类图给出各值对应的分类，形成一种动态聚类，便于全面了解元素聚类，

6、然后根据实际需要选择其阈值，便可确定元素的一种分类，至于如何选择阈值，使分类更加合理，除了凭经验外，还可用 F-统计量来选取.本讲稿第十三页，共三十四页F-统计量统计量：为待分类事物的全体，设xjk 为描述元素 uj 第 k 个特征的数据.设 c 为对应于 值的类数，ni 为第 i 类元素的个数，第 i 类元素记为记为第 i 类元素的第 k 个特征的平均值,而称为第 i 类的聚类中心向量；为全体元素的中心向量，而本讲稿第十四页，共三十四页于是，称为F-统计量，其中为第i类中元素与中心的距离.可见，F-统计量的分子表征类与类间的距离，分母表征类内元素间的距离.因此，F 值越大，说明分类越合理，与

7、此分类相对应的 F-统计量最大的阈值为最佳值.本讲稿第十五页，共三十四页求传递闭包的简便方法求传递闭包的简便方法求传递闭包的简便方法求传递闭包的简便方法设为模糊相似矩阵，求 t(A).(1)求,假定,把 A 中的 a1m,am1,a11,amm 用圆圈圈起来，并记(2)在 A 中第一行、第 m行中剩下的元素中找最大元素,即.且设在第 p 列.用即分别代替 a1p 与 amp 以及它们的对称元素，最后用圆圈将它们及 圈起来.本讲稿第十六页，共三十四页(3)假定 A 中有圈的 k 行是行.而所在的列是 ij 列，在这些行中剩下的元素中找最大元并设 在第 l 行，用 分别代替继续此过程，到 k=n-

8、1,得到 t(A).还有逐步平方法：及其对称矩阵，并把 all 圈起来本讲稿第十七页，共三十四页四、基于模糊相似关系的直接聚类法四、基于模糊相似关系的直接聚类法1.最大树法最大树法 聚类原则是：ui与uj在水平同类当且仅当在相似矩阵R的图中，存在一条权重不低于的路联结ui与uj.(1)画出以被分类元素为结点，以相似矩阵R的元素 rij 为权重的一颗最大树；(2)取定 ，砍断权重低于的枝，得到一个不连通图，各连通分支变构成了在水平上的分类.本讲稿第十八页，共三十四页2.2.编网法编网法编网法编网法对给定的模糊相似矩阵R，取定水平,作截矩阵R，在 R 的主对角线上填入元素的符号，在对角线下方以结点

9、号“*”代替 1，而“0”则略去不写，由结点向主对角线上引经线和纬线，称之为编网，通过经线和纬线能互相连接起来的元素，属于同类，从而实现了分类.本讲稿第十九页，共三十四页五、基于模糊划分的模糊聚类法五、基于模糊划分的模糊聚类法1.c-c-划分划分划分划分(1)(1)普通普通普通普通 c-c-划分划分划分划分如果划分把普通集合分成 c 类，则此划分就叫普通 c-划分，即：若设的特征可表为，那么U的普通c-划分是指U的c个子集满足:(1)(2)本讲稿第二十页，共三十四页其中且满足 (1)(2)(表示每个uj必属于且仅属于一类)；(表示每类Ai至少有一个元素)；反过来，任一满足条件(1)、(2)、(

10、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)(2)模糊模糊模糊模糊

11、 c-c-划分划分划分划分设,一个 cn 模糊矩阵若满足 (1)(2)(表示每个 uj 属于 c 个模糊子集 Ai 的程度总和为 1)；(表示每类 Ai 不等于空集或 U)；则称 A 称为 U 的模糊 c-划分矩阵.本讲稿第二十四页，共三十四页记Mfc 称为 U 的 c 类软分类空间.显然若将 Mc 和Mfc 定义中的条件：放宽为则这样的分类空间分别称为退化的硬分类空间和退化的软分类空间.分别记为 Mco 和 Mfco,显然本讲稿第二十五页，共三十四页2.2.目标函数聚类法和硬目标函数聚类法和硬目标函数聚类法和硬目标函数聚类法和硬 c-c-均值算法划分均值算法划分均值算法划分均值算法划分(1)

12、目标函数法目标函数法 目标函数是对给定的 c 的所有候选类进行度量，最优的类就是使目标函数达到局部最小值的类.对于硬分类情形，通常所选取的目标函数是总体组内误差平方和，其定义为这里将每类 Ai 中元素各特征分别取平均值，所得的聚类中心向量记为 vi，也称为 Ai 的聚类中心.由于 Ai 类中元素个数,Ai类中元素向量和为,因此聚类中心向量本讲稿第二十六页，共三十四页记V 称为聚类中心矩阵.若,则uj到聚类中心vi的距离为Ai 中全体元素到中心距离平方和为而 V 中所有元素到其所在类中心距离平方和为最理想的 c-划分显然是使 J(A,V)取极小的 A.本讲稿第二十七页，共三十四页(2)硬硬 c-

13、均值算法均值算法步骤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.3.模糊模糊模糊模糊 c-c-均值算法均值算法均值算法均值算法定义目标函数其中 是一个加权指数.模糊

14、c-均值算法的目标在于找到和,使得 Jm(A,V)最小 下面，首先建立这个最小化问题的必要条件，然后根据此条件提出模糊 c-均值算法.本讲稿第三十页，共三十四页定理 令为一给定数据集.设定，假设对所有，则仅当和时，才是 Jm(A,V)的局部最小值.本讲稿第三十一页，共三十四页模糊 c-均值算法(ISODATA方法)步骤：步骤1：给定数据集设定,并初始化步骤2：当迭代次数为时,计算聚类中心向量步骤3：用下式将 ，更新为本讲稿第三十二页，共三十四页步骤4：若,则停止算法；否则令 l=l+1，返回步骤2.注意：本方法要求,因此取初始分类 A(0)时,遇到只有一个样本的类，要在聚类前先排除，待聚类后再加上该类，而参数 r 一般常取 r2.本讲稿第三十三页，共三十四页4.4.模糊划分清晰化模糊划分清晰化模糊划分清晰化模糊划分清晰化 在实际问题中，最后的分类结果都要求是明确的，因此，在使用模糊 c-划分分类后，都必须将模糊划分清晰化，可用下述方法进行.方法1 对若则将 uj 归入 Ai 类.方法2 对若则将 uj 归入 Ai 类.本讲稿第三十四页，共三十四页