k近邻算法理论(一)

时间 :2014.07.05

地点:基地

-----------------------------------------------------------------------------------

一、简述

K近邻法(k-nearest neighbor,kNN)是一种基本分类与回归方法。k近邻的输入为实例的特征向量,对应特征空间中的点,输出为实例的类别。k近邻算法的基本思想是:给定训练数据集,实例类别已定,在对目标实例进行分类时,我们根据与目标实例k个最近邻居的训练实例的类别,通过多数表决的方式进行决定。也就是说,k近邻算法实际上是利用了训练数据集对特征向量空间进行了划分,并作为其分类的模型。这样k近邻算法涉及三个最基本的元素:

1.k值的选择,即取多大的k最适合于分类

2.距离的度量,即怎么样一个距离计算判断是否为目标实例的邻居

3.分类决策

-----------------------------------------------------------------------------------

二、k近邻算法

输入:给定训练数据集

其中 为输入实例的特征向量,为实例的类别,通过建模后,我们在输入一个实例特定向量x

输出:实例x所属的类别。

算法描述:

1.根据给定的距离度量,在训练集T中找出与x最近邻的k个点,涵盖这k个点的x的邻域我们记为:

2.在x的k个点邻域中,根据分类决策规则(一般为多数表决)决定x的类别y,即:

argmax是取使得表达式取值最大的参数值,在这里即得到对应的哪个类别值,这类别使得右边表达式取值最大。即表示:在x的领域里,邻域元素大部分属于某个类别时右式取值最大,然后我们把对应的类别(即参数取值)赋给结果。

k近邻算法在k=1时是最近邻算法,k近邻算法也没有显示的学习过程。

-----------------------------------------------------------------------------------

三、k近邻模型

3.1 k近邻的模型

k近邻法的建模,实际上就是对特征空间的划分,当训练集、距离度量、k值和分类决策规则都确定后,对于任何一个新的输入实例它所属的类型也就会被确定。于是整个过程就相当于将特征空间划分为一些子空间,我们的任务就是要确定子空间里的每个点所属的类。

在特征空间中(特征空间的维数为输入向量x的维数),对于每个训练实例点x,我们把距离该点比其他点更近的所有点组成一个单元。这样,每个实例点都拥有一个单元,所有训练实例点的单元构成了对特征空间的一个划分。

3.2 距离的度量

特征空间中两个实例点的距离是两个实例点相似程度的反映,k近邻模型的特征空间由n维实数向量空间张成,距离的度量也有很多方式,比如欧式距离Lp距离等等。

我们设特征空间X是n维实数向量空间张成,其中两个实例 为 ,这样,这两个实例的Lp距离定义如下:

p为大于或等于1的正整数,特别的

当p等于1时就是曼哈顿距离(街道距离)

当p等于2时就是欧式距离(直线距离)

当p为无穷大时就是向量各个维度坐标中距离最大的值,即

3.3k值的选择

k值的选择能对k近邻法的结果产生很大的影响,合理地选择k值的大小,对于预测结果的准确性能起到莫大的作用。

首先,如果k值较小,就相当于用较小的邻域中的训练实例进行预测,当然,这样学习的近似误差会减小,只有与输入实例相对更近的k个训练实例才会对预测结果起作用,缺点是学习的估计误差会增大,预测结果会对近邻的实例点非常敏感,即如果近邻点实例是个噪声点,然而这个噪声点对于分类所占的分量也就随着k值的减小而增大,于是容易在预测时出现误判。换而言之,随着k值的减小,整体模型更为复杂,容易发生过拟合。

其次,如果k值较大,就相当于用较大的邻域训练实例进行预测,这样就可以减少学习的估计误差,但缺点是学习的近似误差会增大,此时输入实例较远的训练实例也会对预测起到作用,使预测发生错误。k值的增大意味着整体的模型变得简单。一种极端案例就是k=N,此时无论输入的实例是什么,都只是简单的预测训练实例中最多的类,忽略了训练实例中大量的有用信息,模型过于简单。

实际应用中,k值取一个比较小的数值,常采用交叉验证的方法来选取一个最优的k值。

3.4分类决策规则

k近邻法中分类规则一般采用多数表决的方式,即由k个近邻总训练实例中多数类决定输入实例的类。多数表决规则等价于经验风险最小化。

k近邻算法理论(一)

时间: 07-04

k近邻算法理论(一)的相关文章

从K近邻算法、距离度量谈到KD树、SIFT+BBF算法

从K近邻算法.距离度量谈到KD树.SIFT+BBF算法 从K近邻算法.距离度量谈到KD树.SIFT+BBF算法 前言 前两日,在微博上说:“到今天为止,我至少亏欠了3篇文章待写:1.KD树:2.神经网络:3.编程艺术第28章.你看到,blog内的文章与你于别处所见的任何都不同.于是,等啊等,等一台电脑,只好等待..”.得益于田,借了我一台电脑(借他电脑的时候,我连表示感谢,他说“能找到工作全靠你的博客,这点儿小忙还说,不地道”,有的时候,稍许感受到受人信任也是一种压力,愿我不辜负大家对我的信任)

K近邻算法

1.1.什么是K近邻算法 何谓K近邻算法,即K-Nearest Neighbor algorithm,简称KNN算法,单从名字来猜想,可以简单粗暴的认为是:K个最近的邻居,当K=1时,算法便成了最近邻算法,即寻找最近的那个邻居.为何要找邻居?打个比方来说,假设你来到一个陌生的村庄,现在你要找到与你有着相似特征的人群融入他们,所谓入伙. 用官方的话来说,所谓K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居),这K个实例的多数属

K近邻算法-KNN

何谓K近邻算法,即K-Nearest Neighbor algorithm,简称KNN算法,单从名字来猜想,可以简单粗暴的认为是:K个最近的邻居,当K=1时,算法便成了最近邻算法,即寻找最近的那个邻居.为何要找邻居?打个比方来说,假设你来到一个陌生的村庄,现在你要找到与你有着相似特征的人群融入他们,所谓入伙. 用官方的话来说,所谓K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居),这K个实例的多数属于某个类,就把该输入实例分

『cs231n』作业1问题1选讲_通过代码理解K近邻算法&交叉验证选择超参数参数

通过K近邻算法探究numpy向量运算提速 茴香豆的"茴"字有... ... 使用三种计算图片距离的方式实现K近邻算法: 1.最为基础的双循环 2.利用numpy的broadca机制实现单循环 3.利用broadcast和矩阵的数学性质实现无循环 图片被拉伸为一维数组 X_train:(train_num, 一维数组) X:(test_num, 一维数组) 方法验证 import numpy as np a = np.array([[1,1,1],[2,2,2],[3,3,3]]) b

K 近邻算法

声明: 1,本篇为个人对<2012.李航.统计学习方法.pdf>的学习总结,不得用作商用,欢迎转载,但请注明出处(即:本帖地址). 2,因为本人在学习初始时有非常多数学知识都已忘记,所以为了弄懂当中的内容查阅了非常多资料.所以里面应该会有引用其它帖子的小部分内容,假设原作者看到能够私信我,我会将您的帖子的地址付到以下. 3.假设有内容错误或不准确欢迎大家指正. 4.假设能帮到你.那真是太好了. 描写叙述 给定一个训练数据集,对新的输入实例.在训练数据集中找到与该实例最邻近的K个实例,若这K个实

k近邻算法(knn)的并行mpi实现

C语言的串行版本已经前些篇博客给出,现在来讨论给算法的并行程序.该算法有很多种并行的方法,比较好的思路有以下几种. 思路一: 也是最容易想到的,就是将训练集在每台机器上都备份一份,然后将预测数据集平分给每台机器.这种并行方案就相当于这些机器单独计算一份预测集,简单来说有多少台机器,其加速比就是多少,由于不需要进程间的通信,所以是一种理想的并行方法. 思路二: 采用主从模式,让一个进程充当master,其他进程作为slave.master结点读取一条测试数据并广播给所有进程(当然也可以选择所有进程

《机器学习实战》——K近邻算法

原理: (1) 输入点A,输入已知分类的数据集data (2) 求A与数据集中每个点的距离,归一化,并排序,选择距离最近的前K个点 (3) K个点进行投票,票数最多的分类即为所求 优点: 简单,可用于非线性分类 缺点: 当样本不均衡时影响投票结果: 分类结果受K值影响: 时空复杂度高:需要保存全部数据O(N),每次取前k个都要与全部数据进行计算O(N),耗费内存大且计算量大 改进: 样本均衡化 太小的K值容易受噪音影响,大的K值减小噪音但会使分类边界模糊,最合适的方法是用交叉验证确定K值:先确定

k近邻(KNN)复习总结

摘要: 1.算法概述 2.算法推导 3.算法特性及优缺点 4.注意事项 5.实现和具体例子 6.适用场合内容: 1.算法概述 K近邻算法是一种基本分类和回归方法:分类时,根据其K个最近邻的训练实例的类别,通过多数表决等方式进行预测:k近邻法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的"模型".(Cover和Hart 在1968)--参考自<统计学习方法> 2.算法推导 2.1 kNN三要素 k值的选择:当k值较小时,预测结果对近邻的实例点非常敏感,容易发生过拟

K近邻法

K近邻算法 给定一个训练数据集,对新的输入实例,在训练数据集中找到跟它最近的k个实例,根据这k个实例的类判断它自己的类(一般采用多数表决的方法). 算法详解: 输入:训练数据集 其中,为实例的特征向量,

统计学习方法 (第3章)K近邻法 学习笔记

第3章 K近邻法 k近邻算法简单.直观:给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类.当K=1时,又称为最近邻算法,这时候就是将训练数据集中与x最邻近点作为x的类. 3.1 k近邻模型 模型由三个基本要素--距离度量.k值得选择.和分类决策规则决定. 3.1.1 距离度量 p=2时,称为欧式距离,p=1时,称为曼哈顿距离. 3.1.2 k值的选择 k 值的选择会对k 近邻法的结果产生重大影响.如果选择较小的k