Développements de Méthodes de Classification basées sur l’Analyse de Concepts Formels sous la Plateforme WEKA

 Introduction Les algorithmes de segmentation K-moyennes Découvrir des structures cachées Les règles d’association A priori La recherche d’association entre individu Les algorithmes de classification/estimation et prédiction Plus proche Voisins/Arbre de décisions Détermination d’une variable particulière d’un individu connaissant le comportement d’un échantillon donné.

Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

6

<!-- Slide number: 7 -->


 U.R.P.A.H

 # Analyse de Concepts Formels

 Introduction Une approche théorique de regroupement conceptuel des données Une discipline bien établie. trouve un usage fondamental en fouille de données, (Règles d’Association, Classification supervisé) Treillis de Galois : Associer les objets avec ses caractéristiques Exemple de méthodes : IPR (Induction de Règles de Production) BCF (Boosting de Concepts Formels) Technique d’apprentissage supervisé But : Classification Diverses méthodes: Treillis complet de concepts Semi treillis de concepts Couverture

Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

7

Notes: une approche théorique de regroupement conceptuel des données permettant d'identifier des concepts et dégager des liens.

2) Actuellement ;L'AFC une discipline bien établie, trouve un usage fondamental en fouille de données, notamment pour construire les règles d'association ou aussi en classification supervisé. 3) s'intéresse à la construction d’un treillis qui définit une relation binaire entre deux ensembles, objets et propriétés, Donc chaque concept associe l’objet à ses caractéristiques. 4) Le treillis de concepts est une structure mathématique permettant de représenter des connaissances. IPR(…) et BCF (…) donnent l’exemple des méthodes basées sur l’ACF. Ces méthodes seront le sujet de notre projet sur lesquelles on a travaillé.

<!-- Slide number: 8 -->


 U.R.P.A.H

 # Analyse de Concepts Formels: Apprentissage et Classification


Apprentissage

Apprentissage Supervisé Apprentissage Non supervisé Introduction Modèle Apprentissage Identification

Cadre et Contexte Données

Données Problématique

Entrées Modèle Sorties Entrées Modèle

Etude de l’existant

Sorties Apprentissage Identification Conception Apprentissage Identification Réalisation Conclusion & Perspectives

Classification : Trouver une application de l’ensemble des objets à classer dans l’ensemble des classes. La phase d’apprentissage , La phase de classification.

8

Notes: L’ apprentissage c’est : Appliquer un ensemble de données d'expériences sur un modèle de recherche pour générer l’ensemble de (Connaissances) concepts. Il couvre plusieurs approches telles que l’apprentissage supervisé, ( ) l’apprentissage non supervisé()

Les méthodes d’apprentissage supervisé servent à construire à partir de la base d’apprentissage, des classifieurs ou fonction de classement . Cette fonction permet, à partir de la description d’un objet, de reconnaître un attribut particulier ; qui c’est la classe.

L’ apprentissage non supervisé dispose au départ d’une masse de données indifférenciées, et on désire savoir si elles possèdent une structure de groupe. C’est ce qu’on appelle le clustering .

<!-- Slide number: 9 -->


 U.R.P.A.H

 Besoins


Intégrer les méthodes sous la plateforme choisie

Bien implémenter les méthodes IPR , BCF et AdaBoostM2 Introduction

Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Choisir la plateforme de fouille de données la plus adéquate Conclusion & Perspectives

9

Notes:

<!-- Slide number: 10 -->


 U.R.P.A.H

 Comparison Fonctionnelle

 | | WEKA | TANAGRA | ORANGE | | --- | --- | --- | --- | | Langage | JAVA | DELPHI | C++ | | Interface | Très complète Quatre Environnements | Un seul environnement d’exécution | Un seul environnement d’exécution | | Données Traitées | Fichier texte avec tabulations spécifiques CVS ARFF Accès à des SGBD | Fichier texte avec tabulation Fichier ARFF Fichier EXCEL | Fichier texte avec tabulation | | Bibliothèque des méthodes | Phénoménal pour le supervisé Traitement des données manquantes | le supervisé+Non supervisé | le supervisé+Non supervisé | | Evaluation et comparaison pour les approches supervisé | Complet pour les comparaisons Validation croisée || le même fichier d’apprentissage | Apprentissage et test sur le même fichier | Apprentissage et test sur le même fichier | | Expérimentation | Outil privilégié Environnement spécialisé(Knowledge Flow) | Pas de spécifique | Pas de spécifique | | Performance | Limitation : Temps de calcul, gestion mémoire (grosse BDs) | | | | Intégration des méthodes basée sur l’ACF | OUI | NON | NON | Introduction Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

10

Notes: L’étude de l’existant s’est basée en fait sur une comparaison fonctionnelle et expérimentale. Pour la comparaison fonctionnelle, le tableau suivant ne donne pas une liste exhaustive des critères de comparaison avec les quels on a travaillé mais on a aimé orienté la présentation vers les point de différence entre les trois outils plutôt qu’on parle du tout (les points de différence et les points communs)

<!-- Slide number: 11 -->


 U.R.P.A.H

 Comparison Expérimentale

 Résultats de l’implémentation de l’algorithme C4.5 lors du traitement d’un fichier comportant 500.000 observations et 22 variables.

Introduction Cadre et Contexte | Logiciel | Temps de traitement (secondes) | | Occupation mémoire (Mo) | | | | | --- | --- | --- | --- | --- | --- | --- | | | Importation | Induction arbre | Avant lancement | Après importation | Pic traitement | Après induction | | ORANGE | 90 | 130 | 24.9 | 259.5 | 795.7 | 795.7 | | TANAGRA | 11 | 33 | 7.0 | 53.1 | 121.6 | 73.5 | | WEKA | 10 | 338 | 52.3 | 253.2 | 699.6 | 699.6 | Problématique Etude de l’existant Conception Tanagra réduit considérablement le temps de calcul. Tanagra consomme moins de mémoire. WEKA est très rapide dans les opérations horizontale. TANAGRA est très rapide dans les opérations Verticale. Source des écarts de performance : Les différences entre les structures internes des outils.

Réalisation Conclusion & Perspectives

11

Notes: WEKA organise les données en ligne. Il est très rapide dans les opérations nécessitant de passer très rapidement d’une variable à l’autre pour un même individu. TANAGRA en revanche organise ses données en colonnes. Il est très rapide lorsqu’il s’agit de parcourir très rapidement l’ensemble des observations pour une variable.

<!-- Slide number: 12 -->


 U.R.P.A.H

 Tentatives d’intégration sous WEKA


Solution basée sur un plugin

Exécution de plugin Incompatibilité entre Weka3.5.7 et Citrec

Solution basée sur les DLL

Des DLL (classifieurs ) Fichier texte (Règles, données) Nécessite la JNI Introduction Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

12

Notes:

<!-- Slide number: 13 -->


 U.R.P.A.H

 # Méthodes à developper


 Introduction IPR AdaBoostM2 BCF Cadre et Contexte Problématique

 Etude de l’existant Conception Réalisation Conclusion & Perspectives

13

Notes: IPR est un algorithme basé sur l’extraction de la couverture des concepts . Les concepts sont extrait un par un. Chaque concept est donné par une optimisation locale de la fonction d'entropie. Les règles sont obtenues à partir des concepts. Chaque concept pertinent avec sa classe majoritaire associé, construit une règle.

<!-- Slide number: 14 -->


 U.R.P.A.H

 # IPR : Exemple illustratif Contexte Initial

 Introduction | G/M | A | B | C | D | C1 | C2 | | --- | --- | --- | --- | --- | --- | --- | | e1 | 1 | 1 | 0 | 0 | 1 | 0 | | e2 | 1 | 1 | 0 | 0 | 1 | 0 | | e3 | 0 | 1 | 1 | 0 | 0 | 1 | | e4 | 0 | 1 | 1 | 1 | 0 | 1 | | e5 | 0 | 0 | 1 | 1 | 0 | 1 | 1 1 Cadre et Contexte 1 1 Problématique 1 1 Etude de l’existant 1 1 1 1 1 Conception Extraction de l’ensemble des couples Réalisation | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 2 | 1 | 2 | 2 | 3 | 1 | 3 | 2 | 3 | 3 | 4 | 2 | 4 | 3 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | Calcul du Pseudo Concept Conclusion & Perspectives

Nombre d’exemple associés: 2 Indices des exemples: [0,1] Entropie associé : 0 14

Notes:

<!-- Slide number: 15 -->


 U.R.P.A.H

 # IPR : Exemple illustratif

 Extraction du Concept pertinent Introduction

 Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Génération de l’ensemble des règles Conclusion & Perspectives

A^BC1 B^CC2 C^DC2.

15

Notes: Le pseudo-concept contenant un couple (o, p) est l'union de tous les concepts passant par (o, p). Avec la correspondance de Galois ; on calcule le concept pertinent. La pertinence d'un pseudo-concept est mesurée grâce à la même fonction d'entropie de Shannon. Dans le cas où deux pseudo-concepts ont la même valeur d'entropie , IPR favorise la structure contenant plus d'exemples.

<!-- Slide number: 16 -->


 U.R.P.A.H

 # Méthodes à développer

 Introduction



 Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

16

Notes:

<!-- Slide number: 17 -->


 U.R.P.A.H

 #





 Introduction Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

17

Notes:

<!-- Slide number: 18 -->


 U.R.P.A.H

 # Diagramme de Classes d’IPR


 Introduction



 Cadre et Contexte

 Problématique

 Etude de l’existant Conception Réalisation

 Conclusion & Perspectives

 18

Notes:

<!-- Slide number: 19 -->


 U.R.P.A.H

 # Diagramme de Classes d’AdaBoostM2

 Introduction Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

19

Notes:

<!-- Slide number: 20 -->


 U.R.P.A.H

 # Diagramme de Classes d’BCF

 Introduction Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

20

Notes:

<!-- Slide number: 21 -->


 U.R.P.A.H

 Introduction

 Cadre et Contexte Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

21

Notes:

<!-- Slide number: 22 -->


 U.R.P.A.H

 Tests

Tests de Réception Tests fournies par WEKA

Tests Unitaires Suivi détaillé de l’exécution Comparaison des résultats Avec d’autres expériences d’implémentation

Introduction Cadre et Contexte Problématique Etude de l’existant Conception Réalisation et Tests Conclusion & Perspectives

22

Notes: Dans un premier lieu , on se référant à une suivie détaillés d’exécution via la génération d’un fichier de trace pour mettre l’accent sur les différents étapes faites pour générer l’ensemble des règles et faire de la classification, on a arrivé à valider l’ensemble des résultats avec les chercheurs d’URPAH. L’annexe D donne le détail des fichiers de trace générés.

Dans un deuxième lieu, en se basant sur les résultats faites par d’autres expériences d’implémentation des méthodes IPR et BFC, on a fait une comparaison au niveau résultats de classification, ensemble de concepts formels générés et ensemble de règles générés. A titre d’exemple, on va donner aperçu sur les résultats des méthodes IPR et BCF suivant notre implémentation propre et la solution 1 commentée dans le chapitre 2 (Etude de l’existant).

<!-- Slide number: 23 -->


 U.R.P.A.H

 Optimisation Introduction Cadre et Contexte Problématique Etude de l’existant Conception Réalisation et Tests Conclusion & Perspectives

23

Notes:

<!-- Slide number: 24 -->


 U.R.P.A.H

 # Conclusion

 Introduction Cadre et Contexte

Découvrir le domaine de la fouille de données et le processus extraction de connaissances, Découvrir les plateformes de fouille de données . Avoir l’occasion de faire de la ri-ingeniering. Prise en main de l’outil WEKA.

Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

24

<!-- Slide number: 25 -->


 U.R.P.A.H

 # Perspectives

 Introduction Cadre et Contexte

Faire optimiser les méthodes développées . L’amélioration de la qualité visuelle des fichiers de trace. Chercher à améliorer encore la capacité des classifieurs . Affiner la notion de degré de pertinence dans le calcul des concepts formels. Publier la famille développée sous le site WEKA. Problématique Etude de l’existant Conception Réalisation Conclusion & Perspectives

25

<!-- Slide number: 26 -->


 U.R.P.A.H

 Merci pour votre attention KHALFI Besma Projet Fin d’EtudeS 2008/2009

 26