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