Les forêts aléatoires

# Les forêts aléatoires
## 🌳🎄🌴🌱🌵 alias random forests
### Cyrille Conord <a href="mailto:cyrille.conord@univ-st-etienne.fr">cyrille.conord@univ-st-etienne.fr</a> 
### 2019/02/27 (màj: 2019-03-25)

---

# Introduction

---

# Idée de base

]

---

.font300.white[Arbres de décision]

???

Image credit: [giphy](https://giphy.com/gifs/tree-U85Z0lxOwDoys?utm_source=media-link&utm_medium=landing&utm_campaign=Media%20Links&utm_term=)

---

# Principe

---

# Un modèle fondé sur .red[un jeu de règles]

---

# Terminologie

---
# Faire pousser un arbre

### Algorithmes

- ID3 
- C4.5
- CART (Classification And Regression Tree)
- CHAID
- MARS
- Conditional Inference Trees
- ...

]

---

# Faire pousser un arbre

### Algorithmes

- ID3
- C4.5
- .bold.blue[CART (Classification And Regression Tree)]
- CHAID
- MARS
- Conditional Inference Trees
- ...

]

### Qu'a donc CART dans son caddie ?

- Classification and regression trees
- Variable continues et catégorielles
- Partitionnement
 - Divisif
 - Divisions binaires (conduit souvent à de grands arbres)
 - Arbres de régression: réduction de la variance
 - Arbres de classification: critère de pureté de Gini
- Elagage possible selon la complexité 
- [(Breiman, 1984)](https://www.taylorfrancis.com/books/9781351460491)

]

---

# Trouver le meilleur partitionnement .red[binaire]

.center.font130.bold[Arbre de régression]

]

.center.font130.bold[Arbre de classification]

]

---

# Trouver le meilleur partitionnement .red[binaire]

.pull-left[
 
- __Variable numérique__: partition numérique minimisant une fonction de coût
 
- __Variable binaire__: partition catégorielle minimisant une fonction de coût
 
- __Variable multi-classes__: Ordonner les classes par la moyenne de la variable cible (régr.) ou par la proportion dans les classes (classif.) et choisir la partition minimisant une fonction de coût ([Voir Elements of Statistical Learning, section 9.2.4](https://web.stanford.edu/~hastie/ElemStatLearn/)).

]

]

---

# Jusqu'où faire pousser un arbre ?

Disons que l'on dispose des données suivantes issues de la fonction sous-jacente .blue["réelle"]

le code

```r
set.seed(1112) # pour la reproductibilité
df <- tibble::tibble(
 x = seq(from = 0, to = 2 * pi, length = 500),
 y = sin(x) + rnorm(length(x), sd = 0.5),
 truth = sin(x)
)
library(rpart)
ctrl <- list(cp = 0, minbucket = 5, maxdepth = 1)
fit <- rpart(y ~ x, data = df, control = ctrl)
df %>%
 mutate(pred = predict(fit, df)) %>%
 ggplot(aes(x, y)) +
 geom_point(alpha = .3, size = 2) +
 geom_line(aes(x, y = truth), color = "blue", size = 1)
```

---

# Jusqu'où faire pousser un arbre ?

Disons que l'on dispose des données suivantes issues de la fonction sous-jacente .blue["réelle"]

---

# Profondeur = 1 (.red[souche] de décision <img src="images/stump.png" style="height:1em; width:auto; "/>)

```
## 
## Model formula:
## y ~ x
## 
## Fitted party:
## [1] root
## | [2] x >= 3.07863: -0.665 (n = 255, err = 95.5)
## | [3] x < 3.07863: 0.640 (n = 245, err = 75.9)
## 
## Number of inner nodes: 1
## Number of terminal nodes: 2
```

]

]
]

---

# Profondeur = 3 <img src="images/small-tree-icon.png" style="height:1em; width:auto; "/>

```
## 
## Model formula:
## y ~ x
## 
## Fitted party:
## [1] root
## | [2] x >= 3.07863
## | | [3] x >= 3.65785
## | | | [4] x < 5.53399: -0.948 (n = 149, err = 40.0)
## | | | [5] x >= 5.53399: -0.316 (n = 60, err = 15.6)
## | | [6] x < 3.65785
## | | | [7] x < 3.20455: -0.476 (n = 10, err = 0.9)
## | | | [8] x >= 3.20455: -0.130 (n = 36, err = 9.0)
## | [9] x < 3.07863
## | | [10] x < 0.52255
## | | | [11] x < 0.28331: 0.142 (n = 23, err = 4.8)
## | | | [12] x >= 0.28331: 0.390 (n = 19, err = 5.1)
## | | [13] x >= 0.52255
## | | | [14] x >= 2.26018: 0.440 (n = 65, err = 13.7)
## | | | [15] x < 2.26018: 0.852 (n = 138, err = 36.6)
## 
## Number of inner nodes: 7
## Number of terminal nodes: 8
```

]

]
]

---

# Profondeur = 20 (.red[arbre complexe] <img src="images/large-tree-icon.png" style="height:1em; width:auto; "/>)

]

]
]

---

# Frontières de décision

---

# Frontières de décision avec .red[deux variables prédictrices]

### Problème de classification: jeu de données Iris

]

---

# Frontières de décision avec .red[deux variables prédictrices]

### Problème de classification: jeu de données Iris

]

### Arbre de Classification

]

---

# Un arbre en action

http://www.r2d3.us/visual-intro-to-machine-learning-part-1/

---

# Le pour, le contre...

### Forces

- .green[Les arbres courts sont faciles à interpréter]

- .green[Les arbres s'adaptent bien à de grands _N_] (rapidement) = "scalabilité"

- .green[Possibilité d'utiliser des données de tous types] (i.e., requière peu ou pas de "pre-processing")

- .green[Sélection des variables automatique]

- .green[Tolérance aux données manquantes]

- .green[Totalement non-paramètrique]

]

### Faiblesses

- .red[Les grands arbres sont plus difficiles à interpréter]

- .red[Chaque branchaison *"split"* dépend des précédentes] (détecter les interactions entre variables ; modèle additif )

- .red[Les arbres se comportent comme des fonctions étagées] (i.e., partitions binaires)

- .red[Un arbre seul est un faible prédicteur]

- .red[Un arbre seul montre une grande variance] (sur-apprentissage des données)

]

---

# Sur-apprentissage ?

---

# Minimiser le sur-apprentissage / overfitting

.font110[Il faur équilibrer la longueur(profondeur) et la complexité de l'arbre pour .bold[généraliser / extrapoler] à des données inédites]

2 stratégies:

* Arrêter la croissance de l'arbre 
   * limiter la profondeur
   * limiter la taille des noeuds

* Elaguer

]

]

---

--
.font300.white[Le Baggy !???!]

--
.font300.black[Non, le Bagging !!]

???

Image credit: [LeMonde.fr](http://s1.lemde.fr/image/2013/03/28/534x0/3149306_5_021a_illustration_be6072959b8bf65fd0345fa812999817.jpg)

---

# Le problème avec les arbres pris isoléments

]

]

---

# .red[B]ootstrap .red[Agg]regat.red[ing]

1. Echantillonner des cas avec remplacement ("bootstraper" les données d'apprentissage)

2. .white[Calculer un arbre sur-dimensionné sur les données recomposées]

3. .white[Moyenner les prédictions]

]

]

---

# .red[B]ootstrap .red[Agg]regat.red[ing]

1. .opacity[.grey[Echantillonner des cas avec remplacement ("bootstraper" les données d'apprentissage)]]

2. .white[Calculer un arbre sur-dimensionné sur les données recomposées]

3. .white[Moyenner les prédictions]

]

]

---

# .red[B]ootstrap .red[Agg]regat.red[ing]

1. .opacity[.grey[Echantillonner des cas avec remplacement ("bootstraper" les données d'apprentissage)]]

2. Calculer un arbre sur-dimensionné sur les données recomposées

3. .white[Moyenner les prédictions]

]

]

---

# .red[B]ootstrap .red[Agg]regat.red[ing]

1. .opacity[.grey[Sample records with replacement (aka "bootstrap" the training data)]]

2. .opacity[.grey[Calculer un arbre "sur-dimensionné" sur les données recomposées]]

3. Moyenner les prédictions

]

]

---

# .red[B]ootstrap .red[Agg]regat.red[ing]

.font120.bold[Plus on ajoute d'arbres...]

![](images/unnamed-chunk-30-1.gif)

]

.font120.bold[plus l'erreur de prédiction décroît]

![](images/unnamed-chunk-31-1.gif)

]
---

# Cependant, .red[il reste un problème]

.center[.content-box-gray[.bold[ce qui empêche justement le bagging de réduire la variance des valeurs prédites]]]

---

class: clear, center, middle
background-image: url(images/oil-palm-plantation-vl.jpg)

background-size: cover

.font300.white[Pb des arbres qui se ressemblent...]
---
class: clear, center, middle

.font300.white[Random Forests]

---
# Principe

### Randomisation de la variable de partitionnement

* .font120[Un processus similaire au bagging mais... ]

]

]

---
# Principe

### Randomisation de la variable de partitionnement

* Un processus similaire au bagging mais...

* à chaque partition, la variable à choisir l'est dans .blue[un sous-jeu limité *m* parmi les *p* variables]
   - arbres de régression: `\(m = \frac{p}{3}\)`
   - arbres de classification: `\(m = \sqrt{p}\)` 
   - `\(m\)` is commonly referred to as .blue[___mtry___] .white[

* Le Bagging introduit l'aléatoire dans les rangées du dataset

* Random forest introduit l'aléatoire dans les rangées et les colonnes du dataset
]
]

]

---

# Bagging contre Random Forest

* Un processus similaire au bagging mais...

* à chaque partition, la variable est tirée dans .blue[un sous-jeu *m* parmi les *p* variables]
]
* Bagging introduit .red[l'aléatoire] dans les rangées du dataset

* Random forest introduit .red[l'aléatoire] dans rangées *et* colonnes du dataset
]

![](images/unnamed-chunk-35-1.gif)

]

.center[.bold[.green[La combinaison produit un jeu d'arbres plus diversifié qui réduit encore l'erreur de prédiction.]]]

---

# Out-of-bag

.pull-left[
.font75[
* Pour un N suffisamment grand, 63.21% des observations sont incluses dans un échantillon bootstrappé

* En gros, 36.79% des observations ne sont pas utilisées pour construire un arbre donné

* Ces observations sont dites .red[out-of-bag (OOB)] et peuvent être utilisées pur une évaluation efficace des performances du modèle (.bold[= cross-validation (validation croisée) non structurée mais gratuite])
]

.font75[.blue[Au doigt mouillé]:
   - Pour un N petit, OOB est moins fiable que la validation
   - N augmentant, OOB devient plus efficace qu'une CV à *k-feuillets*
   - Quand le nombre d'arbres est 3x le nombre pour que l'erreur de la forêt se stabilise, alors l'erreur estimée par OOB error est équivalente à une erreur de validation leave-one-out.
]]

![](images/unnamed-chunk-35-1.gif)

]

---

# Applications ?

* __Cartographie de biotopes__

]

]

---
# Applications ?
  
.pull-left[
    
* __Cartographie de biotopes__
    
]

.pull-right[
  
* Projet CarHAB:  Cartographie des Habitats (Stratégie Nationale pour la Biodiversité)
* MESR, IGN, MNHN, AFB, IRSTEA, URennes, UJM
* Réseau des CBN: CBN Massif Central, CBN Bassin Parisien, CBN Bailleul, CBN Aalpin, CBN Brest, CBN Corse, CBN SE Atlantique
* Géocomputation (reprodutible)
* Ex: Loiret & Cher: un tableau de données avec 43 millions de lignes
  
]
  
---

# Applications ?

* Cartographie de biotopes
* Analyse de __données compositionnelles en écologie-chimique__

]

![un outil dans l'arsenal](images/chemo_eco_bruckner2017_arsenal.png)
.center[
.font80[
*...[RF] is robust against almost all violations  of  common  statistical  assumptions,  needs  notransformation and also provides an additional graphicalMDS output based on the classification results.*
]
]
]

---

# Applications ?

* Cartographie de biotopes
* Analyse de données compositionnelles en écologie-chimique
* Marqueurs sous sélection en génétique des populations
* Classement des données de RNA-Seq
* ...

]

![un outil dans l'arsenal](images/chemo_eco_bruckner2017_arsenal.png)

.font80[
*...[RF] is robust against almost all violations  of  common  statistical  assumptions,  needs  notransformation and also provides an additional graphicalMDS output based on the classification results.*
]
]

---

# Les deux cultures

---

# Breiman 2001

![](images/blackbox01.png)

]
.pull-right[

Prédiction / Information

]

![](images/blackbox02.png)

]
.pull-right[

Validation: oui / non, goodness-of-fit & examen des résidus

]

* ![](images/blackbox03.png)

]
.pull-right[
* Validation: par précision du modèle (succès)
]

---

# Un algo pour tous les problèmes ?

* 179 classifieurs
* 17 familles d'algorithmes
* 121 jeux de données (UCI database)

]

.bold[
.blue[
*The random forest is clearly the best family of classifiers (3 out of 5 bests classifiers are RF),followed by SVM (4 classifiers in the top-10), neural networks and boosting ensembles (5and 3 members in the top-20, respectively)*
]
]

---

# Ensemblisme contre Rasoir d'Ockham ?
## Wisdom of crowds

Galton et l'estimation du poids du boeuf...

Epicure et son principe des explication multiples: *"si plus d'une théorie est en accord avec les données, alors il faut toutes les garder"*

Si plusieurs explications sont en accord, alors il peut être possible d'arriver à un plus grand niveau de précision en les utilisant __conjointement__

Cf méthodes de combinaisons de décision:
* bagging
* boosting
* ...

Nouveaux modèles de démocratie participative ???

---

# Penser ces choses-là en français ?

![](images/Datafranca-logo.png)

]

---

# J'ai pillé

* Bradley Boehmke bradleyboehmke.github.io grâce au __code__ de sa présentation __reproductible__ https://bradleyboehmke.github.io/random-forest-training/