KNN算法浅析.pptx

浅谈K-NN算法 目录 算法简介 算法思想 算法实现 算法应用场面或场景 算法的应用案例 一、算法简介 何谓K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：分析一个人时，我们不妨观察和他最亲密的几个人。同理的，在判定一个未知事物时，可以观察离它最近的几个样本，这就是 kNN（k最近邻）的方法。 二、算法思想 如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。 问题：图中的绿色的圆属于哪一类？ 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。 三、算法实现 产生训练集，使得训练集按照已有的分类标准划分成离散型数值类，或者是连续型数值类输出。 以训练集的分类为基础，对测试集每个样本寻找K个近邻，采用欧式距离作为样本间的相似程度的判断依据，相似度大的即为最近邻。一般近邻可以选择1个或者多个。 当类为连续型数值时，测试样本的最终输出为近邻的平均值；当类为离散型数值时，测试样本的最终为近邻类中个数最多的那一类。 算法步骤 step.1---初始化距离为最大值 step.2---计算未知样本和每个训练样本的距离dist step.3---得到目前K个最临近样本中的最大距离maxdist step.4---如果dist小于maxdist，则将该训练样本作为K-最近邻样本 step.5---重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完 step.6---统计K个最近邻样本中每个类别出现的次数 step.7---选择出现频率最大的类别作为未知样本的类别 算法三个基本要素 K 值的选择 距离度量 分类决策规则 内容补充：K值的选择 内容补充：距离度量之欧式距离   K近邻算法的优点 简单，易于理解，易于实现，无需估计参数，无需训练 适合对稀有事件进行分类 特别适合于多分类问题(multi-modal,对象具有多个类别标签) K近邻算法的缺点 当样本不平衡时（如一个类的样本容量很大，而其他类样本容量很小时）有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 需要存储全部训练样本，计算量较大 可解释性较差，无法给出决策树那样的规则。 针对K近邻缺点的改进方案 缺点一解决方案：1、权值的方法（和该样本距离小的邻居权值大）；2、事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。 缺点二解决方案：选取质点 K近邻算法带来的问题 应用K-近邻算法来进行预测的时候，经常会遇到很多现实问题。包括： 维度灾害问题 近邻索引问题 近邻大小问题 计算效率问题 归纳偏置问题 K近邻算法改进：压缩近邻算法 定义两个存储器，一个用来存放生成的样本集，称为output样本集；另一个用来存放原来的样本集，称为original样本集。 1、初始化：output样本集为空集，原样本集存入original样本集，从original样本集中任意选择一个样本移动到output样本集中。 2、在original样本集中选择第i个样本，并使用output样本集中的样本对其进行最近邻算法分类，若分类错误，则将该样本移动到output样本集中，若分类正确，不做任何处理。 3、重复2步骤，直至遍历完original样本集中的所有样本，output样本集即为压缩后的样本集。 四、K近邻算法应用面或者场景 预测某人是否喜欢推荐电影（Netflix） 模式识别，特别是光学字符识别  数据库，如基于内容的图像检索 编码理论（最大似然编码）；数据压缩（MPEG-2标准） 向导系统；DNA测序； 剽窃侦查；拼写检查，建议正确拼写 相似比分算法，用来推断运动员的职业表现。 四、K近邻算法应用面或者场景 简单说一下这个数据的意思：这里用打斗次数和接吻次数来界定电影类型，如上，接吻多的是Romance类型的，而打斗多的是动作电影。还有一部名字未知（这里名字未知是为了防止能从名字中猜出电影类型），打斗次数为18次，接吻次数为90次的电影，它到底属于哪种类型的电影呢？ 五、K近邻算法 KNN最近邻基于欧几里得距离的java算法实现 1.小规模数据集 2.假设所有数据及类别都是数值类型的 3.直接根据数据规模设定了k值 4.对原训练集进行测试 Thank you!