文档介绍：——K最近邻分类(KNN)
数据挖掘算法
K最近邻分类(KNN)
该方法的思路是:如果一个样本在特征空间中的k个最相近(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。即—“近朱者赤,近墨者黑”,由你的邻居来推断出你的类别。
用下面的谚语最能说明:“如果走像鸭子,叫像鸭子,看起来还像鸭子,那么它很可能就是一只鸭子。”
K值选取
k值通常是采用交叉检验来确定(以k=1为基准)
交叉验证的概念:将数据样本的一部分作为训练样本,一部分作为测试样本,比如选择95%作为训练样本,剩下的用作测试样本。通过训练数据训练一个模型,然后利用测试数据测试其误差率。 cross-validate(交叉验证)误差统计选择法就是比较不同K值时的交叉验证平均误差率,选择误差率最小的那个K值。例如选择K=1,2,3,... , 对每个K=i做100次交叉验证,计算出平均误差,然后比较、选出最小的那个。
经验规则:k一般低于训练样本数的平方根。
需要指出的是:取k=1常常会得到比其他值好的结果,特别是在小数据集中。
不过仍然要注意:在样本充足的情况下,选择较大的K值能提高抗躁能力。
欧氏距离
计算距离有许多种不同的方法,如欧氏距离、余弦距离、汉明距离、曼哈顿距离等等,传统上,kNN算法采用的是欧式距离。
也称欧几里得距离,它是一个采用的距离定义,他是在维空间中两个点之间的真实距离。
二维的公式:
计算步骤如下:

,则将该训练样本作为K-最近邻样本
、3、4,直到未知样本和所有训练样本的距离都算完

注意:
该算法不需要花费时间做模型的构建。其他大多数分类算法,如决策树等都需要构建模型的阶段,而且该阶段非常耗时,但是它们在分类的时候非常省时。
类别的判定
投票决定:少数服从多数,近邻中哪个类别的点最多就分为该类。
如果训练数据大部分都属于某一类,投票算法就有很大问题了。这时候就需要考虑设计每个投票者票的权重了。
加权投票法:根据距离的远近,对近邻的投票进行加权,距离越近则权重越大(权重为距离平方的倒数)
若样本到测试点距离为d,则选1/d为该邻居的权重(也就是得到了该邻居所属类的权重),接下来统计统计k个邻居所有类标签的权重和,值最大的那个就是新数据点的预测类标签。
示例:
如图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?
如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。
优缺点
1、优点
简单,易于理解,易于实现,无需估计参数,无需训练
适合对稀有事件进行分类(例如当流失率很低时,%,构造流失预测模型)
特别适合于多分类问题(multi-modal,对象具有多个类别标签),例如根据基因特征来判断其功能分类,kNN比SVM的表现要好
对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
优缺点
2、缺点
懒惰算法,就是说直到预测阶段采取处理训练数据。
对测试样本分类时的计算量大,内存开销大,评分慢。
可解释性较差,无法给出决策树那样的规则。
由于没有涉及抽象过程,kNN实际上并没有创建一个模型,预测时间较长。