Decision Tree Lab.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision Tree Lab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "from scipy.io import arff\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Debug and Eval\n",
    "\n",
    "### 1.1 (5%) Debug \n",
    "\n",
    "- Train a DecisionTreeClassifier on the [Iris Dataset](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/iris.arff) using all default parameters.\n",
    "- If using Dataframes you may want to change the class values from bytecodes to strings with\n",
    "iris_df['class'] = iris_df['class'].str.decode('utf-8') \n",
    "\n",
    "Expected Accuracy = [1.0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Debug"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 (5%) Evaluation \n",
    "\n",
    "- Train on the iris data set again but this time with max_depth = 3 and output the accuracy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion\n",
    "What did you see? What were the differences in accuracy between the two trained models? How do you account for the differences or no differences? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Missing Values, N-fold CV, and Decision Tree Items  \n",
    "\n",
    "### 2.1 (15%) Handling missing values\n",
    "- Use this [Voting Dataset with missing values](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/voting_with_missing.arff)\n",
    "- This data set has missing data.  Create an extra feature value for each feature with missing data. For example, if the feature were color with possible values R, G, B, you would add a fourth value (e.g. U or ? for unknown).\n",
    "- Do not use a stopping criteria. 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",
    "- SKlearn does not allow nominal features, which initially seems odd. However, SKlearn uses the binary CART algorithm where a nominal data value like color is broken down into blue or not blue, red or not red, etc.  It is thus natural to just use one-hot encoding for each nominal feature.\n",
    "- Use an 80/20 train/test split.\n",
    "- Report the training and test set accuracies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Learn Voting with missing values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion\n",
    "Report on your accuracies and include explaining how the missing values were handled by your model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 (15%)  N-fold Cross Validation\n",
    "- Learn the [Cars Dataset](https://raw.githubusercontent.com/cs472ta/CS472/master/datasets/cars.arff) with the decision tree.\n",
    "- Create a table with the 10-fold cross validation accuracies and show the average predicted accuracy.\n",
    "- Try it again with 5-fold CV and create and show that table also."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import cross_val_score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion\n",
    "Explain n-fold cross validation. Why do we do it? How is it useful? What does it reveal? Do we end up with a model? If so, which one? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 (10%) Decision Tree Intuition\n",
    "For each of the two problems above (Voting and Cars):\n",
    "- Print the full tree for each.  You may use tree.plot_tree(clf) or [another way](https://mljar.com/blog/visualize-decision-tree/) if you prefer.  tree.plot_tree has a number of parameters which you can try which let you print more informative trees which can help your discussion.\n",
    "- Train both again with max_depth = 2 and print these smaller trees and include them in your report.\n",
    "- Summarize in English what these 2 smaller decision trees have learned (i.e. look at the induced trees and describe what \"rules\" they discovered). \n",
    "- Compare your thoughts on important features with the attribute feature_importances_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Print induced trees for the voting and car data sets\n",
    "from sklearn import tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion \n",
    "Discuss what the Trees have learned on the 2 data sets (i.e. look at the induced trees and describe what \"rules\" they discovered). How do the important features you would think about correspond the the \"feature_importances_\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 (5%) Other Parameters\n",
    "- For either of the data sets above experiment and discuss using a different split criterion (Compare Entropy and Log-loss with Gini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment with criterion parameter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion\n",
    "How does using different split criteria (entropy, log-loss, and gini) affect accuracy, tree structure, and feature importance?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Overfit Avoidance with Decision Trees  \n",
    "\n",
    "Above, you found typical training and test set scores for the Cars data set when the tree is induced as far as it can go (until classes are pure or there are no more data or attributes to split on).  This usually leads to great training set scores but can potentially overfit and get lower accuracy on the test set.  You will now experiment with methods which can help avoid overfit and which could lead to better test set accuracy (though training set accuracy may decrease).  \n",
    "\n",
    "### 3.1 Smaller and Simpler Trees (20%) \n",
    "- tree_: [Read about](https://scikit-learn.org/stable/auto_examples/tree/plot_unveil_tree_structure.html#sphx-glr-auto-examples-tree-plot-unveil-tree-structure-py) the tree_ attribute with its sub attributes and methods allowing you to interact with your learned tree.  You don't have to do any specific task for this part.\n",
    "- Use an 80/20 train/test split for all experiments in this part and induce (learn/fit) the full tree for Cars.\n",
    "- For the fully induced tree print out\n",
    "    - Training set accuracy\n",
    "    - Test set accuracy\n",
    "    - Total number of nodes (clf.tree_.node_count)\n",
    "    - Maximum tree depth (clf.tree_.max_depth)\n",
    "- Experiment with the following parameters which lead to smaller and/or simpler trees which can help with overfit.  Try a few different values of each parameter and compare their train and test set accuracies and number of nodes and depth with the fully induced tree.  If you are not sure how parameters are actually working, print some trees to see their effect.  Due to the simplicity of the Cars data set you may not see as great of accuracy improvements as you would for cases where overfit is more prominent.  \n",
    "    - min_samples_leaf\n",
    "    - min_samples_split\n",
    "    - min_impurity_decrease\n",
    "- Try these parameters also, but note that they could lead to underfit\n",
    "    - max_depth\n",
    "    - max_leaf_nodes\n",
    "    - max_features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Explore different overfit parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion\n",
    "How did the methods used above help avoid overfit? How do you know? How did they affect accuracy (training and test) and tree structure? Which parameters helped the most with each dataset? How do you know?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 (10%) Tree Reduction\n",
    "Another approach to avoiding overfit is using pruning to reduce fully induced trees.  Induce the tree fully for Cars (no simplifying parameters such as max_depth).  Prune by setting the [ccp_alpha](https://scikit-learn.org/stable/auto_examples/tree/plot_cost_complexity_pruning.html#sphx-glr-auto-examples-tree-plot-cost-complexity-pruning-py) parameter to a positive value. This parameter controls how aggressive the pruning is. Try some small values (e.g. ,001, ,005, etc.) and try to find and report the value which works the best.  Make a table with at least 5 ccp_alpha values and for each value include\n",
    "- Training set accuracy (you chooses the size of the train/test split)\n",
    "- Test set accuracy\n",
    "- Total number of nodes (clf.tree_.node_count)\n",
    "- Maximum tree depth (clf.tree_.max_depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Pruning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion\n",
    "How did the pruning parameter ccp_alpha affect accuracy and tree structure? How does that compare to the methods above?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Decision Tree Regression\n",
    "### 4.1 (15%) Learn a real-world regression data set of your choice (not already used in this or previous labs)\n",
    "- Report tree statistics (# of nodes, # of leaf nodes, max depth)\n",
    "- Report MAE on the training and test set (you choose the size of the train/test split)\n",
    "- Report the DT regressor score for the training and test set.  Note that for the DT regressor this score is the coefficient of determination. Google it if you are curious."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Learn regression data set\n",
    "from sklearn.tree import DecisionTreeRegressor\n",
    "from sklearn.metrics import mean_absolute_error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion\n",
    "Discuss your choice of dataset and regression feature. Also discuss the items listed above in 4.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Your discussion goes here **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. (Optional 15% extra credit) Code up your own C4.5 Decision Tree Learner \n",
    "Implement the C4.5 algorithm discussed in class and in the slides, NOT the CART algorithm.  Below is a scaffold you could use if you want. Requirements for this task:\n",
    "- Your model should support the methods shown in the example scaffold below.\n",
    "- Use standard information gain as your basic attribute evaluation metric.  Note that C4.5 would usually augment information gain with a mechanism to penalize statistically insignificant attribute splits to avoid overfit (e.g. early stopping, gain ratio, etc.), but you are not required to do that.\n",
    "- Include the ability to handle unknown attributes by making \"unknown\" a new attribute value when needed.\n",
    "- You do not need to handle real valued attributes.\n",
    "- It is a good idea to use simple data set (like the pizza homework), which you can check by hand, to test each detailed step of your algorithm to make sure it works correctly. \n",
    "- Run your algorithm on the voting data set above with unknown attributes and compare your results with CART."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discussion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.base import BaseEstimator, ClassifierMixin\n",
    "\n",
    "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",
    "    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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Optional 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])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.4 64-bit",
   "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.11.4"
  },
  "vscode": {
   "interpreter": {
    "hash": "cf8c9878be96b81c1c8fce57c4415443b48baf3df3953f8cea607d661f4cb93b"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}