数据挖掘十大经典算法——kNN-阿里云开发者社区

开发者社区> inzaghi1984> 正文

数据挖掘十大经典算法——kNN

简介: K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空 间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
+关注继续查看

数据挖掘十大经典算法(8) kNN
1、K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空 间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
2、KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本, 而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
3、KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的 邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比。
4、 该算法在分类时有个主要的不足是 ,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。

  该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。 

算法分类过程如下:
1 首先我们事先定下k值(就是指k近邻方法的k的大小,代表对于一个待分类的数据点,我们要寻找几个它的邻居)。这边为了说明问题,我们取两个k值,分别为3和9;
2 根据事先确定的距离度量公式(如:欧氏距离),得出待分类数据点和所有已知类别的样本点中,距离最近的k个样本。
3 统计这k个样本点中,各个类别的数量。根据k个样本中,数量最多的样本是什么类别,我们就把这个数据点定为什么类别。
训练样本是多维特征空间向量,其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。 在分类阶段,k是一个用户定义的常数。一个没有类别标签的向量 (查询或测试点)将被归类为最接近该点的K个样本点中最频繁使用的一类。
一般情况下,将欧氏距离作为距离度量,但是这是只适用于连续变量。在文本分类这种非连续变量情况下,
另一个度量——重叠度量(或海明距离)可以用来作为度量。通常情况下,如果运用一些特殊的算法来计算度量的话,K近邻分类精度可显著提高,如运用大边缘最近邻法或者近邻成分分析法。
“多数表决”分类的一个缺点是出现频率较多的样本将会主导测试点的预测结果,那是因为他们比较大可能出现在测试点的K邻域而测试点的属性又是通过K领域内的样本计算出来的。解决这个缺点的方法之一是在进行分类时将样本到测试点的距离考虑进去。
K值得选择
如何选择一个最佳的K值取决于数据。一般情况下,在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术来获取,比如,交叉验证。
噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。对于选择特征向量进行分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展[3],还有一种较普遍的方法是利用训练样本的互信息进行选择特征。
K近邻算法也适用于连续变量估计,比如适用反距离加权平均多个K近邻点确定测试点的值。该算法的功能有:
1、从目标区域抽样计算欧式或马氏距离;
2、在交叉验证后的RMSE基础上选择启发式最优的K邻域;
3、计算多元k-最近邻居的距离倒数加权平均。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
单芯片每秒1000万亿次运算:谷歌TPU原班团队全新AI架构,晶体管性能提升6倍
2016 年底,谷歌 TPU 团队的十位核心开发者中的八位悄悄离职,创办了一家名为 Groq 的机器学习系统公司。在此后的三年里,这家公司一直很低调。但最近,他们带着一款名为 TSP 的芯片架构出现在公众视野里。
3 0
SAP ERP classification和C4C的同步
在ERP里创建两个characteristic:
3 0
SAP Cloud for Customer(C4C)的一些学习资料(持续更新)
经常有顾问朋友们问我想自学C4C,有什么好的资料。 SAP内部确实有一些C4C培训材料,但是不能散布到公司外部。 这些标准培训课程的目录,可以在公网上查看,参考我这篇文章:SAP Cloud for Customer 标准培训课程. 想学习C4C,还是得到SAP官网网站上查找资料。 1. 登录https://help.sap.com, 搜索栏里输入cloud for customer:
4 0
可直接编辑的高质量3D生成模型:中科院计算所等提出高质量三维深度生成方法SDM-NET
中科院计算所、香港城市大学、英国卡迪夫大学以及加拿大西蒙弗雷泽大学的研究者,近日提出了一种能够表达几何细节和复杂拓扑结构的三维模型深度生成方法 SDM-NET,解决了之前方法的一部分局限性,使得生成的模型具有高质量的几何细节并可以支持快速编辑。该研究已被计算机图形学顶会 Siggraph Asia 2019 接收。
4 0
SAP Cloud for Customer Extensibility的设计与实现
今天的文章来自Jerry的同事,SAP成都研究院C4C开发团队的开发人员徐欢(Xu Boris)。徐欢就坐我左手边的位置,因此我工作中但凡遇到C4C的技术问题,一扭头就可以请教他了,非常方便。下图是他办公室的桌面。
3 0
经验、技术与开放融合,让老牌CDN重焕青春
有观点认为,CDN厂商为了生存与发展,已将价格拉到负毛利状态,行业整合与洗牌一触即发。似乎,媒体将CDN行业的价格战渲染过重了,毕竟价格战是每个行业发展必然经历的阶段。价格战是企业的竞争策略,是那些没有优势CDN企业保命的手段,但影响不到那些长期专注CDN的企业。对这些企业而言,经验、技术、创新及服务等多种因素,共同决定了客户对其产品的选择权。
3 0
谷歌「双十一」也放大招:Colab上可以免费使用P100 GPU了
双十一的各位读者朋友有没有买买买呢?在深度学习社区,谷歌居然也在这一天提供了福利——Colab 可以免费使用 P100 GPU 了。
3 0
微软核心业务即将上线Project Cortex:AI知识图谱大幅提升企业效率
微软正为旗下核心服务 Microsoft 365 引入知识图谱功能:通过 AI 算法对数据的整合,很快我们就可以在日常工作中享受人工智能技术带来的各种便利了。
3 0
推特发布首个反Deepfake策略草案:换脸一时爽?推文火葬场
昨天,推特正式发布了首个反 Deepfake 策略草案。该公司表示,如果 Deepfake 内容威胁到某人的人身安全或可能造成严重伤害,他们会将该内容从推特上删除。目前,推特还在为这项草案征集公众意见。
3 0
+关注
inzaghi1984
金融IT技术人员
220
文章
62
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载