浅谈K-NN算法PPT课件.ppt

浅谈K NN算法 主讲 苏敏小组成员 骆健 刘兵 张文平 李鸣 苏敏 2020 3 20 1 基本概念 全称 k NearestNeighbor简称 K NN中文 K 近邻算法 2020 3 20 2 什么是K 近邻算法 何谓K近邻算法 即K NearestNeighboralgorithm 简称KNN算法 单从名字来猜想 可以简单粗暴的认为是 K个最近的邻居 当K 1时 算法便成了最近邻算法 即寻找最近的那个邻居 为何要找邻居 打个比方来说 假设你来到一个陌生的村庄 现在你要找到与你有着相似特征的人群融入他们 所谓入伙 用官方的话来说 所谓K近邻算法 即是给定一个训练数据集 对新的输入实例 在训练数据集中找到与该实例最邻近的K个实例 也就是上面所说的K个邻居 这K个实例的多数属于某个类 就把该输入实例分类到这个类中 根据这个说法 咱们来看下引自维基百科上的一幅图 2020 3 20 3 算法举例 如上图所示 有两类不同的样本数据 分别用蓝色的小正方形和红色的小三角形表示 而图正中间的那个绿色的圆所标示的数据则是待分类的数据 问题 给这个绿色的圆分类 如果K 3 绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形 少数从属于多数 基于统计的方法 判定绿色的这个待分类点属于红色的三角形一类 如果K 5 绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形 还是少数从属于多数 基于统计的方法 判定绿色的这个待分类点属于蓝色的正方形一类 2020 3 20 4 基本思想 产生训练集 使得训练集按照已有的分类标准划分成离散型数值类 或者是连续型数值类输出 以训练集的分类为基础 对测试集每个样本寻找K个近邻 采用欧式距离作为样本间的相似程度的判断依据 相似度大的即为最近邻 一般近邻可以选择1个或者多个 当类为连续型数值时 测试样本的最终输出为近邻的平均值 当类为离散型数值时 测试样本的最终为近邻类中个数最多的那一类 2020 3 20 5 K 近邻算法特点 KNN算法本身简单有效 它是一种lazy learning算法 分类器不需要使用训练集进行训练 训练时间复杂度为0 KNN分类的计算复杂度和训练集中的文档数目成正比 也就是说 如果训练集中文档总数为n 那么KNN的分类时间复杂度为O n 2020 3 20 6 K 近邻三个基本要素 K值的选择距离度量根据欧氏距离定义实例间的距离 两个实例xi和xj的距离d xi xj 定义为分类决策规则往往是多数表决 即由输入实例的K个最临近的训练实例中的多数类决定输入实例的类别 2020 3 20 7 内容补充 K值的选择 2020 3 20 8 内容补充 距离度量之欧式距离 2020 3 20 9 K近邻算法的优点 K 近邻算法不是在整个实例空间上一次性地预测目标函数值 而是针对每个待预测的新实例 建立不同的目标函数逼近 作出局部的和相异的预测 这样做的好处是 有时目标函数很复杂 但具有不太复杂的局部逼近 距离加权的k 近邻算法对训练数据中的噪声有很好的健壮性 通过取k个近邻的加权平均 可以消除孤立的噪声样例的影响 2020 3 20 10 K近邻算法的缺点 当样本不平衡时 如一个类的样本容量很大 而其他类样本容量很小时 有可能导致当输入一个新样本时 该样本的K个邻居中大容量类的样本占多数 该算法只计算 最近的 邻居样本 某一类的样本数量很大 那么或者这类样本并不接近目标样本 或者这类样本很靠近目标样本 计算量较大 因为对每一个待分类的文本都要计算它到全体已知样本的距离 才能求得它的K个最近邻点 2020 3 20 11 针对K近邻缺点的改进方案 针对第一个缺点 可以采用权值的方法 和该样本距离小的邻居权值大 来改进 目前常用的解决方法是事先对已知样本点进行剪辑 事先去除对分类作用不大的样本 该算法比较适用于样本容量比较大的类域的自动分类 而那些样本容量较小的类域采用这种算法比较容易产生误分 2020 3 20 12 K近邻算法带来的问题 应用K 近邻算法来进行预测的时候 经常会遇到很多现实问题 这些问题包括 维度灾害问题 近邻索引问题 近邻大小问题 计算效率问题 归纳偏置问题 2020 3 20 13 维度灾害问题 k 近邻算法的一个实践问题 维度灾害许多学习方法 比如决策树方法 选择部分属性作出判断 而k 近邻方法中实例间的距离是根据实例的所有属性计算的 实例间距离会被大量的不相关属性所支配 可能导致相关属性的值很接近的实例相距很远 解决维度灾害问题的常用方法 1 属性加权 2 属性选择 2020 3 20 14 近邻索引问题 k 近邻算法的所有计算几乎都花费在索引近邻问题上 因此 如何建立高效的索引是k 近邻算法的另外一个实践问题 目前 已经开发了很多对存储的训练样例进行索引的方法 以便能高效地确定最近邻 如kd tree把实例存储在树的叶结点内 邻近的实例存储在同一个或附近的节点内 通过测试新查询xq的选定属性 树的内部节点把查询xq排列到相关的叶结点 2020 3 20 15 近邻大小问题 k 近邻算法的预测结果与k的大小相关 同样的数据 K值不同可能导致不同的预测结果 2020 3 20 16 计算效率问题 k 近邻算法推迟所有的计算处理 直到接收到一个新的查询 所以处理每个新查询可能需要大量的计算 2020 3 20 17 归纳偏置问题 k 近邻算法的归纳偏置是 一个实例的分类xq与在欧氏空间中它附近的实例的分类相似 2020 3 20 18 问题 实现K近邻算法时 主要考虑的问题