Algorithmes par niveaux

Algorithmes par niveaux

Pour construire cet arbre des préfixes communs, de nombreuses approches en fouille de données exploitent la propriété d’anti-monotonie (c.f. 5.5.2) afin de procéder par niveaux [Agrawal et Srikant, 1995, Pei et al., 2004]. En effet, cette propriété stipule qu’aucun motif . Ainsi, quelque soit le seuil de fréquence considéré, si un motif P n’est pas fréquent, aucun motif construit par affixation de P ne pourra être fréquent. Il s’ensuit que, pour déterminer l’ensemble des motifs de taille n, nous pouvons n’examiner que ceux dont les sous-séquences de taille n 1 sont fréquents, appelés motifs candidats.Les niveaux correspondent donc à un partitionnement des motifs selon leur taille. L’ex- ploration itère sur la taille des motifs : à partir d’un niveau n, tous les motifs candidats de taille n + 1 sont générés, leurs fréquences sont relevées dans les données puis confrontées au seuil requis afin d’écarter ceux qui s’avèrent ne pas être suffisamment fréquents dans les données. Cette approche nous épargne de représenter et de tester tous les motifs de (, mais il sera alors crucial de pouvoir, à chaque itération, parcourir très rapidement la base de données afin d’y relever les occurrences des motifs pour un niveau donné.

Relever les occurrences dans la base de données

Les travaux de [Wang et Han, 1997] présentent plusieurs techniques afin de rechercher des occurrences de motifs au sein de séquences. Selon une méthode similaire, mineXtract itère sur les données (chaque énoncé et chaque token en leur sein) et réalise la recherche d’occurrences de motifs. Pour chaque token, une procédure récursive permet fait la corres- pondance, à la position donnée, entre l’arbre des préfixes communs et la portion de l’énoncé démarrant à cette position. Chaque motif pour lequel une occurrence est relevée verra sa fréquence incrémentée. A cet effet, nous implémentons une structure de donnée pour un token t en le munissant des attributs suivants :L’algorithme 1 présente une version simplifiée de la procédure tokenM otif s qui re- lève les occurrences de motifs à une position donnée d’un énoncé, aux marqueurs près. Remarquons que, pour optimiser ces parcours, l’algorithme suppose que certaines données ont préalablement été triées : les généralisations hiérarchiques retournées par la fonction parents et les alternatives au sein de l’arbre des préfixes communs. De surcroît, il nous faut tenir compte de deux particularités afin que l’anti-monotonie soit respectée :– Disjonction exclusive : la procédure altP arents permet de vérifier qu’il n’y a pas de comptage de doublons au sein d’une disjonction exclusive (lorsque deux items ont une généralisation commune).

Cet algorithme est au cœur de mineXtract. Nous en implémentons également une version adaptée à l’extraction de motifs de segments, qui associe à un item de motif autant de tokens que possible dans les données. Dans tous les cas, l’algorithme est précédé d’une procédure de génération des candidats et suivi d’une procédure d’élagage de l’arbre des préfixes. Ainsi, nous sommes en mesure de comptabiliser, par niveaux, les occurrences des motifs dans les données, jusqu’à ce qu’il n’y ait plus de motifs fréquents. Au terme de l’exploration, il est trivial de parcourir l’arbre des préfixes communs afin d’extraire les règles d’annotation informatives selon les critères présentés en section 5.5.4.vive de 30-40Go. Le corpus est enrichi selon les traitements morpho-syntaxiques et lexi- caux décrits en 7.2.1 et en 7.2.2. L’approche que nous adoptons nous contraint à explorer exhaustivement tous les motifs fréquents (et non seulement les règles d’annotation). Ainsi, au travers des itérations, seul le critère de fréquence est pris en compte pour filtrer les motifs. En fin de processus, la confiance est calculée afin d’extraire les règles fréquentes et confiantes.

L’arbre des préfixes est donc construit au fur et à mesure de l’exploration. Nous pouvons en mesurer la taille à chaque niveau selon le nombre de nœuds correspondants à des motifs candidats générés ou des motifs fréquents retenus. Nous nous apercevons cependant qu’il est possible d’optimiser la structure de l’arbre afin d’en limiter la taille et le temps de parcours [Wang et Han, 2004, Qian et al., 2010, Bonchi et Lucchese, 2005]. Effectivement, un nœud de l’arbre peut stocker plusieurs motifs lorsque ceux-ci ont exactement les mêmes occurrences dans les données. Or, pour deux motifs, nous pouvons affirmer qu’ils ont mêmes occurrences dans les données s’ils sont généralisation l’un de l’autre et qu’ils ont même fréquence. Selon ce principe, deux optimisations se sont avérées simples à implémenter et efficaces :