对新的输入实例,在训练数据集中找到与该实例最邻近的\(k\)个实例,这\(k\)个实例的多数属于某个类,就把该输入实例分给这个类。
\(k\) 近邻法(\(k\)-nearest neighbor, \(k\)-NN)是一种基本分类与回归方法,这里只讨论分类问题中的\(k\)-NN。
三要素:
- \(k\)值的选择
- 距离度量
- 分类决策规则
\(k\)近邻算法
输入:训练数据集\(T = \{ (x_1,y_1), (x_2,y_2), \cdot \cdot \cdot , (x_N,y_N) \}\),这里的\(y_i\)是实例的类别;实例特征向量\(x\);
输出:实例\(x\)所属的类\(y\)。
- 根据给定的距离度量,在训练集中找出与\(x\)最邻近的\(k\)个点,涵盖这\(k\)个点的\(x\)的邻域记作\(N_k(x)\);
- 在\(N_k(x)\)中根据分类决策规则(如多数表决)决定\(x\)的类别\(y\):
\[ y = \arg \max_{c_j} \sum_{x_i \in N_k(x)} I \left(y_i = c_j \right), i = 1,2, \cdot \cdot \cdot, K \]
其中,\(I\)为指示函数,等于的时候为1,否则为0。
\(k\)近邻模型
- 模型
每个训练实例附近的cell一起构成了对特征空间的一个划分。 - 距离度量
欧氏距离,或者更一般的闵可夫斯基距离等都可以。 - \(k\)值的选择
\(k\)值的减小意味着整体模型的=变得复杂,容易过拟合。通常采用交叉验证法来选取最优的\(k\)值。 - 分类决策规则
往往使用多数表决,对应于经验风险最小化。
\(k\)近邻法的实现:\(kd\)树
线性扫描(linear scan)算出所有的距离,简单但是耗时。可以使用\(kd\)树这种数据结构来提高效率,它可以表示对\(k\)维空间的一个划分,\(kd\)树的每个节点对应一个\(k\)维超矩形区域。
构造平衡\(kd\)树
- 输入:\(k\)维空间数据集\(T={x_1, x_2,...,x_N}\)
- 输出:\(kd\)树
- 开始:构造根节点
选择\(x^{(1)}\)为坐标轴,以所有实例\(x^{(1)}\)坐标的中位数为切分点,这个超平面将空间切分为两个子区域,落在这个超平面上的实例点保存在根节点。- 重复:一个一个地细分,切分成子区域
依次循环往后选择坐标轴。- 直到子区域没有实例存在时停止
搜索\(kd\)树
- 输入:已构造的\(kd\)树;目标点\(x\)
- 输出:\(x\)的最近邻
- 找到包含\(x\)的叶结点
从根节点出发,向左或向右移动,直到找到叶结点。- 以此叶结点为“当前最近点”
- 递归地向上回退,在每个结点进行以下操作:
- 若该结点更近,则以该点为“当前最近点”
- 检查该结点的另一子结点对应的区域内是否有更近的点:
如果这个区域有可能,也就是另一子节点下边可能存在更近的点:\(rightarrow\)递归进行最近邻搜索。
否则向上回退。- 回退到根结点时结束,最后的“当前最近点”即为\(x\)的最近邻。
(注:本文为读书笔记与总结,侧重算法原理,来源为《统计学习方法》一书第三章)
作者:rubbninja
出处:http://www.cnblogs.com/rubbninja/
关于作者:目前主要研究领域为机器学习与无线定位技术,欢迎讨论与指正!
学习笔记——k近邻法的更多相关文章
-
R语言学习笔记—K近邻算法
K近邻算法(KNN)是指一个样本如果在特征空间中的K个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性.即每个样本都可以用它最接近的k个邻居来代表.KNN算法适 ...
-
《统计学习方法》笔记三 k近邻法
本系列笔记内容参考来源为李航<统计学习方法> k近邻是一种基本分类与回归方法,书中只讨论分类情况.输入为实例的特征向量,输出为实例的类别.k值的选择.距离度量及分类决策规则是k近邻法的三个 ...
-
K近邻法(KNN)原理小结
K近邻法(k-nearst neighbors,KNN)是一种很基本的机器学习方法了,在我们平常的生活中也会不自主的应用.比如,我们判断一个人的人品,只需要观察他来往最密切的几个人的人品好坏就可以得出 ...
-
机器学习PR:k近邻法分类
k近邻法是一种基本分类与回归方法.本章只讨论k近邻分类,回归方法将在随后专题中进行. 它可以进行多类分类,分类时根据在样本集合中其k个最近邻点的类别,通过多数表决等方式进行预测,因此不具有显式的学习过 ...
-
k近邻法(kNN)
<统计学习方法>(第二版)第3章 3 分类问题中的k近邻法 k近邻法不具有显式的学习过程. 3.1 算法(k近邻法) 根据给定的距离度量,在训练集\(T\)中找出与\(x\)最邻近的\(k ...
-
统计学习方法与Python实现(二)——k近邻法
统计学习方法与Python实现(二)——k近邻法 iwehdio的博客园:https://www.cnblogs.com/iwehdio/ 1.定义 k近邻法假设给定一个训练数据集,其中的实例类别已定 ...
-
scikit-learn K近邻法类库使用小结
在K近邻法(KNN)原理小结这篇文章,我们讨论了KNN的原理和优缺点,这里我们就从实践出发,对scikit-learn 中KNN相关的类库使用做一个小结.主要关注于类库调参时的一个经验总结. 1. s ...
-
k近邻法
k近邻法(k nearest neighbor algorithm,k-NN)是机器学习中最基本的分类算法,在训练数据集中找到k个最近邻的实例,类别由这k个近邻中占最多的实例的类别来决定,当k=1时, ...
-
机器学习中 K近邻法(knn)与k-means的区别
简介 K近邻法(knn)是一种基本的分类与回归方法.k-means是一种简单而有效的聚类方法.虽然两者用途不同.解决的问题不同,但是在算法上有很多相似性,于是将二者放在一起,这样能够更好地对比二者的异 ...
随机推荐
-
STM32F4读写内部FLASH【使用库函数】
STM32F4Discovery开发帮使用的STM32F407VGT6芯片,内部FLASH有1M之多.平时写的代码,烧写完之后还有大量的剩余.有效利用这剩余的FLASH能存储不少数据.因此研究了一下S ...
-
C# 词法分析器(六)构造词法分析器
系列导航 (一)词法分析介绍 (二)输入缓冲和代码定位 (三)正则表达式 (四)构造 NFA (五)转换 DFA (六)构造词法分析器 (七)总结 现在最核心的 DFA 已经成功构造出来了,最后一步就 ...
-
CSS之绝对定位那些事
1.垂直居中 有时我们会使用margin: 0 auto;作居中使用.但有的时候我们需要垂直居中,例如在div里面垂直居中显示一张加载中的gif图. 下面这种写法就可以完美实现: 垂直居中的子容器 { ...
-
【转】C#中HttpWebRequest的用法详解
本文实例讲述了C#中HttpWebRequest的用法.分享给大家供大家参考.具体如下: HttpWebRequest类主要利用HTTP 协议和服务器交互,通常是通过 GET 和 POST 两种方式来 ...
-
Codeforces Round #134 (Div. 2)
A. Mountain Scenery 枚举山顶位置,满足\(r_{i-1} \lt r_i - 1 \gt r_{i+1}\). 范围要开\(2N\). B. Airport 优先队列维护最值. C ...
-
Win7关机出现关闭程序提示框
运行输入Gpedit.msc回车打开组策略,在左侧选计算机配置/管理模板/系统/关机选项,在右侧双击“关闭会阻止或取消关机的应用程序的自动终止功能”,在打开的提示框中选“已启用”,按确定即可.
-
new jQuery.common
var $c=null;jQuery(function(){$c=new jQuery.common(); $c.methods.init(); }); (function($) { $.common ...
-
HDU4607 - Park Visit(树的直径)
题目大意 给定一颗树,要求走过其中连续的k个点,使得步数最少 题解 每条边要么经过两次,要么一次,因为我们的目标就是使得走一次的边尽量的多,这样就转换成求树的直径了,求树的直径我用的是两次dfs,先随 ...
-
PHP学习笔记十二【数组排序】
<?php $arr=array(0,5,-1); $temp=0; for($i=0;$i<count($arr)-1;$i++) { for($j=0;$j<count($arr ...
-
12.04 如何更专业的使用Chrome开发者工具
顾名思义Chrome开发工具就是一个工具,它允许Web开发人员可以通过浏览器应用程序干预和操作Web页面,也可以通过这个工具调试和测试Web页面或Web应用程序.有了这个工具,你可以做很多有趣的事情: ...