## Introduction

Decision trees are popular due to their simplicity and interpretability. When working with continuous data, one of the key challenges is determining the optimal split points or thresholds. This influences the tree's ability to generalize well on unseen data. The primary goal is to select thresholds that maximize the homogeneity of the target variable within the partitions.

## Overview of Decision Trees

A decision tree is a flowchart-like structure used for decision-making and prediction tasks. Continuous data, unlike categorical data, does not have predefined values, making the choice of thresholds for partitioning crucial. The objective at each node is to find a threshold that best splits the dataset into homogeneous subsets regarding the target variable.

## Techniques for Finding Thresholds

### 1. Exhaustive Search

This method considers all possible thresholds for a particular feature. Typically, a threshold is chosen between each pair of adjacent sorted samples, making it computationally expensive.

**Example**:

Consider a set of data points with feature values: `[2, 3, 10, 18]`. The candidate thresholds are the midpoints between consecutive sorted values: `2.5`, `6.5`, and `14.0`.

**Pros**: Finds the global optimal threshold under the current splitting criterion.

**Cons**: Computationally intensive, especially for large datasets with many unique values.

### 2. Information Gain

Information gain evaluates the reduction in entropy before and after a dataset is split on a specific threshold. This criterion is primarily used for classification tasks. Information gain is defined as:

`$$IG = H(S) - \sum_{v} \frac{|S_v|}{|S|} H(S_v)$$`

where `$H(\cdot)$` denotes entropy and `$S_v$` is a subset after splitting.

Entropy itself is calculated as:

`$$H(S) = -\sum_{i=1}^{c} p_i \log_2(p_i)$$`

where `$p_i$` is the proportion of class `$i$` in set `$S$`, and `$c$` is the number of classes.

**Example**:

For two classes in a dataset split by threshold `$t$`, compute the entropy for subsets before and after the split, and choose the threshold with the maximal information gain.

### 3. Gini Impurity

Gini impurity measures the frequency of a random point being classified incorrectly once assigned to a particular subset. The goal is to minimize the impurity.

The formula is:

`$$\text{Gini}(S) = 1 - \sum_{i=1}^{c} p_i^2$$`

where `$p_i$` is the proportion of items of class `$i$` in the node.

For a binary split into subsets `$S_1$` and `$S_2$`, the weighted Gini after splitting is:

`$$\text{Gini}_{\text{split}} = \frac{|S_1|}{|S|} \text{Gini}(S_1) + \frac{|S_2|}{|S|} \text{Gini}(S_2)$$`

The threshold that minimizes `$\text{Gini}_{\text{split}}$` is selected.

### 4. Variance Reduction

For regression tasks, variance reduction is often used. It measures the reduction of variance after the dataset is split at a given threshold.

The formula is:

`$$VR = \text{Var}(S) - \left(\frac{|S_1|}{|S|} \text{Var}(S_1) + \frac{|S_2|}{|S|} \text{Var}(S_2)\right)$$`

where `$S_1$` and `$S_2$` are the datasets after the split.

**Example**:

For a series of target values, compute variance before and after the split. Choose the threshold that maximizes the variance reduction.

## Summary Table

| Method | Key Formula | Pros | Cons |
| --- | --- | --- | --- |
| Exhaustive Search | Midpoints between consecutive samples | Finds global optimum | Computationally expensive |
| Information Gain | `$IG = H(S) - \sum \frac{|S_v|}{|S|} H(S_v)$` | Measures information quality | Can be biased towards many-valued attributes |
| Gini Impurity | `$\text{Gini}(S) = 1 - \sum p_i^2$` | Fast computation | May favor pure nodes prematurely |
| Variance Reduction | `$VR = \text{Var}(S) - \text{weighted Var after split}$` | Direct measure of split quality | Sensitive to outliers |

## Computational Considerations

The choice of method impacts computational efficiency and effectiveness. While exhaustive search can become unfeasible with large datasets, heuristic methods like Gini impurity and information gain offer more practical approaches. Preprocessing techniques such as quantile binning can also reduce computational load by limiting the number of candidate thresholds.

In practice, implementations like scikit-learn sort the feature values once (`$O(n \log n)$`), then evaluate all candidate splits in a single pass (`$O(n)$`), making the total cost per feature `$O(n \log n)$` rather than the naive `$O(n^2)$`.

## Conclusion

Finding thresholds for continuous data in decision trees involves a balance between precision and computational feasibility. By employing various criteria such as information gain, Gini impurity, or variance reduction, practitioners can tailor their approaches to suit specific datasets and predictive objectives. Understanding these methodologies enables more effective model construction and optimization in machine learning applications.