A decision tree is a supervised ML algorithm that can be used for both classification and regression tasks. The algorithm recursively splits the data into subsets based on the most significant attribute at each level, creating a tree-like structure where each node represents a decision based on a particular feature.

• The algorithm evaluates all the attributes (features) and select the one that best distinguishes the data based on a certain criterion (for instance, gini index).
• The most important attribute becomes the root node.

The tree depth represents how many questions are asked to reach the predicted classification (result).

• Classification: Gini Impurity
• Regression: Mean Squared Error

It calculates the impurity of each node between [0,1]. The lower the better (purer the feature)

$$ \text{Gini(node)} =1-\sum p^2_i $$

Where, $p_i$ is the ratio of observation of being of class $i$ at each node.

If there is a feature that can predict a class with 100% accuracy, the Gini index will 0

$$ 1 - (\text{probability of “yes”})^2 - (\text{probability of “no”})^2 \ 1- (\frac{100}{100})^2 - (\frac{0}{100})^2 = 0 $$

The feature has no impurity as it can 100% predict the class.

The total Gini Impurity is the weighted average of the leaf Impurities.

$$ \text{Gini Impuirity} = (\frac{n_1}{n_1+n_2})g_1 + (\frac{n_2}{n_1+n_2})g_2 $$

Where,

• $n_1$ : Sample size for node 1
• $n_2$: Sample size for node 2
• $g_1$: Gini index for node 1
• $g_2$: Gini index for node 2

1. Sort the feature values (lowest to highest)
2. Calculate the average values for all adjacent values (the middle point between the values)
3. Calculate the impurity values for each average weight.
4. Select the value that the lowest impurity value to be the optimal split.

Similar to classification, DTR splits the dataset by finding the right optimal threshold through an iterative process.

1. Split the dataset into two subsets. The first data point and the remaining data points.
2. For each subset, calculate the sum of squared error. Then combine the sum of squared error.
3. Repeat step 1 and 2 until a predefined stopping condition is met such as min_samples_split
4. Select the optimal split (threshold) that has the lowest SSE
5. To complete the decision tree, repeat step 1 and 4.

• For each feature, compute the sum of squared errors for different thresholds and select the optimal threshold which has yield the lowest sum of squared error.
• Compare the sum of squared errors from each features and select the feature that has the lowest sum of squared errors.

• Select the best attribute to be the root node.
• The dataset is split into subsets based their values of that attribute.
• Repeat the process of selecting the best attribute for each of the subset until a stopping condition is met.

• It reflects a sequential decision-making process, where each internal node corresponds to a decision based on a specific feature.
• Decision trees are visually represented as tree structures, making it easier to follow the decision making process.
• No complex mathematical formulas are used.

• It can handle both classification and regression problems.
• It can process numerical and categorical data together.
• It can handle non-linear relationships.
• It is robust to outliers.
• No assumptions required on the data distribution.

At each decision point, the algorithm evaluates different features and selects the one that provides the best split based on a certain criterion such as the Gini Impurity. The chosen feature will influence subsequent splits. This process enables the algorithm to automatically identify and prioritise the most relevant features and feature interactions.

• Pretty intuitive and easy to interpret
• Versatile
• No scaling necessary
• Robust to outliers
• Automated feature selection

• Local Optimal vs Global Optimal: It makes the most optimal decision at each step but does not take into account the global optimum. Choosing the best result at a given step does not ensure the optimal decision.
• Prone to overfitting: This is because the amount of specificity we look at leading to smaller sample of events that meet the previous assumptions. Using smaller samples could lead to sub-optimal conclusions, not adequate for an informed decision.

Decision nodes represent decisions based on the values of specific features. At each decision node, the algorithm evaluates a feature and decides which branch to follow based on the feature’s value.

Leaf nodes (terminal nodes) represent the final outcomes or predictions.

• In a classification tree, each leaf node corresponds to a class label.
• In a regression tree, each leaf node contains the predicted numerical value.

$$ \text{Gini(node)} =1-(p_1^2 +p^2_2+p^2_3) $$

• min_samples_split sets the minimum of samples required to split an internal node.
• To prevent overfitting, set a higher value.

• min_samples_split sets the minimum of samples to be a leaf node.
• To prevent overfitting, set a higher value.

• max_depth controls the maximum depth of the tree, which is the longest path from the root node to a leaf node.
• To prevent overfitting, set a lower value, which limits the complexity of the tree

min_samples_leaf overrides min_samples_splt. The split won’t be allowed if the number of samples in the leaf is less than min_samples_leaf.