KNN
- 一、算法简述
- 二、运行原理
- 2.1、算法核心思想
- 2.2、距离计算
- 2.3、K值选择
- 三、算法实现
- 3.1、Sklearn KNN参数概述
- 3.2、 KNN代码实例
- 四、算法特点
- 五、算法优缺点
- 六、KNN 和 K-means比较
一、算法简述
KNN 可以说是最简单的分类算法之一,同时,它也是最常用的分类算法之一。注意:KNN 算法是有监督学习中的分类算法,它看起来和另一个机器学习算法 K-means 有点像(K-means 是无监督学习算法),但却是有本质区别的。
二、运行原理
2.1、算法核心思想
KNN 的全称是 K Nearest Neighbors,意思是 K 个最近的邻居。从这个名字我们就能看出一些 KNN 算法的蛛丝马迹了。K 个最近邻居,毫无疑问,K 的取值肯定是至关重要的,那么最近的邻居又是怎么回事呢?其实,KNN 的原理就是当预测一个新的值 x 的时候,根据它距离最近的 K 个点是什么类别来判断 x 属于哪个类别。听起来有点绕,还是看看图吧。
图中绿色的点就是我们要预测的那个点,假设 K=3。那么 KNN 算法就会找到与它距离最近的三个点(这里用圆圈把它圈起来了),看看哪种类别多一些,比如这个例子中是蓝色三角形多一些,新来的绿色点就归类到蓝三角了。
但是,当 K=5 的时候,判定就变成不一样了。这次变成红圆多一些,所以新来的绿点被归类成红圆。从这个例子中,我们就能看得出 K 的取值是很重要的。
明白了大概原理后,我们就来说一说细节的东西吧,主要有两个,K 值的选取和点距离的计算。
2.2、距离计算
要度量空间中点距离的话,有好几种度量方式,比如常见的曼哈顿距离计算、欧式距离计算等等。不过通常 KNN 算法中使用的是欧式距离。这里只是简单说一下,拿二维平面为例,二维空间两个点的欧式距离计算公式如下:
这个高中应该就有接触到的了,其实就是计算(x1,y1)和(x2,y2)的距离。拓展到多维空间,则公式变成这样:
这样我们就明白了如何计算距离。KNN 算法最简单粗暴的就是将预测点与所有点距离进行计算,然后保存并排序,选出前面 K 个值看看哪些类别比较多。但其实也可以通过一些数据结构来辅助,比如最大堆,这里就不多做介绍,有兴趣可以百度最大堆相关数据结构的知识。
2.3、K值选择
通过上面那张图我们知道 K 的取值比较重要,那么该如何确定 K 取多少值好呢?答案是通过交叉验证(将样本数据按照一定比例,拆分出训练用的数据和验证用的数据,比如6:4拆分出部分训练数据和验证数据),从选取一个较小的 K 值开始,不断增加 K 的值,然后计算验证集合的方差,最终找到一个比较合适的 K 值。
通过交叉验证计算方差后可以得到一个有一定趋向的线图,然后通过观察找到最适合的k值。
当你增大 K 的时候,一般错误率会先降低,因为有周围更多的样本可以借鉴了,分类效果会变好。但注意,和 K-means 不一样,当 K 值更大的时候,错误率会更高。这也很好理解,比如说你一共就35个样本,当你 K 增大到30的时候,KNN 基本上就没意义了。
三、算法实现
3.1、Sklearn KNN参数概述
要使用 Sklearn KNN 算法进行分类,我们需要先了解 Sklearn KNN 算法的一些基本参数:
def KNeighborsClassifier(n_neighbors = 5,
weights='uniform',
algorithm = '',
leaf_size = '30',
p = 2,
metric = 'minkowski',
metric_params = None,
n_jobs = None
)
参数的含义:
n_neighbors:这个值就是指 KNN 中的 “K”了。前面说到过,通过调整 K 值,算法会有不同的效果。
weights(权重):最普遍的 KNN 算法无论距离如何,权重都一样,但有时候我们想搞点特殊化,比如距离更近的点让它更加重要。这时候就需要 weight 这个参数了,这个参数有三个可选参数的值,决定了如何分配权重。参数选项如下:
-
‘uniform’:不管远近权重都一样,就是最普通的 KNN 算法的形式。
-
‘distance’:权重和距离成反比,距离预测目标越近具有越高的权重。
-
自定义函数:自定义一个函数,根据输入的坐标值返回对应的权重,达到自
定义权重的目的。
algorithm:在 Sklearn 中,要构建 KNN 模型有三种构建方式:
-
暴力法,就是直接计算距离存储比较的那种方式。
-
使用 Kd 树构建 KNN 模型。
-
使用球树构建。
其中暴力法适合数据较小的方式,否则效率会比较低。如果数据量比较大一般会选择用 Kd 树构建 KNN 模型,而当 Kd 树也比较慢的时候,则可以试试球树来构建 KNN。参数选项如下:
* ‘brute’ :蛮力实现;
* ‘kd_tree’:KD 树实现 KNN;
* ‘ball_tree’:球树实现 KNN ;
* ‘auto’: 默认参数,自动选择合适的方法构建模型。
不过当数据较小或比较稀疏时,无论选择哪个最后都会使用 ‘brute’。
leaf_size:如果是选择蛮力实现,那么这个值是可以忽略的。当使用 Kd 树或球树,它就是停止建子树的叶子节点数量的阈值。默认30,但如果数据量增多这个参数需要增大,否则速度过慢不说,还容易过拟合。
p:和 metric 结合使用,当 metric 参数是 “minkowski” 的时候,p=1 为曼哈顿距离, p=2 为欧式距离。默认为p=2。
metric:指定距离度量方法,一般都是使用欧式距离。
* ‘euclidean’ :欧式距离;
* ‘manhattan’:曼哈顿距离;
* ‘chebyshev’:切比雪夫距离;
* ‘minkowski’: 闵可夫斯基距离,默认参数。
n_jobs:指定多少个CPU进行运算,默认是-1,也就是全部都算。
3.2、 KNN代码实例
功能介绍:完成读取文件中的手写数字的图片,建立模型来验证数字,测试模型的准确率
import time
import matplotlib.pyplot as plt
import cv2
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
import re
if __name__ == '__main__':
# 训练目标数组和训练集数组
train,target = [],[]
# 利用循环将0-9每个3000张图片
for num in range(10):
for flag in range(300):
target.append(num)
digit = cv2.imread("D:/studyapps/mnist_data/"+str(num)+"."+str(flag)+".jpg")
res = digit[:, :, 0].reshape(784)
for rn in range(len(res)):
res[rn] = 0 if res[rn]<100 else 255
train.append(res)
tt = re.findall('^\d{13}',str(time.time()).replace('.',''))[0]
knn = KNeighborsClassifier(n_neighbors=6,weights='distance',p=2,n_jobs=-1)
# val = cross_val_score(knn.train.target,cv=20,scoring="accuracy").mean()
knn.fit(train,target)
print('模型生成--------------')
# 对图片进行识别
test,test_target = [],[]
for rn in range(10):
for co in range(300,310):
test_target.append(rn)
digit = cv2.imread("D:/studyapps/mnist_data/"+str(rn)+ "." +str(co)+ ".jpg")
res1 = digit[:, :, 0].reshape(784)
test.append(res1)
pred_res = knn.predict(test)
print('-----------识别结果--------------')
print(pred_res)
print('--------------真实结果---------------')
zx = range(1,55)
zq = []
for k in zx:
knn = KNeighborsClassifier(n_neighbors=k)
val = cross_val_score(knn,train,target,cv=20,scoring="accuracy").mean()
zq.append(val)
plt.plot(zx,zq)
plt.show()
四、算法特点
KNN是一种非参的、惰性的算法模型。什么是非参,什么是惰性呢?
非参的意思并不是说这个算法不需要参数,而是意味着这个模型不会对数据做出任何的假设,与之相对的是线性回归(我们总会假设线性回归是一条直线)。也就是说 KNN 建立的模型结构是根据数据来决定的,这也比较符合现实的情况,毕竟在现实中的情况往往与理论上的假设是不相符的。
惰性又是什么意思呢?想想看,同样是分类算法,逻辑回归需要先对数据进行大量训练(tranning),最后才会得到一个算法模型。而 KNN 算法却不需要,它没有明确的训练数据的过程,或者说这个过程很快。
五、算法优缺点
优点:
简单易用。相比其他算法,KNN 算是比较简洁明了的算法,即使没有很高的数学基础也能搞清楚它的原理。
模型训练时间快,上面说到 KNN 算法是惰性的,这里也就不再过多讲述。
预测效果好。
对异常值不敏感。
缺点:
对内存要求较高,因为该算法存储了所有训练数据。
预测阶段可能很慢。
对不相关的功能和数据规模敏感。
六、KNN 和 K-means比较
前面说到过,KNN 和 K-means 听起来有些像,但本质是有区别的,这里我们就顺便说一下两者的异同吧。
相同点:
K 值都是重点。
都需要计算平面中点的距离。
相异点:
KNN 和 K-means 的核心都是通过计算空间中点的距离来实现目的,只是他们的目的是不同的。KNN 的最终目的是分类,而 K-means 的目的是给所有距离相近的点分配一个类别,也就是聚类。
简单说,就是画一个圈,KNN 是让进来圈子里的人变成自己人,K-means 是让原本在圈内的人归成一类人。
至于什么时候应该选择使用 KNN 算法,Sklearn 的这张图给了我们一个答案:
简单来说,就是当需要使用分类算法,且数据比较大的时候就可以尝试使用 KNN 算法进行分类了。
https://zhuanlan.zhihu/p/143092725
更多推荐
Python Knn算法详解(近邻算法)
发布评论