Le Data Mining: Méthodologie
Définition et introduction
Principales applications
Méthodologie du DM
Exemples de fonctionnement
1
1. Emergence du domaine
Workshops
1991, 1993, 1994
International Conf. on KDD and DM
1995, 1996, 1997, 1998, 1999
Data Mining and Knowledge Discovery Journal
(1997)
Special Interest Group Knowledge Discovery in
Databases (1999) de l’Association for Computing
Machinery (ACM)
2
Métaphore
Par analogie à la recherche des pépites d ’or
dans un gisement, la fouille de données vise :
à extraire des informations cachées par analyse
globale
à découvrir des modèles (“patterns”) difficiles à
percevoir car:
le volume de données est très grand
le nombre de variables à considérer est important
ces “patterns” sont imprévisibles (même à titre
d ’hypothèse à vérifier)
3
Définition
Data mining
ensemble de techniques d'exploration de données
afin d'en tirer des connaissances (la signification
profonde) sous forme de modèles présentés à
l ’utilisateur averti pour examen
Données Data
entrepôt mining Connaissances
Découverte de Compréhension
modèles Prédiction
4
Découverte de modèles
x1 c Confiance
Entrées x2
x3 y
Sortie
MODELE
x1 x2 x3 y
1 10 100 alpha
2 20 200 beta
5
Découverte et Exploitation
Training Data Mining Model Data to Predict
DM DM
Engine Engine
Mining Model Mining Model Predicted Data
6
Connaissances
Knowledge Discovery in Databases (KDD)
Processus complet d’Extraction de Connaissance des
Données (ECD)
Comprend plusieurs phases dont le data mining
Exemples
analyses (distribution du trafic en fonction de l ’heure)
scores (fidélité d ’un client), classes (mauvais payeurs)
règles (si facture > 10000 et mécontent > 0.5 alors
départ à 70%)
7
Le processus de KDD
8
Etapes du processus
1. Compréhension du domaine d’application
2. Création du fichier cible (target data set)
3. Traitement des données brutes (data cleaning and preprocessing)
4. Réduction des données (data reduction and projection)
5. Définition des tâches de fouille de données
6. Choix des algorithmes appropriés de fouille de données
7. Fouille de données (data mining)
8. Interprétation des formes extraites (mined patterns)
9. Validation des connaissances extraites
(source : Fayyat et al., 1996, p. 1-34)
9
Mécanismes de base
Déduction : base des systèmes experts
schéma logique permettant de déduire un théorème à
partir d'axiomes
le résultat est sûr, mais la méthode nécessite la
connaissance de règles
Induction : base du data mining
méthode permettant de tirer des conclusions à partir
d'une série de faits
généralisation un peu abusive
indicateurs de confiance permettant la pondération
10
2. Domaines d'application
De plus en plus de domaines
explosion des données historisées
puissance des machines support
nombreux datawarehouses
OLAP limité
nécessité de mieux comprendre
rapports sophistiqués, prédictions
aide efficace aux managers
11
Quelques domaines réputés
Analyse de risque (Assurance)
Marketing
Grande distribution
Médecine, Pharmacie
Analyse financière
Gestion de stocks
Maintenance
Contrôle de qualité
12
Exemples
Targeted ads
“What banner should I display to this visitor?”
Cross sells
“What other products is this customer likely to buy?
Fraud detection
“Is this insurance claim a fraud?”
Churn analysis
“Who are those customers likely to churn?”
Risk Management
“Should I approve the loan to this customer?”
13
Churn Analysis
Application de télécom
Bases de données des clients et des appels
Fichiers des réclamations
Qui sont les clients le plus susceptibles de
partir ?
Application de techniques de DM
Fichiers de 1000 clients les plus risqués
600 ont quittés dans les 3 mois
14
Trading Advisor
Application boursière
conseil en achat / vente d'actions
Données de base
historique des cours
portefeuille client
Analyse du risque
Analyse technique du signal
Conseils d'achat – vente
Mise à disposition sur portail Web
15
3. Méthodologie -1
1. Identifier le 2. Préparer les données
problème préciser les sources
cerner les objectifs collecter les données
trouver les sources nettoyer les données
définir les cibles transformer les données
vérifier les besoins intégrer les données
16
Méthodologie - 2
3. Explorer des modèles 5. Suivre le modèle
choisir une technique bâtir des estimateurs
échantillonner sur un groupe
corriger et affiner le
valider sur le reste (5% à
1/3) modèle
calculer le d ’erreurs
4. Utiliser le modèle
observer la réalité
recommander des actions
17
Explorer des modèles :
SEMMA
Sampling = Échantillonner
tirer un échantillon significatif pour extraire les modèles
Exploration = Explorer
devenir familier avec les données (patterns)
Manipulation = Manipuler
ajouter des informations, coder, grouper des attributs
Modelling = Modéliser
construire des modèles (statistiques, réseaux de neuronnes, arbres
de décisions, règles associatives, …)
Assessment = Valider
comprendre, valider, expliquer, répondre aux questions
18
Validation d’un modèle
Matrice de confusion
comparaison des cas observés par rapport aux prédictions
exemple : prédiction de factures impayées
Prédit Observé
Payé Retardé Impayé Total
Payé 80 15 5 100
Retardé 1 17 2 20
Impayé 5 2 23 30
Total 86 34 30 150
Validité du modèle
nombre exacte (diagonale) / nombre totale = 120/150 = 0.80
19
Principales Techniques
Dérivées
des statistiques (e.g., réseaux bayésiens)
de l'analyse de données (e.g., analyse en composantes)
de l'intelligence artificielle (e.g., arbres de décision, réseaux
de neurones)
des bases de données (e.g., règles associatives)
Appliquées aux grandes bases de données
Difficultés :
passage à l'échelle et performance
fonctionnement avec échantillon > qq milliers
présentation et validation des résultats
20
4. Quelques produits
Intelligent Miner d'IBM Oracle 10g ODM
modélisation prédictive (stat.),
groupage, segmentation,
analyse d'associations,
détection de déviation, analyse SQL Server DM
de texte libre
SAS de SAS
Statistiques, groupage, arbres DB2 V8
de décision, réseaux de
neurones, associations, ...
SPSS de SPSS
statistiques, classification,
réseaux de neurones
21
SAS
22
INPUT
Choix des variables
23
SAMPLING
Choix du type d'échantillon
24
INSIGHT
Analyse des données en 4D
25
TRANSFORM
Transformation pour préparer
26
PARTITION
Création de partition d'exploration parallèle
27
REGRESSION
Sélection de la méthode de régression
28
DECISION TREE
Construction d'un arbre par 2
29
NEURONES
Spécification d'un réseau de neurones
30
ASSESSMENT
Validation des résultats
31
Approches
De multiples approches:
Statistiques
Classification
Clustering
Règles associatives
…
32
Méthodes d'analyse
1 ... J ... p
1
.
.
Table
Table = i
.
.
n
1 ... J ... p 1 ... J ... p
1 1
. .
. .
Table = i Table = i
. .
. .
n n
Points dans Rp Points dans Rn
33
Familles de méthodes
Nuage de points
Visualisation dans Regroupement
Le meilleur espace réduit dans tout l'espace
METHODES STATISTIQUES METHODES DE CLASSIFICATION,
ET FACTORIELLES SUPERVISEE OU NON …
34
5. Méthodes statistiques
Quelques techniques de base
A la limite du DM
Calculs d'information sophistiqués
35
Fonctions Statistiques
Espérance
permet de calculer la moyenne pondérée d'une
colonne pi = 1/N par défaut
Variance
traduit la dispersion de la distribution de la v.a.
autour de sa valeur moyenne.
Variable centrée réduite
Permet d'éliminer le facteur dimension
36
Diagrammes en bâtons
Catégorie d'employé
400
Comptage de fréquence 300
COUNT 200
Extension aux calculs 100
Fréquence
d'agrégats 0
Secrétariat Cadre Responsable
AVG, MIN, MAX, …
Catégorie d'employé
Possibilité d'étendre au
100
3D 80
60
North
East
West
40
North
Apporte une vision
West
20
East
0
1st 2nd 3rd 4th
synthétique Qtr Qtr Qtr Qtr
37
Tableaux croisés
(Vision 2D du Datacube)
Tableau croisé Catégorie d'employé * Sexe de l'employé * Classe minoritaire ?
Classe minoritaire ?: Non
Effectif Effectif théorique
Catégorie Secrétariat Sexe de l'employé Masculin 110 144,7
d'employé Féminin 166 131,3
Total 276 276,0
Cadre Sexe de l'employé Masculin 14 7,3
Féminin 0 6,7
Total 14 14,0
Responsable Sexe de l'employé Masculin 70 41,9
Féminin 10 38,1
Total 80 80,0
Total Sexe de l'employé Masculin 194 194,0
Féminin 176 176,0
Total 370 370,0
Effectif théorique = calculé par une loi de distribution
(uniforme)
38
Corrélation
Covariance
La covariance peut être vue comme le moment centré
conjoint d'ordre 1 de deux v.a.
Si les deux v.a. sont indépendantes, alors leur covariance
est nulle (mais la réciproque n'est pas vraie en général).
Coefficient de corrélation
Elimine le facteur dimension
mesure la qualité de la relation linéaire entre deux
variables aléatoires
39
Droite de régression
$160,000
Salaire actuel = 1928,21 + 1,91 * saldeb
Régression linéaire
R-Deux = 0,77
199
$120,000
Y=aX+b
120
70
Salaire actuel
$80,000
$40,000
$20,000 $40,000 $60,000 $80,000
Salaire d'embauche
40
Test du 2
Détermine l'existence d'une dépendance
entre deux variables
Exemple : salaire d'embauche, niveau d'étude
Compare la distribution des variables par
rapport à une courbe théorique supposant
l'indépendance
41
De nombreuses fonctions
Test t sur moyenne
ANOVA
Analyses de variance sophistiquées
Corrélation partielle
Régresion logistique
Séries chronologiques
Lissage exponentiel, Moyenne mobile, …
Comparaison
…
42
Calculs en SQL
Introduction de fonctions d'agrégats
AVG = moyenne
MAVG = moyenne mobile
STDDEV = écart type
VARIANCE = variance
COVARIANCE = covariance
…
Exemple
SELECT COVARIANCE(SALAIRE_ACTU, SALAIRE_EMB)
FROM EMPLOYEE
WHERE GRADE = "ingénieur"
GROUP BY SEXE
43
Statistiques: Conclusion
Calculs statistiques sur variables
Mono ou bi-variées
Résumé des données
Observation de dépendances
Peu de modèles prédictifs ...
La plupart sont faisables avec SQL OLAP
Extensions cube et rollup
Extensions avec fonctions d'agrégats
44
6. Conclusion
Le data mining vise à Questions ?
découvrir des modèles à
partir de grandes bases de
Quoi de nouveau par
faits connus rapport à l'IA et aux
(datawarehouse) statistiques ?
Le processus de
construction de modèles est
complexe
préparer les données
modéliser 1/3 de la base
valider sur 2/3
expérimenter plusieurs
modèles
45
DM, Stat., IA
DM Stat. IA
Tableau individu -variable Formalisme de la logique
Calculs numériques Induction/déduction
Recherche de règles Méthodes de discrimination Apprentissage supervisé/ex.
de classement Réseaux de neuronnes -Génèr° de règles
Segmentation -Constr° d'arbre de décision
-Raisonnement à base de cas
Régression Méthodes de régression
Réseaux de neuronnes _
Classification Classif° automatique hiérarchique Apprentissage non supervisé
automatique Partitionnement -Classif° conceptuelle
Réseaux de neuronnes
Description Stat. Élémentaire (histogramme, Apprentissage non supervisé
synthétique moy, écart-type) -Généralisation
Outils d'interprét° de classes
Méthodes factorielles (ACP)
Recherche de Corrélations Apprentissage non supervisé
dépendances Analyse factorielles des corr. -Généralisation
(AFC) -Recherche d'associations
Réseaux bayésiens
Détection de Test stat sur les écarts
déviations
_
46
