Decision Trees

A decision tree splits data with a sequence of questions. Each internal node tests one feature and sends the data down one of two branches; the leaves hold the final predictions. During training the tree chooses each question greedily — it picks the split that best separates the classes, measured by how much it reduces impurity (common measures are Gini impurity and entropy). It repeats this on each branch until the groups are pure enough or a depth limit is reached. Trees are popular because they are easy to read: you can follow the path and see exactly why a prediction was made. Their weakness is that a single deep tree tends to overfit, memorising the training data. The fix is to combine many trees: a random forest averages hundreds of trees trained on random subsets, and gradient boosting builds trees in sequence where each one corrects the last. These ensembles are among the strongest models for tabular data.

The classic algorithms differ mainly in how they choose splits. ID3 (1986) picks the split with the highest information gain, measured by entropy. C4.5 refined it with gain ratio, continuous attributes, and missing-value handling. CART — what scikit-learn implements today — uses Gini impurity for classification and variance reduction for regression, and always splits two ways. Beyond prediction: Isolation Forest turns the idea inside out for anomaly detection — outliers are the points that random recursive splits isolate quickest. Conditional inference trees choose splits with statistical tests, reducing bias toward features with many categories. Oblique trees split on combinations of features instead of one at a time, capturing diagonal boundaries a normal tree must staircase around.