Évolution de schémas par classification

automatique dans les entrepôts de données

3ème journée francophone sur les Entrepôts de Données et l'Analyse en ligne (EDA 2007)

Futuroscope-Poitiers, juin 2007

Ony Rakotoarivelo et Fadila Bentayeb

Laboratoire ERIC - Université Lyon 2

2

Motivation

schéma classique

Hiérarchies statiques Possibilités d’analyse limitée Tendances inexplorées

opérateur d’évolutionbasé sur la fouille

de données

schéma évolutif

Hiérarchies dynamiques Extension des possibilités d’analyse Découverte de tendances

3

Plan

État de l’art

Approche

Mise en oeuvre

Conclusion et perspectives

4

Plan

État de l’art

Approche

Mise en oeuvre

Conclusion et perspectives

5

Les deux courants d’évolution de schéma

Mise à jour de modèles Blaschka et al. DaWak 1999 Hurtado et al. ICDE 1999 Hurtado et al. DOLAP 1999 Pourrabas et al. DOLAP 1999 Favre et al. ICEIS 2007

Entrepôts de données temporels Bliujute et al. Technical report 1998 Vaisman et al. VLDB 2000 Morzy et al. ICEIS 2003 Morzy et al. DOLAP 2004

6

Evolution par mise à jour de modèles

Dimension = graphe acyclique direct

Sommet = niveau d’analyse Arête = lien d’agrégation

Mise à jour Modification de la structure du graphe Conservation des propriétés de départ

Evolution non historisée

All

Niveau3

Niveau2

Niveau1

Niveau n

7

Modèles d’entrepôts temporels Schéma en étoile temporel

Bliujute et al. Technical report 1998 Idée: Labéliser chaque instance d’un niveau d’analyse

par un intervalle de temps

TOLAP: Temporal OLAP Vaisman et al. VLDB 2000 Idée: Labéliser chaque lien d’agrégation par un

intervalle de temps

Versionnement Morzy et al. ICEIS 2003, DOLAP 2004 Idée:

Effectuer les modifications sur une nouvelle version de l’entrepôt

Labéliser chaque version par un intervalle de temps

8

Positionnement de notre approche par rapport à l’existant

Opérateur

Évolution

Modèle

temporel

Blaschka et al. X

Hurtado et al. X

Pourrabas et al. X

Vaisman et al. X

Bliujute et al. X

Morzy et al. X

Favre et al. X

Notre approche X

Produit catégorie famille all

Notre approche

NOTRE SOLUTIONClassification automatique

Classe produit

P1

P2

P3

p4

Classe1

Classe2

Produit Classe produit

?

9

Plan

État de l’art

Approche

Mise en oeuvre

Conclusion et perspectives

10

Idée générale de l’approche

Approche modulaire basée sur deux opérateurs Opérateur de classification Opérateur d’évolution de schéma

connaissances

Évolutionde schéma

classificationautomatique

Quelle méthode de classification utiliser ?

11

Choix d’une méthode de classification

Objectif de la classification Regrouper les individus similaires et séparer les individus

dissemblables

Les principales méthodes CAH: génère une hiérarchie de partitions Cartes de Kohonen: effectue une classification visuelle

affichant la typologie d’une population sur une carte K-means: génère une partition à partir des centres de

classe

Critères de choix Format des classes: partition Complexité algorithmique: faible

k-means

Comment établir un lien d’agrégation avec les k-means ?

12

Établissement du lien d’agrégationAll

Famille

Catég.

produit

Classeproduit

jupe

robe

shortpantalon

Générer la partition classifiant les instances du niveau de départ

Jupe

Robe

Pantalon

Short

Classe 1

Classe 2

« Produit » « Classe produit »

Un sous-ensemble dans la partition=

une modalité du nouveau niveau

Comment choisir les variables de classification ?

Instances du niveau« produit »

13

Choix des variables de classification

VENTESProduitMagasin

MoisQté vendue

Montant

Famille

famille

Catégorie

Categ.

Produit

Produitprix

Option 1: utiliser les attributs du niveau sourceEx: classifier les produits selon leur prix

JupeRobe

PantalonShort

« produit »

Option 2: combiner les attributs du niveau source avec les indicateursEx: classifier les produits par rapport aux ventes

JupeRobe

PantalonShort

« produit »

classe1

classe2

« Classe prix »

Classe’1

Classe’2

« Classe vente »

Classe venteClasseDesc.

Classe prixClasseDesc.

14

Plan

État de l’art

Approche

Mise en oeuvre

Conclusion et perspectives

15

Approche d’implémentation: fouille de données en ligne

Choix technique Intégration des k-means au sein du SGBD

Oracle

Avantages Pas de limitation sur la taille de la base

d’apprentissage (niveau source) Accès direct aux données via SQL Combinaison efficace k-means / OLAP

Étapes de l’implémentation Programmation en PL/SQL des k-means Programmation en PL/SQL de l’opérateur

d’évolution de schéma qui permet de créer les nouveaux niveaux d’analyse

16

Tests

Entrepôt de données de test http://www.emode.com Table des faits: 89 200 enregistrements Table de dimension « Produit »: 213 produits

regroupés en 12 familles de produits

Scénarii de test Scénario 1: regrouper les produits par prix Scénario 2: regrouper les produits sur les

indicateurs (quantité vendue et chiffre d’affaire).

17

Résultats

Individu atypique

18

Plan

État de l’art

Approche

Mise en oeuvre

Conclusion et perspectives

19

Conclusion et perspectives Conclusion

Définition d’un opérateur d’évolution de schéma en utilisant les k-means

Combinaison OLAP et classification automatique

Intégration des k-means dans le SGBD Oracle

Perspectives Exploitation des règles d’association Intégration de connaissances utilisateurs Détection d’individus atypiques Opérateurs de suppression et de modification