Ce document pédagogique constitue le corrigé d'un examen du module de Data Mining, destiné aux étudiants universitaires de niveau Master II en Informatique. Il vise à approfondir la compréhension des méthodes essentielles utilisées dans l'exploration de données, en offrant des solutions détaillées aux problèmes posés.
Il couvre les notions principales suivantes :
- L'extraction de règles d'association fortes et leur interprétation.
- L'Analyse en Composantes Principales (ACP) normée, incluant l'analyse des valeurs et vecteurs propres, la qualité de représentation des variables et des individus, et l'interprétation des axes factoriels.
Examen 2016-2017 Data Mining
Télécharger PDFExercices Corrigés de Data Mining : Règles d'Association et ACP Normée
Cet ensemble d'exercices corrigés en Data Mining, issu d'une évaluation pour Master II, couvre des concepts fondamentaux tels que les règles d'association et l'analyse en composantes principales (ACP) normée. Il a été conçu pour le module de Data Mining de l'UMBBoumerdes, Faculté des Sciences, Département d'Informatique.
Exercice 1 : Règles d'Association avec l'Algorithme Apriori
Énoncé de l'exercice
Transactions de Livres
Considérons les transactions suivantes :
- T1: L1, L2, L5
- T2: L2, L3
- T3: L1, L2, L4
- T4: L1, L3
- T5: L2, L3
- T6: L1, L3
- T7: L1, L2, L3, L5
- T8: L1, L2, L3
Questions
- Extraire tous les ensembles de livres fréquemment achetés ensemble, avec un support minimum (min_sup) de 2 (ou 2/8 transactions) et une confiance minimale (min_conf) de 70%.
- Déduire les règles d'association fortes composées d'un seul livre comme antécédent et de deux livres comme conclusion.
- Interpréter l'une des règles trouvées à la question 2.
Corrigé de l'Exercice 1
1. Extraction des ensembles d'items fréquents (min_sup = 2)
Les étapes de l'algorithme Apriori sont appliquées pour trouver les itemsets fréquents.
- Itemsets de taille 1 (F1):
- {L1}: Support = 6
- {L2}: Support = 6
- {L3}: Support = 6
- {L5}: Support = 2
- Itemsets de taille 2 (F2):
- {L1, L2}: Support = 4
- {L1, L3}: Support = 4
- {L1, L5}: Support = 2
- {L2, L3}: Support = 4
- {L2, L5}: Support = 2
- Itemsets de taille 3 (F3):
- {L1, L2, L3}: Support = 2
- {L1, L2, L5}: Support = 2
Après élimination des itemsets non fréquents et calcul des supports :
Après élimination des itemsets non fréquents et calcul des supports :
Les ensembles de livres fréquemment achetés ensemble (itemsets fréquents) sont ceux dont le support est d'au moins 2.
2. Déduction des règles d'association fortes (antécédent unique, conclusion double)
Le support minimum est de 2, et la confiance minimale est de 70%. Nous cherchons des règles de la forme {Item} → {Item1, Item2}.
- Règle 1: {L1} → {L2, L3}
- Règle 2: {L2} → {L1, L3}
- Règle 3: {L3} → {L1, L2}
- Règle 4: {L1} → {L2, L5}
- Règle 5: {L2} → {L1, L5}
- Règle 6: {L5} → {L1, L2}
Support({L1, L2, L3}) = 2. Support({L1}) = 6. Confiance = 2/6 ≈ 33.3% (Non forte)
Support({L1, L2, L3}) = 2. Support({L2}) = 6. Confiance = 2/6 ≈ 33.3% (Non forte)
Support({L1, L2, L3}) = 2. Support({L3}) = 6. Confiance = 2/6 ≈ 33.3% (Non forte)
Support({L1, L2, L5}) = 2. Support({L1}) = 6. Confiance = 2/6 ≈ 33.3% (Non forte)
Support({L1, L2, L5}) = 2. Support({L2}) = 6. Confiance = 2/6 ≈ 33.3% (Non forte)
Support({L1, L2, L5}) = 2. Support({L5}) = 2. Confiance = 2/2 = 100% (Forte)
La seule règle d'association forte trouvée avec un antécédent unique et une conclusion double est : {L5} → {L1, L2}.
3. Interprétation de la règle forte
Pour la règle {L5} → {L1, L2} :
- Support (25%) : 25% des transactions totales contiennent les livres L1, L2 et L5.
- Confiance (100%) : 100% des clients qui ont acheté le livre L5 ont également acheté les livres L1 et L2.
Cela signifie que si un client achète le livre L5, il est certain qu'il achètera aussi les livres L1 et L2. C'est une information très utile pour les recommandations ou le placement de produits.
Exercice 2 : Analyse en Composantes Principales (ACP) Normée
Énoncé de l'exercice
Une étude vise à évaluer l'attractivité économique de 20 régions. Pour chaque région, 7 indicateurs économiques (variables) sont collectés :
- X1: POP (Population en milliers)
- X2: TAC (Taux d'activité)
- X3: SUP (Superficie en Km²)
- X4: NEN (Nombre d'entreprises)
- X5: NBR (Nombre de brevets)
- X6: CHO (Taux de chômage)
- X7: NTE (Nombre de lignes téléphoniques)
Un tableau de données (20 régions × 7 indicateurs) est soumis à une ACP Normée. Les informations suivantes sont fournies :
- Quatre premières valeurs propres : λ1 = 4.157, λ2 = 1.898, λ3 = 0.594, λ4 = 0.204.
Coordonnées des projections des régions et des variables sur les deux premiers axes
Les tableaux suivants présentent les coordonnées pour les 20 régions (R1-R20) et les 7 variables (X1-X7) sur les deux premiers axes factoriels (F1 et F2).
Tableau 1: Coordonnées des projections des régions sur les deux premiers axes
| Région | F1 | F2 | Région | F1 | F2 |
|---|---|---|---|---|---|
| R1 | 0.847 | 1.407 | R11 | 0.060 | -2.124 |
| R2 | 0.609 | -0.148 | R12 | -1.180 | 0.553 |
| R3 | -0.619 | 0.153 | R13 | -0.206 | -0.470 |
| R4 | -0.805 | 0.362 | R14 | 0.418 | 0.360 |
| R5 | -0.391 | 0.741 | R15 | 0.624 | -2.268 |
| R6 | 0.336 | -0.124 | R16 | 0.467 | 0.224 |
| R7 | 0.117 | 0.945 | R17 | -0.530 | 0.807 |
| R8 | 0.737 | 0.251 | R18 | -0.448 | -0.233 |
| R9 | -0.988 | 0.588 | R19 | 1.772 | -0.829 |
| R10 | -0.623 | -0.342 | R20 | 2.972 | 1.759 |
Tableau 2: Coordonnées des variables sur les deux premiers axes
| Variable | G1 (F1) | G2 (F2) |
|---|---|---|
| X1 | -0.15 | 0.85 |
| X2 | 0.65 | 0.22 |
| X3 | 0.96 | -0.10 |
| X4 | 0.85 | 0.40 |
| X5 | 0.10 | -0.97 |
| X6 | 0.96 | -0.18 |
| X7 | 0.96 | -0.25 |
Questions
- Parmi les méthodes factorielles, pourquoi l'ACP normée a-t-elle été choisie pour cette analyse ?
- Quelle est la matrice à diagonaliser dans ce cas (notée R) ? Décrire cette matrice.
- Déterminer les deux premiers vecteurs propres de R.
- Combien de facteurs peut-on prendre pour récupérer au moins 94% de l'information initiale ?
- Quelles sont les variables les mieux représentées par l'axe 1, par l'axe 2, et par le plan (1,2) ?
- Quelles sont les 6 régions ayant le plus contribué à l'explication de l'axe 1 et à l'axe 2 ?
- Décrire l'intérêt d'une représentation simultanée des individus (régions) et des variables sur le premier plan factoriel.
- Faire une interprétation des axes en résumant les informations extraites des données.
Corrigé de l'Exercice 2
1. Justification du choix de l'ACP Normée
L'ACP Normée a été choisie car les données (attributs) sont toutes quantitatives et continues, mais elles sont exprimées dans des unités de mesure hétérogènes (milliers, %, Km², etc.). La normalisation permet de donner un poids égal à chaque variable, évitant que celles ayant les plus grandes échelles ne dominent l'analyse.
2. Matrice à diagonaliser
La matrice à diagonaliser dans ce cas est la matrice des corrélations (R). C'est une matrice symétrique dont les éléments diagonaux sont forcément égaux à 1 (corrélation d'une variable avec elle-même). Elle décrit la structure des dépendances linéaires entre toutes les variables.
3. Détermination des deux premiers vecteurs propres
Les vecteurs propres (U) sont liés aux coordonnées des variables (G) et aux valeurs propres (λ) par la relation U = G / √λ.
En utilisant les données du Tableau 2 et les valeurs propres λ1 = 4.157 et λ2 = 1.898 :
- U1 (associé à λ1):
- U2 (associé à λ2):
U1 = (-0.15/√4.157, 0.65/√4.157, 0.96/√4.157, 0.85/√4.157, 0.10/√4.157, 0.96/√4.157, 0.96/√4.157)
U1 ≈ (-0.073, 0.319, 0.470, 0.417, 0.049, 0.470, 0.470)
U2 = (0.85/√1.898, 0.22/√1.898, -0.10/√1.898, 0.40/√1.898, -0.97/√1.898, -0.18/√1.898, -0.25/√1.898)
U2 ≈ (0.617, 0.159, -0.073, 0.290, -0.704, -0.130, -0.181)
4. Nombre de facteurs pour récupérer l'information initiale
Le pourcentage cumulé d'information récupérée par les axes est calculé à partir des valeurs propres :
- Total des valeurs propres (variance totale) = λ1 + λ2 + λ3 + λ4 + ... = 4.157 + 1.898 + 0.594 + 0.204 + ... (Pour 7 variables, il y a 7 valeurs propres)
- Puisque c'est une matrice de corrélation (variables centrées réduites), la somme des valeurs propres est égale au nombre de variables, soit 7.
- Pourcentage d'inertie du plan (1,2) = (λ1 + λ2) / Somme(λi) = (4.157 + 1.898) / 7 = 6.055 / 7 ≈ 86.5%.
- Puisque l'on cherche à récupérer au moins 94% de l'information initiale, nous devons considérer le cumul des valeurs propres.
- % cumulé des 3 premiers facteurs = (λ1 + λ2 + λ3) / 7 = (4.157 + 1.898 + 0.594) / 7 = 6.649 / 7 ≈ 94.98%.
Donc, 3 axes suffisent pour récupérer plus de 94% de l'information initiale.
5. Variables les mieux représentées
La qualité de représentation d'une variable Xj par l'axe k est donnée par g²(j,k), qui est le carré de sa coordonnée sur l'axe k. Pour le plan (1,2), c'est la somme g²(j,1) + g²(j,2).
Calculons les qualités de représentation (g²(j,k)) à partir du Tableau 2:
| Variable | g²(j,1) | g²(j,2) | g²(j,1)+g²(j,2) |
|---|---|---|---|
| X1 | 0.0225 | 0.7225 | 0.745 |
| X2 | 0.4225 | 0.0484 | 0.4709 |
| X3 | 0.9216 | 0.0100 | 0.9316 |
| X4 | 0.7225 | 0.1600 | 0.8825 |
| X5 | 0.0100 | 0.9409 | 0.9509 |
| X6 | 0.9216 | 0.0324 | 0.9540 |
| X7 | 0.9216 | 0.0625 | 0.9841 |
- Mieux représentées par l'axe 1 : X3 (Superficie), X6 (Taux de chômage), X7 (Nombre de lignes téléphoniques) et X4 (Nombre d'entreprises).
- Mieux représentées par l'axe 2 : X1 (Population) et X5 (Nombre de brevets).
- Mieux représentées par le plan (1,2) : X7 (Nombre de lignes téléphoniques), X6 (Taux de chômage), X5 (Nombre de brevets), X3 (Superficie) et X4 (Nombre d'entreprises).
6. Régions ayant le plus contribué à l'explication des axes
La contribution d'un individu (région) i à la variance d'un axe k est proportionnelle au carré de sa coordonnée sur cet axe. Les régions ayant les plus grandes coordonnées en valeur absolue contribuent le plus.
- Contributions à l'Axe 1 : Les 6 régions ayant les plus grandes valeurs absolues sur F1 sont :
- R20 (2.972)
- R19 (1.772)
- R12 (-1.180)
- R9 (-0.988)
- R1 (0.847)
- R4 (-0.805)
- Contributions à l'Axe 2 : Les 6 régions ayant les plus grandes valeurs absolues sur F2 sont :
- R15 (-2.268)
- R11 (-2.124)
- R20 (1.759)
- R1 (1.407)
- R7 (0.945)
- R19 (-0.829)
7. Représentation simultanée des individus et des variables
Une représentation simultanée (biplot) sur le premier plan factoriel (Axe 1, Axe 2) permet de visualiser les proximités entre les régions et les corrélations entre les variables. Elle met en évidence les groupes de régions similaires et les variables qui les caractérisent. Les régions proches des variables fortement corrélées à un axe sont bien expliquées par ces variables.
Avec un taux d'inertie de plus de 86% pour le plan (1,2), cette représentation est fiable et montre bien les relations entre régions et variables.
8. Interprétation des axes factoriels
- Interprétation de l'Axe 1 : L'axe de la structure et taille économique
Cet axe est fortement corrélé positivement avec la Superficie (X3), le Taux de chômage (X6), le Nombre de lignes téléphoniques (X7), le Nombre d'entreprises (X4) et le Taux d'activité (X2). Il différencie les régions selon leur taille, leur niveau d'industrialisation et d'infrastructure. Les régions avec des valeurs élevées sur cet axe (comme R20 et R19) tendent à être de grandes régions avec une forte activité économique, un nombre élevé d'entreprises et d'infrastructures, mais potentiellement aussi un taux de chômage significatif qui peut être lié à une grande population active. Elles s'opposent aux régions de faibles valeurs sur cet axe (comme R9 et R12).
- Interprétation de l'Axe 2 : L'axe de la démographie et de l'innovation
Cet axe est fortement corrélé positivement avec la Population (X1) et fortement corrélé négativement avec le Nombre de brevets (X5). Il oppose les régions à forte population et faible innovation (valeurs positives sur l'axe 2, ex: R1) aux régions à faible population et forte capacité d'innovation (valeurs négatives sur l'axe 2, ex: R11, R15). Cela suggère une distinction entre des régions plus orientées vers une croissance démographique et d'autres vers la recherche et le développement.
FAQ sur le Data Mining et l'Analyse Factorielle
Qu'est-ce qu'une règle d'association en Data Mining ?
Une règle d'association est une expression de la forme "Si A alors B" (A → B), qui identifie des relations fortes entre des variables dans de grands ensembles de données. Par exemple, "si un client achète du pain et du lait, alors il est probable qu'il achète aussi du beurre". Elles sont caractérisées par leur support (fréquence d'apparition de A et B ensemble) et leur confiance (probabilité que B se produise quand A se produit).
Pourquoi utiliser l'ACP Normée plutôt qu'une ACP standard ?
L'ACP Normée est privilégiée lorsque les variables d'un jeu de données sont exprimées dans des unités de mesure différentes ou ont des échelles de variation très différentes. En normalisant les données (souvent par centrage et réduction), toutes les variables contribuent de manière égale à l'analyse, évitant que les variables avec les plus grandes variances n'influencent excessivement les premiers axes principaux.
Comment interpréter les axes principaux d'une ACP ?
L'interprétation des axes principaux se fait en examinant les corrélations des variables avec chaque axe. Les variables qui sont fortement corrélées (positivement ou négativement) à un axe donnent son sens. Un axe peut représenter un concept sous-jacent (par exemple, "taille économique", "développement", "innovation") qui résume une grande partie de la variabilité des données d'origine.