Thread by @ObjectifDataSci

1. Salut les copains

Aujourd'hui on va parler d'un modèle tellement important dans le Machine Learning - Les arbres binaires !

On va voir comment ils sont construits et on va voir également une interprétation géométrique

#datascience #ia #MachineLearning

2. Pour commencer, les arbres binaires sont vieux comme le Machine Learning

C'est un type de modèle qui a constamment évolué, et qui est à la base de modèles phare du moment

Comme les #RandomForest, les #GradientBoosting comme #AdaBoost, #CatBoost, #XGBoost, ...

3. Promis, on verra chacun de ces modèles dans le détail dans des messages dédiés

4. Ce sont des modèles largement utilisés, et c'est pour cela qu'il faut comprendre précisément comment ils fonctionnent et comment ils sont construits

5. J'en profite pour rappeler également qu'ils peuvent être utilisés

> soit dans un mode classification (on affecte une classe à chaque point)

> soit dans un mode de régression (on prédit une valeur)

6. Bon commençons par un exemple d'arbre déjà construit.

Prenons par exemple ce cas très simple d'arbre pour la classification à deux variables, issu du jeu de données archi connu IRIS

7. Le dataset IRIS est un dataset permettant de classifier des types d'Iris en 3 groupes (Setosa, Versicolor et Virginica) en fonction de la taille de leur pétale par exemple

8. Voilà ce que pourrait donner un arbre déjà construit

9. On remarque que cet arbre commence par la question suivante :

est ce que la longueur du pétale est inférieure à 2.45 ?

Si oui, alors c'est une Sétosa et sinon, on repose une autre question derrière

10. On a donc une série de questions binaires (Oui ou non) qui débouchent chacune à

> soit un résultat (et dans ce cas, on a la classification)

> soit à une autre question

11. En langage datascientist

les questions sont des noeuds (Node)

les réponses sont des feuilles (Leafs)

Les noeuds et les feuilles sont reliés par des branches, c'est à dire par les décisions prises suite à la question posée

12. Ce qui est confortable avec ce modèle, c'est qu'il est parfaitement interprétable par un humain, qui peut tout de suite voir si le modèle est cohérent (pour peu que l'humain soit expert du domaine ...)

13. On parle alors de modèle d'algorithme "White Box", car ces résultats sont visibles et interprétables.

Les modèles "Black Box" sont les réseaux de neurones ou les random Forest par exemple, qui sont beaucoup moins facilement interprétables

14. La première chose que je voulais vous montrer concernant ce modèle, c'est qu'il est interprétable géométriquement.

15. Par exemple dans le cas donné, on peut représenter chaque noeud comme une portion du plan dans lequel on a placé nos échantillons de plantes.

Cela donnerait ce graphique

16. Les arbres binaires peuvent donc avoir une double interprétation

> sous forme d'arbre binaire

> sous forme géométrique, avec des régions spatiales définies pour chacune des catégories

17. Maintenant se pose LA question fondamentale

Comment l'algorithme fait pour déterminer à chaque noeud, quelle variable et quelle valeur prendre pour faire la séparation ?

La question ...

18. Dans notre cas, pour la première séparation, comment il sait que c'est le Petal Length et la valeur 2.45 qu'il faut utiliser ?

19. Ce qu'il faut bien saisir, c'est qu'à chaque question, le modèle va choisir la variable et sa valeur associée qui vont séparer le mieux possible les points dans chacune des catégories

20. Pour mesurer le résultat de la séparation, il faut voir comment se répartissent les catégories dans les 2 feuilles qui sont créées

Et déterminer si cette répartition est suffisamment discriminante

21. Pour cela on définit un indice de "pureté", qu'on appelle Gini, et qui dépend de la répartition des classes dans la feuille.

En gros, plus une classe sera prépondérante, meilleur sera l'indice Gini

22. Instant Math

Le Gini sera égal à

1 - la somme des proportions (pourcentage) au carré

Pas de panique, on va prendre des exemples

23. Premier exemple, en prenant une répartition de 100, 15 et 20 pour chacune des 3 catégories.

On trouve un Gini égal à 0,41

24. Deuxième exemple, en prenant une répartition de 40, 50 et 45, on trouve un Gini égal à 0,66

25. L'indice Gini du premier exemple étant inférieur au deuxième exemple, la première répartition est plus discriminante.

Ce qui évident quand on les regarde de près

26. Or, quand on fait une séparation, on a deux groupes, qui à chacun son indice.

Pour mesurer l'indice total, il faut faire la somme pondéré des indices

Plus il y a de cas, et plus l'indice comptera dans le résultat

27. Pour illustrer cette pondération, prenons deux exemples

28.

29. La deuxième répartition est plus discriminante car la feuille qui a le plus d'éléments est celle qui a un meilleur Gini

30. Maintenant que nous savons comparer le caractère discriminant d'une séparation, revenons à notre question initiale.

Comment l'algorithme fait pour déterminer à chaque noeud, quelle variable et quelle valeur prendre pour faire la séparation ?

31. Et bien, c'est tout simple, il va TESTER TOUTES LES VALEURS DE TOUTES LES VARIABLES et choisir la meilleure séparation, celle qui fait la meilleure discrimination.

En langage formel, on dit que l'algorithme est "Greedy", en langage courant, on dit qu'il est bourrin !

32. Se pose ensuite une question, jusqu'où continuer ?

Car a priori, on peut continuer jusqu'à ce que chacune des feuilles ne contiennent plus qu'un élément.

33. Chacune des feuilles sera "parfaite", mais l'arbre sera long à construire et surtout, on sera dans un cas classique d'overfitting !

L'arbre aura appris "par coeur" ses données d'entraînement et ce n'est pas certain qu'il pourra bien généraliser

34. Dans les implémentations classiques, on peut dire à l'algo de s'arrêter si on a atteint une certaine profondeur de l'arbre, où si chacune des feuilles ne contiennent plus qu'un nombre déterminé d'éléments

35. Une dernière petite chose

A la place de l'indice Gini, on peut utiliser également l'entropie H = -p*log(p) pour mesurer le caractère discriminant d'une séparation

Par contre les temps de calcul seront plus longs (à cause de la fonction logarithme)

36. Je vous ferai un tweet très prochainement pour vous parler ce cette mystérieuse formule de l'Entropie.

Il y a beaucoup de chose à dire sur elle.

37. A très vite !

Et n'hésitez pas à liker ou partager si cela vous a plu !