这是我参加mlhub123组织的书籍共读计划的读书笔记,活动见mlhub第一期读书计划

  • 阅读章节:第三章:k近邻法
  • 开始时间:2018-09-29
  • 结束时间:2018-10-23(比较忙)
  • 目标:读完第三章,掌握基本概念,产出一篇笔记
  • 博客地址

k近邻法(k-nearest neighbor,k-NN)是一种基本分类与回归方法,本书只讨论分类形式:

  • k近邻算法
  • k近邻模型
  • k近邻法的实现:kd树

k近邻算法

什么是k近邻算法?

给定一个训练集:$T = {(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$,其中$x_i$为实例的特征向量,$y_i\in \gamma =\{c_1,c_2,...,c_k\}$,输入实例特征向量$x$,输出该实例特征向量的类别$y$

关键点在于是如何进行类别的判断,描述如下:

思想很简单,就是给定一个训练集,输入一个实例,就在训练集中找出与该实例最邻近的k个实例,然后进行多数表决,这k个实例的多数属于某个类,就把该输入实例分为这个类

上面3.1的公式这里解释一下:随着变量j的递增,$c_j$代表不同的类别,每次$x_i$对应的$y_i$会和$c_j$进行比较,如果$y_i$等于$c_j$,该类别计数加一,直到$y_1,y_2,,,y_i$与$c_j$比较完毕,累加之和最高的$c_j$就是输出$y$(意思就是判断输入实例邻域的实例在此类别占据多少个数目),至此,分类成功

k近邻模型

k近邻法使用的模型实际上对应于对特征空间的划分,模型由三个基本要素——距离 度量、k值的选择和分类决策规则决定

模型

通过上面的叙述,当我们知道:

  • 训练集
  • 距离度量(明可夫斯基距离)
  • k值
  • 分类决策规则(多数表决)

此时对于任何一个新的输入实例,都可以确定其所属的类

什么是单元?

特征空间中,对每个训练实例点$i_x$,距离该点比其他点更近的所有点组成一个区域,叫作单元(cell),最终会将特征空间划分为下图所示:

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映,k近邻模型的特征空间一般是n维实数向量空间$R^n$,使用的距离是欧氏距离,但也可以是其他距离,如更一般的$L_p$距离($L_p$ distance)或Minkowski距离(Minkowski distance)

k值的选择

k值的选择会对k近邻法的结果产生重大影响:

  • 如果较小:k值的减小就意味着整体模型变得复杂,容易发生过拟合
  • 如果较大:k值的增大就意味着整体的模型变得简单

分类决策规则

k近邻法中的分类决策规则往往是多数表决(majority voting rule),即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类,实际上等价于经验风险最小化

k近邻法的实现:kd树

实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索

k近邻法最简单的实现方法是线性扫描(linear scan),这时要计算输入实例与每一个训练实例的距离,当训练集很大时,计算非常耗时,这种方法是不可行的

为了提高k近邻搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数,具体方法很多,下面介绍其中的kd树(kd tree)方法

构造kd树

k-d树(k-dimensional树的简称),是一种分割k维数据空间的数据结构,主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)

k-d树是二叉树,表示对k维空间的一个划分(partition),其中每个结点对应于一 个k维超矩形区域,且该超平面垂直于当前划分维度的坐标轴,并在该维度上将空间划分为两部分,一部分在其左子树,另一部分在其右子树

实际做一道例题有助于对算法的理解:

  • 首先对数据集排序:(2,3),(4,7),(5,4),(7,2),(8,1),(9,6),其中值为(7,2)
  • 根结点生成深度为1的左、右子结点,(2,3),(4,7),(5,4)挂在(7,2)节点的左子树,(8,1),(9,6)挂在(7,2)节点的右子树
  • 构建(7,2)节点的左子树,此时切分维度k=2(可以理解为y轴),中值(5,4)作为分割平面,(2,3)挂在其左子树,(4,7)挂在其右子树
  • 构建(7,2)节点的右子树,此时切分维度k=2(可以理解为y轴),中值(6,6)作为分割平面
  • 无法继续划分,k-d tree构建完成

搜索kd树

给定一个目标点,搜索其最近邻,首先找到包含目标点的叶结点;然后从该叶结点出发,依次回退到父结点;不断查找与目标点最邻近的结点,当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上,效率大为提高

说明

有助于理解kd树的博客文章: