专栏首页前沿技墅图穷匕见:K近邻算法与手写数字识别

图穷匕见:K近邻算法与手写数字识别

机器学习算法是从数据中产生模型,也就是进行学习的算法。我们把经验提供给算法,它就能够根据经验数据产生模型。在面对新的情况时,模型就会为我们提供判断(预测)结果。例如,我们根据“个子高、腿长、体重轻”判断一个孩子是个运动员的好苗子。把这些数据量化后交给计算机,它就会据此产生模型,在面对新情况时(判断另一个孩子能不能成为运动员),模型就会给出相应的判断。

比如,要对一组孩子进行测试,首先就要获取这组孩子的基本数据。这组数据包含身高、腿长、体重等数据,这些反映对象(也可以是事件)在某个方面的表现或者性质的事项,被称为属性或特征。而具体的值,如反映身高的“188 cm”就是特征值或属性值。这组数据的集合“(身高=188 cm,腿长=56 cm,体重=46 kg),……,(身高=189 cm,腿长=55 cm,体重=48 kg)”,称为数据集,其中每个孩子的数据称为一个样本。

从数据中学得模型的过程称为学习(learning)或者训练(training)。在训练过程中所使用的数据称为训练数据,其中的每个样本称为训练样本,训练样本所组成的集合称为训练集。

当然,如果希望获取一个模型,除了有数据,还需要给样本贴上对应的标签(label)。例如,“((个子高、腿长、体重轻),好苗子)”。这里的“好苗子”就是标签,通常我们将拥有了标签的样本称为“样例”。

学得模型后,为了测试模型的效果,还要对其进行测试,被测试的样本称为测试样本。输入测试样本时,并不提供测试样本的标签(目标类别),而是由模型决定样本的标签(属于哪个类别)。比较测试样本预测的标签与实际样本标签之间的差别,就可以计算出模型的精确度。

大多数的机器学习算法都来源于日常生活实践。K近邻算法是最简单的机器学习算法之一,主要用于将对象划分到已知类中,在生活中被广泛使用。例如,教练要选拔一批长跑运动员,如何选拔呢?他使用的可能就是K近邻算法,会选择个子高、腿长、体重轻,膝、踝关节围度小,跟腱明显,足弓较大者作为候选人。他会觉得这样的孩子有运动员的潜质,或者说这些孩子的特征和运动员的特征很接近。

理论基础

K近邻算法的本质是将指定对象根据已知特征值分类。例如,看到一对父子,一般情况下,通过判断他们的年龄,能够马上分辨出哪位是父亲,哪位是儿子。这是通过年龄属性的特征值来划分的。

上述例子是最简单的根据单个特征维度做的分类,在实际场景中,情况可能更复杂,有多个特征维度。例如,为一段运动视频分类,判断这段视频是乒乓球比赛还是足球比赛。

为了确定分类,需要定义特征。这里定义两个特征,一个是运动员“挥手”的动作,另一个是运动员“踢脚”的动作。当然,我们不能一看到“挥手”动作就将视频归类为“乒乓球比赛”,因为我们知道某些足球运动员习惯在运动场上通过挥手来跟队友进行交流。同样,我们也不能一看到“踢脚”动作就将视频归类为“足球比赛”,因为有些乒乓球运动员会通过“踢脚”动作来表达自己的感情。

我们分别统计在某段特定时间内,视频中“挥手”和“踢脚”动作的次数,发现如下规律:

  • 在乒乓球比赛的视频中,“挥手”的次数远多于“踢脚”的次数。
  • 在足球比赛的视频中,“踢脚”的次数远多于“挥手”的次数。

根据对一组视频的分析,得到如表1所示的数据。

表1 统计表格

视频编号

视频类型

挥手次数

踢脚次数

A

乒乓球比赛

4801

164

B

乒乓球比赛

4603

308

C

足球比赛

120

3866

D

乒乓球比赛

4417

412

E

乒乓球比赛

3367

526

F

乒乓球比赛

4335

140

G

乒乓球比赛

4222

365

H

乒乓球比赛

3427

190

I

足球比赛

130

4603

J

足球比赛

177

3332

K

乒乓球比赛

4980

532

L

乒乓球比赛

4240

258

M

乒乓球比赛

3040

556

N

乒乓球比赛

3521

300

O

乒乓球比赛

4763

256

P

足球比赛

259

4811

Q

足球比赛

369

4412

R

足球比赛

129

4143

S

乒乓球比赛

3863

236

T

足球比赛

365

4661

U

足球比赛

104

3130

V

足球比赛

172

4704

W

乒乓球比赛

4413

301

X

足球比赛

106

3596

Y

乒乓球比赛

3096

129

Z

足球比赛

589

4816

为了方便观察,将上述数据绘制为散点图

为了方便观察,将上述数据绘制为散点图,如图1所示。

图1 视频数据散点图

从图1中可以看到,数据点呈现聚集特征:

  • 乒乓球比赛视频中的数据点聚集在x轴坐标为[3000,5000],y轴坐标为[1,500]的区域。
  • 足球比赛视频中的数据点聚集在y轴坐标为[3000,5000],x轴坐标为[1,500]的区域。

此时,有一个视频Test,经过统计得知其中出现2000次“挥手”动作,100次“踢脚”动作。如果在图20-1中标注其位置,可以发现视频Test的位置最近的邻居是乒乓球比赛视频,因此可判断该视频是乒乓球比赛视频。

上面的例子是一个比较极端的例子,非黑即白,而实际的分类数据中往往参数非常多,判断起来也不会如此简单。因此,为了提高算法的可靠性,在实施时会取k个近邻点,这k个点中属于哪一类的较多,然后将当前待识别点划分为哪一类。为了方便判断,k值通常取奇数,这和为了能得到明确的投票结果通常将董事会成员安排为奇数的道理是一样的。

例如,已知某知名双胞胎艺人A和B长得很像,如果要判断一张图像T上的人物到底是艺人A还是艺人B,则采用K近邻算法实现的具体步骤如下:

  1. 收集艺人A和艺人B的照片各100张。
  2. 确定几个用来识别人物的重要特征,并使用这些特征来标注艺人A和B的照片。例如,根据某4个特征,每张照片可以表示为[156, 34, 890, 457]这样的形式(即一个样本点)。按照上述方式,获得艺人A的100张照片的数据集FA,艺人B的100张照片的数据集FB。此时数据集FA、FB中的元素都是上述特征值的形式,每个集合中各有100个这样的特征值。简而言之,就是使用数值来表示照片,得到艺人A的数值特征集(数据集)FA、艺人B的数值特征集FB。
  3. 计算待识别图像T的特征,并使用特征值表示图像T。例如,图像T的特征值TF可能为[257, 896, 236, 639]。
  4. 计算图像T的特征值TF与FA、FB中各特征值之间的距离。
  5. 找出产生其中k个最短距离的样本点(找出离T最近的k个邻居),统计k个样本点中属于FA和FB的样本点个数,属于哪个数据集的样本点多,就将T确定为哪个艺人的图像。例如,找到11个最近的点,在这11个点中,属于FA的样本点有7个,属于FB的样本点有4个,那么就确定这张图像T上的艺人为A;反之,如果这11个点中,有6个样本点属于FB,有5个样本点属于FA,那么就确定这张图像T上的艺人为B。

以上所述就是K近邻算法的基本思想,下面介绍一下K近邻手写数字识别。

K近邻手写数字识别

K近邻算法是借助“物以类聚、人以群分”来划分对象分类的方法。在需要判断一个对象的分类信息时,查找当前对象的最近K个邻居,通过这K个邻居的分类来判断当前对象的分类信息。

例如,有一个手写的数字,如何让计算机判断它是哪个数字呢?我们可以将该数字与一些已知的数字进行对比,看看它与哪些数字最相像。然后在与其相像的这堆数字中找出数量最多的数字,将该数字作为识别结果。

例如,我们找出与当前待判断数字最相像的7个数字(K=7),这7个数字中,有6个“数字2”,1个“数字3”。那么,就将7个数字中,数量最多的“数字2”(有6个)作为最终的识别结果。

在OpenCV中,已经对K近邻算法进行了封装,能够通过调用函数的形式实现K近邻算法。本文使用OpenCV自带的K近邻模块来实现手写数字识别。

【例】编写程序,演示K近邻算法。

在本例中,0~9的每个数字都有10个特征值。例如,数字“0”的特征值如图2所示。为了便于描述,将所有这些用于判断分类的图像称为特征图像。

图2 数字“0”的特征图像

上述过程是分步骤的分析结果,以下是全部源代码:

现在,我们要求修改例中的程序,使用OpenCV自带的函数完成对手写数字的识别。根据要求,编写代码如下:

本文节选自《OpenCV轻松入门:面向Python》。在计算机视觉这个崭新而又充满希望的研究领域,OpenCV作为辅助计算机视觉的工具,不可或缺。其与AI时代首选语言Python的结合,更产生巨大威力。其中,旨在提供易于使用的计算机视觉接口的库,包含各个领域500多个函数,阅读原文将细细梳理,通透剖析——“轻松”我们是严肃的!

本文分享自微信公众号 - 前沿技墅(Edge-Book),作者:李立宗著 小美编

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-03

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 树和森林:深度学习不是唯一的选择

    基于树的学习算法是十分流行且应用广泛的一类非参数化的有监督学习算法,这些算法既可用于分类又可用于回归。基于树的学习算法的基础是包含一系列决策规则(例如,“如果他...

    用户1682855
  • 深度推荐:YouTube召回模型设计

    要想了解YouTube的召回模型,需要依次掌握召回算法、召回模型网络结构,以及召回特征和样本设计。

    用户1682855
  • 服务化的基石:聊聊通信协议那些事儿

    用户1682855
  • 【新手总结】在.Net项目中使用Redis作为缓存服务

    最近由于项目需要,在系统缓存服务部分上了redis,终于有机会在实际开发中玩一下,之前都是自己随便看看写写,很零碎也没沉淀下来什么,这次算是一个系统学习和实践过...

    HOHO
  • 基于OpenFlow架构的IaaS云安全

    编者按:云计算技术的服务型基础设施即服务(IaaS),以其可扩展性、高效性及弹性等特点正在成为资源利用的主导方式。在从云计算的IaaS应用获得便捷的同时,安全漏...

    SDNLAB
  • 姬小光前端小讲堂【第001期】

    如果你还不知道前端开发是干嘛的,那美工你一定听说过;如果连美工也没听说过,那姑且就当我是个做网页的好啦~

    姬小光
  • 大数乘大数

    1 /*coder @Gxjun*/ 2 #include<stdio.h> 3 #include<string.h> 4 #include<stdli...

    Gxjun
  • 比特币闪电网络就要来了,竞争币会因此消失吗?

    过去的几个月时间里,比特币网络的交易手续费飞涨,达到了历史最高点30美元。很多人建议推出一种交易成本更低、网络也不容易堵的加密货币来替代比特币。 高昂的链上交易...

    企鹅号小编
  • iOS 后台持续定位

    在日常的工作开发中,有时会遇到需要在后台持续运行的需求。对于这个需求,安卓实现起来比较简单,而iOS来说就比较复杂了。我们公司就有后台持续定位并且上传上传地理坐...

    赵哥窟
  • 区块链101:什么是闪电网络?

    “闪电网络”被认为是目前正在开发的加密货币扩展的最有效的解决方案之一,它有效地在比特币之上创建了一层,使快速和廉价的交易能够满足比特币区块链的要求。 这一想法是...

    首席架构师智库

扫码关注云+社区

领取腾讯云代金券