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

《第7章-无监督学习和聚类》由会员分享，可在线阅读，更多相关《第7章-无监督学习和聚类（114页珍藏版）》请在金锄头文库上搜索。

1、第7章 无监督学习和聚类,无监督学习和聚类,无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类,无监督学习,有监督（supervised）学习 训练集中每个样本都有一个类别标记 所有类别事先已知 常用于：分类、回归 无监督（unsupervised）学习 训练集中样本的类别标记未知 给定一组样本，发现其内在性质，如类别和聚类 常用于：聚类、概率密度估计,无监督学习的动机,收集并且标记大量模式往往花费巨大 希望首先在一个较小的有标记样本集上训练一个粗略的 分类器，然后让这个分类器以非监督的方式在一个较大 的样本集上运行 或者，用大量未标记的样本集来

2、训练分类器，让它自动 发现数据中的分组，然后用代价更高的办法（如人工） 来标记这些分组 在很多应用中，模式的特征会随时间而变化 如果这种特征的变化能够被某种运行在无监督方式下的 分类器捕捉到，那么分类性能将得到大幅提高,无监督学习的动机,无监督方法可以用来提取特征，或者预处理现存特征，从而为后续的模式识别问题做准备 例如：PCA降维 在任何探索性的工作中，无监督方法可以揭示观测数据的一些内部结构和规律 发现模式中内在的聚类或分组可能为分类器设计提供依据,无监督学习与有监督学习方法的区别：,有监督学习方法必须有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而无监督学习没有训练集，

3、只有一组数据，在该组数据集内寻找规律。 有监督学习方法的目的是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号样本组成；而无监督学习方法只有分析数据集本身，无标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号为目的。,无监督学习方法在寻找数据集中的规律性，这种规律性不是划分数据集的目的，即不一定要“分类”。比如分析数据的主分量，或分析数据集的特点。 无监督学习方法分析数据集的主分量与用K-L变换计算数据集的主分量又有区别。 K-L变换不是一种学习方法，不属于无监督学习方法。,无监督学习方法可以分成两大类： 一类为基于概率密度函数估

4、计的直接方法：设法找到各类别在特征空间的分布参数再进行分类； 一类称为基于样本间相似性度量的间接聚类方法。其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。,基于概率密度函数估计的直接方法,该方法的关键是找出各个峰值区。 单峰子类的分离方法(称为投影法) 每个分量有无峰谷点表现出来。 利用投影，直接找密集区域。,样本在整个特征空间中呈现两个分布高峰。 如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值，这些区域被称为单峰区域。 而每个单峰区域则被看作不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为

5、单峰子类。,投影法,对于样本在某一种度量中的分布统计，一般称为直方图统计，在样本数量很大时，又可作为概率统计的估计。 由于这种方法基于将样本投影到某个坐标轴上，因而称为投影方法。 使用投影方法有两个组成部分 一个是如何设计合适的坐标系统。 另一是如何设计直方图。,投影法,在样本属性完全不知的情况下，如何选择坐标系统比较困难的。目前还没有一个准则函数来表征这样坐标系统的性质。 一种启发式的办法是使待分类的样本在某个坐标轴方向具有最大的分散性，采用前面讨论过的K-L变换方法。,投影法,用混合样本协方差矩阵作为K-L变换的产生矩阵，找到其特征值，并按大小排序。 对应最大特征值的特征向量对此混合样本来

6、说，离散程度最大，预期能发现明显的峰值，但是这种方法并不能保证分出各个聚类。,【投影方法】,基本步骤,问题：这样投影有时并不能产生多峰的边缘密度函数 -方差最大的准则有时并不一定最有利于聚类。,【存在问题】,失败的例子,【回顾】,直接方法： 1. 估计概率密度函数 困难 2. 寻找密度函数中的单峰 间接方法：考查样本这间的相似性，根据相似性把样本集划分为若干子集，使某种表示聚类质量的准则函数最优。,不同的聚类方法实际上反映了对聚类的不同理解： 混合模型：数据服从混合分布，聚类对应于各分布 单峰子集：聚类即概率分布中的单峰，即样本分布相对集中的区域 间接方法：相似的样本聚类，不同聚类的样本不相似

7、,无监督学习和聚类,无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类,聚类,聚类（clustering） 聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程 因为训练集样本并无类别标记，所以聚类是无监督学习 过程 一个聚类（cluster）是指一组样本，它们与属于同一聚类的样本相似，而与属于其他聚类的样本不相似 聚类可用作 一种独立的数据分析工具，用于分析数据的内在特性 一种数据预处理方法，为后续模式识别服务,20,取决于分类算法和特征点分布情况的匹配。,注意：聚类方法的有效性,分类无效时的情况 1.特征选取不当使分类无效

8、。,21,分类无效时的情况 2.特征选取不足可能使不同类别的模式判为一类。,取决于分类算法和特征点分布情况的匹配。,注意：聚类方法的有效性,22,分类无效时的情况 3.特征选取过多可能无益反而有害,增加分析负担并使分析效果变差。,取决于分类算法和特征点分布情况的匹配。,注意：聚类方法的有效性,23,量纲不同对聚类的影响,分类无效时的情况 4.量纲选取不当。,无监督学习和聚类,无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类,相似性度量,“同一聚类内部的样本之间比不同聚类的样本之间更相似”是聚类的基本假设。 相似性度量：基于某种定义，描述样本间相

9、似（或不相似）程度的度量 几种主要的相似性（不相似性）度量 基于度量的距离标准 非度量的相似性函数 匹配测度,距离度量,一个距离度量（即距离函数）需满足： 非负性： 自反性： 对称性： 三角不等式：,距离度量,常用的距离度量 最为常用的距离度量为欧氏距离 其次为考虑数据分布的马氏距离 点对称距离 流形距离 ,距离度量,根据距离对样本进行聚类 计算任意两个样本之间的距离 如果两个样本之间的距离小于某个阈值d0 ，那么这两个样本就属于同一个聚类 d0过大，所有样本都被分为同一个聚类 d0过小，每个样本都自成一个聚类,距离度量,2019/9/26,29,欧氏(Euclidean)距离： 2. 绝对值

10、距离(街区距离，Manhattan距离)： 3. 切氏(Chebyshev)距离: 4. 明氏(Minkowski)距离:,设,6. 马氏(Mahalanobis)距离: 设n维矢量 是矢量集 中的两个矢量,性质：对一切非奇异线性变换都是不变的。 即，具有坐标系比例、旋转、平移不变性， 并且从统计意义上尽量去掉了分量间的相关性。,5. Camberra距离：,该距离能克服量纲的影响， 但不能克服分量间的相关性。,2019/9/26,31,马氏距离具有线性变换不变性,证明：设，有非奇异线性变换： 则,2019/9/26,32,故,距离度量,基于欧氏距离的聚类,d0越小，每个聚类就越小，聚类个数就

11、越多,距离度量,采用欧氏距离得到的聚类结果将不会因特征空间的平移和旋转（刚体运动）而改变，但是线性变换或其他会扭曲距离关系的变换是不能保证的。 如坐标轴的缩放会导致数据点的重新分配,规范化,规范化（normalization）：防止某些特征因为数值过大而主导距离度量 位移和缩放不变性：通过平移和缩放，使得新特征具有零均值和单位方差 旋转不变性：旋转坐标轴，使得坐标轴与样本协方差矩阵的本征向量平行。这种主成分变换也可以在前面或者后面接上缩放的规范化步骤。 并不能下结论说规格化一定是必要的！,规范化,规范化不能滥用,不恰当的规范化会减少类与类之间的距离！如果数据都来自一个单一的产生过程（或伴有噪声

12、），这种规范化方法会比较合适；如果有几个不同的产生过程，这种方法就不适合了。,非度量的相似性函数,更一般地，可以不用距离，而引入非度量的相似性函数来比较两个向量。 相似性函数必须满足： 对称性： 当两个样本具有某种相似性时，函数的值较大 常用的相似性函数：归一化内积（两个向量夹角的余弦）,相似性测度,1. 角度相似系数： 2. 相关系数:实际上是数据中心化后的矢量夹角余弦 3. 指数相似系数:,设,（3）式中 为相应分量的协方差， 为矢量维数。它不受量纲变化的影响。,当特征只有两个状态（0，1）时，常用匹配测度。 0表示无此特征 1表示有此特征。故称之为二值特征。 对于给定的x和y中的某两个相

13、应分量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)匹配。,匹配测度,设 为二值特征,匹配测度,1. Tanimoto测度： 2. Rao测度: 3. Dice系数: 4. Kulzinsky系数,41,例,设 (1) Tanimoto测度 (2) Rao测度 (3) Dice系数 (4) Kulzinsky系数,则,注意的问题,没有哪个测度是最好的,1，简单而易于理解 2，易于实现 3，满

14、足速度要求 4，考虑数据的知识,选择时，可考虑以下几点,无监督学习和聚类,无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类,聚类的准则函数,何谓好的聚类？聚类内部相似度高，聚类之间相似度低 聚类结果的质量取决于采用的相似度度量以及聚类算法的具体实现 评价聚类结果的好坏往往具有主观性！,聚类的准则函数,聚类的准则函数：判断“一种聚类的划分比另一种划分好”的依据，采用不同的准则函数可能得到不同的聚类结果。 聚类问题可以看做一种离散优化问题 准则函数用于度量对数据聚类的某种划分的质量 目标是找到某种划分，使得准则函数最小（大）化 常用准则函数 误差平

15、方和准则 最小方差准则 散布准则,聚类的准则函数,误差平方和准则 是最简单也使用最广的聚类准则函数,其中，mi是第 i 个聚类 Di 中样本的均值,当数据点能被划分成很好的相互区分的几个聚类 ，并且聚类内部又很稠密时，适用误差平方和准则,聚类的准则函数,采用误差平方和准则可能存在的问题 当不同聚类所包含的样本个数相差较大时，将一个大的聚类分割开来反而可能得到更小的误差平方和,聚类的准则函数,最小方差准则：经过简单的代数操作，将误差平方和准则函数Je的表达式中去掉均值向量，得到一个等价的表达形式,ni: 第i类中样本的个数,第i类中样本两两之间距离平方的均值,聚类的准则函数,最小方差准则的一般形

16、式,或,为某种相似性函数,聚类的准则函数,散布准则 均值向量 第i个聚类的均值向量 总的均值向量,聚类的准则函数,散布矩阵 第i类的散布矩阵 类内散布矩阵 类间散布矩阵 总体散布矩阵,聚类的准则函数,为了得到更好的聚类质量，我们希望得到较小的类内散布和较大的类间散布。 需要某种标量度量矩阵的“大小”。如矩阵的迹：即矩阵对角线上元素之和。,与误差平方和准则等价,无监督学习和聚类,无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类,基于迭代最优化聚类方法,对一个有限样本集来说，可能的划分的个数是有限的，理论上可以用穷举法找到最优解。然而，穷举法因计算量过大而往往无法实现。 迭代最优化方法经常用于寻求最优划分 首先开始于一些合理的初始划分 然后将某些样本从一个聚类移动到另一个聚类如果 这样做能够改善准则函数的话 重复迭代直到没有显著改善时停止,无监督学习和聚类,无监督学习 聚类