《模式识别第4讲.ppt》由会员分享,可在线阅读,更多相关《模式识别第4讲.ppt(47页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、模式识别模式识别原理、方法及应用第4次课程概要n数据聚类q非监督学习分类q标准化问题q树聚类q降维问题qK均值聚类q聚类有效性非监督学习分类n任务:分类n特点:不存在任何关于样本的先验知识。需要根据样本的内在相似性分类。软木塞两类100个样本我们真的能从中发现有两类吗?非监督学非监督学习分类习分类标准化问题树聚类降维问题K均值聚类聚类有效性聚类方法的用途n为了获得问题中数据有用的概括和解释。n为了启动一个监督学习的统计分类方法。n为了提供质心估计。非监督学非监督学习分类习分类标准化问题树聚类降维问题K均值聚类聚类有效性两类聚类方法n层次化算法 Hierarchical algorithmq也称
2、树聚类算法,使用样本的联接规则,制造一个层次化序列的聚类问题解。n质心调整算法 Centroid adjustment algorithmsq使用一种迭代方法调整聚类的典型模式点,也称作聚类的质心,从而形成一系列可分配给它们的样本。非监督学非监督学习分类习分类标准化问题树聚类降维问题K均值聚类聚类有效性距离尺度对于聚类结果的影响n对于这种十字交叉型数据,假设我们想将它分为两类,并满足类内平均错误率最小欧氏距离尺度下的聚类欧氏距离尺度下的聚类 棋盘格距离尺度下的聚类棋盘格距离尺度下的聚类非监督学习分类标准化问标准化问题题树聚类降维问题K均值聚类聚类有效性坐标轴的比例选取对聚类结果的影响n犯罪数据
3、集在不同坐标轴比例下的分布n既然作比例缩放对于分类结果有影响,为什么不在原分布下进行?缩小了缩小了“人人”的比例的比例 缩小了缩小了“财产财产”的比例的比例非监督学习分类标准化问标准化问题题树聚类降维问题K均值聚类聚类有效性常用的标准化方法n能够保证比例的不变能够保证比例的不变性性,或,或n至少可使距离度量方至少可使距离度量方法在各种特征下的贡法在各种特征下的贡献达到一个最佳平衡。献达到一个最佳平衡。语义信息丢失。语义信息丢失。标准化实质上是在标准化样本间的标准化实质上是在标准化样本间的差异,如果差异代表的是样本的类差异,如果差异代表的是样本的类间差异,会对此产生一定程度上的间差异,会对此产生
4、一定程度上的破坏。破坏。非监督学习分类标准化问标准化问题题树聚类降维问题K均值聚类聚类有效性树聚类n树聚类算法或层次化聚类算法能够q(1)揭示样本集的内部相似性q(2)分级结构化这些相似性n对于有n个样本的集合,算法将产生1到n的聚类序列,这些序列有着二叉树形式。q融合算法:起始于一个个独立的样本,自下而上地合并q分裂算法:起始于一个包含了所有样本的聚类非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性融合算法(1)给定n个样本x1,xn,将每个样本看成一类i=xi(2)聚类数c=n;(3)当c1,重复以下操作:3.1 利用合适的相似性度量尺度和规则确定最相近的两个聚类i j 3
5、.2 合并i和j:ij=i,j,从而得到一个聚类数为c-1的解 3.3 按照以上方法递减c值非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性融合过程示例(1)n完全联接完全联接n两个聚类之间的相似性由两类中距离最远的一对样本间的相似性衡量n通常情况下,聚类结果越平衡(各类样本数均衡),则结果越有意义。非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性融合过程示例(2)n犯罪数据集n理想的聚类结果?非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性分裂算法从上至下进行将整个样本集合看成是一个大聚类。每一步分裂选择一个相异程度最大的分裂。从1个聚类开始,
6、n个聚类结束。非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性联接规则n回顾我们已经知道的衡量两个聚类之间相异程度的方法q完全联接规则n单联接n完全联接规则n类间平均联接规则n类内平均联接规则nWard方法非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性单联接/最近邻NN(Nearest neighbor)规则n衡量两个聚类之间的相异程度时,用的是两个聚类中相距最近的两个样本之间的相异程度n范数的计算可以是2.2节中的任何一种距离尺度n只要两个聚类中存在相近的点,就合并这两个类。n链式效应:即便类中其它相距很远的点存在,也会合并。对对散散乱乱的点和的点和链链条条
7、形形的的数数据集,据集,该该方法聚方法聚类类效果效果较较好好 非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性单联接 Globular数据非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性单联接 Filamentary数据非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性完全联接规则/FN(Furthest neighbor)n衡量两个聚类之间的相异程度时,用的是两个聚类中相距最远的两个样本之间的相异程度当各类聚集紧密,近似球状,大小均衡当各类聚集紧密,近似球状,大小均衡 非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性当FN遇到链式
8、数据非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性类间平均联接规则n单联接和完全联接规则代表了在相异程度估计时的极端情况,因此对于不典型情况较为敏感。n下面关注“平均”意义上的所有可能信息。nUPGMA:un-weighted pair-group method using arithmetic averagesn衡量聚类之间的相异度时,用的是两个聚类中所有样本对之间的平均相异程度这种方法对于多种聚这种方法对于多种聚类形状有效类形状有效非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性类内平均联接规则nUWGMA:un-weighted within-group
9、 method using arithmetic averagesn衡量聚类之间的相异度时,首先将两个类假想成一个类,然后用这个类内所有样本对之间的平均距离表示非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性希望聚类的希望聚类的“体积体积”尽可能小时,该规则尽可能小时,该规则非常有效非常有效Ward方法n对于得到的融合聚类,将计算类内距离的平方和。n每一步中,计算每个类对于总的类内距离平方和的贡献。n选择引起最小增长的两个类进行融合。n该方法可以得到很好的结果,只是它倾向于得到规模小的聚类。非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性树聚类应用实例(1)n根
10、据数据分布图来选择合适的距离尺度和联接规则n数据具备球形分布的特征:欧氏距离nWard方法得到两类:高的和低的财产方面的犯罪率得到两类:高的和低的财产方面的犯罪率非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性树聚类应用实例(2)n用来检测用于监督学习分类的训练集的“自然”特性n软木塞数据,其中用新的特征PRT10=PRT/10代替PRT特征。已知类标签Ward规则,欧氏平方距离尺度下的聚类非监督学习分类标准化问题树聚类树聚类降维问题K均值聚类聚类有效性回顾PCA用于降维的过程n利用PCA分析得到的基变换矩阵P对X作线性变换得到Yn根据本征值(即方差)找到主元n对Y中的特征,根
11、据方差进行排序,确定保留的特征数n取Y中保留的特征参与分类非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性因子分析n从一个例子了解因子模型n考虑5项生理指标n(收缩压 x1、舒张压 x2、心跳间隔 x3、呼吸间隔 x4、舌下温度 x5)n这5项指标受交感神经和副交感神经支配n这个问题体现了5个生理指标有两个公共因子,假设5个指标已标准化f1、f2就是公共因子li1、li2是因子负荷factor loadingui是特殊因子非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性因子分析能做什么?n上一个例子由先验知识知道:5个生理指标与公共因子是有关联的n而这种关联
12、可通过因子负荷L量化,实际上以岩石数据为例,说明因子分析结果的语义解释以岩石数据为例,说明因子分析结果的语义解释非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性主成分因子法估计因子模型n根据PCA的结果(保证多少个成分)确定公共因子的个数n即用主成分作为公共因子n比如由m个特征、n个样本组成的数据集,经PCA分析,保留前两个主成分,这两个特征根分别是 ,对应的m维特征向量a1a2i=1mj=12非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性降维:将高维数据转换到因子空间n利用因子得分计算公共因子Fq公共因子fi=得分系数*X1q利用因子负荷矩阵和特殊方差矩
13、阵计算得分系数q因子负荷矩阵可由因子模型估计获得q特殊方差矩阵可由以下关系得到n原样本集方差=li12+li1k+特殊方差q具体可见Bartlett法或Thomson法因子得因子得分计算分计算式的系式的系数数因子空间的数据分布因子空间的数据分布非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性多维比例尺变换n与PCA和因子分析相比,适用范围广。n该方法约束条件少,没有数据关系及分布上的假设。n主要思路:通过迭代,找到最近似高维空间中样本对距离的低维表示n(1)获取原D维空间中每对样本对之间的距离d(xi,yi)n(2)确定想要的维数dn(3)从原D维特征中选择d个特征,形成低维
14、样本集n(4)计算低维样本集中每对样本对之间的距离d*(xi,yi)n(5)将d*与f(d)比较(f为单调变换函数),如果不近似,则重复(3),足够近似则终止迭代非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性多维比例尺变换计算相异程度矩阵非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性多维比例尺变换迭代过程计算不同特征组合的d维空间下的相异程度矩阵并进行近似计算(将d*与f(d)比较(f为单调变换函数)非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性多维比例尺变换迭代终止,得到满意的结果非监督学习分类标准化问题树聚类降维问题降维问题K均值
15、聚类聚类有效性基于多维比例尺变换降维的树聚类Food数据欧氏距离Ward法树聚类非监督学习分类标准化问题树聚类降维问题降维问题K均值聚类聚类有效性K均值聚类n将样本集划分成k个类,这种划分使得下式最小 是第j个类的质心如果想要设计一个算法求得全局最优解,就必须完成 次聚类,找出其中使得E最小的聚类结果。而K均值聚类则是一个求得局部最优解的算法。非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性K均值聚类算法描述(1)从n个样本中选择k个质心(2)将数据集当中每一个xi分配到与之相距最近的质心mj代表的聚类中(3)分配后,质心会发生变化,计算新质心以及E值(4)重复(2)和(
16、3)直到达到最大迭代次数或新计算的E值与上一次迭代得到的E值之间的差别小于一个给定的阈值非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性K均值聚类初始质心的选择n因为是局部最优解算法,初始点的选择就格外重要n常用的初始点选择方法有:n(1)随机选取n(2)选择特殊的样本作为初始质心。(通过对小样本树聚类获取)n(3)将所有的样本之间的距离进行排列,然后选择将这些距离差不多等分的样本作为质心n(4)选择使得类间距离最大的样本作为质心n(选择任意k个样本作为质心,对于任意一个非质心样本o,计算它与各质心的距离,找到与o最近的质心m,若o与m的距离大于质心对的最小距离,或者大于
17、m与其它质心的最小距离,则o与m互换,即o为新的质心成员,而m则为一般对象)非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性K均值聚类K值的确定n预先确定预先确定q1 在较小的集合上通过树聚类得到q2 在经过多维比例尺变换降维后的低维空间里,进行树聚类得到n根据聚类结果确定根据聚类结果确定非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性聚类价值指数n衡量k聚类问题转化成k+1聚类问题时,聚类质量的变化n为什么不用总类内距离来衡量?非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性聚类价值指数用于确定Kn134个样本的岩石数据集,用
18、2维因子空间表达n分别进行k=1.8的聚类,迭代次数选择10,初始质心选择用方法4,得到聚类价值指数如右图所示聚类数为3是最为有效的,对每类样本的分析也支持这一结论非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性复制分析(1)n复制分析是一个交叉验证过程n以岩石数据进行K均值聚类为例,说明复制分析的过程n岩石数据已进行因子分析,并转换到2维因子空间n第一步 将原始数据集分成两个数据集S1和S2,分别含有66和68个样本非监督学习分类标准化问题树聚类降维问题K均值聚类聚类有效聚类有效性性复制分析(2)n第二步在S1上运行k均值算法(k=3),确定质心如下表非监督学习分类标准
19、化问题树聚类降维问题K均值聚类聚类有效聚类有效性性复制分析(3)n第三步根据前页表中所示的质心(即S1上运行k均值算法得到的质心),将S2中的样本分配到离它们最近的质心所代表的类中,得到的聚类结果记作RS1 RS1:数据集S2根据S1聚类的质心得到的聚类结果非监督学习分类标准化问题树聚类降维问题K均值聚类聚类有效聚类有效性性复制分析(4)n第四步在S2上聚类,采用的算法和参数均与S1上的聚类相同,得到聚类结果记作RS2,下表是S2上聚类得到的质心非监督学习分类标准化问题树聚类降维问题K均值聚类聚类有效聚类有效性性复制分析(5)n第五步给出RS1与RS2的一致性表,用以计算两种聚类方法的一致程度非监督学习分类标准化问题树聚类降维问题K均值聚类聚类有效聚类有效性性利用 统计法进行一致性计算n将68个目标利用2种方法分配到3个类别n可得到3*3矩阵,类似下表非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性岩石数据的一致性计算Z=9.5 大于Z=0.01=2.32因此,在0.01显著水平上,一致性程度高,聚类方法有效岩石数据:68个目标利用2种方法分配到3个类别P(A)=0.971 P(E)=0.418 =0.95非监督学习分类标准化问题树聚类降维问题K K均值聚类均值聚类聚类有效性
限制150内