A decision tree is a tree-like graph, a sequential diagram illustrating all of the possible decision alternatives and the corresponding outcomes. Starting from the root of a tree, every internal node represents the basis on which a decision is made; each branch of a node represents how a choice may lead to the next nodes; and finally, each terminal node, the leaf, represents the outcome produced.

For example, we have just made a couple of decisions that brought us to the point of using a decision tree to solve our advertising problem:

The first condition, or the root is whether the feature type is numerical or categorical. Ad click stream data contain mostly categorical features, so it goes to the right branch. In the next node, our work needs to be interpretable by non-technical clients. So, it goes to the right branch and reaches the leaf of choosing the decision tree classifier. You can also look at paths and see what kinds of problems they can fit in.

Decision tree classifier operates in a form of a decision tree, which maps observations to class assignments (symbolized as leaf nodes) through a series of tests (represented as internal nodes) based on feature values and corresponding conditions (represented as branches). In each node, a question regarding the values and characteristics of a feature is asked; depending on the answer to the question, observations are split into subsets. Sequential tests are conducted until a conclusion about the observations' target label is reached. The paths from root to end leaves represent the decision-making process, the classification rules.

In a much simplified scenario, shown in the following diagram, where we want to predict Click or No click on a self-driven car ad, we manually construct a decision tree classifier that works for an available dataset. For example, if a user is interested in technology and has a car, they will tend to click on the ad; for a person outside of this subset, if the person is a high-income woman, then she is unlikely to click on the ad. We then use the trained tree to predict two new inputs, whose results are Click and No click respectively:

After a decision tree has been constructed, classifying a new sample is straightforward, as we just saw: starting from the root, apply the test condition and follow the branch accordingly until a leaf node is reached, and the class label associated will be assigned to the new sample.

So, how can we build an appropriate decision tree?