Notes De Révision Du Cours De Fouille De Données

Plan

1. Comprendre la fouille de données

1. Définition de la fouille de données
2. Apprentissage supervisé et non supervisé
3. Processus de fouille de données

2. Techniques de fouille de données de base

1. Concept d’arbre de décision et processus général de l’algorithme C 4.5
2. Technologie clé de l’arbre de décision : taux de gain maximal
3. Règles de l’arbre de décision : arbre de décision, règles de production, taux de précision et de couverture
4. Idée de base de l’algorithme Apriori
5. Règles d’association et leur confiance et support
6. Idée de base de l’algorithme K-means
7. Exemple d’analyse de clustering K-means

3. Découverte de connaissances dans les bases de données

1. Définition de KDD (connaissance)
2. Prétraitement des données : réduction par histogramme, normalisation des données et lissage des données

5. Techniques d’évaluation

1. Évaluation des modèles de sortie de type classification : matrice de confusion et taux de précision de classification, précision et rappel
2. Évaluation des modèles de sortie de type numérique : erreur absolue moyenne, erreur quadratique moyenne, erreur quadratique moyenne racine

6. Réseaux neuronaux

1. Modèle de neurone artificiel (savoir dessiner et calculer)
2. Structure du réseau neuronal BP (savoir dessiner, par exemple un avec une entrée, une sortie et deux couches cachées contenant trois neurones), processus de calcul avant
3. Processus général de l’algorithme BP
4. Opérations de base du réseau neuronal convolutionnel - convolution et pooling, caractéristiques de convolution (champ récepteur local, partage de poids)

7. Techniques statistiques

1. Régression linéaire simple, régression linéaire multiple - méthode des moindres carrés
2. Analyse bayésienne : classificateur bayésien
3. Étapes générales de l’algorithme de clustering agglomératif, exemple
4. Algorithme de clustering hiérarchique Cobweb : calcul de la valeur CU

Chapitre 1 Comprendre la fouille de données

Définition de la fouille de données

Point de vue technique : processus de traitement utilisant des technologies informatiques pour analyser automatiquement et extraire des informations à partir de données ; le but est de découvrir des informations potentiellement précieuses dans les données ; généralement réalisé en utilisant des méthodes telles que l’apprentissage automatique, les statistiques, la reconnaissance de formes, etc. Point de vue disciplinaire : discipline interdisciplinaire, impliquant l’intelligence artificielle, les statistiques, la visualisation, le calcul parallèle, etc. Point de vue commercial : révéler des règles cachées, inconnues ou vérifier des règles connues ;

Apprentissage supervisé et non supervisé

Les méthodes de base en apprentissage automatique incluent : apprentissage conceptuel, apprentissage inductif, apprentissage supervisé et apprentissage non supervisé.

Apprentissage supervisé : Entraînement sur un grand nombre d’exemples de classification ou de sortie connus pour ajuster la structure du modèle de classification afin de construire un modèle de classification ou de prédiction précis ; ce processus d’apprentissage conceptuel basé sur l’induction est appelé apprentissage supervisé. Apprentissage non supervisé : Aucun exemple de classification préalablement défini avant l’apprentissage. Les instances de données sont regroupées en un cluster en fonction d’une méthode de mesure de similarité, calculant le degré de similarité, puis interprétant et comprenant la signification de chaque cluster pour découvrir la signification du clustering. (K-Means, clustering agglomératif, hiérarchie conceptuelle Cobweb, algorithme EM)

Processus de fouille de données

Quatre étapes :

1. Préparer les données, y compris les données d’entraînement et de test ;
2. Choisir une technique ou un algorithme de fouille de données, soumettre les données au logiciel de fouille ;
3. Interpréter et évaluer le modèle ;
4. Application du modèle ; La préparation des données peut être effectuée à partir de bases de données, d’entrepôts de données, de fichiers plats ; Choisir la technique et l’algorithme nécessite de considérer :

• Déterminer si l’apprentissage est supervisé ou non supervisé ;
• Comment diviser les données en ensembles d’entraînement, de test et de validation ;
• Comment paramétrer l’algorithme de fouille de données ;

Rôle de la fouille de données (classification des types, non technique)

• Apprentissage supervisé
  • Classification
  • Estimation
  • Prédiction
• Clustering non supervisé
• Analyse des relations d’association

Chapitre 2 Techniques de fouille de données de base

Arbre de décision

1. Concept d’arbre de décision et processus général de l’algorithme C 4.5

2. Technologie clé de l’arbre de décision : taux de gain maximal
3. Règles de l’arbre de décision : arbre de décision, règles de production, taux de précision et de couverture

Concept

Un arbre de décision est un modèle en structure arborescente, chaque nœud représentant un attribut d’un objet, chaque branche représentant une valeur possible de cet attribut, et la valeur du nœud feuille est le résultat de sortie de l’arbre de décision.

Algorithme C4.5

(1) Étant donné un ensemble de données T représenté au format “attribut-valeur”. L’ensemble de données est constitué de plusieurs instances ayant plusieurs attributs d’entrée et un attribut de sortie. (2) Choisir un attribut d’entrée qui distingue le mieux les instances de T, C4.5 utilise le taux de gain pour choisir cet attribut. (3) Utiliser cet attribut pour créer un nœud d’arbre, tout en créant les branches de ce nœud, chaque branche représentant toutes les valeurs possibles de ce nœud. (4) Utiliser ces branches pour classer les instances de l’ensemble de données en sous-classes. (5) Définir l’ensemble des instances de la sous-classe actuelle comme T, répéter les étapes (2) et (3) sur les attributs restants de l’ensemble de données, jusqu’à ce que l’une des deux conditions suivantes soit satisfaite, le processus s’arrête. Créer un nœud feuille, ce nœud est la catégorie exprimée le long de cette branche, sa valeur est la valeur de l’attribut de sortie.

• Les instances de la sous-classe satisfont à un critère prédéfini, comme être toutes dans une classe de sortie, ou le nombre d’instances dans une classe de sortie atteint un certain pourcentage ;
• Aucun attribut restant.

Technologie clé

Méthode de sélection de l’attribut qui distingue le mieux les instances

Priorité à l’attribut avec le taux de gain maximal pour maximiser le degré de généralisation des données (nombre de niveaux et de nœuds minimal). Entropie de l’information L’entropie est une mesure du degré d’incertitude, plus elle est grande, plus l’information est importante, plus la transmission d’informations est importante ; $$H(x)=-\sum_{i=1}^n {p(x_{i})log_{2}(p(x_{i}))}$$ Gain d’information Plus le gain est grand, plus l’entropie diminue rapidement, plus elle est propice à la classification. $$Info(I)=-\sum\frac{nombre\ dans\ la\ classe\ i}{nombre\ total\ d’instances}log_{2}\frac{nombre\ dans\ la\ classe\ i}{nombre\ total\ d’instances}$$ $Info(I)$ est la quantité totale d’informations exprimée par toutes les instances de l’ensemble de données actuel ; $$Info(I,A)=\sum\limits_{j=1}^{k}\frac{nombre\ d’instances\ dans\ la\ classe\ j}{nombre\ total\ d’instances}Info(classe\ j)$$ $Info(I,A)$ est la quantité d’informations après classification de I selon les k valeurs de l’attribut A ; $$SplitsInfo(A)=-\sum\limits_{i}^{k}\frac{nombre\ d’instances\ dans\ la\ classe\ j}{nombre\ total\ d’instances}log_{2}\frac{nombre\ d’instances\ dans\ la\ classe\ j}{nombre\ total\ d’instances}$$ $SplitsInfo(A)$ est la normalisation de la valeur de gain pour l’attribut A ; $$Gain(A)=Info(A)-Info(I,A)$$ $$GainRatio(A)= \frac{Gain(A)}{SplitsInfo(A)}$$

Méthodes de taille

Méthodes de test

• Test en pourcentage
• Validation croisée k-fold leave-out leave-one-out

Règles de l’arbre de décision

Traduire l’arbre de décision en règles, calculer le taux de précision et de couverture ;

1
2
3

SI Cours <≤5 et Météo = Pluie ALORS Jouer = Non
Précision : 3/5 = 60% Couverture : 3/8 = 37.5%
Précision : satisfait à la phrase entière / satisfait à la première moitié de la phrase Couverture : satisfait à la phrase entière / satisfait à la deuxième moitié de la phrase

Avantages et inconvénients (connaissance)

Avantages (1) Facile à comprendre et à expliquer, et peut être mappé à un ensemble de règles de production plus attrayantes. (2) Aucun besoin de faire des hypothèses préalables sur la nature des données. (3) Capable d’utiliser des ensembles de données numériques et de type catégoriel pour construire des modèles. Limites (1) L’attribut de sortie doit être de type catégoriel, et il ne doit y avoir qu’un seul attribut de sortie. (2) Les algorithmes d’arbres de décision sont instables. (3) Les arbres créés avec des ensembles de données numériques sont plus complexes (comme l’arbre de décision non élagué dans l’exemple 2.3), car les divisions d’attributs de données numériques sont généralement des divisions binaires.

Règles d’association

Idée de base de l’algorithme Apriori

• Générer des ensembles d’articles. Un ensemble d’articles est une combinaison “attribut-valeur” qui répond à une exigence de support. Les combinaisons qui ne répondent pas aux exigences de support sont rejetées, ce qui permet de terminer le processus de génération de règles dans un délai raisonnable.
• Utiliser l’ensemble d’articles généré pour créer un ensemble de règles d’association basé sur la confiance.

Règles d’association et leur confiance et support

Support : satisfait à la phrase entière / satisfait à la deuxième moitié de la phrase Confiance : satisfait à la phrase entière / satisfait à la première moitié de la phrase

Dans l’utilisation pratique, générer successivement des ensembles d’articles simples, doubles, triples, et créer des règles d’association basées sur l’ensemble d’articles généré.

1
2
3
4
5
6
7

À partir de la première entrée de l'ensemble d'articles doubles, générer deux règles :
SI Livre =1 ALORS Écouteur = 1 (confiance : 4/5 = 80%, conserver)
SI Écouteur = 1 ALORS Livre =1 (confiance : 4/7 = 57.1%, supprimer)
À partir de la première entrée de l'ensemble d'articles triples, générer trois règles :
SI Livre =1 & Écouteur = 1 ALORS DVD = 1 (confiance : 4/4 = 100%, conserver)
SI Livre =1 & DVD = 1 ALORS Écouteur = 1 (confiance : 4/4 = 100%, conserver)
SI Écouteur = 1 & DVD = 1 ALORS Livre =1 (confiance : 4/6 = 66.7%, supprimer)

Techniques de clustering

Idée de base de l’algorithme K-means

1. Choisir aléatoirement une valeur K pour déterminer le nombre total de clusters.
2. Choisir arbitrairement K instances dans l’ensemble de données, les utiliser comme centres initiaux des clusters.
3. Calculer la distance euclidienne simple entre ces K centres de clusters et les autres instances restantes. Utiliser cette distance comme mesure de similarité entre les instances, classer les instances les plus similaires à un cluster en tant que membres.
4. Utiliser les instances de chaque cluster pour calculer un nouveau centre de cluster.
5. Si le nouveau centre de cluster obtenu est égal au centre de cluster de l’itération précédente, arrêter l’algorithme. Sinon, utiliser le nouveau centre de cluster pour répéter les étapes 3 à 5.

Exemple d’analyse de clustering K-means

Avantages et inconvénients

Avantages Algorithme très populaire, facile à comprendre, simple à implémenter. Limites (1) Ne peut traiter que des données numériques, si l’ensemble de données contient des attributs de type catégoriel, soit supprimer cet attribut, soit le convertir en données numériques équivalentes. (2) Avant de commencer l’algorithme, il est nécessaire de choisir aléatoirement une valeur K comme nombre initial de clusters (avec une certaine arbitraire, un mauvais choix affectera les résultats du clustering). Habituellement, choisir différentes valeurs de K pour effectuer des expériences répétées, espérant trouver la meilleure valeur de K. (3) L’algorithme K-means fonctionne mieux lorsque la taille des clusters est approximativement égale. (4) Les attributs qui ne contribuent pas beaucoup au clustering peuvent affecter les résultats du clustering (points isolés). Il est nécessaire de sélectionner les attributs avant le clustering. (5) Interprétation difficile des clusters. Des outils de fouille supervisée peuvent être utilisés pour expliquer davantage la nature des clusters formés par l’algorithme de clustering non supervisé.

Chapitre 3 Découverte de connaissances dans les bases de données

Définition de KDD (connaissance)

Knowledge Discovery in Data, processus d’extraction d’informations fiables, nouvelles, potentiellement précieuses, compréhensibles par l’homme, non triviales à partir de jeux de données (la plupart des étapes sont exécutées automatiquement par le système).

Modèle de processus KDD

Modèle classique

Modèle commercial CRISP-DM

Modèle en ligne OLAM

Prétraitement des données : réduction par histogramme, normalisation des données et lissage des données

Méthode de binning : (traitement du bruit -> lissage des données) Trier les données comme suit, par exemple 3, 6, 12, 22, 24, 26, 27, 30, 30 Diviser en trois bacs “de même hauteur”, chaque bac contenant le même nombre de données ; “Largeur égale”, chaque bac couvrant une plage fixe ; Lisser en utilisant la moyenne, la valeur maximale, conserver la valeur maximale comme limite et rapprocher les autres.

Réduction par histogramme Diviser en seaux de largeur ou de profondeur égale, compter, dessiner un histogramme

Normalisation des données

1. Mise à l’échelle min-max : Mettre à l’échelle les données pour qu’elles se situent entre 0 et 1, en effectuant une transformation linéaire des données d’origine. Plus précisément, la mise à l’échelle min-max met à l’échelle les données d’origine v dans une nouvelle plage de valeurs v’, calculée par la formule $v_{i}^{’}=\frac{v_{i}-minA}{maxA-minA}(b-a)+a$, où b-a est la longueur de l’intervalle, a est le point de départ de l’intervalle, ce qui permet de mapper le résultat normalisé dans une certaine plage d’intervalle, si non spécifié, ignorer les paramètres de l’intervalle.

2. Normalisation Z-score : Mettre à l’échelle les données pour qu’elles aient une moyenne de 0 et un écart-type de 1, de sorte que les données soient distribuées dans une distribution normale avec une moyenne de 0 et un écart-type de 1. Plus précisément, la normalisation Z-score met à l’échelle les données d’origine x dans une nouvelle plage de valeurs y, calculée par la formule y = (x - μ) / σ, où μ et σ sont respectivement la moyenne et l’écart-type des données d’origine.

3. Normalisation par échelle décimale : En déplaçant la position du point décimal, mettre à l’échelle les données pour qu’elles se situent entre [-1,1] ou [-0.5,0.5]. Plus précisément, la normalisation par échelle décimale met à l’échelle les données d’origine x en les multipliant par 10 à la puissance k, obtenant ainsi une nouvelle plage de valeurs y, calculée par la formule y = x / 10^k, où k est un entier satisfaisant 10^(k-1) ≤ |x| < 10^k. Le nombre de déplacements est déterminé par la valeur maximale.

4. La normalisation logarithmique est une méthode de prétraitement des données qui convertit les données en prenant le logarithme, souvent utilisée pour lisser les données non négatives, les rendant plus faciles à comparer et à analyser. Plus précisément, la normalisation logarithmique prend le logarithme des données d’origine x, obtenant ainsi une nouvelle plage de valeurs y, calculée par la formule y = log(x).

5. Normalisation : Mettre à l’échelle les données pour qu’elles aient une longueur ou une plage unitaire, les méthodes de normalisation courantes incluent la normalisation par norme L1 et la normalisation par norme L2. Plus précisément, la normalisation par norme L1 met à l’échelle les données d’origine x dans une nouvelle plage de valeurs y, calculée par la formule y = x / (|x1| + |x2| + … + |xn|) ; la normalisation par norme L2 met à l’échelle les données d’origine x dans une nouvelle plage de valeurs y, calculée par la formule y = x / sqrt(x1^2 + x2^2 + … + xn^2).

Chapitre 5 Techniques d’évaluation

Évaluation des modèles de sortie de type classification

Évaluation des modèles de sortie de type numérique

$$MAE=\frac{|a_{1}-c_{1}|+|a_{2}-c_{2}|+…+|a_{n}-c_{n}|}{n}$$ $$MSE=\frac{(a_{1}-c_{1})^2+(a_{2}-c_{2})^2+…+(a_{n}-c_{n})^2}{n}$$ $$RMS=\sqrt{MSE}=\sqrt{\frac{(a_{1}-c_{1})^2+(a_{2}-c_{2})^2+…+(a_{n}-c_{n})^2}{n}}$$

Chapitre 6 Réseaux neuronaux

Modèle de neurone artificiel

R entrées $p_i∈R$, c’est-à-dire un vecteur d’entrée R-dimensionnel p n : entrée nette, $n=wp+b$. R poids $wi∈R$, c’est-à-dire un vecteur de poids R-dimensionnel w Seuil b Sortie a=f(n), f : fonction de transfert Fonctions d’activation courantes $$a=f(n)=hardlim(n)=\begin{cases} {1},n>=0 \ {0} ,n<0\ \end{cases}$$ $$a=f(n)=hardlim \quad s(n)=\begin{cases} {1},n>=0 \ {-1} ,n<0\ \end{cases}$$ $$a=f(n)=n$$ $$a=f(n)=\frac{1}{1+e^{-n}}$$ La fonction Sigmoid a pour caractéristique la plus importante d’être infiniment différentiable.

Réseau neuronal BP

Structure du réseau neuronal BP, processus de calcul avant

Notez que chaque neurone est entièrement connecté à la couche suivante, sans connexion entre les neurones de la même couche.

Processus général de l’algorithme BP

Le processus d’apprentissage de l’algorithme B-P est le suivant : (1) Choisir un ensemble d’exemples d’entraînement, chaque exemple étant composé d’informations d’entrée et de résultats de sortie attendus. (2) Prendre un exemple de l’ensemble d’exemples d’entraînement, entrer les informations dans le réseau. (3) Calculer respectivement les sorties des nœuds de chaque couche après traitement par les neurones. (4) Calculer l’erreur entre la sortie réelle du réseau et la sortie attendue. (5) Calculer à l’envers de la couche de sortie à la première couche cachée, et ajuster les poids de connexion de chaque neurone dans le réseau selon un principe qui réduit l’erreur. (6) Répéter les étapes (2) à (5) pour chaque exemple de l’ensemble d’exemples d’entraînement, jusqu’à ce que l’erreur pour l’ensemble d’exemples d’entraînement atteigne l’exigence.

CNN

Convolution

La première technique est appelée champ récepteur local. Dans une image, les pixels proches sont plus étroitement liés, tandis que les pixels éloignés sont moins corrélés. Par conséquent, chaque neurone n’a pas besoin de percevoir l’image entière, il suffit de percevoir localement, puis de combiner les informations locales à un niveau supérieur pour obtenir les informations globales. La deuxième technique est le partage de poids. Comment comprendre le partage de poids ? Nous pouvons considérer l’opération de convolution comme une méthode d’extraction de caractéristiques, indépendante de la position. Le principe sous-jacent est que les caractéristiques statistiques d’une partie de l’image sont les mêmes que celles d’une autre partie. Cela signifie que les caractéristiques apprises dans une partie peuvent également être utilisées dans une autre partie, donc pour toutes les positions de cette image, nous pouvons utiliser les mêmes caractéristiques apprises. Quels sont les avantages du partage de poids ? D’une part, les unités répétées permettent de reconnaître les caractéristiques, indépendamment de leur position dans le champ visuel. D’autre part, le partage de poids nous permet d’extraire les caractéristiques plus efficacement, car il réduit considérablement le nombre de variables libres à apprendre. En contrôlant la taille du modèle, le réseau convolutionnel peut avoir une bonne capacité de généralisation pour les problèmes visuels. La meilleure façon d’expliquer une couche de convolution est d’imaginer une lampe de poche éclairant la partie supérieure gauche de l’image, supposons que la zone éclairée par la lampe de poche est de 5 x 5. Imaginez ensuite que cette lampe de poche glisse sur les différentes régions de l’image d’entrée. En termes d’apprentissage automatique, cette lampe de poche est appelée filtre (parfois aussi appelée neurone ou noyau de convolution), et la zone qu’elle éclaire est appelée champ récepteur. Ce filtre est également une série de données (ces données sont appelées poids ou paramètres).

Pooling/échantillonnage

Le pooling maximal consiste à choisir la valeur maximale dans la fenêtre de pooling comme valeur d’échantillonnage. Le pooling moyen consiste à additionner toutes les valeurs dans la fenêtre de pooling et à prendre la moyenne comme valeur d’échantillonnage. Le pooling peut réduire le nombre de paramètres et diminuer le risque de surapprentissage.

Chapitre 7 Techniques statistiques

Analyse de régression

L’analyse de régression est une méthode d’analyse statistique utilisée pour déterminer les relations de dépendance quantitative entre deux ou plusieurs variables, et établir une équation mathématique pour généraliser un ensemble de données numériques. Méthode des moindres carrés Construire une fonction d’erreur comme fonction objectif (généralement de second ordre), et calculer la dérivée partielle par rapport aux variables indépendantes.

Analyse bayésienne

Une méthode d’estimation des paramètres, combinant les informations a priori sur les paramètres inconnus avec les informations de l’échantillon (liste), et utilisant la formule de Bayes pour calculer la probabilité conditionnelle, obtenant ainsi les informations a posteriori, afin de déduire les paramètres inconnus ; $$P(H|E)=\frac{P(E|H)P(H)}{P(E)}$$ Problèmes existants :

1. Probabilité de 0 - ajouter une petite constante
2. Données manquantes - ignorer simplement, probabilité notée 1

Techniques de clustering

Le clustering comprend le clustering par partition (K-Means), le clustering hiérarchique (agglomératif, division), le clustering par modèle (algorithme EM) ;

Algorithme de clustering agglomératif Un algorithme de clustering non supervisé. Au début, chaque instance est dans une classe différente, formant chacune un cluster ; Trouver deux clusters les plus similaires, les fusionner, jusqu’à ce que la condition soit remplie ou qu’ils soient fusionnés en une seule classe.

Clustering hiérarchique Cobweb Un algorithme de clustering hiérarchique incrémental. Utilise un arbre de classification pour classer les instances, le processus de construction de l’arbre de classification est un processus de hiérarchie conceptuelle. La racine de l’arbre est le niveau conceptuel le plus élevé, contenant les informations agrégées de tous les exemples de domaine ; à l’exception des nœuds feuilles, les autres nœuds sont des nœuds de niveau inférieur de l’arbre, exprimant le niveau de division conceptuelle. Utilise une fonction d’évaluation pour mesurer la qualité du niveau conceptuel. Les objets de classification doivent être de type catégoriel. Algorithme :

• Créer une classe, utiliser le premier exemple comme son seul membre ;
• Pour les exemples restants. À chaque niveau de l’arbre (hiérarchie conceptuelle), utiliser la fonction d’évaluation pour décider d’exécuter l’une des actions suivantes :
  • Placer le nouvel exemple dans un cluster existant ;
  • Créer un nouveau cluster conceptuel avec seulement ce nouvel exemple ;

Calcul de la valeur CU : $$CU=\frac{\sum\limits_{k=1}^{m}P(C_k)(\sum\limits_{i}\sum\limits_{j}P(A_{i}=V_{ij}|C_{k})^{2}-\sum\limits_{i}\sum\limits_{j}({A_{i}=V_{ij})^2})}{m}$$ $P(A_{i}=V_{ij}|C_k)$ représente la probabilité que l’attribut $A_i$ prenne la valeur $V_{ij}$ parmi tous les membres de la classe $C_k$ $P(A_{i}=V_{ij})$ représente la probabilité que l’attribut $A_i$ prenne la valeur $V_{ij}$ dans l’ensemble de données entier $P(C_k)$ représente la probabilité de chaque classe $C_k$

Avantages : Capable d’ajuster automatiquement le nombre de classes (clusters), ne sera pas affecté par l’irrationalité du choix aléatoire du nombre de classifications, ce qui pourrait entraîner des résultats de clustering non idéaux. Limites :

• Sensible à l’ordre des exemples, nécessite l’introduction de deux opérations supplémentaires - fusion et division pour réduire la sensibilité.
• Suppose que la distribution de probabilité de chaque attribut est indépendante les unes des autres, mais en réalité, cette hypothèse n’est pas toujours vraie ;
• La complexité de la représentation, de la mise à jour et du stockage de la distribution de probabilité des classes (clusters) dépend du nombre de valeurs prises par chaque attribut. Lorsque le nombre de valeurs d’attribut est élevé, la complexité temporelle et spatiale de l’algorithme sera grande.
• Les données d’exemples biaisées peuvent entraîner une hauteur de l’arbre de hiérarchie conceptuelle très déséquilibrée, ce qui peut également entraîner des variations drastiques de la complexité temporelle et spatiale.