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

第七章非监督学习方法1主要内容引言单峰子集分离方法类别分离的间接方法分级聚类方法聚类中的问题27.1引言有监督学习（supervisedlearning)：用已知类别的样本训练分类器，以求对训练集的数据达到某种最优，并能推广到对新数据的分类非监督学习（unsupervisedlearning)：样本数据类别未知，需要根据样本间的相似性对样本集进行分类(聚类，clustering)3以前讨论的分类器设计方法都是在样本集类别已知的条件下进行的，这些样本称为训练样本。统计出各类训练样本不同的描述量，如概率分布等，并利用这些参数进行分类器设计，称为有监督的学习方法。当样本的类别未知，没有训练样本，因而只能从未知样本类别样本集进行分类器设计，这就是通常说的无监督学习方法。4方案对比5非监督学习与有监督学习方法的区别有监督学习必须有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；非监督学习没有训练集，只有一组数据，在该组数据集内寻找规律。有监督学习方法的目的是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号样本组成；非监督学习方法只有分析数据集本身，无标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号为目的。6非监督学习方法可以分成两大类：基于概率密度函数估计的直接方法：设法找到各类别在特征空间的分布参数再进行分类；基于样本间相似性度量的间接聚类方法。其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。7基于概率密度函数估计的直接方法前提：无类条件概率分布先验知识思想：把特征空间分为若干个区域，每个区域上混合概率密度函数为单峰，每个单峰区域对应一个类。关键：找出各个峰值区。一维空间中的单峰分离:对样本集KN={xi}应用直方图方法估计概率密度函数，找到概率密度函数的峰以及峰之间的谷底，以谷底为阈值对数据进行分割。7.2单峰子集的分离方法8样本在整个特征空间中呈现两个分布高峰。如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值，这些区域被称为单峰区域。每个单峰区域看作一个不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为单峰子类。9（1）多维空间投影方法多维空间y中直接划分成单峰区域比较困难，把它投影到一维空间x中简化问题。10对于样本在某一种度量中的分布统计，一般称为直方图统计，在样本数量很大时，又可作为概率统计的估计。由于这种方法基于将样本投影到某个坐标轴上，因而称为投影方法。使用投影方法有两个组成部分一是如何设计合适的坐标系统。二是如何设计直方图。（1）多维空间投影方法11在样本属性完全不知的情况下，如何选择坐标系统比较困难。目前还没有一个准则函数来表征这样坐标系统的性质。一种启发式的办法是使待分类的样本在某个坐标轴方向具有最大的分散性，可采用K-L变换方法。（1）多维空间投影方法12用混合样本协方差矩阵作为K-L变换的产生矩阵，找到其特征值，并按大小排序。对应最大特征值的特征向量对此混合样本来说，离散程度最大，预期能发现明显的峰值，但是这样投影有时并不能产生多峰的边缘密度函数，因而并不能保证分出各个聚类。（1）多维空间投影方法1314（1）投影方法算法步骤计算样本y协方差矩阵的最大特征值对应的特征向量u，把样本数据投影到u上，得到v=uTy；用直方图法求边缘概率密度函数p(v)；找到边缘概率密度函数的各个谷点，在这些谷点上作垂直于u的超平面把数据划分成几个子集；如果没有谷点，则用下一个最大的特征值代替；对所得到的各个子集进行同样的过程，直至每个子集都是单峰为止。15（2）单峰子集分离的迭代算法把样本集KN={xi}分成c个不相交子集Ki。每个划分可用Parzen方法估计各类的概率密度函数：聚类准则：合理的划分应使下式最大16迭代算法步骤对数据集进行初始划分：K1,K2,…,Kc用Parzen方法估计各聚类的概率密度函数按照最大似然概率逐个对样本xk进行分类：

若没有数据点发生类别迁移变化，则停止。否则转2（2）单峰子集分离的迭代算法177.3类别分离的间接方法两个要点:相似性度量，准则函数相似性度量样本间相似性度量:特征空间的某种距离度量样本与样本聚类间相似性度量18准则函数准则函数：聚类质量的判别标准，常用的最小误差平方和准则目标:类内元素相似性高，类间元素相似性低19聚类方法按相似度进行划分的方法，原理很简单。如果把相似度表示成在特征空间中的某种距离度量,这种方法又称为基于距离度量的方法。与前一种方法相比，它不是以计算密度为依据的，这是这两种方法的主要区别。不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类，这种方法称为聚类方法。20如何聚类则取决于聚类的准则函数，以便某种聚类准则达到极值为最佳。两种聚类的方法：迭代的动态聚类算法非迭代的分级聚类算法聚类方法21动态聚类方法的任务是将数据集划分成一定数量的子集。要解决的问题:如何确定数据集应该划分的子集数目若划分数目已定，则又如何找到最佳划分。聚类方法22（1）动态聚类方法数据集可以有许多种不同的划分方法，因此需要对不同的划分作出评价，并找到优化的划分结果。由于优化过程是从“不合理的”划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。这里讨论子集数目已知条件下的聚类方法，如何确定合理的子集数目？23动态聚类方法要点选定某种距离度量作为样本间的相似性度量；确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等；确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。24K-均值算法（k-Means)对样本集KN={xi}尚不知每个样本的类别，但可假设所有样本可分为c类，各类样本在特征空间依类聚集，且近似球形分布用一代表点来表示一个聚类，如类内均值mi来代表聚类Ki聚类准则：误差平方和J25K-均值算法的训练初始化：选择c个代表点p1,p2,…,pc建立c个空聚类列表：K1,K2,…,Kc按照最小距离法则逐个对样本x进行分类：

计算J及用各聚类列表计算聚类均值，并用来作为各聚类新的代表点（更新代表点）若J不变或代表点未发生变化，则停止。否则转2。2627K-均值算法举例彩色图像分割：28K-均值算法的其他考虑按照与c个代表点的最小距离法对新样本y进行分类，即：初始划分的方法更新均值的时机：逐个样本修正法与成批样本修正法聚类数目的动态决定29ISODATA算法ISODATA算法的功能与k-均值算法相比，在下列几方面有改进。考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。算法有自我调整的能力.30ISODATA算法(迭代自组织数据分析算法）ISODATA算法与K均值算法有相似之处，即聚类中心根据样本的均值来修改。不同的是，这种算法进行的过程中聚类中心的数目不是固定不变而是反复进行修改。聚类既有合并也有分裂，合并与分裂是在一组预先选定的参数指导下进行的。此外，一些经验结果也包含在算法中。

ISODATA算法共分十四步。其中第一步到第六步是预选参数、进行初始分类，并为合并和分裂准备必要的数据；第七步决定下一步是进行合并还是进行分裂；第八步到第十步是分裂算法，第十一步到第十三步是合并算法，第十四步决定算法是否结束。算法的具体步骤如下：31ISODATA算法设有N个样本模式X1，X2，……XN.第一步：预选NC个聚类中心Z1，Z2，……ZNC,NC不要求等于希望的聚类数目。NC个聚类中心也可在N个样本中选择。然后预选下列指标：K：K是希望的聚类中心的数目。θN

：每个聚类中最少的样本数。若某聚类中的样本少θN

，则该聚类不能作为一个独立的聚类，应删去。θS

：一个聚类中样本的标准偏差参数。要求每一个聚类内标准偏差向量的所有分量中的最大分量小于θS

，否则该类应分裂为两类。标准偏差向量的每一分量等于每个样本的分量与聚类中心对应分量差的平方和平均值。θC

：两聚类中心之间的最小距离。若两类中心之间距离小于θC

，则这两类合并为一类。L：在一次迭代中允许合并的聚类中心的最大对数。I：允许迭代的次数。32第二步：把N个样本按最近邻规则分配到Nc个聚类中。第三步：若Sj中的样本数Nj<θN

，则取消该类，并且NC－1。第四步：修正各聚类中心。第五步：计算聚类Sj中各样本到该类聚类中心的平均距离，用表示：ISODATA算法33第六步：计算全部样本到其所在类聚类中心距离的平均距离。即计算全部样本的总体平均距离，用表示。第七步：判决是进行分裂还是进行合并，决定迭代步骤等。(1)如迭代已达I次，即最后一次迭代，置QC＝0，跳到第十一步。ISODATA算法34(2)若NC≤K/2(聚类中心小于或等于希望数的一半)，进入第八步，将已有的聚类分裂。(3)如果迭代的次数是偶数，或NC≥2K(聚类中心数目大于或等于希望数的两倍)，则跳到第十一步，进行合并。否则进入第八步进行分裂。第八步：计算每个聚类的标准偏差向量，第Sj类的标准偏差向量为：

式中，xij是Sj类样本X的第i个分量，zij是Zj的第i个分量。所以σij是X的第i个分量的标准差，X是n维模式向量。ISODATA算法35第九步：求每个标准差向量的最大分量，σj的最大分量记为σjmax

，j＝1,2,…,NC.第十步：在最大分量集{σjmax,j=1,2,…NC}中,如有σjmax>θS，(即Sj类样本在σjmax对应方向上的标准偏差大于允许的值），同时又满足以下两条之一：(1)和Nj>2(θN

＋1)，即类内平均距离大于总体平均距离，并且Sj类中样本数很大。(2)NC≤K/2,即聚类数小于或等于希望数目的一半。本步完成后，跳回第二步，且迭代次数加1。ISODATA算法36第十一步：计算所有聚类中心之间的距离。Si类和Sj类中心间的距离为第十二步：比较所有Dij与θC的值，将小于θC的Dij按升序排列：{Di1j1,Di2j2

,…,DiLjL}其中，Di1j1<Di2j2

<…<DiLjL

，L为允许每次合并的聚类中心的最大对数。第十三步：如将距离为Diljl的两类合并，得到新的聚类中心为：每合并一对，NC减1。ISODATA算法37第十四步：若是最后一次迭代，即迭代次数为I，算法结束；若需修改参数，则跳到第一步，然后重复上述算法。否则,跳到第二步，继续进行迭代运算。在本步运算里，迭代运算的次数加1。ISODATA算法38例：设有N=8个样本模式，它们分别为X1=[0,0]t X2=[1,1]t X3=[2,2]tX4=[3,4]t X5=[3,5]t X6=[4,4]tX7=[4,5]t X8=[5,6]t

用ISODATA算法对这些样本进行分类。第一步：选NC=1,Z1=X1=[0,0]t。各参数预选为：K＝2，θN

＝1，θS

＝1，θC

＝4，L=0,I=4.第二步：只有一个聚类中心Z1，故

S1={X1,X2,…,X8}N1=8第三步：因N1>θN故无聚类可删除。ISODATA算法39第四步：修改聚类中心，第五步：计算第六步：计算。因只有一类，故第七步：因不是最后一次迭代，且NC＝K/2，故进入第八步进行分裂运算。40第八步：求S1的标准偏差向量σ1，得

σ1=[1.99,1.56]t第九步：σ1的最大分量是1.99，因此，

σ1max＝

1.99第十步：因σ1max>

θS且NC＝K/2，可将Z1分裂为两个新的聚类中心。因σ1max是σ1的第一个分量，即S1中样本分布在X的第一个分量方向上较分散，故分裂应在Z1的第一个分量方向上进行。分裂系数k选为0.5，得41为了方便，令。这一步之后，NC加1，迭代次数加1，即下面进行第2次迭代运算。跳回到第二步。第二步：按最近邻规则对所有样本聚类，得到两个聚类分别为S1={X4,X5,X6,X7,X8}S2={X1,X2,X3}N1=5，N2=3第三步：因N1和N2都大于θN

，无聚类可以删除。第四步：修改聚类中心，得42第五步：计算和，得第六步：计算，得第七步：因这是偶数次迭代，符合第七步的第(3)条，故进入第十一步。第十一步：计算聚类之间距离，得43第十二步：比较D12与θC

，这里D12>

θC

。第十三步：根据第十二步的结果，聚类中心不能发生合并。第十四步：因为不是最后一次迭代，需要判断是否要修改给定的参数。但前面的迭代运算结果已得到希望的聚类数目；聚类之间分散程度大于类内样本的标准差；每一聚类中样本数目都具有样本总数的足够大的百分比，且两类样本数相差不大，故可不必修改参数。因此，回到第二步，且迭代次数加1。第二步到第六步：与前一次迭代运算的结果相同。第七步：没有一种情况被满足，继续执行第八步。44第八步：计算S1和S2的标准偏差向量σ1和σ2

。这时S1和S2仍为S1={X4,X5,X6,X7,X8}S2={X1,X2,X3}计算结果为：σ1=[0.75,0.75]tσ2=[0.82,0.82]t第九步：σ1max

＝0.75，σ2max

＝0.82第十步：分裂条件不满足，故继续执行第十一步。45第十一步：计算聚类中心之间的距离，结果与前次迭代计算结果相同。第十二步、十三步：与前一次迭代结果相同。第十四步：因不是最后一次迭代，且不需修改参数，故返回第二步。迭代次数加1。第二到第六步：与前一次迭代结果相同。第七步：因为是最后一次迭代，置θC

＝0，跳到第十一步。第十一步：第十二步：与前一次迭代结果相同。第十三步：没有合并发生。第十四步：最后一次迭代，故算法结束。46样本与聚类间相似性度量样本x与聚类Ki间相似性度量:聚类的表示：样本集Ki

={xj(i)}用一个所谓的“核函数”Ki，如样本集的某种统计量47样本与聚类间相似性度量基于样本与聚类间相似性度量的动态聚类算法初始化：选择c个初始聚类K1,K2,…,Kc建立c个空聚类列表：L1,L2,…,Lc按照最相似法则逐个对样本进行分类：

计算J

并用{Li}更新各聚类核函数{Ki

}若J不变则停止。否则转248正态核函数，适用于各类为正态分布参数集Vi={mi,Σi}为各类样本统计参数相似性度量：样本与聚类间相似性度量49主轴核函数：适合于各类样本集中在各自的主轴方向上的子空间里的情况。样本协方差矩阵的前dj个最大特征值对应的特征向量基样本到主轴子空间的距离：样本与聚类间相似性度量50样本和核相似性度量的聚类方法特点：可以拟合各种形状的分布；需要预先知道数据的分布形状当不能预先知道数据的分布形状时，如何处理？51（2）近邻函数准则算法近邻函数：样本间相似性的度量

如果yi是yj的第I个近邻，yj是yi的第K个近邻，记aij=I+K−2,i≠j近邻函数使得密度相近的点容易聚成一类同一类中的点之间存在“连接”。连接损失就定义为两点之间的近邻函数aij一个点和其自身的连接损失aii=2N，以惩罚只有一个点的聚类不同类的点不存在连接，连接损失aij=0总类内损失：52两类间最小近邻函数值第i类和第j类间最小近邻函数值定义为：第i类内最大连接损失记为：aimax第i类与第j类之间的连接损失定义为bij，它的设计目标是：如果两类间的最小近邻值小于或等于任何一方的类内的最大连接损失时，损失代价就是正的，从而应该考虑把这两类合并。53近邻函数准则总类间损失：准则函数：算法步骤：计算距离矩阵用距离矩阵计算近邻矩阵M计算近邻函数矩阵L在L中，每个点与其最近邻连接，形成初始的划分对每两个类计算rij

和aimax，ajmax

，只要rij

小于aimax、ajmax中的任何一个，就合并两类（建立连接）。重复至没有新的连接发生为止。547.4分级聚类方法划分序列：N个样本自底向上逐步合并一类：每个样本自成一类（划分水平1）K水平划分的进行