{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 7: k-Nearest Neighbors (kNN)\n",
    "\n",
    "> (c) 2019 Galit Shmueli, Peter C. Bruce, Peter Gedeck \n",
    ">\n",
    "> Code included in\n",
    ">\n",
    "> _Data Mining for Business Analytics: Concepts, Techniques, and Applications in Python_ (First Edition) \n",
    "> Galit Shmueli, Peter C. Bruce, Peter Gedeck, and Nitin R. Patel. 2019.\n",
    "\n",
    "## Import required packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:04.853954Z",
     "iopub.status.busy": "2021-05-27T20:03:04.853521Z",
     "iopub.status.idle": "2021-05-27T20:03:05.649646Z",
     "shell.execute_reply": "2021-05-27T20:03:05.649144Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no display found. Using non-interactive Agg backend\n"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "import pandas as pd\n",
    "from sklearn import preprocessing\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.neighbors import NearestNeighbors, KNeighborsClassifier\n",
    "import matplotlib.pylab as plt\n",
    "\n",
    "import dmba\n",
    "\n",
    "%matplotlib inline\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Table 7.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:05.653676Z",
     "iopub.status.busy": "2021-05-27T20:03:05.653254Z",
     "iopub.status.idle": "2021-05-27T20:03:05.668593Z",
     "shell.execute_reply": "2021-05-27T20:03:05.668219Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Income</th>\n",
       "      <th>Lot_Size</th>\n",
       "      <th>Ownership</th>\n",
       "      <th>Number</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>60.0</td>\n",
       "      <td>18.4</td>\n",
       "      <td>Owner</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>85.5</td>\n",
       "      <td>16.8</td>\n",
       "      <td>Owner</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>64.8</td>\n",
       "      <td>21.6</td>\n",
       "      <td>Owner</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>61.5</td>\n",
       "      <td>20.8</td>\n",
       "      <td>Owner</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>87.0</td>\n",
       "      <td>23.6</td>\n",
       "      <td>Owner</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>110.1</td>\n",
       "      <td>19.2</td>\n",
       "      <td>Owner</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>108.0</td>\n",
       "      <td>17.6</td>\n",
       "      <td>Owner</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>82.8</td>\n",
       "      <td>22.4</td>\n",
       "      <td>Owner</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>69.0</td>\n",
       "      <td>20.0</td>\n",
       "      <td>Owner</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Income  Lot_Size Ownership  Number\n",
       "0    60.0      18.4     Owner       1\n",
       "1    85.5      16.8     Owner       2\n",
       "2    64.8      21.6     Owner       3\n",
       "3    61.5      20.8     Owner       4\n",
       "4    87.0      23.6     Owner       5\n",
       "5   110.1      19.2     Owner       6\n",
       "6   108.0      17.6     Owner       7\n",
       "7    82.8      22.4     Owner       8\n",
       "8    69.0      20.0     Owner       9"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mower_df = dmba.load_data('RidingMowers.csv')\n",
    "mower_df['Number'] = mower_df.index + 1\n",
    "mower_df.head(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:05.673608Z",
     "iopub.status.busy": "2021-05-27T20:03:05.673176Z",
     "iopub.status.idle": "2021-05-27T20:03:05.680451Z",
     "shell.execute_reply": "2021-05-27T20:03:05.679929Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(14, 4) (10, 4)\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Income</th>\n",
       "      <th>Lot_Size</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>60</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Income  Lot_Size\n",
       "0      60        20"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trainData, validData = train_test_split(mower_df, test_size=0.4, random_state=26)\n",
    "print(trainData.shape, validData.shape)\n",
    "newHousehold = pd.DataFrame([{'Income': 60, 'Lot_Size': 20}])\n",
    "newHousehold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scatter plot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:05.688286Z",
     "iopub.status.busy": "2021-05-27T20:03:05.687815Z",
     "iopub.status.idle": "2021-05-27T20:03:05.987594Z",
     "shell.execute_reply": "2021-05-27T20:03:05.987215Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 15480 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig, ax = plt.subplots()\n",
    "\n",
    "subset = trainData.loc[trainData['Ownership']=='Owner']\n",
    "ax.scatter(subset.Income, subset.Lot_Size, marker='o', label='Owner', color='C1')\n",
    "\n",
    "subset = trainData.loc[trainData['Ownership']=='Nonowner']\n",
    "ax.scatter(subset.Income, subset.Lot_Size, marker='D', label='Nonowner', color='C0')\n",
    "\n",
    "ax.scatter(newHousehold.Income, newHousehold.Lot_Size, marker='*', label='New household', color='black', s=150)\n",
    "\n",
    "plt.xlabel('Income')  # set x-axis label\n",
    "plt.ylabel('Lot_Size')  # set y-axis label\n",
    "for _, row in trainData.iterrows():\n",
    "    ax.annotate(row.Number, (row.Income + 2, row.Lot_Size))\n",
    "    \n",
    "handles, labels = ax.get_legend_handles_labels()\n",
    "ax.set_xlim(40, 115)\n",
    "ax.legend(handles, labels, loc=4)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:06.012824Z",
     "iopub.status.busy": "2021-05-27T20:03:06.008674Z",
     "iopub.status.idle": "2021-05-27T20:03:06.329980Z",
     "shell.execute_reply": "2021-05-27T20:03:06.329602Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 20444 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def plotDataset(ax, data, showLabel=True, **kwargs):\n",
    "    subset = data.loc[data['Ownership']=='Owner']\n",
    "    ax.scatter(subset.Income, subset.Lot_Size, marker='o', label='Owner' if showLabel else None, color='C1', **kwargs)\n",
    "\n",
    "    subset = data.loc[data['Ownership']=='Nonowner']\n",
    "    ax.scatter(subset.Income, subset.Lot_Size, marker='D', label='Nonowner' if showLabel else None, color='C0', **kwargs)\n",
    "\n",
    "    plt.xlabel('Income')  # set x-axis label\n",
    "    plt.ylabel('Lot_Size')  # set y-axis label\n",
    "    for _, row in data.iterrows():\n",
    "        ax.annotate(row.Number, (row.Income + 2, row.Lot_Size))\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "\n",
    "plotDataset(ax, trainData)\n",
    "plotDataset(ax, validData, showLabel=False, facecolors='none')\n",
    "\n",
    "ax.scatter(newHousehold.Income, newHousehold.Lot_Size, marker='*', label='New household', color='black', s=150)\n",
    "\n",
    "plt.xlabel('Income')  # set x-axis label\n",
    "plt.ylabel('Lot_Size')  # set y-axis label\n",
    "    \n",
    "handles, labels = ax.get_legend_handles_labels()\n",
    "ax.set_xlim(40, 115)\n",
    "ax.legend(handles, labels, loc=4)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Table 7.2\n",
    "Initialize normalized training, validation, and complete data frames. Use the training data to learn the transformation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:06.343520Z",
     "iopub.status.busy": "2021-05-27T20:03:06.342996Z",
     "iopub.status.idle": "2021-05-27T20:03:06.345127Z",
     "shell.execute_reply": "2021-05-27T20:03:06.345465Z"
    }
   },
   "outputs": [],
   "source": [
    "scaler = preprocessing.StandardScaler()\n",
    "scaler.fit(trainData[['Income', 'Lot_Size']])  # Note the use of an array of column names\n",
    "\n",
    "# Transform the full dataset\n",
    "mowerNorm = pd.concat([pd.DataFrame(scaler.transform(mower_df[['Income', 'Lot_Size']]), \n",
    "                                    columns=['zIncome', 'zLot_Size']),\n",
    "                       mower_df[['Ownership', 'Number']]], axis=1)\n",
    "trainNorm = mowerNorm.iloc[trainData.index]\n",
    "validNorm = mowerNorm.iloc[validData.index]\n",
    "newHouseholdNorm = pd.DataFrame(scaler.transform(newHousehold), columns=['zIncome', 'zLot_Size'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use k-nearest neighbour"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:06.356495Z",
     "iopub.status.busy": "2021-05-27T20:03:06.356037Z",
     "iopub.status.idle": "2021-05-27T20:03:06.358446Z",
     "shell.execute_reply": "2021-05-27T20:03:06.358830Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     zIncome  zLot_Size Ownership  Number\n",
      "3  -0.409776   0.743358     Owner       4\n",
      "13 -0.804953   0.743358  Nonowner      14\n",
      "0  -0.477910  -0.174908     Owner       1\n"
     ]
    }
   ],
   "source": [
    "knn = NearestNeighbors(n_neighbors=3)\n",
    "knn.fit(trainNorm[['zIncome', 'zLot_Size']])\n",
    "distances, indices = knn.kneighbors(newHouseholdNorm)\n",
    "print(trainNorm.iloc[indices[0], :])  # indices is a list of lists, we are only interested in the first element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Table 7.3\n",
    "Initialize a data frame with two columns: `k` and `accuracy`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:06.375434Z",
     "iopub.status.busy": "2021-05-27T20:03:06.374956Z",
     "iopub.status.idle": "2021-05-27T20:03:06.427712Z",
     "shell.execute_reply": "2021-05-27T20:03:06.427353Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     k  accuracy\n",
      "0    1       0.6\n",
      "1    2       0.7\n",
      "2    3       0.8\n",
      "3    4       0.9\n",
      "4    5       0.7\n",
      "5    6       0.9\n",
      "6    7       0.9\n",
      "7    8       0.9\n",
      "8    9       0.9\n",
      "9   10       0.8\n",
      "10  11       0.8\n",
      "11  12       0.9\n",
      "12  13       0.4\n",
      "13  14       0.4\n"
     ]
    }
   ],
   "source": [
    "train_X = trainNorm[['zIncome', 'zLot_Size']]\n",
    "train_y = trainNorm['Ownership']\n",
    "valid_X = validNorm[['zIncome', 'zLot_Size']]\n",
    "valid_y = validNorm['Ownership']\n",
    "\n",
    "# Train a classifier for different values of k\n",
    "results = []\n",
    "for k in range(1, 15):\n",
    "    knn = KNeighborsClassifier(n_neighbors=k).fit(train_X, train_y)\n",
    "    results.append({\n",
    "        'k': k,\n",
    "        'accuracy': accuracy_score(valid_y, knn.predict(valid_X))\n",
    "    })\n",
    "\n",
    "# Convert results to a pandas data frame\n",
    "results = pd.DataFrame(results)\n",
    "print(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Table 7.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-05-27T20:03:06.441970Z",
     "iopub.status.busy": "2021-05-27T20:03:06.441521Z",
     "iopub.status.idle": "2021-05-27T20:03:06.444627Z",
     "shell.execute_reply": "2021-05-27T20:03:06.444255Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Owner']\n",
      "Distances [[0.31358009 0.40880312 0.44793643 0.61217726]]\n",
      "Indices [[ 3  8 13  0]]\n",
      "     zIncome  zLot_Size Ownership  Number\n",
      "3  -0.409776   0.743358     Owner       4\n",
      "8  -0.069107   0.437269     Owner       9\n",
      "13 -0.804953   0.743358  Nonowner      14\n",
      "0  -0.477910  -0.174908     Owner       1\n"
     ]
    }
   ],
   "source": [
    "# Retrain with full dataset\n",
    "mower_X = mowerNorm[['zIncome', 'zLot_Size']]\n",
    "mower_y = mowerNorm['Ownership']\n",
    "knn = KNeighborsClassifier(n_neighbors=4).fit(mower_X, mower_y)\n",
    "distances, indices = knn.kneighbors(newHouseholdNorm)\n",
    "print(knn.predict(newHouseholdNorm))\n",
    "print('Distances',distances)\n",
    "print('Indices', indices)\n",
    "print(mowerNorm.iloc[indices[0], :])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
