第3章-k近邻法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第3章 k近邻法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> * k-nearest neighbor, k-NN。一种基本的分类与回归方法。本节只讨论分类问题中的K-NN法。\n",
    "> * 输入：实例的特征向量。\n",
    "> * 输出：实例的类别，可以是多类别。\n",
    "> * 首先有一个训练集；对于新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。\n",
    "> * 不具备显式学习过程。\n",
    "> * 本质：运用training data，将特征空间进行划分，并作为其分类的model；送进一个新的实例，会看该实例位于特征空间的哪一个划分中，来标记其类别。\n",
    "> * 三个基本要素：k值的选择，距离度量，分类决策规则。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 边际可视化\n",
    "from matplotlib.colors import ListedColormap\n",
    "\n",
    "# classification <= 5\n",
    "def plot_decision_regions(X, y, classifier=None, scaler = None, resolution=0.02, need_samples=1):\n",
    "    # setup marker generator and color map\n",
    "    markers = ('s','x','o','^','v')\n",
    "    colors = ('red','blue','lightgreen','gray','cyan')\n",
    "    cmap = ListedColormap(colors[:len(np.unique(y))])\n",
    "    \n",
    "    # In this way, we can just draw a scatter pic\n",
    "    if classifier:\n",
    "        # plot the decision surface\n",
    "        x1_min, x1_max = X[:,0].min()-1, X[:,0].max()+1\n",
    "        x2_min, x2_max = X[:,1].min()-1, X[:,1].max()+1\n",
    "        xx1,xx2 = np.meshgrid(np.arange(x1_min,x1_max,resolution),\n",
    "                              np.arange(x2_min,x2_max,resolution))\n",
    "        temp = np.array([xx1.ravel(),xx2.ravel()]).T\n",
    "        if scaler:\n",
    "            temp = scaler.transform(temp)\n",
    "        Z = classifier.predict(temp)\n",
    "        Z = Z.reshape(xx1.shape)\n",
    "        plt.contourf(xx1, xx2, Z, alpha=0.3, cmap=cmap)\n",
    "        plt.xlim(xx1.min(), xx1.max())\n",
    "        plt.ylim(xx2.min(), xx2.max())\n",
    "    \n",
    "    if need_samples:\n",
    "        # plot class samples\n",
    "        for idx,cl in enumerate(np.unique(y)):\n",
    "            plt.scatter(x=X[y==cl,0],\n",
    "                        y=X[y==cl,1],\n",
    "                        alpha=0.8,\n",
    "                        c=colors[idx],\n",
    "                        marker=markers[idx],\n",
    "                        label=cl,\n",
    "                        edgecolor='black')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.1 k近邻算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__定义__：给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最近邻(涉及“距离度量”)的k个实例(涉及“k值选择”)，这k个实例的多数属于某个类就把该输入实例分为这个类(涉及“分类决策规则”)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__算法: k-nn__\n",
    "\n",
    "* 输入：\n",
    "    1. 训练数据集，其中$\\mathbf{x_i}\\in \\mathbf{R}^n$，$y_i \\in \\{c_1,c_2,\\cdots,c_K\\}$，$i=1,2,\\cdots,N$\n",
    "$$T=\\{(\\mathbf{x_1},y_1),(\\mathbf{x_2},y_2),\\cdots,(\\mathbf{x_N},y_N)\\}$$\n",
    "    2. 实例$\\mathbf{x}$\n",
    "* 输出：实例$\\mathbf{x}$所属的类别$y$\n",
    "* 过程：\n",
    "    1. 根据给定的距离度量，在训练集$T$中找到与$\\mathbf{x}$最邻近的$k$个点，涵盖这$k$个点的邻域记做$N_k(\\mathbf{x})$；\n",
    "    2. 在$N_k(\\mathbf{x})$中根据分类决策规则(如多数决)，决定$\\mathbf{x}$的类别$y$：\n",
    "$$y = \\underset{c_j}{argmax}\\sum_{x_i \\in N_k(\\mathbf{x})} I(y_i=c_j),\\quad i=1,2,\\cdots,N;\\quad j=1,2,\\cdots,K$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.2 k近邻模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于k-nn，当“三要素”以及training data给定后，特征空间中的每一个点，其所属的类(预测)被唯一确定，也就是特征空间被唯一地划分了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__最近邻算法__：$k=1$时，新输入的实例的类别由与它最近的训练集中的实例确定。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD9CAYAAACcJ53WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGAtJREFUeJzt3X9sXXd5x/H30x+0t6U2beaEmrY0dKZL1KnQWda2yihrABmoQzaGSiQjkaF5ahiUZZNDJ2VRVzatV1MEk5ZIFpAOmZUCpRFmLGsV8OpstJekFNraULWUQXFJIA1JM7zQlmd/nHvse+1r+9g55557zvm8pDS+18fuY6X56Nvn+8vcHRERyY5z0i5ARESWR8EtIpIxCm4RkYxRcIuIZIyCW0QkYxTcIiIZEym4zew2M3vCzJ40s48mXZSIiCxsyeA2s+uAPwV6gOuBm82sK+nCRESksSgj7nXAw+7+S3d/GfhP4A+TLUtERBYSJbifAN5iZqvM7CLgncCVyZYlIiILOW+pB9x90szuAh4ETgPfAV6e+5yZDQKDABdeePHvXHHFb8Vcqkj+HT8OnD7NG17/StqlSJMdefrpn7t7R5RnbblnlZjZ3wPPufuehZ7p6ur23bsPL+v7ihRdpQJjeycY33gHDAykXY40mW3adMTdu6M8u+SIG8DMVrv7MTO7Cvgj4PfOpkARqVfecRyOHWXD6gmFtiwpUnAD95nZKuAl4EPufiLBmkQKpVwGjh1lfN8zwAVplyMZECm43b036UJEiiZsjQAMrRsF1qdbkGRG1BG3iMRs7L7jbFg9wZ13XYBCW5ZDW95FUlDe9iwcO8qdv/3FtEuRDNKIW6TJyluD9sj4rfdAjyYiZfkU3CJNNBPa+54hOEVCZPkU3CJNEE5EdpZOcO+eF9IuRzJOwS2SsJERmDo4UTMRKXJ2FNwiCSqXgckJhtaN0j+klSMSDwW3SELC0NYWdombglskAeEWdq0ckSQouEVippUjkjQFt0hMtHJEmkXBLRIDrRyRZlJwi5wlrRyRZlNwi5yF+klI9bOlORTcIitU3vYsTE9rElKaLtLpgGb2F2b2pJk9YWb3mNmFSRcmzTf3Frtl3mpXGJVKsHKkk6lqaIs015LBbWavAz4CdLv7dcC5wPuSLkya68AB2L9/Nqzdg9cHDqRbV6sp7zjO2N5gElIrRyQtUVsl5wElM3sJuAiYSq4kaTZ3mJ6G8fHg9ebNQWiPj0Nvb/B5s3RrbAUzV4ypny0pWzK43f0nZvaPwI+AaeABd38g8cqkacyCsIYgrMMA7+0N3ldo12yq2XiHdkJK6qK0Si4F3g2sBTqBi81s3n+5ZjZoZofN7PDJkz+Lv1JJVG14hxTagfK2Z4HqTkidOSItIMrk5FuBZ939Z+7+EvBl4PfnPuTuw+7e7e7d7e0dcdcpCQt72rVqe95FpUlIaUVRetw/An7XzC4iaJVsBA4nWpU0VRjaYU+7tscNxRx5ayektLIoPe5HzOxLwKPAy8C3geGkC5PmMYNSqb6nHbZNSqXihXa4E1KhLa0q0qoSd98F7Eq4FklRX1/96pEwvAsX2uFOSJ2hLS0s0gYcKYa5Ia3QFmlN2vIuQs32dYW2ZICCWwpvZo22bquRjFBwS6HpthrJIgW3FJJuq5EsU3BL4YRrtBXaklUKbikUrdGWPFBwS2HoijHJCwW3FEK4RluhLXmg4Jbc0xptyRsFt+TaTGhrjbbkiIJbcktrtCWvFNySO1qjLXmn4JZc0TnaUgQKbsmNMLS1ckTyTsEtuRCu0dbKESmCJYPbzK4F7q156w3A37j7JxKrSiSicH02FPt0v5u2b+fUyZPz3m9rb+fru3enUJEkKcrVZd8H3gRgZucCPwHuT7gukWiOHa0Gdg9FXjly6uRJDre3z3u/u0GYS/Ytt1WyEXjG3f8niWJEoqpdORKEtkhxLDe43wfc0+gTZjYIDAJ0dFx1lmWJLEyTkFJ0kYPbzF4FbAJub/R5dx+mevt7V1e3x1KdyByahBRZ3oj7HcCj7n40qWJEFjNzmW+BJyFFYHnBvYUF2iQiSdP29cW1tbc3nIhsazBhKdkXKbjN7CLgbcCfJVuOSD1tX49GS/6KJVJwu/svgVUJ1yJSR9vXRRrTzklpSbqtRmRhCm5pOfWTkOpni8yl4JaWMnPxgSYhRRak4JaWUb9yREQWouCW1GnliMjyKLglVVo5IrJ8Cm5JjVaOiKyMgltSEa4cUWiLLJ+CW5puZuWIDooSWZFEgvunz/7fzAoB1tWPpjo79Xe1yGZCWwdFiaxYIsF97dozjO9+htHyBDBa97nywX7KB+d8wbr5/6s8NJREZZKmmeV+2lgjclbMPf6js7u7uvxwxENvgnCvV57sn/+gwj2z6u6F1BptkYZs06Yj7t4d5dnUe9yNJqb6mfOXe2SE0akb6t4qT/ZT3jrnC1evmfe9hu7S2VhpGhlB29dFYpZ6cEcyMMDcMXijcJ+r9+Auylvn3PugcG+a2jXaCm2R+GQjuKNoMOM5PjAn3CsVeOqpurdu+e+PUN566fzvVyoFv1/SpmBfgXCNtjbWiMQv6kUKrwE+BVwHOPAn7v7NJAtLRE/PvJHfvQMvAHO2WVcqMx/27t0yf9QOs8FeNbRnbVxVZp7WaIskK+qI+5PAAXf/4+qlwRclWFP6asJ9vKfBZFpNsEMY7vMnWeuUSoUI95kjWbVGWyQxSwa3mbUBbwE+AODuvwJ+lWxZLW7OqL1huM/Ru/Wa3Ie71miLNEeUEfcbgJ8B+8zseuAIcJu7/2+ileVMlGVwt2y7jPLW6cUfatFw12W+Is0TJbjPA24APuzuj5jZJ4GPATtrHzKzQWAQ4KqOjrjrLITgSNPFjzVttXDXkawizbfkBhwzey3wsLtfXX3dC3zM3d+10NcsZwOOxO+WbZcxNd1gpcwcG26dP3G4nFV7YWhr5YjI2Yt1A467/9TMfmxm17r794GNwBLNWklT1JH7U3f/V917U9OXMra3/rmFwl1HsoqkJ+qqkg8Dn6uuKPkBMHfPomRM47ZG/Xs7d5zhqbtP1L1XG+5aOSKSjkjB7e6PAZGG8JIfQftjbsDXvlZoi6ThnLQLEBGR5VFwi4hkjIJbRCRjFNwiIhmj4BYRyRgFt4hIxuTnPG7JrFu2XZZ2CSKZouCWdI2MMHXJHja8R5dVSMF9PPqjCm5pCbrZTCQ69bhFRDJGwS0ikjEKbhGRjFFwi4hkjIJbRCRjFNwiIhkTaTmgmf0QeBF4BXg56vU6IiISv+Ws4/4Dd/95YpWIiEgkapWIiGRM1OB24AEzO2Jmg0kWJCIii4vaKrnR3afMbDXwoJl9z90fqn2gGuiDAFd1dMRcpohIPo2MwNTBiWV9TdTLgqeqvx8zs/uBHuChOc8MA8MA3V1dvqwqREQKprzjOBw7CsDQulEOHYr+tUsGt5ldDJzj7i9WP3478LcrK1VEpNjK256F6WkAxm+9p3rC2nqIM7iBNcD9ZhY+/6/ufmDZ1YqIFFSlAmN7g3ZIZ+kE9+57ofqZlR2LuWRwu/sPgOtX9N1FRAqsXAYmg8AeWjdK/9D6WL6vzuMWEYnZgu2QmCi4RURiEHc7ZDEKbhGRs1DbDtmweoI777og8X+ngltEZAXq2iEb74CBASD50AYFt4hIZLXtEIDxfc9UPxpoah0KbhGRJdTubmxWO2QxCm4RkQXU7m5sdjtkMQpuEZE5ylvTb4csRsEtIkLrtUMWo+AWkUJr1XbIYhTcIlJIde2Qmd2NrdMOWYyCW0QKo7Yd0lk6wb17ktvdmCQFt4jkXlKHPaVFwS0iuZX0YU9pUXCLSK4087CntEQObjM7FzgM/MTdb06uJBFZCXcI7jtp/Drv8tYOWcxyRty3AZNAW0K1tLSbtm/n1MmT895va2/n67t3p1CRyKwDB4KOwObNQVi7w/79UCpBX1/a1SWr8eqQ/IY2RAxuM7sCeBfwd8D2RCtqUadOnuRwe/u897sbhLlIM7kHoT0+HrzevDkI7fFx6O3N58h7Xjsko6tDVirqiPsTwBBwSYK1iMgKmAVhDUFYhwHe2zs7As+DSgXGxmj62detKMot7zcDx9z9iJltWOS5QWAQ4KqOjtgKFJGlheEdhjbkJ7QrFRi7O1gd0lk6wb0b/ykTuxuTFGXEfSOwyczeCVwItJnZiLvXbTFy92FgGKC7q8tjr1REFhT2tGvt35/d8K5Ugt/H9k7QWTpBJ9SsDsnG7sYkRbnl/XbgdoDqiPuv5oa2iKQnDO2wp13b44ZshffISPD71MEgsDesfr6w7ZDFaB13RG3t7Q0nItsaTFiKNJNZsHqktqcd9rxLpeyEdnjY04bVE9y78YuFb4csZlnB7e5jwFgilbQ4LfmTVtbXV796JAzvLIT2/LOvL0DtkMVpxC2SE3NDupVDO0tnX7ciBbeINE0Wz75uRQpuEUlcls++bkUKbhFJRF7Ovm5FCm4RiVXt6Drvhz2lRcEtImet9uwQqL0ZXaGdBAW3iKxY7VGqWh3SPApuSd+xo5S3Hq17a2ifRmqtrHZ1yGw7RKHdLApuSdfAAOMDz9S9dcu2y+r6pACsW8/QUBPrkoaKePZ1K1JwS8sJVh+8MPvGyAi9B3dR3lr/nEblzVH0s69bkYJbWl+DUfnOHWcY2XaCqelLZ9/UqDxWYf9ahz21HgW3ZFIQIjUj80qF3r1b6kblG24NRuQ9GhguS93N6Nrd2JIU3JIPPT2M98yOynfuOMNTdwcj8rG91TfXraezs5pDMs/8w55Auxtbk4JbcqnRiHznfdczNrme8sHZ5zo3rueNbyzuqFyHPWWTgluKoaeHO3sAZkflo+UJKo9PMHZw/eyofPUaWLUq971yHfaUbea++C1jZnYh8BDBn+p5wJfcfddiX9Pd1eWHdX61ZNBoeYLyZH/9mzlqsTRuh0grsE2bjrh7d5Rno4y4zwA3uftpMzsfOGRm/+7uD59VlSItqH9oPf1zRuUwSvlg/2yLpVSCq9cCZGJknod2yE3bt3NqgRuoinjJSZQ7Jx04XX15fvWXLgOWQggPSKoNc0ZGGJ26gcrxayhvrVlL3kJtlnlnh2S8HXLq5EkON7gmsNF1gkUQqcdtZucCR4DfBP7Z3R9JtCqRVjYwQD8QNFSqgV695XbeRqHVa9jwnlVNm/ysPTukfrNMDvo8MiNScLv7K8CbzOw1wP1mdp27P1H7jJkNAoMAF5xzOb1br4m9WEmejuFcoWoDvG6j0MgIOx9/L2N7ayY/SyW4pI2hu1bF+q+vbYfozzD/lntZ8C/MbAzoA56Y87lhYBigq6vbh3brP5ysKZcBRtMuIz8GBrgTmBmVVyoA1Y1CNYdqlUps+MDaFY3Ka0fYs4Gtv3t5t2Rwm1kH8FI1tEvAW4G7Eq9MJG+qyVy7UYhKhdGxV1Pe2z87KgcolRjas3bBb1W3u1GHPRVOlBH35cC/VPvc5wBfcPevJluWSEH09NDfM2fyE+jdes28ExI7N66vvwpsX3EOe2prb284EdnWYMKyCKKsKvku8OYm1CIiVfPWWFdPSCxq/7qIS/4Wo52TIlkwc0Ji8UJb5jsn7QJERGR5FNwiIhmj4BYRyRgFt4hIxii4RUQyRsEtIpIxCm4RkYxRcIuIZIyCW0QkYxTcIiIZo+AWEckYBbeISMYouEVEMkbBLSKSMQruZXBf/LWISDNEubrsSuCzwGuBXwPD7v7JpAtrNQcOBDdFbd4MZkFo798f3P3a15d2dbKUm7Zv59QCN6jokH7JmigXKbwM/KW7P2pmlwBHzOxBd59Y6gvzwj0I7fHx4PXmzUFoj49Db2/webN0a5TFnTp5ksMNrrlqdB2WSKuLcnXZ88Dz1Y9fNLNJ4HVAYYLbLAhrCMI6DPDe3tkRuEjmVW+hl9a3rKvLzOxqgvsnH2nwuUFgEKCj46oYSmstYXiHoQ0KbcmH3q3XBB+Urku3kML7eOQnIwe3mb0auA/4qLufmvt5dx8GhgG6urpzN20X9rRr7d+v8JaMGxkBdjG0T3dZpu3QpujPRgpuMzufILQ/5+5fXllZ2RWGdtjTru1xg8JbMqh6azzsonOjQjtroqwqMeDTwKS7F3L63SxYPVLb0w573qWSQjsL2trbG05EtjWYsCyCnY+/F1avYeiuVWmXIisQZcR9I/B+4HEze6z63l+7+9eSK6v19PXVrx4Jw1uhnQ1a8hcYLU9QnuwHYGifQjuroqwqOQQonpgf0gptyZRKhfLkFli3nqGhtIuRs7GsVSUikk23bLuMqektQXtEoZ15Cm6RnBstTzA13c+GW9fT05N2NRIHBbdIju3ccYaxYwrtvFFwi+RRpULv3i0AWqOdQzodUCSHevdugVJJoZ1TCm6RPBkZCbawr17D0J61aVcjCVFwi+TEaHki2A2pjTW5px63SA7MbKzRGu1CUHCLZFy4cqRz43oGBtKuRppBwS2SYcHGmku13K9gFNwiGRWeo63QLh4Ft0jWaI124WlViUiWhKGtNdqFpuAWyYqRkdnQ1hrtQlOrRCQDgn621mhLIMoNOJ8BbgaOubtuExVpprA1osCuu8ik0esiidIquRvoS7gOEZkrbI2sW1/40D5wILjn1avXkIf3wB44kG5daVkyuN39IeCFJtQiIlXh9vXOjdoJ6Q7T08Hl3GF4h5d1T0/PhnmRqMct0mKCTTU6QztUezn3+HjwC+ov7y6a2ILbzAaBQYCOjqvi+rYihRJuqtFSv3pheIehDcUNbYhxOaC7D7t7t7t3t7d3xPVtRYqhUglCW+uzGwrbI7Vqe95Fo1aJSNpGRnQc6yJqe9pheyR8DcUceS854jaze4BvAtea2XNm9sHkyxIphpkztLVyZEFmUCrV97Q3bw5el0rFC22IMOJ29y3NKESkaMLjWHWG9tL6+urXbYfhXcTQBrVKRFIRHseqM7SjmxvSRQ1tUHCLpEJnaMvZ0CFTIs0Urh5ZvUahLSumEbdIs4SrR9TTlrOk4BZpguAy313qaUssFNwiCdMWdombglskQdrCLknQ5KRIErSFXRKkEbdI3DQJKQlTcIvEKOhnaxJSkqXgFonJzh1ntLFGmkLBLRIDTUJKM2lyUuRsaBJSUqDgFlmp8DLfUomhPWvTrkYKRMEtsgIz52ivXqPQlqaL1OM2sz7gk8C5wKfc/R8SrUqkhYXnaGsSUtKyZHCb2bnAPwNvA54DvmVmX3H3iaSLE2k14Tna6mdLmqK0SnqAp939B+7+K+DzwLuTLUukxVQnIafoVGhL6qIE9+uAH9e8fq76nkhh9O7don62tIwoPe5GFwT5vIfMBoHB6sszmzbZE2dTWIv7DeDnaReRhEPBP3L781Wt7Oc7Doc2xV9MAvTnl02vj/pglOB+Driy5vUVwNTch9x9GBgGMLPD7t4dtYis0c+Xbfr5si3vP18UUVol3wK6zGytmb0KeB/wlWTLEhGRhSw54nb3l83sz4H/IFgO+Bl3fzLxykREpKFI67jd/WvA15bxfYdXVk5m6OfLNv182Zb3n29J5j5vnlFERFqYtryLiGRMrMFtZn1m9n0ze9rMPhbn906bmX3GzI6Z5XOZo5ldaWbfMLNJM3vSzG5Lu6Y4mdmFZlYxs+9Uf7470q4pCWZ2rpl928y+mnYtcTOzH5rZ42b2mJkdTrueNMXWKqlujX+Kmq3xwJa8bI03s7cAp4HPuvt1adcTNzO7HLjc3R81s0uAI8DmHP35GXCxu582s/MJlqzf5u4Pp1xarMxsO9ANtLn7zWnXEycz+yHQ7e55XMO9LHGOuHO9Nd7dHwJeSLuOpLj78+7+aPXjF4FJcrRD1gOnqy/Pr/7K1QSPmV0BvAv4VNq1SLLiDG5tjc8JM7saeDPwSLqVxKvaRngMOAY86O65+vmATwBDwK/TLiQhDjxgZkeqO7ULK87gjrQ1Xlqbmb0auA/4qLufSrueOLn7K+7+JoLdvz1mlpuWl5ndDBxz9yNp15KgG939BuAdwIeq7ctCijO4I22Nl9ZV7f3eB3zO3b+cdj1JcfdfAGNAX8qlxOlGYFO1D/x54CYzG0m3pHi5+1T192PA/QTt2UKKM7i1NT7DqpN3nwYm3X132vXEzcw6zOw11Y9LwFuB76VbVXzc/XZ3v8Ldryb4u/d1dx9IuazYmNnF1UlzzOxi4O1ALld4RRFbcLv7y0C4NX4S+EKetsab2T3AN4Frzew5M/tg2jXF7Ebg/QQjtceqv96ZdlExuhz4hpl9l2CQ8aC7527JXI6tAQ6Z2XeACvBv7n4g5ZpSo52TIiIZo52TIiIZo+AWEckYBbeISMYouEVEMkbBLSKSMQpuEZGMUXCLiGSMgltEJGP+H6wh20pOWHTsAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 最邻法\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "X = np.array([[1,4],[3,2],[5,1],[2,8],[4,7],[4,4],[5,3],[1,2]])\n",
    "y = np.array([0,0,1,1,0,1,0,1])\n",
    "knn = KNeighborsClassifier(n_neighbors=1, p=2)\n",
    "knn.fit(X,y)\n",
    "plot_decision_regions(X,y,classifier=knn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 距离度量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "距离，实质上是__相似性__的一种度量。不同的距离度量方法，可能得到不同的k近邻区域。\n",
    "\n",
    "Minkowski距离：\n",
    "\n",
    "$$L_p(\\mathbf{x_i},\\mathbf{x_j}) = \\Big(\\sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|^p\\Big)^{\\frac{1}{p}}$$\n",
    "\n",
    "* $p=2$时，是__欧氏距离(欧几里得距离)__;\n",
    "* $p=1$时，是__曼哈顿距离__;\n",
    "* $p=\\infty$时，是__切比雪夫距离__。\n",
    "\n",
    "在scikit-learn中，knn也有参数$p$，即距离度量的选择。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三. k值选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $k$值变大——模型变复杂——容易过拟合；\n",
    "* $k$值变小——模型变简单——容易欠拟合；\n",
    "* 使用交叉验证选择合适的$k$值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 四. 分类决策规则"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "往往是__多数表决(majority voting)__：由输入实例的$k$个近邻的训练实例中的多数类决定输入实例的类别。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3 k近邻法的实现: kd树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "实现k近邻法，必须要做到__快速__找到k近邻区域，即__快速__进行k近邻搜索——当特征的维度很大，训练数据容量很大的时候，一个一个算距离需要耗费大量时间(称为“线性扫描”)，是不可行的。因此，必要设计其他高效的算法，能够快速找到对于某个输入实例的$k$个近邻点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "核心思路：使用特殊的数据结构存储训练数据，以致于能够更快地找到对于某个任意实例的$k$个近邻点。下面介绍一种数据结构——__kd树__。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 构造kd树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "kd树是一种对$k$维空间中的实例进行存储以便对其进行快速检索的树形数据结构：\n",
    "\n",
    "* 是二叉树；\n",
    "* 表示对$k$维空间的一个划分；\n",
    "* 构造的过程，相当于不断地用垂直于坐标轴的超平面将$k$维空间切分，切成一系列的$k$维超矩形区域。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__平衡kd树__：按照如下方式切分得到的kd树是平衡kd树\n",
    "\n",
    "* 依次选择坐标轴对空间进行切分；\n",
    "* 选择训练实例点在选定坐标轴上的中位数为切分点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__结点(Node)__：kd树的一个结点对应一个超矩形区域，并存储着该超矩形区域的切分点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__算法：构造平衡kd树__——递归\n",
    "\n",
    "if 区域中无任何实例(termination criteria) met:\n",
    "\n",
    "    return None\n",
    "\n",
    "else:\n",
    "\n",
    "* __生成新结点__\n",
    "* __确定切分维度__：对深度为$j$的结点，选择$x^{(l)}$为切分的维度(坐标轴)，其中$l=j(mod\\ k)+1$；\n",
    "* __确定切分实例__：以该结点的区域中所有实例的$x^{(l)}$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域——将该切分实例保存至该结点中；\n",
    "* __切分__：切分通过切分点并与坐标轴$x^{(l)}$垂直的超平面实现；\n",
    "* __生成左右子区域(结点)__：由该结点的切分生成深度为$j+1$的左右子区域(结点)——左子区域(结点)对应坐标$x^{(l)}$小于等于切分点的子区域，右子区域(结点)对应坐标$x^{(l)}$大于切分点的子区域；\n",
    "* __递归__：重复。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "举例：给定一个二维空间的数据集，构造一个平衡kd树\n",
    "\n",
    "$$T = \\{(2,3)^T, (5,4)^T, (9,6)^T, (4,7)^T, (8,1)^T, (7,2)^T\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解答：\n",
    "* 首先，该区域中有实例，则生成一个新结点，切分维度为$0mod2+1=1$，将该区域中的实例按照第1维度排序得$T = \\{(2,3)^T, (4,7)^T, (5,4)^T, (7,2)^T, (8,1)^T, (9,6)^T\\}$，该维度的中位数所对应的实例为$(7,2)^T$，因此将$(7,2)^T$保存至该结点中，并以$x^{(1)}=7$将该区域划分为左右两个子区域；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAESBJREFUeJzt3X+MXWWdx/HPt6Ap40hEGY3SdsZNcNQloTrNLpSNmbH9A5TKJiLgXgg1JNe4u9oayAZaCH/IFP8AU/5YCBNga+AGmR1IBFJdoXLXbGDJOtCEH3XQYH+t1YIbFsdhBcJ3/3ju7FP6Yzv3ntP73PPM+5U8OXPOzLn3m6fTT58+59zzmLsLAJCXJakLAACUj3AHgAwR7gCQIcIdADJEuANAhgh3AMjQccPdzO4xs4Nm9vwhxz5oZo+Z2S9b29NObJkAgHYsZOS+TdL5hx27VtIOdz9T0o7WPgCgR9hCPsRkZkOSHnX3s1r7M5JG3f2AmX1UUtPdh09koQCAhTu5w/M+4u4HJKkV8B8+1g+aWV1SXZKWLl06smLFig7fMi/vvPOOlizhkodEXxwqdV/07dsnSZpbvjxZDfNS90Uveemll15194F2zuk03BfM3SckTUjS8PCwz8zMnOi3rIRms6nR0dHUZfQE+iJK3hfz791spqtB8yXwezHPzPa0e06n/yz+rjUdo9b2YIevAwA4AToduT8s6UpJ321tf1haRQDSuf761BWgJMcNdzO7X9KopNPNbL+kGxVCfdLMrpK0V9JXTmSRALpk7drUFaAkxw13d//qMb61puRaAKS2c2fYrlyZtg4UdsIvqAKokI0bw7YHLqiiGO4zAoAMEe4AkCHCHQAyRLgDQIa4oAog2rIldQUoCeEOIFq9OnUFKAnTMgCiJ58MDZXHyB1AtGlT2HKfe+UxcgeADBHuAJAhwh0AMkS4A0CGuKAKINq6NXUFKAnhDiDiUb/ZYFoGQPT446Gh8hi5A4huuilsWZGp8hi5A0CGCHcAyBDhDgAZItwBIENcUAUQ3Xln6gpQEsIdQDQ8nLoClIRpGQDRI4+Ehspj5A4guvXWsF23Lm0dKIyROwBkiHAHgAwR7gCQIcIdADLEBVUA0b33pq4AJSHcAUTLl6euACVhWgZA9MADoaHyGLkDiO64I2wvvTRtHSiMkTsAZIhwB4AMFQp3M/u2mb1gZs+b2f1mtrSswgAAnes43M3sDEnfkrTK3c+SdJKky8oqDADQuaIXVE+WdIqZvSWpT9JvipcEIJmpqdQVoCTm7p2fbLZB0rikNyT9xN1rR/mZuqS6JA0MDIxMTk52/H45mZ2dVX9/f+oyegJ9EdEXEX0RjY2NTbv7qnbO6Tjczew0SQ9KulTSa5L+WdKUu993rHOGh4d9Zmamo/fLTbPZ1OjoaOoyegJ9ESXvi23bwnb9+nQ1tCTvix5iZm2He5ELqmsl/drdX3H3tyQ9JGl1gdcDkNq2bTHgUWlFwn2vpHPMrM/MTNIaSbvKKQsAUETH4e7uT0uakvSMpOdarzVRUl0AgAIK3S3j7jdKurGkWgAAJeETqgCQIR4cBiDavj11BSgJ4Q4g6utLXQFKwrQMgOj220ND5RHuAKLJydBQeYQ7AGSIcAeADBHuAJAhwh0AMsStkACiZjN1BSgJI3cAyBDhDiC65ZbQUHmEO4Do0UdDQ+UR7kim0ZCGhqTp6bBtNFJXBOSDC6pIotGQ6nVpbi7s79kT9iWpdsRKvADaxcgdSWzeHIN93txcOA6gOEbuSGLv3vaOo0tOOSV1BSgJ4Y4kVqwIUzFHO46EfvSj1BWgJEzLIInx8SMfHd7XF44DKI5wRxK1mjQxIQ0Ohv3BwbDPxdTEvvOd0FB5hDuSqdWk3bulkZGwJdh7wI4doaHyCHcAyBDhDgAZItwBIEPcCgkg+tCHUleAkhDuAKIHH0xdAUrCtAwAZIhwBxBdd11oqDymZQBETz2VugKUhJE7AGSIcAeADBHuAJAh5twBRMuWpa4AJSHcAUT33Ze6ApSk0LSMmX3AzKbM7BdmtsvMzi2rMABIZX7x9iVLqrt4e9GR+22SfuzuF5vZeyX1He8EAD1s48aw3bo1bR0J5bJ4e8cjdzM7VdLnJN0tSe7+pru/VlZhABLYuTO0RSyXxdvN3Ts70WylpAlJL0o6W9K0pA3u/sfDfq4uqS5JAwMDI5OTk4UKzsXs7Kz6+/tTl9ET6IsodV+sbI3cd/bAyD1VX0xPH/t7IyPdq+NQY2Nj0+6+qp1zioT7Kkn/Luk8d3/azG6T9Lq733Csc4aHh31mZqaj98tNs9nU6Oho6jJ6An0RJe+L+fduNtPVoPkS0vTF0NDRF28fHAwrhqVgZm2He5ELqvsl7Xf3p1v7U5I+W+D1ACC5XBZv7zjc3f23kvaZ2XDr0BqFKRoAVfWJT4S2iB26eLtZdRdvL3q3zDclNVp3yrws6WvFSwKQzMRE6gp6Qq1WvTA/XKFwd/edktqaBwIAnHg8WwZAVK/Hm7pRaTx+AED00kupK0BJGLkDQIYIdwDIEOEOABlizh1AtHJl6gpQEsIdQNQDz5RBOZiWAYAMEe4AossvDw2Vx7QMgGj//tQVoCSM3AEgQ4Q7AGSIcAeADDHnDiA699zUFaAkhDuA6OabU1eAkjAtAwAZItwBRF/+cmioPKZlAES//33qClASRu4AkCHCHQAyRLgDQIaYcwcQrVmTugKUhHAHEN1wQ+oKUBKmZQAgQ4Q7gOiCC0JD5TEtAyB6443UFaAkjNwBIEOEOwBkiHAHgAwx5w4guvDC1BWgJIQ7gOiaa1JXgJIwLQMAGSLcAUSjo6Gh8gh3AMgQ4Q4AGSoc7mZ2kpk9a2aPllEQ0E2NhjQ0JC1ZEraNRuqKgHKUcbfMBkm7JJ1awmsBXdNoSPW6NDcX9vfsCfuSVKulqwsoQ6GRu5ktk/RFSXeVUw7QPZs3x2CfNzcXji9al1wSGirP3L3zk82mJN0s6f2SrnH3Iz4BYWZ1SXVJGhgYGJmcnOz4/XIyOzur/v7+1GX0hFR9MT197O+NjHSvjkPxexHRF9HY2Ni0u69q55yOp2XM7EJJB9192sxGj/Vz7j4haUKShoeHfZTbrCRJzWZT9EWQqi/Wrw9TMYcbHJR27+52NUHy34v5/8r09aWroSV5X1RckWmZ8yR9ycx2S/qBpM+b2X2lVAV0wfj4kRnW1xeOL1pf+EJoqLyOw93dr3P3Ze4+JOkyST9198tLqww4wWo1aWIijNTNwnZigoupyAPPlsGiVqsR5shTKeHu7k1JzTJeCwBQHJ9QBYAMMS0DIFq/PnUFKAnhDiAi3LPBtAyA6NVXQ0PlMXIHEF18cdg2m0nLQHGM3AEgQ4Q7AGSIcAeADBHuAJAhLqgCiL7xjdQVoCSEO4Do0ktTV4CSMC0DINq3LzRUHiN3ANEVV4Qt97lXHiP3Lms0pKGhsMTb0FDYB4CyMXLvokZDqtfjSmZ79oR9iWeKAygXI/cu2rw5Bvu8ublwHADKRLh30d697R0HgE4xLdNFK1aEqZijHQd6wtVXp64AJWHk3kXj41Jf37uP9fWF40BPWLcuNFQe4d5FtZo0MSENDob9wcGwz8VU9IyZmdBQeUzLdFmtFlqzKe3enboa4DBf/3rYcp975TFyB4AMEe4AkCHCHQAyRLgDQIa4oAoguv761BWgJIQ7gGjt2tQVoCRMywCIdu4MDZXHyB1AtHFj2HKfe+UxcgeADBHuAJAhwh0AMkS4A0CGuKAKINqyJXUFKEnHI3czW25mT5jZLjN7wcw2lFkYgO5qNKShv1mtJX+1msXbM1Bk5P62pKvd/Rkze7+kaTN7zN1fLKk2AF0yv3j72XNP6mOSntqzmsXbK67jkbu7H3D3Z1pf/0HSLklnlFUYgO6ZX7x9izZpizZJYvH2qjN3L/4iZkOSfibpLHd//bDv1SXVJWlgYGBkcnKy8PvlYHZ2Vv39/anL6An0RZSqL6anw/aS28OHmCb/duv/fW9kpOvlSOL34lBjY2PT7r6qnXMKh7uZ9Uv6V0nj7v7Q//ezw8PDPsMSXpKkZrOp0dHR1GX0BPoiStUXQ0Nh8fYnFN57TE1JYSnIVCuG8XsRmVnb4V7oVkgze4+kByU1jhfsAHoXi7fnp+MLqmZmku6WtMvdv1deSQC6bf6i6dKrpP/5Uxixj49zMbXKitwtc56kKyQ9Z2bzj5Hb5O7bi5cFoNtqNUl/Hubad69MWwuK6zjc3f3fJFmJtQBIbSWpngsePwAgevzx0FB5PH4AQHTTTWHLikyVx8gdADJEuANAhgh3AMgQ4Q4AGeKCKoDozjtTV4CSEO4AouHh1BWgJEzLAIgeeSQ0VB4jdwDRrbeG7bp1aetAYYzcASBDhDsAZIhwB4AMEe4AekqjEVaGmp4O20YjdUXVxAVVANG99yZ9+0ZDqtfD4txSWPqvXg9fs3BIexi5A4iWLw8tkc2bY7DPm5sLx9Eewh1A9MADoSWyd297x3FshDuA6I47QktkxYr2juPYCHcAPWN8XOrre/exvr5wHO0h3AH0jFpNmpiQBgfD/uBg2Odiavu4WwZAT6nVQms2pd27U1dTXYzcASBDjNwBRFNTqStASQh3ANHpp6euACVhWgZAtG1baKg8wh1ARLhng3AHgAwR7gCQIcIdADJEuANAhrgVEkC0fXvqClASwh1AdPhTu1BZTMsAiG6/PTRUHuEOIJqcDA2VR7gDQIYKhbuZnW9mM2b2KzO7tqyiAADFdBzuZnaSpH+UdIGkT0v6qpl9uqzCAACdKzJy/wtJv3L3l939TUk/kHRROWUBAIoocivkGZL2HbK/X9JfHv5DZlaXVG/t/snMni/wnjk5XdKrqYvoEfRF1Bt9YZa6AqlX+qI3DLd7QpFwP9qfvh9xwH1C0oQkmdnP3X1VgffMBn0R0RcRfRHRF5GZ/bzdc4pMy+yXtPyQ/WWSflPg9QAAJSkS7v8h6Uwz+7iZvVfSZZIeLqcsAEARHU/LuPvbZvb3kv5F0kmS7nH3F45z2kSn75ch+iKiLyL6IqIvorb7wtyPmCYHAFQcn1AFgAwR7gCQoa6EO48pCMxsuZk9YWa7zOwFM9uQuqbUzOwkM3vWzB5NXUtKZvYBM5sys1+0fj/OTV1TKmb27dbfj+fN7H4zW5q6pm4xs3vM7OChnwcysw+a2WNm9svW9rSFvNYJD3ceU/Aub0u62t0/JekcSX+3iPti3gZJu1IX0QNuk/Rjd/+kpLO1SPvEzM6Q9C1Jq9z9LIWbNS5LW1VXbZN0/mHHrpW0w93PlLSjtX9c3Ri585iCFnc/4O7PtL7+g8Jf4DPSVpWOmS2T9EVJd6WuJSUzO1XS5yTdLUnu/qa7v5a2qqROlnSKmZ0sqU+L6PMz7v4zSf912OGLJH2/9fX3Jf31Ql6rG+F+tMcULNpAm2dmQ5I+I+nptJUktVXSP0h6J3Uhif2ZpFck/VNriuouM3tf6qJScPf/lHSLpL2SDkj6b3f/SdqqkvuIux+QwgBR0ocXclI3wn1BjylYTMysX9KDkja6++up60nBzC6UdNDdp1PX0gNOlvRZSXe4+2ck/VEL/K93blrzyRdJ+rikj0l6n5ldnraqaupGuPOYgkOY2XsUgr3h7g+lrieh8yR9ycx2K0zVfd7M7ktbUjL7Je139/n/xU0phP1itFbSr939FXd/S9JDklYnrim135nZRyWptT24kJO6Ee48pqDFzExhXnWXu38vdT0puft17r7M3YcUfid+6u6LcoTm7r+VtM/M5p/8t0bSiwlLSmmvpHPMrK/192WNFunF5UM8LOnK1tdXSvrhQk4q8lTIBenwMQW5Ok/SFZKeM7OdrWOb3H17wprQG74pqdEaAL0s6WuJ60nC3Z82sylJzyjcXfasFtFjCMzsfkmjkk43s/2SbpT0XUmTZnaVwj9+X1nQa/H4AQDID59QBYAMEe4AkCHCHQAyRLgDQIYIdwDIEOEOABki3AEgQ/8LZnljAjDpUS4AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim([0,10])\n",
    "plt.ylim([0,10])\n",
    "plt.grid()\n",
    "plt.scatter([2,5,9,4,8,7],[3,4,6,7,1,2],color='b')\n",
    "plt.plot([7,7],[0,10],'--',color='r');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* (第2层左子区域)：有实例，则生成一个新结点，切分维度为$1mod2+1=2$，将该区域中的实例按照第2维度排序得$T = \\{(2,3)^T, (5,4)^T, (4,7)^T\\}$，该维度的中位数所对应的实例为$(5,4)^T$，因此将$(5,4)^T$保存至该结点中，并以$x^{(2)}=4$将该区域划分为左右两个子区域；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAETxJREFUeJzt3X2MXXWdx/H3t7Raxoog1Cdop7rqrMquVZpdHhJ3EEx8QN1EFzEDQUMyRlylLsYIaPxDq/6BBv9YjeMTRiZot5CoBF0VvZJVJMtg2VLLVB7aaaVQQAcch2e++8e5w3SmU+ncezvn9tf3K5nce36/e8755tczn545997zi8xEklSWRXUXIEnqPMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAzxjuEfGtiNgdEbfu0fb8iPhZRPyh+XjUgS1TkjQf+3Pmfjnw5lltnwCuy8xXANc1lyVJXSL250tMEbEKuCYzj28ujwL9mbkrIl4MNDKz70AWKknaf4tbXO+FmbkLoBnwL9jXCyNiEBgEWLp06QkrV65scZdleeqpp1i0yLc8wLHYU91j0bNjBwCTK1bUVsOUuseim2zduvX+zFw+n3VaDff9lplDwBBAX19fjo6OHuhdHhQajQb9/f11l9EVHItptY/F1L4bjfpqYKoEj4spEbF9vuu0+t/ivc3LMTQfd7e4HUnSAdBquP8QOLf5/FzgB50pR5LUCfvzUcgrgRuAvojYGRHnAV8A3hQRfwDe1FyWJHWJZ7zmnpnv3UfXaR2uRZLUIb4VLUkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFaitcI+Ij0bE5oi4NSKujIilnSpMktS6lsM9Io4FPgKsyczjgcOAszpVmCSpde1ellkMHB4Ri4Ee4O72S5IktWtxqytm5h8j4lJgDHgY+Glm/nT26yJiEBgEWL58OY1Go9VdFmViYsKxaHIsptU9FqvHxwHY2AX/HnWPxcEuMrO1FSOOAq4C3gOMA/8FbMjMK/a1Tl9fX46Ojra0v9I0Gg36+/vrLqMrOBbTah+LqX13QajWPhZdJCJGMnPNfNZp57LM6cBdmXlfZj4OXA2c3Mb2JEkd0k64jwEnRkRPRARwGrClM2VJktrRcrhn5o3ABuBmYFNzW0MdqkuS1IaW31AFyMxPA5/uUC2SpA7xG6qSVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtxVm+FhWLUKRkaqx+HhuiuSytHWLX+lVg0Pw+AgTE5Wy9u3V8sAAwP11SWVwjN31eKSS6aDfcrkZNUuqX2Gu2oxNja/dknzY7irFitXzq9d0vwY7qrFunXQ0zOzraenapfUPsNdtRgYgKEh6O2tlnt7q2XfTJU6w0/LqDYDA9VPowHbttVdjVQWz9wlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIK1Fa4R8SREbEhIm6LiC0RcVKnCpOkukxN3r5o0cE7eXu7t/z9MvCTzHx3RDwL6HmmFSSpm5UyeXvLZ+4RcQTwBuCbAJn5WGaOd6owSapDKZO3R2a2tmLEamAI+D3wWmAEuCAz/zrrdYPAIMDy5ctPWL9+fVsFl2JiYoJly5bVXUZXcCym1T0Wq9euBWDjZZfVVsOUusZiZGTffSecsHB17OnUU08dycw181mnnXBfA/wWOCUzb4yILwMPZean9rVOX19fjo6OtrS/0jQaDfr7++suoys4FtNqH4upfTca9dXAVAn1jMWqVdWlmNl6e+ubMSwi5h3u7byhuhPYmZk3Npc3AK9vY3uSVLtSJm9vOdwz8x5gR0T0NZtOo7pEI0kHrT0nb484eCdvb/fTMh8GhpuflLkTeH/7JUlSvaYmbz+YtRXumbkRmNd1IEnSgec3VCWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAK1He4RcVhE/C4irulEQdJCGh6GVatg0aLqcXi47oqkzljcgW1cAGwBjujAtqQFMzwMg4MwOVktb99eLQMMDNRXl9QJbYV7RBwHvA1YB/zHM72+Z8cO6O+f2XjmmXD++dVv2FvfuvdK73tf9XP//fDud+/d/8EPwnveAzt2wDnn7N1/4YXw9rfD6Ch84AN793/yk3D66bBxI6xdu3f/5z4HJ58Mv/kNXHzx3v2XXQarV8PPfw6f/eze/V/7GvT1wY9+BF/84tPNq8fH4cgj4bvfhRUr4Pvfh69+de/1N2yAY46Byy+vfma79lro6YGvfAXWr9+7v9GoHi+9FK6Z9cfV4YfDj39cPf/MZ+C662b2H300XHVV9fyii+CGG2b2H3ccXHFF9Xzt2moM9/TKV8LQUPV8cBC2bp3Zv3p1NX4AZ58NO3fO7D/pJPj856vn73oXPPDAzP7TToNPfap6/pa3wMMPz+w/4wz42Meq57OPO2DLpjOZnDyfw5nkWprH3iQsPQ/4OrUce08fF3DAjr2nzXXsbdxYbVMHvXbP3C8DPg48d18viIhBYBDg+CVLGB8fn9G/e+tW7m40WPTII/zjrD6Ae267jXsaDZY8+CCvmaP/j5s3c1+jwbN37+ZVc/Tv2LSJB577XA4fG6Nvjv7tt9zCnxcvZtntt/PyOfrvvPlmHnrsMY649VZeNkf/7TfdxMT4OEfdcgu9c/SP3ngjD+/axdGbNrFij/4nn3yS8fFxttxwA4/ecQfLN2/m2DnW3/zrX/P4857Hi267jRfN0f9/11/PU0uX8pKtW3nBHP0bm+G+4o47OHpW/5MPP8ymZn/vXXdx1Kz+x596is3N/peOjfG8Wf2PLlnClmb/y3fuZNms/sm772Zrs/+Vd99Nz6z+iZ07ub3RYGJignvvvZdnz+p/cGyMu5rrv+a++1jy0EMz+v98111sb/b/w5/+xGGPPjqj/4E77mBHs3/1HGPT/y9bOeqUBosfe4S/+8bM/vHxeo69qeMCDtyxN2WuY2/ZE08wMT7+9HFTp4mJCRpdUMfBKjKztRUjzgDempnnR0Q/8LHMPONvrdPX15ejo6Mt7a80jUaD/jnOJg9FdY3FqlXVpZjZenth27aFrqZS+3Exte8uCNXax6KLRMRIZq6ZzzrtvKF6CvCOiNgGfA94Y0Rc0cb2pAW1bl11RWtPPT1Vu3SwazncM/OizDwuM1cBZwG/yMyzO1aZdIANDFRvCfT2QkT1ODTkm6kqQyc+LSMdtAYGDHOVqSPhnpkNoNGJbUmS2uc3VCWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuC+w4eFqBqCRkepxeLjuiiSVyPu5L6Dh4Wqe6MnJann79moZvKe4pM7yzH0BXXLJdLBPmZys2iWpkwz3BTQ2Nr92SWqV4b6AVq6cX7sktcpwX0Dr1kFPz8y2np6qXZI6yXBfQAMDMDQEvb3Vcm9vteybqZI6zU/LLLCBgeqn0YBt2+quRlKpPHOXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqUMvhHhErIuKXEbElIjZHxAWdLEzSwhoeht/+Fhq/cvL2ErRz5v4EcGFmvgo4EfhQRLy6M2VJWkhTk7c/8mi1PDV5uwF/8Go53DNzV2be3Hz+F2ALcGynCpO0cJy8vTyRme1vJGIVcD1wfGY+NKtvEBgEWL58+Qnr169ve38lmJiYYNmyZXWX0RUci2l1jcXISPV45lfWArD+/Mue7jvhhAUvB/C42NOpp546kplr5rNO2+EeEcuAXwHrMvPqv/Xavr6+HB0dbWt/pWg0GvT399ddRldwLKbVNRarVlWXYn5Jte9TaQDVVJB1zRjmcTEtIuYd7m19WiYilgBXAcPPFOySupeTt5en5TlUIyKAbwJbMvNLnStJ0kKbmqR96XnVm6q9vVWwO3n7waudCbJPAc4BNkXExmbbxZl5bftlSVpoAwPA16vn2xp1VqJOaDncM/N/gOhgLZKkDvEbqpJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CV1leHhamaokZHq0Um6W9PO/dwlqaOGh2FwcHqy7u3bq2Vw4pD58sxdUte45JLpYJ8yOVm1a34Md0ldY2xsfu3aN8NdUtdYuXJ+7do3w11S11i3Dnp6Zrb19FTtmh/DXVLXGBiAoSHo7a2We3urZd9MnT8/LSOpqwwMVD+NBmzbVnc1By/P3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgdoK94h4c0SMRsTtEfGJThUlSWpPy+EeEYcB/wm8BXg18N6IeHWnCpMkta6dM/d/Am7PzDsz8zHge8A7O1OWJKkd7czEdCywY4/lncA/z35RRAwCg83FRyPi1jb2WZJjgPvrLqJLOBbTumMsIuquALplLLpD33xXaCfc5/rXz70aMoeAIYCIuCkz17Sxz2I4FtMci2mOxTTHYlpE3DTfddq5LLMTWLHH8nHA3W1sT5LUIe2E+/8Cr4iIl0bEs4CzgB92pixJUjtaviyTmU9ExL8D/w0cBnwrMzc/w2pDre6vQI7FNMdimmMxzbGYNu+xiMy9LpNLkg5yfkNVkgpkuEtSgRYk3L1NQSUiVkTELyNiS0RsjogL6q6pbhFxWET8LiKuqbuWOkXEkRGxISJuax4fJ9VdU10i4qPN349bI+LKiFhad00LJSK+FRG79/w+UEQ8PyJ+FhF/aD4etT/bOuDh7m0KZngCuDAzXwWcCHzoEB6LKRcAW+ouogt8GfhJZv498FoO0TGJiGOBjwBrMvN4qg9rnFVvVQvqcuDNs9o+AVyXma8ArmsuP6OFOHP3NgVNmbkrM29uPv8L1S/wsfVWVZ+IOA54G/CNumupU0QcAbwB+CZAZj6WmeP1VlWrxcDhEbEY6OEQ+v5MZl4P/GlW8zuB7zSffwf41/3Z1kKE+1y3KThkA21KRKwCXgfcWG8ltboM+DjwVN2F1OxlwH3At5uXqL4REc+pu6g6ZOYfgUuBMWAX8GBm/rTeqmr3wszcBdUJIvCC/VlpIcJ9v25TcCiJiGXAVcDazHyo7nrqEBFnALszc6TuWrrAYuD1wFcz83XAX9nPP71L07ye/E7gpcBLgOdExNn1VnVwWohw9zYFe4iIJVTBPpyZV9ddT41OAd4REduoLtW9MSKuqLek2uwEdmbm1F9xG6jC/lB0OnBXZt6XmY8DVwMn11xT3e6NiBcDNB93789KCxHu3qagKSKC6rrqlsz8Ut311CkzL8rM4zJzFdUx8YvMPCTP0DLzHmBHREzd+e804Pc1llSnMeDEiOhp/r6cxiH65vIefgic23x+LvCD/VmpnbtC7pcWb1NQqlOAc4BNEbGx2XZxZl5bY03qDh8GhpsnQHcC76+5nlpk5o0RsQG4merTZb/jELoNQURcCfQDx0TETuDTwBeA9RFxHtV/fv+2X9vy9gOSVB6/oSpJBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoH+H5T5QGRy+vlDAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim([0,10])\n",
    "plt.ylim([0,10])\n",
    "plt.grid()\n",
    "plt.scatter([2,5,9,4,8,7],[3,4,6,7,1,2],color='b')\n",
    "plt.plot([7,7],[0,10],color='r');\n",
    "plt.plot([0,7],[4,4],'--',color='r');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* (第2层右子区域)：有实例，则生成一个新结点，切分维度为$1mod2+1=2$，将该区域中的实例按照第2维度排序得$T = \\{(8,1)^T, (9,6)^T\\}$，该维度的中位数所对应的实例为$(9,6)^T$，因此将$(9,6)^T$保存至该结点中，并以$x^{(2)}=6$将该区域划分为左右两个子区域；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAED5JREFUeJzt3V2MXGd9x/Hv33Gos5jgQMybY+8CRVtoVAyx2pBIaEOClPKWXqQQukQBRVoEFBIaCUEM4gYjLlIULgpieQsqo1DXRAJCRIHAEBWI1Wxw6hhnTQh+AwcnbZewbEiw8+/Fme3aa7venRnPmX38/UijmfOcec75+9nZ3x6fmTlPZCaSpLIsq7sASVL3Ge6SVCDDXZIKZLhLUoEMd0kqkOEuSQU6abhHxBcj4mBE3H9E27Mi4rsR8fPW/TmntkxJ0mIs5Mj9FuDyeW0fBO7MzJcAd7aWJUl9IhbyJaaIGAJuz8zzW8uTwEhmHoiI5wPNzBw+lYVKkhZueZv9npuZBwBaAf+cEz0xIsaAMYAVK1ZcsG7dujZ3WZannnqKZct8ywMciyPVPRYD+/YBMLN2bW01zKp7LPrJrl27Hs3M1Yvp0264L1hmjgPjAMPDwzk5OXmqd7kkNJtNRkZG6i6jLzgWc2ofi9l9N5v11cBsCb4uZkXEnsX2affP4m9ap2No3R9sczuSpFOg3XD/BnBN6/E1wNe7U44kqRsW8lHIW4GfAMMRsT8irgU+Abw2In4OvLa1LEnqEyc9556Zbz3Bqku7XIskqUt8K1qSCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSpQR+EeEe+PiB0RcX9E3BoRK7pVmCSpfW2He0SsAd4HbMjM84EzgKu6VZgkqX2dnpZZDpwVEcuBAeDXnZckSerU8nY7ZuavIuImYC/wOPCdzPzO/OdFxBgwBrB69WqazWa7uyzK9PS0Y9HiWMypeyzWT00BsK0Pfh51j8VSF5nZXseIc4CvAW8BpoB/BbZk5ldO1Gd4eDgnJyfb2l9pms0mIyMjdZfRFxyLObWPxey++yBUax+LPhIRE5m5YTF9Ojktcxnwy8x8JDP/CNwGXNTB9iRJXdJJuO8FLoyIgYgI4FJgZ3fKkiR1ou1wz8ytwBbgXmB7a1vjXapLktSBtt9QBcjMjwIf7VItkqQu8RuqklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcVZtGA4aGYGKium806q5IKkdHl/yV2tVowNgYzMxUy3v2VMsAo6P11SWVwiN31WLjxrlgnzUzU7VL6pzhrlrs3bu4dkmLY7irFuvWLa5d0uIY7qrFpk0wMHB028BA1S6pc4a7ajE6CuPjMDhYLQ8OVsu+mSp1h5+WUW1GR6tbswm7d9ddjVQWj9wlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIK1FG4R8SqiNgSEQ9ExM6IeFW3CpOkusxO3r5s2dKdvL3TS/5+Cvh2Zl4ZEU8DBk7WQZL6WSmTt7cd7hFxNvBq4O0Amfkk8GR3ypJUm23bYGTk6LY3vxne/e4q8V73umP7vP3t1e3RR+HKK49d/653wVveAvv2wdVXH7v+hhvgjW+EyUl45zsBWD81BatWVes//GG47LKqtuuvP7b/xz8OF10EP/4x3HjjsetvvhnWr4fvfQ8+9rFj13/2szA8DN/8Ji++9h/51hNHr7565p/ZuHEto8v/BT7zmWP7b9kC554Lt9xS3ea7445qqrFPfxo2bz52fbNZ3d90E9x++9Hrzjrr2OcvQCdH7i8CHgG+FBEvByaA6zLz90c+KSLGgDGA1atX05z9R5zmpqenHYsWx2JO3WOxfmqKlYcOMT01dVT7wV27+HWzybI//IG/mLcO4OEHHuDhZpMzf/tb/vw463+1YwePNJv8ycGDvPQ46/dt385/PeMZnLV3L8Ot9YcPH2aq9XjPfffxP8uXs/LBB/nT4/R/6N57eezJJzn7/vt50XHWP3jPPUxPTXHOffcxeJz1k1u38viBAzx7+3bWrDl2/Uf+7if8btUv2LFjB2uO03/Hj37EH5/5TJ73wAM87zjr//Ouu3hqxQpesGsXzznO+m2tn/naX/yCZ89bf/jxx495/kJEZrbXMWIDcDdwcWZujYhPAY9l5kdO1Gd4eDgnJyfb2l9pms0mI/OPjk5TjsWc2sdidt998Me2rrEYGqpOxcw3OFjfjGERMZGZGxbTp5M3VPcD+zNza2t5C/DKDrYnSbUrZfL2tsM9Mx8G9kXEcKvpUuBnXalKkmpy5OTtEUt38vZOPy3zXqDR+qTMQ8A7Oi9Jkuo1O3n7UtZRuGfmNmBR54EkSaee31CVpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIK1HG4R8QZEfHTiLi9GwVJvdRowNAQLFtW3TcadVckdcfyLmzjOmAncHYXtiX1TKMBY2MwM1Mt79lTLQOMjtZXl9QNHYV7RJwHvB7YBPzDyZ4/sG8fjIx0sstirJ+aglWr6i6jL9Q1Fi++G771xLzGGVhxLfC5npcD9MHrYts2WLmyvv2razo9cr8Z+ADwjBM9ISLGgDGA8888k6mpqQ53WYbDhw87Fi11jcWaNSdeV9ePpu7XxcpDhzj8xBP8pNmsrYZZ09PTNPugjqWq7XCPiDcABzNzIiJGTvS8zBwHxgGGh4dz1bZt7e6yKM1mkxH/FwPUNxbrh6pTMfMNDsLuml6mtb8uRkZYDn3x2qx9LJa4Tt5QvRh4U0TsBr4KvCYivtKVqqQe2LQJBgaObhsYqNqlpa7tcM/MD2XmeZk5BFwFfD8z39a1yqRTbHQUxserI/WI6n583DdTVYZufFpGWrJGRw1zlakr4Z6ZTaDZjW1JkjrnN1QlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLj3WKMBQ0MwMVHdNxp1VySpRF7PvYcaDRgbg5mZannPnmoZvKa4pO7yyL2HNm6cC/ZZMzNVuyR1k+HeQ3v3Lq5dktpluPfQunWLa5ekdhnuPbRpEwwMHN02MFC1S1I3Ge49NDoK4+MwOFgtDw5Wy76ZKqnb/LRMj42OVrdmE3bvrrsaSaXyyF2SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAbYd7RKyNiB9ExM6I2BER13WzMEm91WjA3XdD84dO3l6CTo7cDwE3ZOZLgQuB90TEy7pTlqRemp28/Q9PVMuzk7cb8EtX2+GemQcy897W498BO4E13SpMUu84eXt5IjM730jEEHAXcH5mPjZv3RgwBrB69eoLNm/e3PH+SjA9Pc3KlSvrLqMvOBZz6hqLiYnq/s2fvh6Aze+++f/WXXBBz8sBfF0c6ZJLLpnIzA2L6dNxuEfESuCHwKbMvO3/e+7w8HBOTk52tL9SNJtNRkZG6i6jLzgWc+oai6Gh6lTMD6j2fQlNoJoKsq4Zw3xdzImIRYd7R5+WiYgzga8BjZMFu6T+5eTt5Wl7DtWICOALwM7M/GT3SpLUa7OTtK+4tnpTdXCwCnYnb1+6Opkg+2LgamB7RGxrtd2YmXd0XpakXhsdBT5XPd7drLMSdUPb4Z6Z/w5EF2uRJHWJ31CVpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuqa80GtXMUBMT1b2TdLenk+u5S1JXNRowNjY3WfeePdUyOHHIYnnkLqlvbNw4F+yzZmaqdi2O4S6pb+zdu7h2nZjhLqlvrFu3uHadmOEuqW9s2gQDA0e3DQxU7Vocw11S3xgdhfFxGByslgcHq2XfTF08Py0jqa+Mjla3ZhN27667mqXLI3dJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVKCOwj0iLo+IyYh4MCI+2K2iJEmdaTvcI+IM4J+AvwZeBrw1Il7WrcIkSe3r5Mj9L4EHM/OhzHwS+CpwRXfKkiR1opOZmNYA+45Y3g/81fwnRcQYMNZafCIi7u9gnyU5F3i07iL6hGMxpz/GIqLuCqBfxqI/DC+2Qyfhfryffh7TkDkOjANExD2ZuaGDfRbDsZjjWMxxLOY4FnMi4p7F9unktMx+YO0Ry+cBv+5ge5KkLukk3P8DeElEvDAingZcBXyjO2VJkjrR9mmZzDwUEX8P/BtwBvDFzNxxkm7j7e6vQI7FHMdijmMxx7GYs+ixiMxjTpNLkpY4v6EqSQUy3CWpQD0Jdy9TUImItRHxg4jYGRE7IuK6umuqW0ScERE/jYjb666lThGxKiK2RMQDrdfHq+quqS4R8f7W78f9EXFrRKyou6ZeiYgvRsTBI78PFBHPiojvRsTPW/fnLGRbpzzcvUzBUQ4BN2TmS4ELgfecxmMx6zpgZ91F9IFPAd/OzD8DXs5pOiYRsQZ4H7AhM8+n+rDGVfVW1VO3AJfPa/sgcGdmvgS4s7V8Ur04cvcyBS2ZeSAz7209/h3VL/CaequqT0ScB7we+HzdtdQpIs4GXg18ASAzn8zMqXqrqtVy4KyIWA4McBp9fyYz7wL+e17zFcCXW4+/DPzNQrbVi3A/3mUKTttAmxURQ8ArgK31VlKrm4EPAE/VXUjNXgQ8AnypdYrq8xHx9LqLqkNm/gq4CdgLHAB+m5nfqbeq2j03Mw9AdYAIPGchnXoR7gu6TMHpJCJWAl8Drs/Mx+qupw4R8QbgYGZO1F1LH1gOvBL4TGa+Avg9C/yvd2la55OvAF4IvAB4ekS8rd6qlqZehLuXKThCRJxJFeyNzLyt7npqdDHwpojYTXWq7jUR8ZV6S6rNfmB/Zs7+L24LVdifji4DfpmZj2TmH4HbgItqrqluv4mI5wO07g8upFMvwt3LFLRERFCdV92ZmZ+su546ZeaHMvO8zByiek18PzNPyyO0zHwY2BcRs1f+uxT4WY0l1WkvcGFEDLR+Xy7lNH1z+QjfAK5pPb4G+PpCOnVyVcgFafMyBaW6GLga2B4R21ptN2bmHTXWpP7wXqDROgB6CHhHzfXUIjO3RsQW4F6qT5f9lNPoMgQRcSswApwbEfuBjwKfADZHxLVUf/z+dkHb8vIDklQev6EqSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KB/hdNy3AO4eVtLgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim([0,10])\n",
    "plt.ylim([0,10])\n",
    "plt.grid()\n",
    "plt.scatter([2,5,9,4,8,7],[3,4,6,7,1,2],color='b')\n",
    "plt.plot([7,7],[0,10],color='r');\n",
    "plt.plot([0,7],[4,4],color='r');\n",
    "plt.plot([7,10],[6,6],'--',color='r');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* (第3层左左子区域)：有实例，则生成一个新结点，切分维度为$2mod2+1=1$，将该区域中的实例按照第1维度排序得$T = \\{(2,3)^T\\}$，该维度的中位数所对应的实例为$(2,3)^T$，因此将$(2,3)^T$保存至该结点中，并以$x^{(1)}=2$将该区域划分为左右两个子区域；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAEINJREFUeJzt3W+MZXV9x/H3d1nsOlJcLIvVZXdGqJmqpK52U/mT0KlgQtVKH1jFjBQsyTTWIloTg2DjE9f4QA0mVuMAisEJSleiiAT/gFdSgU1ZXCvrMrrB/aeLC2mvMo5d3OXbB/eOs6xud+beO/O785v3K9ncOWfuueeT39z57Jlzzj0nMhNJUl1WlA4gSeo9y12SKmS5S1KFLHdJqpDlLkkVstwlqULHLfeI+ExEHIiIh4+Y97yI+GZE/Lj9eMrCxpQkzcdcttxvAi46at7VwN2Z+WLg7va0JKlPxFw+xBQRQ8AdmXlWe3oSGMnM/RHxAqCRmcMLGVSSNHcrO1zu+Zm5H6Bd8Kcd64kRMQaMAaxaterP169f3+Eq6/L000+zYoWHPMCxOFLpsRjYuxeA6XXrimWYUXos+smPfvSjJzJzzXyW6bTc5ywzx4FxgOHh4ZycnFzoVS4JjUaDkZGR0jH6gmMxq/hYzKy70SiXgZkIvi9mRMTu+S7T6X+LP2/vjqH9eKDD15EkLYBOy/124LL215cBX+lNHElSL8zlVMhbgPuB4YjYFxFXAB8GXhMRPwZe056WJPWJ4+5zz8y3HONbF/Q4iySpRzwULUkVstwlqUKWuyRVyHKXpApZ7pJUIctdkipkuUtShSx3SaqQ5S5JFbLcJalClrskVchyl6QKWe6SVCHLXZIqZLlLUoUsd0mqkOUuSRWy3CWpQpa7JFXIcpekClnuklQhy12SKmS5S1KFLHdJqpDlLkkVstwlqUKWuyRVyHKXpApZ7pJUIctdkipkuUtShSx3SaqQ5S5JFbLcJalClrskVairco+Id0fE9oh4OCJuiYhVvQomSepcx+UeEWuBdwIbM/Ms4ATgkl4FkyR1rtvdMiuBZ0fESmAA+Fn3kSRJ3VrZ6YKZ+dOI+AiwB/g18I3M/MbRz4uIMWAMYM2aNTQajU5XWZWpqSnHos2xmFV6LDY0mwBs64OfR+mxWOoiMztbMOIU4EvAm4Em8O/A5sz8/LGWGR4ezsnJyY7WV5tGo8HIyEjpGH3BsZhVfCxm1t0HpVp8LPpIRGzNzI3zWaab3TIXAj/JzMcz8zfAbcC5XbyeJKlHuin3PcDZETEQEQFcAOzoTSxJUjc6LvfM3AJsBh4CftB+rfEe5ZIkdaHjA6oAmfkB4AM9yiJJ6hE/oSpJFbLcJalClrskVchyl6QKWe6SVCHLXZIqZLlLUoUsd0mqkOUuSRWy3CWpQpa7JFXIcpekClnuklQhy13FTEzA0BBs3dp6nJgonUiqR1eX/JU6NTEBY2MwPd2a3r27NQ0wOloul1QLt9xVxLXXzhb7jOnp1nxJ3bPcVcSePfObL2l+LHcVsX79/OZLmh/LXUVs2gQDA8+cNzDQmi+pe5a7ihgdhfFxGBxsTQ8OtqY9mCr1hmfLqJjR0da/RgN27SqdRqqLW+6SVCHLXZIqZLlLUoUsd0mqkOUuSRWy3CWpQpa7JFXIcpekClnuklQhy12SKmS5S1KFLHdJqpDlLkkV6qrcI2J1RGyOiEciYkdEnNOrYJJUyszN21esWLo3b+/2kr8fB+7KzDdGxLOAgeMtIEn9rJabt3dc7hFxMnA+cDlAZj4FPNWbWJKK2LkTpqZgZKR0EjY0m7B69aKv98wH4GsHj5o5DauuAK5f9Dgd62bL/QzgceCzEfFyYCtwVWb+6sgnRcQYMAawZs0aGo1GF6usx9TUlGPR5ljMKj0W5xw8yAmHDjHVbBbLMOPw4cM0C+RYu/bY3+uDYZmzyMzOFozYCDwAnJeZWyLi48AvM/Nfj7XM8PBwTk5Odpa0Mo1Gg5E+2DrqB47FrOJjMbPuPvjPttRYDA21dsUcbXCw3B3DImJrZm6czzLdHFDdB+zLzC3t6c3AK7t4PUkqrpabt3dc7pn5GLA3Iobbsy4AftiTVJJUyJE3b49Yujdv7/ZsmSuBifaZMo8Cb+s+kiSVNXPz9qWsq3LPzG3AvPYDSZIWnp9QlaQKWe6SVCHLXZIqZLlLUoUsd0mqkOUuSRWy3CWpQpa7JFXIcpekClnuklQhy12SKmS5S1KFLHdJqpDlLkkVstwlqUKWuyRVyHKXpApZ7pJUIctdkipkuUtShSx3SaqQ5S5JFbLcJalClrskVchyl6QKWe6SVCHLXZIqZLlLUoUsd0mqkOUuSRWy3CWpQpa7JFXIcpekClnuklQhy12SKtR1uUfECRHxvYi4oxeBpMU0MQFDQ7BiRetxYqJ0Iqk3VvbgNa4CdgAn9+C1pEUzMQFjYzA93Zrevbs1DTA6Wi6X1AtdlXtEnA68DtgE/Mvxnj+wdy+MjHSzympsaDZh9erSMfpCqbE48wH42sGjZk7DqiuA6xc9DtAH74tt2+Ckk8qtXz3T7Zb7dcB7gT881hMiYgwYAzjrxBNpNptdrrIOhw8fdizaSo3F2rXH/l6pH03p98VJhw5x+OBB7m80imWYMTU1RaMPcixVHZd7RLweOJCZWyNi5FjPy8xxYBxgeHg4V2/b1ukq6zE9zb333sv5F11UOklfaDQajBT4i27DUGtXzNEGB2FXobdpqbH4rZERVkLZDG3Fx2KJ6+aA6nnAGyJiF/AF4NUR8fmepKrda1/Ln119dekUy96mTTAw8Mx5AwOt+dJS13G5Z+b7MvP0zBwCLgHuycy39iyZtMBGR2F8vLWlHtF6HB/3YKrq0IuzZaQla3TUMledelLumdkAGr14LUlS9/yEqiRVyN0yJVx+OY898gie5S5pobjlXsLll/OYp0FKWkCWewlPPMGJv/hF6RSSKuZumRLe+EZe1mzCxReXTiKpUm65S1KFLHdJqpDlLkkVstwlqUIeUC3h7W/np9u3e567pAVjuZfw5jfzuNeplrSA3C1Twt69/MGBA6VTSKqYW+4lXHopL2k24U1vKp1EUqXccl9kExPwwAPw5JMwNNSalqRes9wX0cQEjI3B/7Zvyrx7d2vagpfUa5b7Irr2Wpiefua86enWfEnqJct9Ee3ZM7/5ktQpy30RrV/fevwo7+HBv3zT78yXpF6x3BfRpk0wMAB38Dc8+rJzgdb0pk2Fg0mqjqdCLqKZGzHf+N5JTjmwh8HBVrF7g2ZJvWa5L7LRURi9/h9pfr3JP+z6+9JxJFXK3TKSVCHLXZIqZLlLUoUsd0mqkAdUS3j/+9n9/e97PXdJC8ZyL+HCC/mflQ69pIXjbpkStm3jpJ07S6eQVDHLvYR3vYs/+cQnSqeQVDHLXZIqZLlLUoUsd0mqkOUuSRXyfLwSPvQhHn3oIV5ZOoekanW85R4R6yLi2xGxIyK2R8RVvQxWtXPP5ZdnnVU6hfQMMzdvb3zHm7fXoJvdMoeA92TmS4CzgXdExEt7E6ty993HyQ8/XDqF9FvevL0+HZd7Zu7PzIfaXz8J7ADW9ipY1a65hjNuuKF0Cum3vHl7fXqyzz0ihoBXAFt+z/fGgDGANWvW0Gg0erHKJW1Ds8nhw4cdi7apqSnHoq3UWFx5ZevxzE82AfjIP81mKPWj8X3RncjM7l4g4iTgO8CmzLzt/3vu8PBwTk5OdrW+KoyM0Gw2Wb1tW+kkfaHRaDAyMlI6Rl8oNRZDQ61dMd+mte6/ogHA4CDs2rXocQDfF0eKiK2ZuXE+y3R1KmREnAh8CZg4XrFL6l8zN28/kjdvX9o63i0TEQHcCOzIzI/1LpKkxTZzk/ZVV7QOqnrz9qWvm33u5wGXAj+IiJn9C9dk5p3dx6rcddex88EHmdffWNICGx0Frm99vatRMol6oeNyz8z/AKKHWZaPDRuYajZLp5BUMS8/UMK3vsUpW7eWTiGpYpZ7CR/8IIM331w6haSKWe6SVCHLXZIqZLlLUoUsd0mqkNdzL+HTn2ZyyxZeVTqHpGpZ7iUMD/Pr/ftLp5BUMXfLlPDVr/JH991XOoWkilnuJXz0o6y79dbSKSRVzHKXpApZ7pJUIctdkipkuUvqKxMTrTtDbd3aevQm3Z3xVMgSbr6ZHfffzzmlc0h9ZmICxsZmb9a9e3drGrxxyHy55V7CunUcPO200imkvnPttbPFPmN6ujVf82O5l/DFL7LmnntKp5D6zp4985uvY7PcS/jUp1h7++2lU0h9Z/36+c3XsVnukvrGpk0wMPDMeQMDrfmaH8tdUt8YHYXxcRgcbE0PDramPZg6f54tI6mvjI62/jUasGtX6TRLl1vuklQht9xL2LyZ7d/9LueVziGpWm65l3Dqqfzmuc8tnUJSxSz3Em66iT++667SKSRVzHIvwXKXtMAsd0mqkOUuSRWy3CWpQpa7JFXI89xLuPNO/uveezm/dA5J1XLLvYSBAZ5etap0CkkVs9xL+OQneeGXv1w6haSKuVumhFtv5bRms3QKSRVzy12SKtRVuUfERRExGRE7I+LqXoWSJHWn43KPiBOAfwP+Gngp8JaIeGmvgkmSOtfNlvtfADsz89HMfAr4AnBxb2JJkrrRzQHVtcDeI6b3Aa86+kkRMQaMtScPRsTDXayzJqcS8UTpEH3iVMCxaOmPsYgonQD6ZSz6w/B8F+im3H/fTz9/Z0bmODAOEBEPZubGLtZZDcdilmMxy7GY5VjMiogH57tMN7tl9gHrjpg+HfhZF68nSeqRbsr9P4EXR8SLIuJZwCXA7b2JJUnqRse7ZTLzUET8M/B14ATgM5m5/TiLjXe6vgo5FrMci1mOxSzHYta8xyIyf2c3uSRpifMTqpJUIctdkiq0KOXuZQpaImJdRHw7InZExPaIuKp0ptIi4oSI+F5E3FE6S0kRsToiNkfEI+33xzmlM5USEe9u/348HBG3RMSyuT52RHwmIg4c+XmgiHheRHwzIn7cfjxlLq+14OXuZQqe4RDwnsx8CXA28I5lPBYzrgJ2lA7RBz4O3JWZfwq8nGU6JhGxFngnsDEzz6J1ssYlZVMtqpuAi46adzVwd2a+GLi7PX1ci7Hl7mUK2jJzf2Y+1P76SVq/wGvLpionIk4HXgfcUDpLSRFxMnA+cCNAZj6Vmcv5mtArgWdHxEpggGX0+ZnMvBf476NmXwx8rv3154C/nctrLUa5/77LFCzbQpsREUPAK4AtZZMUdR3wXuDp0kEKOwN4HPhsexfVDRHxnNKhSsjMnwIfAfYA+4FfZOY3yqYq7vmZuR9aG4jAaXNZaDHKfU6XKVhOIuIk4EvAuzLzl6XzlBARrwcOZObW0ln6wErglcCnMvMVwK+Y45/etWnvT74YeBHwQuA5EfHWsqmWpsUody9TcISIOJFWsU9k5m2l8xR0HvCGiNhFa1fdqyPi82UjFbMP2JeZM3/FbaZV9svRhcBPMvPxzPwNcBtwbuFMpf08Il4A0H48MJeFFqPcvUxBW0QErf2qOzLzY6XzlJSZ78vM0zNziNZ74p7MXJZbaJn5GLA3Imau/HcB8MOCkUraA5wdEQPt35cLWKYHl49wO3BZ++vLgK/MZaEFv4dqh5cpqNV5wKXADyJiW3veNZl5Z8FM6g9XAhPtDaBHgbcVzlNEZm6JiM3AQ7TOLvsey+gyBBFxCzACnBoR+4APAB8Gbo2IK2j95/d3c3otLz8gSfXxE6qSVCHLXZIqZLlLUoUsd0mqkOUuSRWy3CWpQpa7JFXo/wDKa1yqmVBTagAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim([0,10])\n",
    "plt.ylim([0,10])\n",
    "plt.grid()\n",
    "plt.scatter([2,5,9,4,8,7],[3,4,6,7,1,2],color='b')\n",
    "plt.plot([7,7],[0,10],color='r');\n",
    "plt.plot([0,7],[4,4],color='r');\n",
    "plt.plot([7,10],[6,6],color='r');\n",
    "plt.plot([2,2],[0,4],'--',color='r');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* (第3层左右子区域)：有实例，则生成一个新结点，切分维度为$2mod2+1=1$，将该区域中的实例按照第1维度排序得$T = \\{(4,7)^T\\}$，该维度的中位数所对应的实例为$(4,7)^T$，因此将$(4,7)^T$保存至该结点中，并以$x^{(1)}=4$将该区域划分为左右两个子区域；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAEa5JREFUeJzt3X2MXXWdx/H3twWtYxeLS3G10I6ijjzsWl2y8pCws8IfqKxsoiJmYMElmY2riK7GIGj4x6p/qMHE1Tj4gMEJylaiiAQfwGuzIs1SHFewTK3QJykU1AuMg4UO3/3j3rGlWuncezu/6W/er6S5c07n3PPJb+58evq7554TmYkkqS4LSgeQJPWe5S5JFbLcJalClrskVchyl6QKWe6SVKFnLPeI+FJE7IiIu/ZY9/yI+H5E/LL9ePiBjSlJmon9OXK/Gjhzr3WXArdk5suAW9rLkqQ5IvbnQ0wR0Q/cmJkntJfHgcHM3B4RLwQamTlwIINKkvbfIR1u94LM3A7QLvgj9/WNETEMDAMsWrTo75cvX97hLuvy1FNPsWCBb3n0bd1KZvK4rwug/Ouib+tWACaPPrpYhmmlx2Iu2bBhw8OZuXQm23Ra7vstM0eAEYCBgYEcHx8/0Ls8KDQaDQYHB0vHKG9wkGazyZKxsdJJ5oTir4vpfTca5TIwHcHfkWkRsXmm23T6z+KD7ekY2o87OnweSdIB0Gm53wBc0P76AuBbvYmjeeflL2fyqKNKp5Cq84zTMhFxLTAIHBER24ArgI8D10XERcAW4C0HMqQqNjLChkaDF5XOIVXmGcs9M9+2j786vcdZJEk9csDfUJX+ouFhXn7//bvfyJPUE5a7ytqwgb5ms3QKqTqeRCpJFbLcJalClrskVchyV1krVzLx0peWTiFVxzdUVdaVV7Kx0cCPMUm95ZG7JFXII3eVdd55HPvgg57nLvWY5a6ytm3j2Z7nLvWc0zKSVCHLXZIqZLlLUoWcc1dZJ5/MI1u2sKR0DqkylrvK+tjHuK/RYEXpHFJlnJaRpAp55K6y3vQmjn/oIVizpnQSqSoeuaus3/yGQx99tHQKqTqWuyRVyHKXpApZ7pJUId9QVVmnn87v7rvP89ylHrPcVdaHP8zmRoMXl84hVcZpGUmqkEfuKut1r+Nvf/tbWLu2dBKpKh65q6zHH2fhzp2lU0jVsdwlqUKWuyRVyHKXpAr5hqrKOussfvOrX3meu9RjlrvKev/72dpocEzpHFJlnJaRpAp55K6yBgdZ2WzC2FjpJFJVPHKXpApZ7pJUoa7KPSLeGxF3R8RdEXFtRCzqVTBJUuc6LveIWAa8GzgxM08AFgLn9iqYJKlz3b6hegjwnIh4EugD7u8+kuaVc85hx4YNnucu9VjH5Z6Zv46ITwBbgMeB72Xm9/b+vogYBoYBli5dSqPR6HSXVZmYmHAsAI47jonly7nfsQDKvy5WNpsAjM2Bn0fpsTjYRWZ2tmHE4cA3gLcCTeC/gdWZ+dV9bTMwMJDj4+Md7a82jUaDwcHB0jHKm5xkzZo1nHbmmaWTzAnFXxfT+54DpVp8LOaQiFiXmSfOZJtu3lA9A7gvMx/KzCeB64FTung+zUevfz1/d+mlpVNI1emm3LcAJ0VEX0QEcDqwvjexJEnd6LjcM3MtsBq4E/h5+7lGepRLktSFrs6WycwrgCt6lEWS1CN+QlWSKuSFw1TWhRfywD33eJ671GMeuausCy/kAU+DlHrOcldZDz/MoY88UjqFVB2nZVTWm9/M8c0mnH126SRSVTxyl6QKWe6SVCHLXZIqZLlLUoV8Q1VlveMd/Pruuz3PXeoxy11lvfWtPDQHLi8r1cZpGZW1dSvP3rGjdAqpOh65q6zzz+fYZhPOOad0EqkqHrmrmNFRuP12eOwx6O9vLUvqDctdRYyOwvAw/GFna3nz5tayBS/1huWuIi6/HCYnn75ucrK1XlL3LHcVsWXLzNZLmhnLXUUsX956/CTv445/POdP1kvqjuWuIlatgr4+uJF/5t7jTwFay6tWFQ4mVcJTIVXE0FDr8YsfGOfwHVtYsaJV7NPrJXXHclcxQ0MwdNW/0/xuk3/b9K+l40hVcVpGkipkuUtShSx3SaqQ5S5JFfINVZX1oQ+x+Wc/83ruUo9Z7irrjDP43SG+DKVec1pGZY2NsXjjxtIppOpY7irrPe/hpZ/5TOkUUnUsd0mqkOUuSRWy3CWpQpa7JFXIc9BU1kc/yr133smrS+eQKtPVkXtELImI1RFxT0Ssj4iTexVM88Qpp/DoCSeUTiE9zeho66btCxYcvDdv73Za5tPAzZn5CuCVwPruI2leue02DrvrrtIppD+avnn75s2QefDevL3jaZmIOAw4DbgQIDOfAJ7oTSzNG5ddxkuaTXjXu0onEcDGjTAxAYODpZOwstmEJbN/YYpjbofv7Nxr5SQsugi4atbjdKybOfeXAA8BX46IVwLrgEsy8/d7flNEDAPDAEuXLqXRaHSxy3pMTEw4FrR+gaemphyLttKvi5N37mThrl1MNJvFMkybmpqiWSDHsmX7/rs5MCz7LTKzsw0jTgRuB07NzLUR8Wng0cz88L62GRgYyPHx8c6SVqbRaDA4B46OihscpNlssmRsrHSSOaH462J633PgH9tSY9Hf35qK2duKFbBp02ynaYmIdZl54ky26WbOfRuwLTPXtpdXgyc9SDq4Td+8fU8H483bOy73zHwA2BoRA+1VpwO/6EkqSSpkaAhGRlpH6hGtx5GRg+/m7d2e534xMBoRzwLuBd7efSTNK1deycY77mBG/9+UDrChoYOvzPfWVbln5hj4e6kurFw5J968k2rj5QdU1g9+wOHr1pVOIVXHcldZH/kIK665pnQKqTqWuyRVyHKXpApZ7pJUIctdkirk9dxV1uc/z/jatbymdA6pMpa7yhoY4PHt20unkKrjtIzK+va3+evbbiudQqqO5a6yPvlJjr7uutIppOpY7pJUIctdkipkuUtShSx3SaqQp0KqrGuuYf1PfsLJpXNIlfHIXWUdfTQ7jzyydAqpOpa7yvr611l6662lU0jVsdxV1uc+x7IbbiidQqqO5S5JFbLcJalClrskVchyl6QKeZ67ylq9mrt//GNOLZ1DqoxH7irriCN48nnPK51Cqo7lrrKuvpq/ufnm0imk6ljuKstylw4Iy12SKmS5S1KFLHdJqpDlLkkV8jx3lXXTTfzfmjWcVjqHVBmP3FVWXx9PLVpUOoVUHctdZX32s7zom98snUKqjtMyKuu66ziy2SydQqqOR+6SVKGuyz0iFkbETyPixl4EkmbT6Cj098OCBa3H0dHSiaTe6MW0zCXAeuCwHjyXNGtGR2F4GCYnW8ubN7eWAYaGyuWSeqGrco+Io4A3AKuA/3ym7+/buhUGB7vZZR02buTknTvh+ONLJylvbIzFu3YVeV0cczt8Z+deKydh0UXAVbMeB4CVzSYsWVJm5wBjY7B4cbn9q2e6PXK/EvgA8Ff7+oaIGAaGAU449FCavnnG4maTBZmOBUB/P1NTUywsMBbLlu3770r9aKampoq+Lhbv2sXUzp38pNEolmHaxMQEjTmQ42DVcblHxFnAjsxcFxGD+/q+zBwBRgAGBgZyydhYp7usx+AgzWYTx6Kl0WgwWODIfWV/aypmbytWwKZCP5pSY/FHg4McAmUztBUfi4NcN2+ongq8MSI2AV8DXhsRX+1JKmkWrFoFfX1PX9fX11ovHew6LvfM/GBmHpWZ/cC5wK2ZeV7PkkkH2NAQjIy0jtQjWo8jI76Zqjr4ISbNa0NDlrnq1JNyz8wG0OjFc0mSuucnVCWpQpa7JFXIcpekClnuklQhy12SKmS5S1KFLHdJqpDlLkkVstwlqUKWuyRVyHKXpApZ7pJUIctdkipkuc+y0VG4/XZ47DHo728tS1KvWe6zaHQUhofhD+2bMm/e3Fq24CX1muU+iy6/HCYnn75ucrK1XpJ6yXKfRVu2zGy9JHXKcp9Fy5fPbL0kdcpyn0WrVkFf39PX9fW11ktSL3mD7Fk0fSPmRRe1HlesaBW7N2iW1GuW+ywbGgKugmYTNo2VTiOpVk7LSFKFLHdJqpDlLkkVstwlqUKWuyRVyHKXpApZ7pJUIctdkipkuUtShSx3SaqQ5S5JFbLcJalClrskVajjco+IoyPihxGxPiLujohLehlM0uyavnl740fevL0G3Ry57wLel5nHAicB74yI43oTS9Js8ubt9em43DNze2be2f76MWA9sKxXwSTNHm/eXp+e3KwjIvqBVwFr/8zfDQPDAEuXLqXRaPRilwe1lc0mU1NTjkXbxMSEY9FWaiwuvrj1eMxnmwB84j92Zyj1o/F10Z3IzO6eIGIx8CNgVWZe/5e+d2BgIMfHx7vaXxUGB2k2mywZ81ZMAI1Gg8HBwdIx5oRSY9Hf35qK+SGtff8TDaB1K8hNm2Y9DuDrYk8RsS4zT5zJNl2dLRMRhwLfAEafqdglzV3evL0+HU/LREQAXwTWZ+anehdJ0mzb8+btf9jpzdtr0M2c+6nA+cDPI2J6fuGyzLyp+1iSZtv0zdsBNjVKJlEvdFzumfk/QPQwiySpR/yEqiRVyHKXpApZ7pJUIctdkipkuUtShSx3SaqQ5S5JFbLcJalClrskVchyl6QKWe6SVCHLXZIqZLlLUoUsd0lzyuho685Q69a1Hr1Jd2d6cg9VSeqF0VEYHt59s+7Nm1vL4I1DZsojd0lzxuWX7y72aZOTrfWaGctd0pyxZcvM1mvfLHdJc8by5TNbr32z3CXNGatWQV/f09f19bXWa2Ysd0lzxtAQjIzAihWt5RUrWsu+mTpzni0jaU4ZGmr9aTRg06bSaQ5eHrlLUoUsd0mqkOUuSRWy3CWpQpa7JFXIcpekClnuklQhy12SKmS5S1KFLHdJqpDlLkkVstwlqUKWuyRVyHKXpAp1Ve4RcWZEjEfExoi4tFehJEnd6bjcI2Ih8F/A64DjgLdFxHG9CiZJ6lw3R+7/AGzMzHsz8wnga8DZvYklSepGN3diWgZs3WN5G/Cavb8pIoaB4fbizoi4q4t91uQIIh4uHWKOOAJwLFrmxlhElE4Ac2Us5oaBmW7QTbn/uZ9+/smKzBFgBCAi7sjME7vYZzUci90ci90ci90ci90i4o6ZbtPNtMw24Og9lo8C7u/i+SRJPdJNuf8v8LKIeHFEPAs4F7ihN7EkSd3oeFomM3dFxLuA7wILgS9l5t3PsNlIp/urkGOxm2Oxm2Oxm2Ox24zHIjL/ZJpcknSQ8xOqklQhy12SKjQr5e5lCloi4uiI+GFErI+IuyPiktKZSouIhRHx04i4sXSWkiJiSUSsjoh72q+Pk0tnKiUi3tv+/bgrIq6NiEWlM82WiPhSROzY8/NAEfH8iPh+RPyy/Xj4/jzXAS93L1PwNLuA92XmscBJwDvn8VhMuwRYXzrEHPBp4ObMfAXwSubpmETEMuDdwImZeQKtkzXOLZtqVl0NnLnXukuBWzLzZcAt7eVnNBtH7l6moC0zt2fmne2vH6P1C7ysbKpyIuIo4A3AF0pnKSkiDgNOA74IkJlPZGazbKqiDgGeExGHAH3Mo8/PZOYa4Ld7rT4b+Er7668A/7I/zzUb5f7nLlMwbwttWkT0A68C1pZNUtSVwAeAp0oHKewlwEPAl9tTVF+IiOeWDlVCZv4a+ASwBdgOPJKZ3yubqrgXZOZ2aB0gAkfuz0azUe77dZmC+SQiFgPfAN6TmY+WzlNCRJwF7MjMdaWzzAGHAK8GPpeZrwJ+z37+17s27fnks4EXAy8CnhsR55VNdXCajXL3MgV7iIhDaRX7aGZeXzpPQacCb4yITbSm6l4bEV8tG6mYbcC2zJz+X9xqWmU/H50B3JeZD2Xmk8D1wCmFM5X2YES8EKD9uGN/NpqNcvcyBW0REbTmVddn5qdK5ykpMz+YmUdlZj+t18StmTkvj9Ay8wFga0RMX/nvdOAXBSOVtAU4KSL62r8vpzNP31zeww3ABe2vLwC+tT8bdXNVyP3S4WUKanUqcD7w84gYa6+7LDNvKphJc8PFwGj7AOhe4O2F8xSRmWsjYjVwJ62zy37KPLoMQURcCwwCR0TENuAK4OPAdRFxEa1//N6yX8/l5QckqT5+QlWSKmS5S1KFLHdJqpDlLkkVstwlqUKWuyRVyHKXpAr9P2+BtZimY45yAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim([0,10])\n",
    "plt.ylim([0,10])\n",
    "plt.grid()\n",
    "plt.scatter([2,5,9,4,8,7],[3,4,6,7,1,2],color='b')\n",
    "plt.plot([7,7],[0,10],color='r');\n",
    "plt.plot([0,7],[4,4],color='r');\n",
    "plt.plot([7,10],[6,6],color='r');\n",
    "plt.plot([2,2],[0,4],color='r');\n",
    "plt.plot([4,4],[4,10],'--',color='r');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* (第3层右左子区域)：有实例，则生成一个新结点，切分维度为$2mod2+1=1$，将该区域中的实例按照第1维度排序得$T = \\{(8,1)^T\\}$，该维度的中位数所对应的实例为$(8,1)^T$，因此将$(8,1)^T$保存至该结点中，并以$x^{(1)}=8$将该区域划分为左右两个子区域；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAEdVJREFUeJzt3X+QXWV9x/H3NyQ1rCkGS7AaSKKIW360RstUfswwt4IzqCidURG7IDjMrGMtosVxkOj4j1H/UAdnrI4LKo7uYGlkFJVSFb1mKiZTgmsBw8YI+SWBAHoh62Iw4ekf927zA1J277nZ59wn79c/Z8+z99zznWfP/eTJc849J1JKSJLKMid3AZKk3jPcJalAhrskFchwl6QCGe6SVCDDXZIK9JzhHhFfiYgdEXHPPm0vjIgfRsSvO8ujD22ZkqSZmM7I/QbgvAPargZuTymdCNzeWZck1URM50tMEbEM+F5K6dTO+jjQSCltj4gXA82U0uChLFSSNH1zu9zuRSml7QCdgD/2YC+MiGFgGGD+/Pl/u2TJki53WZann36aOXM85TGwdSspJZ70uADyHxcDW7cCMHn88dlqmJK7L+pkw4YNj6aUFs1km27DfdpSSiPACMDg4GAaHx8/1LvsC81mk0ajkbuM/BoNWq0WC8fGcldSC9mPi6l9N5v5amCqBD8jUyJi80y36fafxYc70zF0lju6fB9J0iHQbbjfAlza+flS4Du9KUeS1AvTuRTyRuDnwGBEbIuIy4FPAa+LiF8Dr+usS5Jq4jnn3FNK7zjIr87pcS2SpB7xVLQkFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKpDhLkkFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLhLUoEMd0kqkOEuSQUy3CWpQIa7JBXIcJekAhnuklSgSuEeER+IiHsj4p6IuDEi5veqMElS97oO94hYDLwPOC2ldCpwBHBRrwqTJHWv6rTMXODIiJgLDAAPVi9JklTV3G43TCn9NiI+DWwBngR+kFL6wYGvi4hhYBhg0aJFNJvNbndZlImJCfsCWN5qsWfPHvuiI/dxsbzVAmCsBn+P3H3R7yKl1N2GEUcD3wLeDrSAfwdWpZS+cbBtBgcH0/j4eFf7K02z2aTRaOQuI79Gg1arxcKxsdyV1EL242Jq3zUI1ex9USMRsS6ldNpMtqkyLXMu8EBK6ZGU0p+Am4EzK7yfJKlHqoT7FuD0iBiIiADOAdb3pixJUhVdh3tKaS2wCrgLuLvzXiM9qkuSVEHXJ1QBUkofAz7Wo1okST3iN1QlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVCDDXZIKZLgrm9FRWLMGdu6EZcva65J6w3BXFqOjMDwMf9zVXt+8ub1uwEu9YbgrixUrYHJy/7bJyXa7pOoMd2WxZcvM2iXNjOGuLJYsmVm7pJkx3JXFypUwMLB/28BAu11SdZWeoSp1a2iovZx/eXu5dGk72KfaJVVjuCuboSHgOmi1YNNY7mqksjgtI0kFMtwlqUCGuyQVyHCXpAIZ7pJUIMNdkgpkuEtSgQx3SSqQ4S5JBTLcJalAhrskFchwl6QCGe6SVKBK4R4RCyNiVUTcFxHrI+KMXhUmSbmMjrYf2j5nTv8+vL3qLX8/B9yWUnprRPwZMPBcG0hSnU09vH3qGb9TD2+H/nreQNfhHhFHAWcDlwGklJ4CnupNWZKy2LgRJiag0chdCctbLVi4cNb3e8Ia+P6uAxonOw+WuW7Wy+lalZH7y4BHgK9GxCuBdcCVKaU/7PuiiBgGhgEWLVpEs9mssMtyTExM2Be0P8B79uyxLzpyHxdn7NrFEbt3M9FqZasBYMHGjTw/JVonnjjr+168+OC/y9wtMxIppe42jDgNWAOclVJaGxGfA55IKX30YNsMDg6m8fHx7iotTLPZpFGD0VF2jQatVouFYz6KCWpwXEztO/c/thmPi2XL2lMxB1q6FDZtmu1q2iJiXUrptJlsU+WE6jZgW0ppbWd9FfDqCu8nSdmV8vD2rsM9pfQQsDUiBjtN5wC/6klVkg5vr3gFk8cdl2XXQ0MwMtIeqUe0lyMj/XUyFapfLXMFMNq5UuZ+4F3VS5J02BsZYUOzyUsy7X5oqP/C/ECVwj2lNAbMaB5IknToVR25S1LvDQ/zigcfrMUlmf3KcJdUPxs2MNBP1x3WkPeWkaQCGe6SVCDDXZIKZLhLqp/ly5l4+ctzV9HXPKEqqX6uvZaNzSZ5vsZUBkfuklQgR+6S6ufiiznp4Ye9zr0Cw11S/WzbxvO8zr0Sp2UkqUCGuyQVyHCXpAI55y6pfs44g8e3bGH2n6BaDsNdUv188pM80GyyNHcdfcxpGUkqkCN3SfXzlrdwyiOPwOrVuSvpW47cJdXPY48x74knclfR1wx3SSqQ4S5JBTLcJalAnlCVVD/nnMPvH3jA69wrMNwl1c9HP8rmZpOX5q6jjzktI0kFcuQuqX5e/3r++ne/g7Vrc1fStxy5S6qfJ5/kiF27clfR1wx3SSqQ4S5JBTLcJalAnlCVVD/nn89jv/mN17lXYLhLqp8PfpCtzSYn5K6jjzktI0kFcuQuqX4aDZa3WjA2lruSvuXIXZIKZLhLUoEqh3tEHBERv4iI7/WiIGk2jY7CsmUwZ057OTqauyKpN3ox534lsB44qgfvJc2a0VEYHobJyfb65s3tdYChoXx1Sb1QKdwj4jjgjcBK4F+e6/UDW7dCo1Fll2XYuJEzdu2CU07JXUl+Y2Ms2L07y3Fxwhr4/oG3L5mE+ZcD1816OQDtk4gLM17dPTYGCxbk2/+UCy9kx4YNXudeQdWR+7XAh4A/P9gLImIYGAY4dd48Wq1WxV32vwWtFnNSsi+AI+fN4+m5c5nI0BeLFx/8d7n+NHv27Ml6XCzYvZs9u3bx82YzWw0AnHwyE0uW8GDuOvpY1+EeEecDO1JK6yKicbDXpZRGgBGAwcHBtNBLm6DRoNVqYV+0NZtNGhlG7suXtadiDrR0KWzK9KfJ1Rf/p9FgLuStAWByktWrV3N27jr6WJUTqmcBb46ITcA3gddGxDd6UpU0C1auhIGB/dsGBtrtyuwNb+Bvrr46dxV9retwTyl9OKV0XEppGXAR8OOU0sU9q0w6xIaGYGSkPVKPaC9HRjyZqjL4DVUd1oaGDHOVqSfhnlJqAs1evJckqTq/oSpJBXJaRlL9XHYZD913n9e5V+DIXVL9XHYZD513Xu4q+prhLql+Hn2UeY8/nruKvua0jKT6eetbOaXVggsuyF1J33LkLkkFMtwlqUCGuyQVyHCXpAJ5QlVS/bznPfz23nu9zr0Cw11S/bz97TzivdwrcVpGUv1s3crzduzIXUVfc+QuqX4uuYSTWi248MLclfQtR+6zbHQU1qyBnTth2bL2uiT1muE+i0ZHYXgY/th5KPPmze11A15Srxnus2jFCpic3L9tcrLdLkm9ZLjPoi1bZtYuSd3yhOosWrKkPRXzbO2S9nHVVWy9+26vc6/AkfssWrkSBgb2bxsYaLdL2seb3sRjZ56Zu4q+5sh9Fk09iHn+5e3l0qXtYPcBzdIBxsc50vnKSgz3WTY0BFwHrRZsGstdjVRT7343g60WvPOduSvpW07LSFKBDHdJKpDhLkkFMtwlqUCeUJVUPx/5CJt/+Uuvc6/AcJdUP+eey+/nGk9VOC0jqX7GxliwcWPuKvqa4S6pft7/fl7++c/nrqKvGe6SVCDDXZIKZLhLUoEMd0kqkNcaSaqfT3yC+++6i1fnrqOPdT1yj4jjI+InEbE+Iu6NiCt7WZik2TX18PbmT2vw8PYzz+SJU0/NWED/qzItsxu4KqV0EnA68N6IOLk3ZUmaTbV7ePsdd3DUPfdk2nkZug73lNL2lNJdnZ93AuuBxb0qTNLsqd3D26+5hpddf32mnZehJ3PuEbEMeBWw9ll+NwwMAyxatIhms9mLXfa15a0We/bssS86JiYm7IuOXH1xxRXt5QlfaAHw6X/aW0OOP42fkeoipVTtDSIWAD8FVqaUbv7/Xjs4OJjGx8cr7a8IjQatVouFYz6KCaDZbNJoNHKXUQu5+mLZsvZUzE9o7/vvaQLtR0Fu2jTr5fgZOUBErEspnTaTbSpdChkR84BvAaPPFeyS6suHt5en62mZiAjgy8D6lNJne1eSpNm278Pb/7jLh7eXoMqc+1nAJcDdETH1f6drUkq3Vi9L0mybeng7wKZmzkqAa69l4513MqN5CO2n63BPKf0XED2sRZLali9notXKXUVf8/YDkurnRz/i6HXrclfR1wx3SfXz8Y+z9Otfz11FXzPcJalAhrskFchwl6QCGe6SVCDv5y6pfr70JcbXruU1uevoY4a7pPoZHOTJ7dtzV9HXnJaRVD/f/S5/cccduavoa4a7pPr5zGc4/qabclfR1wx3SSqQ4S5JBTLcJalAhrukWhkdhTVrYOfO9hOisj2ku88Z7pJqY3QUhofhbbu+zn/84zVs3txeN+BnznCXVBsrVsDkJGzjeHYuPBZor69YkbmwPmS4S6qNLVvaywv5NwbHfvyMdk2f4S6pNpYsaS/fwxd55R23PKNd02e4S6qNlSthYGD/toGBdrtmxnvLSKqNoaH2cv7l7eXSpe1gn2rX9BnukmplaAi4Dlot2DSWu5r+5bSMJBXIkbuk+lm1int/9jPOyl1HH3PkLql+jjmGP73gBbmr6GuGu6T6ueEG/vK223JX0dcMd0n1Y7hXZrhLUoEMd0kqkOEuSQUy3CWpQF7nLql+br2V/1m9mrNz19HHHLlLqp+BAZ6ePz93FX3NcJdUP1/4Ai/59rdzV9HXnJaRVD833cSxrVbuKvqaI3dJKlClcI+I8yJiPCI2RsTVvSpKklRN1+EeEUcA/wq8HjgZeEdEnNyrwiRJ3asycv87YGNK6f6U0lPAN4ELelOWJKmKKidUFwNb91nfBrzmwBdFxDAw3FndFRH3VNhnSY4h4tHcRdTEMYB90VaPvojIXQH4GdnX4Ew3qBLuz/bXT89oSGkEGAGIiDtTSqdV2Gcx7Iu97Iu97Iu97Iu9IuLOmW5TZVpmG3D8PuvHAQ9WeD9JUo9UCff/Bk6MiJdGxJ8BFwG39KYsSVIVXU/LpJR2R8Q/A/8JHAF8JaV073NsNtLt/gpkX+xlX+xlX+xlX+w1476IlJ4xTS5J6nN+Q1WSCmS4S1KBZiXcvU1BW0QcHxE/iYj1EXFvRFyZu6bcIuKIiPhFRHwvdy05RcTCiFgVEfd1jo8zcteUS0R8oPP5uCciboyIw+bevxHxlYjYse/3gSLihRHxw4j4dWd59HTe65CHu7cp2M9u4KqU0knA6cB7D+O+mHIlsD53ETXwOeC2lNJfAa/kMO2TiFgMvA84LaV0Ku2LNS7KW9WsugE474C2q4HbU0onArd31p/TbIzcvU1BR0ppe0rprs7PO2l/gBfnrSqfiDgOeCNwfe5acoqIo4CzgS8DpJSeSikdzve7nQscGRFzgQEOo+/PpJRWA787oPkC4Gudn78G/MN03ms2wv3ZblNw2AbalIhYBrwKWJu3kqyuBT4EPJ27kMxeBjwCfLUzRXV9RDw/d1E5pJR+C3wa2AJsBx5PKf0gb1XZvSiltB3aA0Tg2OlsNBvhPq3bFBxOImIB8C3g/SmlJ3LXk0NEnA/sSCmty11LDcwFXg18MaX0KuAPTPO/3qXpzCdfALwUeAnw/Ii4OG9V/Wk2wt3bFOwjIubRDvbRlNLNuevJ6CzgzRGxifZU3Wsj4ht5S8pmG7AtpTT1v7hVtMP+cHQu8EBK6ZGU0p+Am4EzM9eU28MR8WKAznLHdDaajXD3NgUdERG051XXp5Q+m7uenFJKH04pHZdSWkb7mPhxSumwHKGllB4CtkbE1J3/zgF+lbGknLYAp0fEQOfzcg6H6cnlfdwCXNr5+VLgO9PZ6JA/Q7XL2xSU6izgEuDuiBjrtF2TUro1Y02qhyuA0c4A6H7gXZnrySKltDYiVgF30b667BccRrchiIgbgQZwTERsAz4GfAq4KSIup/2P39um9V7efkCSyuM3VCWpQIa7JBXIcJekAhnuklQgw12SCmS4S1KBDHdJKtD/AkqYvLkkf2ZsAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim([0,10])\n",
    "plt.ylim([0,10])\n",
    "plt.grid()\n",
    "plt.scatter([2,5,9,4,8,7],[3,4,6,7,1,2],color='b')\n",
    "plt.plot([7,7],[0,10],color='r');\n",
    "plt.plot([0,7],[4,4],color='r');\n",
    "plt.plot([7,10],[6,6],color='r');\n",
    "plt.plot([2,2],[0,4],color='r');\n",
    "plt.plot([4,4],[4,10],color='r');\n",
    "plt.plot([8,8],[0,6],'--',color='r');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* (第3层右右子区域)：没有实例。\n",
    "* (第4层所有区域)：没有实例，结束，得到的kd树如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAADzxJREFUeJzt3X+MpHV9wPH35zjMsV7JYTiNPbhbJWQrkAj20oIkZiqa0Gikf7QpZjXUkOwftUitiUFJw1+X+Acx8kfbZFHUhA2mPUgkaCwGGZsmHqnAJoDnAsH7pSiYZuqtK4u3fPrHM9v7odfbnWduvrPfe7/+mZ3n5pnnk2dn3zv3zM48kZlIkuqyqfQAkqThM+6SVCHjLkkVMu6SVCHjLkkVMu6SVKEzxj0i7ouIVyLi2ROWvSUivhsRL/QvLzq7Y0qS1mMtz9y/Btx4yrI7gMcy83Lgsf51SdKYiLW8iSkiJoFHMvOq/vUFoJOZL0fE24FuZk6dzUElSWu3ecD13paZLwP0A//W090wImaAGYAtW7b88c6dOwfcZF3eeOMNNm3yJY+Jw4fJTH7j4wIo/7iYOHwYgKVLLy02w6rS+2KcPP/887/MzO3rWWfQuK9ZZs4CswBTU1O5sLBwtje5IXS7XTqdTukxyut06PV6bJufLz3JWCj+uFjddrdbbgZWR/BnZFVEHFzvOoP+WvxF/3AM/ctXBrwfSdJZMGjcHwZu6X99C/DN4YwjSRqGtfwp5APAD4CpiDgSEbcCXwA+GBEvAB/sX5ckjYkzHnPPzI+e5p9uGPIskqQh8aVoSaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SaqQcZekChl3SapQq7hHxKcj4rmIeDYiHoiILcMaTJI0uIHjHhE7gE8BuzPzKuA84OZhDSZJGlzbwzKbgQsiYjMwAfys/UiSpLY2D7piZv40Iu4GDgG/AR7NzEdPvV1EzAAzANu3b6fb7Q66yaosLi66L4Crez1WVlbcF32lHxdX93oAzI/B96P0vtjoIjMHWzHiIuBB4K+BHvBvwN7MvP9060xNTeXCwsJA26tNt9ul0+mUHqO8Toder8e2+fnSk4yF4o+L1W2PQVSL74sxEhFPZubu9azT5rDMB4CfZOarmflb4CHgvS3uT5I0JG3ifgi4NiImIiKAG4D9wxlLktTGwHHPzCeAvcBTwDP9+5od0lySpBYGfkEVIDPvAu4a0iySpCHxHaqSVCHjLkkVMu6SVCHjLkkVMu6SVCHjLkkVMu6SVCHjLkkVMu6SVCHjLkkVMu6SVCHjLkkVMu6SVCHjrmLm5mDfPjh6FCYnm+uShsO4q4i5OZiZgdeWm+sHDzbXDbw0HMZdRdx5JywtnbxsaalZLqk9464iDh1a33JJ62PcVcTOnetbLml9jLuK2LMHJiZOXjYx0SyX1F6rc6hKg5qebi633Npc7trVhH11uaR2jLuKmZ4G7oVeDw7Ml55GqouHZSSpQsZdkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQq3iHhHbImJvRPw4IvZHxHXDGkySSpmba07avmnTxj15e9uP/L0H+E5m/mVEvAmYONMKkjTOVk/evnqO39WTt8PGOt/AwHGPiAuB9wF/A5CZrwOvD2csSUW8+CIsLkKnU3yO65aX4corR77py/bBt5ZPWbjUP7HMvSMfZ2Btnrm/E3gV+GpEvBt4Erg9M3994o0iYgaYAdi+fTvdbrfFJuuxuLjovgCu7vVYWVlxX/SVflxct7zMeceOsdjrFZsBYGuvx6ZMegXm2LHj9P9WeLesS2TmYCtG7Ab2Addn5hMRcQ/wq8z8x9OtMzU1lQsLC4NNWplut0un9LOjcdDp0Ov12DbvqZhgDB4Xq9su/cu24ONicrI5FHOqXbvgwIFRT9OIiCczc/d61mnzguoR4EhmPtG/vhd4T4v7k6Tiajl5+8Bxz8yfA4cjYqq/6AbgR0OZSpIKmZ6G2dnmmXpEczk7u7FeTIX2fy1zGzDX/0uZl4BPtB9Jksqant54MT9Vq7hn5jywruNAkqSzz3eoSlKFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFjLskVci4S1KFWsc9Is6LiKcj4pFhDCSN0twcTE7Cpk3N5dxc6Ymk4dg8hPu4HdgPXDiE+5JGZm4OZmZgaam5fvBgcx1gerrcXNIwtIp7RFwCfAjYA/zDmW4/cfgwdDptNlmHF1/kuuVluPLK0pOUNz/P1mPHijwuLtsH31o+ZeESbLkVuHfk4wBwda8H27aV2TjA/Dxs3Vpu+xqats/cvwR8FviD090gImaAGYCrzj+fXq/XcpMb39Zej02Z7gvggvPP543Nm1kssC927Dj9v5X61qysrBR9XGw9doyV5WV+0O0WmwGaX3IrKyt0C8+xkQ0c94j4MPBKZj4ZEZ3T3S4zZ4FZgKmpqdw2Pz/oJuvR6dDr9XBfNLrdLp0Cz9yvnmwOxZxq1y44UOhbU2pf/J9Oh81QdgaAbdvo9Xrl59jA2rygej3wkYg4AHwDeH9E3D+UqaQR2LMHJiZOXjYx0SyXNrqB456Zn8vMSzJzErgZ+F5mfmxok0ln2fQ0zM42z9QjmsvZWV9MVR2G8dcy0oY1PW3MVaehxD0zu0B3GPclSWrPd6hKUoWMuyRVyLhLUoWMuyRVyLhLUoWMuyRVyLhLUoWMuyRVyLhLUoWMuyRVyLhLUoWMuyRVyLhLUoWM+4jNzcG+fXD0KExONtcladiM+wjNzcHMDLzWPynzwYPNdQMvadiM+wjdeScsLZ28bGmpWS5Jw2TcR+jQofUtl6RBGfcR2rlzfcslaVDGfYT27IGJiZOXTUw0yyVpmDxB9gitnoh5y63N5a5dTdg9QbOkYTPuIzY9DdwLvR4cmC89jaRaeVhGkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQsZdkipk3CWpQsZdkio0cNwj4tKIeDwi9kfEcxFx+zAHkzRaqydv737fk7fXoM0z92PAZzLzXcC1wCcj4orhjCVplDx5e30GjntmvpyZT/W/PgrsB3YMazBJo+PJ2+szlJN1RMQkcA3wxO/5txlgBmD79u10u91hbHJDu7rXY2VlxX3Rt7i46L7oK7Uvbrutubzsn3sA3P23x2co8a3xZ6S9yMx2dxCxFfg+sCczH/r/bjs1NZULCwuttleFToder8e2eU/FBNDtdul0OqXHGAul9sXkZHMo5nGabf8ZXaA5FeSBAyMfx5+RU0TEk5m5ez3rtPprmYg4H3gQmDtT2CWNL0/eXp+BD8tERABfAfZn5heHN5KkUTvx5O2vLXvy9hq0OeZ+PfBx4JmIWP2/0+cz89vtx5I0aqsnbwc40C05iYZh4Lhn5n8CMcRZJElD4jtUJalCxl2SKmTcJalCxl2SKmTcJalCxl2SKmTcJalCxl2SKmTcJalCxl2SKmTcJalCxl2SKmTcJalCxl3SWJmbg3374OjR5gxRnqR7MMZd0tiYm4OZmeaEIdCc+m9mxsAPwrhLGht33glLSycvW1pqlmt9jLuksXHo0PqW6/SMu6SxsXPn+pbr9Iy7pLGxZw9MTJy8bGKiWa71aXOCbEkaqunp5nLLrc3lrl1N2FeXa+2Mu6SxMj0N3Au9HhyYLz3NxuVhGUmqkHGXpAoZd0mqkHGXpAoZd0mqkHGXpAoZd0mqkHGXpAoZd0mqkHGXpAoZd0mqkHGXpAoZd0mqkHGXpAq1intE3BgRCxHxYkTcMayhJEntDBz3iDgP+Cfgz4ErgI9GxBXDGkySNLg2z9z/BHgxM1/KzNeBbwA3DWcsSVIbbc7EtAM4fML1I8CfnnqjiJgBZvpXlyPi2RbbrMnFRPyy9BBj4mLAfdEYj30RUXoC8GfkRFPrXaFN3H/fdz9/Z0HmLDALEBE/zMzdLbZZDffFce6L49wXx7kvjouIH653nTaHZY4Al55w/RLgZy3uT5I0JG3i/l/A5RHxjoh4E3Az8PBwxpIktTHwYZnMPBYRfwf8O3AecF9mPneG1WYH3V6F3BfHuS+Oc18c5744bt37IjJ/5zC5JGmD8x2qklQh4y5JFRpJ3P2YgkZEXBoRj0fE/oh4LiJuLz1TaRFxXkQ8HRGPlJ6lpIjYFhF7I+LH/cfHdaVnKiUiPt3/+Xg2Ih6IiC2lZxqViLgvIl458f1AEfGWiPhuRLzQv7xoLfd11uPuxxSc5Bjwmcx8F3At8MlzeF+suh3YX3qIMXAP8J3M/CPg3Zyj+yQidgCfAnZn5lU0f6xxc9mpRuprwI2nLLsDeCwzLwce618/o1E8c/djCvoy8+XMfKr/9VGaH+AdZacqJyIuAT4EfLn0LCVFxIXA+4CvAGTm65nZKztVUZuBCyJiMzDBOfT+mcz8D+C/T1l8E/D1/tdfB/5iLfc1irj/vo8pOGeDtioiJoFrgCfKTlLUl4DPAm+UHqSwdwKvAl/tH6L6ckS8ufRQJWTmT4G7gUPAy8D/ZOajZacq7m2Z+TI0TxCBt65lpVHEfU0fU3AuiYitwIPA32fmr0rPU0JEfBh4JTOfLD3LGNgMvAf4l8y8Bvg1a/yvd236x5NvAt4B/CHw5oj4WNmpNqZRxN2PKThBRJxPE/a5zHyo9DwFXQ98JCIO0Byqe39E3F92pGKOAEcyc/V/cXtpYn8u+gDwk8x8NTN/CzwEvLfwTKX9IiLeDtC/fGUtK40i7n5MQV9EBM1x1f2Z+cXS85SUmZ/LzEsyc5LmMfG9zDwnn6Fl5s+BwxGx+sl/NwA/KjhSSYeAayNiov/zcgPn6IvLJ3gYuKX/9S3AN9eyUptPhVyTAT+moFbXAx8HnomI+f6yz2fmtwvOpPFwGzDXfwL0EvCJwvMUkZlPRMRe4Cmavy57mnPoYwgi4gGgA1wcEUeAu4AvAP8aEbfS/PL7qzXdlx8/IEn18R2qklQh4y5JFTLuklQh4y5JFTLuklQh4y5JFTLuklSh/wXehAbB0wnfigAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim([0,10])\n",
    "plt.ylim([0,10])\n",
    "plt.grid()\n",
    "plt.scatter([2,5,9,4,8,7],[3,4,6,7,1,2],color='b')\n",
    "plt.plot([7,7],[0,10],color='r');\n",
    "plt.plot([0,7],[4,4],color='r');\n",
    "plt.plot([7,10],[6,6],color='r');\n",
    "plt.plot([2,2],[0,4],color='r');\n",
    "plt.plot([4,4],[4,10],color='r');\n",
    "plt.plot([8,8],[0,6],color='r');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 搜索kd树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. 最邻搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "算法：\n",
    "\n",
    "1. __在kd tree中找出包含目标点$\\mathbf{x}$的leaf node__——从current root node出发，向下访问kd tree，若目标点$\\mathbf{x}$当前维度的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点(若只有一个子结点，则移动到该子结点)——直到子结点为叶结点为止；\n",
    "2. __保存该path上的所有node__；\n",
    "3. __以“后进先出”的方式回退检索上述node__:\n",
    "    * if “当前最近点”为空: \n",
    "        * 则该node为“当前最近点”；\n",
    "    * else:\n",
    "        * if 该结点比“当前最近点”更近:\n",
    "            * 替换“当前最近点”；\n",
    "    * if 该结点有2个子结点:\n",
    "        * if 目标点$\\mathbf{x}$到该结点切分超平面的距离小于“当前最近点”:\n",
    "            * 以另一子结点为current root node，递归执行该最邻搜索。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最近点为:(-5.2817175226345565, -3.224172040135075), 距离为:5.572262101870562\n",
      "构建kd树用时: 0.000067秒\n",
      "检索用时: 0.000974秒\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGjpJREFUeJzt3X9w1Ped3/HnWz+QVggsJEAG8UOOTeQ4ts8Exfb10hTVTuW4mYDdpOO0l/om6XCZSzptx2Uuiju5TDOpM6fL3bS9uyZck0l6TqK7STD2JXFJ7FrjpmOcQHEAB2SDfzRI1BiBgBUrJK3e/WNXsOAVK+3ud3e/+309ZjTsfn99Pu+ReOmrz/e7n6+5OyIiUv1qyt0BEREpDQW+iEhEKPBFRCJCgS8iEhEKfBGRiFDgi4hEhAJfRCQiFPgiIhGhwBcRiYi6cncg0/Lly72zszOvfcfHx1m8eHFxO1RBVF+4qb5wq/T69u3bd8rdV+TarqICv7Ozk7179+a17+DgIJs3by5uhyqI6gs31RdulV6fmb05n+00pCMiEhEKfBGRiFDgi4hERFEC38y+ZWYnzexQxrIvmdmwmb2U/rq/GG2JiEh+inWG/23gvizL/8zd70h//aRIbYmISB6KcpeOuz9vZp3FOJaISD527R+mf/cQI2MJVrfE2N7bxdaNHeXuVkWxYj3xKh34P3L3W9PvvwT8HnAO2As84u5nsuy3DdgG0N7evmlgYCCv9uPxOM3NzXntGwaqL9xUX7DGElMMn0kwk5FnNWZ0LIvREqsv+Pjlri+Xnp6efe7enWu7IAO/HTgFOPBlYJW7f+pax+ju7nbdh5+d6gs31Res3/nq/2R4LPGO5R0tMf735/9hwccvd325mNm8Aj+wu3Tc/S13T7r7DPBXwJ1BtSUi0TaSJeyvtTyqAgt8M1uV8fYB4NBc24qIFGJ1S2xBy6OqWLdlfh94Aegys+Nm9mngj83soJkdAHqAf1uMtkRErra9t4tYfe0Vy2L1tWzv7SpTjypTse7S+USWxd8sxrFFRHKZvRtHd+lcW0VNniYikq+tGzsU8DloagURkYhQ4IuIRIQCX0QkIhT4IiIRocAXEYkIBb6ISEQo8EVEIkKBLyISEQp8EZGIUOCLiESEAl9EJCI0l46IXJMeHVg9FPgiMqdd+4fp23mQxFQSgOGxBH07DwIo9ENIQzoiMqf+3UOXwn5WYipJ/+6hMvVICqHAF5E56dGB1UWBLyJz0qMDq4sCX0TmpEcHVhddtBWROenRgdWlKIFvZt8CPgKcdPdb08tagb8BOoE3gH/q7meK0Z6IlI4eHVg9ijWk823gvquWfR541t03AM+m34uISJkUJfDd/Xng9FWLtwDfSb/+DrC1GG2JiEh+zN2LcyCzTuBHGUM6Y+7ekrH+jLsvy7LfNmAbQHt7+6aBgYG82o/H4zQ3N+e1bxiovnBTfeFW6fX19PTsc/fuXNuV/aKtu+8AdgB0d3f75s2b8zrO4OAg+e4bBqov3FRfuFVLfUHelvmWma0CSP97MsC2REQkhyAD/yng4fTrh4EnA2xLRERyKErgm9n3gReALjM7bmafBr4KfMjMXgU+lH4vIiJlUpQxfHf/xByr7inG8UVEpHCaWkFEJCIU+CIiEaHAFxGJCAW+iEhEKPBFRCJCgS8iEhEKfBGRiFDgi4hEhAJfRCQiFPgiIhGhwBcRiQgFvohIRCjwRUQiQoEvIhIRCnwRkYgo+zNtRcJg1/5h+ncPMTKWYHVLjO29XWzd2FHuboksiAJfJIdd+4fp23mQxFQSgOGxBH07DwIo9CVUNKQjkkP/7qFLYT8rMZWkf/dQmXokkh8FvkgOI2OJBS0XqVSBD+mY2RvAeSAJTLt7d9BtihTT6pYYw1nCfXVLrAy9Eclfqc7we9z9DoW9hNH23i5i9bVXLIvV17K9t6tMPRLJjy7aiuQwe2FWd+lI2Jm7B9uA2evAGcCBb7j7jqvWbwO2AbS3t28aGBjIq514PE5zc3OBva1cqi/cVF+4VXp9PT09++Y1guLugX4Bq9P/rgR+BXxwrm03bdrk+Xruuefy3jcMVF+4qb5wq/T6gL0+jzwOfAzf3UfS/54EngDuDLpNERF5p0AD38wWm9mS2dfAPwIOBdmmiIhkF/RF23bgCTObbet77v4/Am5TRESyCDTw3f014LeCbENEROZHn7QVEYkIBb6ISEQo8EVEIkKBLyISEQp8EZGIUOCLiESEAl9EJCIU+CIiEaHAFxGJCAW+iEhEKPBFRCJCgS8iEhEKfBGRiFDgi4hEhAJfRCQiFPgiIhGhwBcRiYigH3EoIkWwa/8w/buHGBlLsLolxvbeLrZu7Ch3tyRkFPgiFW7X/mH6dh4kMZUEYHgsQd/OgwAKfVmQwAPfzO4D/hNQC/w3d/9q0G2KlMNUcoYz45OMjk9yZnyScxNTTM84yRnHE1M89asR6mqM+toaWprqaV28iLbFi1jaWE9Njc153P7dQ5fCflZiKkn/7iEFvixIoIFvZrXAXwAfAo4DvzSzp9z910G2K1IK7s7I2QnePDXO6Pgk5yem59y2cca5kLH+7fMXL72urYGWpkWsWNLAjSuauS5Wf8W+I2OJrMeca7nIXII+w78TOOrurwGY2QCwBVDgS2hNTCU59nacoyfjjF9M5t4hh+QMjMYnGY1PcuTEedqXNrBh5RLWLItRU2OsbokxnCXcV7fECm5bosXcPbiDm30MuM/d/2X6/SeBu9z9cxnbbAO2AbS3t28aGBjIq614PE5zc3Phna5Qqq/8kjPOxFSSyeQMC/1vUzM9wUxd48L2qTEa6mqYmJphZCzBTEajNWZ0LIvRctVfA+UShu9fISq9vp6enn3u3p1ru6DP8LMNTF7xX8XddwA7ALq7u33z5s15NTQ4OEi++4aB6iuf5IxzcPgsh0+cW3DQz2o8dYSJ5TcveL8LQGxRDbGlU3zz569X7F06lfz9K4ZqqS/owD8OrM14vwYYCbhNkaIZjV9kz2unOZuYKlsfEpMzNNbX0v+x29nUuYyGutqy9UXCLejA/yWwwcxuAIaBh4B/FnCbIgUrxll9sb0xeoG3zk/w/s5W1ixrKnd3JIQCDXx3nzazzwG7Sd2W+S13fznINkUKNTGVZHDoJKfHy3dWP5fE5AzPv3KKm1ct4X3rlpW7OxIygd+H7+4/AX4SdDsixTB+cZrnhk5yLjH3LZaV4MiJ80xNz3DnDa2YzX0Pv0gmzaUjkjZ+cZpnDr9V8WE/69jb47xwbJQg77ST6qKpFURIDeM8N3SyKPfVl9Iboxeor6vh/Z2t5e5KRdNcRCkKfIm85IwzGIJhnLm8+lacxrpabltzXbm7UpE0F9FlGtKRyDtwfKwiL9AuxKGRs5yKX8y9YQRday6iqFHgS6Sdil/kyP87X+5uFMwd9rw2SnJG4/lX01xElynwJbKSM86e10Yr5j77Qp1LTHNw+Gy5u1Fx5ppzKIpzESnwJbIOHB8L7bj9XA6fOKehnats7+0iVn/lp5Nj9bVs7+0qU4/KR4Ev0XDsGPzBH8DSpVBTw+mVHRz52tfh7bfL3bOimh3a0a2al23d2MFjD95GR0sMAzpaYjz24G2Ru2ALuktHouDpp+FjH4OpqdQXcCS2HP/5z+GFF+D3PwO33lrmThbPucQ0x88kWNuq6Rdmbd3YEcmAv5rO8KW6HTuWCvsLFy6F/URtPf+35XpIJmFyEr5RfWf6R0/Gy90FqUAKfKluX/vapaCfdaxtDTOZ0xEkk/DMMyXuWLBOnJ3g/ES4bzWV4lPgS3V7/PErAt+Bo23rrtwmmYQ9e0rbrxJ4VWf5chUFvlS3+JWhN7x0BeOLsjx56mL13dny2tvjTCdnyt0NqSC6aCslVfI5TZqb4fzlD1a9uWx19u0aGoLrQ5lMTs9w4uyELt7KJTrDl5KZndNkeCyBc3lOk137h4Nr9Hd/F+ovP/d1tCnLfDO1tXD33cH1oYxGxyfL3QWpIAp8KZmyzGnyyCOXAn+ypo74oiyfrqythXvvDa4PZXRGgS8ZFPhSMmWZ0+TGG+EHP4CmJs4svWoK4dpaWLQodR/+ihXB9aGMdIYvmRT4UjJlm9Pkwx+GAwcY/eSnoDEGVpP69+9/EL74R1X1oaurTU7PEL9YXdNHSP500VZKZntv1xXzkkPGnCZnXw228Rtv5PS/egROXwi2nQp0ZnyS5gb9V5cAz/DN7EtmNmxmL6W/7g+qLQmHcs9pUo4PIr04/CJfeLaPN8++yRee7ePF4RdL3oezCX0AS1KC/rX/Z+7+JwG3ISFSzjlNpks8V/yLwy/y+IG/ZjKZGkcfTYzy+IG/BuCujrtK1g/NkS+zNIYvkVHq4HvyyK5LYT9rMjnJk0d2lbQfSc2cKWkW1DSqZvYl4PeAc8Be4BF3P5Nlu23ANoD29vZNAwMDebUXj8dpbm7Ot7sVT/UVbiwxxUwJQ//Ns29eet3RuIzhics//uuvW1+yfjTW19K0qDb3hgXQz2d59fT07HP37lzbFRT4ZvYMcH2WVY8Ce4BTpKYv+TKwyt0/da3jdXd3+969e/Pqy+DgIJs3b85r3zBQfYV78qVhxi8mc29YJF94to/RxCgA/+E9/4QvHv4hAG2xNv7jPY+VrB83r1rC+9YtC7QN/XyWl5nNK/ALGsN393l9WsXM/gr4USFtiRSqtsZyb1REW27eesUYPsCi2kVsuXlrSftRV+K6pXIFdtHWzFa5+4n02weAQ0G1JTIf9bWlvWQ1e2F2dsy+LdbGlpu3lvSCLZS+bqlcQd6l88dmdgepIZ03gN8PsC2RnJY1LWI0XtpPnt7VcRd3ddxF46kjJR3GybSsaVFZ2pXKE1jgu/sngzq2SD5aF9fn3qgKLYto3fJO+ltPIqN1cfVNgZzL4oZaGuqCvUNHwkOBL5HREqsnatcv2yL4S07mpsCXyKipMVqaojW8oeEcyaTAl0hZsSRaZ7xRq1euTYEvkXLjisr9tGSxLY3VsXJJluf3SmQp8CVSWpoWReasd8PKJeXuglQYBb5EzoaV1X+WX1dj3LB8cbm7IRVGgS+Rs661icb66v7RX9/WxKK66q5RFk4/ERI5NTXGu6p8LP/d7RrOkXdS4Esk3Xz9Ehqq9Ax4XWsTyxZrOgV5p+r8iRfJobG+lvd3tpa7G0XXUFdDd2ewUyFLeCnwJbLWtTWxrrWp3N0oqvd3ttJYr6kUJDsFvkRad+eyqhnaWdfaxLq26voFJsUV9EPMRQKxa/8w/buHGBlLsLolxvberrwejj47tPPzo6cC6GXpaChH5qM6Tm0kUnbtH6Zv50GGxxI4MDyWoG/nQXbtH87reOvamnh3e3jv2qkx+Hs3tWkoR3JS4Evo9O8eIjF15bNpE1NJ+ncP5X3M7s5WOkM4HGIGv3PTclZdFyt3VyQEFPgSOiNjiQUtn6+739XG2tbwBKcZ3HVDK2ur7MKzBEeBL6GzuiV7KM+1fL5qaowP3LQ8FFMS1Bh84KblVf8BMikuBb6EzvbeLmJXjVfH6mvZ3ttV8LHNjN++sY1bVi/FKvRhKQ11NfyDrhU6s5cFKyjwzezjZvaymc2YWfdV6/rM7KiZDZlZb2HdFLls68YOHnvwNjpaYhjQ0RLjsQdvy+sunbncsbaFe96zkubGyrqRbW1rjH98+yqN2UteCv1pPgQ8CHwjc6GZ3QI8BLwXWA08Y2bvdvfkOw8hsnBbN3YUNeCzWbmkkftvvZ5fHT/LK2+dxz3Q5q5p9rbL9W2VP9wklaugwHf3w5D6M/gqW4ABd78IvG5mR4E7gRcKaU+k1Opqa9i0fhlrW2Psee008YnpkvdhbWtMn6CVogjq79UOYE/G++PpZe9gZtuAbQDt7e0MDg7m1WA8Hs973zBQfeW3FGhMznBxaoap5MyC9q2ZnqDx1JF5b29mLKqrobGuhmTC2JPfRwxKJgzfv0JUS305A9/MngGuz7LqUXd/cq7dsizL+gexu+8AdgB0d3f75s2bc3Upq8HBQfLdNwxUX2U5e2GKV0+e5/VT40wlc4/1NJ46wsTym3Nut6Sxjg3tzbxreXOo5rMP2/dvoaqlvpyB7+735nHc48DajPdrgJE8jiNSka5rqqe7s5XfWtvCyFiC0fFJzoxPcnp8cl6/AGYtbqildfEiljUtYuWSBlYu1TNoJThBDek8BXzPzP6U1EXbDcAvAmqrYhVrvhepXPW1NaxvW3zFxdRzE1OcGZ/kXGKa6ZkZZtx562wt669fQm2NUV9rl0Je4/JSSgUFvpk9APwXYAXwYzN7yd173f1lM/tb4NfANPDZqN2hMzvfy+wUALPzvQAK/Sq3tLGepY31VywbfL2WTes1uZmUV0GDhO7+hLuvcfcGd293996MdV9x9xvdvcvdny68q+ESxHwvIiKFCM9VoZAJar4XEZF8KfADEtR8LyIi+VLgByTI+V5ERPJRWROFVJHZC7O6S0dEKoUCP0ClmO9FRGS+NKQjIhIRCnwRkYhQ4IuIRIQCX0QkIhT4IiIRocAXEYkIBb6ISEQo8EVEIkKBLyISEQp8EZGIUOCLiESEAl9EJCIU+CIiEaHAFxGJiIIC38w+bmYvm9mMmXVnLO80s4SZvZT++nrhXRURkUIUOh/+IeBB4BtZ1h1z9zsKPL6IiBRJQYHv7ocBzKw4vRERkcCYuxd+ELNB4N+5+970+07gZeAV4Bzw7939f82x7zZgG0B7e/umgYGBvPoQj8dpbm7Oa98wUH3hpvrCrdLr6+np2efu3Tk3dPdrfgHPkBq6ufprS8Y2g0B3xvsGoC39ehPwG2BprrY2bdrk+Xruuefy3jcMVF+4qb5wq/T6gL2eI1/dPfeQjrvfu9DfNu5+EbiYfr3PzI4B7wb2LvRYIiJSHIHclmlmK8ysNv36XcAG4LUg2hIRkfkp9LbMB8zsOPDbwI/NbHd61QeBA2b2K+AHwGfc/XRhXRURkUIUepfOE8ATWZb/EPhhIccWEZHi0idtRUQiQoEvIhIRCnwRkYhQ4IuIRIQCX0QkIhT4IiIRocAXEYkIBb6ISEQo8EVEIkKBLyISEQp8EZGIUOCLiESEAl9EJCIU+CIiEaHAFxGJCAW+iEhEKPBFRCJCgS8iEhEKfBGRiCj0Ieb9ZnbEzA6Y2RNm1pKxrs/MjprZkJn1Ft5VEREpRKFn+D8DbnX324FXgD4AM7sFeAh4L3Af8JdmVltgWyIiUoCCAt/df+ru0+m3e4A16ddbgAF3v+jurwNHgTsLaUtERApj7l6cA5n9HfA37v64mf05sMfdH0+v+ybwtLv/IMt+24BtAO3t7ZsGBgbyaj8ej9Pc3Jx3/yud6gs31RdulV5fT0/PPnfvzrVdXa4NzOwZ4Posqx519yfT2zwKTAPfnd0ty/ZZf7O4+w5gB0B3d7dv3rw5V5eyGhwcJN99w0D1Lcyu/cP07x5iZCzB6pYY23u72Lqxo2jHXyh9/8KtWurLGfjufu+11pvZw8BHgHv88p8Lx4G1GZutAUby7aTIQuzaP0zfzoMkppIADI8l6Nt5EKCsoS9SboXepXMf8IfAR939Qsaqp4CHzKzBzG4ANgC/KKQtkfnq3z10KexnJaaS9O8eKlOPRCpDzjP8HP4caAB+ZmaQGrf/jLu/bGZ/C/ya1FDPZ909eY3jiBTNyFhiQctFoqKgwHf3m66x7ivAVwo5vkg+VrfEGM4S7qtbYmXojUjl0Cdtpeps7+0iVn/lxz5i9bVs7+0qU49EKkOhQzoiFWf2wmwl3aUjUgkU+FKVtm7sUMCLXEVDOiIiEaHAFxGJCAW+iEhEKPBFRCJCgS8iEhFFmy2zGMzsbeDNPHdfDpwqYncqjeoLN9UXbpVe33p3X5Fro4oK/EKY2d75TA8aVqov3FRfuFVLfRrSERGJCAW+iEhEVFPg7yh3BwKm+sJN9YVbVdRXNWP4IiJybdV0hi8iItcQ+sA3sy+b2QEze8nMfmpmq9PLzcz+s5kdTa9/X7n7mg8z6zezI+kanjCzlox1fen6hsyst5z9zJeZfdzMXjazGTPrvmpd6OuD1JPh0jUcNbPPl7s/hTKzb5nZSTM7lLGs1cx+Zmavpv9dVs4+FsLM1prZc2Z2OP2z+a/Ty0NfY+gDH+h399vd/Q7gR8AX08s/TOrRihuAbcB/LVP/CvUz4FZ3vx14BegDMLNbgIeA9wL3AX9pZrVzHqVyHQIeBJ7PXFgt9aX7/Bekfh5vAT6Rri3Mvk3qe5Lp88Cz7r4BeDb9PqymgUfc/T3A3cBn09+z0NcY+sB393MZbxcDsxcltgD/3VP2AC1mtqrkHSyQu//U3afTb/eQeiA8pOobcPeL7v46cBS4sxx9LIS7H3b3bA+brYr6SPX5qLu/5u6TwACp2kLL3Z8HTl+1eAvwnfTr7wBbS9qpInL3E+7+f9KvzwOHgQ6qoMbQBz6AmX3FzH4D/HMun+F3AL/J2Ox4elmYfQp4Ov26GuvLVC31VUsdubS7+wlIBSawssz9KQoz6wQ2Ai9SBTWG4gEoZvYMcH2WVY+6+5Pu/ijwqJn1AZ8D/giwLNtX5C1JuepLb/MoqT81vzu7W5btQ1tftt2yLKvI+nKoljoix8yagR8C/8bdz5ll+1aGSygC393vneem3wN+TCrwjwNrM9atAUaK3LWiyFWfmT0MfAS4xy/fR1s19c0hNPXlUC115PKWma1y9xPpodOT5e5QIcysnlTYf9fdd6YXh77G0A/pmNmGjLcfBY6kXz8F/Iv03Tp3A2dn/xwLEzO7D/hD4KPufiFj1VPAQ2bWYGY3kLo4/Yty9DEg1VLfL4ENZnaDmS0idSH6qTL3KQhPAQ+nXz8MzPWXW8Wz1Kn8N4HD7v6nGavCX6O7h/qL1G/hQ8AB4O+AjvRyI3V3xDHgINBd7r7mWd9RUmPAL6W/vp6x7tF0fUPAh8vd1zzre4DUWfBF4C1gdzXVl67jflJ3WB0jNYxV9j4VWM/3gRPAVPp792mgjdSdK6+m/20tdz8LqO8DpIbdDmT8v7u/GmrUJ21FRCIi9EM6IiIyPwp8EZGIUOCLiESEAl9EJCIU+CIiEaHAFxGJCAW+iEhEKPBFRCLi/wMXIP+imXejwwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from matplotlib.patches import Circle\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import copy\n",
    "import time\n",
    "\n",
    "class Node:\n",
    "    \"\"\"二叉树结点\n",
    "    Parameters\n",
    "    --------------\n",
    "    left: Node\n",
    "        左子结点\n",
    "    right: Node\n",
    "        右子结点\n",
    "    point: tuple\n",
    "        该结点存储的切分点\n",
    "    dim: int\n",
    "        该结点的切分维度，是索引，因此真正的维度应该是dim+1\n",
    "    \"\"\"\n",
    "    def __init__(self, left, right, point, dim):\n",
    "        self.left  = left\n",
    "        self.right = right\n",
    "        self.point = point\n",
    "        self.dim   = dim\n",
    "\n",
    "    def get_child_num(self):\n",
    "        \"\"\"返回该结点的子结点数目\n",
    "        Return\n",
    "        --------------\n",
    "        : int, 0 or 1 or 2      \n",
    "            子结点数目\n",
    "        \"\"\"\n",
    "        return int(self.right != None) + int(self.left != None)\n",
    "\n",
    "class KdTree:\n",
    "    \"\"\"kd树\n",
    "    Parameters\n",
    "    --------------\n",
    "    training_data: list of tuple\n",
    "        训练样本数据点\n",
    "    \n",
    "    Attributes\n",
    "    --------------\n",
    "    dim_: int\n",
    "        样本维度\n",
    "    kdtree_: Node\n",
    "        kd树(根节点表示)\n",
    "    nearest_: list of Node\n",
    "        存储当前最邻点\n",
    "    min_dist_: float\n",
    "        与当前最邻点的距离\n",
    "    \"\"\"\n",
    "    def __init__(self, training_data):\n",
    "        self.training_data = training_data\n",
    "        self.dim_ = len(training_data[0])\n",
    "        self.kdtree_ = None\n",
    "        self.nearest_  = [-999]                              # 储存\"当前最近\"点(Node)\n",
    "        self.min_dist_ = float('inf')                        # 储存\"当前最近\"点与目标的距离\n",
    "\n",
    "    def create_tree(self):\n",
    "        \"\"\"构造kd树\"\"\"\n",
    "        kdtree = self.create_tree_real(self.training_data)\n",
    "        self.kdtree_ = kdtree\n",
    "\n",
    "    def create_tree_real(self, point_list, depth=0):\n",
    "        \"\"\"实际构造kd树函数\n",
    "        Parameters\n",
    "        --------------\n",
    "        point_list: list by tuples\n",
    "            训练数据点(或其一部分)\n",
    "        depth: int\n",
    "            结点深度，默认是0，即root位置\n",
    "\n",
    "        Returns\n",
    "        --------------\n",
    "        Node: Node\n",
    "            kd树(以根节点表示)\n",
    "        \"\"\"\n",
    "        if not point_list:  # 递归的base criteria\n",
    "            return None\n",
    "        dim_index = depth%self.dim_\n",
    "        point_list = sorted(point_list, key=lambda x:x[dim_index])\n",
    "        median_index = len(point_list)//2\n",
    "        return Node(\n",
    "                point  = point_list[median_index],\n",
    "                left  = self.create_tree_real(point_list[:median_index], depth+1),\n",
    "                right = self.create_tree_real(point_list[median_index+1:], depth+1),\n",
    "                dim = dim_index\n",
    "        )\n",
    "\n",
    "    def compute_distance(self, p1, p2):\n",
    "        \"\"\"计算两点间的欧氏距离\n",
    "        Parameters\n",
    "        --------------\n",
    "        p1: tuple\n",
    "            点1\n",
    "        p2: tuple\n",
    "            点2\n",
    "\n",
    "        Returns\n",
    "        --------------\n",
    "        distance: float\n",
    "            两点的欧氏距离\n",
    "        \"\"\"\n",
    "        p1 = np.array(p1)\n",
    "        p2 = np.array(p2)\n",
    "        distance = np.sqrt(np.sum((p1-p2)*(p1-p2)))\n",
    "        return distance\n",
    "\n",
    "    def find_nearest_one(self, query_point):\n",
    "        \"\"\"寻找最近点\"\"\"\n",
    "        if not self.kdtree_:\n",
    "            print(\"Attention: 请先构建kd树!\")\n",
    "            return None\n",
    "        self.find_nearest_one_real(self.kdtree_, query_point)\n",
    "        print(\"最近点为:%s, 距离为:%s\" % (str(self.nearest_[0].point), str(self.min_dist_)))\n",
    "        return self.nearest_[0].point, self.min_dist_\n",
    "\n",
    "    def find_nearest_one_real(self, root, query_point):\n",
    "        \"\"\"实际检索函数\n",
    "        Parameters\n",
    "        --------------\n",
    "        query_point: tuple\n",
    "            目标数据点\n",
    "\n",
    "        Returns\n",
    "        --------------\n",
    "        nearest_[0]: Node\n",
    "            最近点\n",
    "        min_dist_: float\n",
    "            最近点对应的最近距离\n",
    "        \"\"\"\n",
    "        node_list = []                                                              # 储存待检查的结点\n",
    "        cursor_node = root                                                          # 不需要deepcopy\n",
    "        while cursor_node:                                                          # 二叉检索，获得子结点，并将路径结点保存\n",
    "            node_list.append(cursor_node)\n",
    "            if cursor_node.get_child_num() == 1:                                    # 如果下面只剩一个结点，无论是左是右，都走下去\n",
    "                cursor_node = cursor_node.left if cursor_node.left else cursor_node.right\n",
    "            else:\n",
    "                dim = cursor_node.dim\n",
    "                if query_point[dim] < cursor_node.point[dim]:\n",
    "                    cursor_node = cursor_node.left\n",
    "                else:\n",
    "                    cursor_node = cursor_node.right\n",
    "        while node_list:                                                            # 回退检索\n",
    "            back_point = node_list.pop()\n",
    "            btq_dist = self.compute_distance(back_point.point, query_point)\n",
    "            if btq_dist < self.min_dist_:\n",
    "                self.nearest_[0] = back_point\n",
    "                self.min_dist_ = btq_dist\n",
    "            dim = back_point.dim\n",
    "            if back_point.get_child_num() == 2:                                     # 确定有左右两个子结点，有一个或没有都不用进行以下步骤\n",
    "                if abs(query_point[dim] - back_point.point[dim]) < self.min_dist_:\n",
    "                    if query_point[dim] < back_point.point[dim]:                    # 以当前最近点与目标点连线为半径的圆与同父兄弟的矩形空间相交，因此需要检查同父兄弟的矩形空间\n",
    "                        cursor_node = back_point.right\n",
    "                        self.find_nearest_one_real(cursor_node,query_point)\n",
    "                    else:\n",
    "                        cursor_node = back_point.left\n",
    "                        self.find_nearest_one_real(cursor_node,query_point)\n",
    "\n",
    "def draw_pic(X,query_point,min_dist_):\n",
    "    fig = plt.figure()\n",
    "    ax = fig.add_subplot(111)\n",
    "    plt.scatter([i[0] for i in X], [i[1] for i in X])\n",
    "    plt.scatter(nearest_point[0],nearest_point[1],s=100,c='r')\n",
    "    plt.scatter(query_point[0],query_point[1],c='g')\n",
    "    plt.grid()\n",
    "    cir = Circle(xy=query_point, radius=min_dist_, alpha=0.4)\n",
    "    ax.add_patch(cir)\n",
    "    plt.axis('scaled')\n",
    "    plt.axis('equal')\n",
    "    plt.show()\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # 数据生成\n",
    "    n = 10\n",
    "    np.random.seed(1)\n",
    "    temp = np.random.randn(2*n)*10\n",
    "    X = temp[:n]\n",
    "    Y = temp[n:]\n",
    "    input_ = list(zip(X,Y))\n",
    "    query_point = (0,-5)\n",
    "\n",
    "    # 构建kd树并搜寻\n",
    "    time1 = time.time()\n",
    "    kt = KdTree(input_)\n",
    "    kt.create_tree()\n",
    "    time2 = time.time()\n",
    "    nearest_point,min_dist_ = kt.find_nearest_one(query_point)\n",
    "    time3 = time.time()\n",
    "    print(\"构建kd树用时: %f秒\" % (time2-time1))\n",
    "    print(\"检索用时: %f秒\" % (time3-time2))\n",
    "    draw_pic(input_,query_point,min_dist_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. k邻搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "算法：\n",
    "\n",
    "1. __在kd tree中找出包含目标点$\\mathbf{x}$的leaf node__——从current root node出发，向下访问kd tree，若目标点$\\mathbf{x}$当前维度的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点(若只有一个子结点，则移动到该子结点)——直到子结点为叶结点为止；\n",
    "2. __保存该path上的所有node__；\n",
    "3. __以“后进先出”的方式回退检索上述node__:\n",
    "    * if “当前k近邻点”数目小于$k$: \n",
    "        * 则将该node添加至“当前k近邻点”；\n",
    "    * else:\n",
    "        * if 该结点比“当前k近邻点”中最远的点更近:\n",
    "            * 替换“当前k近邻点”中最远的点；\n",
    "    * if 该结点有2个子结点:\n",
    "        * if 目标点$\\mathbf{x}$到该结点切分超平面的距离小于“当前k近邻点”中最远的点:\n",
    "            * 以另一子结点为current root node，递归执行该k邻搜索。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k=5最近点为:[(3.1903909605709857, 0.4221374671559283), (-7.612069008951028, -8.778584179213718), (-5.2817175226345565, -3.224172040135075), (-10.729686221561705, -3.8405435466841564), (-2.493703754774101, 5.828152137158222)], 距离为:[6.291118278496214, 8.498311184961215, 5.572262101870562, 10.792150187998073, 11.111590215717039]\n",
      "构建kd树用时: 0.000085秒\n",
      "检索用时: 0.000923秒\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XuQZOd53/fvc259ncteZxcLEuAFRAxSJEBuMQrJcu1GohZgFBFkUS4ysU2XnMAuSY6SUlAigiRWWWHRFYRWYlmKjaJZUooS1i6LN4uEIJLOhiYkSsKKIAGSWhAgCXIv2MViZ2em7+fy5I/TMzuXnp3p093Tt+dTtbUzp7vPZXrmd95+znveV1QVY4wxk88Z9g4YY4zZGxb4xhgzJSzwjTFmSljgG2PMlLDAN8aYKWGBb4wxU8IC3xhjpoQFvjHGTAkLfGOMmRLesHdgvYMHD+rtt9/e83qq1SqlUqn3HRpBdmzjyY5tPI3LsZ09e/aqqh7a6XkjFfi33347Tz31VM/rOXPmDCdOnOh9h0aQHdt4smMbT+NybCLy4m6eZyUdY4yZEhb4xhgzJSzwjTFmSljgG2PMlOhL4IvIJ0Xkiog8u27Zr4vIBRF5uv3vPf3YljHGmGz61cL/XeDeDst/U1Xvbv/7Yp+2ZYwxJoO+BL6qfhW41o91GWOMGYxB98P/ZRH5u8BTwK+q6uKAt2eMmUKf/cYFHnniHBev17llvsCDp+7k/nuODXu3Ro70a05bEbkd+CNVfVP7+wXgKqDAbwBHVfUXOrzuAeABgIWFhbedPn26532pVCqUy+We1zOK7NjGkx3b4Fyvh1xYrJOsyzJHhGP7CswX/J7WPexj262TJ0+eVdXjOz1vYIG/28fWO378uNqdtjdnxzae7NgG553/9D9w4Xp9y/Jj8wWe/Mh/3tO6h31suyUiuwr8gXXLFJGj6759H/Dsds81xpisLnYI+5stn2Z9qeGLyGPACeCgiJwH/jFwQkTuJi3p/BD4B/3YljHGrHfLfKFjC/+W+cIQ9ma09SXwVfVDHRb/636s2xhjbubBU3fy0KefoR7Ga8sKvsuDp+4c4l6NppEaLdMYY7q12hvHeunszALfGDP27r/nmAX8LthYOsYYMyUs8I0xZkpY4BtjzJSwwDfGmClhgW+MMVPCAt8YY6aEBb4xxkwJC3xjjJkSFvjGGDMlLPCNMWZK2NAKxpht2UxSk8UC3xjT0We/cWHDKJQXrtd56NPPAFjojykr6RhjOnrkiXMbhhwGqIcxjzxxbkh7ZHplgW+M6chmkpo8FvjGmI62mzHKZpIaXxb4xpiOHjx1JwXf3bDMZpIab3bR1hjTkc0kNXn6NYn5J4GfBa6o6pvay/YD/wa4nXQS87+lqov92J4xZm/YTFKTpV8lnd8F7t207CPAV1T1DuAr7e+NMcYMSV8CX1W/ClzbtPi9wO+1v/494P5+bMsYY0w2g7xou6CqlwDa/x8e4LaMMcbsQFS1PysSuR34o3U1/OuqOr/u8UVV3dfhdQ8ADwAsLCy87fTp0z3vS6VSoVwu97yeUWTHNp7s2MbTuBzbyZMnz6rq8Z2eN8heOpdF5KiqXhKRo8CVTk9S1UeBRwGOHz+uJ06c6HnDZ86coR/rGUV2bOPJjm08TdqxDbKk83ngw+2vPwx8boDbMsYYs4O+BL6IPAb8GXCniJwXkb8P/FPg3SLyPeDd7e+NMcYMSV9KOqr6oW0e+ql+rN8YY0zvbGgFY4yZEhb4xhgzJSzwjTFmSljgG2PMlLDAN8aYKWGBb4wxU8IC3xhjpoQFvjHGTAkLfGOMmRIW+MYYMyUs8I0xZkpY4BtjzJSwwDfGmClhgW/MTl54AX7xF2F2Fhwn/f8XfzFdbswYscA35mYefxze/Gb4xCdgZQVU0/8/8Yl0+eOPD3sPjdk1C3xjtvPCC/CBD0CtBmG48bEwTJd/4AM3bemrKkmia18bM0yDnNPWmPH28Y9vDfp1QselLj7N//O3if63jxLFShgnREn6f5LceG49jHn2wjKQVoV818FzJP3fFTzHIfAcCr5L4Fk7zAyGBb4x2/nUp9YCPxaHqp+n4eeo+zlqfp7IcdPnffE/wK+11l4WJ2noJ6ooaRUoUaiFEQI4IoROgus4QLxls64jFAKXYuCS911KgYvn2knA9G7ggS8iPwRWSH+zI1U9PuhtGtMPrVqD5eIcK7kS1aDA+oJM5Lg0XZ+GnyN0fcLFGnGSECdpwG8mUcLFxcbGZQKuA66TtvYD1yHnu+Q8hzhRKo1o7XmFwGU27zNb8Mh57gCP2kyyvWrhn1TVq3u0LWMya0UJ12stluohjdv+BlSrADTdgGqQp+EFNL2A2FnX4s4XIUy2WeP2VCGKIYoTmkCVGEg/UTgO5DyXvO9QyrmoQq0Z89IS5HyH2bzPfNEn71v4m92zko4xwEoj5Fq1xUojQhUUpXbff0n1S1+mJj6Ru02wuh686519358kgXorpt6KWayGuA4Ucx6lwCNRl2aY8PJKk3LeY38pYDbvISJ93w8zWfYi8BX4ExFR4F+p6qN7sE1jdhQnyrVqi2vVFq0obaE3o5jrtZBKK0J/9v3w5F9Cq7n9SlwX7rtvD/YVVuoRK/UIESgFHrPF9M+30ojwPWF/MWB/KbB6v9mWDLqrmIjcoqoXReQw8CXgH6nqV9c9/gDwAMDCwsLbTp8+3fM2K5UK5XK55/WMIju2/ogSJYoVbVfmk0SJEyXZ/OdQr8GVK7Sb/TcIaXH98GEoFHexwQZ4+X7t/o3dkPQir+vI2m557R5Ae8V+J4fv5MmTZ3dzfXTggb9hYyK/DlRU9f/o9Pjx48f1qaee6nk7Z86c4cSJEz2vZxTZsWWnqizWQq6sNAgjJVZdq9cnNyvBX7mc3mD1tSeh2YBcPi3j3HcfHF7Y1bblpe+gR+7qz4F0Wr/AbMFjXzHAcxxcRzg8m+NAKRh4qcd+J4dPRHYV+AMt6YhICXBUdaX99c8A/2SQ2zSmk+VGyEtLDZphQqLKUj1ksda6edCvOrwAH/576b8RpQpLtYjlesR80We+GHDpeoOrlSZHZvPMF4Nh76IZAYOu4S8An2m3MDzgD1T1jwe8TWPWxIly8Xqd67UQRVluRCxWm0Rbu79PBFVYrIYs1UP2FQPmiz4/vpYe/7F9BXyr70+1gQa+qn4feMsgt2HMdpYbIRcW60Sx0oxiLi83aEXTMbxBksArlRbL9ZBDszkAnru8wi1zBfaVrLU/raxbppk4m1v11yotrtfDjjdETbowVi4uNpgtehws5Ti/WGepbq39aWWBbyZKI4x58ZUarSiZulb9zSzXImrNiMOzaU+h712ucNuBIqWcRcA0sVO8mRhL9ZDnr1RoRQnXqk3OL9Yt7NeJYri42ODlSoMoSfjB1SrXqq2dX2gmhp3ezUS4stzg8nKTRJUry00qzWhPt5+oEiUJcaLECnGcEKuulZHmE+V6tZn2mxfBdR3ctT70Du4e3iW7VItoRQlHZvNcWKzTCGOOzuXtTt0pYIFvxlqS6FpdOowTXlqu0wwH36pvxhGtSGlFSTokcqw3vUYwq0qtuX3XIM8VAs/Bdx1ynhB4LsLgArjeSji/WOfIXJ5XKi0aYcxtB0prN3CZyWSBb8ZWkig/fKVKtRlTDyMuLTV2168+y7ZUaYQx9Sim0Yr7vp0oVqI4ZnW4ZMeBvO9S8F1yvjuQTwBhrJy/XmdhJq3r/+BqhdsPlGxohglmgW/GUtwO+1ozptKMuLzcGEgvnFYcs9KMqDfjPe3lkyTp6Ji1Zrw2PHI555Lz+vsnqwm8tNTg0EwABPzgapXbD5asB8+EssA3YydZH/aNiMsr/Q17Ram10nWvDqo2TKtDI9eaMb4XUs55FAMPp4+t/pdXWigw3w791x60lv4kssA3Y2V92K80Qq6sNPsa9tVWxHI9JIpHs3dPGCmLUXon7VzBp5Tz+lbrv7qS9thZC/1DZavpTxgLfDNWfrxYo9ou4/Qz7OthlF74HZNunEmSDqGw0oiYLfiUgv78KV9dabVPHwE/fCVt6VvvnclhgW/GxuXlBsv1iFrYv5p9nCQs1lrUW8Mv3WQRxemdxFU/Yl/Jx3d6nwHr5ZUWrqTlnAvX69y6bxfDP5uxYEU6MxaWaiFXlpu04piXlvoT9tVWxEvLjbEN+/WaYcLlpSaVZtiX9V1eadCM0tm2rlZuMgGMGSsW+GbkNcKYHy/WSFR5qQ9dL2NVrlYaXKvscnjkMbE6UuaVlQZxjwemCpeW6sRJwktLjT2/kc0MhgW+GWlRnPDDV6qo0pdxcVpxzJWVyWjVb6cZJry03KAZ9xbSUQyXlhskqvzolRrNSR1TeopY4JuRdvF6OjvVK9Um1Zvcqbob9TC90BuNyYXZXiQJvLzcotrqLfQbrYQrK03i9h3NZrzZRVszspZqaffDehixWO2tNr3SDLne4zp2K0wSokTR9lg6qkqSKNVWOgG5iOA56b9ddalcvAZf+xp885vQakEQwFveAu96F+zbv+3LVOFapUVUSJgrZB8Df6UeUQrSE8fVSpOD5VzmdZnhssA3IymKEy5cr6eDoa30dtFwqdFiuTaYGvRquIdRTJSk+93pgnLiKJXGxn0QAc9x8FzwPbfzSeD55+CxxyBOIGl/wmk14exZePob8KEPwevfcNN9XK5HJKrsK2YP6pdXGhT8Ii8tNZjJe+S83nsDmb1nJR0zki5ebxAnyrVqs6e+8YMI+4S0tX610uRapcVyLaTeSgijzmG/HVUI44R6K2G5FnKt0uJqJe1pk2iStuwfewzC8EbYr+1EnC5/7LH0eTuoNGIWa9lPnHECVystVLHSzhizwDcjZ30p53oPYb3SDPsa9mGSsNRocXWlSaURESf9vxaQJFBtxlyttFh68s9p7fQnGifw5JO7WnelEbNUyz7+/UojotKMqDVj66o5pgYe+CJyr4icE5HnReQjg96eGW+qykvLDZTeSjn1MOpbzb4RxVyrpq35RmvnVnycJDTjhEYYU2vFVFsRsUKtFdMIY5pRsmO3SVVofO8FFnMlrhbmqXvblGOSGJ7+5q6PZbkRUenhQu7LKw1iVS4vNwZywjODNdAavoi4wG8D7wbOA38pIp9X1e8McrtmfL1SbdGKkp6GOWjFMa/0YSanRBNWGhGNcPtwTlQJEyWK01p+nHQeF18DpR5uLMusTobiuYLnOPiubBwQLUxPWLHrsOyWqMcBc40arm4q74TdnRivV1v4DplG3oyT9PUHyjleXmlyZC7f9TrM8Ay6hf924HlV/b6qtoDTwHsHvE0zxq4sN4lVM0+9F6vySqWF9tjNvhHFXK22tg37KEmotiKu10Mq7ZPCTpOgbKYKUaI0woRKM2KxHlJthYSrrX/f3/D80PV5pThLzdsUsn53F2NV03p8lPHmrOv1kChJuFppEsaTez/DJBp04B8Dfrzu+/PtZcZssdpCvl7LfgfstUqzp5EuE03r9Eu1cMtJQ1Ga7U8fS/U05Ps6Rr5CI1SW6+lAbo07/hMS2dgbRkVYyRe5VpghFhccF+5+S9ebShJ4pdJE6f4AVNNPYqs3w5nxITrAWR1E5OeBU6r637S//zvA21X1H617zgPAAwALCwtvO336dM/brVQqlMvlntcziib52JZXVvBzRZpxQoYcas8rm/33WVW3rUurpp8esio5EdWkyxJKnMDyEk6S4GzzA3E1QQ4dgowTo7iOZJtNSyBwHRyBsFFnZmYyfyfH5e/t5MmTZ1X1+E7PG3Q//PPAq9Z9fytwcf0TVPVR4FGA48eP64kTJ3re6JkzZ+jHekbRpB7b5eUGf/XnT5J71ZtoZOhZEyXpcAJZSzmtOOZ6LdzSYk9Q6q34pnX83XhH6TJ/Wl3o/oWLAn/2p+RaTYqtGs7qDooLriCn7mW28DryGfvFi8Dh2RyB2/3r/ZzHkbk8L507O5G/kzB5f2+DDvy/BO4QkdcAF4APAv/VgLdpxoyuq9kv17P1IFmsZq/bN6OYpfrWsA/jhGoz7WEzNAtH4N0/Q/O55whffJFSbYXAEXjDHfCWu9HZWZZqIUkRihlCPx1wrcXh2XzXE6lUmhFhnBC3S3E2WcroG2jgq2okIr8MPAG4wCdV9duD3KYZP8v1iCjevofLTmqtm/ekuZlW3Dnsqz2ss+9KZbjnrST3vJUVIO8LxWDjTFcrtRApQiFD6LcipdKMmMn5Oz95k+V6iAKLtZYNuTAGBj60gqp+EfjioLdjxtcr1bRbYZZ+3Yqy1MjW376VbC3jpPPZRjTC0e1j3giVOIko5z2c9aFfD3EKZBr2YLkeUsowT+5SIyQArlUt8MeB3WlrhqoRxlSbMbUwytS6r7biTKNfJpp0DPtKc7TDflUYKyuNiGTdxVxV0vsXMnRxShJYyXDiTJJ0nuFmu2upGW02eJoZqrXafYYLtYlq5qEClhvRlpp/rRX1PN7+XoridEC2mfyN8o5qOrrlvpLfdU1+pRlRznm4TnftwNVPZtcqLcq50YqUz37jAo88cY6L1+vcMl/gwVN3cv8909sz3Fr4ZqiWGyGxaqZx22utKFN//XoU09xUn6+OeBlnO2GsVDe1rMM4odbqfu4ATdgyouduJJpeC1luhAyym3e3PvuNCzz06We4cL2Oks7P+9Cnn+Gz37gw7F0bGgt8MzSNMCaMlFozWzlnJUMJIR0uYWPpIoyT0blAm0EzSm8IW6/ajDKVdiqtKNPNWNVmjCojVdZ55IlzW4azqIcxjzxxbkh7NHwW+GZolutp8GZpjTaiKFPtfnMpJ1EdqZDKqtpKx7xftVra6Ta8kyTb+1Frf0JbzvAJYVAuXu88jPN2y6eBBb4ZmuVGGkhZRm+sNroPpU6lnHoYMwmDPnZqXWct7WQ5ATbCdATQLBd+B+WW+UJXy6eBBb4ZinTij5h6GHd9w1ScJFs+qu9Gp1r3OJdyNgvjDqWdDCWaVpjQirv7+Wp7+OcwSu9MHgUPnrqTgr+xi2rBd3nw1J1D2qPhG61L6mZqrF4crGVpTXY5sxRA6+pV4q+fhe99D8KQxPepvOGNcOed6Y1NE6LaivBdf60/vSbpz6vbG7LqYdz1cAu1VsxM3melGVIIhj8F4mpvHOulc4MFvhmK1RZ6PUMLu9FtC/L556h9+t+DeNAeS76lkPzgh/CjF+E/e0c6hMEEUE3LK8V1gVtvxl0HfqOV0O1Q9/UwWnvtqLj/nmNTHfCbWUnHDEU9jFGUVtRdOChbJxK5qcVrJKf/DS1kLewBmm6QNn+jGP7sT6Fa6Wo/RlkzijeUccI46brHTmsXs3JtFsVpua0Wjs6FW7ORBb7Zc6ppnbeVoTTTCOPuXvO1r1Fz/A1V7FBcImddizdWeO657nZkhKX94jf+kGoZLow3ujwZr74mjNIZwMzosZKO2VsvvEDz47+JPvEfaUYCB4/CO98J73nPrl7e9SeCb36TmlfcsKy5eX5YTeDFH8E9b+1q3aOsEcbk3BvtuWaYkOR1w9g7O64jiikF3UVEs/2aehgz41p7ctTYO2L2zuOPw5vfTP1Tj0G1StPzoFGHM2fgoYegXttxFd0Gfhgn6LphexORdLubxaPTnbAf0tFHb/ysVLv/2UUZWvir3V6z9KIyg2eBb/bGCy/ABz4AtRpNTQO46QXpY3EErSZcuQJXLt90Na0uSwVRfmOf65brQ6dWrtv90MCjrrnpxrRuAzyMtfsune1tbL7fwYwGC3yzNz7+cQjTVnTYrp/Hm+ZrRTX9FLCNOEm6HjsnfONPpLNDra5j8zYBxIHbXt3disfA5knKW13eYabtMXK626Zu+N+MFgt8szc+9am1wI/ctKSy4cIppPPYfu3JbVfRbeseILznbeDeaNFHnUaCdAXe8Iau1z3qNofu5hPArtbRZWVmde5fu2g7mizwzd6o3Oj2GDkusThop+uHzca2q+i20ZigxDOzcOpe8DySzb1zxAHPTfvhT9DNV6tU2VjHTyDq8rbmLMEdxUmmk7MZPAt8szfKNwI1dLzOLW2A3PZ3+3TbQl0Lq1e9Gv7WB4nveiN4QVrC93x47Wvg3T8zMTdddbJ5Pt6oywl64wzDmMaqaxOjmNEysG6ZIvLrwH8LvNxe9D+1pzs00+hv/234xCfQMCR2HGKnw6+eAO9657ar6DZANpQ0ZmeJf/Id8NbpuikoipX1oxxEUZJ+qtmlLKEdxwo+hElCbnPZzgzVoFv4v6mqd7f/WdhPs1/9VfB9Ykl/5ZJOc6eKwH33bbuKbkvQm8Mq7naUtj740dKL/PHzX2CxvsgfP/8FfrT04p5uP9l0zHGXvW6yVGZWPxVkmZzGDJaVdMzeeN3r4N/9O7RUAs9D1we+60GQg8OH4fDCtqvourww5IrCj5Ze5Oyls1TC9P6CSljj7KWzexr6vf4IskyGsvo2ZXmtGaxBB/4vi8i3ROSTIrJvwNsyo+6++9CzfwXvfz9aLKUXTfNFOHkSPvYxKBR3XkcXkiEHzndefpZYN3ZziTXmOy8/u2f7sOUcuQfnzNWgH6HZDk2b9DIHpYh8Geh0xeth4OvAVdLfmd8AjqrqL3RYxwPAAwALCwtvO336dOb9WVWpVCiXJ6/XBYz/sSnpbf9JooRbrig2wLv5RdtuSspxohvmWI1V9zSEFuuLa18fLRS4VL8x09K+wt60fwRw191pLCIbvt/x9QL+TpOab3rfPDfdRs5z6WJTI2lc/t5Onjx5VlWP7/S8ngJ/t0TkduCPVPVNN3ve8ePH9amnnup5e2fOnOHEiRM9r2cUjfuxtaKEcy+tsNIIubzc3PCYvPQd9Mhd2772ykqjqzs4VxotauuG6k0nKt+7wvIfP/+FtXLO//LGn+A3vv0MAGW/yL2v/y/2ZB8CT5jJ3biLOB84zOWDXb/e94QjszefIWrz+3agHLCvGPC6wyWKXY7FM2rG5e9NRHYV+AMr6YjI0XXfvg/Yu8+xZmStlu6li0G81l7b9baG27y869CbcDfd2euKy12HbtruGSm9/ASzvMdmsAZ5+v3fReRu0k/xPwT+wQC3ZcaE2w5hydDUcFyBbsY425Q33YwU2Q+vnrsNYK1mX/aL3HXoTWvL94Kz6aTX7U9g8+t39Zp2HWfI51vTwcACX1X/zqDWbcaX4wgi4GUo7npdJkhae75x0dTr9oTRB6+eu41Xz93GvsLlPSvjrOdtqr97Xc585bgZ3qf2e+vb8Mgjx94Rs+d81+nqwuGqbl/jbwqrLNscd5sz1+/yZ9DtSRbSwBeZzp/3qLPAN3vOcwXPcbr+yN9tecERZ0PpyBEhQ4N1bG0O3SyfrLKemK11P5rsXTF7brWbX7dZ4mVI62BT8LhTlPiuyIYLp54jXV9I7Tbw05OKk+m9MoNngW/23GoYeF22AgPX7fpTweYWrZflavGY2hy6mU6Y3db825vYse++GQp7V8yeC7z0125z63s3fK+712wuLfje9LQ8N/98u71g67my1qtq19tcfW+7fJ/M3rB3xey5gp8GT87v/tcv6LKV6nsbrxV4jpOph9C4cWXrya7bn12WE3KuHfSr77EZLRb4Zs8V/LQ0k8vQCuy6xIBsObHkpyCMNh+j7zldl7O6/TQFkG9PEJ8PLFpGkb0rZs85jpDzHHJdhjdA3uu+d08h2LidwJOJvilIZGtJpRhk+Fln+QTm3xhHx4weC3wzFHnfxRHpuqbuOk7XLc/AcTf0yRck06eLcZHzZEMXVsfp/tOU5wqB211oi5NeWN98gjWjY3J/681IWw2FfIaWYJb6cD638abyvOf0NlDMCNvcui74btfdMbO07lffS6vfjy4LfDMU5XYA71WpIe9tvAnLdRyKE1h2yPvOhuEURLL9jLO00le3U8xN3s91Uoz32KVmbOV9F98TijkPkWZX49QHr1wlePwrtL75DLRaEATwlrfAu94F+/Z3fI2DUPRdqs0bY+vkA4dWnGyc+3aMubI1qHO+g9PlxVrXvXHxtRulXHoxfiZnsTKqrIVvhmY27+OKdNdi/9bT8NBDlL/2/0GrCWj6/9mz8C9+C55/btuXFnPehjttBaGccyemtFPKeRtGBBUnW/iWMrzG99Ka/0zeG/qw1GZ7FvhmaGbyabDsOmCuXIb/659Dq0mhUcVZ3zJPYghDeOwxWLzW8eUOwmx+47YmpbST950t/e5n837XrXsRKGeYtGT1NbN5f4dnmmGywDdDU855OE4XNeYvfhHitCTjoJTC+tbnxAk8+eS2qwhcl+KmPuL5YLxvxupUyskHTrYL4oGLm2FYhNW6/UzeyjmjzALfDI1IOv1e4Lq7u+v2ySchjta+LTfrW6sxSQxPf/Omqynl/S2lnZm8l2ko4GFzJA3ZfpRyIFtgi0DB9yjm3K7HRzJ7y94dM1T7SmkJYK6wi1JAo7HhW08jys3a1ueFza3L1ulU2nFEmCl4YzV8sgjM5r0tLfIspRxIP2l12/ceboyoua+4+7lyzXBY4Juhmsn7BJ5DOeftfPdrPr/19Y0qsrmLj5/bcbuB61LuEPqzBX8sQt8RmOsQ9sWMpRwRmC1ma927IjgOzO/mpG2GygLfDN3+UoAjsvMEJ+98J7ibLrqSMLO+le+4cPdbdrXdUuBR2tRnfDX0R7mm727Tss8HDjP5bK3sYs7Fd7o/UZRzHkj7PRzhn5lJ9RT4IvLzIvJtEUlE5Pimxx4SkedF5JyInOptN80k21f0dzcl3nvek3YS32SmWcVrX8zFddITwy6Vcz6FTRdxV8s7eX/07sbN+076KWRz2PtO5h4yjgNzGV87W0hPwPtLVs4ZB7228J8F3g98df1CEbkL+CDwRuBe4HdEZPz7vpmB8FyHuYK/812hhxfgV/47CHIbWvoOyr5WFXwfPvShbW++2s5sPqC0absOQinw0pb0CIS+027VlwJvyyehfJCeBLodPmHVfDHI1DMn5wsF38MVGyxtXPQU+Kr6XVU91+Gh9wKnVbWpqj8Angfe3su2zGQ7NJPW3Q+Ud2gpvvlu+NjH4ORJyBfTLin5Ivm/+S5K/8OvwOvfkGn75bxPKb81tHzHYbboD7W1n/fTE2KneWK9F5HlAAAR80lEQVQLgcNcPsgc9oXAoZSh3z3A/lL6ntl0huNjUJ1mjwFfX/f9+fYyYzrK+y5ee1jdcs6j0oy2f/LhBfjw30v/rTOvSnO5QRRnGyqhHPj4jsNyIyRJbixfbe3nvIRGGNOMFQY9GoOkE5bkPbdj0IuTXvAu9NCydpzsPWvy7RNFKefyyhh2Z51WOwa+iHwZONLhoYdV9XPbvazDso5/IiLyAPAAwMLCAmfOnNlpl3ZUqVT6sp5RNMnH1qjXuPDdp0gUJE66DlUXOIoSZgz89SuKRdHNvX8cwEt3SxWSLgYAKjkR7yhd3tVzHUnb69vlqEg65jwh6b+MPEdwGtnCWj2H85fSkTlr1cn9nZy0v7cdA19VfzrDes8Dr1r3/a3AxW3W/yjwKMDx48f1xIkTGTa30ZkzZ+jHekbRpB/bHXf/p1yrtLhSabBcu0kr/yZarYhrlVbP+9OM4i2t/S3bihPCOCaKIGL7lv87Spf50+pCx8dcScsivucSuIJoO4Q3rasfrfpVc0Wf2byf6YNKKedydK7AbMHjtgOlif+dnKRjG1RJ5/PAH4jIPwNuAe4A/mJA2xp5n/3GBR554hwXr9e5Zb7Ag6fu5P57rMLVyeGZHIvVFvuLASv1qKtRNFeVAo8on7DcyHbCWJXzXA6UHVYaIc0w6bgvgeukc78GkKDEsRInSqwJUcJaaAtpixppB7zj4DppS33H7qikdfyZvJfphqrNijk3c48eaXfBFIGF2a33RZjR1lPgi8j7gN8CDgFfEJGnVfWUqn5bRP4t8B0gAn5JVeObrWtSffYbF3jo089QD9PDv3C9zkOffgbAQr8D33U4NJPjynKTg+WAl1eytdTnigFhklBv3aR5vgsOwlw+IMkl1FoxtTBGt1mlg+C4Qjr/x8ZWuOvI7u4mXkccKHgOhZzX9Xy02wl8p6culPNFn5znMl/0p2Ju4EnTay+dz6jqraqaU9UFVT217rGPqurrVPVOVX28910dT488cW4t7FfVw5hHnujUuclA2spPe6YEW/rId+NAObe7MXp2wRGHcs7nUDnHXNHPNMH3bvlu2jPoUDnHTD7oX9h7wsFyLnOPnsAT9pcCPFc4Olfoyz6ZvWV32g7YxesdRnS8yXKTXpQ8tq+ACByeyWeecFxIA65fob+6zrznsr8YsL8cUM575ANnw2Bs3XKctGRTyrvsLwfsLwUUvO6nJbyZ1bB3M/4wV0s4Qvre7HiTnBlJNpbpgN0yX+BCh3C/Zd5aSDdTDDwOlnO8vNJbaccR4dBMjqsrTRphb+WdzXzHwV/3CSRBieKEMFaiJCFZ19FIVPC9dExLx0lLPL7j4LvSl7r8zQSew8GZ7GEPG0s5Nub9+LIW/oA9eOrOLZM6F3yXB0/dOaQ9Gh8Ls+tLO9nrxYJwcCZHucONVf3kkM76VAo85vIB+4pB+kmgGOA6wv5iumwuH1AO0gAddNgXcy6Hegz7nH+jlGMNlfFmgT9g999zjI+9/yc4Nl9AgGPzBT72/p+wC7a7ICLcuq+ICByZzeH3UDYRhH3FHPvKQeYS0biZLXocKOV21QtoO44DR2YLVsqZEFbS2QP333PMAj6jQuBybL7A+cU6R+bynL9e37aXzG6UAw/fgauV1k37148zceBAKaDg9/bnLQJH5/L4rsPCbM5KORPAWvhm5O0rBRwoB+Q8lyN96Pud8zyOzObXpuWbJHnf4ehsvuewBzg4k6Pge8wVfA5bn/uJYC18MxaOzuVpRmmTfH/Z51qlhzEFSCcvP1DKUfAjFmvj39qX9rg4WQdC22y26DGXT4eOvnWf1e0nhbXwzVgQEV69v0jgOewv5jLNztRJMUhb++W8O7a1/WLO5ehsvm9hX855HCrncB3h1ftLNrHJBLHAN2PDdYTbDhTxXOFwOc9MoT8B5zoO+4o5FuZyY1XmyfsOC3M5DpRymcaz76QYuCzMpRd6bz+YnmDN5LB304yVvO/ymoMlXEdYmMkzk+9fVdJ3XA6U2sEfjG6LP+87HJ4NODSTzzTp+HaKgcvR+TyOCK85WKLYp08MZnTYO2rGzmro/+BqNb3708k+smYngetyoOwSJwmVZkS1FREPeSQox0l7GJXyHl6fWvPrlXIuR+by7ZZ9iVLOomES2btqxlIhcHntoRLff7nK4XIeV5osVnu7kLuZ66Q3fc0WfBphTD2MqbfiPbvAmw654FLwXQpBf4daWG+2mNbsV1v2FvaTy95ZM7byfhr6P3ylyoFSjpzrcnmlkWlI5ZsR0rlbC74HRWjFafA3o4QwTvp2AhAnHW455zrkA4ecN9g/TxE4WA6YK6R3At9+sGhlnAln764Za3nf5fWHyrx4rQaA7xW4tFQnGmAJJnBdgsKN2nmUJLTa4R+rkiRKnECs6Rj6q+cfx0lD1m3PWOU4giuC7zr4nuA7e3fB2HHgyFyeou+R9x1uO1CyC7RTwALfjD3PdXjtwRIXrtdZrMKr9hW5tNyg0eNY+LvevuPg7TCMszQcjs0X92R/dhJ46fDGvuswW/B41b6idb2cEhb4ZiKsjrtT8JtcWmpwbL7AYq3FYjXse4lnnM0XPfa3x9c5PJuzWaumjAW+mSgHyjnyvsuPF2vsL+YoBR5XVho0w+lOfd+TdPRRz8N10oHQup2By4w/C3wzcUo5jzccnuHScoNrlRa37iuyWG2xWJvO1v76Vv1cweeW+Tyea/X6aWSBbyaS4wjH5tNW7PnFGvtLOUo5j2vVFtXmdEyvXAicdMYvz01b9fMF5orWqp9mPZ3mReTnReTbIpKIyPF1y28XkbqIPN3+9y9731Vjuldut/b3lwPyvsvRuQK37s/3NFfuqMv5wtH5PMfmi2uzVL1hoWxhb3pu4T8LvB/4Vx0ee0FV7+5x/cb0bLW1f6AUcHm5AXU4Nu9RbUVcqzYnpr7vu8KBUo5ye7iJcj4dGK6X2cLMZOkp8FX1u5D2kDBm1OV9l9sOlKi1Il5aagBQCjxqYcRyLR1CYRxr/MXAZa7or42WWQgcFmbzzNiEJWYT0T78hovIGeB/VNWn2t/fDnwbeA5YBv5nVf2P27z2AeABgIWFhbedPn265/2pVCqUy+We1zOK7Nj6J1ElipV49W9AIVYlTrT/wR81wOtfF8jVG7gcR9YGeXNE8BzZ82kI7Xdy+E6ePHlWVY/v9LwdW/gi8mXgSIeHHlbVz23zskvAq1X1FRF5G/BZEXmjqi5vfqKqPgo8CnD8+HE9ceLETru0ozNnztCP9YwiO7b+a4Qx16qttYlQFKXWiqm1IqrNqC937cpL30GP3NXTOlwHijmPcs5LR/MkDfv5op9O5jKk0o39To6PHQNfVX+625WqahNotr8+KyIvAG8Anup6D40ZsLzvcst8gSOzea7XQ65VWwhCKfA4VIZmFFNtRlRbMa0o2bOyj0h6V2wx8CjlXPLrxtbJ+w77SgH7ioFNLG52bSDdMkXkEHBNVWMReS1wB/D9QWzLmH5xHGF/KWB/KSCME5brISuNCGlCznPZX0pb/60ooRElNKOYZpj05SQgkl50zfkuec8h5zsErovTrteIpLX62YLPTN4j59mFWNO9ngJfRN4H/BZwCPiCiDytqqeAvwn8ExGJgBj4h6p6ree9NWaP+K7DgXKOA+UcSaKsNCMqzYh6K8aRuB24Ny6KxqpEcUKUpNcAoiRB2+UhBaqOUC56aRnGScffcZ205p7W3Td2ExVJW/F536Wc85jJ+9aSNz3rtZfOZ4DPdFj+h8Af9rJuY0aF46R3qK4ORaCqNKOEWisdI78ZxkSJEsay7VDJTVc4WN560dZx0pOL5wiB51DwXYpBOoKl9X4z/WZ32hrTJREh77vk/a1llSRRwiRZ6/2jCihccR1efaC41rvGcwXfcWyUSrOnLPCN6SPHEXKOy+ZJo9z2pwRjhmly7y83xhizgQW+McZMCQt8Y4yZEhb4xhgzJSzwjTFmSljgG2PMlLDAN8aYKWGBb4wxU8IC3xhjpoQFvjHGTAkLfGOMmRIW+MYYMyUs8I0xZkpY4BtjzJSwwDfGmClhgW+MMVOip8AXkUdE5K9F5Fsi8hkRmV/32EMi8ryInBORU73vqjHGmF702sL/EvAmVX0z8BzwEICI3AV8EHgjcC/wOyKydT44Y4wxe6anwFfVP1HVqP3t14Fb21+/Fzitqk1V/QHwPPD2XrZljDGmN/2s4f8C8Hj762PAj9c9dr69zBhjzJDsOIm5iHwZONLhoYdV9XPt5zwMRMDvr76sw/N1m/U/ADwAsLCwwJkzZ3be6x1UKpW+rGcU2bHtzvV6yOWlBq04IXAdFubyzA9xEnF738bTpB3bjoGvqj99s8dF5MPAzwI/paqroX4eeNW6p90KXNxm/Y8CjwIcP35cT5w4sfNe7+DMmTP0Yz2jyI5tZ5/9xgUe+soz1EOH1Q+xBT/mY++/i/vvGc4HTXvfxtOkHVuvvXTuBX4N+DlVra176PPAB0UkJyKvAe4A/qKXbRmzW488cY56GG9YVg9jHnni3JD2yJjRsGMLfwf/AsgBXxIRgK+r6j9U1W+LyL8FvkNa6vklVY1vsh5j+ubi9XpXy42ZFj0Fvqq+/iaPfRT4aC/rNyaLW+YLXOgQ7rfMF4awN8aMDrvT1kycB0/dScHfeNtHwXd58NSdQ9ojY0ZDryUdY0bO6oXZR544x8XrdW6ZL/DgqTuHdsHWmFFhgW8m0v33HLOAN2YTK+kYY8yUsMA3xpgpYYFvjDFTwgLfGGOmhAW+McZMCQt8Y4yZEhb4xhgzJeTGAJfDJyIvAy/2YVUHgat9WM8osmMbT3Zs42lcju02VT2005NGKvD7RUSeUtXjw96PQbBjG092bONp0o7NSjrGGDMlLPCNMWZKTGrgPzrsHRggO7bxZMc2nibq2Cayhm+MMWarSW3hG2OM2WSiAl9EfkNEviUiT4vIn4jILe3lIiL/XESebz/+1mHva7dE5BER+ev2/n9GRObXPfZQ+9jOicipYe5nFiLy8yLybRFJROT4psfG+tggnfu5vf/Pi8hHhr0/vRCRT4rIFRF5dt2y/SLyJRH5Xvv/fcPcx6xE5FUi8v+KyHfbv4+/0l4+EccHExb4wCOq+mZVvRv4I+B/bS+/j3Qi9TuAB4D/e0j714svAW9S1TcDzwEPAYjIXcAHgTcC9wK/IyLutmsZTc8C7we+un7hJBxbe39/m/R38C7gQ+3jGle/S/perPcR4Cuqegfwlfb34ygCflVV/wbwk8Avtd+rSTm+yQp8VV1e920JWL1A8V7g/9HU14F5ETm65zvYA1X9E1WN2t9+Hbi1/fV7gdOq2lTVHwDPA28fxj5mparfVdVzHR4a+2Mj3d/nVfX7qtoCTpMe11hS1a8C1zYtfi/we+2vfw+4f093qk9U9ZKq/lX76xXgu8AxJuT4YMICH0BEPioiPwb+a2608I8BP173tPPtZePqF4DH219P2rGtNwnHNgnHsJMFVb0EaWgCh4e8Pz0TkduBe4A/Z4KOb+ymOBSRLwNHOjz0sKp+TlUfBh4WkYeAXwb+MSAdnj9y3ZN2Orb2cx4m/ej5+6sv6/D8sTy2Ti/rsGzkjm0Hk3AMU0VEysAfAv+9qi6LdHoLx9PYBb6q/vQun/oHwBdIA/888Kp1j90KXOzzrvVsp2MTkQ8DPwv8lN7oTzsRx7aNsTi2HUzCMezksogcVdVL7VLplWHvUFYi4pOG/e+r6qfbiyfm+CaqpCMid6z79ueAv25//Xng77Z76/wksLT6EW1ciMi9wK8BP6eqtXUPfR74oIjkROQ1pBem/2IY+zgAk3BsfwncISKvEZGA9CL054e8T/32eeDD7a8/DGz3iW2kSdqU/9fAd1X1n617aCKODwBVnZh/pGfmZ4FvAf8eONZeLqQ9JV4AngGOD3tfMxzb86S14Kfb//7luscebh/bOeC+Ye9rhmN7H2lLuAlcBp6YlGNrH8N7SHtWvUBawhr6PvVwLI8Bl4Cw/Z79feAAae+V77X/3z/s/cx4bO8iLbd9a93f2Xsm5fhU1e60NcaYaTFRJR1jjDHbs8A3xpgpYYFvjDFTwgLfGGOmhAW+McZMCQt8Y4yZEhb4xhgzJSzwjTFmSvz/wiu205VIuOsAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from matplotlib.patches import Circle\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import copy\n",
    "import time\n",
    "\n",
    "class Node:\n",
    "    \"\"\"二叉树结点\n",
    "    Parameters\n",
    "    --------------\n",
    "    left: Node\n",
    "        左子结点\n",
    "    right: Node\n",
    "        右子结点\n",
    "    point: tuple\n",
    "        该结点存储的切分点\n",
    "    dim: int\n",
    "        该结点的切分维度，是索引，因此真正的维度应该是dim+1\n",
    "    \"\"\"\n",
    "    def __init__(self, left, right, point, dim):\n",
    "        self.left  = left\n",
    "        self.right = right\n",
    "        self.point = point\n",
    "        self.dim   = dim\n",
    "\n",
    "    def get_child_num(self):\n",
    "        \"\"\"返回该结点的子结点数目\n",
    "        Return\n",
    "        --------------\n",
    "        : int, 0 or 1 or 2      \n",
    "            子结点数目\n",
    "        \"\"\"\n",
    "        return int(self.right != None) + int(self.left != None)\n",
    "\n",
    "class KdTree:\n",
    "    \"\"\"kd树\n",
    "    Parameters\n",
    "    --------------\n",
    "    training_data: list of tuple\n",
    "        训练样本数据点\n",
    "    \n",
    "    Attributes\n",
    "    --------------\n",
    "    dim_: int\n",
    "        样本维度\n",
    "    kdtree_: Node\n",
    "        kd树(根节点表示)\n",
    "    nearest_: list of Node\n",
    "        存储当前最邻点\n",
    "    min_dist_: float\n",
    "        与当前最邻点的距离\n",
    "    \"\"\"\n",
    "    def __init__(self, training_data):\n",
    "        self.training_data = training_data\n",
    "        self.dim_ = len(training_data[0])\n",
    "        self.kdtree_ = None\n",
    "        self.nearest_  = []\n",
    "        self.min_dist_ = []\n",
    "\n",
    "    def create_tree(self):\n",
    "        \"\"\"构造kd树\"\"\"\n",
    "        kdtree = self.create_tree_real(self.training_data)\n",
    "        self.kdtree_ = kdtree\n",
    "\n",
    "    def create_tree_real(self, point_list, depth=0):\n",
    "        \"\"\"实际构造kd树函数\n",
    "        Parameters\n",
    "        --------------\n",
    "        point_list: list by tuples\n",
    "            训练数据点(或其一部分)\n",
    "        depth: int\n",
    "            结点深度，默认是0，即root位置\n",
    "\n",
    "        Returns\n",
    "        --------------\n",
    "        Node: Node\n",
    "            kd树(以根节点表示)\n",
    "        \"\"\"\n",
    "        if not point_list:  # 递归的base criteria\n",
    "            return None\n",
    "        dim_index = depth%self.dim_\n",
    "        point_list = sorted(point_list, key=lambda x:x[dim_index])\n",
    "        median_index = len(point_list)//2\n",
    "        return Node(\n",
    "                point  = point_list[median_index],\n",
    "                left  = self.create_tree_real(point_list[:median_index], depth+1),\n",
    "                right = self.create_tree_real(point_list[median_index+1:], depth+1),\n",
    "                dim = dim_index\n",
    "        )\n",
    "\n",
    "    def compute_distance(self, p1, p2):\n",
    "        \"\"\"计算两点间的欧氏距离\n",
    "        Parameters\n",
    "        --------------\n",
    "        p1: tuple\n",
    "            点1\n",
    "        p2: tuple\n",
    "            点2\n",
    "\n",
    "        Returns\n",
    "        --------------\n",
    "        distance: float\n",
    "            两点的欧氏距离\n",
    "        \"\"\"\n",
    "        p1 = np.array(p1)\n",
    "        p2 = np.array(p2)\n",
    "        distance = np.sqrt(np.sum((p1-p2)*(p1-p2)))\n",
    "        return distance\n",
    "\n",
    "    def find_nearest_k(self, query_point, k=1):\n",
    "        \"\"\"寻找最近的k个点\"\"\"\n",
    "        if not self.kdtree_:\n",
    "            print(\"Attention: 请先构建kd树!\")\n",
    "            return None\n",
    "        self.find_nearest_k_real(self.kdtree_, query_point, k)\n",
    "        nearest_points = [i.point for i in self.nearest_]\n",
    "        min_distances  = self.min_dist_\n",
    "        print(\"k=%s最近点为:%s, 距离为:%s\" % (str(k), str(nearest_points), str(min_distances)))\n",
    "        return nearest_points,min_distances\n",
    "\n",
    "    def find_nearest_k_real(self, root, query_point, k=1):\n",
    "        \"\"\"实际检索函数\n",
    "        Parameters\n",
    "        --------------\n",
    "        root: Node\n",
    "            搜索的起始位置\n",
    "        query_point: tuple\n",
    "            目标数据点\n",
    "        k: int\n",
    "            k邻\n",
    "        \"\"\"\n",
    "        node_list = []                                                              # 储存待检查的结点\n",
    "        cursor_node = root                                                          # 不需要deepcopy\n",
    "        while cursor_node:                                                          # 二叉检索，获得子结点，并将路径结点保存\n",
    "            node_list.append(cursor_node)\n",
    "            if cursor_node.get_child_num() == 1:                                    # 如果下面只剩一个结点，无论是左是右，都走下去\n",
    "                cursor_node = cursor_node.left if cursor_node.left else cursor_node.right\n",
    "            else:\n",
    "                dim = cursor_node.dim\n",
    "                if query_point[dim] < cursor_node.point[dim]:\n",
    "                    cursor_node = cursor_node.left\n",
    "                else:\n",
    "                    cursor_node = cursor_node.right\n",
    "        while node_list:                                                            # 回退检索\n",
    "            back_point = node_list.pop()\n",
    "            btq_dist = self.compute_distance(back_point.point, query_point)\n",
    "            if len(self.nearest_) < k:                                              # 如果存储当前最近点的列表不满k个，则直接加入\n",
    "                self.nearest_.append(back_point)\n",
    "                self.min_dist_.append(btq_dist)\n",
    "            elif btq_dist < max(self.min_dist_):\n",
    "                replace_index = self.min_dist_.index(max(self.min_dist_))           # 如果存储当前最近点的列表满k个，则与其中距离最大的点进行比较，看是否可以替换\n",
    "                self.nearest_[replace_index] = back_point\n",
    "                self.min_dist_[replace_index] = btq_dist\n",
    "            dim = back_point.dim\n",
    "            if back_point.get_child_num() == 2:                                     # 确定有左右两个子结点，有一个或没有都不用进行以下步骤\n",
    "                if abs(query_point[dim] - back_point.point[dim]) < max(self.min_dist_):\n",
    "                    if query_point[dim] < back_point.point[dim]:                    # 以当前最近点集合中最远点与目标点连线为半径的圆与同父兄弟的矩形空间相交，因此需要检查同父兄弟的矩形空间\n",
    "                        cursor_node = back_point.right\n",
    "                        self.find_nearest_k_real(cursor_node,query_point,k)\n",
    "                    else:\n",
    "                        cursor_node = back_point.left\n",
    "                        self.find_nearest_k_real(cursor_node,query_point,k)\n",
    "\n",
    "def draw_pic(X,query_point,nearest_points,min_distances):\n",
    "    fig = plt.figure()\n",
    "    ax = fig.add_subplot(111)\n",
    "    for j in min_distances:\n",
    "        cir = Circle(xy=query_point, radius=j, alpha=0.2)\n",
    "        ax.add_patch(cir)\n",
    "        plt.axis('scaled')\n",
    "        plt.axis('equal')\n",
    "    plt.scatter([i[0] for i in X], [i[1] for i in X])\n",
    "    plt.scatter([i[0] for i in nearest_points],[i[1] for i in nearest_points],s=100,c='r')\n",
    "    plt.scatter(query_point[0],query_point[1],c='g')\n",
    "    plt.grid()\n",
    "    plt.show()\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # 数据生成\n",
    "    n = 10\n",
    "    np.random.seed(1)\n",
    "    temp = np.random.randn(2*n)*10\n",
    "    X = temp[:n]\n",
    "    Y = temp[n:]\n",
    "    input_ = list(zip(X,Y))\n",
    "    query_point = (0,-5)\n",
    "    # 构建kd树并搜寻\n",
    "    time1 = time.time()\n",
    "    kt = KdTree(input_)\n",
    "    kt.create_tree()\n",
    "    time2 = time.time()\n",
    "    nearest_points,min_distances = kt.find_nearest_k(query_point,k=5)\n",
    "    time3 = time.time()\n",
    "    print(\"构建kd树用时: %f秒\" % (time2-time1))\n",
    "    print(\"检索用时: %f秒\" % (time3-time2))\n",
    "    draw_pic(input_,query_point,nearest_points,min_distances)"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}