{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这一节我们使用 sklearn 自带的鸢尾花数据集来实现 kNN 算法，和前面一样，我们只取数据集中的两个维度："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAFz1JREFUeJzt3W+MXFd5x/Hv45kUMDREIqsSxX9WFYi2oBDiVQhNhUJsqhAs8wKqplpKg1q5eEMJLRV/GilVLSFUIVGgYKMlqEpqt4QGaANKaZsAhb4g1TokgWBaBWonTmizSUrS1G0q209f3Lt4d3Z25p6ZOTPnnPl9pKuduXNy9zn33n1yfe5zz5i7IyIiZdk06QBERGT0lNxFRAqk5C4iUiAldxGRAim5i4gUSMldRKRASu4iIgVSchcRKZCSu4hIgdpNG5pZC1gCHnH33R2fXQt8GHikXvUJd7+p1/bOP/98n52dDQpWRGTaHTly5HF3n+nXrnFyB64HjgLnbvD5re7+zqYbm52dZWlpKeDXi4iImR1v0q7RsIyZbQHeCPS8GhcRkTQ0HXP/KPBe4EyPNm82s/vN7DYz29qtgZntNbMlM1taXl4OjVVERBrqm9zNbDfwmLsf6dHsS8Csu18E3Anc3K2Ruy+6+5y7z83M9B0yEhGRATW5cr8c2GNmx4DPAlea2aHVDdz9CXd/tn77aWDHSKMUEZEgfZO7u3/A3be4+yxwDfBVd3/r6jZmdsGqt3uobryKiMiEhFTLrGFm+4Eld78deJeZ7QFOAU8C144mPBERGUTQQ0zu/vWVGnd3v7FO7CtX9y9391e6++vc/fsxghWZiMOHYXYWNm2qfh4+POmIRPoa+MpdZCocPgx798LJk9X748er9wDz85OLS6QPTT8g0ssNN5xN7CtOnqzWiyRMyV2kl4ceClsvkggld5Fetm0LWy+SCCV3kV4++EHYvHntus2bq/UiCVNyF+llfh4WF2H7djCrfi4u6maqJE/VMiL9zM8rmUt2dOUuIlIgJXcRkQIpuYuIFEjJXUSkQEruIiIFUnIXESmQkruISIGU3EVECqTkLiJSICV3KYe+VEPkJzT9gJRBX6ohsoau3KUM+lINkTWU3KUM+lINkTWU3KUM+lINkTWU3KUM+lINkTWU3KUM+lINkTVULSPl0JdqiPyErtxleKovF0mOrtxlOKovF0mSrtxlOKovF0mSkrsMR/XlIklScpfhqL5cJElK7jIc1ZeLJEnJXYaj+nKRJDWuljGzFrAEPOLuuzs+ew5wC7ADeAL4VXc/NsI4JWWqLxdJTsiV+/XA0Q0++03gP939JcCfAH88bGAiWVLNvySiUXI3sy3AG4GbNmjyJuDm+vVtwE4zs+HDE8nISs3/8ePgfrbmXwleJqDplftHgfcCZzb4/ELgYQB3PwU8Bbxo6OhEcqKaf0lI3+RuZruBx9z9SK9mXdZ5l23tNbMlM1taXl4OCFMkA6r5l4Q0uXK/HNhjZseAzwJXmtmhjjYngK0AZtYGXgg82bkhd1909zl3n5uZmRkqcJHkqOZfEtI3ubv7B9x9i7vPAtcAX3X3t3Y0ux34jfr1W+o2667cRYqmmn9JyMB17ma238z21G8/A7zIzB4Efg94/yiCE8mKav4lITapC+y5uTlfWlqayO8WEcmVmR1x97l+7fSEqqRrYQHa7eoquN2u3otII5rPXdK0sAAHD559f/r02fcHDkwmJpGM6Mpd0rS4GLZeRNZQcpc0nT4dtl5E1lBylzS1WmHrRWQNJXdJ08r3sDZdLyJr6IaqpGnlpuniYjUU02pViV03U0UaUXKXdB04oGQuMiANy0h3u3ZV9eUry65dk45ocjRHu2RIyV3W27UL7rpr7bq77prOBK852iVTmn5A1uv1PSvTNh/c7GyV0Dtt3w7Hjo07GhFNPyAyEpqjXTKl5C7Si+Zol0wpuct6O3eGrS+Z5miXTCm5y3p33rk+ke/cWa2fNpqjXTKlG6oiIhnRDVUZTqza7pDtqr5cZGB6QlXWW6ntPnmyer9S2w3DDUeEbDdWDCJTQsMysl6s2u6Q7aq+XKQrDcvI4GLVdodsV/XlIkNRcpf1YtV2h2xX9eUiQ1Fyl/Vi1XaHbFf15SJDUXKX9WLVdodsV/XlIkPRDVURkYzohmpsKdRgh8aQQswiMhaqcx9ECjXYoTGkELOIjI2GZQaRQg12aAwpxCwiQ9OwTEwp1GCHxpBCzCIyNkrug0ihBjs0hhRiFpGxUXIfRAo12KExpBCziIyNkvsgUqjBDo0hhZhFZGz63lA1s+cC3wCeQ1Vdc5u7/2FHm2uBDwOP1Ks+4e439dpu1jdURUQmZJQ3VJ8FrnT3VwIXA1eZ2WVd2t3q7hfXS8/ELhOysADtdnXl3m5X70fRNpX6+VTiEElA3zp3ry7tn6nfnlMvk6mflMEtLMDBg2ffnz599v2BA4O3TaV+PpU4RBLRqM7dzFrAEeAlwCfd/X0dn18LfAhYBv4V+F13f7jXNjUsM2btdpWkO7VacOrU4G1TqZ9PJQ6RyEZa5+7up939YmALcKmZvaKjyZeAWXe/CLgTuHmDoPaa2ZKZLS0vLzf51TIq3ZL1RutD2qZSP59KHCKJCKqWcfcfA18HrupY/4S7P1u//TSwY4P/ftHd59x9bmZmZoBwZWCtVvP1IW1TqZ9PJQ6RRPRN7mY2Y2bn1a+fB+wCvt/R5oJVb/cAR0cZpIzAyvhzk/UhbVOpn08lDpFUuHvPBbgI+DZwP/Bd4MZ6/X5gT/36Q8ADwH3A14Cf67fdHTt2uIzZvn3urZY7VD/37RtN20OH3Ldvdzerfh46NOrIm0klDpGIgCXvk1/dXROHiYjkRBOHxRarpjqkvjzmtkP6l+O+yIxK+CVYk8v7GEvWwzKHDrlv3lwNWawsmzcPPwywb9/aba4svYZEYmw7pH857ovMxNrFkic0LBNRrJrqkPrymNsO6V+O+yIzKuGX1ZoOyyi5D2LTpuoCqpMZnDkz+HbNNv5s2OMUsu2Q/uW4LzITaxdLnjTmHlOsmuqQ+vKY2w7pX477IjMq4ZdBKLkPIlZNdUh9ecxth/Qvx32RGZXwy0CaDMzHWLK+oeoer6Y6pL485rZD+pfjvsiMSvhlBbqhKiJSHo25y3op1K5L1nRa5KPvfO5SiJD5zjU3unSh0yIvGpaZFinUrkvWdFqkQcMyslbIfOeaG1260GmRFyX3aZFC7bpkTadFXpTcp0UKteuSNZ0WeVFynxbz87C4WA2QmlU/Fxe73wkLaStTQ6dFXnRDVUQkI7qhuiJWYW7IdlOZl1xFykkp/XCU3r8QE9kXTR5jjbGMZfqBWBNhh2w3lXnJNSl4Uko/HKX3L8So9wWafoB4hbkh201lXnIVKSel9MNRev9CjHpfaD53iDcRdsh2U5mXXJOCJ6X0w1F6/0KMel9ozB3iFeaGbDeVeclVpJyU0g9H6f0LMal9UXZyj1WYG7LdVOYlV5FyUko/HKX3L8TE9kWTgfkYy9jmc481EXbIdlOZl1yTgiel9MNRev9CjHJfoBuqIiLl0Zh7bKqfF8lCrD+T5Ov4m1zex1iy/po91c+LZCHWn8kk6/jRsExEqp8XyUKsP5NJ1vFrWCamWBNbh2y32xnba73IFIr1Z5LD3PZK7oNQ/bxIFmL9meRQx6/kPgjVz4tkIdafSRZ1/E0G5mMsWd9QdVf9vEgmYv2ZTKqOH91QFREpz8huqJrZc83sn83sPjN7wMz+qEub55jZrWb2oJndbWazg4XdQGhxafLFqB1CinIL3xcxw425m5uK2b/MDnWQwk/70el3aQ8Y8IL69TnA3cBlHW0WgE/Vr68Bbu233YGGZUKLS3ObVDqkKLfwfREz3Ji7uamY/cvsUAcp/LRvhIbDMkHj5MBm4B7g1R3r/w54Tf26DTxOPZ3wRstAyX379u5/ldu3j6b9pK0MDHYurdb6toXvi5jhxtzNTcXsX2aHOkjhp30jTZN7ozF3M2sBR4CXAJ909/d1fP5d4Cp3P1G//0H9P4DHO9rtBfYCbNu2bcfxbk8B9BI6MXJuk0qHzP1e+L6IGW7M3dxUzP5ldqiDFH7aNzLSh5jc/bS7XwxsAS41s1d0/r5u/1mX7Sy6+5y7z83MzDT51WuFFpfmUIy6WkhRbuH7Ima4MXdzUzH7l9mhDlL4aT9SQXXu7v5j4OvAVR0fnQC2AphZG3gh8OQI4lsrtLg0i2LUVUKKcgvfFzHDjbmbm4rZv8wOdZDCT/vR6jduA8wA59Wvnwd8E9jd0eY61t5Q/Vy/7Q5c5x5aXJrbpNIhRbmF74uY4cbczU3F7F9mhzpI4ad9X4xqzN3MLgJuBlpUV/qfc/f9Zra//iW3m9lzgT8HXkV1xX6Nu/+w13ZV5y4iEq7pmHu7XwN3v58qaXeuv3HV6/8FfiU0SBERiaP8uWWm9gkG6SXktEjhFIr54E5uD2mlcDyy0GTsJsYylrllSnyCQYYWclqkcArFfHAnt4e0Ujgek4bmlmGyM+pLskJOixROodAYUuhfbtvNSdMx97KTe4lPMMjQQk6LFE6hmA/u5PaQVgrHY9L0TUww3U8wyIZCTosUTqGYD+7k9pBWCscjF2Un96l+gkE2EnJapHAKxXxwJ7eHtFI4HtloMjAfYxnbl3WU9gSDjETIaZHCKRTzwZ3cHtJK4XhMErqhKiJSHo25i4xIyBd7pCK3mFOpXU8ljpFocnkfY8n+O1RlKoR8sUcqcos5ldr1VOLoBw3LiAyv3YbTp9evb7Xg1Knxx9NEbjGnUrueShz9aFhGZAS6Jcle61OQW8wPPRS2vvQ4RkXJXaSHkC/2SEVuMadSu55KHKOi5C7SQ8gXe6Qit5hTqV1PJY6RaTIwH2PRDVXJRcgXe6Qit5hTqV1PJY5e0A1VEZHy6IaqjE2OtcGxYo5VX57jPpYJa3J5H2PRsEwZcqkNXi1WzLHqy3PcxxIPGpaRccilNni1WDHHqi/PcR9LPBqWkbHIsTY4Vsyx6stz3McyeUruMpQca4NjxRyrvjzHfSyTp+QuQ8mxNjhWzLHqy3Pcx5KAJgPzMRbdUC1HDrXBnWLFHKu+PMd9LHGgG6oiIuXRDVWZOrFqwUO2q3p0SUV70gGIjMLhw9XY9smT1fvjx8+Odc/Pj2e7sWIQGYSGZaQIsWrBQ7arenQZBw3LyFSJVQsesl3Vo0tKlNylCLFqwUO2q3p0SYmSuxQhVi14yHZVjy4pUXKXIszPw+JiNb5tVv1cXBz+RmbIdmPFIDKIvjdUzWwrcAvwYuAMsOjuH+tocwXwN8C/1au+4O77e21XN1RFRMKN8obqKeA97v7zwGXAdWb2C13afdPdL66Xnold0pdjvbbq0ePTfstIk8dYVy9UV+iv71h3BfDlkO1o+oF05Th/eEjMOfYvBdpvaSDG9ANmNgt8A3iFuz+9av0VwOeBE8CjwO+7+wO9tqVhmXTlWK+tevT4tN/S0HRYpnFyN7MXAP8IfNDdv9Dx2bnAGXd/xsyuBj7m7i/tso29wF6Abdu27Tje7UyRidu0qbou62QGZ86MP54mQmLOsX8p0H5Lw0gfYjKzc6iuzA93JnYAd3/a3Z+pX98BnGNm53dpt+juc+4+NzMz0+RXywTkWK+tevT4tN/y0je5m5kBnwGOuvtHNmjz4rodZnZpvd0nRhmojE+O9dqqR49P+y0z/QblgV8CHLgfuLdergbeAbyjbvNO4AHgPuBbwC/2265uqKYtx/nDQ2LOsX8p0H6bPDSfu4hIeTRx2BRQzfFaCwvQblc3+Nrt6r3ItNJ87pnS3OFrLSzAwYNn358+ffb9gQOTiUlkkjQskynVHK/VblcJvVOrBadOjT8ekVg0LFM4zR2+VrfE3mu9SOmU3DOlmuO1Wq2w9SKlU3LPlGqO11q539B0vUjplNwzpbnD1zpwAPbtO3ul3mpV73UzVaaVbqiKiGREN1QHUXjheOHdK75/KdA+zkiTx1hjLMlNP1D4ZNWFd6/4/qVA+zgNaPqBQIUXjhfeveL7lwLt4zSMfD73UUsuuRc+WXXh3Su+fynQPk6DxtxDFV44Xnj3iu9fCrSP86LkvqLwwvHCu1d8/1KgfZwXJfcVhReOF9694vuXAu3jvGjMXUQkIxpzFylIzPpy1a6XSfO5iyQu5tz9+l6AcmlYRiRxMevLVbueHw3LiBQi5tz9+l6Acim5iyQuZn25atfLpeQukriY9eWqXS+XkrtI4mLWl6t2vVy6oSoikhHdUBURmWJK7iIiBVJyFxEpkJK7iEiBlNxFRAqk5C4iUiAldxGRAim5i4gUqG9yN7OtZvY1MztqZg+Y2fVd2piZfdzMHjSz+83skjjhyjA0b7fI9Ggyn/sp4D3ufo+Z/TRwxMz+wd2/t6rNG4CX1surgYP1T0mE5u0WmS59r9zd/Ufufk/9+r+Ao8CFHc3eBNzilW8B55nZBSOPVgZ2ww1nE/uKkyer9SJSnqAxdzObBV4F3N3x0YXAw6ven2D9/wAws71mtmRmS8vLy2GRylA0b7fIdGmc3M3sBcDngXe7+9OdH3f5T9bNSObui+4+5+5zMzMzYZHKUDRvt8h0aZTczewcqsR+2N2/0KXJCWDrqvdbgEeHD09GRfN2i0yXJtUyBnwGOOruH9mg2e3A2+qqmcuAp9z9RyOMU4akebtFpkuTapnLgV8HvmNm99br/gDYBuDunwLuAK4GHgROAm8ffagyrPl5JXORadE3ubv7P9F9TH11GweuG1VQIiIyHD2hKiJSICV3EZECKbmLiBRIyV1EpEBK7iIiBVJyFxEpkJK7iEiBrCpRn8AvNlsGjk/kl/d3PvD4pIOISP3LV8l9A/Wvie3u3ndyrokl95SZ2ZK7z006jljUv3yV3DdQ/0ZJwzIiIgVSchcRKZCSe3eLkw4gMvUvXyX3DdS/kdGYu4hIgXTlLiJSoKlO7mbWMrNvm9mXu3x2rZktm9m99fJbk4hxGGZ2zMy+U8e/1OVzM7OPm9mDZna/mV0yiTgH0aBvV5jZU6uO342TiHNQZnaemd1mZt83s6Nm9pqOz7M9dtCof9kePzN72aq47zWzp83s3R1toh+/Jl/WUbLrgaPAuRt8fqu7v3OM8cTwOnffqK72DcBL6+XVwMH6Zy569Q3gm+6+e2zRjNbHgK+4+1vM7KeAji9JzP7Y9esfZHr83P1fgIuhuoAEHgG+2NEs+vGb2it3M9sCvBG4adKxTNCbgFu88i3gPDO7YNJBTTszOxd4LdXXW+Lu/+fuP+5olu2xa9i/UuwEfuDunQ9sRj9+U5vcgY8C7wXO9Gjz5vqfTLeZ2dYe7VLlwN+b2REz29vl8wuBh1e9P1Gvy0G/vgG8xszuM7O/NbOXjzO4If0ssAz8WT1seJOZPb+jTc7Hrkn/IN/jt9o1wF92WR/9+E1lcjez3cBj7n6kR7MvAbPufhFwJ3DzWIIbrcvd/RKqfwJeZ2av7fi829cn5lI+1a9v91A9pv1K4E+Bvx53gENoA5cAB939VcB/A+/vaJPzsWvSv5yPHwD1cNMe4K+6fdxl3UiP31Qmd6ov/d5jZseAzwJXmtmh1Q3c/Ql3f7Z++2lgx3hDHJ67P1r/fIxqzO/SjiYngNX/ItkCPDqe6IbTr2/u/rS7P1O/vgM4x8zOH3uggzkBnHD3u+v3t1Elw842WR47GvQv8+O34g3APe7+H10+i378pjK5u/sH3H2Lu89S/bPpq+7+1tVtOsa/9lDdeM2GmT3fzH565TXwy8B3O5rdDrytvnN/GfCUu/9ozKEGa9I3M3uxmVn9+lKqc/2Jccc6CHf/d+BhM3tZvWon8L2OZlkeO2jWv5yP3yq/RvchGRjD8Zv2apk1zGw/sOTutwPvMrM9wCngSeDaScY2gJ8Bvlj/fbSBv3D3r5jZOwDc/VPAHcDVwIPASeDtE4o1VJO+vQXYZ2angP8BrvG8ntj7HeBw/U/7HwJvL+TYrejXv6yPn5ltBl4P/PaqdWM9fnpCVUSkQFM5LCMiUjoldxGRAim5i4gUSMldRKRASu4iIgVSchcRKZCSu4hIgZTcRUQK9P/zUmS5eqGLXgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from sklearn import datasets\n",
    "\n",
    "iris = datasets.load_iris();\n",
    "\n",
    "X = iris.data\n",
    "y = iris.target\n",
    "\n",
    "X = X[y < 2, :2]\n",
    "y = y[y < 2]\n",
    "\n",
    "plt.scatter(X[y == 0, 0], X[y == 0, 1], color='red')\n",
    "plt.scatter(X[y == 1, 0], X[y == 1, 1], color='blue')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用 sklearn 的 kNN 算法和 sklearn 的其他算法流程是一样的：首先定义分类器（在这里分类器为 `KNeighborsClassifier`），然后通过 `fit` 训练数据得到模型，最后通过 `predict` 对新的样本进行预测。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 0]\n"
     ]
    }
   ],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "\n",
    "kNN = KNeighborsClassifier(n_neighbors=6)\n",
    "kNN.fit(X, y)\n",
    "results = kNN.predict([[6,2], [4, 3]])\n",
    "print(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面对 (6,2) 和 (4,3) 两个样本进行预测，可以看到预测结果是正确的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 其他实例\n",
    "\n",
    "在 Peter Harrington 的《机器学习实战》的第二章，还介绍了很多使用 kNN 解决现实问题的例子，譬如：\n",
    "\n",
    "1. 电影分类：根据电影中出现的打斗镜头数和接吻镜头数判断电影的类别\n",
    "\n",
    "![](../images/knn-movie.png)\n",
    "\n",
    "2. 海伦约会：根据对方每年的飞行里程公里数、每周玩游戏所花费的小时数、每周吃掉的零食的斤数来判断对方是不是自己喜欢的类型\n",
    "\n",
    "![](../images/knn-date.jpg)\n",
    "\n",
    "3. 手写数字识别\n",
    "\n",
    "可以参考这里：https://cuijiahua.com/blog/2017/11/ml_1_knn.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 归一化\n",
    "\n",
    "在 kNN 算法中，还有一点需要特别注意，由于大多数时候我们都是使用欧式距离来作为距离度量方法，而欧氏距离公式会极大地受到数值大小的影响，比如上面海伦约会的例子中，两个人的飞行里程可能很容易就相差2000，但吃掉的零食斤数最多可能也就差10，这样算出来的距离就几乎只受飞行里程影响，而对于海伦来说，3个特征是同等重要的。为了解决这个问题，我们需要对这三个特征的特征值进行 **归一化** （Normalization）处理，使得它们的取值范围都落在0到1之间。\n",
    "\n",
    "$$\n",
    "x_i := \\frac{x_i-min(x_i)}{max(x_i)-min(x_i)}\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}