学习笔记——k近邻法

时间:2022-11-12 09:32:29

对新的输入实例,在训练数据集中找到与该实例最邻近的\(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\)。

  1. 根据给定的距离度量,在训练集中找出与\(x\)最邻近的\(k\)个点,涵盖这\(k\)个点的\(x\)的邻域记作\(N_k(x)\);
  2. 在\(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\)树
  1. 开始:构造根节点
    选择\(x^{(1)}\)为坐标轴,以所有实例\(x^{(1)}\)坐标的中位数为切分点,这个超平面将空间切分为两个子区域,落在这个超平面上的实例点保存在根节点。
  2. 重复:一个一个地细分,切分成子区域
    依次循环往后选择坐标轴。
  3. 直到子区域没有实例存在时停止

搜索\(kd\)树

  • 输入:已构造的\(kd\)树;目标点\(x\)
  • 输出:\(x\)的最近邻
  1. 找到包含\(x\)的叶结点
    从根节点出发,向左或向右移动,直到找到叶结点。
  2. 以此叶结点为“当前最近点”
  3. 递归地向上回退,在每个结点进行以下操作:
    • 若该结点更近,则以该点为“当前最近点”
    • 检查该结点的另一子结点对应的区域内是否有更近的点:
      如果这个区域有可能,也就是另一子节点下边可能存在更近的点:\(rightarrow\)递归进行最近邻搜索。
      否则向上回退。
  4. 回退到根结点时结束,最后的“当前最近点”即为\(x\)的最近邻。

(注:本文为读书笔记与总结,侧重算法原理,来源为《统计学习方法》一书第三章)


作者:rubbninja
出处:http://www.cnblogs.com/rubbninja/
关于作者:目前主要研究领域为机器学习与无线定位技术,欢迎讨论与指正!

学习笔记——k近邻法的更多相关文章

  1. R语言学习笔记—K近邻算法

    K近邻算法(KNN)是指一个样本如果在特征空间中的K个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性.即每个样本都可以用它最接近的k个邻居来代表.KNN算法适 ...

  2. 《统计学习方法》笔记三 k近邻法

    本系列笔记内容参考来源为李航<统计学习方法> k近邻是一种基本分类与回归方法,书中只讨论分类情况.输入为实例的特征向量,输出为实例的类别.k值的选择.距离度量及分类决策规则是k近邻法的三个 ...

  3. K近邻法&lpar;KNN&rpar;原理小结

    K近邻法(k-nearst neighbors,KNN)是一种很基本的机器学习方法了,在我们平常的生活中也会不自主的应用.比如,我们判断一个人的人品,只需要观察他来往最密切的几个人的人品好坏就可以得出 ...

  4. 机器学习PR:k近邻法分类

    k近邻法是一种基本分类与回归方法.本章只讨论k近邻分类,回归方法将在随后专题中进行. 它可以进行多类分类,分类时根据在样本集合中其k个最近邻点的类别,通过多数表决等方式进行预测,因此不具有显式的学习过 ...

  5. k近邻法(kNN)

    <统计学习方法>(第二版)第3章 3 分类问题中的k近邻法 k近邻法不具有显式的学习过程. 3.1 算法(k近邻法) 根据给定的距离度量,在训练集\(T\)中找出与\(x\)最邻近的\(k ...

  6. 统计学习方法与Python实现(二)——k近邻法

    统计学习方法与Python实现(二)——k近邻法 iwehdio的博客园:https://www.cnblogs.com/iwehdio/ 1.定义 k近邻法假设给定一个训练数据集,其中的实例类别已定 ...

  7. scikit-learn K近邻法类库使用小结

    在K近邻法(KNN)原理小结这篇文章,我们讨论了KNN的原理和优缺点,这里我们就从实践出发,对scikit-learn 中KNN相关的类库使用做一个小结.主要关注于类库调参时的一个经验总结. 1. s ...

  8. k近邻法

    k近邻法(k nearest neighbor algorithm,k-NN)是机器学习中最基本的分类算法,在训练数据集中找到k个最近邻的实例,类别由这k个近邻中占最多的实例的类别来决定,当k=1时, ...

  9. 机器学习中 K近邻法&lpar;knn&rpar;与k-means的区别

    简介 K近邻法(knn)是一种基本的分类与回归方法.k-means是一种简单而有效的聚类方法.虽然两者用途不同.解决的问题不同,但是在算法上有很多相似性,于是将二者放在一起,这样能够更好地对比二者的异 ...

随机推荐

  1. STM32F4读写内部FLASH【使用库函数】

    STM32F4Discovery开发帮使用的STM32F407VGT6芯片,内部FLASH有1M之多.平时写的代码,烧写完之后还有大量的剩余.有效利用这剩余的FLASH能存储不少数据.因此研究了一下S ...

  2. C&num; 词法分析器(六)构造词法分析器

    系列导航 (一)词法分析介绍 (二)输入缓冲和代码定位 (三)正则表达式 (四)构造 NFA (五)转换 DFA (六)构造词法分析器 (七)总结 现在最核心的 DFA 已经成功构造出来了,最后一步就 ...

  3. CSS之绝对定位那些事

    1.垂直居中 有时我们会使用margin: 0 auto;作居中使用.但有的时候我们需要垂直居中,例如在div里面垂直居中显示一张加载中的gif图. 下面这种写法就可以完美实现: 垂直居中的子容器 { ...

  4. 【转】C&num;中HttpWebRequest的用法详解

    本文实例讲述了C#中HttpWebRequest的用法.分享给大家供大家参考.具体如下: HttpWebRequest类主要利用HTTP 协议和服务器交互,通常是通过 GET 和 POST 两种方式来 ...

  5. Codeforces Round &num;134 &lpar;Div&period; 2&rpar;

    A. Mountain Scenery 枚举山顶位置,满足\(r_{i-1} \lt r_i - 1 \gt r_{i+1}\). 范围要开\(2N\). B. Airport 优先队列维护最值. C ...

  6. Win7关机出现关闭程序提示框

    运行输入Gpedit.msc回车打开组策略,在左侧选计算机配置/管理模板/系统/关机选项,在右侧双击“关闭会阻止或取消关机的应用程序的自动终止功能”,在打开的提示框中选“已启用”,按确定即可.

  7. new jQuery&period;common

    var $c=null;jQuery(function(){$c=new jQuery.common(); $c.methods.init(); }); (function($) { $.common ...

  8. HDU4607 - Park Visit&lpar;树的直径&rpar;

    题目大意 给定一颗树,要求走过其中连续的k个点,使得步数最少 题解 每条边要么经过两次,要么一次,因为我们的目标就是使得走一次的边尽量的多,这样就转换成求树的直径了,求树的直径我用的是两次dfs,先随 ...

  9. PHP学习笔记十二【数组排序】

    <?php $arr=array(0,5,-1); $temp=0; for($i=0;$i<count($arr)-1;$i++) { for($j=0;$j<count($arr ...

  10. 12&period;04 如何更专业的使用Chrome开发者工具

    顾名思义Chrome开发工具就是一个工具,它允许Web开发人员可以通过浏览器应用程序干预和操作Web页面,也可以通过这个工具调试和测试Web页面或Web应用程序.有了这个工具,你可以做很多有趣的事情: ...