PR2010_第7讲_1.ppt

C-均值算法举例 彩色图像分割： k-均值算法 1.准则函数—误差平方和准则 2.样本集初始划分 3.迭代计算 C-均值算法的其他考虑 按照与c个代表点的最小距离法对新样本y进行分类，即： 初始划分的方法 更新均值的时机：逐个样本修正法与成批样本修正法 聚类数目的动态决定 K-算法举例 例：已知有20个样本，每个样本有2个特征，数据分布如下图 样本序号 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 特征x1 0 1 0 1 2 1 2 3 6 7 特征x2 0 0 1 1 1 2 2 2 6 6 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 8 6 7 8 9 7 8 9 8 9 6 7 7 7 7 8 8 8 9 9 第一步：令K=2，选初始聚类中心为 第三步：根据新分成的两类建立新的聚类中心 第四步： ∵ 转第二步。 第二步：重新计算 到z1(2) , z2(2) 的距离，把它们归为最近聚类中心，重新分为两类， 第三步，更新聚类中心 第四步， 第二步， 第三步，更新聚类中心 上机作业 已知十个样本，每个样本2个特征，数据如下： 用K-均值算法分成3类，编程上机，并画出分类图。 样本序号 1 2 3 4 5 6 7 8 9 10 x1 0 1 2 4 5 5 6 1 1 1 x2 0 1 1 3 3 4 5 4 5 6 专题九 无监督学习和聚类 (Unsupervised learning, Clustering) 监督学习：给定已知类别的学习样本，设计分类器。 非监督学习：给定未知(未知类别及类别数)样本，设计分类器。 两大类非监督学习：基于概率密度函数估计的直接方法和基于样本间相似性(similarity)度量的间接聚类方法。 主要内容 掌握非监督学习方法的概念、用途。 了解非监督学习方法对数据划分有两种基本方法。 掌握以k-均值算法，ISODATA算法为代表的动态聚类方法。 了解层次(分级)聚类方法。 9.1 基本概念 以前讨论分类器设计方法都是在样本集中的类别已知的条件下进行的，这些样本称为训练样本。统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。 未知样本的类别，没有训练样本，因而只能从未知样本类别样本集进行分类器设计，这就是通常说的无监督学习方法。 非监督学习与有监督学习方法的区别： 有监督学习方法必须有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而非监督学习没有训练集，只有一组数据，在该组数据集内寻找规律。 有监督学习方法的目的是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号样本组成；而非监督学习方法只有分析数据集本身，无标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号为目的。 非监督学习方法在寻找数据集中的规律性，这种规律性不是划分数据集的目的，即不一定要“分类”。比如分析数据的主分量，或分析数据集的特点。 非监督学习方法分析数据集的主分量与用K-L变换计算数据集的主分量又有区别。 K-L变换不是一种学习方法，不属于非监督学习方法。 在人工神经元网络中寻找主分量的方法属于非监督学习方法。 非监督学习方法可以分成两大类： 一类为基于概率密度函数估计的直接方法：设法找到各类别在特征空间的分布参数再进行分类； 一类称为基于样本间相似性度量的间接聚类方法。其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。 9.2 基于概率密度函数估计的直接方法 该方法的关键是找出各个峰值区。 单峰子类的分离方法(称为投影法) 每个分量有无峰谷点表现出来。 利用投影，直接找密集区域。 样本在整个特征空间中呈现两个分布高峰。 如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值，这些区域被称为单峰区域。 而每个单峰区域则被看作不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为单峰子类。 投影法 对于样本在某一种度量中的分布统计，一般称为直方图统计，在样本数量很大时，又可作为概率统计的估计。 由于这种方法基于将样本投影到某个坐标轴上，因而称为投影方法。 使用投影方法有两个组成部分 一个是如何设计合适的坐标系统。 另一是如何设计直方图。 投影法 在样本属性完全不知的情况下，如何选择坐标系统比较困难的。目前还没有一个准则函数来表征这样坐标