3-5_decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision tree\n",
    "\n",
    "- we will work with binary decision tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes from video lecture 1\n",
    "\n",
    "https://www.youtube.com/watch?v=OBWL4oLT7Uc\n",
    "\n",
    "<hr/>\n",
    "\n",
    "- This lecture focuses on how to use decision tree once you have it\n",
    "- Lecture 2 will cover how to build decision tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Factors\n",
    "\n",
    "- branches\n",
    "- these are quantitative metrics we can check; could be binary or may be even some classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision tree\n",
    "\n",
    "- Composed of nodes; 2 types of nodes \n",
    "  - decision node and leaves; one of the node is also root node\n",
    "  - in each of the decision node it will ask some question about the factors; for a binary node it can be:\n",
    "    - yes proceeds to one node\n",
    "    - no proceeds to another node\n",
    "  - last nodes are the leaves \n",
    "\n",
    "## What makes a decision tree - shape of the tree:\n",
    "- Factors: X1, X2, X3 ...\n",
    "- Label: Y - could be label or numeric value\n",
    "- Nodes: \n",
    "  - Have a set of nodes\n",
    "  - Each node includes the factor used and `split value`\n",
    "  - We are going to be looking at this split value; we will go down one way of the tree if factor value is less then or equal to the split value and another way down if factor is great then the split value (else condition)\n",
    "  - also coming out of nodes are edges pointing to the next nodes in left and right\n",
    "- Root: one of node will be designated as root node\n",
    "- Leaves: leaves at the bottom of tree\n",
    "\n",
    "These are all the things needed to define decision tree\n",
    "\n",
    "## Example Decision Tree\n",
    "\n",
    "<img alt=\"3_DT_1.png\" src=\"images/3_DT_1.png\" width=\"500\">\n",
    "\n",
    "- To each node we ask a question; if the answer is Yes then go to Left else go to right\n",
    "- EG: for root node question is: is factor X11 <= 10? Yes - go left else go to right node\n",
    "- Walk through the data set in top right of the board:\n",
    "  - result is path through 0, 1, 5, 6 & answer is 3\n",
    "\n",
    "## Notes on factor:\n",
    "- A factor may not be used at all or it may be used multiple times\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data set\n",
    "\n",
    "- Last column is our Y and everything else preceding it is X<sub>i</sub>\n",
    "- Each row represents a set of data\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data structure to build and store decision tree\n",
    "\n",
    "- We will use ndArray (numpy array) with 2 dimensions\n",
    "- We will use above example tree to build this data structure\n",
    "\n",
    "Factor |   Split val | left | right\n",
    "--- | --- | --- | --- \n",
    "11 | 10 | 1 | 8       <-- this row is root node\n",
    "2 | .5 | 2 | 5\n",
    "10 | .5 | 3 | 4\n",
    "-1 | 3 | - | -      <-- for leaf node -1 is factor and split val is the label\n",
    "-1 | 4 | - | -\n",
    "8 | 1.0 | 6 | 7\n",
    "-1 | 3 | - | -\n",
    "-1 | 4 | - | - \n",
    "11 | 12 | 9 | 10\n",
    "-1 | 4 | - | - \n",
    "-1 | 5 | - | -\n",
    "\n",
    "\n",
    "\n",
    "meaning of column values:\n",
    "- first row is root\n",
    "- factor: factor to query on\n",
    "- split val: this is the factor value based on which we go to left or right\n",
    "- left: value mean next node to evaluate is at that index\n",
    "- right: next node to evaluate\n",
    "  - for left & right you can use absolute value to indicate exactly what is the index of array\n",
    "  - or use relative value which is little bit more easy because you don't have to keep track of exactly where you are in algorithm as you build the tree\n",
    "    - relative eg:\n",
    "      - value 1: means 1 row below current row\n",
    "      - value 2: means 2 row below current row\n",
    "      - value 3: means 3 row below current row and so on\n",
    "      - Lecture 2 demo around 40ish mins covers this\n",
    "- after root node, all rows will be split into two groups - for left and right\n",
    "  - top rows will be for all left sides\n",
    "  - bottom rows will be for all right sides\n",
    "- leaves: we will use factor value of -1 to represent leaf nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Learning time for DT:\n",
    "\n",
    "- they are slow at learning times in order build this tree structure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes from video lecture 2\n",
    "\n",
    "https://www.youtube.com/watch?v=WVc3cjvDHhw\n",
    "<hr/>\n",
    "\n",
    "How do we build a decision tree?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img alt=\"3_DT_2.png\" src=\"images/3_DT_2.png\" width=\"550\" height=\"400\">\n",
    "<br/>\n",
    "\n",
    "- each row in data is sets of x's & y; \n",
    "- If the tree is binary tree, it will be easy to build and good for efficiency\n",
    "- special nodes: root & leaf nodes\n",
    "\n",
    "<img alt=\"3_DT_3.png\" src=\"images/3_DT_3.png\" width=\"550\" height=\"400\">\n",
    "<br/>\n",
    "\n",
    "\n",
    "<img alt=\"3_DT_4.png\" src=\"images/3_DT_4.png\" width=\"550\" height=\"400\">\n",
    "<br/>\n",
    "\n",
    "- Build this using numpy array\n",
    "- This is explained in part 1 of lecture\n",
    "\n",
    "\n",
    "<img alt=\"3_DT_5.png\" src=\"images/3_DT_5.png\" width=\"550\" height=\"400\">\n",
    "<br/>\n",
    "\n",
    "<img alt=\"3_DT_6.png\" src=\"images/3_DT_6.png\" width=\"550\" height=\"400\">\n",
    "<br/>\n",
    "\n",
    "- this is recursive algorithm\n",
    "- very first thing to do is check base case (in recursive algorithm)\n",
    "  - first base case: case if we are given one row of data\n",
    "  - second base case: all y are same so create a leaf node with a label\n",
    "- else: now we have real data so lets build the data\n",
    "  - Step 1: figure out what question to build our root node i.e. best feature to use say i\n",
    "    - coming up in another slide to talk about how to find this best feature\n",
    "    - if multiple features end up being candidate for best feature, deterministically pick one\n",
    "        - we will have randomness in the data; therefore, no reason to randomly pick a feature randomly in case of tie (although you can)\n",
    "  - Step 2: Now we know feature to use; at what value do we split?\n",
    "    - Look at all the values in this column and use median\n",
    "    - using median because we are trying to keep the tree balanced (a balanced tree!); with median we split the data exactly in half in each level and so on each level; this is the general idea\n",
    "  - Step 3: lets build left side of the tree  (<=)\n",
    "      - gather data to use to build left side of tree\n",
    "        - can do the gathering in numpy using boolean indexing\n",
    "      - call build tree, recursive call\n",
    "  - Step 4: lets build right side of the tree  (>)\n",
    "    - just like step 3\n",
    "    - gather data for right side and use it\n",
    "  - Step 5: time for the root after we have left & right\n",
    "    - From step 1 we have feature to split on called i\n",
    "    - we also have split val from step 2\n",
    "    - next we said, left tree start right after root node so index is 1\n",
    "    - Finally after all left are done then we add right trees in array; so index is left tree row count + 1\n",
    "    - we have all data points our array needs; let's create root node\n",
    "  - Step 6: \n",
    "    - we append root, left tree and right tree\n",
    "    - append here is calling numpy's append method; lookup the documentation for numpy\n",
    "\n",
    "- All done!\n",
    "\n",
    "### Best feature:\n",
    "- In `Step 1` of `algorithm` we said to split by `best feature`. `How` do you determine best feature?\n",
    "<img alt=\"3_DT_7.png\" src=\"images/3_DT_7.png\" width=\"550\" height=\"400\">\n",
    "<br/>\n",
    "\n",
    "- Rephrase the question: how do I group data such that it does partition data most effectively?\n",
    "  - One way: `Information gain`\n",
    "    - Which factor provides the most information about our data?\n",
    "    - There are number of `ways to do find` out `about information gain`:\n",
    "      - Entropy (used by original quinlan paper)\n",
    "        - quite an effective way to select information gain\n",
    "      - Correlation\n",
    "        - closely related to entropy for regression problem\n",
    "        - Idea:\n",
    "          - For each factor of the data, see how closely it is related to labels\n",
    "          - Factor that is most strongly co-related is going to help us make the split effectively\n",
    "      - Gini Index\n",
    "        - We used this approach in AI class - CS 6601\n",
    "        - another measure of diversity\n",
    "\n",
    "  Note on scipy: with this library you can use between Entropy or Gini Index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## See lecture video walk through with excel on building tree using above algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In above algorithm the cost is high at?\n",
    "\n",
    "- computing the best feature & median\n",
    "- to speed up the algorithm, we need to figure out how to speed up these 2 steps\n",
    "- Random Tree Algorithm by A cutler does this\n",
    "\n",
    "<img alt=\"3_DT_8.png\" src=\"images/3_DT_8.png\" width=\"550\" height=\"400\">\n",
    "<br/>\n",
    "\n",
    "- Rather then spending time to figure out what feature to split and where to split, lets do it randomly\n",
    "- Instead of computing the median, choose two random rows and take their mean\n",
    "- Rest is just like before\n",
    "- Question:\n",
    "  - Sure this approach will be fast but doesn't it impair the quality of our tree?\n",
    "  - Answer is yes if you have only one tree!\n",
    "  - But with ensemble model of trees (multiple trees) rather then a single tree (aka single learner) it's performance can supersede best individual tree\n",
    "\n",
    "## `Random forest`\n",
    "- A random forest is a group of trees where each tree is built randomly\n",
    "- Ways to create random forest:\n",
    "    1. Above algorithm where features and split value are randomly selected\n",
    "    2. Data you construct the tree from is selected randomly with replacement; keep sampling and building trees. Turns out the key is having the different sets of data\n",
    "- You wanted uncorrelated learners or diversity among your learners\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cost of learning\n",
    "\n",
    "- Compared to KNN, decision tree lose for learning steps because in KNN all you do is store the data\n",
    "- Compared to Linear Regression learner, DT takes short time\n",
    "- Random forest: multiply cost of tree by number of tree in forest\n",
    "\n",
    "`ordered by low cost to high cost`: KNN < Linear Regression <  DT "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cost of querying\n",
    "\n",
    "- KNN has high cost\n",
    "- Linear regression is fastest because all you have to do is plugin data and out comes the answer\n",
    "- DT is log based; considering a balanced tree for 1000 rows you will only have to ask `log<sub>2</sub> 1000` which is approximately 10 questions to ask\n",
    "\n",
    "`ordered by hight cost to low cost`: KNN > DT > Linear Regression\n",
    "\n",
    "### Quality\n",
    "- Regression are usually fast to learn and query but in terms of quality they do not have high quality in terms of prediction vs actual result\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Benefits of decision tree\n",
    "\n",
    "- don't have to normalize your data\n",
    "  - For KNN you will have to normalize the data so that each dimension has same range; otherwise dimension with larger range will end up overwhelming the smaller one. eg 1 - 1000 range vs 1 - 10 for feature X1 & X2\n",
    "  - no such need for decision tree"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}