机器学习算法与实践 课件 第3、4章 K近邻、贝叶斯

第三章K近邻K-近邻算法（K-NearestNeighbor，KNN）是一种基于一定距离测度的抽样检验方法，属于监督学习，所以使用算法时必须有已知标记的训练集。K-近邻算法既可用于分类也可用于回归。在处理分类问题时，该方法只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别。处理回归问题的流程与分类问题相似，区别在于样本的输出标记为距离其最近的一个或者几个样本的标记的加权平均值。13.1算法原理在分类问题中，给定一个训练数据集，对于任何一个待分类样本，在训练数据集中找到与该样本最邻近的K个样本（也就是最近的K个邻居），那么即可以使用这K个样本中的多数类别标记作为待分类样本的类别标记。特别的，必须保证训练数据集中的每个样本都有类别标记。在回归问题中，样本的标记为连续变量，因此一般将待处理样本的K个最近邻的标记的加权平均值作为输出（以距离的倒数为权重）。除此之外，还可以指定一个半径，将半径范围内的全部邻居的标记的加权平均值作为输出。23.1算法原理图中的样本有两个类别，分别以正方形和三角形表示，而图正中间的圆形代表待分类样本。

首先假设我们选择K的值为3，圆形样本最近的3个邻居是2个三角形和1个正方形，少数从属于多数，基于统计的方法，判定这个待分类样本属于三角形一类。

如果我们选择K的值为5，那么圆形样本最近的5个邻居是2个三角形和3个正方形，还是少数从属于多数，可以判定这个待分类点属于正方形一类。33.1算法原理K-近邻算法的基本流程为：1）计算已经正确分类的数据集中每个样本与待分

类样本之间的距离；2）按照距离递增次序对数据集中的样本排序；3）选取与待分类样本距离最小的K个样本；4）确定该K个样本所在类别的出现频率；5）返回该K个样本出现频率最高的类别作为待分

类样本的预测类别。43.1算法原理K值的选择会对算法的结果产生重大影响：K值较小意味着只有与待分类样本较近的已知样本才会对预测结果起作用，但容易发生过拟合K值较大可以减少学习的估计误差，但是学习的近似误差增大，因为这时与待分类样本较远的已知样本也会对预测起作用，容易使预测发生错误。K值一般选择一个奇数值，因为算法中的分类决策规则往往是多数表决，奇数取值可防止出现邻居中不同类别样本数量相等的情况。53.2距离度量方法

在K-近邻算法以及其他很多机器学习算法中都会涉及到距离的计算，距离度量方式对算法的性能有很大的影响。

常用的距离计算方式如下： 1.闵科夫斯基距离（Minkowskidistance） 2.欧几里德距离（Euclideandistance） 3.曼哈顿距离（Manhattandistance） 4.切比雪夫距离（Chebyshevdistance） 5.余弦相似度（Cosinesimilarity） 6.皮尔逊相关系数（Pearsoncorrelationcoefficient） 7.杰卡德相似系数（Jaccardsimilaritycoefficient） 8.马氏距离（Mahalanobisdistance）6

3.2距离度量方法

7

3.2距离度量方法

8

3.2距离度量方法

9

3.2距离度量方法

10

3.3搜索优化方法

当数据集和特征数量较大时，K-近邻算法的距离计算成本可能会较高。在近邻搜索的过程中，算法会有较高的计算成本。因此，为了提高K-近邻算法的搜索效率，可以考虑使用特殊的结构来存储已知样本，以减少距离计算的次数。11

3.3.1

k-d树 k-d树（k-dimensionalTree）是针对暴力搜索效率低下而提出的基于树的数据结构。

基本思想：若A点距离B点非常远，B点距离C点非常近，可知A点与C点很远，因此不需要准确计算它们之间的距离。通过这种方式，对于具有k个特征的n个样本来说，近邻搜索的计算成本可以降低至O[knlog(𝑛)]以下，可以显著改善暴力搜索在大样本容量数据集中的表现。12

3.3.1

k-d树例1：假设数据集有2个特征、6个样本，如T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}。使用k-d树算法确定样本点的划分空间分割线。

13

3.3.1

k-d树首先，选择划分特征，即确定分割线是垂直于X轴还是Y轴。分别计算X轴和Y轴方向样本的方差，得知X轴方向的方差最大，所以首先对X轴进行划分，确定分割线的X轴坐标。然后基于上述步骤，对Y轴进行同样划分操作。14

3.3.1

k-d树最后，对依然有样本存在的子空间再按X轴进行划分，直至子空间不再有样本为止。由于此时的每个子空间仅包含一个样本，因此可直接按剩余样本划分空间区域。15

3.3.1

k-d树k-d树的构建过程可以总结为：1）构造根结点，使根结点对应于k维空间中包含所有样本点的超矩形区域；2）通过递归的方法，不断地对k维空间进行切分，生成子结点。3）重复上述过程直到子区域内没有样本时终止。在此过程中，将样本保存在相应的结点上。4）通常，循环的依次选择坐标轴对空间切分。16

3.3.1

k-d树构建k-d树时，关键需要解决2个问题：1）选择向量的哪一维进行划分？2）如何划分数据？对于第一个问题，简单的解决方法可以是随机选择某一维或按顺序选择，但是更好的方法应该是在数据比较分散的那一维进行划分。好的划分方法可以使构建的树比较平衡，可以每次选择中位数来进行划分，这样第二个问题也得到了解决。17

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

18

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

接着，由于被搜索点的划分维度值3小于当前节点的划分维度的值7，因此将当前节点的左子节点(5,4)作为新的当前节点。由于此时当前节点到被搜索点的距离为2.83，小于全局最短距离，所以更新当前最佳点为(5,4)。19

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

继续下去，由于被搜索点的划分维度值2小于当前节点的划分维度值4，因此设当前节点的左子节点(2,3)为新的当前节点。由于此时当前节点到被搜索点的距离为1.41，小于全局最短距离，所以更新当前最佳点为(2,3)，全局最短距离为1.4120

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

21

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

22

3.3.2球树 k-d树算法虽然提高了K-近邻算法的搜索效率，但在处理非均匀数据集和高维数据时也会出现效率不高的情况。为了优化k-d树的算法策略，提出了球树模型。

球树将数据递归地划分为由质心c和半径r定义的节点，每个结点本质上是一个空间，包含了若干个样本点，每个空间内有一个独一无二的中心点23

3.3.2球树

24

3.3.2球树

首先建立根节点，找到包含所有样本点的超球体，记录球心位置，作为根节点。然后，找到所有点中距离最远的两个点，并判断其他样本点与这两个点的距离，距离哪个点最近，则将该样本点划分到该点的类内，这两个类即是根节点的左子节点和右子节点。分别对两个子节点构建超球体，记录球心坐标和半径。25

3.3.2球树重复上述过程直至样本全部划分完毕26

3.4本章小结本章主要介绍了K-近邻算法，给出了其在处理分类和回归问题时的原理和流程，并介绍了k-d树和球树两种提升K-近邻搜索效率的方法。K-近邻算法简单易懂且实用，但是因为每一次分类或者回归，都要把已知数据样本和测试样本的距离全部计算一遍并搜索其中最近的K个邻居，在数据量和数据维度很大的情况下，需要的计算资源会十分巨大，因此会出现效率不高的现象。使用k-d树和球树两种方式可以提升K-近邻算法的搜索效率。k-d树是每个节点都为k维点的二叉树，所有非叶节点可以视作用一个超平面把空间分割成两个半空间，其在数据维度较高而样本数量又相对较少的情况下表现不佳。而球树则沿着一系列球体来分割数据，虽然球树构建数据结构的时间花费大于k-d树，但在高维数据上表现得很高效。27第四章贝叶斯贝叶斯系列算法是基于贝叶斯定理和概率统计原理的一类算法。它们通过对特征之间的条件概率进行建模，从而进行分类、回归、聚类等任务。贝叶斯模型作为一种重要的机器学习模型已在数据挖掘、计算机视觉、自然语言理解、经济统计与预测等领域得到广泛应用。贝叶斯系列算法在处理小样本问题、噪声数据以及不确定性建模方面具有优势，并且能够有效利用先验知识进行模型推理与预测。284.1贝叶斯方法概述贝叶斯方法提供了一种基于主观概率的数理统计分析方法，使用概率分布表示和理解样本数据，根据样本的先验概率分布和训练样本的标记数据计算出相应的后验概率分布，以贝叶斯风险为优化目标实现对样本数据的分类或回归。294.1.1贝叶斯公式

304.1.1贝叶斯公式假设模型参数的各取值状态互不相容，则可根据全概率公式得到概率P(X)。

因此可求得314.1.1贝叶斯公式

即后验概率=先验概率×样本信息。324.1.2贝叶斯决策理论贝叶斯决策具体步骤：1）定义决策空间：确定可供选择的决策及其可能的结果。2）确定先验概率：对每个可能的结果（即条件）估计先验概率。先验概率可以基于经验或专家知识进行估计。3）观测到证据：收集到与决策相关的证据或观测数据。4）计算后验概率：根据贝叶斯定理，将先验概率和观测到的证据相结合，计算各个条件下的后验概率。5）选择最优决策：根据后验概率，选择具有最大后验概率的决策，作为最优的决策。334.1.3极大似然估计极大似然估计具体步骤：1）确定概率分布模型：假设观测数据符合某个特定的概率分布模型，如正态分布、伯努利分布等。2）建立似然函数：将观测数据看作是参数的函数，构建似然函数。似然函数表示给定参数值下观测数据出现的概率。3）最大化似然函数：找到使似然函数取得最大值的参数值，即寻找最大似然估计。通常使用优化算法，如梯度下降法或牛顿法，求解似然函数的最大值点。4）得出估计值：最大似然估计得到的参数值即为所要求的估计值。344.1.3极大似然估计

354.2朴素贝叶斯算法

朴素贝叶斯算法的核心思想是根据给定的特征向量，通过计算后验概率来确定该样本属于不同类别的概率，然后选择具有最大后验概率的类别作为分类结果。364.2朴素贝叶斯算法

条件概率分布为

374.2朴素贝叶斯算法

朴素贝叶斯法对条件概率分布作了条件独立性的假设

384.2朴素贝叶斯算法后验概率计算根据贝叶斯定理可表示为

394.2.1高斯朴素贝叶斯

高斯朴素贝叶斯算法是一种基于贝叶斯定理和特征独立性假设的分类算法，适用于处理连续特征的分类问题。

404.2.1高斯朴素贝叶斯

对于一个新的测试样本，算法先计算该样本在每个类别下的后验概率。使用高斯分布的概率密度函数，算法计算每个特征值在给定类别下的对数似然。然后，将先验概率和对数似然相加得到后验概率。最后，选择具有最大后验概率的类别作为预测结果。41

高斯朴素贝叶斯算法的优势在于它对于大规模数据集具有较高的训练和预测效率，并且对于缺失数据的处理比较鲁棒。然而，它的一个主要限制是它假设特征之间是独立的，这在某些实际问题中可能不符合实际情况，因此其结果可能受到特征相关性的影响。4.2.2多项式朴素贝叶斯

多项式朴素贝叶斯假设每个特征的出现次数是由多项分布生成的，即特征的计数符合多项分布。根据先验概率和条件概率计算每个类别的后验概率，并选择具有最大后验概率的类别作为预测结果。

对于每个测试样本，算法会计算特征的计数，并使用条件概率计算后验概率。424.2.3伯努利朴素贝叶斯

伯努利朴素贝叶斯算法的主要思想是将文档表示为二进制特征向量，其中每个特征表示单词或特定的文本属性是否出现。因此每个特征的取值是布尔型的，即true和false，或者1和0。它基于一个关键假设，即每个特征在给定类别下是条件独立的。

在训练过程中，遍历类别和特征，并根据特征是否存在来根据贝叶斯公式计算后验概率。最后选择具有最大后验概率的类别作为预测结果。434.3半朴素贝叶斯算法

半朴素贝叶斯算法的核心思想是，适当考虑一部分属性间的相互依赖信息。假设给定某个类别的条件下，特征之间的相关性可被一些选定的特征表示。

相比于传统的朴素贝叶斯算法，半朴素贝叶斯算法考虑了特征之间的相关性，可以更准确地捕捉数据中的复杂关系。并且该算法允许根据具体问题选择不同的核心特征和配对特征组合，可以适应不同类型的数据集和任务需求444.3半朴素贝叶斯算法独依赖估计（One-DependentEstimator，ODE）是半朴素贝叶斯分类器最常用的一种策略。独依赖是假设每个属性在类别之外最多依赖一个其他属性，即：

454.3半朴素贝叶斯算法

相比于传统的朴素贝叶斯算法，半朴素贝叶斯算法考虑了特征之间的相关性。这使得模型可以更准确地捕捉数据中的复杂关系。半朴素贝叶斯算法允许根据具体问题选择不同的核心特征和配对特征组合。这种灵活性使得算法可以适应不同类型的数据集和任务需求。此外，半朴素贝叶斯算法在处理高维数据时表现出较好的性能，因为它可以通过选择核心特征和相关特征来减少特征空间的维度。

但是，在半朴素贝叶斯算法中，仍然假设给定类别下的特征是相互独立的。然而，在实际问题中，特征之间通常存在一定的依赖关系。为了解决这个问题，可以引入更复杂的模型，如贝叶斯网络、树模型等，以捕捉特征之间的依赖性。464.4贝叶斯网络算法贝叶斯网络（BayesianNetworks）也被称为信念网络（BelifNetworks）或者因果网络（CausalNetworks），是描述数据变量之间依赖关系的一种图形模式，是一种用来进行推理的模型。贝叶斯网络为人们提供了一种方便的框架结构来表示因果关系。474.4.1贝叶斯网结构

在贝叶斯网结构中，一条弧由一个属性A指向另外一个属性B说明属性A的取值可以对属性B的取值产生影响，由于是有向无环图，A、B间不会出现有向回路。在贝叶斯网当中，直接的原因结点（弧尾）A叫做其结果结点（弧头）B的双亲结点（parents），B叫做A的孩子结点（children）。如果从一个结点X有一条有向通路指向Y，则称结点X为结点Y的祖先（ancestor），同时称结点Y为结点X的后代（descendent）。484.4.1贝叶斯网结构高油高糖饮食（X1）糖尿病（X2）高血脂（X3）心脏病（X4）

左图中共有四个结点和四条弧。高油高糖饮食X1是一个原因结点，它会导致糖尿病X2和高血脂X3。而我们知道糖尿病X2和高血脂X3都可能最终导致心脏病X4。494.4.1贝叶斯网结构

504.4.2贝叶斯网学习算法

贝叶斯网学习的首要任务就是根据训练数据集来找出结构最“恰当”的贝叶斯网。“评分搜索”是求解这一问题的常用办法。具体来说，我们先定义一个评分函数，以此来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。514.4.2贝叶斯网学习算法

524.4.2贝叶斯网学习算法

534.4.3贝叶斯网推断

在现实应用中，贝叶斯网的近似推断常使用吉布斯采样来完成，这是一种随机采样方法。

544.4.3贝