Decision Trees
A decision tree is a graphical representation of all possible outcomes of a decision based on specific conditions. It can be viewed as a set of rules composed of simple clauses that collectively form a comprehensive equation.
These rules, structured as a series of if/then statements, segment data into similar groups. Decision trees are easily interpretable, revealing insights that might not be immediately apparent from a simple data inspection.
The term “decision tree” arises from its structure: it begins with a single box, known as the root node, which branches out into multiple solutions, resembling a tree. The root node represents the entire dataset and splits based on the most significant attribute.
Subsequent nodes, called decision nodes, further divide the data based on additional attributes, creating branches that represent different decision paths. These nodes are named decision nodes because each split represents a decision on the best way to segment the data.
Finally, the leaf nodes, found at the ends of the branches, represent the outcomes or predicted values based on the path taken through the tree.
- Root Node: The starting point of the tree where the first test is applied.
- Internal Nodes: Nodes where decisions or tests on data attributes are made.
- Branches: Represent the outcome of the test and lead to the next node.
- Leaf Nodes: Represent the final decision or prediction (e.g., buy, sell, hold).
Origin & History
The concept of decision trees has a rich and multifaceted history that dates back to early developments in statistical analysis and cognitive psychology, which later influenced their adoption in the fields of artificial intelligence and machine learning. Based on the findings in the paper (WIREs Comput Stat, 2013), the origins and evolution of Decision Trees has been illustrated below.
I. Early Origins
Decision trees trace their origins to ancient methodologies for organizing knowledge. The “Porphyrian tree,” conceived by the Greek philosopher Porphyry in the 3rd century C.E., is considered one of the earliest forms of classification tree diagrams. These early attempts to organize information in a tree-like structure underscored the intuitive nature of decision trees, making complex decisions and classifications easier to understand.
II. Development in the 20th Century
The computational use of decision trees began to take shape in the mid-20th century. William A. Belson was one of the pioneers, utilizing mechanical calculators and Hollerith punch cards for his analysis of nation-wide audience surveys for the British Broadcasting Corporation (BBC) in the 1950s. Belson’s work involved sorting and identifying imbalances in data distributions, which laid the groundwork for modern decision tree algorithms.
III. Advancements by Morgan and Sonquist
Building on Belson’s work, James N. Morgan and John A. Sonquist developed the Automatic Interaction Detection (AID) program at the University of Michigan in the early 1960s. They aimed to find interaction terms that would enhance regression models. Their approach demonstrated that decision trees could partition data into groups that explained a significant portion of the variance in the response variable, often outperforming traditional regression methods. This work underscored the potential of decision trees in exploratory data analysis and model building.
IV. The Influence of Kass and Breiman
The development of decision trees was further advanced by Gordon V. Kass and later by Leo Breiman and his colleagues. Kass introduced the CHAID (Chi-squared Automatic Interaction Detection) algorithm, which used statistical tests to determine the best splits in the data. Breiman, along with Friedman, Olshen, and Stone, published the seminal work “Classification and Regression Trees” (CART) in 1984. CART formalized the use of decision trees for both classification and regression tasks and introduced techniques for pruning trees to avoid overfitting.
V. Integration with Machine Learning and AI:
In parallel, researchers in artificial intelligence and machine learning began to explore decision trees as tools for concept learning and knowledge acquisition. J. Ross Quinlan’s development of the ID3 (Interactive Dichotomizer 3) algorithm in the late 1970s was a significant milestone. ID3 used information gain as a criterion for selecting the best attribute to split the data. Quinlan’s work evolved into the C4.5 algorithm, which became one of the most widely used decision tree algorithms.
Construction of Decision Trees
The construction of decision trees is a fundamental technique in machine learning, providing a clear and interpretable model for both classification and regression tasks. This process is rooted in Hunt’s algorithm, developed in the 1960s to model human learning in psychology. Hunt’s algorithm introduced the concept of recursive partitioning, which is the cornerstone of modern decision tree algorithms such as ID3, C4.5, and CART.
I. Start with the Entire Dataset
The process begins with the entire dataset at the root node. This initial step sets the foundation for the recursive partitioning process that follows. When starting with the entire dataset, the goal is to utilize all available data points and features to build the most informative and accurate decision tree. The root node provides a comprehensive view of the dataset. It includes all the instances (data points) and their corresponding features (attributes), allowing the decision tree algorithm to evaluate the complete scope of the data.
II. Select the Best Attribute to Split
The second crucial step is selecting the best attribute to split the dataset into subsets that are as homogenous as possible. This step is vital because the effectiveness of the decision tree largely depends on how well the chosen splits reduce impurity and increase the homogeneity of the resulting subsets. Homogeneous subsets mean that the data points within each subset are similar to each other, leading to more accurate and reliable predictions.
III. Split the Data
Once the best feature is selected in the decision tree construction process, the next crucial step is to split the dataset into subsets based on the values of that feature. This step involves creating branches in the tree, where each branch represents a subset of the data that shares a specific attribute value or range of values. The primary goal of splitting the data is to create subsets that are more homogeneous in terms of the target variable. This means that the data points within each subset should be similar, leading to more accurate predictions.
IV. Create Child Nodes
Creating child nodes is a critical step in the recursive construction of decision trees. This step involves taking the subsets generated from the previous split and treating each subset as a new node. The process of selecting the best attribute and splitting the data is then repeated for each of these child nodes. By recursively creating child nodes and splitting the data, the decision tree can capture finer details and more specific patterns within the dataset. Each level of the tree adds more granularity to the decision-making process, improving the model’s accuracy.
V. Continue Recursively
The algorithm continues to split the data subsets created at each child node until specific stopping criteria are met. If a stopping criterion is satisfied, the node becomes a leaf node, and the recursion stops for that branch. If no stopping criteria are met, the algorithm continues to split the data further.
Following are some stopping criteria:
- All Instances in a Node Belong to the Same Class: If all data points at a node have the same class label, the node becomes a leaf node with that class label. There is no need for further splitting, as the subset is already homogeneous.
- No Remaining Attributes to Split: If there are no remaining attributes to split the data, the node becomes a leaf node. This situation occurs when all attributes have been used in the splits leading to the node, or the attributes do not provide any further information gain.
- Subset Too Small to Split Further: If the number of data points in a subset is too small, further splitting may not be meaningful. A minimum threshold for the number of data points can be set to stop splitting when the subset size falls below this threshold.
- Predefined Depth of the Tree is Reached: To prevent overfitting, a maximum depth for the tree can be specified. Once this depth is reached, the node becomes a leaf node. This criterion controls the complexity of the tree and ensures that it does not become too specific to the training data.
VI. Assign Class Labels
The final step in the construction of decision trees is to assign class labels to the leaf nodes. This step is crucial because it determines the final predictions made by the decision tree model. When a node can no longer be split based on the stopping criteria, it becomes a leaf node, and a class label or continuous value is assigned to it.
VII. Pruning
To prevent overfitting, where the decision tree becomes overly complex and starts capturing noise in the data, a technique called pruning is applied. Pruning involves trimming branches that provide minimal contribution to the model’s predictive power, thereby simplifying the tree without significantly reducing accuracy.
One common method is cost complexity pruning, which aims to balance the tree’s complexity against its performance on a validation set. By removing unimportant branches, pruning enhances the model’s generalizability and robustness, ensuring it performs well on new, unseen data.
Types of Decision Tree Algorithms
Hunt’s algorithm, developed in the 1960s to model human learning in psychology, serves as the foundation for many types of decision tree algorithms, including ID3, C4.5, and CART. While ID3, C4.5, and CART each have unique features and improvements, they all adhere to the basic principles of Hunt’s algorithm. They start with the entire dataset, recursively select the best attributes to split the data, and continue partitioning until stopping criteria are met. Hunt’s algorithm is a general framework for constructing decision trees, and these specific algorithms are extensions and improvements that follow the basic recursive partitioning approach introduced by Hunt.
I. ID3
Ross Quinlan is credited with developing the ID3 algorithm, which stands for “Iterative Dichotomiser 3.” This algorithm utilizes entropy and information gain as metrics to evaluate and determine the best splits for constructing decision trees.
The ID3 algorithm is considered as a very simple decision tree algorithm. The ID3 (Iterative Dichotomiser 3) algorithm, developed by Ross Quinlan, is a method used to generate a decision tree from a dataset.
This algorithm is part of the broader TDIDT (Top-Down Induction of Decision Trees) family and was specifically designed to handle classification tasks by dividing a dataset into subsets based on the attribute that offers the highest information gain. (Quinlan, 1986).
- Advantage: The ID3 algorithm is simple and easy to implement. It produces a clear and interpretable model that can handle both categorical and numerical data by converting numerical data into categorical form through discretization.
- Limitation: ID3 can be prone to overfitting, especially with noisy data. It does not handle missing values directly and does not support pruning within its standard implementation. Moreover, ID3 has a bias towards attributes with more levels, which can lead to unnecessary complexity.
II. C4.5
The C4.5 algorithm, developed by same author (Quinlan, 1993) is an extension of the earlier ID3 algorithm and is designed to generate decision trees used for classification tasks. The primary goal of C4.5 is to create a decision tree that can classify a set of data into predefined classes. C4.5 builds decision trees from a set of training data using the concept of information entropy. The algorithm can handle both continuous and discrete attributes, handle missing values, and prune trees after creation to improve their generalization.
- Advantage: One of the significant improvements of C4.5 over ID3 is its ability to handle continuous attributes. C4.5 can split continuous attributes into discrete intervals, enabling the algorithm to handle numerical data more effectively.
- Limitation: The algorithm can be computationally intensive, especially with large datasets, due to the need to sort continuous attributes and calculate the gain for each potential split.
III. CART
CART stands for Classification and Regression Trees (Breiman et al., 1984). It is characterized by constructing binary trees, where each internal node has exactly two outgoing edges. The splits are selected using the twoing criteria, and the resulting tree is pruned using cost-complexity pruning. Additionally, CART can incorporate misclassification costs in the tree induction process and allows users to provide a prior probability distribution.
A key feature of CART is its ability to generate regression trees. In regression trees, the leaves predict a real number rather than a class. For regression, CART seeks splits that minimize the prediction squared error, also known as the least-squared deviation. The prediction at each leaf node is based on the weighted mean of the node.
Advantages of Decision Trees
Decision trees offer several advantages that make them a popular choice for both classification and regression tasks in machine learning. Here are some of the key advantages:
I. Interpretability & Simplicity
One of the most significant advantages of decision trees is their ease of interpretation. The tree-like structure allows for clear visualization of the decision-making process, making it straightforward to understand and explain. This transparency is valuable in fields where interpretability is crucial, such as healthcare, finance, and regulatory environments.
II. Handling of Both Numerical & Categorical Data
Decision trees can naturally handle both numerical and categorical data, which makes them versatile and applicable to a wide range of problems. They can split into both types of variables, making them suitable for datasets with mixed variable types without requiring extensive preprocessing.
III. Self-Explanatory
Decision trees are self–explanatory and when compacted they are also easy to follow. In other words, if the decision tree has a reasonable number of leaves, it can be grasped by non–professional users. Furthermore, decision trees can be converted to a set of rules. Thus, this representation is considered as comprehensible.
IV. Nonparametric Model
Decision trees are classified as nonparametric models, which means they do not make any assumptions about the underlying distribution of the data. Unlike parametric models, which have a fixed number of parameters and assume a specific distribution (such as linear regression assuming a linear relationship), nonparametric models like decision trees are more flexible. They can adapt to the structure of the data without being constrained by predetermined forms or distributions.
V. Non-Linear Relationships
Decision trees excel at capturing non-linear relationships between features and the target variable. Unlike linear models, which assume a straight-line relationship between the input variables and the output, decision trees can model complex, intricate patterns without any need for data transformation. This ability stems from their hierarchical structure, where the data is recursively split based on feature values.
Disadvantages of Decision Trees
While decision trees offer many advantages, they also come with several disadvantages that can impact their performance and applicability in certain scenarios.
I. Overfitting
One of the primary disadvantages of decision trees is their tendency to overfit the training data, especially if the tree is allowed to grow too deep. Overfitting occurs when the model becomes too complex and captures noise or random fluctuations in the training data rather than the underlying pattern. This results in poor generalization to new, unseen data, leading to high variance in predictions. Pruning techniques and setting constraints on the tree depth can help mitigate overfitting but may not always be sufficient.
II. Instability
Decision trees are highly sensitive to small changes in the data. A minor alteration in the training dataset, such as adding or removing a few data points, can lead to a completely different tree structure. This instability arises because each split in the tree is based on the best possible feature and threshold at that node, which can change with slight variations in the data. Ensemble methods like Random Forests and Gradient Boosting are often used to address this issue by averaging the predictions of multiple trees.
III. Bias Towards Dominant Features
Decision trees can be biased towards features with more levels or categories. For instance, when using categorical variables, features with a large number of categories can dominate the splits, potentially leading to suboptimal tree structures. This bias can affect the model’s ability to accurately capture the true relationships in the data.
IV. Greedy Algorithms
The construction of decision trees is based on greedy algorithms that make locally optimal choices at each step (i.e., choosing the best feature to split the data at each node). While this approach simplifies the construction process, it may not always result in a globally optimal tree. The greedy nature of the algorithm means that the model might miss better splits that could improve overall performance.
Decision Trees in Trading
In stock trading, decision trees can be used to enhance traditional trading rules by incorporating additional market information. The research by Muh-Cherng Wu and colleagues (Wu, 2006) demonstrates this by combining the filter rule—a common technical analysis technique—with the C4.5 decision tree algorithm. The filter rule suggests buying stocks when their prices rise by a certain percentage above a recent low and selling them when prices fall by a similar percentage from a recent high. While effective, this rule’s performance can vary. By integrating a decision tree algorithm, the research aims to improve the identification of profitable trading points.
Another study performed by Prajwal and his colleagues (Prajwal et al.) concludes that decision trees are an effective tool for creating intraday trading strategies with technical indicators. Decision trees can efficiently select relevant features, adapt to different stocks and market conditions, and provide interpretable trading rules. Although the strategy’s total returns were marginally lower in the testing dataset, its superior risk-adjusted performance highlights the potential of decision tree-based strategies for enhancing intraday trading performance.
The Bottom Line
Decision trees are a powerful and intuitive tool in machine learning, representing possible outcomes based on specific conditions through a hierarchical, tree-like structure. Starting from a root node that encapsulates the entire dataset, decision trees split the data into subsets at each node based on the most significant attributes. These splits, guided by criteria such as information gain or Gini impurity, create branches that lead to decision nodes and ultimately to leaf nodes, which represent the final outcomes or predictions.
The construction of decision trees follows a recursive process, beginning with the whole dataset and continuously splitting it into more homogeneous subsets. This method, rooted in Hunt’s algorithm, ensures that each node in the tree makes a decision that best reduces impurity and increases the homogeneity of the data. Despite their advantages, such as interpretability and the ability to handle both numerical and categorical data, decision trees also have limitations, including a tendency to overfit and sensitivity to small changes in the data. However, techniques like pruning can enhance their robustness, making them a valuable model in various applications.
