What is a decision tree?
A decision tree is a map of the possible outcomes of a series of related choices. It allows an individual or organization to weigh possible actions against one another based on their costs, probabilities, and benefits. They can can be used either to drive informal discussion or to map out an algorithm that predicts the best choice mathematically.
A decision tree typically starts with a single node, which branches into possible outcomes. Each of those outcomes leads to additional nodes, which branch off into other possibilities. This gives it a treelike shape.
There are three different types of nodes: chance nodes, decision nodes, and end nodes. A chance node, represented by a circle, shows the probabilities of certain results. A decision node, represented by a square, shows a decision to be made, and an end node shows the final outcome of a decision path.
Decision trees can also be drawn with flowchart symbols, which some people find easier to read and understand.
How to draw a decision tree
To draw a decision tree, first pick a medium. You can draw it by hand on paper or a whiteboard, or you can use special decision tree software. In either case, here are the steps to follow:
1. Start with the main decision. Draw a small box to represent this point, then draw a line from the box to the right for each possible solution or action. Label them accordingly.
2. Add chance and decision nodes to expand the tree as follows:
- If another decision is necessary, draw another box.
- If the outcome is uncertain, draw a circle (circles represent chance nodes).
- If the problem is solved, leave it blank (for now).
From each decision node, draw possible solutions. From each chance node, draw lines representing possible outcomes. If you intend to analyze your options numerically, include the probability of each outcome and the cost of each action.
3. Continue to expand until every line reaches an endpoint, meaning that there are no more choices to be made or chance outcomes to consider. Then, assign a value to each possible outcome. It could be an abstract score or a financial value. Add triangles to signify endpoints.
With a complete decision tree, you’re now ready to begin analyzing the decision you face.
Decision tree analysis example
By calculating the expected utility or value of each choice in the tree, you can minimize risk and maximize the likelihood of reaching a desirable outcome.
To calculate the expected utility of a choice, just subtract the cost of that decision from the expected benefits. The expected benefits are equal to the total value of all the outcomes that could result from that choice, with each value multiplied by the likelihood that it’ll occur. Here’s how we’d calculate these values for the example we made above:
When identifying which outcome is the most desirable, it’s important to take the decision maker’s utility preferences into account. For instance, some may prefer low-risk options while others are willing to take risks for a larger benefit.
When you use your decision tree with an accompanying probability model, you can use it to calculate the conditional probability of an event, or the likelihood that it’ll happen, given that another event happens. To do so, simply start with the initial event, then follow the path from that event to the target event, multiplying the probability of each of those events together.
In this way, a decision tree can be used like a traditional tree diagram, which maps out the probabilities of certain events, such as flipping a coin twice.
Advantages and disadvantages
Decision trees remain popular for reasons like these:
- How easy they are to understand
- They can be useful with or without hard data, and any data requires minimal preparation
- New options can be added to existing trees
- Their value in picking out the best of several options
- How easily they combine with other decision making tools
However, decision trees can become excessively complex. In such cases, a more compact influence diagram can be a good alternative. Influence diagrams narrow the focus to critical decisions, inputs, and objectives.
Decision trees in machine learning and data mining
A decision tree can also be used to help build automated predictive models, which have applications in machine learning, data mining, and statistics. Known as decision tree learning, this method takes into account observations about an item to predict that item’s value.
In these decision trees, nodes represent data rather than decisions. This type of tree is also known as a classification tree. Each branch contains a set of attributes, or classification rules, that are associated with a particular class label, which is found at the end of the branch.
These rules, also known as decision rules, can be expressed in an if-then clause, with each decision or data value forming a clause, such that, for instance, “if conditions 1, 2 and 3 are fulfilled, then outcome x will be the result with y certainty.”
Each additional piece of data helps the model more accurately predict which of a finite set of values the subject in question belongs to. That information can then be used as an input in a larger decision making model.
Sometimes the predicted variable will be a real number, such as a price. Decision trees with continuous, infinite possible outcomes are called regression trees.
For increased accuracy, sometimes multiple trees are used together in ensemble methods:
- Bagging creates multiple trees by resampling the source data, then has those trees vote to reach consensus.
- A Random Forest classifier consists of multiple trees designed to increase the classification rate
- Boosted trees that can be used for regression and classification trees.
- The trees in a Rotation Forest are all trained by using PCA (principal component analysis) on a random portion of the data
A decision tree is considered optimal when it represents the most data with the fewest number of levels or questions. Algorithms designed to create optimized decision trees include CART, ASSISTANT, CLS and ID3/4/5. A decision tree can also be created by building association rules, placing the target variable on the right.
Each method has to determine which is the best way to split the data at each level. Common methods for doing so include measuring the Gini impurity, information gain, and variance reduction.
Using decision trees in machine learning has several advantages:
- The cost of using the tree to predict data decreases with each additional data point
- Works for either categorical or numerical data
- Can model problems with multiple outputs
- Uses a white box model (making results easy to explain)
- A tree’s reliability can be tested and quantified
- Tends to be accurate regardless of whether it violates the assumptions of source data
But they also have a few disadvantages:
- When dealing with categorical data with multiple levels, the information gain is biased in favor of the attributes with the most levels.
- Calculations can become complex when dealing with uncertainty and lots of linked outcomes.
- Conjunctions between nodes are limited to AND, whereas decision graphs allow for nodes linked by OR.