PA6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [CPSC 310](https://github.com/GonzagaCPSC310) Data Mining\n",
    "[Gonzaga University](https://www.gonzaga.edu/)\n",
    "\n",
    "[Gina Sprint](http://cs.gonzaga.edu/faculty/sprint/)\n",
    "# PA6 Decision Trees (100 pts)\n",
    "\n",
    "## Learner Objectives\n",
    "At the conclusion of this programming assignment, participants should be able to:\n",
    "* Represent a tree in Python as a nested list\n",
    "* Implement a decision tree classifier using the TDIDT algorithm\n",
    "* Select an attribute using partition entropy\n",
    "* Extract rules from a decision tree\n",
    "\n",
    "\n",
    "## Prerequisites\n",
    "Before starting this programming assignment, participants should be able to:\n",
    "* Implement a $k$NN and Naive Bayes classifier\n",
    "* Evaluate classifiers using train/test sets\n",
    "* Understand tree representations and common tree traversal algorithms\n",
    "* Understand recursion\n",
    "\n",
    "## Acknowledgments\n",
    "Content used in this assignment is based upon information in the following sources:\n",
    "* Dr. Shawn Bowers' Data Mining HW5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Github Classroom Setup\n",
    "For this assignment, you will use GitHub Classroom to create a private code repositories to track code changes and submit your assignment. Open this PA6 link to accept the assignment and create a private repository for your assignment in Github classroom: https://classroom.github.com/a/ZxvGubQy\n",
    "\n",
    "Your repo, for example, will be named GonzagaCPSC310/pa6-yourusername (where yourusername is your Github username). I highly recommend committing/pushing regularly so your work is always backed up. We will grade your most recent commit, even if that commit is after the due date (your work will be marked late if this is the case)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview and Requirements\n",
    "Write a program (`pa6.py`) that builds a decision classifier for the \"pre-processed\" automobile dataset (auto-data.txt) you created for PA1 (pick one method to deal with missing values for this assignment (e.g., eliminate rows with missing values, use means or medians, etc.)) and the titanic dataset. Download the titanic.txt dataset from https://github.com/GonzagaCPSC310/PAs/tree/master/files\n",
    "\n",
    "For this assignment you will need to perform the following steps and turn in your source code and a log of any assumptions and/or issues you had in doing the steps. Your log needs to be written separately from your .py file and may be written in a .txt or a .md (markdown) file.\n",
    "\n",
    "Note: as you write solutions for the following steps, I highly encourage you to design functions that are generic and re-usable for future programming assignments and data mining tasks.\n",
    "\n",
    "Note: we are learning data mining from scratch! The only libraries you should need to use for this assignment include numpy (sparingly), csv (if you'd like to use it for file I/O), and tabulate (if you'd like to use it for pretty printing). This means no pandas..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1\n",
    "Create a decision tree classifier for the \"interview\" dataset from class using the entropy selection method described in class. Your classifier should predict the class values from the level, lang, tweets, and phd attributes. Since each attribute is categorical, you do not need to perform any discretization, etc. Represent your decision tree using the nested list representation described in class. Check your entropy calculations and decision tree rules with your completed work on the \"Entropy Lab\" we started in class. Only after you are confident that your decision tree classifier is working correctly, move on to the next step. For convenience, I've provided the column names and dataset as Python lists below: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "col_names = [\"level\", \"lang\", \"tweets\", \"phd\", \"interviewed_well\"]\n",
    "table = [\n",
    "        [\"Senior\", \"Java\", \"no\", \"no\", \"False\"],\n",
    "        [\"Senior\", \"Java\", \"no\", \"yes\", \"False\"],\n",
    "        [\"Mid\", \"Python\", \"no\", \"no\", \"True\"],\n",
    "        [\"Junior\", \"Python\", \"no\", \"no\", \"True\"],\n",
    "        [\"Junior\", \"R\", \"yes\", \"no\", \"True\"],\n",
    "        [\"Junior\", \"R\", \"yes\", \"yes\", \"False\"],\n",
    "        [\"Mid\", \"R\", \"yes\", \"yes\", \"True\"],\n",
    "        [\"Senior\", \"Python\", \"no\", \"no\", \"False\"],\n",
    "        [\"Senior\", \"R\", \"yes\", \"no\", \"True\"],\n",
    "        [\"Junior\", \"Python\", \"yes\", \"no\", \"True\"],\n",
    "        [\"Senior\", \"Python\", \"yes\", \"yes\", \"True\"],\n",
    "        [\"Mid\", \"Python\", \"no\", \"yes\", \"True\"],\n",
    "        [\"Mid\", \"Java\", \"yes\", \"no\", \"True\"],\n",
    "        [\"Junior\", \"Python\", \"no\", \"yes\", \"False\"]\n",
    "    ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2\n",
    "Create a decision tree classifier for the titanic dataset. Since each attribute is categorical, you do not need to perform any discretization, etc. Use the majority voting method to deal with clashes. Test your classifier using stratified k-fold cross-validation (with k = 10), and compare your results to those from PA5. Also create a confusion matrix for the result and format your results as per PA4 and PA5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 3\n",
    "Create a decision tree classifier that predicts mpg rankings (given in PA2)) from the cylinders, weight, and model year attributes. Discretize weights using the NHTSA vehicle sizes from PA5:\n",
    "\n",
    "|Ranking |Range|\n",
    "|-|-|\n",
    "|5 |$\\geq$ 3500\n",
    "|4 |3000-3499|\n",
    "|3 |2500-2999|\n",
    "|2 |2000-2499|\n",
    "|1 |$\\leq$ 1999|\n",
    "\n",
    "Test your classifier using stratified k-fold cross-validation (with k = 10), and compare your results to those from PA4 and PA5. Also create a confusion matrix for the result and format your results as per PA4 and PA5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 4\n",
    "For steps 2 and 3, have your program print out the rules inferred from your decision tree classifiers when run over the entire dataset (as opposed to the cross validation trees). Your rules should take the form:\n",
    "\n",
    "```\n",
    "IF att == val AND ... THEN class = label\n",
    "IF att == val AND ... THEN class = label\n",
    "...\n",
    "```\n",
    "\n",
    "Based on your results, determine ways your trees can/should be pruned. Note you do not need to write code\n",
    "to perform pruning, just explain how they can be pruned and give the resulting \"pruned\" rules."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BONUS (5 pts)\n",
    "Extend your script to automatically generate a Graphviz .dot file to produce a visual representation of the decision trees from step 4. \n",
    "\n",
    "Include the code with your script and also hand in the graphs generated as PDF files (produced via dot)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Submitting Assignments\n",
    "1. Use Github classroom to submit your assignment via a Github repo. See the \"Github Classroom Setup\" section at the beginning of this document for details on how to do this. You must commit your solution by the due date and time.\n",
    "1. Your repo should contain only your .py file(s), your input .csv/.txt file(s), and your log file (.txt or .md) file(s). Double check that this is the case by cloning (or downloading a zip) your submission repo and running your code from command line like we will when we grade your code. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grading Guidelines\n",
    "This assignment is worth 100 points + 5 points bonus. Your assignment will be evaluated based on a successful compilation from command line (using the Anaconda Python Distribution v3.7) and adherence to the program requirements. We will grade according to the following criteria:\n",
    "* 25 pts for correct step 1\n",
    "* 20 pts for correct step 2\n",
    "* 20 pts for correct step 3\n",
    "* 20 pts for correct step 4\n",
    "* 5 pts for quantity and quality of Github commit messages\n",
    "* 10 pts for adherence to course [coding standard](https://nbviewer.jupyter.org/github/GonzagaCPSC310/PAs/blob/master/Coding%20Standard.ipynb)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}