lab_3_decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision Tree Lab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.base import BaseEstimator, ClassifierMixin\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. (40%) Correctly implement the ID3 decision tree algorithm, including the ability to handle unknown attributes (You do not need to handle real valued attributes).  \n",
    "### Code Requirements/Notes:\n",
    "- Use standard information gain as your basic attribute evaluation metric.  (Note that normal ID3 would usually augment information gain with gain ratio or some other mechanism to penalize statistically insignificant attribute splits. Otherwise, even with approaches like pruning below, the SSE type of overfit could still hurt us.) \n",
    "- You are welcome to create other classes and/or functions in addition to the ones provided below. (e.g. If you build out a tree structure, you might create a node class).\n",
    "- It is a good idea to use a simple data set (like the lenses data or the pizza homework), which you can check by hand, to test your algorithm to make sure that it is working correctly. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DTClassifier(BaseEstimator,ClassifierMixin):\n",
    "\n",
    "    def __init__(self,counts=None):\n",
    "        \"\"\" Initialize class with chosen hyperparameters.\n",
    "        Args:\n",
    "        Optional Args (Args we think will make your life easier):\n",
    "            counts: A list of Ints that tell you how many types of each feature there are\n",
    "        Example:\n",
    "            DT  = DTClassifier()\n",
    "            or\n",
    "            DT = DTClassifier(count = [2,3,2,2])\n",
    "            Dataset = \n",
    "            [[0,1,0,0],\n",
    "            [1,2,1,1],\n",
    "            [0,1,1,0],\n",
    "            [1,2,0,1],\n",
    "            [0,0,1,1]]\n",
    "\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "    def fit(self, X, y):\n",
    "        \"\"\" Fit the data; Make the Decision tree\n",
    "\n",
    "        Args:\n",
    "            X (array-like): A 2D numpy array with the training data, excluding targets\n",
    "            y (array-like): A 1D numpy array with the training targets\n",
    "\n",
    "        Returns:\n",
    "            self: this allows this to be chained, e.g. model.fit(X,y).predict(X_test)\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        return self\n",
    "\n",
    "    def predict(self, X):\n",
    "        \"\"\" Predict all classes for a dataset X\n",
    "\n",
    "        Args:\n",
    "            X (array-like): A 2D numpy array with the training data, excluding targets\n",
    "\n",
    "        Returns:\n",
    "            array, shape (n_samples,)\n",
    "                Predicted target values per element in X.\n",
    "        \"\"\"\n",
    "        pass\n",
    "\n",
    "\n",
    "    def score(self, X, y):\n",
    "        \"\"\" Return accuracy(Classification Acc) of model on a given dataset. Must implement own score function.\n",
    "\n",
    "        Args:\n",
    "            X (array-like): A 2D numpy array with data, excluding targets\n",
    "            y (array-like): A 1D numpy array of the targets \n",
    "        \"\"\"\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Debug\n",
    "\n",
    "Debug your model by training on the lenses dataset: [Debug Dataset](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/lenses.arff)\n",
    "\n",
    "Test your model on the lenses test set: [Debug Test Dataset](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/lenses_test.arff)\n",
    "\n",
    "Parameters:\n",
    "(optional) counts = [3,2,2,2] (You should compute this when you read in the data, before fitting)\n",
    "\n",
    "---\n",
    "\n",
    "Expected Results: Accuracy = [0.33]\n",
    "\n",
    "Predictions should match this file: [Lenses Predictions](https://raw.githubusercontent.com/cs472ta/CS472/master/debug_solutions/pred_lenses.csv)\n",
    "\n",
    "*NOTE: The [Lenses Prediction](https://raw.githubusercontent.com/cs472ta/CS472/master/debug_solutions/pred_lenses.csv) uses the following encoding: soft=2, hard=0, none=1. If your encoding is different, then your output will be different, but not necessarily incorrect.*\n",
    "\n",
    "Split Information Gains (These do not need to be in this exact order):\n",
    "\n",
    "[0.5487949406953987, 0.7704260414863775, 0.3166890883150208, 1.0, 0.4591479170272447, 0.9182958340544894]\n",
    "\n",
    "<!-- You should be able to get about 68% (61%-82%) predictive accuracy on the lenses data -->\n",
    "\n",
    "Here's what your decision tree splits should look like, and the corresponding child node predictions:\n",
    "\n",
    "Decision Tree:\n",
    "<pre>\n",
    "tear_prod_rate = normal:\n",
    "    astigmatism = no:\n",
    "        age = pre_presbyopic:\n",
    "            prediction: soft\n",
    "        age = presbyopic:\n",
    "            spectacle_prescrip = hypermetrope:\n",
    "                prediction: soft\n",
    "            spectacle_prescrip = myope:\n",
    "                prediction: none\n",
    "        age = young:\n",
    "            prediction: soft\n",
    "    astigmatism = yes:\n",
    "        spectacle_prescrip = hypermetrope:\n",
    "            age = pre_presbyopic:\n",
    "                prediction: none\n",
    "            age = presbyopic:\n",
    "                prediction: none\n",
    "            age = young:\n",
    "                prediction: hard\n",
    "        spectacle_prescrip = myope:\n",
    "            prediction: hard\n",
    "tear_prod_rate = reduced:\n",
    "    prediction: none\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load debug training data \n",
    "\n",
    "\n",
    "# Train Decision Tree\n",
    "\n",
    "\n",
    "# Load debug test data\n",
    "\n",
    "\n",
    "# Predict and compute model accuracy\n",
    "\n",
    "\n",
    "# Print the information gain of every split you make.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Optional/Additional Debugging Dataset - Pizza Homework\n",
    "# pizza_dataset = np.array([[1,2,0],[0,0,0],[0,1,1],[1,1,1],[1,0,0],[1,0,1],[0,2,1],[1,0,0],[0,2,0]])\n",
    "# pizza_labels = np.array([2,0,1,2,1,2,1,1,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 Evaluation\n",
    "\n",
    "We will evaluate your model based on its performance on the zoo dataset. \n",
    "\n",
    "Train your model using this dataset: [Evaluation Train Dataset](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/zoo.arff)\n",
    "\n",
    "Test your model on this dataset: [Evaluation Test Dataset](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/zoo_test.arff)\n",
    "\n",
    "Parameters:\n",
    "(optional) counts = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2] (You should compute this when you read in the data, before fitting)\n",
    "\n",
    "---\n",
    "Print out your accuracy on the evaluation test dataset.\n",
    "\n",
    "Print out the information gain of every split you make."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load evaluation training data\n",
    "\n",
    "\n",
    "# Train Decision Tree\n",
    "\n",
    "\n",
    "# Load evaluation test data\n",
    "\n",
    "\n",
    "# Print out the information gain for every split you make\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. (20%) You will use your ID3 algorithm to induce decision trees for the cars dataset and the voting dataset.  Do not use a stopping criteria, but induce the tree as far as it can go (until classes are pure or there are no more data or attributes to split on).  \n",
    "- Implement and use 10-fold Cross Validation (CV) on each data set to predict how well the models will do on novel data.  \n",
    "- For each dataset, report the training and test classification accuracy for each fold and the average test accuracy. \n",
    "- As a rough sanity check, typical decision tree accuracies for these data sets are: Cars: .90-.95, Vote: .92-.95."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 Implement 10-fold Cross Validation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write a function that implements 10-fold cross validation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  2.2 Cars Dataset\n",
    "- Use this [Cars Dataset](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/cars.arff)\n",
    "- Make a table for your K-Fold cross validation accuracies\n",
    "\n",
    "*If you are having trouble using scipy's loadarff function (scipy.io.arff.loadarff), try:*\n",
    "\n",
    "*pip install arff &nbsp;&nbsp;&nbsp;&nbsp;          # Install arff library*\n",
    "\n",
    "*import arff as arf*                   \n",
    "\n",
    "*cars = list(arf.load('cars.arff'))   &nbsp;&nbsp;&nbsp;&nbsp;# Load your downloaded dataset (!curl, etc.)*\n",
    "\n",
    "*df = pd.DataFrame(cars)*  \n",
    "\n",
    "*There may be additional cleaning needed*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use 10-fold CV on Cars Dataset\n",
    "\n",
    "# Report Training and Test Classification Accuracies\n",
    "\n",
    "# Report Average Test Accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3 Voting Dataset\n",
    "- Use this [Voting Dataset with missing values](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/voting_with_missing.arff)\n",
    "- Note that you will need to support unknown attributes in the voting data set. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Used 10-fold CV on Voting Dataset\n",
    "\n",
    "# Report Training and Test Classification Accuracies\n",
    "\n",
    "# Report Average Test Accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.4 Discuss Your Results\n",
    "\n",
    "- Summarize your results from both datasets, and discuss what you observed. \n",
    "- A fully expanded tree will often get 100% accuracy on the training set. Why does this happen and in what cases might it not?  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discuss your results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. (15%) For each of the two problems above, summarize in English what the decision tree has learned (i.e. look at the induced tree and describe what rules it has discovered to try to solve each task). \n",
    "- If the tree is very large you can just discuss a few of the more shallow attribute combinations and the most important decisions made high in the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.1 Discuss what the decision tree induced on the cars dataset has learned"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discussion Here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.2 Discuss what the decision tree induced on the voting dataset has learned"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discussion Here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3 How did you handle unknown attributes in the voting problem? Why did you choose this approach? (Do not use the approach of just throwing out data with unknown attributes)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discuss how you handled unknown attributes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.1 (10%) Use SciKit Learn's decision tree on the voting dataset and compare your results. Try different parameters and report what parameters perform the best on the test set. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1.1 SK Learn on Voting Dataset\n",
    "- Use this [Voting Dataset with missing values](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/voting_with_missing.arff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use SK Learn's Decision Tree to learn the voting dataset\n",
    "\n",
    "# Explore different parameters\n",
    "\n",
    "# Report results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discuss results & compare to your method's results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 (10%) Choose a data set of your choice (not already used in this or previous labs) and use the SK decision tree to learn it. Experiment with different hyper-parameters to try to get the best results possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use SciKit Learn's Decision Tree on a new dataset\n",
    "\n",
    "# Experiment with different hyper-parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. (5%) Visualize sklearn's decision tree for your chosen data set (using export_graphviz or another tool) and discuss what you find. If your tree is too deep to reasonably fit on one page, show only the first several levels (e.g. top 5)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Include decision tree visualization here\n",
    "\n",
    "# Discuss what the model has learned"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. (optional 5% extra credit) Implement reduced error pruning to help avoid overfitting.  \n",
    "- You will need to take a validation set out of your training data to do this, while still having a test set to test your final accuracy. \n",
    "- Create a table comparing your decision tree implementation's results on the cars and voting data sets with and without reduced error pruning. \n",
    "- This table should compare:\n",
    "    - a) The # of nodes (including leaf nodes) and tree depth of the final decision trees \n",
    "    - b) The generalization (test set) accuracy. (For the unpruned 10-fold CV models, just use their average values in the table)."
   ]
  },
  {
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}