k近邻法(kNN)
2024-09-06 02:02:23
《统计学习方法》(第二版)第3章
3 分类问题中的k近邻法
k近邻法不具有显式的学习过程。
3.1 算法(k近邻法)
- 根据给定的距离度量,在训练集\(T\)中找出与\(x\)最邻近的\(k\)个点,涵盖这k个点的x的邻域记作\(N_k(x)\)
- 在\(N_k(x)\)中根据分类决策规则(如多数表决)决定\(x\)的类别\(y\)
3.2 k近邻模型的三个基本要素
距离度量
特征空间中,对每个实例点的距离是两个实例点相似程度的反映。
\(L_p\)距离:
\[
L_p(x_i,x_j)=(\sum_{t=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p},p \ge 1
\]
\(p=2→欧氏距离\)
\(p=1→曼哈顿距离\)
\(p=\infty→各个坐标距离的最大值\)
\[
L_{\infty}(x_i,x_j)=max_l|x_i^{(l)}-x_j^{(l)}|
\]
k值的选择
k值较小,学习的近似误差会减小,但是意味着整体模型变得复杂,容易发生过拟合。
k值较大,整体的模型变得简单,但是学习的近似误差会增大。
通常采用交叉验证法来选取最优的k值。
分类决策规则
往往选择多数表决,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
3.3 实现
最简单的实现:线性扫描(当训练集很大时,计算非常耗时,不可行)
另一种想法:使用特殊的结构存储训练数据
kd树
kd树是一种对K维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。
kd树是二叉树, 表示对K维空间的一个划分( partition)。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
算法(构造平衡kd树)
算法(用kd树的最近邻搜索)
最新文章
- MVC
- SQL Server 索引和表体系结构(包含列索引)
- python常用文件处理函数_1
- Web自动化基础(一)使用Selenium定位元素
- HDU 5596 GTW likes gt 倒推
- EF中使用语句 或存储过程 查询(转)
- IOS高级开发 runtime(一)
- JavaScript 中常用的 正则表达式
- spring jdbc 笔记3
- Spring MVC前后端的数据传输
- 在没有DOM操作的日子里,我是怎么熬过来的(上)
- Docker pull下来的镜像(2)
- Java基础_0308:String类的常用方法
- springboot整合三 共享session,集成springsession
- JAVA spring 常用包作用详解(转)
- 简单利用jQuery,让前端开发不再依赖于后端的接口
- html----不常见标签
- tomcat之日志切割
- 浅谈JavaScript DDOS 攻击原理与防御
- iOS编程中比较两个日期的大小