Introduction

Les algorithmes de segmentation

K-moyennes

D couvrir des structures cach es

Les r gles dassociation

A priori

La recherche dassociation entre individu

Les algorithmes de classification/estimation et pr diction

Plus proche Voisins/Arbre de d cisions

D termination dune variable particuli re

dun individu connaissant le comportement dun chantillon donn .

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation

Conclusion

& Perspectives

6

<!-- Slide number: 7 -->

! (Image18.jpg)

! (Picture2.jpg)

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 dAssociation, 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 dapprentissage supervis

But : Classification

Diverses m thodes:

Treillis complet de concepts

Semi treillis de concepts

Couverture

Cadre et Contexte

Probl matique

Etude de lexistant

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 dun treillis qui d finit une relation binaire entre deux ensembles, objets et propri t s, Donc chaque concept associe lobjet ses caract ristiques.

4) Le treillis de concepts est une structure math matique permettant de repr senter des connaissances.

IPR(&) et BCF (&) donnent lexemple des m thodes bas es sur lACF. Ces m thodes seront le sujet de notre projet sur lesquelles on a travaill .

<!-- Slide number: 8 -->

! (Image19.jpg)

! (Picture2.jpg)

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 lexistant

Sorties

Apprentissage

Identification

Conception

Apprentissage

Identification

R alisation

Conclusion

& Perspectives

Classification : Trouver une application de lensemble des objets classer dans lensemble des classes.

La phase dapprentissage ,

La phase de classification.

8

Notes:

L apprentissage cest : Appliquer un ensemble de donn es d'exp riences sur un mod le de recherche pour g n rer lensemble de (Connaissances) concepts. Il couvre plusieurs approches telles que

lapprentissage supervis , ( )

lapprentissage non supervis ()

Les m thodes dapprentissage supervis servent construire partir de la base dapprentissage, des classifieurs ou fonction de classement . Cette fonction permet, partir de la description dun objet, de reconna tre un attribut particulier ; qui cest la classe.

L apprentissage non supervis dispose au d part dune masse de donn es indiff renci es, et on d sire savoir si elles poss dent une structure de groupe. Cest ce quon appelle le clustering .

<!-- Slide number: 9 -->

! (Image18.jpg)

! (Picture2.jpg)

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 lexistant

Conception

R alisation

Choisir

la plateforme

de fouille de donn es

la plus ad quate

Conclusion

& Perspectives

9

Notes:

<!-- Slide number: 10 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Comparison Fonctionnelle


| | WEKA | TANAGRA | ORANGE |

| --- | --- | --- | --- |

| Langage | JAVA | DELPHI | C++ |

| Interface | Tr s compl te Quatre Environnements | Un seul environnement dex cution | Un seul environnement dex 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 dapprentissage | 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 lACF | OUI | NON | NON |

Introduction

Cadre et Contexte

Probl matique

Etude de

lexistant

Conception

R alisation

Conclusion

& Perspectives

10

Notes:

L tude de lexistant sest 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 quon parle du tout (les points de diff rence et les points communs)

<!-- Slide number: 11 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Comparison Exp rimentale


R sultats de limpl mentation de lalgorithme C4.5 lors du traitement

dun 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

lexistant

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 dune variable lautre pour un m me individu.

TANAGRA en revanche organise ses donn es en colonnes. Il est tr s rapide lorsquil sagit de parcourir tr s rapidement lensemble des observations pour une variable.

<!-- Slide number: 12 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Tentatives dint 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

lexistant

Conception

R alisation

Conclusion

& Perspectives

12

Notes:

<!-- Slide number: 13 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


M thodes developper

! (Image36.jpg)


Introduction

IPR

AdaBoostM2

BCF

Cadre et Contexte

Probl matique


Etude de

lexistant

Conception

R alisation

Conclusion

& Perspectives

13

Notes:

IPR est un algorithme bas sur lextraction 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 -->

! (Image18.jpg)

! (Picture2.jpg)

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

lexistant

1

1

1

1

1

Conception

Extraction de lensemble 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 dexemple associ s: 2

Indices des exemples: [0,1]

Entropie associ : 0

14

Notes:

<!-- Slide number: 15 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


IPR : Exemple illustratif


Extraction du Concept pertinent

Introduction


Cadre et Contexte

Probl matique

Etude de

lexistant

Conception

R alisation

G n ration de lensemble 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 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


M thodes d velopper


Introduction

! (Image24.jpg)

! (Image23.jpg)

! (Image21.jpg)

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation

Conclusion

& Perspectives

16

Notes:

<!-- Slide number: 17 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


#

! (Image22.jpg)


! (Image23.jpg)

! (Image24.jpg)

! (Image25.jpg)

Introduction

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation

Conclusion

& Perspectives

17

Notes:

<!-- Slide number: 18 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Diagramme de Classes dIPR

! (Image45.jpg)


Introduction




Cadre et Contexte


Probl matique


Etude de lexistant

Conception

R alisation


Conclusion

& Perspectives


18

Notes:

<!-- Slide number: 19 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Diagramme de Classes dAdaBoostM2

! (Image23.jpg)

Introduction

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation

Conclusion

& Perspectives

19

Notes:

<!-- Slide number: 20 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Diagramme de Classes dBCF

! (Image21.jpg)

Introduction

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation

Conclusion

& Perspectives

20

Notes:

<!-- Slide number: 21 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Introduction

! (Image15.jpg)

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation

Conclusion

& Perspectives

21

Notes:

<!-- Slide number: 22 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Tests

Tests de R ception

Tests fournies

par WEKA

Tests Unitaires

Suivi d taill

de lex cution

Comparaison des r sultats

Avec dautres exp riences

dimpl mentation

Introduction

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation et Tests

Conclusion

& Perspectives

22

Notes:

Dans un premier lieu , on se r f rant une suivie d taill s dex cution via la g n ration dun fichier de trace pour mettre laccent sur les diff rents tapes faites pour g n rer lensemble des r gles et faire de la classification, on a arriv valider lensemble des r sultats avec les chercheurs dURPAH. Lannexe 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 dautres exp riences dimpl 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 dexemple, 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 lexistant).

<!-- Slide number: 23 -->

! (Image18.jpg)

! (Picture2.jpg)

U.R.P.A.H


Optimisation

Introduction

Cadre et Contexte

Probl matique

Etude de lexistant

Conception

R alisation et Tests

Conclusion

& Perspectives

23

Notes:

<!-- Slide number: 24 -->

! (Image19.jpg)

! (Picture2.jpg)

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 loccasion de faire de la ri-ingeniering.

Prise en main de loutil WEKA.

Probl matique

Etude de lexistant

Conception

R alisation

Conclusion

& Perspectives

24

<!-- Slide number: 25 -->

! (Image19.jpg)

! (Picture2.jpg)

U.R.P.A.H


Perspectives


Introduction

Cadre et Contexte

Faire optimiser les m thodes d velopp es .

Lam 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 lexistant

Conception

R alisation

Conclusion

& Perspectives

25

<!-- Slide number: 26 -->

! (Image19.jpg)

! (Picture2.jpg)

U.R.P.A.H


Merci pour votre attention

KHALFI Besma

Projet Fin dEtudeS

2008/2009


26