ECHANTILLONNAGE SOUS CONTRAINTES DE MOTIFS STRUCTURES

Résumé

La littérature de la découverte de motifs a longtemps lutté avec deux problèmes majeurs. Premièrement, il n'est pas possible d’utiliser directement les motifs pertinents si le seuil d'intérêt minimal est petit car ils sont bien trop nombreux. A l'opposé, si le seuil d'intérêt minimal est trop grand, certaines instances seront peu ou pas décrites. Deuxièmement, l'ensemble complet des motifs ayant satisfait la contrainte de seuil d'intérêt minimal peut contenir de nombreuses redondances. L'échantillonnage en sortie est une méthode non exhaustive pour la découverte instantanée de motifs intéressants qui assure une bonne interactivité tout en offrant de solides garanties statistiques en raison de sa nature aléatoire. Curieusement, une telle approche étudiée pour différents types de motifs, y compris les itemsets et les sous-graphes, n'a pas encore été appliquée aux motifs séquentiels et aux bases de données distribuées. Dans cette thèse, nous proposons de nombreuses méthodes dédiées à l'échantillonnage en sortie de motifs séquentiels, l'échantillonnage en sortie de motifs dans des bases de données distribuées et l'échantillonnage en sortie de motifs basé sur les tries. En plus de répondre à ces tâches complexes, l'originalité de nos approches est d'introduire une classe de mesures d'intérêt reposant sur la norme des motifs, nommée classe de mesures d'intérêt fondées sur la norme. En particulier, cette classe permet d'ajouter des contraintes sur la norme des motifs échantillonnés pour contrôler leur longueur et éviter l'écueil de la “longue traîne” où les motifs les plus rares inondent l'utilisateur. Dans ce cadre, nous proposons en premier lieu deux algorithmes nommés NUSSampling pour les bases de données séquentielles et DDSampling pour les bases de données distribuées. Basés sur des procédures aléatoires en deux étapes intégrant cette classe de mesures, ils tirent au hasard des motifs proportionnellement à la fréquence pondérée par une utilité fondée sur la norme. En second lieu, nous proposons TPSampling, un algorithme d'échantillonnage en sortie de motifs ensemblistes basé sur la structure du trie. Moins consommateur en mémoire, il tire aussi aléatoirement des motifs en fonction de leur fréquence pondérée par une utilité fondée sur la norme. Nous montrons que toutes nos méthodes effectuent un échantillonnage exact selon la mesure sous-jacente. Au niveau des applications, nous nous concentrons sur l'intérêt des contraintes de norme et de décroissance exponentielle qui aident à tirer des motifs généraux de la tête de la longue traine. Nous illustrons également comment profiter de ces motifs échantillonnés pour construire des classificateurs dédiés aux séquences et aux itemsets. Cette approche de classification rivalise avec les propositions de l'état de l'art montrant l'intérêt de l'échantillonnage en sortie de motifs avec une mesure d'intérêt fondée sur la norme. Par ailleurs, nous illustrons également l'intérêt des motifs échantillonnés sur les données distribuées du Web sémantique pour détecter des entités aberrantes dans DBpedia et Wikidata.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 4

Téléchargements : 0