无监督学习和聚类.pptx

会计学1无监督学习和聚类无监督学习和聚类7 7 无监督学习和聚类无监督学习和聚类(Unsupervised learning,Clustering)(Unsupervised learning,Clustering)uu监督学习：给定监督学习：给定已知已知类别类别的学习样本，设的学习样本，设计分类器。计分类器。uu非监督学习：给定非监督学习：给定未知未知(未知未知类别类别及及类别数类别数)样本，设计分类器。样本，设计分类器。uu两大类非监督学习：基于两大类非监督学习：基于概率密度函数估概率密度函数估计计的的直接直接方法和基于方法和基于样本间相似性样本间相似性(similarity)(similarity)度量的度量的间接间接聚类方法。聚类方法。第1页/共61页主要内容主要内容uu 掌握非监督学习方法的概念、用途。uu了解非监督学习方法对数据划分有两种基本方法。uu掌握以k-均值算法，ISODATA算法为代表的动态聚类方法。uu了解层次(分级)聚类方法。第2页/共61页9.1 9.1 9.1 9.1 基本概念基本概念基本概念基本概念uu以前讨论分类器设计方法都是在样本集中的类别已知的条件下进行的，这些样本称为训练样本。统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。uu未知样本的类别，没有训练样本，因而只能从未知样本类别样本集进行分类器设计，这就是通常说的无监督学习方法。第3页/共61页第4页/共61页第5页/共61页非监督学习与有监督学习方法的区别：非监督学习与有监督学习方法的区别：非监督学习与有监督学习方法的区别：非监督学习与有监督学习方法的区别：uu有监督学习方法必须有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而非监督学习没有训练集，只有一组数据，在该组数据集内寻找规律。uu有监督学习方法的目的是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号样本组成；而非监督学习方法只有分析数据集本身，无标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号为目的。第6页/共61页n n非监督学习方法在寻找数据集中的规律性，这种规律性不是划分数据集的目的，即不一定要“分类”。比如分析数据的主分量，或分析数据集的特点。n n非监督学习方法分析数据集的主分量与用K-L变换计算数据集的主分量又有区别。n nK-LK-L变换不是一种学习方法，不属变换不是一种学习方法，不属于非监督学习方法。于非监督学习方法。n n在人工神经元网络中寻找主分量在人工神经元网络中寻找主分量的方法属于非监督学习方法。的方法属于非监督学习方法。第7页/共61页非监督学习方法可以分成两大类：非监督学习方法可以分成两大类：n n一类为一类为基于概率密度函数基于概率密度函数估计的直接估计的直接方法：方法：设法找到各类别在特征空间的设法找到各类别在特征空间的分布参数再进行分类；分布参数再进行分类；n n一类称为一类称为基于样本间相似性度量基于样本间相似性度量的间的间接聚类方法。其原理接聚类方法。其原理是设法定出不同是设法定出不同类别的核心或初始类核，然后依据样类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本与这些核心之间的相似性度量将样本聚集成不同类别。本聚集成不同类别。第8页/共61页9.2 9.2 9.2 9.2 基于概率密度函数估计的直接方法基于概率密度函数估计的直接方法基于概率密度函数估计的直接方法基于概率密度函数估计的直接方法 uu该方法的关键是找出各个峰值区。uu单峰子类的分离方法(称为投影法)每个分量有无峰谷点表现出来。每个分量有无峰谷点表现出来。利用投影，直接找密集区域。利用投影，直接找密集区域。第9页/共61页n n样本在整个特征空间中呈现两个分布高峰。n n如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值，这些区域被称为单峰区域。n n而每个单峰区域则被看作不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为单峰子类。第10页/共61页第11页/共61页投影法投影法投影法投影法 uu对于样本在某一种度量中的对于样本在某一种度量中的分布统计分布统计，一般称为一般称为直方图统计直方图统计，在样本数量很，在样本数量很大时，又可作为大时，又可作为概率统计的估计概率统计的估计。uu由于这种方法基于将由于这种方法基于将样本样本投影投影到某个到某个坐标轴上，因而称为坐标轴上，因而称为投影方法投影方法。uu使用投影使用投影方法方法有有两个两个组成组成部分部分一个是如何一个是如何设计设计合适的合适的坐标系统坐标系统。另一是如何另一是如何设计设计直方图直方图。第12页/共61页投影法投影法投影法投影法 uu在样本属性完全不知的情况下，如在样本属性完全不知的情况下，如何选择何选择坐标系统坐标系统比较比较困难困难的。目前的。目前还没有一个准则函数来表征这样坐还没有一个准则函数来表征这样坐标系统的性质。标系统的性质。uu一种一种启发式的启发式的办法是使待分类的样办法是使待分类的样本在本在某个坐标轴方向某个坐标轴方向具有具有最大最大的的分分散性散性，采用上一章讨论过的，采用上一章讨论过的K-LK-L变变换换方法。方法。第13页/共61页投影法投影法投影法投影法 uu用用混合样本协方差矩阵混合样本协方差矩阵作为作为K-LK-L变换的变换的产生矩阵，找到其特征值，并按大小产生矩阵，找到其特征值，并按大小排序。排序。uu对应最大特征值的对应最大特征值的特征向量特征向量对此混合对此混合样本来说，样本来说，离散程度离散程度最大，预期能发最大，预期能发现明显的峰值，但是这种方法并现明显的峰值，但是这种方法并不能不能保证保证分出各个聚类。分出各个聚类。第14页/共61页第15页/共61页投影法算法步骤：投影法算法步骤：投影法算法步骤：投影法算法步骤：uu计算样本协方差矩阵具有最大特征值的特征向量uj，把数据投影到 uj轴上。uu用直方图方法求数据的边缘概率密度函数。uu在直方图的峰值间求最小值，在这些最小点作垂直于uj的各个超平面把数据划分为若干个聚类。uu 如果在轴上没有这样的最小值，则用下一个最大特征值对应的特征向量重复以上过程。uu 对每个得到的子集(聚类)重复上述过程，直到每个集不能再分(为单峰)为止。第16页/共61页灰度图像二值化算法灰度图像二值化算法n n灰度图像阈值:取主值，使J(k)最大时的K值第17页/共61页单峰子集分离的迭代单峰子集分离的迭代算法算法uu把样本集把样本集K KN N=x=xi i 分成分成c c个不相交子集个不相交子集K Ki i。用。用这样的一个划分可用这样的一个划分可用ParzenParzen方法估计各类方法估计各类的概率密度函数：的概率密度函数：uu聚类准则：即理想的划分应使下式最大聚类准则：即理想的划分应使下式最大第18页/共61页迭代算法步迭代算法步骤骤1.1.对数据集进行初始划分：K1,K2,Kc2.2.用Parzen方法估计各聚类的概率密度函数3.3.按照最大似然概率逐个对样本xk k进行分类：4.4.若没有数据点发生类别迁移变化，则停止。否则转2第19页/共61页9.3 类别分离的间接方法类别分离的间接方法n n两个要点:相似性度量，准则函数n相似性度量n n样本间相似性度量样本间相似性度量:特征空间的某种距离特征空间的某种距离度量度量n样本与样本聚类间相似性度量第20页/共61页准则函数准则函数n n准则函数：聚类质量的判别标准，常用的最小误差平方和准则uu目标目标:类内元素相似性高，类间元素相似性类内元素相似性高，类间元素相似性低低第21页/共61页聚类方法聚类方法聚类方法聚类方法 uu按按相相似似度度进进行行划划分分的的方方法法，原原理理很很简简单单。如如果果把把相相似似度度表表示示成成在在特特征征空空间间中中的的某某种种距距离离度度量量,这这种种方方法法又又称称为为基基于于距距离离度度量量的的方方法法。与与前前一一种种方方法法相相比比，它它不不是是以以计计算算密密度度程程度度为为依依据据的的，因因此此这这是是这这两两种种方方法的主要区别。法的主要区别。uu不通过对概率密度函数作出估计而直接按不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中样本间的相似性，或彼此间在特征空间中的的距离长短距离长短进行分类，这种方法称为进行分类，这种方法称为聚类聚类方法。方法。第22页/共61页聚类方法聚类方法聚类方法聚类方法 uu如如何何聚聚类类则则取取决决于于聚聚类类的的准准则则函函数数，以便某种聚类准则达到以便某种聚类准则达到极值极值为最佳。为最佳。uu有有两两种种对对数数据据集集进进行行聚聚类类的的方方法法：迭迭代代的的动动态态聚聚类类算算法法和和非非迭迭代代的的分分级聚类级聚类算法。算法。第23页/共61页第24页/共61页9.3.1 9.3.1 9.3.1 9.3.1 动态聚类方法动态聚类方法动态聚类方法动态聚类方法 uu动动态态聚聚类类方方法法的的任任务务是是将将数数据据集集划划分分成一定数量的子集。成一定数量的子集。uu要解决的问题是要解决的问题是:1 1怎怎样样才才能能知知道道该该数数据据集集应应该该划划分的子集分的子集数目数目2 2若若划划分分数数目目已已定定，则则又又如如何何找找到到最佳划分最佳划分。第25页/共61页9.3.1 9.3.1 9.3.1 9.3.1 动态聚类方法动态聚类方法动态聚类方法动态聚类方法 uu因因为为数数据据集集可可以以有有许许多多种种不不同同的的划划分分方方法法，需需要要对对不不同同的的划划分分作作出出评评价价，并并找找到到优化优化的划分结果。的划分结果。uu由由于于优优化化过过程程是是从从”不不合合理理的的”划划分分到到“最最佳佳”划划分分，是是一一个个动动态态的的迭迭代代过过程程，故这种方法称为故这种方法称为动态聚类方法动态聚类方法。uu先先讨讨论论子子集集数数目目已已知知条条件件下下的的聚聚类类方方法法，然后在讨论如何确定然后在讨论如何确定合理合理的子集数目。的子集数目。第26页/共61页第27页/共61页9.3.1 9.3.1 9.3.1 9.3.1 动态聚类方法要点动态聚类方法要点动态聚类方法要点动态聚类方法要点 uu1.1.选选定定某某种种距距离离度度量量作作为为样样本本间间的的相相似似性度量性度量；uu2.2.确确定定样样本本合合理理的的初初始始分分类类，包包括括代代表表点的选择，初始分类的方法选择等；点的选择，初始分类的方法选择等；uu3.3.确确定定某某种种评评价价聚聚类类结结果果质质量量的的准准则则函函数数，用用以以调调整整初初始始分分类类直直至至达达到到该该准准则函数的极值则函数的极值。第28页/共61页(1).K-均值算法（均值算法（k-Means,k-均值均值)uu对样本集对样本集K KN N=x=xi i 尚不知每个样本的类别，尚不知每个样本的类别，但可但可假设假设所有样本可分为所有样本可分为c c类，各类样本在类，各类样本在特征空间依类聚集，且近似球形分布特征空间依类聚集，且近似球形分布uu用一用一代表点(prototype)(prototype)来表示一个聚类，如来表示一个聚类，如类内均值类内均值mmi i来代表聚类来代表聚类K Ki iuu聚类准则：误差平方和聚类准则：误差平方和J J第29页/共61页k-均值均值算法的训练算法的训练1.初始化：选择c个代表点p1,p2,pc2.建立c个空聚类列表：K1,K2,Kc3.按照最小距离法则逐个对样本x进行分类：4.计算J及用各聚类列表计算聚类均值，并用来作为各聚类新的代表点（更新代表点）5.若J不变或代表点未发生变化，则停止。否则转2。第30页/共61页第31页/共61页k-均值均值算法举例算法举例n n彩色图像分割：彩色图像分割：第32页/共61页k-k-均值算法均值算法均值算法均值算法uu1.1.准则函数准则函数误差平方和准则误差平方和准则 uu2.2.样本集初始划分样本集初始划分uu3.3.迭代计算迭代计算第33页/共61页k-均值算法的其他考均值算法的其他考虑虑n n按照与c个代表点的最小距离法对新样本y进行分类，即：n n初始划分的方法n n更新均值的时机：逐个样本修正法与成批样本修正法n n聚类数目的动态决定第34页/共61页nK-算法举例 例：已知有20个样本，每个样本有2个特征，数据分布如下图样本序号样本序号x1x2x3x4x5x6x7x8x9x10特征特征x10101212367特征特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899第35页/共61页第36页/共61页第一步：令K=2，选初始聚类中心为第37页/共61页第38页/共61页n第三步：根据新分成的两类建立新的聚类中心第四步：转第二步。第二步：重新计算 到z1(2),z2(2)的距离，把它们归为最近聚类中心，重新分为两类，第39页/共61页n第三步，更新聚类中心第40页/共61页n第四步，n第二步，n第三步，更新聚类中心第41页/共61页上机作业上机作业n已知十个样本，每个样本2个特征，数据如下：n用K-均值算法分成3类，编程上机，并画出分类图。样本序号样本序号1 2 3 4 5 6 7 8 9 10 x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 6第42页/共61页(2).ISODATA(2).ISODATA 算法算法uuISODATAISODATA算算法法的的功功能能与与k-k-均均值值算算法法相相比，在下列几方面有改进。比，在下列几方面有改进。考考虑虑了了类类别别的的合合并并与与分分裂裂，因因而而有有了了自自我我调调整整类类别别数数的的能能力力。合合并并主主要要发发生生在在某某一一类类内内样样本本个个数数太太少少的的情情况况，或或两两类类聚聚类类中中心心之之间距离太小的情况。间距离太小的情况。算法有自我调整的能力算法有自我调整的能力.第43页/共61页考考虑虑了了类类别别的的合合并并与与分分裂裂，因因而而有有了了自自我我调调整整类类别别数数的的能能力力。合合并并主主要要发发生生在在某某一一类类内内样样本本个个数数太太少少的的情情况况，或或两两类类聚聚类类中中心心之之间距离太小的情况。间距离太小的情况。第44页/共61页(3).样本与聚类间相似性度量样本与聚类间相似性度量n n样本样本x x与聚类与聚类K Ki i间相似性度量间相似性度量:n n聚类的表示：聚类的表示：n n样本集样本集K Ki i =x xj j(i)(i)n n用一个所谓的用一个所谓的“核函数核函数”K Ki i，如样本集的，如样本集的某种统计量某种统计量第45页/共61页(3).样本与聚类间相似性度量样本与聚类间相似性度量n n基于样本与聚类间相似性度量的动态聚类算法1.1.初始化：选择初始化：选择c c个初始聚类个初始聚类K K1 1,K K2 2,K Kc c2.2.建立建立c c个空聚类列表：个空聚类列表：L L1 1,L L2 2,L Lc c3.3.按照最相似法则逐个对样本进行分类：按照最相似法则逐个对样本进行分类：4.4.计算计算J J并用并用 L Li i 更新各聚类核函数更新各聚类核函数 K Ki i 5.5.若若J J不变则停止。否则转不变则停止。否则转2 2第46页/共61页(3).正态核函数的聚类算法正态核函数的聚类算法n n正态核函数，适用于各类为正态分布正态核函数，适用于各类为正态分布uu参数集参数集V Vi i=mmi i,i i 为为各类样本统计参数各类样本统计参数uu相似性度量：相似性度量：第47页/共61页9.3.2 近邻函数准则算法近邻函数准则算法n近邻函数：样本间相似性的度量如果y yi i是是y yj j的第的第I I个近邻，个近邻，y yj j是是y yi i的第的第K K个近邻个近邻 a aij ij=I I+K K 2,2,i i j jn n近邻函数使得密度相近的点容易聚成一类近邻函数使得密度相近的点容易聚成一类n n同一类中的点之间存在同一类中的点之间存在“连接连接”。连接损。连接损失就定义为两点之间的近邻函数失就定义为两点之间的近邻函数a aij ijn n一个点和其自身的连接损失一个点和其自身的连接损失a aii ii=2=2NN，以惩，以惩罚只有一个点的聚类罚只有一个点的聚类n n不同类的点不存在连接，连接损失不同类的点不存在连接，连接损失a aii ii=0=0n n总类内损失：总类内损失：第48页/共61页9.3.2 两类间最小近邻函数值两类间最小近邻函数值n n第i类和第j类间最小近邻函数值定义为：uu第第i i类内最大连接损失记为：类内最大连接损失记为：a ai imaxmaxuu第第i i类与第类与第j j类之间的连接损失定义为类之间的连接损失定义为b bij ij，它的设计目标是：，它的设计目标是：如果两类间的最小近邻值大于任何一方的类内的最大连接如果两类间的最小近邻值大于任何一方的类内的最大连接损失时，损失代价就是正的，从而应该考虑把这两类合并损失时，损失代价就是正的，从而应该考虑把这两类合并第49页/共61页9.3.2 近邻函数准则近邻函数准则n n总类间损失：uu准则函数：准则函数：uu算法步骤：算法步骤：1.计算距离矩阵2.用距离矩阵计算近邻矩阵M3.计算近邻函数矩阵L4.在L 中，每个点与其最近邻连接，形成初始的划分5.对每两个类计算rij 和aimax，ajmax，只要rij 小于aimax、ajmax中的任何一个，就合并两类（建立连接）。重复至没有新的连接发生为止第50页/共61页9.4 分级聚类方法分级聚类方法n n划分序列：划分序列：NN个样本个样本自底向上逐步合并自底向上逐步合并一类：一类：1.1.每个样本自成一类（划分水平每个样本自成一类（划分水平1 1）2.2.K K水平划分的进行：计算已有的水平划分的进行：计算已有的c c=NN-K K+2+2个类的类间个类的类间距离矩阵距离矩阵DD(K K-1)-1)=d dij ij(K K-1)-1)，其最小元素记作，其最小元素记作d d(K K-1)-1)，相应，相应的两个类合并成一类的两个类合并成一类3.3.重复第重复第2 2步，直至形成包含所有样本的类（划分水平步，直至形成包含所有样本的类（划分水平NN）n n划分处于划分处于K K水平时，类数水平时，类数c c=NN-K K+1+1，类间距离矩，类间距离矩阵阵DD(K K)=d dij ij(K K)，其最小元素记作，其最小元素记作d d(K K)n n如果如果d d(K K)阈值阈值d dT T，则说明此水平上的聚类是适，则说明此水平上的聚类是适宜的宜的第51页/共61页分级聚类树表示方法分级聚类树表示方法y1y2y3y4y5y61009080706050401-水平-2-水平-3-水平-4-水平-5-水平-6-水平-第52页/共61页两聚类间的距离度量两聚类间的距离度量n n聚类Ki与Kj间的距离度量 最近距离：最近距离：最远距离：最远距离：均值距离：均值距离：第53页/共61页举例：如下图所示 1.按距离定义层次聚类2.作距离矩阵D(0)第54页/共61页G1G2G3G4G5G29G3116G4491664G5254364G664258119第55页/共61页n3.求最小元素：n4.把G1,G3合并G7=(1,3)G4,G6合并G8=(4,6)n5.作距离矩阵D(1)G7G2G8G29G84916G52544第56页/共61页n6.若合并的类数没有达到要求，转3。否 则停止。n7.求最小元素：n8.G8,G5,G2合并,G9=（2,5,4,6）第57页/共61页10.5 聚类中的问题聚类中的问题n n非监督模式识别问题存在更大的不确定性:可利用信息少n n相似性度量一般对数据尺度相似性度量一般对数据尺度(scale)(scale)较敏感较敏感n n影响聚类结果的因素：样本的分布，样本数量，聚类准则，相似性度量，预分类数等n n针对不同数据，不同目标选择不同的聚类算法n n动态聚类算法计算效率高，实际应用多第58页/共61页习题习题1.1.习题10.52.2.试用流程图描述C-Means算法第59页/共61页谢谢！谢谢！第60页/共61页