Correction examen data mining 2024 2025

Ce document académique est un corrigé d'examen de Data Mining, spécifiquement adapté aux étudiants de Master 2 en informatique de la Faculté des Sciences de l'UMBBoumerdes. Il offre une solution détaillée aux questions posées lors de l'examen ETLD, servant de ressource pédagogique essentielle pour renforcer la compréhension des méthodes et techniques clés d'exploration de données.

Ce support didactique est conçu pour accompagner les apprenants dans leur maîtrise des concepts fondamentaux de la matière et couvre les notions suivantes :

Le calcul de l'entropie et du gain d'information.
Les métriques de distance courantes (Manhattan, Euclidienne, Chebyshev).
L'implémentation de l'algorithme de classification Naive Bayes avec l'estimateur de Laplace.
L'évaluation des performances des modèles à travers la matrice de confusion et la précision (Accuracy).

Correction examen Data Mining 2024-2025

Télécharger PDF

Correction de l'examen de Data Mining

Informations générales sur l'examen

Université : M'hamed Bougara de Boumerdès
Faculté : Sciences
Département : Informatique
Matière : Correction de Data Mining
Nature de l'examen : ETLD
Durée : 1h 30min
Année Universitaire : 2024/2025
Cycle : Master 2
Responsable : A. Berrichi
Barème :

Questions 1 à 4 : 4 pts
Questions 5 à 6 : 3 pts
Exercice 1 : 5 pts
Exercice 2 : 8 pts

Réponses aux questions préliminaires

A. B. C.
A. C. (CD)E
A. C.
D.
Distances :
- Distance de Manhattan : Somme des valeurs absolues des différences des coordonnées. Pour les données implicites : |20-22| + |14-3| + |16-10| + |18-7| + |18-10| = 2 + 11 + 6 + 11 + 8 = 38. L'exemple donné dans la correction est : 2 + 1 + 6 + 1 + 2 = 12.
- Distance Euclidienne : Racines carrée de la somme des carrés des différences des coordonnées. Pour les données implicites (issues des différences unitaires de Manhattan) : √(2² + 1² + 6² + 1² + 2²) = √(4 + 1 + 36 + 1 + 4) = √46.
- Distance de Chebyshev : Maximum des valeurs absolues des différences des coordonnées. Pour les données implicites : Max(2, 1, 6, 1, 2) = 6.
Réponse : Formule mathématique illisible ou incomplète dans le document original.

Exercice 1 : Entropie et Gain d'Information

Soit l'ensemble de huit lettres de l'alphabet : O, L, O, C, T, R, O, N.

Il y a 3 'O', 1 'L', 1 'C', 1 'T', 1 'R', 1 'N'.

a) Quelle est l'entropie de cet ensemble de lettres ?

L'entropie (H) mesure le degré d'incertitude ou de désordre dans un ensemble de données. Elle est calculée comme :

H = - Σ p(x) * log₂(p(x))

P(O) = 3/8
P(L) = 1/8
P(C) = 1/8
P(T) = 1/8
P(R) = 1/8
P(N) = 1/8

Calcul de l'entropie :

H = - [ (3/8)log₂(3/8) + (1/8)log₂(1/8) + (1/8)log₂(1/8) + (1/8)log₂(1/8) + (1/8)log₂(1/8) + (1/8)log₂(1/8) ]

H = - [ (3/8)log₂(3/8) + 5 * (1/8)log₂(1/8) ]

H ≈ 2,4056

b) Quel est le gain d'information si nous divisons ces lettres en deux ensembles, l'un contenant les voyelles et l'autre les consonnes ?

Ensemble des voyelles : {O, O, O} (3 lettres)

P(O) = 3/3 = 1

Entropie des voyelles E(voyelles) = - (1 * log₂(1)) = 0

Ensemble des consonnes : {L, C, T, R, N} (5 lettres)

P(L) = 1/5
P(C) = 1/5
P(T) = 1/5
P(R) = 1/5
P(N) = 1/5

Entropie des consonnes E(consonnes) = - [ 5 * (1/5)log₂(1/5) ] = - log₂(1/5) = log₂(5) ≈ 2,3219

Après division en 2 sous-ensembles, l'entropie conditionnelle est calculée comme la moyenne pondérée des entropies des sous-ensembles :

E_{après division} = (3/8) * E(voyelles) + (5/8) * E(consonnes)

E_{après division} = (3/8) * 0 + (5/8) * 2,3219 ≈ 1,4512

Le gain d'information (GI) mesure la réduction de l'incertitude après la division :

GI = E_initiale - E_{après division}

GI = 2,4056 - 1,4512 = 0,9544

c) Quelle est l'entropie maximale possible pour un ensemble de huit lettres ?

L'entropie est maximale lorsque toutes les lettres ont une probabilité égale d'apparaître (1/8 chacune).

E_max = - Σ (1/8) * log₂(1/8) = - 8 * (1/8) * log₂(1/8) = - log₂(1/8) = log₂(8) = 3

L'entropie maximale possible pour un ensemble de huit lettres est de 3 bits.

Exercice 2 : Classification avec Naive Bayes et Estimateur de Laplace

Soit un patient avec les symptômes X = (Mal de tête = Oui, Température = 40, Vomissement = Très fréquent).

1. Calculer P(Non|X) et P(Oui|X) et comparer les résultats.

Nous utilisons le théorème de Bayes : P(Classe|X) ∝ P(X|Classe) * P(Classe)

Où P(X|Classe) = P(Mal de tête=Oui|Classe) * P(Température=40|Classe) * P(Vomissement=Très fréquent|Classe) (hypothèse d'indépendance des caractéristiques).

Probabilités a priori :

P(Non) = 6/9
P(Oui) = 3/9

Probabilités conditionnelles (sans l'estimateur de Laplace) :

P(MdT = Oui|Non) = 2/6
P(Vom = T. freq|Non) = 0
P(MdT = Oui|Oui) = 0
P(Vom = T. freq|Oui) = 1/3

Calcul des probabilités de température (P(Température=40|Classe)) en utilisant une distribution normale :

Pour la classe 'Non' : moyenne (μ_Non) = 38,5, variance (σ²_Non) = 4,91
P(Température = 40|Non) ≈ 0,09528
Pour la classe 'Oui' : moyenne (μ_Oui) = 43, variance (σ²_Oui) = 0,67
P(Température = 40|Oui) ≈ 0,02432

Calcul de P(Non|X) et P(Oui|X) :

P(Non|X) ∝ P(MdT=Oui|Non) * P(Vom=T.freq|Non) * P(Temp=40|Non) * P(Non)

P(Non|X) ∝ (2/6) * 0 * 0,09528 * (6/9) = 0

P(Oui|X) ∝ P(MdT=Oui|Oui) * P(Vom=T.freq|Oui) * P(Temp=40|Oui) * P(Oui)

P(Oui|X) ∝ 0 * (1/3) * 0,02432 * (3/9) = 0

Puisque les deux probabilités P(Non|X) et P(Oui|X) sont nulles, le classifieur Naive Bayes ne peut pas prendre de décision dans ce cas.

Application de l'estimateur de Laplace pour remédier aux probabilités nulles

L'estimateur de Laplace (lissage de Laplace) ajoute 1 au numérateur et le nombre de catégories (k) au dénominateur pour chaque probabilité conditionnelle, évitant ainsi les zéros.

Nombre d'instances 'Non' = 6
Nombre d'instances 'Oui' = 3

Exemples de correction avec l'estimateur de Laplace (en supposant 2 catégories pour chaque caractéristique) :

P(MdT = Oui|Oui)_Laplace = (0 + 1) / (3 + 2) = 1/5
P(Vom = T. Freq|Non)_Laplace = (0 + 1) / (6 + 2) = 1/8

En recalculant avec ces valeurs lissées et les autres probabilités inchangées, il est déterminé que P(Non|X) > P(Oui|X).

Conclusion : Après application de l'estimateur de Laplace, Naive Bayes prédit que le nouveau patient n'est pas atteint de méningite.

2. Évaluation du modèle de Bayes

Le modèle de Bayes a fourni les prédictions suivantes pour neuf patients :

Predit : Non, Non, Non, Non, Non, Oui, Oui, Oui, Non

Réel (Attendu) : Non, Non, Non, Oui, Non, Oui, Non, Oui, Oui

Matrice de confusion :

	Prédit Positif (Oui)	Prédit Négatif (Non)
Réel Positif (Oui)	2 (Vrais Positifs - TP)	2 (Faux Négatifs - FN)
Réel Négatif (Non)	1 (Faux Positifs - FP)	4 (Vrais Négatifs - TN)

La précision (Accuracy) du modèle sur les données d'apprentissage est calculée comme :

Accuracy = (TP + TN) / (TP + TN + FP + FN)

Accuracy = (2 + 4) / (2 + 4 + 1 + 2) = 6 / 9 ≈ 0,667

FAQ sur le Data Mining

Qu'est-ce que l'entropie en Data Mining et pourquoi est-elle utilisée ?

En Data Mining, l'entropie est une mesure du désordre ou de l'incertitude dans un ensemble de données. Elle est couramment utilisée dans les algorithmes d'arbres de décision pour déterminer l'efficacité d'une division de données. Un gain d'information élevé, calculé à partir de la réduction de l'entropie, indique une division plus utile pour la classification ou la prédiction.

Pourquoi l'estimateur de Laplace est-il important dans le classifieur Naive Bayes ?

L'estimateur de Laplace, ou lissage de Laplace, est crucial dans le classifieur Naive Bayes pour éviter le problème des probabilités nulles. Si une caractéristique observée dans les données de test n'apparaît jamais avec une classe donnée dans les données d'entraînement, la probabilité conditionnelle de cette caractéristique pour cette classe serait de zéro, ce qui annulerait le produit de toutes les probabilités et empêcherait toute classification. Le lissage de Laplace ajoute une petite valeur (souvent 1) aux comptes de chaque caractéristique et classe, assurant ainsi que toutes les probabilités restent non nulles.

Quels sont les principaux cas d'utilisation de l'algorithme Naive Bayes ?

L'algorithme Naive Bayes est un classifieur simple mais efficace, particulièrement adapté aux grands ensembles de données. Ses principaux cas d'utilisation incluent :

Filtrage de spam : Classifier les e-mails comme spam ou non-spam.
Analyse de sentiments : Déterminer le sentiment (positif, négatif, neutre) d'un texte.
Classification de documents : Catégoriser des documents texte en différentes rubriques.
Systèmes de recommandation : Prédire les préférences des utilisateurs.
Diagnostic médical : Aider au diagnostic de maladies basé sur un ensemble de symptômes.