Traitement de données massives

John Samuel
CPE Lyon

Année: 2024-2025
Courriel: john.samuel@cpe.fr

Creative Commons License

Data Mining

Objectifs

  1. Régularités
  2. Exploration des données
  3. Algorithmes
  4. Sélection de caractéristiques

2.1. Régularités

2.1. Régularités

Régularités naturelles

2.1. Régularités

Créations humaines

2.1. Régularités

Création

2.1. Régularités

Synonymes

2.1.2. Approches de l'apprentissage machine

Approches

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation

2.1.3. Formalisation des problèmes d'apprentissage

Exemples de caractéristiques

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation

  1. https://en.wikipedia.org/wiki/Feature_vector

2.1.3. Formalisation des problèmes d'apprentissage

Exemple

La construction de caractéristiques est une étape essentielle dans le pipeline de prétraitement des données en apprentissage machine, car elle peut aider à rendre les données plus informatives pour les algorithmes d'apprentissage.

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage supervisé

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage supervisé

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage supervisé

Cette formalisation est au cœur de l'apprentissage supervisé, où l'objectif est d'apprendre à partir d'exemples étiquetés et de trouver une fonction qui puisse prédire de manière précise les étiquettes pour de nouvelles données non vues.

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage supervisé

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage non supervisé

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage non supervisé

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage non supervisé

L'apprentissage non supervisé est utilisé pour explorer et découvrir des modèles, des structures ou des caractéristiques inhérentes aux données, sans l'utilisation d'étiquettes ou de labels préalables. Il est couramment utilisé dans des domaines tels que la clustering, l'analyse de composantes principales (PCA), l'analyse en composantes indépendantes (ICA), et bien d'autres.

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage semi-supervisé

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage semi-supervisé

2.1.3. Formalisation des problèmes d'apprentissage

Formalisation: Apprentissage semi-supervisé

2.2. Data Mining

Activités

  1. Classification
  2. Partitionnement de données (Clustering)
  3. Régression
  4. Étiquetage des séquences
  5. Règles d'association
  6. Détection d'anomalies
  7. Récapitulation

2.2.1. Classification

2.1.1 Introduction

2.2.1. Classification

Applications

2.2. Méthodes de classification

Classification: Définition formelle

2.2. Méthodes de classification

Classificateurs

2.2. Méthodes de classification

Classification binaire

Classification binaire

2.2. Méthodes de classification

Linear Classificateurs

2.2. Méthodes de classification

Évaluation

Dans le contexte de la classification en apprentissage machine, l'évaluation des performances d'un modèle implique la compréhension de différents types de prédictions qu'il peut faire par rapport à la réalité. Les vrais positifs (VP) et les vrais négatifs (VN) sont deux de ces éléments.

2.2. Méthodes de classification

Évaluation

Les vrais positifs et les vrais négatifs
Précision et rappel

2.2. Méthodes de classification

Évaluation

Soit

2.2. Méthodes de classification

Évaluation

La précision mesure la proportion de prédictions positives faites par le modèle qui étaient effectivement correctes, tandis que le rappel mesure la proportion d'exemples positifs réels qui ont été correctement identifiés par le modèle. Alors

2.2. Méthodes de classification

Évaluation

Le F1-score est la moyenne harmonique de la précision et du rappel. Il fournit une mesure globale de la performance d'un modèle de classification, tenant compte à la fois de la précision et du rappel. Il est particulièrement utile lorsque les classes sont déséquilibrées.

Le F1-score tient compte à la fois des erreurs de type I (faux positifs) et des erreurs de type II (faux négatifs), fournissant ainsi une mesure équilibrée de la performance du modèle.

2.2. Méthodes de classification

Évaluation

2.2. Méthodes de classification

Le \(F_2\)-score est souvent utilisé dans des domaines où le rappel est considéré comme plus critique que la précision.

2.2. Méthodes de classification

2.2. Méthodes de classification

Évaluation: matrice de confusion

La matrice de confusion est un outil essentiel dans l'évaluation des performances d'un système de classification. Elle fournit une vue détaillée des prédictions faites par le modèle par rapport aux classes réelles.

2.2. Méthodes de classification

Évaluation: matrice de confusion

Matrice de confusion pour un classificateur SVM pour les chiffres manuscrits (MNIST)

2.2. Méthodes de classification

Évaluation: matrice de confusion

Matrice de confusion pour un perceptron pour les chiffres manuscrits (MNIST)

2.2.1. Classification

Classification binaire

Classification binaire

2.2.1. Classification

Classification multiclasse

Classification multiclasse

2.2.1. Classification

Classification multiclasse [Aly 2005]

2.2.1. Classification

One-vs.-rest (One-vs.-all) strategy

La strategie un-contre le rest pour la classification multiclasse

2.2.1. Classification

One-vs.-rest (One-vs.-all) strategy

La strategie un-contre le rest pour la classification multiclasse

2.2.1. Classification

One-vs.-rest or One-vs.-all (OvR, OvA) strategy

2.2.1. Classification

One-vs.-rest or One-vs.-all (OvR, OvA) strategy

Prendre des décisions signifie appliquer tous les classificateurs à un échantillon invisible x et prédire l'étiquette k pour laquelle le classificateur correspondant rapporte le score de confiance le plus élevé : \[\hat{y} = \underset{k \in \{1 \ldots K\}}{\arg\!\max}\; f_k(x)\]

2.2.1. Classification

One-vs.-one strategy

La strategie un-contre-un pour la classification multiclasse

2.2.1. Classification

One-vs.-one strategy

  • nécessite l'entraînement des \(\frac{K (K - 1)}{2}\) classificateurs binaires
  • chaque classificateur reçoit les échantillons d'une paire de classes du jeu de formation original, et doit apprendre à distinguer ces deux classes.
  • Au moment de la prédiction, un système de vote est appliqué : tous les \(\frac{K (K - 1)}{2}\) classificateurs sont appliqués à un échantillon non vu et la classe qui a obtenu le plus grand nombre de prédictions est prédite par le classificateur combiné.
  • La strategie un-contre-un pour la classification multiclasse

    2.2.2. Partitionnement de données

    2.2.2.1. Introduction

    2.2.2. Partitionnement de données

    Applications

    2.2.2. Partitionnement de données

    Définition formelle

    2.2.2. Partitionnement de données

    Modèles de regroupement

    2.2.2. Partitionnement de données

    Modèles de regroupement

    2.2.2. Partitionnement de données

    Modèles de regroupement

    k-means regroupement (voir section 3.3)

    2.2.2. Partitionnement de données

    Modèles de regroupement

    Dendrogramme de regroupement hiérarchique de l'ensemble de données Iris

    2.2.3 Régression

    2.2.3 Régression

    2.2.3 Régression

    Applications

    2.2.3 Régression

    Définition formelle

    2.2.3 Régression

    Régression linéaire

    La régression linéaire est un modèle mathématique qui représente une relation linéaire entre une variable indépendante \(x_i\) et une variable dépendante \(y_i\). Le modèle a une forme d'une ligne droite (pour la régression linéaire simple) ou d'une parabole (pour la régression linéaire multiple).

    2.2.3 Régression

    Régression linéaire

    Ligne droite: \(y_i = β_0 + β_1x_i + ε_i\) où \(β_0\) et \(β_1\) sont les coefficients de régression, \(x_i\) est la variable indépendante, et \(ε_i\) est l'erreur résiduelle.

    Pour minimiser l'erreur :

    L'objectif est de minimiser SSE pour obtenir la meilleure approximation de la relation linéaire entre les variables.

    2.2.4. Étiquetage des séquences

    Processus consistant à attribuer une classe ou une étiquette à chaque élément d'une séquence de valeurs ou de tokens. Exemple : Reconnaissance d'entités nommées (NER) avec spaCy, où des entités comme les noms de personnes, les lieux, ou les organisations sont identifiées et étiquetées dans un texte.

    spaCy: Reconnaissance d'entités nommées

    Paris GPE is the capital of France GPE . In 2015 DATE , its population was recorded as 2,206,488 CARDINAL

    2.2.4. Étiquetage des séquences

    Reconnaissance d'entités nommées (spaCy)

    Paris GPE is the capital of France GPE . In 2015 DATE , its population was recorded as 2,206,488 CARDINAL
    Balise Signification
    GPE Pays, villes, états.
    DATE Dates ou périodes absolues ou relatives
    CARDINAL Les chiffres qui ne correspondent à aucun autre type.

    2.2.4. Étiquetage des séquences

    Applications

    2.2.4. Étiquetage des séquences

    Définition formelle

    2.2.5. Règles d'association

    Association Rules

    Les règles d'association, également connues sous le nom de "Association Rules", sont un ensemble de techniques d'analyse de données visant à découvrir les relations et les associations entre les variables dans un ensemble de données. Cette méthode recherche des corrélations et des co-occurrences entre les éléments, permettant ainsi de dégager des motifs ou des modèles significatifs.

    Un exemple courant d'application des règles d'association est l'analyse de paniers d'achats dans le domaine du commerce de détail, où ces règles sont utilisées pour identifier des schémas d'achat, tels que les combinaisons de produits souvent achetés ensemble.

    2.2.5. Règles d'association

    Association Rules

    Prenons un exemple concret avec un tableau de données représentant les transactions d'une épicerie :

    Transaction Produits achetés
    1 Pain, Lait, Œufs
    2 Pain, Beurre
    3 Lait, Œufs, Fromage
    4 Pain, Lait, Œufs, Bière
    5 Lait, Bière, Chips

    2.2.5. Règles d'association

    Association Rules

    Dans ce tableau, chaque colonne représente un produit et chaque ligne représente une transaction. Un "1" indique que le produit a été acheté lors de cette transaction, tandis qu'un "0" indique que le produit n'a pas été acheté.

    Transaction Pain Lait Œufs Beurre Fromage Bière Chips
    1 1 1 1 0 0 0 0
    2 1 0 0 1 0 0 0
    3 0 1 1 0 1 0 0
    4 1 1 1 0 0 1 0
    5 0 1 0 0 0 1 1

    2.2.5. Règles d'association

    Applications

    2.2.5. Règles d'association

    Définition formelle

    Une règle d'association \(X ⇒ Y\) est valide si le support et la confiance de la règle dépassent les seuils spécifiés. Cela signifie que \(X\) et \(Y\) apparaissent fréquemment ensemble dans les transactions, et que lorsque \(X\) est présent, \(Y\) est également souvent présent.

    2.2.5. Règles d'association

    Support

    Le support d'un ensemble d'articles dans le contexte des règles d'association est défini comme la fréquence à laquelle cet ensemble d'articles apparaît dans la base de données. En d'autres termes, c'est le nombre de transactions dans lesquelles cet ensemble d'articles est présent, divisé par le nombre total de transactions dans la base de données. Le support mesure donc la popularité ou la prévalence d'un ensemble d'articles. Il est utilisé pour évaluer à quel point une association entre deux ensembles d'articles est forte. Une valeur élevée de support indique que l'association est fréquente dans la base de données, ce qui la rend potentiellement plus significative.

    \[supp(X) = \frac{|t ∈T; X ⊆ t|}{ |T|}\]

    2.2.5. Règles d'association

    Confidence

    La confidence dans le contexte des règles d'association représente la fréquence à laquelle la règle a été trouvée vraie dans la base de données. Plus précisément, elle mesure la probabilité conditionnelle que la conséquence Y se produise dans une transaction, étant donné que l'antécédent X est également présent dans cette transaction.

    La confidence d'une règle est calculée en divisant le nombre de transactions dans lesquelles à la fois X et Y sont présents par le nombre de transactions dans lesquelles X est présent. Ainsi, une confidence élevée indique que la conséquence Y est souvent vraie lorsque l'antécédent X est présent, ce qui renforce la fiabilité de la règle d'association.

    \[conf(X ⇒ Y) = \frac{supp(X ∪ Y)}{supp(X)}\]

    2.2.5. Règles d'association

    En utilisant les règles d'association, nous pouvons extraire des relations significatives entre les produits. Par exemple, en appliquant un support minimum de 40% et un seuil de confiance de 60%, nous pouvons identifier les règles d'association suivantes :

    1. {Pain, Lait} \( ⇒\) {Œufs} (Support : 40%, Confiance : 100%)
    2. {Lait} \( ⇒\) {Œufs} (Support : 60%, Confiance : 75%)
    3. {Œufs} \( ⇒\) {Lait} (Support : 60%, Confiance : 75%)

    Cela signifie que dans 40% des transactions, les clients ont acheté du pain et du lait ensemble, et dans 100% de ces transactions, ils ont également acheté des œufs. De même, dans 60% des transactions, les clients ont acheté du lait, et dans 75% de ces transactions, ils ont également acheté des œufs.

    2.2.5. Règles d'association

    Lift

    Le lift dans le contexte des règles d'association est le rapport entre le "support" observé de la règle et celui attendu si les ensembles d'items X et Y étaient indépendants.Formellement, le lift est calculé en divisant le support de la règle par le produit des supports individuels de X et Y. En d'autres termes, c'est la mesure de combien plus fréquemment la règle est observée que ce à quoi on s'attendrait si les événements X et Y étaient indépendants.

    Un lift supérieur à 1 indique que la règle a une association positive entre X et Y (c'est-à-dire que les items X et Y apparaissent ensemble plus fréquemment que prévu au hasard), tandis qu'un lift inférieur à 1 indique une association négative ou non significative. Un lift de 1 indique une indépendance entre les items X et Y.

    2.2.6. Détection d'anomalies

    La détection d'anomalies, également connue sous le nom de détection des valeurs aberrantes, implique l'identification de données inhabituelles ou divergentes dans un ensemble de données. Voici quelques approches courantes pour détecter les anomalies :

    2.2.6. Détection d'anomalies

    Applications

    2.2.6. Détection d'anomalies

    Caractéristiques

    Des sursauts inattendus : Les anomalies peuvent se manifester sous forme de sursauts ou de pointes inattendues dans les données. Par exemple, une augmentation soudaine du trafic sur un site Web peut indiquer une attaque de déni de service (DDoS) dans le cas de la surveillance du trafic réseau, ou une augmentation anormale des transactions financières peut signaler une fraude.

    Les caractéristiques des données varient selon le domaine d'application et les types spécifiques d'anomalies recherchées. Identifiez les schémas inhabituels ou les comportements aberrants dans les données peut aider à détecter les anomalies et à prendre des mesures appropriées pour les gérer.

    2.2.6. Détection d'anomalies

    Formalisation

    2.2.7. Récapitulation

    2.2.7. Récapitulation

    Applications

    2.2.7. Récapitulation

    Formalisation: Synthèse multi-documents

    2.2.7. Récapitulation

    Formalisation: Multidocument summarization

    2.2.7. Récapitulation

    Trouver un sous-ensemble à partir de l'ensemble du sous-ensemble.

    1. Extraction: Cette approche implique la sélection d'un sous-ensemble de mots, de phrases ou d'expressions existants dans le texte original sans aucune modification. L'objectif est de repérer les parties les plus importantes du texte et de les présenter de manière concise dans le résumé. Les techniques utilisées dans cette approche incluent l'identification de phrases clés, la classification des phrases par importance, et l'extraction de phrases représentatives.
    2. Abstraction: Contrairement à l'extraction, l'approche d'abstraction implique la construction d'une représentation sémantique interne du texte, suivie de l'utilisation de techniques de génération du langage naturel pour produire un résumé. Cela nécessite une compréhension plus profonde du contenu du texte et la capacité de reformuler les idées de manière concise tout en préservant leur signification. Les techniques d'abstraction peuvent inclure la réécriture de phrases, la fusion d'informations similaires et la génération de paraphrases.

    2.2.7. Récapitulation

    Résumé extractif

    1. Résumé générique: Cette approche vise à obtenir un résumé général et représentatif du contenu original en extrayant les informations les plus importantes et les plus pertinentes. Elle cherche à capturer l'essence du texte original en identifiant les phrases ou les sections clés qui révèlent les principaux points et concepts abordés. Ce type de résumé est souvent utilisé dans des contextes où une vue d'ensemble est nécessaire sans se concentrer sur des aspects spécifiques ou des détails.
    2. Résumé pertinent pour la recherche : Cette approche vise à produire un résumé qui répond spécifiquement aux besoins ou aux intérêts d'un utilisateur ou d'une tâche de recherche particulière. Elle utilise des techniques de sélection de phrases basées sur la pertinence pour extraire les parties du texte qui correspondent aux critères de recherche spécifiques de l'utilisateur. Cela permet de fournir des résumés plus ciblés et adaptés aux besoins individuels, ce qui peut être particulièrement utile dans les domaines où la précision et la pertinence sont essentielles, comme la recherche d'informations spécialisées ou la prise de décision.

    2.3. Algorithmes

    1. Support Vector Machines (SVM)
    2. Descente du gradient stochastique
    3. Voisins proches
    4. Bayes naïfs
    5. Arbres de décision
    6. Ensemble Methods (Forêt d'arbres décisionnels)

    2.3.1. Machine à vecteurs de support (SVM)

    Introduction

    La machine à vecteurs de support (SVM) est une méthode d'apprentissage supervisé. SVM cherche à trouver la meilleure frontière de décision qui optimise la séparation des classes, ce qui permet une classification précise même dans des espaces de données complexes.

    2.3.1. Machine à vecteurs de support (SVM)

    Hyperplane

    L'hyperplan dans l'espace n-dimensionnel est un sous-espace de dimension n-1 qui permet de séparer les données en deux classes.

    2.3.1. Machine à vecteurs de support (SVM)

    Définition formelle

    Normal vector

    2.3.1. Machine à vecteurs de support (SVM)

    Définition formelle

    2.3.1. Machine à vecteurs de support (SVM)

    Définition formelle

    2.3.1. Machine à vecteurs de support (SVM)

    Définition formelle

    2.3.1. Machine à vecteurs de support (SVM)

    Data mining

    2.3.1. Machine à vecteurs de support (SVM)

    Applications

    2.3.2. Gradient stochastique de descente

    Le gradient stochastique de descente est une technique d'optimisation utilisée pour minimiser une fonction objective qui peut être exprimée comme une somme de fonctions différenciables.

    2.3.2. Gradient stochastique de descente

    Gradient

    Le gradient est une généralisation multi-variable de la notion de dérivée.

    2.3.2. Gradient stochastique de descente

    Gradient

    2.3.2. Gradient stochastique de descente

    Gradient

    2.3.2. Gradient stochastique de descente

    Gradient ou dérivé

    Dérivé Gradient
    Définition Taux de variation instantanée d'une fonction Vecteur des dérivées partielles d'une fonction de plusieurs variables
    Nombre de variables Une seule Plusieurs
    Nature Fonction scalaire Fonction vectorielle
    Représentation Un seul nombre réel Un vecteur de nombres réels
    Utilisation Fonctions d'une seule variable Fonctions de plusieurs variables, notamment en optimisation et en machine learning
    Géométrie Pente de la tangente à un point d'une courbe Direction et taux de variation le plus rapide d'une fonction dans un espace multi-dimensionnel

    2.3.2. Gradient stochastique de descente

    Algorithme du gradient

    L'algorithme du gradient stochastique de descente est un algorithme d'optimisation itératif largement utilisé pour trouver le minimum d'une fonction.

    1. Initialisation : Choisissez un point de départ aléatoire ou prédéfini dans l'espace des paramètres.
    2. Calcul du gradient : Calculez le gradient de la fonction objective par rapport aux paramètres au point courant.

    2.3.2. Gradient stochastique de descente

    Algorithme du gradient

    1. Mise à jour des paramètres : Mettez à jour les paramètres dans la direction opposée au gradient. Cela implique de soustraire une fraction du gradient de chaque paramètre.
    2. Répétition : Répétez les étapes 2 et 3 jusqu'à ce qu'un critère d'arrêt soit satisfait, par exemple, un nombre fixe d'itérations, une petite variation de la fonction objective ou une tolérance pour le gradient.

    2.3.2. Gradient stochastique de descente

    Algorithme du gradient

    L'algorithme stochastique du gradient de descente est une variante où le gradient est calculé de manière stochastique, c'est-à-dire qu'au lieu d'utiliser l'ensemble complet des données pour calculer le gradient à chaque itération, un sous-ensemble aléatoire ou une seule observation est utilisé. Cela permet de gagner en efficacité, en particulier pour les grands ensembles de données.

    L'objectif principal de cet algorithme est de minimiser une fonction objective, souvent une fonction de perte dans le cadre de l'apprentissage automatique, et il est largement utilisé dans des domaines tels que l'optimisation convexe, l'apprentissage automatique et le traitement du signal.

    2.3.2. Gradient stochastique de descente

    Méthode standard de descente de gradient

    2.3.2. Gradient stochastique de descente

    Méthode itérative

    2.3.2. Gradient stochastique de descente

    Applications

    2.3.3. Méthode des plus proches voisins

    La méthode des k plus proches voisins (kNN) et le partitionnement en k-moyennes (k-means clustering) sont deux techniques importantes en apprentissage automatique et en exploration de données :

    1. Méthode des k plus proches voisins (kNN) : C'est un algorithme d'apprentissage supervisé utilisé pour la classification et la régression. L'idée principale derrière kNN est de trouver les k échantillons d'entraînement les plus proches du point de données de test et de prédire l'étiquette de classe en fonction de la classe majoritaire parmi ces voisins. Pour la régression, la prédiction est la moyenne des valeurs cibles des k voisins les plus proches.
    2. Partitionnement en k-moyennes (k-means clustering) : C'est une méthode non supervisée de partitionnement de données en k groupes distincts. L'algorithme fonctionne en répétant deux étapes : d'abord, il attribue chaque point de données au groupe dont le centroïde est le plus proche, puis il met à jour les centroïdes en calculant la moyenne de tous les points attribués à chaque groupe. Ces étapes sont répétées jusqu'à ce qu'une convergence soit atteinte et que les centroïdes ne changent plus de manière significative.

    2.3.3. Méthode des plus proches voisins

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    Étape 1 (Initialisation)

    Les "moyens", également appelés centroïdes, sont les points initiaux autour desquels les clusters seront formés. Dans cette étape, k points sont sélectionnés de manière aléatoire à partir de l'ensemble de données pour servir de moyens initiaux.

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    Étape 2 (Étape d'affectation)

    Dans la deuxième étape de l'algorithme de partitionnement en k-moyennes (k-means clustering), également connue sous le nom d'étape d'affectation, les k clusters sont créés en associant chaque observation à la moyenne la plus proche.Les partitions représentent ici le diagramme de Voronoï généré par les moyennes.

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    Étape 2 (Étape d'affectation)

  • Calcul des distances : Pour chaque observation de l'ensemble de données, la distance jusqu'à chaque moyen est calculée. La distance la plus couramment utilisée est la distance euclidienne, mais d'autres mesures de distance peuvent également être utilisées en fonction des besoins spécifiques de l'application.
  • Association des observations aux clusters : Une fois les distances calculées, chaque observation est associée au cluster dont le moyen est le plus proche. Cela crée k partitions dans l'ensemble de données, où chaque partition contient les observations associées à un cluster spécifique.
  • Diagramme de Voronoï : Les partitions formées dans cette étape peuvent être visualisées comme un diagramme de Voronoï dans l'espace des données. Chaque cluster est représenté par une région de l'espace des données où les points sont plus proches de son moyen que de tout autre moyen.
  • 2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    Étape 3 (Étape de mise à jour et calcul du centroïde)

    Les centroids de chacun des k agrégats sont recalculés pour devenir les nouvelles moyennes.

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    Étape 3 (Étape de mise à jour et calcul du centroïde)

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    Étape 4 (Répéter jusqu'à la convergence)

    La quatrième étape de l'algorithme de partitionnement en k-moyennes (k-means clustering) consiste à répéter les étapes 2 et 3 jusqu'à ce que la convergence soit atteinte.

    2.3.3. Méthode des plus proches voisins

    Partitionnement en k-moyennes

    Étape 4 (Répéter jusqu'à la convergence)

    2.3.3. Méthode des plus proches voisins

    Méthode des k plus proches voisins

    La méthode des k plus proches voisins (k-NN) est un algorithme d'apprentissage supervisé utilisé à la fois pour la classification et la régression.

    2.3.3. Méthode des plus proches voisins

    Méthode des k plus proches voisins

    Supposons que nous ayons un ensemble de données d'apprentissage composé de points dans un espace bidimensionnel, où chaque point est associé à une classe. Supposons que nous voulions classer un nouveau point avec des coordonnées (x = 4, y = 3).

    Point Coordonnée x Coordonnée y Classe
    A 2 3 Rouge
    B 4 4 Rouge
    C 3 2 Bleu
    D 6 5 Rouge
    E 5 3 Bleu

    2.3.3. Méthode des plus proches voisins

    Méthode des k plus proches voisins

    1. Choix de k : Disons que nous choisissons k = 3.
    2. Calcul de la distance : Nous calculons la distance euclidienne entre le nouveau point et chaque point de notre ensemble d'apprentissage.
      • - Pour le point A : Distance = sqrt((4 - 2)^2 + (3 - 3)^2) = sqrt(4) = 2
      • - Pour le point B : Distance = sqrt((4 - 4)^2 + (3 - 4)^2) = sqrt(1) = 1
      • - Pour le point C : Distance = sqrt((4 - 3)^2 + (3 - 2)^2) = sqrt(2) ≈ 1.41
      • - Pour le point D : Distance = sqrt((4 - 6)^2 + (3 - 5)^2) = sqrt(8) ≈ 2.83
      • - Pour le point E : Distance = sqrt((4 - 5)^2 + (3 - 3)^2) = sqrt(1) = 1

    2.3.3. Méthode des plus proches voisins

    Méthode des k plus proches voisins

    1. Sélection des k plus proches voisins : Nous identifions les k points les plus proches du nouveau point en termes de distance.
      • - Pour k = 3, les trois plus proches voisins sont B, C et E.
    2. Vote majoritaire : Enfin, nous attribuons la classe majoritaire parmi les k voisins les plus proches au nouveau point. Dans ce cas, deux des voisins les plus proches (C et E) sont de la classe "Bleu" et un (B) est de la classe "Rouge". Par conséquent, le nouveau point est classé comme "Bleu".

    2.3.3. Méthode des plus proches voisins

    Applications

    2.3.4. Classification naïve bayésienne

    La classification naïve bayésienne est une méthode de classification probabiliste simple basée sur l'application du théorème de Bayes avec une forte hypothèse d'indépendance entre les caractéristiques.

    2.3.4. Classification naïve bayésienne

    2.3.4. Classification naïve bayésienne

    Applications

    2.3.4. Classification naïve bayésienne

    Théorème de Bayes

    \[P(A|B) = \frac{(P(B|A).P(A))}{P(B)}\]

    2.3.4. Classification naïve bayésienne

    Théorème de Bayes: Classification d'un message

    \[P(S|W) = \frac{P(W|S) \cdot P(S)}{P(W|S) \cdot P(S) + P(W|H) \cdot P(H)}\]

    2.3.5. Arbres de décision

    Les arbres de décision sont un outil puissant d'aide à la décision qui utilise un modèle arborescent pour représenter les décisions et leurs conséquences possibles

    2.3.5. Arbres de décision

    2.3.5. Arbres de décision

    Animal Pelage Plumes Peut voler Classe
    Chien Poilu Non Non Mammifère
    Chat Poilu Non Non Mammifère
    Aigle Plumeux Oui Oui Oiseau
    Pingouin Plumeux Oui Non Oiseau
    Serpent Écaille Non Non Reptile

    Nous voulons classer ces animaux en trois classes : Mammifère, Oiseau ou Reptile. Utilisons un arbre de décision pour ce faire.

    2.3.5. Arbres de décision

    L'algorithme de l'arbre de décision est une méthode d'apprentissage supervisé utilisée pour la classification et la régression.

    2.3.5. Arbres de décision

    2.3.5. Arbres de décision

    Dans le contexte des arbres de décision, les données sont généralement représentées sous forme de vecteurs où chaque élément du vecteur correspond à une caractéristique ou à une variable indépendante, et la variable dépendante est la cible que l'on cherche à prédire ou à classifier.

    2.3.5. Arbres de décision

    Applications

    2.3.5. Arbres de décision

    Applications

    2.3.6. Apprentissage ensembliste (Forêt d'arbres décisionnels)

    L'apprentissage ensembliste, en particulier les forêts d'arbres décisionnels, est une technique qui combine plusieurs modèles d'apprentissage pour améliorer les performances prédictives par rapport à un seul modèle. Les forêts d'arbres décisionnels sont obtenues en construisant de multiples arbres de décision lors de la phase d'entraînement.

    2.3.6. Apprentissage ensembliste (Forêt d'arbres décisionnels)

    2.3.6. Apprentissage ensembliste (Forêt d'arbres décisionnels)

    Algorithme

    2.3.6. Apprentissage ensembliste (Forêt d'arbres décisionnels)

    Applications

    2.3.6. Apprentissage ensembliste (Forêt d'arbres décisionnels)

    Applications

    2.4. Sélection de caractéristique

    La sélection de caractéristiques est un processus visant à choisir un sous-ensemble de caractéristiques pertinentes parmi un grand nombre de caractéristiques disponibles.

    2.4. Sélection de caractéristique

    Applications

    2.4. Sélection de caractéristique

    Définition formelle[8]

    Références

    Articles de recherche

    1. From data mining to knowledge discovery in databases, Usama Fayyad, Gregory Piatetsky-Shapiro, and Padhraic Smyth, AI Magazine Volume 17 Number 3 (1996)
    2. Survey of Clustering Data Mining Techniques, Pavel Berkhin
    3. Mining association rules between sets of items in large databases, Agrawal, Rakesh, Tomasz Imieliński, and Arun Swami. Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD 1993. p. 207.
    4. Comparisons of Sequence Labeling Algorithms and Extensions, Nguyen, Nam, and Yunsong Guo. Proceedings of the 24th international conference on Machine learning. ACM, 2007.

    Références

    Articles de recherche

    1. An Analysis of Active Learning Strategies for Sequence Labeling Tasks, Settles, Burr, and Mark Craven. Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, 2008.
    2. Anomaly detection in crowded scenes, Mahadevan; Vijay et al. Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010
    3. A Study of Global Inference Algorithms in Multi-Document Summarization. McDonald, Ryan. European Conference on Information Retrieval. Springer, Berlin, Heidelberg, 2007.
    4. Feature selection algorithms: A survey and experimental evaluation., Molina, Luis Carlos, Lluís Belanche, and Àngela Nebot. Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on. IEEE, 2002.
    5. Support vector machines, Hearst, Marti A., et al. IEEE Intelligent Systems and their applications 13.4 (1998): 18-28.

    Références

    Ressources en ligne

    Références

    Ressources en ligne

    Références

    Couleurs

    Images