Ce document, conçu pour les étudiants universitaires en Master 2 du Département d'Informatique, représente un examen en Data Mining pour l'année universitaire 2023/2024. Il a pour objectif d'évaluer la compréhension des concepts clés et la capacité à appliquer divers algorithmes dans ce domaine.
Il couvre les notions suivantes:
- Algorithmes de classification (Régression logistique, Naive Bayes) et de clustering (K-Means).
- Techniques de prétraitement des données (normalisation) et règles d'association.
- Évaluation des modèles et gestion du sur-apprentissage (overfitting).
Examen 2023-2024 Data Mining
Télécharger PDFExamen de Data Mining - Master 2 (2023/2024)
Université de Boumerdès - Faculté des Sciences - Département d'Informatique
Matière : Data Mining
Nature de l'examen : ETLD
Durée : 1 H 30
Année Universitaire : 2023/2024
Cycle : Master 2
Responsable : A. Berrichi
Barème : Questions 1 à 2 : 1 point, Questions 3 à 6 : 2 points, Exercice : 10 points.
N.B. : Ne recevront une note complète que les réponses complètes (cochez toutes les réponses qui s'appliquent).
Questions d'évaluation
1. Prédiction de probabilité de décès
On veut prédire la probabilité de décès dû à la maladie du cœur en se basant sur trois facteurs de risque : l'âge, le sexe et le niveau de cholestérol. Quel est l'algorithme le plus approprié ?
- A. La régression logistique.
- B. La régression linéaire.
- C. K-Means.
- D. L'algorithme Apriori.
Explication : La régression logistique est l'algorithme le plus approprié pour prédire une probabilité (une variable dépendante binaire ou catégorique) en fonction de plusieurs facteurs de risque. La régression linéaire est pour des variables continues, K-Means est un algorithme de clustering (non supervisé), et Apriori est utilisé pour l'analyse des règles d'association.
2. Analyse d'associations
Vous avez exécuté un algorithme d'analyse d'associations sur un ensemble de données, et les deux règles (Banane, Pomme) → (Raisins) et (Pomme, Orange) → (Raisins) se sont avérées pertinentes (fortes). Qu'est-ce qui est vrai aussi ?
- A. (Banane, Pomme, Raisins, Orange) est un ensemble d'articles fréquent.
- B. (Banane, Pomme) → (Orange) est une règle pertinente (forte).
- C. (Raisins) → (Banane, Pomme) est une règle pertinente (forte).
- D. (Raisins, Pomme) est un ensemble d'articles fréquent.
Explication : Si une règle (X) → (Y) est forte, cela implique que l'ensemble d'articles (X U Y) est un ensemble d'articles fréquent. Ainsi, si (Banane, Pomme) → (Raisins) est forte, alors (Banane, Pomme, Raisins) est un ensemble d'articles fréquent. De même, si (Pomme, Orange) → (Raisins) est forte, alors (Pomme, Orange, Raisins) est un ensemble d'articles fréquent. Par la propriété d'Apriori, tous les sous-ensembles d'un itemset fréquent sont également fréquents. En conséquence, l'ensemble (Raisins, Pomme) doit être un ensemble d'articles fréquent car il est un sous-ensemble de (Pomme, Orange, Raisins) et de (Banane, Pomme, Raisins).
3. Normalisation des attributs
Considérons 5 observations d'un attribut (ou variable) ayant les valeurs (2, 4, 6, 8, 10). Que devient cet attribut (ces valeurs) s'il est transformé à l'aide de :
- Normalisation Standard (Standardization ou z-score) :
- Moyenne (μ) = (2 + 4 + 6 + 8 + 10) / 5 = 30 / 5 = 6
- Écart type (σ) = √[((2-6)² + (4-6)² + (6-6)² + (8-6)² + (10-6)²) / 5] = √[(16 + 4 + 0 + 4 + 16) / 5] = √(40 / 5) = √8 ≈ 2.828
- Valeurs normalisées :
- (2 - 6) / 2.828 ≈ -1.414
- (4 - 6) / 2.828 ≈ -0.707
- (6 - 6) / 2.828 = 0
- (8 - 6) / 2.828 ≈ 0.707
- (10 - 6) / 2.828 ≈ 1.414
- Les valeurs transformées sont approximativement : (-1.414, -0.707, 0, 0.707, 1.414).
- Normalisation Min-Max (Min-Max Normalization) :
- Min = 2
- Max = 10
- Valeurs normalisées :
- (2 - 2) / (10 - 2) = 0 / 8 = 0
- (4 - 2) / (10 - 2) = 2 / 8 = 0.25
- (6 - 2) / (10 - 2) = 4 / 8 = 0.5
- (8 - 2) / (10 - 2) = 6 / 8 = 0.75
- (10 - 2) / (10 - 2) = 8 / 8 = 1
- Les valeurs transformées sont : (0, 0.25, 0.5, 0.75, 1).
La normalisation standard (Z-score) transforme les données pour qu'elles aient une moyenne de 0 et un écart type de 1. La formule est : z = (x - μ) / σ, où μ est la moyenne et σ est l'écart type.
Pour les valeurs (2, 4, 6, 8, 10) :
La normalisation Min-Max met les données à l'échelle dans une plage spécifique, généralement [0, 1]. La formule est : x_norm = (x - min) / (max - min).
Pour les valeurs (2, 4, 6, 8, 10) :
4. Modèle de classification avec régression logistique
Vous entraînez un modèle de classification avec régression logistique. Parmi les affirmations suivantes, lesquelles sont vraies ? Cochez toutes les cases qui s'appliquent.
- A. L'introduction de la régularisation dans le modèle se traduit toujours par des performances égales ou meilleures sur l'ensemble d'apprentissage.
- B. L'ajout d'une nouvelle fonctionnalité au modèle se traduit toujours par des performances égales ou supérieures sur l'ensemble d'apprentissage.
- C. L'introduction de la régularisation dans le modèle se traduit toujours par des performances égales ou meilleures sur les exemples ne figurant pas dans l'ensemble d'apprentissage.
Explication :
- B est vraie : L'ajout de nouvelles fonctionnalités offre au modèle plus d'informations pour apprendre les relations dans les données d'apprentissage, ce qui peut potentiellement améliorer ou au moins maintenir ses performances sur cet ensemble, à condition que la nouvelle fonctionnalité soit pertinente.
- C est vraie : La régularisation vise à prévenir le sur-ajustement (overfitting) en pénalisant les coefficients importants, ce qui rend le modèle moins sensible aux bruits dans les données d'apprentissage et améliore sa capacité de généralisation sur de nouvelles données (ensemble de test). Elle peut même réduire légèrement les performances sur l'ensemble d'apprentissage, mais l'objectif est d'améliorer la performance sur les données non vues.
- A est fausse : La régularisation est conçue pour réduire le sur-ajustement, ce qui peut entraîner une légère baisse des performances sur l'ensemble d'apprentissage, car elle contraint le modèle à être plus simple et moins apte à "mémoriser" les données d'entraînement.
5. Le sur-ajustement (Overfitting)
Le sur-ajustement (Overfitting) d'un modèle de régression se produit lorsque vous tentez d'estimer trop de paramètres à partir d'un échantillon de taille trop faible. Cela veut dire que le modèle prédictif généré durant l'apprentissage :
- A. s'adapte mal aux données d'apprentissage et donc il ne se généralisera pas bien sur de nouvelles données.
- B. est trop mauvais sur les données d'apprentissage avec une sur-estimation de la qualité de prédiction sur de nouvelles données.
- C. s'adapte très bien aux données d'apprentissage et qui se généralisera mal sur de nouvelles données.
- D. est trop spécialisé sur les données d'apprentissage avec de mauvaises performances sur de nouvelles données.
Explication : L'overfitting signifie que le modèle apprend trop spécifiquement les données d'apprentissage, y compris le bruit, et perd sa capacité à généraliser. Par conséquent, il obtient d'excellentes performances sur l'ensemble d'apprentissage mais de mauvaises performances sur de nouvelles données non vues. L'option C décrit le mieux ce phénomène.
6. K-Means et fonction de distorsion
Supposons que nous avons des données non étiquetées : x(1) = (1,0), x(2) = (0,2), x(3) = (3,2), x(4) = (3,4), x(5) = (5,5). À une itération donnée de K-Means (pour K=2), les centroïdes étaient μ1 = (1,1) et μ2 = (4,3). Représenter les données dans un repère orthonormé et calculer la fonction de distorsion (de coût) pour cette itération.
Explication :
L'algorithme K-Means vise à partitionner un ensemble de données en K clusters, où chaque observation appartient au cluster avec le centroïde le plus proche. La fonction de distorsion (ou de coût) mesure la somme des carrés des distances euclidiennes entre chaque point de donnée et le centroïde de son cluster assigné. Elle est souvent notée J = ∑i=1K ∑x∈Ci ||x - μi||².
Calcul de la fonction de distorsion pour K=2 :
D'abord, assignons chaque point au centroïde le plus proche en utilisant la distance euclidienne au carré :
- x(1) = (1,0) :
- Distance² à μ1=(1,1) : (1-1)² + (0-1)² = 0 + 1 = 1
- Distance² à μ2=(4,3) : (1-4)² + (0-3)² = 9 + 9 = 18
- Assigné à μ1. Coût : 1.
- x(2) = (0,2) :
- Distance² à μ1=(1,1) : (0-1)² + (2-1)² = 1 + 1 = 2
- Distance² à μ2=(4,3) : (0-4)² + (2-3)² = 16 + 1 = 17
- Assigné à μ1. Coût : 2.
- x(3) = (3,2) :
- Distance² à μ1=(1,1) : (3-1)² + (2-1)² = 4 + 1 = 5
- Distance² à μ2=(4,3) : (3-4)² + (2-3)² = 1 + 1 = 2
- Assigné à μ2. Coût : 2.
- x(4) = (3,4) :
- Distance² à μ1=(1,1) : (3-1)² + (4-1)² = 4 + 9 = 13
- Distance² à μ2=(4,3) : (3-4)² + (4-3)² = 1 + 1 = 2
- Assigné à μ2. Coût : 2.
- x(5) = (5,5) :
- Distance² à μ1=(1,1) : (5-1)² + (5-1)² = 16 + 16 = 32
- Distance² à μ2=(4,3) : (5-4)² + (5-3)² = 1 + 4 = 5
- Assigné à μ2. Coût : 5.
Points assignés :
- Cluster 1 (μ1=(1,1)) : x(1)=(1,0), x(2)=(0,2)
- Cluster 2 (μ2=(4,3)) : x(3)=(3,2), x(4)=(3,4), x(5)=(5,5)
Calcul de la fonction de distorsion J :
- Pour Cluster 1 (μ1) : Coût = 1 (pour x1) + 2 (pour x2) = 3
- Pour Cluster 2 (μ2) : Coût = 2 (pour x3) + 2 (pour x4) + 5 (pour x5) = 9
Distorsion J = Coût Cluster 1 + Coût Cluster 2 = 3 + 9 = 12.
La fonction de distorsion pour cette itération est 12.
Exercice pratique : Prédiction de défaut de paiement avec Naive Bayes
Contexte
Le tableau ci-dessous montre des données relatives aux emprunteurs d'une banque avec les attributs suivants : "Propriétaire de Maison", "État Civil" et "Revenu Annuel". Les emprunteurs en défaut de paiement sont classés dans la catégorie "Oui", tandis que ceux qui ont remboursé leurs prêts sont classés dans la catégorie "Non".
| Id. | Propriétaire de Maison | État Civil | Revenu Annuel | Défaut de Paiement |
|---|---|---|---|---|
| 1 | Oui | Célibat. | 125 | Non |
| 2 | Non | Marié | 100 | Non |
| 3 | Non | Célibat. | 70 | Non |
| 4 | Oui | Marié | 120 | Non |
| 5 | Non | Divorcé | 95 | Oui |
| 6 | Non | Marié | 60 | Non |
| 7 | Non | Célibat. | 85 | Oui |
| 8 | Non | Marié | 75 | Non |
| 9 | Non | Célibat. | 90 | Oui |
Soit un nouveau client X ayant les caractéristiques suivantes : X = (Maison = Oui, État = Divorcé, Revenu = 120).
1. Prédiction du défaut de paiement pour un nouveau client (Classifieur Naive Bayes)
Il est demandé de prédire si ce nouveau client sera en défaut de paiement ou non en utilisant le classifieur Naive Bayes et les données ci-dessus comme données d'apprentissage.
Explication du Classifieur Naive Bayes :
Le classifieur Naive Bayes est un algorithme de classification probabiliste basé sur le théorème de Bayes avec l'hypothèse (naïve) d'indépendance conditionnelle entre les attributs. Il est particulièrement efficace pour les tâches de classification et fonctionne bien avec de grands ensembles de données.
Étapes de calcul :
- Calculer les probabilités a priori P(Défaut=Oui) et P(Défaut=Non).
- Calculer les probabilités conditionnelles P(Attribut|Défaut) pour chaque attribut et chaque valeur du client X.
- Appliquer le théorème de Bayes pour trouver la probabilité P(Défaut|X) pour chaque classe.
- Assigner le client X à la classe avec la probabilité la plus élevée.
Calculs détaillés :
1. Probabilités a priori :
- Total d'enregistrements = 9
- Nombre de "Défaut=Oui" = 3 (Clients 5, 7, 9)
- Nombre de "Défaut=Non" = 6 (Clients 1, 2, 3, 4, 6, 8)
- P(Défaut=Oui) = 3/9 = 1/3
- P(Défaut=Non) = 6/9 = 2/3
2. Probabilités conditionnelles pour le client X (Maison=Oui, État=Divorcé, Revenu=120) :
Pour la classe "Défaut=Oui" :
- P(Maison=Oui | Défaut=Oui) : Parmi les 3 clients avec Défaut=Oui (5,7,9), aucun n'est Propriétaire de Maison=Oui. → 0/3 = 0.
- P(État=Divorcé | Défaut=Oui) : Parmi les 3 clients avec Défaut=Oui (5,7,9), 1 est Divorcé (client 5). → 1/3.
- P(Revenu=120 | Défaut=Oui) : Parmi les 3 clients avec Défaut=Oui, aucun n'a un revenu de 120. → 0/3 = 0.
Pour la classe "Défaut=Non" :
- P(Maison=Oui | Défaut=Non) : Parmi les 6 clients avec Défaut=Non (1,2,3,4,6,8), 2 sont Propriétaire de Maison=Oui (clients 1, 4). → 2/6 = 1/3.
- P(État=Divorcé | Défaut=Non) : Parmi les 6 clients avec Défaut=Non, aucun n'est Divorcé. → 0/6 = 0.
- P(Revenu=120 | Défaut=Non) : Parmi les 6 clients avec Défaut=Non, 1 a un revenu de 120 (client 4). → 1/6.
3. Application du théorème de Bayes :
- P(Défaut=Oui | X) ∝ P(Défaut=Oui) * P(Maison=Oui|Oui) * P(État=Divorcé|Oui) * P(Revenu=120|Oui)
- P(Défaut=Oui | X) ∝ (1/3) * 0 * (1/3) * 0 = 0.
- P(Défaut=Non | X) ∝ P(Défaut=Non) * P(Maison=Oui|Non) * P(État=Divorcé|Non) * P(Revenu=120|Non)
- P(Défaut=Non | X) ∝ (2/3) * (1/3) * 0 * (1/6) = 0.
Ceci est un cas où l'application stricte de Naive Bayes sans technique de lissage (comme le lissage de Laplace) conduit à une probabilité de 0 pour les deux classes. Lorsqu'une probabilité conditionnelle est nulle (c'est-à-dire qu'une combinaison d'attributs n'est jamais observée dans une classe donnée dans les données d'apprentissage), le produit entier pour cette classe devient 0, rendant la prédiction ambiguë ou impossible. Pour une application réelle, un lissage serait indispensable.
2. Matrice de confusion et Précision (Accuracy)
Le modèle de Bayes fournit les prédictions suivantes pour les neuf clients de la banque :
| Défaut de Paiement Prédit |
|---|
| Non |
| Non |
| Oui |
| Non |
| Oui |
| Oui |
| Non |
| Non |
| Oui |
Calculer la matrice de confusion et la précision (Accuracy) du modèle sur les données d'apprentissage.
Explication :
La matrice de confusion est un tableau qui permet de visualiser les performances d'un algorithme de classification. Chaque ligne représente les instances d'une classe prédite, tandis que chaque colonne représente les instances d'une classe réelle. Elle permet de calculer des métriques telles que la précision, le rappel, le F1-score et l'exactitude (accuracy).
L'Accuracy (précision ou exactitude) est la proportion d'observations correctement classées parmi le nombre total d'observations. Accuracy = (TP + TN) / (TP + TN + FP + FN), où TP = Vrais Positifs, TN = Vrais Négatifs, FP = Faux Positifs, FN = Faux Négatifs.
Données réelles de défaut de paiement :
- Client 1: Non
- Client 2: Non
- Client 3: Non
- Client 4: Non
- Client 5: Oui
- Client 6: Non
- Client 7: Oui
- Client 8: Non
- Client 9: Oui
Prédictions du modèle :
- Client 1: Non
- Client 2: Non
- Client 3: Oui
- Client 4: Non
- Client 5: Oui
- Client 6: Oui
- Client 7: Non
- Client 8: Non
- Client 9: Oui
Comparons les réels et les prédits :
- Client 1: Réel=Non, Prédit=Non (TN)
- Client 2: Réel=Non, Prédit=Non (TN)
- Client 3: Réel=Non, Prédit=Oui (FP)
- Client 4: Réel=Non, Prédit=Non (TN)
- Client 5: Réel=Oui, Prédit=Oui (TP)
- Client 6: Réel=Non, Prédit=Oui (FP)
- Client 7: Réel=Oui, Prédit=Non (FN)
- Client 8: Réel=Non, Prédit=Non (TN)
- Client 9: Réel=Oui, Prédit=Oui (TP)
Comptage :
- Vrais Positifs (TP - Réel=Oui, Prédit=Oui) = 2 (Clients 5, 9)
- Faux Positifs (FP - Réel=Non, Prédit=Oui) = 2 (Clients 3, 6)
- Faux Négatifs (FN - Réel=Oui, Prédit=Non) = 1 (Client 7)
- Vrais Négatifs (TN - Réel=Non, Prédit=Non) = 4 (Clients 1, 2, 4, 8)
Matrice de Confusion :
| Prédiction | ||
|---|---|---|
| Réel | Oui | Non |
| Oui | TP = 2 | FN = 1 |
| Non | FP = 2 | TN = 4 |
Calcul de la Précision (Accuracy) :
Accuracy = (TP + TN) / (TP + TN + FP + FN)
Accuracy = (2 + 4) / (2 + 4 + 2 + 1)
Accuracy = 6 / 9
Accuracy ≈ 0.6667 ou 66.67%
La précision du modèle est d'environ 66.67%.
Questions Fréquentes (FAQ)
Qu'est-ce que la régression logistique et quand l'utiliser ?
La régression logistique est une méthode d'analyse statistique utilisée pour prédire la probabilité d'un événement en fonction de variables indépendantes. Elle est particulièrement utile lorsque la variable dépendante est binaire (par exemple, "oui/non", "succès/échec") ou ordinale. Contrairement à la régression linéaire, elle modélise la probabilité en utilisant une fonction logistique, ce qui la rend adaptée aux problèmes de classification binaire.
Pourquoi la normalisation des données est-elle importante en Data Mining ?
La normalisation des données est cruciale car elle permet de ramener tous les attributs à une échelle comparable. Sans normalisation, les attributs ayant des plages de valeurs plus grandes pourraient dominer l'algorithme d'apprentissage, conduisant à des résultats biaisés et à des performances médiocres. Elle est essentielle pour de nombreux algorithmes basés sur la distance, tels que les machines à vecteurs de support (SVM), le K-Means ou les réseaux de neurones.
Quelle est la différence entre l'overfitting (sur-ajustement) et l'underfitting (sous-ajustement) ?
L'overfitting (sur-ajustement) se produit lorsque un modèle est trop complexe et apprend le bruit et les détails spécifiques des données d'apprentissage. Il excelle sur ces données mais échoue à généraliser à de nouvelles données non vues. L'underfitting (sous-ajustement), à l'inverse, survient lorsque le modèle est trop simple pour capturer la relation sous-jacente dans les données. Il sous-performe aussi bien sur les données d'apprentissage que sur les nouvelles données, car il n'a pas suffisamment appris les patterns essentiels.