Problems

1 / 1

Decision Tree Best Split

Classic ML

Hard

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.

Algorithm

Compute the Gini impurity of the parent node:

\text{Gini}(S) = 1 - \sum_{k} p_k^2

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:

\text{Gini}_{\text{split}} = \frac{|S_L|}{|S|} \cdot \text{Gini}(S_L) + \frac{|S_R|}{|S|} \cdot \text{Gini}(S_R)

The information gain is the parent Gini minus the weighted split Gini. Return the feature and threshold with the highest gain. Break ties by smallest feature index, then smallest threshold.

Return the selected feature index and threshold as a two-item list.

Loading visualization...

Examples

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]

Hint 1

Generate candidate thresholds from midpoints between sorted unique feature values.

Hint 2

Compare parent impurity with the size-weighted impurities of both children.

Requirements

Use Gini impurity as the splitting criterion
Try thresholds at the midpoint between consecutive sorted unique values for each feature
Weight the child Gini impurities by the fraction of samples in each child
Return [feature_index, threshold] as a list

Constraints

X has at least 2 rows and 1 column
y has at least 2 distinct classes
A valid split exists
Return [feature_index, threshold]
Time limit: 300 ms

Try Similar Problems

Gini Impurity Information Gain Entropy Node Random Forest Vote Gaussian Naive Bayes

Prev Next

Decision Tree Best Split

Classic ML

Hard

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.

Algorithm

Compute the Gini impurity of the parent node:

\text{Gini}(S) = 1 - \sum_{k} p_k^2

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:

\text{Gini}_{\text{split}} = \frac{|S_L|}{|S|} \cdot \text{Gini}(S_L) + \frac{|S_R|}{|S|} \cdot \text{Gini}(S_R)

The information gain is the parent Gini minus the weighted split Gini. Return the feature and threshold with the highest gain. Break ties by smallest feature index, then smallest threshold.

Return the selected feature index and threshold as a two-item list.

Loading visualization...

Examples

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]

Hint 1

Generate candidate thresholds from midpoints between sorted unique feature values.

Hint 2

Compare parent impurity with the size-weighted impurities of both children.

Requirements

Use Gini impurity as the splitting criterion
Try thresholds at the midpoint between consecutive sorted unique values for each feature
Weight the child Gini impurities by the fraction of samples in each child
Return [feature_index, threshold] as a list

Constraints

X has at least 2 rows and 1 column
y has at least 2 distinct classes
A valid split exists
Return [feature_index, threshold]
Time limit: 300 ms

Try Similar Problems

Gini Impurity Information Gain Entropy Node Random Forest Vote Gaussian Naive Bayes

Case 1

Case 2

X =

Accepts: array

y =

Accepts: array

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.

Algorithm

Compute the Gini impurity of the parent node:

\text{Gini}(S) = 1 - \sum_{k} p_k^2

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:

\text{Gini}_{\text{split}} = \frac{|S_L|}{|S|} \cdot \text{Gini}(S_L) + \frac{|S_R|}{|S|} \cdot \text{Gini}(S_R)

The information gain is the parent Gini minus the weighted split Gini. Return the feature and threshold with the highest gain. Break ties by smallest feature index, then smallest threshold.

Return the selected feature index and threshold as a two-item list.