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

算法简介

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])
  3. neigh = KNeighborsClassifier(n_neighbors=3,weights='uniform')
  4. neigh.fit(X, y)
  5. print(neigh.predict([[3]]))
  6. print (predict_by_k_nearest([3], X, y, 3))
  7. ### [1]

补充:

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

原文发布于微信公众号 - IT派(transfer_3255716726)

原文发表时间:2018-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

TensorFlow基本操作 实现卷积和池化

之前已经提到过图像卷积的操作和意义,并且用OpenCV中的filter2D函数实现了一些例子。OpenCV中的filter2D函数仅仅是用一个卷积核去卷积单个的...

1002
来自专栏决胜机器学习

机器学习(十一) ——神经网络基础

机器学习(十一)——神经网络基础 (原创内容,转载请注明来源,谢谢) 一、概述 神经网络,可以理解为输入的内容,经过一系列的内部的处理,得到输出的假设函数。简...

3776
来自专栏大数据挖掘DT机器学习

机器学习-R-特征选择

特征选择是实用机器学习的重要一步,一般数据集都带有太多的特征用于模型构建,如何找出有用特征是值得关注的内容。 1. Feature selection: Al...

5278
来自专栏Petrichor的专栏

深度学习: 参数初始化

好的开始是成功的一半。 为了让你的模型跑赢在起跑线 ε=ε=ε=(~ ̄▽ ̄)~ ,请慎重对待参数初始化。

3523
来自专栏青青天空树

趣味问题:画图(c++实现)

描述:在一个定义了直角坐标系的纸上,画一个(x1,y1)到(x2,y2)的矩形指将横坐标范围从x1到x2,纵坐标范围从y1到y2之间的区域涂上颜色。下图给出了一...

1084
来自专栏专知

理解多层CNN中转置卷积的反向传播(附代码)

1.4K3
来自专栏小小挖掘机

听说GAN很高大上,其实就这么简单

本文使用的tensorflow版本:1.4 tensorflow安装:pip install tensorflow 1、先来目睹一下效果吧 这篇文章讲解了如何使...

5724
来自专栏文武兼修ing——机器学习与IC设计

基于Pytorch的MLP实现基于Pytorch的MLP实现

基于Pytorch的MLP实现 目标 使用pytorch构建MLP网络 训练集使用MNIST数据集 使用GPU加速运算 要求准确率能达到92%以上 保存模型 实...

49311
来自专栏AI科技评论

开发 | 用 Kaggle 经典案例教你用 CNN 做图像分类!

前言 在上一篇专栏中,我们利用卷积自编码器对 MNIST 数据进行了实验,这周我们来看一个 Kaggle 上比较经典的一个图像分类的比赛 CIFAR( CIFA...

4026
来自专栏Python中文社区

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

KNN(K近邻算法)是一种不需要学习任何参数同时也非常简单的机器学习算法,既可以用来解决分类问题也可以用来解决回归问题。直观解释这个算法就是'近朱者赤,近墨者黑...

1262

扫码关注云+社区

领取腾讯云代金券