Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

PJE : Analyse de comportements avec Twitter Classiﬁcation supervisée Arnaud Lie

PJE : Analyse de comportements avec Twitter Classiﬁcation supervisée Arnaud Liefooghe arnaud.liefooghe@univ-lille1.fr Master 1 Informatique – PJE2 – 2012-2013 B. Derbel – L. Jourdan – A. Liefooghe Contenu • Classiﬁcation supervisée • Classiﬁcation bayésienne • Exemple : Classiﬁcation de texte Sources et références • Apprentissage artiﬁciel : Concepts et algorithmes, A. Cornuéjols et L. Miclet • Fouille de données, F. Decomité • Fouille de données, P. Preux • Apprentissage à partir d'exemples, F. Denis et R. Gilleron Classiﬁcation supervisée Classiﬁcation supervisée vs. non-supervisée • Clustering • Le but est de regrouper des objets similaires (pas d'attribut particulier) • Fouille supervisée • Il existe un attribut particulier : la classe • Le but est de «deviner» la classe d'un exemple en ne connaissant que la valeur de ses autres attributs Classiﬁcation supervisée vs. non-supervisée • Clustering • On conserve toutes les données • Fouille supervisée • On modélise : les données servent à construire le modèle et sont (généralement) oubliées ensuite 2 types de classiﬁeurs • Classiﬁeurs qui utilisent directement les exemples pour prédire la classe d’une donnée • Classiﬁeurs pour lesquels on a d’abord construit un modèle et qui, ensuite, utilisent ce modèle pour effectuer leur classiﬁcation/prédiction Problèmes • Méthode d’induction du classiﬁeur ? • Comment utiliser le classiﬁeur obtenu ? • Comment évaluer la qualité du classiﬁeur obtenu : taux d’erreur (ou de succès) ? • Comment traiter les attributs manquants dans le jeu d’apprentissage ? dans une donnée à classer ? • Comment estimer la tolérance au bruit ? Le bruit concerne ici la valeur des attributs de l’exemple avec lequel on construit le classiﬁeur Vocabulaire • Classiﬁcation : prévoir une classe discrète • Prédiction : prévoir une valeur continue (degré de conﬁance) Principe • Une instance = une suite de valeurs d’attributs et une classe (a1, a2, ..., an, c) • À l’aide d’un ensemble d’exemples, on veut construire un modèle des données (classiﬁeur, prédicteur, ...) • On demande à ce classiﬁeur de trouver la classe de nouveaux exemples Principe • Modèle : découvrir la structure des données • Quels sont les attributs importants pour deviner une classe ? Mode opératoire • Etape 1 : Construction du modèle à partir de l’ensemble d’apprentissage (training set) • Etape 2 : Evaluation de la qualité/précision du classiﬁeur • Etape 3 : Utilisation du modèle pour la classiﬁcation de nouvelles instances Schéma Exemples Nouvel exemple Classiﬁeur Algo Classe 1 2 3 3 1 - Construction du modèle • Chaque instance est supposée appartenir à une classe prédéﬁnie • La classe d’une instance est déterminée par l’attribut «classe» • L’ensemble des instances d’apprentissage est utilisé dans la construction du modèle • Le modèle est représenté par des règles de classiﬁcation, arbres de décision, formules mathématiques, ... 2 - Évaluation du modèle • Estimer le taux d’erreur • La classe connue d’une instance test est comparée avec le résultat du modèle • Taux d’erreur = pourcentage de tests incorrectement classés par le modèle 3 - Utilisation du modèle • Classiﬁcation de nouvelles instances (inconnues) Domaines d’application • Délivrance de crédit • Diagnostic médical • Prédiction du cours d’une action • Optimisation d’un envoi de courrier • ... La classiﬁcation dans le processus du data-mining • Collecte, préparation des données • Données d’apprentissage • Évaluation, validation Apprentissage • On manipule : • Des données • Des hypothèses • On veut trouver la meilleure hypothèse en fonction des données disponibles Quelques méthodes de classiﬁcation • Arbres de décision : minimiser l’erreur de classiﬁcation • Classiﬁcation bayésienne (classiﬁeur naïf, réseaux bayésiens) : hypothèse la plus probable • Réseaux de neurones : minimiser l’erreur quadratique • ... Qu’est-ce qu’un bon classiﬁeur ? • Intuition : classiﬁeurs binaires discrets • 4 cas • Vrai positif : exp. positif classé positif • Faux négatif : exp. positif classé négatif • Vrai négatif : exp. négatif classé négatif • Faux positif : exp. positif classé négatif Matrice de confusion vrai classe → ↓ classé positif négatif positif VP FP négatif FN VN total P N Taux • Proportion de positifs bien classés • tp-rate = VP / P • Proportion de négatifs mal classés • fp-rate = FP / N Figure tp-rate fp-rate 0 0 1 1 C A B D E F • A = tous négatifs • B = tous positifs • C = k% positifs • D = conservateur • E < aléatoire • F = class. idéal Classiﬁcation bayésienne Principe • On doit inférer (deviner) des quantités gouvernées (décrites) par des probabilités : on veut se servir de ces probabilités pour guider l’inférence • Cadre plus général que la classiﬁcation Classiﬁcation bayésienne • À chaque hypothèse : • On associe une probabilité (probabilité d’être la solution) • L’observation d’une (ou de plusieurs) instances peut modiﬁer cette probabilité • On peut parler de l’hypothèse la plus probable, au vu des instances Buts (possibles) • Formaliser les méthodes et les intuitions • Préciser la notion de ‘plus probable’ • Nouveaux algorithmes d’apprentissage • Analyse d’autres algorithmes ne manipulant pas explicitement des probabilités Classiﬁcation bayésienne • Approche probabiliste • Basée sur les probabilités conditionnelles (et la règle de Bayes) • Connaissances a priori • Prévision du futur à partir du passé • Suppose l'indépendance des attributs Classiﬁcation bayésienne • Différente de l’approche basée sur les fréquences ! • Fréquences : on estime la probabilité d'occurrence d’un événement • Bayésienne : on estime la probabilité d'occurrence d’un événement sachant qu’une hypothèse préliminaire est vériﬁée (connaissance) Probabilités • La probabilité d’un événement A est notée P(A) • Elle est comprise entre 0 et 1 • La probabilité d’un événement certain vaut 1 • La probabilité d’un événement impossible vaut 0 • Si A et B sont indépendants • P(A∪B) = P(A) + P(B) • P(non A) = 1 - P(A) Probabilités conditionnelles • P(A|B) = Probabilité que l'événement A survienne si l'événement B survient • P(A|B) = P(A∩B) / P(B) • P(A∩B) = P(A|B)·P(B) = P(B|A)·P(A) Probabilités conditionnelles Exemple • 99% des sujets atteint d’une maladie M sont positifs à un test de dépistage • La maladie M touche 10% de la population • Quelle est la fraction de la population des sujets malades positifs au test de dépistage ? • P(M)=0.1 , P(T|M)=0.99 • P(T∩M) = P(T|M)·P(M) = 0.99·0.1 = 9.9% Indépendance • Deux événements sont indépendants si la connaissance de l’un ne modiﬁe pas la probabilité de l’autre • Si A et B sont indépendants, alors : • P(A|B) = P(A) • Deux événements A et B sont indépendants si • P(A⋀B) = P(A)·P(B) , P(A), P(B) > 0 Théorème de Bayes • P(A|B) = P(A∩B) / P(B) • P(A∩B) = P(B|A)·P(A) • Donc, P(A|B) = P(B|A)·P(A) / P(B) Problématique • On veut calculer, pour chaque classe, la probabilité pour que ce soit la solution, sachant qu’on a observé (a1,...,an) • Garder la meilleure • Rejeter les hypothèses de probabilité nulle • Tout garder (traitements ultérieurs) Problématique • Quelle est l’hypothèse la plus probable, au vu de l’ensemble d’apprentissage ? • Pour une instance donnée, au vu de l’ensemble d’apprentissage, quelle sera la classiﬁcation la plus probable de cet exemple ? Classiﬁeur bayésien optimal • Classiﬁcation optimale si les probabilités de chaque hypothèse sont connues • Pas souvent le cas : • Trop d’hypothèses, trop de calculs, trop d’estimations • Simpliﬁcation ? Application à la classiﬁcation • P(ck|a1,...,an) = P(a1,...,an|ck)·P(ck) / P(a1,...,an) • P(a1,...,an|ck), P(a1,...,an) et P(ck) peuvent être estimées sur les instances de l'ensemble d’apprentissage Application à la classiﬁcation • P(ck|a1,...,an) = P(a1,...,an|ck)·P(ck) / P(a1,...,an) • P(ck) ≈ proportion d’instances de la classe ck • P(a1,...,an) ≈ proportion d’instances d’attributs (a1,...,an) • P(a1,...,an|ck) ≈ nb fois où on rencontre (a1,...,an) dans les instances de la classe ck (vraissemblance) Quelques observations • P(ck|a1,...,an) = P(a1,...,an|ck)·P(ck) / P(a1,...,an) • P(ck|a1,...,an) croît quand P(ck) croît : plus ck est probable, plus il y a de chances qu’elle soit la classe • P(ck|a1,...,an) croît quand P(a1,...,an|ck) croît : si (a1,...,an) arrive souvent quand ck est la classe, alors il y a des chances que ck soit la classe • P(ck|a1,...,an) décroît quand P(a1,...,an) croît : si (a1,...,an) est courant, il nous apprend peu sur ck Classiﬁcation bayésienne • C = (c1,...,ck) ensemble de classes (chacune munie d’une probabilité) • (a1,...,an) un ensemble d’attributs • Retourner la classe ayant la probabilité la plus forte après l’observation de (a1,...,an) • Hypothèse Maximale A Posteriori : hMAP • hMAP = argmaxck∈C P(a1,...,an|ck)·P(ck)/P(a1,...,an) Hypothèses MAP, ML • hMAP = argmaxck∈C P(a1,...,an|ck)·P(ck) / P(a1,...,an) • P(a1,...,an) est constant • hMAP = argmaxck∈C P(a1,...,an|ck)·P(ck) • Maximum de vraisemblance • hML = argmaxck∈C P(a1,...,an|ck) Classiﬁeur bayésien naïf • Appliquer le théorème de Bayes pour déﬁnir un algorithme de classiﬁcation simple et efﬁcace (en pratique) • Caractéristiques : • Classiﬁcation supervisée • Classes discrètes Classiﬁeur bayésien naïf • On suppose que tous les attributs sont indépendants (eg. absence d’information) • P(a1,...,an|ck) = ∏ P(ai|ck) • hMAP = argmaxck∈C ∏ P(ai|ck)·P(ck) • ∏ P(ai|ck) estimé à partir de l’ensemble d’apprentissage Classiﬁeur bayésien naïf • Attribut discret • P(ai|c) = nic uploads/Ingenierie_Lourd/ pje-cours.pdf