八PR2010_第7讲_1.ppt

C-均值算法举例 彩色图像分割： k-均值算法 1.准则函数—误差平方和准则 2.样本集初始划分 3.迭代计算 C-均值算法的其他考虑 按照与c个代表点的最小距离法对新样本y进行分类，即： 初始划分的方法 更新均值的时机：逐个样本修正法与成批样本修正法 聚类数目的动态决定 专题九 无监督学习和聚类 (Unsupervised learning, Clustering) 监督学习：给定已知类别的学习样本，设计分类器。 非监督学习：给定未知(未知类别及类别数)样本，设计分类器。 两大类非监督学习：基于概率密度函数估计的直接方法和基于样本间相似性(similarity)度量的间接聚类方法。 主要内容 掌握非监督学习方法的概念、用途。 了解非监督学习方法对数据划分有两种基本方法。 掌握以k-均值算法，ISODATA算法为代表的动态聚类方法。 了解层次(分级)聚类方法。 9.1 基本概念 以前讨论分类器设计方法都是在样本集中的类别已知的条件下进行的，这些样本称为训练样本。统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。 未知样本的类别，没有训练样本，因而只能从未知样本类别样本集进行分类器设计，这就是通常说的无监督学习方法。 非监督学习与有监督学习方法的区别： 有监督学习方法必须有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而非监督学习没有训练集，只有一组数据，在该组数据集内寻找规律。 有监督学习方法的目的是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号样本组成；而非监督学习方法只有分析数据集本身，无标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号为目的。 非监督学习方法在寻找数据集中的规律性，这种规律性不是划分数据集的目的，即不一定要“分类”。比如分析数据的主分量，或分析数据集的特点。 非监督学习方法分析数据集的主分量与用K-L变换计算数据集的主分量又有区别。 K-L变换不是一种学习方法，不属于非监督学习方法。 在人工神经元网络中寻找主分量的方法属于非监督学习方法。 非监督学习方法可以分成两大类： 一类为基于概率密度函数估计的直接方法：设法找到各类别在特征空间的分布参数再进行分类； 一类称为基于样本间相似性度量的间接聚类方法。其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。 9.2 基于概率密度函数估计的直接方法 该方法的关键是找出各个峰值区。 单峰子类的分离方法(称为投影法) 每个分量有无峰谷点表现出来。 利用投影，直接找密集区域。 样本在整个特征空间中呈现两个分布高峰。 如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值，这些区域被称为单峰区域。 而每个单峰区域则被看作不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为单峰子类。 投影法 对于样本在某一种度量中的分布统计，一般称为直方图统计，在样本数量很大时，又可作为概率统计的估计。 由于这种方法基于将样本投影到某个坐标轴上，因而称为投影方法。 使用投影方法有两个组成部分 一个是如何设计合适的坐标系统。 另一是如何设计直方图。 投影法 在样本属性完全不知的情况下，如何选择坐标系统比较困难的。目前还没有一个准则函数来表征这样坐标系统的性质。 一种启发式的办法是使待分类的样本在某个坐标轴方向具有最大的分散性，采用上一章讨论过的K-L变换方法。 投影法 用混合样本协方差矩阵作为K-L变换的产生矩阵，找到其特征值，并按大小排序。 对应最大特征值的特征向量对此混合样本来说，离散程度最大，预期能发现明显的峰值，但是这种方法并不能保证分出各个聚类。 投影法算法步骤： 计算样本协方差矩阵具有最大特征值的特征向量uj，把数据投影到 uj轴上。 用直方图方法求数据的边缘概率密度函数。 在直方图的峰值间求最小值，在这些最小点作垂直于uj的各个超平面把数据划分为若干个聚类。 如果在轴上没有这样的最小值，则用下一个最大特征值对应的特征向量重复以上过程。 对每个得到的子集(聚类)重复上述过程，直到每个集不能再分(为单峰)为止。 灰度图像二值化算法 灰度图像阈值: 单峰子集分离的迭代算法 把样本集KN={xi}分成c个不相交子集Ki。用这样的一个划分可用Parzen方法估计各类的概率密度函数： 聚类准则：即理想的划分应使下式最大 迭代算法步骤 对数据集进行初始划分：K1, K2, …,Kc 用Parzen方法估计各聚类的概率密度函数 按照最大似然概率逐个对样本xk进行分类： 若没有数据点发生类别迁移变化，则停止。否则转