lab3a.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 3a: Intro to Machine Learning and  Scikit-learn\n",
    "\n",
    "## Overview\n",
    "\n",
    "* [Part 1: What is machine learning, and how does it work?](#Part-1:-What-is-machine-learning,-and-how-does-it-work?)\n",
    "* [Part 2: Machine learning using scikit-learn](#Part-2:-Machine-learning-using-scikit-learn)\n",
    "* [Part 3: Getting started in scikit-learn with the famous iris dataset](#Part-3:-Getting-started-in-scikit-learn-with-the-famous-iris-dataset)\n",
    "* [Part 4: Training a machine learning model with scikit-learn](#Part-4:-Training-a-machine-learning-model-with-scikit-learn)\n",
    "* [Part 5: Comparing machine learning models in scikit-learn](#Part-5:-Comparing-machine-learning-models-in-scikit-learn)\n",
    "\n",
    "\n",
    "## Part 1: What is machine learning, and how does it work?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Machine learning](images/01_robot.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Agenda\n",
    "\n",
    "- What is machine learning?\n",
    "- What are the two main categories of machine learning?\n",
    "- What are some examples of machine learning?\n",
    "- How does machine learning \"work\"?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 What is machine learning?\n",
    "\n",
    "One definition: \"Machine learning is the semi-automated extraction of knowledge from data\"\n",
    "\n",
    "- **Knowledge from data**: Starts with a question that might be answerable using data\n",
    "- **Automated extraction**: A computer provides the insight\n",
    "- **Semi-automated**: Requires additional decisions by a human"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 What are the two main categories of machine learning?\n",
    "\n",
    "**1. Supervised learning**: Making predictions using data\n",
    "    \n",
    "- Example: Is a given email \"spam\" or \"ham\"?\n",
    "- There is an outcome we are trying to predict\n",
    "- Uses preexisting examples to try and learn the task"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Spam filter](images/01_spam_filter.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Unsupervised learning**: Extracting structure from data\n",
    "\n",
    "- Example: Segment grocery store shoppers into clusters that exhibit similar behaviors\n",
    "- There is no \"right answer\"\n",
    "- Subsequent study of the segment's behavior may lead to valuable insights and even predictive models based on segment membership"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Clustering](images/01_clustering.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 How does machine learning \"work\"?\n",
    "\n",
    "High-level steps of supervised learning:\n",
    "\n",
    "1. First, train a **machine learning model** using **labeled data**\n",
    "\n",
    "    - *Labeled data* has been labeled with the outcome\n",
    "    - *Machine learning model* learns the relationship between the attributes of the data and its outcome\n",
    "\n",
    "2. Then, make **predictions** on **new data** for which the label is unknown"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Supervised learning](images/01_supervised_learning.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The primary goal of supervised learning is to build a model that \"generalizes\" it's responses, in that it should accurately predict labels given new unlabeled data. In terms of forecasting, it should accurately predict the **future** rather than just the **past**!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Questions about machine learning\n",
    "\n",
    "- How do I choose **which attributes** of my data to include in the model?\n",
    "- How do I choose **which model** to use?\n",
    "- How do I **optimize** this model for best performance?\n",
    "- How do I ensure that I'm building a model that will **generalize** to unseen data?\n",
    "- Can I **estimate** how well my model is likely to perform on unseen data?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Resources\n",
    "\n",
    "- Book: [An Introduction to Statistical Learning](http://www-bcf.usc.edu/~gareth/ISL/) (section 2.1, 14 pages)\n",
    "- Video: [Learning Paradigms](http://work.caltech.edu/library/014.html) (13 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Machine learning using scikit-learn "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![scikit-learn logo](images/02_sklearn_logo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Agenda\n",
    "\n",
    "- What are the benefits and drawbacks of scikit-learn?\n",
    "- How is scikit-learn organized? \n",
    "- What methods should be used for a particular problem?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Benefits and drawbacks of scikit-learn\n",
    "\n",
    "#### Benefits:\n",
    "\n",
    "- **Consistent interface** to machine learning models\n",
    "- Provides many **tuning parameters** but with **sensible defaults**\n",
    "- Exceptional **documentation**\n",
    "- Rich set of functionality for **companion tasks**\n",
    "- **Active community** for development and support\n",
    "\n",
    "#### Potential drawbacks:\n",
    "\n",
    "- Harder (than R) to **get started with machine learning**\n",
    "- Less emphasis (than R) on **model interpretability**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 How is scikit-learn organized?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generally, software in scikit-learn is organized into six categories:\n",
    "\n",
    "[![scikit-learn homepage](images/6_categories.png)](http://scikit-learn.org/stable/index.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 What methods should be used for a particular problem? \n",
    "Often the hardest part of solving a machine learning problem can be finding the right estimator for the job, particularly for new practioners. <br>\n",
    "The flowchart below is designed to give users a bit of a rough guide on how to approach problems with regard to which estimators to try on your data. <br>\n",
    "\n",
    "__Task 1:__ Click on this graph to view the chart in a more interactive way on the sklearn website.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![scikit-learn algorithm map](images/02_sklearn_algorithms.png)](http://scikit-learn.org/stable/tutorial/machine_learning_map/index.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 3: Getting started in scikit-learn with the famous iris dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Agenda\n",
    "\n",
    "- What is the famous iris dataset, and how does it relate to machine learning?\n",
    "- How do we load the iris dataset into scikit-learn?\n",
    "- How do we describe a dataset using machine learning terminology?\n",
    "- What are scikit-learn's four key requirements for working with data?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Introducing the iris dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Iris](images/03_iris.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 50 samples of 3 different species of iris (150 samples total)\n",
    "- Measurements: sepal length, sepal width, petal length, petal width\n",
    "- The data in plain text looks like the following:\n",
    "```\n",
    "5.1,3.5,1.4,0.2,Iris-setosa\n",
    "4.9,3.0,1.4,0.2,Iris-setosa\n",
    "4.7,3.2,1.3,0.2,Iris-setosa\n",
    "4.6,3.1,1.5,0.2,Iris-setosa\n",
    "5.0,3.6,1.4,0.2,Iris-setosa\n",
    "5.4,3.9,1.7,0.4,Iris-setosa\n",
    "...\n",
    "6.2,2.9,4.3,1.3,Iris-versicolor\n",
    "5.1,2.5,3.0,1.1,Iris-versicolor\n",
    "5.7,2.8,4.1,1.3,Iris-versicolor\n",
    "...\n",
    "6.3,3.3,6.0,2.5,Iris-virginica\n",
    "5.8,2.7,5.1,1.9,Iris-virginica\n",
    "7.1,3.0,5.9,2.1,Iris-virginica\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Machine learning on the iris dataset\n",
    "\n",
    "- Framed as a **supervised learning** problem: Predict the species of an iris using the measurements\n",
    "- Famous dataset for machine learning because prediction is **easy**\n",
    "- Learn more about the iris dataset: [UCI Machine Learning Repository](http://archive.ics.uci.edu/ml/datasets/Iris)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Loading the scikit-learn iris dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scikit includes a number of example datasets, stored in a scikit friendly format. More details on this format, are located [here](http://scikit-learn.org/stable/datasets/index.html).  Below is some code to load sklearn's version of the iris dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# import load_iris function from datasets module\n",
    "from sklearn.datasets import load_iris\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sklearn.datasets.base.Bunch"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# save an \"sklearn.datasets.base.Bunch\" object containing iris dataset and its attributes\n",
    "iris = load_iris()\n",
    "type(iris)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.1</td>\n",
       "      <td>3.5</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4.7</td>\n",
       "      <td>3.2</td>\n",
       "      <td>1.3</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4.6</td>\n",
       "      <td>3.1</td>\n",
       "      <td>1.5</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.0</td>\n",
       "      <td>3.6</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     0    1    2    3\n",
       "0  5.1  3.5  1.4  0.2\n",
       "1  4.9  3.0  1.4  0.2\n",
       "2  4.7  3.2  1.3  0.2\n",
       "3  4.6  3.1  1.5  0.2\n",
       "4  5.0  3.6  1.4  0.2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# print 5 rows of iris data\n",
    "pd.DataFrame(iris.data).head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Machine learning terminology\n",
    "\n",
    "- Each data row is an **observation** (also known as: sample, example, instance, record)\n",
    "- Each data column is a **feature** (also known as: predictor, attribute, independent variable, input, regressor, covariate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']\n"
     ]
    }
   ],
   "source": [
    "# print the names of the four features\n",
    "print(iris.feature_names)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Each value we are predicting is the **response** (also known as: target, outcome, label, dependent variable)\n",
    "- **Classification** is supervised learning in which the response is categorical (as is in the iris data set, where the **response** is the iris variety, of which there are only three.)\n",
    "- **Regression** is supervised learning in which the response is ordered and continuous (e.g. prediction of stock prices, cholesterol levels, swimming speed, etc.)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n",
      " 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2\n",
      " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\n",
      " 2 2]\n"
     ]
    }
   ],
   "source": [
    "# print integers representing the species of each observation\n",
    "print(iris.target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['setosa' 'versicolor' 'virginica']\n"
     ]
    }
   ],
   "source": [
    "# print the encoding scheme for species: 0 = setosa, 1 = versicolor, 2 = virginica\n",
    "print(iris.target_names)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 Requirements for working with data in scikit-learn\n",
    "\n",
    "1. Features and response are **separate objects**\n",
    "2. Features and response should be **numeric**\n",
    "3. Features and response should be **NumPy arrays**\n",
    "4. Features and response should have **specific shapes**, i.e., for each row of features there should be a corresponding response row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'numpy.ndarray'>\n",
      "<class 'numpy.ndarray'>\n"
     ]
    }
   ],
   "source": [
    "# check the types of the features and response\n",
    "print(type(iris.data))\n",
    "print(type(iris.target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(150, 4)\n"
     ]
    }
   ],
   "source": [
    "# check the shape of the features (first dimension = number of observations, second dimensions = number of features)\n",
    "print(iris.data.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(150,)\n"
     ]
    }
   ],
   "source": [
    "# check the shape of the response (single dimension matching the number of observations)\n",
    "print(iris.target.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Task 2:__ Store the feature data in the variable X and the target labels in the variable y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# store feature matrix in \"X\"\n",
    "X = iris.data\n",
    "\n",
    "# store response vector in \"y\"\n",
    "y = iris.target\n",
    "\n",
    "# Test cases\n",
    "assert (150, 4) == X.shape\n",
    "assert (150,) == y.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.6 Resources\n",
    "\n",
    "- scikit-learn documentation: [Dataset loading utilities](http://scikit-learn.org/stable/datasets/)\n",
    "- Jake VanderPlas: Fast Numerical Computing with NumPy ([slides](https://speakerdeck.com/jakevdp/losing-your-loops-fast-numerical-computing-with-numpy-pycon-2015), [video](https://www.youtube.com/watch?v=EEUXKG97YRw))\n",
    "- Scott Shell: [An Introduction to NumPy](http://www.engr.ucsb.edu/~shell/che210d/numpy.pdf) (PDF)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 4: Training a machine learning model with scikit-learn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Agenda\n",
    "\n",
    "- What is the **K-nearest neighbors** classification model?\n",
    "- What are the four steps for **model training and prediction** in scikit-learn?\n",
    "- How can I apply this pattern to **other machine learning models**?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 K-nearest neighbors (KNN) classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Pick a value for K.\n",
    "2. Search for the K observations in the training data that are \"nearest\" to the measurements of the unknown iris.\n",
    "3. Use the most popular response value from the K nearest neighbors as the predicted response value for the unknown iris."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Example training data \n",
    "**Note:** The data displayed below wil be used to illustrate KNN classicification, it is not from the IRIS data set, we will return to that shortly.\n",
    "\n",
    "Initially there are 60 points in each class。 Each point's color indicates its class. So, for this problem the **features** are (x,y) points and **labels** are point colors. \n",
    "\n",
    "![Training data](images/04_knn_dataset.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### KNN classification map (K=1)\n",
    "The figure below shows the 1NN classification map: each pixel is classified by 1NN using all the data.<br>\n",
    "The color of an area designates how points that land in that area are classified.\n",
    "\n",
    "![1NN classification map](images/04_1nn_map.png)\n",
    "\n",
    "The small islands are from isolated training points whose labels differ from points that surround it.  They have this effect when K=1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### KNN classification map (K=5)\n",
    "\n",
    "The 5NN classification map is shown below. White areas correspond to the unclassified regions, where 5NN voting is tied (for example, if there are two green, two red and one blue points among 5 nearest neighbors).\n",
    "\n",
    "![5NN classification map](images/04_5nn_map.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "*Image Credits: [Data3classes](http://commons.wikimedia.org/wiki/File:Data3classes.png#/media/File:Data3classes.png), [Map1NN](http://commons.wikimedia.org/wiki/File:Map1NN.png#/media/File:Map1NN.png), [Map5NN](http://commons.wikimedia.org/wiki/File:Map5NN.png#/media/File:Map5NN.png) by Agor153. Licensed under CC BY-SA 3.0*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Reviewing the iris dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iris Plants Database\n",
      "====================\n",
      "\n",
      "Notes\n",
      "-----\n",
      "Data Set Characteristics:\n",
      "    :Number of Instances: 150 (50 in each of three classes)\n",
      "    :Number of Attributes: 4 numeric, predictive attributes and the class\n",
      "    :Attribute Information:\n",
      "        - sepal length in cm\n",
      "        - sepal width in cm\n",
      "        - petal length in cm\n",
      "        - petal width in cm\n",
      "        - class:\n",
      "                - Iris-Setosa\n",
      "                - Iris-Versicolour\n",
      "                - Iris-Virginica\n",
      "    :Summary Statistics:\n",
      "\n",
      "    ============== ==== ==== ======= ===== ====================\n",
      "                    Min  Max   Mean    SD   Class Correlation\n",
      "    ============== ==== ==== ======= ===== ====================\n",
      "    sepal length:   4.3  7.9   5.84   0.83    0.7826\n",
      "    sepal width:    2.0  4.4   3.05   0.43   -0.4194\n",
      "    petal length:   1.0  6.9   3.76   1.76    0.9490  (high!)\n",
      "    petal width:    0.1  2.5   1.20  0.76     0.9565  (high!)\n",
      "    ============== ==== ==== ======= ===== ====================\n",
      "\n",
      "    :Missing Attribute Values: None\n",
      "    :Class Distribution: 33.3% for each of 3 classes.\n",
      "    :Creator: R.A. Fisher\n",
      "    :Donor: Michael Marshall (MARSHALL%PLU@io.arc.nasa.gov)\n",
      "    :Date: July, 1988\n",
      "\n",
      "This is a copy of UCI ML iris datasets.\n",
      "http://archive.ics.uci.edu/ml/datasets/Iris\n",
      "\n",
      "The famous Iris database, first used by Sir R.A Fisher\n",
      "\n",
      "This is perhaps the best known database to be found in the\n",
      "pattern recognition literature.  Fisher's paper is a classic in the field and\n",
      "is referenced frequently to this day.  (See Duda & Hart, for example.)  The\n",
      "data set contains 3 classes of 50 instances each, where each class refers to a\n",
      "type of iris plant.  One class is linearly separable from the other 2; the\n",
      "latter are NOT linearly separable from each other.\n",
      "\n",
      "References\n",
      "----------\n",
      "   - Fisher,R.A. \"The use of multiple measurements in taxonomic problems\"\n",
      "     Annual Eugenics, 7, Part II, 179-188 (1936); also in \"Contributions to\n",
      "     Mathematical Statistics\" (John Wiley, NY, 1950).\n",
      "   - Duda,R.O., & Hart,P.E. (1973) Pattern Classification and Scene Analysis.\n",
      "     (Q327.D83) John Wiley & Sons.  ISBN 0-471-22361-1.  See page 218.\n",
      "   - Dasarathy, B.V. (1980) \"Nosing Around the Neighborhood: A New System\n",
      "     Structure and Classification Rule for Recognition in Partially Exposed\n",
      "     Environments\".  IEEE Transactions on Pattern Analysis and Machine\n",
      "     Intelligence, Vol. PAMI-2, No. 1, 67-71.\n",
      "   - Gates, G.W. (1972) \"The Reduced Nearest Neighbor Rule\".  IEEE Transactions\n",
      "     on Information Theory, May 1972, 431-433.\n",
      "   - See also: 1988 MLC Proceedings, 54-64.  Cheeseman et al\"s AUTOCLASS II\n",
      "     conceptual clustering system finds 3 classes in the data.\n",
      "   - Many, many more ...\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# print out the description of the iris dataset\n",
    "print(iris.DESCR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 150 **observations**\n",
    "- 4 **features** (sepal length, sepal width, petal length, petal width)\n",
    "- **Response** variable is the iris species\n",
    "- **Classification** problem since response is categorical\n",
    "- More information in the [UCI Machine Learning Repository](http://archive.ics.uci.edu/ml/datasets/Iris)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(150, 4)\n",
      "(150,)\n"
     ]
    }
   ],
   "source": [
    "# print the shapes of X and y\n",
    "print(X.shape)\n",
    "print(y.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4  scikit-learn 4-step modeling pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 1:** Import the estimator class you plan to use"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 2:** \"Instantiate\" the \"estimator\"\n",
    "\n",
    "- \"Estimator\" is scikit-learn's term for model\n",
    "- \"Instantiate\" means \"make an instance of\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "knn = KNeighborsClassifier(n_neighbors=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Name of the object does not matter\n",
    "- Can specify tuning parameters (aka \"hyperparameters\") during this step\n",
    "- All parameters not specified are set to their defaults"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
      "           metric_params=None, n_jobs=1, n_neighbors=1, p=2,\n",
      "           weights='uniform')\n"
     ]
    }
   ],
   "source": [
    "print(knn) # here you can see the parameters and their current settings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 3:** Fit the model with data (aka \"model training\")\n",
    "\n",
    "- Model is learning the relationship between X and y\n",
    "- Occurs *in-place*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
       "           metric_params=None, n_jobs=1, n_neighbors=1, p=2,\n",
       "           weights='uniform')"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn.fit(X, y)  # Fit tries to determine a relationship between X and y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 4:** Predict the response for a new observation\n",
    "\n",
    "- New observations are called \"out-of-sample\" data\n",
    "- Uses the information it learned during the model training process"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn.predict([[3, 5, 4, 2]])  # Predict uses the relationship found by fit and applies it to new X value(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Returns a NumPy array\n",
    "- Can predict for multiple observations at once"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2, 1])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_new = [[3, 5, 4, 2], [5, 4, 3, 2]]\n",
    "knn.predict(X_new)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.5 Using a different value for K\n",
    "\n",
    "__Task 3:__ Fit a k-nearest neighbors to the training data (`X`, and `y`) use it to predict the response of `X_new`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2, 1])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# instantiate the model (using the value K=5 instead of K=1)\n",
    "knn_new = KNeighborsClassifier(n_neighbors=1)\n",
    "\n",
    "# fit the model with data\n",
    "knn_new.fit(X, y)\n",
    "\n",
    "# predict the response for new observations\n",
    "knn_new.predict(X_new)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.6 Using a different classification model\n",
    "__Task 4:__ We have the first two steps given to you when applying this pattern to another machine learning model -- Logistic Regression (aka logit, MaxEnt) classifier. \n",
    "\n",
    "Please fill in the next two steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2, 0])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# import the class\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "# Note: despite it's name LogisticRegression is used for classification\n",
    "\n",
    "# instantiate the model (using the default parameters)\n",
    "logreg = LogisticRegression()\n",
    "\n",
    "# fit the model with data\n",
    "logreg.fit(X, y)\n",
    "\n",
    "# predict the response for new observations\n",
    "logreg.predict(X_new)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.7 Resources\n",
    "\n",
    "- [Nearest Neighbors](http://scikit-learn.org/stable/modules/neighbors.html) (user guide), [KNeighborsClassifier](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html) (class documentation)\n",
    "- [Logistic Regression](http://scikit-learn.org/stable/modules/linear_model.html#logistic-regression) (user guide), [LogisticRegression](http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html) (class documentation)\n",
    "- [Videos from An Introduction to Statistical Learning](http://www.dataschool.io/15-hours-of-expert-machine-learning-videos/)\n",
    "    - Classification Problems and K-Nearest Neighbors (Chapter 2)\n",
    "    - Introduction to Classification (Chapter 4)\n",
    "    - Logistic Regression and Maximum Likelihood (Chapter 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 5: Comparing machine learning models in scikit-learn\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Now you might have the following questions\n",
    "\n",
    "- How do I choose **which model to use** for my supervised learning task?\n",
    "- How do I choose the **best tuning parameters** for that model?\n",
    "- How do I estimate the **likely performance of my model** on out-of-sample data?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's review what we've learned so far in this lab\n",
    "\n",
    "- Classification task: Predicting the species of an unknown iris\n",
    "- Used three classification models: KNN (K=1), KNN (K=5), logistic regression\n",
    "- Need a way to choose between the models\n",
    "\n",
    "** So our next topic is:** Model evaluation procedures.  It's a [big topic](http://scikit-learn.org/stable/model_selection.html#model-selection), but we'll start at the beginning."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Evaluation procedure #1: Train and test on the entire dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Train the model on the **entire dataset**.\n",
    "2. Test the model on the **same dataset**, and evaluate how well we did by comparing the **predicted** response values with the **true** response values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert (X == iris.data).all()  # if these statement fail, rerun your notebook\n",
    "assert (y == iris.target).all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Logistic regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1,\n",
       "       1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# import the class\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "\n",
    "# instantiate the model (using the default parameters)\n",
    "logreg = LogisticRegression()\n",
    "\n",
    "# fit the model with data\n",
    "logreg.fit(X, y)\n",
    "\n",
    "# predict the response values for the observations in X\n",
    "logreg.predict(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "150"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# store the predicted response values\n",
    "y_pred = logreg.predict(X)\n",
    "\n",
    "# check how many predictions were generated\n",
    "len(y_pred)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Classification accuracy:\n",
    "\n",
    "- **Proportion** of correct predictions\n",
    "- Common **evaluation metric** for classification problems\n",
    "\n",
    "__Task 5:__ Compute the accuracy of your `logreg` classifier on the training data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.95999999999999996"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Your solution here:\n",
    "truth_matrix = (y_pred == y)\n",
    "\n",
    "sum(truth_matrix)/len(truth_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This quantity is known as **training accuracy**.\n",
    "\n",
    "Computing accuracy and other machine learning metrics is such a common task sklean has a whole module [sklearn.metrics](http://scikit-learn.org/stable/modules/classes.html#module-sklearn.metrics) dedicated to this task. Below is an example of using it to compute the accuracy of `y_pred` versus `y`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.96\n"
     ]
    }
   ],
   "source": [
    "# compute classification accuracy for the logistic regression model\n",
    "from sklearn import metrics\n",
    "print(metrics.accuracy_score(y, y_pred))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below we compute the accuracy of both the K=5 and K=1 KNN-Classifiers discussed earlier.\n",
    "\n",
    "####  KNN (K=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.966666666667\n"
     ]
    }
   ],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "knn = KNeighborsClassifier(n_neighbors=5)\n",
    "knn.fit(X, y)\n",
    "y_pred = knn.predict(X)\n",
    "print(metrics.accuracy_score(y, y_pred))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### KNN (K=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n"
     ]
    }
   ],
   "source": [
    "knn = KNeighborsClassifier(n_neighbors=1)\n",
    "knn.fit(X, y)\n",
    "y_pred = knn.predict(X)\n",
    "print(metrics.accuracy_score(y, y_pred))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Task 6:__  Explain why does K=1 has an accuracy of 1.0?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It has an accuracy of 1.0 since the algorithm chooses the most \"popular\" class label from the k points around it: but here, k=1, and so even outlier points will be classified correctly. Obviously this model will not generalize well when applied to new data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problems with training and testing on the same data\n",
    "\n",
    "- Goal is to estimate likely performance of a model on **out-of-sample data**\n",
    "- But, maximizing training accuracy rewards **overly complex models** that won't necessarily generalize\n",
    "- Unnecessarily complex models **overfit** the training data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Overfitting](images/05_overfitting.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Image Credit: [Overfitting](http://commons.wikimedia.org/wiki/File:Overfitting.svg#/media/File:Overfitting.svg) by Chabacano. Licensed under GFDL via Wikimedia Commons.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Evaluation procedure #2: Train/test split"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Split the dataset into two pieces: a **training set** and a **testing set**.\n",
    "2. Train the model on the **training set**.\n",
    "3. Test the model on the **testing set**, and evaluate how well we did\n",
    "\n",
    "The [sklearn.model_selection.train_test_split](http://scikit-learn.org/stable/modules/generated/sklearn.model_selection.train_test_split.html) function allows one to randomly select subsets of features and labels for use in model training and testing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# STEP 1: split X and y into training and testing sets\n",
    "from sklearn.model_selection import train_test_split\n",
    "X_train, X_test, y_train, y_test = \\\n",
    "    train_test_split(X, y, test_size=0.4, random_state=4)\n",
    "# test_size is the fraction of the data used for test, \n",
    "# (1 - test_size) is used for train.\n",
    "# random_state is the seed used to generate random row selections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Train/test split](images/05_train_test_split.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What did this accomplish?\n",
    "\n",
    "- Model can be trained and tested on **different data**\n",
    "- Response values are known for the testing set, and thus **predictions can be evaluated** out-of-sample\n",
    "- **Testing accuracy** is a better estimate than training accuracy of out-of-sample performance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(150, 4)\n",
      "(150,)\n"
     ]
    }
   ],
   "source": [
    "# print the orginal shapes of X and y\n",
    "print(X.shape)\n",
    "print(y.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Task 7:__ Print the shapes of the 2 new X and 2 new y arrays. Do the dimensions make sense?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(90, 4)\n",
      "(60, 4)\n"
     ]
    }
   ],
   "source": [
    "# print the shapes of the new X objects\n",
    "print(X_train.shape)\n",
    "print(X_test.shape)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(90,)\n",
      "(60,)\n"
     ]
    }
   ],
   "source": [
    "# print the shapes of the new y objects\n",
    "print(y_train.shape)\n",
    "print(y_test.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "LogisticRegression(C=1.0, class_weight=None, dual=False, fit_intercept=True,\n",
       "          intercept_scaling=1, max_iter=100, multi_class='ovr', n_jobs=1,\n",
       "          penalty='l2', random_state=None, solver='liblinear', tol=0.0001,\n",
       "          verbose=0, warm_start=False)"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# STEP 2: train the model on the training set\n",
    "logreg = LogisticRegression()\n",
    "logreg.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.95\n"
     ]
    }
   ],
   "source": [
    "# STEP 3: make predictions on the testing set\n",
    "y_pred = logreg.predict(X_test)\n",
    "\n",
    "# compare actual response values (y_test) with predicted response values (y_pred)\n",
    "print(metrics.accuracy_score(y_test, y_pred))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Repeat for KNN with K=5:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Task 8:__ Compute and print the accuracy score of `KNN` with K=5.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.966666666667\n"
     ]
    }
   ],
   "source": [
    "# YOUR CODE HERE\n",
    "knn_5 = KNeighborsClassifier(n_neighbors=5)\n",
    "knn_5.fit(X_train, y_train)\n",
    "\n",
    "y_pred_knn_5 = knn_5.predict(X_test)\n",
    "print(metrics.accuracy_score(y_test, y_pred_knn_5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Repeat for KNN with K=1:\n",
    "\n",
    "__Task 9:__ Train the KNN model for K=1 and then print its accuracy score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.95\n"
     ]
    }
   ],
   "source": [
    "# YOUR CODE HERE\n",
    "knn_1 = KNeighborsClassifier(n_neighbors=1)\n",
    "knn_1.fit(X_train, y_train)\n",
    "\n",
    "y_pred_knn_1 = knn_1.predict(X_test)\n",
    "print(metrics.accuracy_score(y_test, y_pred_knn_1))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Can we find an even better value for K? **  Below is a computer experiment to try and find out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# try K=1 through K=25 and record testing accuracy\n",
    "import numpy as np\n",
    "k_range = list(range(1, 26))\n",
    "scores = []\n",
    "for k in k_range:\n",
    "    knn = KNeighborsClassifier(n_neighbors=k)\n",
    "    knn.fit(X_train, y_train)\n",
    "    y_pred = knn.predict(X_test)\n",
    "    scores.append(metrics.accuracy_score(y_test, y_pred))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0.94999999999999996, 1), (0.94999999999999996, 2), (0.96666666666666667, 3), (0.96666666666666667, 4), (0.96666666666666667, 5), (0.98333333333333328, 6), (0.98333333333333328, 7), (0.98333333333333328, 8), (0.98333333333333328, 9), (0.98333333333333328, 10), (0.98333333333333328, 11), (0.98333333333333328, 12), (0.98333333333333328, 13), (0.98333333333333328, 14), (0.98333333333333328, 15), (0.98333333333333328, 16), (0.98333333333333328, 17), (0.96666666666666667, 18), (0.98333333333333328, 19), (0.96666666666666667, 20), (0.96666666666666667, 21), (0.96666666666666667, 22), (0.96666666666666667, 23), (0.94999999999999996, 24), (0.94999999999999996, 25)]\n",
      "best [score, k] pair = [0.983333, 6]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZIAAAEKCAYAAAA4t9PUAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XuYo/V53//3Z87SnkaDh2VYiZMDNhuCN2a6iV3HsYNx\nwLVDTF0HWhtCba/xFVPT+vo1lKa126b5UWI3pQkxwT+T4sY2sYkJe7nUGEMS3P5cYDHLYTmEzQKW\nlmF3QdqjNOe7fzyPtGJWM6PTI2lG9+u65hrpOej5Pqsd3fqe7q/MDOecc65ePe0ugHPOuZXNA4lz\nzrmGeCBxzjnXEA8kzjnnGuKBxDnnXEM8kDjnnGtIpIFE0sWSnpe0W9L1FfYnJN0t6UlJj0g6r2zf\nP5e0S9LTkr4laSjc/kVJeyXtDH8+EOU9OOecW1pkgURSL3ALcAmwGbhC0uYFh90A7DSz84ErgZvD\nczcB/wwYN7PzgF7g8rLz/sDMtoQ/90Z1D84555YXZY1kK7DbzPaY2TRwJ3DpgmM2Aw8CmNlzwBmS\nNob7+oCYpD4gDrwSYVmdc87VqS/C194EpMueZ4BfWHDME8BlwI8kbQVOB5Jm9pikLwE/BQrAD8zs\nB2XnXSvpSmAH8Hkzyy28uKRtwDaANWvWXPDWt761SbflnHPd4bHHHnvNzEaXOy7KQFKNG4GbJe0E\nngIeB+YkJQhqL2cCB4HvSPqYmf0Z8BXgPwAW/v4y8E8XvrCZ3QbcBjA+Pm47duxowe0459zqIenl\nao6LMpDsBVJlz5PhthIzOwxcDSBJwIvAHuBXgRfN7EC477vAO4E/M7N9xfMlfRX4XoT34JxzbhlR\n9pE8Cpwt6UxJAwSd5dvLD5A0HO4D+CTwUBhcfgr8oqR4GGAuBJ4Nzxkre4kPA09HeA/OOeeWEVmN\nxMxmJX0WuI9g1NXtZrZL0jXh/luBc4E7JBmwC/hEuO9hSXcBPwFmCZq8bgtf+iZJWwiatl4CPh3V\nPTjnnFueuiGNvPeROOdc7SQ9Zmbjyx3nM9udc841xAOJc865hnggcc4515B2zyNxHWp+3rj9f7/I\n4cJMu4viVojxM0Z49znLzl2r2+TMHPfs3Ms/uiBFT48iu46rnQcSV9GTew/xu//jWQDkf7NuGWZw\n2kich/7leyO7xg+e2cdv/8VT/MzJ67jg9ERk13G180DiKvppNg/Afde9m7ecsq7NpXGd7vfve44/\n+Zs9zM0bvRHVFn76+jEA0tm8B5IO430krqJ0GEiSiVibS+JWglQizuy8MXGoENk10tlC+Dsf2TVc\nfTyQuIoyuTwjawZYM+iVVre8ZCIOHP+wj0I6l3/Db9c5PJC4itLZAimvjbgqpUaC/ytRfsiXAkmE\nwcrVxwOJqyidy5Mcibe7GG6FOHU4Ro8gE1Gz0+zcPK8cnAS8RtKJPJC4E8zNG68cLJBKeCBx1env\n7WFsQ4x0LprawsShSebmjTetHWTi0CSzc/ORXMfVxwOJO8G+w5PMzFmpucK5aiQTMTIR1RYyYYB6\n55tPYm7emDg0Gcl1XH08kLgTFEfFeI3E1SI1Eo+s/6LYnPXON5/0hueuM3ggcScoNk+kvI/E1SCV\niLPvyCRTs3NNf+1MNk+P4O+dORI+9w73TuKBxJ0gnc0jwanDQ+0uiltBkokYZrA3gn6SdK7AKeuH\nOG0kTo+8RtJpPJC4E6RzeTauG2Kwr7fdRXErSLEGG0WHezobjCIsder7pMSO4oHEnSCTLXhHu6tZ\naS5JBB/y6Vy+1GeXGoludJirjwcSd4JM2R+tc9XauG6Igd6e0girZpmanWPf4alSoEol4pGNDnP1\n8UDi3mB6dp6Jw5M+GdHVrKdHbErEmt5/UexzOV4jibPv8BSTM83v1Hf18UDi3uCVgwXM8PQori7J\nRKzps9sXjiIs1kz2HvTmrU7hgcS9QfHbZNKbtlwdkol40/svFmaiPp4g0pu3OkWkgUTSxZKel7Rb\n0vUV9ick3S3pSUmPSDqvbN8/l7RL0tOSviVpKNw+Iul+SS+Ev31hgiYqTijzznZXj9RIjOyxaY5N\nzTbtNdO5PP29YuP6YDh6sYnLO9w7R2SBRFIvcAtwCbAZuELS5gWH3QDsNLPzgSuBm8NzNwH/DBg3\ns/OAXuDy8JzrgQfM7GzggfC5a5J0Lk9fjxjb4IHE1e74h3zzaguZbIFNw7HSglknrxtkoK8nsgSR\nrnZR1ki2ArvNbI+ZTQN3ApcuOGYz8CCAmT0HnCFpY7ivD4hJ6gPiwCvh9kuBO8LHdwC/Ht0tdJ90\nNs+pZX+0ztWiNJekiTPP07n8G7Is9PSI5HDzO/Vd/aIMJJuAdNnzTLit3BPAZQCStgKnA0kz2wt8\nCfgpMAEcMrMfhOdsNLOJ8PGrwEYqkLRN0g5JOw4cONCM++kKmZzPIXH1Kw7SaObw3EyucEKfXXIk\n3vRhxq5+7e5svxEYlrQTuBZ4HJgL+z0uBc4ETgXWSPrYwpPNzACr9MJmdpuZjZvZ+OjoaGQ3sNr4\nHBLXiJE1A8QHeptWIzk2NUv22PQJX25SCZ/d3kmiDCR7gVTZ82S4rcTMDpvZ1Wa2haCPZBTYA7wP\neNHMDpjZDPBd4J3hafskjQGEv/dHeA9dJT89y2tHpz1Zo6ubJFKJeNOanYqvs/DLTWokTi4/w9Em\nduq7+kUZSB4FzpZ0pqQBgs7y7eUHSBoO9wF8EnjIzA4TNGn9oqS4JAEXAs+Gx20HrgofXwXcE+E9\ndJViU0HS55C4BiSbWFso1mwW/p8sPvdaSWeILJCY2SzwWeA+giDwbTPbJekaSdeEh50LPC3peYLR\nXZ8Lz30YuAv4CfBUWM7bwnNuBC6S9AJBzeXGqO6h2xwfr+81Ele/VNh/EbQ8N6a0Ns6CWnLK55J0\nlL4oX9zM7gXuXbDt1rLHPwbOWeTcLwBfqLD9dYIaimuy43+0XiNx9UsmYhydmuVgfobEmoHlT1hC\nOpcn1t/LSQteJ8pMw6527e5sdx0knSsw1N/D6NrBdhfFrWDFD/lmjKoqjiIMWriPS8T7WTPQ6zWS\nDuGBxJVkcnmSifgJf7TO1aKZkxLT2cqjCCWVmtBc+3kgcSXpbMGTNbqGJZu0LomZhTWSyn12SU8n\n3zE8kLiSdFgjca4R64f62RDrb7hGcjAc3rvYKMLi6LBmdOq7xnggcQAcys9wZHLWO9pdU6RGYg1P\nSlwuE3VqJM6x6Tly+ZmGruMa54HEAYtP/HKuHs2YlLhcJuqUzyXpGB5IHLD4eH3n6lHsCJ+fr7/Z\nqfTlZpH/k8eHAHsgaTcPJA44PlTTaySuGVKJGNOz87x2dKru18jk8myI9bN+qL/yNZo4zNg1xgOJ\nA4JvdeuG+tgQr/xH61wtkk2oLaSzS2eiXjvYRyLe701bHcADiQMWH6/vXD2OpzCpv7aQriITdWqk\n+Uv7utp5IHFAMKvdkzW6Zmk0qeL8vIXrkCz9fzKZiPlKiR3AA4kLJ37lvaPdNc1Qfy+j6wbrbto6\ncHSK6dn5Zf9PphKNd+q7xnkgcRw4OsXkzLzPandNFSw+VV+zU2kU4TJNW8mRONNz8+w/Un+nvmuc\nBxJXNl7faySueVIjcTIH66uRlEYRLjNBtjSXxIcAt5UHElfKV+SBxDVTKhHnlYOTzM7N13xutWvj\nHB8C7IGknTyQOF8Z0UUiNRJjbt6YODRZ87npXJ7RdYMM9fcuedym4WKnvo/caicPJI50Ns9JawaI\nD0S6zpnrMskG0smns9WNIhzq7+XkdYM+l6TNPJC4IOuvN2u5Jit2lGfqqC1UM4ekdJ2RxvN6ucZ4\nIHG+DomLxNjwED2qvUYyOzfPxKHJqjNRNzI6zDWHB5IuNzdvvHJw8cWDnKtXf28PYxtiNTc7TRya\nZG7eaqqRTBwqMFNHp75rDg8kXe7Vw5PM1vBH61wtUiOxmpMqLpf194RrJOLMG7xaR6e+a45IA4mk\niyU9L2m3pOsr7E9IulvSk5IekXReuP0tknaW/RyWdF2474uS9pbt+0CU97DaHU8f701brvnqWZek\n2KdS7ZebZi3t6+oX2TAdSb3ALcBFQAZ4VNJ2M3um7LAbgJ1m9mFJbw2Pv9DMnge2lL3OXuDusvP+\nwMy+FFXZu0m1M4idq0dqJM6+w1NMzswtO5S3KJ3L06Ogj6WqazQwOsw1R5Q1kq3AbjPbY2bTwJ3A\npQuO2Qw8CGBmzwFnSNq44JgLgb8zs5cjLGvXSucKqIY/WudqURzCu/dg9c1b6WyesQ0x+nur+3ga\n2zBEb4+8w72Nogwkm4B02fNMuK3cE8BlAJK2AqcDyQXHXA58a8G2a8PmsNslJSpdXNI2STsk7Thw\n4EC997DqZbJ5Tlk/xGBfdd8WnatFaRXDGpqdas1E3dfbw9iGIa+RtFG7O9tvBIYl7QSuBR4H5oo7\nJQ0AvwZ8p+ycrwBnETR9TQBfrvTCZnabmY2b2fjo6GhExV/5ahmv71ytjjc71VYjqXUUYSoR9z6S\nNooykOwFUmXPk+G2EjM7bGZXm9kW4EpgFNhTdsglwE/MbF/ZOfvMbM7M5oGvEjShuTqls4VSZ6Vz\nzXbyukEG+nqqzoU1OTPH/iNTNX+5SY3EfIGrNooykDwKnC3pzLBmcTmwvfwAScPhPoBPAg+Z2eGy\nQ65gQbOWpLGypx8Gnm56ybvE1Owc+45Meo3ERaanRySHY1XPbi/2pdQ6ijCViHPgSNCp71ovslFb\nZjYr6bPAfUAvcLuZ7ZJ0Tbj/VuBc4A5JBuwCPlE8X9IaghFfn17w0jdJ2gIY8FKF/a5KrxycxMyz\n/rpoJWtIYXJ8OHqtNZJiFuACP3Py2toK6BoWaZY+M7sXuHfBtlvLHv8YOGeRc48BJ1XY/vEmF7Nr\nHU/V7U1bLjrJRIynMgerOjZdZybqZNm6JB5IWq/dne2ujWqdQexcPVKJOLn8DEenZpc9NpPNM9Db\nw8Z1tQ1HL9VIvMO9LTyQdLF0tkB/rzhlvc8hcdFJ1TDzPJ3LsykRo6dHNV1jdG3Qqe8d7u2xbCCR\n9BlJG1pRGNda6VyeU4dj9Nb4R+tcLUpDgKsJJFWuQ7JQT49IJmpPEOmao5oayenATyR9U9L7oi6Q\na51M1ueQuOiVd4QvJ5OrfQ5J6Tp15PVyzbFsIDGz64GzgW8A10h6QdK/l3RGxGVzEcvkCp6s0UUu\nEe9nzUDvsh/yR6dmyeVn6v5yU0+mYdccVfWRhJP/Xgp/5oEx4B5J/29kJXOROjY1y+vHpkvLoToX\nFUnBKobLzCVpNBN1KhHnYH6GI5MzdZ3v6ldNH8lvSXoEuBl4DDjfzD4F/DzwGxGXz0UkU+cwS+fq\nkUzElp3dfnw4en1fbkprxHvyxparpkZyKnCFmb3PzL5lZlNQqqX8WqSlc5Gpd+KXc/VIhrmwzGzR\nY4ojrupd9rk0Osz7SVqumkDyl0Ap15WkdZLGAczM05OsUKU5JN605VogNRLn2PQcufzizU7pbJ74\nQC8jawYWPWbJa9QwOsw1VzWB5Dag/J05BvxJNMVxrZLOFoj19/KmtfX90TpXi2ItY6nmrUyuQCoR\nR6pvOPpwvJ+1g33e4d4G1QSSnrAZCyg1afVHVyTXCplcnmQiVvcfrXO1OL4uyeIf8sHQ3/r77CRV\n1Rfjmq+aQPJiOCmxV1KPpN8iGL3lVrB0ruD9I65lynNhVWJmpLP5hkcRVjM6zDVfNYHk0wTL3e4L\nf34Z+FSUhXLRMjMy2byP2HIts26on+F4/6L9F7n8DMem5xr+P5lMxEjnlu7Ud823bPbfcFGpj7Sg\nLK5FDhVmODI16x3trqWCmeeVawvNGkWYSsTJT8+RPTbNSWsHG3otV71lA4mkQeA3gZ8FStn9zGxb\ndMVyUSpW/X1Wu2ul1EiM5yaOVNzXrFGEpb6YXMEDSQtV07T1deAM4IPAw8CbgckIy+QiVvyj9Vnt\nrpVSiTiZXIH5+RObnZr15aaWTMOueaoJJOeY2b8CjprZ14CL8XXSVzSfjOjaITkSZ3pungNHp07Y\nl8nlGY73s26osQGhpbkkPnKrpaoJJMUZRAclnQusA06OrkguaplcgfVDfWyI+Shu1zrFuSSVagvp\ncA5Jo9YM9jGyZsDnkrRYNYHka5ISwBcI1l//W+BLkZbKRSrdQKpu5+p1vP/ixECSyTY2h+QN1/F1\nSVpuyc52Sb3Aa2aWA/4KOK0lpXKRSmd9XWvXepuGizWSN9YW5ueNTK7A+zZvbMp1kok4z0wcbspr\nueosWSMxsznghnpfXNLFkp6XtFvS9RX2JyTdLelJSY9IOi/c/hZJO8t+Dku6Ltw3Iun+cF2U+8Pa\nkquSmZVSUTjXSkP9vZy8bvCE2sL+I1NMz83XnaxxoeRIjL2LdOq7aFTTtPUDSddJGpO0vviz3Elh\nbeYW4BJgM3CFpM0LDrsB2Glm5wNXEqSqx8yeN7MtZrYFuIAg19fd4TnXAw+Y2dnAA+FzV6UDR6aY\nmp33pi3XFqmRE1cxLI0ibNL/yVQi6NTfd8QHl7ZKNYHkY8DngUeAXeFPNVl/twK7zWyPmU0DdwKX\nLjhmM/AggJk9B5whaWH99kLg78zs5fD5pcAd4eM7gF+voiwuVBqv73NIXBukEieuYphpcibqavJ6\nueaqZqndVIWfavpKNgHpsueZcFu5J4DLACRtJVgfPrngmMuBb5U932hmE+HjV4GKDauStknaIWnH\ngQMHqihud8iU1nzwGolrvdRInIlDk8zOlfLAlj7wm5Wyp5pMw665qpnZ/o8rbTezbzbh+jcCN0va\nCTwFPA7MlV17gGDxrH+1SBlMUsWGUDO7jSAFPuPj495YGmp0FTrnGpFKxJmbNyYOTZbVHPKcvG6Q\nof7eplxjU6Jyp76LzrKBBPilssdDwK8QLLm7XCDZC6TKnifDbSVmdhi4GkBBPvMXgT1lh1wC/CTM\n91W0T9KYmU1IGgP2V3EPLpTOFnjT2gFiA835o3WuFsmyuSTlw4GbmUB0sK+XjesHfVJiC1WTtPEz\n5c/DUVLV1EYeBc6WdCZBALkceEPtRtIwkA/7UD4JPBQGl6IreGOzFsB24CqC2sxVwD1VlMWFgj9a\nr4249qg0lySdLTB+RnMHX6bCpX1da1TT2b7QEeCs5Q4ys1ngswSTGJ8Fvm1muyRdI+ma8LBzgacl\nPU9Q+/hc8XxJa4CLgO8ueOkbgYskvQC8L3zuquSTEV07jW0YordHpWanmbl5Jg41fzh6aiTus9tb\nqJo+kruBYh9DD0EW4KpqAWZ2L3Dvgm23lj3+MXDOIuceA06qsP11gpFcrkazc/O8cnCSD53vI7Zc\ne/T19jC2YahUI5k4OMm8NX8UYSoR456dBWbm5unvref7sqtFNX0kf1T2eBZ42cxeiqY4LkoThyaZ\nmzevkbi2KmYBhuYP/S1KjsSZN3jlYIHTT1rT1Nd2J6omkLwA7DezSQBJMUkpM0svc57rMD7013WC\n1EiMv34+GJJ/fF5Tk5u2wv/jmZwHklaops73XWC+7Pk88BfRFMdFyScjuk6QSsTZf2SKyZk50tkC\nvT1ibMPQ8ifWcg1fl6SlqgkkfeGoKgDMbArwpcdWoEw2jwRjGzyQuPZJjhQnDBZI5/Kcsn6Ivib3\nY5yyPuzU9yHALVHNu/e6pA8Un0j6IJCNrkguKulcgbH1Qwz0eeeja5/yxafSTUwfX66vt4dTh4d8\nUmKLVNNH8hngm5JuCZ8fIMi/5VaYdDbftMR4ztWr2B+SyeZJ5wq855zRaK6TODFBpItGNRMS/xYY\nDycPYmYHIy+Vi0Q6l+ddPxPNH61z1RpdO8hAXw+79x/lwJGpyEYRphJxHnjOE1+0wrJtHJL+g6Rh\nMztoZgfDNUT+XSsK55pnanaOfYenvKPdtV1Pj0gmYjz8YtBCHtX/ydRIjNeOBp36LlrVNJZ/sLwW\nEq6W+KHoiuSisNeH/roOkkrEee7VI6XHkVyj2ITmzVuRqyaQ9IZZeAGQNAQMLHG860DpXHNTdTvX\niPL/h1Hlfkt6FuCWqaaz/U7gfkm3h8//KdUlbXQdpDie3me1u05Q/H840NfDyeuimU1QPjrMRaua\nzvbfk/QkQYJEgJvM7H9EWyzXbOlcnv5esXF9cyd+OVeP4od8cjhGT48iucboukEG+3p8UmILVDWh\nwMy+Z2bXmdl1BPNKbo64XK7JMtkCm4Zj9Eb0R+tcLYod7FEOR5eCTn1v2opeNU1bSPo5grVBfgN4\nBU+R0jTHpmb5wvZdHJuajfQ6D7+Y5WdPXR/pNZyrVrFGkoq4zy41EufhF1/nM3/2WKTXqcf5yWE+\n8543t7sYTbFoIJF0FkHwuAI4Cvw50G9mv7TYOa52j76U5a7HMpx+UpzBCGecv2ntAB88fyyy13eu\nFsPxfv7h25Nccl60/yc/eP6pvHKwwN8dOBrpdWr1+tFpHnh2P59+91mRNe210lI1kt3Aj4DLwkmJ\nSLq2JaXqIsXRVH++7R2c0uTEdc51Kkl8+aNvi/w6H7kgyUcuSEZ+nVr99//zMv/mL59m/5GpVfF3\nv9RX4I8SpEP5oaQ/lvTLwMoPnR0mk81HOnLFOdd5ik16q2VE2aKBxMzuMrOPEKyI+H+A64GNkv5Q\n0q+0qoCrXSZXiHTkinOu86y2yZLLNsqb2REz+7qZXQKcRrD++hciL1mXSOc8kaJz3WbT8OqaLFlT\n766ZvWZmf2xmvxxVgbpNOpuPfOSKc66zDPX3snH94KqZ4+ILU7TR0alZcvmZyFJEOOc6V3IVpbmP\nNJBIuljS85J2S7q+wv6EpLslPSnpEUnnle0blnSXpOckPSvpHeH2L0raK2ln+POBha+7UhxPW+I1\nEue6TWoVTZaMLJBI6gVuAS4BNgNXSNq84LAbgJ1mdj5wJVA+Y/5m4Ptm9lbgbQR9M0V/YGZbwp97\no7qHqJUCiddInOs6qZE4E4cKzMzNt7soDatmPZKcpOyCnxclfUfSGUucuhXYbWZ7wjXf7wQuXXDM\nZuBBADN7DjhD0kZJG4B3A18L902vxgW1MsXU7t7Z7lzXSSXizBtMHJxsd1EaVk2N5Bbg3wBvDn9+\nB/gO8JfAny5x3iYgXfY8E24r9wRwGYCkrcDpQBI4k2AOy59KelzS/ydpTdl514bNYbdLSlS6uKRt\nknZI2nHgwIEqbrP10rk8awZ6ScT7210U51yLJcMm7dUwBLiaQPIhM7vFzHLhzx8D7zezbwAjDV7/\nRmBY0k7gWuBxYI5gxv3bga+Y2c8DxwjmsQB8BTgL2AJMAF+u9MJmdpuZjZvZ+OhoZy4vm84WSI3E\nkXwOiXPdZjWlua8mkBQkXVZ8Ej6eCp8u1bi3F0iVPU+G20rM7LCZXW1mWwj6SEaBPQS1l4yZPRwe\nehdBYMHM9pnZnJnNA18laEJbkTK5vC805VyXGtswRG+PVkWHezWB5GPAp8K+kdeBTwEflxQHrlvi\nvEeBsyWdGa6weDmwvfyAcGRWcbXFTwIPhcHlVSAt6S3hvguBZ8JzyrO8fRh4uop76DhmRjqb96G/\nznWpvt4exjYMrYoaSTULW+0mGHlVyd8scd6spM8C9wG9wO1mtkvSNeH+W4FzgTskGbAL+ETZS1wL\nfCMMNHuAq8PtN0naAhjwEvDp5e6hE+XyMxybnvOOdue6WCoRXxWTEpcNJJLeRLC87hnlx5vZtuXO\nDYfm3rtg261lj38MnLPIuTuB8QrbP77cdVeC40N/vWnLuW6VGonxV8935mCgWlSzsNU9BEkb/xdB\nR7hrAh/665xLJeIcODLF5MwcQ/297S5O3aoJJGvM7PORl6TLFNtFPZA4172OZwEu8DMnr21zaepX\nTWf7/5T0/shL0mXS2TyJeD9rB6ta7dg5twoV0yOt9A73agLJNcD3JR0NR27lJGWjLthql84VfMSW\nc12u+BmQWeEd7tV8HX5T5KXoQplsnreOrWt3MZxzbTS6dpCBvp7Sktsr1aKBRNLZZvYCwQqJlTwZ\nTZFWv/l5I5MrcNHmje0uinOujXp6RDIRW/FDgJeqkVxPMK/jlgr7jCCpoqvDgaNTTM/N+8qIzrlg\nLskK7yNZNJCYWXFy4K+Y2Uz5PkmeZbABPofEOVeUGomxM72yk5tX09n+cJXbXJV86K9zriiViHOo\nMMPhyZnlD+5QS/WRnAyMATFJPwcUU9SuB/wTsAHFJG2bhr1G4ly3Oz5yq8DmU1dmY89SfST/gCA1\nSpKgn6QYSI4QrE/i6pTO5jl53eCKnsnqnGuO8rkkm09d3+bS1GepPpI/JVhY6qNm9u0WlmnVS+fy\n3qzlnAPK1iVZwSO3qukjOVnSegBJt0p6RNKFEZdrVUtnC97R7pwDYDjMcJFZwXNJqgkk28zscJgm\nZYxgPZKboi3W6jU7N8+rhye9RuKcA0Ba+XNJqgkkFv7+APB1M3uiyvNcBROHJpmbt1J11jnnUiMr\ney5JNQHhCUn3Ah8kSOC4luPBxdWo+K0jOeJNW865QCoRJ5MrYLYyP1qrybV1NXABsNvM8uFCV59Y\n5hy3iNIcEq+ROOdCyUSM/PQc2WPTnLR2sN3FqdmyNRIzmwPOAj4TbopVc56rLJ0t0NsjxjYMtbso\nzrkOUewzXanJG5cNCJL+CHgv8LFw0zHg1sXPcEtJ5/KMbRiir9djsXMuUJpLskI73Ktp2nqnmb1d\n0uMAZpaVNBBxuVatTK7gzVrOuTcozSVZoR3u1XwtnpHUQ9jBLukkYL6aF5d0saTnJe2WdH2F/QlJ\nd0t6Mpyfcl7ZvmFJd0l6TtKzkt4Rbh+RdL+kF8LfiarutEOks/nStw/nnANYM9jHyJqBUvqklWbR\nQCKpWFu5BfgLYFTSvwP+F/CflnthSb3huZcAm4ErJG1ecNgNwE4zOx+4Eri5bN/NwPfN7K3A24Bn\nw+3XAw+Y2dnAA+HzFWFyZo79R6a8RuKcO0EqESOzCmskjwCY2deB3wG+BOSAf2Rmd1bx2lsJRnrt\nMbNp4E7g0gXHbAYeDK/zHHCGpI2SNhCsd/K1cN+0mRXzLF8K3BE+vgP49SrK0hGKM1d96K9zbqFk\nOAR4JVqIsL1RAAAQ10lEQVSqj6SYpBEz2wXsqvG1NwHpsucZ4BcWHPMEcBnwI0lbgdMJkkTOAQcI\ncn29DXgM+JyZHQM2mtlEeP6rwIpZZtCH/jrnFpMciXH/M/uYnzd6erT8CR1kqUAyKulfLLbTzP5z\nE65/I3CzpJ3AU8DjBEGkD3g7cK2ZPSzpZoImrDdkHTYzk1RxBo+kbcA2gNNOO60JRW1cJuvrkDjn\nKksl4kzPzbPvyCRjG1ZWq8VSTVu9wFpg3SI/y9kLpMqeJ8NtJWZ22MyuNrMtBH0ko8AegtpLxsyK\nC2jdRRBYAPZJGgMIf++vdHEzu83Mxs1sfHR0tIriRi+dKzDQ18PoCpxw5JyLVmkuyQrscF+qRjJh\nZv++gdd+FDhb0pkEAeRy4B+XHyBpGMiHfSifBB4ys8PAYUlpSW8xs+eBC4FnwtO2A1cR1GauAu5p\noIwtlcnlSSZiK67a6pyLXjEjeDqbZ+uZI20uTW2q6iOph5nNSvoscB9B7eZ2M9sl6Zpw/63AucAd\nYfPULt6YeuVa4BvhnJU9BKlaIAgg35b0CeBl4KONlLOVgvTx3qzlnDvRpkQMaWXOJVkqkDS85oiZ\n3Qvcu2DbrWWPfwycs8i5O4HxCttfb0bZ2iGdy/O21IZ2F8M514EG+3rZuG5oRTZtLdpHYmbZVhZk\ntTsyOcPB/ExpfWbnnFsouULnknjCpxYpfsvwpi3n3GJSIytzLokHkhYpzSHxyYjOuUWkEjEmDhWY\nmasqC1XH8EDSIsVvGV4jcc4tJjkSZ97glYMrq1bigaRF0tk8awf7GI73t7sozrkOVcoCvMI63D2Q\ntEhxDonkc0icc5WV1iVZYR3uHkhaJJ0t+Igt59ySTlk/RG+PVtwCVx5IWsDMSOd8HRLn3NL6ens4\ndXhoxY3c8kDSAtlj0+Sn57yj3Tm3rFQi7k1b7kTp4ogtz/rrnFtGKhH3znZ3oozPIXHOVSk1EuO1\no1MUpufaXZSqeSBpAZ/V7pyrVrHlYiWlSvFA0gLpXJ6RNQOsGVwqR6ZzzlEa3bmS+kk8kLRAOhvM\nIXHOueUcX5dk5fSTeCBpgUzO1yFxzlVndN0gg3093rTljpufN/bmCiS9o905VwVJJBMxr5G44/Yd\nmWR6bt5rJM65qqVGVtZcEg8kEcv4HBLnXI2CuSQeSFyo+J8h5Z3tzrkqpUZiHJ6c5VBhpt1FqYoH\nkogV2zlPHfZA4pyrTmkI8AqplXggiVg6l2fj+kGG+nvbXRTn3ApR7FNdKSO3Ig0kki6W9Lyk3ZKu\nr7A/IeluSU9KekTSeWX7XpL0lKSdknaUbf+ipL3h9p2SPhDlPTQqnc17R7tzribFdEorJQtwZFOt\nJfUCtwAXARngUUnbzeyZssNuAHaa2YclvTU8/sKy/e81s9cqvPwfmNmXoip7M2VyBbaeOdLuYjjn\nVpANsX7WDfZ50xawFdhtZnvMbBq4E7h0wTGbgQcBzOw54AxJGyMsU0vNzM0zcajgHe3OuZpIIjkS\nL2UO73RRBpJNQLrseSbcVu4J4DIASVuB04FkuM+AH0p6TNK2BeddGzaH3S4pUenikrZJ2iFpx4ED\nBxq9l7pMHJxk3iDpQ3+dczVKJWJeI6nSjcCwpJ3AtcDjQDF38rvMbAtwCfBbkt4dbv8KcBawBZgA\nvlzphc3sNjMbN7Px0dHRKO9hUcUJRd5H4pyrVWokTiZXwMzaXZRlRZmOdi+QKnueDLeVmNlh4GoA\nSQJeBPaE+/aGv/dLupugqewhM9tXPF/SV4HvRXgPDSl+m/CEjc65WiUTMQozc7x2dJrRdYPtLs6S\noqyRPAqcLelMSQPA5cD28gMkDYf7AD5JECgOS1ojaV14zBrg/cDT4fOxspf4cHF7J0rn8vT2iLEN\nQ+0uinNuhUmtoHTykdVIzGxW0meB+4Be4HYz2yXpmnD/rcC5wB2SDNgFfCI8fSNwd1BJoQ/4ppl9\nP9x3k6QtBH0oLwGfjuoeGpXOFjh1eIi+3na3IDrnVprjC1wVePtpFbuCO0akKy2Z2b3AvQu23Vr2\n+MfAORXO2wO8bZHX/HiTixmZdM7nkDjn6pMsrUvS+TUS/6ocIV+HxDlXrzWDfZy0ZmBFzG73QBKR\nyZk5DhyZKs1Qdc65WiVH4itiXRIPJBEpfotIeo3EOVenZCK2IjrbPZBEpPgtwmskzrl6pRJxXjlY\nYG6+s+eSeCCJiE9GdM41KjUSY2bOePXwZLuLsiQPJBFJZ/MM9vV0/EQi51znKqWT7/CRWx5IIpLJ\nFUgmYoRzYZxzrmbFuSSdnrzRA0lE0rm8r9PunGvIqcNDSJ0/l8QDSUTSWZ9D4pxrzGBfL6esH+r4\nkVseSCJweHKGQ4UZT9bonGtYMhEj0+FzSTyQRKBYDfWmLedco1KJuNdIulFpDok3bTnnGpQcifPq\n4UmmZueWP7hNPJBEoDir3ScjOucalUrEMAtWXO1UHkgikMkVWDfYx4ZYf7uL4pxb4Y4PAe7c5i0P\nJBFIZ/MkR+I+h8Q517BSIOngDncPJBFI5/I+Yss51xSnrB+ir0deI+kmZuZzSJxzTdPbI04djnX0\npEQPJE32+rFpCjNz3tHunGua1Eiso9OkeCBpstIcEq+ROOeaJJWId3TiRg8kTZbJFdch8UDinGuO\n1Eic149Nk5+ebXdRKvJA0mTp0sqI3rTlnGuO4udJpkObtyINJJIulvS8pN2Srq+wPyHpbklPSnpE\n0nll+16S9JSknZJ2lG0fkXS/pBfC34ko76FW6WyBk9YMsGawr91Fcc6tEseHAHdm81ZkgURSL3AL\ncAmwGbhC0uYFh90A7DSz84ErgZsX7H+vmW0xs/GybdcDD5jZ2cAD4fOOkfGhv865Jit+pnRqIIny\na/NWYLeZ7QGQdCdwKfBM2TGbgRsBzOw5SWdI2mhm+5Z43UuB94SP7wD+Gvjt5hY98IcPvMD2J16p\n6ZyXs3ku2rwxiuI457rU6NpBhvp7+K8P7uYbD/+0pnN/77Kf4++dMRJRyQJRBpJNQLrseQb4hQXH\nPAFcBvxI0lbgdCAJ7AMM+KGkOeBPzOy28JyNZjYRPn4VqPipLWkbsA3gtNNOq+sGRtcNcvbGtTWd\nc87GdXzsF06v63rOOVeJJD5/0Vt4PJ2r+dxYf28EJXqjdjfk3wjcLGkn8BTwOFBMcfkuM9sr6WTg\nfknPmdlD5SebmUmySi8cBp7bAMbHxyses5zLt57G5VvrC0LOOddMn3r3We0uwqKiDCR7gVTZ82S4\nrcTMDgNXAyhITPUisCfctzf8vV/S3QRNZQ8B+ySNmdmEpDFgf4T34JxzbhlRjtp6FDhb0pmSBoDL\nge3lB0gaDvcBfBJ4yMwOS1ojaV14zBrg/cDT4XHbgavCx1cB90R4D84555YRWY3EzGYlfRa4D+gF\nbjezXZKuCfffCpwL3BE2T+0CPhGevhG4O8ye2wd808y+H+67Efi2pE8ALwMfjeoenHPOLU9mdXUf\nrCjj4+O2Y8eO5Q90zjlXIumxBdMvKvKZ7c455xrigcQ551xDPJA455xriAcS55xzDemKznZJBwhG\neL0JeK3NxWmnbr7/br536O777+Z7h8bu/3QzG13uoK4IJEWSdlQzAmG16ub77+Z7h+6+/26+d2jN\n/XvTlnPOuYZ4IHHOOdeQbgskty1/yKrWzfffzfcO3X3/3Xzv0IL776o+Euecc83XbTUS55xzTeaB\nxDnnXEO6JpBIuljS85J2S+qodd5bQdJLkp6StFPSqs5gKel2SfslPV22bUTS/ZJeCH8n2lnGqCxy\n71+UtDd873dK+kA7yxgVSSlJfyXpGUm7JH0u3N4t7/1i9x/5+98VfSSSeoG/BS4iWPL3UeAKM3tm\nyRNXEUkvAeNmtuonZkl6N3AU+LqZnRduuwnImtmN4ReJhJn9djvLGYVF7v2LwFEz+1I7yxa1cKG7\nMTP7Sbie0WPArwO/SXe894vd/0eJ+P3vlhrJVmC3me0xs2ngTuDSNpfJRSRckjm7YPOlwB3h4zsI\n/sBWnUXuvSuY2YSZ/SR8fAR4FthE97z3i91/5LolkGwC0mXPM7ToH7iDGPBDSY9J2tbuwrTBRjOb\nCB+/SrB4Wje5VtKTYdPXqmzaKSfpDODngYfpwvd+wf1DxO9/twQSB+8ysy3AJcBvhU0gXcmC9tzV\n36Z73FeAs4AtwATw5fYWJ1qS1gJ/AVxnZofL93XDe1/h/iN//7slkOwFUmXPk+G2rmFme8Pf+4G7\nCZr7usm+sA252Ja8v83laRkz22dmc2Y2D3yVVfzeS+on+BD9hpl9N9zcNe99pftvxfvfLYHkUeBs\nSWdKGgAuB7a3uUwtI2lN2PmGpDXA+4Gnlz5r1dkOXBU+vgq4p41laanih2jow6zS916SgK8Bz5rZ\nfy7b1RXv/WL334r3vytGbQGEQ97+C9AL3G5m/7HNRWoZSWcR1EIA+oBvrub7l/Qt4D0E6bP3AV8A\n/hL4NnAawZICHzWzVdcpvci9v4egWcOAl4BPl/UZrBqS3gX8CHgKmA8330DQT9AN7/1i938FEb//\nXRNInHPORaNbmracc85FxAOJc865hnggcc451xAPJM455xrigcQ551xDPJC4VSHMevqrC7ZdJ+kr\ny5x3NOJyjUp6WNLjkn5pwb6/ljQePj4zzE77qxVe4/fDbK6/X2cZ3iPpe2XPf1fS9yUNhmXYUbZv\nXNJfl51nkj5Utv97kt5TTznc6uWBxK0W3yKYaFru8nB7O10IPGVmP29mP6p0gKQk8H3g82Z2X4VD\ntgHnm9n/U80FJfUtse93gL8PfNjMpsLNJ0u6ZJFTMsC/rua6rnt5IHGrxV3APwgzFxST1p0K/EjS\nWkkPSPqJgjVZTsj8XOFb+x9J+s3w8QWS/iZMeHnfgpnCxePPkPRgmBjvAUmnSdoC3ARcGq4DEatQ\n7jHgB8C/NrMTsi1I2g6sBR6T9BuVrhMe998k3Srp4fCaJ5D0eYJcax8ys0LZrt9n8WDxBHBI0kWL\n7HfOA4lbHcKZyo8QfFBCUBv5dpikb5LgG/jbgfcCXw7TSSwrzF30h8BHzOwC4HagUlaAPwTuMLPz\ngW8A/9XMdgL/FvhzM9uy4MO76A7gj8zsrkXu69eAQnj+n1e6TtnhSeCdZvYvKrzU3weuAS4xs4XN\neT8GpiW9t1IZwvv9nUX2OeeBxK0q5c1b5c1aAn5P0pPADwmWEKg2lfhbgPOA+yXtJPhATVY47h3A\nN8PH/x14V5Wv/0PgY5LiVR6/1HW+Y2Zzi5y3m+DfYbGaxe+ySLAI1zgppuBw7gQeSNxqcg9woaS3\nA3Ezeyzc/k+AUeCCMJX+PmBowbmzvPHvobhfwK6wRrDFzH7OzN7fxDLfRJBU9DtL9W1U6dgS+/YB\nHwD+S6Wah5k9CMSAX1zkfK+VuEV5IHGrRthk81cEzU/lnewbgP1mNhN+iJ5e4fSXgc3hSKZhgk5y\ngOeBUUnvgKCpS9LPVjj//+d4beifECTPq9Z1wGHga1U0udV9HTP7W+Ay4M/C/puFfhf4l4uc+wMg\nAZxf7fVc9/BA4labbwFv442B5BvAuKSngCuB5xaeZGZpggyxT4e/Hw+3TwMfAf6TpCeAncA7K1z3\nWuDqsPns48Dnqi1w2I9zFUHHe8WO8mZcJ7zWo8DVwHZJb16w717gwBKn/0feuK6Pc4Bn/3XOOdcg\nr5E455xriAcS55xzDfFA4pxzriEeSJxzzjXEA4lzzrmGeCBxzjnXEA8kzjnnGvJ/AaPr3LSlsHpj\nAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x111b23f98>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# import Matplotlib (scientific plotting library)\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# allow plots to appear within the notebook\n",
    "%matplotlib inline\n",
    "\n",
    "# plot the relationship between K and testing accuracy\n",
    "plt.plot(k_range, scores)\n",
    "plt.xlabel('Value of K for KNN')\n",
    "plt.ylabel('Testing Accuracy')\n",
    "print(list(zip(scores, k_range)))\n",
    "scores = np.array(scores)\n",
    "print('best [score, k] pair = [%g, %g]' % (np.max(scores),k_range[np.argmax(scores)]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Training accuracy** rises as model complexity increases\n",
    "- **Testing accuracy** penalizes models that are too complex or not complex enough\n",
    "- For KNN models, complexity is determined by the **value of K** (lower value = more complex)\n",
    "\n",
    "__Task 10:__ Explain why lower values of k represent more complex models"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Your solution here.\n",
    "\n",
    "# A lower value of k means that more complicated patterns in the data will be captured by the KNN algorithm, since less neighboring points are being used to predict class labels. This means that the model will fit the training data very well but may fail to capture simple patterns once tested on new data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Making predictions on out-of-sample data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# instantiate the model with a good known parameter\n",
    "knn = KNeighborsClassifier(n_neighbors=6)\n",
    "\n",
    "# train the model with X and y (not X_train and y_train)\n",
    "knn.fit(X, y)\n",
    "\n",
    "# make a prediction for an out-of-sample observation\n",
    "knn.predict([[3, 5, 4, 2]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 Downsides of train/test split?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Provides a **high-variance estimate** of out-of-sample accuracy\n",
    "- In the next lab we will see how **K-fold cross-validation** overcomes this limitation\n",
    "- But, train/test split is still useful because of its **flexibility and speed**\n",
    "\n",
    "__Task 11__:  Demonstrate the variability of measured accuracy\n",
    "Write some code to similar to the previous computer experiment to demonstrate that classifier accuracy depends on train/test splits. Hint:  Changing `random_state` in `train_test_split` will cause a new random selection of train and test data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0.91666666666666663, 0), (0.98333333333333328, 1), (0.96666666666666667, 2), (0.94999999999999996, 3), (0.98333333333333328, 4), (0.96666666666666667, 5), (0.94999999999999996, 6), (0.93333333333333335, 7), (0.94999999999999996, 8), (0.98333333333333328, 9), (0.98333333333333328, 10), (0.91666666666666663, 11), (0.98333333333333328, 12), (0.94999999999999996, 13), (0.96666666666666667, 14), (0.94999999999999996, 15), (0.93333333333333335, 16), (0.94999999999999996, 17), (0.98333333333333328, 18), (0.96666666666666667, 19)]\n",
      "best [score, k] pair = [0.983333, 2]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYwAAAEKCAYAAAAB0GKPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHJNJREFUeJzt3X+QXGWd7/H3h0mQQdDBTeSSHxCwMEtEBOzKIq5eFNcQ\nFoGlXCVXRCOYxRIu3MvNFgFL94fuRbNryWo0NytBWFFUDIHiooMKu2BdBSbkFxFGYsAlExaiEIIy\nSBK+949zBjpN98wzmTl9utOfV9VUup/nOf1855kz8805zznPUURgZmY2kn3KDsDMzNqDE4aZmSVx\nwjAzsyROGGZmlsQJw8zMkjhhmJlZEicMMzNL4oRhZmZJnDDMzCzJhLIDGE+TJk2KGTNmlB2GmVnb\nWLVq1W8iYnJK28IShqTlwGnAkxFxdJ16AVcBpwLPAR+NiPvzulPyui7g6xFxZUqfM2bMoK+vb5y+\nAzOzvZ+kX6e2LfKU1DeAU4apnwscmX8tAL4GIKkLWJLXzwLmSZpVYJxmZpagsIQREXcBTw3T5Azg\nusj8HOiRdAgwG9gYEZsi4gXghrytmZmVqMxJ76nAY1XvN+dljcrrkrRAUp+kvq1btxYSqJmZ7QVX\nSUXEsoioRERl8uSkeRszM9sDZV4lNQBMr3o/LS+b2KDczMxKVOYRxi3AucqcADwTEY8D9wFHSjpc\n0r7A2XlbMzMrUZGX1X4bOAmYJGkz8BmyowciYilwG9kltRvJLqudn9ftlHQh0Et2We3yiNhQVJxm\nZpamsIQREfNGqA/gkw3qbiNLKGZm1iLaftLbzMyawwnDzMySOGGYmVkSJwwzM0vihGFmZkmcMMzM\nLIkThpmZJXHCMDOzJE4YZmaWxAnDzMySOGGYmVkSJwwzM0vihGFmZkmcMMzMLIkThpmZJXHCMDOz\nJE4YZmaWxAnDzMySOGGYmVkSJwwzM0vihGFmZkmcMMzMLIkThpmZJXHCMDOzJE4YZmaWxAnDzMyS\nTCg7gHa3cvUAi3v72bJtkCk93SycM5Mzj5tadljJ2j3+so11/Moe/7L773TtNv5OGGOwcvUAi1as\nZ3DHLgAGtg2yaMV6gJb+oQ9p9/jLNtbxK3v8y+6/07Xj+PuU1Bgs7u1/6Yc9ZHDHLhb39pcU0ei0\ne/xlG+v4lT3+Zfff6dpx/J0wxmDLtsFRlbeado+/bGMdv7LHv+z+O107jr8TxhhM6ekeVXmraff4\nyzbW8St7/Mvuv9O14/g7YYzBwjkz6Z7YtVtZ98QuFs6ZWVJEo9Pu8ZdtrONX9viX3X+na8fx96T3\nGAxNTLXTVQ7V2j3+so11/Moe/7L773TtOP6KiOI+XDoFuAroAr4eEVfW1B8ELAfeADwPfCwiHsjr\n/gdwPhDAemB+RDw/XH+VSiX6+vrG/fswM9tbSVoVEZWUtoWdkpLUBSwB5gKzgHmSZtU0uxxYExHH\nAOeSJRckTQX+O1CJiKPJEs7ZRcVqZmYjK3IOYzawMSI2RcQLwA3AGTVtZgF3AETEQ8AMSQfndROA\nbkkTgP2BLQXGamZmIygyYUwFHqt6vzkvq7YWOAtA0mzgMGBaRAwA/wj8B/A48ExE3F6vE0kLJPVJ\n6tu6des4fwtmZjak7KukrgR6JK0BLgJWA7vyuY0zgMOBKcCrJZ1T7wMiYllEVCKiMnny5GbFbWbW\ncYq8SmoAmF71flpe9pKI2A7MB5Ak4BFgEzAHeCQituZ1K4ATgW8WGK+ZmQ2jyCOM+4AjJR0uaV+y\nSetbqhtI6snrILsi6q48ifwHcIKk/fNEcjLwYIGxmpnZCAo7woiInZIuBHrJrnJaHhEbJF2Q1y8F\njgKulRTABuC8vO4eSTcC9wM7yU5VLSsqVjMzG1mh92E0m+/DMDMbnZa4D8PMzPYuThhmZpbECcPM\nzJI4YZiZWRInDDMzS+KEYWZmSZwwzMwsiROGmZklccIwM7MkThhmZpbECcPMzJI4YZiZWRInDDMz\nS+KEYWZmSZwwzMwsyYgJQ9InJL22GcGYmVnrSjnCOAy4X9K3JL2n6IDMzKw1jZgwIuIy4EjgeuAC\nSQ9L+jtJMwqOzczMWkjSHEZEvAg8mn+9CBwC3CzpfxcWmZmZtZQJIzWQ9EngI8B24Grgioj4g6R9\ngI3AomJD3LutXD3A4t5+tmwbZEpPNwvnzOTM46aWHVaydo/fyuX9Z2yaPX4jJgxgCjAvIn5VXRgR\nL0o6vZiwOsPK1QMsWrGewR27ABjYNsiiFesB2uKXpt3jt3J5/xmbMsYv5ZTUSuCJoTeSDpRUAYiI\nBwqJqkMs7u1/6Yc9ZHDHLhb39pcU0ei0e/xWLu8/Y1PG+KUkjGXAc1Xvfw/8n2LC6Sxbtg2OqrzV\ntHv8Vi7vP2NTxvilJIx98klv4KUJ8ImFRdRBpvR0j6q81bR7/FYu7z9jU8b4pSSMR/Kb97ok7ZNP\ngj9aWEQdZOGcmXRP7NqtrHtiFwvnzCwpotFp9/itXN5/xqaM8UuZ9P4rYAnw90AAdwIfLyyiDjI0\nMdWuV4m0e/xWLu8/Y1PG+CkiCvvwZqtUKtHX11d2GGZmbUPSqoiopLRNuQ/jVcBHgTcB+w2VR8SC\nPQ3QzMzaT8ocxnXADOA04B7gDcDzBcZkZmYtKCVhvDEiFgG/i4irgVOA2cWGZWZmrSYlYezI/90m\n6SjgQOD1xYVkZmatKOUqqaslHQR8BugF9gc+XWhUZmbWcoY9wpDUBfwmIp6OiDsj4tCImBQRX035\ncEmnSOqXtFHSZXXqD5J0k6R1ku6VdHRVXY+kGyU9JOlBSW8b9XdnZmbjZtiEERG7gMv35IPzZLME\nmAvMAuZJmlXT7HJgTUQcA5wLXFVVdxXww4j4Y+AtwIN7EoeZmY2PlDmM2yVdIukQSa8Z+krYbjaw\nMSI2RcQLwA3AGTVtZgF3AETEQ8AMSQfnj4R9J9ly6kTECxGxLfWbMjOz8Zcyh3FO/u+lVWUBHDrC\ndlOBx6rebwb+pKbNWuAs4G5Js8keBzsN2AVsBa6R9BZgFXBxRPw+IV4zMytAyiNap9f5GilZpLoS\n6JG0BrgIWE2WLCYAxwNfi4jjyFbIfcUcCICkBZL6JPVt3bp1nMIyM7NaKXd6/7d65RHxrRE2HQCm\nV72flpdVf8Z2YH7ej4BHgE1kV2Jtjoh78qY30iBhRMQysiXYqVQqe886J2ZmLSbllNQ7ql7vB7yb\n7BTRSAnjPuBISYeTJYqzgd2Sj6Qe4Ll8juN84K48iWyX9JikmRHRD5wM/CLlGzIzs2KMmDAi4hPV\n7/N7MkZKFkTETkkXkt270QUsj4gNki7I65cCRwHXSgpgA3Be1UdcBFwvaV+yo475ad+SmZkVIeUI\no9azwBEpDSPiNuC2mrKlVa9/BryxwbZrgKQVFM3MrHgpcxg3kV0VBdkk+ZuAm4sMyszMWk/KEcZX\nql7vBH4dEY8WE46ZmbWqlITxMPBkRDwPIKlb0vSIeGyE7czMbC+Scqf3CuDFqvcvAt8vJhwzM2tV\nKQljQn7ZKwAR8QfgVcWFZGZmrSglYfxW0qlDbySdBjxVXEhmZtaKUuYwPgF8S9KS/P1WXl5fyszM\nOkTKjXu/BCr5Xdl41Vgzs8404ikpSX8vqScitkXEtvyhR3/bjODMzKx1pMxhnFZ9VBERTwPvKy4k\nMzNrRSkJoytfzwkASfsB+w7T3szM9kIpk943AD+StDx//zESFh80M7O9S8qk9z9IWge8Jy/6QkT8\n32LDMjOzVpO0Wm1E3ArcCiDpBElXRcTFhUZmSVauHmBxbz9btg0ypaebhXNmcuZxU8sOK1nZ8Zfd\nf7sre/w6vf9mS0oYkt4MzAM+CGzBS4O0hJWrB1i0Yj2DO3YBMLBtkEUr1gO0xU5bdvxl99/uyh6/\nTu+/DA0nvSUdIekKSQ8A/0J2w97EiHhHRHypaRFaQ4t7+1/aWYcM7tjF4t7+kiIanbLjL7v/dlf2\n+HV6/2UY7ghjI3A3cFZ+8x6SLmpKVJZky7bBUZW3mrLjL7v/dlf2+HV6/2UY7rLaD5AdVfxY0lcl\n/VdAzQnLUkzp6R5VeaspO/6y+293ZY9fp/dfhoYJIyJujIj3kz1h7+fAZcDBkr4s6d3NCtAaWzhn\nJt0Tu3Yr657YxcI5M0uKaHTKjr/s/ttd2ePX6f2XIeWy2meB64DrJE0iO/L4DHBHwbHZCIYm1tr1\nKo2y4y+7/3ZX9vh1ev9lUESM3KpNVCqV6OvrKzsMM7O2IWlVRFRS2qYsDWJmZuaEYWZmaZwwzMws\nyYiT3pKeBmonOp4B+oCFEfFoAXGZmVmLSVkaZAnwOC+vUDsPmAGsBa4B3lVIZGZm1lJSTkm9LyKW\nRMTT+ddXgfdGxPXA6wqOz8zMWkRKwhiUdNbQm/z1H/K3LxYSlZmZtZyUhHEO8HFJT0n6LfBx4MOS\n9gcuKTQ6MzNrGSl3em8E5jao/vfxDcfMzFpVylVSk8geyzqjun1ELCguLDMzazUpV0ndTLb44E+B\nXSO0NTOzvVRKwnh1RFxaeCRmZtbSUia9fyDpvXvy4ZJOkdQvaaOky+rUHyTpJknrJN0r6eia+i5J\nqyXduif9m5nZ+ElJGBcAP5T0u/xKqaclPTXSRpK6yG76mwvMAuZJmlXT7HJgTUQcA5wLXFVTfzHw\nYEKMZmZWsJSEMQmYCLwWmJy/n5yw3WxgY0RsiogXgBuAM2razCJ/rkZEPATMkHQwgKRpwJ8DX0/o\ny8zMCtZwDkPSkRHxMNkT9+pZN8JnTwUeq3q/GfiTmjZrgbOAuyXNBg4DpgFPAF8C/ho4cIR+zMys\nCYab9L4MOI/stFKtAN45Dv1fCVwlaQ2wHlgN7JJ0GvBkRKySdNJwHyBpAbAA4NBDDx2HkMzMrJ6G\nCSMizstfvjsidlTXSZqY8NkDwPSq99Pysuo+tgPz888U8AiwCfggcLqkU4H9gNdI+mZEnFMnzmXA\nMsieuJcQl5mZ7YGUOYx7Estq3QccKelwSfsCZwO3VDeQ1JPXAZwP3BUR2yNiUURMi4gZ+XZ31EsW\nZmbWPMPNYbweOATolvRmQHnVa4D9R/rgiNgp6UKgF+gClkfEBkkX5PVLgaOAayUFsIHsFJiZmbUg\nRdQ/iyNpPtmSIMeSzS0MJYxngWsi4ntNiXAUKpVK9PX1lR2GmVnbkLQqIiopbYebw7gGuEbSByLi\nu+MWnZmZtaWUOYzXS3oNgKSl+R3ZJxccl5mZtZiUhLEgIrbny4McQvY8jC8UG5aZmbWalIQxNMlx\nKnBdRKxN3M7MzPYiKX/410q6DTiNbCHCA3g5iZiZWYdIWd58PvBWsnWhnssfqOTLX83MOkzKI1p3\nSToC+DPgc0A3PiVlLWLl6gEW9/azZdsgU3q6WThnJmceN7XssKxNeP8ZnRH/8Ev6CvAuYOhO698D\nS4sMyizFytUDLFqxnoFtgwQwsG2QRSvWs3L1wIjbmnn/Gb2UI4UTI+KvgOcBIuIpYN/hNzEr3uLe\nfgZ37P7U4MEdu1jc219SRNZOvP+MXkrC2CFpH/KJbkl/BLxYaFRmCbZsGxxVuVk17z+j1zBhSBqa\n31gCfB+YLOlvgZ8Cn29CbGbDmtLTPapys2ref0ZvuCOMewEi4jrgU8A/Ak8DfxkRNzQhNrNhLZwz\nk+6JXbuVdU/sYuGcmSVFZO3E+8/oDXeV1NBig0TEBrLVZM1axtDVLL7KxfaE95/RG2612s3AFxtt\nGBEN68ri1WrNzEZnXFarJXuGxQFUHWmYmVnnGi5hPB4Rf9e0SMzMrKUNN+ntIwszM3vJcAnDz7ww\nM7OXNEwY+R3dZmZmgBcRNDOzRE4YZmaWxAnDzMySOGGYmVkSJwwzM0vihGFmZkmcMMzMLIkThpmZ\nJXHCMDOzJE4YZmaWxAnDzMySOGGYmVkSJwwzM0vihGFmZkkKTRiSTpHUL2mjpMvq1B8k6SZJ6yTd\nK+novHy6pDsl/ULSBkkXFxmnmZmNrLCEIakLWALMBWYB8yTNqml2ObAmIo4BzgWuyst3ApdGxCzg\nBOCTdbY1M7MmKvIIYzawMSI2RcQLwA3AGTVtZgF3AETEQ8AMSQdHxOMRcX9e/izwIDC1wFjNzGwE\nRSaMqcBjVe8388o/+muBswAkzQYOA6ZVN5A0AzgOuKegOM3MLEHZk95XAj2S1gAXAauBXUOVkg4A\nvg9cEhHb632ApAWS+iT1bd26tRkxm5l1pAkFfvYAML3q/bS87CV5EpgPIEnAI8Cm/P1EsmRxfUSs\naNRJRCwDlgFUKpUYx/jNzKxKkUcY9wFHSjpc0r7A2cAt1Q0k9eR1AOcDd0XE9jx5XA08GBFfLDBG\nMzNLVNgRRkTslHQh0At0AcsjYoOkC/L6pcBRwLWSAtgAnJdv/nbgw8D6/HQVwOURcVtR8ZqZ2fCK\nPCVF/gf+tpqypVWvfwa8sc52PwVUZGxDVq4eYHFvP1u2DTKlp5uFc2Zy5nG+IMvag/dfa6ZCE0ar\nW7l6gEUr1jO4I5tnH9g2yKIV6wH8S2ctz/uvNVvZV0mVanFv/0u/bEMGd+xicW9/SRGZpfP+a83W\n0Qljy7bBUZWbtRLvv9ZsHZ0wpvR0j6rcrJV4/7Vm6+iEsXDOTLondu1W1j2xi4VzZpYUkVk677/W\nbB096T00MeirTKwdef+1ZlPE3nNzdKVSib6+vrLDMDNrG5JWRUQlpW1Hn5IyM7N0ThhmZpbECcPM\nzJI4YZiZWRInDDMzS+KEYWZmSZwwzMwsiROGmZklccIwM7MkThhmZpbECcPMzJI4YZiZWRInDDMz\nS+KEYWZmSZwwzMwsiROGmZklccIwM7MkThhmZpbECcPMzJI4YZiZWRInDDMzS+KEYWZmSZwwzMws\niROGmZklccIwM7MkThhmZpak0IQh6RRJ/ZI2SrqsTv1Bkm6StE7SvZKOTt3WzMyaq7CEIakLWALM\nBWYB8yTNqml2ObAmIo4BzgWuGsW2ZmbWREUeYcwGNkbEpoh4AbgBOKOmzSzgDoCIeAiYIengxG3N\nzKyJikwYU4HHqt5vzsuqrQXOApA0GzgMmJa4rZmZNVHZk95XAj2S1gAXAauBXaP5AEkLJPVJ6tu6\ndWsRMZqZGTChwM8eAKZXvZ+Wl70kIrYD8wEkCXgE2AR0j7Rt1WcsA5YBVCqVGKfYzcysRpFHGPcB\nR0o6XNK+wNnALdUNJPXkdQDnA3flSWTEbc3MrLkKO8KIiJ2SLgR6gS5geURskHRBXr8UOAq4VlIA\nG4Dzhtu2qFjNzGxkith7zuJI2gr8eg83nwT8ZhzDGW+Ob2wc39g4vrFp5fgOi4jJKQ33qoQxFpL6\nIqJSdhyNOL6xcXxj4/jGptXjS1X2VVJmZtYmnDDMzCyJE8bLlpUdwAgc39g4vrFxfGPT6vEl8RyG\nmZkl8RGGmZkl6biEkbDkuiT9c16/TtLxTYxtuqQ7Jf1C0gZJF9dpc5KkZyStyb8+3az48v4flbQ+\n77uvTn2Z4zezalzWSNou6ZKaNk0dP0nLJT0p6YGqstdJ+pGkh/N/D2qwbeFL/DeIb7Gkh/Kf302S\nehpsO+y+UGB8fyNpoOpneGqDbcsav+9UxfZovvRRvW0LH79xFxEd80V2E+CvgCOAfckWP5xV0+ZU\n4AeAgBOAe5oY3yHA8fnrA4Ff1onvJODWEsfwUWDSMPWljV+dn/V/kl1jXtr4Ae8EjgceqCr7AnBZ\n/voy4PMN4h92Xy0wvvcCE/LXn68XX8q+UGB8fwP8r4SffynjV1P/T8Cnyxq/8f7qtCOMlGXTzwCu\ni8zPyRZHPKQZwUXE4xFxf/76WeBB2m+V3tLGr8bJwK8iYk9v5BwXEXEX8FRN8RnAtfnra4Ez62za\nlCX+68UXEbdHxM787c/J1nIrRYPxS1Ha+A3J18f7APDt8e63LJ2WMFKWTW+JpdUlzQCOA+6pU31i\nfrrgB5Le1NTAIIAfS1olaUGd+pYYP7L1xxr9opY5fgAHR8Tj+ev/BA6u06ZVxvFjZEeM9Yy0LxTp\novxnuLzBKb1WGL93AE9ExMMN6sscvz3SaQmjLUg6APg+cElkizFWux84NLKnFH4ZWNnk8P40Io4l\nexriJyW9s8n9j0jZgpWnA9+rU132+O0msnMTLXmpoqQrgJ3A9Q2alLUvfI3sVNOxwONkp31a0TyG\nP7po+d+lWp2WMEZccj2xTWEkTSRLFtdHxIra+ojYHhG/y1/fBkyUNKlZ8UXEQP7vk8BNZIf+1Uod\nv9xc4P6IeKK2ouzxyz0xdJou//fJOm3K3g8/CpwGfChPaq+QsC8UIiKeiIhdEfEi8C8N+i17/CaQ\nPRzuO43alDV+Y9FpCSNl2fRbgHPzq31OAJ6pOn1QqPyc59XAgxHxxQZt/kvebugphfsAv21SfK+W\ndODQa7LJ0QdqmpU2flUa/s+uzPGrcgvwkfz1R4Cb67QpbYl/SacAfw2cHhHPNWiTsi8UFV/1nNhf\nNOi37EckvAd4KCI216ssc/zGpOxZ92Z/kV3F80uyKyiuyMsuAC7IXwtYktevBypNjO1PyU5PrAPW\n5F+n1sR3IdlS8GvJJiRPbGJ8R+T9rs1jaKnxy/t/NVkCeG1VWWnjR5a4Hgd2kJ1HPw/4I+AnwMPA\nj4HX5W2nALcNt682Kb6NZOf/h/bBpbXxNdoXmhTfv+b71jqyJHBIK41fXv6NoX2uqm3Tx2+8v3yn\nt5mZJem0U1JmZraHnDDMzCyJE4aZmSVxwjAzsyROGGZmlsQJw9qKstV859SUXSLpayNs97uC45os\n6R5JqyW9o6bu3yRV8teHK1uldk6dz1isbJXixXsYw0mSbq16/1lJP5T0qjyGvqq6iqR/q9ouJL2v\nqv5WSSftSRy293LCsHbzbbKbsKoNt25Us5wMrI+I4yLi7noNJE0DfghcGhG9dZosAI6JiIUpHeZ3\nEzeq+xTwduAvIuIPefHrJc1tsMlm4IqUfq1zOWFYu7kR+PP87t2hRRqnAHdLOkDSTyTdnz9n4BWr\nk9b5X/hX8mUwkPRWSf+eLwbXW2+VXUkzJN2RL3z3E0mHSjqWbMnyM5Q926C7TtyHALeT3aD1ijuO\nJd0CHACskvTBev3k7b4haamke/I+X0HSpWTLo7wvIgarqhbTOCmsBZ6R9GcN6s2cMKy9RMRTwL1k\nfxAhO7r4bmR3oD5P9j/q44F3Af80tAzISPI1vL4MvD8i3gosBz5Xp+mXgWsjW7zweuCfI2IN8Gng\nOxFxbM0f6SHXAl+JiBsbfF+nA4P59t+p109V82lkd6j/zzof9XayO9vnRr5mVpWfAS9Iele9GPLv\n91MN6sycMKwtVZ+Wqj4dJeAfJK0jW3JjKvWXDq9nJnA08CNlT0j7FPWfA/E24Fv5638lW84lxY+B\ncyTtn9h+uH6+FxG7Gmy3kWwcGh0pfJYGSSGyZzsgKfV7sg7jhGHt6GbgZGWPf90/Ilbl5R8CJgNv\njWzZ6CeA/Wq23cnu+/1QvYAN+f/wj42IN0fEe8cx5i+QLYj3veHmHhL9fpi6J8jWUPpSvSOJiLgD\n6CZ7GmI9PsqwhpwwrO3kp1ruJDttVD3Z/VrgyYjYkf+xPKzO5r8GZuVXDvWQTVYD9AOTJb0NslNU\nqv9wpf/Hy0c3HwLqTnA3cAmwHbg64VTZHvcTEb8kW1r7m/n8Sq3Pkq1GW2/b24GDgGNS+7PO4YRh\n7erbwFvYPWFcD1QkrQfOBR6q3SgiHgO+S7aU9HeB1Xn5C8D7gc9LWku2SuuJdfq9CJifn/b6MHBx\nasD5PMtHyCbA605Yj0c/eV/3AfOBWyS9oabuNmDrMJt/jt2fJWEG4NVqzcwsjY8wzMwsiROGmZkl\nccIwM7MkThhmZpbECcPMzJI4YZiZWRInDDMzS+KEYWZmSf4/SEfKA1ZtfTYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x112806c50>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "import numpy as np\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "test_range = range(20)\n",
    "scores = []\n",
    "for t in test_range:\n",
    "    X_train, X_test, y_train, y_test = \\\n",
    "    train_test_split(X, y, test_size=0.4, random_state=t)\n",
    "    \n",
    "    knn = KNeighborsClassifier(n_neighbors=6)\n",
    "    knn.fit(X_train, y_train)\n",
    "    y_pred = knn.predict(X_test)\n",
    "    scores.append(metrics.accuracy_score(y_test, y_pred))\n",
    "    \n",
    "# plot the relationship between K and testing accuracy\n",
    "plt.scatter(test_range, scores)\n",
    "plt.xlabel('Value of K for KNN')\n",
    "plt.ylabel('Testing Accuracy')\n",
    "print(list(zip(scores, test_range)))\n",
    "scores = np.array(scores)\n",
    "print('best [score, k] pair = [%g, %g]' % (np.max(scores),k_range[np.argmax(scores)]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resources\n",
    "\n",
    "- Quora: [What is an intuitive explanation of overfitting?](http://www.quora.com/What-is-an-intuitive-explanation-of-overfitting/answer/Jessica-Su)\n",
    "- Video: [Estimating prediction error](https://www.youtube.com/watch?v=_2ij6eaaSl0&t=2m34s) (12 minutes, starting at 2:34) by Hastie and Tibshirani\n",
    "- [Understanding the Bias-Variance Tradeoff](http://scott.fortmann-roe.com/docs/BiasVariance.html)\n",
    "    - [Guiding questions](https://github.com/justmarkham/DAT8/blob/master/homework/09_bias_variance.md) when reading this article\n",
    "- Video: [Visualizing bias and variance](http://work.caltech.edu/library/081.html) (15 minutes) by Abu-Mostafa"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}