A decision tree grows by repeatedly splitting the data on the feature and threshold that best separates the classes. The quality of a split is measured by the information gain: how much the Gini impurity decreases after splitting.
Given a feature matrix X and class labels y, find the single best split (feature index and threshold) that maximizes information gain using Gini impurity.
Where p_k is the fraction of samples belonging to class k.
For each feature and each midpoint between consecutive sorted unique values, split the data into left (feature <= threshold) and right (feature > threshold)
Compute the weighted Gini impurity after the split:
Return the selected feature index and threshold as a two-item list.
Input: X = [[1, 5], [2, 5], [3, 5], [4, 5]], y = [0, 0, 1, 1]
Output: [0, 2.5]
Explanation: Feature 0 at 2.5 separates the two classes perfectly.
Input: X = [[1, 1], [2, 1], [1, 10], [2, 10]], y = [0, 0, 1, 1]
Output: [1, 5.5]
Generate candidate thresholds from midpoints between sorted unique feature values.
Compare parent impurity with the size-weighted impurities of both children.
Accepts: array
Accepts: array
A decision tree grows by repeatedly splitting the data on the feature and threshold that best separates the classes. The quality of a split is measured by the information gain: how much the Gini impurity decreases after splitting.
Given a feature matrix X and class labels y, find the single best split (feature index and threshold) that maximizes information gain using Gini impurity.
Where p_k is the fraction of samples belonging to class k.
For each feature and each midpoint between consecutive sorted unique values, split the data into left (feature <= threshold) and right (feature > threshold)
Compute the weighted Gini impurity after the split:
Return the selected feature index and threshold as a two-item list.
Input: X = [[1, 5], [2, 5], [3, 5], [4, 5]], y = [0, 0, 1, 1]
Output: [0, 2.5]
Explanation: Feature 0 at 2.5 separates the two classes perfectly.
Input: X = [[1, 1], [2, 1], [1, 10], [2, 10]], y = [0, 0, 1, 1]
Output: [1, 5.5]
Generate candidate thresholds from midpoints between sorted unique feature values.
Compare parent impurity with the size-weighted impurities of both children.
Accepts: array
Accepts: array