Plan

Introduction aux méthodes de Fouille de 1. Typologies des méthodes de fouille de données

données 2. Segmentation par la méthode des k-moyennes
! Objet de la segmentation
(10) ! Méthode des k-moyennes (k-mean)

Bernard ESPINASSE 3. Méthodes des règles dʼassociation

Professeur à Aix-Marseille Université (AMU) ! Objet de lʼassociation
Ecole Polytechnique Universitaire de Marseille
! Méthode des règles dʼassociation
4. Classification / Prédiction par les Arbres de décision
Septembre 2009
! Objet de la classification et de la prédiction
! Méthode des arbres de décision
• Rappel typologies des méthodes de fouille de données
5. Classification par la méthode des k-plus proches voisins
• Segmentation par la Méthode des k-moyennes
! Méthode des k-plus proches voisins
• Méthodes des Règles dʼAssociation 6. Classification / Prédiction par les réseaux de neurones
• Classification/Prédiction par les Arbres de décision ! Méthode des Réseaux de Neurones (Perceptron multi-couches)
! Autres méthodes de classification
• Classification par la Méthode des k-Plus proches voisins ! Conclusion sur la classification / prédiction
• Classification/Prédiction par les Réseaux de neurones

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 1 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 2

Références bibliographiques
Ouvrages :
! Franco J-M., « Le Data Warehouse et le Data Mining ». Ed. Eyrolles, Paris, 1997.
ISBN 2-212-08956-2.
! Gardarin G., « Internet/intranet et bases de données », Ed. Eyrolles, Paris, 1999, ISBN
2-212-09069-2.
! Han J., Kamber M., « Data Mining: Concepts and Techniques », Morgan Kaufmann
Publishers, 2004.
! Lefébure R., Venturi G., « Le data Mining », Ed. Eyrolles, Paris, 1998. ISBN 2-212-
1 – Typologies des méthodes de
08981-3.
! Tufféry S., « Data Mining et statistique décisionnelle », Ed. Technip, Paris, 2005, ISBN
2-7108-0867-6.
fouille de données
!…
Cours : ! Typologie selon objectifs
! Cours de A. Rakotomamonjy, INSA Rouen, Lab. PSI, Rouen. ! Typologie selon le type de modèle obtenu
! Cours de G. Gardarin, Univ. de Versailles
! Cours de J. Han et M. Kamber M., Simon Fraser Univ., Vancouver BC, Canada ! Typologie selon le type dʼapprentissage
! Cours de M. Adiba et M.C. Fauvet, Univ. Grenoble
! Quelques méthodes de fouille de données
! Cours de R. Gilleron et M. Tommasi, Lab. LIFL., Univ. Charles De Gaulle-Lille 3
! Cours de R. Rakotomalala, Univ. Lumière Lyon 2, Lab. ERIC Lyon
! Cours du Lab. « Bases de données » de lʼEPFL
! …

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 3 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 4
Typologie selon objectifs Typologie selon le type de modèle obtenu
Types dʼobjectifs : Types de modèles obtenus :
! Classification :
! consiste à examiner les caractéristiques d'un objet et lui attribuer une ! Modèles prédictifs :
classe : ! utilisent les données avec des résultats connus pour développer des
• attribuer ou non un prêt à un client modèles permettant de prédire les valeurs d'autres données
• établir un diagnostic
Ex: modèle permettant de prédire les clients qui ne rembourseront pas
! Prédiction :
leur crédit
! consiste à prédire la valeur future d'un attribut en fonction d'autres
attributs : ! utilisé principalement en classification et prédiction
• prédire la "qualité" d'un client en fonction de son revenu, de son
nombre d'enfant,... ! Modèles descriptifs :
! Association : ! proposent des descriptions des données pour aider à la prise de décision
! consiste à déterminer les attributs qui sont corrélés :
! aident à la construction de modèles prédictifs
• analyse du panier de la ménagère: ex. poisson et vin blanc
! Segmentation : ! utilisés principalement en segmentation et association
! consiste à former des groupes homogènes à l'intérieur d'une population
! tâche souvent faite avant les précédentes pour trouver les groupes sur
lesquels appliquer la classification.

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 5 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 6

Typologie selon le type dʼapprentissage Quelques méthodes de fouille de données

Types d'apprentissage utilisés dans les méthodes de fouille : Supervisées Non spervisées
Segmentation ! k moyennes (K-means)
! Apprentissage supervisé - Fouille supervisée : ! k plus proches voisins (PPV-
! processus dans lequel l'apprenant reçoit des exemples d'apprentissage raisonnement à partir de cas)
comprenant à la fois des données d'entrée et de sortie ! Réseaux de neurones avec cartes
de Kohonen
! les exemples dʼapprentissage sont fournis avec leur classe (valeur de ! …
sortie prédite) Classification ! Arbres de décision ! k plus proches voisins (PPV-
Prédiction ! Réseaux de neurones avec raisonnement à partir de cas)
! But : classer correctement un nouvel exemple (généralisation)
Perceptron ! Règles temporelles
! utilisées principalement en classification et prédiction ! (raisonnement à partir de cas) ! Recherche de séquences
! Modèles / réseaux bayésiens ! Reconnaissance de formes
! Apprentissage non supervisé - Fouille non supervisée : ! Machines à vecteur supports ! …
! processus dans lequel l'apprenant reçoit des exemples d'apprentissage (SVM)
ne comprenant que des données d'entrée ! programmation logique inductive
! …
! pas de notion de classe Prédiction ! Arbres de décision ! k plus proches voisins (PPV-
! But : regrouper les exemples en « paquets » (clusters) dʼexemples ! Réseaux de neurones avec raisonnement à partir de cas)
similaires (on peut ensuite donner un nom à chaque paquet) Perceptron ! …
! …
! utilisé principalement en association et segmentation Association Règles dʼassociation

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 7 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 8
 Objectifs de la segmentation (ou clustering)
Face à une grande population (dʼexemples) à étudier, il peut sʼavérer judicieux de
commencer par diviser en groupes (clusters) la population, la segmenter
la segmentation est une tâche dʼapprentissage NON supervisée car on nʼa rien
dʼautre que les exemples (pas de classes)
Méthode de segmentation :
1 – Méthode de segmentation ! méthode permettant de découvrir les groupes (clusters) d'individus
similaires en se basant sur une mesure de similarité (ou distance)
des k-moyennes (k-mean) pour grouper les données
! on ne connaît pas les classes à priori : elles sont à découvrir
! Objectifs de la segmentation (ou clustering) automatiquement
! Buts : Maximiser la similarité intra-classes et minimiser la similarité
! La méthode des K-moyennes inter-classes.
! Problème de mise en œuvre Méthodes de segmentation par partitionnement :

! Autres méthodes pour la segmentation ! Construire k partitions et les corriger jusqu'à obtenir une similarité
satisfaisante
! Conclusion sur la Méthode des K-moyennes ! Méthode des k-moyennes (k-mean) [Mac Queen 67]

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 9 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 10

Méthode des K-moyennes Méthode des K-moyennes

Méthode basée sur une notion de similarité entre enregistrements : Algorithme des K-moyennes ou K-mean (k clusters, n objects):
! on considère un espace géométrique muni dʼune distance : 2 points sont ! choisir aléatoirement k objets comme centres de cluster
similaires sʼils sont proches pour la distance considérée ! assigner chaque objet au centre le plus proche
! recalculer les k centres
! on considère un nombre limité de champs dʼenregistrements ! tant que les k centres ont étéchangés
! réassigner les tuples
! on se place dans lʼespace euclidien de dimension 2, munie de la distance
! recalculer les k centres
euclidienne classique
Illustration :
Principe général de lʼalgorithme :
! on a choisi (au hasard) un nombre k de groupes à constituer
! on choisi k enregistrements, soit k points de lʼespace appelés « centres »
! on constitue alors les k groupes initiaux en affectant chacun des
enregistrements dans le groupe correspondant au centre le plus proche
! pour chaque groupe constitué on calcule son nouveau centre (de gravité) en
affectant la moyenne des points du groupe et on réitère le procédé
! critère dʼarrêt : si aucun point nʼa changé de groupe, les groupes sont stables 1. cluster initiaux 2. recalcul des centres 3. reconstruction des clusters
par rapport aux nouveaux
centres
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 11 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 12
Méthode des K-moyennes Méthode des K-moyennes : problèmes de mise en oeuvre
Exemple (Gilleron & Tommasi) :
étape 1 étape 2 étape 3
Mise en œuvre de K-means dans les BD réelles plus complexe :
centre D(2;4) centre D(2;4) centre J(5/3;10/3)
centre B(2;2) centre I(27/7;17/7) centre K(24/5;11/5)
Problème 1 : Proximité/similarité entre les données
points groupe groupe groupe ! les BD constituées d'enregistrements, les données (des clients, des produits,
A(1;3) B D J
des ventes) ont peu de rapport avec des points
B(2;2) B I J
C(2;3) B D J ! nécessité de définir une mesure de proximité/similarité entre ces données
D(2;4) D D J (points proches = enregistrements similaires dans la BD).
E(4;2) B I K
F(5;2) B I K Si enregistrement avec champs à valeurs continues :
G(6;2) B I K ! mesure de similarité = distance euclidienne entre 2 points
H(7;3) B I K
! nécessite en général une normalisation des échelles pour les différents
• Données d'entrée : 8 points A, ..., H de l'espace euclidien de dimension 2
champs : si un champ A prend ses valeurs dans l'intervalle réel [0,1] et un
• On choisit k=2 : on cherche à constituer deux groupes dans cet ensemble de 8 points
• On tire aléatoirement les 2 centres initiaux : B et D choisis champ B ses valeurs dans [0,100 000], B est privilégié, car 2 enregistrements
• On répartit les points dans les 2 groupes (nommés B et D) en fonction de leur proximité aux centres B et seront considérés proches si les valeurs pour le champ B sont proches.
D. Géométriquement, il suffit de tracer la médiatrice du segment [BD]. Seul D est affecté au groupe D. Si enregistrements avec champs à valeurs discrètes :
• On calcule les nouveaux centres pour l'étape 2, on obtient D et I (26/7;17/7) où les coordonnées de I
sont les moyennes des coordonnées des 7 points autres que D. ! une mesure de similarité usuelle : étant donné 2 enregistrements x et y, la
• On recrée les groupes en fonction de leur proximité aux centres D et I, on remarque que A et C similarité est égale au rapport entre le nombre de champs égaux divisé par le
changent de groupe. nombre total de champs (nombreuses variantes existent).
• Le procédé est réitéré, la stabilité est obtenue à l'étape 4 car on constate que les groupes ne sont plus
modifiés : les 2 groupes obtenus sont {A, B, C, D} et {E, F, G, H}.

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 13 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 14

Méthode des K-moyennes : problèmes de mise en oeuvre Autres méthodes pour la segmentation
Problème 2 : choix initial du nombre de groupes Méthode ascendante, utilisant un algorithme d'agglomération :
! Ce nombre est choisi a priori et fourni à l'algorithme • A partir d'un échantillon de m enregistrements, on commence avec m groupes, chacun
! Il peut avoir été fixé par un expert mais en règle générale, il est inconnu des groupes est constitué d'un enregistrement :
• On calcule la matrice des distances 2 à 2 entre enregistrements.
• On choisit la plus petite valeur dans cette matrice des similarités, elle identifie la
Sʼil est inconnu : paire de groupes les plus similaires.
• on fait fonctionner l'algorithme avec différentes valeurs de k (boucle • On regroupe ces 2 groupes en un seul, on remplace les 2 lignes par une ligne pour
externe ajoutée à l'algorithme) le groupe ainsi créé.
• on choisit ensuite une valeur de k telle que, pour les groupes obtenus : • On réitère jusqu'à obtenir un groupe constitué de tous les enregistrements.
! les distances à l'intérieur du groupe soient petites et • On a ainsi construit une suite de partitions de l'échantillon d'entrée où le nombre k
! les distances entre centres des groupes soient grandes. de groupes varie de m à 1.
• On choisit ensuite la valeur de k (différentes méthodes possibles)

L'algorithme possède de nombreuses variantes selon : Méthode ascendante, utilisant des arbres de décision :
• On démarre avec un groupe constitué de l'ensemble des enregistrements et on
• la méthode utilisée pour choisir les k premiers centres, divise récursivement les groupes en utilisant une fonction de diversité minimisant la
• la mesure de similarité choisie, distance moyenne dans un groupe et maximise la distance entre groupes.
• le choix de la valeur de k et le calcul des distances entre groupes, • On choisit ensuite la valeur de k (différentes méthodes possibles pour ce choix)
• la possibilité de pondérer les champs en fonction d'une connaissance Méthode par réseaux de neurones (cartes de Kohonen) :
initiale du problème. • les cartes de Kohonen (réseaux de neurones auto-organisés) sont bien adaptées à
la segmentation
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 15 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 16
Conclusion sur la Méthode des K-moyennes
Apprentissage non supervisé :
! elle réalise une tâche dite « non supervisée », en ne nécessitant pas information sur
les données
! elle peut permettre, en segmentation, de découvrir une structure cachée pouvant
améliorer les résultats de méthodes d'apprentissage supervisé (classification,
estimation, prédiction)
Type de données :
! elle peut s'appliquer à tout type de données (mêmes textuelles), en choisissant une 3 – Les Règles dʼassociation
bonne notion de distance
Facile à implanter : ! Introduction aux règles dʼassociation
! elle demande peu de transformations sur les données (excepté normalisations de
valeurs numériques), pas de champ particulier à identifier, les algorithmes sont faciles à ! Tableau de co-occurrence
implanter et généralement disponibles dans les environnements de fouille
Performance et sensibilité : ! Notions de support, de confiance et dʼamélioration
! ses performances (qualité des groupes constitués) dépendent du bon choix d'une
mesure de similarité (délicat quand les données sont de types différents) ! Extraction des règles dʼassociation
! elle est sensible au choix des bons paramètres : choix de k (groupes à constituer)
Interprétation des résultats : ! Conclusion sur les règles dʼassociation
! il est difficile d'interpréter les résultats produits, d'attribuer une signification aux groupes
constitués (vrai pour toutes les méthodes de segmentation).

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 17 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 18

Introduction aux règles dʼassociation (1) Introduction aux règles dʼassociation (2)
! Elles sont principalement utilisées dans le domaine de la distribution, en marketing, ! Domaines dʼutilisation :
pour « l'analyse du panier de la ménagère » pour : ! tout domaine où lʼon veut rechercher des groupements potentiels de
! rechercher des associations entre produits sur les tickets de caisse, produits ou de services (services bancaires, services de télécommunications)
notamment pour savoir quels produits tendent à être achetés ensemble ! domaine médical : recherche de complications dues à des associations
de médicaments
! étudier de ce que les clients achètent pour obtenir des informations sur qui ! recherche de fraudes : rechercher des associations inhabituelles
sont les clients et pourquoi ils font certains achats
! Intérêt de la méthode :
! Exemple de règles dʼassociation pour lʼanalyse du panier de la ménagère : ! la clarté des résultats produits : un ensemble de règles d'association
! SI un client achète des plantes ALORS il achète du terreau ! ces règles sont en général faciles à interpréter
! SI un client achète du poisson et du citron ALORS il achète ! elles peuvent être facilement réutilisées dans le SI de l'entreprise
du vin blanc ! Limites de la méthode : si elle peut produire des règles intéressantes, elle peut
aussi produire des :
! SI un client achète une télévision, ALORS il achètera un
magnétoscope dans un an ! règles triviales (déjà bien connues des intervenants du domaine) ou
! règles inutiles (provenant de particularités de l'ensemble d'apprentissage).
! La recherche de règles d'association = méthode non supervisée car on ne
dispose en entrée que de la description des achats.

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 19 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 20
Règles dʼassociation : un exemple Tableau de co-occurence
Exemple (Gilleron & Tommasi) : ! Liste des achats :
! on suppose avoir prédéfini une classification des articles produit A produit B produit C produit D produit E
achat 1 X X
! les données d'entrée sont constituées d'une liste d'achats achat 2 X X X
achat 3 X X
! un achat est lui-même constitué d'une liste d'articles. achat 4 X X X
achat 5 X X
! les achats peuvent être de longueur variable (contrairement aux
enregistrements d'une table) ! Pour trouver les associations entre 2 produits, on construit le tableau de co-
occurrence montrant combien de fois 2 produits ont été achetés ensemble :
! Soit la liste des achats : produit A produit B produit C produit D produit E
produit A 4 1 1 2 1
produit A produit B produit C produit D produit E produit B 1 2 1 1 0
achat 1 X X produit C 1 1 1 0 0
achat 2 X X X produit D 2 1 0 3 1
achat 3 X X produit E 1 0 0 1 2
achat 4 X X X ! permet de déterminer avec quelle fréquence 2 produits se rencontrent dans un même achat :
achat 5 X X Ex : le produit A apparaît dans 80% des achats, le produit C n'apparaît jamais en même
temps que le produit E, les produits A et D apparaissent simultanément dans 40% des
achats.
! Ces observations peuvent suggérer une règle de la forme : « SI un client achète le produit A
ALORS il achète le produit D ».

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 21 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 22

Notions de support et de confiance (1) Notions de supports et de confiance (2)

Une règle n'est pas toujours vraie, aussi on a 2 indicateurs : support et confiance ! Considérons les règles relatives à notre exemple :
d'une règle « si X alors Y » : • si A alors B (règle 1)
! Support : • si A alors D (règle 2)
! fréquence dʼapparition simultanée des items (articles) qui apparaissent dans la • si D alors A (règle 3)
condition et dans le résultat dans la liste des transactions (achats) ! Supports des règles :
! Support (XY) = !XY!/ !BD ! avec • A et B apparaissent dans 20% des achats,
• A et D apparaissent dans 40% des achats,
• !XY!nombre transactions comportant items (articles) X et Y
• !BD!nombre transactions (achats) sur lʼensemble de la base " support de la règle 1 = support(AB) = 1/5 = 20%
Ex: 5% des clients ont acheté X et Y " support des règles 2 et 3 = support(AD) support(DA) = 2/5 = 0,4 = 40%
! Confiance des règles :
! Confiance :
• Considérons les règles 2 et 3, c'est-à-dire les produits A et D.
! rapport entre le nombre de transactions (achats) où tous les items (articles)
• D apparaît dans 3 achats dans lesquels A apparaît 2 fois.
figurants dans la règle apparaissent et le nombre de transaction (achats) où les
• Par contre, A apparaît dans 4 achats dans lesquels D n'apparaît que 2 fois.
items (articles) de la partie condition apparaissent (vérifiant lʼimplication X " Y)
• confiance de la règle 3 = support(DA)/support(D) = 0,4/ (3/5) = 0,4/0,6 = 67%
! Confiance (X "Y) = !XY!/ !X ! • confiance de la règle 2 = support(AD)/support(A) = 0,4/ (4/5) = 0,4/0,8 = 50%
! Confiance (XY) = Support (XY)/Support(X) " On préfère ainsi la règle 3 (D alors A) à la règle 2 (A alors D)
Ex: Parmi les clients ayant acheté des X, 90% ont également acheté Y ! On peut généraliser à toutes les combinaisons d'un nombre quelconque d'articles, ainsi
! Seules les règles ayant une certaine valeur de support et de confiance sont pour 3 articles, on cherche à générer des règles de la forme « si X et Y alors Z »
intéressantes ! Mais le support et la confiance ne sont pas toujours suffisants
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 23 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 24
Notions de supports et de confiance (3) Notion dʼamélioration
! En effet, considérons 3 articles A, B et C et leurs fréquences d'apparition : ! Aussi on introduit « l'amélioration » permettant de comparer le résultat de la
article(s) A B C A et B A et C B et C A et B et C prédiction en utilisant la règle avec la prédiction sans la règle :
fréquence 45% 42,5% 40% 25% 20% 15% 5% amélioration = confiance / fréquence(résultat)
! Si on considère les règles à 3 articles, elles ont le même niveau de support = 5% ! Une règle est intéressante lorsque l'amélioration est supérieure à 1.
! Niveau de confiance des 3 règles est :
! Dans notre exemple on a :
Règle confiance
Règle confiance f(résultat) amélioration
si A et B alors C 0.20
si A et B alors C 0.20 40% 0.50
si A et C alors B 0.25
si B et C alors A 0.33 si A et C alors B 0.25 42.5% 0.59

! La règle si B et C alors A possède la plus grande confiance = 0,33 => si B et C si B et C alors A 0.33 45% 0.74
apparaissent simultanément dans un achat, alors A y apparaît aussi avec une ! la règle « si A alors B » possède un support de 25%, une confiance de 0.55 et une
probabilité estimée de 33%. amélioration de 1.31 => cette règle est la meilleure
! Mais, si on regarde le tableau des fréquences d'apparition des articles, on constate
! En règle générale, la meilleure règle est celle qui contient le moins d'articles.
que A apparaît dans 45% des achats
=> Il vaut mieux prédire A sans autre information que de prédire A lorsque B et C
apparaissent.

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 25 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 26

Extraction des règles dʼassociation (1) Exemple dʼextraction des règles dʼassociation
Extraction des règles : Exemple (issu du cours EPFL):

! seules les règles ayant un certain support et une certaine valeur de confiance Etape 1 : calcul des ensembles fréquents
sont intéressantes :
! calcul du support de toutes les combinaisons dʼitems possibles de la base
• valeurs de minconf et minsup doivent être fixées par l'analyste
! La plupart des méthodes pour extraire des règles :
• retiennent les règles dont le support > minsup
• et parmi celles-ci retiennent celles dont la confiance > minconf
Génération de règles :
! calcul du support de toutes les règles obtenues par combinaisons dʼitems
possibles de la base
! on ne garde que les règles dont le support est supérieur à un seuil donné =
« ensembles fréquents »
! on ne garde que règles dont le support est supérieur à un seuil donné =
ensembles fréquents

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 27 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 28
Extraction des règles dʼassociation (3) Extraction des règles dʼassociation (4)
Etape 2 : recherche des sous-ensembles fréquents Génération d'un k-ensemble fréquent :
Un ensemble de k éléments est appelé « k-ensemble »
! A partir des 1-ensemble fréquents on génère des 2-ensembles fréquents,
Lemme de base:
! A partir des 2-ensemble fréquents on génère des 3-ensembles fréquents,
! Tout k-ensemble fréquent est composé de sous-ensembles fréquents
! ainsi un 3-ensemble fréquent est composé de 2-ensembles et de 1-ensembles ! ...
fréquents
Règle de génération : procédure apriori-gen
Procédure:
! 1) on cherche les 1-ensembles fréquents ! L'algorithme génère un candidat de taille k à partir de 2 candidats de taille k-1
différents par le dernier élément
! 2) on cherche les 2-ensembles fréquents
! ... ! on garde ce candidat s'il ne contient pas de k-1 ensemble qui n'est pas
! n) on cherche les n-ensembles fréquents fréquent
ceci jusqu'à ce qu'il n'y ait plus d'ensemble fréquent de taille supérieure

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 29 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 30

Extraction des règles dʼassociation (5) Extraction des règles dʼassociation (6)
Exemple: Algorithme APriori :
! les 2-ensembles fréquents obtenus à partir des 1-ensembles fréquents sont : L1 = {frequent1-ensemble} ;
{1,3,5} et {2,3,5}
for (k = 2 ; Lk-1 =! # ; k++) do {
! On ne garde que {2,3,5} parce que {1,3,5} comprend le 2-ensemble fréquent
{1,5} qui ne fait pas partie des 2-ensembles fréquents => {1,3,5} n'est pas un Ck= apriori-gen(Lk-1); // Génération nouveaux candidats
3-ensemble fréquent k-ensemble fréquents
for eachtransactions t $ DBdo { //Comptage
Ct= { subset(Ck, t) }; // sous-ensembles de la BD
foreach c $ Ct do c.count++; } comptage support
{1,3}
Lk= { c $ Ck |c.count>= minsup} ;// Filtrer par rapport
{2,3}
{2,5} au support
{3,5} }
Answer= {Lk} ;

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 31 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 32
Extraction des règles dʼassociation (7) Extraction des règles dʼassociation (8)
Exemple: Génération des règles
! A partir des k-ensembles fréquents:
! pour chaque ensemble fréquent l, générer tous les sous-ensembles s non
vides
! pour chaque sous-ensemble s, si Confiance (s "l –s) > minconf, générer la
règle "s "l –s"
Exemple :
! {2,3,5}: sous-ensembles non vides: {2}, {3}, {5}, {2,3}, {2,5}, {3,5}
! Confiance (X "Y) = Support (XY)/Support(X)
Règles:
• 2 et 3 " 5 Confiance = 2/2 = 100%
• 2 et 5 " 3 Confiance = 2/3 = 66%
• 3 et 5 " 2 Confiance = 2/2 = 100%
• 2 " 3 et 5 Confiance = 2/3 = 66%
• 3 " 2 et 5 Confiance = 2/3 = 66%
• 5 " 2 et 3 Confiance = 2/3 = 66%
Si seuil = 70% on ne garde que les règles 1 et 3

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 33 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 34

Extraction des règles dʼassociation (8) Conclusion sur les règles dʼassociation (1)
Inconvénients de Apriori : • Résultats clairs : les règles d'association sont faciles à interpréter, à utiliser pour
! Beaucoup de candidats : 1041-ensembles vont générer 1072-ensembles des utilisations concrètes
! Plusieurs parcours de la BD (pour calculer les supports) : on doit faire n+1 • Apprentissage non supervisé : elles ne nécessitent pas d'autre information
parcours pour trouver les n-ensembles fréquents qu'une classification en articles et la donnée d'une liste d'articles pour extraire les
! Les indicateurs de support et confiance sont insuffisants : règles.
• support est symétrique : il ne distingue pas A " B de B " A
• Achats de taille variable : une des rares méthodes qui prend en entrée des
• confiance favorise les évenements rares :
achats qui sont des listes d'articles de taille variable
! confiance (A "B ) = Support (AB)/Support(A)
! si Support(A) est faible, Support(AB) aussi et confiance ! • Introduction du temps :
Améliorations de Apriori : • possible d'adapter la méthode pour traiter des séries temporelles pour
! Algorithme AprioriTID qui garde en mémoire les n°de tuples correspondant à générer des règles de la forme : « un client ayant acheté le produit A est
chaque k-ensemble susceptible d'acheter le produit B dans 2 ans »
! Marquer les tuples qui ne contiennent pas de k-ensembles fréquents pour qu'ils • possible d'introduire des « articles virtuels » tels que le jour, la période
ne soient pas lus lorsqu'on considère les j-ensembles fréquents (j>k) ou la saison et limiter la forme des règles si on souhaite rechercher des
! Autres mesures : comportements d'achat qui dépendent du temps.
• conviction : P(X)*P(non Y)/P(X, nonY)
• "lift": Confiance (X " Y)/Support(Y) • Simplicité de la méthode : calculs élémentaires (fréquences d'apparition) :
Autres algorithmes : • peut être programmée sur tableur pour des problèmes de taille raisonnable
! Apriori partitionné, Algorithme de comptage dynamique, FP-Growth, Close, … • généralement disponible dans la plupart des environnements de fouille
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 35 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 36
Conclusion sur les règles dʼassociation (2)
• Coût de la méthode : coûteuse en temps de calcul, le regroupement d'articles et
la méthode du support minimum permettent de diminuer les calculs mais on peut
alors éliminer sans le vouloir des règles importantes.
• Le choix des articles : difficile de déterminer le bon niveau d'articles. Les 4 – Méthodes de Classification /
traitements préalables sur les achats peuvent être complexes : par exemple, il peut
être difficile de retrouver l'article à partir de son code-barre enregistré sur le ticket
de caisse.
Prédiction
• Les articles rares : méthode efficace pour les articles fréquents, pour les articles ! Objet de la classification et de la prédiction
rares, on peut restreindre la forme des règles choisies ou faire varier le support
minimum. ! Méthode des arbres de décision
• La qualité des règles : la méthode peut produire des règles triviales ou inutiles. ! Méthode des k-Plus proches voisins
• Les règles triviales sont des règles évidentes (si camembert alors vin rouge) ! Méthode des Réseaux de Neurones (Perceptron multi-couches)
qui, par conséquent, n'apportent pas d'information.
• Les règles inutiles sont des règles difficiles à interpréter qui peuvent provenir ! Autres méthodes de classification
de particularités propres à la liste des achats ayant servie à l'apprentissage. ! Conclusion sur la classification / prédiction

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 37 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 38

Objet de la classification et de la prédiction Classifications non supervisée et supervisée

• La classification : 2 familles de modèles de classification
! consiste à examiner les caractéristiques d'un objet et lui attribuer une
classe, la classe est un champ particulier à valeurs discrètes. • Classification non supervisée :
! Exemples : ! Établir des représentations des données dans des espaces à faible dimensions
• attribuer ou non un prêt à un client, pour y lire des typologies dʼindividus
• établir un diagnostic, ! Nombre de classes initialement inconnu
• accepter ou refuser un retrait dans un distributeur, ! Méthodes :
• attribuer un sujet principal à un article de presse, ... • Analyse en composante principales (ACP), …
• La prédiction : • Classification supervisée (apprentissage) :
! consiste à prédire la valeur future dʼun champ, en général, à partir de ! Obtenir un critère de séparation destiné à prédire lʼappartenance à une classe
valeurs connues historisées ! Nombre de classes initialement connu
! tâche proche de la classification, les méthodes de classification peuvent être ! Méthodes :
utilisées en prédiction. • Analyse discriminante
! Exemples : • Régression
• prédire les valeurs futures d'actions, • k-Plus proches voisins
• prédire au vu de leurs actions passées les départs de clients. • Arbre de décision "
• Réseau de neurones "
• …
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 39 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 40
Les arbres de décision Exemple 1 dʼarbre de décision
Arbre de décision : Il sʼagit de prédire la valeur de lʼattribut risque à partir des valeur des attributs age
! Objectif général : et type de véhicule (exemple tiré de Gardarin) :
• A partir dʼun ensemble de valeurs d'attributs (variables prédictives ou TupleIdAge Type Voiture Risque Age < 25
variable endogènes) prédicats de partitionnement
0 23 familiale élevé
• il sʼagit de prédire la valeur d'un autre attribut (variable cible ou variable
1 17 sportive élevé Oui Non
exogène)
2 43 sportive élevé TypeVoiture dans
! une des méthodes supervisée (apprentissage) les plus connues de
3 68 familiale faible {Sportive}
classification et de prédiction Oui Non
! un arbre est équivalent à un ensemble de règles de décision : grande 4 32 utilitaire faible élévé
explicabilité du modèle 5 20 familiale élevé
! un arbre est composé : élévé faible
ensemble dʼapprentissage
• de noeuds = classes d'individus de plus en plus fine depuis la racine
Arbre binaire Nœud classes
• dʼarcs = prédicats de partitionnement de la classe source Nœud attribut
dʼindividus
! arbres binaires : 2 branches partent de chaque nœuds Règles de déduction associées :
! arbres n-aire : n branches partent de chaque nœud • Si âge < 25 alors élévé
! algorithmes dʼapprentissage dʼarbre : ID3 [Quilan 79], CART [Brieman et al. • Si âge < 25 et TypeVoiture dans {sportive} alors élevé
84], … • Si âge < 25 et TypeVoiture pas dans {sportive} alors faible

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 41 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 42

Exemple 2 dʼarbre de décision (1) instance

Il sʼagit de prédire si selon la météo (ciel, temp., humidité et vent) on va aller jouer au
tennis :

• instance = fonction x qui associe à tout attribut a la valeur v

• exemple = paire (x, c) où x est une instance et c la classe à prédire pour cette

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 43 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 44
Exemple 2 dʼarbre de décision (2) Principe général de construction dʼun arbre de décision
Soit lʼinstance : • Arbre est construit en découpant successivement les données en
fonction des variables prédictives selon lʼAlgorithme générique :
Segmenter (T)
SI (tous les tuples de T appartiennent à la même classe de
elle est testée (classée) par son chemin depuis la racine jusquʼà la feuille : variable à prédire ou critère d'arrêt) ALORS retourner une
feuille;
Pour chaque attribut prédictif A
évaluer la qualité de découpage selon A
Utiliser l'attribut donnant la meilleure découpe pour
découper en sous-ensembles T1,...,Tn selon les valeurs de A
Pour i = 1..n Segmenter (Ti);
Fin
• Problèmes fondamentaux pour construire l'arbre
1. Choix de l'attribut discriminant
2. Affectation d'un label à une feuille
3. Arrêt de segmentation (choix de la profondeur de l'arbre) : si lʼarbre est trop
profond, il est trop complexe et trop adapté à l'ensemble d'apprentissage =>
Chaque chemin depuis la racine jusquʼà une feuille est une règle de décision, ici : pas assez généraliste
Si (ciel = soleil) et (humidité = élevée) alors (classe = non) 4. Choix des bornes de discrétisation : comment découper les valeurs d'un
attribut continu, par exemple : 1-25 , 25-50, 50-100 ou 1-50, 50-100 ?
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 45 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 46

Construction dʼun arbre de décision Construction dʼun arbre de décision : paramètres

1) Critère de choix de lʼattribut : 3) Arrêt de la segmentation : Différentes techniques:
! Si y est l'attribut dont la valeur à prédire à partir des valeurs des attributs pre-pruning:
prédictifs xi : choisir l'attribut dont la valeur a le plus d'influence sur celle de y On arrête l'expansion de l'arbre selon certains critères:
! Plusieurs techniques provenant de la théorie de l'information de Shannon : • profondeur maximale
• Ratio du Gain ou de lʼEntropie (algo ID3, C5, …) • effectif de chaque sous-groupe: on fixe un seuil (souvent empiriquement)
• indice de Gini (algo CART) • on calcule des mesures comme pour le choix de l'attribut de segmentation
• X2 (gain d'information, X2,...) auquel on associe un seuil en dessous duquel la
Ratio du gain / entropie segmentation sera refusée
! On parle de gain d'information ou d'entropie (concepts inverses) post-pruning:
! On va chercher à choisir l'attribut qui va induire le gain d'information le plus On laisse l'arbre se construire jusqu'au bout
élevé (ou dont l'entropie est la plus basse) On élague lʼarbre en retirant des sous-arbres :
! Intuitivement, l'entropie mesure le degré de désordre qui restera si on • à l'aide d'heuristiques ou
découpe selon cet attribut -> entropie la plus basse est la meilleure • grâce à l'intervention d'un expert,
! Donc pour chaque attribut candidat, on va calculer son entropie et on choisit • l'arbre est élagué tant que l'erreur de l'arbre élagué reste inférieure à celle
celui qui a l'entropie la plus basse. de l'arbre non élagué.
• le nœud duquel on a retiré un sous-arbre devient une feuille et porte le label
2) Affectation d'un label à une feuille : On affecte la modalité la plus fréquente. de la valeur la plus fréquente du sous-arbre

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 47 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 48
Construction dʼun arbre de décision : paramètres Lʼalgorithme ID3 [Quilan 79]
Soit : Classe C : valeur d'attribut à prédire (ex: C1: risque = élevé, C2: risque = faible)
4) Choix des bornes de discrétisation : tuples : ensemble des tuples de l'échantillon, liste_attributs: ensemble des attributs
• On fixe les valeurs candidates comme les valeurs au milieu de 2 Procédure Générer_arbre_décision
valeurs consécutives : Créer un nœud N
si tuples est vide alors
ex: 35, 45, 52... -> 40, 48.5 • retourner une feuille portant le label "Failure"
si tuples sont dans la même classe C alors
• Puis on calcule éventuellement la meilleure valeur parmi celles là • retourner N avec comme label C
grâce à des mesures telles que : si liste_attributs = vide alors
• retourner N avec comme label le nom de la classe la plus
! le gain, fréquente dans l'échantillon
Choisir l’attribut a le plus discriminant parmi liste_attributs
! le X2 Affecter le label « a » au nœud N
Pour chaque valeur ai de a :
! ... • créer une branche issue du nœud N avec condition a s= ai
• Soit ti l'ensemble des éléments tuples vérifiant cette
condition
• Attacher le nœud retourné par
Générer_arbre_décision(ti, liste_attributs – a)

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 49 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 50

Calcul de lʼEntropie Calcul du Gain

Entropie = Quantité d'information nécessaire pour classifier l'exemple Gain (A) = réduction d'entropie (i.e. de désordre) espérée si on utilise A
• Soit S un ensemble de s tuples
• Soit C comprenant m valeurs différentes, définissant Ci classes (i = 1,...,m) • On va alors choisir l'attribut ayant le gain le plus élevé
• Soit si le nombre de tuples de S appartenant à Ci :
• Données :
• I(s1,...sm) = quantité d'information nécessaire pour classifier l'ensemble des tuples
• I(s1,...sm) = - Σ(i=1..m) pi log2(pi) ! Soit S un ensemble de s tuples
! pi: probabilité qu'un tuple appartienne à Ci
! pi=si/s ! Soit C comprenant m valeurs différentes définissant Ci classes (i=1,...,m)
Entropie de l'attribut A = E(A) : ! Soit si le nombre de tuples de S appartenant à Ci
• Soit A un attribut candidat possédant v valeurs {a1 ,..., av}.
• A permet de partionner l'ensemble S en v sous-ensembles {S1,..., Sv} ! Soit A l'attribut candidat
• Si comprend les tuples ayant la valeur ai pour A
• Soit sij le nombre de tuples du sous-ensemble Sj appartenant à Ci
Gain(A) = I(S1 ,..., Sm ) " E(A)
E(A) = " # (S1 j + ...+ Smj ) . I(S1 j ,..., Smj )
( j=1..v)
Pour chaque valeur de A Probabilité qu'un tuple ait cette Qté d'info nécessaire pour classifier
valeur dans ce sous-ensemble les tuples ayant cette valeur

51 52
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE -
!
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE -

!
Exemple de mise en oeuvre (1) Exemple de mise en oeuvre (2)
• Entropie de l'attribut Couleur?
N° Couleur Contour Point ? Forme
! C1: carré ; C2: triangle
1 vert fin non triangle
2 vert fin oui triangle
!
E(A) = " # (S 1j + ...+ Sij ).I(S1 j ,..., Sij )
3 jaune fin non carré ( j=1..v)

4 rouge fin non carré • Pour couleur = rouge (i= carré ou triangle?, j=rouge) :
5 rouge plein non carré ! s11= scarré/rouge= 3 ; s21= striangle/rouge= 2
6 rouge plein oui triangle ! I(s11,s21) = I(3,2) = -3/5 log23/5 - 2/5 log22/5 = 0,971
7 vert plein non carré ! • Pour couleur = vert :
8 vert fin non triangle ! s12= scarré/vert= 2 ; s22= striangle/vert= 3
9 jaune plein oui carré On veut prédire ! I(s12, s22) = I(2,3) = -2/5 log22/5 - 3/5 log23/5 = 0,971
10 rouge plein non carré lʼattribut forme ! • Pour couleur = jaune :
11 vert plein oui carré
! s13= scarré/jaune=4 s23= striangle/jaune=0
12 jaune fin oui carré
! I(s13,s23)=I(4,0)= -4/4 log24/4 - 0/4 log20/4 = 0
13 jaune plein non carré
• E (couleur) = 5/14 I(s11,s21) + 5/14 I(s12, s22) + 4/14 I(s13,s23) = 0,694
14 rouge fin oui triangle
• Gain (couleur) = 0,940 –0,694 = 0,246

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 53 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 54

Exemple de mise en oeuvre (3) Exemple de mise en oeuvre (4)

Gain (Couleur) = 0,246 Gain (Contour) = 0,971
Gain (Contour) = 0,151 Gain (point?) = 0,020
Gain (Point?) = 0,048
-> on choisit Couleur

rouge
rouge
vert jaune
vert jaune

On s'arrête car ce sont tous des carrés

(tous les tuples dans la même classe)
Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 55 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 56
Exemple de mise en oeuvre (5) Exemple de mise en oeuvre (6)

Gain (Contour)=0,020
Gain (point?) =0,971
rouge
rouge

point=non
vert point=oui vert
jaune jaune

plein fin plein fin

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 57 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 58

Exemple de mise en oeuvre (7) Autres algorithmes dʼapprentissage

Arbre de décision obtenu : • Algorithme C5 [Quinlan 93] :
! version plus récente de lʼalgorithme ID3 [Quinlan 79]
Couleur ! peut prendre en compte des attributs d'arité quelconque.
! fonction entropie, mesurant le degré de mélange (et le gain), a tendance à
vert rouge privilégier les attributs possédant un grand nombre de valeurs : pour éviter ce
jaune biais, une fonction gain d'information est également disponible.
! élagage effectué avec l'ensemble d'apprentissage par une évaluation
Contour carré Point ? pessimiste de l'erreur.
• Algorithme CART [Breiman et al., 84] :
fin plein oui non ! intégré à de nombreux environnements de fouille de données sous de
nombreuses variantes
! fonction mesurant le degré de mélange (et le gain) = fonction de Gini (les
triangle carré triangle carré versions diffusées proposent d'autres choix).
! élagage par parcours ascendant de l'arbre : un sous arbre peut être élagué en
comparant l'erreur réelle estimée de l'arbre courant avec l'arbre élagué.
! l'estimation de l'erreur réelle mesurée sur un ensemble test ou par validation
croisée.

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 59 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 60
Conclusion sur les arbres de décision (1) Conclusion sur les arbres de décision (2)
• lisibilité du résultat : • classification efficace : l'attribution d'une classe à un exemple à l'aide d'un arbre
! un arbre de décision est facile à interpréter et constitue la représentation de décision est un processus très efficace (parcours d'un chemin dans un arbre).
graphique d'un ensemble de règles. • outil disponible : les algorithmes de génération d'arbres de décision sont
! Si la taille de l'arbre est importante, il est difficile d'appréhender l'arbre dans sa disponibles dans tous les environnements de fouille de données.
globalité, mais des outils permettent une navigation aisée dans l'arbre • extensions et modifications :
! permet dʼexpliquer comment est classé un exemple par l'arbre, ce qui peut être ! la méthode peut être adaptée pour résoudre des tâches d'estimation et de
fait en montrant le chemin de la racine à la feuille pour l'exemple courant. prédiction.
• tout type de données : ! Des améliorations des performances des algorithmes de base sont possibles
! l'algorithme peut prendre en compte tous les types d'attributs et les valeurs grâce aux techniques de bagging et de boosting : on génère un ensemble
manquantes d'arbres qui votent pour attribuer la classe.
! Il est robuste au bruit. • sensible au nombre de classes : les performances tendent à se dégrader
lorsque le nombre de classes devient trop important.
• sélection des variables :
! l'arbre contient les attributs utiles pour la classification • évolutivité dans le temps : l'algorithme n'est pas incrémental, c'est-à-dire, que si
=> il peut alors être utilisé comme pré-traitement sélectionnant l'ensemble des les données évoluent avec le temps, il est nécessaire de relancer une phase
variables pertinentes pour ensuite appliquer une autre méthode d'apprentissage sur l'échantillon complet (anciens exemples et nouveaux
exemples).

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 61 Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 62

4 – Méthode des Réseaux de

Neurones (perceptron multi-
couches)
! xxx

Introduction aux grandes méthodes de fouille de données - Bernard ESPINASSE - 63