浅谈K-NN算法.ppt

浅谈 K-NN 算法主讲:苏敏小组成员:骆健、刘兵、张文平、李鸣、苏敏基本概念?全称: k-Nearest Neighbor ?简称: K-NN ?中文: K-近邻算法什么是 K-近邻算法?何谓 K近邻算法,即 K-Nearest Neighbor algorithm ,简称 KNN 算法,单从名字来猜想,可以简单粗暴的认为是: K个最近的邻居,当 K=1 时,算法便成了最近邻算法,即寻找最近的那个邻居。为何要找邻居?打个比方来说,假设你来到一个陌生的村庄,现在你要找到与你有着相似特征的人群融入他们,所谓入伙。?用官方的话来说,所谓 K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的 K个实例(也就是上面所说的 K个邻居), 这K 个实例的多数属于某个类,就把该输入实例分类到这个类中。根据这个说法,咱们来看下引自维基百科上的一幅图: 算法举例?如上图所示,有两类不同的样本数据,分别用蓝色的小正方形和红色的小三角形表示,而图正中间的那个绿色的圆所标示的数据则是待分类的数据。?问题:给这个绿色的圆分类? ?如果 K=3 ,绿色圆点的最近的 3个邻居是 2个红色小三角形和 1个蓝色小正方形,少数从属于多数,基于统计的方法,判定绿色的这个待分类点属于红色的三角形一类。?如果 K=5 ,绿色圆点的最近的 5个邻居是 2个红色三角形和 3个蓝色的正方形,还是少数从属于多数,基于统计的方法,判定绿色的这个待分类点属于蓝色的正方形一类。基本思想?产生训练集,使得训练集按照已有的分类标准划分成离散型数值类,或者是连续型数值类输出。?以训练集的分类为基础,对测试集每个样本寻找 K个近邻,采用欧式距离作为样本间的相似程度的判断依据,相似度大的即为最近邻。一般近邻可以选择 1个或者多个。?当类为连续型数值时,测试样本的最终输出为近邻的平均值;当类为离散型数值时,测试样本的最终为近邻类中个数最多的那一类。 K-近邻算法特点? KNN 算法本身简单有效,它是一种 lazy-learning 算法,分类器不需要使用训练集进行训练,训练时间复杂度为 0。 KNN 分类的计算复杂度和训练集中的文档数目成正比,也就是说,如果训练集中文档总数为 n,那么 KNN 的分类时间复杂度为 O(n) 。 K-近邻三个基本要素? K 值的选择?距离度量?根据欧氏距离定义实例间的距离。两个实例 xi和 xj的距离 d(xi,xj) 定义为?分类决策规则?往往是多数表决,即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别?????? nr jrirjixaxaxxd 1 2)()(),(内容补充: K值的选择内容补充:距离度量之欧式距离 K近邻算法的优点? K-近邻算法不是在整个实例空间上一次性地预测目标函数值,而是针对每个待预测的新实例,建立不同的目标函数逼近,作出局部的和相异的预测。这样做的好处是:有时目标函数很复杂,但具有不太复杂的局部逼近。?距离加权的 k-近邻算法对训练数据中的噪声有很好的健壮性,通过取 k个近邻的加权平均,可以消除孤立的噪声样例的影响。