Parallélisation de la méthode A Priori avec Apache Spark

Les RDD (Resilient Distributed Datasets)

L’un des grands principes de Spark est l’utilisation des Resilient Distributed Datasets (RDD). Un RDD représente une partition des données que l’utilisateur va utiliser pour ses calculs. Cette partition est mise en mémoire (RAM) pour éviter au système de faire des lectures sur disque, à chaque fois qu’une donnée est nécessaire à un calcul. Si la partition demandée est trop grande, le système ira chercher certaines données sur le disque. Les opérations sur un RDD sont effectuées de manière distribuée (selon le Spark Context utilisé), tout en étant tolérantes aux pannes matérielles. Le traitement que l’on écrit semble ainsi s’exécuter au sein de notre JVM mais il sera découpé pour s’exécuter sur plusieurs nœuds. En cas de perte d’un nœud, le sous traitement sera automatiquement relancé sur un autre nœud par le framework, sans que cela impacte le résultat. Deux concepts de base s’appuient et s’appliquent sur le RDD : les transformations et les actions. Les transformations sont caractérisées de « lazy » (à évaluation paresseuse) car elles ne s’exécuteront que si une action est réalisée en bout de chaîne. De plus, les RDD sont immutables, c’est-à-dire une transformation appliquée à un RDD ne va pas le modifier mais plutôt en créer un nouveau qui est enrichi de nouvelles informations correspondant à cette transformation. Une fois que vous avez défini toutes les transformations que vous voulez appliquer à votre donnée, il suffira d’appliquer une action pour lancer le calcul sur votre cluster ou CPU locaux (selon le SparkContext). Les actions sont terminales.

Communication au sein du cluster

Les workers établissent une communication bidirectionnelle avec le master : le worker se connecte au master pour ouvrir un canal dans un sens, puis le master se connecte au worker pour ouvrir un canal dans le sens inverse. Il est donc nécessaire que les différents nœuds du cluster puissent se joindre correctement (résolution DNS. . . ).
La communication entre les nœuds s’effectue avec le framework Akka. Les nœuds du cluster (master comme workers) exposent par ailleurs une interface Web permettant de surveiller l’état du cluster ainsi que l’avancement des traitements. Chaque nœud ouvre donc deux ports :
un port pour la communication interne : port 7077 par défaut pour le master, port aléatoire pour les workers;
un port pour l’interface Web : port 8080 par défaut pour le master, port 8081 par défaut pour les workers .

La génération des 2-itemsets fréquents

L’algorithme R-Apriori est plus rapide que YAFIM lors de la génération des 2-itemsets fréquents. De ce fait, nous avons utilisé l’approche de R-Apriori, mais avec une implémentation différente. à partir du RDD « Transactions » qui contient l’ensemble des transactions, nous allons y appliquer une transformation flatMap(.genPair()) qui génére des ensembles à 2 articles (2-Itemsets) à partir de l’intersection des articles fréquents avec chaque transaction.
Ces derniers (les 2-Itemsets) seront mis dans un RDD, qui sera appliqué une transformation mapToPair() pour transformer tous ces 2-itemsets à des paires clé – valeur sous la forme (2-itemset, 1). Ensuite, une transformation reduceByKey(+) sera utilisée pour agréger les données sous la forme (2-itemset, fréquence). Et enfin, la transformation filter(Count>= minCount) sera appliquée pour filtrer les paires qui ont une fréquence supérieure ou égale à la fréquence minimale fixée ; ce qui donne les 2-itemsets fréquents.

Apache Spark

Apache Spark est un framework permettant de faire du traitement sur de gros volumes de données, de manière distribuée (cluster computing). Il offre la possibilité de créer des tâches d’analyse de données qui peuvent fonctionner jusqu’à 100 fois plus vite en mémoire et 10 fois plus vite sur disque, que celles réalisées avec le traditionnel outil Hadoop MapReduce. Il a prouvé sa scalabilité jusqu’à 8000 nœuds. La propriété principale de Spark est le traitement des données en mémoire, mais elles peuvent être traitées sur disque.
Spark est né en 2009 dans l’université de Californie, et plus précisément dans le laboratoire AMP (Algorithms, Machines and People) de Berkeley, en partant du principe que :
d’une part, la RAM coûte de moins en moins cher et les serveurs en ont de plus à leur disposition; d’autre part, beaucoup de jeux de données dits « Big Data » ont une taille de l’ordre de 10 Go et ils tiennent donc en RAM.
Le projet a été adopté par la fondation Apache en juin 2013 et est devenu un « Top-Level Project » en février 2014. Il s’intègre parfaitement avec l’écosystème Hadoop (notamment HDFS), Cassandra, etc. Il est l’un des projets Apache les plus actifs avec pas moins de 450 contributeurs. De nos jours, il est l’une des technologies qui se démarque le plus dans le monde du big data, grâce à sa rapidité d’exécution, sa facilité d’utilisation et ses nombreuses librairies.
Des entreprises IT comme Cloudera, Pivotal, IBM, Intel et MapR ont déjà commencé à intégrer Spark dans leur distribution Hadoop. Databricks, une société fondée par certains développeurs de Spark, offre d’ores et déjà un support commercial pour ce logiciel. Yahoo et la NASA, entre autres, ont déjà commencé à l’utiliser pour leurs opérations quotidiennes de traitement de données. Spark est écrit en Scala. Mais il propose des librairies manipulables en Java, Scala et Python : Spark SQL (Java, Scala et Python) : pour requêter les RDDs en SQL. Spark Streaming (Java et Scala) : pour le traitement en continu de flux de données. MLlib (Java, Scala et Python) : pour faire du » machine learning « . GraphX (Scala) : apporte les outils pour explorer les graphes.

Table des matières

Introduction
1 La méthode A Priori
1.1 Présentation
1.2 Définitions, notations et concepts
1.3 Fonctionnement
1.3.1 La recherche des ensembles d’articles fréquents
1.3.2 La génération des règles d’association
1.4 Problèmes
2 Apache Spark
2.1 Présentation
2.2 Les concepts de base
2.2.1 Les RDD (Resilient Distributed Datasets)
2.2.2 Spark Context
2.3 Fonctionnement
2.3.1 Topologie
2.3.2 Communication au sein du cluster
3 Approches de parallélisation et d’optimisation avec Spark
3.1 YAFIM : A Parallel Frequent Itemset Mining Algorithm with Spark
3.1.1 Fonctionnement
3.1.2 Evaluation
3.2 R-Apriori : An Efficient Apriori based Algorithm on Spark
3.2.1 Fonctionnement
3.2.2 Evaluation
4 Notre Approche
4.1 Fonctionnement
4.1.1 La génération des 1-itemsets fréquents
4.1.2 La génération des 2-itemsets fréquents
4.1.3 La génération des k-itemsets fréquents avec k > 2
4.2 Evaluation
Conclusion
Bibliographie