Fouille de données - Institut de Recherche en...

Fouille de donnéesApproches supervisées

1

Plan du cours

1. Le pré-traitement des données

2. Méthodes non supervisées

3. Méthodes supervisées

4. Méthodes semi-supervisées

5. Fouille de données Web

2

Approches supervisées

3

Exemple d’applicationSociété de créditPour chaque client qui veut emprunter :

- Age - Statut marital - Salaire annuel - Dettes contractées - …

Faut-il accorder le crédit ?

4

Apprentissage supervisé

- On apprend des expériences passées

- Un ordinateur n’a pas d’expérience

- Il apprend à partir des données

- Objectif: apprendre une fonction objectif pour prédire la

valeur d’une classe

- Plusieurs noms possibles: classification, apprentissage

supervisé, machine learning

5

Un processus en deux étapes1. Apprentissage du modèle sur un jeu de données d’apprentissage

2. Test du modèle sur un jeu de données test

X Y Z ClasseA C E 1B D E 2A C E 1A D F 2

6

X Y Z ClasseB D E ?A C F ?A D E ?B D F ?

X Y Z Classeprédite

B D E 2A C F 1A D E 1B D F 2

Données d’apprentissage Modèle

Données de test Modèle Prédiction

Hypothèse fondamentaleHypothèse

Distribution des classes identique entre le jeu d’apprentissage et le jeu de test

Remarques

- Ce n’est jamais vraiment le cas en pratique

- Si la distribution est vraiment différente alors la classification sera de mauvaise qualité

- Le jeu d’apprentissage doit être suffisamment représentatif du jeu de test

7

Jeu de données Choix des jeux de données de test et d’apprentissage

Principes

Soit le jeu de données. On note le jeu d’apprentissage et le jeu de test. On a :

- -

Objectif

- Etre représentatif de l’ensemble du jeu de donnée

- Eviter l’overfitting (sur-apprentissage)

8

Jeu de données Validation simple

PrincipesDécoupe du jeu de données en 2 : apprentissage et test A appliquer lorsque le jeu de données est large Répartition courante :

- 50 % apprentissage - 50% test - 2/3 apprentissage - 1/3 test

Tirage aléatoire ou en fonction de la temporalité de la donnée

9

=

Jeu de données Tirage multiple aléatoire

PrincipesApplicable si le jeu de données est petit Application n fois de la validation simple Obtention de n indicateurs de performance Efficacité moyenne = la moyenne des n indicateurs de performance

10

= =

Jeu de données Validation croisée

11

PrincipesDécoupe du jeu de données en k (5 ou 10 généralement) parties On apprend sur k-1 parties et on teste sur la k ème partie Processus répété k fois (chaque partie sert de jeu de données de test) Calcul de l’efficacité globale identique au tirage multiple aléatoire

Apprentissage Test

Round 1

Round 2

Round 3

Round 4

Evaluation des méthodes- Efficacité de la classification

- Temps de calcul - Passage à l’échelle: - Interprétabilité - Compacité

12

Efficacité n’est qu’une mesure Erreur = 1 - efficacité Pas toujours valide sur jeux de données déséquilibrés

- Fouille de texte - Détection d’intrusion - Détection de fraude

Communément : - Classe d’intérêt : classe positive - Autre classe : classe négative

Mesures

13

- Très utilisé en recherche d’information - Utilisation d’une matrice de contingence

Précision et rappel

14

+ -

+ VP FN

- FP VN

Classe prédite

Cla

sse

réel

le

Précision et rappel

15

+ -

+ VP FN

- FP VN

Classe prédite

Cla

sse

réel

le

Precision

Rappel

F-mesure

Précision et rappel

16

+ -

+ 1 99

- 0 1000

Classe prédite

Cla

sse

réel

le

Precision

Rappel

F-mesure Remarques 1. Précision et rappel ne s’occupent

que de la classe positive 2. Peut facilement être étendu au

cas où nbClasses > 2

- Communément utilisé pour évaluer les performances d’un classifieur bi-classe

- Nécessité d’ordonner les instances selon la vraisemblance d’appartenir à la classe positive

17

Courbe ROC Receiver Operating Characteristic

Ratio Vrai Positif (RVP)

Ratio Faux Positif (RFP)

Sensitivité

1 - spécificité

Courbe ROC Receiver Operating Characteristic

18

Exploitation de la courbe

- Calcul de l’aire sous la courbe (AUC)

- AUC = 1 équivaut à un tirage aléatoire

- AUC = 1 équivaut à un classifieur parfait

Courbe ROC Construction

19

Rang 1 2 3 4 5 6 7 8 9 10Classe + + - - + - - + - -

VP 0 1 2 2FP 0 0 0 1VN 6 6 6 5FN 4 3 2 2

RVP 0 0,25 0,5 0,5RFP 0 0 0 0,17

Courbe ROC Construction

20

Rang 1 2 3 4 5 6 7 8 9 10Classe + + - - + - - + - -

VP 0 1 2 2 2 3 3 3 4 4 4FP 0 0 0 1 2 2 3 4 4 5 6VN 6 6 6 5 4 4 3 2 2 1 0FN 4 3 2 2 2 1 1 1 0 0 0

RVP 0 0,25 0,5 0,5 0,5 0,75 0,75 0,75 1 1 1RFP 0 0 0 0,17 0,33 0,33 0,50 0,67 0,67 0,83 1

- Une des techniques les plus utilisées - Efficacité compétitive - Rapide à construire - Résultat facile à interpréter

Arbres de décision

21

Chaque instance du jeu d’apprentissage est

couverte une et une seule fois

Arbres de décision Algorithme C4.5 [Quinlan J.,1993]

22

Quilan J. C4.5: programs for machine learning. 1993: Morgan Kaufmann Publishers.

Arbres de décision Gestion d’attributs numériques

23

- Ne gère pas nativement les attributs numériques - Nécessité de discrétiser - Deux classes sont souvent suffisantes (valeur qui maximise le gain) - Nécessite de modifier légèrement l’algorithme initial (on garde

l’attribut numérique) - Impact négatif sur la complexité temporelle

Arbres de décision Elagage de l’arbre

24

- Arbre potentiellement très profond - Bruit, complexité des données, caractère aléatoire - L’arbre produit ne généralise pas bien les données (sur-

apprentissage) - Elagage nécessaire (pré ou post traitement) - Si l’erreur estimée d’un noeud est inférieure ou proche de l’erreur

estimée moyenne du sous-arbre alors on élague

Arbres de décision Données manquantes et classes non-équilibrées

25

Situation très courante si pré-traitement mal effectué Plusieurs manières d’aborder le problème

- Remplacement par une valeur joker - Remplacement par la valeur la plus fréquente ou la moyenne

Données manquantes

Une classe apparaît significativement plus qu’une autre (alarmes) Plusieurs manières d’aborder le problème

- Augmenter la proportion de la classe sous-représentée - Echantillonner la classe sur-représentée

Classes non-équilibrées

Arbres de décision Résumé

AVANTAGES

Inconvénients

INCONVÉNIENTS

26

- Très utilisé- Efficacité compétitive

- Rapide à construire

- Attributs numérique ou

catégoriel- Résultats interprétables

- Données manquantes- Classes non-équilibrées

Point de vue probabiliste de l’apprentissage Soit A1,…,Ak des attributs discrets et C la classe à prédire

On cherche la classe c telle que : Pr(C=c | A1=a1,…,Ak=ak) soit maximale

Fonctionne sur données catégorielles

Classification naive bayésienne

27

Articles fondateursDomingos, P., & Pazzani, M. (1997). On the optimality of the simple Bayesian classifier under zero-one loss. Machine learning, 29(2-3), 103-130.

Kohavi, R., Becker, B., & Sommerfield, D. (1997). Improving simple bayes.

Langley, P., Iba, W., & Thompson, K. (1992, July). An analysis of Bayesian classifiers. In AAAI (Vol. 90, pp. 223-228).

Classification naive bayésienne

28

Probabilité a priori

Inutile à des fins de classification

Par le théorème de Bayes on a :

Classification naive bayésienne

29

Hypothèse d’indépendance conditionnelle

et de façon similaire pour les autres attributs

Sous l’hypothèse d’indépendance conditionnelle, on a :

Classification naive bayésienne

30

Classe prédite

31

Classification naive bayésienne Exercice

A = m, B = q, C = ?

A B Cm b fm s fg q fh s fg q fg q tg s th b th q tm b t

32

Classification naive bayésienne Attributs numériques,valeurs absentes et valeurs

manquantes

Situation très courante On peut utiliser une technique de discrétisation vue précédemment

Attributs numériques

Valeurs absentesProblème si une valeur apparaît uniquement dans le jeu de test On utilise un facteur correcteur : où nij le nombre d’instances avec ai et cj, nj le nombre d’instances avec cj, mi le nombre de valeurs d’Ai et (n est la taille du jeu)

Valeurs manquantesElles sont ignorées dans le calcul

Classification naive bayésienne Résumé

AVANTAGES

Inconvénients

INCONVÉNIENTS

33

- Implémentation aisée

- Efficacité compétitive

- Rapide à construire

- Indépendance- Attributs numériques- Valeurs absentes- Valeurs manquantes

Classification naive bayésienne sur les textes

[McCallum A. et Nigam K., 1998]

34

ConstatMéthode précédente assez peu efficace sur des textes

Classification de textesAssigner un document à une classe (e.g., Sports, Politique, Finance, …)

AméliorationsCadre probabiliste pour les textes Idées similaires à l’approche précédente

McCallum, A., & Nigam, K. (1998, July). A comparison of event models for naive bayes text classification. In AAAI-98 workshop on learning for text categorization (Vol. 752, pp. 41-48).

CNB sur les textes Cadre probabiliste pour les textes

35

- Modèle génératif probabiliste - Chaque document est généré par une distribution paramétrique - Estimation des paramètres via le jeu de données d’apprentissage

Suppositions du modèle génératif probabiliste1. Les données (ou les textes) sont générés par un modèle de

mixture 2. Correspondance une à une entre les composants de la mixture et

les classes

CNB sur les textes Cadre probabiliste pour les textes

36

Notations

Génération de di

Probabilité que di soit généré par le modèle de mixture

CNB sur les textes Quelques hypothèses sur les textes

37

Hypothèses

Génération de di

- Chaque mot d’un document est généré indépendamment de son contexte, i.e., des autres mots du document et de la classe

- La probabilité d’un mot est indépendante de sa position dans le texte - La longueur des documents est indépendante de la classe

Modélisation d’un texteLes textes sont représentés comme des sacs de mots (comme en Recherche d’Information)

Par une distribution multinomiale k tirages avec k la taille du document

Le nombre d’apparitions de wt dans di

CNB sur les textes Calcul de la probabilité conditionnelle

38

Application de la fonction de probabilité d’une distribution mulinomiale

Indépendant de la classe

CNB sur les textes Estimation des paramètres

39

Estimation à partir du jeu d’apprentissage

L’estimation de wt sachant cj est simplement le nombre de fois que wt apparaît dans un document de la classe cj

Cas des valeurs absentes

CNB sur les textes Probabilités a priori et classification

40

Probabilités a priori = poids des mixturesProbabilités a priori

Classification

Classification naive bayésienne Résumé

AVANTAGES

Inconvénients

INCONVÉNIENTS

41

- Efficace même si violation des

hypothèses (indépendance des

mots et correspondance une à

une entre classes et

composants de la mixture)

- Rapide à construire

42

SVM Support Vector Machine

Séparateur à Vaste Marge [Vapnik V., 2013]

Classification binaire Attributs réels

Quand ?

PrincipeTrouver un séparateur dont la marge est maximale

Séparateur

Marge

Vapnik, V. (2013). The nature of statistical learning theory. Springer Science & Business Media.

43

SVM Pré-requis mathématiques

Optimisation non-linéaire- Méthode de Lagrange, lagrangien, multiplicateur de Lagrange - Problèmes primal et dual - Problèmes convexes et leurs résolution

Analyse fonctionnelle- Espaces de Hilbert - Espace de Hilbert à noyau reproduisant

44

SVM Formulation mathématique du problème

Z

Z

Minimiser ce terme maximise la séparabilité

Formulation

45

SVM Difficultés

Séparateur rarement linéaire

Séparation rarement parfaite

Séparateur

Séparateur

46

SVM SVM non linéaire

« Dans une tâche de classification supervisée, plus la dimension des données est grande, i.e., plus ils ont d’attributs linéairement indépendants, plus la probabi l i té que les c lasses soient l inéairement séparables est grande » [Théoreme de Cover, 1965]

PrincipePulvérisation des données dans un espace potentiellement infini Problème : produit scalaire en grandes dimensions est coûteux Astuce du noyau : noyau symétrique défini positif pour calculer le produit scalaire des données pulvérisées dans l’espace de représentation d’origine

Noyaux usuelsNoyau polynomial

Noyau gaussien

47

SVM Cas linéairement non séparable

PrincipeIntroduction de nouvelles contraintes Nouveau problème de minimisation avec contraintes

48

SVM Multi-classes

Un contre tousConstruction

Construction de M classifier binaires (classe + pour une classe et - pour toutes les autres)

Test Le classifieur donnant la marche la plus élevée remporte le vote et sa décision sera suivie

Un contre unConstruction

Construction de M(M-1)/2 classifieurs Test

Vote majoritaire

49

SVM Données catégorielles

Solutions possiblesCréation d’une variable prenant n valeurs numériques Création de n variables binaires

RemarquesMeilleures performances des variables binaires Très utilisé pour la classification de documents Fonctionne très bien pour de grandes dimensions

SVM Résumé

AVANTAGES

Inconvénients

INCONVÉNIENTS

50

- Solides fondations théoriques

- Très bonnes performances

- Supporte les grandes

dimensions

- Attributs réels- Classification binaire- Modèle difficilement interprétable

- Pas de construction de modèle (lazy learning vs eager learning) - Nécessite une fonction de distance - Compte la classe majoritaire dans le voisinage

51

K plus proches voisins

1 plus proche voisin2 plus proches voisins

3 plus proches voisins

- La classe majoritaire est élue - Possibilité de pondérer en fonction de la distance

52

K plus proches voisins Classification

1 plus proche voisin2 plus proches voisins

3 plus proches voisins

?

Très sensible au paramètre k

K plus proches voisins Résumé

AVANTAGES

Inconvénients

INCONVÉNIENTS

53

- Simplicité- Efficacité- Gestion des multi-classes

- Classification lente- Non gestion des données manquantes

54

Classification supervisée Approches ensemblistes

QuestionsNe peut on pas construire de nombreux modèles puis les combiner ? Comment les combiner ?

SolutionsGénériques :

- Bagging - Boosting

Spécifique: - Random forest

ConstatClassifieurs isolés peuvent peiner à résoudre un problème de classification Mais ils peuvent chacun être efficaces sur une partie de l’espace de données

55

Approches ensemblistes Bagging (Bootstrap Aggregating)

[Breiman L., 1996]

NotationsUn jeu de données D avec n exemples et un algorithme d’apprentissage M

Apprentissage1. Création de k jeu d’apprentissage, S1 à Sk, par tirage aléatoire avec remise

de n exemples 2. Création de k modèles construites sur S1 … Sk avec le même algorithme M

Test- Système de vote (poids égaux) - Election de la classe majoritaire

Breiman, L. (1996). Bagging predictors. Machine learning, 24(2), 123-140.

Bagging Forces et faiblesses

AVANTAGES

Inconvénients

INCONVÉNIENTS

56

Peut significativement augmenter

les performances des méthodes

instables (arbres de décision)

Peut dégrader les résultats des méthodes stables (KPP et c lass ificat ion bayésienne)

57

Approches ensemblistes Boosting

[Schapire R., 1990]

Idée généraleUn classifieur dit « faible » est exécuté à plusieurs reprises sur le jeu de données repondéré.

MécanismeA chaque itération t :

1. Pondération de chaque exemple selon s’il a été bien classé précédemment (fort poids si mal classé)

2. Apprentissage d’un modèle noté ht

3. Affection d’une force à ce modèle noté Sortie

Combinaison linéaire du vote des différents modèles pondéré par leur force

Schapire, R. E. (1990). The strength of weak learnability. Machine learning, 5(2), 197-227.

58

Boosting Pondération du jeu de données

Les exemples ne sont pas égauxPlus un exemple est dur à classer plus celui-ci devrait être « sur-représenté » dans le jeu de données

Jeu de données pondéréOn note D(i) le poids du ième exemple (xi, yi) Interprétation :

- Le ième exemple compte pour D(i) exemples - Si on doit «  resampler  » le jeu de données, les exemples ayant un fort

poids seront plus présents

59

Boosting AdaBoost

60

Références

- Data Mining - Concepts and Techniques par J. Han et M.Kamber (ed. Morgan Kauffman)

- Web Data Mining - ExploringHyperlink, Contents and Usage Data par B. Liu (ed. Springer)

- Statistiques Exploratoires Multidimensionnelles par L. Lebart et al. (ed. Dunod)

Ces ouvrages pointent vers de nombreuses références d’articles scientifiques décrivant les approches vues en cours ou des variantes de celles-ci