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

第7章 无监督学习和聚类 无监督学习和聚类 无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类 无监督学习 有监督（supervised）学习 训练集中每个样本都有一个类别标记 所有类别事先已知 常用于：分类、回归 无监督（unsupervised）学习 训练集中样本的类别标记未知 给定一组样本，发现其内在性质，如类别和聚类 常用于：聚类、概率密度估计 无监督学习的动机 收集并且标记大量模式往往花费巨大 希望首先在一个较小的有标记样本集上训练一个粗略的 分类器，然后让这个分类器以非监督的方式在一个较大 的样本集上运行 或者，用大量未标记的样本集来训练分类器，让它自动 发现数据中的分组，然后用代价更高的办法（如人工） 来标记这些分组 在很多应用中，模式的特征会随时间而变化 如果这种特征的变化能够被某种运行在无监督方式下的 分类器捕捉到，那么分类性能将得到大幅提高 无监督学习的动机 无监督方法可以用来提取特征，或者预处理现存特征，从而为后续的模式识别问题做准备 例如：PCA降维 在任何探索性的工作中，无监督方法可以揭示观测数据的一些内部结构和规律 发现模式中内在的聚类或分组可能为分类器设计提供依据 无监督学习和聚类 无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类 聚类 聚类（clustering） 聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程 因为训练集样本并无类别标记，所以聚类是无监督学习 过程 一个聚类（cluster）是指一组样本，它们与属于同一聚类的样本相似，而与属于其他聚类的样本不相似 聚类可用作 一种独立的数据分析工具，用于分析数据的内在特性 一种数据预处理方法，为后续模式识别服务 无监督学习和聚类 无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类 相似性度量 “同一聚类内部的样本之间比不同聚类的样本之间更相似”是聚类的基本假设。 相似性度量：基于某种定义，描述样本间相似（或不相似）程度的度量 几种主要的相似性（不相似性）度量 基于度量的距离标准 非度量的相似性函数 匹配测度 距离度量 一个距离度量（即距离函数）需满足： 非负性： 自反性： 对称性： 三角不等式： 距离度量 常用的距离度量 最为常用的距离度量为欧氏距离 其次为考虑数据分布的马氏距离 点对称距离 流形距离 …… 距离度量 根据距离对样本进行聚类 计算任意两个样本之间的距离 如果两个样本之间的距离小于某个阈值d0 ，那么这两个样本就属于同一个聚类 d0过大，所有样本都被分为同一个聚类 d0过小，每个样本都自成一个聚类 距离度量 基于欧氏距离的聚类 距离度量 采用欧氏距离得到的聚类结果将不会因特征空间的平移和旋转（刚体运动）而改变，但是线性变换或其他会扭曲距离关系的变换是不能保证的。 如坐标轴的缩放会导致数据点的重新分配 规范化 规范化（normalization）：防止某些特征因为数值过大而主导距离度量 位移和缩放不变性：通过平移和缩放，使得新特征具有零均值和单位方差 旋转不变性：旋转坐标轴，使得坐标轴与样本协方差矩阵的本征向量平行。这种主成分变换也可以在前面或者后面接上缩放的规范化步骤。 并不能下结论说规格化一定是必要的！ 规范化 规范化不能滥用 非度量的相似性函数 更一般地，可以不用距离，而引入非度量的相似性函数来比较两个向量。 相似性函数必须满足： 对称性： 当两个样本具有某种相似性时，函数的值较大 常用的相似性函数：归一化内积（两个向量夹角的余弦） 无监督学习和聚类 无监督学习 聚类 相似性度量 聚类的准则函数 基于迭代最优化聚类方法 基于划分的聚类方法 层次聚类 聚类的准则函数 何谓好的聚类？聚类内部相似度高，聚类之间相似度低 聚类结果的质量取决于采用的相似度度量以及聚类算法的具体实现 评价聚类结果的好坏往往具有主观性！ 聚类的准则函数 聚类的准则函数：判断“一种聚类的划分比另一种划分好”的依据，采用不同的准则函数可能得到不同的聚类结果。 聚类问题可以看做一种离散优化问题 准则函数用于度量对数据聚类的某种划分的质量 目标是找到某种划分，使得准则函数最小（大）化 常用准则函数 误差平方和准则 最小方差准则 散布准则 聚类的准则函数 误差平方和准则 是最简单也使用最广的聚类准则函数 聚类的准则函数 采用误差平方和准则可能存在的问题 当不同聚类所包含的样本个数相差较大时，将一个大的聚类分割开来反而可能得到更小的误差平方和 聚类的准则函数 最小方差准则：经过简单的代数操作，将误差平方和准则函数Je的表达式中去掉均值向量，得到一个等价的表