Find the best split

This is the core of decision-tree training: try every question on every numeric feature and keep the one that separates the classes best.

What to build

A program that finds the feature and threshold with the largest Gini gain.

Requirements

  • Candidate thresholds for a feature are the midpoints between consecutive different values of that feature.
  • A split sends examples with value < threshold left and the rest right; its gain is Gini(parent) − (n_left/n) Gini(left) − (n_right/n) Gini(right).
  • Print feature I, threshold T, gain G (I counting from 1, T with 2 decimals, G with 3), choosing the largest gain; on a tie, the earlier feature, then the smaller threshold.
  • If no feature has two different values, print no split.

Input

Line 1: n and f. Then n lines with f numbers and a label.

Output

One line.

Constraints

1 ≤ n ≤ 300, 1 ≤ f ≤ 10.

Example

Input:

6 2
1 5 A
2 6 A
3 1 B
4 2 B
5 3 B
6 4 A

Output:

feature 2, threshold 3.50, gain 0.500

Why it works

Only thresholds between neighbouring values can change which examples go left, so the midpoints cover every distinct split, and the Gini gain measures how much purer the two sides are than the parent.

Examples

Example 1 · Input
6 2
1 5 A
2 6 A
3 1 B
4 2 B
5 3 B
6 4 A
Expected output
feature 2, threshold 3.50, gain 0.500
Example 2 · Input
4 1
1 x
2 x
3 y
4 y
Expected output
feature 1, threshold 2.50, gain 0.500

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each feature, sort its different values and try the midpoints between neighbours as thresholds.

Hint 2

Left is value < threshold, right is value ≥ threshold; gain = Gini(parent) − weighted Gini of the two sides.

Hint 3

Keep a candidate only if its gain is strictly larger, going through features in order and thresholds from small to large.

Solution

Show one correct solution (try it yourself first)
n, f = map(int, input().split())
rows = [input().split() for _ in range(n)]
xs = [[float(v) for v in r[:f]] for r in rows]
ys = [r[f] for r in rows]


def gini(labels):
    counts = {}
    for y in labels:
        counts[y] = counts.get(y, 0) + 1
    return 1 - sum((c / len(labels)) ** 2 for c in counts.values())


parent = gini(ys)
best = None
for j in range(f):
    values = sorted({x[j] for x in xs})
    for a, b in zip(values, values[1:]):
        t = (a + b) / 2
        left = [y for x, y in zip(xs, ys) if x[j] < t]
        right = [y for x, y in zip(xs, ys) if x[j] >= t]
        gain = parent - len(left) / n * gini(left) - len(right) / n * gini(right)
        if best is None or gain > best[2]:
            best = (j, t, gain)
if best is None:
    print("no split")
else:
    print(f"feature {best[0] + 1}, threshold {best[1]:.2f}, gain {best[2]:.3f}")

Lesson: Decision trees →