{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "根据前面的学习，我们知道实现 k-近邻算法的关键就是如何找到距离某个样本最近的 k 个样本。最简单的实现方法是线性扫描（linear scan），或者叫做暴力搜索，也就是依次计算输入样本和每个训练样本的距离，不过当训练集非常大时，这种计算非常耗时，是行不通的。\n", "\n", "为了提高 k-近邻搜索的效率，人们想出了很多特殊的数据结构存储训练数据，以减少计算距离的次数，其中 **kd 树**（kd tree）是最基础，也是最重要的一种。它的基本思想是对搜索空间进行层次划分，将整个空间划分为特定的几个部分，然后在特定空间的部分内进行搜索操作。如果划分空间没有重叠，这种情况叫做 **Clipping**，其代表算法就是 kd 树；如果划分空间有重叠，这种情况叫 **Overlapping**，其代表算法是 R 树。\n", "\n", "### 什么是 kd 树\n", "\n", "kd 树的概念是斯坦福大学 Jon Louis Bentley 于 1975 年在 ACM 杂志上发表的一篇论文 **Multidimensional Binary Search Trees Used for Associative Searching** 中正式提出的。它是 K-dimension tree 的缩写。其本质是一颗二叉树，树中存储的是一些 k 维数据，当 k = 1 时，kd 树就是我们非常熟悉的 **二叉搜索树**（Binary Search Tree，BST）。\n", "\n", "二叉搜索树具有如下性质：\n", "\n", "* 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；\n", "* 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；\n", "* 它的左、右子树也分别为二叉搜索树；\n", "\n", "我们不妨看一个例子，假设我们有一个表格存储了学生的语文成绩 chinese、数学成绩 math 和 英语成绩 english，如果要查询语文成绩介于 30～93 分的学生，如何处理？假设学生数量为N，如果顺序查询，则其时间复杂度为O(N)，当学生规模很大时，其效率显然很低，如果使用二叉树，则其时间复杂度为O(logN)，能极大地提高查询效率。将语文成绩存在构造好的二叉树里，就相当于在语文成绩上建立了索引，二叉搜索树示意图为：\n", "\n", "\n", "\n", "现在我们考虑二维的情况：查询语文成绩介于 30～93 分，且数学成绩介于 30～90 分的学生，又该如何处理呢？很显然，我们可以分别使用二叉树对语文成绩和数学成绩建立索引，先在语文成绩中查询得到集合 S1，再在数学成绩中查询得到集合 S2，然后计算 S1 和 S2 的交集，若 |S1|=m，|S2|=n，则其时间复杂度为 O(m\\*n)，有没有更好的办法呢？\n", "\n", "实际上，kd 树可以更好的解决这个问题。\n", "\n", "### 构造 kd 树\n", "\n", "我们首先在二维平面上画出所有学生的成绩分布，然后先根据语文成绩，将所有人的成绩分成两半，其中一半的语文成绩 <=a，另一半的语文成绩 >a，分别得到集合 S1 和 S2；然后针对 S1，根据数学成绩分为两半，其中一半的数学成绩 <=b1，另一半的数学成绩 >b1，分别得到 S3 和 S4，针对 S2，也根据数学成绩分为两半，其中一半的数学成绩 <=b2，另一半的数学成绩 >b2，分别得到 S5 和 S6，然后再根据语文成绩分别对 S3、S4、S5、S6 继续执行类似划分得到更小的集合，然后再在更小的集合上根据数学成绩继续，以此类推...\n", "\n", "上面描述的就是构建 kd 树的基本思路，其构建后的 kd 树如下图所示：\n", "\n", "\n", "\n", "可以看到，l1 左边都是语文成绩低于 45 分的，l1 右边都是语文成绩高于 45 分的，l2 下方都是语文成绩低于 45 分且数学成绩低于 50 分的，l2 上方都是语文成绩低于 45 分且数学成绩高于 50 分的，后面以此类推。下面的图示，更清晰地表示了 kd 树的结构及其对应的二叉树：\n", "\n", "\n", "\n", "### kd 树相关算法\n", "\n", "上面只是介绍了构造 kd 树的基本思路，其具体的算法实现可以参考后面的参考链接。除了 kd 树的构造之外，关于 kd 树的常见算法还有：\n", "\n", "* kd 树的插入\n", "* kd 树的删除\n", "* kd 树的搜索\n", "\n", "关于 kd 树的搜索又可以分成几种不同的应用场景：\n", "\n", "* 范围查询：譬如上面的例子，查询语文成绩介于 30～93 分，且数学成绩介于 30～90 分的学生；\n", "* k-近邻查询：查询距离某个点最近的几个点，当 k = 1 时，就相当于最近邻查询；\n", "\n", "要实现 kNN 算法，就要用到这里的 kd 树的构造算法和 k-近邻查询算法，这两个是重点，其他的算法可以稍微了解一下，可以参考后面的参考链接。在李航老师的《统计学习方法》中，也介绍了 kd 树的构造算法和最近邻查询的算法以及相应的实例。\n", "\n", "关于 kd 树的搜索，还有一种改进算法，叫做 **BBF 算法**，另外，除了可以使用 kd 树来构造多维索引，还可以使用上面提到过的 **R 树**，以及 **球树**、**M树**、**VP树**、**MVP树** 等等数据结构。\n", "\n", "### 参考\n", "\n", "1. https://zhuanlan.zhihu.com/p/23966698\n", "1. https://blog.sengxian.com/algorithms/k-dimensional-tree\n", "1. https://www.jianshu.com/p/ffe52db3e12b\n", "1. https://wuzhiwei.net/kdtree/\n", "1. https://blog.csdn.net/v_JULY_v/article/details/8203674" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.1" } }, "nbformat": 4, "nbformat_minor": 2 }