Decision Trees

FEATURES = ["Outlook", "Temperature", "Humidity", "Wind"]
TARGET = "Play"

raw = """Sunny Hot High Weak No
Sunny Hot High Strong No
Overcast Hot High Weak Yes
Rain Mild High Weak Yes
Rain Cool Normal Weak Yes
Rain Cool Normal Strong No
Overcast Cool Normal Strong Yes
Sunny Mild High Weak No
Sunny Cool Normal Weak Yes
Rain Mild Normal Weak Yes
Sunny Mild Normal Strong Yes
Overcast Mild High Strong Yes
Overcast Hot Normal Weak Yes
Rain Mild High Strong No"""

rows = [dict(zip(FEATURES + [TARGET], line.split())) for line in raw.splitlines()]

import math
from collections import Counter

def entropy(rows):
    n = len(rows)
    counts = Counter(r[TARGET] for r in rows)
    return -sum(c / n * math.log2(c / n) for c in counts.values())   # classes with count 0 never appear

print(round(entropy(rows), 3))   # 0.94

def split(rows, feature):
    groups = {}                                    # value -> list of rows
    for r in rows:
        groups.setdefault(r[feature], []).append(r)
    return groups

def information_gain(rows, feature):
    n = len(rows)
    children = split(rows, feature).values()
    weighted = sum(len(ch) / n * entropy(ch) for ch in children)
    return entropy(rows) - weighted

for f in FEATURES:
    print(f, round(information_gain(rows, f), 3))
# Outlook 0.247
# Temperature 0.029
# Humidity 0.152
# Wind 0.048

def majority(rows):
    return Counter(r[TARGET] for r in rows).most_common(1)[0][0]

def build_tree(rows, features, max_depth=None, depth=0):
    classes = set(r[TARGET] for r in rows)
    if len(classes) == 1:                                  # pure node
        return classes.pop()
    if not features or (max_depth is not None and depth == max_depth):
        return majority(rows)                              # nothing left to ask / depth limit
    best = max(features, key=lambda f: information_gain(rows, f))
    rest = [f for f in features if f != best]
    return {
        "feature": best,
        "majority": majority(rows),                        # used for values unseen in training
        "children": {v: build_tree(sub, rest, max_depth, depth + 1)
                     for v, sub in split(rows, best).items()},
    }

tree = build_tree(rows, FEATURES)
print(tree)
# {'feature': 'Outlook', 'majority': 'Yes', 'children': {
#     'Sunny': {'feature': 'Humidity', 'majority': 'No', 'children': {'High': 'No', 'Normal': 'Yes'}},
#     'Overcast': 'Yes',
#     'Rain': {'feature': 'Wind', 'majority': 'Yes', 'children': {'Weak': 'Yes', 'Strong': 'No'}}}}

def predict(tree, x):
    while isinstance(tree, dict):                          # walk down until we reach a leaf
        tree = tree["children"].get(x[tree["feature"]], tree["majority"])
    return tree

def print_tree(tree, indent=""):
    if not isinstance(tree, dict):
        print(indent + "→ " + tree)
        return
    for value, child in tree["children"].items():
        print(f"{indent}{tree['feature']} = {value}")
        print_tree(child, indent + "    ")

day = {"Outlook": "Sunny", "Temperature": "Cool", "Humidity": "High", "Wind": "Strong"}
print(predict(tree, day))                                              # No
print(sum(predict(tree, r) == r[TARGET] for r in rows), "/", len(rows))   # 14 / 14
print_tree(tree)

def entropy_of(labels):
    n = len(labels)
    return -sum(c / n * math.log2(c / n) for c in Counter(labels).values())

def best_threshold(xs, ys):
    """Best question 'x <= t' for one numeric feature. Returns (t, gain)."""
    pairs = sorted(zip(xs, ys))
    parent, n = entropy_of(ys), len(ys)
    best_t, best_gain = None, -1.0
    for i in range(1, n):
        if pairs[i - 1][0] == pairs[i][0]:
            continue                                       # no threshold between equal values
        t = (pairs[i - 1][0] + pairs[i][0]) / 2            # midpoint between neighbours
        left = [y for _, y in pairs[:i]]
        right = [y for _, y in pairs[i:]]
        gain = parent - (len(left) / n * entropy_of(left) + len(right) / n * entropy_of(right))
        if gain > best_gain:
            best_t, best_gain = t, gain
    return best_t, best_gain

temps = [64, 65, 68, 69, 70, 71, 72, 75, 80, 81, 83, 85]
play  = ["Yes", "No", "Yes", "Yes", "Yes", "No", "No", "Yes", "No", "Yes", "Yes", "No"]
t, g = best_threshold(temps, play)
print(t, round(g, 3))   # 84.0 0.113

import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text

df = pd.DataFrame(rows)
X = pd.get_dummies(df[FEATURES])           # Outlook_Sunny, Outlook_Rain, ... (0/1 columns)
y = df[TARGET]

clf = DecisionTreeClassifier(
    criterion="entropy",     # or "gini" (the default)
    max_depth=None,          # pre-pruning: limit the depth
    min_samples_leaf=1,      # pre-pruning: minimum examples in a leaf
    ccp_alpha=0.0,           # post-pruning: cost-complexity parameter
    random_state=0,
).fit(X, y)

print(export_text(clf, feature_names=list(X.columns)))
print("training accuracy:", clf.score(X, y))   # 1.0