模式识别课件(总顺序 No12)(第八章 NO1)

1、第八章第八章 非监督学习与聚类方法非监督学习与聚类方法8.1 8.1 引言引言 统计模式识别统计模式识别依学习与否依学习与否可分成可分成两类两类：1) 1) 监督学习分类监督学习分类:（如前所述）是在如前所述）是在已知类别已知类别标签的样本集标签的样本集的基础上进行分类（即已知类条件概率密度下的分类）。的基础上进行分类（即已知类条件概率密度下的分类）。2 2）非非/无监督学习分类：无监督学习分类：不知类别不知类别标签的样本集下进行分类标签的样本集下进行分类（即不知类条件概率密度下的分类）。（即不知类条件概率密度下的分类）。 非监督学习方法又可分为两大类：非监督学习方法又可分为两大类：1 1）基

2、于基于概率密度函数估计概率密度函数估计的直接方法的直接方法2）基于样本间相似性度量样本间相似性度量的间接聚类方法 即按照样本间的相似性样本间的相似性（常用距离距离来表示两样本间的相似度）把集合划分成若干个子集，划分的结果应使某种表示聚类质量的准则函数为最大聚类质量的准则函数为最大。 聚类方法：聚类方法：就是将同一个聚合类的模式比不同聚合类中模式更相近。其原理就是在没有先验知识没有先验知识的情况下，基于“物以类聚物以类聚”观点，用数学方法分析各模式向量之间各模式向量之间的距离及分散情况的距离及分散情况，按照样本的距离远近划分类别样本的距离远近划分类别即属于非监督学习。l聚类分类的结果可用来聚类分

3、类的结果可用来对数据提出初始假设对数据提出初始假设，对新数，对新数据分类，据分类，测试数据的同类性及压缩数据测试数据的同类性及压缩数据。l由于数据集的复杂性，所以由于数据集的复杂性，所以目前还没有通用的聚类方目前还没有通用的聚类方法来识别所有这些结构法来识别所有这些结构。即每个新的聚类算法对特殊。即每个新的聚类算法对特殊的数据结构比已有的算法会显得更有效。的数据结构比已有的算法会显得更有效。l聚类分析与聚类分析与样本模式向量的分布形式密切相关样本模式向量的分布形式密切相关。l聚类算法的聚类算法的重点是寻找特定形状的聚合类重点是寻找特定形状的聚合类。l聚类分析中，由于可聚类分析中，由于可获得的信

4、息甚少，获得的信息甚少，即没有关于类即没有关于类 别数目的任何知识，所以别数目的任何知识，所以需要有一个好的数据结构需要有一个好的数据结构，而，而数据结构的组织数据结构的组织依赖于数据的格式、大小和形状依赖于数据的格式、大小和形状等，等，常常用的数据结构有用的数据结构有： 模式向量：模式向量： 模式矩阵：模式矩阵：pn矩阵，由模式向量构成，其矩阵，由模式向量构成，其行行表示表示模式模式，列列表示表示特征特征（特征可看作是一级（特征可看作是一级正交的轴正交的轴，而模，而模式可看作式可看作n维空间（特征空间）中的点维空间（特征空间）中的点） 逼近度矩阵：逼近度矩阵：pp矩阵，其矩阵，其行列行列均代

5、表均代表模式模式，而，而 矩阵的元素矩阵的元素表示对应行列的表示对应行列的一对模式之间的近似度一对模式之间的近似度（相（相似性）。逼近度矩阵常由模式似性）。逼近度矩阵常由模式使用欧氏距离方法使用欧氏距离方法来求得来求得（要用到分级技术）。（要用到分级技术）。l聚类的定义有三种：聚类的定义有三种： 1 1）聚类是那些聚类是那些相似的实体的集合相似的实体的集合，而且，而且不同的聚类内的不同的聚类内的实体是不相似的实体是不相似的； 2 2）特征空间中点的聚合特征空间中点的聚合。即在一个聚类内的。即在一个聚类内的两个点间的两个点间的距离距离小于小于在这个类内的在这个类内的任意一点和不在这个类内的另任意

6、一点和不在这个类内的另一一任意点的距离任意点的距离。 3 3）可被描述成可被描述成n维空间内这样连接的区域，包含维空间内这样连接的区域，包含较高密较高密度点的区域度点的区域通过包含通过包含较低密度点的区域较低密度点的区域与与其它较高密度其它较高密度点的区域相分点的区域相分。 总之，聚类方法就是把总之，聚类方法就是把两个最接近的模式放于同一聚两个最接近的模式放于同一聚类内类内。 8.2 模式相似性测度模式相似性测度 为了能将模式集为了能将模式集划分成不同的类别划分成不同的类别，需定义一种，需定义一种相似性的测度相似性的测度来度量来度量同一类样本间的同一类样本间的类似性类似性和和不同不同样本间的样

7、本间的差异性差异性。常用有：。常用有： 1 1）欧氏距离欧氏距离 Tn21212222211z,.,z ,z Z, ,.,)(.)()(TnnnxxxXzxzxzxZXD样本 2 2）马氏（）马氏（MahalanobisMahalanobis）距离）距离 注：马氏距离的使用难点在于：注：马氏距离的使用难点在于： 难以得到难以得到。 3 3）明氏（）明氏（MinkowskiMinkowski）距离）距离 式中：式中：X、Z为样本向量；为样本向量；xk和和zk分别为分别为X和和Z的第的第k个分个分量；量； m为正整数。为正整数。为其协方差阵。为其均值，向量为特征向量，式中：MXMXMXDT)()(

8、 12 mkmkkzxZXD1),( 4 4）角度相似性函数）角度相似性函数 即为模式向量即为模式向量X和和Z之间夹角的余弦。之间夹角的余弦。注：注： 这几种测度都涉及把两个比较的向量这几种测度都涉及把两个比较的向量X和和Z的分量值的分量值 组合起来，也就是说，对于具体的模式分类，需视情况选择组合起来，也就是说，对于具体的模式分类，需视情况选择适当的组方法。适当的组方法。 不同的测度度量可能导致对同样数据的不同划分。不同的测度度量可能导致对同样数据的不同划分。ZXZXZXST),(8.3 8.3 聚类准则聚类准则 有了相似性测度，就能有了相似性测度，就能聚类相似的模式样本聚类相似的模式样本，而

9、，而要剔出相异的样本，就需有数值描述的要剔出相异的样本，就需有数值描述的聚类准则聚类准则。 聚类是将样本进行组合分类以使类别分离性为最聚类是将样本进行组合分类以使类别分离性为最大大，而类别是由若干个样本组成。，而类别是由若干个样本组成。聚类准则应是反映聚类准则应是反映类别间相似性或分离性的函数且与样本类别间相似性或分离性的函数且与样本X和类别有关和类别有关，所以其所以其一般定义一般定义为：为： J=f(X,i) i=1,2,c式中：式中：X为样本，为样本，i为分类类别。为分类类别。 误差平方和准则误差平方和准则 式中：式中：c为聚类类别数目为聚类类别数目， 为为属于属于i类的样本均类的样本均值

10、向量值向量，Ni为为i中样本的数中样本的数目目。注：注：1) 即即Je是是i类中各样本类中各样本X与均值与均值Mi间的间的误差平方和误差平方和对所有对所有类相加类相加。 2) Je度量了用度量了用c个聚类中心个聚类中心M1,MC代表代表c个样本子集个样本子集1,c时所产生的时所产生的总的误差平方总的误差平方。 3) 常用的。常用的。适用于那些适用于那些相互间分离较开的能形成紧密状相互间分离较开的能形成紧密状的的聚类。聚类。 ciXieiMXJ12iXiiXNM18.4 8.4 聚类方法聚类方法 聚类方法和聚类算法是不同的聚类方法和聚类算法是不同的。相同的聚类方法可用。相同的聚类方法可用不同的途

11、径来实现，从而不同的途径来实现，从而产生一系列聚类算法产生一系列聚类算法。 常用的聚类算法基本上都是常用的聚类算法基本上都是以寻找使分类的均方误差以寻找使分类的均方误差最小为基础的最小为基础的。 聚类算法可分成聚类算法可分成两类两类： 1 1）动态聚类方法：）动态聚类方法：通过对通过对每个模式的标记把模式组织成每个模式的标记把模式组织成少量的聚类少量的聚类，即给出单一的分类。，即给出单一的分类。 2 2）系统聚类方法：）系统聚类方法：是把模式样本是把模式样本聚合成一系列聚类的分聚合成一系列聚类的分层结构层结构，所得到的系统结构可由一个，所得到的系统结构可由一个树形图树形图来表示。来表示。 一、

12、动态聚类方法一、动态聚类方法 就是把就是把已知的已知的N个模式个模式集合集合划分成划分成C类类（CN,类别类别数数c取决于用户取决于用户) )。 需需3 3个要点：个要点：1 1）选定选定某种距离度量作为某种距离度量作为样本间的相似性度量样本间的相似性度量。 2 2）确定确定某个评价聚类结果质量的某个评价聚类结果质量的准则函数准则函数。 3 3）给定初始分类给定初始分类，然后依据算法，然后依据算法找出聚类结果找出聚类结果。 注：注：1 1）动态聚类方法允许）动态聚类方法允许模式样本从一个聚类移到另一个聚类模式样本从一个聚类移到另一个聚类，使使初始的不准确的划分逐步得到改进初始的不准确的划分逐步

13、得到改进。 2 2）聚类结果是）聚类结果是使一些准则函数取极值的划分使一些准则函数取极值的划分。 3 3）由于最优划分在计算上是困难的，）由于最优划分在计算上是困难的，例如：将例如：将1919个模式归入个模式归入3 3个聚类共有个聚类共有1.931.9310108 8种不同的划分。种不同的划分。因此只能在因此只能在使用启发式方式（即信息）后得出局部最优使用启发式方式（即信息）后得出局部最优。 1. 1. 启发式代表点（即初始点）的选择方法启发式代表点（即初始点）的选择方法 1 1）凭凭经验选择经验选择代表点。代表点。 2 2）将全部模式将全部模式随机地分成随机地分成c类类，计算每类，计算每类重

14、心重心并用并用其作为每类的代表点。其作为每类的代表点。 3 3）“密度密度”法选择代表点。法选择代表点。 4 4）用用前前c个样本点个样本点作为代表点。作为代表点。 等等等等2. 2. 初始分类的常用方法初始分类的常用方法 1 1）选定代表点后，选定代表点后，其余的点离哪个代表点最近就归其余的点离哪个代表点最近就归入哪一类入哪一类，而，而原来的每个代表点作为各自类的代表点原来的每个代表点作为各自类的代表点。 2 2）选定代表点后，其余的点离哪个代表点最近就归选定代表点后，其余的点离哪个代表点最近就归入哪一类，并计算入哪一类，并计算重心从而作为各自类的代表点重心从而作为各自类的代表点。 3 3）

15、给定一个正数给定一个正数，然后以选择的，然后以选择的一个样本为中心，一个样本为中心，以以为半径为半径，则，则超球面超球面内为一类，内为一类，球球外被分为另一类外被分为另一类（多类下的描述见书（多类下的描述见书236236页）页）。 3.3.动态聚类法的实现步骤动态聚类法的实现步骤 1 1）初始化聚类中心初始化聚类中心（即初始分类）；（即初始分类）； 2 2）修改聚类成员，）修改聚类成员，重新分配模式至聚类内重新分配模式至聚类内； 3 3）删除及合并聚类删除及合并聚类并认定远离点；并认定远离点； 4 4）当）当误差小于某一门限值误差小于某一门限值，或，或迭代的数目超出预先迭代的数目超出预先设设置

16、的数时停止置的数时停止。4. 4. C均值算法均值算法 此算法能使聚类域中此算法能使聚类域中所有样本到聚类中心所有样本到聚类中心的的距离平方和最小距离平方和最小。 即即 步骤如下：步骤如下： step1：任选初始聚类中心任选初始聚类中心：（括号内序号为迭代：（括号内序号为迭代序号）；序号）； step2：计算：计算所有样本与聚类中心的距离所有样本与聚类中心的距离)(2kXjjjMXJ),.,2, 1( )(CikMXi)(X ),.,2 , 1( )(min)( kCikMXkDjij则即(1)M),.,1 (MC1并并按最小距离原则进行分类按最小距离原则进行分类spet3: 重新计算重新计算

17、各个类新的聚类中心均值各个类新的聚类中心均值 式中：式中：Nj为为j类中所含的样本个数类中所含的样本个数 以以均值向量作为新的聚类中心，修改均值向量作为新的聚类中心，修改JeStep4: 如果如果 ，则转至，则转至step2; 否则停（即算法收敛）。否则停（即算法收敛）。)(),.,2 , 1( 1) 1(kXjjjCjXNkM)() 1(kMkMjj二、系统聚类方法（亦称分级聚类方法）二、系统聚类方法（亦称分级聚类方法）设有设有, ,N N共共N N个样本。个样本。Step1:Step1: 选择选择每个样本为一类每个样本为一类。 i i(0) ( i=1,2,(0) ( i=1,2,N N ) ) i i(0)(0)表示第表示第i i类第次聚类。类第次聚类。 计算计算类间距离类间距离 （不一定是欧氏距离）（不一定是欧氏距离） D Dijij ( i ( i与与j j类间的距离，记为类间的距离，记为D(0)D(0) ) )Step2:Step2