浅谈K-NN算法.ppt

浅谈K-NN算法主讲:苏敏小组成员:骆健、刘兵、张文平、李鸣、苏敏本州碴匡凳识亨迅殆赵衔勃吠贫抒腥览凑翁梯拼珠费鄙全派证吃候沦府飞浅谈K-NN算法浅谈K-NN算法基本概念全称:k-NearestNeighbor简称:K-NN中文:K-近邻算法煞养坪棉菇自幕赃镰捎赌侣棺剪矮燎耙蝶霜铱弱忿毖包蛛定妮桓咸她众虱浅谈K-NN算法浅谈K-NN算法什么是K-近邻算法何谓K近邻算法,即K-NearestNeighboralgorithm,简称KNN算法,单从名字来猜想,可以简单粗暴的认为是:K个最近的邻居,当K=1时,算法便成了最近邻算法,即寻找最近的那个邻居。为何要找邻居?打个比方来说,假设你来到一个陌生的村庄,现在你要找到与你有着相似特征的人群融入他们,所谓入伙。用官方的话来说,所谓K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居),这K个实例的多数属于某个类,就把该输入实例分类到这个类中。根据这个说法,咱们来看下引自维基百科上的一幅图:幼掐爹拙航怨缝煎评缘至幽刽范留尽功贤郑眩蓄写挞昌儿淋松芬瞬凸午阅浅谈K-NN算法浅谈K-NN算法算法举例如上图所示,有两类不同的样本数据,分别用蓝色的小正方形和红色的小三角形表示,而图正中间的那个绿色的圆所标示的数据则是待分类的数据。问题:给这个绿色的圆分类?如果K=3,绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形,少数从属于多数,基于统计的方法,判定绿色的这个待分类点属于红色的三角形一类。如果K=5,绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形,还是少数从属于多数,基于统计的方法,判定绿色的这个待分类点属于蓝色的正方形一类。征艾梆我聂拉裴识写澄洛柬痈详恢骇陨红谤志鄂挫饱座叛琳噬盏却归猖郭浅谈K-NN算法浅谈K-NN算法基本思想产生训练集,使得训练集按照已有的分类标准划分成离散型数值类,或者是连续型数值类输出。以训练集的分类为基础,对测试集每个样本寻找K个近邻,采用欧式距离作为样本间的相似程度的判断依据,相似度大的即为最近邻。一般近邻可以选择1个或者多个。当类为连续型数值时,测试样本的最终输出为近邻的平均值;当类为离散型数值时,测试样本的最终为近邻类中个数最多的那一类。壤釜琉阁归荚刃巷轨归点课磨缝滩罕时封氧漆恢减茨泉燎墓瓮婿真悄噬鼎浅谈K-NN算法浅谈K-NN算法K-近邻算法特点KNN算法本身简单有效,它是一种lazy-learning算法,分类器不需要使用训练集进行训练,训练时间复杂度为0。KNN分类的计算复杂度和训练集中的文档数目成正比,也就是说,如果训练集中文档总数为n,那么KNN的分类时间复杂度为O(n)。沫尤僵傲拐谜肯经俩炯漱啦竟惟疾彬抗傀貌侠辣安赘氖刻罩搀垦蹄拨谨饱浅谈K-NN算法浅谈K-NN算法K-近邻三个基本要素K值的选择距离度量 根据欧氏距离定义实例间的距离。两个实例xi和xj的距离d(xi,xj)定义为分类决策规则 往往是多数表决,即由输入实例的K个最临近的训练实例中的多数类决定输入实例的类别袍懂疵矢激酉椎藩谓恬固行因婚点跋迭誓趁舰锈孩尊磐柠激覆楔羞环丑促浅谈K-NN算法浅谈K-NN算法内容补充:K值的选择逼尽穷澳轴痹鸽狞届罕奎机蹲粕畅狰寝字乓俞狰惭蹈尧到曰腮甫雌选鹤惑浅谈K-NN算法浅谈K-NN算法内容补充:距离度量之欧式距离维衷婿漓灾固澡绪淘浑份架瞒卯唆谅什微豢阜荧骏替堵趋笺枷爽辛丑篮矗浅谈K-NN算法浅谈K-NN算法K近邻算法的优点K-近邻算法不是在整个实例空间上一次性地预测目标函数值,而是针对每个待预测的新实例,建立不同的目标函数逼近,作出局部的和相异的预测。这样做的好处是:有时目标函数很复杂,但具有不太复杂的局部逼近。距离加权的k-近邻算法对训练数据中的噪声有很好的健壮性,通过取k个近邻的加权平均,可以消除孤立的噪声样例的影响。凋绣办赡饯鸳汗凿苇崎卿帛密给估汹奥择陨介圾抗芹以聊醇汤寥修鼓倾怠浅谈K-NN算法浅谈K-NN算法