17/02/2025

Master PR0 Industrie 4,0: FSM

Chapitre 1: Introduction à la fouille de

Big Data et science des données données
Support de cours

AU 2024-2025

1 2

Introduction à la fouille de données

Plan
a. Pourquoi la Fouille de donnée?
b. Métaphore
c. Evolution des sciences
d. Qu’est ce que la fouille de données?
e. Des données aux connaissances
f. Exemples d’application concrètes
g. Les données
h. Fonctionnalités du Data Mining
i. Confluence de plusieurs Disciplines
j. Logiciels libres

3 4

1
 17/02/2025

Introduction Introduction
Motivation: Le besoin crée l’invention Motivation: Le besoin crée l’invention

Problème de l’explosion de données Problème de l’explosion de données

Les outils de collecte automatique des données et les bases de données

conduisent à d’énormes masses de données stockées dans des • Les données sont collectées et stockées rapidement (GB/heures)
- Télescopes,
entrepôts
- Puces à ADN générant des expressions de gènes,
- Entrepôts du Web
-Simulations générant de téra-octets de données.
- Réseaux sociaux et hébergement de documents : • Submergés par les données, manque de connaissance !

- e-commerce Achats dans les supermarchés

- Transactions de cartes bancaires

5 6

Introduction Introduction
Motivation: Le besoin crée l’invention Motivation: Le besoin crée l’invention

Problème de l’explosion de données: Développement des TICs Problème de l’explosion de données: Développement des TICs

7 8

2
 17/02/2025

Introduction Introduction
Motivation: Le besoin crée l’invention Motivation: Le besoin crée l’invention
Métaphore
Problème de l’explosion de données: Développement des TICs

•Trop de données...
– Paradoxe : trop données mais pas assez d’informations

• Difficulté d’accès à l’information…

– Trop de données tue …l’information

• Trop de pistes à explorer

9 10

Evolution des sciences

Evolution de la technologie des bases de données
• Avant 1600 : science empirique
• 1600-1950 : science théorique •1970… : Bases de données relationnelles

• Années 50 - Années 90 : «Computational science» •1980… : modèles de données avancé

- Depuis plus de 50 ans, beaucoup de disciplines se sont développées • 1990 : entrepôts de données, …

- Simulation : trouver des modèles proches de la réalité

• 1990 - Aujourd’hui : «data science»
- Données omniprésentes
- capacité à gérer et stocker des volumes gigantesques.
- Internet
Solution: Data warehousing et data mining est devenu un challenge majeur
!!!

11 12

3
 17/02/2025

Fouille de données: Définition

Ce qu’est le Data Mining
Pourquoi maintenant ? • Terme récent (1990) représentant un mélange d’idées et d’outils provenant de
la Statistique, l’Intelligence Artificielle et l’Informatique.
– Limites de l’approche humaine & Techniques traditionnelles ne sont pas
• La définition exacte reste peu claire et les terminologies associées au Data-
adaptées
Mining sont encore floues.
Requêtes traditionnelles (SQL) impossibles : « Rechercher tous les
Une définition suivant un critère égocentré :
enregistrements indiquant une fraude »
Le data-mining est un processus de découverte de règle, relations, corrélations
– Solutions et compétences en Fouille récentes disponibles fournir de
et/ou dépendances à travers une grande quantité de données, grâce à des
meilleurs services, s’adapter aux clients
méthodes statistiques, mathématiques et de reconnaissances de formes.
– Les données sont produites électroniquement et archivées
Autres définitions :
– Le contexte est ultra-concurrentiel : Industriels, médicaux, marketing, etc.
•Data mining :
– Plateformes de calculs disponibles à bas prix
- Un processus d’extractions automatique d’informations prédictives à partir de
grandes bases de données.

13 14

Fouille de données: Définition Fouille de données: Définition

Ce qu’est le Data Mining Ce qu’est le Data Mining
• Data mining : • Autres appellations:
– Extraction d’informations intéressantes (implicites, et – ECD (Extraction de Connaissances à partir de Données)
potentiellement utiles) à partir de grandes bases de données.
– KDD (Knowledge Discovery from Databases)
• Le datamining est l’ensemble des:
– Analyse de données/patterns, business intelligence, fouille de
– Algorithmes et méthodes données, etc …
• Destinés à l’exploration et l’analyse
• De grandes quantités de données
• En vue de détecter des règles, des tendances inconnues ou
cachées, des structures particulières restituant de façon concise
l’essentiel de l’information utile
• … pour l’aide à la décision

15 16

4
 17/02/2025

Fouille de données: les raisons du développement Le processus KDD

pourquoi ça s’est développé ?
• Intérêt économique
• Technologie de l’information : faible coût de stockage de données, saisie
automatique de transaction (code bar, click, données de localisation GPS, internet) •

• Augmentation de la puissance de calculs des ordinateurs

⇒ Extraire de la connaissance à partir de grandes bases de données devient possible ▶ Bases de données relationnelles.
▶ Entrepôt de données
▶ Base de données transactionnelles.
▶ Données de type document
▶ Données sous forme de graphe
▶ Base de données multimédia

17 18

Le processus KDD
Le processus KDD
1-«Focussing»
2- « Pré-traitement »

• Comprendre l’application • Intégration des données à partir de différentes sources

• Conversion des noms d’attributs (CNo  CustomerNumber)
• Définir l’objectif KDD • Utilisation de la connaissance du domaine
• Ex. : Etablir des «profils de consommateurs»
• «Complétion»
• Acquisition des données • Le cas des valeurs manquantes
• Ex. : Bases de données des factures • le cas du bruits

• Gestion des données • Le pré-traitement des données est souvent la tâche la plus coûteuse dans le
• Système de fichiers ou SGBD ? processus KDD!
• Sélection des données pertinentes
Ex. : considérer les 100 000 clients les plus importants et tous
leurs appels sur l’année 2019

19 20

5
 17/02/2025

Le processus KDD Le processus KDD

3-Transformation 5-Fouille de données
Discrétisation des attributs numériques
• l’application d’algorithmes efficaces qui identifient les motifs contenus dans une
• Indépendamment de la tâche de fouille de données
base de données
• Ex. : partitionner le domaine des attributs en des intervalles de même • Ensemble de techniques d'exploration des données permettant d'extraire d'une
base de données des connaissances sous la forme de modèles de description afin de :
longueur.
• Spécifique de la tâche de fouille de données - décrire le comportement actuel des données et/ou
- prédire le comportement futur des données
• Partitionner en des intervalles qui maximisent le gain d’information par
• Les différentes tâches de fouille :
rapport à la classe
• Agrégation d’un ensembles d’attributs
• Ex. : à partir d’appels
• nb d’appels par jour, semaine...
•Généralisation des données
•Normalisation des données
• Autres tâches : régression, détection d’outlier, etc

21 22

Le processus KDD Le processus KDD

6- Evaluation
5-Fouille de données
• Présentation des motifs découverts avec une visualisation appropriée
• Applications • Evaluation des motifs par l’utilisateur
• Clustering • Si l’évaluation n’est pas satisfaisante, alors relancer la fouille avec :
- Segmentation, structuration d’un ensemble de documents «web», • des paramètres différents
découvertes de communautés • d’autres méthodes
• Classification : • d’autres données
- prédiction de la fonction d’une protéine, accorder un crédit, interpréter des • Si l’évaluation est positive :
images en astronomie, etc. • Intégrer les connaissances découvertes dans une base de connaissance
• Règles d’association : • Utiliser ces connaissances dans les futures processus KDD
- mise en rayon, promotion, améliorer la structure d’un site web ...

23 24

6
 17/02/2025

Les données
Data Mining: Données, information, connaissance  Dans le domaine de la gestion et de la finance, de très nombreuses données
(informations), de types très variés, peuvent être relevées:
• nombre de ventes par mois d’un commercial,
• prix d’achat d’une matière première au cours du temps,
• bénéfices d’une société sur plusieurs exercices,
• préférences d’achat de consommateurs,
• avis de clients sur des produits à commercialiser,
• indicateurs de performance de plusieurs entreprises, à un instant T ou au cours du
temps...
 Les données brutes sont en général peu aisées d’interprétation directe: ce sont de
"gros" tableaux remplis de "chiffres"....
C’est pour ces besoins que sont mis en œuvre les outils d’analyse de données

Les données: tableau individu*variables

Les données
Quelles données ?
Population: groupe ou ensemble d’individus que l’on analyse.
Sondage: étude d’une partie seulement d’une population appelée échantillon.
Variables: ensemble de caractéristiques d’une population
— quantitatives : nombres sur lesquels les opérations usuelles (somme,
moyenne,...) ont un sens ; elles peuvent être discrètes ou continues;
— qualitatives : appartenance à une catégorie donnée ; elles peuvent être
nominales ou ordinales quand les catégories sont ordonnées
- Les modalités d’une variable sont l’ensemble des valeurs qu’elle prend dans les
données ex : les modalité de notes sont {0, 1, 2, · · · , 20} les modalités de couleur
sont {bleu,vert,noir,...}

7
 17/02/2025

Les données: tableau individu*variables

Exemples: tableau individu*variables
Les données ? Les données peuvent être vues comme une collection d’objets
(enregistrements) et leurs attributs.
▶ Un attribut est une propriété et ou une caractéristique de l’objet.
▶ Un ensemble d’attributs décrit un objet.

Attribut - valeur
▶ La valeur d’un attribut est un nombre ou
un symbole.
▶ Ne pas confondre attribut et valeur

Les données: tableau individu*variables

Les données: tableau individu*variables
Exemple1: la température en France Contexte température moyenne mois
par mois dans 25 villes de France.
Les données brutes sont difficiles à interpréter

8
 17/02/2025

But et méthode de l’analyse de données

Les données : exemples concrets
- de synthétiser, structurer l’information contenue dans des données
multidimensionnelles (n individus, p variables). • Sciences de la vie

Trois groupes de méthodes : - médecine : patients et maladies

- Méthode de régression linéaire: prédire la valeur future d’un attribut en fonction - génomique : gènes, patients,

d’autres attributs. • Marketing

- Méthodes de segmentation : former des groupes homogènes à l’intérieur d’une -fichiers clients

population. -traces d’usage (site web, communication mobile)

- Méthodes factorielles : réduire le nombre de variables en les résumant par un petit -Achats

nombre de composantes synthétiques. • Industrie

- senseurs : température, vibration

34

Outils utilisés Data Mining: Données, information, connaissance

Statistiques élémentaires on calcule des moyennes, variances corrélations... Exemple: Tester le pourcentage des clients qui consultent leurs comptes bancaires
sur le web
Statistiques inférentielles on utilisera quelques tests statistiques.
Matrices les tableaux de données sont vus comme des matrices : opérations
élémentaires, vecteurs propres...
Espaces métriques les données sont aussi vues comme des nuages de points en
grande dimension : produits scalaires, …

Données?
Information?
Connaissance?

36

9
 17/02/2025

Data Mining : centre du processus KDD Applications KDD

• L’analyse d’une BD de transactions d’un supermarché permet d’étudier
le comportement des clients :
– réorganiser les rayons/ segmentation du marché
– Ajuster les promotions
– Associations/co-relations entre ventes de produits
• L’analyse de données médicales :
– Support pour la recherche
• L’analyse de données financières :
– Prédire l’évolution des actions
– Organismes de crédit (dresser des profils de clients)
à quoi cela sert ?
• Les supporters achètent de la bière le samedi et de l’aspirine le dimanche • Domaine d’astronomie
• Regrouper ensemble des documents retournés par un moteur de recherche en
• Autres Applications
fonction de leur contenu
– Text mining : emails, documents Web.
– des algorithmes de data mining pour réorganiser leurs sites WEB
37 38
afin de faciliter la navigation.

Applications KDD: Astronomie

Applications KDD : Commerce électronique
[Fayad et al 1996]
• Architecture

• Méthode de classification : arbre de décision

• Evaluation :
- beaucoup plus rapide qu’une classification manuelle
- Classifie aussi des objets célestes très petits

39 40

10
 17/02/2025

Applications KDD : Marketing Applications KDD : puces ADN

[Piatetsky-Shapiro et al 2000]

• Customer
• But : partitionner les consommateurs par rapport à leurs achats
• Motivation :
- product packages
- établir une nouvelle politique tarifaire

• Problème : 50% des clients de Dell achètent leurs machines à travers le site
Web. Mais seulement 0.5% des visiteurs du site deviennent clients.

• Solution : Stocker les séquences de clicks des visiteurs, analyser les

caractéristiques des acheteurs et lors de la visite d’un client potentiel, adapter le
contenu du site pour maximiser la probabilité d’un achat.

41 42

Fonctionnalités du Data Mining

Fonctionnalités du Data Mining
On distingue deux grandes familles de tâches réalisées en datamining

– Description : consiste à trouver les caractéristiques générales relatives

aux données fouillées
– Prédiction : consiste à faire de l’inférence à partir des données
43
actuelles pour prédire des évolutions futures
44

11
 17/02/2025

Fonctionnalités du Data Mining Fonctionnalités du Data Mining

Techniques descriptives Prédiction

• Vise à extrapoler de nouvelles informations à partir d’informations

• Regroupement (ou segmentation, ou clustering) déjà présentes

• Recherche d’associations, de corrélations • Il y a une variable cible à prédire

• Recherche de séquences similaires

45 46

Fonctionnalités du Data Mining

Fonctionnalités du Data Mining
Prédiction Techniques prédictives
Exemple : va-t-on faire du kite-surf ?

Classification
– Arbres de décision
– Classification bayésienne
– Réseaux neuronaux
– Méthodes SVM (support vector machine)
– Régression
– …

Va-t-on jouer s’il y a du soleil, beaucoup d’humidité et pas de vent ?

47 48

12
 17/02/2025

Fonctionnalités du Data Mining

Remarques:
Data Mining: Confluence de plusieurs Disciplines
Extraction de connaissances
Un déroulement non linéaire
▶ On constate souvent à l’étape de validation que : IA Statistique
▶ les performances obtenues sont insuffisantes.
▶ les utilisateurs du domaine jugent l’information inexploitable.
▶ ...
▶ Il faut donc : Data Mining Visualisation
Apprentissage
▶ Choisir une autre méthode de fouille.
▶ Remettre en cause l’étape de transformation.
▶ Enrichir les données
Autres
▶ Dans un projet d’ECD, le temps passé à l’étape de fouille de données ne Reconnaissance des formes Disciplines
représente souvent que 40% du temps.

49 50

Logiciels libres

-R
-Weka ;
- RapidMiner ;
- Orange ;
- SIPINA/Tanagra. Chapitre 2: Modèle de règles
d’association
dans les bases de données

51 52

13
 17/02/2025

Règles d’association
La règle utile contenant des informations de qualité qui peuvent être mises en
L’idée principale: la recherche des régularités dans les BD pratique
Objectifs : Exemples :
Transcrire la connaissance sous forme de règle d’association - le samedi, les clients des épiceries achètent en même temps de la bière et des
Utiles : Aide à la décision couches
Efficaces : Algorithmes de recherche - SI achat de riz + vin blanc ALORS achat de poisson (avec une grande probabilité)
Utilité des règles et exemple  Résultats inexplicables difficiles à situer et donc à expliquer
- Dans une base de données découvrir des règles de la forme: Exemple :
“95% des étudiants qui ont suivi un cours de géographie et un cours d’histoire lors de l'ouverture d'une quincaillerie, parmi les articles les plus vendus on trouve
économique ont également suivi un cours de droit” les abattants de toilette.
Application typique:
- Détection de corrélations entre descripteurs dans des ensembles de données
 Analyser les transactions d’achats des utilisateurs pour dégager les habitudes
Exemple:
Découverte d’associations et de corrélations entre les articles achetés par les d’achat des clients
- Disposition des produits dans le magasin
clients en analysant les achats effectués (panier)
- Quels produits mettre en promotion, gestion de stock, …

 Très utile pour développer des stratégies de Marketing

53 54

Approche applicable dans d’autres domaines Exemple : Analyse du panier de la ménagère

•Cartes de crédit, e-commerce, …
•Services des compagnies de télécommunication Découverte d’associations et de corrélations entre les articles achetés par les clients
en analysant les achats effectués (panier)
•Services bancaires
•Traitements médicaux
 Les serveurs Web stockent les sessions de visite des internautes
- IP, navigateur, pages visitées, ordre de la visite, durée, ...

Etant donnée :
•Une base de données de transactions de clients, où chaque transaction est
représentée par un ensemble d’articles -set of items- (ex., produits)
Trouver :
55
•Groupes d’articles (itemset) achetés fréquemment (ensemble) 56

14
 17/02/2025

Type de données traitées

Type de données traitées
Données de transaction
 Tableau individus x variables Tableau binaire 0/1
Analyse des tickets de caisse

Commentaires:
>> Une observation = Un caddie
>> Ne tenir compte que de la présence des
produits (pas de leur quantité)
>> Nombre variable de produits dans un
caddie
>> La liste des produits est immense !  On cherche des relations entre les mots d'un corpus sous forme de règles :
si les mots x1; : : : ; xm apparaissent dans un texte alors les mots xm+1; : : : ; xn
apparaissent aussi dans le texte
Autre représentation des données de transactions

Selon la granularité choisie, le nombre de colonnes peut

être immense. 57 58

Données transactionnelles
Données transactionnelles
Exemple1:
Notation ou formalisation du problème
Etant donnés :
(1) une liste d’items I(Ex: item = produit)
(2) une base D de transactions où chaque transaction T est un ensemble d’items

• I = {I1, I2, …, In} désigne un ensemble d’objets

ensemble de produits (ex. {p1,p3})
• D = {T1, T2, …, Tm} est un ensemble de transactions tel que
• On note par k-ensemble tout ensemble de taille k (contenant k objets)
3-itemset : {Café, Moutarde, Saucisse}
.
• Une transaction T est dite contenir un ensemble
• La fréquence d’un ensemble A est le nombre de transactions dans D contenant A

59 60

15
 17/02/2025

Règles d’association pour le web usage mining Recherche de règles d’association

Formats de représentation des règles d’association de la forme :
motifs de la forme : Corps  Tête
Règles d’association dans les Transactions Web Exemple:
- Découvrir les affinités parmi les ensembles de page Web à travers les sessions couches =>bière [0.5%, 60%]
d’un utilisateur (support et confiance sont des mesures d’intérêt définies par l’utilisateur)
- Exemple: achète:couches =>achète:bière [0.5%, 60%]
60% des clients qui ont accédé /products/, ont aussi accédé achète(x, “couches”) achète(x, “bière”)
/products/software/webminer.html

•“SI achète couches ALORS achète bière dans 60% de cas. Les couches et la bière
sont tous deux achetés dans 0.5% des transactions de la base de données."

61 62

Recherche de règles d’association Critères d’évaluation des règles d’association

Pour mesurer la qualité d’une règle d’association, on va utiliser deux indices:
Evaluation des règles d’association
Support et confiance

“SI achète couche, ALORS achète bière,

dans 60% de cas, dans 0.5% de la base"

R1 : Si p1 alors p2

1:
2:
3:
4:
RQ:« Bonne » règle = règle avec un support et une confiance élevée
63 64

16
 17/02/2025

Exemple:
Soit A={I1,I2}, B={I3} Constructions des règles d’association
Schéma algorithmique de base
Règle: A=>B?

La plupart des approches utilise le même schéma algorithmique

- Pour construire les règles d ’association, le support de tous les itemsets fréquents
dans la base doit être calculé
- L ’algorithme procède en deux phases :
1) Génération de tous les ensembles fréquents
2) Génération des règles d ’association

65 66

Constructions des règles d’association

Constructions des règles d’association
Vers un algorithme générique
But : minimiser les candidats
L’idée est surtout de contrôler (limiter) le nombre de règles produites

Démarche: Construction en deux temps

L’algorithme APRIORI

Principe : générer seulement les candidats pour lesquels tous les sous-ensembles
ont été déterminés fréquents
- Génération des candidats réalisée avant et de manière séparée de l'étape de
comptage

67 68

17
 17/02/2025

Phase 1: Algorithme Apriori

Phase 1: Algorithme Apriori Extraction des itemsets fréquents
Exemple:
Données

Il s’agit de parcourir un treillis et de calculer les supports associés à chaque

combinaison

70

Propriétés des ensembles fréquents

Propriété 1 : support pour les sous- Propriétés des ensembles fréquents
ensembles
Si A ⊆ B pour les itemsets A, B alors
supp(A) >= supp(B) car toutes les
transactions dans D qui supportent
B supportent aussi nécessairement A.
A={Café, Moutarde}, B ={Café, Moutarde,
Saucisse}
Propriété 2 :
les sous-ensembles d’ensembles
fréquents sont fréquents
Exemple:
Donne la représentation la plus
Phase élagage: compacte possible de la liste des
Itemset fréquent : itemset dont le itemsets. Ex. si on sait que {p1,p2,p3} est
support>= sup_min fréquent, on sait que {p1,p2}, {p1,p3} et
{p2,p3} le sont également (mais on ne
connaît pas leur support)
Démonstration:

71 72

18
 17/02/2025

Propriétés des ensembles fréquents

Exemple: Extraction des itemsets fréquents

Min_sup=2/9 (min_freq=2)

73

19
 10/03/2025

BD Nosql

Introduction
Depuis les années 70, la BD relationnelle était l'incontournable référence pour gérer les
données d'un système d'information.
Comment gérer une énorme base de données et comment l'interroger efficacement ?
 Ces questions, on se les pose dès que le volume devient ingérable et que répondre à
de simples requêtes prend des heures.
Oubliez les SGBD traditionnels, ils peinent à passer à l'échelle ! Vous devez être
capable de choisir la bonne solution parmi les dizaines qui s'offrent à vous.

- "Not Only SQL". Cette approche propose de relâcher certaines contraintes lourdes du
relationnel pour favoriser la distribution

1
 10/03/2025

-Découvrir l'univers du NoSQL.

-Découvrir des solutions NoSQL extrêmement populaires :
- Redis, MongoDb et ElasticSearch.
 A stocker et à réaliser des requêtes sur les données tout en assurant le passage à
l'échelle.

-IL est préférable d'avoir un langage de haut niveau pour interroger les données plutôt que
tout exprimer en Map/Reduce

- le NoSQL est à la fois une autre manière d'interroger les données, mais aussi de les
stocker.

différentes familles de bases NoSQL existent : Clé/Valeur, colonnes, documents, graphes.

Les clés-valeurs

Un système clé-valeur agit comme une énorme table de hachage distribuée sur le réseau
La clé identifie la donnée de manière unique et permet de la gérer. La valeur contient
n'importe quel type de données.

Stockage Clé/Valeur

2
 10/03/2025

Qui s'intéresse à des fonctionnalités aussi simples ?

Redis (VMWare) : Vodafone, Trip Advisor, Nokia, Samsung, Docker

Memcached (Danga) : LiveJournal, Wikipédia, Flickr, Wordpress
Azure Cosmos DB (Microsoft) : Real Madrid, Orange tribes, MSN, LG, Schneider
Electric
SimpleDB (Amazon)
Quels types d'applications pourraient correspondre à cette solution ?
- Détection de fraude en temps réel,
- e-commerce,
- gestion de cache,
- transactions rapides,
-fichiers de logs,
- chat.

Des lignes vers les colonnes

Les données sont représentées en ligne, représentant l'ensemble des attributs.

Le stockage orienté colonne change ce paradigme en se focalisant sur chaque attribut et
en les distribuant.
 Il est alors possible de focaliser les requêtes sur une ou plusieurs colonnes, sans avoir à
traiter les informations inutiles (les autres colonnes).

3
 10/03/2025

Qui fait de l'orienté-colonnes ?

- BigTable (Google)
- HBase (Apache Hadoop)
- Spark SQL (Apache)
- Elasticsearch (elastic) -> moteur de recherche

Exemples d'applications :
-Comptage (vote en ligne, compteur, e etc),
-recherche de produits dans une catégorie.

La gestion de documents

Solution: Les bases orientées documents ressemblent sans doute le plus à ce que l'on peut
faire dans une base de données classique pour des requêtes complexes.

Le but : de ce stockage est de manipuler des documents contenant des informations avec
une structure complexe (types, listes, imbrications). Il repose sur le principe du clé/valeur,
mais avec une extension sur les champs qui composent ce document.

Stockage orienté document

4
 10/03/2025

Avantage

Approche structurée de chaque valeur, formant ainsi un document.

Solutions proposent des langages d'interrogation riches permettant de faire des
manipulations complexes sur chaque attribut du document (et sous-documents) comme
dans une base de données traditionnelles, tout en passant à l'échelle dans un contexte
distribué.

Quelles solutions pour gérer vos documents :

MongoDB (MongoDB) : ADP, Adobe, Bosch, Cisco, eBay, Electronic Arts, Expedia,
Foursquare
CouchBase (Apache) : AOL, AT&T, Comcast, Disney, PayPal, Ryanair
DynamoDB (Amazon) : BMW, Dropcam, Duolingo, Supercell, Zynga
Cassandra (Facebook -) : NY Times, eBay, Sky, Pearson Education

Exemples d'utilisation :

Gestion de contenu (bibliothèques numériques, collections de produits, dépôts de logiciels,

collections multimédia, etc.),
Framework stockant des objets,
Collection d’événements complexes,
Gestion des historiques d’utilisateurs sur réseaux sociaux.

5
 10/03/2025

Stockage orienté graphe

 Les trois premières familles NoSQL n'adressent pas le problème de corrélations entre
les éléments.
 Prenons l'exemple d'un réseau social : dans certains cas, il devient très complexe de
calculer la distance entre deux personnes non directement connectées. ce type
d'approche que résolvent les bases orientées Graphe.

Stockage orienté graphe

Stockage orienté graphe

Dans la base orientée graphe, les données stockées sont :

•les nœuds, les liens et des propriétés sur ces nœuds et ces liens.
•Les requêtes que l'on peut exprimer sont basées sur la gestion de chemins, de
propagations, d'agrégations, voire de recommandations.
•Toutefois, contrairement aux solutions précédentes la distribution des nœuds sur le
réseau n'est pas triviale.

Quelles bases de données gèrent de gros graphes ?

•Neo4j:Bay, Cisco, UBS, HP, TomTom, The National Geographic Society

•OrientDB (Apache) : Comcast, Warner Music Group, Cisco, Sky, United Nations,
VErisign
•FlockDB (Twitter) : Twitter

6
 10/03/2025

Passez à l'échelle

La distribution

le but de la distribution est de soulager le serveur central en répartissant les données sur
plusieurs serveurs.
 Les bases de données distribuées ne sont pas tolérantes aux pannes, la disponibilité est
problématique en termes de synchronisation multi-serveurs, et il n’y a pas de techniques
pour permettre l’élasticité de la base de données.

L’élasticité
C’est la capacité du système à s’adapter automatiquement en fonction du nombre de
serveurs qu’il dispose et de la quantité de données à répartir.

7
 10/03/2025

Le sharding
Le sharding est une technique permettant de distribuer des chunks sur un ensemble de
serveurs, avec la capacité de gérer l’élasticité (serveurs/données) et la tolérance aux
pannes.

des caractéristiques des bases NoSQL : l’élasticité et le sharding.

Replicatset et sharding
Comment résoudre le problème de la tolérance aux pannes?
MongoDB utilise pour cela une architecture basée sur le principe « M/E».

Réplication en MongoDB
Assure le redondance et augmente la disponibilité des données.
offre un niveau de tolérance aux pannes contre la perte d’un seul serveur de base de
données.
Un réplicatset est un groupe d’instance mongod qui conservent le même jeu de données.
Un replicaSet contient plusieurs nœuds porteurs de données:
Parmi ces nœuds un seul membres est considéré comme le nœud principal et l’autre
secondaire

8
 10/03/2025

L’architecture du ReplicaSet

Le serveur primaire "Primary", à qui toutes les requêtes sont envoyées (lecture/écriture),
va s’occuper de gérer la cohérence des données.

Les serveurs secondaires: sont utilisés dans le processus de réplication des données lors
d'une mise à jour."

Comment instancier un ReplicaSet ?

1.Un nom de ReplicaSet : rst
2.Un port d’écoute pour chaque serveur : 27018 (à incrémenter)
3.Créer un répertoire dédié : /data/NS1 (ReplicaSet 0/Serveur 1) -
4.Ouvrir une console et aller dans le répertoire de mongodb
5.Lancer le serveur :mongod --replSet rst --port 27018 --dbpath
/data/NS1

9
 10/03/2025

sharding

 La réplication est essentiellement destinée à pallier les pannes en dupliquant une

collection sur plusieurs serveurs et en permettant donc qu’un serveur prenne la relève
quand un autre vient à faillir.

 Le fait de disposer des mêmes données sur plusieurs serveurs par réplication :implique
la copie de toute la collection sur tous les serveurs.

 Lorsqu’une application croît et que le serveur initial n’est plus suffisamment puissant
pour répondre aux sollicitations des utilisateurs, la première option est d’envisager
un scaling vertical.
=>pas une méthode applicable à grande échelle
Ouvre également la voie à la distribution de la charge (en recherche, en insertion) et
donc à la sociabilité.

scaling horizontal et utiliser le MongoDB Sharding.

Le partitionnement: technique privilégiée pour obtenir une véritable scalabilité.

10
 18/03/2025

Origine d’Hadoop
● 2002: Doug Cutting développe Nutch, un moteur de recherche Open Source exploitant le calcul distribué :
l'implémentation peut tourner seulement sur quelques machines et a de multiples problèmes, notamment
en ce qui concerne l'accès et le partage de fichiers.
● 2003/2004: le département de recherche de Google publie deux articles, le premier sur GFS (un système de
fichier distribué Google File System) et le second sur le paradigme Map/Reduce pour le calcul distribué.
● 2004: Doug Cutting développe framework (encore assez primitif) inspiré des papers de Google et porte le
projet Nutch sur ce framework.
● 2006: Doug Cutting (désormais chez Yahoo) est en charge d'améliorer l'indexation du moteur de recherche
de Yahoo. Il exploite le framework réalisé précédemment...

1
 18/03/2025

Origine d’Hadoop
● … et créé une nouvelle version améliorée du framework en tant que projet Open Source de la fondation
Apache, qu'il nomme Hadoop (le nom d'un éléphant en peluche de son fils).
● A l'époque, Hadoop est encore largement en développement – un cluster pouvait alors comporter au
maximum 5 à 20 machines, etc.
● 2008 : le développement est maintenant très abouti, et Hadoop est exploité par le moteur de recherche de
Yahoo-‐ ainsi que par de nombreuses autres divisions de l'entreprise.

2
 18/03/2025

Hadoop aujourd’hui
● Plusieurs distributions d’Hadoop disponibles – dont celle de
Cloudera (CDH), celle d’Hortonworks (HDP) et MapR
● Hadoop pénètre de plus en plus les entreprises – tout secteur
d’activité (ex banque : HSBC, ING, Crédit Mutuel, …) – avec
l’argument d’un excellent équilibre coût / performance / stockage
/ flexibilité
● Le monde académique utilise aussi Hadoop : MIT, Berkeley, …
● Dans ce contexte, les éditeurs classiques intègrent aussi Hadoop
dans leur offre – comme IBM, Microsoft et Teradata
● Facebook a le plus gros cluster au monde ( en 2010, 40 PB)
● Criteo a le plus gros cluster Hadoop en europe (1200 serveurs / 39
PB)

L’équation Hadoop
Hadoop = excellent équilibre coût / performance / stockage / flexibilité

● coût : open-source + commodity hardware

● performance : map-reduce et scalabilité
● Stockage : hdfs – stockage distribué
● Flexibilité : écosystème riche

3
 18/03/2025

Map Reduce
Pour pouvoir traiter un grand volume de données sur un cluster de machines, il
faut découper le problème en plusieurs problèmes de taille réduite à exécuter
sur différentes machines (stratégie « diviser pour régner »).

De multiples approches existent et ont existé pour cette division d'un problème
en plusieurs « sous-tâches ».

MapReduce est un paradigme (modèle) de programmation distribuée

popularisé par Google

Map Reduce
Le modèle MapReduce préconise deux opérations distinctes:
● Map () : transforme les données d'entrée en une série de couples
clef/valeur. Cette opération doit être parallélisable: on doit pouvoir
découper les données d'entrée en plusieurs fragments, et faire exécuter
l'opération MAP à chaque machine du cluster sur un fragment distinct.
● Reduce () : applique un traitement à toutes les valeurs de chacune des clefs
distinctes produite par l'opération MAP. Chaque machine du cluster recevra
une des clefs uniques produites par MAP, accompagnées de la liste des
valeurs associées à la clef. Chaque machine effectuera alors l'opération
REDUCE pour cette clef et les valeurs associées.

4
 18/03/2025

Map Reduce
Les 4 étapes du traitement MapReduce :
● Split: les données en entrée sont découpées en plusieurs fragments

● Mapper: l’opération Map est appliquée sur chacun de ces fragments afin
d’obtenir les couples (clef;valeur)
● Shuffle: les couples (clef;valeur) sont groupés par clef

● Reduce: l’opération Reduce est appliquée sur chacun de ces groupes

indexés par clef afin d’obtenir une valeur finale pour chaque clef

Map Reduce (exemple Word Count)

Objectif: compter le nombre d'occurrence de chaque mot dans un texte

1ere étape “Split”:

Première étape: déterminer une manière de découper (split) les données

d'entrée pour que chacune des machines puisse travailler sur une partie du
texte.

Notre problème est ici très simple – on peut par exemple décider de découper
les données d'entrée ligne par ligne. Chacune des lignes du texte sera un
fragment de nos données d'entrée.

5
 18/03/2025

Map Reduce (exemple Word Count)

Nos données d'entrée (le texte):

Pour simplifier les choses, avant le découpage, nous allons supprimer toute
ponctuation et les caractères accentués. Nous allons également passer
l'intégralité du texte en minuscules.

Map Reduce (exemple Word Count)

Ce qui donne, après découpage:

on obtient 4 fragments depuis nos données d'entrée.

6
 18/03/2025

Map Reduce (exemple Word Count)

2eme étape “MAP”:

On doit désormais déterminer la clef à utiliser pour notre opération MAP, et

écrire le code de l'opération MAP elle-même.

Puisqu'on s'intéresse aux occurrences des mots dans le texte, et qu'à terme on
aura après l'opération REDUCE un résultat pour chacune des clefs distinctes, la
clef qui s'impose logiquement dans notre cas est: le mot-lui même.

Quand à notre opération MAP, elle sera elle aussi simple: nous allons
simplement parcourir le fragment qui nous est fourni et, pour chacun des
mots, générer le couple clef/valeur: (MOT ; 1). La valeur indique ici l’occurrence
pour cette clef - puisqu'on a croisé le mot une fois, on lui donne la valeur « 1 ».

Map Reduce (exemple Word Count)

Le code de notre opération MAP sera donc (ici en
pseudo code):

Pour chacun de nos fragments, les couples (clef;

valeur) générés seront donc:

7
 18/03/2025

Map Reduce (exemple Word Count)

3eme étape “SHUFFLE”:

Une fois notre opération MAP effectuée (de manière distribuée), Hadoop groupera (shuffle) tous les couples par
clef commune.

Cette opération est effectuée automatiquement par Hadoop. Elle est, là aussi, effectuée de manière distribuée en
utilisant un algorithme de tri distribué, de manière récursive. Après son exécution, on obtiendra les 15 groupes
suivants:

Map Reduce (exemple Word Count)

4eme étape “REDUCE”:

Il nous reste à créer notre opération REDUCE, qui sera appelée pour chacun des
groupes/clef distincte.

Dans notre cas, elle va simplement consister à additionner toutes les valeurs
liées à la clef spécifiée:

8
 18/03/2025

Map Reduce (exemple Word Count)

Une fois l'opération REDUCE effectuée, on obtiendra donc une valeur unique
pour chaque clef distincte. En l’occurrence, notre résultat sera:

9
 18/03/2025

Map Reduce (exemple Word Count)

Récapitulatif :

Conclusion

L’intérêt du modèle MapReduce est qu'il nous suffit de développer les deux opérations
réellement importantes du traitement: MAP et REDUCE, et de bénéficier automatiquement
de la possibilité d'effectuer le traitement sur un nombre variable de machines de manière
distribuée.

10
 18/03/2025

Exemple2 : la longueur moyenne

des mots

11
 18/03/2025

Exemple3 : le nombre de voyelles

et consonnes

12
 18/03/2025

Ecosystème Hadoop

13
 18/03/2025

Hadoop 1.0 et 2.0

HDFS
● HDFS = Hadoop Distributed File System

● HDFS =Système de fichiers (FileSystem) d’Hadoop par défaut

● HDFS est inspiré de GFS – « The Google File System », 2003

● Principales caractéristiques :

○ Distribué : les données sont réparties sur les machines du cluster

○ Répliqué : les données sont répliquées (par défaut 3) pour palier la
défaillance d’une machine
● HDFS est « taillé » pour les fortes volumétries

14
 18/03/2025

HDFS
● Dans HDFS, les données sont découpées en « blocks » - 128Mo par défaut

● HDFS s’appuie sur :

○ Le NameNode : 2 NameNodes par Cluster (Hadoop 2), et 3 NameNodes

par cluster (Hadoop 3)

○ Le DataNode : 1 DataNode par machine du Cluster

● Namenode = stocke les métadonnées des blocks (leur localisation, taille,

date de création, …)

● Datanode = stocke les données (fichiers csv, json, images, vidéos …)

15
 18/03/2025

HDFS : écriture d’un fichier

16
 18/03/2025

HDFS : lecture d’un fichier

HDFS : quelques commandes

hdfs dfs -ls /user ⇒ lister le contenu du dossier /user

hdfs dfs -mkdir nom_dossier_hdfs ⇒ créer un dossier sur HDFS

hdfs dfs -put fichier_en_local destination_sur_hdfs ⇒ écrire un fichier dans

HDFS

hdfs dfs -copyToLocal fichier_hdfs destination_en_local ⇒ copier le fichier

depuis hdfs vers un dossier sur le FS local

hdfs dfs -cat fichier_sur_hdfs ⇒ afficher le contenu d'un fichier sur HDFS

17
 18/03/2025

HDFS : quelques commandes

hdfs dfs -cp fichier_sur_hdfs destination_sur_hdfs ⇒ copier un fichier de HDFS
vers une destination sur HDFS

hdfs dfs -mv fichier_sur_hdfs destination_sur_hdfs ⇒ déplacer une fichier de

HDFS vers une destination sur HDFS

hdfs dfs -rm fichier_sur_hdfs ⇒ supprimer une fichier sur HDFS

hdfs dfs -du -h dossier_sur_hdfs ⇒ lister la taille du dossier sur HDFS

hdfs dfs -setrep -R -w 3 fichier_sur_hdfs ⇒ définir le facteur de réplication du

fichier sur HDFS

18
 18/03/2025

Phase 1: Algorithme Apriori

Phase 1: Algorithme Apriori

Extraction des itemsets fréquents
Exemple:
Données

Il s’agit de parcourir un treillis et de calculer les supports associés à chaque

combinaison

1
 18/03/2025

Propriétés des ensembles fréquents

Propriété 1 : support pour les sous-
ensembles
Si A ⊆ B pour les itemsets A, B alors
supp(A) >= supp(B) car toutes les
transactions dans D qui supportent
B supportent aussi nécessairement A.
A={Café, Moutarde}, B ={Café, Moutarde,
Saucisse}
Propriété 2 :
les sous-ensembles d’ensembles
fréquents sont fréquents
Exemple:
Donne la représentation la plus
Phase élagage: compacte possible de la liste des
Itemset fréquent : itemset dont le itemsets. Ex. si on sait que {p1,p2,p3} est
support>= sup_min fréquent, on sait que {p1,p2}, {p1,p3} et
{p2,p3} le sont également (mais on ne
connaît pas leur support)
Démonstration:

Propriétés des ensembles fréquents

2
 18/03/2025

Propriétés des ensembles fréquents

Exemple: Extraction des itemsets fréquents

Min_sup=2/9 (min_freq=2)

Génération des candidats

Exemple:
Supposons que la table Transaction(Tid, Item). On a :
107 transactions et l’on a 105 items différents.
En moyenne chaque transaction concerne 10 items.
C 45
10
Pour chaque transaction on a paires à regarder ainsi la jointure a 45*107
2
tuples
Remarque: si {item_1} n’est pas fréquent alors certainement la paire {item_1,
item_i} ne l’est pas.
Considérons la requête si seuil = 0,01
Pour qu’un item soit fréquent il faut qu’il apparaisse 0,01 * 107 =105 fois.

3
 18/03/2025

Problèmes d’Apriori

• Le principe de l’algorithme:
– Utiliser les (k – 1)-itemsets fréquents pour générer les k-itemsets
candidats
– Scanner la base pour tester le support des candidats
• Là où l’algo pèche : génération des candidats
– Beaucoup:
• 104 1-itemsets fréquents générant 107 2-itemsets candidats
• Pour trouver les 100-itemsets on doit générer 2100  1030
candidats.
– Plusieurs scans de la base:

Phase 2: Règles fortes

4
 18/03/2025

Règles fortes
Concept de base

Règles fortes

Recherche des règles pour les itemsets fréquent

les itemsets de card= 2:

Il faut tester toutes les combinaisons : 2 tests par itemset

{P1,P2} : P1->p2 : conf. = 2/4 = 50% (refusé)

P2->p1 : conf. = 2/3 = 67% (refusé)

{P1, P3} P1->P3 : conf. = 4/4 = 100% (accepté)

P3->P1 : conf. = 4/5 = 80% (accepté)

{P2,P3} P2->P3 : conf. = 3/3 = 100% (accepté)

P3->P2 : conf. = 3/5 = 60% (refusé)

Rq: Règles avec conséquent de card = 1

10

5
 18/03/2025

Règles fortes

Recherche des règles pour les itemsets de card= 3 et plus…

Règles avec antécédent de card = 2

11

Règles fortes
Exemple:

12

6
 18/03/2025

Règles fortes
Complexité temporelle

Théorème 1:
Transférer les éléments d’un ensemble fréquent de l’antécédent d’une règle au
conséquent ne peut pas augmenter son degré de confiance.
Démonstration:

Règles fortes
Ainsi, on peut dégager à partir du théorème 1 les résultats suivants

Théorème 2
Tout sur-ensemble (superset) du ‘conséquent’ d’une règle non-confidente est aussi non-
confident
Tout sous-ensemble du ‘conséquent’ d’une règle confidente est aussi confident
Exemple: ?

7
 18/03/2025

Propriété 1 : pas de composition des règles

Si X → Z et Y → Z sont vrais dans D, X U Y → Z n’est pas nécessairement vrai.
Propriété 2 : décomposition des règles
Si X U Y → Z convient, X → Z et Y → Z peut ne pas être vrai.
Propriété 3 : pas de transitivité
Si X → Y et Y → Z , nous ne pouvons pas en déduire que X → Z.

15

Règles fortes

Améliorations cherchées

Élimination des règles redondantes

• R1: A ⇒ BC
R2: AB ⇒ C
R2 redondante par rapport à R1
– pour un k-ensemble fréquent, présenter les règles de condition minimale
• R1: A ⇒ BCD
R2: AB ⇒ C
R2 redondante par rapport à R1

– chercher les règles issues du plus grand k-ensemble fréquent; si on trouve une
règle ayant une condition minimale, on évite de chercher les règles dont la
prémisse contient cette condition minimale.

16

8
 18/03/2025

oExtraction des autres types d’itemsets

- Extraction des itemsets fermés

•si aucun de ses supersets n’a de support identique.
• tous ses supersets ont un support strictement plus faible.
•Exemple
Soient SUP ({S1, S2, S3}) = 3/10, SUP({S1, S3, S4}) = 1/10 et SUP{S1,S3}=5/10
Donc {S1, S3} est fermé car aucun de ses supersets n’a de support égal à 5/10

17

-Extraction des itemsets maximaux

•si aucun de ses supersets n’est fréquent.

•Exemple:
Soit {S1, S2, S3, S4} n’est pas fréquent (sup=1/10)
{S1, S2, S3} est maximal car son superset {S1, S2, S3, S4} n’est pas fréquent avec
un support de 1/10.
•Extraction des itemsets fermés sous R

18

9
 18/03/2025

- Itemset générateur (generator itemset).

•si tous ses sousitemsets ont un support strictement supérieur.
•Exemple,
Soit {S1, S2, S3} de support 4/10
n’est pas générateur puisque {S1, S2} avec un support identique

19

Règles fortes
Mesures d’évaluation des règles
Support et confiance:

En termes probabilistes:
R : p1->p2
Sup ( R ) = prob(p1p2)
Conf( R )= prob(p1/p2)=2/4

Problème: Une règle peut avoir d’excellents supports et confiance sans être pour
autant «intéressante»

Solution: une mesure d’intérêt

Qui caractérise une forme de causalité c.-à-d. l’idée «la connaissance de l’antécédent
amène de l’information (supplémentaire) sur la connaissance du conséquent»
Indice de pertinence des règles: la métrique Lift(R: A-> B)=P(B/A)/P(B)
= conf (R )/sup (B)
RQ:
Le LIFT ne peut être calculé qu’après coup pour filtrer les règles.

20

10
 18/03/2025

Règles fortes
Mesures d’évaluation des règles

Leverage=sup(AB)/|D| - sup(A)/|D| * sup(B)/|D|

Conviction =sup(A) *(|D| -sup(B))/|D| *(sup(A)-sup(AB))

21

Discussion

22

11