Decision tree (CART)

import pandas as pd
import numpy as np
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text

df = pd.read_csv(DATA / "uy_ijara.csv")
num = ["xonalar", "maydon_m2", "qavat", "qavatlar_soni", "metro_km", "mebel"]
X, y = df[num], df["ijaraga_berildi_30k"]
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42, stratify=y)

tree = DecisionTreeClassifier(max_depth=3, random_state=42).fit(X_tr, y_tr)
print(export_text(tree, feature_names=num, decimals=1))

def gini(y):
    if len(y) == 0: return 0.0
    p = np.bincount(y, minlength=2) / len(y)
    return float(1 - np.sum(p ** 2))

def entropy(y):
    if len(y) == 0: return 0.0
    p = np.bincount(y, minlength=2) / len(y)
    p = p[p > 0]
    return float(-np.sum(p * np.log2(p)))

print(f"{'case':<34} {'Gini':>8} {'Entropy':>11}")
print("-" * 55)
for name, arr in [
    ("Pure: all 1 (10 of them)", np.ones(10, int)),
    ("Pure: all 0 (10 of them)", np.zeros(10, int)),
    ("Almost pure: 9 ones, 1 zero", np.r_[np.ones(9, int), np.zeros(1, int)]),
    ("Half and half: 5 ones, 5 zeros", np.r_[np.ones(5, int), np.zeros(5, int)]),
]:
    print(f"{name:<34} {gini(arr):>8.4f} {entropy(arr):>11.4f}")

def best_split(X, y, col):
    values = np.unique(X[col])
    cuts = (values[:-1] + values[1:]) / 2
    best, best_cut = -1, None
    start = gini(y.to_numpy())
    for c in cuts:
        left = y[X[col] <= c].to_numpy()
        right = y[X[col] > c].to_numpy()
        if len(left) == 0 or len(right) == 0: continue
        weighted = (len(left) * gini(left) + len(right) * gini(right)) / len(y)
        gain = start - weighted
        if gain > best:
            best, best_cut = gain, c
    return best_cut, best

print("The BEST question for each column (by Gini gain):")
result = []
for c in num:
    cut, gain = best_split(X_tr, y_tr, c)
    result.append({"column": c, "best threshold": round(float(cut), 2),
                   "Gini gain": round(gain, 5)})
show(pd.DataFrame(result).sort_values("Gini gain", ascending=False))

show(pd.DataFrame([
    {"Criterion": "gini", "Formula": "1 - sum(p^2)", "Speed": "Faster",
     "In sklearn": "THE DEFAULT", "In practice": "Almost always this one"},
    {"Criterion": "entropy", "Formula": "-sum(p * log2(p))", "Speed": "Slower (computes logs)",
     "In sklearn": "criterion='entropy'", "In practice": "Almost the same result"},
]))

print("The two criteria, measured and compared:")
for crit in ["gini", "entropy"]:
    b = cross_val_score(DecisionTreeClassifier(criterion=crit, max_depth=6, random_state=42),
                        X, y, cv=5, scoring="f1")
    print(f"  criterion={crit:<8} F1 = {b.mean():.4f} ±{b.std():.4f}")
print()
print("The difference is usually negligible, so you leave the default alone.")

print(f"{'max_depth':>10} {'train F1':>10} {'test F1':>9} {'gap':>8} {'leaves':>9}")
print("-" * 52)
from sklearn.metrics import f1_score
for d in [2, 3, 5, 8, 15, None]:
    m = DecisionTreeClassifier(max_depth=d, random_state=42).fit(X_tr, y_tr)
    tr_f = f1_score(y_tr, m.predict(X_tr))
    te_f = f1_score(y_te, m.predict(X_te))
    flag = "  <-- MEMORISED" if tr_f - te_f > 0.2 else ""
    print(f"{str(d):>10} {tr_f:>10.4f} {te_f:>9.4f} {tr_f-te_f:>8.4f} {m.get_n_leaves():>9}{flag}")

show(pd.DataFrame([
    {"Parameter": "max_depth", "What it does": "A limit on the tree's depth",
     "Practical value": "3-10"},
    {"Parameter": "min_samples_leaf", "What it does": "Every leaf must have at least this many samples",
     "Practical value": "5-50"},
    {"Parameter": "min_samples_split", "What it does": "A split needs at least this many samples",
     "Practical value": "10-100"},
    {"Parameter": "ccp_alpha", "What it does": "Pruning: cutting back after growing",
     "Practical value": "0.0-0.02"},
]))

print("min_samples_leaf is the most useful lever:")
print(f"{'min_samples_leaf':>18} {'CV F1':>9} {'±':>8} {'leaves':>9}")
print("-" * 48)
for msl in [1, 5, 20, 50, 100]:
    m = DecisionTreeClassifier(min_samples_leaf=msl, random_state=42)
    b = cross_val_score(m, X, y, cv=5, scoring="f1")
    m.fit(X_tr, y_tr)
    print(f"{msl:>18} {b.mean():>9.4f} {b.std():>8.4f} {m.get_n_leaves():>9}")

m = DecisionTreeClassifier(max_depth=6, min_samples_leaf=20, random_state=42).fit(X_tr, y_tr)
importance = pd.DataFrame({"feature": num, "importance": m.feature_importances_.round(4)})
show(importance.sort_values("importance", ascending=False))
print()
print(f"Sum: {m.feature_importances_.sum():.4f}  (always 1.0)")

from sklearn.inspection import permutation_importance
pi = permutation_importance(m, X_te, y_te, n_repeats=20, random_state=42, scoring="f1")
compare = pd.DataFrame({
    "feature": num,
    "from the tree": m.feature_importances_.round(4),
    "permutation": pi.importances_mean.round(4),
}).sort_values("permutation", ascending=False)
show(compare)

show(pd.DataFrame([
    {"Property": "Needs scaling?", "Tree": "NO: it only asks 'bigger or smaller?'",
     "Linear model": "Yes"},
    {"Property": "Non-linear patterns", "Tree": "Handles them (the ring: 0.9883)",
     "Linear model": "Can't (0.5350)"},
    {"Property": "Explanation", "Tree": "The easiest: you can draw it",
     "Linear model": "Through coefficients"},
    {"Property": "Text columns", "Tree": "NEED ENCODING in sklearn",
     "Linear model": "Need encoding"},
    {"Property": "Overfitting", "Tree": "VERY prone: you must limit it",
     "Linear model": "Less prone"},
    {"Property": "Stability", "Tree": "Low: change the data a little and the tree is completely different",
     "Linear model": "Higher"},
]))

print("One tree, the first question on different train splits:")
for rs in [0, 1, 7, 42, 99]:
    Xa, _, ya, _ = train_test_split(X, y, test_size=0.3, random_state=rs, stratify=y)
    d1 = DecisionTreeClassifier(max_depth=2, random_state=42).fit(Xa, ya)
    root = num[d1.tree_.feature[0]]
    cut = d1.tree_.threshold[0]
    print(f"  random_state={rs:<4} first question: {root} <= {cut:.2f}")

from sklearn.pipeline import Pipeline
from sklearn.compose import ColumnTransformer
from sklearn.preprocessing import OneHotEncoder

try:
    DecisionTreeClassifier().fit(df[["tuman", "maydon_m2"]], y)
except ValueError as e:
    print("If we pass the text column directly:")
    print(f"  ValueError: {str(e)[:78]}")
print()
print("So a tree needs encoding too:")
pipe = Pipeline([
    ("t", ColumnTransformer([("cat", OneHotEncoder(handle_unknown="ignore"), ["tuman"])],
                            remainder="passthrough")),
    ("m", DecisionTreeClassifier(max_depth=6, min_samples_leaf=20, random_state=42)),
])
b = cross_val_score(pipe, df[num + ["tuman"]], y, cv=5, scoring="f1")
print(f"  with tuman    F1 = {b.mean():.4f} ±{b.std():.4f}")
b2 = cross_val_score(DecisionTreeClassifier(max_depth=6, min_samples_leaf=20, random_state=42),
                     X, y, cv=5, scoring="f1")
print(f"  without tuman F1 = {b2.mean():.4f} ±{b2.std():.4f}")

show(pd.DataFrame([
    {"Concept": "The idea", "In one sentence": "Not coefficients: a sequence of questions"},
    {"Concept": "The split criterion", "In one sentence": "Gini or entropy: reduce impurity"},
    {"Concept": "gini vs entropy", "In one sentence": "The difference is negligible; leave the default"},
    {"Concept": "Overfitting", "In one sentence": "An unlimited tree memorises"},
    {"Concept": "The most useful lever", "In one sentence": "min_samples_leaf, rather than max_depth"},
    {"Concept": "feature_importances_", "In one sentence": "Free but misleading; permutation is more reliable"},
    {"Concept": "Scaling", "In one sentence": "NOT NEEDED"},
    {"Concept": "Text columns", "In one sentence": "Encoding is REQUIRED in sklearn: it raises ValueError"},
    {"Concept": "The biggest weakness", "In one sentence": "Unstable: the root question changes from split to split"},
]))