12.1 Decision Trees

: 60 minutes

Decision trees are defined by recursively partitioning the input space, and defining a local model in each resulting region of the input space. Consequently, the overall model can be represented by a tree.

Although decision trees can also be used for regression, we study here only classifiers trees.

TipTrees

Trees are special graphs with a designated root node and no cycles.

Decision Trees are Everywhere!

It’s quite common in real life to use nested decision rules or a decision tree for making day-to-day choices.

For example, a GW data science student like yourself may choose a DATS course based on the following decision tree.

Plot.plot({
  axis: null,
  height: 400,
  margin: 10,
  marginLeft: 70,
  marginRight: 100,
  marks: [
    Plot.tree(course, {textStroke: 'None', fontSize: 20})
  ]
})

Figure 31.1: Choosing a DATS course

Tip Internal vs External Nodes

Exercise 31.1 How many internal and external nodes are there in the tree shown in Figure 31.1.

The diagram above, we pretend to use four binary features: \{x_1\ ({\tt required}), x_2\ ({\tt exam}), x_3\ ({\tt takehome}), x_4\ ({\tt curve})\} and two class labels: \{{\color{green}\tt Y}, {\color{red}\tt N}\}.

In practice, the features are continuous—e.g. average final score, number of students, etc. In that case, it’s most nature to use a threshold value for each feature for creating the nested decision rules.

Tip More Decision Trees

Exercise 31.2 Give examples of real life scenarios where nested decision are used.

Mathematical Formulation

Let us consider a classification problem with features \bold{x}=(x_1, x_2, \ldots, x_d) and class labels \{{\tt 1}, {\tt 2}, \ldots, {\tt C}\}.

The idea behind decision tree is to divide the feature space \mathcal{X} into non-overlapping regions \mathcal{T}=\{\mathcal{R}_i\}, where each region \mathcal{R}_i is given by

1. a sequence of nested conditions each defined by a threshold t\in\mathbb{R} (e.g., x_i\leq t_i, etc)
2. a class label \tt c_j\in \{{\tt 1}, {\tt 2}, \ldots, {\tt C}\}.

The regions are commonly taken to be rectangular (axis-parallel) and entire the decision boundary looks like a colored maze.

For example, below is a decision tree for a two-dimensional feature vector \bold{x}=(x_1, x_2) and three class labels \{{\color{orange}\tt 0}, {\color{green}\tt 1}, {\color{royalblue}\tt 2}\}. See ; see Figure 31.2.

plotBoundary(tree_ex);

Figure 31.2: The decision boundary of an example decision tree

The governing decision tree is shown below in Figure 31.3.

plotTree(tree_ex, ['x_1', 'x_2']);

Figure 31.3: An example decision tree for three-class problem

Tip Prediction using Decision Tree

Exercise 31.3 Using the decision tree (Figure 31.3) predict the label of the point (7, 1.5) in the feature space.

Prediction

Given such a decision tree with colored regions, a new data point \bold{x} can be classified depending on the color or label of the unique region \mathcal{R}_i that contains \bold{x}.

Training

To obtain such a decision tree, we use training data \mathcal{D} to meaningfully choose a sequence of features and thresholds that minimizes some notion of loss. The two commonly used loss functions are Gini (Equation 31.2) and Entropy ((Equation 31.3)). See [Subsection](#the-training-algorithm-(optional) for more details.

Tip Parametric vs Non-parametric

Exercise 31.4 Is decision tree model parametric or non-parametric?

Classifying Iris

Before we describe the loss functions and training algorithm in the next section, we first take an easy example.

Recall the classic Iris dataset has four features and three class labels: \color{orange}\tt setosa, \color{green}\tt versicolor, and \color{royalblue}\tt virginica. To keep it simple, let us assume that we have only two (continuous) features petalLength, petalWidth of Iris flower.

Try to pick thresholds t_1 and t_2 to visually classify the training labels to avoid miss classification as much as possible.

Plot.plot({
  width: 600,
  height: 400,
  margin: 50,
  grid: true,
  x: { domain: [0, 8], label: "Petal Length (x_1)" },
  y: { domain: [-1, 3], label: "Petal Width (x_2)" },
  color: { 
    domain: ['setosa', 'versicolor', 'virginica'],
    range: ["rgb(255, 165, 0)", "rgb(0, 128, 0)", "rgb(65, 105, 225)"]
  },
  marks: [
    Plot.ruleX([t1]),
    Plot.ruleY([t2], {x1: t1, x2: 8}),
    // Decision boundary background
    Plot.rect(boundaryData(treeA, ['petalLength', 'petalWidth'], true, iris), {
      x1: d => d.x - 0.05,
      x2: d => d.x + 0.05,
      y1: d => d.y - 0.05,
      y2: d => d.y + 0.05,
      fill: d => label ? d.label : 'None',
      opacity: 0.2
    }),
    Plot.dot(iris, {
      x: 'petalLength',
      y: 'petalWidth',
      fill: 'species'
    })
  ]
});

viewof t1 = Inputs.range([0, 8], {value: 4, step: 0.1, label: tex`t_1`});
viewof t2 = Inputs.range([-1, 3], {value: 2, step: 0.1, label: tex`t_2`});
viewof label = Inputs.toggle({label: 'Show labels'})

Below is the associated decision tree.

plotTree(treeA, ['petalLength', 'petalWidth'], true, iris);

The Training Algorithm (Optional)

Training the perfect split of the feature space that minimizes loss is known to be an \mathcal{NP}-hard problem. The standard approach is to use a greedy procedure, in which we iteratively grow the tree one node at a time.

Step: i\geq1

Suppose we are at node i; let \mathcal{D}_i=\{(\bold{x}_n, y_n)\in N_i\} be the subset of the training data that reaches the node. We consider how to split this node into a left branch and right branch so as to minimize the training error in each child subtree.

1. We first sort the unique values of the jth feature x_j in \mathcal{D}_i to get the set of all possible thresholds \mathcal{T}_{j}=\{x_{nj}\} for x_j.

2. For each possible threshold t\in\mathcal{T}_j, define the left and right splits, respectively: \mathcal{D}_i^L(j, t)=\{(\bold{x}_n, y_n)\in N_i\mid x_{n,j}\leq t\},\text{ and} \mathcal{D}^R_i(j, t)=\{(\bold{x}_n, y_n)\in N_i\mid x_{n,j}> t\}.

3. Finally, to find the best split at node i, we choose the best feature x_{ji} and threshold t_i that minimizes the following loss: \mathcal{L}_i(j, t)=\frac{\mathcal{D}^L_i(j,t)}{\mathcal{D}_i}{\tt cost}(\mathcal{D}^L_i(j,t)) + \frac{\mathcal{D}^R_i(j,t)}{\mathcal{D}_i}{\tt cost}(\mathcal{D}^R_i(j,t)). \tag{31.1} Here, the cost {\tt cost}(\mathcal{D}_i) is computed by Gini index as described below.

Gini and Entropy

Let us consider any node with data \mathcal{D}_i. We first compute the empirical distribution over class labels for this node: \hat\pi_{ic}=\frac{|\{ n\in\mathcal{D}_i\mid y_n=c\}|}{|\mathcal{D}_i|}. From this, we can define the Gini index. G_i=\sum_{c=1}^C\hat\pi_{ic}(1-\hat\pi_{ic})=1-\sum_{c=1}^C\hat\pi_{ic}^2. \tag{31.2} Alternatively, the entropy is defined by H_i=-\sum_{c=1}^C\hat\pi_{ic}\log{\hat\pi_{ic}}. \tag{31.3}

In Equation 31.1, one of the above cost description can be used to compute the loss used by the decision tree algorithm.

Training Demo

In this demo, we see the steps of the training algorithm as discussed above. We still use the Iris dataset with just two features petalLength and petalWidth.

mutable leaf = null;
gini = {
  if(!leaf)
    return '';
  const tree = JSON.parse(JSON.stringify(treeB));
  const l = findNode(tree, leaf.id);
  const lastId = leaves(tree).map(d => d.id).reduce((a, b) => (a > b ? a : b));
  const left = {
    id: lastId + 1,
    parent: l.id,
    type: "leaf"
  };
  const right = {
    id:  lastId + 2,
    parent: l.id,
    type: "leaf"
  }
  Object.assign(l, {
      type: "split",
      feature: feature,
      value: t,
      name: `${feature} ≤ ${t}`,
      left: left,
      right: right
  });
  const left_count = Object.values(getCount(tree, left, iris));
  const right_count = Object.values(getCount(tree, right, iris));
  const left_n = left_count.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
  const right_n = right_count.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
  const left_gini = 1-left_count.reduce((accumulator, currentValue) => accumulator + (currentValue/left_n * currentValue/left_n), 0);
  const right_gini = 1-right_count.reduce((accumulator, currentValue) => accumulator + (currentValue/right_n * currentValue/right_n), 0);
  const n = left_n + right_n;
  const gini = (left_n/n) * left_gini + (right_n/n) * right_gini;
  return gini;
}
plot = {
  const p = Plot.plot({
  width: 550,
  height: 350,
  grid: true,
  x: { domain: [0, 8], label: "Petal Length (x_1)" },
  y: { domain: [-1, 3], label: "Petal Width (x_2)" },
  color: { 
    domain: ['setosa', 'versicolor', 'virginica', null],
    range: ["rgb(255, 165, 0)", "rgb(0, 128, 0)", "rgb(65, 105, 225)"]
  },
  marks: [
    Plot.rect(leaves(treeB).map(l => ({
      label: l.label, 
      ...regionAtLeaf(treeB, l, {x1: 0, y1: -1, x2: 8, y2: 3})})
    ), 
    {x1: "x1", y1: "y1", x2: "x2", y2: "y2", fill: d => d.label, opacity: showLabel ? 0.2 : 0, stroke: 'gray', strokeWidth: 4}),
    Plot.ruleX([{x: t, y1: rect.y1, y2: rect.y2}], {x: 'x', y1: 'y1', y2: 'y2', opacity: () => feature == 'petalLength' ? 1 : 0, stroke: 'red'}),
    Plot.ruleY([{y: t, x1: rect.x1, x2: rect.x2}], {y: 'y', x1: 'x1', x2: 'x2', opacity: () => feature == 'petalWidth' ? 1 : 0, stroke: 'red'}),
    Plot.dot(iris, {
      x: 'petalLength',
      y: 'petalWidth',
      fill: 'species',
    }),
    Plot.rect([rect], 
    {x1: "x1", y1: "y1", x2: "x2", y2: "y2", stroke: "red", strokeDasharray: 4})
  ]
  });
  p.addEventListener('click', (event) => {
    const rect = p.getBoundingClientRect();
    const pixelX = event.clientX - rect.left;
    const pixelY = event.clientY - rect.top;
    const xScale = p.scale("x");
    const yScale = p.scale("y");
      
    if (xScale && yScale && xScale.invert && yScale.invert) {
        // Get the actual plot dimensions (excluding margins)
        const plotArea = p.querySelector("svg");
        
        const dataX = xScale.invert(pixelX);
        // Y scale is already handled correctly by Plot's invert
        const dataY = yScale.invert(pixelY);  
        mutable leaf = findLeaf(treeB, {petalLength: dataX, petalWidth: dataY});
    }
  });
  return p;
};

Gini loss:

viewof t = Inputs.range(feature == 'petalLength' ? [rect.x1,rect.x2] : [rect.y1,rect.y2], {step: 0.1, label: tex`t`, disabled: leaf === null});
viewof feature = Inputs.select(['petalLength', 'petalWidth'], {label: 'Select feature'});
viewof split = Inputs.button("Split", {
  reduce: () => {
      delete leaf.label;
      const lastId = leaves(treeB).map(d => d.id).reduce((a, b) => (a > b ? a : b));
      const left = {
        id: lastId + 1,
        parent: leaf.id,
        type: "leaf"
      };
      const right = {
        id:  lastId + 2,
        parent: leaf.id,
        type: "leaf"
      }
      Object.assign(leaf, {
        type: "split",
        feature: feature,
        value: t,
        name: `${feature} ≤ ${t}`,
        left: left,
        right: right
      });
      mutable treeB = treeB;
      let count = getCount(treeB, left, iris);
      let name = Object.entries(count).map(([k, v]) => `${k}: ${v}`).join(', ');
      let label = Object.keys(count).reduce((a, b) => {
            return count[a] > count[b] ? a : b;
      });
      left.name= name;
      left.label = label;
      count = getCount(treeB, right, iris);
      name = Object.entries(count).map(([k, v]) => `${k}: ${v}`).join(', ');
      label = Object.keys(count).reduce((a, b) => {
            return count[a] > count[b] ? a : b;
      });
      right.name= name;
      right.label = label;
      mutable leaf = null;
  }
});
viewof showLabel = Inputs.toggle({label: 'Show labels'});

Below is the final decision tree.

plotTree(treeB, ['petalLength', 'petalWidth']);

Figure 31.4: The output decision tree

Tip Training Error

Exercise 31.5 What’s the minimum training error that can be achieved?

Feature Importance

For a decision tree \mathcal{T}, the feature importance of the feature x_k is defined by its total contribution in reducing impurity or Gini.

Let us assume that the feature x_k appears in J many internal nodes of the decision tree \mathcal{T}. The contribution or importance of x_k in reducing impurity at node the jth node can be defined as: {\tt Imp_k(j)}=\frac{|\mathcal{D}_j|}{|\mathcal{D}|}G(\mathcal{D}_j) -\left(\frac{|\mathcal{D}_j^L|}{|\mathcal{D}|}G(\mathcal{D}_j^L) +\frac{|\mathcal{D}^R_j|}{|\mathcal{D}|}G(\mathcal{D}_j^R)\right). Adding the contributions from all the J nodes, we get the feature importance of the feature: {\tt Imp_k(j)}=\sum_{j-1}^J{\tt Imp_k(j)}.

Pros and Cons

Tip Pros and Cons

Exercise 31.6 Discuss some of the pros and cons of the decision tree classifier.

mutable treeB = ({
      id: 0,
      type: "leaf",
      parent: null,
      label: null  
});
function findNode(tree, id) {
  if(tree.id === id)
    return tree;
  if(!tree || tree.type === 'leaf')
    return null;
  return findNode(tree.left, id) || findNode(tree.right, id);
}
rect = regionAtLeaf(treeB, leaf, {x1: 0, y1: -1, x2: 8, y2: 3});

function dataAtNode(tree, node, data) {
    const res = [];
    if(tree.id === node.id)
      return data;
    if(tree.type === 'leaf')
      return [];
    const leftData = data.filter((d) => d[tree.feature] <=  tree.value);
    const rightData = data.filter((d) => d[tree.feature] >  tree.value);
    res.push(...dataAtNode(tree.left, node, leftData));
    res.push(...dataAtNode(tree.right, node, rightData));
    return res;
}
function regionAtLeaf(tree, node, rect) {
    if(!node)
      return {x1: -Infinity, x2: Infinity, y1: -Infinity, y2: Infinity};
    if(tree.type === 'leaf' && tree.id === node.id)
      return rect;
    if(tree.type === 'leaf')
      return {x1: -Infinity, x2: Infinity, y1: -Infinity, y2: Infinity};
    const left = regionAtLeaf(tree.left, node, {
      x1: rect.x1,
      x2: tree.feature === 'petalLength' ? tree.value : rect.x2,
      y1: rect.y1,
      y2: tree.feature === 'petalWidth' ? tree.value : rect.y2,
    });
    const right = regionAtLeaf(tree.right, node, {
      x2: rect.x2,
      x1: tree.feature === 'petalLength' ? tree.value : rect.x1,
      y2: rect.y2,
      y1: tree.feature === 'petalWidth' ? tree.value : rect.y1,
    });
    return {
      x1: Math.max(left.x1, right.x1),
      x2: Math.min(left.x2, right.x2),
      y1: Math.max(left.y1, right.y1),
      y2: Math.min(left.y2, right.y2)
    };
}

course =[
  "Course/required/Y",
  "Course/elective/Exam/Take-home/Y",
  "Course/elective/Exam/Paper/Curve/Y",
  "Course/elective/Exam/Paper/No Curve/N",
  "Course/elective/Project/Y",
];
boundaryData = function(tree, features=['x_1', 'x_2'], predict=false, data=null) {
  const gridSize = 80;
  const grid = [];
  for (let i = 0; i < gridSize; i++) {
      for (let j = 0; j < gridSize; j++) {
        const x =  (i / gridSize) * 8;
        const y = -1 + (j / gridSize) * 4;
        const p = {};
        p[features[0]] = x; p[features[1]] = y;
        const node = findLeaf(tree, p);
        let label = node.label;
        if(predict) {
          const count = getCount(tree, node, data);
          label = Object.keys(count).reduce((a, b) => {
            return count[a] > count[b] ? a : b;
          });
        }
        grid.push({ x, y, label });
      }
  }
  return grid;
}
//
function findLeaf(tree, p) {
  let node = tree;
  while (node.type === 'split') {
    node = p[node.feature] <= node.value ? node.left : node.right;
  }
  return node;
}
treeData = function(tree, features=['x_1', 'x_2'], predict=false, data=null) {
  function flatten(node, depth = 0, parentPath = 'Node_') {
    const currentPath = parentPath ? `${parentPath}/Node_${node.id.toString()}` : node.id.toString();
    let label = node.label;
    let name = node.name;
    if(node.type === 'leaf' && predict) {
      const count = getCount(tree, node, data);
      name = Object.entries(count).map(([k, v]) => `${k}: ${v}`).join(', ');
      label = Object.keys(count).reduce((a, b) => {
            return count[a] > count[b] ? a : b;
      });
    }
    const nodes = [{
      path: currentPath,
      name: name,
      type: node.type,
      label: label,
      depth: depth
    }];
    
    if (node.left) {
      nodes.push(...flatten(node.left, depth + 1, currentPath));
    }
    if (node.right) {
      nodes.push(...flatten(node.right, depth + 1, currentPath));
    }
    
    return nodes;
  }
  
  return flatten(tree);
}

function leaves(tree) {
  const l = []
  if(tree.type === 'leaf') {
    l.push(tree);
    return l;
  }
  l.push(...leaves(tree.left));
  l.push(...leaves(tree.right));

  return l;
}
function plotTree(tree, features=['petalLength', 'petalWidth'], predict=false, data=null, labels=["setosa", "versicolor", "virginica"], colors=["rgb(255, 165, 0)", "rgb(0, 128, 0)", "rgb(65, 105, 225)"]) {
  return Plot.plot({
  width: 900,
  height: 400,
  margin: 70,
  marginTop: 40,
  marginLeft: 80,
  marginRight: 120,
   axis: null,
  color: { 
    domain: labels.concat("split"),
    range: colors.concat("#888")
  },
  marks: [
    Plot.tree(treeData(tree, features, predict, data), {
      path: "path",
      strokeWidth: 2,
      stroke: "#666",
      textStroke: 'None',
      fill: d => d.type === "leaf" ? d.label : "split",
      fontSize: 20,
      dy: 25,
      dx: 0
    }),
    Plot.dot(treeData(tree, features, predict, data), Plot.treeNode({
      path: "path",
      fill: d => d.type === "leaf" ? d.label : "split",
      r: 10,
      stroke: "white",
      strokeWidth: 2
    })),
    Plot.text(treeData(tree, features, predict, data), Plot.treeNode({
      path: "path",
      text: "name",
      fontSize: 14,
      fill:  d => d.type === "leaf" ? d.label : "split",
      dy: -22,
      textAnchor: "middle"
    }))
  ]
});
}
tree_ex = ({
  id: 0,
  type: "split",
  feature: "x_1",
  value: 6,
  parent: null,
  name: `x_1 ≤ 6`,
  left: {
    id: 1,
    type: "leaf",
    label: 'setosa',
    parent: 0,
  },
  right: {
      id: 2,
      type: "split",
      parent: 0,
      name: `x_2 ≤ 0.5`,
      value: 0.5,
      feature: "x_2",
      left: {
        id: 3,
        type: "leaf",
        label: 'versicolor',
        parent: 2
      }, 
      right: {
        id: 4,
        type: "leaf",
        label: 'virginica',
        parent: 2
      }
    }
});
treeA = ({
  id: 0,
  type: "split",
  feature: "petalLength",
  value: t1,
  parent: null,
  name: `petalLength ≤ ${t1}`,
  left: {
    id: 1,
    type: "leaf",
    parent: 0
  },
  right: {
      id: 2,
      type: "split",
      parent: 0,
      name: `petalWidth ≤ ${t2}`,
      value: t2,
      feature: "petalWidth",
      left: {
        id: 3,
        type: "leaf",
        parent: 2
      }, 
      right: {
        id: 4,
        type: "leaf",
        parent: 2
      }
    }
});
iris = require("@observablehq/iris");
function plotBoundary(tree, features= ['x_1', 'x_2'], labels=['setosa', 'versicolor', 'virginica'], colors=["rgb(255, 165, 0)", "rgb(0, 128, 0)", "rgb(65, 105, 225)"]) {
  return Plot.plot({
  width: 700,
  height: 500,
  margin: 50,
  grid: true,
  x: { domain: [0, 8], label: features[0] },
  y: { domain: [-1, 3], label: features[1] },
  color: { 
    domain: labels,
    range: colors
  },
  marks: [
    Plot.rect(boundaryData(tree, features), {
      x1: d => d.x - 0.05,
      x2: d => d.x + 0.05,
      y1: d => d.y - 0.05,
      y2: d => d.y + 0.05,
      fill: d => d.label,
      opacity: 0.2
    })
  ]
});
}
function getCount(tree, node, data=iris, target='species', labels=['setosa', 'versicolor', 'virginica']) {
  const dataSubset = dataAtNode(tree, node, data);
  const res = {};
  labels.forEach(l => res[l]=dataSubset.filter(d => d[target] === l).length);
  return res;
}