Evaluation & Catégorisation

Evaluation & Catégorisation Gilles Bisson Equipe SICLAD Laboratoire LEIBNIZ, CNRS-INPG-UJF Gilles.Bisson@imag.frLa catégorisation Opération ayant pour objectifs d’organiser un ensemble d’observations en groupes homogènes et contrastés Classification (ou catégorisation) Végétaux Etres Vivants Précisions terminologiques Le mot “Classification” est souvent utilisé pour désigner • L’élaboration et la caractérisation de classes (classification/catégorisation) • L’affectation d’un individu à une classe (classement/identification) • La structure issue de la classification (hiérarchie/taxinomie) Le mot “catégorisation” est lui-même parfois ambigu (ex. “Text categorization”)Des objectifs multiples ... On peut classer de bien des façons ... Exemple de “classification” des animaux en Chine Impériale (Borges 66) Appartenant à l’empereur, Embaumés, Imaginaires, Décrits dans cette classification, Domestiqués, Ressemblant à des mouches vus de loin, Dessinés à l’aide de poils de chameaux, ... L’intérêt s’évalue à niveau pragmatique et sémantique : “Le problème n’est pas d’obtenir un résultat vrai ou faux, ni probable ou improbable, mais d’obtenir un résultat utile ou inutile” (Lance, Williams 67) “Classification artificielle” et “Classification naturelle” (Durkheim 1884) Classification artificielle (ou perceptuelle) : • Organisation des individus selon des critères visibles mais arbitraires • But : faciliter la mémorisation et la manipulation des données Classification naturelle (ou conceptuelle) : • Organisation sur des critères reflétant la nature intime des individus • But : expliquer les relations exactes qui existent entre les individusUtilisation d’une catégorisation Il s’agit de ... Résumer de manière pertinente un ensemble d’informations Mettre en évidence des liens structurels entre les données Utilisation dans une démarche d’analyse exploratoire des données • Mise en évidence de nouveaux concepts • Inférence de valeurs inconnues à partir de la définition des classes Tester la qualité de la représentation des connaissances adoptée • Les critères de description permettent-ils de retrouver les classes connues ? • Observe-t-on des individus aberrants (classes isolées) ? Construction +/- automatique de structures de données hiérarchiques • Taxonomie de termes ou de documentsEvaluations des classes Type d’évaluation et connaissances Evaluation interne Evaluation externe (construction) (validation) Connaissances Evaluation empirique par l’expert Effectué sur une tâche : Approches coopératives de la • Classement de documents, classification • Désambiguation syntaxique, • ... Entropie, F-mesure, RLM, ... Pas de connaissances Mesure de ressemblance Critères “objectifs” • distance euclidienne, cosinus, ... • Compacité des classes, • Partition Utility,Critères probabilistes • Prédiction de valeurs inconnues,• Partition Utility, .. • Coûts de classement, • ...Validation des classes par l’utilisateur Exemples de validation apprises à l’aide d’interface : Caractérisation visuelle des classes Navigation dans “l’espace” des classesValidation coopérative des classes Pourquoi un expert ? Données non représentatives Bruitées Analyses incorrectes Rôle de la coopération Acquisition des étiquettes Validation des classes Révision des classesDifférentes approches de la classification Stratégie utilisées et résultats produits Incrémentale Non incrémentale {C} + Instance -> {C’} {Instances} -> C Classes “plates” Les méthodes d’échange K-means, (ou nuées dynamique) Cartes de Kohonen AutoClass (Cheeseman et al.) BIRCH (Zhang et al. 96), ... Descendantes COBWEB (Fisher) K-means “divisif” Hiérarchiques CLASSIT (Gennari et al.) CLUSTER/2 (Michalski et al.) ADECLU (Decaestecker) CLUSTER/S (Stepp et al.) Et de nombreux autres depuis ... HIERACH ... Ascendantes WITT (Hanson, Bauer) CAH Hiérarchiques KBG basé sur la CAH (Bisson) Pyramid (Diday, Brito)Classification numérique “Je me propose de regrouper les objets en familles en fonction de leurs ressemblances puis de fusionner, de proche en proche, les familles voisines ” (Andanson 1757) 2 Grandes familles d’approches (Anderberg 73 ; Everitt 80 ; Diday et al. 82 ...) Approche par partitionnement : K-means (Forgy 65), ... , BIRCH (Zhang et al. 96), WaveCluster (Sheikholeslami et al. 2000) Partition Recouvrement (clumping) Approches hiérarchique : Agglomératives (SAHN), Divisives (bisecting K-means (Steinbach et al. 99)) Hiérarchies strictes Pyramides (Diday 89; Brito 91) Graphes acycliques- Le critère d’inertie Inertie d’un nuage d’individus Soit un ensemble G d’individus de centre de gravité g Notion de variance n 1 n 2 12 2I = Dist(x ,g) ( Dist ( x , y ) étant une distance quadratique)G i s = (x x ) x in ni Ł ł i I = I + IThéorème de König-Huygens : tot intra inter Gn c 2 2 2 Dist(x , g) = Dist(x ,g ) + G Dist(g , g)i i c c c i c i c G1 g1 G3 g3 G2 gg g4 G4g2