模式识别第七章 非监督分类

1第七章非监督学习方法2主要内容引言单峰子集分离方法类别分离的间接方法分级聚类方法聚类中的问题37.1引言有监督学习（supervisedlearning)：用已知类别的样本训练分类器，以求对训练集的数据达到某种最优，并能推广到对新数据的分类􀂄非监督学习（unsupervisedlearning)：样本数据类别未知，需要根据样本间的相似性对样本集进行分类(聚类，clustering)􀂄4以前讨论的分类器设计方法都是在样本集类别已知的条件下进行的，这些样本称为训练样本。统计出各类训练样本不同的描述量，如概率分布等，并利用这些参数进行分类器设计，称为有监督的学习方法。当样本的类别未知，没有训练样本，因而只能从未知样本类别样本集进行分类器设计，这就是通常说的无监督学习方法。5方案对比6非监督学习与有监督学习方法的区别有监督学习必须有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；非监督学习没有训练集，只有一组数据，在该组数据集内寻找规律。有监督学习方法的目的是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号样本组成；非监督学习方法只有分析数据集本身，无标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号为目的。7非监督学习方法可以分成两大类：基于概率密度函数估计的直接方法：设法找到各类别在特征空间的分布参数再进行分类；基于样本间相似性度量的间接聚类方法。其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。8基于概率密度函数估计的直接方法前提：无类条件概率分布先验知识思想：把特征空间分为若干个区域，每个区域上混合概率密度函数为单峰，每个单峰区域对应一个类。关键：找出各个峰值区。一维空间中的单峰分离:对样本集KN={xi}应用直方图方法估计概率密度函数，找到概率密度函数的峰以及峰之间的谷底，以谷底为阈值对数据进行分割。7.2单峰子集的分离方法9样本在整个特征空间中呈现两个分布高峰。如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值，这些区域被称为单峰区域。每个单峰区域看作一个不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为单峰子类。10（1）多维空间投影方法多维空间y中直接划分成单峰区域比较困难，把它投影到一维空间x中简化问题。11对于样本在某一种度量中的分布统计，一般称为直方图统计，在样本数量很大时，又可作为概率统计的估计。由于这种方法基于将样本投影到某个坐标轴上，因而称为投影方法。使用投影方法有两个组成部分一是如何设计合适的坐标系统。二是如何设计直方图。（1）多维空间投影方法12在样本属性完全不知的情况下，如何选择坐标系统比较困难。目前还没有一个准则函数来表征这样坐标系统的性质。一种启发式的办法是使待分类的样本在某个坐标轴方向具有最大的分散性，可采用K-L变换方法。（1）多维空间投影方法13用混合样本协方差矩阵作为K-L变换的产生矩阵，找到其特征值，并按大小排序。对应最大特征值的特征向量对此混合样本来说，离散程度最大，预期能发现明显的峰值，但是这样投影有时并不能产生多峰的边缘密度函数，因而并不能保证分出各个聚类。（1）多维空间投影方法1415（1）投影方法算法步骤1.计算样本y协方差矩阵的最大特征值对应的特征向量u，把样本数据投影到u上，得到v=uTy；2.用直方图法求边缘概率密度函数p(v)；3.找到边缘概率密度函数的各个谷点，在这些谷点上作垂直于u的超平面把数据划分成几个子集；4.如果没有谷点，则用下一个最大的特征值代替；5.对所得到的各个子集进行同样的过程，直至每个子集都是单峰为止。16（2）单峰子集分离的迭代算法把样本集KN={xi}分成c个不相交子集Ki。每个划分可用Parzen方法估计各类的概率密度函数：211[(|)(|)]()ccijijJfKfKpdxxxx聚类准则：合理的划分应使下式最大1(|)(,)iiiKfKKNxxxx17迭代算法步骤对数据集进行初始划分：K1,K2,…,Kc用Parzen方法估计各聚类的概率密度函数按照最大似然概率逐个对样本xk进行分类：若没有数据点发生类别迁移变化，则停止。否则转2argmax(|),kikjijfKKxx（2）单峰子集分离的迭代算法187.3类别分离的间接方法两个要点:相似性度量，准则函数相似性度量样本间相似性度量:特征空间的某种距离度量样本与样本聚类间相似性度量􀂄(,)ijKx(,)()()Tijijijxxxxxx19准则函数准则函数：聚类质量的判别标准，常用的最小误差平方和准则􀂄1(,)iciiKJyym目标:类内元素相似性高，类间元素相似性低20聚类方法按相似度进行划分的方法，原理很简单。如果把相似度表示成在特征空间中的某种距离度量,这种方法又称为基于距离度量的方法。与前一种方法相比，它不是以计算密度为依据的，这是这两种方法的主要区别。不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类，这种方法称为聚类方法。21如何聚类则取决于聚类的准则函数，以便某种聚类准则达到极值为最佳。两种聚类的方法：迭代的动态聚类算法非迭代的分级聚类算法聚类方法22动态聚类方法的任务是将数据集划分成一定数量的子集。要解决的问题:如何确定数据集应该划分的子集数目若划分数目已定，则又如何找到最佳划分。聚类方法23（1）动态聚类方法数据集可以有许多种不同的划分方法，因此需要对不同的划分作出评价，并找到优化的划分结果。由于优化过程是从“不合理的”划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。这里讨论子集数目已知条件下的聚类方法，如何确定合理的子集数目？24动态聚类方法要点选定某种距离度量作为样本间的相似性度量；确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等；确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。25K-均值算法（k-Means)对样本集KN={xi}尚不知每个样本的类别，但可假设所有样本可分为c类，各类样本在特征空间依类聚集，且近似球形分布用一代表点来表示一个聚类，如类内均值mi来代表聚类Ki聚类准则：误差平方和J11(,)()()iiccTiiiiKiKJxxxmxmxm26K-均值算法的训练1.初始化：选择c个代表点p1,p2,…,pc2.建立c个空聚类列表：K1,K2,…,Kc3.按照最小距离法则逐个对样本x进行分类：4.计算J及用各聚类列表计算聚类均值，并用来作为各聚类新的代表点（更新代表点）5.若J不变或代表点未发生变化，则停止。否则转2。argmin(,),add(,)ijijKxpx1(,)iciiKJxxp27K-means聚类算法流程图与前i-1个中心比较，距离满足预定的值则认为是同一个中心，要再次随机取样判断，随机取样的次数预定为不超过一幅多通道图像像素点数的2倍初始化类个数i循环i次随机取一个像素点作为一个类的中心这个中心唯一吗？YesNo类中心已满吗？NoYes返回是否稳定?分类更新类中心按像素所在的类修改像素值YesNo初始化类中心结束内部类MeanElement基于像素（数组）统计类内像素，计算各类所有样本即像素的算术平均值类别灰度值第1类：1第2类：2第3类：3第4类：4…第i类：i（第1类中心-新的中心）距离+（第2类中心-新的中心）距离+…0.0001根据距离最小的准则，把所有像素分配到相应的类28K-均值算法举例彩色图像分割：29K-均值算法的其他考虑按照与c个代表点的最小距离法对新样本y进行分类，即：初始划分的方法更新均值的时机：逐个样本修正法与成批样本修正法聚类数目的动态决定argmin(,),ijijypy30ISODATA算法ISODATA算法的功能与k-均值算法相比，在下列几方面有改进。考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。算法有自我调整的能力.31ISODATA算法(迭代自组织数据分析算法）ISODATA算法与K均值算法有相似之处，即聚类中心根据样本的均值来修改。不同的是，这种算法进行的过程中聚类中心的数目不是固定不变而是反复进行修改。聚类既有合并也有分裂，合并与分裂是在一组预先选定的参数指导下进行的。此外，一些经验结果也包含在算法中。ISODATA算法共分十四步。其中第一步到第六步是预选参数、进行初始分类，并为合并和分裂准备必要的数据；第七步决定下一步是进行合并还是进行分裂；第八步到第十步是分裂算法，第十一步到第十三步是合并算法，第十四步决定算法是否结束。算法的具体步骤如下：32ISODATA算法设有N个样本模式X1，X2，……XN.第一步：预选NC个聚类中心Z1，Z2，……ZNC,NC不要求等于希望的聚类数目。NC个聚类中心也可在N个样本中选择。然后预选下列指标：K：K是希望的聚类中心的数目。θN：每个聚类中最少的样本数。若某聚类中的样本少θN，则该聚类不能作为一个独立的聚类，应删去。θS：一个聚类中样本的标准偏差参数。要求每一个聚类内标准偏差向量的所有分量中的最大分量小于θS，否则该类应分裂为两类。标准偏差向量的每一分量等于每个样本的分量与聚类中心对应分量差的平方和平均值。θC：两聚类中心之间的最小距离。若两类中心之间距离小于θC，则这两类合并为一类。L：在一次迭代中允许合并的聚类中心的最大对数。I：允许迭代的次数。33第二步：把N个样本按最近邻规则分配到Nc个聚类中。第三步：若Sj中的样本数NjθN，则取消该类，并且NC－1。第四步：修正各聚类中心。第五步：计算聚类Sj中各样本到该类聚类中心的平均距离，用表示：jCijSXNiZXZX则若},....2,1,min{jDCSXjjNjXNZj,.....2,1,1其中ISODATA算法34第六步：计算全部样本到其所在类聚类中心距离的平均距离。即计算全部样本的总体平均距离，用表示。第七步：判决是进行分裂还是进行合并，决定迭代步骤等。(1)如迭代已达I次，即最后一次迭代，置QC＝0，跳到第十一步。是类内平均距离。其中jCSXjjjDNjZXNDj,....2,1,1DCCjNjjjNjSXjDNNZXND1111ISODATA算法35(2)若NC≤K/2(聚类中心小于或等于希望数的一半)，进入第八步，将已有的聚类分裂。(3)如果迭代的次数是偶数，或NC≥2K(聚类中心数目大于或等于希望数的两倍)，则跳到第十一步，进行合并。否则进入第八步进行分裂。第八步：计算每个聚类的标准偏差向量，第Sj类的标准偏差向量为：式中，xij是Sj类样本X的第i个分量，zij是Zj的第i个分量。所以σij是X的第i个分量的标准差，X是n维模式向量。CSXijijjijtnjjjjNjnizxNj,....,2,1.,...2,1)(1],...,,[221ISODATA算法36第九步：求每个标准差向量的最大分量，σj的最大分量记为σjmax，j＝1,2,…,NC.第十步：在最大分量集{σjmax,j=1,2,…NC}中,如有σjmaxθS，(即Sj类样本在σjmax对应方向上的标准偏差大于允许的值），同时又满足以下两条之一：(1)和Nj2(θN＋1)，即类内平均距离大于总体平均距离，并且Sj类中样本数很大。(2)NC≤K/2,即聚类数小于或等于希望数目的一半。本步完成后，跳回第二步，且迭代次数加1。DDj。的分量减去中对应这样构成：的分量加上；中对应这样