第10章-非监督学习方法汇总课件

模 式 识 别 徐蔚然北京邮电大学信息工程学院北京邮电大学信息工程学院本章学习目标本章学习目标 n1.掌握非监督学习方法的概念、用途n2.了解非监督学习方法对数据划分有两种基本方法n3.掌握以c-均值算法，ISODATA算法为代表的动态聚类方法 10.1 引引 言言(什么是无监督学习)n有监督的学习方法n以前讨论的分类器设计方法都是在样本集中的类别标签已知的条件下进行的，这些样本称为训练样本。n在样本标签已知的情况下，可以统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。什么是无监督学习n无监督学习n然而在实际应用中，不少情况下无法预先知道样本的标签，也就是说没有训练样本n因而只能从原先没有样本标签的样本集开始进行分类器设计，这就是通常说的无监督学习方法。n对一个具体问题来说有监督与无监督的作法是不相同的什么是无监督学习n例对路面与非路面分类的两种不同做法 什么是无监督学习n目的:根据像素点颜色对其分类n有监督学习方法n其中左图是在图像中路面区与非路面中各找一个窗口，将其中每个象素分别作为这两类的训练样本集，用这两个样本集在特征空间的分布参数进行设计n无监督学习方法 n它不预先选择样本类别的样本集，而是将整幅图的像素都作为待分类样本集，通过它们在特征空间中表现出来的聚类现象，把不同类别划分开 什么是无监督学习n非监督学习与有监督学习方法的不同点n1 有监督学习方法必须要有训练集与测试样本。而非监督学习没有训练集。n2有监督学习方法的目的就是识别事物，识别的结果表现在给待识别数据加上了标号。因此训练样本集必须由带标号的样本组成。而非监督学习方法只有要分析的数据集本身，预先没有什么标号。什么是无监督学习n非监督学习与有监督学习方法的不同点n3 非监督学习方法在寻找数据集中的规律性，这种规律性并不一定要达到划分数据集的目的，也就是说不一定要“分类”n这一点是比有监督学习方法的用途要广泛 n譬如分析一堆数据的主分量，或分析数据集有什么特点都可以归于非监督学习方法的范畴 无监督学习的应用n计算机视觉n图像分割n基于内容的图像检索n数据挖掘n推荐系统/协同过滤n文本分类无监督学习方法n无监督学习方法可以分成两大类 n一类为基于概率密度函数估计的直接方法n指设法找到各类别在特征空间的分布参数再进行分类 n另一类称为基于样本间相似性度量的间接聚类方法 n其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别 直方图方法 n直方图方法n最常用的基于概率密度估计的直接方法的例子是直方图方法 Otsu thresholdingu灰度图像阈值:可分性判据10.2 单峰子类的分离方法单峰子类的分离方法 n基于概率分布方法中又可分成两种基本方法n一种是从每个分量有无峰谷点表现出来，称为投影法n另一种方法是利用投影，直接找密集区域的方法单峰子类的分离方法n如果对于各类别的类条件概率分布一无所知，我们只按待分类样本在特征空间的自然聚集进行划分。样本在整个特征空间中呈现出两个分布高峰，如果从分布的谷点将此特征空间划分为两个区，则对应每个区域，样本分布就只有一个峰值这些区域被称为单峰区域单峰区域单峰子类的分离方法n如果对于各类别的类条件概率分布一无所知，我们只按待分类样本在特征空间的自然聚集进行划分。落在同一单峰区域的待分类样本就被划分成同一类称为单峰子类单峰子类10.3 聚类方法n本节讲的按相似度进行划分的方法n如果把相似度表示成在特征空间中的某种距离度量,这种方法又称为基于距离度量的方法。n与前一种方法相比，它不是以计算密度程度为依据的，因此这是这两种方法的主要区别。聚类方法n基于概率密度函数估计 n把一个具有混合概率密度函数的集合分解为若干个子集 n对每个子集来说，其概率密度函数分布都是单峰的，每个子集就相当于一个类 n这种方法需要对概率密度函数作出估计，这往往是比较困难的 聚类方法 n聚类方法 n不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类，这种方法称为聚类方法 n如何聚类则取决于聚类的准则函数，以使某种聚类准则达到极值为最佳。聚类方法n例 使用聚类方法实现道路识别 10.3.1动态聚类方法n动态聚类方法的任务n将数据集划分成一定数量的子集n例如将一个数据集划分成三个子集，四个子集等。n要划分成多少个子集往往要预先确定，或大致确定n这个子集数目在理想情况下能体现数据集比较合理的划分n这里要解决的问题是:n1 怎样才能知道该数据集应该划分的子集数目n2 如果划分数目已定，如何找到最佳划分10.3.1动态聚类方法n因为数据集可以有许多种不同的划分方法，需要对不同的划分作出评价，并找到优化的划分结果。n由于优化过程是从不甚合理的划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法动态聚类方法n 我们先讨论在子集数目已定条件下的聚类方法，然后讨论如何确定合理的子集数目 动态聚类方法基本要点n动态聚类方法基本要点 动态聚类方法基本要点n动态聚类方法基本要点n1.选定某种距离度量作为样本间的相似性度量；n2.确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等。n3.确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。n具体算法C-均值算法n准则函数误差平方和准则 n这个准则函数是以计算各类均值mi，与计算各类样本到其所属类均值点误差平方和为准则，若各类均值表示成n其中第i类集合为i，其样本数目为Ni,y是样本特征向量n此时误差平方和准则可表示成 C-均值算法n样本集初始划分n初始划分的一般作法是先选择一些代表点作为聚类的核心，然后把其余的样本按某种方法分到各类中去n注n通过迭代方法求极值的一个普遍问题是局部极值与全局极值问题，c-均值算法等动态聚类方法中也有类似问题n在这种情况下初始值的选择就会对最终达到那一个极值有决定性影响n因此c-均值算法的初始划分也是一个重要环节n一般通过一些启发式方式来确定初始划分 C-均值算法n样本集初始划分 n代表点的几种选择方法：n(1)凭经验选择代表点:根据问题的性质，用经验的办法确定类别数，从数据中找出从直观上看来是比较合适的代表点。n(2)将全部数据随机地分为C类，计算各类重心，将这些重心作为每类的代表点C-均值算法n样本集初始划分 n代表点的几种选择方法：n(3)“密度”法选择代表点n这里的“密度”是具有统计性质的样本密度 n在得到样本“密度”后，选“密度”为最大的样本点作为第一个代表点 n然后人为规定距该代表点d1距离外的区域内找次高“密度”的样本点作为第二个代表点 n依次选择其它代表点，使用这种方法的目的是避免代表点过分集中在一起 C-均值算法n样本集初始划分 n代表点的几种选择方法：n(4)从(c-1)聚类划分问题的解中产生C聚类划分问题的代表点n先从一类聚类的解找两聚类划分的代表点,再依次增加一个聚类代表点。n对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成两聚类的代表点。n依同样方法，对已有(c-1)个聚类代表点(由(c-1)个类均值点组成)找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第c个代表点。C-均值算法n样本集初始划分n在选定代表点后要进行初始划分，下面列出几种确定初始划分的方法 n样本集初始划分n(1)对选定的代表点按距离最近的原则将样本划属各代表点代表的类别。n(2)在选择样本的点集后，将样本按顺序划归距离最近的代表点所属类，并立即修改代表点参数，用样本归入后的重心代替原代表点，因此代表点在初始划分过程中作了修改。C-均值算法n样本集初始划分n样本集初始划分n(3)一种既选择了代表点又同时确定了初始划分的方法n(4)先将数据标准化,再按照某个指标平均分布样本C-均值算法n迭代计算nc-均值算法的迭代计算过程在原理上与梯度下降法是一样的n即以使准则函数值下降为准则。n但是由于c-均值算法的准则函数值由数据划分的调整所决定，因此只能通过逐个数据从某个子集转移到另一子集计算准则函数值是否降低为准则 C-均值算法n迭代计算方法n如果原属第k类中的一个样本y从k类移入j类时，它会对误差平方和产生影响nk类在抽出样本y后用，其相应均值为nj类在加入样本y后用，其相应均值为C-均值算法n迭代计算方法nk类在抽出样本y后用，其误差平方和 nj类在加入样本y后用，其误差平方和 C-均值算法n迭代计算方法n如果满足下式，则表明样本变动是合乎准则要求的。C-均值算法nC均值算法 综上所述C均值算法可归纳成：n(1)选择某种方法把N个样本分成C个聚类的初始划分，计算每个聚类的均值和误差平方和jc n(2)选择一个备选样本y，设其在第i类n(3)若Ni=1，则转(2)，否则继续 C-均值算法nC均值算法n(4)计算 n(5)对于所有的j，若ej最小，则把y放入第j类 C-均值算法nC均值算法n(6)重新计算第i，j类的均值和jcn(7)若连续迭代N次(即所有样本都运算过)不变，则停止，否则转到2。n上述C均值算法都是在类别c已知条件下进行的，在类别数未知情况下使用C均值算法时，可以假设类别数是逐步增加的，例如对c1，2，3，分别使用该算法 C-均值算法nC均值算法n显然准则函数jc是随c的增加而单调地减少n如果样本集的合理聚类数为c类，当类别数继续增大时，相当于将聚类很好的类别又分成子类，则值虽然继续减少但会呈现平缓趋势n如果作一条jc值随c变化的曲线，如下图所示，则其拐点对应的类别数就比较接近于最优聚类数。C-均值算法nC均值算法c3是较合适的聚类数 但是并非所有的情况都能找到明显的转折点。ISODATA算法nc-均值算法的一个主要问题 n划分类别数必须事先确定 n主观确定数据子集数目并不一定符合数据集自身的特点 nISO-DATA算法,将硬性确定聚类数目改成给出这个数目的期望值，作为算法的一个控制量。在算法中又加上分类与合并机制，因而能使聚类结果比较适应数据集的内在特性。n对于ISODATA算法只要求大体看懂ISODATA算法nISODATA算法的功能与C均值算法相比，在下列几方面有改进n1.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。n合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。n为此设有最小类内样本数限制N，以及类间中心距离参数c。若出现两类聚类中心距离小于的情况c，可考虑将此两类合并。ISODATA算法n分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。n给出一个对类内分量方差的限制参数s，用以决定是否需要将某一类分裂成两类。n2.由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K、每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。ISODATA算法nISODATA算法的步骤 n步骤1(确定控制参数及设置代表点)需确定的控制参数为：K：聚类期望数；QN:一个聚类中的最少样本数 s:标准偏差控制参数，用于控制分裂 c:类间距离控制参数，用于控制合并 L：每次迭代允许合并的最大聚类对数；I：允许迭代的次数。设初始聚类数为c及聚类中心 ISODATA算法n步骤2(分类)n对所有样本，按给定的c个聚类中心，以最小距离进行分类n步骤3(撤消类内样本数过小类别)n步骤4(更新均值向量)n步骤5(计算类内平均距离)n步骤6(计算整个样本集偏离均值的平均距离)ISODATA算法n步骤7(入口选择)n如这是最后一次迭代(取决于I)，则转步骤11 n如果CK/2，则转向步骤8，执行分裂步骤；n如果c2K，则转向步骤11，执行合并步骤。n步骤8(求各类内各分类标准偏差)n步骤9(求每类具有最大标准偏差的分量)n步骤10(分裂计算步骤)n步骤11(计算类间聚类中心距离)ISODATA算法n步骤12(列出类间距离过近者)n步骤13(执行合并)n步骤14(结束步骤)10.3.2分级聚类方法分级聚类方法 n分级聚类方法要解决的问题 n分级聚类方法的目的:把样本集按不同的相似程度要求分成不同类别的聚类n两种极端情况:n每个样本各自为一类，N个样本共有N类n另一极端则是将所有样本归一类n在这两个极端之间的是类别数从N逐渐减少，每类的数量相应增加，而类内样本的相似程度要求也随之下降 分分级级聚聚类类方方法法分级聚类方法分级聚类方法n聚类的相似性度量方法 n1.最近距离 n2.最远距离 n3.均值距离 分级聚类方法分级聚类方法n分级聚类算法步骤 n初始时每个样本自成一类 n步骤1:在集合中找到一对满足条件类别n步骤2:类别合并n步骤3:把i从指标集I中除掉，若I的基数仅等于2时，则终止计算，否则转向步骤1分分级级聚聚类类方方法法最近距离分分级级聚聚类类方方法法最远距离10.4非监督学习方法中的一些问非监督学习方法中的一些问题题 n影响到分类的结果的因素n点集的数据构造、被分析的点集中样本点的数量、所采用的距离度量和相似性度量、所用的聚类准则，以及最终的聚类数都会影响到分类的结果n样本各分量之间的尺度比例的确定也是十分重要的问题