模式识别第4讲.ppt

1、模式识别,模式识别原理、方法及应用,第4次课程概要,数据聚类 非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,非监督学习分类,任务：分类 特点：不存在任何关于样本的先验知识。需要根据样本的内在相似性分类。,软木塞两类100个样本 我们真的能从中发现有两类吗？,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,聚类方法的用途,为了获得问题中数据有用的概括和解释。 为了启动一个监督学习的统计分类方法。 为了提供质心估计。,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,两类聚类方法,层次化算法 Hierarchical algorit

2、hm 也称树聚类算法，使用样本的联接规则，制造一个层次化序列的聚类问题解。 质心调整算法 Centroid adjustment algorithms 使用一种迭代方法调整聚类的典型模式点，也称作聚类的质心，从而形成一系列可分配给它们的样本。,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,距离尺度对于聚类结果的影响,对于这种十字交叉型数据，假设我们想将它分为两类，并满足类内平均错误率最小,欧氏距离尺度下的聚类 棋盘格距离尺度下的聚类,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,坐标轴的比例选取对聚类结果的影响,犯罪数据集在不同坐标轴比例下的分布

3、 既然作比例缩放对于分类结果有影响，为什么不在原分布下进行？,缩小了“人”的比例 缩小了“财产”的比例,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,常用的标准化方法,能够保证比例的不变性 ，或 至少可使距离度量方法在各种特征下的贡献达到一个最佳平衡。,语义信息丢失。 标准化实质上是在标准化样本间的差异，如果差异代表的是样本的类间差异，会对此产生一定程度上的破坏。,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,树聚类,树聚类算法或层次化聚类算法能够 （1）揭示样本集的内部相似性 （2）分级结构化这些相似性 对于有n个样本的集合，算法将产生1到n的

4、聚类序列，这些序列有着二叉树形式。 融合算法：起始于一个个独立的样本，自下而上地合并 分裂算法：起始于一个包含了所有样本的聚类,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,融合算法,（1）给定n个样本x1,xn，将每个样本看成一类i=xi （2）聚类数c=n； （3）当c1，重复以下操作： 3.1 利用合适的相似性度量尺度和规则确定最相近的两个聚类i j 3.2 合并i和j： ij=i，j，从而得到一个聚类数为c-1的解 3.3 按照以上方法递减c值,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,融合过程示例（1）,完全联接 两个聚类之间的相似

5、性由两类中距离最远的一对样本间的相似性衡量 通常情况下，聚类结果越平衡（各类样本数均衡），则结果越有意义。,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,融合过程示例（2）,犯罪数据集 理想的聚类结果？,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,分裂算法,从上至下进行 将整个样本集合看成是一个大聚类。 每一步分裂选择一个相异程度最大的分裂。 从1个聚类开始，n个聚类结束。,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,联接规则,回顾我们已经知道的衡量两个聚类之间相异程度的方法 完全联接规则 单联接 完全联接规则 类间平

6、均联接规则 类内平均联接规则 Ward方法,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,单联接/最近邻NN(Nearest neighbor)规则,衡量两个聚类之间的相异程度时，用的是两个聚类中相距最近的两个样本之间的相异程度 范数的计算可以是2.2节中的任何一种距离尺度 只要两个聚类中存在相近的点，就合并这两个类。 链式效应：即便类中其它相距很远的点存在，也会合并。,对散乱的点和链条形的数据集，该方法聚类效果较好,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,单联接 Globular数据,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚

7、类 聚类有效性,单联接 Filamentary数据,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,完全联接规则/FN(Furthest neighbor),衡量两个聚类之间的相异程度时，用的是两个聚类中相距最远的两个样本之间的相异程度,当各类聚集紧密，近似球状，大小均衡,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,当FN遇到链式数据,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,类间平均联接规则,单联接和完全联接规则代表了在相异程度估计时的极端情况，因此对于不典型情况较为敏感。 下面关注“平均”意义上的所有可能信息。 U

8、PGMA：un-weighted pair-group method using arithmetic averages 衡量聚类之间的相异度时，用的是两个聚类中所有样本对之间的平均相异程度,这种方法对于多种聚类形状有效,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,类内平均联接规则,UWGMA：un-weighted within-group method using arithmetic averages 衡量聚类之间的相异度时，首先将两个类假想成一个类，然后用这个类内所有样本对之间的平均距离表示,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性

9、,希望聚类的“体积”尽可能小时，该规则非常有效,Ward方法,对于得到的融合聚类，将计算类内距离的平方和。 每一步中，计算每个类对于总的类内距离平方和的贡献。 选择引起最小增长的两个类进行融合。 该方法可以得到很好的结果，只是它倾向于得到规模小的聚类。,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,树聚类应用实例(1),根据数据分布图来选择合适的距离尺度和联接规则 数据具备球形分布的特征：欧氏距离 Ward方法,得到两类：高的和低的财产方面的犯罪率,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,树聚类应用实例(2),用来检测用于监督学习分类的训练

10、集的“自然”特性 软木塞数据，其中用新的特征PRT10=PRT/10代替PRT特征。,已知类标签,Ward规则，欧氏平方距离尺度下的聚类,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,回顾PCA用于降维的过程,利用PCA分析得到的基变换矩阵P对X作线性变换得到Y 根据本征值（即方差）找到主元 对Y中的特征，根据方差进行排序，确定保留的特征数 取Y中保留的特征参与分类,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,因子分析,从一个例子了解因子模型 考虑5项生理指标 (收缩压 x1、舒张压 x2、心跳间隔 x3、呼吸间隔 x4、舌下温度 x5) 这5

11、项指标受交感神经和副交感神经支配 这个问题体现了5个生理指标有两个公共因子，假设5个指标已标准化,f1、f2就是公共因子 li1、li2是因子负荷factor loading ui是特殊因子,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,因子分析能做什么？,上一个例子由先验知识知道：5个生理指标与公共因子是有关联的 而这种关联可通过因子负荷L量化，实际上,以岩石数据为例，说明因子分析结果的语义解释,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,主成分因子法估计因子模型,根据PCA的结果（保证多少个成分）确定公共因子的个数 即用主成分作为公共因子

12、比如由m个特征、n个样本组成的数据集，经PCA分析，保留前两个主成分，这两个特征根分别是 ，对应的m维特征向量a1a2,i=1m j=12,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,降维：将高维数据转换到因子空间,利用因子得分计算公共因子F 公共因子fi=得分系数*X1 利用因子负荷矩阵和特殊方差矩阵计算得分系数 因子负荷矩阵可由因子模型估计获得 特殊方差矩阵可由以下关系得到 原样本集方差=li12+li1k+特殊方差 具体可见Bartlett法或Thomson法,因子得分计算式的系数,因子空间的数据分布,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚

13、类有效性,多维比例尺变换,与PCA和因子分析相比，适用范围广。 该方法约束条件少，没有数据关系及分布上的假设。,主要思路：通过迭代，找到最近似高维空间中样本对距离的低维表示 （1）获取原D维空间中每对样本对之间的距离d(xi,yi) （2）确定想要的维数d （3）从原D维特征中选择d个特征，形成低维样本集 （4）计算低维样本集中每对样本对之间的距离d*(xi,yi) （5）将d*与f(d)比较（f为单调变换函数），如果不近似，则重复(3)，足够近似则终止迭代,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,多维比例尺变换计算相异程度矩阵,非监督学习分类 标准化问题 树聚类

14、 降维问题 K均值聚类 聚类有效性,多维比例尺变换迭代过程,计算不同特征组合的d维空间下的相异程度矩阵 并进行近似计算（将d*与f(d)比较（f为单调变换函数）,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,多维比例尺变换迭代终止，得到满意的结果,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,基于多维比例尺变换降维的树聚类,Food数据 欧氏距离 Ward法树聚类,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,K均值聚类,将样本集划分成k个类，这种划分使得下式最小,是第j个类的质心,如果想要设计一个算法求得全局最优解，就必

15、须完成 次聚类，找出其中使得E最小的聚类结果。 而K均值聚类则是一个求得局部最优解的算法。,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,K均值聚类算法描述,（1）从n个样本中选择k个质心 （2）将数据集当中每一个xi分配到与之相距最近的质心mj代表的聚类中 （3）分配后，质心会发生变化，计算新质心以及E值 （4）重复（2）和（3）直到达到最大迭代次数或新计算的E值与上一次迭代得到的E值之间的差别小于一个给定的阈值,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,K均值聚类初始质心的选择,因为是局部最优解算法，初始点的选择就格外重要 常用的初始点选

16、择方法有： （1）随机选取 （2）选择特殊的样本作为初始质心。（通过对小样本树聚类获取） （3）将所有的样本之间的距离进行排列，然后选择将这些距离差不多等分的样本作为质心 （4）选择使得类间距离最大的样本作为质心 （选择任意k个样本作为质心，对于任意一个非质心样本o，计算它与各质心的距离，找到与o最近的质心m，若o与m的距离大于质心对的最小距离，或者大于m与其它质心的最小距离，则o与m互换，即o为新的质心成员，而m则为一般对象）,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,K均值聚类K值的确定,预先确定 1 在较小的集合上通过树聚类得到 2 在经过多维比例尺变换降维后

17、的低维空间里，进行树聚类得到 根据聚类结果确定,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,聚类价值指数,衡量k聚类问题转化成k+1聚类问题时，聚类质量的变化 为什么不用总类内距离来衡量？,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,聚类价值指数用于确定K,134个样本的岩石数据集，用2维因子空间表达 分别进行k=1.8的聚类，迭代次数选择10，初始质心选择用方法4，得到聚类价值指数如右图所示,聚类数为3是最为有效的，对每类样本的分析也支持这一结论,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,复制分析（1）,复制分析

18、是一个交叉验证过程 以岩石数据进行K均值聚类为例，说明复制分析的过程 岩石数据已进行因子分析，并转换到2维因子空间 第一步 将原始数据集分成两个数据集S1和S2，分别含有66和68个样本,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,复制分析（2）,第二步在S1上运行k均值算法（k=3），确定质心如下表,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,复制分析（3）,第三步根据前页表中所示的质心（即S1上运行k均值算法得到的质心），将S2中的样本分配到离它们最近的质心所代表的类中，得到的聚类结果记作RS1 RS1：数据集S2根据S1聚类的质心得到的聚类结果,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,复制分析（4）,第四步在S2上聚类，采用的算法和参数均与S1上的聚类相同，得到聚类结果记作RS2，下表是S2上聚类得到的质心,非监督学习分类 标准化问题 树聚类 降维问题 K均值聚类 聚类有效性,复制分析（5）,第五步给出R