k近邻KNN算法

KNN(K-NearestNeighbor);即K近邻算法是数据挖掘分类技术中最简单的方法之一。所谓K近邻就是K个最近的邻居的意思,说的是每个样本都可以用它最接近的K个邻近值来代表。

假设特征空间有8个样本点;

其中红色点为良性肿瘤;蓝色点为恶性肿瘤;

现在要预测绿色点是良性肿瘤还是恶性肿瘤;

我们需要计算出绿色点到所有其他样本点的距离;选择出距离最小的K个点;对K个点所属的类别进行比较;根据少数服从多数的原则;将测试样本点归入在K个点中占比最高的那一类。计算距离方法一般采用欧拉距离公式:

n维特征空间欧式距离计算公式

实现步骤
	总体来说，KNN分类算法包括以下4个步骤： ①准备数据，对数据进行预处理 ②计算测试样本点（也就是待分类点）到其他每个样本点的距离 。 ③对每个距离进行排序，然后选择出距离最小的K个点。 ④对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类。

K 值的选择

了解完它的原理之后，下一个要讨论的问题就是，K 的值怎么选择。也就是说，应该选取最近的几个数据点来预测当前数据点呢？

以上面的图为例，如果我们把 K 的值定为 3，那么新数据（绿色）最终的预测结果为红色的三角形，如果 K 为 5，那结果就成了蓝色正方形。在 KNN 算法中，选择 K 的值的过程，其实就是算法参数调优的过程，并没有一个通用的最优的 K 值。

• 如果 K 的值太小，那么预测结果很容易被出现在附近的一场数据点所影响，导致数据异常被扩大。
• 如果 K 的值太大，距离较远的那些与预测数据点相似度不大的数据点与之匹配，会导致隐含的模式被忽略。

通常为了找到合适的 K 值，可以使用交叉验证法（挖个坑）对 K 进行调优。另外，还可以根据距离远近，使用不同的权重对新数据进行预测，使得离预测数据点越近的邻居对其影响越大。

KNN算法优缺点
	优点：
	1）思想简单、效果强大。 2）天然可解决多分类问题。 2）重新训练的代价较低（类别体系的变化和训练集的变化，在Web环境和电子商务应用中是很常见的）。 3）计算时间和空间线性于训练集的规模（在一些场合不算太大）。
	缺点：
	1）效率低下，如果训练集有m个样本，n个特征，则预测每一个新的数据，计算复杂度O（m*n） 2）高度数据相关，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数；对数据的局部结构比较敏感。如果查询点是位于训练集较密集的区域，那预测相对比其他稀疏集来说更准确。 3）预测结果不具有可解释性，只是找到了预测样本距离最近的样本点，不知道为什么属于预测类别。 4）维数灾难：随着维度增加，看似距离很近的2个点距离越来越大

这篇好文章是转载于：学新通技术网