学习KNN(一) 图像分类与KNN原理

学习KNN(一) 图像分类与KNN原理 学习KNN(二)KNN算法手写数字识别的OpenCV实现 学习KNN(三)KNN+HOG实现手写数字识别

简介

KNN算法,即K近邻算法是一种监督学习算法,本质上是要在给定的训练样本中找到与某一个测试样本A最近的K个实例,然后统计k个实例中所属类别计数最多的那个类,就是A的类别。 从上面一句话中可以看出,KNN的原理非常简单粗暴,而且是一种“在线”的学习方式,即每一次分类都需要遍历所有的训练样本,此外KNN算法还有几个要素:K,距离,分类决策规则。

要素

对于KNN而言有三个要素: 1.K的选择: K值是KNN算法中为数不多的超参数之一,K值的选择也直接影响着模型的性能。 如果我们把k值设置的比较小,那么意味着我们期望个到一个更复杂和更精确的模型,同时更加容易过拟合; 相反,如果K值越大,模型机会越简单,一个很极端的例子就是如果将K值设置的与训练样本数量相等,即K=N,那么无论是什么类别的测试样本最后的测试结果都会是测试样本中数量最多的那个类。 2.距离的度量: 距离的度量描述了测试样本与训练样本的临近程度,这个临近程度就是K个样本选择的依据,在KNN算法中,如果特征是连续的,那么距离函数一般用曼哈顿距离(L1距离)或欧氏距离(L2距离),如果特征是离散的,一般选用汉明距离。 曼哈顿距离在KNN中其实就是样本特征每一个维度上的差值的和:

欧氏距离在KNN中其实就是样本特征每一个维度上的差值的平方和开根号:

汉明距离:

3.分类决策规则: 通过上面提到的K与距离两个概念,我们就能选择出K个与测试样例最近的训练样本,如何根据这K个样本决定测试样例的类别就是KNN的分类决策规则,在KNN中最常用的就是多数表决规则。但是该规则严重依赖于训练样本的数目,我们后面会提到。

图像分类问题

那么KNN算法如何应用到图像分类问题中,其实问题也就是如何评价一张待分类的图像A与P个训练样本图像中间的距离呢? 其中关键的问题就是图像的特征选择成什么,把问题往更大的方面考虑下,对于图像而言,(传统)机器学习与深度学习的一个很大区别是后者的自动特征抽取,所以深度学习的问世在一定程度上改变了人们对图像处理问题的侧重点,从特征描述到网络结构。所以在下面我们可以不严格的分为两类考虑,直接使用图像与使用一种图像特征提取方法。

1.直接分类 所谓的直接分类本质上是将图像的每个像素点的像素值作为特征,那么此时两种图像的距离(假设使用L1)就是每个对应位置的像素点的像素值差值的绝对值的和。

那么两张图的L1距离为 371。 2.对特征分类 然后很多时候我们不会直接使用像素值作为图像的特征来使用,因为它并不能从本质上反映了人对图像的认知,比如我们将一张图稍稍向一个方向平移一段距离,在人眼看来他们应该是一类,甚至就是同一张,但是如果用像素值计算距离的话,距离确很大。 所以在更多的时候,要计算距离的对象是一些描述子生成的特征,举个例子,HOG+SVM的方法在行人检测中有很好的效果,而SVM的作用也是个分类器,如果换成KNN的话也是可行的(可行指的是原理上可行,效果如何并未考证),所以此时KNN计算的对象其实是HOG生成的描述子,而不再是图像的像素。

但是很不幸的是,KNN在图像问题中几乎不会使用,这个观点来源于斯坦福CS231n,它的原话是 K-Nearest Neighbor on images never used. 原因有两个: 1.很差的测试效率; 2.整个图像水平的距离度量可能非常不直观。 如说第二个原因可以靠着一些特征描述子来解决的话,那么第一个问题就是KNN算法的硬伤,在机器学习中其实我们对测试阶段的时间容忍要远远高于训练阶段,因为最终使用模型解决问题时足够快就可以了,CNN普遍是这样。但是这个问题在KNN中就会无限的暴露出来,“在线”学习的方式决定了样本量越大,分类过程就会越慢。

总结

1.对于样本不平均问题,KNN相比于其他监督学习算法容忍度更差。 2.KNN的计算量和数据存储量都很大。 3.但是KNN的思想简单,在某些方便可以带来很高的准确率,比如在经典的手写数字识别问题上,KNN的准确率可以排在第二位。 4.KNN是一种在线的学习方式,效率低,而且样本量越大效率就越低。

针对于以上问题,各种改进的算法主要在两个方向上对KNN作出改进,第一个是如何解决样本不平衡问题,第二个是如何提高分类效率。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法工程师

深度学习入门

引言 近几年来人工智能越来越火,大家都已经知道了AlphaGo的威力,然而在其背后,从技术层面来说,深度学习功不可没。那么深度学习到底是什么,其...

2967
来自专栏ACM算法日常

第四篇:《机器学习之逻辑回归(上)》

前面我们学习了线性回归,它通过输入一个样本的所有特征,然后和参数计算得到了自己的预测值,再通过梯度下降完成代价函数的最小化。

975
来自专栏应兆康的专栏

21. 关于偏差和方差的实例

1361
来自专栏AI科技大本营的专栏

什么是迁移学习?它都用在深度学习的哪些场景上?这篇文章替你讲清楚了

翻译 | 刘畅 迁移学习是机器学习方法之一,它可以把为一个任务开发的模型重新用在另一个不同的任务中,并作为另一个任务模型的起点。 这在深度学习中是一种常见的方法...

35010
来自专栏机器之心

深度 | 从Boosting到Stacking,概览集成学习的方法与性能

选自Statsbot 作者:Vadim Smolyakov 机器之心编译 参与:Jane W 集成学习(Ensemble learning)通过组合几种模型来提...

2588
来自专栏Python小屋

Python使用K-means聚类算法进行分类案例一则

K-means算法是经典的基于划分的聚类方法,是十大经典数据挖掘算法之一,其基本思想是:以空间中k个点为中心进行聚类,对最靠近它们的对象归类。通过迭代的方法,逐...

3016
来自专栏云时之间

译文 朴素贝叶斯算法总结

在所有的机器学习分类算法中,朴素贝叶斯和其他绝大多数的分类算法都不同。对于大多数的分类算法,比如决策树,KNN,逻辑回归,支持向量机等,他们都是判别方法,也就是...

2899
来自专栏应兆康的专栏

21. 关于偏差和方差的实例

思考我们的猫咪分类器。一个理想的分类器(如:人为分类)会在这个任务中有着完美的表现。

34210
来自专栏机器之心

解读 | ICLR-17 最佳论文:理解深度学习需要重新思考泛化问题

选自morning paper 机器之心编译 参与:黄玉胜、黄小天 本文是一篇很好的综述论文:结果很容易理解,也让人有些惊讶,但其意指又会让人思考良久。 对于文...

3789
来自专栏专知

【干货】监督学习与无监督学习简介

【导读】本文是一篇入门级的概念介绍文章,主要带大家了解一下监督学习和无监督学习,理解这两类机器学习算法的不同,以及偏差和方差详细阐述。这两类方法是机器学习领域中...

4478

扫码关注云+社区