08/04/2018

FOUILLE DE
DONNÉES
A. BELAID, 2018

Université de Béjaia,
Département Informatique

I. Introduction

1
 08/04/2018

Plateforme d’enseignement à
distance
• [Link]

• Mot de passe FD2018

• Vous trouverez : le cours en présentation pdf, énoncés de TD

et TP + projet, Biblio, Forum…

Définition
• Data Mining == Fouille de données

• Regroupe un ensemble de techniques et d’outils de la

Statistique, l’Informatique et la Science de l’information

• Le data-mining est un processus d’extractions automatique

d’informations predictives à partir de grandes bases de
données.

• Le data-mining est un processus de découverte de règle,

relations, corrélations et/ou dépendances à travers une
grande quantité de données, grâce à des méthodes
statistiques, mathématiques et de reconnaissances de formes.

2
 08/04/2018

Data-Mining : les raisons du

développement
• Données
• Big Data : augmentation sans cesse de données générées
• 11.28 milliards de transactions assurées par CB en 2015, France
• Twitter : 50M de tweets /jour (=7 téraoctets)
• Youtube : 50h de vidéos uploadées /minute
• Facebook : 10 téraoctets /jour
• 2.9 million de mail /seconde
• Création de valeur ajoutée
• Puissance de calcul

• Submergés par les données, manque de connaissance !

Exemples d’applications
• Entreprise et Relation Clients: création de profils clients,
ciblage de clients potentiels et nouveaux marchés
• Finances: minimisation de risques financiers
• Bioinformatique: analyse du génome, mise au point de
médicament ...
• Internet: spam, e-commerce, détection d’intrusion, recherche
d’informations ...
• Sécurité

3
 08/04/2018

Exemples d’applications : E-
commerce
Targeting (ciblage)
• Stocker les séquences de clicks des visiteurs, analyser les
caractéristiques des acheteurs
• Faire du ”targeting” lors de la visite d’un client potentiel

Systèmes de recommandation
• Opportunité : les clients notent les produits! Comment tirer
profit de ces données pour proposer des produits à un autre
client ?
• Solutions: technique dit de filtrage collaboratif pour regrouper
les clients ayant les mêmes “goûts”.

Exemples d’applications :
Analyse des risques
Détection de fraudes pour les assurances
• Analyse des déclarations des assurés par un expert afin
d’identifier les cas de fraudes.
• Applications de méthodes statistiques pour identifier les
déclarations fortement corrélées à la fraude.

Prêt Bancaire
• Objectif des banques: réduire le risque des prêts bancaires.
• Créer un modèle à partir de caractérisques des clients pour
discriminer les clients à risque des autres.

4
 08/04/2018

Exemples d’applications :
Commerce
Opinion mining
• Exemple: analyser l’opinion des usagers sur les produits d’une
entreprise à travers les commentaires sur les réseaux sociaux
et les blogs

• B. Pang et L. Lee, Opinion mining and sentiment analysis, 2008

Mise en oeuvre d’un projet de

DM

5
 08/04/2018

Mise en oeuvre d’un projet de

DM

Type de données
• Capteurs  variables quantitatives, qualitatives, ordinales
• Texte  Chaîne de caractères
• Parole  Séries temporelles
• Images  données 2D
• Videos  données 2D + temps
• Réseaux  Graphes
• Flux  Logs, coupons. . .
• Etiquettes  information d’évaluation
• Big Data (volume, vélocité, variété), flot "continu" de données
• Pre-traitement des données: nettoyage, normalisation, codage. . .
• Représentation : des données aux vecteurs

6
 08/04/2018

Données du DM: illustration

Données et Métriques
Les algorithmes nécessitent une notion de similarité dans l’espace 𝓧 des
données. La similarité est traduite par la notion de distance. Pour
𝑥, 𝑦 ∈ 𝑅𝑑 , on a :
distance euclidienne :
𝑑
2
𝐷 𝑥, 𝑦 = 𝑥 − 𝑦 2 = 𝑥𝑗 − 𝑦𝑗
𝑗=1

= 𝑥 − 𝑦 𝑇 (𝑥 − 𝑦).
distance de manhattan
𝑑

𝐷 𝑥, 𝑦 = 𝑥 − 𝑦 1 = 𝑥𝑗 − 𝑦𝑗 .
𝑗=1
distance de mahalanobis
𝐷 𝑥, 𝑦 = 𝑥 − 𝑦 𝑇 𝑀−1 (𝑥 − 𝑦), avec 𝑀 ∈ 𝑅𝑑×𝑑 : matrice carrée
définie positive

7
 08/04/2018

Caractérisation des méthodes

Types d’apprentissage
• Apprentissage supervisé (predictif) – Reg, Reg logi :Class
• Apprentissage non-supervisé (descriptif)- Clust, ACP
• Apprentissage semi-supervisé

Organisation du cours
• Introduction et généralités
• Méthode des 𝑘 plus proches voisins
• Clustering
• CHA
• K means
• Modèles de mélange
• Modèle bayesien
• La régression
• La réduction de données

8
 08/04/2018

Caractérisation des méthodes :

apprentissage supervisé
Objectif
• A partir des données *(𝑥𝑖 , 𝑦𝑖 ) ∈ 𝓧 × 𝓨, 𝑖 = 1, … , 𝑁+, estimer
les dépendances entre 𝓧 𝑒𝑡 𝓨.
• On parle d’apprentissage supervisé car les 𝑦𝑖 permettent de
guider le processus d’estimation.
Exemples
• Estimer les liens entre habitudes alimentaires et risque
d’infarctus. 𝑥𝑖 : d attributs concernant le régime d’un patient,
𝑦𝑖 sa catégorie (risque, pas risque).
• Applications: détection de fraude, diagnostic médical ...
Techniques
• k-plus proches voisins, SVM, régression logistique, arbre de
décision ...

Caractérisation des méthodes :

Apprentissage non-supervisé
Objectifs
• Seules les données *𝑥𝑖 ∈ 𝓧, 𝑖 = 1, … , 𝑁+ sont disponibles. On
cherche à décrire comment les données sont organisées et en
extraire des sous-ensemble homogènes.
Exemples
• Catégoriser les clients d’un supermarché. 𝑥𝑖 représente un
individu (adresse, âge, habitudes de courses ...)
• Applications: identification de segments de marchés,
catégorisation de documents similaires, segmentation
d’images biomédicales ...
Techniques
• Classification hiérarchique, Carte de Kohonen, K-means,
extractions de règles ...

9
 08/04/2018

Caractérisation des méthodes :

apprentissage semi-supervisé
Objectifs
• Parmi les données, seulement un petit nombre ont un label i.e
𝑥1 , 𝑦1 , … , 𝑥𝑛 , 𝑦𝑛 , 𝑥𝑛+1 , … , 𝑥𝑁 . L’objectif est le même que
pour l’apprentissage supervisé mais on aimerait tirer profit
des données sans étiquette.
Exemples
• Pour la discrimination de pages Web, le nombre d’exemples
peut être très grand mais leur associer un label (ou étiquette)
est coûteux.
Techniques
• Méthodes bayésiennes, SVM ...

Apprentissage supervisé : les

concepts
• Soit deux ensembles 𝓧et 𝓨 munis d’une loi de probabilité
jointe 𝑝(𝑋, 𝑌).

• Objectifs : On cherche une fonction 𝑓: 𝓧 → 𝓨 qui à 𝑋 associe

𝑓(𝑋) qui permet d’estimer la valeur 𝑦 associée à 𝑥.
• 𝑓 appartient à un espace 𝑯 appelé espace d’hypothèses.
• Exemple de 𝑯 : ensemble des fonctions polynomiales

10
 08/04/2018

Apprentissage supervisé : les

concepts
• On introduit une notion de coût 𝐿(𝑌, 𝑓(𝑋)) qui permet
d’évaluer la pertinence de la prédiction de 𝑓 , et de pénaliser
les erreurs.

• L’objectif est donc de choisir la fonction 𝑓 qui minimise:

𝑅 𝑓 = 𝐸𝑋,𝑌 ,𝐿(𝑌, 𝑓(𝑋))-

• où R est appelé le risque moyen ou erreur de généralisation. Il

est également noté EPE(f ) pour Expected Prediction Error

Apprentissage supervisé : les

concepts
• Exemples de fonction coût et de risque moyen associé.
• Coût quadratique (moindres carrés)
2
𝐿(𝑌, 𝑓 (𝑋)) = 𝑌 − 𝑓 𝑋 ,
2 2
𝑅 𝑓 = 𝐸 𝑌 − 𝑓 𝑋 =∫ 𝑦 − 𝑓 𝑥 𝑝 𝑥, 𝑦 𝑑𝑥𝑑𝑦.

• Coût (moindres valeurs absolues)

𝐿(𝑌, 𝑓(𝑋)) = 𝑌 − 𝑓 𝑋 ,
𝑅 𝑓 = 𝐸 𝑌 − 𝑓 𝑋 = ∫ 𝑦 − 𝑓 𝑥 𝑝 𝑥, 𝑦 𝑑𝑥𝑑𝑦.

11
 08/04/2018

Apprentissage supervisé : les

concepts
• On parle de régression quand 𝓨 est un sous-espace de 𝑅 𝑑 .

2
• Fonction de coût typique : quadratique 𝑦 − 𝑓 𝑥
𝑅 𝑓

𝑃𝑎𝑟𝑎𝑚è𝑡𝑟𝑒 𝛼

Apprentissage supervisé : les

concepts
• On parle de Classification ou Discrimination si 𝓨 est un
ensemble discret non-ordonné, (par exemple −1,1 )

• La fonction de coût la plus usitée est : Θ(−𝑦𝑓(𝑥)) où Θ est la

fonction échelon.

12
 08/04/2018

Apprentissage supervisé : les

concepts
• En pratique, on a un ensemble de données * 𝑥𝑖 , 𝑦𝑖 ∈ 𝓧 ×
𝓨, 𝑖 = 1, … , 𝑁+ appelé ensemble d’apprentissage obtenu par
échantillonnage indépendant de 𝑝(𝑋, 𝑌) que l’on ne connaît
pas.

• On cherche une fonction 𝑓 , appartenant à 𝐻 qui minimise le

risque empirique :
𝑁
1
𝑅𝑒𝑚𝑝(𝑓) = 𝐿(𝑦𝑖 , 𝑓(𝑥𝑖 ))
𝑁
𝑖=1
• Le risque empirique ne permet pas d’évaluer la pertinence
d’un modèle car il est possible de choisir 𝑓 de sorte que le
risque empirique soit nul mais que l’erreur en généralisation
soit élevée. On parle alors de sur-apprentissage

Illustration du sur-
apprentissage

Faible Complexité du modèle Elevé

13
 08/04/2018

Sélection de modèles
Problématique

• On cherche une fonction 𝑓 qui minimise un risque empirique donné.

On suppose que 𝑓 appartient à une classe de fonctions paramétrées
par 𝛼. Comment choisir 𝛼 pour que 𝑓 minimise le risque empirique
et généralise bien ?

• Exemple : On cherche un polynôme de degré 𝛼 qui minimise un

risque
𝑁

𝑅𝑒𝑚𝑝 𝑓𝛼 = 𝑦𝑖 − 𝑓𝛼 𝑥𝑖 2.

𝑖=1
• Objectifs :
1) proposer une méthode d’estimation d’un modèle afin de choisir
(approximativement) le meilleur modèle appartenant à l’espace
hypothèses.
2) une fois le modèle choisi, calculer son erreur de généralisation.

Sélection de modèles :
approche classique
Cas idéal : Données 𝑫𝑵 avec N très grand

1) Découper aléatoirement 𝐷𝑁 = 𝐷𝑎𝑝𝑝 ∪ 𝐷𝑣𝑎𝑙 ∪ 𝐷𝑡𝑒𝑠𝑡

2) Apprendre chaque modèle possible sur 𝐷𝑎𝑝𝑝
3) Evaluer sa performance en généralisation sur 𝐷𝑣𝑎𝑙
1
𝑅𝑣𝑎𝑙 = 𝐿 𝑦𝑖 , 𝑓 𝑥𝑖 ,
𝑁𝑣𝑎𝑙
𝑖∈𝐷𝑣𝑎𝑙
4) Sélectionner modèle qui donne la meilleure performance sur 𝐷𝑣𝑎𝑙
5) Tester le modèle retenu sur 𝐷𝑡𝑒𝑠𝑡

14
 08/04/2018

Sélection de modèles :
Validation Croisée
Cas moins favorable : les données 𝑫𝑵 sont modestes

• Estimation de l’erreur de généralisation par rééchantillonnage.

• Principe
1) Séparer les 𝑁 données en 𝐾 ensembles de part égales.
2) Pour chaque 𝑘 = 1, … , 𝐾, apprendre un modèle en utilisant les
𝐾 − 1 autres ensemble de données et évaluer le modèle sur la
𝑘-ième partie.
3) Moyenner les 𝐾 estimations de l’erreur obtenues pour avoir
l’erreur de validation croisée.

Sélection de modèles :
Validation Croisée (suite)
• Détails :
𝑘 𝑁𝑘
1 1
𝑅𝐶𝑉 = 𝐿(𝑦𝑖𝑘 , 𝑓 −𝑘 (𝑥𝑖𝑘 ))
𝐾 𝑁𝑘
𝐾=1 𝑖=1

• où 𝑓 −𝑘 est le modèle 𝑓 appris sur l’ensemble des données

sauf la 𝑘-ième partie.
• Propriétés : Si 𝐾 = 𝑁 , CV est approximativement un
estimateur sans biais de l’erreur en généralisation.
L’inconvénient est qu’il faut apprendre 𝑁 − 1 modèles.
• typiquement, on choisit 𝐾 = 5 ou 𝐾 = 10 pour un bon
compromis entre le biais et la variance de l’estimateur.

15
 08/04/2018

Conclusions
Pour bien mener un projet de DM:

• Identifier et énoncer clairement les besoins.

• Créer ou obtenir des données représentatives du problème
• Identifier le contexte de l’apprentissage
• Analyser et réduire la dimension des données
• Choisir un algorithme et/ou un espace d’hypothèses.
• Choisir un modèle en appliquant l’algorithme aux données
prétraitées.
• Valider les performances de la méthode.

Au final ...
• Les voies du Machine Learning et du traitement des données c’est ...

16