Los árboles extremadamente aleatorios (Extra-Trees o Extremely Randomized Trees) fueron propuesto por los investigadores Pierre Geurts, Damien Ernst y Louis Wehenkel en 2006. Este algoritmo lleva la aleatoriedad de Random Forest un paso más allá: Además de considerar un subconjunto de las características predictivas para cada uno de los árboles a crear, a la hora de escoger una característica y un valor de corte (threshold) para dividir cada nodo, en lugar de escoger el threshold que mejor divida cada característica (y escoger la característica y valor de corte que minimice el criterio de impureza), se genera un valor de corte aleatorio para cada característica planteada, escogiéndose como regla de división el mejor de ellos. Otra diferencia con Random Forest es que las muestras con las que se entrena cada aprendiz se escogen sin reemplazo.
Scikit-learn implementa este algoritmo de clasificación en la clase sklearn.ensemble.ExtraTreesClassifier.
