Cette série d'exercices, élaborée par le Département d'Informatique de la Faculté des Sciences de l'UMBBoumerdes, est destinée aux étudiants universitaires. Elle vise à renforcer la compréhension des concepts fondamentaux du Data Mining, axés sur la classification.
Ce document explore les notions suivantes :
- Les indices de Gini et d'entropie pour la classification ;
- Les algorithmes d'arbres de décision et leurs critères d'arrêt ;
- La comparaison entre C4.5 et C5.0 ;
- Le sur-apprentissage (overfitting) et les méthodes d'élagage.
Exercices TD Indice de Gini Data mining
Télécharger PDFSérie d'exercices n° 02 en Data Mining
Ce document présente une série d'exercices pratiques en Data Mining, axés sur des concepts fondamentaux tels que l'indice de Gini, l'entropie, le gain d'information, les algorithmes de construction d'arbres de décision et les techniques de lutte contre le surapprentissage (overfitting).
Exercice 01 : Indice de Gini et Arbres de Décision
Considérons les exemples d'apprentissage présentés dans le tableau ci-dessous pour un problème de classification binaire. L'indice de Gini est une mesure de l'impureté utilisée dans les algorithmes d'arbres de décision pour sélectionner la meilleure caractéristique de division. Un indice de Gini faible indique une plus grande pureté du nœud, ce qui est souhaitable pour la construction d'un arbre de décision.
Tableau d'Exemples d'Apprentissage
| ID Client | Genre | Type de voiture | Taille | Class |
|---|---|---|---|---|
| 1 | M | Familial | S | 0 |
| 2 | M | Sports | M | 0 |
| 3 | M | Sports | M | 0 |
| 4 | M | Sports | L | 0 |
| 5 | M | Sports | XL | 0 |
| 6 | M | Sports | XL | 0 |
| 7 | F | Sports | S | 0 |
| 8 | F | Sports | S | 0 |
| 9 | F | Sports | M | 0 |
| 10 | F | Luxe | L | 0 |
| 11 | M | Familial | L | 1 |
| 12 | M | Familial | XL | 1 |
| 13 | M | Familial | M | 1 |
| 14 | M | Luxe | XL | 1 |
| 15 | F | Luxe | S | 1 |
| 16 | F | Luxe | S | 1 |
| 17 | F | Luxe | M | 1 |
| 18 | F | Luxe | M | 1 |
| 19 | F | Luxe | M | 1 |
| 20 | F | Luxe | L | 1 |
- Calculez l'indice de Gini pour l'ensemble des exemples d'apprentissage.
- Calculez l'indice de Gini pour l'attribut ID client.
- Calculez l'indice de Gini pour l'attribut Genre.
- Calculez l'indice de Gini pour l'attribut Type de voiture à l'aide d'une division multidirectionnelle (Multi-way split).
- Calculez l'indice de Gini pour l'attribut Taille à l'aide d'une division multidirectionnelle.
- Quel attribut est le meilleur (Genre, Type de voiture ou Taille) selon l'indice de Gini ? Expliquez pourquoi l'ID client ne doit pas être utilisé comme condition de test d'attribut, même s'il a potentiellement le Gini le plus bas.
Exercice 02 : Critère d'Arrêt de l'Algorithme de Hunt
Quelle est la condition d'arrêt de l'algorithme de Hunt ?
L'algorithme de Hunt est une approche récursive utilisée pour construire des arbres de décision. Il continue à diviser les nœuds tant que les conditions d'arrêt ne sont pas remplies. Les critères typiques qui signalent la fin de la division d'un nœud incluent :
- Tous les enregistrements d'un nœud donné appartiennent à la même classe ; le nœud est alors considéré comme "pur" et devient une feuille.
- Il n'y a plus d'attributs restants à considérer pour la division, ou tous les attributs restants ont déjà été utilisés.
- Le nombre d'enregistrements dans un nœud est inférieur à un seuil prédéfini, empêchant ainsi la création de feuilles avec très peu d'exemples.
- L'arbre a atteint une profondeur maximale prédéfinie, pour contrôler la complexité du modèle et éviter le surapprentissage.
Exercice 03 : Entropie, Gain d'Information et Taux d'Erreur de Classification
Considérons les exemples d'apprentissage présentés dans le tableau ci-dessous pour un problème de classification binaire. L'entropie mesure l'incertitude ou le désordre dans un ensemble de données. Le gain d'information, quant à lui, mesure la réduction de l'entropie après une division basée sur un attribut, indiquant l'efficacité de cet attribut pour la classification. Un gain d'information élevé signifie que l'attribut est pertinent pour séparer les classes.
Tableau d'Exemples d'Apprentissage
| Instance | X1 | X2 | X3 | Class |
|---|---|---|---|---|
| 1 | T | T | 1.0 | + |
| 2 | T | T | 6.0 | + |
| 3 | T | F | 5.0 | - |
| 4 | F | F | 4.0 | + |
| 5 | F | T | 7.0 | - |
| 6 | F | T | 3.0 | - |
| 7 | F | F | 8.0 | - |
| 8 | T | F | 7.0 | + |
| 9 | F | T | 5.0 | - |
- Quelle est l'entropie de cette collection d'exemples d'apprentissage par rapport à l'attribut de classe ?
- Quels sont les gains d'information de X1 et X2 par rapport à ces exemples d'apprentissage ?
- Pour X3, qui est un attribut continu, calculez le gain d'information pour chaque division possible.
- Quelle est la meilleure division (entre X1, X2 et X3) selon le gain d'information ?
- Quelle est la meilleure division (entre X1 et X2) selon le taux d'erreur de classification (misclassification error rate) ?
- Quelle est la meilleure division (entre X1 et X2) selon l'indice de Gini ?
Exercice 05 : Différences entre C4.5 et C5.0
Quelle est la différence entre les algorithmes C4.5 et C5.0 ?
C4.5 et C5.0 sont des algorithmes d'arbres de décision développés par Ross Quinlan, C5.0 étant une amélioration significative de son prédécesseur C4.5. Les principales différences et améliorations de C5.0 incluent :
- Vitesse : C5.0 est significativement plus rapide que C4.5, souvent plusieurs ordres de grandeur, ce qui le rend plus adapté aux grands ensembles de données.
- Efficacité de la mémoire : C5.0 est plus économe en mémoire que C4.5, permettant de traiter des datasets plus volumineux sur des machines avec des ressources limitées.
- Taille de l'arbre : C5.0 tend à générer des arbres de décision plus petits et plus compacts que C4.5, ce qui les rend plus faciles à interpréter et potentiellement plus généralisables.
- Boosting : C5.0 intègre nativement des techniques de boosting (comme les forêts d'arbres de décision), qui permettent d'améliorer considérablement la précision du modèle en combinant plusieurs arbres. Cette fonctionnalité n'est pas présente dans C4.5.
- Types d'attributs : C5.0 gère mieux les attributs continus et les attributs avec de nombreuses valeurs distinctes.
- Licence : C4.5 est open source, tandis que C5.0 est propriétaire et commercial, bien qu'il existe des implémentations open source inspirées de C5.0 (comme rpart).
Exercice 06 : Le Problème de Surapprentissage (Overfitting)
Expliquez le problème de sur-ajustement (overfitting) en machine learning (ou data mining), particulièrement dans le cas des arbres de décision.
Le surapprentissage (overfitting) est un phénomène critique en machine learning où un modèle d'apprentissage automatique apprend les données d'entraînement de manière trop détaillée, capturant non seulement les motifs sous-jacents mais aussi le bruit et les particularités spécifiques à cet ensemble de données. En conséquence, le modèle performe exceptionnellement bien sur les données qu'il a déjà vues (l'ensemble d'entraînement), mais sa capacité à généraliser et à prédire correctement sur de nouvelles données (non vues) est fortement compromise, menant à une performance médiocre en production.
Dans le cas des arbres de décision, le surapprentissage se manifeste par la construction d'un arbre excessivement complexe, avec trop de branches et de nœuds profonds. Cet arbre "mémorise" littéralement chaque exemple d'entraînement, créant des règles très spécifiques qui ne sont pas représentatives de la population générale. Par exemple, un arbre pourrait créer une branche pour chaque instance unique si un attribut d'identification est utilisé, ou continuer à se diviser jusqu'à ce que chaque feuille contienne un seul exemple, ce qui est le signe d'un surapprentissage extrême.
Exercice 07 : Approches pour Éviter l'Overfitting
Quelles sont les deux approches principales utilisées pour éviter le problème d'overfitting dans les arbres de décision ?
Pour contrer le surapprentissage en particulier avec les arbres de décision, deux grandes catégories d'approches sont utilisées :
- Le pré-élagage (Pre-pruning) :
Cette approche consiste à arrêter la croissance de l'arbre de décision avant qu'il ne s'ajuste parfaitement aux données d'entraînement. Cela est généralement réalisé en imposant des contraintes ou des conditions d'arrêt pendant la phase de construction de l'arbre. Les critères de pré-élagage peuvent inclure :
- La définition d'une profondeur maximale pour l'arbre.
- Le nombre minimum d'échantillons requis pour qu'un nœud puisse être divisé.
- Le nombre minimum d'échantillons requis dans une feuille terminale.
- L'arrêt de la division si l'amélioration du critère de scission (comme l'indice de Gini ou le gain d'information) est en dessous d'un certain seuil prédéfini.
- Le post-élagage (Post-pruning) :
Contrairement au pré-élagage, cette approche consiste à construire d'abord un arbre de décision complet (qui peut être surajusté aux données d'entraînement), puis à élaguer (supprimer) les branches ou les nœuds jugés non pertinents ou responsables du surapprentissage. Le post-élagage est souvent considéré comme plus efficace car il permet d'évaluer l'impact de chaque nœud et sous-arbre une fois l'arbre entièrement formé. Deux méthodes courantes de post-élagage sont le "Rule post-pruning" et le "Reduced-error pruning", expliquées ci-dessous.
Exercice 08 : Méthodes de Post-Élagage
Expliquez les méthodes « Rule post-pruning » et « Reduced-error pruning ».
- Rule Post-Pruning (Élagage des règles après extraction) :
Cette méthode commence par convertir l'arbre de décision complet en un ensemble de règles "si-alors". Chaque chemin allant de la racine à une feuille devient une règle unique. Ensuite, chaque règle est considérée et élaguée indépendamment en supprimant des conditions (littéraux) si cela améliore la précision de la règle sur un ensemble de validation séparé. Une fois toutes les règles élaguées, elles sont triées par leur précision (ou un autre critère) et appliquées dans cet ordre. L'avantage est que les règles sont souvent plus compréhensibles et que l'élagage peut être plus fin que celui effectué sur l'arbre lui-même.
- Reduced-Error Pruning (Élagage par réduction d'erreur) :
Le Reduced-Error Pruning est une technique de post-élagage qui nécessite un ensemble de données d'élagage distinct (différent des ensembles d'entraînement et de test). La méthode fonctionne en parcourant l'arbre de décision de bas en haut, à partir des feuilles. Pour chaque nœud non-feuille, elle évalue l'impact de sa suppression sur le taux d'erreur mesuré sur l'ensemble d'élagage. Si le fait de remplacer un sous-arbre par une feuille (qui représente la classe majoritaire des exemples de ce sous-arbre) ou de le remplacer par l'une de ses sous-branches réduit ou ne modifie pas le taux d'erreur sur l'ensemble d'élagage, alors le nœud est élagué. Ce processus est répété de manière itérative jusqu'à ce qu'aucune amélioration significative ne puisse être obtenue.
Foire Aux Questions (FAQ) sur les Arbres de Décision
Qu'est-ce que l'indice de Gini et pourquoi est-il important dans la construction des arbres de décision ?
L'indice de Gini est une mesure d'impureté ou de désordre dans un ensemble de données. En Data Mining, il est crucial pour la construction des arbres de décision (comme dans l'algorithme CART) car il permet d'évaluer la qualité d'une division. Un indice de Gini plus faible pour un attribut signifie que cet attribut sépare mieux les classes, conduisant à des nœuds plus purs et, par conséquent, à un arbre de décision plus efficace pour la classification.
Pourquoi l'ID client n'est-il pas un bon attribut pour la classification, même s'il peut avoir un indice de Gini très faible ?
Bien que l'ID client puisse avoir un indice de Gini très faible (souvent proche de zéro ou nul), il ne doit pas être utilisé comme attribut de classification. Chaque ID client est unique, ce qui signifierait que l'arbre créerait des nœuds feuilles contenant un seul exemple. Cela entraînerait un surapprentissage extrême, où le modèle mémoriserait chaque instance spécifique au lieu d'apprendre des motifs généralisables. Un attribut d'identification n'apporte aucune capacité de généralisation et rend le modèle incapable de prédire correctement sur de nouvelles données.
Quelle est la principale amélioration de C5.0 par rapport à C4.5 et quel en est le bénéfice ?
La principale amélioration de C5.0 par rapport à C4.5 réside dans sa vitesse d'exécution, sa consommation de mémoire réduite et l'intégration de techniques de boosting. Ces améliorations permettent à C5.0 de construire des arbres de décision beaucoup plus rapidement et efficacement, de gérer de plus grands ensembles de données, et de générer des modèles plus précis et compacts grâce au boosting, rendant l'algorithme plus adapté aux défis des données massives et des applications réelles.