kNN/03. k-近邻的算法实现：kd 树.ipynb

{
 "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",
    "<img src=\"../images/bst.png\" width=\"600px\" />\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",
    "<img src=\"../images/kd-create.webp\" width=\"600px\" />\n",
    "\n",
    "可以看到，l1 左边都是语文成绩低于 45 分的，l1 右边都是语文成绩高于 45 分的，l2 下方都是语文成绩低于 45 分且数学成绩低于 50 分的，l2 上方都是语文成绩低于 45 分且数学成绩高于 50 分的，后面以此类推。下面的图示，更清晰地表示了 kd 树的结构及其对应的二叉树：\n",
    "\n",
    "<img src=\"../images/kd-bst.webp\" width=\"600px\" />\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
}