Laboratoire d’Informatique

Fondamentale de Lille
O
OPAC

Fouille de données (Data Mining)

- Un tour d’horizon -

E-G. Talbi
[email protected]
Introduction au Data Mining

ƒ Définition du Data Mining

ƒ Pourquoi le Data Mining ?
ƒ Description du processus KDD
(Knowledge Data Discovery)
ƒ Applications
ƒ Tâches et Techniques du Data Mining
 Qu’est-ce que le DM ?

ƒ Processus inductif, itératif et interactif de

découverte dans les BD larges de modèles de
données valides, nouveaux, utiles et
compréhensibles.
ƒ Itératif : nécessite plusieurs passes

ƒ Interactif : l’utilisateur est dans la boucle du

processus
ƒ Valides : valables dans le futur
ƒ Nouveaux : non prévisibles
ƒ Utiles : permettent à l’utilisateur de prendre
des décisions
ƒ Compréhensibles : présentation simple
 Notion d’induction [Peirce 1903]

ƒ Abduction : diagnostic médical, ...

ƒ Toutes les voitures ont 4 roues
ƒ La Peugeot 206 a 4 roues
ƒ ==> La Peugeot 206 est une voiture

ƒ Déduction : Raisonnement qui conclut à partir de

prémisses et d’hypothèses à la vérité d’une proposition en
usant des règles d’inférence
ƒ Toutes les voitures ont 4 roues
ƒ La Peugeot 206 est une voiture
ƒ ==> La Peugeot 206 a 4 roues
 Notion d’induction [Peirce 1903]

ƒ Induction : Généralisation d’une observation ou d’un

raisonnement établis à partir de cas singuliers.

ƒ Utilisée en Data mining (tirer une conclusion à partir

d ’une série de faits, pas sûre à 100%)

ƒ La clio a 4 roues, La Peugeot 106 a 4 roues, La BMW M3 a 4

roues, La Mercedes 190 a 4 roues
ƒ ==> Toutes les voitures ont 4 roues
 Motivations (1)

ƒ Explosion des données

ƒ Masse importante de données (millions de milliards
d’instances) : elle double tous les 20 mois.
ƒ BD très larges - Very Large Databases (VLDB)
ƒ Données multi-dimensionnelles (milliers d’attributs)
ƒ BD denses
ƒ Inexploitables par les méthodes d’analyse classiques
ƒ Collecte de masses importantes de données (Gbytes/heure)
ƒ Données satellitaires, génomiques (micro-arrays, …),
simulations scientifiques, etc.
ƒ Besoin de traitement en temps réel de ces données
 Motivations (2)

ƒ Améliorer la productivité
ƒ Forte pression due à la concurrence du marché
ƒ Brièveté du cycle de vie des produits
ƒ Besoin de prendre des décisions stratégiques efficaces
ƒ Exploiter le vécu (données historiques) pour prédire le
futur et anticiper le marché
ƒ individualisation des consommateurs (dé-massification).

ƒ Croissance en puissance/coût des machines capables

ƒ de supporter de gros volumes de données
ƒ d’exécuter le processus intensif d’exploration
ƒ hétérogénéité des supports de stockage
 Motivations (3)

F ile E dit

500

400

300

200
L oc ate V iew

E
D
C
B
A
H elp

Storage
Storage
100 Mount
431 7437 1950
0
1 2 3 4 5 6
Network
7
79% /
Traffic 02 631963
Help 47358
93% /us

Storage
Storage

Storage
Storage Storage
Storage
Storage Storage Storage
Storage
Storage Storage

Internet
Storage
Storage

Masse importante de données – supports hétérogènes

Le processus de découverte de connaissances

ƒ Data mining : coeur de KDD

(Knowledge Data Discovery).

Collecte, Data
Data
Collecte, Préparation
Nettoyage,
Nettoyage, Data
Préparation Données Mining
Mining
Intégration desdonnées
des données
Intégration d’apprentissage
Warehouse

Vérification&&
Vérification Modèles,
Sources de Evaluation
Evaluation Patterns
données
 Démarche méthodologique (1)

ƒ Comprendre l’application
ƒ Connaissances a priori, objectifs, etc.
ƒ Sélectionner un échantillon de données
ƒ Choisir une méthode d’échantillonnage
ƒ Nettoyage et transformation des données
ƒ Supprimer le «bruit» : données superflues, marginales,
données manquantes, etc.
ƒ Effectuer une sélection d’attributs, réduire la dimension
du problème, etc.
ƒ Appliquer les techniques de fouille de données
ƒ Choisir le bon algorithme
 Démarche méthodologique (2)

ƒ Visualiser, évaluer et interpréter les modèles

découverts
ƒ Analyser la connaissance (intérêt)
ƒ Vérifier sa validité (sur le reste de la base de données)
ƒ Réitérer le processus si nécessaire

ƒ Gérer la connaissance découverte

ƒ La mettre à la disposition des décideurs
ƒ L’échanger avec d’autres applications (système expert, …)
ƒ etc.
 Data Mining et aide à la décision

Potentiel de support
de décision Utilisateur(s)
Prise
de décisions

Présentation des Décideur(s)

connaissances
Techniques de visualisation
Data Mining Analyste(s) de données
Découverte de connaissances

Exploration de données
(Statistiques, Requêtes, ...)
Data Warehouses Administrateur de
(OLAP, ...) Bases de données
Sources de données
(Papier, Fichiers, Fournisseurs d’information, SGBD, …)
 Objectifs

ƒ Développer des techniques et systèmes efficaces

et extensibles pour l’exploration de :
ƒ BD larges et multi-dimensionnelles
ƒ Données distribuées

ƒ Faciliter l’utilisation des systèmes de DM

ƒ Limiter l’intervention de l’utilisateur
ƒ Représentation simple de la connaissance
ƒ Visualisation sous forme exploitable
 Communautés impliquées

ƒ Intelligence artificielle et apprentissage

ƒ Bases de données

ƒ Analyse de données (statistiques)

ƒ Visualisation

ƒ Recherche opérationnelle et optimisation

ƒ Informatique parallèle et distribuée

ƒ Etc.
 Data Mining et Statistiques

ƒ Data mining : Exploratoire, Data-driven modeling

ƒ Statistiques : Confirmatoire, User-driven modeling

ƒ Distribution d ’une seule variable : moyenne, médiane,

variance, écart-type, …

ƒ Explorer les relation entre variables : coefficient de

corrélation, …
ƒ Découverte de la cause des relations entre de nombreuses
variables est assez complexe.

ƒ test du X2, ...

ƒ Réseaux bayésiens (probabilités conditionnelles)
 Découverte de modèles fonctionnels

ƒ Méthodes de régression :
ƒ régression linéaire : Y = aX+ b (a, b : valeurs réelles)
Nombre de
petits commerçants
*
* *
*
*
* * Nombre de grandes
surfaces
ƒ Rapide et efficace (valeurs réelles)
ƒ Insuffisante pour l ’analyse d’espace multidimentionnel
 Découverte de modèles fonctionnels

ƒ Kernel regression : découvrir graphiquement

la fonction à utiliser, peut être une courbe
Nombre de
petits commerçants
*
*
*
* *
* Nombre de grandes
*
surfaces

ƒ Techniques statistiques inadéquates : nombre de

facteurs important, modèles non linéaires.
 Domaines d’application

ƒ Prise de décision basée

sur de nouvelles
connaissances
Marketing
ƒ Ex., impact sur le
marketing

ƒ Le rôle et l’importance du BDD

Marketing
KDD et DM est de plus en
plus important
Data KDD &
Warehousing Data Mining
ƒ Mais le DM n’est pas
seulement dans le
marketing...
 Domaines d’application

ƒ Marketing direct : population à cibler (âge, sexe,

profession, habitation, région, …) pour un
publipostage.
ƒ Gestion et analyse des marchés : Ex. Grande
distribution : profils des consommateurs, modèle
d ’achat, effet des périodes de solde ou de
publicité, « panier de la ménagère »
ƒ Détection de fraudes : Télécommunications, ...
ƒ Gestion de stocks : quand commander un produit,
quelle quantité demander, …
ƒ Analyse financière : maximiser l ’investissement de
portefeuilles d ’actions.
 Domaines d’application

ƒ Gestion et analyse de risque : Assurances, Banques

(crédit accordé ou non)
ƒ Compagnies aériennes
ƒ Bioinformatique et Génome : ADN mining, …
ƒ Médecine et pharmacie :
ƒ Diagnostic : découvrir d ’après les symptomes du
patient sa maladie
ƒ Choix du médicament le plus approprié pour
guérir une maladie donné
ƒ Web mining, text mining, etc.
Exemple 1 - Marketing

ƒ Vous êtes gestionnaire marketing d’un

opérateur de télécommunications
mobiles :
ƒ Les clients recoivent un téléphone gratuit
(valeur 150€) avec un contrat d’un an ;
vous payer une commission de vente de
250€ par contrat
ƒ Problème : Taux de renouvellement (à la
fin du contrat) est de 25%
ƒ Donner un nouveau téléphone à toute
personne ayant expirer son contrat coûte
cher.
ƒ Faire revenir un client après avoir quitter
est difficile et coûteux.
Exemple 1 - Marketing

ƒ Trois mois avant

Yippee!
Yippee! l’expiration du contrat,
Jereste
Je reste!! prédire les clients qui
vont quitter :

ƒ Si vous voulez les garder,

offrir un nouveau
téléphone.
Exemple 2 - Assurances
ƒ Vous êtes un agent
Oh,oui!
Oh, oui! d’assurance et vous
J’aimema
J’aime ma devez définir un
Ferrari!
Ferrari! paiement mensuel adapté
à un jeune de 18 ans qui a
acheté une Ferrari.

ƒ Qu’est ce qu’il faut faire

?
Exemple 2 - Assurances

ƒ Analyser les données de tous les

clients de la compagnie.
ƒ La probabilité d’avoir un accident
est basée sur … ?
ƒ Sexe du client (M/F) et l’âge
ƒ Modèle de la voiture, âge, adresse, ....
ƒ etc.
ƒ Si la probabilité d’avoir un
accident est supérieure à la
moyenne, initialiser la mensualité
suivant les risques.
 Exemple 3 – Banque - Télécom

ƒ Vous êtes à l’étranger et

quelqu’un a volé votre carte de
crédir ou votre mobile …
ƒ compagnies bancaires …
ƒ Utiliser les données historiques pour
construire un modèle de comportement
frauduleux et utiliser le data mining
pour identifier des instances
similaires.
ƒ compagnies téléphoniques …
ƒ Analyser les “patterns” qui dérivent du
comportement attendu (destinataire,
durée, etc.)
 Exemple 4 - Web

ƒ Les logs des accés Web sont

analysés pour …
bonne
bonne
expériencede
expérience desurfing!
surfing! ƒ Découvrir les préférences des
utilisateurs

ƒ Améliorer l’organisation du site

Web

ƒ De manière similaire …
ƒ L’analyse de tous les types
d’informations sur les logs

ƒ Adaptation de l’interface
utilisateur/service
Paramètres d’un processus KDD

Technique ?
Format, Type ?

Données
Data
Data
Tâche ?
d’apprentissage Mining
Mining

Modèles, Type de
Patterns représentation ?
 Les données

ƒ Valeurs des champs des enregistrements des

tables de l’entropot (base de données)
ƒ Types :
ƒ Données discrètes : données binaires (sexe, …),
données énumératives (couleur, …), énumératives
ordonnées (réponses 1:très satisfait, 2:satisfait,
…).
ƒ Données continues : données entières ou réelles
(âge, salaire, …)
ƒ Dates
ƒ Données textuelles
ƒ Pages/liens web, Multimédia, …
 Tâches du Data Mining

ƒ Classification

ƒ Clustering (Segmentation)

ƒ Recherche d’associations

ƒ Recherche de séquences

ƒ Détection de déviation
 Classification

ƒ Elle permet de prédire si une instance de donnée est membre

d’un groupe ou d’une classe prédéfinie.

ƒ Classes
ƒ Groupes d’instances avec des profils particuliers
ƒ Apprentissage supervisé : classes connues à l’avance

ƒ Applications : marketing direct (profils des consommateurs),

grande distribution (classement des clients), médecine
(malades/non malades), etc.
ƒ Exemple : les acheteurs de voitures de sport sont de jeunes
citadins ayant un revenu important
 Clustering (Segmentation)

ƒ Partitionnement logique de la base de données en

clusters

ƒ Clusters : groupes d’instances ayant les mêmes

caractéristiques
ƒ Apprentissage non supervisé (classes inconnues)

ƒ Pb : interprétation des clusters identifiés

ƒ Applications : Economie (segmentation de marchés),

médecine (localisation de tumeurs dans le cerveau), etc.
 Règles d’association

ƒ Corrélations (ou relations) entre attributs (méthode non

supervisée)

ƒ Applications : grande distribution, gestion des stocks, web

(pages visitées), etc.

ƒ Exemple
ƒ BD commerciale : panier de la ménagère
ƒ Articles figurant dans le même ticket de caisse
ƒ Ex : achat de riz + vin blanc ==> achat de poisson
ƒ Achats bières et couches-culottes (USA, Week-end)
 Recherche de séquences
ƒ Recherche de séquences
ƒ Liaisons entre événements sur une période de temps
ƒ Extension des règles d’association
ƒ Prise en compte du temps (série temporelle)
ƒ Achat Télévision ==> Achat Magnétoscope d’ici 5 ans
ƒ Applications : marketing direct (anticipation des
commandes), bioinformatique (séquences d’ADN), bourse
(prédiction des valeurs des actions)
ƒ Exemple
ƒ BD commerciale (ventes par correspondance)
ƒ Commandes de clients
ƒ Ex : 60% des consommateurs qui commandent la bière
«Mort subite» commandent de l’aspro juste après
Q Séquences d’AND : ACGTC est suivie par GTCA après un
gap de 9, avec une probabilité de 30%
 Détection de déviation

ƒ Instances ayant des caractéristiques les plus

différentes des autres
ƒ Basée sur la notion de distance entre instances
ƒ Expression du problème
ƒ Temporelle : évolution des instances ?
ƒ Spatiale : caractéristique d’un cluster d’instances ?
ƒ Applications
ƒ Détection de fraudes (transactions avec une carte
bancaire inhabituelle en telemarketing)
ƒ Caractéristiques
ƒ Problème d’interprétation : bruit ou exception (donc
connaissance intéressante)
 Illustration

Point isolé
 Techniques utilisées

ƒ K-moyennes, A-priori, K-NN

ƒ Réseaux de neurones
ƒ Algorithmes génétiques
ƒ Chaînes de Markov cachées
ƒ Arbres de décision
ƒ Réseaux bayesiens
ƒ Soft computing : ensembles flous
ƒ …
 Résumé - Introduction
ƒ Data mining : découverte automatique de modèles
intéressants à partir d’ensemble de données de
grande taille
ƒ KDD (knowledge data discovery) est un processus :
ƒ Pré-traitement (Pre-processing)
ƒ Data mining
ƒ Post-traitement (Post-processing)
ƒ Pour le data mining, utilisation de différents …
ƒ Base de données (relationelle, orientée objet, spatiale,
WWW, …)
ƒ Connaissances (classification, clustering, association, …)
ƒ Techniques (apprentissage, statistiques, optimisation, …)
ƒ Applications (génomique, télécom, banque, assurance,
distribution, …)
Travaux pratiques :
Cadre du travail
WEKA 3.2

Waikato Environment for Knowledge

Analysis

http://www.cs.waikato.ac.nz/ml/weka/
http://www.lifl.fr/~jourdan
 WEKA

ƒ Logiciel gratuit disponible sur le web :

http://www.cs.waikato.ac.nz/ml/weka/
ƒ Plate forme logicielle en Java tournant
sous :
ƒ Windows
ƒ Linux
ƒ Facile à prendre en main
 WEKA
ƒ Interface en ligne de commande
ƒ Explorer (interface graphique)
ƒ Filtre
ƒ Apprentissage (clustering,
classification, ...)
ƒ Sélection d’attributs
ƒ Visualisateur de données et de
résultats
ƒ Expérimenter (environnement
d’expérience)
ƒ Test d’une méthode spécifique sur
un ensemble de données avec des
critères variés pour la
comparaison de résultats
 WEKA
ƒ En entrée : fichiers, base de données, Url
ƒ En sortie : affichage des résultats, sortie des
résultats dans des fichiers, visualisation
graphique …

Exemple de
visualisation après
une classification :
une couleur
représente une
classe
 Weka - Explorer

Les fonctions disponibles :

ƒ Filtre et Preprocess sur les données
ƒ Classification
ƒ Clustering
ƒ Règles d’association
ƒ Sélection d’attributs
ƒ Visualisateur
 Plan du cours

ƒ Clustering
Plan
ƒ Classification

ƒ Règles d’association

ƒ Outils pour le Data Mining

Clustering
(Segmentation)
 Clustering - Plan

ƒ Problèmatique du clustering
ƒ Applications
Sommaire ƒ Similarité et types de données
ƒ Méthodes de clustering
ƒ Méthodes de partitionnement
ƒ Méthodes hiérarchiques
ƒ Méthodes par voisinage dense
ƒ Application réelle en génomique
ƒ Résumé
 Problèmatique

ƒ Soient N instances de données à k attributs,

ƒ Trouver un partitionnement en c clusters
(groupes) ayant un sens (Similitude)

ƒ Affectation automatique de “labels” aux clusters

ƒ c peut être donné, ou “découvert”
ƒ Plus difficile que la classification car les classes
ne sont pas connues à l’avance (non supervisé)
ƒ Attributs
• Numériques (distance bien définie)
• Enumératifs ou mixtes (distance difficile à définir)
 Qualité d’un clustering

ƒ Une bonne méthode de clustering produira

des clusters d’excellente qualité avec :
ƒ Similarité intra-classe importante
ƒ Similarité inter-classe faible
ƒ La qualité d’un clustering dépend de :
ƒ La mesure de similarité utilisée
ƒ L’implémentation de la mesure de
similarité
ƒ La qualité d’une méthode de clustering est
évaluée par son abilité à découvrir certains
ou tous les “patterns” cachés.
 Objectifs du clustering

Minimiser
Minimiser les
les distances
distances Maximiser
Maximiser les
les distances
distances
intra-cluster
intra-cluster inter-clusters
inter-clusters
 Exemples d’applications

ƒ Marketing : segmentation du marché en découvrant des

groupes de clients distincts à partir de bases de doneées
d’achats.
ƒ Environnement : identification des zones terrestres
similaires (en termes d’utilisation) dans une base de
données d’observation de la terre.
ƒ Assurance: identification de groupes d’assurés distincts
associés à un nombre important de déclarations.
ƒ Planification de villes : identification de groupes
d’habitations suivant le type d’habitation, valeur,
localisation géographique, …
ƒ Médecine : Localisation de tumeurs dans le cerveau
ƒ Nuage de points du cerveau fournis par le neurologue
ƒ Identification des points définissant une tumeur
Exemple: segmentation de marchés
Mesure de la similarité

ƒ Il n’y a pas de définition unique

de la similarité entre objets
ƒ Différentes mesures de
distances d(x,y)

ƒ La définition de la similarité
entre objets dépend de :
ƒ Le type des données
considérées
ƒ Le type de similarité
recherchée
 Choix de la distance

ƒ Propriétés d’une distance :

1. d ( x , y ) ≥ 0
2. d ( x , y ) = 0 iff x = y
3. d ( x , y ) = d ( y , x )
4. d ( x , z ) ≤ d ( x , y ) + d ( y , z )

ƒ Définir une distance sur chacun des champs

ƒ Champs numériques : d(x,y) = |x-y|, d(x,y)= |x-y|/dmax
(distance normalisée).
ƒ Exemple : Age, taille, poids, …
 Distance – Données numériques

ƒ Combiner les distances : Soient x=(x1,…,xn) et y=(y1, …,yn)

ƒ Exemples numériques :
n
ƒ Distance euclidienne : d(x, y)= ∑(xi − yi )2

i=1
n
ƒ Distance de Manhattan : d(x, y)= ∑x−y
i=1
i i

q n q
−y
ƒ Distance de Minkowski : d(x, y)= ∑
i =1
xi i

k=1 : distance de Manhattan.

k=2 : distance euclidienne
 Choix de la distance

ƒ Champs discrets :

ƒ Données binaires : d(0,0)=d(1,1)=0, d(0,1)=d(1,0)=1

ƒ Donnée énumératives : distance nulle si les valeurs sont

égales et 1 sinon.

ƒ Donnée énumératives ordonnées : idem. On peut définir

une distance utilisant la relation d’ordre.

ƒ Données de types complexes : textes, images, données

génétiques, ...
 Distance – Données binaires

Object j
Table de contingence 1 0 sum
(dissimilarité)
1 a b a +b
Object i 0 c d c+d
sum a + c b + d p

ƒ Coefficient de correspondance simple (similarité

invariante, si la variable binaire est symétrique)
symétrique :
d (i, j ) = b+c
a+b+c+d
ƒ Coefficient de Jaccard (similarité non invariante,
si la variable binaire est asymétrique):
asymétrique
d (i, j ) = b+c
a+b+c
 Distance – Données binaires

Exemple : dissimilarité entre variables binaires

• Table de patients
Nom Sexe Fièvre Toux Test-1 Test-2 Test-3 Test-4
Jack M Y N P N N N
Mary F Y N P N P N
Jim M Y P N N N N

• 8 attributs, avec
ƒ Sexe un attribut symétrique, et
ƒ Les attributs restants sont asymétriques
(test VIH, …)
 Distance – Données binaires

ƒ Les valeurs Y et P sont initialisées à 1, et la

valeur N à 0.
ƒ Calculer la distance entre patients, basée
sur le coefficient de Jaccard.

0 +1
d ( jack , mary ) = = 0.33
2 + 0 +1
1+1
d ( jack , jim ) = = 0.67
1+1+1
1+ 2
d ( jim , mary ) = = 0.75
1+1+ 2
 Distance – Données énumératives

ƒ Généralisation des variables binaires, avec

états e.g., rouge, jaune, bleu, vert
plus de 2 états,

ƒ Méthode 1: correpondance simple

ƒ m: # de correspondances, p: # total de
variables

d (i, j ) = p − m
p
 Distance – Données mixtes

ƒ Exemple : (Age, Propriétaire résidence principale, montant

des mensualités en cours)

ƒ x=(30,1,1000), y=(40,0,2200), z=(45,1,4000)

ƒ d(x,y)=sqrt( (10/15)2 + 12 + (1200/3000)2) = 1.27
ƒ d(x,z)= sqrt( (15/15)2 + 02 + (3000/3000)2) = 1.41
ƒ d(y,z)= sqrt( (5/15)2 + 12 + (1800/3000)2) = 1.21
ƒ plus proche voisin de x = y

ƒ Distances normalisées.
ƒ Sommation : d(x,y)=d1(x1,y1) + … + dn(xn,yn)
 Données mixtes – Exemple 1

ƒ Base de données « Cancer du sein »

http://www1.ics.uci.edu/~mlearn/MLSummary.html
ƒ #instances = 286 (Institut Oncologie, Yugoslavie)
ƒ # attributs = 10
ƒ Classe : no-recurence-events, recurrence-events
ƒ Age : 10-19, 20-29, 30-39, 40-49, …, 90-99
ƒ Menopause : Lt40, Ge40, premeno
ƒ Taille de la tumeur : 0-4, 5-9, 10-14, …, 55-59
ƒ Inv-nodes : 0-2, 3-5, 6-8, …, 36-39 (ganglions lymphatiques)
ƒ Node-caps : Oui, Non
ƒ Deg-malig : 1, 2, 3 (Dégré de malignité)
ƒ Sein : Gauche, Droit
ƒ Breast-quad : left-up, left-low, right-up, right-low, central
ƒ Irradiation : Oui, Non
 Données mixtes – Exemple 2

ƒ Base de données « Diabète » : Diagnostic (OMS)

http://www1.ics.uci.edu/~mlearn/MLSummary.html
ƒ #instances = 768 (Arizona, USA)
ƒ # attributs = 8
ƒ Nombre de grossesses
ƒ Concentration du taux de glucose dans le plasma
ƒ Pression sanguine diastolique (mm Hg)
ƒ Epaisseur de la graisse du triceps (mm)
ƒ Taux d’insuline après 2 heures (repas) (mu U/ml)
ƒ Indice de masse corporelle (poids en kg / (taille en m)^2)
ƒ Fonction « Diabete pedigree »
ƒ Age (ans)
ƒ Classe (Positif ou Négatif)
Méthodes de Clustering

ƒ Méthode de partitionnement (K-

moyennes)
ƒ Méthodes hiérarchiques (par
agglomération)
ƒ Méthode par voisinage dense

ƒ Caractéristiques
ƒ Apprentissage non supervisé
(classes inconnues)
ƒ Pb : interprétation des
clusters identifiés
Méthodes de clustering - Caractéristiques

ƒ Extensibilité
ƒ Abilité à traiter différents
types de données
ƒ Découverte de clusters de
différents formes
ƒ Connaissances requises
(paramètres de l’algorithme)
ƒ Abilité à traiter les données
bruitées et isolées.
 Algorithme des k-moyennes (K-means)

ƒ Entrée : un échantillon de m enregistrements x1, …, xm

ƒ 1. Choisir k centres initiaux c1, …, ck
ƒ 2. Répartir chacun des m enregistrements dans le groupe
i dont le centre ci est le plus proche.
ƒ 3. Si aucun élément ne change de groupe alors arrêt et
sortir les groupes
ƒ 4. Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.
ƒ Aller en 2.
Illustration (1)

Centres
initiaux
Illustration (2)

Nouveaux
centres
Illustration (3)

Centres
finaux
 Algorithme des k-moyennes : Exemple

ƒ 8 points A, …, H de l ’espace euclidéen 2D. k=2 (2 groupes)

ƒ Tire aléatoirement 2 centres : B et D choisis.
points Centre Centre Centre
D(2,4), D(2,4), J(5/3,10/3),
B(2,2) I(27/7,17/7) K(24/5,11/5)

A(1,3) B D J
B(2,2) B I J
C(2,3) B D J
D(2,4) D D J
E(4,2) B I K
F(5,2) B I K
G(6,2) B I K
H(7,3) B I K
K-moyennes : Avantages

ƒ Relativement extensible dans le

traitement d’ensembles de taille
importante
ƒ Relativement efficace : O(t.k.n),
où n représente # objets, k #
clusters, et t # iterations.
Normalement, k, t << n.
ƒ Produit généralement un optimum
local ; un optimum global peut être
obtenu en utilisant d’autres
techniques telles que :
algorithmes génétiques, …
K-moyennes : Inconvénients

ƒ Applicable seulement dans le cas où la

moyenne des objets est définie
ƒ Besoin de spécifier k, le nombre de
clusters, a priori
ƒ Incapable de traiter les données
bruitées (noisy).
ƒ Non adapté pour découvrir des
clusters avec structures non-convexes,
et des clusters de tailles différentes
ƒ Les points isolés sont mal gérés
(doivent-ils appartenir obligatoirement
à un cluster ?) - probabiliste
K-moyennes : Variantes

ƒ Sélection des centres initiaux

ƒ Calcul des similarités
ƒ Calcul des centres (K-medoids : [Kaufman
& Rousseeuw’87] )
ƒ GMM : Variantes de K-moyennes basées
sur les probabilités
ƒ K-modes : données catégorielles
[Huang’98]
ƒ K-prototype : données mixtes (numériques
et catégorielles)
Méthodes hiérarchiques

ƒ Une méthode hiérarchique :

construit une hiérarchie de clusters,
non seulement une partition unique
des objets.
ƒ Le nombre de clusters k n’est pas
exigé comme donnée
ƒ Utilise une matrice de distances
comme critère de clustering
ƒ Une condition de terminaison peut
être utilisée (ex. Nombre de
clusters)
 Méthodes hiérarchiques

ƒ Entrée : un échantillon de m enregistrements x1, …, xm

ƒ 1. On commence avec m clusters (cluster = 1
enregistrement)
ƒ 2. Grouper les deux clusters les plus « proches ».
ƒ 3. S’arrêter lorsque tous les enregistrements sont
membres d’un seul groupe
ƒ 4. Aller en 2.
Arbre de clusters : Exemple

Step 0 Step 1 Step 2 Step 3 Step 4

a
ab
b abcde
c
cde
d
de
e
 Arbre de clusters
ƒ Résultat : Graphe hiérarchique qui peut être coupé à un
niveau de dissimilarité pour former une partition.

ƒ La hiérarchie de clusters est

représentée comme un arbre de
clusters, appelé dendrogramme
ƒ Les feuilles de l’arbre représentent
les objets
ƒ Les noeuds intermédiaires de l’arbre
représentent les clusters
 Distance entre clusters

ƒ Distance entre les centres des clusters (Centroid

Method)
ƒ Distance minimale entre toutes les paires de données des
2 clusters (Single Link Method) d (i, j ) = min x∈Ci , y∈Cj { d ( x, y) }

ƒ Distance maximale entre toutes les paires de données

des 2 clusters (Complete Link Method)
d (i, j ) = max x∈Ci , y∈Cj { d ( x, y ) }

ƒ Distance moyenne entre toutes la paires

d’enregistrements (Average Linkage) d (i, j ) = avg x∈Ci , y∈Cj { d ( x, y ) }
Méthodes hiérarchiques :
Avantages

ƒ Conceptuellement simple

ƒ Propriétés théoriques sont

bien connues

ƒ Quand les clusters sont

groupés, la décision est
définitive => le nombre
d’alternatives différentes à
à examiner est réduit
Méthodes hiérarchiques :
Inconvénients

ƒ Groupement de clusters est

définitif => décisions
erronnées sont impossibles à
modifier ultérieurement

ƒ Méthodes non extensibles

pour des ensembles de
données de grandes tailles
 Méthodes basées sur la densité
ƒ Pour ce types de problèmes, l’utilisation de mesures
de similarité (distance) est moins efficace que
l’utilisation de densité de voisinage.
 Méthodes basées sur la densité
ƒ Minimiser la distance inter-clusters n’est pas
toujours un bon critère pour reconnaître des
«formes » (applications géographiques,
reconnaissance de formes – tumeurs, …).
Dist=18

Dist=15.3
Méthodes basées sur la densité (1)

ƒ Soit d* un nombre réel positif

ƒ Si d(P,Q)<=d*, Alors P et Q appartiennent au

même cluster

ƒ Si P et Q appartiennent au même cluster, et

d(Q,R)<=d*, Alors P et R appartiennent au
même cluster
Méthodes basées sur la densité (2)

ƒ Soit e* un nombre réel positif

ƒ Un point P est dense ssi |{Q/d(P,Q)<=d*}|>=e*
ƒ Si P et Q appartiennent au même cluster, et
d(Q,R)<=d* et Q est dense, Alors P et R
appartiennent au même cluster
ƒ Les points non-denses sont appelés points de
« bordure ».
ƒ Les points en dehors des clusters sont
appelés « bruits ».
 Méthodes basées sur la densité

d* e*=4

Q
S R

• Points noirs sont denses ; les autres ne sont pas denses

• Pour montrer que P et S appartiennent au même cluster, il suffit de
montrer que P et R appartiennent au même cluster. Pour le
montrer pour P et R, il suffit de le montrer pour P et Q …
 Méthodes basées sur la densité

ƒ Deux clusters sont trouvés

ƒ Deux points sont des « bruits »
ƒ Trois points sont des « bordures »
Etude de cas réel : Génomique

Sélection d’attributs
+ Clustering

LIFL : Equipe OPAC

I.B.L
 Le contexte

ƒ Génopole de Lille : Aspect génétique des

maladies multifactorielles
ƒ Collaboration avec l’I.B.L. (Institut de
Biologie de Lille) laboratoire des
maladies multifactorielles (UPRES-A
8090) : diabète, obésité
ƒ Génération de gros volumes de données :
outil d’aide à l’interprétation des
résultats
 Etudes de l’IBL
ƒ Etudes de type familial (parents, enfants) –
Prélévement d’ADN
ƒ Analyse de liaison : co-transmission d’un gène
ƒ Comparaison de gènes entre paires d’individus
d’une même famille

Objectif :
Localiser un ou plusieurs gènes de
prédisposition pour la maladie
 Problème posé

ƒ Très grand nombre de données générées

ƒ (~ 1 000 points de comparaison, 200 familles)

ƒ Méthodes statistiques limitées pour

étudier la corrélation entre gènes

Besoin d’un outil d’extraction

de connaissances : Data Mining
 Contexte
Hypothèses de travail :
ƒ un cas particulier de Data Mining
ƒ les données fournies par l’IBL contiennent de
nombreux attributs
ƒ existence de données manquantes ou incertaines
ƒ contexte d ’apprentissage non supervisé
Objectif :
ƒ connaître les classes d ’attributs provoquant la
maladie
ƒ connaître les corrélations entre les attributs
 Méthodologie adoptée
Réalisation :
• d’une sélection d ’attributs : Réduire le nombre
d ’attributs pour améliorer la classification
• d’un clustering

Sélection Classes
d ’attributs Clustering

m attributs
N attributs N>>m
 K-moyennes

ƒ Sans sélection d ’attributs :

ƒ 400 attributs pour 200 objets,
ƒ temps de calcul > 7500 min. (>125 h.),
ƒ résultats inexploitables
ƒ Avec sélection d ’attributs :
ƒ une dizaine d ’attributs pour 200 objets,
ƒ temps de calcul entre 3 minutes et 15 minutes,
ƒ résultats exploitables.
 Workshop GAW11 de 1998

ƒ Données simulées dont on connaît les

résultats
ƒ Résultats à trouver :

A B
C
D
E1
 Résultats

Résultats obtenus sur le workshop GAW11 de 1998

ƒ Exemple d ’ensembles d ’attributs sélectionnés
(Support trouvé > 0.65) :
ƒ 81 85, 402 407, 224 229 (Locus C) , 308 313, 190
195, 374 379 (Locus B)
ƒ Exemple de clustering

E1 C E2 B

Classe 1 Classe 2
 Conclusion

ƒ Bilan
ƒ Compréhension et modélisation d ’un
problème complexe
ƒ Sélection d ’attributs : sélection de locus
impliqués dans la maladie
ƒ Clustering : les ensembles finaux sont
trouvés lorsqu ’il y a peu d ’erreurs dans le
choix des attributs sélectionnés
Clustering – Résumé (1)
ƒ Le clustering groupe des objets
en se basant sur leurs
similarités.
ƒ Le clustering possède plusieurs
applications.
ƒ La mesure de similarité peut
être calculée pour différents
types de données.
ƒ La sélection de la mesure de
similarité dépend des données
utilisées et le type de similarité
recherchée.
Clustering – Résumé (2)

ƒ Les méthodes de clustering

peuvent être classées en :
ƒ Méthodes de
partitionnement,
ƒ Méthodes hiérarchiques,
ƒ Méthodes à densité de
voisinage.
ƒ Plusieurs travaux de
recherche sur le clustering
en cours et en perspective.
ƒ Plusieurs applications en
perspective : Génomique,
Environnement, …
 Références

ƒ M. R. Anderberg. Cluster Analysis for Applications.

Academic Press, 1973.
ƒ P. Arabie, L. J. Hubert, and G. De Soete. Clustering
and Classification. World Scientific, 1996
ƒ A. K. Jain and R. C. Dubes. Algorithms for Clustering
Data. Prentice Hall, 1988
ƒ L. Kaufman and P. J. Rousseeuw. Finding Groups in
Data: an Introduction to Cluster Analysis. John
Wiley & Sons, 1990.
Classification
 Sommaire

ƒ Définition
ƒ Validation d’une classification
Sommaire (accuracy)
ƒ K-NN (plus proches voisins)
ƒ Arbres de décision
ƒ Réseaux de neurones
ƒ Autres méthodes de
classification
ƒ Etude de cas réel :
Protéomique
ƒ Résumé
 Classification

ƒ Elle permet de prédire si un élément est membre

d’un groupe ou d ’une catégorie donné.
ƒ Classes
ƒ Identification de groupes avec des profils
particuliers
ƒ Possibilité de décider de l’appartenance d’une
entité à une classe

ƒ Caractéristiques
ƒ Apprentissage supervisé : classes connues à
l’avance
ƒ Pb : qualité de la classification (taux d’erreur)
ƒ Ex : établir un diagnostic (si erreur !!!)
Classification - Applications

ƒ Accord de crédit
ƒ Marketing ciblé
Applications
ƒ Diagnostic médical
ƒ Analyse de l’effet d’un
traitement
ƒ Détection de fraudes
fiscales
ƒ etc.
 Processus à deux étapes

Etape 1 :
Construction du modèle à
processus partir de l’ensemble
à 2 étapes d’apprentissage (training
set)

Etape 2 :
Utilisation du modèle :
tester la précision du
modèle et l’utiliser dans la
classification de nouvelles
données
 Construction du modèle

ƒ Chaque instance est supposée

appartenir à une classe
prédéfinie
Etape 1 ƒ La classe d’une instance est
déterminée par l’attribut ”classe”
ƒ L’ensemble des instances
d’apprentissage est utilisé dans la
construction du modèle
ƒ Le modèle est représenté par des
règles de classification, arbres
de décision, formules
mathématiques, ...
 Utilisation du modèle

ƒ Classification de nouvelles
instances ou instances inconnues

Etape 2
ƒ Estimer le taux d’erreur du
modèle
ƒ la classe connue d’une instance
test est comparée avec le
résultat du modèle
ƒ Taux d’erreur = pourcentage de
tests incorrectement classés
par le modèle
 Validation de la Classification
(accuracy)

Estimation des taux d’erreurs :

ƒ Partitionnement : apprentissage et test (ensemble
de données important)
ƒ Utiliser 2 ensembles indépendents, e.g.,
ensemble d’apprentissage (2/3), ensemble test
(1/3)

Apprentissage Dt Validation D\Dt

 Validation de la Classification
(accuracy)

ƒ Validation croisée (ensemble de données modéré)

ƒ Diviser les données en k sous-ensembles
ƒ Utiliser k-1 sous-ensembles comme données
d’apprentissage et un sous-ensemble comme données test

D1 D2 D3 D4

D1 D2 D3 D4 D1 D2 D3 D4

D1 D2 D3 D4 D1 D2 D3 D4

ƒ Bootstrapping : n instances test aléatoires (ensemble de

données réduit)
 Exemple : Construction du modèle
Algorithmes
Données
Classification
Apprentissage

Nom Rang Année Titulaire

Mary Assistant Prof 3 non
Modèle
James Assistant Prof 7 oui
Bill Professor 2 oui
John Associate Prof 7 oui Si Rang = ‘Professor’
Mark Assistant Prof 6 non Ou Année > 6
Annie Associate Prof 3 non Alors Titulaire = Oui
 Exemple : Utilisation du modèle

Classifier

Données
Taux d’erreur
Test
du modèle ?

Nom Rang Année Titulaire

Tom Assistant Prof 2 non
Lisa Associate Prof 7 non
Jack Professor 5 oui
Ann Assistant Prof 7 oui
 Exemple : Utilisation du modèle

Classifier

Donnée
inconnue Titulaire ?

Nom Rang Année Titulaire

Jeff Professor 4 ? Oui
Paul Associate Prof 7 ? Oui
 Evaluation des
méthodes de classification

ƒ Taux d’erreur (Accuracy)

ƒ Temps d’exécution (construction,
utilisation)
ƒ Robustesse (bruit, données
manquantes,...)
ƒ Extensibilité
ƒ Interprétabilité
ƒ Simplicité
Méthodes de Classification

ƒ Méthode K-NN (plus proche

voisin)
ƒ Arbres de décision
ƒ Réseaux de neurones
ƒ Classification bayésienne

ƒ Caractéristiques
ƒ Apprentissage supervisé
(classes connues)
 Méthode des plus proches voisins

ƒ Méthode dédiée à la classification (k-NN : nearest

neighbor).
ƒ Méthode de raisonnement à partir de cas : prendre
des décisions en recherchant un ou des cas similaires
déjà résolus.
ƒ Pas d’étape d ’apprentissage : construction d ’un
modèle à partir d’un échantillon d ’apprentissage
(réseaux de neurones, arbres de décision, …).
ƒ Modèle = échantillon d’apprentissage + fonction de
distance + fonction de choix de la classe en fonction
des classes des voisins les plus proches.
 Algorithme kNN (K-nearest neighbors)

ƒ Objectif : affecter une classe à une nouvelle instance

ƒ donnée : un échantillon de m enregistrements classés
(x, c(x))
ƒ entrée : un enregistrement y
ƒ 1. Déterminer les k plus proches enregistrements
de y
ƒ 2. combiner les classes de ces k exemples en une
classe c
ƒ sortie : la classe de y est c(y)=c
 Algorithme kNN : sélection de la classe

ƒ Solution simple : rechercher le cas le plus proche et

prendre la même décision (Méthode 1-NN).
ƒ Combinaison des k classes :
ƒ Heuristique : k = nombre d ’attributs + 1
ƒ Vote majoritaire : prendre la classe majoritaire.
ƒ Vote majoritaire pondéré : chaque classe est pondérée.
Le poids de c(xi) est inversement proportionnel à la
distance d(y,xi).

ƒ Confiance : Définir une confiance dans la classe attribuée

= rapport entre les votes gagnants et le total des votes.
Illustration

Voisinage
5 de la classe
3 de la classe

=
 Algorithme kNN : critique

ƒ Pas d’apprentissage : introduction de nouvelles données ne

nécessite pas la reconstruction du modèle.
ƒ Clarté des résultats
ƒ Tout type de données
ƒ Nombre d’attributs
ƒ Temps de classification : -
ƒ Stocker le modèle : -
ƒ Distance et nombre de voisins : dépend de la distance, du
nombre de voisins et du mode de combinaison.
 Arbres de décision

ƒ Génération d’arbres de décision à partir des données

ƒ Arbre = Représentation graphique d’une procédure de
classification

Accord d’un prêt bancaire

MS : moyenne solde compte courant Un arbre de décision est un
MS>5000 arbre où :
Non Oui
ƒ Noeud interne = un
Age>25 Oui attribut
Oui Non
ƒ Branche d’un noeud = un
Non
Autres comptes test sur un attribut
Oui Non
ƒ Feuilles = classe donnée
Oui Non
 Arbre de décision - Exemple

Outlook Temperature Humidity Windy Class

sunny hot high false N
sunny hot high true N
Ensemble overcast hot high false P
d’apprentissage rain mild high false P
rain cool normal false P
rain cool normal true N
overcast cool normal true P
sunny mild high false N
sunny cool normal false P
rain mild normal false P
sunny mild normal true P
overcast mild high true P
overcast hot normal false P
rain mild high true N
Jouer au tennis ?
 Arbre de décision - Exemple

Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes
 Exemple – Jouer au tennis ?

Outlook

Sunny Overcast Rain

Humidity Chaque noeud interne teste un attribut

High Normal Chaque branche correspond à une

valeur de l’attribut
No Yes Chaque feuille représente une classe
Arbres de décision – Exemple

Risque - Assurances
Age < 27.5
Tid Age Car Type Class
0 23 Family High
1 17 Sports High CarType ∈ {Sports}

2 43 Sports High
High
3 68 Family Low
4 32 Truck Low
5 20 Family High
High Low

Age=40, CarType=Family ⇒ Class=Low

Numérique Enumératif
Des arbres de décision aux règles

Age < 27.5

1) Age < 27.5 ⇒ High

CarType ∈ {Sports}
2) Age >= 27.5 and
CarType = Sports ⇒ High
High
3) Age >= 27.5 and
CarType ≠ Sports ⇒ High
High Low
 Arbres de décision – Exemple
Détection de fraudes fiscales
atif atif ue Attributs significatifs
r r iq
m
é
m
é ér se
u u m as Ristourne
én én nu cl
Oui Non
Id Ristourne Situation Impôt
famille revenu Fraude Non Situation
1 Oui Célibat. 125K Non Célibat, Divorcé Marié

2 Non Marié 100K Non Impôt Non

3 Non Célibat. 70K Non < 80K >= 80K
4 Oui Marié 120K Non
Non Oui
5 Non Divorcé 95K Oui
6 Non Marié 60K Non ƒ L’attribut significatif à un noeud est
déterminé en se basant sur l’indice
7 Oui Divorcé 220K Non
Gini.
8 Non Célibat. 85K Oui ƒ Pour classer une instance : descendre
9 Non Marié 75K Non dans l’arbre selon les réponses aux
différents tests. Ex = (Ristourne=Non,
10 Non Célibat. 90K Oui
10
Situation=Divorcé, Impôt=100K) Î Oui
 De l’arbre de décision aux règles
de classification

ƒ une règle est générée pour

outlook
chaque chemin de l’arbre (de
sunny
overcast
rain
la racine à une feuille)
humidity P windy ƒ Les paires attribut-valeur
high normal false
d’un chemin forment une
true
conjonction
ƒ Le noeud terminal
N P N P

représente la classe prédite

Si outlook=sunny
ƒ Les règles sont
Et humidity=normal
généralement plus faciles à
Alors play tennis comprendre que les arbres
 Des arbres de décision aux règles

Arbre de décision = Système de règles exhaustives et

mutuellement exclusives
1) Ristourne = Oui ⇒ Non
Ristourne
Oui Non
2) Ristourne = Non et
Situation in {Célibat., Divorcé}
Non Situation et Impôt < 80K ⇒ Non
Célibat., Divorcé Marié

Impôt Non 3) Ristourne = Non et

< 80K >= 80K Situation in {Célibat., Divorcé}
et Impôt >= 80K ⇒ Oui
Non Oui

4) Ristourne = Non et
Situation in {Marié} ⇒ Non
 Des arbres de décision aux règles

Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes
R1: If (Outlook=Sunny) ∧ (Humidity=High) Then PlayTennis=No
R2: If (Outlook=Sunny) ∧ (Humidity=Normal) Then PlayTennis=Yes
R3: If (Outlook=Overcast) Then PlayTennis=Yes
R4: If (Outlook=Rain) ∧ (Wind=Strong) Then PlayTennis=No
R5: If (Outlook=Rain) ∧ (Wind=Weak) Then PlayTennis=Yes
Génération de l’arbre de décision

Deux phases dans la génération de

l’arbre :

ƒ Construction de l’arbre
ƒ Arbre peut atteindre une taille
élevée
ƒ Elaguer l’arbre (Pruning)
ƒ Identifier et supprimer les
branches qui représentent du
“bruit” Æ Améliorer le taux
d’erreur
 Algorithmes de classification

ƒ Construction de l’arbre
ƒ Au départ, toutes les instances d’apprentissage
sont à la racine de l’arbre
ƒ Sélectionner un attribut et choisir un test de
séparation (split) sur l’attribut, qui sépare le
“mieux” les instances.
La sélection des attributs est basée sur une
heuristique ou une mesure statistique.
ƒ Partitionner les instances entre les noeuds fils
suivant la satisfaction des tests logiques
 Algorithmes de classification

ƒ Traiter chaque noeud fils de façon récursive

ƒ Répéter jusqu’à ce que tous les noeuds soient des
terminaux. Un noeud courant est terminal si :
ƒ Il n’y a plus d’attributs disponibles
ƒ Le noeud est “pur”, i.e. toutes les instances
appartiennent à une seule classe,
ƒ Le noeud est “presque pur”, i.e. la majorité des instances
appartiennent à une seule classe (Ex : 95%)
ƒ Nombre minimun d’instances par branche (Ex :
algorithme C5 évite la croissance de l’arbre, k=2 par
défaut)
ƒ Etiqueter le noeud terminal par la classe
majoritaire
 Algorithmes de classification

ƒ Elaguer l’arbre obtenu (pruning)

ƒ Supprimer les sous-arbres qui n’améliorent pas
l’erreur de la classification (accuracy) Î arbre
ayant un meilleur pouvoir de généralisation,
même si on augmente l’erreur sur l’ensemble
d’apprentissage
ƒ Eviter le problème de sur-spécialisation (over-
fitting), i.e., on a appris “par coeur” l’ensemble
d’apprentissage, mais on n’est pas capable de
généraliser
Sur-spécialisation - arbre de
décision

ƒ L’arbre généré peut sur-

spécialiser l’ensemble
d’apprentissage
ƒ Plusieurs branches
ƒ Taux d’erreur important pour les
instances inconnues
ƒ Raisons de la sur-spécialisation
ƒ bruits et exceptions
ƒ Peu de donnée d’apprentissage
ƒ Maxima locaux dans la recherche
gloutonne
Overfitting dans les arbres de décision
Comment éviter l’overfitting ?

ƒ Deux approches :

ƒ Pré-élagage : Arrêter de
façon prématurée la
construction de l’arbre

ƒ Post-élagage : Supprimer des

branches de l’arbre complet
(“fully grown”)
ƒ Convertir l’arbre en règles ;
élaguer les règles de façon
indépendante (C4.5)
 Construction de l’arbre -
Synthèse

ƒ Evaluation des différents branchements pour

tous les attributs
ƒ Sélection du “meilleur” branchement “et de
l’attribut “gagnant”
ƒ Partitionner les données entre les fils
ƒ Construction en largeur (C4.5) ou en profondeur
(SPLIT)
ƒ Questions critiques :
ƒ Formulation des tests de branchement
ƒ Mesure de sélection des attributes
 Exemple : Jouer au tennis ?

Outlook Temperature Humidity Windy Class

sunny hot high false N
sunny hot high true N
Ensemble overcast hot high false P
d’apprentissage rain mild high false P
rain cool normal false P
rain cool normal true N
overcast cool normal true P
sunny mild high false N
sunny cool normal false P
rain mild normal false P
sunny mild normal true P
overcast mild high true P
overcast hot normal false P
rain mild high true N
 Arbre de décision obtenu avec
ID3 (Quinlan 86)
Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes
 Arbre de décision obtenu avec
ID3 (Quinlan 86)
Outlook Temperature Humidity Wind PlayTennis
Sunny Hot High Weak ?No
Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes
Arbre de décision et conjonction

Outlook=Sunny ∧ Wind=Weak

Outlook

Sunny Overcast Rain

Wind No No

Strong Weak

No Yes
Arbre de décision et disjonction

Outlook=Sunny ∨ Wind=Weak

Outlook

Sunny Overcast Rain

Yes Wind Wind

Strong Weak Strong Weak

No Yes No Yes
 Arbre de décision et XOR

Outlook=Sunny XOR Wind=Weak

Outlook

Sunny Overcast Rain

Wind Wind Wind

Strong Weak Strong Weak Strong Weak

Yes No No Yes No Yes

 Arbre de décision et conjonction
• arbre de décision représente des disjonctions de conjonctions
Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

(Outlook=Sunny ∧ Humidity=Normal)
∨ (Outlook=Overcast)
∨ (Outlook=Rain ∧ Wind=Weak)
Algorithmes pour les arbres de
décision

ƒ Algorithme de base
ƒ Construction récursive d’un arbre de
manière “diviser-pour-régner” descendante
ƒ Attributs considérés énumératifs
ƒ Glouton (piégé par les optima locaux)

ƒ Plusieurs variantes : ID3, C4.5, CART, CHAID

ƒ Différence principale : mesure de sélection
d’un attribut – critère de branchement
(split)
Mesures de sélection d’attributs

ƒ Gain d’Information (ID3,

C4.5)

ƒ Indice Gini (CART)

ƒ Table de contingence
statistique χ2 (CHAID)

ƒ G-statistic
Bonne sélection et branchement ?
CarType
Low Risk
High Risk

Sports

< 25 Age
 Gain d’information

ƒ Sélectionner l’attribut avec le plus grand gain

d’information
ƒ Soient P et N deux classes et S un ensemble
d’instances avec p éléments de P et n éléments
de N
ƒ L’information nécessaire pour déterminer si
une instance prise au hasard fait partie de P
ou N est (entropie) :
p p n n
I ( p, n) = − log 2 − log 2
p+n p+n p+n p+n
 Entropie

ƒ S est l’ensemble d’apprentissage

ƒ p+ est la proportion d’exemples positifs (P)
ƒ p- est la proportion d’exemples négatifs (N)
ƒ Entropie mesure l’impureté de S
ƒ Entropie(S) = -p+ log2 p+ - p- log2 p-
 Gain d’information

ƒ Soient les ensembles {S1, S2 , …, Sv} formant une

partition de l’ensemble S, en utilisant l’attribut A
ƒ Toute partition Si contient pi instances de P et ni
instances de N
ƒ L’entropie,
L’entropie ou l’information nécessaire pour classifier
les instances dans les sous-arbres Si est :
ν p +n
E ( A) = ∑ i i I ( pi , ni )
i =1 p + n

ƒ Le gain d’information par rapport au branchement sur

A est
Gain ( A ) = I ( p , n ) − E ( A )

ƒ Choisir l’attribut qui maximise le gain Æ besoin

d’information minimal
Gain d’information - Exemple

Hypothèses :

• Classe P : jouer_tennis =
“oui”
• Classe N : jouer_tennis =
“non”
• Information nécessaire
pour classer un exemple
donné est :

I ( p, n) = I (9,5) = 0.940
 Gain d’information - Exemple

Calculer l’entropie pour

outlook pi ni I(pi, ni)
l’attribut outlook :
sunny 2 3 0,971
overcast 4 0 0
rain 3 2 0,971

On a 5 4 5
E (outlook ) = I ( 2,3) + I ( 4,0) + I (3,2) = 0.694
14 14 14
Alors Gain (outlook ) = I (9,5) − E (outlook ) = 0.246

De manière similaire Gain (temperatur e) = 0.029

Gain ( humidity ) = 0.151
Gain ( windy ) = 0.048
 Quel Attribut est ”meilleur” ?

[29+,35-] A1=? A2=? [29+,35-]

True False True False

[21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

 Gain d’information - Exemple
ƒ Gain(S,A) : réduction attendue de l’entropie dûe
au branchement de S sur l’attribut A

Gain(S,A)=Entropie(S) - ∑v∈values(A) |Sv|/|S| Entropie(Sv)

Entropie([29+,35-]) = -29/64 log2 29/64 – 35/64 log2 35/64

= 0.99
[29+,35-] A1=? A2=? [29+,35-]

True False True False

[21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

 Gain d’information - Exemple

Entropie([21+,5-]) = 0.71 Entropie([18+,33-]) = 0.94

Entropie([8+,30-]) = 0.74 Entropie([8+,30-]) = 0.62
Gain(S,A1)=Entropie(S) Gain(S,A2)=Entropie(S)
-26/64*Entropie([21+,5-]) -51/64*Entropie([18+,33-])
-38/64*Entropie([8+,30-]) -13/64*Entropie([11+,2-])
=0.27 =0.12

[29+,35-] A1=? A2=? [29+,35-]

True False True False

[21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

 Exemple d’apprentissage
Day Outlook Temp. Humidit Wind Play Tennis
D1 Sunny Hot y
High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Weak Yes
D8 Sunny Mild High Weak No
D9 Sunny Cold Normal Weak Yes
D10 Rain Mild Normal Strong Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No
 Sélection de l’attribut suivant
S=[9+,5-] S=[9+,5-]
E=0.940 E=0.940
Humidity Wind

High Normal Weak Strong

[3+, 4-] [6+, 1-] [6+, 2-] [3+, 3-]

E=0.985 E=0.592 E=0.811 E=1.0
Gain(S,Humidity) Gain(S,Wind)
=0.940-(7/14)*0.985 =0.940-(8/14)*0.811
– (7/14)*0.592 – (6/14)*1.0
=0.151 =0.048
Sélection de l’attribut suivant
S=[9+,5-]
E=0.940
Outlook

Over
Sunny Rain
cast

[2+, 3-] [4+, 0] [3+, 2-]

E=0.971 E=0.0 E=0.971
Gain(S,Outlook)
=0.940-(5/14)*0.971
-(4/14)*0.0 – (5/14)*0.0971
=0.247
 Algorithme ID3
[D1,D2,…,D14] Outlook
[9+,5-]

Sunny Overcast Rain

Ssunny=[D1,D2,D8,D9,D11] [D3,D7,D12,D13] [D4,D5,D6,D10,D14]

[2+,3-] [4+,0-] [3+,2-]
? Yes ?
Gain(Ssunny , Humidity)=0.970-(3/5)0.0 – 2/5(0.0) = 0.970
Gain(Ssunny , Temp.)=0.970-(2/5)0.0 –2/5(1.0)-(1/5)0.0 = 0.570
Gain(Ssunny , Wind)=0.970= -(2/5)1.0 – 3/5(0.918) = 0.019
 Algorithme ID3
Outlook

Sunny Overcast Rain

Humidity Yes Wind

[D3,D7,D12,D13]

High Normal Strong Weak

No Yes No Yes

[D1,D2] [D8,D9,D11] [D6,D14] [D4,D5,D10]

 Indice Gini

ƒ Utiliser l’indice Gini pour un partitionnement pur

c
Gini ( S ) = 1 − ∑ pi2
i =1

n1 n
Gini ( S1 , S 2 ) = Gini ( S1 ) + 2 Gini ( S 2 )
n n
ƒ pi est la fréquence relative de la classe c dans S
ƒ Si S est pur (classe unique), Gini(S) = 0
ƒ Gini(S1,S2) = Gini pour une partition de S en deux sous-
ensembles S1 et S2 selon un test donné.
ƒ Trouver le branchement (split-point) qui minimise
l’indice Gini
ƒ Nécessite seulement les distributions de classes
 Indice Gini - Exemple

Fraude
Situation famille Situation famille Pas fraude

Revenu Revenu

Calcul de Gini nécessite une Matrice de dénombrement

Non Oui Non Oui
<80K 14 9 M 5 23
>80K 1 18 F 10 4

Gini(split) = 0.31 Gini(split) = 0.34

 Attributs énumératifs – indice GINI

ƒ Pour chaque valeur distincte, calculer le nombre

d’instances de chaque classe
ƒ Utiliser la matrice de dénombrement pour la prise
de décision

Partage en plusieurs Partage en deux “classes”

classes (trouver la meilleure partition de valeurs)

CarType CarType CarType

Family Sports Luxury {Sports, {Family,
{Family} {Sports}
Luxury} Luxury}
C1 1 2 1 C1 3 1 C1 2 2
C2 4 1 1 C2 2 4 C2 1 5
Gini 0.393 Gini 0.400 Gini 0.419
 Attributs numériques – indice GINI

ƒ calcul efficace : pour chaque attribut,

ƒ Trier les instances selon la valeur de l’attribut
ƒ Entre chaque valeur de cette liste : un test possible (split)
ƒ Evaluation de Gini pour chacun des test
ƒ Choisir le split qui minimise l’indice gini
Fraude No No No Yes Yes Yes No No No No
Revenu imposable
Valeurs triées 60 70 75 85 90 95 100 120 125 220

Positions Split 55 65 72 80 87 92 97 110 122 172 230

<= > <= > <= > <= > <= > <= > <= > <= > <= > <= > <= >
Yes 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0

No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0

Gini 0.420 0.400 0.375 0.343 0.417 0.400 0.300 0.343 0.375 0.400 0.420
Méthodes à base d’arbres de
décision

ƒ CART (BFO’80 - Classification and

regression trees, variables numériques,
Gini, Elagage ascendant)
ƒ C5 (Quinlan’93 - dernière version ID3 et
C4.5, attributs d’arité quelconque,
entropie et gain d’information)
ƒ SLIQ (EDBT’96 — Mehta et al. IBM)
ƒ SPRINT (VLDB’96—J. Shafer et al. IBM)
ƒ PUBLIC (VLDB’98 — Rastogi & Shim)
ƒ RainForest (VLDB’98 — Gehrke,
Ramakrishnan & Ganti)
ƒ CHAID (Chi-square Automation
Interaction Detection – variables
discrètes)
Arbres de décision - Avantages

ƒ Compréhensible pour tout utilisateur

(lisibilité du résultat – règles - arbre)
ƒ Justification de la classification d’une
instance (racine Æ feuille)
ƒ Tout type de données
ƒ Robuste au bruit et aux valeurs manquantes
ƒ Attributs apparaissent dans l’ordre de
pertinence Æ tâche de pré-traitement
(sélection d’attributs)
ƒ Classification rapide (parcours d’un chemin
dans un arbre)
ƒ Outils disponibles dans la plupart des
environnements de data mining
Arbres de décision - Inconvénients

ƒ Sensibles au nombre de
classes : performances se
dégradent

ƒ Evolutivité dans le temps :

si les données évoluent
dans le temps, il est
nécessaire de relance la
phase d’apprentissage
 Réseaux de neurones

ƒ Réseau neuronal : simule le système nerveux biologique

ƒ Un réseau de neurones est composé de plusieurs
neurones interconnectés. Un poids est associé à chaque
arc. A chaque neurone on associe une valeur.

ƒ Temps de ”switch” d’un

neurone > 10-3 secs
ƒ Nombre de neurones
(humain) ~1010
ƒ Connexions (synapses)
par neurone : ~104–105
 Neurone ou perceptron

ƒ Neurone = Unité de calcul élémentaire

ƒ Le vecteur d’entrée X est transformé en une variable de sortie y,
par un produit scalaire et une fonction de transformation non
linéaire

X0 w0
X1 w1
∑ f
Sortie y
Xn wn

Vecteur Vecteur Somme Fonction

entrée X poids w pondérée d’activation
(coefficients
Synaptiques)
 Neurone ou perceptron

Linear treshold unit (LTU)

x0=1
x1 w1
w0
w2
x2 Σ o
. Σi=0n wi xi
.
. wn
xn 1 si Σi=0n wi xi >0
o(xi)= { -1 sinon
 Neurone

ƒ Fonction d’activation la plus utilisée est la fonction sigmoide

σ(x)= 1
1+e x

ƒ Elle prend ses valeurs (entrée et sortie) dans l’intervalle [0,1]

0 1
 Réseaux de neurones

ƒ Capacité d ’apprentissage : apprendre et changer son

comportement en fonction de toute nouvelle
expérience.

ƒ Permettent de découvrir automatiquement des

modèles complexes.

ƒ Plusieurs modèles de réseaux de neurones : PMC

(Perceptron Multi-Couches), RBF (Radial Basis
Function), Kohonen, ...
 Perceptron Multi Couches (PMC)

Vecteur sortie

Couche sortie Calculs effectués des entrées

vers les sorties

Plusieurs
Couches
cachées

Couche Graphe complet

entrée

Vecteur entrée
Paradigme d’apprentissage

Vecteur sortie

Classification : Ajuster les poids

en utilisant l’erreur

Erreur = Valeur désirée – Valeur

actuelle

Vecteur entrée
 Algorithmes d’apprentissage

ƒ Rétro-propagation du gradient (Back

propagation)
ƒ Kohonen
ƒ RBF (Radial basis function)
ƒ Réseaux de neurones probabilistes
ƒ ART (Adaptive resonance theory)
ƒ …
 Rétro-propagation du gradient

Principales étapes

ƒ Construction du réseau
ƒ Représentation des entrées
ƒ Nombre de couches, nombre de noeuds dans chaque
couche
ƒ Apprentissage du réseau utilisant les données
disponibles
ƒ Elagage du réseau
ƒ Interprétation des résultats
 Construction du réseau

ƒ Nombre de noeuds en entrée : correspond à la

dimension des données du problème (attributs ou
leurs codages).

Normaliser dans l’intervalle [0,1].

Exemple énumératif : Attribut A prenant ses valeurs

{1,2,3,4,5}
ƒ 5 entrées à valeurs binaires ; 3 = 00100
ƒ 3 bits ; 3 = 010
ƒ 1 entrée réelle ; 0, 0.25, 0.5, 0.75, 1
 Construction du réseau

ƒ Nombre de couches cachées : Ajuster pendant

l’apprentissage.
ƒ Nombre de nœuds par couche : Le nombre de nœuds
par couche est au moins égal à deux et au plus égal au
nombre de nœuds en entrée
ƒ Nombre de nœuds en sortie : fonction du nombre de
classes associées à l’application.

ƒ Réseau riche Æ pouvoir d’expression grand (Ex. 4-2-1

est moins puissant que 4-4-1)
ƒ Attention : Choisir une architecture riche mais pas
trop – Problème de sur-spécialisation
 Apprentissage du réseau
ƒ Objectif principal : obtenir un ensemble de poids qui
font que la plupart des instances de l’ensemble
d’apprentissage sont correctement classées.
ƒ Etapes :
ƒ Poids initiaux sont générés aléatoirement
ƒ Les vecteurs en entrée sont traités en séquentiel par le
réseau
ƒ Calcul des valeurs d’activation des nœuds cachés
ƒ Calcul du vecteur de sortie
ƒ Calcul de l’erreur (sortie désirée – sortie actuelle).

e(PMC)= 1 ∑
2 x∈S (d(x)−a(x)) 2

ƒ d(x) : sortie désirée, a(x) : sortie actuelle

 Apprentissage du réseau

ƒ Les poids sont mis à jour en utilisant l’erreur. Le nombre

d’instances qui sont passés dans le réseau avant la mise
à jour des poids est un paramètre (entre 1 –
convergence rapide et minimum local - et m –
convergence lente -).

ƒ Rétro propagation à l’aide de la méthode de gradient. Le

paramètre taux d’apprentissage [0,1] influe sur la
modification des poids.
Valeur grande : modification forte ; Valeur petite :
modification minime
 Apprentissage du réseau

wi = wi + ∆wi
∆wi = η (t - o) xi
t=c(x) est la valeur désirée
o est la sortie obtenue
η est le taux d’apprentissage (e.g 0.1)

ƒ Critère d’arrêt : la tolérance définit l’erreur cible.

et/ou Nombre d’instances bien classées (seuil)
Apprentissage du réseau

(w1,w2)

(w1+∆w1,w2 +∆w2)
 Elagage du réseau

ƒ Réseau fortement connexe est difficile à articuler

ƒ N nœuds en entrée, h couches cachées, et m nœuds

en sortie Æ h(m+n) arcs (poids)

ƒ Elagage : Supprimer les arcs et les nœuds qui

n’affectent pas le taux d’erreur du réseau. Eviter le
problème de sur-spécialisation (over-fitting).
Ceci permet de générer des règles concises et
compréhensibles.
Réseaux de neurones - Avantages

ƒ Taux d’erreur généralement bon

ƒ Outil disponible dans les
environnements de data mining
ƒ Robustesse (bruit) –
reconnaissance de formes (son,
images sur une rétine, …)
ƒ Classification rapide (réseau
étant construit)
ƒ Combinaison avec d’autres
méthodes (ex : arbre de décision
pour sélection d’attributs)
Réseaux de neurones -
Inconvénients

ƒ Apprentissage très long

ƒ Plusieurs paramètres
(architecture, coefficients
synaptiques, …)
ƒ Pouvoir explicatif faible (boite
noire)
ƒ Pas facile d’incorporer les
connaissances du domaine.
ƒ Traitent facilement les attributs
numériques et binaires
ƒ Evolutivité dans le temps (phase
d’apprentissage)
 Classification bayésienne :
Pourquoi ? (1)

ƒ Apprentissage probabiliste :
ƒ calcul explicite de probabilités sur des
hypothèses
ƒ Approche pratique pour certains types de
problèmes d’apprentissage
ƒ Incrémental :
ƒ Chaque instance d’apprentissage peut de façon
incrémentale augmenter/diminuer la
probabilité qu’une hypothèse est correcte
ƒ Des connaissances a priori peuvent être
combinées avec les données observées.
 Classification bayésienne :
Pourquoi ? (2)

ƒ Prédiction Probabiliste :
ƒ Prédit des hypothèses multiples, pondérées par
leurs probabilités.

ƒ Référence en terme d’évaluation :

ƒ Même si les méthodes bayésiennes sont
coûteuses en temps d’exécution, elles peuvent
fournir des solutions optimales à partir
desquelles les autres méthodes peuvent être
évaluées.
 Classification bayésienne

ƒ Le problème de classification peut être formulé

en utilisant les probabilités a-posteriori :
ƒ P(C|X) = probabilité que le tuple (instance)
X=<x1,…,xk> est dans la classe C
ƒ Par exemple
ƒ P(classe
P( =N | outlook=sunny,windy=true,…)

ƒ Idée : affecter à une instance X la classe C

telle que P(C|X) est maximale
Estimation des probabilités a-
posteriori

ƒ Théorème de Bayes :
ƒ P(C|X) = P(X|C)·P(C) / P(X)
ƒ P(X) est une constante pour toutes les
classes
ƒ P(C) = fréquence relative des
instances de la classe C
ƒ C tel que P(C|X) est maximal =
C tel que P(X|C)·P(C) est maximal
ƒ Problème : calculer P(X|C) est non
faisable !
 Classification bayésienne naive

ƒ Hypothèse Naïve : indépendance des

attributs
ƒ P(x1,…,xk|C) = P(x1|C)·…·P(xk|C)

P(xi|C) est estimée comme la fréquence

relative des instances possédant la valeur
xi (i-ème attribut) dans la classe C

ƒ Non coûteux à calculer dans les deux cas

 Classification bayésienne –
Exemple (1)

ƒ Estimation de P(xi|C)
P(p) = 9/14
P(n) = 5/14

Outlook
P(sunny | p) = 2/9 P(sunny | n) = 3/5 Humidity
P(overcast | p) = 4/9 P(overcast | n) = 0 P(high | p) = 3/9 P(high | n) = 4/5
P(rain | p) = 3/9 P(rain | n) = 2/5 P(normal | p) = 6/9 P(normal | n) = 1/5
Temperature
P(hot | p) = 2/9 P(hot | n) = 2/5 Windy
P(mild | p) = 4/9 P(mild | n) = 2/5 P(true | p) = 3/9 P(true | n) = 3/5
P(cool | p) = 3/9 P(cool | n) = 1/5 P(false | p) = 6/9 P(false | n) = 2/5
 Classification bayésienne –
Exemple (1)

ƒ Classification de X :
ƒ Une instance inconnue X = <rain, hot, high, false>
ƒ P(X|p)·P(p) =
P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p) =
3/9·2/9·3/9·6/9·9/14 = 0.010582
ƒ P(X|n)·P(n) =
P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n) =
2/5·2/5·4/5·2/5·5/14 = 0.018286
ƒ Instance X est classifiée dans la classe n (ne pas
jouer)
 Classification bayésienne –
l’hypothèse d’indépendance

ƒ … fait que le calcul est possible

ƒ … trouve un modèle de classification optimal si
hypothèse satisfaite
ƒ … mais est rarement satisfaite en pratique, étant
donné que les attributs (variables) sont souvent
corrélés.
ƒ Pour éliminer cette limitation :
ƒ Réseaux bayésiens,
bayésiens qui combinent le
raisonnement bayésien et la relation causale
entre attributs
ƒ Arbres de décision,
décision qui traitent un attribut à la
fois, considérant les attributs les plus importants
en premier
 Etude de cas

Prédiction de structure de la
protéine
 Les protéines

ƒ Une protéine = séquence d’acides aminés définie par un gêne

et ayant une fonction spécifique dans la cellule
« Building block of life »

• Les protéines sont partout :

• Protéines enzymatiques (catalyse)
• Protéines de transport : hémoglobine (oxygène),
albumine (corps gras) …
• Protéine messager : insuline …
• Protéines récepteur
• Protéines sériques : anticorps
• Protéines structurelles : collagène dans la peau,
kératine dans les cheveux, …
•…
 Les protéines

ƒ 20 acides aminés distincts, chaque acide aminé étant

constitué de (jusqu’à) 18 atomes
ƒ Une séquence protéique est constituée de 50 à 2000
acides aminés
ƒ 3000 à 4000 protéines dans une cellule
ƒ Une protéine se replie « en pelote », adoptant une
configuration spatiale caractéristique de sa fonction
 Les 20 Acides Aminés

ƒ A Ala Alanine ƒ M Met Methionine

ƒ C Cys Cysteine ƒ N Asn Asparagine
ƒ D Asp Aspartic ƒ P Pro Proline
ƒ E Glu Glutamic ƒ Q Gln Glutamine
ƒ F Phe Phenylalanine ƒ R Arg Arginine
ƒ G Gly Glycine ƒ S Ser Serine
ƒ H His Histidine ƒ T Thr Threonine
ƒ I Ile Isoleucine ƒ V Val Valine
ƒ K Lys Lysine ƒ W Trp Tryptophan
ƒ L Leu Leucine ƒ Y Tyr Tyrosine

20 Lettres de l’alphabet
 Les structures

ƒ Structure primaire = ordre dans lequel sont

enchaînés les acides aminés dans la molécule

ƒ Structure secondaire = rotation des atomes de la

chaîne peptidique les uns par rapport aux autres au
cours de la synthèse de la chaîne

ƒ Structure tertiaire = résultat de liaisons diverses

(hydrogène, hydrophobes, électrostatiques,
covalentes,...) entre des acides aminés de la même
chaîne peptidique mais non voisins dans la
structure primaire
 Structure primaire
O H O H O H O H O H OH OH
H3N+ CH C N CH C N CH C N CH C N CH C N CH C N CH C N CH COO-

CH2 CH2 CH CH2 H C CH3 CH2 CH2 CH2 CH2

COO- CH2 H3C CH3 CH2 HC CH CH2

CH2 CH3 HN N

NH CH

NH2 N +H 2

Asp Arg Val Tyr Ile His Pro Phe

D R V Y I H P F
Séquence de la protéine : DRVYIHPF
 Protein Folding Problem
Etant donné une séquence primaire de la protéine, ex.,
MDPNCSCAAAGDSCTCANSCTCLACKCTSCK,
prédire la structure secondaire et 3D.
 Base de données

Structures prédites (connues) :

Protein Data Bank (PDB) (centaine de structures
non redondantes) [www.rcsb.org/pdb/]

Base de données de séquences de protéines :

Genbank (milliers de séquences)
[www.ncbi.nlm.nih.gov/Genbank/GenbankSearch.html]
SWISSPROT
[www.ebi.ac.uk/swissprot]
 Structure secondaire

ƒ Hélice α

ƒ Feuillet ß parallèle :
tous les segments
ont la même
orientation
ƒ Feuillet ß anti-
parallèle
ƒ Feuillet ß mixte
 Structure secondaire

ƒ Hélice α
ƒ Feuillet ß parallèle :
tous les segments
ont la même
orientation
ƒ Feuillet ß anti-
parallèle
ƒ Feuillet ß mixte
 Structure secondaire

ƒ Beta Hélice
 Structure 3D
ƒ Permet de comprendre le mode d'action d'une
protéine : activité enzymatique, interaction avec
d'autres protéines (ligands, substrats, récepteur,
épitope, etc.).

Structure primaire Structure

secondaire / tertiaire
 Réseaux de neurones
- Le processus neuronal de base traite des signaux
d'entrée d'un ou plusieurs neurones et envoie un
signal de sortie à un ou plusieurs (un 0 ou un 1)
- Le signal de sortie à chaque neurone récepteur est
pondéré – ces poids sont ajustés par entraînement
du modèle avec des séquences de structures
connues
- Le programme donne une évaluation de fiabilité de
chaque prévision basée sur la force des signaux
d’une hélice alpha, d’un feuillet bêta et d’une
boucle
Référence : Rost B, Sander C (1994) Combining evolutionary
information and neural networks to predict protein
secondary structure. Proteins, 19, 55-72
 Réseaux de neurones

ƒ Entrée : structure
primaire
ƒ Sortie : indication sur … Entrée
la structure
secondaire
Couche cachée

Sortie

Hélice α Feuillet β Boucle

Efficacité > 70% H B C
 Plus proches voisins

ƒ Une liste de fragments courts de séquence

est faite en glissant une fenêtre de
longueur n le long d'un ensemble
d'approximativement 100-400 séquence
d’entraînement de structure connue mais
de similitude minimale
ƒ La structure secondaire de l'acide aminé
central dans chaque fenêtre
d’entraînement est enregistrée
ƒ Une fenêtre coulissante de même taille est
alors choisi parmi la séquence de requête
 Plus proches voisins

ƒ La séquence dans la fenêtre à chaque position de la

séquence demandée est comparée à chacun des
fragments d’entraînement et les 50 meilleurs
fragments appariés sont identifiés → Nécessité
d’une notion de distance
ƒ Les fréquences de la structure secondaire connue
de l'acide aminé du milieu dans chacun de ces
fragments appariés (H, B et C) sont alors employés
pour prévoir la structure secondaire de l'acide
aminé du milieu de la fenêtre de requête
ƒ Des règles ou un NN sont utilisées pour faire la
prédiction finale pour chaque AA.
 Liens Web - Logiciels

ƒ http://dot.imgen.bcm.tmc.edu:9331/seq-
search/struc-predict.html
ƒ http://jura.ebi.ac.uk:8888/jnet/
ƒ http://www.embl-
heidelberg.de/predictprotein/
ƒ http://cubic.bioc.columbia.edu/predictprot
ein

ƒ (B Rost: PHD: predicting one-dimensional protein

structure by profile based neural networks. Methods
in Enzymology, 266, 525-539, 1996 )
Autres méthodes de classification

ƒ Réseaux bayésiens
ƒ Algorithmes génétiques
Autres
méthodes
ƒ Case-based reasoning
ƒ Ensembles flous
ƒ Rough set
ƒ Analyse discriminante
(Discriminant linéaire de Fisher,
Algorithme Closest Class Mean -
CCM-)
Classification - Résumé

ƒ La classification est un
problème largement étudié

ƒ La classification, avec ses

nombreuses extensions,
est probablement la
technique la plus répandue

ƒ Modèles Facile à comprendre

ƒ Arbres de décision
ƒ Règles d’induction
ƒ Modèles de régression
ƒ Réseaux de neurones Difficile à comprendre
Classification - Résumé

ƒ L’extensibilité reste une

issue importante pour les
applications

ƒ Directions de recherche :
classification de données
non relationnels, e.x.,
texte, spatiales et
données multimédia
 Classification - Références

ƒ J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan

Kaufman, 1993.
ƒ J. R. Quinlan. Induction of decision trees. Machine Learning,
1:81-106, 1986.
ƒ L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification
and Regression Trees. Wadsworth International Group, 1984.
ƒ S. M. Weiss and C. A. Kulikowski. Computer Systems that Learn:
Classification and Prediction Methods from Statistics, Neural
Nets, Machine Learning, and Expert Systems. Morgan Kaufman,
1991.
ƒ D. E. Rumelhart, G. E. Hinton and R. J. Williams. Learning
internal representation by error propagation. In D. E. Rumelhart
and J. L. McClelland (eds.) Parallel Distributed Processing. The
MIT Press, 1986
Règles
d’association
 Sommaire

ƒ Exemple : Panier de la
Sommaire ménagère
ƒ Définitions
ƒ A-Priori
ƒ Algorithmes génétiques
ƒ Résumé
 Exemple : Analyse du panier
de la ménagère
• Découverte d’associations et de corrélations entre les
articles achetés par les clients en analysant les achats
effectués (panier)

Lait, Oeufs, Sucre,

Lait, Oeufs, Céréale, Lait Oeufs, Sucre
Pain

Client 1
Client 3
Client 2
 Exemple : Analyse du panier
de la ménagère
• 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 :
• Groupes d’articles (itemset) achetés fréquemment (ensemble)
 Exemple : Analyse du panier
de la ménagère
ƒ Extraction d’informations sur le comportement
de clients
ƒ SI achat de riz + vin blanc ALORS achat de poisson (avec
une grande probabilité)

ƒ Intérêt de l’information : peut suggérer ...

ƒ Disposition des produits dans le magasin
ƒ Quels produits mettre en promotion, gestion de stock, …

ƒ Approche applicable dans d’autres domaines

ƒ Cartes de crédit, e-commerce, …
ƒ Services des compagnies de télécommunication
ƒ Services bancaires
ƒ Traitements médicaux, …
 Règles d’associations

ƒ Recherche de règles d’association :

ƒ Découvrir des patterns, corrélations, associations
fréquentes, à partir d’ensembles d’items contenus dans
des base de données.
ƒ Compréhensibles : Facile à comprendre
ƒ Utiles : Aide à la décision
ƒ Efficaces : Algorithmes de recherche
ƒ Applications :
ƒ Analyse des achats de clients, Marketing, Accés Web,
Design de catalogue, Génomique, etc.
 Règles d’associations

ƒ Formats de représentation des règles

d’association :
ƒ couches ⇒ bière [0.5%, 60%]
ƒ achète:couches ⇒ achète:bière [0.5%, 60%]

ƒ “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."

ƒ Autres représentations (utilisée dans l’ouvrage

de Han) :
ƒ achète(x, “couches") ⇒ achète(x, “bière") [0.5%, 60%]
 Règles d’associations

couche ⇒ bière [0.5%, 60%]

“SI achète couche,
ALORS achète bière,
1 2 3 4 dans 60% de cas,
dans 0.5% de la base"
1 Condition partie gauche de la règle
Condition,
2 quence partie droite de la règle
Conséquence,
3 Support fréquence (“partie gauche et droite sont
Support,
présentes ensemble dans la base”)
4 Confiance (“si partie gauche de la règle est
vérifiée, probabilité que la partie droite de la
règle soit vérifiée“)
 Règles d’associations

• Support : % d’instances de la base vérifiant la règle.

support(A ⇒ B [ s, c ]) = p(A∪B) = support ({A,B})

• Confiance : % d’instances de la base vérifiant l’implication

confiance(A ⇒ B [ s, c ]) = p(B|A) = p(A∪B) / p(A) =

support({A,B}) / support({A})
 Exemple

TID Items
1 Pain, Lait
2 Bière, Couches, Pain, Oeufs {Couches , Lait} ⇒ s ,α Bière
3 Bière, Coca, Couches, Lait
4 Bière, Pain, Couches, Lait
σ (Couches , Lait, Bière ) 2
5 Coca, Pain, Couches, Lait s= = = 0. 4
Nombre total d' instances 5

Règle : X ⇒ s ,α y
σ (Couches, Lait, Bière)
α= = 0.66
σ ( X ∪ y) σ (Couches, Lait) |
Support : s= ( s = P (X, y))
|T |

Confiance : α = σ (X ∪ y) (α = P( y | X))
σ (X) |
 Règles d’associations

ƒ Support minimum σ :
ƒ Elevé ⇒ peu d’itemsets fréquents
⇒ peu de règles valides qui ont été
souvent vérifiées
ƒ Réduit ⇒ plusieurs règles valides qui ont été
rarement vérifiées
ƒ Confiance minimum γ :
ƒ Elevée ⇒ peu de règles, mais toutes “pratiquement”
correctes
ƒ Réduite ⇒ plusieurs règles, plusieurs d’entre elles sont
“incertaines”

ƒ Valeurs utilisées : σ = 2 - 10 %, γ = 70 - 90 %
 Règles d’associations

ƒ Etant donné : (1) un base de données de

transactions, (2) chaque transaction est un
ensemble d’articles (items) achetés
Transaction ID Items achetés Itemset fréquent Support
100 A,B,C {A} 3 ou 75%
200 A,C {B} et {C} 2 ou 50%
400 A,D {D}, {E} et {F} 1 ou 25%
500 B,E,F {A,C} 2 ou 50%
Autres paires d’items max 25%

ƒ Trouver : toutes les règles avec un support et une

confiance minimum donnés
• Si support min. 50% et confiance min. 50%, alors
A ⇒ C [50%, 66.6%], C ⇒ A [50%, 100%]
 Recherche de règles d’association

ƒ Données d ’entrée : liste d ’achats

ƒ Achat = liste d ’articles (longueur variable)

Produit Produit Produit Produit Produit

A B C D E
Achat 1
* *
Achat 2
* * *
Achat 3
* *
Achat 4
* * *
Achat 5
* *
 Recherche de règles d’association

ƒ Tableau de co-occurrence : combien de fois deux

produits ont été achetés ensemble ?

Produit Produit Produit Produit Produit

A B C D E
Produit A 4 1 1 2 1

Produit B 1 2 1 1 0

Produit C 1 1 1 0 0

Produit D 2 1 0 3 1

Produit E 1 0 0 1 2
 Illustration / Exemple

ƒ Règle d ’association :
ƒ Si A alors B (règle 1)
ƒ Si A alors D (règle 2)
ƒ Si D alors A (règle 3)
ƒ Supports :
ƒ Support(1)=20% ; Support(2)=Support(3)=40%
ƒ Confiances :
ƒ Confiance(2) = 50% ; Confiance(3) = 67%

ƒ On préfère la règle 3 à la règle 2.

 Description de la méthode

ƒ Support et confiance ne sont pas toujours suffisants

ƒ Ex : Soient les 3 articles A, B et C
article A B C A et B A et C B et C A, B et C

fréquence 45% 42,5% 40% 25% 20% 15% 5%

ƒ Règles à 3 articles : même support 5%

ƒ Confiance
ƒ Règle : Si A et B alors C = 0.20
ƒ Règle : Si A et C alors B = 0.25
ƒ Règle : Si B et C alors A = 0.33
 Description de la méthode

ƒ Amélioration = confiance / fréq(résultat)

ƒ Comparer le résultat de la prédiction en utilisant la
règle avec la prédiction sans la règle
ƒ Règle intéressante si Amélioration > 1
Règle Confiance F(résultat) Amélioration

Si A et B alors C 0.20 40% 0.50

Si A et C alors B 0.25 42.5% 0.59

Si B et C alors A 0.33 45% 0.74

ƒ Règle : Si A alors B ; support=25% ; confiance=55% ;

Amélioration = 1.31 Meilleure règle
 Recherche de règles

ƒ Soient une liste de n articles et de m achats.

ƒ 1. Calculer le nombre d’occurrences de chaque article.
ƒ 2. Calculer le tableau des co-occurrences pour les paires
d ’articles.
ƒ 3. Déterminer les règles de niveau 2 en utilisant les
valeurs de support, confiance et amélioration.
ƒ 4. Calculer le tableau des co-occurrences pour les
triplets d ’articles.
ƒ 5. Déterminer les règles de niveau 3 en utilisant les
valeurs de support, confiance et amélioration
ƒ ...
 Complexité

ƒ Soient :
ƒ n : nombre de transactions dans la BD
ƒ m : Nombre d’attributs (items) différents

ƒ Complexité
ƒ Nombre de règles d’association : Ο(m.2m −1 )
ƒ Complexité de calcul : Ο(n.m.2m )
 Réduction de la complexité
ƒ n de l’ordre du million (parcours de la liste nécessaire)
ƒ Taille des tableaux en fonction de m et du nombre d ’articles
présents dans la règle

2 3 4
n n(n-1)/2 n(n-1)(n-2)/6 n(n-1)(n-2)(n-3)/24
100 4950 161 700 3 921 225
10000 5.107 1.7 1011 4.2 1014

ƒ Conclusion de la règle restreinte à un sous-ensemble de l ’ensemble

des articles vendus.
ƒ Exemple : articles nouvellement vendues.
ƒ Création de groupes d ’articles (différents niveaux d’abstraction).
ƒ Elagage par support minimum.
 Illustration sur une BD commerciale

Attribut Compteur Attributs (1-itemsets)

Pain 4
Coca 2
Lait 4 Itemset Compteur paires (2-itemsets)
Bière 3
{Pain,Lait} 3
Couches 4
Oeufs 1 {Pain,Bière} 2
{Pain,Couches} 3
{Lait,Bière} 2
{Lait,Couches} 3
{Bière,Couches} 3
Support Minimum = 3
Triplets (3-itemsets)

Si tout sous-ensemble est considéré, Itemset Compteur

C61 + C62 + C63 = 41 {Pain,Lait,Couches} 3
{Lait,Couches,Bière} 2
En considérant un seuil support min,
6 + 6 + 2 = 14
 L’algorithme Apriori [Agrawal93]

ƒ Deux étapes
ƒ Recherche des k-itemsets fréquents
(support≥MINSUP)
ƒ (Pain, Fromage, Vin) = 3-itemset
ƒ Principe : Les sous-itemsets d’un k-itemset fréquent
sont obligatoirement fréquents

ƒ Construction des règles à partir des k-itemsets

trouvés
ƒ Une règle fréquente est retenue si et seulement si sa
confiance c≥ MINCONF
ƒ Exemple : ABCD fréquent
ƒ AB Æ CD est retenue si sa confiance ≥ MINCONF
 Recherche des k-itemsets fréquents (1)

ƒ Exemple
ƒ I = {A, B, C, D, E, F}
ƒ T = {AB, ABCD, ABD, ABDF, ACDE, BCDF}
ƒ MINSUP = 1/2
ƒ Calcul de L1 (ensemble des 1-itemsets)
ƒ C1 = I = {A,B,C,D,E,F} // C1 : ensemble de 1-itemsets candidats
ƒ s(A) = s(B) = 5/6, s(C) = 3/6, s(D) = 5/6, s(E) = 1/6, s(F) = 2/6
ƒ L1 = {A, B, C, D}
ƒ Calcul de L2 (ensemble des 2-itemsets)
ƒ C2 = L1xL1 = {AB,AC, AD, BC, BD, CD}
ƒ s(AB) = 4/6, s(AC) = 2/6, s(AD) = 4/6, s(BC) = 2/6, s(BD) = 4/6,
s(CD) = 3/6
ƒ L2 = {AB,AD, BD, CD}
Recherche des k-itemsets fréquents (2)

ƒ Calcul de L3 (ensemble des 3-itemsets)

ƒ C3 = {ABD} (ABC ∉ C3 car AC ∉ L2)
ƒ s(ABD) = 3/6
ƒ L3 = {ABD}
ƒ Calcul de L4 (ensemble des 4-itemsets)
ƒ C4 = φ

ƒ L4 = φ

ƒ Calcul de L (ensembles des itemsets fréquents)

ƒ L = ∪Li = {A, B, C, D, AB, AD, BD, CD, ABD}
 L’algorithme Apriori

L1 = {1-itemsets fréquents};
for (k=2; Lk-1≠ φ; k++) do
Ck = apriori_gen(Lk-1);
forall instances t∈T do
Ct = subset(Ck,t);
forall candidats c ∈ Ct do
c.count++;
Lk = { c∈ Ck / c.count ≥ MINSUP }
L = ∪iLi;
 La procédure Apriori_gen

{ Jointure Lk-1 * Lk-1 ; k-2 éléments communs}

insert into Ck;
select p.item1, p.item2, …, p.itemk-1, q.itemk-1
from Lk-1p, Lk-1q
where p.item1=q.item1, …, p.itemk-2=q.itemk-2
, p.itemk-1< q.itemk-1
forall itemsets c ∈ Ck do
forall (k-1)-itemsets s⊂c do
if s∉Lk-1 then
delete c from Ck;
 Apriori - Exemple

Base de
C1 L1
données D
itemset sup.
TID Items itemset sup.
{1} 2
100 134 {1} 2
200 235
Scan D {2} 3
{2} 3
{3} 3
300 1235 {3} 3
{4} 1
400 25 {5} 3
{5} 3
 Apriori - Exemple

C2 C2 L2
itemset itemset sup
{1 2} {1 2} 1 itemset sup
{1 3} {1 3} 2 {1 3} 2
{1 5}
Scan D {1 5} 1 {2 3} 2
{2 3} {2 3} 2 {2 5} 3
{2 5} {2 5} 3 {3 5} 2
{3 5} {3 5} 2
 Apriori - Exemple

C3 L3

itemset Scan D itemset sup

{2 3 5} {2 3 5} 2
 Apriori - Exemple

Espace de 12345
recherche
1234 1235 1245 1345 2345

123 124 125 134 135 145 234 235 245 345

12 13 14 15 23 24 25 34 35 45

1 2 3 4 5
 Apriori - Exemple

Apriori 12345
au Niveau 1
1234 1235 1245 1345 2345

123 124 125 134 135 145 234 235 245 345

12 13 14 15 23 24 25 34 35 45

1 2 3 4 5
 Apriori - Exemple

Apriori 12345
au niveau 2
1234 1235 1245 1345 2345

123 124 125 134 135 145 234 235 245 345

12 13 14 15 23 24 25 34 35 45

1 2 3 4 5
Génération des règles à partir des itemsets

ƒ Pseudo-code :
ƒ pour chaque itemset fréquent l
générer tous les sous-itemsets non vides s de l
ƒ pour chaque sous-itemset non vide s de l
produire la règle "s ⇒ (l-s)" si
support(l)/support(s) ≥ min_conf", où min_conf est la
confiance minimale

ƒ Exemple : itemset fréquent l = {abc},

ƒ Sous-itemsets s = {a, b, c, ab, ac, bc)

ƒ a ⇒ bc, b ⇒ ac, c ⇒ ab
ƒ ab ⇒ c, ac ⇒ b, bc ⇒ a
Génération des règles à partir des itemsets

ƒ Règle 1 à mémoriser :
ƒ La génération des itemsets fréquents est une opération
coûteuse
ƒ La génération des règles d’association à partir des itemsets
fréquents est rapide
ƒ Règle 2 à mémoriser :
ƒ Pour la génération des itemsets, le seuil support est utilisé.
ƒ Pour la génération des règles d’association, le seuil confiance
est utilisé.
ƒ Complexité en pratique ?
ƒ A partir d’un exemple réel (petite taille) …
ƒ Expériences réalisées sur un serveur Alpha Citum 4/275 avec
512 MB de RAM & Red Hat Linux release 5.0 (kernel 2.0.30)
 Exemple de performances

Network
NetworkManagement
ManagementSystem
System Réseau switché

MSC
MSC MSC
MSC MSC
MSC

BSC
BSC BSC
BSC BSC
BSC
Réseau d’accés
BTS
BTS BTS
BTS BTS
BTS
MSC
MSC Mobile station controller
Alarms
Alarms

BSC
BSC Base station controller

BTS Base station transceiver

BTS

Réseau cellulaire
 Exemple de performances

ƒ Données télécom contenant des alarmes :

ƒ 1234 EL1 PCM 940926082623 A1 ALARMTEXT..
Alarm type Date, time Alarm severity class
Alarming network element
Alarm number

ƒ Exemple de données 1 :
ƒ 43 478 alarmes (26.9.94 - 5.10.94; ~ 10 jours)
ƒ 2 234 différent types d’alarmes, 23 attributs, 5503 différentes
valeurs
ƒ Exemple de données 2 :
ƒ 73 679 alarmes (1.2.95 - 22.3.95; ~ 7 semaines)
ƒ 287 différent types d’alarmes, 19 attributs, 3411 différentes
valeurs
 Exemple de performances

Ensemble données 1 (~10 jours) Ensemble données 2 (~7 semaines)

Exemple de règles :
alarm_number=1234, alarm_type=PCM ⇒ alarm_severity=A1 [2%,45%]
 Exemple de performances

ƒ Exemple de résultats pour les données 1 :

ƒ Seuil de fréquence : 0.1
ƒ Itemsets candidats : 109 719 Temps: 12.02 s
ƒ Itemsets fréquents : 79 311 Temps: 64 855.73 s
ƒ Règles : 3 750 000 Temps: 860.60 s

ƒ Exemple de résultats pour les données 2 :

ƒ Seuil de fréquence : 0.1
ƒ Itemsets candidats : 43 600 Temps: 1.70 s
ƒ Itemsets fréquents : 13 321 Temps: 10 478.93 s
ƒ Règles : 509 075 Temps: 143.35 s
 Apriori - Complexité

• Phase coûteuse : Génération des candidats

– Ensemble des candidats de grande taille :

• 104 1-itemset fréquents génèrent 107 candidats pour les 2-
itemsets
• Pour trouver un itemset de taille 100, e.x., {a1, a2, …, a100},
on doit générer 2100 ≈ 1030 candidats.

– Multiple scans de la base de données :

• Besoin de (n +1 ) scans, n est la longueur de l’itemset le plus
long
 Apriori - Complexité

ƒ En pratique :
ƒ Pour l’algorithme Apriori basique, le nombre d’attributs est
généralement plus critique que le nombre de transactions
ƒ Par exemple :
ƒ 50 attributs chacun possédant 1-3 valeurs, 100.000 transactions
(not very bad)
ƒ 50 attributs chacun possédant 10-100 valeurs, 100.000 transactions
(quite bad)
ƒ 10.000 attributs chacun possédant 5-10 valeurs, 100 transactions
(very bad...)
ƒ Notons :
ƒ Un attribut peut avoir plusieurs valeurs différentes
ƒ Les algorithmes traitent chaque paire attribut-valeur comme un
attribut (2 attributs avec 5 valeurs Æ “10 attributs”
ƒ Quelques pistes pour résoudre le problème …
Apriori – Réduction de la complexité

ƒ Suppression de transactions :
ƒ Une transaction qui ne contient pas de k-itemsets
fréquents est inutile à traiter dans les parcours (scan)
suivants.

ƒ Partitionnement :
ƒ Tout itemset qui est potentiellement fréquent dans une
BD doit être potentiellement fréquent dans au moins une
des partitions de la BD.

ƒ Echantillonage :
ƒ Extraction à partir d’un sous-ensemble de données,
décroitre le seuil support
Apriori - Avantages

ƒ Résultats clairs : règles faciles à

interpréter.
ƒ Simplicité de la méthode
ƒ Aucune hypothèse préalable
(Apprentissage non supervisé)
ƒ Introduction du temps : méthode facile
à adapter aux séries temporelles. Ex :
Un client ayant acheté le produit A est
susceptible d ’acheter le produit B dans
deux ans.
Apriori - Inconvénients

ƒ Coût de la méthode : méthode

coûteuse en temps
ƒ Qualité des règles : production d’un
nombre important de règles triviales
ou inutiles.
ƒ Articles rares : méthode non
efficace pour les articles rares.
ƒ Adapté aux règles binaires
ƒ Apriori amélioré
ƒ Variantes de Apriori : DHP, DIC, etc.
ƒ Partition [Savasere et al. 1995]
ƒ Eclat et Clique [Zaki et al. 1997]
ƒ …
 Typologie des règles

ƒ Règles d’association binaires

ƒ Forme : if C then P. C,P : ensembles d’objets
ƒ Règles d’association quantitatives
ƒ Forme : if C then P
ƒ C = terme1 & terme2 & … & termen
ƒ P = termen+1
ƒ termei = <attributj, op, valeur> ou <attributj, op,
valeur_de, valeur_a>
ƒ Classes : valeurs de P
ƒ Exemple : if ((Age>30) & (situation=marié)) then prêt=prioritaire
ƒ Règles de classification généralisée
ƒ Forme : if C then P, P=p1, p2, …, pm P: attribut but
ƒ etc.
Classification généralisée
par Algorithmes
Génétiques
 Problématique

Q Découvrir dans une large BD quelques petites

règles intéressantes «Si C Alors P»

• C = terme1 & terme2 ... & termen (n≤MAXTERM)
• termei =1..n ≡ <attribut=valeur> / valeur est énumératif

• P = terme ≡ <attribut but=valeur>

• attribut but ∈ GoalsSet (défini par l’utilisateur)

Q Exemple : SI (Situation=Single) and (Age=Young) THEN

(Recommandation=Very_recommand)
 Les algorithmes génétiques

ƒ J. Holland (1975)
Population

Sélection
ƒ Principes Génération Parents
suivante Elitisme
ƒ Codage des solutions
ƒ Opérateurs Mutation
ƒ Sélection
Croisement
ƒ Croisement (Crossover)
ƒ Mutation

Enfants
Situation Age Recommandation
Very_recommand
L’algorithme Génétique
Single Young

Sous-population 1 Sous-population K

C11 P1 Ck1 Pk
... ... ...
C1N P1 CkN Pk

Suppression petites règles Suppression

Crossover Crossover
Mutation Mutation
Remplacement quelques règles Remplacement
intéressantes
Evaluation Evaluation
(Fitness function) (Fitness function)

BD
 Fitness (Intérêt d’une règle)

C
G ( Rule ) = b . log( ab ) [Wang et al. 98]
N
P C & P
a = ,b =
N C

ω 1 .G ( Rule ) + ω 2.
η pu

F ( Rule ) =
ηt [Freitas 99]
ω1+ω 2
 Opérateurs génétiques : Crossover (1)

ƒ Deux parents P1 et P2 ont un ou plusieurs

attributs commun(s) dans leurs parties C
ƒ Sélection aléatoire d’un terme
ƒ Permutation de leurs valeurs
ƒ Exemple :
ƒ P1 : (Marital_status=married) ∧ (Gender=male)
ƒ P2 : (Marital_status= single) ∧ (Salary=high)

ƒ Enfant1 : (Marital_status=single) ∧ (Gender=male).

ƒ Enfant2 : (Marital_status=married) ∧ (Salary=high).
 Opérateurs génétiques : Crossover (2)

ƒ P1,P2 n’ont aucun attribut commun dans C

ƒ Sélection aléatoire d’un terme dans P1
ƒ Insertion dans P2
ƒ Proba = (MAXTERM - K)/MAXTERM
ƒ K: Nombre de termes dans la partie C de P2
ƒ Vice versa
ƒ Exemple :
ƒ P1 : (Marital_status=married) ∧ (Gender=male)
ƒ P2 : (Age = young) ∧ (Salary=high)
ƒ E1 : (Marital_status=married) ∧ (Gender=male) ∧ (Age=young)
ƒ E2 : (Marital_status=married) ∧ (Salary=high) ∧
(Gender=male)
Opérateurs génétiques : Mutation (1)

ƒ Deux types de mutation

ƒ Mutation d’attributs
ƒ Mutation de valeurs d’attributs

ƒ Le type de mutation est choisi aléatoirement

ƒ Mutation d’attribut
ƒ Remplacement d’un attribut par un autre (choix aléatoire)
ƒ La valeur du nouvel attribut est choisie aléatoirement
ƒ Exemple :
ƒ P : (Marital_status=married) ∧ (Gender=male)
ƒ Enfant : (Age=young) ∧ (Gender=male)
Opérateurs génétiques : Mutation (2)

ƒ Mutation de valeur d’attribut

ƒ Sélection d’un attribut aléatoirement
ƒ Remplacement de sa valeur par une autre choisie
aléatoirement

ƒ Exemple :
ƒ Parent : (Marital_status=married) ∧ (Gender=male)
ƒ Enfant : (Marital_status=single) ∧ (Gender=male)
 Opérateurs génétiques : Suppression

ƒ Suppression de termes
ƒ But : règles plus faciles à comprendre (petites)
ƒ Suppression d’un terme choisi aléatoirement avec
une probabilité proportionnelle à sa longueur

ƒ Exemple :
ƒ P : (Marital_status=married) ∧ (Gender=male) ∧
(Age=young)
ƒ E : (Marital_status=married) ∧ (Gender=male)
 Application
• BD : Nursery school
Q From http://www.ics.uci.edu/AI/ML/Machine-Learning.html
Q 12960 data instances with 9 attributes
Attribute name Attribute values
1 Parents Usual, pretentious, great_pret
2 Has_nurs Proper, less_proper, improper, critical, very_crit
3 Form Complete, completed, incomplete, foster
4 Children 1, 2, 3, more
5 Housing Convenient, less_conv, critical
6 Finance Convenient, inconv
7 Social Nonprob, slightly_prob, problematic
8 Health Recommended, priority, not_recom
9 Recommendation Recommend, priority, not_recom, very_recom

• Hardware platform • Paramètres de l’AG

Q SGI/IRIX (100MHz R4600, Q 3 attributs buts
32MB RAM, 549MB disque) Q MAXTERM=5
Q 150 individus /3 sous-populations
 Evaluation expérimentale (1)

ƒ Publication
ƒ N. Melab and E-G. Talbi. A Parallel Genetic Algorithm
for Rule Mining. IEEE Intl. Workshop on Bio-Inspired
Solutions to Parallel Processing Problems (BioSP3), San
Francisco, USA, Apr. 23, 2001.
ƒ Evaluation de l’AG
ƒ Qualité des règles extraites
ƒ Paramètres mesurés :
ƒ Validité : facteur de confiance des règles
C&P
FC =
C
 Evaluation expérimentale (2)

Règle |C| |P| |C&P| FCTrain FCTest

R1 18 1296 9 0.500000 0.500000
R2 6 1296 3 0.500000 0.500000
R3 288 196 124 0.430556 0.000000
R4 18 864 18 1.000000 1.000000
R5 18 864 18 1.000000 1.000000
R6 54 864 18 0.333333 0.333333
R7 57 864 18 0.333333 0.333333
R8 162 864 54 0.333333 0.333333
Moyenne 0.552500 0.4987500

ƒ FC mesurés
ƒ Sur les données d’apprentissage (20%) : FCtrain
ƒ Sur les données de test (80%) : Fctest

ƒ Exemple : R4 : SI ((parents=usual) && (health=not_recomm))

ALORS (recommandation=not_recomm)
 Technique “Puces à ADN”

ƒ Avantage principal des techniques “Puces à

ADN”
ƒ Permet l’analyse simultanée d’expressions de
milliers de gènes dans une seule expérience

ƒ Processus “Puces à AND”

ƒ Arrayer
ƒ Expérience : Hybridation
ƒ Capture des images résultats
ƒ Analyse
 Analyse de l’expression de gènes :
Technologie Puces à ADN

ƒ Des robots alignent les

ESTs (Expressed
Sequence Tags) sur les
lames de microscopes
ƒ cellules mRNA marquées
par des tags fluorescents
ƒ Liaison mRNA - cDNA
exprimée (fluorescence)
indique que le gène est
actif
Ressources
Objectif de “Microarray Mining”

Analyse des expressions de gènes

sous différentes conditions
test … … ….
A B C
gene
1 0.6 0.4 0.2 …
2 0.2 0.9 0.8 …
3 0 0 0.3 …
4 0.7 0.5 0.2 …
.. .. .. .. …
.. .. .. .. …
1000 0.3 0.8 0.7 …
Objectif du “Microarray Mining”

Analyse des expressions de gènes

sous différentes conditions
test … … ….
A B C
gène
1 0.6 0.4 0.2 …
2 0.2 0.9 0.8 …
3 0 0 0.3 …
4 0.7 0.5 0.2 …
.. .. .. .. …
.. .. .. .. …
1000 0.3 0.8 0.7 …
 Clustering de gènes
Genes participating in the same pathway are most likely expression at same time.
 Règles d’association
Gene1, Gene2, Gene3, Gene4, Gene5.
Gène représentant la conséquence ?

Chaque condition (microarray) est une instance.

Gènes représentent les itemsets.

Règles d’association avec confiance élevée (100%?)

Gènes cibles = conséquence des règles

Positive regulation

Gene 1 Gene 2 Gene 3 Gene 4

Gene x
Negative regulation
 Expérimentations

ƒ Ensemble de données

ƒ Source：Lawrence Berkeley National Lab

(LBNL) Michael Eisen's Lab
http://rana.lbl.gov/EisenData.htm

ƒ Données d’expression Microarray de “yeast

saccharomyces cerevisiae”, contenant 6221
gènes sous 80 conditions
Règles d’association – Résumé

ƒ Probablement la contribution
la plus significative de la
communauté KDD
ƒ Méthodes de recherche de
règles :
ƒ A-priori
ƒ Algorithmes génétiques
ƒ Plusieurs articles ont été
publiés dans ce domaine
Règles d’association – Résumé
ƒ Plusieurs issues ont été
explorées : intérêt d’une règle,
optimisation des algorithmes,
parallélisme et distribution, …

ƒ Directions de recherche :
ƒ Règles d’associations pour
d’autres types de données :
données spatiales,
multimedia, séries
temporelles, …
 Règles d’association - Références

ƒ R. Agrawal, T. Imielinski, and A. Swami. Mining association rules

between sets of items in large databases. SIGMOD'93, 207-216,
Washington, D.C.
ƒ S. Brin, R. Motwani, and C. Silverstein. Beyond market basket:
Generalizing association rules to correlations. SIGMOD'97, 265-276,
Tucson, Arizona.
ƒ M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, and A.I.
Verkamo. Finding interesting rules from large sets of discovered
association rules. CIKM'94, 401-408, Gaithersburg, Maryland.
ƒ H. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for
discovering association rules. KDD'94, 181-192, Seattle, WA, July
1994.
ƒ G. Piatetsky-Shapiro. Discovery, analysis, and presentation of strong
rules. In G. Piatetsky-Shapiro and W. J. Frawley, editors, Knowledge
Discovery in Databases, 229-238. AAAI/MIT Press, 1991.
Outils pour le Data
Mining
Comment Choisir un outil ?

ƒ Systèmes commerciaux de data

mining possèdent peu de
propriétés communes :
ƒ Différentes méthodologies et
fonctionalités de data mining
ƒ Différents types d’ensembles
de données

ƒ Pour la sélection d’un outil, on a

besoin d’une analyse multi-
critère des systèmes existants
 Comment Choisir un outil ?

ƒ Types de donnés : relationnel, transactionnel,

texte, séquences temporelles, spaciales ?
ƒ Issues systèmes
ƒ Support systèmes d’exploitation ?
ƒ Architecture client/serveur ?
ƒ Fournit une interface Web et permet des
données XML en entrée et/ou en sortie ?
ƒ Sources des données :
ƒ Fichiers texte ASCII, sources de données
relationnels multiples, …
ƒ Support ODBC (OLE DB, JDBC) ?
 Comment Choisir un outil ?

ƒ Fonctionalités et méthodologies
ƒ une vs. plusieurs fonctions de data mining
ƒ une vs. plusieurs méthodes par fonction
ƒ Couplage avec les systèmes de gestion de base
de données et les entropots de données

ƒ Outils de visualization : visualisation des

données, visualisation des résultats obtenus,
visualisation du processus, visualisation interactive
(split attribut, …), etc.
 Comment Choisir un outil ?

ƒ Extensibilité (Scalability)
ƒ instances (Taille de la base de données)
ƒ attributs (dimension de la base)
ƒ Extensibilité en terme d’attributs est plus
difficile à assurer que l’extensibilité en terme
d’instances

ƒ Langage de requête et interface graphique

(IHM)
ƒ easy-to-use et qualité de l’interface
ƒ data mining interactif
 Exemple d’outils (1)

ƒ Intelligent Miner d’IBM

ƒ Intelligent Miner for Data (IMA)
ƒ Intelligent Miner for Text (IMT)
ƒ Tâches : groupage de données, classification,
recherche d’associations, etc.
ƒ Entreprise Miner de SAS
ƒ SAS : longue expérience en statistiques
ƒ Outil «complet» pour le DM
ƒ Darwin de Thinking Machines
ƒ Trois techniques : réseaux de neurones, arbres de
décision et régression.
ƒ Client-Serveur
 Exemples d’outils (2)

ƒ MineSet de Silicon Graphics

ƒ Fonctionnalités interactives et graphiques
ƒ Techniques sous-jacentes : classification,
segmentation, recherche de règles d’association.
ƒ Outils/librairies libres
ƒ SIPINA
ƒ WEKA
ƒ Data-Miner Software Kit (DMSK)
ƒ Kit de programmes : méthodes statistiques,
segmentation, groupage, réseaux de neurones, etc.
ƒ Il existe une version en java
ƒ etc.
SAS Entreprise Miner (1)

ƒ Société : SAS Institute Inc.

ƒ Création : Mai 1998
ƒ Plate-formes : Windows NT & Unix
ƒ Utilisation
ƒ Réduction des coûts
ƒ Maîtrise des risques
ƒ Fidélisation
ƒ Prospection
ƒ Outils de data warehouse
SAS Entreprise Miner (2)
ƒ Interface graphique (icônes)
ƒ Construction d’un diagramme
SAS Entreprise Miner (3)

ƒ Deux types d’utilisateurs

ƒ Spécialistes en statistiques
ƒ Spécialistes métiers (chef de projet, études…)

ƒ Techniques implémentées
ƒ Arbres de décision
ƒ Régression
ƒ Réseaux de neurones
Alice (1)

ƒ Société : ISoft
ƒ Création : 1988
ƒ Plate-formes : Windows 95/98/NT/2000,
TSE, Metaframe

ƒ Utilisation
ƒ Marketing : études de marché, segmentation …
ƒ Banque, Assurance : scoring, analyse de risques, détection de
fraudes
ƒ Industrie : contrôle qualité, diagnostic, segmentation,
classification, construction de modèles, prédiction et
simulation
Alice (2)

ƒ Interface graphique (tools)

ƒ Type d’utilisateur : responsables opérationnels

Clementine (1)
ƒ Société : ISL (Integral Solutions Limited)
ƒ Création : 1994
ƒ Plate-formes : Windows NT, Unix
ƒ Utilisation
ƒ Prévision de parts de marché
ƒ Détection de fraudes
ƒ Segmentation de marché
ƒ Implantation de points de vente …
ƒ Environnement intégré : #Types d’utilisateurs
ƒ Gens du métier (pas forcement des informaticiens)
ƒ Développeurs / End users
 Clementine (2)
ƒ Interface simple, puissante et complète
interface conviviale
 Clementine (3)

ƒ Techniques :
ƒ Arbres de décision
ƒ Induction de règles
ƒ Réseaux de neurones
ƒ Méthodes statistiques
Forecast Pro (1)

ƒ Société : Business Forecast Systems

ƒ Création : 1997
ƒ Plate-formes : Windows 95, NT
ƒ Utilisation
ƒ Tous domaines activités et secteurs
ƒ Notamment la prévision (5 types différents)
ƒ Outil d’analyse incomparable
ƒ Le plus utilisé dans le monde
Forecast Pro (2)
ƒ Types d’utilisateurs : PME/PMI,
administrations, consultants, universitaires,
chefs de projets,…
ƒ Facilité d’utilisation (connaissances en
statistiques non requises)
ƒ Vaste palette de choix graphiques
ƒ Valeurs observées, prévisions, valeurs calculées
sur l'historique, intervalles de confiance,
diagnostics (erreurs)
Forecast Pro (3)
Intelligent Miner (1)

ƒ Société : IBM
ƒ Création : 1998
ƒ Plate-formes : AIX, OS/390, OS/400,
Solaris, Windows 2000 & NT
ƒ Utilisation
ƒ Domaines où l’aide à la décision est très
importante (exemple : domaine médical)
ƒ Analyse de textes
ƒ Fortement couplé avec DB2 (BD relationnel)
Intelligent Miner (2)

ƒ Deux versions
ƒ Intelligent Miner for Data (IMD)
ƒ Intelligent Miner for Text (IMT)
ƒ Types d’utilisateurs : spécialistes ou
professionnels expérimentés

ƒ Parallel Intelligent Miner

Intelligent Miner (3)
ƒ L’IMD
ƒ Sélection et codage des données à explorer
ƒ Détermination des valeurs manquantes
ƒ Agrégation de valeurs
ƒ Diverses techniques pour la fouille de données
ƒ Règles d’association (Apriori), classification (Arbres
de décision, réseaux de neurones), clustering,
détection de déviation (analyse statistique &
visualisation)
ƒ Visualisation des résultats
ƒ Algorithmes extensibles (scalability)
 Intelligent Miner (4)
ƒ IMT = analyse de textes libres
ƒ Trois composants
ƒ Moteur de recherche textuel avancé (TextMiner)
ƒ Outil d'accès au Web (moteur de recherche
NetQuestion et un méta-moteur)
ƒ Outil d'analyse de textes (Text Analysis)
ƒ L'objectif général est de faciliter la
compréhension des textes
Intelligent Miner (5)
MineSet (1)

ƒ Société : SGI (Silicon Graphics Inc.)

ƒ Création : 1996
ƒ Plate-forme : Silicon Graphics
ƒ Utilisation
ƒ Services financiers
ƒ Prise de décisions
ƒ Algorithmes de visualisation avancés
MineSet (2)
ƒ Interface visuelle 3D
 MineSet (3)

ƒ Interface graphique
ƒ client/serveur
ƒ Tool Manager (Client)
ƒ DataMover (Server)
ƒ Utilisateurs
ƒ Managers
ƒ Analystes
MineSet (4)
ƒ Tâches
ƒ Règles d’association
ƒ Classification
ƒ Présentation de la connaissance
ƒ Arbre
ƒ Statistiques
ƒ Clusters (nuages de points)
Synthèse
Autres techniques de Data Mining

ƒ Web mining (contenu,

usage, …)

ƒ Visual data mining (images)

ƒ Audio data mining (son,

musique)

ƒ Data mining et requêtes

d’interrogation
“intelligentes”
Visualisation de données

ƒ Données dans un base de

données ou un entropot de
données peuvent être
visualisées :
ƒ À différents niveaux de
granularité ou d’abstraction
ƒ A l’aide de différentes
combinaisons d’attributs ou
dimensions
ƒ Résultats des outils de Data
Mining peuvent être présentées
sous diverses formes visuelles
Box-plots dans StatSoft
Scatter-plots dans SAS
Enterprise Miner
Règles d’association dans
MineSet 3.0
Arbres de décision dans
MineSet 3.0
Clusters dans IBM Intelligent
Miner
 Résumé
ƒ Data mining : découverte
automatique de “patterns”
intéressants à partir d’ensembles de
données de grande taille
ƒ KDD (Knowledge discovery) est un
processus :
ƒ pré-traitement
ƒ data mining
ƒ post-traitement
ƒ Domaines d’application :
distribution, finances, biologie,
médecine, télécommunications,
assurances, banques, ...
 Résumé
ƒ L’information peut être extraite à
partir de différentes types de
bases de données (relationnel,
orienté objet, spatial, WWW, ...)
ƒ Plusieurs fonctions de data mining
(différents modèles) : clustering,
classification, règles d’association,
...
ƒ Plusieurs techniques dans
différents domaines :
apprentissage, statistiques, IA,
optimisation, ....
Résumé

ƒ Plusieurs problèmes
ouverts :
ƒ Visualisation
ƒ Parallélisme et
distribution
ƒ Issues de sécurité et
confidentialité

ƒ Futur prometteur …
 Références bibliographiques (1)

ƒ Georges Gardarin
ƒ Université de Versailles (laboratoire PRISM)
ƒ Internet/intranet et bases de données – Data Web,
Data Warehouse, Data Mining, Ed. Eyrolles
ƒ http://torquenada.prism.uvsq.fr/~gardarin/home.html
ƒ Rakesh Agrawal (IBM)
ƒ IBM Almaden Research Center
ƒ http://www.almaden.ibm.com/cs/people/ragrawal/
ƒ Mohammed Zaki
ƒ Rensselaer Polytechnic Institute, New York
ƒ http://www.cs.rpi.edu/~zaki/
 Références bibliographiques (2)

ƒ Vipin Kumar
ƒ Army High Performance Computing Research Center
ƒ http://www-users.cs.umn.edu/~kumar
ƒ Rémi Gilleron
ƒ Découverte de connaissances à partir de données,
polycopié (Université de Lille 3)
ƒ http://www.univ-lille3.fr/grappa
ƒ The Data Mine
ƒ http://www.cs.bham.ac.uk/~anp/TheDataMine.html
ƒ Knowledge Discovery Nuggets (Kdnuggets)
ƒ www.kdnuggets.com
Références bibliographiques (3)

•"Data Mining: Concepts and Techniques“

by Jiawei Han and Micheline Kamber,
Morgan Kaufmann Publishers,
August 2000. 550 pages. ISBN 1-55860-489-8
 Conférences - Historique

ƒ 1989 Workshop IJCAI

ƒ 1991-1994 Workshops KDD
ƒ 1995-1998 Conférences KDD
ƒ 1998 ACM SIGKDD
ƒ 1999- Conférences SIGKDD
ƒ Et plusieurs nouvelles conférences DM …
ƒ PAKDD, PKDD
ƒ SIAM-Data Mining, (IEEE) ICDM
ƒ etc.
 Conférences - Journaux

“Standards”
“Standards”
ƒ DM: Conférences : KDD, PKDD, PAKDD, ...
Journaux : Data Mining and Knowledge
Discovery, CACM
ƒ DM/DB: Conférences : ACM-SIGMOD/PODS, VLDB, ...
Journaux : ACM-TODS, J. ACM,
IEEE-TKDE, JIIS, ...
ƒ AI/ML: Conférences : Machine Learning, AAAI, IJCAI,
...
Journaux : Machine Learning, Artific. Intell.,
...