60
Fouille de données Approches supervisées 1

Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

  • Upload
    lamkien

  • View
    230

  • Download
    1

Embed Size (px)

Citation preview

Page 1: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

Fouille de donnéesApproches supervisées

1

Page 2: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 3: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

Approches supervisées

3

Page 4: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 5: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 6: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 7: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 8: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 9: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

=

Page 10: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

= =

Page 11: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 12: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

Evaluation des méthodes- Efficacité de la classification

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

12

Page 13: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 14: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

- 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

Page 15: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

Précision et rappel

15

+ -

+ VP FN

- FP VN

Classe prédite

Cla

sse

réel

le

Precision

Rappel

F-mesure

Page 16: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 17: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

- 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é

Page 18: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 19: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 20: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 21: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

- 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

Page 22: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

22

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

Page 23: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 24: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 25: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 26: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 27: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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).

Page 28: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

Classification naive bayésienne

28

Probabilité a priori

Inutile à des fins de classification

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

Page 29: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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 :

Page 30: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

Classification naive bayésienne

30

Classe prédite

Page 31: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 32: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 33: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 34: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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).

Page 35: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 36: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 37: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 38: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 39: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 40: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

CNB sur les textes Probabilités a priori et classification

40

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

Classification

Page 41: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 42: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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.

Page 43: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 44: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

44

SVM Formulation mathématique du problème

Z

Z

Minimiser ce terme maximise la séparabilité

Formulation

Page 45: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

45

SVM Difficultés

Séparateur rarement linéaire

Séparation rarement parfaite

Séparateur

Séparateur

Page 46: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 47: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

47

SVM Cas linéairement non séparable

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

Page 48: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 49: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 50: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 51: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

- 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

Page 52: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

- 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

Page 53: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 54: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 55: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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.

Page 56: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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)

Page 57: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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.

Page 58: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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

Page 59: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

59

Boosting AdaBoost

Page 60: Fouille de données - Institut de Recherche en ...Yoann.Pitarch/Docs/SID/Fouille/slides_dm_sid... · Arbres de décision Algorithme C4.5 [Quinlan J.,1993] 22 Quilan J. C4.5: ... Arbres

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