Decision Trees: Structure and Concepts

Structure of a Tree

• Root: The top-most node in the tree.
• Subtree: A portion of the tree that represents a smaller decision tree within the larger one.
• Edge: A connection between two nodes, representing a decision or path.
• Parent Node: A node that has child nodes below it.
• Siblings: Nodes that share the same parent.
• Child Node: A node directly connected to and below a parent node.
• Leaf Node: A node that has no children, representing the final outcome or decision.

Decision Trees

• A decision tree is a tree-like model where each node signifies a feature/attribute from the dataset.
• Each branch represents a decision rule based on the value of the feature at the node.
• Each leaf represents the final outcome or classification (categorical or continuous value) based on traversing the tree.

Decision Tree specific

• Decision Trees are one of the most popular Machine Learning algorithms.
• Decision Trees are used for supervised learning tasks like classification and regression.
• Decision trees built for predicting a continuous target column are called regression trees.

Decision Tree Algorithms

• ID3 (Iterative Dichotomiser 3) uses Entropy function and Information gain as metrics.
• CART (Classification and Regression Trees) uses the Gini Index as a metric.

Classification using ID3 Algorithm

• Weather dataset uses weather conditions to predict whether to play, answering Y or N for "Play”.

Entropy

• Entropy measures the amount of impurity or uncertainty in a dataset.
• The formula to calculate Entropy in a dataset is: H(S) = ∑ -p(c) log₂(p(c)), where c belongs to C.
• S is the current dataset for entropy calculation.
• C is the set of classes in S, C = {yes, no}.
• p(c) is the proportion of elements in class c relative to the total elements in S.
• The attribute with the least entropy is used to split the set.
• If an event is highly predictable, it has low entropy (low uncertainty).
• Random probabilities have higher entropy (higher are uncertain).
• Entropy(P1, P2, P3, ... Pn) = -p₁log(p1) -p2log(p2) - p3log(p3).. -pnlog(pn).

Information Gain

• Information gain is a measure used to to decide which feature to choose when splitting the data at each internal node.
• Step 1: Calculate the entropy of the dataset before splitting.
• Step 2: Calculate the average entropy of the dataset after splitting.
• Step 3: Subtract the average entropy after splitting from the entropy before splitting.
• Step 4: The result is the information gain.
• The formula for calculating the information gain is: IG(A, S) = H(S) - Σ p(t)H(t) where t belongs to T.
• H(S) is the entropy of set S.
• T is the subset created by splitting S by attribute A.
• p(t) is the proportion of elements in t relative to the total elements in S.
• H(t) is the entropy of subset t.

Metrics: Weather Dataset

• Compute the entropy for the dataset, then for every attribute:
  • Calculate entropy for all categorical values.
  • Take average for the current attribute.
  • Calculate information gain for the current attribute.
• Pick the attribute with the highest information gain.
• Repeat until the decision tree is created.

Analyzing Weather Dataset

• Out of 14 instances, 9 are classified as Yes and 5 as No.
• P(Yes) = (-9/14) * log₂(9/14) = 0.41.
• P(No) = (-5/14) * log₂(5/14) = 0.53
• The total entropy H(S) = P(Yes) + P(No) = 0.94.
• Entropy of Outlook feature calculations:
  • H(Outlook = Sunny) = (-2/5) * log₂(2/5) - (3/5) * log₂(3/5) = 0.5288 + 0.4422 = 0.971.
  • H(Outlook = Overcast) = (-4/4) * log₂(4/4) - (0/4) * log₂(0/4) = 0.
  • H(Outlook = Rainy) = (-3/5) * log₂(3/5) - (2/5) * log₂(2/5) = 0.4422 + 0.5288 = 0.971.
• Average Entropy for Outlook: M(Outlook) = (5/14) * 0.971+ (4/14) * 0 + (5/14) * 0.971 = 0.6936
• Information Gain(Outlook) = H(S) – M(Outlook) = 0.94 - 0.6936 = 0.2464.

Metrics Sumarry for Weather Data

• The outlook has the highest Information Gain, so the root node is Outlook:
  • Average Entropy: 0.693, Information Gain: 0.247
• Temperature:
  • Average Entropy: 0.911, Information Gain: 0.029
• Humidity:
  • Average Entropy: 0.788, Information Gain: 0.152
• Windy:
  • Average Entropy: 0.892, Information Gain: 0.048

Pruning

• This technique reduces the number of attributes used in tree-pruning.
• Pruning prevents decision trees from overfitting the training data.
• There are two types of pruning:
  • Pre-pruning (forward pruning): Deciding during building to stop adding attributes, based on their information gain.
  • Post-pruning (backward pruning): Building the full decision tree and then prune attributes

Random Forest

• Random Forest is a supervised learning ensemble algorithm.
• Ensemble algorithms combine multiple algorithms (same or different) for classifying objects.
• Random forest builds multiple decision trees and merges them for more accurate and stable predictions.

Bagging Method

• Bagging is a technique used with DT learning Algorithms.
• N subsets (with replacement) in the Training set