模式识别-Ch8-非监督学习方法.ppt

《模式识别-Ch8-非监督学习方法.ppt》由会员分享，可在线阅读，更多相关《模式识别-Ch8-非监督学习方法.ppt（60页珍藏版）》请在三一办公上搜索。

1、第八章 非监督学习方法,2,主要内容,1.引言2.单峰子集（类）的分离方法3.类别分离的间接方法4.分级聚类方法,3,1.引言,4,引言,有监督学习（supervised learning)：分类器设计方法是在样本集中的类别标签已知的条件下进行的，这些样本称为训练样本。在样本标签已知的情况下，可以统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计。用已知类别的样本训练分类器，以求对训练集的数据达到某种最优，并能推广到对新数据的分类。,5,无监督学习（unsupervised learning)：样本数据类别未知，需要根据样本间的相似性对样本集进行

2、分类(聚类，clustering)，试图使类内差距最小化，类间差距最大化。利用聚类结果，可以提取数据集中隐藏的信息，对未来数据进行预测和分类。应用于数据挖掘、模式识别、图像处理、经济学,引言,6,广泛的应用领域,商务：帮助市场分析人员从客户信息库中发现不同的客户群，用购买模式来刻画不同的客户群的特征土地使用：在地球观测数据库中识别土地使用情况相似的地区保险业：汽车保险单持有者的分组，标识那些有较高平均赔偿成本的客户。城市规划：根据房子的类型，价值和地理分布对房子分组生物学：推导植物和动物的分类，对基因进行分类地震研究:根据地质断层的特点把已观察到的地震中心分成不同的类。,7,有监督学习与无监督

3、学习的区别,有监督学习方法必须要有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而非监督学习没有训练集这一说，只有一组数据，在该组数据集内寻找规律。有监督学习方法的目的就是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号的样本组成。而非监督学习方法只有要分析的数据集本身，预先没有什么标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号对上号为目的。,8,无监督学习方法在寻找数据集中的规律性，这种规律性并不一定要达到划分数据集的目的，也就是说不一定要“分类”。这一点是比有监督学习方法的用途要广泛。譬如分析一堆数据的主分

4、量，或分析数据集有什么特点都可以归于无监督学习方法的范畴。用无监督学习方法分析数据集的主分量与用K-L变换计算数据集的主分量又有区别。应该说后者从方法上讲不是一种学习方法。因此用K-L变换找主分量不属于无监督学习方法，即方法上不是。而通过学习逐渐找到规律性这体现了学习方法这一点。在人工神经元网络中寻找主分量的方法属于无监督学习方法。,有监督学习与无监督学习的区别,9,无监督学习方法的分类,基于概率密度函数估计的方法：指设法找到各类别在特征空间的分布参数再进行分类。基于样本间相似性度量的方法：直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类。其原理是设法定出不同类别的核心，然后依据样

5、本与这些核心之间的相似性度量，将样本聚集成不同类别。如何聚类则取决于聚类的准则函数，以使某种聚类准则达到极值为最佳。两种聚类方法：迭代的动态聚类方法和非迭代的分级聚类方法,10,2.单峰子集（类）的分离方法,11,思想：把特征空间分为若干个区域，在每个区域上混合概率密度函数是单峰的，每个单峰区域对应一个类别。,【基本思想】,12,直接方法,一维空间中的单峰分离:对样本集KN=xi应用直方图/Parzen窗方法估计概率密度函数，找到概率密度函数的峰以及峰之间的谷底，以谷底为阈值对数据进行分割。,【一维空间中的单峰子集分离】,13,【多维空间投影方法】,基本思路：多维空间中直接划分成单峰区域比较困

6、难，而一维空间中则比较简单。寻找一个坐标系统，在该系统下，数据的混合概率密度函数可以用边缘概率密度表示。如果某边缘概率密度函数呈现多峰形式，则在此坐标轴上（一维）作分割。做法：把样本投影到某一一维坐标轴（按某种准则），在这一维上求样本的概率密度（边缘概率密度），根据这一概率密度函数的单峰划分子集。（如果这一维上只有一个峰，则寻找下一个投影方向。）,投影方向：使方差最大的方向，即协方差阵本征值最大的本征向量方向。,14,【投影方法】,基本步骤,15,问题：这样投影有时并不能产生多峰的边缘密度函数-方差最大的准则有时并不一定最有利于聚类。,【存在问题】,失败的例子,16,3.类别分离的间接方法,1

7、7,【引言】,回顾：直接方法：1.估计概率密度函数 困难2.寻找密度函数中的单峰间接方法：考查样本这间的相似性，根据相似性把样本集划分为若干子集，使某种表示聚类质量的准则函数最优。,18,【引言】,相似性度量：以某种距离定义直观理解：同一类的样本的特征向量应是相互靠近的。前提：特征选取合理，能反映所求的聚类关系。,与基于密度函数的方法的关系：概念上相互关联，因密度估计也是在样本间距离的基础上的。具体关系取决于具体数据情况。,19,动态聚类方法的任务：将数据集划分成一定数量的子集，例如将一个数据集划分成三个子集，四个子集等。因此要划分成多少个子集往往要预先确定，或大致确定，这个子集数目在理想情况

8、下能够体现数据集比较合理的划分。需要解决的问题：怎样才能知道该数据集应该划分的子集数目 如果划分数目已定，则又如何找到最佳划分。因为数据集可以有许多种不同的划分方法，需要对不同的划分作出评价，并找到优化的划分结果。由于优化过程是从不甚合理的划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。,【动态聚类方法】,20,对计算机来说，所确定的初始代表点很可能不甚合理，以至于影响到聚类的结果。这就需要有一个对聚类的结果进行修改或迭代的过程，使聚类结果逐步趋向合理。迭代的过程需要一个准则函数来指导，使迭代朝实现准则函数的极值化方向收敛。,聚类过程：从确定各聚类的代表点开始（比如，确定

9、三个质心点）按各样本到三个质心最短距离将样本分到该类,【动态聚类方法】,21,三个要点选定某种距离度量作为样本间的相似性度量；确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等；确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。,【动态聚类方法】,22,1.准则函数误差平方和准则 这个准则函数是以计算各类均值，与计算各类样本到其所属类别均值点误差平方和为准则。,反映了用c个聚类中心代表c个样本子集所带来的总的误差平方和。,目标:最小化Je，即类内元素相似性高，类间元素相似性低，实现最小方差划分。,【C均值算法】,23,2.样本集初始划分初始划分的一般作法

10、是先选择一些代表点作为聚类的核心，然后把其余的样本按某种方法分到各类中去。代表点的几种选择方法：凭经验选择代表点。根据问题的性质，用经验的办法确定类别数，从数据中找出从直观上看来是比较合适的代表点。将全部数据随机地分为C类，计算各类重心，将这些重心作为每类的代表点。,【C均值算法】,24,“密度”法选择代表点。这里的“密度”是具有统计性质的样本密度。一种求法是对每个样本确定大小相等的邻域(如同样半径的超球体)，统计落在其邻域的样本数，称为该点“密度”。在得到样本“密度”后，选“密度”为最大的样本点作为第一个代表点，然后人为规定距该代表点一定距离外的区域内找次高“密度”的样本点作为第二个代表点，

11、依次选择其它代表点，使用这种方法的目的是避免代表点过分集中在一起。用前c个样本点作为代表点,【C均值算法】,25,从(c-1)聚类划分问题的解中产生C聚类划分问题的代表点。其具体做法：对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成两聚类的代表点。依同样方法，对已有(c-1)个聚类代表点(由(c-1)个类均值点组成)找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第c个代表点。,【C均值算法】,26,【动态聚类】,初始分类方法：1.最近距离法。离哪个代表点近就归入哪一类。2.最近距离法归类，但每次都重新计算该类代表点。3.直接划分初始

12、分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，4.将特征归一化，用样本各特征之和作为初始分类依据。,说明：初始划分无一定之规，多为启发式方法。C 均值方法结果受初值影响，是局部最优解。,27,【动态聚类】,C 均值算法,28,【动态聚类】,29,【动态聚类】,30,【动态聚类】,C 均值聚类方法用于非监督模式识别的问题：1.要求类别数已知；2.是最小方差划分，并不一定能反映内在分布；3.与初始划分有关，不保证全局最优。,31,在类别数未知情况下使用C均值算法时，可以假设类别数是逐步增加的，例如对c1，2，3，分别使用该算法。准则函数 是随c的增加而单调地减少的

13、。如果样本集的合理聚类数为c类，当类别数继续增大时，相当于将聚类很好的类别又分成子类，则 值虽然继续减少但会呈现平缓趋势，如果作一条 值随c变化的曲线，则其拐点对应的类别数就比较接近于最优聚类数。,【C均值算法-类别数未知】,32,但是并非所有的情况都能找到明显的转折点。在无明显的转折点时，这种选择最佳分类数的方法将失效。一般需要利用先验知识对不同的聚类结果进行分析比较。,【C均值算法-类别数未知】,33,C 均值算法比较简单，但它的自我调整能力也比较差。这主要表现在类别数必须事先确定，不能改变，这种主观确定数据子集数目并不一定符合数据集自身的特点，受代表点初始选择的影响也比较大。类似于C 均

14、值算法，ISODATA算法的聚类中心也是通过样本均值的迭代运算来决定。与C均值算法不同的是，ISODATA算法 将硬性确定聚类数目改成给出这个数目的期望值，作为算法的一个控制量。在算法中又加上分裂与合并机制，增加了一些试探性步骤和人机交互的“自组织”处理方式，因而能使聚类结果比较适应数据集的内在特性。ISODATA算法与C 均值算法相比，在下列几方面有改进。1.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。,【迭代自组织的数据分析算法-ISODATA】,34,分裂则主要发生在某一类别的某分量出现类内方差过大的现

15、象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数，用以决定是否需要将某一类分裂成两类。2.由于算法有自我调整的能力，因而需要设置若干个控 制用参数。,迭代自组织算法流程图如图5-7所示。,【迭代自组织的数据分析算法-ISODATA】,35,ISODATA算法的具体步骤如下：,【迭代自组织的数据分析算法-ISODATA】,36,【迭代自组织的数据分析算法-ISODATA】,37,【迭代自组织的数据分析算法-ISODATA】,38,【迭代自组织的数据分析算法-ISODATA】,39,【迭代自组织的数据分析算法-ISODATA】,40,步骤9(求每类具有最大标准偏差的

16、分量),步骤10(分裂计算步骤),【迭代自组织的数据分析算法-ISODATA】,41,合并处理：步骤11(计算全部聚类中心之间的距离),【迭代自组织的数据分析算法-ISODATA】,42,步骤12(列出类间距离过近者),步骤13(执行合并),【迭代自组织的数据分析算法-ISODATA】,43,步骤14(结束步骤),如果迭代运算次数已达最大的迭代次数I，即是最后一次迭代，则算法结束；否则，如果需要由操作者改变输入参数，转入步骤1，设计相应的参数；否则，转入步骤2。到了本步运算，迭代运算的次数加1。以上是整个ISODATA算法的计算步骤。可以看出ISODATA算法与C 均值算法一样，都是以与代表点

17、的最小距离作为样本聚类的依据，因此比较适合各类物体在特征空间以超球体分布的方式分布，对于分布形状较复杂的情况需要采用别的度量。ISODATA算法与C均值算法的主要不同在于自我控制与调整的能力不同。,【迭代自组织的数据分析算法-ISODATA】,44,ISODATA算法流程图,【迭代自组织的数据分析算法-ISODATA】,45,【基于样本和核的相似性度量的动态聚类算法】,46,【基于样本和核的相似性度量的动态聚类算法】,47,【基于样本和核的相似性度量的动态聚类算法】,48,【近邻函数准则算法】,定义,第七章 非监督学习方法,49,【近邻函数准则算法】,第i类和第j类间最小近邻函数值定义为：,相

18、似性分析,第i类内最大连接损失记为：aimax第i类与第j类之间的连接损失定义为bij，它的设计目标是：如果两类间的最小近邻值大于任何一方的类内的最大连接损失时，损失代价就是正的，从而应该考虑把这两类合并,第七章 非监督学习方法,50,【近邻函数准则算法】,总类间损失：,相似性分析,准则函数：算法步骤：计算距离矩阵用距离矩阵计算近邻矩阵计算近邻函数矩阵在L 中，每个点与其最近邻连接，形成初始的划分对每两个类计算rij 和aimax，ajmax，只要rij 小于aimax、ajmax中的任何一个，就合并两类（建立连接）。重复至没有新的连接发生为止,51,4.分级聚类方法（Hierachical

19、Clustering）,52,分级聚类方法的目的并不把N个样本分成某一个预定的类别数C，而是把样本集按不同的相似程度要求分成不同类别的聚类。最极端的情况是每个样本各自为一类，N个样本共有N类，没有任何聚类，另一极端则是将所有样本归一类。在这两个极端之间的是类别数从N逐渐减少，每类的数量相应增加，而类内样本的相似程度要求也随之下降。这种聚类就是分级聚类，它可以用一树形结构表示。,【分级聚类方法-类别数未知】,53,这是一棵具有6个样本的分类树。图中左边表示分级层次，第一层次各样本自成一类，其类内相似度自然是百分之百，在第二层次y3与y5合成一类，第三层次y1与y4也合并成一类，依次下去。一经合并

20、成一类的样本不再分裂，类别数也随之逐渐减少，类内相似程度逐渐降低。这种聚类方法在科学技术领域中得到了广泛的应用，如生物分类就是分级聚类应用的一个例子。,【分级聚类树表示方法】,54,【分级聚类方法】,思想：从各类只有一个样本点开始，逐级合并，每级只合并两类，直到最后所有样本都归到一类。,Hierarchical tree-dendrogram聚类过程中逐级考查类间相似度，依此决定类别数,55,算法（从底向上）：（1）初始化，每个样本形成一类（2）把相似性最大（距离最小）的两类合并（3）重复（2），直到所有样本合并为两类。,【分级聚类方法】,56,【分级聚类方法】,划分序列：N个样本自底向上逐步

21、合并一类：每个样本自成一类（划分水平1）K水平划分的进行：计算已有的c=N-K+2个类的类间距离矩阵D(K-1)=dij(K-1)，其最小元素记作d(K-1)，相应的两个类合并成一类重复第2步，直至形成包含所有样本的类（划分水平N）划分处于K水平时，类数c=N-K+1，类间距离矩阵D(K)=dij(K)，其最小元素记作d(K)如果d(K)阈值dT，则说明此水平上的聚类是适宜的,57,采用最近距离作相似性度量时聚成两类的结果,（a）,（b）,（c）,图1,图2,58,最远距离的聚类结果,（a）,（b）,（c）,图3,59,分析,从图2与3的比较中可以看出，使用最近距离与最远距离在样本不同的分布中

22、可能得出不同的结果，图1(a)与(b)不同在于(b)中两个密集的分布中间多了两个干扰点y1与y2。在使用最短距离时，它对聚类产生了明显的影响，在图2中(a)与(b)是两种很不相同的聚类结果，然而在图3的(a)与(b)中可以看出两个干扰点对聚类没有明显的影响，这说明采用最近距离对两个密集区的相邻区中的干扰点十分敏感，而用最远距离则可防止两个密集区通过某个路经聚为一类的可能性。但是如果我们再对比图2中(c)的点集分布情况及使用最近距离与最远距离的聚类结果，可以看出最近距离对这种长条形分布是比较适合的，而最远距离不能检出具有长条形状的聚类。显然使用最远距离将使个别的远离点对聚类结果产生明显的影响。至于使用均值距离的效果，将介乎于上述两者之间。,60,【非监督学习方法中的一些问题讨论】,