Random forest

Random forests blev introduceret af Leo Breiman (2001, Machine Learning 45(1)). De kombinerer bagging (bootstrap aggregating, Breiman 1996), hvor hvert træ trænes på en bootstrapstikprøve trukket med tilbagelægning, med tilfældig udvælgelse af features: Ved hver opdeling overvejes kun en tilfældig delmængde af features. Den anden kilde til tilfældighed dekorrelerer træerne, og fordi variansen af et gennemsnit falder med korrelationen mellem dets medlemmer, har ensemblet langt lavere varians end noget enkelt dybt træ, samtidig med at den lave bias bevares.

De vigtigste hyperparametre er antallet af træer, hvor flere aldrig giver dårligere nøjagtighed, men koster tid; max_features, størrelsen af den tilfældige delmængde, hvor sqrt(p) er en almindelig standard ved klassifikation og alle features er scikit-learns standard ved regression; samt træernes dybde eller mindste bladstørrelse. Breimans oprindelige metode lader hvert træ stemme; scikit-learn tager i stedet gennemsnittet af træernes forudsagte klassesandsynligheder.

Da hver bootstrapstikprøve udelader omkring en tredjedel af rækkerne (1 - 1/e, ca. 36,8 procent), har hvert træ out-of-bag-eksempler, det aldrig har set. Forudsiges hver række kun med de træer, der ikke er trænet på den, får man out-of-bag-fejlen, et næsten gratis skøn over generaliseringsfejlen. Skove giver også feature-vigtigheder, enten gennemsnitligt fald i urenhed (hurtigt, men skævt mod features med mange værdier) eller permutationsvigtighed.

Random forests er robuste, lader sig let parallelisere og kræver lidt tuning, hvilket gør dem til en stærk målestok for data i tabeller. Veltunet gradient boosting slår dem som regel på nøjagtighed, og som alle træensembler kan de ikke ekstrapolere ud over det interval af målværdier, de så under træningen. Extremely randomised trees (Geurts m.fl., 2006) fører idéen videre ved også at vælge opdelingstærsklerne tilfældigt.