Exploitation du DIG-DAG

Exploitation du DIG-DAG

 Extraction de motifs pertinents

Dans cette section, nous présentons une solution permettant d’extraire d’un DIG-DAG ou d’un sous-DIG-DAG les chaînes de causalité potentielle conformes à une recherche spécifiée par l’utilisateur. Définition 7 (sous-DIG-DAG) Soient D = (V, E, λ, A) un DIG-DAG, et (V 0 , E0 ) un sous-graphe de (V, E). Le quadruplet D0 = (V 0 , E0 , λ|V 0, A ∩ V 0 ) est un sous-DIG-DAG de D. On peut remarquer qu’un sous-DIG-DAG n’est pas nécessairement un DIG-DAG : il pourrait très bien avoir plusieurs racines ou être non connexe.

Requêtes

Nous cherchons à présent à formaliser un système de requête conforme au modèle introduit par la définition 7 et pratique pour l’utilisateur. Définition 8 (Requête et sous-DIG-DAG correspondant) Une requête est définie par un quintuplet Q = (D, S, T, Vi , Ei), où D = (V, E, λ, A) est un DIG-DAG, S, T, Vi ⊆ V et Ei ⊆ E. Le résultat de cette requête est le plus grand sous-DIG-DAG (V 0 , E0 , λ0 , A0 ) de D tel que : • V 0 ⊆ Vi , E0 ⊆ Ei ; • les sommets de degré entrant 0 sont tous dans S ; • les sommets de degré sortant 0 sont tous dans T. Le résultat de la requête est noté D0 (Q). Intuitivement, le sous-DIG-DAG de D issu d’une requête Q = (D, S, T, Vi , Ei) est le sous-graphe de D dont les chemins maximaux partent tous de S et terminent dans T. Ces chemins ne passent que par les sommets de Vi et les arcs de Ei .

Requêtes régulières

La définition de requête est très large et, dans ce paragraphe, nous nous restreignons aux requêtes paramétrées par un automate fini et des propriétés locales sur les sommets et sur les arcs. Intuitivement, le rôle de l’automate fini est de stocker des motifs satisfaisant certaines relations entre les sommets, tandis que les propriétés locales permettent de sélectionner arcs et sommets. Ces propriétés ne dépendent pas seulement des symboles portés par les sommets (elles auraient pu sinon être inclues dans un automate), mais reposent sur tout type de métadonnées rattachées aux sommets. Par exemple, il peut être utile d’extraire des sommets récemment actifs ou de ne conserver que des arcs pertinents (pertinence définie à partir de la pondération décrite en section 3.2.4). Définition 9 (Requêtes régulières) Soient M un automate fini, ainsi que Pv : V → {0, 1} et Pe : E → {0, 1} deux propriétés (respectivement sur les sommets et sur les arcs). On définit la requête régulière R(S, T,M, Pv, Pe) = (S, T, Vi , Ei), où : • pour tout u ∈ Vi, u satisfait Pv ; • pour tout (u, v) ∈ Ei, (u, v) satisfait Pe ; • D0 (R(S, T,M, Pv, Pe)) contient tous les chemins étiquetés de D0 ((D, S, T, Pv, Pe)) reconnus par M. Par conséquent, Si et Ti sont respectivement définis par l’ensemble des sommets et des arcs appartenant à ces chemins ; • D0 (R(S, T,M, Pv, Pe)) est le plus petit sous-DIG-DAG de D (au sens de l’inclusion) satisfaisant ces propriétés. L’algorithme 3 calcule le sous-DIG-DAG correspondant à une requête régulière donnée. Nous supposons que nous connaissons un ordre topologique sur les sommets. Pour cela, il est possible d’utiliser un algorithme classique (cf. [Cormen et al., 2009] (section 22.4) par exemple). L’ordre topologique peut aussi être calculé en ligne au moment de l’indexation des sommets lors de la construction du DIG-DAG. En effet, pendant la mise à jour du DIG-DAG (cf. algorithme 2), les nouveaux sommets qui ne sont pas issus d’une scission sont toujours des feuilles : incrémenter leur indexe suffit à entretenir un ordre. Le cas de la fusion est réglé en conservant le maximum des deux indices. Concernant les scissions, il suffit de décider d’un sous-ordre arbitraire entre les copies. Il n’est alors plus utile de recalculer cet ordre topologique par la suite.  Algorithme 3 : regular_query(D,M, S, T, Pv, Pe) Entrées : D = (V, E, λ, A),M = (Q, Σ, δ, I, F), S, T, Pv, Pe Output : un sous-DIG-DAG D0 // Phase 1: parcours dans le sens direct 1 pour chaque u ∈ V faire Q1(u) ← ∅; 2 pour chaque u ∈ V (dans un ordre topologique) faire 3 si u ∈ S ∩ Pv alors Q1(u) ← Q1(u) ∪ I; 4 pour chaque v ∈ V ∩ Pv tel que (u, v) ∈ E ∩ Pe faire 5 Q1(v) ← Q1(v) ∪ {q 0 ∈ Q | ∃q ∈ Q1(u), δ(q, λ(v)) = q 0} // Phase 2: parcours en sens inverse 6 V 0 ← ∅ ; E0 ← ∅; 7 pour chaque u ∈ V faire Q2(u) ← ∅; 8 pour chaque u ∈ V (dans l’ordre topologique inverse) faire 9 si u ∈ T ∩ Pv alors Q2(u) ← Q2(u) ∪ (Q1(u) ∩ F); 10 si Q2(u) 6= ∅ alors 11 V 0 ← V 0 ∪ {u} 12 pour chaque v tel que (v, u) ∈ E ∩ Pe faire 13 si {q ∈ Q1(v) | ∃q 0 ∈ Q2(u), δ(q, λ(u)) = q 0} 6= ∅ alors 14 E0 ← E0 ∪ {(v, u)}; 15 Q2(v) ← Q2(v) ∪ {q ∈ Q1(v) | ∃q 0 ∈ Q2(u), δ(q, λ(u)) = q 0} 16 renvoyer D0 = (V 0 , E0 , λ|V 0, A ∩ V 0 ) L’algorithme 3 est réalisé en deux étapes : la première identifie, par un parcours dans le sens direct, tous les chemins possibles partant de S, dont les sommets et arcs vérifient respectivement Pv et Pe, et dont les étiquettes forment des préfixes de mots reconnus par l’automate. Pour cela, un ensemble Q1(u) est attribué à chaque sommet u ∈ V , contenant tous les états de l’automate qui peuvent être atteints depuis un sommet de S. La seconde étape consiste en un parcours inverse de D qui identifie les sommets et les arcs qui appartiennent au sous-DIG-DAG désiré. Pour chaque sommet u, Q2(u) est le sousensemble d’états de Q1(u) tel qu’il y ait un chemin de u à un sommet de T qui corresponde à un chemin d’un état de Q2(u) vers un état terminal de l’automate. Les sommets et les arcs impliqués dans ces chemins constituent le sous-DIG-DAG souhaité. Plus formellement, soit M = (Q, Σ, δ, I, F) un automate fini, où Σ représente son alphabet, Q l’ensemble de ses états, I ses états initiaux, F ses états terminaux et δ sa fonction de transition. Nous représentons le DIG-DAG comme un automate : l’étiquette d’une transition (u, v) du DIG-DAG correspond à l’étiquette λ(v) du sommet cible. Notons que M ne 89 peut pas être utilisé pour conditionner la pertinence d’un chemin selon l’étiquette portée par le sommet de départ (ce qui peut être pris en charge par Pv). Nous montrons ensuite que le résultat renvoyé par l’algorithme 3 est le sous-DIG-DAG correspondant à la requête régulière définie dans la définition 9. Exposons tout d’abord quelques propriétés de Q2(u). Lemme 2 Avec les notations ci-dessus, • pour tout u ∈ V 0 et q ∈ Q2(u), soit il existe v ∈ V 0 et q 0 ∈ Q2(v) tels que (u, v) ∈ E0 et q 0 = δ(q, λ(v)), soit u ∈ T et q ∈ F ; • pour tout v ∈ V 0 et q 0 ∈ Q2(v), soit il existe u ∈ V 0 et q ∈ Q2(u) tels que (u, v) ∈ E0 et q 0 = δ(q, λ(v)), soit v ∈ S et q 0 ∈ I ; • pour tout v ∈ V 0 , pour tout q 0 ∈ Q2(v), il existe un chemin d’un sommet u ∈ S vers v correspondant à un chemin dans M d’un état initial q ∈ I vers q 0 ; u et v (resp. q et q 0 ) peuvent être confondus ; • pour tout v ∈ V 0 , pour tout q 0 ∈ Q2(v), il existe un chemin de v vers un sommet u ∈ T correspondant à un chemin dans M de q 0 vers un état terminal q ∈ F ; v et u (resp. q 0 et q) peuvent être confondus. Preuve. Commençons par prouver le premier point. Soit u ∈ V 0 un sommet du sousDIG-DAG renvoyé par l’algorithme 3. D’après la ligne 10, Q2(u) 6= ∅ puisque u a été retenu dans le sous-DIG-DAG. Soit q ∈ Q2(u). Cet état a été introduit soit à la ligne 15, soit à la ligne 9. Dans le premier cas, l’état q est rajouté après que le test de la ligne 13 soit passé : u est le prédécesseur d’un sommet v dans le sous-DIG-DAG (voir ligne 14) tel qu’il existe un état q 0 ∈ Q2(v) où δ(q, λ(v)) (ligne 15). Ou alors, cet état a été introduit au moment de la ligne 9, ce qui implique u ∈ T et q ∈ F. Pour prouver le second point du lemme, considérons un sommet v ∈ V 0 . D’après la ligne 10, Q2(v) 6= ∅. D’après les lignes 9 et 15, Q2(v) est un sous-ensemble de Q1(v). Ainsi, tout état q 0 ∈ Q2(v) est d’abord introduit dans Q1(v) par les lignes 3 et 5. S’il a été introduit dans 3, alors v ∈ S et q ∈ I. Sinon, il a été introduit au moment de 5 : il existe un sommet u ∈ V ∩ Pv et un état q ∈ Q1(u) tels que δ(q, λ(v)) = q 0 . Puisque q 0 ∈ Q2(v), alors q appartient aussi à Q2(u) (ligne 15) et u est un sommet du sous-DIG-DAG (ligne 11). Par ailleurs, l’arc (u, v) est un arc du sous-DIG-DAG d’après la ligne 14.

Simplification d’un sous-DIG-DAG

Bien que le système de requête permette de spécifier quelles parties du DIG-DAG extraire, le sous-DIG-DAG obtenu peut être grand selon la requête présentée par l’expert. En effet, le DIG-DAG peut être dense et les motifs recherchés peuvent apparaître à divers endroits dans la structure. Afin d’améliorer la lisibilité du résultat, cette section présente trois manières de simplifier le sous-DIG-DAG extrait. Notons que ces simplifications ne peuvent être considérées comme des opérations d’extraction de sous-DIG-DAG, puisqu’elles peuvent altérer la structure originale de DIG-DAG, en fusionnant des sommets, ou en n’étant pas compatibles avec la notion de poids développée dans le paragraphe 3.2.4. Ce n’est pas un inconvénient trop important puisque nous introduisons ces opérations pour améliorer la représentation graphique.