这篇文章重点讲解一下k近邻算法的最经典算法kd树的相关知识点以及最终的总结!希望看完这篇文章,大家对kd树能够有一个直观的感觉~

一、k近邻算法的回顾

1.我们提出了k近邻算法,算法的核心思想是,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例,这K个实例的多数属于某个类,就把该输入实例分类到这个类中。更通俗说一遍算法的过程,来了一个新的输入实例,我们算出该实例与每一个训练点的距离(这里的复杂度为0(n)比较大,所以引出了下文的kd树等结构),然后找到前k个,这k个哪个类别数最多,我们就判断新的输入实例就是哪类!

2.与该实例最近邻的k个实例,那么最近邻的衡量标准是是什么。这个最近邻的定义是通过不同距离函数来定义,我们最常用的是欧式距离。

3.为了保证每个特征同等重要性,我们这里对每个特征进行归一化。

4.k值的选取,既不能太大,也不能太小,何值为最好,需要实验调整参数确定!

二、k近邻算法中的分类决策规则讲解

k近邻算法的分类决策规则通俗来说就是k 近邻法中的分类决策规则往往是多数表决决定,背后的数学思维是什么?

k 近邻法中的分类决策规则往往是多数表决,即由输入实例的 k 个近邻的训练实例中的多数类决定输入实例的类。

多数表决规则(majority voting rule)有如下解释:如果分类的损失函数为 0-1 损失函数,分类函数为:

https://pic3.zhimg.com/v2-42340e5b426f3cabbf2dd4743bffdd90_b.png

那么误分类的概率是:

https://pic1.zhimg.com/v2-99dbc311f29743e737f0df96b86ed9a8_b.png

https://pic4.zhimg.com/v2-5b3abf769eee1bf03aa1435b551b8353_b.png

换句话说,目前候选种类为c1,c2….cj,我选择哪一个,使得我们的经验风险最小(经验风险通俗讲就是训练数据的错误值)。

那么由上式经验风险最小,也就是说,要我们预测出的种类属于cj类的最多(那么预测出来的种类结果和真实结果一致的越多,我们认为正确可能性就越大,也就是经验风险越小),也就是我们所说的多数表决规则。而它也等价于我们的经验风险最小。这也是我们在k近邻算法中采用多数表决规则的正确性说明!

三、k近邻法的实现:kd树原理的讲解以及kd树详细例子讲解


kd 树的结构

kd树是一个二叉树结构,它的每一个节点记载了【特征坐标,切分轴,指向左枝的指针,指向右枝的指针】。

其中,特征坐标是线性空间 Rn 中的一个点 (x1,x2,…,xn)切分轴由一个整数 r 表示,这里 1≤r≤n,是我们在 n 维空间中沿第 rr维进行一次分割。节点的左枝和右枝分别都是 kd 树,并且满足:如果 y 是左枝的一个特征坐标,那么 yr≤xr(左分支结点);并且如果 z 是右枝的一个特征坐标,那么 zr≥xr(右分支结点)。

给定一个数据样本集 S⊆Rn 和切分轴 r,以下递归算法将构建一个基于该数据集的 kd 树,每一次循环制作一个节点:
−− 如果 |S|=1,记录 S 中唯一的一个点为当前节点的特征数据,并且不设左枝和右枝。(|S| 指集合 S 中元素的数量)
−− 如果 |S|>1

哎呀,到这里有没有一点晕了,这么多文字,好罗,下面通过例子一步一步给出kd树的构建,以便容易理解!举出李航博士例子3.2!

kd树的构建!例题3.2

给定一个二维空间的数据集:

T = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}, 构造一个平衡kd树。

为了方便,我这里进行编号A(2,3)、B(5,4)、C(9,6)、D(4,7)、E(8,1)、F(7,2)

初始值r=0,对应x轴。

可视化数据点如下:

https://pic2.zhimg.com/v2-02963ee4baf049d326c42b4785530d87_b.png

首先先沿 x 坐标进行切分,我们选出 x 坐标的中位点,获取最根部节点的坐标,对数据点x坐标进行排序得:

A(2,3)、D(4,7)、B(5,4)、F(7,2)、E(8,1)、C(9,6)

则我们得到中位点为B或者F,我这里选择F作为我们的根结点,并作出切分(并得到左右子树),如图:

https://pic2.zhimg.com/v2-3cd1d305955fa5c654fd7ed87bd950a7_b.png

对应的树结构如下:

https://pic1.zhimg.com/v2-2716dd711a6597e076571f7e215148e6_b.png

根据算法,此时r=r+1=1,对应y轴,此时对应算法|S|>1,则我们分别递归的在F对应的左子树与右子树按y轴进行分类,得到中位节点分别为B,C点,如图所示:

https://pic4.zhimg.com/v2-4fc1ec4b5b699d237691b3d441402cfd_b.png

对应树结构为:

https://pica.zhimg.com/v2-7525bf5bc361f265c326a3d8d5593efe_b.png

而到此时,B的左孩子为A,右孩子为D,C的左孩子为E,均满足|S|==1,此时r = (r+1)mod2 = 0,又满足x轴排序,对x轴划分!则如图所示:

https://pic2.zhimg.com/v2-b13c4448f5919c581b6271bece2e3ae5_b.png

对应树结构如下:

https://pic3.zhimg.com/v2-09134b6a4bf5cd55bc04874f77ff56ae_b.png

恩恩,到这里为止,给定的kd树构造完成啦,**所有的数据点都能在树上的每个结点找到!**而我们根据上面构造树的过程,也能很容易的知道,来了一个新的数据点的时候,对应该层的指定维数,通过比较大小,我就能知道往左(预测点对应维度数据小于该结点对对应维度数据)走还是往右(预测点对应维度数据大于该结点对应维度数据)走,那么好的情况下,我们就能省掉一半的数据点啦~(不好的情况,哈哈,没有节省,后面会说到,这也是kd树的致命缺点~

恩,好啦,到这里为止,我们一步一步给出了kd树的构造过程。这也是李航博士书籍上例子中kd树构造的详细过程!他的图片如下:

https://pica.zhimg.com/v2-e20d55ea5cd78f4f48862c44d9921274_b.png

对应kd树为:

https://pica.zhimg.com/v2-5919cd9936fab67c0a194cb2be5b3bb4_b.png


我这里和统计学习方法例子一样,以最近邻为例加以叙述,同样的方法可以应用到k近邻。

为了让大家更好的理解,我这里直接用上面例子给大家一步一步给出过程!

首先我们来看用kd树的最近邻搜索算法流程:

输入:已构造的kd树;目标点x;

输出:x的最近邻.

(1)在kd树中找出包含目标点x的叶结点:从根结点出发,递归地向下访问kd树,若目标点x当前维的坐标小于切分点的坐标,则移动到左子节点,否则移动到右子结点.直到子结点为叶结点位置.

(2)以此叶结点为“当前最近点”

(3)递归地向上回退,在每个结点进行以下操作:

(a)如果该结点保存的实例点比当前最近点距离目标点更近,则以该实例点为“当前最近点”.

(b)当前最近点一定存在于该结点一个子结点对应的区域.检查该子结点的父结点的另一个子结点对应的区域是否有更近的点.具体地,检查另一子结点对应的区域是否以目标点为球心、以目标点与“当前最近点”间为半径的超球体相交。

如果不相交,向上回退.

(4)当回退到根结点时,搜索结束。最后的“当前最近点”即为最近邻点.

看到这里是不是有点晕了,哈哈,不要怕,下面通过例子,一步一步走一遍上面所描述的算法过程,化抽象为具体!

kd树最近邻搜索例题:

给定一个二维空间的数据集:

T = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},输入目标实例为K(8.5,1),求K的最近邻。

首先我们由上面可以给出,T的kd树对应如下:

https://pica.zhimg.com/v2-5919cd9936fab67c0a194cb2be5b3bb4_b.png

我们此时的K(8.5,1),根据算法第一步得:第一层的x轴K点为8大于F点的7,所以进入F(7,2)的右子树,进入下面红色线条区域:

https://picx.zhimg.com/v2-bfb2dd930277521e1d4979b44d3db323_b.png

到了第二层,分割平面坐标为y轴,K点y轴坐标为1,小于C点y轴坐标6,则继续向右走,在下图红色线条区域内:

https://pic1.zhimg.com/v2-56ee840fe3ea3edb4bcd641cfc557816_b.png

则此时算法对应第(1)部分完成,我们找到了叶子节点E(8,1)。

我们进行算法第(2)步,把E(8,1)作为最近邻点。此时我们算一下KE之间的距离为0.5(便于后面步骤用到).

然后进行算法第(3)步,递归的往上回退,每个结点进行相同步骤,好,我现在从E点回退到C点,对应图片如下;

https://pic1.zhimg.com/v2-c8d7c8845b6d579535328ba6f9e9138c_b.png

此时对C点进行第(3)步的(a)操作,判断一下KC距离与保存的最近邻距离(这时是KE)比较,KC距离为点K(8.5,1)与点C(9,6)之间的距离\sqrt{25.25} >最近邻0.5,于是不更新最近邻点。

然后对C点进行第(3)步的(b)操作,判断一下当前最近邻的距离画一个圆是否与C点切割面相交,如图所示:

https://pica.zhimg.com/v2-41c86985c60fb9e93c45d88739ce8c54_b.png

我们很容易看到与C点切割面并没有相交,于是执行由C点回退到它的父结点F点。如图:

https://pica.zhimg.com/v2-8e7afc3b7caa7e2cc5cda479d1ab08ba_b.png

对F点进行(a),(b)操作!

进行(a)步骤,判断FK的距离是否小于当前保存的最小值,FK=\sqrt{(7-8.5)^{2}+(2-1)^{2} }=\sqrt{1.25} >0.5,所以不改变最小距离

下面我们进行(b)步骤,为了判断F点的另一半区域是否有更小的点,判断一下当前最近邻的距离画一个圆是否与F点切割面相交,如图所示:

https://pica.zhimg.com/v2-41c86985c60fb9e93c45d88739ce8c54_b.png

发现与任何分割线都没有交点,那么执行算法最后一步,此时F点已经是根结点,无法进行回退,那么我们可以得到我们保留的当前最短距离点E点就是我们要找的最近邻点!任务完成,

并且根据算法流程,我们并没有遍历所有数据点,而是F点的左孩子根本没有遍历,节省了时间,但是并不是所有的kd树都能到达这样的效果。

四、kd树的不足以及最差情况举例

讲解这个知识点,我还是通过一个例子来直观说明!

给定一个二维空间的数据集:

T = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},输入目标实例为K(8,3),求K的最近邻。

首先我们由上面可以给出,T的kd树对应如下:

https://pica.zhimg.com/v2-5919cd9936fab67c0a194cb2be5b3bb4_b.png

我们此时的K(8,3),根据算法第一步得:第一层的x轴K点为8大于F点的7,所以进入F(7,2)的右子树,进入下面红色线条区域:

https://pic3.zhimg.com/v2-2e0c07a9583b237747d8422ce7a41648_b.png

(注意:这里叶子节点画不画分割线都没有关系!)

到了第二层,分割平面坐标为y轴,K点y轴坐标为3,小于C点y轴坐标6,则继续向右走,在下图红色线条区域内:

https://pic1.zhimg.com/v2-c4720c3958cdf5c9ade9ba9c4f635cdc_b.png

则此时算法对应第(1)部分完成,我们找到了叶子节点E(8,1)。

我们进行算法第(2)步,把E(8,1)作为最近邻点。此时我们算一下KE之间的距离为2(便于后面步骤用到).

然后进行算法第(3)步,递归的往上回退,每个结点进行相同步骤,好,我现在从E点回退到C点,对应图片如下;

https://pic1.zhimg.com/v2-c8d7c8845b6d579535328ba6f9e9138c_b.png

此时对C点进行第(3)步的(a)操作,判断一下KC距离与保存的最近邻距离(这时是KE)比较,KC距离为点K(8,3)与点C(9,6)之间的距离\sqrt{10} >最近邻2,于是不更新最近邻点。

然后对C点进行第(3)步的(b)操作,判断一下当前最近邻的距离画一个圆是否与C点切割面相交,如图所示:

https://pica.zhimg.com/v2-e5584222989de056cd4bd4ad3427a54e_b.png

我们很容易看到与C点切割面并没有相交,于是执行由C点回退到它的父结点F点。如图:

https://pica.zhimg.com/v2-8e7afc3b7caa7e2cc5cda479d1ab08ba_b.png

对F点进行(a),(b)操作!

进行(a)步骤,判断FK的距离是否小于当前保存的最小值,FK=\sqrt{(7-8)^{2}+(2-3)^{2} }=\sqrt{2}

<2,所以将最小距离替换为FK的距离!

**下面我们进行(b)步骤,为了判断F点的另一半区域是否有更小的点,**判断一下当前最近邻的距离画一个圆是否与F点切割面相交,如图所示:

https://pica.zhimg.com/v2-e5584222989de056cd4bd4ad3427a54e_b.png

我们可以看出,此时圆与F点有交点,那么说明F点左侧是有可能存在与K点距离更小的点(注:这里我们人为看起来好像没有,但是计算机不知道,必须搜索下去,只要以当前最小值画圆发现与节点切割面有交点,那么一定要进行搜索,不然数据如果是下图:)

https://picx.zhimg.com/v2-0e57a14c656812ed001004fc714c8e01_b.png

如果不进行搜索,我们就可能会漏掉Z数据点,因为KZ比当前最小值KF小!

此时相交,我们就需要再F点的左孩子进行搜索,一直搜索到叶子节点A,然后进行(a),(b)步骤,继续回溯到它的父亲结点B,以及最后到达F点,完成最后的最近邻是F点,这里几乎遍历了所有数据点,几乎退化了为线性时间0(n)了。这也是kd树的最差的情况。

当给定的数据分布很差的时候,我们每一次计算画圆过程中,**都会与每一个分割面相交的时候,都会递归搜索到该结点的另一个子空间中遍历,那么这样最坏的情况是进行线性时间搜索!**比如构建的kd树和数据分布如下:

https://pic3.zhimg.com/v2-b1772df69e6cb106c9822a8f9cb41b3a_b.png

如图所示,我们可以看到几乎所有的数据离给定预测的点距离很远,每次进行算法第三步判断是否与分割面有交点的时候,几乎每个面都有交点,只要有交点,就必须将该点的另一半结点遍历到叶子结点,重复的进行算法步骤,导致了搜索的低效!

五、k近邻方法的一些优缺点总结

优点:

1.KNN分类方法是一种非参数的分类技术,简单直观,易于实现!只要让预测点分别和训练数据求距离,挑选前k个即可,非常简单直观。

2.KNN是一种在线技术,新数据可以直接加入数据集而不必进行重新训练

缺点及改进:

1.当样本不平衡时,比如一个类的样本容量很大,其他类的样本容量很小,输入一个样本的时候,K个邻近值大多数都是大样本容量的那个类,这时可能会导致分类错误。

改进方法:对K邻近点进行加权,也就是距离近的权值大,距离远的点权值小。

**2.**计算量较大,每个待分类的样本都要计算它到全部点的距离,根据距离排序才能求得K个临近点。

改进方法:先对已知样本带你进行裁剪,事先去除分类作用不大的样本,采取kd树以及其它高级搜索方法BBF等算法减少搜索时间。

参考:

李航老师《统计学习方法》