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 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

计算机视觉中,有哪些比较好的目标跟踪算法?(下)

相信很多来这里的人和我第一次到这里一样,都是想找一种比较好的目标跟踪算法,或者想对目标跟踪这个领域有比较深入的了解,虽然这个问题是经典目标跟踪算法,但事实上,可...

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

通俗的将Xgboost的原理讲明白

初看Xgboost,翻了多篇博客发现关于xgboost原理的描述实在难以忍受,缺乏逻辑性,写一篇供讨论。 观其大略,而后深入细节,一开始扎进公式反正我是觉得效...

9256
来自专栏AI研习社

视频 | 如何用 AI 预测股价?

我们能用机器学习准确地预测股价吗? 一种普遍的说法是股价是完全随机和不可预测的——让一只猴子蒙住眼睛在报纸的金融版面用飞镖选出来的投资组合,也能和投资专家精...

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

神探Sherlock如何用AI破案?教你在Excel中搭建一个人脸识别CNN网络

【导读】人脸识别技术已经有了非常广泛的应用,国内大规模监控系统背后运用的技术就是人脸识别。

961
来自专栏AI科技评论

开发 | 为什么ResNet和DenseNet可以这么深?一文详解残差块为何有助于解决梯度弥散问题。

AI科技评论按:本文作者Professor ho,原文载于其知乎主页,雷锋网获其授权发布。 传统的“提拉米苏”式卷积神经网络模型,都以层叠卷积层的方式提高网络深...

4165
来自专栏机器学习和数学

[有意思的数学] 傅里叶变换和卷积与图像滤波的关系 (2)

昨天简单介绍了Fourier变换和卷积的概念,有了一个基本的认识之后,再看图像滤波,就不会觉得那么莫名其妙了。图像滤波这其实也是个大坑,里面涉及的东西很多,想通...

3876
来自专栏人工智能LeadAI

最全算法工程师面试题目整理(一)

1 基于每日用户搜索内容,假设只有少量已知商品的情况下,如何根据用户搜索内容获取平台内没有的新商品? ? ? 答案:这是一条类似于分词“新词获取问题”,答案是...

3966
来自专栏人工智能头条

Yoshua Bengio:在能量模型中使用提前推断近似反向传播

1572
来自专栏Coding迪斯尼

深度学习:透过神经网络的内在灵活与柏拉图的哲学理念

1373
来自专栏AI研习社

详解基于朴素贝叶斯的情感分析及Python实现

相对于「 基于词典的分析 」,「 基于机器学习 」的就不需要大量标注的词典,但是需要大量标记的数据,比如: 还是下面这句话,如果它的标签是: 服务质量 - 中 ...

3598

扫码关注云+社区