decision trees splitting criteria tree construction
# Decision Trees: Splitting Criteria & Tree Construction
## Introduction & Motivation
Decision trees recursively partition feature space via splitting criteria (Gini, entropy) maximizing information gain. Interpretable—each path root-to-leaf visualizes decision rule. No feature scaling required; handles mixed data types. Foundation for ensemble methods (Random Forest, Gradient Boosting).
Motivation: Linear models insufficient for complex relationships. Trees capture non-linearities interpretably. Non-parametric—no assumptions on data distribution. Base learner for powerful ensembles.
Applications: Medical diagnosis decision rules, credit approval, feature importance extraction, anomaly detection.
---
## Core Concepts & Theory
### Splitting Criteria
Gini impurity:
$$ ext{Gini} = 1 - \sum_k p_k^2$$
where p_k is fraction of class k. Lower Gini → purer split.
Entropy (Information Gain):
$$H = -\sum_k p_k \log p_k$$
Gain = H_parent - weighted sum H_children.
### Tree Construction
Greedy algorithm: at each node, select feature/threshold maximizing gain; recurse on partitions; stop via max_depth or min_samples_leaf.
---
## Mathematical Formulation
Gini impurity after split:
$$ ext{Gini}_{ ext{split}} = \frac{n_L}{n} ext{Gini}_L + \frac{n_R}{n} ext{Gini}_R$$
Choose split maximizing gain:
$$ ext{Gain} = ext{Gini}_{ ext{parent}} - ext{Gini}_{ ext{split}}$$
---
## Advanced Theory & Extensions
### Pruning
Post-hoc removal of leaves reducing validation accuracy (cost-complexity pruning).
### Handling Imbalance
Class weight adjustment; adjust min_samples_leaf per class.
---
## Computational Considerations
Training: O(n \log n imes d) for n samples, d features.
Inference: O( ext{tree depth}) per sample, typically O(\log n).
Memory: O( ext{num_nodes}) for tree structure.
---
## Practical Implementation Strategies
### Hyperparameter Selection
max_depth: Limit depth to prevent overfitting; start with 5-10.
min_samples_split: Minimum samples to split; default 2, increase for noise.
min_samples_leaf: Minimum samples in leaf; larger → smoother boundaries.
### Feature Importance
Importance = sum of gain across all splits using feature.
---
## Benchmark Datasets & Evaluation
Classification: Iris, Wine, Breast Cancer. Metric: Accuracy, F1.
Regression: Boston Housing, California Housing. Metric: MSE, MAE.
---
## Key Challenges & Limitations
### Overfitting
Unconstrained trees perfectly memorize training data. Prune or limit depth.
### Bias Toward High-Cardinality Features
Many splits → higher information gain. Balance via regularization.
---
## Hyperparameter Tuning
Grid search: max_depth \in {3, 5, 10\}, min_samples_split \in {2, 5, 10\}, min_samples_leaf \in {1, 2, 4\}.
---
## Real-World Applications & Case Studies
Healthcare: Diagnostic decision trees interpretable for physicians.
Finance: Loan approval rules encoded as tree paths.
---
## Integration with Other Methods
Tree + Ensemble → Random Forest, Gradient Boosting.
---
## Future Research Directions
Oblique trees (non-axis-aligned splits); uncertainty quantification via Bayesian trees.
---
## Summary & Key Takeaways
Decision trees recursively partition feature space via gain-maximizing splits, balancing interpretability with expressiveness.
Principles:
1. Greedy splitting maximizes information gain.
2. Gini and entropy measure node purity.
3. Tree depth controls bias-variance tradeoff.
4. Pruning reduces overfitting.
5. Feature importance via split contribution.
---
---
## Appendix: Practical Labs
### Lab 1: Decision Tree from Scratch
import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
class Node:
def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
self.feature = feature
self.threshold = threshold
self.left = left
self.right = right
self.value = value # Class value if leaf
class DecisionTree:
def __init__(self, max_depth=10):
self.max_depth = max_depth
self.tree = None
def gini(self, y):
_, counts = np.unique(y, return_counts=True)
p = counts / len(y)
return 1 - np.sum(p ** 2)
def build(self, X, y, depth=0):
if depth >= self.max_depth or len(np.unique(y)) == 1:
leaf_value = np.argmax(np.bincount(y))
return Node(value=leaf_value)
best_gain = -1
best_feature, best_threshold = None, None
for feature in range(X.shape[1]):
for threshold in np.unique(X[:, feature]):
left_idx = X[:, feature] <= threshold
right_idx = ~left_idx
if len(y[left_idx]) == 0 or len(y[right_idx]) == 0:
continue
gain = self.gini(y) - (len(y[left_idx])/len(y) * self.gini(y[left_idx]) +
len(y[right_idx])/len(y) * self.gini(y[right_idx]))
if gain > best_gain:
best_gain = gain
best_feature = feature
best_threshold = threshold
if best_feature is None:
leaf_value = np.argmax(np.bincount(y))
return Node(value=leaf_value)
left_idx = X[:, best_feature] <= best_threshold
left = self.build(X[left_idx], y[left_idx], depth + 1)
right = self.build(X[~left_idx], y[~left_idx], depth + 1)
return Node(feature=best_feature, threshold=best_threshold, left=left, right=right)
def fit(self, X, y):
self.tree = self.build(X, y)
return self
def predict_sample(self, x, node):
if node.value is not None:
return node.value
if x[node.feature] <= node.threshold:
return self.predict_sample(x, node.left)
return self.predict_sample(x, node.right)
def predict(self, X):
return np.array([self.predict_sample(x, self.tree) for x in X])
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
tree = DecisionTree(max_depth=5)
tree.fit(X_train, y_train)
y_pred = tree.predict(X_test)
accuracy = np.mean(y_pred == y_test)
print(f"Accuracy: {accuracy:.4f}")
assert accuracy > 0.7, "Should exceed baseline"
print("✓ Decision Tree from scratch working")
if __name__ == "__main__":
print("Lab 1: Decision Tree - PASSED")### Lab 2: Gini vs Entropy
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
tree_gini = DecisionTreeClassifier(criterion='gini', max_depth=5, random_state=42)
tree_entropy = DecisionTreeClassifier(criterion='entropy', max_depth=5, random_state=42)
tree_gini.fit(X_train, y_train)
tree_entropy.fit(X_train, y_train)
acc_gini = accuracy_score(y_test, tree_gini.predict(X_test))
acc_entropy = accuracy_score(y_test, tree_entropy.predict(X_test))
print(f"Gini: {acc_gini:.4f}, Entropy: {acc_entropy:.4f}")
assert acc_gini > 0.7 and acc_entropy > 0.7, "Both should be good"
print("✓ Gini vs Entropy working")
if __name__ == "__main__":
print("Lab 2: Gini vs Entropy - PASSED")### Lab 3: Feature Importance
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
iris = load_iris()
X, y = iris.data, iris.target
tree = DecisionTreeClassifier(max_depth=5, random_state=42)
tree.fit(X, y)
importances = tree.feature_importances_
feature_names = iris.feature_names
for name, imp in zip(feature_names, importances):
print(f"{name}: {imp:.4f}")
assert len(importances) == 4, "Should have 4 features"
assert abs(np.sum(importances) - 1.0) < 1e-6, "Importances should sum to 1"
print("✓ Feature importance working")
if __name__ == "__main__":
print("Lab 3: Feature Importance - PASSED")### Lab 4: Depth vs Overfitting
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
X, y = make_classification(n_samples=200, n_features=20, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
depths = range(1, 16)
train_accs = []
test_accs = []
for d in depths:
tree = DecisionTreeClassifier(max_depth=d, random_state=42)
tree.fit(X_train, y_train)
train_accs.append(accuracy_score(y_train, tree.predict(X_train)))
test_accs.append(accuracy_score(y_test, tree.predict(X_test)))
print(f"Shallow (d=2): train={train_accs[1]:.4f}, test={test_accs[1]:.4f}")
print(f"Deep (d=15): train={train_accs[-1]:.4f}, test={test_accs[-1]:.4f}")
assert train_accs[-1] >= train_accs[1], "Deeper tree should fit training better"
print("✓ Depth vs overfitting working")
if __name__ == "__main__":
print("Lab 4: Depth vs Overfitting - PASSED")