机器学习（MATLAB版）ch05-k近邻算法 教学课件.pptxVIP

k近邻算法新工科建设之路·人工智能系列教材机器学习(MATLAB 版)第五章 01k近邻算法的基本原理 1.k 近邻算法的基本流程k 近邻算法是“懒惰学习”的著名代表，因为它没有模型参数需要确定，因此也就没有训练过程，超参数龙由人工指定。图 5.1 给出了 近邻分类器的一个示意图。显然，k 是一个重要参数，当无 取不同值时，分类结果会有显著不同。图 5.1 中的测试样本在=3 时被判别为“_”类，在7时被判别为“+”类。此外，不同的距离计算方式找出的“近邻”样本个数可能不同，从而导致分类的结果也会有所不同。 1.k 近邻算法的基本流程我们先对“最近邻分类器”(即 k = 1)在分类问题上的性能做一个简单的讨论。假设距离计算是“恰当”的，即能够恰当地找出 个近邻。给定测试样本 ，若其最近邻样本为 ，则最近邻分类器出错的概率就是签不同的率，即: 1.k 近邻算法的基本流程式(5.2)表明:最近邻分类器虽简单，但它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。 1.k 近邻算法的基本流程算法 5.1(k 近邻算法)显然，当飞=1 时，k 近邻算法退化为最近邻算法。更通俗地说，k 近邻算法是按照定规则将相似的样本数据进行归类的，类似于现实生活中的“物以类聚，人以群分”。首先，计算待分类数据特征与训练数据特征之间的距离并排序，取出距离最近的 个训练数据特征;然后，根据这无 个相近训练数据特征所属的类别来判定新样本的类别:如果它们都属于同一类，那么新样本也属于这一类:否则，对每个候选类别进行评分，按照某种规则确定新样本的类别。一般采用投票规则，即少数服从多数，期望的 值是一个奇数。精确的投票方法是计算每一个测试样本与个样本之间的距离。 1.k 近邻算法的基本流程容易发现，k 近邻算法实现十分简单，只需计算待测样本与每一个训练样本的距离即可，这是它的优点;其缺点是当训练样本容量大、特征向量维数高时，计算复杂度将变得十分可观。因为每次预测时都要计算待测样本与每一个训练样本的距离，而且需要对距离进行排序找到最近的无 个样本。此外，一个不容忽视的问题是参数 的取值，除了必须是一个奇数外，还需要根据问题和数据的特点来确定。在算法实现时还可以考虑样本的权重，即每个样本有不同的投票权重，这种方法称为加权 近邻算法。 1.k 近邻算法的基本流程另外，k 近邻算法也可以用于回归问题。在得到待处理数据的k个最相似训练数据后，求取这些训练数据特征的平均值，并将该平均值作为待处理数据的特征值。也就是说，假设距离待测试样本最近的k个训练样本的标签值为yi，则对该样本的回归预测值为:即 个近邻样本标签值的算术平均，在这里个近邻样本的贡献被认为是相等的。进一步地，可以考虑加权方案，即根据 个最相似训练样本和待预测样本的实际距离，赋予每个训练样本不同的权值，然后再进行加权平均，这样得到的回归值更为有效，即:其中，wi是第个样本的权重。权值可以人工设定，也可以用其他方法来确定，例如设置为与距离成反比。 2.k近邻算法的距离函数必须指出的是，k 近邻算法的实现依赖于样本之间的距离，因此需要定义距离的计算方式。下面介绍几种常用的距离定义，它们适用于不同特点的数据。 2.k近邻算法的距离函数在样本数有限的情况下，k 近邻算法的误判概率和距离的具体测度有直接关系。因此，在选择近邻样本数时利用适当的距离函数能够提高分类的正确率。通常， 近邻算法可采用欧氏距离(Euclidean Distance)、曼氏距离(Manhattan Distance)马氏距离(Mahalanobis Distance)等距离函数。 2.k近邻算法的距离函数其中，∑为 x 和y 在数据集的协方差阵。欧氏距离是最常用也是我们最熟知的距离。但在使用欧氏距离时，要注意将特征向量的分量归一化，以减少因特征值的尺度范围差异所带来的干扰，否则数值小的特征分量会被数值大的特征分量所淹没。也就是说，欧氏距离只是将特征向量看作空间中的点，并未考虑这些样本特征向量的概率分布规律。与欧氏距离不同，马氏距离则是一种概率意义上的距离，它与数据的尺度无关。马氏距离更为一般的定义是: 2.k近邻算法的距离函数其中，S 是对称正定矩阵。这种距离度量的是两个随机向量的相似度。显然，当 S 为单位阵时，马氏距离即退化为欧氏距离。矩阵 S 可以通过计算训练样本的协方差矩阵得到，也可以通过对样本的“距离度量学习”得到。另外还有一种巴氏距离(Bhattacharyya Distance)，它定义了两个离散型或连续型随机向量概率分布的相似性。对于在同一域 X 的两个散型分布 p(x),q(x)，其定为：对于连续型分布，其定义为:显然，两个随机向量越相似，这个距离值越小。注意，巴氏距离不满足三角不等式。 3.k近邻算法的判别函数现在来建立