Mining and ranking closed itemsets from large-scale transactional datasets

Résumé : Les algorithmes actuels pour la fouille d’ensembles fréquents sont dépassés par l’augmentation des volumes de données. Dans cette thèse nous nous intéressons plus particulièrement aux données transactionnelles (des collections d’ensembles d’objets, par exemple des tickets de caisse) qui contiennent au moins un mil- lion de transactions portant sur au moins des centaines de milliers d’objets. Les jeux de données de cette taille suivent généralement une distribution dite en “longue traine”: alors que quelques objets sont très fréquents, la plupart sont rares. Ces distributions sont le plus souvent tronquées par les algorithmes de fouille d’ensembles fréquents, dont les résultats ne portent que sur une infime partie des objets disponibles (les plus fréquents). Les méthodes existantes ne per- mettent donc pas de découvrir des associations concises et pertinentes au sein d’un grand jeu de données. Nous proposons donc une nouvelle sémantique, plus intuitive pour l’analyste: parcourir les associations par objet, au plus une centaine à la fois, et ce pour chaque objet présent dans les données. Afin de parvenir à couvrir tous les objets, notre première contribution consiste à définir la fouille centrée sur les objets. Cela consiste à calculer, pour chaque objet trouvé dans les données, les k ensembles d’objets les plus fréquents qui le contiennent. Nous présentons un algorithme effectuant ce calcul, TopPI. Nous montrons que TopPI calcule efficacement des résultats intéressants sur nos jeux de données. Il est plus performant que des solutions naives ou des émulations reposant sur des algorithmes existants, aussi bien en termes de rapidité que de complétude des résultats. Nous décrivons et expérimentons deux versions par- allèles de TopPI (l’une sur des machines multi-coeurs, l’autre sur des grappes Hadoop) qui permettent d’accélerer le calcul à grande échelle. Notre seconde contribution est CAPA, un système permettant d’étudier quelle mesure de qualité des règles d’association serait la plus appropriée pour trier nos résultats. Cela s’applique aussi bien aux résultats issus de TopPI que de j LCM, notre implémentation d’un algorithme récent de fouille d’ensembles fréquents fer- més (LCM). Notre étude quantitative montre que les 39 mesures que nous com- parons peuvent être regroupées en 5 familles, d’après la similarité des classements de règles qu’elles produisent. Nous invitons aussi des experts en marketing à par- ticiper à une étude qualitative, afin de déterminer laquelle des 5 familles que nous proposons met en avant les associations d’objets les plus pertinentes dans leur domaine. Notre collaboration avec Intermarché, partenaire industriel dans le cadre du projet Datalyse, nous permet de présenter des expériences complètes et por- tant sur des données réelles issues de supermarchés dans toute la France. Nous décrivons un flux d’analyse complet, à même de répondre à cette application. Nous présentons également des expériences portant sur des données issues d’Internet; grâce à la généricité du modèle des ensembles d’objets, nos contributions peuvent s’appliquer dans d’autres domaines. Nos contributions permettent donc aux analystes de découvrir des associations d’objets au milieu de grandes masses de données. Nos travaux ouvrent aussi la voie vers la fouille d’associations interactive à large échelle, afin d’analyser des données hautement dynamiques ou de réduire la portion du fichier à analyser à celle qui intéresse le plus l’analyste.
Type de document :
Thèse
Databases [cs.DB]. Université Grenoble Alpes, 2016. English
Liste complète des métadonnées

Littérature citée [73 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01378794
Contributeur : Martin Kirchgessner <>
Soumis le : lundi 10 octobre 2016 - 17:45:41
Dernière modification le : jeudi 11 octobre 2018 - 08:48:05
Document(s) archivé(s) le : samedi 4 février 2017 - 01:30:24

Fichier

Identifiants

  • HAL Id : tel-01378794, version 1

Collections

Citation

Martin Kirchgessner. Mining and ranking closed itemsets from large-scale transactional datasets. Databases [cs.DB]. Université Grenoble Alpes, 2016. English. 〈tel-01378794〉

Partager

Métriques

Consultations de la notice

392

Téléchargements de fichiers

299