Cours sur le Framework Hadoop et les fouille de données enjeux et pratique
Agenda
? Présentation de Talend
? Définition du Big Data ? Le framework Hadoop ? 3 thématiques
? Rapprochement des données
? Détection de fraude ? Clustering
? Les futurs outils de fouille de données sur Hadoop
Le domaine de Talend
? Talend propose des outils graphiques pour :
? L'intégration de données
? Le traitement des Big Data
? La qualité de données
? Le MDM
? L'intégration d'applications (ESB)
? La gestion des processus métier (BPM)
Le Studio de développement
? Open source ? Générateur de code ? Extensible
? Composants DI, DQ, BD, ESB
? Indicateurs DQ
Agenda
? Présentation de Talend
? Définition du Big Data
? Le framework Hadoop ? 3 thématiques
? Rapprochement des données
? Détection de fraude ? Clustering
? Les futurs outils de fouille de données sur Hadoop
Définition du Big Data
Définition encours d'élaboration en même temps que les techno évoluent
? Gartner : 3 V ou 5 V
? Intel : 300 TB de données générées par semaine
? Oracle : extraction de valeur des bases de données augmentées de sources de données non structurées
? Microsoft : ensembles de données complexes ? NIST: dépasse les capacités des systèmes actuels.
Google trend: “Big Data” associé à Hadoop, NoSQL, Google, IBM et Oracle.
Croissance exponentielle des données
En 2012, 90% des données ont été générées durant les 2 années précédentes.
Chaque jour de 2012, 2.5 Exaoctets de données sont créés.
Quelques chiffres
? Par jour
? 144.8 milliards d'Email.
? 340 millions tweets.
? 684 000 bits de contenu partagé sur Facebook.
? Par minute
? 72 heures (259,200 secondes) de video sont partagées sur YouTube.
? 2 millions de recherches sur Google.
? 34 000 “likes” des marques sur Facebook.
? 27 000 nouveaux posts sur Tumblr.
? 3 600 nouvelles photos sur Instagram.
? 571 nouveaux sites web
? 2.5 Petaoctects dans les bases de données Wal-Mart
? 40 To de données générées chaque secondes au LHC
? 25 Po de données stockées et analysées au LHC chaque année.
? 10 To produits par les capteurs des avions lors d'un vol pendant 30 minutes
? 1.25 To ce que peut contenir le cerveau humain
Plus encore sur
Une révolution technologique
En 2000, le stockage de 1Go coûtait moins de 1$.
=> Augmentation des capacités de stockage.
Le Cloud a a permis une généralisation du Big Data.
De nouvelles technologies sont apparues dès les années 2000 pour gérer la volumétrie et la variété des données : ? Hadoop HDFS
? Map Reduce
Le Marché du Big Data
? Un marché de 24 milliards de $ en 2016
? Taux de croissance annuel de 31.7%
? Entreprises ayant un projet Big Data
? En France : 10%
? En Allemagne : 18%
? Au UK : 33%
? Les technologies de pointe (Etude IDC) :
? Bases de données objets ou graphiques : 47%
? L'indexation de contenu : 38%
? Les bases de données en mémoire : 37%
Agenda
? Présentation de Talend ? Définition du Big Data
? Le framework Hadoop
? 3 thématiques
? Rapprochement des données
? Détection de fraude ? Clustering
? Les futurs outils de fouille de données sur Hadoop
La naissance d'Hadoop
? Quelques dates
? 2003 : “The Google File System”, Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung
? 2004 : “MapReduce: Simplified Data Processing on Large Clusters”, Jeffrey Dean et Sanjay Ghemawat
? 2005 : Naissance d'Hadoop chez Yahoo (HDFS et MapReduce),
Doug Cutting et Mike Cafarella
? 2006 : “Bigtable: A Distributed Storage System for Structured
Data”, Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber
Le framework Hadoop
?
? projet opensource (Fondation Apache) dédié au calcul distribué, fiable et scalable
– Hypothèse de départ : les machines ne sont pas fiables
– Hadoop la haute disponibilité au niveau applicatif (redondance des données entre machines, pertes de connexions, plantages de machines, )
? Modules
– HDFS : Hadoop Distributed File System (inspiré de GFS)
– MapReduce : système pour le traitement parallèle des gros volumes de données (inspiré de Google MapReduce)
– En version 2 : YARN : système de gestion et planification des ressources du cluster
Hadoop : un changement de paradigme
? Localité des Données
? Auparavant les données étaient déplacées dans une application pour être manipulées (SGBD, ETL, Applications )
? Désormais, les applications (sous forme MapReduce) sont déplacées vers les données
Le modèle MapReduce
? Un programme MapReduce est composé de 2 fonctions
? Map() divise les données pour traiter des sous-problèmes ? Reduce() collecte et aggrège les résultats des sous-problèmes
? Fonctionne avec des données sous forme de paires (clé, valeur)
? Map(k1,v1) ? list(k2,v2)
? Reduce(k2, list (v2)) ? list(v3)
Le modèle MapReduce
? Exemple avec le décompte de mots
Agenda
? Présentation de Talend ? Définition du Big Data ? Le framework Hadoop
? 3 thématiques
? Rapprochement des données
? Détection de fraude ? Clustering
? Les futurs outils de fouille de données sur Hadoop
? Processus permettant d'identifier les enregistrements concernant les mêmes objets
? 2 enregistrements R1 = {a} et R2 = {b}
i i
? Calcul du score
S = P(R1=R2) = ? w x p(a=b) avec w poids normalisés
i i i i i
? S = 1 => identité
S > T => similaires (T = seuil)
? Nécessité de comparer les enregistrements 2 à 2 ? MAIS si N enregistrements à comparer avec M enregistrements, alors N x M comparaisons
? Exemple : 1.000 nouveaux clients à comparer aux 10.000 clients référencés => 10.000.000 de comparaisons !!
? Alors que le nombre de clients déjà référencés dans les 1000 nouveaux est au max 1000 = min(N,M).
? => 9 999 000 comparaisons inutiles
? Optimisation en réduisant le nombre de comparaisons
? Stratégie de “blocking” partitionnement des données
? Exemple :
100 x blocs de 10 enregistrements en entrée à comparer à 100 blocs de 100 enregistrements.
? Nb comparaisons : 100 x (10 x 100) = 100 000
? Approche idéale pour Hadoop Map Reduce
Splitting Mapping
? Shuffle
? Reduce
Rapprochement avec Talend
? Cluster 9 noeuds (Cloudera CDH 4.5 avec Yarn)
Modèle quadratique dépend de la stratégie de “blocking” t ~ 16 + 1,6x10-5 N + 2,5x10-11 N2
Agenda
? Présentation de Talend ? Définition du Big Data ? Le framework Hadoop
? 3 thématiques
? Rapprochement des données
? Détection de fraude ? Clustering
? Les futurs outils de fouille de données sur Hadoop
? Loi de Benford
? Loi du 1er chiffre d ? {1,2, ,9}
? Quelle est la répartition de ce 1er chiffre ?
? Loi de Benford
? Loi du 1er chiffre d ? {1,2, ,9}
? Quelle est la répartition de ce 1er chiffre ?
?
? Loi de Benford
? Loi du 1er chiffre d ? {1,2, ,9}
? Quelle est la répartition de ce 1er chiffre ?
? Intérêt pour la détection de fraude ?
? Les nombres falsifiés suivent souvent une distribution uniforme
? Très simple à mettre en oeuvre : comparer la distribution du 1er chiffre avec la loi de Benford
? Utilisé sur des données de finance, comptabilité, socio-économiques, …
– Loi de Benford a un statut légal aux US
– Mise en évidence de fraude aux élections iraniennes en 2009
– Accord avec les données du génome, ou les publications scientifiques.
– Série télévisée Numb3rs (S2 Ep 15)
? Conditions d'application
? Avoir plusieurs ordres de grandeur (au moins 3)
Détection de fraude – Exemple 1
Détection de fraude – Exemple 2
Structure du fichier
Attention aux conditions:
? nombre de lignes = 360
? Ordres de grandeurs pas toujours respectés
? Biais dans les données
Détection de fraude sur données massives
? Utilisation de Hive ? Hive projet Apache initié par Facebook ? Langage de requêtage de type SQL
? Traduit les requêtes HiveQL en jobs map/reduce Hadoop.
Agenda
? Présentation de Talend ? Définition du Big Data ? Le framework Hadoop
? 3 thématiques
? Rapprochement des données
? Détection de fraude
? Clustering
? Les futurs outils de fouille de données sur Hadoop
? Algorithmes disponibles (basés sur Mahout)
? Canopy (souvent utilisé pour initialiser les clusters du k-means)
? K-means
? Fuzzy k-means ? Dirichlet
? Et plusieurs distances
? Euclidienne
? Manhattan
? Chebyshev
? Cosinus
? Mahout k-means en ligne de commande
? Chaque itération de l'algorithme génère un job mapreduce
? Initialisation des clusters du k-means en exécutant l'algorithme de Canopy
? Parallélisation de l'algorithme de canopy en 3 étapes
? Chaque Mapper calcule les centroïdes des canopies sur son jeu de données
? Les Reducers groupent les centroïdes des canopies pour former un ensemble de centroides finaux
? Chaque point (donnée) est rattaché à son canopy final
Référence (lecture vidéo Google) :
Cluster Computing for Web-Scale Data Processing (2008) Aaron Kimball
Agenda
? Présentation de Talend ? Définition du Big Data ? Le framework Hadoop ? 3 thématiques
? Rapprochement des données
? Détection de fraude ? Clustering
? Les futurs outils de fouille de données sur Hadoop
Mahout
? Mahout ? Librairie d'algorithmes d'apprentissage automatique ? 3 familles d'algorithmes reposant sur Hadoop
? Clustering
? Classification
? Filtrage collaboratif (Recommandation)
? Contient d'autres algorithmes non distribués
Mahout - fondation
? Mahout
? fondé par Isabel Drost, Grant Ingersoll, Karl Witten
? En 2008 comme sous projet de Lucene (moteur de recherche) + Taste (Sean Owen)
? Devient un projet Apache à part entière en 2010
Mahout - Classification
? Classification avec Mahout
? Classification naïve bayesienne
? Modèle de Markov caché (HMM)
? Régression logistique
? Forêts d'arbres décisionnels (random forests)
? La classification avec Mahout devient intéressante au-delà de 1 à 10 millions de lignes
? Là où les autres approches ne sont plus scalables.
Mahout - Recommandation
? Recommandation (filtrage collaboratif)
? filtrage collaboratif utilisateurs
? le filtrage collaboratif objets
? Plusieurs lectures/écritures disque
Mahout – les limites
? Mahout a été pensé pour fonctionner avec Map Reduce v1.
? Traitement batch des données
? les algorithmes d'apprentissage sont coûteux en IO
? La conversion des calculs matriciels en programmes MapReduce n'est pas si efficace
? A la limite, Mahout serait bon pour l'apprentissage, mais la recommandation, les prédictions ou la classification doivent être faite en “temps réel”
Architecture Lambda
Nathan Marz de Twitter définit une architecture générique pour être robuste face aux
? erreurs humaines
? problèmes matériels
Permettant des requêtes ad-hoc, une scalabilité en ajoutant des machines
L'architecture hadoop 2 - YARN
? Amélioration de la scalabilité
? Hadoop1: taille max du cluster ~ 5000 noeuds
? Nombre max de tâches ~ 40 000
? Haute disponibilité
? Meilleure gestion des ressources du cluster
? Mauvaise répartition des tâches Mappers et Reducer
? Support d'autres modèles de programmation que MapReduce (parcours de graphe, MPI)
? tout n'est pas adapté à MapReduce
? YARN : système de gestion d'applications distribuées
YARN en tant qu'OS distribué
Les futurs outils de fouille de données sur Hadoop - Spark
? Spark (projet Apache)
? Tourne sur un cluster
Hadoop 2
? 100x plus rapide que Hadoop
(en mémoire)
? Mllib
? K-means
? Régression linéaire
? Régression logistique
? Classification naïve bayesienne
? Descente de gradient stochastique
Mahout – renaissance ?
? Mahout va être réécrit pour supporter
? Spark
? Ainsi que H20
– Moteur opensource de machine learning et math.
– Travaille principalement en mémoire (distributed in-memory Key/Value store)
– Swap sur HDFS si besoin
Les futurs outils de fouille de données sur Hadoop - Oryx
? Nouveau projet Oryx de Cloudera
?
? S'appuyant sur l'architecture lambda
Conclusion
? Futurs travaux
? sur le rapprochement
– Mesure de la qualité de l'algorithme (F-score)
– Comparaison avec algorithme MFB du LIPN
– Version distribuée de l'algorithme MFB
? Sur la détection de fraude
– Alerter l'utilisateur si déviation du modèle trop élevée
? Sur l'apprentissage
– Développer des composants pour la classification et la recommandation
– Supporter les nouveaux frameworks Big Data