Parallel Itemset Mining in Massively Distributed Environments

Saber Salah 1
1 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Le volume des données ne cesse de croître. À tel point qu’on parle aujourd’hui de "Big Data". La principale raison se trouve dans les progrès des outils informatique qui ont offert une grande flexibilité pour produire, mais aussi pour stocker des quantités toujours plus grandes. Les méthodes d’analyse de données ont toujours été confrontées à des quantités qui mettent en difficulté les capacités de traitement, ou qui les dépassent. Pour franchir les verrous technologiques associés à ces questions d’analyse, la communauté peut se tourner vers les techniques de calcul distribué. En particulier, l’extraction de motifs, qui est un des problèmes les plus abordés en fouille de données, présente encore souvent de grandes difficultés dans le contexte de la distribution massive et du parallélisme. Dans cette thèse, nous abordons deux sujets majeurs liés à l’extraction de motifs : les motifs fréquents, et les motifs informatifs (i.e., de forte entropie). Les algorithmes d’extraction des motifs fréquents peuvent montrer de mauvaises per-formances lors du traitement des grandes volumes des données. Ceci est particulièrement le cas lorsque i) les données tendent à être très grandes et/ou ii) le seuil de support minimum est très faible. Dans cette thèse, nous adressons ce problème en faisant appel à des techniques spécifiques de placement des données dans des environnements massivement distribués pour améliorer la performance des algorithmes d’extraction des motifs fréquents. Nous étudions soigneusement l’impact de la combinaison d’un algorithme d’extraction des motifs fréquents avec une stratégie particulière de placement des données. Dans un premier temps, nous montrons que le choix d’une stratégie de placement des données dans un environnement massivement distribué, associé à un algorithme spécifique d’extraction des motifs, a un très fort impact sur le processus d’extraction et peut aller jusqu’à le rendre inopérant. Nous proposons ODPR (Optimal Data-Process relation ship) une solution pour l’extraction des motifs fréquents dans MapReduce. Notre méthode permet de découvrir des motifs fréquents dans des grandes bases des données, là où les solutions standard de la littérature ne passent pas à l’échelle. Notre proposition a été évaluée en utilisant des données du monde réel. Nos différents résultats illustrent la capacité de notre approche à passer à l’échelle, même avec un support minimum très faible, ce qui confirme l’efficacité de notre approche. Sur la base de ce premier résultat, nous avons étendu ce travail en poussant encore un peu les possibilités apportées par le calcul distribué. Généralement, dans un environnement massivement distribué, la performance globale d’un processus est améliorée quand on peut minimiser le nombre de "jobs" (les "aller/retours" entre les machines distribuées). Cela impacte le temps d’exécution, mais aussi le transfert de données, etc. Dans le cas de l’extraction des motifs fréquents, la découverte des motifs fréquents en un seul job simplifié serait donc préférable. Nous proposons Parallel Absolute Top Down (PATD), un algorithme parallèle d’extraction des motifs fréquents qui minimise ces échanges. PATD rend le processus d’extraction des motifs fréquents dans les grandes bases des données (au moins 1 Téraoctets de données) simple et compact. Son processus d’extraction est constitué d’un seul job, ce qui réduit considérablement le temps d’exécution, les coûts de communication et la consommation énergétique dans une plate-forme de calcul distribué. Faisant appel à une stratégie adaptée et efficace de partitionnement des données nommée IBDP (Item Based Data Partitioning), PATD est capable de fouiller chaque partition des données indépendamment, en se basant sur un seuil de support minimum absolu au lieu d’un seuil relatif. La performance de l’algorithme PATD a été évaluée avec des données du monde réel. Nos résultats expérimentaux suggèrent que PATD est largement plus efficace par rapport à d’autres approches. Malgré les réponses que les algorithmes d’extraction des motifs fréquents fournissent concernant les données, certaines relations cachées ne peuvent pas être facilement détectées dans les données. Cela est particulièrement le cas lorsque les données sont extrêmement grandes et qu’il faut faire appel à une distribution massive. Dans ce cas, une analyse minutieuse de l’information contenue dans les motifs, mesurée grâce à l’entropie, peut donner plus d’explications et de détails sur les corrélations et les relations entre les données. Cependant, explorer de très grandes quantités des données pour déterminer des motifs informatifs présente un défi majeur dans la fouille des données. Ceci est particulièrement le cas lorsque la taille des motifs à découvrir devient très grande. Dans un deuxième temps, nous adressons donc le problème de la découverte des motifs informatifs maximales de taille k (miki ou "maximally informative k-itemsets) dans les big data. Nous proposons PHIKS (Parallel Highly Informative K-ItemSet), un algorithme pour leur extraction en environnement distribué. PHIKS rend le processus d’extraction de miki dans des grandes bases de données simple et efficace. Son processus d’extraction se résume à deux jobs. Avec PHIKS, nous proposons un ensemble de techniques d’optimisation pour calculer l’entropie conjointe des motifs de différentes tailles. Ceci permet de réduire le temps d’exécution du processus d’extraction de manière significative. PHIKS a été évalué en utilisant des données massives de monde réel. Les résultats de nos expérimentations confirment l’efficacité de notre approche par le passage à l’échelle de notre approche sur des motifs de grande taille, à partir de très grandes volumes données.
Type de document :
Thèse
Information Retrieval [cs.IR]. Université de Montpellier, 2016. English
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/tel-01415587
Contributeur : Reza Akbarinia <>
Soumis le : mardi 13 décembre 2016 - 12:14:53
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mardi 14 mars 2017 - 12:48:12

Identifiants

  • HAL Id : tel-01415587, version 1

Citation

Saber Salah. Parallel Itemset Mining in Massively Distributed Environments. Information Retrieval [cs.IR]. Université de Montpellier, 2016. English. 〈tel-01415587〉

Partager

Métriques

Consultations de la notice

474

Téléchargements de fichiers

651