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

相关文章

来自专栏desperate633

LeetCode Invert Binary Tree题目分析

Invert a binary tree. 4 / \ 2 7 / \ / \1 3 6 9 to4 / \ 7 2 / \ / \9 6 3 1 Tri...

841
来自专栏聊聊技术

原 初学图论-Kahn拓扑排序算法(Kah

2878
来自专栏java闲聊

JDK1.8 ArrayList 源码解析

当运行 ArrayList<Integer> list = new ArrayList<>() ; ,因为它没有指定初始容量,所以它调用的是它的无参构造

1192
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

1716
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1692
来自专栏开发与安全

算法:AOV网(Activity on Vextex Network)与拓扑排序

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网(Activity on Vextex ...

2517
来自专栏Java Edge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

422
来自专栏后端之路

LinkedList源码解读

List中除了ArrayList我们最常用的就是LinkedList了。 LInkedList与ArrayList的最大区别在于元素的插入效率和随机访问效率 ...

19510
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1K4
来自专栏刘君君

JDK8的HashMap源码学习笔记

3008

扫码关注云+社区