Ce document académique est un examen de rattrapage en Data Mining, spécifiquement destiné aux étudiants de la Faculté des Sciences, Département d'Informatique de l'UMBBoumerdes. Il a pour objectif d'évaluer leur maîtrise des concepts clés et des techniques fondamentales de l'exploration de données.
Le document couvre les notions suivantes :
- Les principales tâches du Data Mining, incluant la classification et la détection d'intrusion.
- L'algorithme de la descente de gradient et ses applications en optimisation.
- L'extraction et l'interprétation des règles d'association à partir de données transactionnelles.
Examen de Rattrapage Data Mining
Télécharger PDFExamen de Rattrapage Data Mining
Université M'hamed Bougara de Boumerdès - Faculté des Sciences - Département d'Informatique
Cet examen de rattrapage en Data Mining se compose de deux parties principales : des questions théoriques et un exercice pratique. Le barème est réparti comme suit : 10 points pour les questions et 10 points pour l'exercice.
Questions (10 points)
1. On veut construire un système de détection d'intrusion dans les réseaux. Quelles sont les tâches de Data Mining pouvant jouer un rôle pour l'efficacité d'un tel système ?
Pour la construction d'un système de détection d'intrusion, plusieurs tâches de fouille de données sont particulièrement pertinentes :
- Classification : Pour catégoriser les activités réseau en "normales" ou "intrusives" en se basant sur des modèles appris à partir de données historiques.
- Clustering (Regroupement) : Pour identifier des comportements réseau anormaux ou de nouvelles formes d'intrusion non prévues, en regroupant les données similaires et en détectant des clusters inhabituels.
- Détection d'Anomalies : Spécifiquement conçue pour repérer les points de données qui s'écartent significativement de la norme, ce qui est essentiel pour signaler une potentielle intrusion.
- Règles d'Association : Pour découvrir des corrélations et des séquences d'événements fréquents dans le trafic réseau, ce qui peut aider à identifier des schémas d'attaque connus ou émergents.
2. Donnez un exemple d'application de la tâche de classification, le modèle de représentation des connaissances extraites et la technique (ou les techniques) applicable(s) à la tâche correspondante.
- Exemple d'application : La détection de spams dans les emails, où chaque email est classifié comme "spam" ou "non-spam" (ham).
- Modèle de représentation des connaissances :
- Arbre de décision : Les règles de classification sont structurées comme un arbre, où chaque nœud représente un test sur un attribut et les feuilles indiquent la classe prédite.
- Réseau de neurones : Les connaissances sont encodées dans les poids des connexions entre les neurones, permettant d'apprendre des relations complexes entre les entrées et les sorties.
- Machine à Vecteurs de Support (SVM) : Le modèle construit un hyperplan optimal dans un espace de grande dimension pour séparer les différentes classes.
- Techniques applicables : Algorithmes d'arbres de décision (C4.5, CART), Naive Bayes, K-plus proches voisins (KNN), Réseaux de neurones, Machines à vecteurs de support (SVM), régression logistique, etc.
3. Décrire l'algorithme de la descente de gradient en spécifiant tous ses paramètres.
La descente de gradient est un algorithme d'optimisation itératif largement utilisé en apprentissage automatique pour minimiser une fonction de coût (ou fonction d'erreur) en ajustant les paramètres d'un modèle. Il fonctionne en prenant des pas proportionnels à l'opposé du gradient de la fonction à chaque itération. Ses principaux paramètres sont :
- Fonction de coût (J ou L) : C'est la fonction que l'algorithme cherche à minimiser. Elle quantifie l'erreur entre les prédictions du modèle et les valeurs réelles observées. Pour la régression linéaire, l'erreur quadratique moyenne (MSE) est souvent utilisée.
- Paramètres du modèle (θ) : Ce sont les variables du modèle que l'algorithme ajuste à chaque itération pour minimiser la fonction de coût. Dans une régression linéaire simple, ces paramètres sont θ₀ (l'ordonnée à l'origine) et θ₁ (la pente).
- Taux d'apprentissage (α ou η) : Il s'agit d'un hyperparamètre crucial qui détermine la taille de chaque pas effectué dans la direction opposée au gradient. Un taux d'apprentissage trop élevé peut entraîner une divergence de l'algorithme, tandis qu'un taux trop faible peut rendre la convergence extrêmement lente.
- Gradient (∇J(θ)) : Le gradient est un vecteur de dérivées partielles de la fonction de coût par rapport à chacun des paramètres du modèle. Il indique la direction de la plus forte pente (augmentation) de la fonction de coût. La descente de gradient se déplace donc dans la direction opposée.
- Nombre d'itérations : Il spécifie le nombre de fois où l'algorithme va mettre à jour les paramètres. Alternativement, un critère de convergence peut être utilisé, comme s'arrêter lorsque la diminution de la fonction de coût devient inférieure à un certain seuil.
- Initialisation des paramètres (θ_initial) : Les valeurs de départ assignées aux paramètres du modèle. Une bonne initialisation peut influencer la vitesse de convergence et la capacité de l'algorithme à trouver un minimum global ou un bon minimum local.
La formule de mise à jour des paramètres pour chaque θj est la suivante :
θj := θj - α * ∂J(θ) / ∂θj
4. Supposons que nous utilisions la descente de gradient pour essayer de minimiser une fonction quelconque f(θ₀, θ₁) en fonction de θ₀ et θ₁. Parmi les affirmations suivantes, lesquelles sont vraies ?
- A. Si θ₀ et θ₁ sont initialisés au minimum global, alors une itération ne changera pas leurs valeurs.
VRAI. Au minimum (local ou global) d'une fonction, le gradient est nul. Par conséquent, l'étape de mise à jour des paramètres (θj := θj - α * ∇J(θ)j) ne produira aucun changement si le gradient est égal à zéro. - B. Fixer un taux d'apprentissage très faible n'est pas nocif, et ne peut qu'accélérer la convergence de la descente de gradient.
FAUX. Un taux d'apprentissage très faible n'est pas directement "nocif" dans le sens où il ne fera généralement pas diverger l'algorithme. Cependant, il peut entraîner une convergence extrêmement lente, augmentant considérablement le temps de calcul nécessaire pour atteindre le minimum, ou même l'empêcher d'atteindre le minimum dans un nombre raisonnable d'itérations. - C. Peu importe comment θ₀ et θ₁ sont initialisés, tant que le taux d'apprentissage est suffisamment petit, on peut s'attendre à ce que la descente de gradient converge vers la même solution.
FAUX. Cette affirmation n'est vraie que si la fonction de coût est convexe (n'a qu'un seul minimum global). Pour les fonctions non convexes (qui possèdent plusieurs minima locaux), le point d'initialisation des paramètres est crucial. La descente de gradient convergera vers le minimum local le plus proche du point de départ, qui n'est pas nécessairement le même pour toutes les initialisations. - D. Si les premières itérations de descente de gradient provoquent une augmentation de f(θ₀, θ₁) plutôt qu'une diminution, la cause la plus probable est que nous avons défini une valeur du taux d'apprentissage trop élevée.
VRAI. Un taux d'apprentissage trop élevé peut faire "sauter" l'algorithme par-dessus le minimum et le faire osciller ou même diverger, entraînant une augmentation de la fonction de coût à chaque pas au lieu d'une diminution. C'est un signe clair que le pas est trop grand.
5. Supposons que pour un problème de régression linéaire, on a réussi à trouver certaines valeurs de θ₀ et θ₁ telles que la fonction coût J(θ₀, θ₁) = 0. Lesquelles des affirmations ci-dessous sont vraies ? (Cochez tout ce qui s'applique.)
- A. La descente de gradient est susceptible de rester bloquée à un minimum local et de ne pas trouver le minimum global.
FAUX. Pour la régression linéaire utilisant l'erreur quadratique moyenne (MSE) comme fonction de coût, la fonction de coût est toujours convexe. Cela signifie qu'il n'y a qu'un seul minimum (qui est donc le minimum global). Par conséquent, la descente de gradient (avec un taux d'apprentissage approprié) convergera toujours vers ce minimum global. - B. Pour que cela soit vrai, nous devons avoir θ₀ = 0 et θ₁ = 0 de sorte que hθ(x) = 0.
FAUX. Si J(θ₀, θ₁) = 0, cela signifie que le modèle de régression linéaire hθ(x) = θ₀ + θ₁x prédit parfaitement les valeurs cibles (c'est-à-dire hθ(x(i)) = y(i) pour tous les exemples). Cela n'implique absolument pas que θ₀ et θ₁ doivent être nuls, mais plutôt qu'ils ont des valeurs spécifiques qui permettent à la droite de régression de passer exactement par tous les points de données. - C. Pour que cela soit vrai, nous devons avoir y(i) = 0 pour chaque valeur de i = 1, 2,...,m.
FAUX. Une fonction de coût égale à zéro signifie que hθ(x(i)) = y(i) pour tous les exemples d'apprentissage. Cela signifie une prédiction parfaite, mais n'impose pas que les valeurs cibles y(i) soient toutes nulles. Elles peuvent être n'importe quelle valeur réelle, tant que le modèle est capable de les prédire sans erreur. - D. Notre ensemble d'apprentissage peut être parfaitement ajusté par une ligne droite, c'est-à-dire que tous nos exemples d'apprentissage reposent parfaitement sur une ligne droite.
VRAI. Si la fonction de coût (qui est une mesure de l'erreur) est nulle, cela signifie qu'il n'y a absolument aucune erreur entre les prédictions du modèle et les valeurs réelles. Pour une régression linéaire, cela implique que la droite de régression passe exactement par tous les points de données de l'ensemble d'apprentissage, signifiant qu'ils sont parfaitement alignés.
EXERCICE (10 points)
Un site de vente en ligne propose, entre autres, des livres. En effectuant une recherche sur un livre particulier, il vous affiche les livres qui sont fréquemment achetés ensemble avec le livre recherché. Ce mécanisme est basé sur l'analyse des transactions d'achat.
Transactions d'achat de livres (Trans. Livres)
Voici le tableau des transactions pour l'achat de livres :
| Transaction (ID) | Livres achetés |
|---|---|
| T1 | L2, L4 |
| T2 | L1, L2, L3 |
| T3 | L1, L2, L5 |
| T4 | L2, L3 |
| T5 | L1, L2, L4 |
| T6 | L1, L3 |
| T7 | L2, L3 |
| T8 | L1, L2, L3, L5 |
| T9 | L1, L3 |
1. Quelle est la tâche de Data Mining la plus appropriée utilisée par le site Web pour nous livrer cette information ?
La tâche de Data Mining la plus appropriée pour identifier les livres fréquemment achetés ensemble est la découverte de règles d'association (ou l'analyse des paniers d'achats). Cette technique permet de trouver des relations significatives et des dépendances fréquentes entre différents articles dans un ensemble de transactions.
2. Sur la base des transactions portant sur les achats des livres, extraire tous les ensembles de livres fréquemment achetés ensemble (min_sup = 2 ou 2/9).
Nous allons extraire tous les itemsets (ensembles de livres) fréquents en utilisant l'algorithme Apriori avec un support minimum (min_sup) de 2 transactions.
Étape 1 : Calcul du support des Itemsets à 1 item
- {L1} : présent dans {T2, T3, T5, T6, T8, T9} → Support = 6
- {L2} : présent dans {T1, T2, T3, T4, T5, T7, T8} → Support = 7
- {L3} : présent dans {T2, T4, T6, T7, T8, T9} → Support = 6
- {L4} : présent dans {T1, T5} → Support = 2
- {L5} : présent dans {T3, T8} → Support = 2
Tous les itemsets à 1 item ({L1}, {L2}, {L3}, {L4}, {L5}) sont fréquents car leur support est supérieur ou égal à 2.
Étape 2 : Calcul du support des Itemsets à 2 items (candidats générés à partir des itemsets fréquents à 1 item)
- {L1, L2} : {T2, T3, T5, T8} → Support = 4 (Fréquent)
- {L1, L3} : {T2, T6, T8, T9} → Support = 4 (Fréquent)
- {L1, L4} : {T5} → Support = 1 (Non Fréquent - éliminé)
- {L1, L5} : {T3, T8} → Support = 2 (Fréquent)
- {L2, L3} : {T2, T4, T7, T8} → Support = 4 (Fréquent)
- {L2, L4} : {T1, T5} → Support = 2 (Fréquent)
- {L2, L5} : {T3, T8} → Support = 2 (Fréquent)
- {L3, L4} : {} → Support = 0 (Non Fréquent - éliminé)
- {L3, L5} : {T8} → Support = 1 (Non Fréquent - éliminé)
- {L4, L5} : {} → Support = 0 (Non Fréquent - éliminé)
Les itemsets fréquents à 2 items sont : {L1, L2}, {L1, L3}, {L1, L5}, {L2, L3}, {L2, L4}, {L2, L5}.
Étape 3 : Calcul du support des Itemsets à 3 items (candidats générés à partir des itemsets fréquents à 2 items)
- {L1, L2, L3} : {T2, T8} → Support = 2 (Fréquent)
- {L1, L2, L4} : {T5} → Support = 1 (Non Fréquent - éliminé)
- {L1, L2, L5} : {T3, T8} → Support = 2 (Fréquent)
- {L1, L3, L5} : {T8} → Support = 1 (Non Fréquent - éliminé)
- {L2, L3, L4} : {} → Support = 0 (Non Fréquent - éliminé)
- {L2, L3, L5} : {T8} → Support = 1 (Non Fréquent - éliminé)
Les itemsets fréquents à 3 items sont : {L1, L2, L3}, {L1, L2, L5}.
Étape 4 : Calcul du support des Itemsets à 4 items (candidats générés à partir des itemsets fréquents à 3 items)
- {L1, L2, L3, L5} : {T8} → Support = 1 (Non Fréquent - éliminé)
Il n'y a pas d'itemsets fréquents à 4 items ou plus.
Liste finale des ensembles de livres fréquemment achetés ensemble (itemsets fréquents) :
- Itemsets à 1 item : {L1} (Sup=6), {L2} (Sup=7), {L3} (Sup=6), {L4} (Sup=2), {L5} (Sup=2)
- Itemsets à 2 items : {L1, L2} (Sup=4), {L1, L3} (Sup=4), {L1, L5} (Sup=2), {L2, L3} (Sup=4), {L2, L4} (Sup=2), {L2, L5} (Sup=2)
- Itemsets à 3 items : {L1, L2, L3} (Sup=2), {L1, L2, L5} (Sup=2)
3. Quel est le nombre maximum de règles d'association qu'on peut extraire de cette base de transactions ?
Pour un itemset fréquent de k items, il est possible de générer 2k - 2 règles d'association (en excluant l'itemset lui-même et l'ensemble vide comme antécédent ou conséquent).
Calculons le nombre maximum de règles à partir des itemsets fréquents identifiés :
- Pour chaque itemset fréquent à 2 items (il y en a 6 : {L1, L2}, {L1, L3}, {L1, L5}, {L2, L3}, {L2, L4}, {L2, L5}) :
Nombre de règles = 22 - 2 = 4 - 2 = 2 règles par itemset. Total = 6 * 2 = 12 règles. - Pour chaque itemset fréquent à 3 items (il y en a 2 : {L1, L2, L3}, {L1, L2, L5}) :
Nombre de règles = 23 - 2 = 8 - 2 = 6 règles par itemset. Total = 2 * 6 = 12 règles.
Le nombre total maximum de règles d'association que l'on peut extraire de cette base de transactions, en se basant sur les itemsets fréquents trouvés, est de 12 + 12 = 24 règles.
4. Déduire les règles d'association fortes (min_conf = 70%) composées de deux items comme antécédent et un item comme conséquence.
Nous recherchons des règles de la forme {A, B} -> {C}, où {A, B, C} doit être un itemset fréquent à 3 items. Les itemsets fréquents à 3 items sont : {L1, L2, L3} (Support=2) et {L1, L2, L5} (Support=2).
Pour l'itemset {L1, L2, L3} (Support = 2) :
- Règle : {L1, L2} -> {L3}
Confiance = Support({L1, L2, L3}) / Support({L1, L2}) = 2 / 4 = 0.5 (50%) -> Non forte (inférieure à 70%) - Règle : {L1, L3} -> {L2}
Confiance = Support({L1, L2, L3}) / Support({L1, L3}) = 2 / 4 = 0.5 (50%) -> Non forte - Règle : {L2, L3} -> {L1}
Confiance = Support({L1, L2, L3}) / Support({L2, L3}) = 2 / 4 = 0.5 (50%) -> Non forte
Pour l'itemset {L1, L2, L5} (Support = 2) :
- Règle : {L1, L2} -> {L5}
Confiance = Support({L1, L2, L5}) / Support({L1, L2}) = 2 / 4 = 0.5 (50%) -> Non forte - Règle : {L1, L5} -> {L2}
Confiance = Support({L1, L2, L5}) / Support({L1, L5}) = 2 / 2 = 1.0 (100%) -> Forte (supérieure ou égale à 70%) - Règle : {L2, L5} -> {L1}
Confiance = Support({L1, L2, L5}) / Support({L2, L5}) = 2 / 2 = 1.0 (100%) -> Forte (supérieure ou égale à 70%)
Les règles d'association fortes (avec une confiance minimale de 70%) avec deux items comme antécédent et un item comme conséquence sont :
- {L1, L5} -> {L2} (Confiance = 100%)
- {L2, L5} -> {L1} (Confiance = 100%)
5. Interpréter l'une des règles découvertes.
Interprétons la règle : {L1, L5} -> {L2} avec une Confiance de 100%.
Cette règle signifie que, dans les transactions enregistrées, chaque fois que les livres L1 et L5 sont achetés ensemble, le livre L2 est également acheté systématiquement dans la même transaction. Il y a une probabilité de 100% que l'achat de L1 et L5 entraîne l'achat de L2.
Pour un site de vente en ligne, cette règle est très pertinente. Par exemple, si un client ajoute les livres L1 et L5 à son panier, le site peut fortement recommander ou même inclure automatiquement le livre L2, sachant que cette association est extrêmement fiable. Cela peut augmenter les ventes, améliorer l'expérience client et optimiser les stratégies de merchandising.
Foire Aux Questions (FAQ)
Qu'est-ce que le Data Mining et à quoi sert-il ?
Le Data Mining, ou fouille de données, est le processus d'extraction de modèles, de tendances et de connaissances exploitables à partir de grands ensembles de données. Il combine des techniques issues de l'apprentissage automatique, des statistiques et des systèmes de bases de données. Son objectif principal est d'aider les organisations à prendre de meilleures décisions en transformant des données brutes en informations précieuses, par exemple pour la prédiction de comportements, la détection de fraudes ou la personnalisation de services.
Quelle est l'importance du taux d'apprentissage dans la descente de gradient ?
Le taux d'apprentissage (learning rate) est un paramètre crucial dans l'algorithme de descente de gradient. Il détermine la taille des pas effectués à chaque itération pour se rapprocher du minimum de la fonction de coût. Un taux d'apprentissage trop élevé peut faire "sauter" l'algorithme par-dessus le minimum et le faire diverger, tandis qu'un taux trop faible ralentira considérablement la convergence, rendant l'entraînement du modèle très long et potentiellement inefficace.
Comment les règles d'association sont-elles appliquées dans le commerce ?
Dans le commerce, les règles d'association sont principalement utilisées pour l'analyse du panier d'achats, permettant d'identifier quels produits sont fréquemment achetés ensemble. Cette information est ensuite exploitée pour :
- La recommandation de produits ("Les clients qui ont acheté X ont aussi acheté Y").
- L'optimisation du placement des produits en magasin ou sur les pages web (produits complémentaires à proximité).
- La création d'offres promotionnelles groupées (bundles).
- L'amélioration de la personnalisation de l'expérience d'achat client.