Find the Best Split Practice Problem

This data science coding problem helps you practice Decision Trees, find the best split, and implementation skills. Read the problem statement, write your solution, and strengthen your understanding of Decision Trees.

• Problem ID: 207
• Problem key: 207-find-the-best-split
• URL: https://datacrack.app/solve/207-find-the-best-split
• Difficulty: medium
• Topic: Decision Trees
• Module: Supervised Learning

Problem Statement

# 🧩 Find the Best Split

---

### 🎯 Goal

Compare possible decision-tree questions and choose the split with the lowest weighted Gini impurity.

---

### 📖 Introduction

A decision tree needs to choose the best question to split a node.

For numeric features, a split is defined by:

> feature value <= threshold

The tree tries different features and thresholds, creates child nodes, and measures how clean they become.

In this problem, we use **weighted Gini impurity** to compare possible splits.

First, we calculate the weighted Gini impurity of the child nodes:

$$
Gini_{children}=\frac{n_L}{n}Gini_L+\frac{n_R}{n}Gini_R
$$

A lower `Gini_children` means the child nodes are cleaner.

This is equivalent to choosing the split with the highest Gini reduction:

$$
Gini\ Reduction = Gini_{parent} - Gini_{children}
$$

Since `Gini_parent` is the same for all candidate splits at the same node, we do not need to compute Gini reduction directly. We can simply choose the split with the **lowest weighted Gini impurity**.

The best split is the one with the **lowest weighted Gini impurity**, because it leaves the child nodes least mixed.

---

### 💻 Task

Implement `find_best_split(X, y, feature_names)`.

Your function should:

- Try every feature.
- Build midpoint thresholds between sorted unique feature values.
- Split labels into left and right groups for each threshold.
- Compute the weighted child Gini impurity for each split.
- Choose the split with the lowest weighted child Gini impurity.
- Return the best split.

This is equivalent to choosing the split with the highest Gini reduction, because the parent Gini impurity is the same for all candidate splits.

Round `threshold` and `weighted_gini` to 6 decimals.

If scores tie, choose the smaller feature index. If still tied, choose the smaller threshold.

---

### 📥 Input / 📤 Output

**Input**
- `X`: feature matrix
- `y`: labels
- `feature_names`: names for each feature column

**Output**
- dictionary containing the best split:
  - `feature_index`
  - `feature_name`
  - `threshold`
  - `weighted_gini`
  - `left_y`
  - `right_y`

---

### 🧩 Starter Code

```python
def find_best_split(X, y, feature_names):
    def gini_impurity(labels_at_node):
        # Your code here
        pass

    # Your code here
    pass
```

---

### 💡 Example

This example uses two numeric features: `size` and `color_code`.

```python
find_best_split(
    [[2.7, 1], [1.3, 1], [3.1, 0], [1.0, 0], [3.8, 1], [1.5, 0]],
    ["yes", "no", "yes", "no", "yes", "no"],
    ["size", "color_code"]
)
```

Expected best split:

```python
{
    "feature_index": 0,
    "feature_name": "size",
    "threshold": 2.1,
    "weighted_gini": 0.0,
    "left_y": ["no", "no", "no"],
    "right_y": ["yes", "yes", "yes"]
}
```

---

### ⚠️ Common Mistakes

- Testing only the original feature values instead of midpoint thresholds.
- Forgetting to weight child Gini values by child size.
- Allowing a split where one child is empty.