数据挖掘经典算法之 K- 邻近算法(超详细附代码)
简介
又叫 K-邻近算法,是监督学习中的一种分类算法。目的是根据已知类别的样本点集求出待分类的数据点类别。
基本思想
kNN 的思想很简单:在训练集中选取离输入的数据点最近的 k 个邻居,根据这个 k 个邻居中出现次数最多的类别(最大表决规则),作为该数据点的类别。kNN 算法中,所选择的邻居都是已经正确分类的对象。
算法复杂度
kNN 是一种 lazy-learning 算法,分类器不需要使用训练集进行训练,因此训练时间复杂度为 0;kNN 分类的计算复杂度和训练集中的文档数目成正比,也就是说,如果训练集中文档总数为 n,那么 kNN 的分类时间复杂度为 O(n);因此,最终的时间复杂度是 O(n)。
优缺点
优点
理论成熟,思想简单,既可以用来做分类也可以用来做回归 ;
适合对稀有事件进行分类(例如:客户流失预测);
特别适合于多分类问题(multi-modal,对象具有多个类别标签,例如:根据基因特征来判断其功能分类), kNN 比 SVM 的表现要好。
缺点
当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的 K 个邻居中大容量类的样本占多数;
计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的 K 个最近邻点;
可理解性差,无法给出像决策树那样的规则。
代码
复制代码
版权声明: 本文为 InfoQ 作者【Python研究者】的原创文章。
原文链接:【http://xie.infoq.cn/article/8e5616d8f23b376c8e985d276】。文章转载请联系作者。
评论