Decision Trees
A decision tree answers a prediction by asking one feature question at a time, so the real questions are how to choose each split and when to stop. The page starts with split criteria and visualizing forests, then CART with SSE, Gini, early stopping, and pruning, then KD-trees for nearest neighbours, and ends with the forest variants built from trees: random forests and extremely randomized trees.
The same notes are in Hoeffding tree, IMBALANCED DATASETS, Interview questions, and Unbalanced labels.
The split criterion is the first choice, and it matters most when the classes are imbalanced. Evgeni Dubov's post on classifying imbalanced data starts from the usual sklearn RandomForestClassifier setup and proposes Using hellinger distance to split supervised datasets, instead of gini and entropy. Claims better results. Once a forest is trained, it helps to look inside it. Visualize decision forests: forests is Will Koehrsen's guide to visualizing a decision tree from a random forest in Python using scikit-learn.
CART TREES
The classical tree algorithm, known by its more modern name CART, is where the split math lives; the heading link is Jason Brownlee's MachineLearningMastery post on classification and regression trees. The same notes are in REGRESSION ALGORITHMS and Tutorials.
The post explains about the similarities and how to measure. which is the best split? based on SSE and GINI (good info about gini here). For classification the Gini cost function is used which provides an indication of how “pure” the leaf nodes are (how mixed the training data assigned to each node is).
Gini = sum(pk * (1 – pk))
A tree grown until every leaf is pure memorizes the data, so two controls follow. Early stop — 1 sample per node is overfitting, 5-10 are good. Pruning — evaluate what happens if the lead nodes are removed, if there is a big drop, we need it.
KDTREE
The same split-by-feature idea also organizes space for search rather than prediction. Victor Lavrenko's KD tree algorithm: how it works explains it: Similar to a binary search tree, just by using the median and selecting a feature randomly for each level. His kNN.15 K-d tree algorithm lecture shows what it is for: Used to find nearest neighbours. The Quora question on what a kd-tree is used for lists Many applications of using KD tree, reduce color space, Database key search, etc.
RANDOM FOREST
Back to prediction: one tree overfits, so a forest averages many, and the forest can also be used as a feature transform. The same notes are in Ensembles.
scikit-learn's feature transformations with ensembles of trees fits an ensemble first, then trains a linear model on the resulting features: Using an ensemble of trees to create a high dimensional and sparse representation of the data and classifying using a linear classifier
Imbalance comes back here too. How do deal with imbalanced data in Random-forest — the Berkeley paper proposes two ways and shows both improve prediction accuracy:
One is based on cost sensitive learning.
Other is based on a sampling technique
EXTRA TREES
Random forests still search for the best split; extremely randomized trees go one step further and randomize the split itself. The same notes are in Ensembles.
A comparison between random forest and extra trees used to be linked here; the original article address is kept at the end of the page. Its figure caption reads:
Fig. 1: Comparison of random forests and extra trees in presence of irrelevant predictors. In blue are presented the results from the random forest and red for the extra trees. The results are quite striking: Extra Trees perform consistently better when there are a few relevant predictors and many noisy ones
To see why, the Difference between RF and ET thread states that random forest splits are deterministic, while in extremely randomized trees the next split is the best among random uniform splits, and asks what impact that has. Differences #2 is the same question for RandomForestClassifier vs ExtraTreesClassifier in scikit-learn, read against the Geurts, Ernst, and Wehenkel paper "Extremely randomized trees".
To close, Will Koehrsen's post, a helpful utility for understanding your model, is the place to visualize decision forests: https://towardsdatascience.com/how-to-visualize-a-decision-tree-from-a-random-forest-in-python-using-scikit-learn-38ad2d75f21c
Deprecated links
These links and images no longer work. The original wording is kept here. A same-resource copy, when one was checked, is used above.
Visualize decision trees. This address no longer opens: https://towardsdatascience.com/interactive-visualization-of-decision-trees-with-jupyter-widgets-ca15dd312084
A comparison between random forest and extra trees. This address no longer opens: https://www.thekerneltrip.com/statistics/random-forest-vs-extra-tree/
Last updated
Was this helpful?