机器学习算法KNN简介及实现

CodingGo技术社区

自由的编程学习平台

算法简介

KNN(K近邻算法)是一种不需要学习任何参数同时也非常简单的机器学习算法，既可以用来解决分类问题也可以用来解决回归问题。直观解释这个算法就是'近朱者赤，近墨者黑'，当输入一个新样本时，根据与其相近的样本值来估计新输入的样本。如下图所示新输入的样本会被分类为W1。

影响算法的几个因子

在了解算法大体的思路后，其实还有几个问题需要继续深究:

1、如何表达两个样本的距离(相似度)？ 

2、KNN中的K值应该如何选取？ 

3、确定了相邻的点后，如何得出最终的结果？

距离的计算:

首先我们把每个样本的特征映射到特征空间中,样本距离的衡量其实就是空间中两点之间的距离，一般使用的是欧式距离

使用哪种方式来计算距离还是需要看具体的场景以及要解决的问题(domain-knowledge)，比如输入经纬度的信息预测房价，计算距离的话可以直接使用经纬度的距离计算公式。

预测黑色点的房价

K值的选取:

K值的选择会对最后的结果产生非常大的影响，假设我们选取的k值很小那么样本很容易被周围的异常点给影响，这样的模型容易过拟合。

下图为是k取1时的效果图，很明显边界非常不平滑并且一些异常点严重影响到了分类的结果。

K取值为1的分类效果 

那如果选择较大的K值，就相当于用较大范围的训练实例进行预测，可以减少异常数据的影响。假如K取值为整个样本的大小那么最后的结果相当于对样本整体做了个平均，这时模型会过于简单。

总结一下：K取值越小，模型越容易过拟合。取值越大，模型越简单，发现不了数据的差异。

确定相邻点后的的决策过程:

一般情况下直接对K个值取平均或者多数表决来决定最后的预测结果，也可以对每种类型或者不同距离的远近施加不同的权重，具体需要根据业务场景来决定。

算法实现:

下面是一个非常简单的版本实现，每次都需要遍历完一遍样本集，最后取平均得出预测结果。

1. import numpy as np

2. from sklearn.neighbors import KNeighborsClassifier

3. from sklearn.metrics.pairwise import pairwise_distances

4. ‘’‘

5. # samples为需要分类的样本

6. # topk为Number of neighbors

7. ’‘’

8. def predict_by_k_nearest(samples, features, labels, topk):

9.    distance = [pairwise_distances(i, samples)[0][0] for i in features]

10.    index = np.argsort(distance)[:topk]

11.    return 1 if (y[index].mean() > 0.5) else 0

完成分类过程，以sklearn的KNeighborsClassifier做了一下验证，发现预测结果都是1。sklearn的KNeighborsClassifier有不同的参数可以设置，但都围绕我们之前讨论的3个问题。

1. X = np.asarray([[0], [1], [2], [3], [4]])

2. y = np.asarray([0, 0, 1, 1, 1])

4. neigh = KNeighborsClassifier(n_neighbors=3,weights='uniform')

5. neigh.fit(X, y)

6. print(neigh.predict([[3]]))

7. print (predict_by_k_nearest([3], X, y, 3))

8. ### [1]

补充：

KNN每次在计算距离的时候都需要遍历完全部的样本，非常耗时。我们可以使用KD树来优化查询的过程，核心思想就是把相近的样本索引在同一个区间上，这样每次查询的时候只要看相近的区间都可以。这部分我没有实现，有兴趣的同学可以在网上查询相关的资料。

?

严力，一个有着老师梦的程序猿

专栏：https://zhuanlan.zhihu.com/yanli

?