模式识别与机器学习 课件 第5、6章 其他分类方法、无监督学习和聚类

其他分类方法第五章模式识别与机器学习新工科建设·人工智能与智能科学系列教材01近邻法近邻法使用最简单的分段线性分类器将各个类划分为若干子类。以子类的中心作为类代表点，考察新样本到各代表点的距离，据此将其分给最近代表点所代表的类。近邻法最近邻法最近邻法将与测试样本最近的类作为决策结果。假设在c类问题中，抽样试验样本集为X={x1，x2，…，xN}。1-NN规则为近邻法式中，D（x，xki）是样本x到类ωi的第k个样本的距离，这个距离一般采用欧氏距离，也可采用其他距离。这个规则表明，只要样本x到某个类的某个样本的距离最近，就将样本x分给该类，也就是说，将样本xki分给离它最近的那个样本对所属的类ωi，因此又称最近邻判别规则。近邻法近邻法不难将1-NN规则推广到k-NN规则。在5.1.1节的条件下，对每个待分类的样本x，找出k个最近邻，它们分别属于c个类。令k=k1+k2+…+kc，其中k1为类ω1的样本数，k2为类ω2的样本数……kc为类ωc的样本数，于是k-NN规则为近邻法简单地说，就是将样本x分给k个最近邻中的多数所属的那个类。在实际应用中，往往规定这个多数不能低于某个最低数，否则就拒绝判别而将该样本x排除。这种判别规则又称k近邻判别规则。近邻法可以看出，为了执行近邻法分类，需要将已分类的样本集X={x1，x2…xn}存入计算机；对每个待分类的样本x，要求计算x到样本集x中的所有样本的距离，然后进行距离比较。为了减小错误率，要求n很大，这就使得这种分类方法的存储量和计算量都很大。近邻法距离度量特征空间中两个实例点的距离是两个点的相似度的反映。k近邻模型的特征空间一般是n维实数向量空间Rn，使用的距离是欧氏距离，但也可使用其他距离，例如更一般的Lp距离，近邻法01k值的选择k值的选择对结果有很大的影响。03kd树为了提高k近邻搜索的效率，减少计算距离的次数，k近邻算法一般采用kd树来存储训练数据。02决策规则k近邻分类决策规则往往是多数表决，即由输入实例的k个近邻训练实例中的多数类决定输入实例的类。近邻法02逻辑斯蒂回归一般情况下，我们关心的变量可能与多个自变量有关，这就是多元线性回归问题，即y=w0+w1x1+…+wnxn+b。其中y是我们要回归的变量，b是回归的残差，即用x的线性函数w0+w1x1+…+wnxn估计y带来的误差。逻辑斯蒂回归系数wi的直观解释是，当其他因素不变时，特征xi增加一个单位给y带来的变化。然而，在模式识别问题中，我们关心的是分类，譬如是否患某种病，这时不能用简单的线性回归方法研究特征与分类之间的关系。逻辑斯蒂回归考虑两分类任务。设x∈R是样本的特征，y∈{0，1}是样本的类标记，在这种情况下，很难用一个线性模型来表示y和x之间的关系。但是可以找到一个函数将分类任务的真实标记y与线性回归模型的预测值联系起来，即将线性回归模型产生的预测值z=wTx+b转换为两分类的0/1值。逻辑斯蒂回归逻辑斯蒂函数的图像如图5.4所示。逻辑斯蒂回归03决策树与随机森林决策树是一种十分常用的分类方法。决策树是一个预测模型，代表对象属性与对象值之间的一种映射关系。通常使用ID3、C4.5和CART等算法生成树。决策树与随机森林非数值特征：定名特征只能比较相同/不同，无法比较相似性/大小。例如，颜色、形状、性别、民族、职业、字符串中的字符、DNA序列中的核酸类（A、C、G、T）等。决策树与随机森林定序特征一种数值，可能有顺序，但不能视为欧氏空间中的数值，如序号、分级等。决策树与随机森林定距特征与研究目标之间呈非线性关系的数值特征，需要分区段处理，可以比较大小，但没有“自然的”零，如年龄、考试成绩、温度等。决策树与随机森林决策树决策树是类似于流程图的树形结构，其中树的每个内部节点代表对一个属性（取值）的测试，每个分支代表测试的一个结果，每个叶节点代表一个类。树的最高层节点是根节点。决策树与随机森林图5.5所示为示意性决策树，它描述的是购买电脑的分类模型，利用它可对一名学生是否在商场购买电脑进行分类预测。决策树的中间节点常用矩形表示，而叶节点常用椭圆表示。决策树与随机森林为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属性值进行测试。从决策树的根节点到叶节点的一条路径，形成对相应对象的类预测。决策树可以很容易地转换为分类规则。决策树与随机森林下面的算法5.1是学习构造决策树的一个基本归纳算法。构造决策树时，有许多由数据集中的噪声或异常数据产生的分支。树枝修剪（TreePruning）是指识别并消除这类分支，以帮助改善对未知对象分类的准确性。决策树与随机森林属性选择方法在决策树归纳方法中，通常使用信息增益方法来帮助确定生成每个节点时所应采用的合适属性。这样，就可以选择具有最高信息增益（熵减少的程度最大）的属性作为当前节点的测试属性，以便分类之后划分得到训练样本子集时所需要的信息最小。决策树与随机森林也就是说，利用该属性进行当前（节点所含）样本集划分，会使得产生的各样本子集中的“不同类混合程度”降至最低。因此，采用这样一种信息论方法可以有效减少对象分类所需的次数，确保产生的决策树最简单，尽管不一定是最简单的。决策树与随机森林设S是一个包含s个数据样本的集合，且类属性可以取m个不同的值，它们对应于m个不同的类Ci，i∈{1，2，3，…，m}。假设si为类Ci中的样本数。于是，对一个给定数据对象进行分类所需的信息量为决策树与随机森林式中，pi是任意一个数据对象属于类Ci的概率，可按si/s计算；之所以出现以2为底的对数，是因为在信息论中信息都是按位进行编码的。设属性A取v个不同的值{a1，a2，a3…，av}。决策树与随机森林过学习与决策树的剪枝决策树建立后，许多分支都是根据训练样本集中的异常数据构造出来的。树枝修剪就是针对这类数据的过拟合问题而提出的。树枝修剪方法通常利用统计方法删去最不可靠的分支（树枝），以提高分类识别的速度和分类识别新数据的能力。决策树与随机森林事前修剪（Prepruning）方法：该方法提前停止分支生成过程，即在当前节点上判断是否需要继续划分该节点所含的训练样本集。一但停止分支，当前节点就成为一个叶节点，该叶节点中可能包含多个不同类的训练样本。决策树与随机森林在建造一棵决策树时，可以利用卡方检验或信息增益等来对分支生成情况（优劣）进行评估。在一个节点上划分样本集时，如果节点中的样本数少于指定的阈值，就要停止分解样本集。然而，确定这样一个合理的阈值通常比较困难。阈值过大会使得决策树过于简单化，阈值过小又会使得多余的树枝无法修剪。决策树与随机森林事后修剪（Postpruning）方法该方法从一棵“充分生长”树中修剪掉多余的树枝（分支）。基于代价成本的修剪算法就是一种事后修剪方法。被修剪（分支）的节点成为一个叶节点，并标记为其所包含样本中类数最多的类。决策树与随机森林对于树中的每个非叶节点，计算出该节点（分支）被修剪后所发生的预期分类错误率，同时根据每个分支的分类错误率及每个分支的权重（样本分布），计算该节点不被修剪时的预期分类错误率。如果修剪导致预期分类错误率变大，就放弃修剪，保留相应节点的各个分支，否则就将相应的节点分支剪掉。决策树与随机森林产生一系列经过修剪的决策树候选后，利用一个独立的测试数据集对这些经过修剪的决策树的分类准确性进行评价，保留预期分类错误率最小的（修剪后）决策树。除了利用预期分类错误率进行决策树修剪，还可利用决策树的编码长度来修剪决策树。所谓最佳修剪树，是指编码长度最短的决策树。决策树与随机森林该修剪方法利用最短描述长度（MinimumDescriptionLength，MDL）原则来修剪决策树，基本思想是：最简单的就是最好的。与基于代价成本的方法相比，利用MDL进行决策树修剪不需要额外的独立测试数据集。当然，事前修剪可以与事后修剪相结合，可以构成混合修剪方法。事后修剪比事前修剪需要更多的计算时间，因此可以获得更可靠的决策树。决策树与随机森林随机森林基于数据结构的模式识别方法面临着一个共同的问题，即数据的随机性问题。该方法的任何一次实现都是基于一定数据集的，这个数据集只是所有可能数据中的一次随机抽样。决策树与随机森林很多方法的结果受这种随机性的影响，训练得到的分类器也有一定的偶然性，当样本量比较少时，情况更是如此。在训练过程中，决策树根据每个节点下的局部划分准则进行学习，受样本随机性的影响可能更大一些，容易导致过学习。决策树与随机森林随机森林是指建立很多决策树，组成决策树的“森林”，通过多棵树投票来进行决策。理论和试验研究都表明，这种方法能够有效提高对新样本的分类准确度，也就是推广能力。决策树与随机森林04小结本章首先简要介绍了近邻法、逻辑斯蒂回归、决策树与随机森林，然后介绍了为快速求解近邻法而构造kd树的详细过程。以及逻辑斯蒂回归的原理和过程；最后描述了构造决策树的算法过程。小结无监督学习和聚类第六章模式识别与机器学习新工科建设·人工智能与智能科学系列教材01引言前面在设计分类器时，一直假设训练样本集中每个样本的类标记都是已知的。这种利用已标记样本集的方法称为监督方法。本章介绍一些无监督方法，以处理未被标记样本类的样本集。引言收集并标记大型样本集是件非常费力的事情，如果能够首先在一个较小的样本空间中粗略地训练一个分类器。然后让它自适应地处理大量的无监督样本，我们就可节省大部分时间和精力。引言此外，在一些应用中，因为我们往往不知道数据的具体情况，所以首先要用大量未标记的数据集自动地训练分类器，然后人工地标记数据分组的结果。这些问题都需要我们在未知样本标记的情况下建立一个分类器，以对样本集中的数据做一定的分类，或者得到样本集中数据的某种基本特征。引言02混合模型的估计无监督最大似然估计考虑由n个样本组成的样本集D={x1，x2…，xn}，这些样本都是未标记的，且是独立地对一个混合密度采样得到的。这个混合密度为混合模型的估计式中，参数向量θ具有确定但未知的值。于是，样本集的似然函数就具有如下联合概率密度形式：使得该密度函数最大的参数值^θ就是θ的最大似然估计值。混合模型的估计正态分布下的无监督参数估计在很多情况下，我们都假设样本服从正态分布。在聚类分析中引入混合模型后，样本服从混合正态分布。分布的每个分量密度都是多元正态分布的，即p（x|ωi，θi）~N（μi，∑i）。混合模型的估计在混合正态分布的参数估计中，我们将引出几种不同情况下的参数估计：第一种是只有均值向量是未知的，而方差向量和类的先验知识是已知的。第二种是只有样本集中数据所属的类数是已知的，而每个类分布的均值、方差、类先验知识都是未知的；第三种是，第二种情况下样本集中数据所属的类数也是未知的。混合模型的估计03动态聚类算法在聚类分析中，动态聚类算法被普遍采用，该算法首先选择某种样本相似性度量和适当的聚类准则函数。使用迭代算法，在初始划分的基础上逐步优化聚类结果，使准则函数达到极值。动态聚类算法对于动态聚类算法，要解决的关键问题如下。02代表点选好后，如何将所有样本区分到以代表点为初始聚类中心的范围内，形成初始划分，是算法的另一个关键问题。01首先选择有代表性的点作为起始聚类中心。动态聚类算法均值聚类算法c均值聚类算法使用的聚类准则函数是误差平方和准则Jc：动态聚类算法式中，X={xi，i=1，2，…，N}是所给样本集的N个样本，rkj表示样本xk是否被分配到以m为聚类中心的聚类中。M={mj，j=1，2，…，K}是需要求解的c个聚类中心。为了优化聚类结果，应使准则Jc最小。动态聚类算法ISODATA聚类算法ISODATA算法：英文全称为IterativeSelf-OrganizingDataAnalysisTechniquesAlgorithm，中文全称为迭代自组织数据分析技术算法。ISODATA算法的特点：可以通过类的自动合并与分裂得到较合理的类数c。动态聚类算法ISODATA算法的流程框图如图6.4所示。动态聚类算法04层次聚类算法凝聚的层次聚类算法自底向上的层次聚类过程是相似类之间的凝聚过程。它首先将每个对象作为一个类，然后将这些类合并为越来越大的类，直到所有样本都在同一个类中，或者满足某个终止条件。层次聚类算法分裂的层次聚类算法分裂的层次聚类算法与凝聚的层次聚类算法相反。这种算法采用自顶向下的策略，首先将所有样本设为同一个类，然后逐渐细分为越来越多的小类，直到每个样本都自成一个类，或者达到某个终止条件。层次聚类算法图6.5显示了凝聚和分裂的层次聚类。层次聚类算法05谱聚类谱聚类是一种基于图论的聚类方法，它使用关联矩阵的谱分解所传达的信息，选择合适的特征向量聚类不同的数据点。聚类算法将数据集中的每个样本都视为图的一个顶点V，将顶点间的相似性度量作为相应顶点连接边E的权值。谱聚类到一个基于相似度的无向加权图，进而将聚类问题转化为图的划分问题。基于图论的最优划分准则使得所划分的子图内部相似度最大，子图之间的相似度最小。谱聚类如图6.6所示，最小划分准则会使得两个聚类被虚线分开，但实线是更优的划分。谱聚类06模糊聚类方法前几章中介绍的聚类算法主要分为两大类。一类算法根据已知样本分布概率密度的基本形式来估计概率密度的各个参数，使得某个样本以一定的概率属于某个类，如高斯混合模型；另一类算法不使用概率密度，但每个样本都确定地属于某个类，而在其他类中没有分布，如c均值聚类。模糊聚类方法基于概率的聚类方法的难点是，使用概率密度函数时要假设合适的模型，不易处理聚类不致密的情形。对于c均值聚类来说，确定地将某个样本归入某个类可能会引入错误。模糊聚类算法可以摆脱这些限制。模糊聚类方法模糊集基本知识模糊集的定义如下：设U是一个论域，U到区间[0，1]的一个映射μ：U→[0，1]确定U的一个模糊子集A。映射μ称为A的隶属函数，记为μA（u）。对于任意u∈U，μA（u）∈[0，1]称为u属