Decision Trees are versatile, non-parametric supervised learning models that can be used
for both classification and regression tasks. Their strength lies in their intuitive, flowchart-like
structure, which makes them highly interpretable. A Decision Tree essentially mimics human
decision-making by creating a series of sequential tests on feature values that lead to a final
classification or prediction.

• The tree building process begins at the root node, which initially contains all
  the data.
• Each internal node within the tree represents a "test" or a decision based on
  a specific feature (e.g., "Is 'Age' greater than 30?").
• Each branch extending from an internal node represents the outcome of that
  test (e.g., "Yes" or "No").
• The process continues down the branches until a leaf node is reached. A leaf
  node represents the final classification label (for classification tasks) or a
  predicted numerical value (for regression tasks).

The construction of a Decision Tree is a recursive partitioning process. At
each node, the algorithm systematically searches for the "best split" of the
data. A split involves choosing a feature and a threshold value for that feature
that divides the current data subset into two (or more) child subsets.

• The goal of finding the "best split" is to separate the data into child nodes that
  are as homogeneous (or pure) as possible with respect to the target
  variable. In simpler terms, we want each child node to contain data points
  that predominantly belong to a single class after the split. This "purity" is
  quantified by impurity measures.
• This splitting process continues recursively on each new subset of data
  created by a split, moving down the tree until a predefined stopping condition
  is met (e.g., a node becomes perfectly pure, or the tree reaches a maximum
  allowed depth).

These measures are mathematical functions that quantify how mixed or
impure the classes are within a given node. The objective of any split in a
Decision Tree is to reduce impurity in the resulting child nodes as much as
possible.

• Gini Impurity:
• Concept: Gini impurity measures the probability of misclassifying a
  randomly chosen element in the node if it were randomly labeled
  according to the distribution of labels within that node.
• Interpretation: A Gini impurity value of 0 signifies a perfectly pure
  node (all samples in that node belong to the same class). A value
  closer to 0.5 (for a binary classification) indicates maximum impurity
  (classes are equally mixed).
• Splitting Criterion: The algorithm chooses the split that results in the
  largest decrease in Gini impurity across the child nodes compared to
  the parent node.
• Entropy:
• Concept: Entropy, rooted in information theory, measures the amount
  of disorder or randomness (uncertainty) within a set of data.
• Interpretation: A lower entropy value indicates higher purity (less
  uncertainty about the class of a random sample). An entropy of 0
  means perfect purity. A higher entropy indicates greater disorder.
• Information Gain: When using Entropy, the criterion for selecting the
  best split is Information Gain. Information Gain is simply the
  reduction in Entropy after a dataset is split on a particular feature. The
  algorithm selects the feature and threshold that yield the maximum
  Information Gain, meaning they create the purest possible child nodes
  from a given parent node.

Decision Trees, particularly when they are allowed to grow very deep and
complex without any constraints, are highly prone to overfitting.

• Why? An unconstrained Decision Tree can continue to split its nodes until
  each leaf node contains only a single data point or data points of a single
  class. In doing so, the tree effectively "memorizes" every single training
  example, including any noise, random fluctuations, or unique quirks present
  only in the training data. This creates an overly complex, highly specific, and
  brittle model that perfectly fits the training data but fails to generalize well to
  unseen data. It's like building a set of rules so specific that they only apply to
  the exact examples you've seen, not to any new, slightly different situations.

Pruning is the essential process of reducing the size and
complexity of a decision tree by removing branches or nodes that either
have weak predictive power or are likely to be a result of overfitting to noise in
the training data. Pruning helps to improve the tree's generalization ability.

• Pre-pruning (Early Stopping): This involves setting constraints or stopping
  conditions before the tree is fully grown. The tree building process stops once
  these conditions are met, preventing it from becoming too complex. Common
  pre-pruning parameters include:
• max_depth: Limits the maximum number of levels (depth) in the tree. A
  shallower tree is generally simpler and less prone to overfitting.
• min_samples_split: Specifies the minimum number of samples that
  must be present in a node for it to be considered for splitting. If a node
  has fewer samples than this threshold, it becomes a leaf node,
  preventing further splits.
• min_samples_leaf: Defines the minimum number of samples that must
  be present in each leaf node. This ensures that splits do not create
  very small, potentially noisy, leaf nodes.
• Post-pruning (Cost-Complexity Pruning): In this approach, the Decision Tree
  is first allowed to grow to its full potential (or a very deep tree). After the
  full tree is built, branches or subtrees are systematically removed (pruned) if
  their removal does not significantly decrease the tree's performance on a
  separate validation set, or if they contribute little to the overall predictive
  power. While potentially more effective, this method is often more
  computationally intensive. (For this module, we will primarily focus on
  pre-pruning for practical implementation).