Exercices td apprentissage automatique data mining

Ce document pédagogique est une ressource complète, compilant des notes de cours et des exercices pratiques. Il est destiné aux étudiants universitaires suivant des modules sur le Data Mining et le Machine Learning.

Il couvre les notions fondamentales suivantes :

Les concepts clés du Data Mining, incluant les types de variables et les tâches supervisées et non supervisées.
L'application des algorithmes d'arbres de décision, avec les mesures d'impureté et de gain d'information.
Les principes de la régression linéaire et logistique, l'optimisation des fonctions de coût et la régularisation.

Exercices TD Apprentissage Automatique Data mining

Télécharger PDF

Introduction au Data Mining et à l'Apprentissage Automatique

Concepts Fondamentaux

Le Data Mining (DM) et l'Apprentissage Automatique (Machine Learning - ML) sont des disciplines étroitement liées. L'Apprentissage Automatique (ML) utilise des algorithmes qui apprennent à partir de données pour identifier des modèles et faire des prédictions. L'Apprentissage Profond (Deep Learning - DL), un sous-domaine du ML, s'inspire du fonctionnement du cerveau humain (réseaux de neurones) pour traiter des tâches complexes.

En Data Mining, nous nous concentrons sur l'extraction de connaissances à partir de vastes ensembles de données. Les principales tâches de DM se divisent en deux grandes catégories :

Prédictive (Supervisée) : Une variable cible (y) est disponible et les algorithmes apprennent à la prédire. Cela inclut la classification et la régression.
Descriptive (Non Supervisée) : Il n'y a pas de variable cible prédéfinie. L'objectif est de découvrir des structures cachées dans les données, comme la segmentation (clustering) ou les règles d'association.

Types de Variables

Les variables peuvent être classées selon leur nature :

Variables Qualitatives (Catégorielles) : Représentent des catégories.
- Nominales : Les catégories n'ont pas d'ordre intrinsèque (ex: couleurs). Elles possèdent la même importance.
- Ordinales : Les catégories ont un ordre défini, mais les intervalles entre elles ne sont pas mesurables ou uniformes (ex: taux de satisfaction : Faible, Moyen, Fort).
Variables Quantitatives (Numériques) : Représentent des mesures numériques.
- Intervalles : Les intervalles entre les valeurs sont uniformes, mais le zéro n'est pas absolu (il ne signifie pas l'absence du phénomène). Ex: température, année.
- Ratio : Les intervalles sont uniformes et le zéro est absolu (signifiant l'absence du phénomène). Ex: taille, poids.

Exercice sur la Classification des Variables

Classifiez les types de variables suivants :

a. Binaire (Catégorielle, Nominale)
b. Continue (Ratio), où 0 signifie l'absence (ex: lumière)
c. Faible, moyen, fort (Discrète, Quantitative, Ordinale)
d. Continue (Quantitative, Ratio)
e. Discrète (Quantitative, Ordinale)
f. Continue (Quantitative, Intervalle)
g. Continue (Quantitative, Ratio)
h. Discrète (Quantitative, Nominale)
i. Discrète (Ordinale)
j. Discrète (Ratio)
k. Continue (Ratio)
l. Discrète (Nominale)

Tâches de Data Mining Supervisées et Non Supervisées

Les tâches de Data Mining sont fondamentales pour l'extraction de connaissances. Elles se distinguent principalement par la présence ou l'absence d'une variable cible.

Supervisées (Prédictives) :
- Classification : La variable cible est catégorielle (discrète). L'objectif est de prédire la classe d'une nouvelle observation (ex: prédire si un email est un spam ou non).
- Régression : La variable cible est quantitative (continue). L'objectif est de prédire une valeur numérique (ex: prédire le prix d'une maison).
Non Supervisées (Descriptives) :
- Détection d'anomalies : Identifier des observations qui s'écartent significativement de la majorité (ex: détection de fraudes).
- Segmentation (Clustering) : Regrouper des observations similaires en clusters (ex: segmentation de clients).
- Règles d'association : Découvrir des relations entre les variables (ex: les clients qui achètent A achètent aussi B).

Exemples de règles :

Règle de classification : "Une voiture contient une boîte de vitesse automatique." (Prédire la présence d'une boîte automatique).
Règle de régression : "Si l'âge est < 45 ans et le salaire est < 80k, alors le conducteur achète une voiture de sport avec 80% de probabilité." (Cet exemple mélange régression et classification/règles d'association, car la sortie est catégorielle et probabiliste).
Règle de séquences : "Après avoir acheté X, le client achète Y dans 15 jours."

Arbres de Décision

Introduction aux Arbres de Décision

Les arbres de décision sont une technique d'apprentissage automatique supervisée (utilisée pour la classification et la régression). Ils représentent des règles de décision sous la forme d'une structure arborescente. Chaque nœud interne teste un attribut, chaque branche représente le résultat du test et chaque feuille représente une décision ou une classe. Ils sont utiles pour comprendre les résultats à travers une série de choix interconnectés.

Exemple : Les survivants du Titanic. L'arbre peut diviser les passagers en fonction du genre, de l'âge, etc., pour prédire la survie.

La construction de l'arbre se fait à l'aide d'algorithmes (comme CART) qui visent à créer des nœuds ayant la plus grande pureté possible. Pour ce faire, des mesures d'impureté sont utilisées.

Mesures d'Impureté : Indice de Gini

L'indice de Gini mesure l'impureté d'un nœud. Un Gini de 0 indique une pureté parfaite (toutes les instances appartiennent à la même classe). L'objectif est de minimiser le Gini (plus la valeur est faible, meilleure est la division).

La formule de Gini est : Gini(S) = 1 - ∑(Pi)² où Pi est la proportion d'instances de la classe i dans l'ensemble S.

Exemple de Calcul de Gini (Exercice simplifié) :

Considérons un ensemble de données.

ID Client (attribut unique) : Un ID client est une clé primaire unique et non une caractéristique prédictive. L'utilisation d'un tel attribut entraînerait un surapprentissage car on ne pourrait pas classifier un nouveau client.
Calcul pour un attribut "Genre" (M/F) :
- Gini(Genre = M) = 1 - (proportion_classe1_M)² - (proportion_classe2_M)²
- Gini(Genre = F) = 1 - (proportion_classe1_F)² - (proportion_classe2_F)²
- Gini(Genre) = (Proportion_M * Gini(Genre = M)) + (Proportion_F * Gini(Genre = F))
Calcul pour un attribut "Type de Voiture" (Sport, Famille, Luxe) :
- Gini(Type = Sport) = 1 - (proportion_classe1_Sport)² - (proportion_classe2_Sport)²
- Gini(Type = Famille) = 1 - (proportion_classe1_Famille)² - (proportion_classe2_Famille)²
- Gini(Type = Luxe) = 1 - (proportion_classe1_Luxe)² - (proportion_classe2_Luxe)²
- Gini(Type) = Somme pondérée des Gini pour chaque catégorie de type de voiture.
Calcul pour un attribut "Taille" (S, M, L) :
- Gini(Taille = S) = 1 - (proportion_classe1_S)² - (proportion_classe2_S)²
- Gini(Taille = M) = 1 - (proportion_classe1_M)² - (proportion_classe2_M)²
- Gini(Taille = L) = 1 - (proportion_classe1_L)² - (proportion_classe2_L)²
- Gini(Taille) = Somme pondérée des Gini pour chaque catégorie de taille.

L'attribut qui offre la meilleure division est celui qui obtient la valeur de Gini la plus faible. Par exemple, si "Type de voiture" a le Gini le plus faible, c'est le meilleur attribut pour la division.

Mesures d'Impureté : Entropie et Gain d'Information

L'entropie mesure le désordre ou l'incertitude dans un ensemble de données. Un gain d'information élevé est préférable (plus la valeur est élevée, meilleure est la division).

La formule de l'entropie est : Entropy(S) = -∑(Pi * log2(Pi)).

Le gain d'information (Gain) pour un attribut A est : Gain(S, A) = Entropy(S) - ∑((|Sv| / |S|) * Entropy(Sv)), où Sv est le sous-ensemble pour lequel l'attribut A a la valeur v.

Exemple de Calcul (Exercice simplifié) :

a) Calcul de l'entropie d'un ensemble S (ex: 4 "Oui", 5 "Non" sur 9 instances):

Entropy(S) = - [ (4/9) * log2(4/9) + (5/9) * log2(5/9) ] ≈ 0.9911

b) Calcul du Gain d'Information pour un attribut A1 (avec valeurs T/F) :

Entropy(A1 = T) = - [ (3/4) * log2(3/4) + (1/4) * log2(1/4) ] ≈ 0.8112
Entropy(A1 = F) = - [ (1/5) * log2(1/5) + (4/5) * log2(4/5) ] ≈ 0.7219
Gain(S, A1) = Entropy(S) - [ (4/9) * Entropy(A1 = T) + (5/9) * Entropy(A1 = F) ] ≈ 0.2294

c) Calcul du Gain d'Information pour un attribut A2 (avec valeurs I/F) :

Entropy(A2 = I) = - [ (2/4) * log2(2/4) + (2/4) * log2(2/4) ] = 1
Entropy(A2 = F) = - [ (3/5) * log2(3/5) + (2/5) * log2(2/5) ] ≈ 0.9709
Gain(S, A2) = Entropy(S) - [ (4/9) * Entropy(A2 = I) + (5/9) * Entropy(A2 = F) ] ≈ 0.0072

Dans cet exemple, l'attribut A1 offre une meilleure division car il a un gain d'information plus élevé (0.2294 > 0.0072).

Algorithmes de Construction d'Arbres de Décision (Algorithme de Hunt)

L'algorithme de Hunt est une technique gloutonne descendante pour construire un arbre. Il divise récursivement les données. Les conditions d'arrêt incluent :

Tous les enregistrements d'un nœud appartiennent à la même classe (nœud pur).
Tous les enregistrements d'un nœud ont les mêmes valeurs d'attributs (pas de division possible).
La profondeur maximale est atteinte.

Algorithmes Spécifiques : ID3 et C4.5

ID3 (Iterative Dichotomiser 3) : Procédure itérative dichotomique. Utilise le gain d'information. Présente des limitations sur la profondeur et ne supporte pas les valeurs continues ni manquantes.
C4.5 : Une version plus évoluée et optimisée d'ID3. Gère les valeurs continues et manquantes. Introduit le concept de pondération des attributs. Consomme moins de mémoire et génère un arbre plus optimal, moins sujet au surapprentissage.

L'Élagage (Pruning) des Arbres de Décision

L'élagage est une technique qui permet de contrôler la complexité d'un arbre de décision et de prévenir le surapprentissage. Un arbre trop complexe peut s'ajuster trop aux données d'apprentissage, ce qui entraîne une performance médiocre sur les données de validation et de test.

L'élagage consiste à supprimer les nœuds ou branches qui ne contribuent pas à une amélioration significative des performances ou qui augmentent le taux d'erreur sur les données non vues.

Types d'Élagage

Pré-élagage (Pre-Pruning) : Appliqué lors de la construction de l'arbre, en définissant des conditions d'arrêt (profondeur maximale, nombre minimum d'échantillons par feuille, etc.). Seuls les attributs les plus significatifs sont sélectionnés.
Post-élagage (Post-Pruning) : Appliqué après la construction complète de l'arbre. Les nœuds ou branches sont supprimés si leur suppression n'entraîne pas une dégradation des performances. Par exemple, chaque sous-arbre peut être remplacé par la classe majoritaire de sa feuille, et le changement est conservé si la performance ne se dégrade pas.

Régression Linéaire et Descente de Gradient

Introduction à la Régression Linéaire

La régression linéaire est une technique prédictive où l'on cherche à prédire une variable dépendante continue (y) à l'aide d'une ou plusieurs variables indépendantes (x). Le modèle prend souvent la forme d'une fonction affine : hθ(x) = θ0 + θ1x, où θ0 est l'ordonnée à l'origine et θ1 est la pente.

L'objectif est de trouver les valeurs optimales des paramètres θ0 et θ1 qui minimisent la fonction de coût.

Fonction de Coût (Erreur Quadratique Moyenne)

La fonction de coût la plus courante pour la régression linéaire est l'erreur quadratique moyenne (Mean Squared Error - MSE) :

J(θ) = 1/(2m) * ∑(hθ(xi) - yi)²

où m est le nombre d'observations. Cette fonction de coût est convexe, ce qui garantit qu'il n'y a qu'un seul minimum global à trouver.

Optimisation par la Descente de Gradient

La descente de gradient est un algorithme itératif utilisé pour minimiser la fonction de coût en ajustant les paramètres θ. À chaque itération, les paramètres sont mis à jour dans la direction opposée au gradient de la fonction de coût.

Les règles de mise à jour sont :

θ0 = θ0 - α * (∂J/∂θ0)
θ1 = θ1 - α * (∂J/∂θ1)

où α est le taux d'apprentissage (learning rate) qui contrôle la taille des pas à chaque itération. Un α trop grand peut faire "sauter" le minimum, un α trop petit peut rendre l'apprentissage très lent. L'algorithme se répète jusqu'à convergence.

Dynamique de l'apprentissage : Au début, la fonction de coût génère des valeurs élevées à cause de l'initialisation aléatoire des paramètres. Durant l'apprentissage, la fonction commence à diminuer graduellement grâce à l'ajustement des paramètres. À la fin de l'apprentissage, on constate une stabilisation de la fonction de coût, indiquant l'atteinte de la configuration optimale.

Méthode Analytique pour la Régression Linéaire

Pour la régression linéaire simple (une seule caractéristique x), il existe une solution analytique qui permet de trouver directement les paramètres optimaux (θ0 et θ1) sans itération. Les formules sont basées sur les moyennes et les sommes des produits et carrés des observations.

Exemple de calcul des paramètres (simplifié) :

Si la moyenne des visites est ȳ = ∑yi / m et la moyenne de x est x̄ = ∑xi / m :

θ1 = ( ∑(xi * yi) - m * x̄ * ȳ ) / ( ∑(xi²) - m * x̄² )
θ0 = ȳ - θ1 * x̄

Cette méthode est très précise et ne dépend pas du taux d'apprentissage.

Qualité de l'Ajustement : Coefficient de Détermination R²

Le coefficient de détermination R² évalue la qualité de l'ajustement du modèle de régression. Il indique la proportion de la variance de la variable dépendante qui est expliquée par le modèle. Sa valeur est comprise entre 0 et 1. Plus R² est proche de 1, meilleur est l'ajustement.

R² = 1 - ( ∑(yi - ŷi)² / ∑(yi - ȳ)² )

Régression Linéaire Multiple

La régression linéaire multiple étend la régression linéaire simple pour modéliser la relation entre une variable dépendante et plusieurs variables indépendantes. Le modèle s'écrit : hθ(x) = θ0 + θ1x1 + ... + θnxn.

En notation matricielle, l'équation normale pour trouver les paramètres optimaux θ est :

θ = (XᵀX)⁻¹Xᵀy

où X est la matrice des caractéristiques (avec une colonne de 1 pour θ0), y est le vecteur des variables cibles, et Xᵀ est la transposée de X.

Régression Logistique

Introduction à la Régression Logistique

La régression logistique est un algorithme de classification, principalement utilisé pour des problèmes de classification binaire. Elle prédit la probabilité qu'une observation appartienne à une classe spécifique.

Exemples de problèmes de classification binaire :

Spam / Non Spam (email)
Survivant / Décédé (Titanic)

Exemples de problèmes de classification multiple :

Type d'attaque en réseau (DDoS, Man-in-the-middle, etc.)
Classification des sentiments (Positif, Négatif, Neutre)
Reconnaissance de chiffres manuscrits (MNIST Dataset)
Classification de fleurs (IRIS Dataset)

Fonction d'Activation Sigmoïde

La régression logistique utilise la fonction d'activation sigmoïde pour transformer la sortie linéaire du modèle en une probabilité comprise entre 0 et 1.

La formule de la fonction sigmoïde est : σ(z) = 1 / (1 + e⁻ᶻ), où z = θᵀx.

Rôles de la fonction sigmoïde :

Transformer la valeur linéaire z en une probabilité.
Introduire la non-linéarité, garantissant que toutes les classes ont la même importance et permettant des frontières de décision non linéaires.

hθ(x) représente la probabilité que l'observation x appartienne à la classe positive (par exemple, y=1 pour "Non Spam"). Si hθ(x) = 0.10, cela indique 10% de probabilité que l'email soit un spam. S'il s'agit d'un seuil, cet email serait considéré comme un non-spam si le seuil est par exemple de 0.5.

Fonction de Coût (Cross-Entropy ou Log Loss)

L'utilisation de l'erreur quadratique moyenne avec la fonction sigmoïde génère une fonction de coût non convexe avec plusieurs solutions optimales. Par conséquent, la régression logistique utilise la fonction de coût de Cross-Entropy (Binary Cross-Entropy) pour garantir une fonction convexe avec un minimum global unique.

La fonction de coût pour une observation est :

Cost(hθ(xi), yi) = -yi * log(hθ(xi)) - (1 - yi) * log(1 - hθ(xi))

Cette fonction de coût produit des valeurs élevées pour les mauvaises prédictions et des valeurs faibles pour les bonnes prédictions, ce qui est idéal pour la classification binaire.

Frontière de Décision

La frontière de décision est la limite qui sépare les classes. Pour la régression logistique, elle est définie par θᵀx = 0, ce qui correspond à σ(z) = 0.5. Si la probabilité prédite est ≥ 0.5, l'observation est classée dans la classe positive, sinon dans la classe négative.

Par exemple, si z = θ0 + θ1x1 + θ2x2, la frontière de décision est θ0 + θ1x1 + θ2x2 = 0.

Techniques d'Optimisation et de Généralisation

Augmentation de Données (Data Augmentation)

L'augmentation de données est un ensemble de techniques qui permettent de générer des données synthétiques (artificielles) en se basant sur les données existantes. Elle est utilisée pour accroître la taille et la diversité de l'ensemble d'entraînement.

Objectif : Améliorer la robustesse du modèle et sa capacité à généraliser sur de nouvelles données, en réduisant le surapprentissage.

Régularisation

La régularisation est une technique qui permet de contrôler les valeurs affectées aux paramètres (poids) du modèle, les empêchant d'avoir des valeurs trop grandes. Elle ajoute un terme de pénalité à la fonction de coût.

Objectif : Assurer que le modèle ne s'ajuste pas excessivement aux données d'entraînement (prévenir le surapprentissage) et améliore ainsi sa capacité de généralisation. Il existe différentes formes de régularisation (L1, L2).

Foire Aux Questions (FAQ)

Quelle est la différence entre l'apprentissage supervisé et non supervisé ?

L'apprentissage supervisé utilise des données étiquetées avec une variable cible connue pour prédire cette variable. L'apprentissage non supervisé travaille avec des données non étiquetées, cherchant à découvrir des structures ou des regroupements cachés sans variable cible prédéfinie.

À quoi servent les indices de Gini et l'entropie dans les arbres de décision ?

Les indices de Gini et l'entropie sont des mesures d'impureté utilisées pour évaluer la qualité d'une division dans la construction des arbres de décision. Ils quantifient le désordre d'un ensemble de données. L'objectif est de choisir la division qui maximise le gain d'information (réduction de l'entropie) ou minimise l'indice de Gini, afin de créer des nœuds plus "purs".

Pourquoi la fonction de coût de la régression logistique utilise-t-elle la Cross-Entropy et non l'erreur quadratique moyenne ?

L'erreur quadratique moyenne, utilisée avec la fonction sigmoïde de la régression logistique, produirait une fonction de coût non convexe avec de multiples minimums locaux, rendant difficile la recherche du minimum global par les algorithmes d'optimisation. La Cross-Entropy, en revanche, est une fonction de coût convexe pour la régression logistique, garantissant un seul minimum global et facilitant ainsi l'apprentissage du modèle.