第7章-无监督学习和聚类

第7章无监督学习和聚类无监督学习和聚类无监督学习聚类相似性度量聚类的准则函数基于迭代最优化聚类方法基于划分的聚类方法层次聚类无监督学习有监督（supervised）学习训练集中每个样本都有一个类别标记所有类别事先已知常用于：分类、回归无监督（unsupervised）学习训练集中样本的类别标记未知给定一组样本，发现其内在性质，如类别和聚类常用于：聚类、概率密度估计无监督学习的动机收集并且标记大量模式往往花费巨大希望首先在一个较小的有标记样本集上训练一个粗略的分类器，然后让这个分类器以非监督的方式在一个较大的样本集上运行或者，用大量未标记的样本集来训练分类器，让它自动发现数据中的分组，然后用代价更高的办法（如人工）来标记这些分组在很多应用中，模式的特征会随时间而变化如果这种特征的变化能够被某种运行在无监督方式下的分类器捕捉到，那么分类性能将得到大幅提高无监督学习的动机无监督方法可以用来提取特征，或者预处理现存特征，从而为后续的模式识别问题做准备例如：PCA降维在任何探索性的工作中，无监督方法可以揭示观测数据的一些内部结构和规律发现模式中内在的聚类或分组可能为分类器设计提供依据无监督学习与有监督学习方法的区别：有监督学习方法必须有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而无监督学习没有训练集，只有一组数据，在该组数据集内寻找规律。有监督学习方法的目的是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号样本组成；而无监督学习方法只有分析数据集本身，无标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号为目的。无监督学习方法在寻找数据集中的规律性，这种规律性不是划分数据集的目的，即不一定要“分类”。比如分析数据的主分量，或分析数据集的特点。无监督学习方法分析数据集的主分量与用K-L变换计算数据集的主分量又有区别。K-L变换不是一种学习方法，不属于无监督学习方法。无监督学习方法可以分成两大类：一类为基于概率密度函数估计的直接方法：设法找到各类别在特征空间的分布参数再进行分类；一类称为基于样本间相似性度量的间接聚类方法。其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。基于概率密度函数估计的直接方法该方法的关键是找出各个峰值区。单峰子类的分离方法(称为投影法)每个分量有无峰谷点表现出来。利用投影，直接找密集区域。样本在整个特征空间中呈现两个分布高峰。如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值，这些区域被称为单峰区域。而每个单峰区域则被看作不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为单峰子类。投影法对于样本在某一种度量中的分布统计，一般称为直方图统计，在样本数量很大时，又可作为概率统计的估计。由于这种方法基于将样本投影到某个坐标轴上，因而称为投影方法。使用投影方法有两个组成部分一个是如何设计合适的坐标系统。另一是如何设计直方图。投影法在样本属性完全不知的情况下，如何选择坐标系统比较困难的。目前还没有一个准则函数来表征这样坐标系统的性质。一种启发式的办法是使待分类的样本在某个坐标轴方向具有最大的分散性，采用前面讨论过的K-L变换方法。投影法用混合样本协方差矩阵作为K-L变换的产生矩阵，找到其特征值，并按大小排序。对应最大特征值的特征向量对此混合样本来说，离散程度最大，预期能发现明显的峰值，但是这种方法并不能保证分出各个聚类。【投影方法】基本步骤问题：这样投影有时并不能产生多峰的边缘密度函数-方差最大的准则有时并不一定最有利于聚类。【存在问题】失败的例子【回顾】直接方法：1.估计概率密度函数——困难2.寻找密度函数中的单峰间接方法：考查样本这间的相似性，根据相似性把样本集划分为若干子集，使某种表示聚类质量的准则函数最优。不同的聚类方法实际上反映了对聚类的不同理解：混合模型：数据服从混合分布，聚类对应于各分布单峰子集：聚类即概率分布中的单峰，即样本分布相对集中的区域间接方法：相似的样本聚类，不同聚类的样本不相似无监督学习和聚类无监督学习聚类相似性度量聚类的准则函数基于迭代最优化聚类方法基于划分的聚类方法层次聚类聚类聚类（clustering）聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程因为训练集样本并无类别标记，所以聚类是无监督学习过程一个聚类（cluster）是指一组样本，它们与属于同一聚类的样本相似，而与属于其他聚类的样本不相似聚类可用作一种独立的数据分析工具，用于分析数据的内在特性一种数据预处理方法，为后续模式识别服务20取决于分类算法和特征点分布情况的匹配。注意：聚类方法的有效性2w2W1w1W2x1xb分类无效时的情况1.特征选取不当使分类无效。21分类无效时的情况2.特征选取不足可能使不同类别的模式判为一类。2w2W1w1W2x1x3w3W取决于分类算法和特征点分布情况的匹配。注意：聚类方法的有效性22分类无效时的情况3.特征选取过多可能无益反而有害,增加分析负担并使分析效果变差。2w2W1w1W2x1xb取决于分类算法和特征点分布情况的匹配。注意：聚类方法的有效性23量纲不同对聚类的影响分类无效时的情况4.量纲选取不当。无监督学习和聚类无监督学习聚类相似性度量聚类的准则函数基于迭代最优化聚类方法基于划分的聚类方法层次聚类相似性度量“同一聚类内部的样本之间比不同聚类的样本之间更相似”是聚类的基本假设。相似性度量：基于某种定义，描述样本间相似（或不相似）程度的度量几种主要的相似性（不相似性）度量基于度量的距离标准非度量的相似性函数匹配测度距离度量一个距离度量（即距离函数）需满足：非负性：自反性：对称性：三角不等式：12,0dxx1212,0ifandonlyifdxxxx1221,,dxxdxx122313,,,dxxdxxdxx距离度量常用的距离度量最为常用的距离度量为欧氏距离其次为考虑数据分布的马氏距离点对称距离流形距离……距离度量根据距离对样本进行聚类计算任意两个样本之间的距离如果两个样本之间的距离小于某个阈值d0，那么这两个样本就属于同一个聚类d0过大，所有样本都被分为同一个聚类d0过小，每个样本都自成一个聚类距离度量2019/10/8291.欧氏(Euclidean)距离：2.绝对值距离(街区距离，Manhattan距离)：3.切氏(Chebyshev)距离:4.明氏(Minkowski)距离:设)',,(,)',,(2121nnyyyyxxxx2/112])([||||),(niiiyxyxyxdniiiyxyxd1||),(||),(maxiiiyxyxdmnimiiyxyxd/11])([),(6.马氏(Mahalanobis)距离:设n维矢量是矢量集中的两个矢量miimiiijijijixmxxxxxmVxxVxxxxd1111)')((11)()'(),()0,0,(||||),(1iiiiniiiiiyxyxyxyxyxdjixx,},,,{21mxxx性质：对一切非奇异线性变换都是不变的。即，具有坐标系比例、旋转、平移不变性，并且从统计意义上尽量去掉了分量间的相关性。5.Camberra距离：该距离能克服量纲的影响，但不能克服分量间的相关性。2019/10/831马氏距离具有线性变换不变性证明：设，有非奇异线性变换：则yAx111111nnniiiiiiyyAxAxAxmmm11111()()'11()()'11()()''11[()()']''1myiiimiiimiiimiixiVyyyymAxAxAxAxmAxxxxAmAxxxxAAVAm2019/10/832故1111121112()'()()'()()''()()''(')()(,)(()'''()())),'(ijyijijyijijyijijxijijxijijxjiiyijxjyyVyyAxAxVAxAxxxAVAxxxxAAVAAxxxxAAVAAxdyydxxxVxxxx111{()}ABBA距离度量基于欧氏距离的聚类d0越小，每个聚类就越小，聚类个数就越多距离度量采用欧氏距离得到的聚类结果将不会因特征空间的平移和旋转（刚体运动）而改变，但是线性变换或其他会扭曲距离关系的变换是不能保证的。如坐标轴的缩放会导致数据点的重新分配规范化规范化（normalization）：防止某些特征因为数值过大而主导距离度量位移和缩放不变性：通过平移和缩放，使得新特征具有零均值和单位方差旋转不变性：旋转坐标轴，使得坐标轴与样本协方差矩阵的本征向量平行。这种主成分变换也可以在前面或者后面接上缩放的规范化步骤。并不能下结论说规格化一定是必要的！规范化规范化不能滥用不恰当的规范化会减少类与类之间的距离！如果数据都来自一个单一的产生过程（或伴有噪声），这种规范化方法会比较合适；如果有几个不同的产生过程，这种方法就不适合了。非度量的相似性函数更一般地，可以不用距离，而引入非度量的相似性函数来比较两个向量。相似性函数必须满足：对称性：当两个样本具有某种相似性时，函数的值较大常用的相似性函数：归一化内积（两个向量夹角的余弦）1221,,sxxsxx121212,xxsxxxx相似性测度1.角度相似系数：2.相关系数:实际上是数据中心化后的矢量夹角余弦3.指数相似系数:||||||||'),cos(yxyxyx2/1)]()')(()'[()()'(),(yyyyxxxxyyxxyxrniiiiyxnyxe122])(43exp[1),(设)',,(,)',,(2121nnyyyyxxxx（3）式中为相应分量的协方差，为矢量维数。它不受量纲变化的影响。2in当特征只有两个状态（0，1）时，常用匹配测度。0表示无此特征1表示有此特征。故称之为二值特征。对于给定的x和y中的某两个相应分量xi与yj若xi=1,yj=1，则称xi与yj是(1-1)匹配；若xi=1,yj=0，则称xi与yj是(1-0)匹配；若xi=0,yj=1，则称xi与yj是(0-1)匹配；若xi=0,yj=0，则称xi与yj是(0-0)匹配。匹配测度设为二值特征)',,(,)',,(2121nnyyyyxxxx匹配测度1.Tanimoto测度：2.Rao测度:3.Dice系数:4.Kulzinsky系数'(,)'''xysxyxxyyxy'(,)xysxyn2'(,)''xymxyxxyy(,)2xymxyxxyyxy41例设(1)Tanimoto测度(2)Rao测度(3)Dice系数(4)Kulzinsky系数(,1,0,,1,0)'(,0,011,,00,1)'1xy'3,'3,'1xxyyxy'1(,)6xysxyn2'21(,)''333xymxyxxyy'1(,)''2'4xymxyxxyyxy则'11(,)'''3315xysxyxxyyxy注意的问题没有哪个测度是最好的1，简单而易于理解2，易于实现3，满足速度要求4，考虑数据的知识选择时，可考虑以下几点无监督学习和聚类无监督学习聚类相似性度量聚类的准则函数基于迭代最优化聚类方法基于划分