Forêts aléatoires
L'idée peut paraître incongrue mais imaginons ceci : si nous ne savons pas résoudre un problème sur un groupe de données, alors pourquoi ne pas tester aléatoirement sur plusieurs sous-groupes et voir si un résultat se dégage ?
Arbre décisionnel
Nous allons créer des groupes d'exemples différents depuis notre ensemble de départ.
Par exemple, un premier groupe qui ne contient que les 15 premières caractéristiques et les 50000 premiers exemples, ou alors un autre groupe, avec seulement 3 caractéristiques et tous les exemples etc.
Pour cela nous allons utiliser et comparer les résultats en utilisant un même type de classificateur : des arbres décisionnels.
Regarder l'image plus haut, tirée d'un fameux jeu de société et choisissez un personnage. Si maintenant, nous devons essayer le deviner, nous allons poser des questions du type "Est-ce un homme", "A-t-il une moustache ?". Et bien tout ceci correspond exactement à un arbre décisionnel. On décide du nom du personnage (le label ou le nom de la classe) en fonction de son apparence (les caractéristiques). On voit que le schéma ci-dessous à la forme d'un arbre (si on le tourne à 90 degré), d'où le nom arbre décisionnel
Construire un arbre
La construction d'un arbre se fait de la même manière que lorsque l'on joue au jeu pour trouver les personnages. On cherche d'abord quelle est la caractéristique qui découpe le mieux (c'est à dire en 2 si possible), notre ensemble. Par exemple, mieux vaut poser comme première question "Est-ce un homme ou une femme" afin d'éliminer la moitié des personnages plutôt que prendre le risque de demander "A-t-il les cheveux blancs" et de n'en éliminer que 3. Puis à chaque étape, en traitant les oui et les non, on recherche de nouveau la meilleure caractéristique et on découpe.
En réalité, on peut choisir à chaque étape plus d'une caractéristique. Leo Breiman et Adele Cutler, les inventeurs des Random Forest préconisent de choisir ½√m, √m, ou 2√m où m est le nombre total de caractéristiques disponibles.
Bagging - Une forêt = beaucoup d'arbres
Nous allons donc créer une forêt, soit beaucoup d'arbres. Chaque arbre utilisera donc un ensemble d'exemples différents. Et nous aurons tellement d'arbres qu'on pourra se dire qu'on va voir émerger la bonne solution, en prenant comme solution la moyenne des résultats ou le résultat majoritaire.
Mais en fait, on ne va pas choisir ces ensembles d'exemples, ou échantillon, de manière aléatoire, nous allons utiliser une technique bien précise : le bagging