K近邻算法

原创声明:本文为 SIGAI 原创文章,仅供个人学习使用,未经允许,不得转载,不能用于商业目的。

我们在网上购买水果的时候经常会看到同一种水果会标有几种规格对应不同价格进行售卖,水果分级售卖已经是电商中常见的做法,那么水果分级具体是怎么操作的呢?一种简单的做法是根据水果果径的大小进行划分。今年老李家苹果丰收了,为了能卖个好价钱,老王打算按照果径对苹果进行分级。想法是很好的,但是面对成千上万的苹果这可愁坏了老李。老李的儿子小李是计算机系毕业的,他知道这件事后设计了一个算法,按照老李的要求根据果径大小定义了5个等级

70mm左右(<72.5mm)

75mm左右(>=72.5mm&&<77.5mm)

80mm左右(>=77.5mm&&<82.5mm)

85mm左右(>=82.5mm&&<87.5mm)

90mm左右(>=87.5mm)

如下图

当一个未分级的苹果拿到后可以首先将这个苹果的果径测量出来,然后再和这5个等级的苹果进行对照,假如未分级苹果的果径是82mm则划分为第三个等级,如果是83mm则划分为第二个等级,以此类推。基于这个原则小李发明了一个分级装置,见下图,大大提高了工作效率,很快将老李的问题解决了。

老李的问题是一个经典的最近邻模板匹配,根据一个已知类别参考模板对未分类的数据进行划分,小李选择的每个类的模板数是一,现实生活中的问题往往会复杂很多,可能需要多个参考模板进行综合决策,当选定的模板数为k的时候就是k近邻算法的思想了,最近邻算法是k近邻算法k=1时的一种特殊情况。

k近邻算法简称kNN算法,由Thomas等人在1967年提出[1]。它基于以下思想:要确定一个样本的类别,可以计算它与所有训练样本的距离,然后找出和该样本最接近的k个样本,统计这些样本的类别进行投票,票数最多的那个类就是分类结果。因为直接比较样本和训练样本的距离,kNN算法也被称为基于实例的算法。

基本概念

确定一个样本所属类别的一种最简单的方法是直接比较它和所有训练样本的相似度,然后将其归类的最相似的样本所属的那个类,这是一种模板匹配的思想。下图6.1是使用k近邻思想进行分类的一个例子:

图6.1 k近邻分类示意图

在上图中有红色和绿色两类样本。对于待分类样本即图中的黑色点,我们寻找离该样本最近的一部分训练样本,在图中是以这个矩形样本为圆心的某一圆范围内的所有样本。然后统计这些样本所属的类别,在这里红色点有12个,圆形有2个,因此把这个样本判定为红色这一类。上面的例子是二分类的情况,我们可以推广到多类,k近邻算法天然支持多类分类问题。

预测算法

k近邻算法没有求解模型参数的训练过程,参数k由人工指定,它在预测时才会计算待预测样本与训练样本的距离。

k近邻算法实现简单,缺点是当训练样本数大、特征向量维数很高时计算复杂度高。因为每次预测时要计算待预测样本和每一个训练样本的距离,而且要对距离进行排序找到最近的k个样本。我们可以使用高效的部分排序算法,只找出最小的k个数;另外一种加速手段是k-d树实现快速的近邻样本查找。

一个需要解决的问题是参数k的取值。这需要根据问题和数据的特点来确定。在实现时可以考虑样本的权重,即每个样本有不同的投票权重,这称方法称为为带权重的k近邻算法。另外还其他改进措施,如模糊k近邻算法[2]。

距离定义

根据前面的介绍,kNN算法的实现依赖于样本之间的距离值,因此需要定义距离的计算方式。接下来介绍常用的几种距离定义,它们适用于不同特点的数据。

常用距离定义

这是我们最熟知的距离定义。在使用欧氏距离时应该尽量将特征向量的每个分量归一化,以减少因为特征值的尺度范围不同所带来的干扰。否则数值小的特征分量会被数值大的特征分量淹没。例如,特征向量包含两个分量,分别为身高和肺活量,身高的范围是150-200厘米,肺活量为2000-9000,如果不进行归一化,身高的差异对距离的贡献显然为被肺活量淹没。欧氏距离只是将特征向量看做空间中的点,并没有考虑这些样本特征向量的概率分布规律。

距离度量学习

Mahalanobis距离中的矩阵可以通过对样本的学习得到,这称为距离度量学习。距离度量学习通过样本集学习到一种线性变换,目前有多种实现。下面我们介绍文献[9]的方法,它使得变换后每个样本的k个最近邻居都和它是同一个类,而不同类型的样本通过一个大的间隔被分开,这和第8章将要介绍的线性判别分析的思想类似。如果原始的样本点为x,变换之后的点为y,在这里要寻找的是如下线性变换:

为了保证kNN算法能准确的分类,任意一个样本的目标邻居样本要比其他类别的样本更接近于该样本。对每个样本,我们可以将目标邻居想象成为这个样本建立起了一个边界,使得和本样本标签值不同的样本无法入侵进来。训练样本集中,侵入这个边界并且和该样本不同标签值的样本称为冒充者(impostors),这里的目标是最小化冒充者的数量。

为了增强kNN分类的泛化性能,要让冒充者离由目标邻居估计出的边界的距离尽可能的远。通过在kNN决策边界周围加上一个大的安全间隔(margin),可以有效的提高算法的鲁棒性。

同类样本尽量都成为最近的邻居节点;而不同类型的样本会拉开距离。这会有效的提高kNN算法的分类精度。

实验程序

下面用一个例子程序来演示kNN算法的使用,这里我们对2个类进行分类。

图6.2 kNN算法的分类效果

在这里分类边界是曲线,证明了kNN算法有非线性分类的能力。以上结果来自SIGAI云端实验室,如果你对此感兴趣,可以向SIGAI公众号发消息,申请使用。我们的实验室提供了强大的功能,可以帮助大家更容易,深刻的理解各种数学,机器学习,深度学习,以及应用领域的算法。

应用

kNN算法简单但却有效,如果能够定义合适的距离度量,它可以取得很好的性能。kNN算法被成功的用于文本分类[5-7],图像分类[8-11]等模式识别问题。应用kNN算法的关键是构造出合适的特征向量以及确定合适的距离函数。

参 考 文 献

[1] Thomas M Cover, Peter E Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 1967.

[2] James M Keller, Michael R Gray, James Givens. A fuzzy K-nearest neighbor algorithm. systems man and cybernetics, 1985.

[3] Thierry Denoeux. A k-nearest neighbor classification rule based on Dempster-Shafer theory. systems man and cybernetics, 1995

[4] Trevor Hastie, Rolbert Tibshirani. Discriminant adaptive nearest neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996.

[5] Bruno Trstenjak, Sasa Mikac, Dzenana Donko. KNN with TF-IDF based Framework for Text Categorization. Procedia Engineering, 2014.

[6] J He, Ahhwee Tan, Chew Lim Tan. A Comparative Study on Chinese Text Categorization Methods. pacific rim international conference on artificial intelligence, 2000.

[7] Shengyi Jiang, Guansong Pang, Meiling Wu, Limin Kuang. An improved K-nearest-neighbor algorithm for text categorization. 2012, Expert Systems With Application.

[8] Oren Boiman, Eli Shechtman, Michal Irani. In defense of Nearest-Neighbor based image classification. 2008, computer vision and pattern recognition.

[9] Kilian Q Weinberger, Lawrence K Saul. Distance Metric Learning for Large Margin Nearest Neighbor Classification. 2009, Journal of Machine Learning Research.

[10] S. Belongie, J. Malik, J. Puzicha. Shape matching and obejct recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4):509-522, 2002.

[11] P. Y. Simard, Y. LeCun, I. Decker. Efficient pattern recognition using a new transformation distance. In S. Hanson, J. Cowan, and L. Giles, editors, Advances in Neural Information Processing Systems 6, pages 50-58, San Mateo, CA, 1993. Morgan Kaufman.

[12] S. Chopra, R. Hadsell, Y. LeCun. Learning a similarity metric discriminatively, with application to face verification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2005), pages 349-356, San Diego, CA, 2005.

推荐文章

[1] 机器学习-波澜壮阔40年 SIGAI 2018.4.13.

[2] 学好机器学习需要哪些数学知识?SIGAI 2018.4.17.

[3] 人脸识别算法演化史 SIGAI 2018.4.20.

[4] 基于深度学习的目标检测算法综述 SIGAI 2018.4.24.

[5] 卷积神经网络为什么能够称霸计算机视觉领域? SIGAI 2018.4.26.

[6] 用一张图理解SVM的脉络 SIGAI 2018.4.28.

[7] 人脸检测算法综述 SIGAI 2018.5.3.

[8] 理解神经网络的激活函数 SIGAI 2018.5.5.

[9] 深度卷积神经网络演化历史及结构改进脉络-40页长文全面解读 SIGAI 2018.5.8.

[10] 理解梯度下降法 SIGAI 2018.5.11.

[11] 循环神经网络综述—语音识别与自然语言处理的利器 SIGAI 2018.5.15

[12] 理解凸优化 SIGAI 2018.5.18

[13]【实验】理解SVM的核函数和参数 SIGAI 2018.5.22

[14] 【SIGAI综述】行人检测算法 SIGAI 2018.5.25

[15] 机器学习在自动驾驶中的应用—以百度阿波罗平台为例(上) SIGAI 2018.5.29

[16] 理解牛顿法 SIGAI 2018.5.31

[17]【群话题精华】5月集锦—机器学习和深度学习中一些值得思考的问题 SIGAI 2018.6.1

[18] 大话Adaboost算法 SIGAI 2018.6.2

[ 19] FlowNet到FlowNet2.0:基于卷积神经网络的光流预测算法 SIGAI 2018.6.4

[20] 理解主成分分析(PCA) SIGAI 2018.6.6

[21] 人体骨骼关键点检测综述 SIGAI 2018.6.8

[22] 理解决策树 SIGAI 2018.6.11

[23] 用一句话总结常用的机器学习算法 SIGAI 2018.6.13

[24] 目标检测算法之YOLO SIGAI 2018.6.15

[25] 理解过拟合 SIGAI 2018.6.18

[26] 理解计算:从√2到AlphaGo ——第1季 从√2谈起 SIGAI 2018.6.20

[27] 场景文本检测—CTPN算法介绍 SIGAI 2018.6.22

[28] 卷积神经网络的压缩和加速 SIGAI 2018.6.25

原创声明:本文为 SIGAI 原创文章,仅供个人学习使用,未经允许,不得转载,不能用于商业目的。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

利用显著-偏置卷积神经网络处理混频时间序列

显著-偏置卷积神经网络简介 金融时间序列通常通常包含多个维度,不同维度数据的采样频率也不一致。例如螺纹钢研究员通常关心螺纹钢的因素有日频更新的现货螺纹钢价格,周...

2735
来自专栏信数据得永生

《Scikit-Learn与TensorFlow机器学习实用指南》 第1章 机器学习概览

42210
来自专栏积累沉淀

数据挖掘算法之深入朴素贝叶斯分类

写在前面的话:   我现在大四,毕业设计是做一个基于大数据的用户画像研究分析。所以开始学习数据挖掘的相关技术。这是我学习的一个新技术领域,学习难度比我以往学过的...

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

通俗易懂的机器学习入门指导

机器学习,也叫数据挖掘、模式识别;其定义很多。但大白话的说,机器学习要做的就是,现在有一些数据(比如你人人网好友和他们的发言),我们要对数据进行...

3307
来自专栏AI研习社

2017 知乎看山杯从入门到第二

利用一个暑假的时间,做了研究生生涯中的第一个正式比赛,最终排名第二,有些小遗憾,但收获更多的是成长和经验。我们之前没有参加过机器学习和文本相关的比赛,只是学过一...

2697
来自专栏机器之心

MIT提出精细到头发丝的语义分割技术,打造效果惊艳的特效电影

随着电影越来越关注 CGI,电影制作人必须更加擅长「合成」,即将前景和背景图像融合,比如将演员放在飞机或行星上,或者放在电影《黑豹》里瓦坎达这样的虚构世界中。

1051
来自专栏AI科技评论

学界 | 腾讯AI Lab解读多篇ACL 2018入选长文

本文转载自腾讯 AI Lab,微信号 tencent_ailab。本文将详解 2018 年 NLP 领域顶级学术会议 ACL 上,腾讯AI Lab入选 5 篇文...

1072
来自专栏DT数据侠

看脸时代,“颜值”竟然都有了计算方法!

“魔镜魔镜告诉我,谁是世界上最美的女人?”这句伴随童年的话也有现实版哦~神经网络可以预测人脸颜值,这方面也出现了不少研究。今年年初华南理工大学的研究者发布论文,...

920
来自专栏闪电gogogo的专栏

莫凡《机器学习》笔记

机器学习方法 1.1 机器学习 通常来说, 机器学习的方法包括: 监督学习 supervised learning:(有数据有标签)在学习过程中,不断的向计算...

4394
来自专栏AI科技评论

干货 | 如何测量 NLP 模型的性别偏见到底有多大?

AI 科技评论按:本文由 Ben Packer, Yoni Halpern, Mario Guajardo-Céspedes & Margaret Mitche...

1201

扫码关注云+社区