###### tags: `umons 2022-23` `classification` `association`

# Bases de données II : Classification & Association

## Table des matières:
[toc]

# Qu'est-ce que la classification ?

Méthode qui permet de prédire des attributs non-numériques (appelés classes).

> [name=Livius A] Que veux-tu dire par non-numérique? la plupart des attributs sont discrets mais certains peuvent contenir des valeurs continues.

La classification est la tâche d'apprentissage d'une fonction *f* qui fait correspondre à chaque attribut X l'une des étiquettes de classe prédéfinies Y.

<p float="left">
<img src=https://i.imgur.com/gHOGKV3.png
width="400" />
</p>

## Methodologie
1. Créer un seul ensemble S d'exemples, avec les classes connues.
2. Diviser l'ensemble S en deux parties (apprentissage A et test T).
3. S'appuyer sur A pour construire un modèle prédictif (appelé classificateur dans le cas d'une classification)
4. Vérifier que le modèle colle bien à T
5. Utiliser le modèle pour prédire de nouveaux cas.

# Situez chaque terme dans le cursus et expliquez de façon succincte mais précise.


## Generalization error
- Terme abordé dans le chapitre de la classification.
- C'est une mesure de précision qui mesure la capacité d'un modèle à pouvoir effectuer des prédictions robustes sur les nouvelles données (ensemble de test).

## Erreur d'apprentissage
On entraîne l'algorithme d'apprentissage avec un ensemble d'entrainement et ensuite on teste avec le même ensemble de données. Le problème est que ce que nous calculons est biaisé, car l'algorithme est devenu spécialiste de l'ensemble de l'entrainement. L'erreur calculée ne dit absolument rien des capacités que l'algorithme aura sur les nouvelles données.

## Accuracy (Fiabilité ou Exactitude)
- Compromis entre Recall et Précision, l'Accuracy est une métrique de performance qui montre la fiabilité du résultat.

Accuracy = $\frac{VP+VN}{VP+FP+FN+VN}$

<p float="left">
<img src=https://i.imgur.com/5piiTkO.png
width="400" />
</p>

## Recall
- Terme abordé dans le chapitre de la classification.
- Il permet de calculer le rapport entre les échantillons positifs correctement classés comme positifs et le nombre total d'échantillons positif.
- C'est le nombre de positifs bien prédit (VP) divisé par l'essemble des positifs(VP+FN)
- Il permet de savoir le ratio de positifs bien prédit par notre modèle.

Recall = $\frac{VP}{VP+FN}$

- Plus il est élevé, plus le modèle de ML maximise les VP
- Cela ne veut pas dire que le modèle ne se trompe pas, quand le recall est haut, cela veut plûtot dire qu'il ne ratera aucun positif. Néanmois cela ne donne aucune information sur sa qualité de prédiction sur les négatifs.

E.g. Dans toutes les femmes qui sont réellement enceintes, combien ont étés correctement prédites enceintes.

## Précision
- Terme abordé dans la classification
- Elle permet de connaître le nombre de prédictions positives bien effectuées.
- C'est le nombre de positifs bien prédits (VP) divisé par l'ensemble des positifs prédits (VP+FP)

Précision = $\frac{VP}{VP+FP}$

- Plus elle est élevée, plus le modèle minimise le nombre de FP.
- Quand la précision est haute, cela veut dire que la majorité des prédictions positives du modèle sont des positifs bien prédit.

E.g. Dans toutes les femmes prédites enceinte, combien le sont réelement.

<p float="left">
<img src=https://i.imgur.com/Tno0qAA.png
width="300" />
</p>

**Exemple:**

On veut avoir tous les articles qui parlent de Tennis et uniquement les articles qui parlent de Tennis.

On commence par construire une table avec pour chaque ligne un article.

Pour chaque ligne on va chercher des mots clé $A_1, A_2,...,A_n$

Avec $A_1$ = Nadal, $A_2$ = Goffin, etc.

| $A_1$ | $A_2$ | ... | C |
| -------- | -------- | -------- | -------- |
| 1 | 0 | ... | no |
| 0 | 1 | ... | no |
| 1 | 1 | ... | yes |

Si on a Nadal et Goffin on peut dire "yes" c'est du Tennis sinon c'est "no"

Pour ne pas rater des articles sur le Tennis, on s'aide de la mesure de Recall:

$\frac{TP}{TP+FN}$

Mais on risque

## F1 Score (ou F-measure)
- Permet d'effectuer une bonne évaluation de la performance du modèle

F1 Score = $2*$$\frac{recall*précsision}{recall+précision}$

- Plus le F1 Score est élevé, le plus le modèle est performant

## TPR ou True Positif Rate
Le rapport de vrais positifs (TP rate ou sensitivity) qui mesure la proportion de cas positifs correctement classés parmi tous les cas positifs réels.

## TNR ou True Negative Rate ou Spécificité

## FPR ou False Positif Rate
Le rapport de faux positifs (FP rate ou specificity) qui mesure la proportion de cas négatifs correctement classés parmi tous les cas négatifs réels.

## Overfitting
Le sur-apprentissage, trop collé aux données d’entrainement. Bonne performance sur les données d’apprentisssage et mauvaise généralisation. (haute variance mais biais faible)

- Erreur de généralisation moins bonne et erreur d'apprentissage plus élevée.
- Lorsque l'arbre commence à grandir son taux d'erreur de test commence à augmenter même si son taux d'erreur de formation continue à diminuer, c'est ce qu'on appelle overfitting.
- L'erreur d'apprentissage d'un modèle peut être diminuée en augmentant la complexité du modèle. Par exemple, les noeud feuilles peuvent être étendus jusqu'à ce que le modèle ajuste parfaitement les données d'apprentissage. Bien que l'erreur d'apprentissage pour un tel arbre complexe soit nulle, l'erreur de test peut être importante car l'arbre peut contenir des noeuds qui ajustent accidentellement certains des points de bruit dans les données d'apprentissage.

## Underfitting
Le sous-apprentissage, les données s’adapte mal aux données d’entrainement. Mauvaise performance sur les données d’apprentissage et mauvaise généralisation. ( Faible variance mais biais élevé)
- Taux d'erreur d'apprentissage et de test du modèle sont importants lorsque la taille est très petite.
- Se produit parce que le modèle n'a pas encore appris la vraie structure des données. Donc performances médiocres à la fois sur l'ensemble d'apprentissage et de test.

<p float="left">
<img src=https://i.imgur.com/GRYG5Be.png
width="300" />
<img src=https://i.imgur.com/lwJPqwr.png
width="300" />
</p>

## Gini
Permet de choisir les meilleures caractèristiques (attributs) pour former l'arbre.

Mesure utilisée pour choisir les bonnnes caractèristiques qui font les meilleurs noeuds qui forment l'arbre.

Permet de mesurer le degré d'impureté d'un noeud. 0 étant la pureté de la classification, c'est à dire tous les élements appartiennent à la même classe et 1 étant la distribution aléatoire des élements à travers différentes classe. La valeur 0.5 montre une distribution equilibrée des élements à travers les classes.

On va favoriser une pureté élevée, proche de 0, qui induira un gain d'information important entre le père et le nouveau noeud sélectionné.

## Entropy
Permet de choisir les meilleurs caractèristiques pour former l'arbre.
C'est une mesure de diversification des labels.
Varie de 0 à 1. Avec 1 le degré d'impureté maximal.

**Formule:**
<p float="left">
<img src=https://i.imgur.com/Djqcs2L.png
width="500" />
</p>

**Exemple de calcul:**
<p float="left">
<img src=https://i.imgur.com/mqigZTV.png
width="500" />
</p>

## Variable indépendante
Variable utilisée pour prédire la cible (Target).
Syn. Feature, predictor

## Erreur de classification
L'erreur de classement est un terme utilisé en statistiques lorsqu'un modèle de classification classe de façon erronée une observation dans une catégorie à laquelle elle n'appartient pas.

## Gain d'information
Classification.

Quand entropy est utilisé comme mesure d'impureté, c'est la différence entre entropy du parent et de l'enfant.
$\Delta$ = entropy(parent) - entropy(enfant)

L'attribut avec le gain d'information le plus élevé produira le meilleur fractionnement car il fait mieux le travail de classement des données d'apprentissage selon sa classification cible.

**Exemple de calcul du gain d'information avec Gini comme métrique d'impureté:**


$Gini_{parent}$ $= 1 - (\frac{7}{10})^2 - (\frac{3}{10})^2 = 0.420$

$Gini_{N_1}= 1 - (\frac{3}{3})^2 - (\frac{0}{3})^2 = 0$
$Gini_{N_2}= 1 - (\frac{4}{7})^2 - (\frac{3}{7})^2 = 0.49$
Moyenne pondérée $= (\frac{3}{10}) * 0 + (\frac{7}{10}) * 0.49 = 0.343$
gain d'information Home Owner $\Delta_{HO}$ $= 0.42 - 0.343 = 0.077$

tandis que

gain d'information Marital Status N°1 $\Delta_{MS1}$ $= 0.42 - 0.40 = 0.020$

En conclusion, les attributs qui séparent de la manière la plus pure sont "Home Owner" et "Marital Status n°3" car le gain d'information obtenu est le plus important.

## Gain ratio
Permet de mesurer la qualité du découpage d'un arbre et de contrer les caractèristiques indésirables car le gain d'information à tendance à favoriser les caractéristiques ayant un grand nombre d'enfants. Par exemple, les cas extremes, comme les ID.

**Formule:**
$Gain\ ratio = \frac{\Delta\ gain\ d'information}{entropy\ parent}$

<p float="left">
<img src=https://i.imgur.com/mgBt2La.png
width="400" />
</p>
<p float="left">
<img src=https://i.imgur.com/brYe72q.png
width="400" />
</p>

Le gain ratio permet donc d'éviter
* L'overfitting
* D'avoir un arbre avec un nombre de noeuds très grand (en largeur).
* risquant également de favoriser un attribut de type clé unique qui ne sert **pas** à classer les **nouvelles données**

**Exemple de calcul du Gain Ratio:**
<p float="left">
<img src=https://i.imgur.com/TjisEX3.png
width="400" />
</p>
<p float="left">
<img src=https://i.imgur.com/dltM4Ja.png
width="400" />
</p>

Le calcul de l'**entropie des enfants** ($Entropy_{(children)}$) est détaillée ci-dessous:

$Entropy_{child_1} = -\frac{6}{10}log_2{\frac{6}{10}} -\frac{4}{10}log_2{\frac{4}{10}} = 0.971$
$Entropy_{child_2} = -\frac{4}{10}log_2{\frac{4}{10}} -\frac{6}{10}log_2{\frac{6}{10}} = 0.971$
$\mu_{pondérée}\ Entropy_{children} = 0.971*\frac{10}{20}+ 0.971*\frac{10}{20} = 0.971$

## CART

Algorithme de création d'arbres décisionnels employant la stratégie des arbres **binaires** pour éviter l'overfitting et donc le problème des attributs à nombre d'enfants élevé.

## C4.5

Algorithme de création d'arbres décisionnels employant la mesure du **gain ratio**, utilisée désavantager les attributs qui produisent un grand nombre d'enfants.
Si un attribut produit un grand nombre d'enfants, sont *Split information* ($Entropy$) sera grand, ce qui réduira son gain ratio.

<p float="left">
<img src=https://i.imgur.com/s3K4saF.png
width="200" />
</p>

## ID3
Utilisé pour générer un arbre de décision grâce aux règles d'association. Souvent employé avec des variables nominales. Utilise le gain d'information pour créer son arbre. Donc possibilité d'avoir un problème en favorisant les variables prédictives ayant un grand nombre de valeurs.

Ses **défauts** sont:
* les attributs doivent être sélectionnés par l'utilisateur
* les attributs ne peuvent pas être numériques
* exemple:
* pas d'attributs de type clé primaire

Les étapes de l'algo incluent:
* répertorier les itemsets fréquents
* exemple: ACD
* énumérer les règles concernant cet itemset
* exemple:
* $AC \implies D$
* $AD \implies C$
* $CD \implies A$
* ...
* calculer la **Confiance** de chaque règle grâce à la formule $\frac{\sigma(itemset)}{\sigma(subset)}$
* exemples:
* $\frac{\sigma(ACD)}{\sigma(AC)} = \frac{2}{3}$
* $\frac{\sigma(ACD)}{\sigma(AD)} = \frac{2}{2}$
* $\frac{\sigma(ACD)}{\sigma(AA)} = \frac{2}{4}$
* garder les règles dont la confiance est **supérieure ou égale** au seuil de confiance
* exemple:
* <p float="center">
<img src=https://i.imgur.com/GAD6iUv.png
width="200" /> </p>

## Naïve Bayes
Se base sur la notion de **probabilité conditionnelle:**
$Pr(H|E) = \frac{Pr(H \wedge E)}{Pr(E)}$ (où H est l'hypothèse et E l'événement)

:::info
**Règle de Bayes:**
$Pr(H|E) = \frac{Pr(E|H)*Pr(H)}{Pr(E)}$
:::
*Rappel: si on simplifie on a que $Pr(H \wedge E) = Pr(E \wedge H)$*

### Règles de calcul des probabilités:

$Pr(A$&$B) \approx Pr(A) * Pr(B)$ uniquement si A et B sont indépendants (par exemple si A = être masculin et B = savoir nager, cela ne fonctionne pas si A = être masculin et B = être féminin)

La ==naïveté== de Naïve Bayes se trouve donc en la supposition suivante:
$Pr(E_1$&$E_2|H) \approx Pr(E_1 | H) * Pr(E_2 | H)$

**Exemple de calcul:**

<p float="left">
<img src=https://i.imgur.com/JqWiDQ5.png
width="400" />
</p>

Note: pour normaliser les probabilités et les obtenir sur 1 on calcule comme suit:

$Pr(H_n|E) = \frac{0.0206}{0.0206 + 0.0053} = 0.795$
$Pr(H_y|E) = \frac{0.0053}{0.0206 + 0.0053} = 0.205$

## Ordinal attribute

Un exemple d'attribut ordinal est la mention au BAC (bien, très bien), ou encore un attribut température (froid < tempéré < chaud)

Ses valeurs peuvent être classées dans un ordre naturel sans pour autant qu'il y ait une notion de distance qui les sépare.

## Attribut nominal
Les valeurs ne peuvent pas être classées de façon naturelle, comme par exemple une variable sexe ou couleur des yeux.

*Les variables ordinales et nominales sont des **variables qualitatives (catégorielles)**.*

## Cross validation

On utilise tous les blocs, à la fois dans l'ensemble d'entrainement et dans l'ensemble test, mais jamais simultanément.

## Leave-one-out

C'est un cas particulier de la validation croisée où on utilise 1 enregistrement à la fois pour le test et le reste pour l’apprentissage.

Cela permet de tester la capacité d'un modèle d'apprentissage automatique à prédire de nouvelles données.

<p float="left">
<img src=https://i.imgur.com/yoO68xH.png
width="600" />
</p>

L'avantage de cette méthode est de permettre l'utilisation de toutes les données pour l'apprentissage. Ceci est utile lorsque le jeu de données est petit.

Cependant cette méthode ne produit pas toujours des résultats satisfaisants et est particulièrement coûteuse car la procédure de validation croisée est répétée *N* fois.

## Arbre de décision

Un arbre de décision est une structure hiérarchique composée de noeuds et d'arêtes dirigées.

Un arbre de décision permet d'expliquer une variable cible à partir d'autres variables dites explicatives.

## Arbre de hachage (hash tree)

Dans l'algorithme APRIORI, les itemsets candidats sont séparés en groupes (appelés buckets) et stockés dans un arbre de hachage. Durant la phase de comptage du support, chaque itemset contenu dans les transactions sont hachés et stockés dans le bucket correspondant.
Au lieu de comparer chaque itemset de la transaction avec chaque itemset candidat, ce dernier est matché contre les itemsets du bucket correspondant.

La fonction de hachage dans l'exemple qui suit est:

$h(p) = (p-1)\ mod\ 3\ )$

Par exemple, les items candidats contenant 1, 4 ou 7 en début sont classés dans les noeuds feuilles de la branche de gauche.

Lorsque la transaction $t={1,2,3,5,6}$ arrive, les *support counts* des itemsets candidats sont mis à jour. **Si** un itemset candidat est un subset de la transaction, son *support count* est incrémenté.

**Rappel:** les 3-itemsets contenus dans *t* doivent commencer par 1, 2 ou 3. Les items 1, 2 et 3 sont donc hachés séparément, respectivement à gauche, au milieu et à droite.

<p float="left">
<img src=https://i.imgur.com/hKSExbS.png
width="500" />
</p>

Au second niveau de l'arbre, la transaction est hachée sur les items commençant par 12 et finissant donc par 3, par 5 ou par 6. Ce processus est répété jusqu'à ce qu'une feuille est atteinte.

<p float="left">
<img src=https://i.imgur.com/INkbYZC.png
width="500" />
</p>

Rappel des **niveaux** de l'arbre de hachage:
<p float="left">
<img src=https://i.imgur.com/EPgilBH.png
width="300" />
</p>

## Elagage (pruning)
Appliqué pour supprimer les données indésirables.

Exemple d'élagage dans **C4.5**:

<p float="left">
<img src=https://i.imgur.com/P3cFv68.png
width="300" />
</p>

![]()

Si on laisse le noeud "health plan condition" on a une borne inférieure de l'erreur $p_1 = \frac{6}{14}*0.528 + \frac{2}{14}*0.283 + \frac{6}{14}*0.528 = 0.493$

## Caractèristique
Aussi appelé attribut ou variable.

# Qu'est-ce qu'un entrepot de données?
- C'est une collection de données origanisée pour la prise de décision, possédant les caractèristiques suivant :
- Thématique et intégrée : LEs données OLTP sont souvent réparties sur plusieru applications (facturation, livraison, production, ...). LEs données seront intégrées dans un data warehouse autour d'un certain nombre de thèmes (client, produit, fournisseur, ...).
- Non volatile et historisée : LEs données, une fois dans l'entrepôt, ne sont plus supposées être modifiées. LEs données couvrent une certiane période de temps (par ex. dix ans) pour en extraire des tendances.

___
___

# Chapitre: Association

## Support count $\sigma$

Le support count d'un itemset (sous-ensemble) *X* se note $\sigma(X)$ est le nombre de transactions qui incluent *X*.

Exemple avec $\sigma(BC)$ dans la transaction suivante est de 3:

<p float="left">
<img src=https://i.imgur.com/QuFbkV1.png
width="300" />
</p>

## Support d'un règle

Le support d'une règle *$X \implies Y = \frac{\sigma(XY)}{N}$* (avec N, le nombre de transactions)

($* 100$ si on veut un pourcentage)

## Confiance d'un règle

La confiance de la règle *$X \implies Y = \frac{\sigma(XY)}{\sigma(X)}$*

## L'algorithme APRIORI

L'algorithme APRIORI relève deux défis:
* limiter le nombre de transactions lues
* limiter le nombre de lectures dans la base de données

On parcourir une seule fois la base de données et compter le support count.

Si on trouve que E n'est pas fréquent, on déduit que tout surensemble contenant E ne sera pas fréquent non plus car la logique veut que $\sigma(AE) \leq \sigma(E)$

Les support counts des candidats de taille incrémentale $C_i$ sont répertoriés et seuls les candidats fréquents $F_i$ ayant un support count $\sigma \geq$ au **seuil** prédéfini sont retenus.

La ==règle== qui facilite la génération des candidats est de vérifier que entre les candidats fréquents $F_{n}$ et les nouveaux $F_{n+1}$ les sous-ensembles précédents $XA$ et $XB$ avec une taille de $|X| = n$, ont un préfixe $X$ commun:

<p float="left">
<img src=https://i.imgur.com/CLLuzVL.png
width="100" />
</p>

Cette règle est exprimée comme suit:
:::info
Un sur ensemble ne peut être fréquent que si **tous** ses sous-ensembles sont fréquents.

Autrement dit: *"si à priori un candidat ne peut pas être fréquent, je ne vais même pas le générer"*
:::

C'est ce qu'on appelle la **Méthode $F_{(k-1)} * F_{(k-1)}$**:
:::info
*Procédure de génération de candidats de l'algorithme APRIORI qui fusionne une paire de (k-1)-itemsets fréquents uniquement si leurs k-2 items, classés par ordre lexicographique, sont identiques.*

k-1 ou X, est le préfixe d'un item fréquent.
:::

Dans l'exemple qui suit, les deux itemsets fréquents ($F_k$) sont XC et XD.
On peut donc prendre XCD comme candidat puisque par définition les sous-ensembles $(k+1)-2 = k-1$ des items $k$ sont fréquents. On prend donc le candidat $C_{k+1}$ $XCD$ comme candidat.
<p float="left">
<img src=https://i.imgur.com/3DGiZ8A.png
width="200" />
</p>

Le nombre de sous-ensembles traités est, avec cette méthode plus petit que si l'on parcourait toutes les possibilités, dans cette exemple: $2^6$.

Exemple de parcours APRIORI d'une transaction:
<p float="left">
<img src=https://i.imgur.com/SUIP8zf.png
width="400" />
</p>

Le graphique des frequent itemsets en fonction de la taille des

Ce qu'on appelle élagage dans APRIORI c'est le fait d'éliminer les surensembles candidats potentiels dont les sous-ensembles ne sont pas fréquents.
<p float="left">
<img src=https://i.imgur.com/lITMRog.png
width="400" />
</p>

Ce type de treillis de taille N aura plus de chances d'être large au niveau N/2. $\binom{N}{\frac{N}{2}}$ ce qui signifie ($\frac{N}{2}$ parmi $N$).
Dans le cas de la figure 6.4, le treillis sera à son maximum au niveau $k = 2$ et $k = 3$ car $N=5$
> cf. formule des sous-ensembles de taille $k$ possibles dans un ensemble de taille $N$
> $\frac{N}{k}$ = $\frac{n!}{k!(n-k)!}$, k est maximal lorsque $k = \frac{N}{2}$

Autre exemple du phénomène:
<p float="left">
<img src=https://i.imgur.com/pMB4hh9.png
width="400" />
</p>

## ROC curve (Receiver Operating Characteristic curve)

La forme d'une courbe ROC suggère la capacité d'un modèle de classification binaire à séparer les classes positives des classes négatives.

Un modèle qui sépare parfaitement les classes négatives des classes positives est représenté comme suit:


Le pire cas est un modèle qui prédit les classes de manière aléatoire, sa représentation graphique ROC a la forme de la ligne en pointillés ci-dessous:


## AUC ou Area Under Curve

L'AUC (aire sous la courbe) est une métrique utilisée pour évaluer les systèmes de classification binaire en comparant le taux de vrais positifs et le taux de faux positifs. Il va de 0 à 1, avec une valeur de 1 indiquant un classificateur parfait et une valeur de 0,5 indiquant un classificateur aléatoire ou inutile.

AUC résume les performances d'un classificateur par une seule mesure: l'aire sous la courbe ROC.


* le point good a comme valeur ° et 1, ce qui signifie que $0\leq AUC \leq 1$
* le point perverse, qui est pire que les opints sur la diagolane chance, a un AUC $\leq$ 0.5
* Tout point sur la diagonale chance a un AUC = 0.5
* Maximiser AUC signifie maximiser TPR-FPR
* la ligne chance (aléatoire) signifie que TPR - FPR = 0
* Isocost signifie que TPR-FPR = k. C'est une igne parallèle à la diagonale chance et elle a une valeur AUC identique en chaque point, car chaque triangle formé sur la diagonale chance donne une surface identique. Donc les modèles sont identiques mais avec des valeurs TPR et FPR différentes.

**Algorithme AUC:**

L'AUC mesure la performance d'un classificateur binaire en comparant le taux de vrais et faux positifs à différents seuils de classification. Sa valeur va de 0 à 1, avec une valeur de 1 indiquant un classificateur parfait et une valeur de 0,5 indiquant un classificateur aléatoire ou inutile. L'AUC est souvent utilisé avec d'autres métriques de performance pour évaluer un classificateur, en particulier lorsque les classes sont déséquilibrées.

___

# Examen 2016
## Question 2
Une faiblesse de l’algorithme ID3 est que celui-ci a tendance à favoriser des attributs avec un grand nombre de valeurs distinctes. Comparer, par exemple, l’attribut Gendre avec deux valeurs (Femme et Homme) et l’attribut Revenue avec dix-neuf valeurs [10, 20], [20, 30],. . ., [190, 200]. L’algorithme C4.5 utilise le gain ratio pour faire face à cette faiblesse.
### 1. Expliquez plus en détail l’origine de cette faiblesse de ID3.
ID3 utilise le gain d'information pour générer son arbre. Le problème c'est qu'il favorise les variables prédictives ayant un grand nombre de valeurs. Par exemple, il pourra créer des arbres très large si l'attribut contient beaucoup d'enregistrements différents, comme les ID car ID3 ne minimise pas la largeur.
### 2. Détaillez le gain ratio et expliquez son usage
Permet de mesuré la qualité du découpage d'un arbre et de contrer le problème de caractéristiques indésirables généré par ID3. Le gain d'information permet d'éviter l'overfitting et d'avoir un arbre très grand.

$Gain\ ratio = \frac{information\ gain}{entropy([p_1,p_2,...,p_n])}$

L'objectif de gain ratio est de pénaliser les attributs avec beaucoup de branches en divisant le gain d'information par entropy (= log(n)). En somme, si n le nombre de branches augmente, on divise par un nombre plus grand (cf. fonction logarithmique).

## Question 3


### Que signifient les symboles + et - ?
Ce sont des classes positive (+) ou négative (-).

### Comment l'arbre $T_R$ est-il calculé à partir de $T_L$ ?
On a élagué le niveau 3 de l'arbre $T_L$.

### Soit $e$ le *training error*. Donnez les valeurs de $e(T_L)$ et de $e(T_R)$.

Le training error est obtenu en additionnant les enregistrements des classes minoritaires:
Exemple pour l'arbre de gauche, les enregistrements à additionner sont:
1 + 1 + 0 + 1 + 0 + 1 et 0 car ils appartiennent dans les classes les moins peuplées. On a donc $e(T_L)$ = 4 erreurs d'apprentissage.

Pour $e(T_R)$ on additionne 2 + 1 + 0 + 3, ce qui nous donne $e(T_R) = 6$ erreurs d'apprentissage.

### Comment peut-on rectifier $e$ pour tenir compte de la complexité du modèle ?

---
---