content top

Implémenter MapReduce avec TPL (Task Parallel Library)

Implémenter MapReduce avec TPL (Task Parallel Library)

 

Dans cet article je vous propose une implémentation de MapReduce avec TPL (Task Parallel Library) du framework .NET 4.0. Si vous ne connaissez pas MapReduce, vous avez toujours la possibilité de consulter mon article (partie 1 et partie 2) dédié à sa présentation et à son mode opératoire.

Read More

L’algorithme FP-Growth – Identification des motifs fréquents (3/3)

L’algorithme FP-Growth – Identification des motifs fréquents (3/3)

 

Présentation :

Cet article constitue la troisième et dernière partie de la serie consacrée à l’algorithme FP-Growth. Dans l’article précédent  j’ai introduit la construction d’une structure FP-tree, structure utilisée par l’algorithme FP-Growth pour stocker les informations concernant tous les motifs (itemsets) fréquents dans une base de transactions.

Dans cet article je vais présenter la manière dont sont identifiés les itemsets fréquents de la base de transactions à partir de la structure FP-tree construite à la suite du parcours des éléments de la bases de transactions. Le but étant de générer à partir de ces ensembles d’itemsets fréquents les règles d’associations.

Read More

L’algorithme FP-Growth – Construction du FP-tree (2/3)

L’algorithme FP-Growth – Construction du FP-tree (2/3)

 

Présentation:

Cet article est le deuxième article de la série concernant l’algorithme FP-Growth. Dans le premier article j’ai présenté l’algorithme, son fonctionnement global ainsi que ses avantages et inconvénients.

Dans cet article je vais introduire la construction d’une structure FP-tree. Pour rappel, l’algorithme FP-Growth utilise une structure de donnée appelée Frquent Pattern tree. Il permet de trouver les itemsets fréquents dans une base de transactions. Grace à la structure FP-tree on conserve l’ensemble des éléments fréquents de la base des transactions dans une structure compacte. Ainsi il n’est plus nécessaire de devoir parcourir la base de transactions. De plus, ces éléments se retrouvent triés ce qui accélère la recherche des règles d’association.

Read More

L’algorithme FP-Growth – Les bases (1/3)

L’algorithme FP-Growth – Les bases (1/3)

Présentation :

Nous avons vu que l’algorihme Apriori effectue plusieurs passes (scans) de la base de données. Ceci peut être très pénalisant lorsqu’il s’agit de données voluminineuses. Afn d’éviter les parcours répétés de la base de données, Han et al. [1] ont proposé  une méthode différente des approches par niveaux permettant d’extraire des itemsets fréequents sans génération de candidats.

Cette méthode s’appelle FP-growth (Frequent Pattern growth). Elle consiste d’abord à compresser la base de données en une structure compacte appelée FP-tree (Frequent Pattern tree), puis à diviser la base de donnees ainsi compressée en sous projections de la base de données appelées bases conditionnelles.

Chacune de ces projections est associée à un item fréquent. L’extraction des itemsets fréquents se fera sur chacune des projections séparement.

L’algorithme FP-growth apporte ainsi une solution au problème de la fouille de motifs fréquents dans une grande base de données transactionnelle. En stockant l’ensemble des éléments fréquents de la base de transactions dans une structure compacte, on supprimer la nécessité de devoir scanner de façon répétée la base de transactions. De plus, en triant les éléments dans la structure compacte, on accélère la recherche des motifs.

Read More

Application de K-Means à la définition du nombre de VM optimal dans un Cloud

Application de K-Means à la définition du nombre de VM optimal dans un Cloud

Résumé

Ce papier présente les premiers éléments de définition d’un algorithme permettant de  déterminer le nombre optimal de machines virtuelles (VM – Virtual Machines) lors de  l’exécution des applications de fouille de données dans un environnement Cloud. L’efficacité  de traitement des problèmes de fouille de données requiert d’obtenir au préalable un  partitionnement intelligent de données par clustering de manière à effectuer le plus  indépendamment que possible les traitements des fragments de données à cohérence sémantique forte.

Nous pensons que l’exécution sur les données distribuées dans le Cloud d’une variante parallèle de l’algorithme de clustering h-means adaptée en phase de présélection du processus PMML [18] pour (Predictive Model Markup Language) permettrait d’assurer un partitionnement optimal des données et de déterminer un nombre de VM optimal avant l’exécution de l’application.

Mots-clés : Cloud computing, h-means, classification, parallélisme dans des grilles, partitionnement de données, fouille de données.

Read More

MapReduce – 2ème Partie

MapReduce – 2ème Partie

Ceci est la deuxième partie de l’article autour de MapReduce. La première partie peut être consultée ici.

Un mot à propos des ‘Workers’ MapReduce

Comme évoqué, un ‘Worker’ correspond à une ‘unité de travail’. Cette unité possède trois états:

  1. idle
  2. in-progress
  3. completed
  • L’état idle indique qu’un worker est disponible pour une nouvelle planification de traitement.
  • L’état completed indique la fin d’un traitement, le worker informe le Master de la taille, de la localisation de ses fichiers intermédiaires.
  • L’état in-progress indique qu’un traitement est toujours en cours d’éxécution. (Continuer la lecture…)

Read More

MapReduce – 1ère Partie

MapReduce – 1ère Partie

Qu’est ce que c’est ?

MapReduce est un framework de calcul distribué sur de gros volumes de données. Il s’agit d’un modèle de programmation parallèle dont les combinators Map et Reduce sont inspirés du langage fonctionnel Lisp.

MapReduce a été développé dans Google comme mécanisme pour traiter des gros volumes de données en environnement distribué. Il permet de répartir la charge sur un grand nombre de serveurs et gère entièrement, d’une manière transparente, le cluster, la distribution de données, la répartition de la charge et la tolérance aux pannes.

MapReduce apporte une abstraction quasi-totale de la couche matérielle de l’infrastructure. La librairie MapReduce de Google existe dans plusieurs langages de programmation dont C++, C#, Erlang, Java, Python, Ruby…D’autres librairies implémentent bien ce concept : par exemple Hadoop de la fondation Apache et Elastic de chez Amazon …

Ces mécanismes dont je présente les principes, dans cette conférence, peuvent être appliqués pour exécuter les algorithmes de fouille de données en mode PaaS (Platform as a Service) dans un Cloud privé.

Qui utilise MapReduce ?

Plusieurs grands acteurs du monde web comme Google, Yahoo, Facebook et bien d’autres utilisent MapReduce. En effet, parmi les diiféentes utilisation de Mapreduce par ces grands acteurs on trouve que Google l’utilise pour construire les index de Google Search, Yahoo l’utilise pour la detection de spam, facebook l’utilise à des fins de Data Mining.

Egalement, MapReduce est utilisé par les laboratoires de Recherches à travers le monde pour faire par exemple de l’analyse d’images astronomique, de la bioinformatique, de la simulation métrologique, de l’Apprentissage Machine (Machine Learning), pour des statistiques, etc…(Continuer la lecture…)

Read More

Slides présentation MapReduce

Au cours du séminaire qui a lieu le 17 mars 2011 j’ai présenté le model de programmation MapReduce.

Les slides de cette présentation peuvent être téléchargées au format pdf  ici.

Read More

L’algorithme A-priori

L’algorithme A-priori

Définitions :

L’algorithme A-priori1 est un algorithme d’exploration de données conçu en 1994, par Rakesh Agrawal et Ramakrishnan Sikrant, dans le domaine de l’apprentissage des règles d’association. Il sert à reconnaître des propriétés qui reviennent fréquemment dans un ensemble de données et d’en déduire une catégorisation.

A-Priori détermine les règles d’association présentes dans un jeu de données, pour un seuil de support et un seuil de confiance fixés. Ces deux valeurs peuvent être fixées arbitrairement par l’utilisateur. (Continuer la lecture…)

Read More

2e SéRI 2010-2011

Le 2ème Séminaire en Recherche Informatique aura lieu le 17 mars 2011 à l’EISTI, Amphi-Turing à  Cergy-Pontoise entre 14h et 17h30;

Au cours de ce séminaire plusieurs sujet seront traités autour du Cloud Computing, comme :

  1. Architectures et performances des solutions Cloud Open Source
  2. Mise en oeuvre du protocole OpenFlow dans une grille
  3. MapReduce et exécution des algorithmes de fouille de données dans un Cloud privé

le programme détaillé peut être consulté ici.

Read More
content top