模式识别Ch非监督学习方法

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第八章,非监督学习方法,1,主要内容,1.,引言,2.,单峰子集（类）的分离方法,3.,类别分离的间接方法,4.,分级聚类方法,2,1.,引言,3,引言,有,监督学习,（,supervised learning),：,分类器设计方法是在,样本集中的类别标签已知,的条件下进行的，这些样本称为训练样本。在样本标签已知的情况下，可以统计出,各类训练样本不同的描述量,，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计。􀂄,用已知类别的样本训练分类器，以求对训练集的数据达到某种最优，并能推广到对新数据的分类。,4,无监督学习,（,unsupervised learning),：,样本数据类别未知，需要根据样本间的相似性对样本集进行分类,(,聚类，,clustering,),，试图使类内差距最小化，类间差距最大化。,利用聚类结果，可以提取数据集中隐藏的信息，对未来数据进行,预测和分类,。应用于数据挖掘、模式识别、图像处理、经济学,引言,5,广泛的应用领域,商务：,帮助市场分析人员从客户信息库中发现不同的客户群,，,用购买模式来刻画不同的客户群的特征,土地使用：,在地球观测数据库中识别土地使用情况相似的地区,保险业：,汽车保险单持有者的分组，标识那些有较高平均赔偿成本的客户。,城市规划：,根据,房子的类型，价值和地理分布对房子分组,生物学：,推导植物和动物的分类，对基因进行分类,地震研究,:,根据地质断层的特点把已观察到的地震中心分成不同的类。,6,有监督学习与无监督学习的区别,有监督学习方法,必须要有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而,非监督学习,没有训练集这一说，,只有一组数据，在该组数据集内寻找规律,。,有监督学习方法的目的就是识别事物,，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号的样本组成。而,非监督学习方法只有要分析的数据集本身,，预先没有什么标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号对上号为目的。,7,无监督学习方法在寻找数据集中的规律性,，这种规律性并不一定要达到划分数据集的目的，也就是说,不一定要“分类”,。这一点是比有监督学习方法的用途要广泛。譬如分析一堆数据的主分量，或分析数据集有什么特点都可以归于无监督学习方法的范畴。,用无监督学习方法分析数据集的主分量与用,K-L,变换,计算数据集的主分量又有区别。应该说后者从方法上讲不是一种学习方法。因此,用,K-L,变换找主分量不属于无监督学习方法，即方法上不是,。而通过学习逐渐找到规律性这体现了学习方法这一点。在人工神经元网络中寻找主分量的方法属于无监督学习方法。,有监督学习与无监督学习的区别,8,无监督学习方法的分类,基于概率密度函数估计的方法,：,指设法找到各类别在特征空间的,分布参数,再进行分类。􀂄,基于样本间相似性度量的方法,：,直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类。其原理是设法定出不同类别的核心，然后依据样本与这些核心之间的相似性度量，将样本聚集成不同类别。,如何聚类则取决于聚类的准则函数,，以使某种聚类准则达到极值为最佳。,两种聚类方法：,迭代的动态聚类方法,和,非迭代的分级聚类方法,9,2.,单峰子集（类）的分离方法,10,思想：,把特征空间分为若干个区域，,在每个区域上混合概率密度函数是单峰的,，每个单峰区域对应一个类别。,【,基本思想,】,11,直接,方法,一维空间中的单峰分离,:,对样本集,KN,=,xi,应用直方图,/,Parzen,窗方法,估计概率密度函数,，找到概率密度函数的峰以及峰之间的谷底，,以谷底为阈值,对数据进行分割。,【,一维空间中的单峰子集分离,】,12,【,多维空间投影方法,】,基本思路：,多维空间中直接划分成单峰区域比较困难，而一维空间中则比较简单。,􀂄 寻找一个坐标系统，在该系统下，数据的混合概率密度函数可以用边缘概率密度表示。,􀂄 如果某边缘概率密度函数呈现多峰形式，则在此坐标轴上（一维）作分割。,做法：,把样本投影到某一一维坐标轴（按某种准则），在这一维上求样本的概率密度（边缘概率密度），根据这一概率密度函数的单峰划分子集。,（如果这一维上只有一个峰，则寻找下一个投影方向。）,投影方向：使方差最大的方向，即协方差阵本征值最大的本征向量方向。,13,【,投影方法,】,基本步骤,14,问题：这样投影有时并不能产生多峰的边缘密度函数,-,方差最大的准则有时并不一定最有利于聚类。,【,存在问题,】,失败的例子,15,3.,类别分离的间接方法,16,【,引言,】,回顾：,直接方法：,1.,估计概率密度函数,困难,2.,寻找密度函数中的单峰,间接方法：考查样本这间的相似性，根据相似性把样本集划分为若干子集，使某种表示聚类质量的准则函数最优。,17,【,引言,】,相似性度量：以某种距离定义,直观理解：同一类的样本的特征向量应是相互靠近的。,前提：特征选取合理，能反映所求的聚类关系。,与基于密度函数的方法的关系：,概念上相互关联，因密度估计也是在样本间距离的基础上的。,具体关系取决于具体数据情况。,18,动态聚类方法的任务：,将数据集划分成一定数量的子集，,例如将一个数据集划分成三个子集，四个子集等。因此,要划分成多少个子集往往要预先确定，或大致确定,，这个子集数目在理想情况下能够体现数据集比较合理的划分。,需要解决的问题：,怎样才能知道该数据集应该划分的,子集数目,如果划分数目已定，则又,如何找到最佳划分,。因为数据集可以有许多种不同的划分方法，需要对不同的划分作出评价，并找到优化的划分结果。由于优化过程是从不甚合理的划分到,“,最佳,”,划分，是一个动态的迭代过程，故这种方法称为,动态聚类方法,。,􀂄,【,动态聚类方法,】,19,对计算机来说，所确定的初始代表点很可能不甚合理，以至于影响到聚类的结果。,这就需要有一个对聚类的结果进行修改或迭代的过程，使聚类结果逐步趋向合理。迭代的过程需要一个,准则函数,来指导，使迭代朝实现准则函数的极值化方向收敛。,聚类过程：,从确定各聚类的代表点开始（比如，确定三个质心点 ）,按各样本到三个质心最短距离将样本分到该类􀂄,【,动态聚类方法,】,20,三个要点,选定某种,距离度量,作为样本间的,相似性度量,；,确定样本合理的,初始分类,，包括代表点的选择，初始分类的方法选择等；􀂄,确定某种评价聚类结果质量的,准则函数,，用以调整初始分类直至达到该准则函数的极值。,【,动态聚类方法,】,C,均值算法（,k,均值，,C-means or k-means,）,ISODATA,方法,常用算法：,21,1.,准则函数,误差平方和准则,这个准则函数是以计算各类均值 ，与计算各类样本到其所属类别均值点误差平方和为准则。,反映了用,c,个聚类中心代表,c,个样本子集所带来的总的误差平方和。,目标,:,最小化,J,e,，即类内元素相似性高，类间元素相似性低，实现最小方差划分。,【C,均值算法,】,22,2.,样本集初始划分,􀂄,初始划分的一般作法是先选择一些,代表点,作为聚类的核心，然后把其余的样本按某种方法分到各类中去。,代表点的几种选择方法：,凭经验选择代表点,。,根据问题的性质，用经验的办法确定类别数，从数据中找出从直观上看来是比较合适的代表点。,将全部数据,随机,地分为,C,类，计算各类重心,，将这些重心作为每类的代表点。,【C,均值算法,】,23,“,密度,”,法选择代表点,。,这里的,“,密度,”,是具有统计性质的样本密度。,一种求法是对每个样本确定大小相等的邻域,(,如同样半径的超球体,),，,统计落在其邻域的样本数,，称为该点,“,密度,”,。在得到样本,“,密度,”,后，,选,“,密度,”,为最大的样本点作为第一个代表点,，然后人为规定距该代表点一定距离外的区域内找次高,“,密度,”,的样本点作为,第二个代表点,，依次选择其它代表点，使用这种方法的目的是避免代表点过分集中在一起。,用,前,c,个样本点,作为代表点,【C,均值算法,】,24,从,(c-1),聚类,划分,问题的解中产生,C,聚类划分问题的代表点。,其具体做法：对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成两聚类的代表点。依同样方法，对已有,(c-1),个聚类代表点,(,由,(c-1),个类均值点组成,),找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第,c,个代表点。,【C,均值算法,】,25,【,动态聚类,】,C,均值算法,初始分类方法：,1.,最近距离法。离哪个代表点近就归入哪一类。,2.,最近距离法归类，但每次都重新计算该类代表点。,3.,直接划分初始分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，,4.,将特征归一化，用样本各特征之和作为初始分类依据。,说明：,􀁺 初始划分无一定之规，多为启发式方法。,􀁺,C,均值方法结果受初值影响，是局部最优解。,26,【,动态聚类,】,C,均值算法,27,【,动态聚类,】,C,均值算法,28,【,动态聚类,】,C,均值算法,29,【,动态聚类,】,C,均值聚类方法用于非监督模式识别的问题：,1.,要求类别数已知；,2.,是最小方差划分，并不一定能反映内在分布；,3.,与初始划分有关，不保证全局最优。,C,均值算法,30,在,类别数未知,情况下使用,C,均值算法时，可以假设类别数是逐步增加的，例如对,c,1,，,2,，,3,，,分别使用该算法。,准则函数 是随,c,的增加而单调地减少的。如果样本集的合理聚类数为,c,类，当类别数继续增大时，相当于将聚类很好的类别又分成子类，则 值虽然继续减少但会呈现平缓趋势，如果作一条 值随,c,变化的曲线，则其,拐点对应的类别数就比较接近于最优聚类数,。,【C,均值算法,-,类别数未知,】,31,但是并非所有的情况都能找到明显的转折点。在无明显的转折点时，这种选择最佳分类数的方法将失效。,一般需要利用先验知识对不同的聚类结果进行分析比较。,【C,均值算法,-,类别数未知,】,32,C,均值算法比较简单，但它的自我调整能力也比较差。这主要表现在类别数必须事先确定，不能改变，这种主观确定数据子集数目并不一定符合数据集自身的特点，受代表点初始选择的影响也比较大。,类似于,C,均值算法，,ISODATA,算法的聚类中心也是通过样本均值的迭代运算来决定。与,C,均值算法不同的是，,ISODATA,算法 将硬性确定聚类数目改成,给出这个数目的期望值,，作为算法的一个控制量。在算法中又加上,分裂,与,合并,机制，增加了一些试探性步骤和人机交互的“自组织”处理方式，因而能使聚类结果比较适应数据集的内在特性。,ISODATA,算法与,C,均值算法相比，在下列几方面有改进。,1.,考虑了类别的合并与分裂，因而有了自我调整类别数的,能力。,合并主要发生在某一类内样本个数太少的情况，或两类,聚类中心之间距离太小的情况。,【,迭代自组织的数据分析算法,-ISODATA】,33,分裂,则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。,给出一个对类内分量方差的限制参数 ，用以决定是否需要将某一类分裂成两类。,2.,由于算法有自我调整的能力，因而需要,设置若干个控,制用参数。,迭代自组织算法流程图如图,5-7,所示。,【,迭代自组织的数据分析算法,-ISODATA】,34,ISODATA,算法的具体步骤如下：,【,迭代自组织的数据分析算法,-ISODATA】,35,【,迭代自组织的数据分析算法,-ISODATA】,36,【,迭代自组织的数据分析算法,-ISODATA】,37,【,迭代自组织的数据分析算法,-ISODATA】,38,【,迭代自组织的数据分析算法,-ISODATA】,39,步骤,9(,求每类具有最大标准偏差的分量,),步骤,10(,分裂计算步骤,),【,迭代自组织的数据分析算法,-ISODATA】,40,合并处理：,步骤,11(,计算全部聚类中心之间的距离,),【,迭代自组织的数据分析算法,-ISODATA】,41,步骤,12(,列出类间距离过近者,),步骤,13(,执行合并,),【,迭代自组织的数据分析算法,-ISODATA】,42,步骤,14(,结束步骤,),如果迭代运算次数已达最大的迭代次数,I,，即是最后一次迭代，则算法结束；否则，如果需要由操作者改变输入参数，转入步骤,1,，设计相应的参数；否则，转入步骤,2,。到了本步运算，迭代运算的次数加,1,。,以上是整个,ISODATA,算法的计算步骤。可以看出,ISODATA,算法与,C,均值算法一样，都是以与代表点的最小距离作为样本聚类的依据，因此比较适合各类物体在特征空间以超球体分布的方式分布，对于分布形状较复杂的情况需要采用别的度量。,ISODATA,算法与,C,均值算法的主要不同在于自我控制与调整的能力不同。,【,迭代自组织的数据分析算法,-ISODATA】,43,ISODATA,算法流程图,【,迭代自组织的数据分析算法,-ISODATA】,44,【,基于样本和核的相似性度量的动态聚类算法,】,45,【,基于样本和核的相似性度量的动态聚类算法,】,46,【,基于样本和核的相似性度量的动态聚类算法,】,47,【,近邻函数准则算法,】,定义,48,【,近邻函数准则算法,】,第,i,类和第,j,类间最小近邻函数值定义为：,相似性分析,第,i,类内最大连接损失记为：,a,i,max,第,i,类与第,j,类之间的连接损失定义为,b,ij,，它的设计目标是：如果两类间的最小近邻值大于任何一方的类内的最大连接损失时，损失代价就是正的，从而应该考虑把这两类合并,49,【,近邻函数准则算法,】,总类间损失：,相似性分析,准则函数：,算法步骤：,计算距离矩阵,用距离矩阵计算近邻矩阵,计算近邻函数矩阵,在,L,中，每个点与其最近邻连接，形成初始的划分,对每两个类计算,r,ij,和,a,imax,，,a,jmax,，只要,r,ij,小于,a,imax,、,a,jmax,中的任何一个，就合并两类（建立连接）。重复至没有新的连接发生为止,50,4.,分级聚类方法,（,Hierachical Clustering,）,51,分级聚类方法的目的并不把,N,个样本分成某一个预定的类别数,C,，而是,把样本集按不同的相似程度要求分成不同类别的聚类,。,最极端的情况是每个样本各自为一类，,N,个样本共有,N,类，没有任何聚类，另一极端则是将所有样本归一类。在这两个极端之间的是类别数从,N,逐渐减少，每类的数量相应增加，而类内样本的相似程度要求也随之下降。,这种聚类就是分级聚类，它可以用一,树形结构,表示。,【,分级聚类方法,-,类别数未知,】,52,这是一棵具有,6,个样本的分类树。图中左边表示分级层次，第一层次各样本自成一类，其类内相似度自然是百分之百，在第二层次,y3,与,y5,合成一类，第三层次,y1,与,y4,也合并成一类，依次下去。一经合并成一类的样本不再分裂，类别数也随之逐渐减少，类内相似程度逐渐降低。,这种聚类方法在科学技术领域中得到了广泛的应用，如生物分类就是分级聚类应用的一个例子。,【,分级聚类树,表示方法,】,53,【,分级聚类方法,】,思想：从各类只有一个样本点开始，逐级合并，每级只合并两类，直到最后所有样本都归到一类。,Hierarchical tree - dendrogram,聚类过程中逐级考查类间相似度，依此决定类别数,54,算法（从底向上）：,（,1,）初始化，每个样本形成一类,（,2,）把相似性最大（距离最小）的两类合并,（,3,）重复（,2,），直到所有样本合并为两类。,【,分级聚类方法,】,55,【分级聚类方法,】,划分序列：,N,个样本,自底向上逐步合并,一类：,每个样本自成一类（划分水平,1,）,K,水平划分的进行：计算已有的,c,=,N,-,K,+2,个,类的类间距离矩阵,D,(,K,-1),=,d,ij,(,K,-1),，其最小元素记作,d,(,K,-1),，相应的两个类合并成一类,重复第,2,步，直至形成包含所有样本的类（划分水平,N,）,划分处于,K,水平时，类数,c,=,N,-,K,+1,，,类间距离矩阵,D,(,K,),=,d,ij,(,K,),，其最小元素记作,d,(,K,),如果,d,(,K,),阈值,d,T,，则说明此水平上的聚类是适宜的,56,采用最近距离作相似性度量时聚成两类的结果,（,a,）,（,b,）,（,c,）,图,1,图,2,57,最远距离的聚类结果,（,a,）,（,b,）,（,c,）,图,3,58,分析,从图,2,与,3,的比较中可以看出，,使用最近距离与最远距离在样本不同的分布中可能得出不同的结果,，图,1(a),与,(b),不同在于,(b),中两个密集的分布中间多了两个干扰点,y1,与,y2,。,在使用最短距离时，它对聚类产生了明显的影响，在图,2,中,(a),与,(b),是两种很不相同的聚类结果，然而在图,3,的,(a),与,(b),中可以看出两个干扰点对聚类没有明显的影响，这说明,采用最近距离对两个密集区的相邻区中的干扰点十分敏感,，而,用最远距离则可防止两个密集区通过某个路经聚为一类的可能性,。,但是如果我们再对比图,2,中,(c),的点集分布情况及使用最近距离与最远距离的聚类结果，可以看出,最近距离对这种长条形分布是比较适合的,，而,最远距离不能检出具有长条形状的聚类,。显然,使用最远距离将使个别的远离点对聚类结果产生明显的影响,。至于使用均值距离的效果，将介乎于上述两者之间。,59,【,非监督学习方法中的一些问题讨论,】,60,