01.1.kNN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# kNN k近邻算法原理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 原理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 问题描述"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "已知训练数据集 $X\\_train$ 中包含 $N$ 条样本特征（对应下图中的蓝点和黄点共10条），   \n",
    "每条样本中包含 $D$ 个特征（对应下图中是 $x_{1}$ 和$x_{2}$两个特征），  \n",
    "以及训练监督数据集 $y\\_train$ ，包含训练集中每条样本所对应的类别。  \n",
    " $X\\_train$ 是一个 $N * D$ 形状的二维矩阵， $y\\_train$ 是一个长度为 $N$ 的一维向量。  \n",
    "输入：一个长度为 $D$ 的一维特征向量表示的未知类别的测试样本（对应下图）。  \n",
    "输出：测试样本对应的类别。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEKCAYAAAD9xUlFAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAF1xJREFUeJzt3X+M3XW95/Hne0rXcuSXKZO7QDs9zV7jVivlx8CtqWsE4hUuBtxc7i7roFfjZrzKrpgYFBwXI9lJNCYs26zinUV2vXKIuPgjXAW3uNYouUCdclv80RpQmNLCpmOVCs7FpfjeP87pt+0w0/l1vvOdmfN8JCff8/18P+c77zk5mdd8v5/v+XwjM5EkCaCr6gIkSQuHoSBJKhgKkqSCoSBJKhgKkqSCoSBJKhgKkqSCoSBJKhgKkqTCCVUXMFOnn3561uv1qsuQpEVl+/btv87M7qn6LbpQqNfrDA8PV12GJC0qETEynX6ePpIkFQwFSVLBUJAkFRbdmIIktcNLL73E3r17efHFF6supa1WrFjBqlWrWL58+axebyhI6kh79+7l5JNPpl6vExFVl9MWmcmBAwfYu3cva9eundU+PH0kqSO9+OKLrFy5cskEAkBEsHLlyjkd/RgK0iw0GlCvQ1dXc9loVF2RZmMpBcJhc/2dPH0kzVCjAf39MDbWXB8Zaa4D9PVVV5fUDh4pSDM0MHAkEA4bG2u2S4udoSDN0J49M2uXFhNDQZqhnp6ZtWtpKGsc6Z3vfCfnn38+b3jDGxgaGmrPTufAUJBmaHAQarVj22q1ZruWpsPjSCMjkHlkHKkdwXDHHXewfft2hoeH2bx5MwcOHJj7TufAUJBmqK8PhoZgzRqIaC6HhhxkXsrKHEfavHkzGzZsYOPGjTz99NM8/vjjc9/pHHj1kTQLfX2GQCcpaxzpBz/4Ad/73vd46KGHqNVqvPWtb638G9YeKUjSFMoaRzp48CCvec1rqNVq7N69m4cffnhuO2wDQ0GSplDWONKll17KoUOHWLduHTfccAMbN26c2w7bwNNHkjSFw6cKBwaap4x6epqBMNdTiK961au4//77515gGxkKkjQNnTKO5OkjSVLBUJAkFQwFSVLBUJAkFQwFSVKh1FCIiKci4icRsSMihifYHhGxOSKeiIjHIuK8MuuRpIXkqaeeYv369VWXcYz5uCT1osz89STbLgNe23r8GXBbaylJqkDVp4+uBP4umx4GTouIMyquSZJe6ckGfKsOd3U1l0+2Z+7sQ4cO0dfXx7p167jqqqsYGz/z3jwrOxQS2BIR2yOif4LtZwFPH7W+t9UmSQvHkw3Y1g9jI0A2l9v62xIMv/jFL/jQhz7Erl27OOWUU/jCF74w93rnoOxQeHNmnkfzNNG1EfGW2ewkIvojYjgihkdHR9tboSRNZecAvDzuP/iXx5rtc7R69Wo2bdoEwDXXXMODDz44533ORamhkJn7Wsv9wDeBC8d12QesPmp9Vatt/H6GMrM3M3u7u7vLKleSJjY2yRzZk7XPQEQcd32+lRYKEfHqiDj58HPgz4Gfjut2L/Ce1lVIG4GDmflsWTVJ0qzUJpkje7L2GdizZw8PPfQQAHfddRdvfvOb57zPuSjzSOFPgAcjYiewDfhOZn43Iv4mIv6m1ec+4FfAE8B/Bz5UYj2SNDsbBmHZuLmzl9Wa7XP0ute9js9//vOsW7eO3/72t3zwgx+c8z7norRLUjPzV8CGCdq/eNTzBK4tqwZJaou1relRdw40TxnVepqBsHZu06bW63V2797dhgLbx6mzJWk61vbNOQQWg6q/pyBJWkAMBUlSwVCQJBUMBUlSwVCQJBUMBUmqwHPPPTfreY5uvfXW0ibOMxQkqQKGgiQtYo1Gg3q9TldXF/V6nUZjbjOk3nDDDfzyl7/knHPO4frrr+dzn/scF1xwAWeffTaf+tSnAPj973/P5ZdfzoYNG1i/fj133303mzdv5plnnuGiiy7ioosuasevdgy/vCZJU2g0GvT39xf/nY+MjNDf37wbQF/f7L7Q9pnPfIaf/vSn7Nixgy1btnDPPfewbds2MpMrrriCH/7wh4yOjnLmmWfyne98B4CDBw9y6qmncsstt7B161ZOP/309vyCR/FIQZKmMDAw8IrTNWNjYwwMzH3qbIAtW7awZcsWzj33XM477zx2797N448/zhvf+EYeeOABPv7xj/OjH/2IU089tS0/73g8UpCkKezZM/EU2ZO1z1RmcuONN/KBD3zgFdseffRR7rvvPj75yU9yySWXcNNNN7XlZ07GIwVJmkJPz8RTZE/WPh0nn3wyzz//PABvf/vbueOOO3jhhRcA2LdvH/v37+eZZ56hVqtxzTXXcP311/Poo4++4rXt5pGCJE1hcHDwmDEFgFqtxuDg7KfOXrlyJZs2bWL9+vVcdtllvOtd7+JNb3oTACeddBJ33nknTzzxBNdffz1dXV0sX76c2267DYD+/n4uvfRSzjzzTLZu3Tq3X26caM5evXj09vbm8PBw1WVIWuR27drFunXrpt2/0WgwMDDAnj176OnpYXBwcNaDzGWb6HeLiO2Z2TvVaz1SkKRp6OvrW7Ah0E6OKUiSCoaCpI612E6fT8dcfydDQVJHWrFiBQcOHFhSwZCZHDhwgBUrVsx6H44pSOpIq1atYu/evYyOjlZdSlutWLGCVatWzfr1pYdCRCwDhoF9mfmOcdveC3wO2Ndq+m+ZeXvZNUnS8uXLWbt2bdVlLDjzcaRwHbALOGWS7Xdn5n+YhzokSVModUwhIlYBlwP+9y9Ji0DZA823Ah8D/nicPn8ZEY9FxD0RsbrkeiRJx1FaKETEO4D9mbn9ON3+Hqhn5tnAA8CXJ9lXf0QMR8TwUhsUkqSFpMwjhU3AFRHxFPBV4OKIuPPoDpl5IDP/0Fq9HTh/oh1l5lBm9mZmb3d3d4klS1JnKy0UMvPGzFyVmXXgauD7mXnN0X0i4oyjVq+gOSAtSarIvH9PISJuBoYz817gwxFxBXAI+A3w3vmuR5J0hLOkSlIHmO4sqU5zIUkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqlB4KEbEsIv4xIr49wbZXRcTdEfFERDwSEfWy65EkTW4+jhSuA3ZNsu39wG8z80+B/wJ8dh7qkSRNotRQiIhVwOXA7ZN0uRL4cuv5PcAlERFl1iRJmlzZRwq3Ah8D/jjJ9rOApwEy8xBwEFhZck2SpEmUFgoR8Q5gf2Zub8O++iNiOCKGR0dH21CdJGkiZR4pbAKuiIingK8CF0fEneP67ANWA0TECcCpwIHxO8rMoczszcze7u7uEkuWpM5WWihk5o2ZuSoz68DVwPcz85px3e4F/rr1/KpWnyyrJknS8Z0w3z8wIm4GhjPzXuBLwFci4gngNzTDQ5JUkXkJhcz8AfCD1vObjmp/Efir+ahBkjQ1v9EsSSoYCpKkgqEgSSoYCpKkgqEgSSoYCpKkgqEgSSoYCpKkgqEgSSoYCpKkgqEgSSoYCpKkgqEgSSocNxQi4pSI+BcTtJ9dXkmSpKpMGgoR8W+A3cDXI+JnEXHBUZv/Z9mFSZLm3/GOFD4BnJ+Z5wDvo3kznH/d2halVyZJmnfHu8nOssx8FiAzt0XERcC3I2I14C0zJWkJOt6RwvNHjye0AuKtwJXAG0quS5JUgeOFwgeBroh4/eGGzHweuBT492UXJkmaf5OGQmbuzMzHga9FxMej6UTgFuBD81ahJGneTOd7Cn8GrAb+Afgx8AywaaoXRcSKiNgWETtbVy99eoI+742I0YjY0Xp4BCJJFZpOKLwE/BNwIrACeDIz/ziN1/0BuDgzNwDnAJdGxMYJ+t2dmee0HrdPt3Atfo0G1OvQ1dVcNhpVV6SO82QDvlWHu7qayyf9EE4nFH5MMxQuAP4V8O8i4n9N9aJseqG1urz18KolAc0A6O+HkRHIbC77+w0GzaMnG7CtH8ZGgGwut/V3fDBMJxTen5k3ZeZLmflsZl4J3DudnUfEsojYAewHHsjMRybo9pcR8VhE3NO63FUdYGAAxsaObRsba7ZL82LnALw87kP48lizvYNNGQqZOTxB21ems/PMfLn15bdVwIURsX5cl78H6pl5NvAA8OWJ9hMR/RExHBHDo6Oj0/nRWuD27JlZu9R2Y5N82CZr7xDzMiFeZj4HbKV5OevR7Qcy8w+t1duB8yd5/VBm9mZmb3d3d7nFal709MysXWq72iQftsnaO0RpoRAR3RFxWuv5icDbaM6ldHSfM45avQLYVVY9WlgGB6FWO7atVmu2S/NiwyAsG/chXFZrtnewMo8UzgC2RsRjNAerH8jMb0fEzRFxRavPh1uXq+4EPgy8t8R6tID09cHQEKxZAxHN5dBQs12aF2v74MIhqK0Borm8cKjZfjxL/IqlyFxcFwT19vbm8PArhjkkqXyHr1g6eoB6WW16YVKxiNiemb1T9fMmO5I0XR1wxZKhIEnT1QFXLBkKkjRdHXDFkqEgSdPVAVcsGQqSNF2zvWJpETnendckSeOt7VtSITCeRwqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpEJpoRARKyJiW0TsjIifRcSnJ+jzqoi4OyKeiIhHIqJeVj2NBtTr0NXVXDYaZf2kxVGHJE2kzJvs/AG4ODNfiIjlwIMRcX9mPnxUn/cDv83MP42Iq4HPAv+23YU0GtDfD2NjzfWRkeY6QN883itjodQhSZMp7Ughm15orS5vPXJctyuBL7ee3wNcEhHR7loGBo78IT5sbKzZPp8WSh2SNJlSxxQiYllE7AD2Aw9k5iPjupwFPA2QmYeAg8DKCfbTHxHDETE8Ojo64zr27JlZe1kWSh2SNJlSQyEzX87Mc4BVwIURsX6W+xnKzN7M7O3u7p7x63t6ZtZeloVShyRNZl6uPsrM54CtwKXjNu0DVgNExAnAqcCBdv/8wUGo1Y5tq9Wa7fNpodQhSZMp8+qj7og4rfX8ROBtwO5x3e4F/rr1/Crg+5k5ftxhzvr6YGgI1qyBiOZyaGj+B3cXSh2SNJko4W9wc8cRZ9McRF5GM3y+lpk3R8TNwHBm3hsRK4CvAOcCvwGuzsxfHW+/vb29OTw8XErNkrRURcT2zOydql9pl6Rm5mM0/9iPb7/pqOcvAn9VVg2SpJnxG82SpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqlBYKEbE6IrZGxM8j4mcRcd0Efd4aEQcjYkfrcVNZ9UiSplbmkcIh4KOZ+XpgI3BtRLx+gn4/ysxzWo+bS6xHeoVGo0G9Xqerq4t6vU6j0ai6JC0UTzbgW3W4q6u5fLIzPhsnlLXjzHwWeLb1/PmI2AWcBfy8rJ8pzUSj0aC/v5+xsTEARkZG6O/vB6Cvr6/K0lS1JxuwrR9ebn42GBtprgOsXdqfjXkZU4iIOnAu8MgEm98UETsj4v6IeMN81CMBDAwMFIFw2NjYGAMDAxVVpAVj58CRQDjs5bFm+xJX2pHCYRFxEvB14COZ+btxmx8F1mTmCxHxF8C3gNdOsI9+oB+gp6en5IrVKfbs2TOjdnWQsUk+A5O1LyGlHilExHKagdDIzG+M356Zv8vMF1rP7wOWR8TpE/QbyszezOzt7u4us2R1kMn+wfAfD1Gb5DMwWfsSUubVRwF8CdiVmbdM0ueft/oRERe26jlQVk3S0QYHB6nVase01Wo1BgcHK6pIC8aGQVh27GeDZbVm+xJX5umjTcC7gZ9ExI5W2yeAHoDM/CJwFfDBiDgE/BNwdWZmiTVJhcODyQMDA+zZs4eenh4GBwcdZNaRweSdA81TRrWeZiAs8UFmgFhsf4N7e3tzeHi46jIkaVGJiO2Z2TtVP7/RLEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAodqNGAeh26uppL7yuj0nTojWoWs9KnztbC0mhAfz8cvo3AyEhzHcApf9RWHXyjmsXMI4UOMzBwJBAOGxtrtktt1cE3qlnMDIUOM9n9Y7yvjNqug29Us5gZCh1msvvHeF8ZtV0H36hmMTMUOszgIIy7rwy1WrNdaqsOvlHNYmYodJi+PhgagjVrIKK5HBpykFklWNsHFw5BbQ0QzeWFQw4yL3DeZEeSOoA32ZEkzZihIEkqGAqSpEJpoRARqyNia0T8PCJ+FhHXTdAnImJzRDwREY9FxHll1SNJmlqZRwqHgI9m5uuBjcC1EfH6cX0uA17bevQDt5VYjyQtLhXMHVVaKGTms5n5aOv588Au4Kxx3a4E/i6bHgZOi4gzyqpJkhaNw3NHjY0AeWTuqJKDYV7GFCKiDpwLPDJu01nA00et7+WVwSFJnaeiuaNKD4WIOAn4OvCRzPzdLPfRHxHDETE8Ojra3gIlaSGqaO6oUkMhIpbTDIRGZn5jgi77gNVHra9qtR0jM4cyszcze7u7u8spVpIWkormjirz6qMAvgTsysxbJul2L/Ce1lVIG4GDmflsWTVJ0qJR0dxRZd5kZxPwbuAnEbGj1fYJoAcgM78I3Af8BfAEMAa8r8R6JGnxODxH1M6B5imjWk8zEEqeO6q0UMjMB4GYok8C15ZVgyQtamv75n0CQb/RLEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpIKhIEkqGAqSpEI0vz+2eETEKDAyh12cDvy6TeUsdr4XR/heHMv344il8l6sycwpJ49bdKEwVxExnJm9VdexEPheHOF7cSzfjyM67b3w9JEkqWAoSJIKnRgKQ1UXsID4Xhzhe3Es348jOuq96LgxBUnS5DrxSEGSNImOCYWIWB0RWyPi5xHxs4i4ruqaqhIRKyJiW0TsbL0Xn666pqpFxLKI+MeI+HbVtVQpIp6KiJ9ExI6IGK66nipFxGkRcU9E7I6IXRHxpqprmg9l3nltoTkEfDQzH42Ik4HtEfFAZv686sIq8Afg4sx8oXUf7Qcj4v7MfLjqwip0HbALOKXqQhaAizJzKVyXP1f/FfhuZl4VEf8MqE31gqWgY44UMvPZzHy09fx5mn8Azqq2qmpk0wut1eWtR8cOLkXEKuBy4Paqa9HCEBGnAm+heZ95MvP/ZeZz1VY1PzomFI4WEXXgXOCRaiupTut0yQ5gP/BAZnbsewHcCnwM+GPVhSwACWyJiO0R0V91MRVaC4wC/6N1WvH2iHh11UXNh44LhYg4Cfg68JHM/F3V9VQlM1/OzHOAVcCFEbG+6pqqEBHvAPZn5vaqa1kg3pyZ5wGXAddGxFuqLqgiJwDnAbdl5rnA74Ebqi1pfnRUKLTOn38daGTmN6quZyFoHRJvBS6tupaKbAKuiIingK8CF0fEndWWVJ3M3Nda7ge+CVxYbUWV2QvsPeoI+h6aIbHkdUwoRETQPD+4KzNvqbqeKkVEd0Sc1np+IvA2YHe1VVUjM2/MzFWZWQeuBr6fmddUXFYlIuLVrYswaJ0q+XPgp9VWVY3M/L/A0xHxulbTJUBHXJTSSVcfbQLeDfykdS4d4BOZeV+FNVXlDODLEbGM5j8GX8vMjr4UUwD8CfDN5v9PnADclZnfrbakSv1HoNG68uhXwPsqrmde+I1mSVKhY04fSZKmZihIkgqGgiSpYChIkgqGgiSpYChIbRQR342I5zp9tlUtXoaC1F6fo/l9GGlRMhSkWYiICyLisda9KV7dui/F+sz8P8DzVdcnzVYnfaNZapvM/HFE3Av8Z+BE4M7M7MgpIbS0GArS7N0M/Bh4EfhwxbVIbeHpI2n2VgInAScDKyquRWoLQ0Gavb8F/hPQAD5bcS1SW3j6SJqFiHgP8FJm3tWabfYfIuJi4NPAvwROioi9wPsz839XWas0E86SKkkqePpIklQwFCRJBUNBklQwFCRJBUNBklQwFCRJBUNBklQwFCRJhf8PZ04d7fHcKokAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "class_a_x1 = [2., 2.5, 3.0, 3.5, 4.2]\n",
    "class_a_x2 = [3., 3., 2.2, 3.5, 5.3]\n",
    "class_b_x1 = [5.3, 5.9, 6., 6.1, 6.5]\n",
    "class_b_x2 = [2.2, 3.5, 2.5, 3.4, 2.]\n",
    "pred_x = [4., 2.5]\n",
    "\n",
    "plt.figure()\n",
    "plt.scatter(x=class_a_x1, y=class_a_x2, c=\"blue\", label=\"a\")\n",
    "plt.scatter(x=class_b_x1, y=class_b_x2, c=\"orange\", label=\"b\")\n",
    "plt.scatter(*pred_x, c=\"black\", label=\"test\")\n",
    "plt.xlabel(\"x1\")\n",
    "plt.ylabel(\"x2\")\n",
    "plt.legend()\n",
    "# plt.grid(True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 求解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基本步骤：\n",
    "* 求测试样本到所有训练样本的距离\n",
    "* 对求得的距离进行排序，并从排序的训练样本中，取k个与测试样本最近的邻居点\n",
    "* k个邻居点投票方式，选出票数最多的类别，做为测试样本的预测结果  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 求距离的方式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "manhattan曼哈顿距离：$\\mathrm{d}_{12}=\\sum_{k=1}^{n}\\left|\\mathrm{x}_{1 k}-x_{2 k}\\right|$  \n",
    "  \n",
    "euclidean欧几里德距离：$d_{12}=\\sqrt{\\sum_{k=1}^{n}\\left(x_{1 k}-x_{2 k}\\right)^{2}}$  \n",
    "  \n",
    "chebyshev切比雪夫距离：$d_{12}=\\max _{i}\\left(\\left|x_{1 i}-x_{2 i}\\right|\\right)$  \n",
    "  \n",
    "Minkowski闵可夫斯基距离：$d_{12}=\\sqrt[p]{\\sum_{k=1}^{n}\\left|x_{1 k}-x_{2 k}\\right|^{p}}$  \n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.4.1 k如何选择？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "取不同的k做交叉验证，选出效果最好的k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.4.2 kNN如何做回归任务？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 词汇表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 数值型数据\n",
    "    > 1. 在数值上可以连续表示的数据（如身高、体重），或者数值大小可以具有实际意义的（如年龄）\n",
    "* 离散型数据（又称分类数据、无序数据）\n",
    "    > 1. 简单来说就是类别  \n",
    "    > 2. 如性别：男和女两个类别"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 分类任务\n",
    "    > 预测的结果是离散型数据\n",
    "* 回归任务  \n",
    "    > 预测的结果是连续性数值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.4.3 离散型特征怎么求距离？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 离散型数据的表示方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 计数表示\n",
    "    > 假设有10类，分别用数字0-9表示没个类别  \n",
    "    > 采用计数表示，让原本没有顺序、没有大小的离散型数据带上了数值的属性  \n",
    "    > 求距离不合理，不同类别的距离本该是平等的。$d_{00}=0$，$d_{09} = 9$，$d_{01}=1$   \n",
    "* one-hot编码\n",
    "    > 假设有10类，分别用一个长度为10的向量表示每一类，如第1类表示为[0,0,0,0,0,0,0,0,0,1]，第二类表示为[0,0,0,0,0,0,0,0,1,0]  \n",
    "    > $d_{00}=0$，$d_{01} = \\sqrt2$，$d_{09} = \\sqrt2$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 算法复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设训练样本中有N条数据，每个数据有D个特征"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 时间复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ O(N*D) = max(O_{distance}(N*D), O_{topk}(N))$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 空间复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ O(N*D) = O_{X\\_train}(N*D) + O_{distance}(N) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 优缺点及其他特点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 优点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 实现简单  \n",
    "* 精度高，多分类效果甚至好于SVM\n",
    "* 对异常值不敏感\n",
    "* 既可以做分类任务，又可以做回归任务"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 缺点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 计算复杂度大且不可控，随着训练样本数增大而增大    \n",
    "* 每次预测都需要重新计算测试集与每个训练集的距离，实际使用消耗太大   \n",
    "* 受数值差值最大的特征的影响大，需要做特征值归一化  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 其他特点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 是一种监督学习  \n",
    "* 没有可学习的参数  \n",
    "* kNN模型的三个基本要素：距离度量、k值的选择、分类决策规则的决定。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 优化空间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 kd树构建"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 kd树搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 球树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ O(D\\log_{2} N) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 适用范围  \n",
    "* 训练集较小的任务  \n",
    "* 对时间没有要求的离线训练任务  \n",
    "* 其他较简单的分类任务和回归任务  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 相关链接  \n",
    "  \n",
    "<a href=\"./01.2.kNN-sklearn.ipynb\" style=\"\"> 1.2 sklearn中使用kNN做分类、回归任务  </a>  \n",
    "<a href=\"./01.3.kNN-numpy.ipynb\" style=\"\"> 1.3 numpy实现kNN分类和回归 </a>  \n",
    "<a href=\"./01.4.kNN-tf2.ipynb\"> 1.4 TensorFlow2实现kNN分类和回归 </a>  \n",
    "<a href=\"./01.5.kNN-torch1.ipynb\"> 1.5 Pytorch1实现kNN分类和回归 </a>  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 项目源码  \n",
    "https://github.com/LossJ  \n",
    "进入后点击Statistic-Machine-Learning  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献  \n",
    "<a href=\"https://book.douban.com/subject/24703171/\">[1] [M]Peter Harrington[美]. 机器学习实战. 北京: 人民邮电出版社, 2013.6.</a>  \n",
    "<a href=\"https://book.douban.com/subject/33437381/\">[2] [M]李航. 统计学习方法(第二版). 北京：清华大学出版社，2019.5.1.</a>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}