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

算法简介

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

影响算法的几个因子

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

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

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

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

距离的计算:

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

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

预测黑色点的房价

K值的选取:

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

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

K取值为1的分类效果

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

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

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

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

算法实现:

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

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics.pairwise import pairwise_distances
‘’‘
# samples为需要分类的样本
# topk为Number of neighbors
’‘’
def predict_by_k_nearest(samples, features, labels, topk):
    distance = [pairwise_distances(i, samples)[0][0] for i in features]
    index = np.argsort(distance)[:topk]
    return 1 if (y[index].mean() > 0.5) else 0

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

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

neigh = KNeighborsClassifier(n_neighbors=3,weights='uniform')
neigh.fit(X, y)
print(neigh.predict([[3]]))
print (predict_by_k_nearest([3], X, y, 3))
### [1]

补充:

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

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

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

原文发布于微信公众号 - Python中文社区(python-china)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

一文带你认识深度学习中不同类型的卷积

卷积(convolution)现在可能是深度学习中最重要的概念。靠着卷积和卷积神经网络(CNN),深度学习超越了几乎其它所有的机器学习手段。 ? 这篇文章将简要...

4489
来自专栏量化投资与机器学习

深度学习Matlab工具箱代码注释之cnnbp.m

%%========================================================================= %...

2285
来自专栏贾志刚-OpenCV学堂

VGG卷积神经网络模型解析

一:VGG介绍与模型结构 VGG全称是Visual Geometry Group属于牛津大学科学工程系,其发布了一些列以VGG开头的卷积网络模型,可以应用在人脸...

4694
来自专栏专知

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

1.4K3
来自专栏Petrichor的专栏

深度学习: 参数初始化

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

3523
来自专栏杨熹的专栏

详解 LSTM

今天的内容有: LSTM 思路 LSTM 的前向计算 LSTM 的反向传播 关于调参 ---- LSTM 长短时记忆网络(Long Short Term Mem...

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

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

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

1002
来自专栏人工智能LeadAI

黑猿大叔-译文 | TensorFlow实现Batch Normalization

原文:Implementing Batch Normalization in Tensorflow(https://r2rt.com/implementing-...

5268
来自专栏LhWorld哥陪你聊算法

【神经网络篇】--RNN递归神经网络初始与详解

由图可知,比如第二个节点的输入不仅依赖于本身的输入U1,而且依赖上一个节点的输入W0,U0,同样第三个节点依赖于前两个节点的输入,

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

译:支持向量机(SVM)及其参数调整的简单教程(Python和R)

一、介绍 数据分类是机器学习中非常重要的任务。支持向量机(SVM)广泛应用于模式分类和非线性回归领域。 SVM算法的原始形式由Vladimir N.Vapnik...

7068

扫码关注云+社区

领取腾讯云代金券