Lab12.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实验课 12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实验12-1 k-近邻算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "k-近邻算法采用测量不同特征值之间的距离方法进行分类。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。\n",
    "\n",
    "例如在二维平面中有一些已知类别（用不同颜色标记）的点，现在我们有一个新的数据点（白色），如何确定该点所属的类别呢？\n",
    "\n",
    "![KNN](img/Lab12-1-1.png)\n",
    "\n",
    "你可能说这个点是和蓝色点属于同一类别的，因为该点周围大部分都是蓝色点。这就是k-近邻算法的简易思想：待分类数据周围k个点的大比数类别就是该数据的类别。\n",
    "\n",
    "现在我们使用Scikit-Learn库中的k-近邻算法对鸢尾花进行简单分类，为了可视化方便，这里我们只利用花瓣长度（Petal Length）和花瓣宽度（Petal Width）作为数据特征，首先先进行数据集划分、再将训练集中的数据点可视化："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/d3fzzAAAACXBIWXMAAAsTAAALEwEAmpwYAAAjr0lEQVR4nO3de3hV9Z3v8fc3ITSIKFawpqCCPYJWEgnGW63iDaxClacVweMFmKnW8VJ7PPaoc1AzPszYeZxqmRHr2KkFR6tcbNGCra1a2zpeExDwUlA5jAawXCyINkhIvuePvROTnbWTvbN29t5r5fN6njxk//ZvrfXd8fGbld/6/n4/c3dERCT6SgodgIiI5IYSuohITCihi4jEhBK6iEhMKKGLiMREv0JdeMiQIT5ixIhCXV5EJJLq6+u3ufvQoPcKltBHjBhBXV1doS4vIhJJZvbf6d7TkIuISEwooYuIxIQSuohITBRsDD1IU1MTDQ0N7N69u9ChxEJ5eTnDhw+nrKys0KGISB4UVUJvaGhg0KBBjBgxAjMrdDiR5u5s376dhoYGRo4cWehwRCQPuh1yMbNDzOx3ZvaWmb1hZtcF9DnNzHaa2WvJr1t7Eszu3bs58MADlcxzwMw48MAD9deOFKXl65czcclEqhZUMXHJRJavXx762DDnjItM7tD3Av/b3VeY2SCg3sx+6+5vpvT7o7tPDhuQknnu6GcpxWj5+uXUvlDL7ubEzcbmTzZT+0ItAJMOn9SjY1duWcnj7zzeo3PGSbd36O6+2d1XJL/fBbwFDOvtwEQknuaumNuWeFvtbt7N3BVze3zs4nWLe3zOOMmqysXMRgDVwMsBb59kZqvM7FdmdnSa468wszozq9u6dWv20RaZ+fPns2nTpkKHIRIpH3zyQVbtmfRp8ZYenzNOMk7oZrYv8BjwXXf/KOXtFcBh7n4M8G/A0qBzuPv97l7j7jVDhwbOXI0UJXSR7B088OCs2jPpU2LBqSyTc8ZJRgndzMpIJPOH3f3nqe+7+0fu/nHy+yeBMjMbktNIAyxduZGTv/8sI29azsnff5alKzeGPucnn3zCpEmTOOaYYxgzZgwLFy6kvr6e8ePHc+yxx3L22WezefNmlixZQl1dHRdffDFjx46lsbGRZ555hurqaiorK/mbv/kbPv30UwBuuukmvvzlL1NVVcUNN9wAwC9/+UtOOOEEqqurOeuss/jzn/8cOnaRKLhu3HWUl5Z3aCsvLee6cZ3qLTI+duqoqT0+Z6y4e5dfgAEPAj/sos/BgCW/Px54r/V1uq9jjz3WU7355pud2tL5xYoGP3L2r/ywG5e1fR05+1f+ixUNGZ8jyJIlS/xb3/pW2+sdO3b4SSed5Fu2bHF390cffdRnzZrl7u7jx4/3V1991d3dGxsbffjw4b527Vp3d7/00kv97rvv9u3bt/uoUaO8paXF3d3/8pe/uLv7hx9+2Nb24x//2K+//vpQcaeTzc9UJF+WvbvMJyye4JXzK33C4gm+7N1loY8Nc84oAeo8TV7NpMrlZOBSYI2ZvZZs+3vg0OQvhPuAC4C/M7O9QCMwPXnhXnPnU2tpbGru0NbY1MydT61lSnXPn9lWVlZyww03cOONNzJ58mQOOOAAXn/9dSZMmABAc3MzFRUVnY5bu3YtI0eOZNSoUQDMmDGDefPmcc0111BeXs63vvUtJk2axOTJiUKghoYGpk2bxubNm9mzZ49qxaVPmXT4pB5Xn6Q7Nsw546LbhO7uz5O4S++qzz3APbkKKhObdjRm1Z6pUaNGUV9fz5NPPsnNN9/MhAkTOProo3nxxRe7PC7d769+/frxyiuv8Mwzz/Doo49yzz338Oyzz3Lttddy/fXXc9555/Hcc89RW1sbKm6RbC1fv5y5K+bywScfcPDAg7lu3HW9khDnvDSHxesW0+ItlFgJU0dNZfaJs3N+HYnwWi5fHDwgq/ZMbdq0iX322YdLLrmEG264gZdffpmtW7e2JfSmpibeeOMNAAYNGsSuXbsAOPLII9mwYQPvvPMOAP/5n//J+PHj+fjjj9m5cyfnnnsuP/zhD3nttdcA2LlzJ8OGJf6SWLBgQaiYRbLVWs+9+ZPNON5Wt53ryThzXprDwrUL26pQWryFhWsXMuelOTm9jiRENqF/7+zRDCgr7dA2oKyU7509OtR516xZw/HHH8/YsWP5x3/8R26//XaWLFnCjTfeyDHHHMPYsWN54YUXAJg5cyZXXnklY8eOxd356U9/ytSpU6msrKSkpIQrr7ySXbt2MXnyZKqqqhg/fjx33303ALW1tUydOpVTTjmFIUN6/fmxSAdhasGzsXjd4qzaJRzr5aHutGpqajx1g4u33nqLo446KuNzLF25kTufWsumHY18cfAAvnf26FDj53GU7c9U+oaqBVU4nf/fN4zVM1bn7DqVCyrTvrdmxpqcXacvMbN6d68Jeq+oFufK1pTqYUrgIj1w8MCD2fzJ5sD2XCqxksBJP+nqxiUc/VRF+qAwteDZmDpqalbtEk6k79BFpGdaq1l6u8qltZpFVS75EekxdOmefqYi8dLVGLqGXEREYkJDLiLSJmiyEXQemglq641JSdlMfsrXRKkwejtGJfReduutt3Lqqady1llnZXXcc889x7/8y7+wbNmyXopMpKOgzSNmPz8bM6Oppamt7Zb/ugV3Z6/vbWvrjc0kstkII8ymGfmSjxg15JID7k5LS/B6zLfffnvWybwn9u7d2+vXkHgLmmy01/e2JfNWTS1Nbcm8VW9MSspm8lO+JkqFkY8Yo53QVy+Cu8dA7eDEv6sXhTrdjTfeyL333tv2ura2lh/84AfceeedHHfccVRVVXHbbbcBsGHDBo466iiuuuoqxo0bx/vvv8/MmTMZM2YMlZWVbTNCZ86cyZIlSwB49dVX+cpXvsIxxxzD8ccfz65du9i9ezezZs2isrKS6upqfve733WK68MPP2TKlClUVVVx4oknsnr16rb4rrjiCiZOnMhll10W6rOLhN0MItebSWSzEUaYTTPyJR8xRjehr14Ev/wO7Hwf8MS/v/xOqKQ+ffp0Fi5c2PZ60aJFDB06lLfffptXXnmF1157jfr6ev7whz8AiRUWL7vsMlauXMm2bdvYuHEjr7/+OmvWrGHWrFkdzr1nzx6mTZvG3LlzWbVqFU8//TQDBgxg3rx5QGLJgUceeYQZM2Z02tj5tttuo7q6mtWrV/NP//RPHZJ3fX09jz/+OD/72c96/LlFIPykolxPSspmI4wwm2bkSz5ijG5Cf+Z2aEpZWbGpMdHeQ9XV1WzZsoVNmzaxatUqDjjgAFavXs1vfvMbqqurGTduHH/60594++23ATjssMM48cQTATj88MNZv3491157Lb/+9a/Zb7/9Opx77dq1VFRUcNxxxwGw33770a9fP55//nkuvfRSILHA12GHHca6des6HNu+zxlnnMH27dvZuXMnAOeddx4DBoRbkEwEgicb9bN+lJWUdWgrKymjn3V8/NYbk5KymfyUr4lSYeQjxug+FN3ZkF17hi644AKWLFnCBx98wPTp09mwYQM333wz3/72tzv027BhAwMHDmx7fcABB7Bq1Sqeeuop5s2bx6JFi3jggQfa3nd3zDqvQpzJPICgPq3nah+DSBjpJhtl2pbrh4/ZTH7K10SpMPIRY3QT+v7Dk8MtAe0hTJ8+ncsvv5xt27bx+9//njVr1nDLLbdw8cUXs++++7Jx40bKyso6Hbdt2zb69+/PN7/5Tb70pS8xc+bMDu8feeSRbNq0iVdffZXjjjuOXbt2MWDAAE499VQefvhhzjjjDNatW8d7773H6NGjO6y/3trnlltu4bnnnmPIkCGd/gIQyYWuNo/IpC1f8YTtWyi9HWN0E/qZtybGzNsPu5QNSLSHcPTRR7Nr1y6GDRtGRUUFFRUVvPXWW5x00kkA7Lvvvjz00EOUlnZcunfjxo3MmjWrrdrljjvu6PB+//79WbhwIddeey2NjY0MGDCAp59+mquuuoorr7ySyspK+vXrx/z58/nc5z7X4dja2lpmzZpFVVUV++yzj9ZPl0jJtPY6CnXkQYop7mhP/V+9KDFmvrMhcWd+5q1QdWGOI402Tf2XQkqtvYbEuHHtV2o7JL1M+xWbQsQd36n/VRfC/3odanck/lUyFykqmdZeR6GOPEixxR3thC4iRS3T2uso1JEHKba4ldBFpNdkWnsdhTryIMUWtxK6iPSaTGuvo1BHHqTY4o5ulYuIFL1Ma6+jUEcepNjijnaVi3RLP1OReIlvlUsebNq0iQsuuCDr484991x27NjRZZ9bb72Vp59+uoeRiRTO8vXLmbhkIlULqpi4ZCLL1y9P255pWxQUe9y6Q++hvXv30q9f8Y9YRelnKtGQrvb6/P9xPo+/83iH9rKSsg5rp0NifZj2a6y3Hq+a88zE9g49178t0y2fO2bMGADmz5/P1KlT+frXv87EiRP561//yoUXXkhVVRXTpk3jhBNOoPWX1IgRI9i2bVvbMruXX345Rx99NBMnTqSxMTG7tbuldTds2MApp5zCuHHjGDduHC+88EKozyeSC+lqrxevW9ypPWjt9KA11lVznhuRTeitvy03f7IZx9t2/wiT1IOWz21dHbHViy++yIIFC3j22We5995721ZkvOWWW6ivrw8879tvv83VV1/NG2+8weDBg3nsscc6vJ9uad2DDjqI3/72t6xYsYKFCxfyne98p8efTSRX0tVYt3jwJi9hz1ssiq3mPEhkE3pv/LYMWj730EMP7dBnwoQJfP7znwcSy9pOnz4dgDFjxlBVVRV43pEjRzJ27FgAjj32WDZs2NDh/XRL6zY1NXH55ZdTWVnJ1KlTefPNN3v82URyJV2NdYmFSyeqOQ8vsgm9t35bti6fu3DhwrZk3V775Wozff7QfrGt0tLSTtvFpVta9+677+YLX/gCq1atoq6ujj179mT6MUR6Tbra66mjpnZqD1o7PWiNddWc50bxP9VL4+CBB7P5k82B7WGkLp/76aefpu371a9+lUWLFnH66afz5ptvsmbNmh5dM93Sujt37mT48OGUlJSwYMECmpube/qxRHKmq9rr6oOqi2Y99VwrtprzIJFN6NeNuy7wiXPY35apy+emDo+0d9VVVzFjxgyqqqqorq6mqqqK/fffP+trdrW07je/+U0WL17M6aefrs0spGh0tW56Ma2nnmvFvuZ6t2WLZnYI8CBwMNAC3O/uc1P6GDAXOBf4KzDT3Vd0dd5clC0Weh3i5uZmmpqaKC8v59133+XMM89k3bp19O/fP28xdEdli31P0P8XUDw7EcVNvvNQV2WLmST0CqDC3VeY2SCgHpji7m+263MucC2JhH4CMNfdT+jqvFGvQwfYtWsXp59+Ok1NTbg7//zP/8w555xT6LA6iNrPVMIJqpXOtBY8qvXhhVRs66F3O+Ti7puBzcnvd5nZW8AwoH3JxfnAg5747fCSmQ02s4rksbE1aNAgUn8piRRSUPVXas03JGrB8e7bWivHlNCDdVVtV4ifWVZVLmY2AqgGXk55axjQfoPPhmRb6vFXmFmdmdVt3bo18BqFmrkaR/pZ9j29URNdTHXWxabYatMzTuhmti/wGPBdd/8o9e2AQzplE3e/391r3L1m6NChnQ4oLy9n+/btSkQ54O5s376d8vLy7jtLbPRGTXQx1VkXm2KrTc+oysXMykgk84fd/ecBXRqAQ9q9Hg5syjaY4cOH09DQQLq7d8lOeXk5w4cPL3QYkkdB1V9hx9CLqc662PRWtV1PdZvQkxUsPwHecve70nR7ArjGzB4l8VB0Z0/Gz8vKyhg5cmS2h4lIUrpa6TBtGj9Pr9hq0zOpcvkq8EdgDYmyRYC/Bw4FcPf7kkn/HuBrJMoWZ7l7l08Lg6pcRESka2GrXJ4neIy8fR8Hru5ZeCIikguRnSkqIuHMeWkOi9ctpsVbKLESpo6ayuwTZ3fqV+gJfJmKSpy9SQldpA+a89IcFq79bKnoFm9pe90+qadOnGldphqKa+p+VOLsbZFdbVFEem7xusUZtUdhUweITpy9TQldpA9KtxlFanuxTZxJJypx9jYldJE+KN1mFKntxTZxJp2oxNnblNBF+qCpo6Zm1B6FTR0gOnH2Nj0UFemDWh98dlflUmwTZ9KJSpy9rduJRb1FE4tERLIXamKRiBSnOctmsnhbHS0kxk6nDqlh9uT5Ba0vD7p20LZ0QdfJVx15nOvVdYcuEkFzls1k4bY6aL+5uDtf+txQ3t2zrVP/aaOndVlfDuE3ZkitbW9lGN5u8dWg6+Rro4hCbEiRa13doeuhqEgELU5N5gBmvPtp8Eql+agvT1fb7ikraQddJ1915HGvV1dCF4mg4CryLvrnob48XW17JtfJVx153OvVldBFIijb/3HzUV+errY9k+vkq4487vXqSugiETR1SA2kPv9KjqEH9s9DfXm62nZLWaw16Dr5qiOPe726ErpIBM2ePJ9pQ2oocQd3StyZNqSGpRf9jmmjp7XdLZdYSacHopCo2679Si0VAyswjIqBFaEfDM4+cXbgte845Y5ur9Mb8QTJ13UKRVUuIiIRoioXkSK1fP1yJi6ZSNWCKiYumcjy9csLHZJEmCYWiRSI1vCWXNMdukiBxL0mWvJPCV2kQOJeEy35p4QuUiBxr4mW/FNCFymQuNdES/7poahIgWgNb8k1JXSRApp0+CQlcMkZDbmIFNLqRXD3GKgdnPh39aK+ce0AqskPT3foIoWyehH88jvQ1Jh4vfP9xGuAqgvje+0AqsnPDd2hixTKM7d/llBbNTUm2uN87QCqyc8NJXSRQtnZkF17XK4dQDX5uaGELlIo+w/Prj0u1w6gmvzcUEIXKZQzb4WyAR3bygYk2uN87QCqyc8NPRQVKZTWh4/P3J4Y6th/eCKh5uOhZCGvHUA1+bmh9dBFRCIk1HroZvaAmW0xs9fTvH+ame00s9eSX4X5m01EpI/LZMhlPnAP8GAXff7o7pNzEpFIlKxeFG7YIuh4yKwt3XWWXQ/188GbwUrh2Jks//KZnYYzQEMccZPRkIuZjQCWufuYgPdOA27INqFryEUiL3VyDiQeLH79XzNL6kHHl/ZPbP7c0vRZW0kZmEHznu6vs+x6qPtJh6blA/eh9qCD2E1LW1s/64eZ0dTuOuWl5bHaXzOu8rEF3UlmtsrMfmVmR+fonCLFLezknKDjm/d0TOaQeN0+mXd1nfr5nZrmHjC4QzIH2Ot7OyRz0ESeOMhFlcsK4DB3/9jMzgWWAkcEdTSzK4ArAA499NAcXFqkgMJOzgk7iSfoeG/u1PRBv9KMT6mJPNEW+g7d3T9y94+T3z8JlJnZkDR973f3GnevGTp0aNhLixRW2Mk5YSfxBB1vnZP3wXs7J/l0NJEn2kIndDM72Mws+f3xyXNuD3tekaIXdnJO0PGl/RNj5u2VlCXaM7nOsTM7NV33lx2Up/yv3s/6UZZyHU3kib5uh1zM7BHgNGCImTUAtwFlAO5+H3AB8HdmthdoBKZ7oYrbRfIp7OScdMdn2hZ0ncl3Jf5tV+Uy6aiLQFUufYImFomIREhXVS6a+i8StpY819cJ6vfeS51qyzn0xKKZut+V5euX6y+BPNEduvRtYWvJc32doH6UQErZYWB7b8QdUurGFaB697DyUYcuEk352ugh0+sE9QtM5gHtBdygIh1tXJFfSujSt+Vro4dMr9MbtekFpI0r8ksJXfq2fG30kOl1eqM2vYC0cUV+KaFL35avjR4yvU5Qv7T/m6a0F3CDinS0cUV+KaFL31Z1YeJB4v6HAJb4tzceLGZ6naB+3/h3qPnbz2aBWmni9Tf+vffjDmnS4ZOo/UotFQMrMIyKgRV6INqLVOUiIhIhqkOX+Mt1LfmC8+D//f6z1yPHQ/Ulmc/gDFiTPLBuPOj4dOcU6Ybu0CX6cl1LnprM2xjQ7v+XdOuUDz8++PiSUmhpt1BW0NrnQW1FWF8uhaM6dIm3XNeSByZz6JDMIf065emOb0lZ9TBo7fOgtiKsL5fipIQu0ZevWvJCitNnkV6jhC7Rl69a8kKK02eRXqOELtGX61rykePTvGEdX6Zbpzzd8SUpm08ErX0e1FaE9eVSnJTQJfpyXUs+44nOSXnkePjG/R2vMeVeOH9e5+vOeCK4bnzKfR37nj8vcY7u2vRAVDKkKhcRkQhRlYtIV1YvgrvHQO3gxL+rF+XnWJEc08Qi6dtSa9h3vp94Dd0Pc4Q5VqQX6A5d+rYwNez5WktdJENK6NK3halh7wv17xIpSujSt4WpYe8L9e8SKUro0reFqWHP11rqIhlSQpe+LUwNe77WUhfJkOrQRUQiRHXoIiJ9gOrQpW8J2ggDtKGExIISuvQdQROBHr+644YSmhwkEaYhF+k7giYCaUMJiREldOk7spnwo8lBEkFK6NJ3ZDPhR5ODJIKU0KXvCJoIpA0lJEaU0KXvCJoIpA0lJEZU5SJ9S9WFwclaCVxioNuEbmYPAJOBLe4+JuB9A+YC5wJ/BWa6+4pcByoxt+x6qJ8P3pzYsu3YmTD5rp73g+Ca80wTt+rVJYIyuUOfD9wDPJjm/XOAI5JfJwA/Sv4rkpll10PdTz577c2fvW6frDPtB7nfuGLpVWCWKHPM9nwiedLtGLq7/wH4sIsu5wMPesJLwGAzq8hVgNIH1M/PrD3TfpD7jStamj5L5tmeTyRPcvFQdBjwfrvXDcm2TszsCjOrM7O6rVu35uDSEgvenFl7pv2gdzauCNtXpJflIqFbQFvgEo7ufr+717h7zdChQ3NwaYkFK82sPdN+0DsbV4TtK9LLcpHQG4BD2r0eDmzKwXmlrzh2ZmbtmfaD3G9cUVKWqFnvyflE8iQXCf0J4DJLOBHY6e6bc3Be6Ssm3wU1f/vZnbaVJl6nPujMtB/kfuOKKfcmatZVry5FrNsNLszsEeA0YAjwZ+A2oAzA3e9Lli3eA3yNRNniLHfvducKbXAhIpK9rja46LZs0d0v6uZ9B67uYWwiIpIjmvovIhITSugiIjGhhC4iEhNK6CIiMaGELiISE0roIiIxoYQuIhITSugiIjGhhC4iEhNK6CIiMaGELiISE0roIiIxoYQuIhITSugiIjGhhC4iEhNK6CIiMaGELiISE0roIiIxoYQuIhITSugiIjGhhC4iEhNK6CIiMaGELiISE0roIiIx0a/QAUTF0pUbufOptWza0cgXBw/ge2ePZkr1sEKHJSLSRgk9A0tXbuTmn6+hsakZgI07Grn552sAlNRFpGhoyCUDdz61ti2Zt2psaubOp9YWKCIRkc6U0DOwaUdjVu0iIoWghJ6BLw4ekFW7iEghKKFn4Htnj2ZAWWmHtgFlpXzv7NEFikhEpDM9FM1A64NPVbmISDFTQs/QlOphSuAiUtQyGnIxs6+Z2Voze8fMbgp4/zQz22lmryW/bs19qMVp6cqNnPz9Zxl503JO/v6zLF25sdAhiUgf1e0dupmVAvOACUAD8KqZPeHub6Z0/aO7T+6FGIuW6tNFpJhkcod+PPCOu6939z3Ao8D5vRtWNKg+XUSKSSYJfRjwfrvXDcm2VCeZ2Soz+5WZHR10IjO7wszqzKxu69atPQi3uKg+XUSKSSYJ3QLaPOX1CuAwdz8G+DdgadCJ3P1+d69x95qhQ4dmFWgxUn26iBSTTBJ6A3BIu9fDgU3tO7j7R+7+cfL7J4EyMxuSsyiLlOrTRaSYZJLQXwWOMLORZtYfmA480b6DmR1sZpb8/vjkebfnOthiM6V6GHd8o5JhgwdgwLDBA7jjG5V6ICoiBdFtlYu77zWza4CngFLgAXd/w8yuTL5/H3AB8HdmthdoBKa7e+qwTCypPl1EioUVKu/W1NR4XV1dQa7dndlL1/DIy+/T7E6pGRedcAg1h31eM0VFpODMrN7da4Le00zRFLOXruGhl95re93szkMvvcfPXn6PluTvPtWbi0gx0uJcKR55+f3A9paUP2RUby4ixUYJPUVzFkNQqjcXkWKihJ6i1ILK7oOp3lxEiokSeoqLTjgksL0kJc+r3lxEio0Seoo5Uyq55MRD2+7US8245MRDuevCsao3F5GiprJFEZEIUdli0tKVGzvVki+ue4//evfDtj4nf+nzPHz5SaHOqTt3ESmEPnOHnrp2OSTGxVPLESHzpB50zgFlpRqOEZFe09Udep8ZQw9auzwomQMd7tizPafq00WkUPpMQu+NmnGthy4ixaTPJPTeqBnXeugiUkz6TEIPWrs8tba81clf+nyPz6n6dBEplD6T0IPWLr/rwrGdknc2VS5aD11EikmfqXIREYkDVbmIiPQBkZpYFHYSz8U/frHTJKL6DX9hd/Nnf6WUlyYG1lPbDjlwH97e8klb2xEHDeS315+WcUyagCQivS0yQy5hJ/GkJvNc+MKg/ny0u7nbmDQBSURyJRZDLmEn8eQ6mQP8edeejGLSBCQRyYfIJPQoTeJJjSlKsYtIdEUmoUdpEk9qTFGKXUSiKzIJPewknkwnC2XjC4P6ZxSTJiCJSD5EJqGHncTz8OUnBU4iaq1qaVVeaoFtRxw0sEPbEQcN5OX/OyGjmDQBSUTyITJVLiIi0gc2uAhT4z176Roeefl9mt0pNWvbUzS1bc6Uyt78CCIioUU+oafWeG/c0cjNP18D0G1Sn710DQ+99F7b62b3Dq9T25TURaSYRWYMPZ0wNd6PvPx+xtfJpq+ISCFEPqGHqfFuzuL5QTZ9RUQKIfIJPUyNd6mlWRA9ZF8RkUKIfEIPU+Pd+gA0E9n0FREphMg/FG198NmTKpfWh5yqchGROFAduohIhIRebdHMvmZma83sHTO7KeB9M7N/Tb6/2szGhQ1aRESy021CN7NSYB5wDvBl4CIz+3JKt3OAI5JfVwA/ynGcIiLSjUzu0I8H3nH39e6+B3gUOD+lz/nAg57wEjDYzCpyHKuIiHQhk4Q+DGg/q6Yh2ZZtH8zsCjOrM7O6rVu3ZhuriIh0IZOEHlSAnfokNZM+uPv97l7j7jVDhw7NJD4REclQJmWLDUD7IuzhwKYe9Omgvr5+m5n9dyZBBhgCbOvhscVIn6d4xemzQLw+T5w+C2T+eQ5L90YmCf1V4AgzGwlsBKYD/zOlzxPANWb2KHACsNPdN3d1Unfv8S26mdWlK9uJIn2e4hWnzwLx+jxx+iyQm8/TbUJ3971mdg3wFFAKPODub5jZlcn37wOeBM4F3gH+CswKE5SIiGQvo5mi7v4kiaTdvu2+dt87cHVuQxMRkWxEdS2X+wsdQI7p8xSvOH0WiNfnidNngRx8noJN/RcRkdyK6h26iIikUEIXEYmJSCV0M3vAzLaY2euFjiUXzOwQM/udmb1lZm+Y2XWFjqmnzKzczF4xs1XJz/IPhY4pLDMrNbOVZras0LGEZWYbzGyNmb1mZpFf5tTMBpvZEjP7U/L/n5MKHVNPmdno5H+X1q+PzOy7PTpXlMbQzexU4GMS68aMKXQ8YSXXu6lw9xVmNgioB6a4+5sFDi1rZmbAQHf/2MzKgOeB65Jr+0SSmV0P1AD7ufvkQscThpltAGrcPRYTccxsAfBHd/8PM+sP7OPuOwocVmjJxRA3Aie4e9YTLyN1h+7ufwA+LHQcueLum919RfL7XcBbBKyBEwXJhdk+Tr4sS35F524hhZkNByYB/1HoWKQjM9sPOBX4CYC774lDMk86E3i3J8kcIpbQ48zMRgDVwMsFDqXHkkMUrwFbgN+6e2Q/C/BD4P8ALQWOI1cc+I2Z1ZvZFYUOJqTDga3AT5NDYv9hZgMLHVSOTAce6enBSuhFwMz2BR4DvuvuHxU6np5y92Z3H0tiLZ/jzSySw2JmNhnY4u71hY4lh05293Ek9i64Ojl8GVX9gHHAj9y9GvgE6LTxTtQkh47OAxb39BxK6AWWHG9+DHjY3X9e6HhyIfnn73PA1wobSY+dDJyXHHd+FDjDzB4qbEjhuPum5L9bgF+Q2OcgqhqAhnZ/AS4hkeCj7hxghbv/uacnUEIvoOSDxJ8Ab7n7XYWOJwwzG2pmg5PfDwDOAv5U0KB6yN1vdvfh7j6CxJ/Az7r7JQUOq8fMbGDyoTvJoYmJQGQrxdz9A+B9MxudbDoTiFwhQYCLCDHcAhmu5VIszOwR4DRgiJk1ALe5+08KG1UoJwOXAmuSY88Af59cOydqKoAFyaf0JcAid498uV9MfAH4ReL+gX7Az9z914UNKbRrgYeTwxTrifiCgGa2DzAB+Hao80SpbFFERNLTkIuISEwooYuIxIQSuohITCihi4jEhBK6iEhMKKGLiMSEErqISEz8fxmlpxXIG7l+AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "\n",
    "iris_data = load_iris()\n",
    "x = iris_data['data'][:,2:]\n",
    "y = iris_data['target']\n",
    "\n",
    "x_train,x_test,y_train,y_test = train_test_split(x,y,test_size = 0.2,random_state = 1)\n",
    "\n",
    "dataframe = pd.DataFrame(x_train)\n",
    "dataframe['y'] = y_train\n",
    "plt.scatter(dataframe.loc[dataframe['y'] == 0][0],dataframe.loc[dataframe['y'] == 0][1],label=iris_data['target_names'][0])\n",
    "plt.scatter(dataframe.loc[dataframe['y'] == 1][0],dataframe.loc[dataframe['y'] == 1][1],label=iris_data['target_names'][1])\n",
    "plt.scatter(dataframe.loc[dataframe['y'] == 2][0],dataframe.loc[dataframe['y'] == 2][1],label=iris_data['target_names'][2])\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在建立k-近邻分类模型之前，我们需要考虑一个问题：k 应该取多少？\n",
    "\n",
    "也许我们可以进行多次实验，分别赋予 k 不同的值，可是这样会给人一种为了达到测试集上最大正确性而去调节参数以“适应”测试集的感觉。测试集更像是“期末测验”，我们建立的模型应当不知道测试集的具体数据，只有模型训练完毕后才能将测试集输入模型，以检验模型的准确性和泛化能力。\n",
    "\n",
    "实际上在训练集和测试集的基础上我们还要再建立一个**验证集**，验证集是模型训练过程中单独留出的样本集，它可以用于调整模型的超参数和用于对模型的能力进行初步评估。\n",
    "\n",
    "对于小规模数据（万级别以下），训练集、验证集和测试集的比例建议为6:2:2；而对于大规模数据，比例建议为98:1:1.\n",
    "\n",
    "我们常用的方法是k折交叉验证：将原始训练集数据分为k（注意这里的k与k-近邻的k不是一个含义!）组（一般是均分），将每个子集数据分别做一次验证集，其余的k-1组子集数据作为新训练集，这样会得到k个模型，用这k个模型的验证集的分类准确率的平均数作为模型的性能指标，进而选择较适合的超参数。\n",
    "\n",
    "![VaildSet](img/Lab12-1-2.jpg)\n",
    "\n",
    "Scikit-Learn库中提供了交叉验证方法帮助我们确定较合适的超参数，现在我们确定一下较合适的k值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 0.95\n",
      "5 0.9583333333333334\n",
      "7 0.9666666666666668\n",
      "9 0.9666666666666668\n",
      "11 0.9666666666666668\n",
      "13 0.9666666666666668\n",
      "15 0.9666666666666668\n",
      "17 0.9666666666666668\n",
      "19 0.9583333333333334\n"
     ]
    }
   ],
   "source": [
    "from sklearn.model_selection import cross_val_score\n",
    "\n",
    "for k in range(3,20,2):\n",
    "    model = KNeighborsClassifier(n_neighbors=k)\n",
    "    scores = cross_val_score(model,x_train,y_train)\n",
    "    print(k,scores.mean())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们看到k取7较为合适，现在我们建立一个7-近邻分类模型，并在测试集上进行测试。我们使用传统的正确率作为评测指标：模型对测试数据的预测标签与实际标签相同则记为成功预测。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9666666666666667\n"
     ]
    }
   ],
   "source": [
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "model = KNeighborsClassifier(n_neighbors=7)\n",
    "model.fit(x_train,y_train)\n",
    "y_pre = model.predict(x_test)\n",
    "acc_score = accuracy_score(y_test,y_pre)\n",
    "print(acc_score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到对测试集的数据分类准确率为96.67%"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* ### 进一步改进"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们看到传统k-近邻算法中每个邻居无论远近，投票权重均相同，这样会造成一个问题，如图所示，直观来说Y点应属于红色类别，但是Y点的k-近邻中蓝色点居多，算法将其标记为蓝色类别。这样当样本分布不均衡时新的未知样本容易被归类为数量过大的主导样本。\n",
    "\n",
    "我们可以考虑未知样本与近邻点的距离，根据距离远近设定权重，再统计各类别的权重和进行分类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实验12-2 决策树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "机器学习中，决策树（Decision tree）是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。\n",
    "\n",
    "例如判断一个西瓜质量的好坏，我们从多个特征确定：\n",
    "\n",
    "![Watermelon](img/Lab12-2-1.jpg)\n",
    "\n",
    "分裂条件不仅可以是离散值，也可以是连续值，例如直径小于某个值时生成一个叶子节点。\n",
    "\n",
    "在不加限制的情况下，一棵决策树会生长到衡量不纯度的指标最优，或者没有更多的特征可用为止。这样的决策树往往会过拟合，这就是说，它会在训练集上表现很好，在测试集上却表现糟糕。我们收集的样本数据不可能和整体的状况完全一致，因此当一棵决策树对训练数据有了过于优秀的解释性，它找出的规则必然包含了训练样本中的噪声，并使它对未知数据的拟合程度不足。\n",
    "\n",
    "为了让决策树有更好的泛化性，我们要对决策树进行剪枝。剪枝策略对决策树的影响巨大，正确的剪枝策略是优化决策树算法的核心。在这里我们采取预剪枝策略，限制决策树的最大深度，最大深度一般大于等于3而小于等于特征数量。\n",
    "\n",
    "现在我们再利用鸢尾花数据集，利用四个特征对鸢尾花进行三分类。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 0.9333333333333333\n",
      "4 0.9416666666666668\n"
     ]
    }
   ],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split,cross_val_score\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "iris_data = load_iris()\n",
    "x = iris_data['data']\n",
    "y = iris_data['target']\n",
    "\n",
    "x_train,x_test,y_train,y_test = train_test_split(x,y,test_size = 0.2,random_state = 1)\n",
    "\n",
    "for k in range(3,len(iris_data['feature_names'])+1):\n",
    "    model = DecisionTreeClassifier(max_depth=k)\n",
    "    scores = cross_val_score(model,x_train,y_train)\n",
    "    print(k,scores.mean())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9666666666666667\n"
     ]
    }
   ],
   "source": [
    "model = DecisionTreeClassifier(max_depth=3)\n",
    "model.fit(x_train,y_train)\n",
    "y_pre = model.predict(x_test)\n",
    "acc_score = accuracy_score(y_test,y_pre)\n",
    "print(acc_score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以使用Graphviz工具可视化刚才生成的决策树！\n",
    "\n",
    "Windows用户请首先[按此](https://www2.graphviz.org/Packages/stable/windows/10/cmake/Release/x64/graphviz-install-2.44.1-win64.exe)下载并安装Graphviz，安装时注意请**勾选添加系统变量**。\n",
    "\n",
    "MacOS用户请参考[这个网页](https://graphviz.org/download/)进行安装。\n",
    "\n",
    "然后请在Anaconda Powershell Prompt命令行中输入\n",
    "\n",
    "`conda install graphviz`\n",
    "\n",
    "`conda install pydotplus`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pydotplus\n",
    "from sklearn import tree\n",
    "\n",
    "dot_data = tree.export_graphviz(model, out_file=None) \n",
    "graph = pydotplus.graph_from_dot_data(dot_data) \n",
    "graph.write_pdf(\"iris.pdf\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "生成的可视化决策树存放于PDF文件中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实验练习12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "互联网中充斥着大量钓鱼欺诈类网站。这类非法网站通常试图掩人耳目、充当正规网站，而实际上却是在窃取用户的身份、密码、交易等重要信息。\n",
    "\n",
    "![Web](img/Lab12-E-1.jpg)\n",
    "\n",
    "机器学习在信息安全领域中的一个重要应用就是用来识别这些钓鱼网站。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`fraudulent.csv`文件中含有10,086条数据，每条数据含有18个特征以及1个标签。各个特征的含义如下：\n",
    "\n",
    "1. contain_IP：网址中是否包涵ip，比如`http://121.99.3.123/fake.html` 包含ip。1表示包含，0表示不包含；\n",
    "2. is_long：网址字符是否过长。1表示网址过长，0表示网址不长；\n",
    "3. is_tinyurl：网址是否是短网址。比如`https://bit.ly/2kXX6jV` 就是短网址。1表示是短网址，0表示不是；\n",
    "4. contain_at：网址是否包含“@”符号。1表示包含，0表示不包含；\n",
    "5. contain_double_slash：网址是否包含“//”符号，该符号用来表示网址跳转。1表示包含，0表示不包含；\n",
    "6. contain_dash：网址是否包含“-”符号，该符号经常帮助用来伪装真网站，比如`www.my-taobao.com` 。 1表示包含，0表示不包含；\n",
    "7. contain_subdomain：网址是否包含子域名，比如`www.ecnu.edu.cn` 就包含edu和cn子域名。1表示包含，0表示不包含；\n",
    "8. is_SSL：网址是否是https安全链接。1表示包含，0表示不包含；\n",
    "9. with_long_history：网址所属的主域名存在的时间。1表示长久，0表示不长久；\n",
    "10. contain_icon：网址网页是否有小图标。1表示包含，0表示不包含；\n",
    "11. contain_ext_domain：该网页是否加载其他域名下的附件或者网页。1表示包含，0表示不包含；\n",
    "12. contain_email_to：该网页是否包含发送邮件的组件。1表示包含，0表示不包含；\n",
    "13. allow_right_click：该网页是否允许用户进行右击操作。1表示允许，0表示不允许；\n",
    "14. contain_pop_up_windowL：该网页是否包含弹窗。1表示包含，0表示不包含；\n",
    "15. contain_Iframe：该网页是否包含Iframe（嵌套网页）。1表示包含，0表示不包含；\n",
    "16. has_DNSRecord：网址是否有DNS记录。1表示有，0表示无；\n",
    "17. traffic：该网站的流量大小。1表示大，0表示小；\n",
    "18. google_rank：该网址在google搜索中的排名。1表示高于同类网站的平均排名，0表示低于同类网站的平均排名；\n",
    "* **y：表示网站是否是钓鱼欺诈网站，1表示是，0表示不是。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "原始数据中含有大量缺失值，请自行处理这些缺失值（可以剔除缺失值过多的列或者使用众数填充等方法）。\n",
    "\n",
    "将原始数据分为训练集、测试集（随机种子请设置为1）（若有需要可以将训练集进一步分为训练集和验证集）。\n",
    "\n",
    "现在请建立一个二分类模型，使用训练集训练模型，再使用测试集测试模型。\n",
    "\n",
    "评估指标为F1值（[详细解释](https://blog.csdn.net/xiaodongxiexie/article/details/67009112)）\n",
    "\n",
    "分类模型可采用：k-近邻、决策树、逻辑回归、支持向量机等。\n",
    "\n",
    "可以与周围同学比较一下F1值的大小（越接近1越好），看看谁的数据预处理和分类模型更强。"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}