ATTESTATION SUR L’HONNEUR
J’atteste sur l’honneur que ce mémoire a été réalisé par moi-même et que les
données et les résultats qui y sont présentés sont exacts et n’ont jamais été publiés
ailleurs. La source des informations citées dans ce mémoire a été bien précisée.

LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai
công bố trong bất kỳ công trình nào khác. Các thông tin trích dẫn trong Luận văn
đã được chỉ rõ nguồn gốc.

Signature de l’étudiant

DƯƠNG MINH ĐỨC


Table des mati`
eres
Remerciements

iii

R´
esum´
e

iv

Abstract

vi

1 Introduction

2

1.1

Contexte g´en´eral et probl´ematique

. . . . . . . . . . . . .

2

1.2

Motivation et objectifs . . . . . . . . . . . . . . . . . . . .

4

1.3

Approche propos´ee . . . . . . . . . . . . . . . . . . . . . .

5

1.4

Contributions . . . . . . . . . . . . . . . . . . . . . . . . .


5

1.5

Organisation du m´emoire . . . . . . . . . . . . . . . . . . .

6

´
2 Etat
de l’art
2.1

2.2

7

Revue de la bibliographie . . . . . . . . . . . . . . . . . . .

7

2.1.1

Chromatic correlation clustering . . . . . . . . . . .

7

2.1.2


Exceptional Model Mining . . . . . . . . . . . . . .

12

2.1.3

Discussions . . . . . . . . . . . . . . . . . . . . . .

15

S´erie temporelle et mesures de distance . . . . . . . . . . .

16

2.2.1

Introduction de s´erie temporelle . . . . . . . . . . .

16

2.2.2

Dynamic Time Warping . . . . . . . . . . . . . . .

17

2.2.3

Symbolic Aggregate approXimation . . . . . . . . .


21

i


3 M´
ethodes et solutions propos´
ees

26

3.1

Graphe d’arˆetes attribu´ees et mod´elisation du probl`eme

.

26

3.2

Formulation du probl`eme . . . . . . . . . . . . . . . . . . .

28

3.2.1

D´efinitions pr´ealables . . . . . . . . . . . . . . . . .

28


3.2.2

´
Evaluation
statistique d’une arˆete . . . . . . . . . .

29

3.2.3

Contexte particulier

. . . . . . . . . . . . . . . . .

29

3.2.4

Formulation la tˆache de fouille des motifs . . . . . .

29

Algorithme FastRabbit . . . . . . . . . . . . . . . . . . . .

31

3.3

4 Exp´

erimentation et r´
esultats

33

4.1

R´esultats quantitatifs . . . . . . . . . . . . . . . . . . . . .

33

4.2

R´esultats qualitatifs et Comparaison avec EMM . . . . . .

35

4.2.1

R´esultats qualitatifs . . . . . . . . . . . . . . . . .

35

4.2.2

Comparaison avec EMM . . . . . . . . . . . . . . .

40

5 Conclusion


42

R´
ef´
erences

44

ii


Remerciements
Tout d’abord, j’adresse mes remerciements au Laboratoire d’InfoRmatique en Image et Syst`emes d’information (LIRIS) d’avoir financ´e ce travail.
Je tiens a` remercier tout particuli`erement mes encadrants Marc Plantevit et C´eline Robardet. Ils m’ont guid´e et support´e dans tous les ´etapes
de ce stage. La dur´ee 6 mois de travail avec eux n’est pas beaucoup mais
il m’a suffit d’avoir confiance a` continuer des ´etudes dans l’avenir.
Je remercie ´egalement Albrecht Zimmermann ainsi que tous les membres
de l’´equipe DM2L pour des discussions et suggestions.
Finalement, je remercie sinc`erement mes parents et mes camarades pour
leurs soutiens pendant cette p´eriode.

iii


R´
esum´
e
Les graphes sont une abstraction math´ematique qui permet de repr´esenter
naturellement de nombreux ph´enom`enes r´eels. La fouille de graphes est un

domaine majeur de la fouille de donn´ees. De nombreux travaux se sont
int´eress´es a` fournir des m´ethodes pour analyser des grands graphes en se
focalisant sur sa structure. R´ecemment, face `a l’h´et´erog´en´eit´e des sources
de donn´ees continues comme par exemple des donn´ees temporelles provenant de diff´erents types de capteurs (e.g., temp´erature, humidit´e, vent,
position), des propositions visant a` travailler sur des structures de graphes
plus sophistiqu´ees telles que les graphes d’arˆetes-attribu´ees sont apparues,
apportant des ´eclairages nouveaux sur de telles donn´ees. L’objectif de ce
stage de master est de concevoir une m´ethode originale d’extraction de
connaissances pertinentes dans des donn´ees temporelles et h´et´erog`enes que
nous mod´eliserons sous forme de graphes d’arˆetes-attribu´ees. Il s’agit donc
de d´efinir une m´ethode g´en´erique permettant d’extraire des comportements
p´eriodiques dans des graphes d’arˆetes-attribu´ees. Le mod`ele global ainsi
construit pourra ˆetre ensuite utilis´e pour d´ecouvrir et expliquer des comportements anormaux/exceptionnels dans les donn´ees. Ce sujet de master
qui s’inscrit dans le domaine de l’extraction de connaissances dans des
grandes bases de donn´ees s’appuiera donc sur une mod´elisation sous forme
de graphes d’arˆete-attribu´es. L’approche d´evelopp´ee devra faire avancer
l’´etat de l’art sur la fouille de donn´ees sous contraintes, les m´ethodes d’extraction de motifs, la fouille de donn´ees interactive. Des exp´erimentations
iv


sur des donn´ees issues de centrales photovolta¨ıques seront men´ees.
Mots-cl´es : graphe d’arˆetes-attribu´ees, s´eries temporelles, FastRabbit,
fouille des motifs locaux

v


Abstract
Graph is a mathematical abstraction that can naturally represent many
real phenomena. The graph mining is a major field of data mining. Many

studies have focused on providing methods to analyze large graphs by focusing on its structure. Recently, the heterogeneity of continuous sources
of data such as temporal data from different types of sensors (eg, temperature, humidity, wind, position), proposals to work on more sophisticated
graph structures such as edge-attributed graphs. The aim of this master
intership is to design an original method of extraction knowledge in temporal and heterogeneous data that we will model as edge-attributed graphs.
It is therefore to define a generic method for extracting periodic behavior
in the edge-attributed graphs. The global model thus constructed can then
be used to explore and explain abnormal/exceptional behavior in the data.
This topic master who is in the field of knowledge discovery in large databases will rely on modeling as edge-attributed graphs. The developed
approach will advance the state of the art data mining with constraints,
the methods of motif extraction, interactive data mining. Experiments on
data from photovoltaic central will be conducted.
Keywords : edge-attributed graphs, time series, FastRabbit, local pattern mining

vi


Table des figures
1.1

Structure des capteurs photovolta¨ıques [1] . . . . . . . . .

3

1.2

Des arbres devant la fa¸cade et sur l’horizon [1] . . . . . . .

3

2.1


Un exemple de Chromatic correlation clustering [2] . . . .

8

2.2

Un exemple de r´eseau social [3] . . . . . . . . . . . . . . .

8

2.3

Une partition de Chromatic Correlation Clustering [3] . . .

9

2.4

Coˆ
ut de Chromatic Correlation Clustering [3] . . . . . . .

9

2.5

Un exemple de graphe d’arˆetes-´etiquett´es [2] . . . . . . . .

10


2.6

Un exemple de clustering par Chromatic pivot [3] . . . . .

11

2.7

Un exemple de clustering par Lazy Chromatic pivot [3] . .

12

2.8

Exemple d’un r´eseau bay´esien [4] . . . . . . . . . . . . . .

14

2.9

Exemple d’une s´erie temporelle . . . . . . . . . . . . . . .

17

2.10 La diff´erence entre distance Euclidienne et distance DTW [5] 18
2.11 Un grid DTW [6] . . . . . . . . . . . . . . . . . . . . . . .

18

2.12 Condition monotone [5] . . . . . . . . . . . . . . . . . . . .


19

2.13 Condition de continuit´e [5] . . . . . . . . . . . . . . . . . .

19

2.14 Condition de fronti`ere [5] . . . . . . . . . . . . . . . . . . .

20

2.15 Condition de Warping Window [5] . . . . . . . . . . . . . .

20

2.16 Condition d’angle [5] . . . . . . . . . . . . . . . . . . . . .

20

2.17 Une s´equence de la taille 128 est r´eduite en 8 dimensions [7]

23

2.18 Le tableau statistique pour diviser la courbe Gaussienne [7]

23

2.19 Discretisation avec le nombre de symbol a = 3 [7] . . . . .

24


vii


2.20 Distance mesur´ee sur la repr´esentation symbolique [7] . . .

24

2.21 Le tableau utilis´e par la fonction MINDIST [7] . . . . . . .

25

4.1

Performance de l’algorithme FastRabbit . . . . . . . . . .

34

4.2

Nombre de motifs avant et apr`es post-traitement . . . . . .

34

4.3

Visualisation des positions de capteurs . . . . . . . . . . .

36


4.4

Graphe d’arˆetes-attribu´ees avec contexte g´en´erale

. . . .

37

4.5

Un motif d´etect´e par l’algorithme FastRabbit . . . . . . .

37

4.6

Un motif d´etect´e par l’algorithme FastRabbit . . . . . . .

38

4.7

Un graphe qui a seulement 2 sommets

. . . . . . . . . . .

38

4.8


Un motif avec le jour type ”Ensoleill´ee” . . . . . . . . . . .

39

4.9

Un motif avec le jour type ”non Vent´ee” . . . . . . . . . .

39

4.10 R´eseau bay´esien du jeu de donn´ees Juillet 2012 . . . . . .

40

4.11 Un groupe exceptionnel d´etect´e par EMM . . . . . . . . .

40

4.12 Un autre r´esultat exceptionnel . . . . . . . . . . . . . . . .

41

4.13 Conditions pour d´eterminer un groupe . . . . . . . . . . .

41

1


Chapitre 1


Introduction
1.1

Contexte g´
en´
eral et probl´
ematique

Les travaux de ce stage se sont d´eroul´es au sein de l’´equipe Data Mining
et Machine Learning (DM2L) du laboratoire informatique LIRIS UMR
5205, et sont en collaboration avec laboratoire solaire et thermique CETHIL UMR 5008. Les physiciens du CETHIL ont install´e un r´eseau de capteurs qui collecte des donn´ees temporelles et h´et´erog`enes. L’installation des
sondes (des capteurs) est effectu´ee sur face ouest du bˆatiment HBS-Technal,
a` Toulouse. Nous avons environ 150 capteurs qui mesurent diff´erents types
de donn´ees (e.g., la temp´erature, l’humidit´e, le vent). L’´echantillon se compose de la s´equence de donn´ees r´ecup´er´ees en juillet 2012, le mois o`
u on a
constat´e un ph´enom`ene d’ombrage vers 18h tous les jours.
Des sondes de temp´erature sont install´ees sur les surfaces, la structure ”peignes” est utilis´ee pour les mesures de vitesse. L’´etat des capteurs est bon vieillissement g´en´eral, beaucoup de toiles d’araign´ees (gˆenant
pour la circulation d’air), certains des sondes d´econnect´ees ou partiellement
d´ecoll´ees des surfaces.

2


Figure 1.1 – Structure des capteurs photovolta¨ıques [1]
L’objectif de cette installation est d’observer l’´evolution de r´eseau de
capteurs afin de d´etecter des anomalies ou des comportements sp´eciaux.
En plus, avec la croissance des arbres devant la fa¸cade et sur l’horizon,
des impacts de cette ´ev´enement sur des capteurs seront consid´er´es car le
ph´enom`ene d’ombrage est une contrainte obligatoire avec des ´etudes de

temp´erature et solaire dans des villes modernes.

Figure 1.2 – Des arbres devant la fa¸cade et sur l’horizon [1]

3


1.2

Motivation et objectifs

Avec le d´ev´elopement des technoligies, les volumes de donn´ees collect´ees
par les entreprises ou les laboratoires sont devenus ´enormes. En observant
des ph´enom`enes sp´eciaux dans un jeu de donn´ees massive, les d´ecideurs
sont extrˆemement difficles d’avoirs une bonne vision des leurs donn´ees afin
d’en tirer des connaissances et b´en´efices. R´ecemment, pour d´etecter des
motifs exceptionnelles, de nombreuses approches en basant la structure du
graphe sont propos´ees. Le graphe est un puissant outil de mod´elisation,
nous pouvons facilement observer des sous parties et des comportements
anormaux sur un graphe. Dans le cadre de ce stage, nous proposons une
m´ethode d’extraction des connaissances dans des donn´ees de capteurs que
nous mod´eliserons sous forme de graphes arˆetes-attribu´ees. L’approche
d´evelopp´ee va faire avancer l’´etat de l’art sur la fouille de donn´ees sous
contraintes et la fouille de motifs locaux.
R´ecemment, les syst`emes photovolta¨ıques int´egr´es au bˆatiments offrent
une solution prometteuse pour une production locale d’´electricit´e propre
et naturelle. Nous voudrions donc observer l’´evolution des capteurs enfin
de d´etecter des comportement anormaux. L’objectif principal de ce travail
est de proposer une technique de formulation des donn´ees de capteurs sous
forme graphes d’arˆetes-attribu´ees et puis, d´evelopper un algorithme d’extraction des sous graphes (i.e. sous groupes de capteurs) ”int´eressantes”,

exceptionnelles. Par example, des groupes de capteurs qui mal fonctionnent
(en panne, ou en raison de jours sp´eciaux comme trop chaude ou trop
vent´ee). L’id´ee de notre approche est introduite dans la section suivante.

4


1.3

Approche propos´
ee

Notre approche a deux principales ´etapes : mod´elisation du probl`eme
sous forme graphe d’arˆetes-attribu´ees et r´ealisation d’un algorithme (qui
s’appelle FastRabbit) pour d´etecter des arˆetes diff´erents, anormaux sous
contraints. Pour la mod´elisation, nous consid´erons chaque capteur est un
sommet du graphe, on a totalement 151 sommets. Une arˆete pr´esente la
relation de 2 capteurs dans un jours. La distance entre 2 capteurs est
consid´er´ee comme un des attributs importants d’une arˆete, 2 mesures de
´
distance seront pr´esenter pr´ecis´ement dans le chapitre ”Etat
de l’art”. Pour
l’algorithme FastRabbit, il exploite des contraintes, v´erifie la diff´erence
d’une arˆete dans un contexte, i.e. un groupe des contraints, par le teste
statistique χ2 et calcule quelques mesures de qualit´e d’un motif. Nous devons consid´erer en mˆeme temps tous les contextes possible et tous les sousgraphes de chaque contexte, le temps et l’espace de recherche sont donc le
major probl`eme de cette approche.
Nous pr´esentons ensuite les principales contributions de ce m´emoire et
terminons ce chapitre en ´enon¸cant le plan du m´emoire.

1.4


Contributions

Les principales contributions de ce m´emoire sont :
— Des mesures de dissimilarit´e entre des capteurs. Nous pr´esentons
des donn´ees de capteurs sous forme s´erie temporelle et puis, mesurons la distance entre des s´eries temporelles par deux techniques
Distance Time Warping (DTW) et Symbolic Aggregate approXimation (SAX).
— Une formulation du probl`eme sous forme graphe d’arˆetes-attribu´ees.
Nous d´efinissons la structure du graphe d’arˆetes-attribu´ees avec des
5


distances mesur´ees, des corr´elation de capteurs et des jours types
(e.g., fort/faible ensoleillement, avec/sans vent). Quelques mesures
pour ´evaluer la qualit´e d’une arˆete ainsi qu’un motif sont pr´esent´ees.
— Une d´eveloppement de l’algorithme FastRabbit qui extrait des motifs exceptionnels sous contraintes. La sortie de cet algorithme est
des motifs au sens d’optimum de Pareto, i.e., ce sont des meilleurs
motifs d’apr`es des mesures de qualit´e et les uns ne dominent pas les
autres.

1.5

Organisation du m´
emoire

La suite de ce m´emoire est organis´ee de la mani`ere suivante. Le chapitre
2 effectue un tour d’horizon des approches existantes dans le domaine de ce
travail. Dans ce chapitre, nous pr´esentons aussi deux techniques DTW et
SAX pour mesurer la distance entre des capteurs parce que des mesures de
distance sont la cl´e des m´ethodes de d´etection des diff´erences ou des anomalies. Dans le chapitre 3, nous repr´esentons le probl`eme sous forme graphe

d’arˆetes-attribu´ees. Ensuite, nous introduisons des d´efinitions formelles et
l’algorithme FastRabbit qui calcule des motifs d’optimum de Pareto dans
graphe d’arˆetes-attribu´ees. Le chapitre 4 pr´esente des exp´erimentations et
le r´esultat au niveau quantitatif et qualitatif. Nous concluons le m´emoire
et proposons quelques perspectives par le chapitre 5.

6


Chapitre 2

´
Etat
de l’art
Dans la premi`ere partie de ce chapitre, nous pr´esentons et discutons
les approches de la litt´erature proches de notre probl´ematique. Ensuite,
dans la deuxi`eme partie, nous introduisons comment pr´esenter les donn´ees
de notre projet RESSOURCE-HBS sous forme s´erie temporelle et nous
pr´esentons 2 techniques Dynamic Time Warping (DTW) et Symbolic Aggregate approXimation (SAX) pour mesurer la distance entre des s´eries
temporelles.

2.1
2.1.1

Revue de la bibliographie
Chromatic correlation clustering

Introduction
Dans [2], l’auteur a pr´esent´e une technique d’extraction des sous-graphes
similaires dans graphe d’arˆetes-attribu´ees. Ce probl`eme peut ˆetre consid´er´e

comme un clustering des sommets d’un graphe dont des arˆetes ont des
´etiquettes (couleurs) diff´erentes.

7


Figure 2.1 – Un exemple de Chromatic correlation clustering [2]
La similarit´e d’objets x et y est pr´esent´ee par la fonction sim(x, y). Dans
cet article [2], la relation entre des objets est pr´esent´ee par une ´etiquette
l a` partir d’un ensemble fini des ´etiquettes possibles L. Si 2 objets x et y
n’ont aucune relation, nous d´enotons par l’´etiquette l0 ∈
/ L.
L’entr´ee de ce probl`eme est un graphe d’arˆetes-attribu´ees G = (V, E, L, l)
o`
u V est l’ensemble des sommets, E = {(x, y) ∈ V × V | l(x, y) = l0 },
chaque arˆetes a une ´etiquette dans L (on peut consid´erer une ´etiquette
comme une couleur).
L’objective de ce framework est de chercher des partitions dans graphe
o`
u des arˆetes ont mˆeme une couleur. Observer l’exemple suivant :

Figure 2.2 – Un exemple de r´eseau social [3]
Chaque arˆete a une ´etiquette (couleur ou attribut). Nous voudrions
regrouper des sommets similaires et maximiser le nombre des arˆetes dans
chaque cluster le plus possible. Nous avons un r´esultat comme suivant :

8


Figure 2.3 – Une partition de Chromatic Correlation Clustering [3]

Chaque solution a un coˆ
ut, ce sont :
— des arˆetes qui ne sont pas dans un mˆeme cluster
— des arˆetes dans un mˆeme cluster mais la couleur de cette arˆete est
diff´erente avec la couleur de cluster, ou des arˆetes entre 2 sommets
qui n’ont aucune relation

Figure 2.4 – Coˆ
ut de Chromatic Correlation Clustering [3]
Nous introduisons maintenant la formulation du probl`eme Chromatic
Correlation Clustering :
´
Etant
donn´e un ensemble d’objets label V , un ensemble d’´etiquettes L,
une ´etiquette sp´eciale l0 et une fonction d’´etiquette l : V × V → L ∪ {l0 },
chercher un clustering C : V → N et une fonction d’´etiquette de cluster
cl : C[V ] → L qui minimiser le coˆ
ut :
(1 − I[l(x, y) = cl(C(x))]) +

cost(C, cl) =
(x,y)∈V ×V
C(x)=C(y)

I[l(x, y) = l0 ]
(x,y)∈V ×V
C(x)=C(y)

9



o`
u I est la fonction indicatrice, par example :

I[l(x, y) = cl(C(x))] =



1 si l(x, y) = cl(C(x))

0 si l(x, y) = cl(C(x))

Dans la section suivant, nous pr´esentons un algorithme Chromatic pivot
pour identifier des clusters. Il choisit une arˆete al´eatoire comme un pivot
et construit un cluster autour ce pivot. Cet algorithme a quelques limites
et l’auteur a pr´esente ensuite une ´evolution qui s’appelle Lazy Chromatic
pivot pour choisir mieux le pivot.
Algorithme Chromatic pivot
Les principales ´etapes de cet algorithme sont :
— Par hasard, choisir une arˆete (u, v) de couleur c
— Faire un cluster avec u, v et des voisins w, (u,v,w) est triangle monochromatique (i.e., l(u, w) = l(v, w) = l(u, v))
— Assigner couleur c
— Rep´eter les ´etapes pr´ec´edentes jusqu’`a les sommets du graphe sont
vides
Observons l’exemple dans le figure suivant :

Figure 2.5 – Un exemple de graphe d’arˆetes-´etiquett´es [2]
Supposons que le premier pivot est (Y, S), le premier cluster est donc
{Y, S, T } parce que l(Y, T ) = l(S, T ) = l(Y, S) = rouge. Continuons avec


10


(X, Z) comme le pivot, nous obtenons un cluster {X, W, Z} avec la couleur verte. R´ep´eter ce processus, deux derniers cluster {U, V } et {R} sont
obtenus.

Figure 2.6 – Un exemple de clustering par Chromatic pivot [3]
Dans cet exemple, nous voyons ´evidemment que le plus grand cluster
est le cluster vert {U, V, R, X, Y, Z, W } mais avec le fa¸con de s´election du
` cause de cette limite,
pivot, nous obtenons seulement des petits clusters. A
l’auteur pr´esente un autre algorithme, le pivot est choisit bas´e sur le degr´e
d’un sommet.
Lazy Chromatic pivot
Les ´etapes de cet algorithme sont similaires avec Chromatic pivot, nous
avons 2 points diff´erents :
— S´election du pivot (x,y) : pas par hasard, le pivot est choisit par le
degr´e chromatique maximal.
— Construction de cluster autour de (x,y) : non seulement des sommets
triangle monochromatique avec le pivot mais aussi des sommets adjacents et mˆeme couleur avec le pivot
Retournons l’exemple au dessus, maintenant nous cherchons un sommet
qui a le degr´e d’un couleur le plus grand. Le sommet X ou Y a mˆeme
degr´e 5 de couleur verte. Nous choisissons le sommet X. Et puis, pour
construire le pivot, nous cherchons un deuxi`eme sommet adjacent avec X
et son degr´e est le plus grand. Le sommet Y est donc choisit, le pivot
maintenant est (X, Y ). Ensuite, les sommets {U, V, Z} sont ajout´es dans
11


le cluster parce que chaque sommet U, V, Z est triangle vert avec le pivot.

Et puis, l’algorithme ajoute aussi {R} et {W } dans le cluster car ils sont
triangle vert avec (X, Z) et (Y, V ). Nous obtenons un cluster verte, r´ep´etons
ces ´etapes pr´ec´edentes, un autre cluster rouge est d´etect´e. Le figure dessous
montre le r´esultat de Lazy Chromatic pivot :

Figure 2.7 – Un exemple de clustering par Lazy Chromatic pivot [3]

2.1.2

Exceptional Model Mining

Introduction
Exceptional Model Mining (EMM) [8] est un framework pour trouver
des sous-groupes dans une base de donn´ees o`
u ses distributions sont nottamment diff´erentes avec la distribution de la base de donn´ees. Dans les
m´ethodes classiques de d´ecouverte des sous-groupes (subgroup discovery,
en anglais), des groupes sp´eciaux sont d´etect´es en basant sur la distribution d’une seule attribute cibl´ee. Par contre, EMM accepte des concepts
cibl´ees plus complexes. En plus, nous voulons chercher non seulement des
motifs exceptionnels mais aussi des interd´ependances entre eux. Dans l’article [4], l’auteur a appliqu´e le framework EMM sur plusieurs variables
cibl´ees discr`etes, les interd´ependances de cibles sont pr´esent´ees par le r´eseau
bay´esien. On a deux crit`eres pour choisir un sous-groupe :
— la distance entre sous-groupe et le jeu de donn´ee doit ˆetre grande
— un groupe qui ont la taille trop petit ou trop large n’est pas consid´er´e

12


Dans la partie suivante, nous repr´esentons quelques notions et la technique EMM avec multi variables cibl´ees discr`etes d’apr`es l’article [4]
EMM dans des donn´
ees avec multi variables cibl´

ees discr`
etes
Supposons que des tuples dans un jeu de donn´ees D sont d´ecrits sous
forme {a1 , . . . , ak , t1 , . . . , tm }, k est le nombre d’attributes de description
(k ≥ 1) et m est le nombre d’attributes de cible (ou mod`ele) (m ≥ 1). Avec
le tˆache SD (subgroup discovery) classique, on a seulement un attribut de
cible t1 . Par contre, nous avons plusieurs attributs t1 , . . . , tm dans le tˆache
EMM.
Par exemple, avec le jeu de donn´ees Juillet 2012, on a 30 jours et 30 matrices de corr´elation Pearson, ils sont correspondants avec 30 tuples.Dans
chaque tuple, la partie de description est des valeurs de corr´elation entre
capteurs, la partie de cible est trois valeurs discr`etes de jourtype : Ensoleill´ee, Vent´ee, Chaude. Nous cherchons des jours o`
u la distribution (le
mod`ele) de jourtype est diff´erente avec le mod`ele de jourtype dans le jeu
de donn´ees.
Un autre terme important, c’est la fonction Mesure de qualit´e ϕ : P →
R qui assigne un motif, pattern p a` une valeur r´eelle r. Une valeur de mesure
de qualit´e montre comment un sous-groupe est int´eressant, diff´erent avec
des autres.
Nous voudrions observer des interd´ependances entre des cibles et puis,
utiliser ces interd´ependances pour valider des sous-groupes. Des interd´ependances
sont donc mod´elis´ees d’abord, nous appliquons le r´eseau bay´esien sur des
variables cibl´ees. Dans [4], L’auteur a choisit la technique Bayesian Dirichlet equivalent uniform (BDeu) [9]. Noter bien que pour un mˆeme jeu de
donn´ees, des r´eseaux bay´esiens peuvent ˆetre diff´erents.
Un r´eseau bay´esien est un graphe orient´e acyclique (DAG) qui pr´esente
l’ensemble des variables al´eatoires et l’interaction entre eux. Nous construi13


sons deux r´eseaux bay´esiens, un sur des cibles du jeu de donn´ees et un autre
sur des cibles des sous-groupes envisag´es. Maintenant, nous voudrions comparer le structure ces deux r´eseaux. L’id´ee est de trouver des sous-groupes
qui sont les plus diff´erents avec le jeu de donn´ees.


Figure 2.8 – Exemple d’un r´eseau bay´esien [4]
D´
efinition 1 (V-structure). Un V-structure dans un r´eseau bay´esien est un
ensemble de trois sommets {x,y,z} o`
u le r´eseau contient des arˆetes x → y
et z → y mais il n’existe pas d’arˆet entre x et z.
V-structure est immoralit´e, i.e., on n’a pas d’arˆete entre x et z (e.g.
r´eseau (c) au d´esus). Un graphe peut ˆetre moralis´e en ajoutant une arˆete
entre des couples de sommet qui a un enfant commun mais n’a pas une
arˆete commune (e.g. r´eseau (d) au d´esus).
Th´
eorem 1 (Equivalent DAGs). Deux graphes orient´es acycliques (DAGs)
sont ´equivalents si et seulement si ils ont le mˆeme squelette et le mˆeme vstructure.
D´
efinition 2 (Edit distance for Bayesian networks). Supposons BN1 et
BN2 sont deux r´eseaux bay´esiens avec le mˆeme de nombre de sommet,
d´enote par m. D´enote l’ensemble d’arˆetes de ses squelettes par S1 et S2 ,
l’ensemble de ses graphes moralis´es par M1 et M2 . Supposons

l = [S1 ⊕ S2 ] ∪ [M1 ⊕ M2 ]
14


o`
u X ⊕ Y = (X ∪ Y ) − (X ∩ Y ) La distance entre BN1 et BN2 est
d´efinit comme :

d(BN1 , BN2 ) =


2l
m(m − 1)

D’apr`es le formule, les distances entre des graphes dans le figure d’exemple
ci-d´esus sont : d(a, b) = 0etd(a, c) = d(a, d) = d(b, c) = d(b, d) = d(c, d) =
1
3.

D´
efinition 3 (Edit distance based quality measure). D´enote le r´eseau
bay´esien du jeu de donn´ee D par BND , le r´eseau bay´esien d’un sous-groupe
p par BNp . La qualit´e de p est :

ϕed (p) = d(BND , BNp )
La formule ci-d´esus est une mesure de qualit´e, une autre mesure va ˆetre
introduit dans suivant.
D´
efinition 4 (Entropie). Entropie d’un sous-groupe p :

ϕent (p) = −

n
n
N −n N −n
lg( ) −
lg(
)
N
N
N

N

o`
u n et N sont des tailles de sous-groupe et jeu de donn´ees.
D´
efinition 5 (Weighed Entropy and Edit Distance). L’auteur a propos´e
une autre quality mesure qui est bas´ee sur l’entropie d’un sous-groupe :
ϕweed (p) =

2.1.3

ϕent (p).ϕed (p)

Discussions

Nous avons vu 2 approches Chromatic Correlation Clustering [2] et Exceptional Model Mining [8, 4] pour la tˆache d’extraction des sous-groupes
dans une base de donn´ees.
15