Projet Acquisition

de connaissanc

es

Réalisé parAnne-Laure BERRÉE, Andra BLAJ,

Stéphanie CHARLET, Diana DRAGUSIN,Daphné DUSSAUD, Emeline ESCOLIVET,

Nolwenn POIRIER & Fanny TOLLEC

Encadré par Peggy CELLIER

INSA de RennesDépartement INFO4ième année – G2.1

Plan

I. Contexte et objectifsa)Quelques rappelsb)Objectifs

II.Choix effectuésa)Langageb)Algorithmec)Modélisation

III.Description de l’outila)Import et récupération des donnéesb)Implémentation de l’algorithmec)Génération des itemsets fréquents maximaux ou fermés d)Exécution et affichage des résultats

IV.Comparaison avec Weka2

I.Contexte et objectifs

Weka

Notre outil

Règles d’associations SI condition(s) ALORS fait(s)

Quelques rappels

Objectif général Extraire des règles d’associations à partir de données de la forme

Attribut 1 Attribut 2

Transaction 1 0/1 0/1

Transaction 2 0/1 0/1

3

I.Contexte et objectifs

Objectif n°2 Implémenter un algorithme from scratch effectuant un travail semblable à Apriori

Objectifs

Objectif n°3Implémenter différents calculs d’indice statistique

Objectif n°4 Implémenter différents types d’itemsets

Objectif n°5 Comparer les performances de l’outil avec Weka

Objectif n°1 Transformer deux types de jeux de données en la matrice Transaction/Items

4

II. Choix effectuésLangage

Pourquoi Java ?

Langage orienté objet permettant une modélisation simple et rapide

Présence de structures de données facilement manipulables

Import des fichiers relativement aisé

Facilité de mise en place d’une interface graphique

Multiplateforme

5

II. Choix effectuésAlgorithme

6

Algorithme APriori

Algorithme FP-Growth

Exploration des données dans le domaine de l’apprentissage des règles d’association

Reconnaissance des propriétés qui reviennent fréquemment dans un ensemble des données

Très proche d’Apriori

Recherche basée sur la génération d’itemsets et leur fréquence

Utilisation d’une structure de données : Frequent-Pattern tree permettant de trouver des itemsets fréquents dans une grande base de données

II. Choix effectuésAlgorithme

7

Comparaison des algorithmes Apriori

Multiples parcours de la base de données Génération d’un nombre considérable d'itemsets Calcul de leur support à chaque fois

Très coûteux de gérer cette quantité d'itemsets

FP-Growth Réduction du nombre de parcours de la base de données Diminution du nombre de génération d'itemsets Facilité du calcul du support

Plus adapté aux grandes bases de données Mise en œuvre assez difficile

- premisse : Integer []- but : int -valeurCritere : double

-Transactions : Vector<Vector<Integer>> - unItems : Vector<Integer>- itemsFreq : Vector<ItemSet>

- matrix : boolean[][] - seuilSupportMin : double- seuilCritereMin : double

II. Choix effectuésModélisation

RègleAssociation

Attribut

Indice

Moteur

AlgoApriori

IndiceConfiance

IndiceSupport IndiceLift

8

APrioriMaximaux APriorisClos

ItemSet

-itemset : Vector<Integer> - support : double

algoSelectionne

listeRegles items

indice

III. Description de l’outil

9

Import et mise en forme des données

Attributs :Mots sous forme de liste

Transactions :Articles de journaux

+

=Chirac Jospin

Article 1 0 1

Article 2 1 1

Données non structurées :articles de journaux

Discrétisation d’attributs nominaux

-Homme-Femme

Données structurées :tickets de caisse

Attributs et transactions :Tickets de caisse

Phase de discrétisation des données

Discrétisation d’attributs continus

- Âge < 20 - 20 < Âge < 40 - 40 < Âge < 60

Homme Femme

Ticket 1 0 1

Ticket 2 1 0=

III. Description de l’outil

10

Implémentation de l’algorithme

1. Transformation des données de la matrice booléenne en transactions

2. Génération des un-itemsets fréquents

3. Génération des 2-itemsets fréquents

III. Description de l’outil

11

Implémentation de l’algorithme

4. Génération de k-itemsets fréquents

constructionkItemsSets(entier k, entier supportMin)si (il y a eu des (k-1)-itemsets générés) alors pour chaque itemset i de taille k-1 faire pour chaque itemset j de taille k-1 différent de i faire si (i et j sont différents que par le dernier élément) alors kItem = i+dernier élément de j tri de kItem en ordre croissant des items supportItem = support de kItem si (supportItem>=supportMin) alors ajouter kItem et son support dans la liste des itemsets fréquents finsi finsi fin pour fin pour si (k+1 est inférieur au cardinal de la liste de 1-itemsets fréquents) alors constructionkItemsSets(k+1, support) finsi finsifin

12

Stratégiemodifier l’algorithme Apriori pour supprimer les itemsets fréquents non fermés ou non maximaux lors de leur génération

Au moment où on construit un (k+1)-itemset J à partir de 2 k-itemsets, si J est fréquent alors

pour chaque k-itemset I, si I est inclus dans J et I est de même support que J

alorsI n’est pas clos, donc on le supprime

finsifin pour

finsi

Comparaison des résultats

Génération des itemsets fréquents maximaux ou fermés

certaines règles pertinentes non générées en utilisant les itemsets fréquents maximaux ou fermés

MAIS

Implémentation similaire pour les itemsets fréquents maximaux

moins de redondance

III. Description de l’outil

III. Description de l’outil

13

Exécution et affichage des résultats

Démonstration de l’outil

acquico.jar

14

IV. Comparaison avec Weka

Weka

Calcul avec indice statistique de confiance, et Itemsets fréquents sur le petit article : outil moins exhaustif, plus rapide et moins pertinent

Tests de performance

Règles crées1. france=no politique=no président=no monde=no foi=no ==> national=no conf:(0.92)2. france=no politique=no président=no foi=no ==> national=no conf:(0.92)3. france=no américain=yes ==> national=no conf:(0.92)4. france=no politique=no président=no monde=no ==> national=no conf:(0.92)

Notre outil7 itemsets 5 itemsets

Règles créesEau, loi ->art ( CONF 0.9255 )Loi ->art ( CONF 0.8571 )Vie ->art ( CONF 0.8390 )Eau ->art ( CONF 0.8303 )Loi , art ->eau ( CONF 0.8285 )Vie ->eau ( CONF 0.8218)Loi ->eau ( CONF 0.7673)

Bilan

15

Difficultés rencontrées

Atouts de l’outil

- Implémentation de FP-Growth- Choix de la modélisation

- Simplicité d’utilisation- Rapidité de la générations des règles

Améliorations possibles - Ajouter l’algorithme FP-Growth- Donner plus de choix de fichiers de données