KNN算法是有监督学习中的分类算法,它看起来和另一个机器学习算法K-means有点像(K-means是无监督学习算法),但却是有本质区别的。

KNN的原理就是:当预测一个新的值x的时候,根据它距离最近的K个点是什么类别,来判断x属于哪个类别。

图中绿色的点就是我们要预测的那个点,假设K=3。那么KNN算法就会找到与它距离最近的三个点(这里用圆圈把它圈起来了),看看哪种类别多一些,比如这个例子中是蓝色三角形多一些,新来的绿色点就归类到蓝三角了。

但是,当K=5的时候,判定就变成不一样了。这次变成红圆多一些,所以新来的绿点被归类成红圆。从这个例子中,我们就能看得出K的取值是很重要的

KNN的两个核心点:K值的选取点之间距离的计算方式

距离计算公式就不多说了,是欧氏距离: d ( x , y ) : =∑ i = 1n( xi− yi)2d(x,y):=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}d(x,y):=i=1n(xiyi)2

(对于高维特征,曼哈顿距离(即p更低)更能避免维度灾难的影响,效果更优。欧几里得距离(次数更高)更能关注大差异较大的特征的情况)

最简单粗暴的就是将预测点与所有点距离进行计算,然后保存并排序,选出前面K个值看看哪些类别比较多。但其实也可以通过一些数据结构来辅助,比如最大堆

如何确定K值?答案是通过网格搜索,交叉验证(将样本数据按照一定比例,拆分出训练用的数据和验证用的数据,比如6:4拆分出部分训练数据和验证数据),从选取一个较小的K值开始,不断增加K的值,然后计算验证集合的方差,最终找到一个比较合适的K值

有个反直觉的现象,K取值较小时,模型复杂度(容量)高,训练误差会减小,泛化能力减弱;K取值较大时,模型复杂度低,训练误差会增大,泛化能力有一定的提高。原因是K取值小的时候(如k=1),仅用较小的领域中的训练样本进行预测,模型拟合能力比较强,决策就是只要紧跟着最近的训练样本(邻居)的结果。但是,当训练集包含”噪声样本“时,模型也很容易受这些噪声样本的影响(如图 过拟合情况,噪声样本在哪个位置,决策边界就会画到哪),这样会增大”学习”的方差,也就是容易过拟合。这时,多听听其他邻居训练样本的观点就能尽量减少这些噪声的影响。K值取值太大时,情况相反,容易欠拟合。

KNN是一种非参的惰性的算法模型:

非参的意思并不是说这个算法不需要参数,而是意味着这个模型不会对数据做出任何的假设,与之相对的是线性回归(我们总会假设线性回归是一条直线)。也就是说KNN建立的模型结构是根据数据来决定的,这也比较符合现实的情况,毕竟在现实中的情况往往与理论上的假设是不相符的。

此处的非参数似乎不太正确

惰性又是什么意思呢?想想看,同样是分类算法,逻辑回归需要先对数据进行大量训练,最后才会得到一个算法模型。而KNN算法却不需要,它没有明确的训练数据的过程,或者说这个过程很快。

KNN算法优点

  • 算法简单直观,易于应用于回归及多分类任务
  • 对数据没有假设,准确度高,对异常点较不敏感
  • 由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此适用于类域的交叉或非线性可分的样本集。

KNN算法缺点

  • 计算量大,尤其是样本量、特征数非常多的时候。另外KD树、球树之类的模型建立也需要大量的内存
  • 只与少量的k相邻样本有关,样本不平衡的时候,对稀有类别的预测准确率低
  • 使用懒散学习方法,导致预测时速度比起逻辑回归之类的算法慢。当要预测时,就临时进行 计算处理。需要计算待分样本与训练样本库中每一个样本的相似度,才能求得与 其最近的K个样本进行决策。
  • 与决策树等方法相比,KNN考虑不到不同的特征重要性,各个归一化的特征的影响都是相同的。
  • 相比决策树、逻辑回归模型,KNN模型可解释性弱一些
  • 差异性小,不太适合KNN集成进一步提高性能。