{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "kNN算法：  \n",
    "输入：训练数据集$T = \\left\\{ \\left( x_{1}, y_{1} \\right), \\left( x_{2}, y_{2} \\right), \\cdots, \\left( x_{N}, y_{N} \\right) \\right\\}$，其中$x_{i} \\in \\mathcal{X} \\subseteq R^{n}$是实例的特征向量，$ y_{i} \\in \\mathcal{Y} = \\left\\{ c_{1}, c_{2}, \\cdots, c_{K} \\right\\}$是实例的类别，$ i = 1, 2, \\cdots, N$；实例特征向量$x$  \n",
    "输出：实例$x$所属的类$y$  \n",
    "1. 根据给定的距离度量，在训练集$T$中找出与$x$最近邻的$k$个点，涵盖这$k$点的$x$的邻域记作$N_{k} \\left( x \\right)$；  \n",
    "2. 在$N_{k} \\left( x \\right)$中根据分类决策规则决定$x$的类别$y$：\n",
    "\\begin{align*}  \\\\ & y = \\arg \\max_{c_{j}} \\sum_{x_{i} \\in N_{k} \\left( x \\right)} I \\left( y_{i} = c_{j} \\right), \\quad i=1,2, \\cdots, N; \\quad j=1,2,\\cdots,K \\end{align*}   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "设特征空间$\\mathcal{X}$是$n$维实数向量空间$R^{n}$，$x_{i},x_{j} \\in \\mathcal{X},x_{i} = \\left( x_{i}^{\\left( 1 \\right)},x_{i}^{\\left( 2 \\right) },\\cdots,x_{i}^{\\left( n \\right) } \\right)^{T},x_{j} = \\left( x_{j}^{\\left( 1 \\right)},x_{j}^{\\left( 2 \\right) },\\cdots,x_{j}^{\\left( n \\right) } \\right)^{T}$，$x_{i},x_{j}$的$L_{p}$距离\n",
    "\\begin{align*}  \\\\ & L_{p} \\left( x_{i},x_{j} \\right) = \\left( \\sum_{l=1}^{N} \\left| x_{i}^{\\left(l\\right)} - x_{j}^{\\left( l \\right)} \\right|^{p} \\right)^{\\dfrac{1}{p}}\\end{align*}  \n",
    "其中，$p \\geq 1$。当$p=2$时，称为欧氏距离，即\n",
    "\\begin{align*}  \\\\ & L_{2} \\left( x_{i},x_{j} \\right) = \\left( \\sum_{l=1}^{N} \\left| x_{i}^{\\left(l\\right)} - x_{j}^{\\left( l \\right)} \\right|^{2} \\right)^{\\dfrac{1}{2}}\\end{align*}  \n",
    "当$p=1$时，称为曼哈顿距离，即\n",
    "\\begin{align*}  \\\\ & L_{1} \\left( x_{i},x_{j} \\right) =  \\sum_{l=1}^{N} \\left| x_{i}^{\\left(l\\right)} - x_{j}^{\\left( l \\right)} \\right| \\end{align*} \n",
    "当$p=\\infty$时，是各个坐标距离的最大值，即\n",
    "\\begin{align*}  \\\\ & L_{\\infty} \\left( x_{i},x_{j} \\right) =  \\max_{l} \\left| x_{i}^{\\left(l\\right)} - x_{j}^{\\left( l \\right)} \\right| \\end{align*} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "多数表决规则：如果分类的损失函数为0-1损失函数，分类函数\n",
    "\\begin{align*}  \\\\ & f: R^{n} \\to \\left\\{ c_{1}, c_{2}, \\cdots, c_{K} \\right\\} \\end{align*}   \n",
    "则误分类的概率\n",
    "\\begin{align*}  \\\\ & P \\left( Y \\neq f \\left( X \\right) \\right) = 1 - P \\left( Y = f\\left( X \\right) \\right) \\end{align*} \n",
    "对给定的实例$x \\in \\mathcal{X}$，其最近邻的$k$个训练实例点构成的集合$N_{k} \\left( x \\right)$。如果涵盖$N_{k} \\left( x \\right)$的区域的类别是$c_{j}$，则误分类率\n",
    "\\begin{align*}  \\\\ & \\dfrac{1}{k} \\sum_{x_{i} \\in N_{k} \\left( x \\right)} I \\left( y_{i} \\neq c_{j}\\right) = 1 -\\dfrac{1}{k} \\sum_{x_{i} \\in N_{k} \\left( x \\right)} I \\left( y_{i} = c_{j}\\right) \\end{align*}  \n",
    "即经验风险最小化等价于多数表决规则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "平衡kd树构造算法：  \n",
    "输入：$k$维空间数据集$T = \\left\\{  x_{1}, x_{2}, \\cdots, x_{N} \\right\\}$，其中$x_{i} = \\left( x_{i}^{\\left(1\\right)}, x_{i}^{\\left(1\\right)},\\cdots,x_{i}^{\\left(k\\right)} \\right)^{T}, i = 1, 2, \\cdots, N$；  \n",
    "输出：kd树  \n",
    "1. 开始：构造根结点，根结点对应于包涵$T$的$k$维空间的超矩形区域。   \n",
    "选择$x^{\\left( 1 \\right)}$为坐标轴，以$T$中所欲实例的$x^{\\left( 1 \\right)}$坐标的中位数为切分点，将根结点对应的超矩形区域切分成两个子区域。切分由通过切分点并与坐标轴$x^{\\left( 1 \\right)}$垂直的超平面实现。  \n",
    "由根结点生成深度为1的左、右子结点：坐子结点对应坐标$x^{\\left( 1 \\right)}$小于切分点的子区域，右子结点对应于坐标$x^{\\left( 1 \\right)}$大与切分点的子区域。  \n",
    "将落在切分超平面上的实例点保存在跟结点。\n",
    "2. 重复：对深度为j的结点，选择$x^{\\left( l \\right)}$为切分坐标轴，$l = j \\left(\\bmod k \\right) + 1 $，以该结点的区域中所由实例的$x^{\\left( l \\right)}$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{\\left( l \\right)}$垂直的超平面实现。  \n",
    "由根结点生成深度为$j+1$的左、右子结点：坐子结点对应坐标$x^{\\left( l \\right)}$小于切分点的子区域，右子结点对应于坐标$x^{\\left( l \\right)}$大与切分点的子区域。  \n",
    "将落在切分超平面上的实例点保存在跟结点。\n",
    "3. 直到两个子区域没有实例存在时停止。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "kd树的最近邻搜索算法：  \n",
    "输入：kd树；目标点$x$  \n",
    "输出：$x$的最近邻  \n",
    "1. 在kd树中找出包含目标点$x$的叶结点：从跟结点出发，递归地向下访问kd树。若目标点$x$当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。   \n",
    "2. 以此叶结点为“当前最近点”。\n",
    "3. 递归地向上回退，在每个结点进行以下操作：  \n",
    "3.1 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。  \n",
    "3.2 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。  \n",
    "如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；  \n",
    "如果不相交，向上回退。  \n",
    "4. 当回退到根结点时，搜索结束。最后的“当前最近点”即为$x$的当前最近邻点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}