1

2
 La maturité
scientifique
Reconnaissance des Formes

Intelligence Artificielle

Data
Analyse de Données
Mining

Bases de Données

Réseaux

3
1945 2000 2002
 Représentation et manipulation de connaissances symboliques
Systèmes de mémorisation et de stockage de l’information

Reconnaissance des Formes

Protocoles de communication et d’échange de l’information
Processus de perception et de reconnaissance de formes et de structures

Intelligence Artificielle
Base
s de
Don
ux
sea

nées

L’édifice cognitif
4
Ré
 stockées dans des
bases de données …

Analyse de
données…

Data réparties sur un

réseau …
Mining

pour la
reconnaissance/découverte
de structures/connaissances La spirale
technologique5
 Exploration
de
Data
données
Mining

Fouille
de
Données

KDD ?
6
Comment détecter des ressemblances, des structures, des motifs a priori ?

Jean-Paul

Samia

Lin

Samy

7
8
Système de Reconnaissance de Formes Classique

Monde Pré-
Physique Codage traitements Analyse

Apprentissage Décision

Interprétation

9
 A Apprentissage

B Décision

A = Ensemble d ’échantillons pour chaque classe

A = ∅ ⇒ Apprentissage Non Supervisé
A ≠ ∅ ⇒ Apprentissage Supervisé
10
Codage Prétraitement Analyse
Filtrage du bruit
e

Décision
Normalisation
ag
ss
Squelettisation
nti
Segmentation
pre
Ap
«3»
avec un score de
0.6

11
Dans le cas NON supervisé, les techniques spécifiques utilisées sont typiques des
applications dites de Fouille de Données

• Classification

• Segmentation

12
 Un problème typique visuel qui pourrait relever de la problématique de la Fouille de
Données plus que Reconnaissance des Formes

On donne ces données stockées

sur des supports électroniques
hétérogènes et non centralisés :

Alors sans intervention de type supervisé (cad sans apprentissage avec exemples), le système parvient à détecter (structurer, extraire) la
présence de 10 formes différentes sans forcément les reconnaître, ou bien de 4 scripteurs différents sans forcément les identifier dans un
premier temps :

13
Outre le paradigme de Reconnaissance des Formes, cette intégration nouvelle ou ce paradigme
nouveau est la résultante de problématiques arrivées à maturité ou à leur limite comme :

• Les systèmes experts issus de l’IA

• Les bases et les entrepôts de données
• Les protocoles réseaux normalisés

Créer une intelligence des systèmes, avec les potentialités de chacun des outils technologiques
intégrés -> le rêve de système pensant plus que pensé

Différence de points de vue entre : SELECTIONNE moi les NOMS des CLIENTS ayant
acheté du NUTELLA et du SAVON (requête de type SQL) et je (le logiciel) te (l’utilisateur du
logiciel) fais remarquer que les clients qui achète du Nutella achètent aussi du Savon

14
Système Expert Classique

15
Base de Données Classique

Protocole de Communication Réseau Classique

16
 applicat ion 1 applicat ion 2
LES VUES EXTERNES
Les Virtuelles … côté client
dans le cadre du OLTP classique

PROD_VINS EXPEDITIONS

Schéma ext erne Schéma ext er

CREATE VIEW <nom_vue> VITICULTEURS

[(liste_attributs)]
AS <expression_de_sélection> VINS COMMANDES BUVEURS
[WITH CHECK OPTION]
Schéma concept uel

• Recalculé à chaque transaction l’impliquant

• L'expression de sélection peut porter sur des tables de
base et/ou des vues
• [WITH CHECK OPTION] : à manipuler avec des pincettes car
le problème des mmises à jour de la base au travers des 17
vues est loin d’être efficacement résolu
 LES VUES EXTERNES

Les Concrètes … côté serveur

Dans le cadre de l’OLAP, ROLAP,MROLAP
Pour le data warehouse

CREATE CONCRETE VIEW

<nom_vue> [(liste_attributs)]
AS <expression_de_sélection>

• Vue Stockée en dur

• Si Vue souvent utilisée;
• Si Tables sources peu modifiées;
• Alors Mise à Jour par TRIGGER ou déclencheurs mais
pas automatique;
• Alors Vues orientées objets au-dessus des BDR.

18
OLTP versus OLAP
Caractéristiques OLTP OLAP

Opérations typiques Mise à jour Analyse

Type d'accès Lecture et écriture Lecture

Niveau d'analyse Elémentaire Global

Ecrans Fixe Interactif

Quantité d'info échangée Faible Importante

Orientation Ligne Multi-dimensions

Taille BD 100MB-GB 1GB - TB

Ancienneté des données Récente Historique

19
 Motivations des entreprises
• Besoin des entreprises
–accéder à toutes les données de l’entreprise
–regrouper les informations disséminées dans les bases
–analyser et prendre des décisions rapidement (OLAP)

• Exemples d'applications concernées

–Bancaire : suivi des clients, gestion de portefeuilles
•mailing ciblés pour le marketing
–Grande distribution : marketing, maintenance, ...
•produits à succès, modes, habitudes d’achat
•préférences par secteurs géographiques
–Télécommunications : pannes, fraudes, mobiles, ...
•classification des clients, détection fraudes, fuites de clients, etc.
–Médecine, Pharmacie, Bourse, Production, …
20
L'approche entrepôt de données
•Datawarehouse
–Ensemble de données historisées variant dans le temps,
organisé par sujets, consolidé dans une base de données
unique, géré dans un environnement de stockage particulier,
aidant à la prise de décision dans l’entreprise.
•Trois fonctions essentielles :
–collectede données de bases existantes et chargement
–gestion des données dans l’entrepôt
–analyse de données pour la prise de décision

21
 Architecture type
Présentation

Datawarehouse
Exploration Analyse
Client Client
BD
décisionnel décisionnel
Entrepôt

Médiateur

Transformation, Fusion
Extraction, Filtrage
Moniteur/Adapteur Moniteur/Adapteur

Sourc Moniteur/Adapteur BD Source

e
Données
BD source opérationnelles
Données externes
BD légataires 22
 Datamart (Magasin de données)
•sous-ensemble de données extrait du
datawarehouse et ciblé sur un sujet unique
Bases
multidimensionnelles
Data Warehouse

Bases de
production

Data Marts
SGBD
relationnel

Outils Outils
d’alimentation d ’extraction Bases
Bases externes relationnelles
23
Modélisation multidimensionnelle
•Dimensions:
–Temps
–Géographie
–Produits
–Clients
–Canaux de ventes.....
•Indicateurs:
–Nombre d’unités vendues
–CA
–Coût
–Marge.....
24
 Le data cube et les dimensions
Axe d'analyse: La géographie
(Pays - région - ville)

Variables analysées:
Nb unités, CA, marge...

Axe d'analyse: Les produits

(classe, produit)

Axes d'analyse: dimensions

Axe d'analyse: Le temps Variables analysées: indicateur
(Année, trimestre, mois, semaine) 25
 La granularité des dimensions

Temps Jours Mois Trimestres Années

Géographie Villes Régions Pays

Produits Numéros Types Gammes Marques

26
 La navigation
multidimensionnelle
Projection en 2 dimensions Coupe d ’un cube
Produits Produits
pour une région donnée
CA CA

Région
Temps en semaines
Réduction selon 1 dimension
Produits Zoom selon une dimension
France

CA Est Sud Ouest

Temps en mois
Lyon Marseille Nice
27
 Bilan OLAP

• La modélisation multidimensionnelle est adaptée à

l ’analyse de données

• Le datacube est au centre du processus décisionnel

–transformation et visualisation 3D
–une algèbre du cube :
•Slice, Dice, Rollup, Drilldown (SQL spécifique)

28
 Qu ’est-ce-que le data mining ?
• Data mining
–ensembles de techniques d'exploration de données afin d'en tirer
des connaissances (la substantifique moelle) sous forme de modèles
présentées à l ’utilisateur averti pour examen

Données Data
entrepôt mining Connaissances
Découverte de Compréhension
modèles Prédiction
• Connaissances
–analyses (distribution du trafic en fonction de l ’heure)
–scores (fidélité d ’un client), classes (mauvais payeurs)
–règles (si facture > 10000 alors départ à 70%)
29
 Mécanismes de base
•Déduction : base des systèmes experts
–schéma logique permettant de déduire un théorème à partir
d'axiomes
–le résultat est sûr, mais la méthode nécessite la connaissance de
règles
•Induction : base du data mining
–méthode permettant de tirer des conclusions à partir d'une série
de faits
–généralisation un peu abusive
–indicateurs de confiance permettant la pondération

30
 Découverte de modèles
•Description ou prédiction

Confiance
Entrées
Sortie

•Apprentissage sur la base

•Utilisation pour prédire le futur
•Exemple : régression linéaire Y = a X + B
31
Le matériel biologique

32
 A ce compte là, il ne s’agit plus d’apprendre donc de reconnaître mais déjà de comprendre donc de structurer

33
Comment analyser, visualiser, structurer des grandes masses de données réparties, hétérogènes
>cDNA inconnu

AATGCAAGTGCATGCATGCATGCATCGGATCGTACGGATTGCAGTTCGGATTCATAATAA
ATGCGTAAAAACAGTAGTTTCACTAGTTTCAAAAGTTGCATAATACTTGCTGTTCTTCTT
GTTTACCCTAACAGTATGGCTGTTTTCGCTGTTGCTGCTGACGGTATACCTTTCCCTTAC
CACGCTAAATACAGTAACGGTGCTATAAGTCCTCTTCACGTTACTCAAAGTAGTGGTAAC
AGTAGTGTTAAAGCTGAATGGGAACAATGGAAAAGTGCTCACATAACTAGTGACCTTAAC
GGTGCTGGTGGTTACAAATACGTTCAACGTGACATAAACGGTAACACTGACGGTGTTAGT
GAAGGTCTTGGTTACGGTCTTATAGCTACTGTTTGCTTCAACGGTGCTGACAGTAACGCT
CAAACTCTTTACGACGGTCTTTACAAATACGTTAAAAGTTTCCCTAGTGCTAACAACCCT
AACCTTATGGGTTGGCACATAAACAGTAGTAACAACATAACTGAAAAAGACGACGGTATA
GGTGCTGCTACTGACGCTGACGAAGACATAGCTGTTAGTCTTATACTTGCTCACAAAAAA
TGGGGTACTAGTGGTAAAATAAACTACCTTAAAGCTGCTCGTGACTACATAAACAAAAAC
ATATACGCTAAAATGGTTGAACCTAACAACTACACTCTTAAACTTGGTGACATGTGGGGT
GGTAACGACTTCAAAAACGCTACTCGTCCTAGTTACTTCGCTCCTGCTCACCTTCGTATA
TTCTACGCTTACACTGGTGACAAAGGTTGGATAAACGTTGCTAACAAACTTTACACTACT
GTTAACGAAGTTCGTAACAAATACGCTCCTAAAACTGGTCTTCTTCCTGACTGGTGCGCT
GCTAACGGTACTCCTGAAAGTGGTCAAAGTTTCGACTACGACTACGACGCTTGCCGTGTT
CAACTTCGTACTGCTATAGACTACAGTTGGTACGGTGACGCTCGTGCTGCTGCTCAAAGT
GACAAAATGAACAGTTTCATAGCTGCTGACACTGCTAAAAACCCTAGTAACATAAAAGAC
GGTTACACTCTTAACGGTAGTAAAATAAGTAGTAACCACAGTGCTAGTTTCTACAGTCCT
GCTGCTGCTGCTGCTATGACTGGTACTAACACTGCTTTCGCTAAATGGATAAACAGTGGT
TGGGACAAAGTTAAAGACAGTAAAAAATACGGTTACTACGGTGACAGTCTTAAAATGCTT
ATAATGCTTTACATAACTGGTAACTTCCCTAACCCTCTTAGTGACCTTAGTAGTCAACCT
AGTCCTGGTGACCTTAACGGTGACGGTGAAATAGACGAACTTGACATAGCTGCTCTTAAA
AAAGCTATACTTAAACAAAGTACTAGTAACATAAACCTTACTAACGCTGACATGAACCGT
GACGGTGCTATAGACGCTAGTGACTTCGCTATACTTAAAGTTTACCTTTAAT

34
35
Tableau 1. Tableau récapitulatif des base de données biologiques accessibles sur l'Internet.
Biomedical PubMed [Link]/entrez/[Link]
literature
Nucleic acid GenBank Idem
sequence
SRS at EMBL/EBI [Link]
Genome Sequence Entrez Genome
[Link]/tdb
TIGR databases
Protein sequence GenBank

SWISS-PROT at [Link]/spro/
ExPASy

PIR [Link]
Protein Structure Protein Data Bank [Link]/pdp/
Entrez Structure DB
Protein and peptide PROWL [Link]
mass spectroscopy
Biochemical PathDB
pathways KEGG [Link]/kegg/
WIT [Link]
Microarray Gene Expression [Link]
Links
…
36
Un système d’Extraction de Connaissances

Rough Clear
Information Information
37
Les étapes du processus de KDD
• Comprendre le domaine d’application
• Sélection d’un ensemble de données
• Nettoyage et pré-traitement des données (peut prendre 60% de
l’effort)
• Choix des fonctionnalités du data mining
– classification, consolidation, régression, association,
clustering.
• Choix de(s) l’algorithme(s) d’extraction
• Data mining : Recherche des motifs (patterns) intéressants
• Évaluation des Patterns et présentation
– visualisation, transformation, suppression des patterns
redondants, etc.
• Utilisation de la connaissance extraite 38
 Des techniques issus de l’IA et de la RF

Machine learning techniques such as :

• Arbre de décision • Réseaux de neurones
• Règles d’association • Clustering

Des systèmes combinant les technologies Réseaux et BD

• SQL • FTP
• TCP/IP • Php / mySQL

Des champs d’applications très diversifiés

• Commerce – Economie • Bio-informatique
• Web Mining et Marketing • Médecine
39
Principe global

L’importance pratique et industrielle des procédés d’analyse automatique et intelligente

de données, textes, images, sons ou enregistrements électroniques est telle que
beaucoup de recherches spécialisées se sont développées.

Nous cherchons ici à en donner une idée et à en dégager les points communs qui sont le
propre de la méthodologie de la Fouille de Données.

C’est essentiellement dans la conception des processus de discrimination (ou

d’affectation à diverses catégories) que l’on retrouve une méthodologie commune,
à quelques variantes près.

En gros une telle fonctionnalité est constituée de plusieurs composantes, correspondant

à plusieurs phases de traitement. On en distinguera essentiellement deux, les
autres pouvant s’échelonner entre les deux extrêmes :
1. Le prétraitement
2. La découverte de catégories proprement dite

Un fait remarquable en FD est que chaque application fait appel à plusieurs techniques
parmi celles présentées ici, avec une interrelation parfois surprenante où l’invention
et le flair de l’ingénieurs sont rois.

40
Des algorithmes

Une évolution plus qu’une

révolution

Un cocktail de techniques

41
Des algorithmes

D’inspirations …

Mathématiques : stat. et AD

Calculatoires

Biologiques

42
Des algorithmes

Calculatoires
« Clustering »
Arbres de décision
Règles d’association
Programmation dynamique

Biologiques
Réseaux de neurones
Algorithmes génétiques
43
Des algorithmes
Non Supervisés
Apprentissage a priori en mode Découverte

« Clustering »
Algorithmes génétiques
Règles d’association

Supervisés
Apprentissage a posteriori en mode Reconnaissance -
Prédiction
Réseaux de neurones
Arbres de décision
Programmation dynamique 44
 Cas pratique avec les mains
Cas de marketing classique : identification de profils de clients et
organisation d'une campagne de marketing direct
Il s'agit d'un voyagiste organisant des circuits touristiques avec 5 types de
prestation (A,B,C,D et E). Son directeur marketing souhaite mettre en
place une politique de fidélisation.
Décomposition en sous-problèmes précis :
Fidéliser la clientèle ?
Clientèle ?

Typologie de problèmes à résoudre :

Structuration : qui sont mes clients ?
Affectation : quels sont les clients à contacter ?

Objectifs :
1. Connaître les clients pour revoir les offres et la politique marketing.
2. Fournir à la cellule marketing opérationnelle et aux réseaux de
distribution une liste ciblée de clients par requête SQL, ce qui implique
45
des critères compréhensibles
Cas pratique avec les mains

Sélections des données

Recherche des pertinentes
Data Input Informations (ex. : filtre « Si le client n'a effectué
aucun achat au cours des 5 dernières
(SQL, perl, ftp, Java, XML...) années,
alors pas d'extraction »)

Action sur les Nettoyage des

variables données Fichier de 1400
(ex. : filtre « si le client est (ex. : filtre « si le client est né
né le 01/01/1901, le 01/01/1901, clients à analyser
alors suppression du alors suppression du
fichier » fichier » »
Apprentissage des 2
Choix d'un classes :
Clustering en 9 types segment de client mono et multi
de clients pertinent acheteurs
(ex. : algorithmes hiérarchiques, à modéliser (ex. : Arbre de décision, réseaux
K-Means etc.) de neurones)

Knowledge Validation et interprétation

(ex. : ce sont les erreurs ou confusions du
Output sous prédicteurs
qui constituent une connaissance très intéressante :
forme de règle de « Les prospects : les monoacheteurs prédits
décision (ex. : arbre de multiacheteurs (15 %) » 46
décision)
 Chapitre I. Apprentissage a priori
par Similitude
Clustering

Voici un des enjeux du processus de data mining : comment

comparer des éléments disparates pour les rassembler ou au
contraire les différencier ? 47
Objectifs :

• Comprendre la notion d’apprentissage NON supervisé

• Le lier à la notion de Découverte de Structures

• Connaître des algorithmes de regroupement

• Hiérarchiques et leur représentation graphique : dendrogramme
• par Optimisation type K-Means, ISODATA

• Comprendre que la notion de Similitude liée à la vaste notion

mathématique de Distance est subjective mais centrale dans cette
problématique
•Savoir construire un espace de mesure multi-dimensionnelle et
définir une mesure de similarité dans cette espace

•Savoir choisir l’algorithme à utiliser en fonction des données en

entrée
48
Principes

Contexte non supervisé

« Révéler » l’organisation de motifs

en groupes cohérents

Subjectif

49
Disciplines Synonymes

Biologie
Zoologie Apprentissage non supervisé
Psychiatrie Taxonomie
Sociologie Typologie
Géologie Partition
Géographie

50
Définition
Le clustering consiste à construire un classificateur intrinsèque, sans
classes connues a priori, par apprentissage à partir d’échantillons
donnés.
Le nombre de classes possibles est en général connu et on veut
construire le classificateur K : M->{1..c} partitionnant l’espace M des
mesures.

Hypothèse
Plus deux échantillons sont proches dans M, plus leur probabilité
d’appartenir à la même classe est grande.

51
ko/(largeur*hauteur)
? bmp gif
Format

%Contour

Ng moyen
52
Notion d'espace, de dimension ... Image∈CxNxF
Cadre numérique
Vecteurs de caractéristiques
V(x1,x2,x3,x4)

Différentes natures des caractéristiques

Continue
Discrète
Ordinal
Nominal
… 53
« Clustering »

Imaginez un lien avec une requête SQL

54
Algorithme Séquentiel Basique
(ASB) :
INPUT : S={x1,x2,…,xN}, seuil de distance Θ et seuil de nombre
de classes q

•m=1
• Cm={x1}
• For i=2 to N
 Find Ck : d ( xi , Ck ) = min 1≤j≤m d(xi,Cj)
 If ( d( xi , Ck ) > Θ ) AND ( m < q ) then
 m = m+1
 Cm = {xi}
 Else
 Ck = Ck ∪ {xi}
 Where necessary, update representatives.
 End {If}
• End {For}

OUTPUT : une classification dure R= ∪ Ci 55

« Clustering » Algorithme Séquentiel Basique
Modifié (ASBM) :
Cluster Determination
• m=1
• Cm={x1}
• For i=2 to N
 Find Ck : d ( xi , Ck ) = min 1≤j≤m d(xi,Cj)
 If ( d( xi , Ck ) > Θ ) AND ( m < q ) then
 m = m+1
 Cm = {xi}
 End {If}
• End {For}

Pattern Classification
• For i=1 to N
 If xi has not been assigned to a cluster, then
 Find Ck : d ( xi , Ck ) = min 1≤j≤m d(xi,Cj)
Remarque :
 Ck = Ck ∪ {xi} new old
(nCk − 1)mCk +x
Where necessary, update representatives Si d(x, C) = d(x, m C ) alors m Ck
new
= new
nCk
 End {If}
• End {For}
56
6

5 x1

x5
x2 Ordre :
4
x7
x1,x2,x3,x4,x5,x6,x7,x8
3 x8 x3

2 x4 x6

0
0 1 2 3 4 5 6 7

5 x1
x2
4 x5

x7
3 x8 x3
Ordre :
x1,x2,x5,x3,x8,x6,x7,x4 2 x4 x6

0
0 1 2 3 4 5 6 7
57
Notes sur l’algorithme ASB :

• Cet algorithme séquentiel est bien adapté pour traiter des

échantillons à mesure de leur acquisition (analyse on-line)

• mais fournit des résultats dépendant de l’orde de présentation

(arbitraire)

58
« Clustering »

59
« Clustering »

Quantifier la similarité entre :

2 vecteurs de caractéristiques

2 ensembles de vecteurs de
caractéristiques

60
« Clustering »
Soit X = { x1 ,..., xN }

Hard On appelle m-clustering de X la partition de X en m ensembles (clusters)

C1 , ..., C m tels que :
Clustering
Ci ≠ ∅ , i = 1,..., m
∪im=1 C i = X
Ci ∩ C j = ∅, i ≠ j , i, j = 1,..., m

Soit X = { x1 ,..., x N }

Le m-clustering flou de X en m clusters est caractérisé par

m fonctions d' appartenance u j avec :

Fuzzy u j : X → [0,1], j = 1,..., m

Clustering m

∑ u ( x ) = 1,
j i i = 1,..., N
j =1
N
0 < ∑ u j ( xi ) < N , j = 1,..., m
Zadeh (1965) i =1
61
« Clustering »
Mesure de (dis)similarité
Mesures de
Mesure de (dis)similarité
proximité métrique ou Distance
Distinction importante surtout d’un point de vue thérorique et de propriétés
de convergence des algorithmes

d : X × X → ℜ telle que :

∀x, y ∈ X, d(x, y) ≥ 0
Mesure de d(x, x) = 0 ∀x ∈ X
d(x, y) = d(y, x) ∀x, y ∈ X
(dis)similarité
métrique d(x, y) = 0 ⇔ x = y

d(x, z) ≤ d(x, y) + d(y, z) ∀x, y, z ∈ X

62
 A partir de maintenant,

« Clustering » Point = vecteur de caractéristiques

Ensemble = ensemble de vecteurs de caractéristiques

Mesures de proximité entre 2 points

Valeurs réelles
1/ p
Valeurs discrètes
 N p
d p ( x, y ) =  ∑ wi xi − yi  Les coordonnées des vecteurs appartiennent
 i =1  à un ensemble fini F = { 0,1,..., k - 1} , k ≥ 0

Distances de Si x,y ∈ F l ,on définit la matrice

Mahalanobis, de contingence A( x, y ) k ×k = [aij ] par :
euclidienne, aij = nombre de places où le premier vecteur
Manhattan, a le symbole i et l' élément correspondant du
infini
second vecteur a le symbole j
sinner = xT y (corrélation)
d Hamming ( x, y ) = ∑i =0 ∑ j =0, j ≠i aij
k −1 k −1
T
x y
sTanimoto = 2 2
x + y − xT y
63
 Exemple: distance de Manhattan
Age Salaire
Personne1 50 11000 d(p1,p2)=120
Personne2 70 11100
Personne3 60 11122
d(p1,p3)=132
Personne4 60 11074
Conclusion: p1 ressemble plus à
p2 qu’à p3 

z-scoring Age Salaire

Personne1 -2 -0,5
d(p1,p2)=4,675
Personne2 2 0,18
Personne3 0 0,32 d(p1,p3)=2,324
Personne4 0 0
Conclusion: p1 ressemble
mage=60, sage =5
plus à p3 qu’à p2 
msalaire=11074 ssalaire=48 64
 Exemple: le problème de normalisation des données
: cas des intervalles
Il faut standardiser les données en calculant une mesure
normalisée par la moyenne et l'écart type du feature f : ce qu'on
appelle le z-score.

〚 〛
Soit la matrice de n données suivantes : x 11 x 12 ... x 1f ... x 1p
On définit alors la matrice standardisée ... ... ... ... ... ...
des z-scores par : x i1 x i2 ... x if ... x ip
 x if −m f  ... ... ... ... ... ...
z if =
sf x n1 x n2 ... x nf ... x np

Avec mf la moyenne du feature en colonne et sf son écart type

absolu moyen (plus robuste que la variance classique)

65
 Exemple : Variables binaires
 Une table de contingence pour données binaires
a= nombre de positions
Objet j où i a 1 et j a 1
1 0 Sum
1 a b a+b
Objet i 0 c d c+d

Sum a+c b+d p

 Exemple oi=(1,1,0,1,0) et oj=(1,0,0,0,1)
a=1, b=2, c=1, d=1
66
 Exemple : variable binaire et Mesures de distances
 Coefficient d’appariement (matching) simple
(invariant pour variables symétriques):

bc
d i , j =
abcd 

Exemple oi=(1,1,0,1,0) et oj=(1,0,0,0,1) : d(oi, oj)=3/5

 Coefficient de Jaccard (pour variables asymétriques)
d(oi, oj)=3/4 d i , j=
bc 
abc 
67
 Exemple : Variables binaires (I)

 Variable symétrique: Ex. le sexe d’une personne, i.e coder

masculin par 1 et féminin par 0 c’est pareil que le codage
inverse

 Variable asymétrique: Ex. Test HIV. Le test peut être positif ou

négatif (0 ou 1) mais il y a une valeur qui sera plus présente
que l’autre. Généralement, on code par 1 la modalité la moins
fréquente
 2 personnes ayant la valeur 1 pour le test sont plus

similaires que 2 personnes ayant 0 pour le test

68
 Exemple : Variables binaires(II)
 Exemple
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
 Sexe est un attribut symétrique
 Les autres attributs sont asymétriques
 Y et P ≡ 1, N ≡ 0, la distance n’est mesurée que sur les asymétriques

d  jack , mary =01/ 201=0,33

d  jack , jim=11/111=0,67
d  jim , mary =12 /112=0,75

Les plus similaires sont Jack et Mary⇒atteints du même mal

69
 Exemple : Variables Nominales

• Une généralisation des variables binaires, ex: rouge, vert et bleu

• Méthode 1: Matching simple
– m: # d’appariements, p: # total de variables
 p−m
d i , j =
p

• Méthode 2: utiliser un grand nombre de variables binaires

– Créer une variable binaire pour chaque modalité (ex: variable
rouge qui prend les valeurs vrai ou faux)

70
 Exemple : Variables Ordinales
• Une variable ordinale peut être discrète ou continue
• L’ordre peut être important, ex: classement
• Par contre, l'écart entre deux valeurs n'est pas équivalent :
exemple, le degré de douleur de 1 à 10 : l'écart entre 5 et 7 n'a pas
la même signification qu'entre 7 et 9.
• Peut-être traitée comme “interval-scaled” (f est une variable)
– remplace xif par leurs rangs rif ∈{1,..., M f }
– mappe la dynamique de chaque variable sur [0, 1] en
remplaçant le i-ème objet dans la f-ième variable by
rif −1
zif =
Mf − 1

71
 Exemple : Google ou Similarité entre
documents
Créer des moteurs de recherche comprenant le langage naturel
-> évolution de google au-delà des mots clés
-> le « text-mining » ou le « web-mining »

Collection : ensemble des documents

Vector Space Model (VSM) : espace à N dimensions où N est le

nombre de termes utiles dans le langage (« le », « la »... sont inutiles et
sont appelés stop-words)

72
Etape 1 : Pour chacun des N termes du langage, création d'un Inverse Index qui stocke
pour chaque terme du langage les documents l'utilisant
• calcul du Document Frequency = nb doc utilisant ce terme / nb total de document
= df (Plus df grand, moins le terme a d'importance d'un point de vue informatif)
• soit idf = log (1/df)
Etape 2 : Pour chaque document,
•Pour chaque terme, calcul du Term Frequency (Plus tf est grand dans un document
plus ce terme doit être important par rapport au sujet du document)
•Calcul d'un vecteur caractéristique VSM :
• Pour i allant de 0 à N, VSM[i] = tf(terme i dans ce document)*idf(terme i)
• On normalise ce vecteur pour que ||VSM(document)||=1

Chaque requête de l'utilisateur est associée de le même façon à un

VSM(requête) et la Similarité est calculée par produit scalaire (voir
clustering pour indexation et optimisation, voir ontologies pour web
sémantique)
73
 Si on veut être plus stastisticien :
« Clustering »
Mesures de proximité entre 2 vecteurs-distributions : le cadre fréquentiste
Dans le cadre du texte mining, la distance du chi2
est la distance euclidienne entre deux vecteurs-
documents normalisés par leur longueur (nombre
de mots), pondérée par la masse de chacun des
mots par rapport à l'ensemble des textes (nombre
total d'un mot dans l'ensemble des textes)

En fait, la distance du chi2

permet de comparer deux
histogrammes de valeurs ou
encore deux distributions de
74
probabilité
Très utile dès qu'on veut comparer des histogrammes, des
distributions de probabilités....

Pour les documents (un feature = un mot)...

...ou pour les images (un feature = un niveau de gris)...

75
A vous de former des exemples, avec des tailles d'image ou de document différentes. 76
 « Clustering »
Mesures de proximité entre 2 vecteurs-distributions : le cadre probabiliste
La distance de Kullback-Leibler entre les documents D1 et D2 :

Pas une vraie distance. Pas symétrique. Appelée divergence.

77
« Clustering »

Valeurs floues
x1=(1,1)
x = ( xi ) i∈[1, N ] , xi ∈ [0,1] x3=(3/4,3/4)
s ( xi , yi ) = max( min (1 − xi ,1 − yi ) , min( xi , yi ) Zone d’incertitude
x4=(1/2,1/2)

1/ p x2=(1/4,1/4)
 N 
s F ( x, y ) =  ∑ s ( xi , yi ) p 
p

 i =1 
(0,0)
Propriétés :
s Fp max = N 1/ p et s Fp min = 0,5 N 1/ p sF(x1,x1) =
sF(x2,x2) = A comparer aux
distances
Si p → ∞ : sF(x3,x3) = euclidiennes !!
s F∞ ( x, y ) = max1≤i ≤ N s ( xi , yi ) sF(x4,x4) =
sF(x1,x3) =
Remarque : d F ( x, y ) = s F ( x, y ) sF(x2,x4) = 78
Finalement, dans le cas de mélanges de variables de différents types on
calcule une distance entre éléments à partir d'une moyenne pondérée
des distances définies pour chaque feature (ou dimension d'analyse ou
variable) : d'un point de vue mathématique, on parle de combinaison
linéaire, d'où en partie l'aspect matriciel des algorithmes

Proposer une mesure de dissimilarité pour les données étudiantes

suivantes :
Nom de la Note Personal Couleur
variable Exam en Sexe TOEIC Com puter Age des yeux Motivation Origin e
{IUT, Licen ce
Domaine {vert,bleu, Gén érale,
de la m arron, Licen ce Pro,
variable [0,20] M/F O /N O/N [18,40] noir} [0,10] Master, au tre}
Type de
variable

d(e1,e2)=

79
« Clustering »

Mesures de proximité entre 1 point x

et 1 ensemble C de points
Sans prototypes Avec Prototypes
On utilise un représentant de la classe.
Dans le cas d' un cluster sphérique C,
℘pe max ( x, C ) = max y∈C ℘( x, y ) 1
on utilise le point barycentre m C = ∑y
℘pe min ( x, C ) = min y∈C ℘( x, y ) n C y∈C
et d ( x, C ) = d ( x, mC )
1
℘ moy ( x, C ) =
pe

N
∑℘( x, y)
y∈C
Dans le cas d' un cluster linéaire C,
on utilise l' hyperplan (droite) H
d' approximation optimale
a T x + a0
et d ( x, C ) = d ( x, H ) =
a
p
avec H : ∑ a j x j + a0 = a T x + a0 = 0
j =1 80
« Clustering »

Mesures de proximité entre 2

ensembles de points
℘ee max ( B, C ) = max x∈B , y∈C ℘( x, y ) D1={x1,x2,x3,x4} et D2={y1,y2,y3,y4}
X1(0,0), x2(0,2), x3(2,0), x4(2,2)
Y1(-3,0), y2(-5,0), y3(-3,-2), y4(-5,-2)
... Avec la distance euclidienne :

℘ee max ( B, C ) = 8
nB nC ℘ee min ( B, C ) = 3
℘ ( B, C ) =
ee
℘(mB , mC )
nB + nC ℘ee moy ( B, C ) = 5,6
℘ee p ( B, C ) = 7,6

Conclusion (la part d’arbitraire ou d’expertise) : “La seule façon d’arriver

un clustering des données adéquat (choix des distances, des prototypes),
c’est par essai-erreur et bien sûr, en prenant en compte l’opinion d’un
expert dans le champ d’application”
81
 « Clustering »

Nombre de « clustering » possibles S

S(15,3) = 2 375 101

S(20,4) = 45 232 115 901

S(25,8) = 690 223 721 118 368 580

S(100,5) ≈ 1068
Si 10-12 secondes par cluster formé, il faudrait 1048 an/machine. Cela justifie le
développement d’algorithme “informé”
82
« Clustering »

3 Catégories d’algorithmes :

 Séquentiels

 Hiérarchiques

 Basés sur l’optimisation d’une fonction de coût

83
Définition

Les méthodes de regroupement hiérarchique proposent une famille de

regroupements dont la taille et le nombre des classes varie (inversement
l’une de l’autre). Ces regroupements sont énumérés par un paramètre t, le
niveau.

Ils forment une hiérarchie dans le sens que si deux échantillons sont
regroupés dans une même classe au niveau t, ils le seront à tous les
niveaux supérieurs à t.

La représentation graphique idéale pour une telle hiérarchie est le

dendrogramme, car on ne produit pas un seul clustering mais une hiérarchie
de clustering imbriqués (nested clustering).

84
Algorithme Hiérarchique Basique (AHB) :

INPUT : S={x1,x2,…,xN}, Choose R0 = { Ci = {xi} , i = 1, …, N } as the initial

clustering, t = 0

• Repeat :
 t = t +1

 Among all possible pairs of clusters (Cr, Cs) in Rt-1 find the one, say
(Ci,Cj), such that Dis(Ci,Cj) = minr,s Dis(Cr,Cs)

 Define Cq = Ci ∪ Cj and produce the new clustering

Rt = (Rt-1 – {Ci,Cj}) ∪ {Cq}

• Until all vectors lie in a single cluster

OUTPUT : Un ensemble de partitions R= ∪ Ri , avec Ri = ∪ Cij

85
 Data Structures
• Data matrix
– (two modes)  x11 ... x1f ... x1p 
 
 ... ... ... ... ... 
x ... xif ... xip 
 i1 
• Dissimilarity matrix  ... ... ... ... ... 
– (one mode) x ... xnf ... xnp 
 n1 

 0 
 d(2,1) 0 
 
 d(3,1) d ( 3,2) 0 
 
 : : : 
d ( n,1) d ( n,2) ... ... 0
86
7

6
x5 Matrice des Motifs
5
x4
1 1
4
x3
2 1 
3 
2 D( X ) =  5 4
x1 x2
 
6 5
1

6,5 6
0
0 1 2 3 4 5 6 7

Matrice des Dissimilarités Matrice des Similarités

0 1 5 6,4 7,4  1 0.75 0.26 0.21 0.18

 0 4.2 5.7 6.7   1 0.44 0.35 0.2 
  
Peuclid ( X ) =  0 1.4 2.5 Ptanimoto ( X ) =  1 0.96 0.9 
   
0 1.1  1 0.98
 
  1 
0 

87
 x1 x2 x3 x4 x5
0
7
x5 1
6
x4 2

Echelle de dissimilarité
5
x3 3
4

3 4
2 5
x1 x2
1
6
0
0 1 2 3 4 5 6 7 7
8
9
10

1
x1 x2 x3 x4 x5 Les
0,9
0,8
Dendrogrammes
Echelle de similarité

0,7
Notion de durée de vie d’un cluster
0,6
0,5
0,4
0,3
0,2
0,1
0

88
Algorithme Hiérarchique Matriciel (AHM) :
• INPUT : S={x1,x2,…,xN}, Choose R0 = { Ci = {xi} , i = 1, …, N } as the initial clustering, t = 0,
P0 = P(X)

• Repeat :
 t = t +1

 Find (Ci, Cj) in Rt-1 such that Dis(Ci ,Cj ) = minr,s Dis(Cr,Cs)

 Define Cq = Ci ∪ Cj and produce Rt = (Rt-1 – {Ci,Cj}) ∪ {Cq}

Define the new proximity matrix Pt from Pt-1 (voir transparent suivant)

• Until RN-1 clustering is formed

OUTPUT : Un ensemble de partitions R= ∪ Ri , avec Ri = ∪ Cij

89
« Clustering »

Algorithme Hiérarchique Matriciel (AHM) :

• Mise à jour de la matrice Pt avec :

Dis(Cq ,Cs) = ai Dis(Ci, Cs) + aj Dis(Cj, Cs) +b Dis(Ci, Cj) + c |Dis(Ci, Cs) – Dis(Cj, Cs)|

• Single Link Algorithm ou voisin immédiat : ai = aj = ½ et b=0 et c = - ½

Dis(Cq ,Cs) = Min { Dis (Ci,Cs),Dis (Cj,Cs) }

• Complete Link Algorithm ou voisin éloigné : ai = aj = ½ et b=0 et c = ½

Dis(Cq ,Cs) = Max { Dis (Ci,Cs),Dis (Cj,Cs) }

90
ai = aj = ½ et b=0 et c = - ½ ai = aj = ½ et b=0 et c = ½ ai = aj = ½ et b=c=0

91
Effet de Chaîne

Single-link (10 clusters) Single-link (2 clusters)

Complete-link (2 clusters) Complete-link (2 clusters)

92
 2 variantes remarquables :

•Algorithme de Ward qui minimise la variance : on construit une distance

pondérée d’ij :
ni n j 2
d 'ij = d ij avec d ij = mi − m j
ni + n j
ni + ns n j + ns ns
d 'qs = d 'is + d ' js − d 'ij
ni + n j + n s ni + n j + n s ni + n j + n s

∑
2 2
Si er = x − mr est la variance du r ième cluster
x∈Cr
N −t
et E t = ∑ e r , cet algorithme forme la R t +1 partition en fusionnant les 2 clusters
2

r =1

Ci + C j qui conduisent à l' augmentation minimum de la variance totale E t

• Si ai =ni /(ni+nj) aj = nj /(ni+nj) et b= -ninj /(ni+nj)2 et c = 0

93
dqs=aidis+ajdjs+bdij=||mq-ms||2
 [Link]

3 clusters

8 clusters

A dendrogram for a part of Yeast cDNA microarray data set.

Heuristique pour le meilleur nombre de clusters : on s’arrête par exemple à la hiérarchie Rt pour laquelle

∃C j ∈R t −1 / h(C j ) > θ avec h(C ) = max{ d ( x, y ), x, y ∈ C} 94

Notes sur l’algorithme hiérarchique :

• Cet algorithme hiérarchique est bien adapté pour fournir une

segmentation multi-échelle puisqu’il donne en ensemble de
partitions possibles en C classes pour 1 variant de 1 à N,
nombre de points dans le nuage de points

•Différents niveaux de granularité sont ainsi directement

visualisable dans les données

•Peut prendre en entrée des données ou directement une

matrice de mesures de proximité sans connaissance sur
l’espace des données (voir exercice sur la phonétique).

95
« Clustering »

3 Catégories d’algorithmes :

 Séquentiels

 Hiérarchiques

 Basés sur l’optimisation d’une fonction de coût

96
97
Nuées Dynamiques

Algorithme
ISODATA

C-moyennes floues

98
Principe
les Nuées Dynamiques

99
 Schéma numérique :
Algorithme itératif de type
ISODATA
 Nombre de groupements C connu

V est un vecteur de paramètres de forme : on peut

prendre par exemple les barycentres mC des nuages de points C.

Minimisation itérative d'une fonctionnelle J qui

mesure la valeur d’un regroupement selon un
critère variable

100
Implémentation par les C-moyennes
Coefficient d ’appartenance uij dans [0,1]

V1 ui1=0.6
ui2=0.4

Minimisation de la fonctionnelle générale :

C N
J m (U ;V ) = ∑∑ u d ( xi , V j ) m
ij
2

j =1 i =1
Dans le cas dur, si uij ∈ { 0;1} :

J m (U ;V ) = J (V ) 101
 Algorithme ISODATA Dur (Nuées Dynamiques
ou K-Means ou C-moyennes) uij ∈ { 0;1}

• INPUT : S={x1,x2,…,xN}, un nombre de classes C et un ensemble de noyaux initial V0i,

i = 1, …, C, itération n=1, nombre d’itérations maximum n0

• Pour chaque valeur de k (de 1 à C), calculer

{ }
Ckn ← xi ∈ S ∀j ≠ k , d ( xi , Vkn −1 ) ≤ d ( xi , V jn −1 )
Calcul de Vkn à partir de Ckn

n −1
• Si ∀ k , C n
k ≠ C k et n ≤ en
retourner n0 ,1
Sinon arrêt

• OUTPUT : une classification dure R= ∪ Ci

102
« Clustering » Cas « Fuzzy » : uij∈ 0,1 [ ]
Dans le cas où m=2, minimisation de la fonctionnelle suivante
:
C N
J (U ;V ) = ∑∑ u d ( xi , V j ) 2
ij
2

j =1 i =1
 En utilisant la formulation lagrangienne, on montre que
minimiser J revient à résoudre ce système couplé :
N ∂d ( xi , V j )
2

∑ uij 2
=0
 i =1 ∂V j
 1
 urs = C d 2 ( x , V )


∑
j =1 d 2
i s
( xi , V j )
103
 Algorithme ISODATA Flou (Nuées Dynamiques
ou K-Means ou C-moyennes) uij∈[0,1]
• INPUT : S={x1,x2,…,xN}, un nombre de classes C et un ensemble de noyaux initial V0i, i
= 1, …, C, itération t=1, nombre d’itérations maximum t0

Répéter
• Pour chaque valeur de i (de 1 à N),
1
Pour chaque valeur de j (de 1 à C), calculer uij (t ) = C d 2 ( xi , V j )
Fin pour
∑d
k=1
2
( xi , Vk )

Fin pour
• t =t+1
• Pour chaque valeur de j (de 1 à C),
N ∂d 2 ( xi , V j )
Résoudre ∑u
i =1
2
ij (t −1)
∂V j
=0

Fin pour
Tant que un critère d’arrêt n’est pas atteint
104
• OUTPUT : une classification floue U= u[i][j] pour i de 1 à N et j de 1 à C
 « Clustering » Cas « Fuzzy » : uij∈ 0,1 [ ]
Dans le cas classique où on utilise la distance euclidienne
T
d ( xi , V j ) =( xi −V j ) ( xi −V j )
2

On met à jour les prototypes par l’équation suivante :

N

∑u 2
ij (t −1) xi
V j (t ) = i =1N
∑ ij (t −1)
u 2

i =1

Il s’agit de l’algorithme du « Fuzzy K-Means »

ou C-moyennes floues classique qui dans ce
cas fait l’hypothèse d’une distribution Normale
105
des données dans les classes
 « Clustering » [ ]
Cas « Fuzzy » : uij∈ 0,1

Ajoutons que pour m=1, il n’y a pas de clustering flou

meilleur que le meilleur des « crisp clustering ».

Mais pour m=2 (le cas étudié), il y a des cas pour

lesquels le clustering flou a de plus petites valeurs
pour J2(U;V)

106
« Clustering »
Algorithme des C-Moyennes Floues Exponentielles
(CMFE)
 Prototypes : centroïdes Vj et
matrices de covariance floue Fj
N T
∑u 2
ij ( xi −V j )( xi −V j )
Fj = i =1
N

∑ ij
u 2

i =1

 Distance : exponentielle de

[ det( F )]
1/ 2
1 
( ) ( )
j T −1
d (x , v ) =
2
e i j exp  xi − v j Fi xi − v j 
Pj 2 
107
 « Clustering »
Algorithme des C-Moyennes Floues Exponentielles
(CMFE)
Prend en compte pour chaque cluster :
•La forme
•Le nombre de points
•La densité

108
 « Clustering »
Comment déterminer
le nombre de groupements C optimal ?
Critère numérique :
la Densité Moyenne
de Partition
(DMP) ?

109
« Clustering »

Critère numérique :la Densité Moyenne de Partition

C
DPM(C)= ∑
1 S j
C j=1 Vj
Avec X j ={ x∈X :(x−V j)Fj−1(x−Vj)<1}
S j = ∑uij
xi∈X j
1/ 2
et l’hypervolume flou de chaque cluster Vj = Fj

110
Notes sur l’algorithme ISODATA :

• Cet algorithme procédant par optimisation itérative est très

simpe et très connu.

•Il a des propriétés de convergence surprenantes en pratique

(l’initialisation influe assez peu sur le résultat final par exemple)
notamment pour traiter un grand nombre de données

Pour une analyse pratique des clusters , voir Section 2.1 de l'étude de
cas : dm_case_studies.pdf

111
Exemple d’Application en biologie : l’analyse
des résultats fournis par les puces ADN

pseudo-colour
sample
(labelled) image

probe
[image from Jeremy Buhler]
(on chip)
112
Regroupement en
familles de gènes

113
Chapitre I. Apprentissage a priori
par Induction
Règles d’association

114
Complément récent aux méthodes statistiques classiques de détection de relations
entre attributs

Input : données booléennes

Output : implications logiques entre attributs ou ensemble d’attributs en utilisant la

table de vérité de l’implication logique :

x y x->y
V V V
F V V
F F V
V F F

115
Un exemple e (non supervisé) = enregistrement d’une table.
e est décrit par d attributs binaires (x1, x2, xd) ou champs.
La valeur à 1 d’un attribut pour un exemple est appelé un item.
Un ensemble d’items pour un enregistrement a été appelé un itemset.

Soit l’ensemble d’apprentissage ou la base de données suivantes contenant 10

exemples décrits par 5 attributs binaires :
x1 x2 x3 x4 x5
Couverture (ou support) de x1->x2 :
e1 0 1 0 0 1
la probabilité P(x1,x2) que x1 et x2 e2 0 0 1 0 1
soient VRAI en même temps.
e3 0 0 1 0 0
Propriété symétrique : sx1->x2=sx2->x1 e4 1 1 1 1 1
Ici, P(x1,x2)=3/10
e5 1 1 1 1 1
e6 1 1 1 1 0
Cas peu intéressants : sx->y~0 ou 1 e7 1 0 1 1 0
e8 1 0 1 1 0
e9 1 0 0 0 1
e10 1 0 0 0 1 116
Ici, {x2,x3} et {x1,x4} sont des itemsets de e5.

Association :
Implication disant que deux itemsets sont VRAI ensemble pour un nombre
suffisant d’exemples. La couverture de l’association est calculée comme
nombre d’itemsets, divisé par le nombre total d’exemples. Quand une
couverture est supérieure à une valeur MinCouv fixée à l’avance par
l’utilisateur, on dit que l’itemset constitué par cette intersection est fréquent.

Ici, si MinCouv=0.3, les itemsets (x1,x2,x3) et (x1,x3,x4) sont fréquents

avec une couverture d’association : sx1x3x5=0.3 et sx1x3x4=0.5
Du coup toutes les règles d’association associées ont une couverture
fréquente : s x1->x3=…=s x1 et x3->x5=0.3

On peut définir un algorithme rapide comme “A Priori” pour trouver les

items fréquents en utilisant s itemset1∪itemset2<=sitemset1

117
Algorithme A priori

Créer L1, l’ensemble des 1-itemsets fréquents par une consultation de la base de
données
Tant que le test d’arrêt n’est pas satisfait faire
Etape 1 : utiliser L k-1 pour produire Ck contenant les k-itemsets candidats.
NB. : Ceci se fait sans consulter la base de données
Etape 2 : Ne conserver que les itemsets de Ck qui sont fréquents : ils
constituent Lk
NB. : Ceci demande une consultation de la base de Données
Fin tant que

118
Chapitre I. Apprentissage a priori
par Induction
Règles d’association

119
 Créer des moteurs de recherche comprenant le langage naturel
-> évolution de google au-delà des mots clés
-> le « text-mining » ou le « web-mining »
Collection : ensemble des documents
Vector Space Model (VSM) : espace à N dimensions où N est le
nombre de termes utiles dans le langage (« le », « la »... sont inutiles et
sont appelés stop-words)
Etape 1 : Pour chaque terme du langage,
• création d'un Inverse Index qui stocke pour chaque terme du langage les
documents l'utilisant
• calcul du Document Frequency = nb doc utilisant ce terme / nb total de document
= df (Plus df grand moins le terme a d'importance d'un point de vue informatif)
• soit idf = log (1/df)
Etape 2 : Pour chaque document,
•Pour chaque terme, calcul du Term Frequency (Plus tf est grand dans un document
plus ce terme doit être important par rapport au sujet du document)
•Calcul d'un vecteur caractéristique VSM :
• Pour i allant de 0 à N VSM[i] = tf(terme i dans ce document)*idf(terme i)
• On normalise ce vecteur pour que ||VSM(document)||=1
Chaque requête de l'utilisateur est associée de le même façon à un
VSM(requête) et la Similarity est calculé par produit scalaire (voir
clustering pour indexation et optimisation, voir ontologies pour web 120
sémantique)
Chapitre II. Apprentissage a
posteriori par Séparatrices
Linéaires
Réseaux de Neurones

121
Inspiration Biologique

Dendrites

Soma (cell body)

Axon

122
Inspiration Biologique

dendrites
axon

synapses

La transformation de l’information symbolique

a lieu au niveau des synapses sous forme d’impulsions
électriques quantifiées (numérisables)

123
 Inspiration Biologique

• Cerveau humain : 100 billions de neurones

(1011) et des centaines de types différents.

• Les neurones se rassemblent en couches,

contenant chacune des milliers de neurones
fortement interconnectés.

124
Une modélisation simplifiée de la réalité

[Link] 125
Le modèle de neurone artificiel de
McCullogh et Pitts
x0=1
x1 w0=-1
w1

y
x2 w2 y=f(X)

xn wn

126
 Histoire
• 1943 - McCullock et Pitts : le problème
[(x AND y) OR (x OR y)]
• 1950's - Hodgkin et Huxley : prix Nobel.
• 1969 - Minsky et Papert, Perceptrons, le problème
non résolu : le XOR :
[(x AND NOT y) OR (y AND NOT x)]

• 1987 - Robert Hecht-Nielsen

127
Principe
Fonctions d'activation : linéaire contre non linéaire
Pas unitaire

Sigmoïde

Linéaire Seuillée

Gaussienne

Identité f (x) = x

128
Principe Réseau Multi-couches
(MLP en anglais pour Multi-Layer Perceptron)

Fonctions d'activation :

Non linéaire

Linéaire

129
 Frontières que l'on peut obtenir dans le cas d'une
Principe fonction d'activation ϕ linéaire par morceaux

Une
couche
cachée

Deux
couches
cachées

130
 Le perceptron à 1 couche
Principe cachée
OUTPUTS
Mais en général, une seule couche
cachée suffit à résoudre tout problème
de classification pourvu que les
neurones de la couche cachée
possèdent une fonction d'activation
NON linéaire (par exemple, la fonction
sigmoïde).

INPUTS
Le perceptron simple 131
 x1 x2 Classe
0 0 0
-1/2
1 1 0
Problème du XOR 1 0 1
x1 1 y1 -1

1
classe
0 1 1
1
-2
x2 1
y2 -1/2

-3/2

x2
- +
1
g1(x1)
g2(x1)

- +

0 1 x1
132
Projection dans un y2
1
espace où le problème
est linéairement
séparable
+ -
0 y1
1
-1/2

x1 1
y1 +1
Réseau de neurones à 1
classe
une couche cachée. 1 -2

x2 1 y2 -1/2

-3/2

Projection du repère (x1,x2) x1 x2 y1 y2 Classe

vers un hypercube de R2 ! 0 0 0(-) 0(-) 0

Quelle est la fonction 1 1 1(+) 1(+) 0

1 0 1(+) 0(-) 1
d'activation dans ce cas ? 0 1 1(+) 0(-) 1
133
134
 x2
001
1 000
-
011 +
+ - 101
+ - 100
111 0 x1
1

110

001 101
011 111 Quelle structure de réseau avons-nous a priori ?

Et si la région 111 avait été grisée,

000 100 cette structure aurait-elle suffit ?

135
110
 Output
Inputs

y11 = f ( x1 , w11 )  y11 

 1
y 12 = f ( x2 , w12 ) y 
y 1 =  21 
y31 = f ( x3 , w31 )  y3 
 y1 
y 14 = f ( x4 , w14 )  4
136
Apprentissage biologique
Apprentissage par adaptation :

“The young animal learns that the green fruits are sour,
while the yellowish/reddish ones are sweet. The learning
happens by adapting the fruit picking behaviour.
At the neural level the learning happens by changing of the
synaptic strengths, eliminating some synapses, and building
new ones.”

137
Principe mathématique
Énergie ou Erreur à minimiser
1 N
E=
N
∑ ( F ( xt ; W ) − y t ) 2

t =1

[Link]

138
Un principe d’optimisation numérique, si
l’Énergie ou Erreur est :
1 N
E=
N
∑ ( F ( xt ; W ) − y t ) 2

t =1

une mise à jour des poids efficace à

chaque itération suit la loi
∂E
∆wi = −c ⋅
j
(W )
∂wi j

wi j , new
= wi + ∆wi
j j

jusqu’à convergence… 139

 Résolution informatique
Cas simple:
ADALINE

d : sortie désirée
Mise à jour des poids
y : sortie obtenue
x : entrée fournie
w j (t + 1) = w j (t ) + η (d − y ) x η : pas
d'apprentissage
(learning rate)

140
Comment faire sur un MLP ?

w11
w11
w12
w11
w21 w12

w22 w21 w12

w31 w22

w32

141
Algorithme de rétro-propagation du gradient

• RPROP (BackProp) : algorithme

d ’apprentissage pour un réseau de type MLP
• But : Pour un ensemble d ’éléments
(d ’apprentissage), trouver les poids du réseau
MLP qui fournissent la réponse attendue pour
chacun des éléments

142
143
•Très efficace
•Sans modélisation a priori
•Simple à implémenter

•Un maximum d’exemples (comportement

statistique, loi des grands nombres)
•Effet boîte noire : comportement interne
difficile à expliquer, modéliser

144
 SVM
Nouvelle modélisation des Neural Network :
les SVM ou Support Vector Machine

Utile quand peu d'exemples d'apprentissage et

problème à 2 classes

Carte de Kohonen
Auto-organisation de données
145
Dans le cadre des SVM, on cherche l'hyperplan de marge optimale pour
séparer correctement les données tout en étant éloigné le plus possible de
toutes les observations.
On cherche donc à trouver un classifieur ou une fonction de
discrimination dont la capacité de généralisation (qualité de la
prédiction) est la plus grande possible.

marge

146
 SVM = Séparateurs à vastes marges
= Support Vector Machines
= Machine à noyaux ou kernel machines
Liés aux fonctions noyaux pour introduire de la non linéarité dans
des espaces de plus grandes dimensions en particulier (cf. fonction
d'activation sigmoïde du MLP)et à la dimension de Vapnik
Chernovenkis

Compromis entre
complexité de la frontière
(capacité d'ajustement du
modèle) et qualités de
généralisation ou
prédiction de ce modèle

147
Dans le cas de SVM, on va surtout s'appuyer sur les
« support vectors » les plus proches de la frontière pour les
calculs et la modélisation de la frontière optimale.

Pour les software et tutorial,

[Link] / 148
Cas à 2 classes :
Soit une variable Y à prédire prenant ses valeurs dans {-1,1}.
Soit X = X1, ..., Xp les variables explicatives ou prédictives.
X∈Rp ou plus généralement X∈F quelconque
Soit m(X) un modèle pour Y.
On note z={(x1,y1),...(xn,yn)} un échantillon statistique de taille n.

L'objectif est de construire une estimation me de m, fonction de F dans

{-1,1} de sorte que la probabilité P(m(X)≠Y) soit minimale.
L'astuce est de rechercher plutôt qu'une fonction me à valeurs dans {-1,1}
une fonction réelle f dont le signe fournira la prédiction :
me = signe (f)
L'erreur s'exprime alors comme la quantité :
P(m(X)≠Y)=P(Yf(X)≤0)
De plus, la quantité |Yf(X)| fournit un indicateur sur la confiance à
accorder au résultat du classement. Yf(X) est la marge de f en (X,Y).
149
Espace intermédiaire :
une première étape consiste à transformer les valeurs de X, cad les
objets de F par une fonction T à valeurs dans un espace H
intermédiaire (feature space) muni d'un produit scalaire et d'une plus
grande dimension.
Cette transformation est fondamentale dans le principe des SVM,
elle prend en compte l'éventuelle non linéarité du problème posé et
le ramène à la résolution d'une séparation linéaire.
(cf. projection 2D vers 3D une dizaine de transparents
précédemment).
En pratique, il n'est pas nécessaire d'expliciter la transformée T ce
qui serait souvent impossible, à condition de savoir exprimer les
produits scalaires dans H à l'aide d'une fonction k:FxF->R
symétrique appelé noyau de sorte que :
k(x,x')=<T(x),T(x')>
Bien choisi, le noyau permet de matérialiser une notion de
« proximité » adaptée au problème de discrimination et à sa structure
de donnée. 150
151
 Exemples de noyaux parmi une infinité (c'est la difficulté de
construction et d'utilisation grand public de l'outil SVM)

D'où, procédure de stabilisation par essai erreur en utilisant une bonne

méthode d'évaluation des erreurs de prédiction par exemple par
validation croisée.
Par rapport aux réseaux de neurones, les SVM mettent en oeuvre des
stratégie d'optimisation spécifique.
[Link]
[Link]
[Link]
152
153
 Applications
Taches que peut résoudre un Réseau de Neurones Artificiels:
• contrôler le mouvement d'un robot en se fondant sur la
perception;
• décider de la catégorie de certaines nourritures (comestibles
ou non) dans les mondes artificiels (jeux);
• prédire si une séquence ADN est une séquence codante
correspondant à un gène;
• prédire le comportement de valeurs boursières;
• prédire le comportement de futurs utilisateurs d'un service …

154
 DNA Sequence Analysis
Eukaryotic Gene Structure

5’ - Promoter Exon1 Intron1 Exon2 Terminator – 3’

UTR splice splice UTR

transcription
Poly A

translation

protein 155
 TDNN
(Time-delay
Neural Network)

Training: 300 promoter

sequences, 3000 random
NON-promoter sequences.
Test: 129 promoters, 1000
random sequences.

(BDGP Server)
Martin G. Reese and Frank H. 156
Eeckman.
 Evaluation de l’apprentissage supervisé
Input : algorithme paramétrable + ensemble d’exemples A
Output: hypothèse h
Question : évaluer la performance de cette hypothèse

Sur l’ensemble de
test non appris

Sur l’ensemble
d’apprentissage

157
On travaille en général sur deux ensembles : un ensemble d’apprentissage A et
un ensemble de test T.

Une estimation du risque réel de l’hypothèse h proposée sur l’ensemble de test

T peut être obtenue à partir de la matrice dite de confusion.

Dans le cas binaire par exemple, c'est-à-dire dans le cas du test d'une
hypothèse (une classe) indépendamment des autres classes (hypothèses), on a

‘+’ prédit ‘-‘ prédit

Vrais positifs Faux positifs

‘+’
réel
Faux négatifs Vrais négatifs
‘-‘
réel

Risque Réel (h) = Somme des termes non diagonaux / Nombre d’exemples
= Somme des exemples mal classés / Nombre d’exemples

158
Considérons le cas où je possède un ensemble E de 1000 exemples pour apprendre.
Pour valider l’apprentissage, j’ai plusieurs choix pour l’ensemble d’apprentissage et
l’ensemble de test. Par exemple :
• A = 2/3 de E et T = le 1/3 restant
• A = 1/2 de E et T = la 1/2 restante

On voit bien que les risques réels mesurés R(h,T) dans chacun des cas seront
différents et on sent bien que plus T sera grand et plus la mesure réelle du risque sera
proche de sa véritable valeur.
Mais, plus T est grand et plus A est petit puisque les ensembles doivent rester
décorrélés et donc moins l’apprentissage sera efficace.

Conclusion : cette méthode (dite hold-out) de validation est correcte si E possède

beaucoup d’exemples.

Dans le cas contraire, on utilisera d’autres méthodes statistiquement correcte pour

estimer la validité d’un apprentissage sur un ensemble réduit d’exemples.

159
L’estimation par validation croisée (N-fold cross-validation)

• Diviser A en N sous-échantillons de tailles égales

• Retenir l’un de ces échantillons Ni pour le test et apprendre sur les N-1 autres
• Mesurer le taux d’erreurs R(hi,Ni) sur Ni
• Recommencer n fois en faisant varier l’échantillon i de 1 à N
L’erreur estimée finale est la moyenne des R(hi,Ni) pour i de 1 à N.

Souvent N varie entre 5 et 10.

On refait souvent un apprentissage global sur A tout entier (plutôt que de choisir une
des hypothèse hi). Mais la procédure précédente est utile pour avoir une bonne
mesure de la validité ou du taux d’erreur de la méthode d’apprentissage choisie.

A l’extrême,quand A est très petit, le leave-one-out mais moins performant.

Une technique aléatoire sensée être statistiquement encore plus performante : le

bootstrap.

Enfin, jusqu’ici on essayait d’estimer au mieux la performance d’une méthode mais

pour comparer différentes méthodes entre elles ou différents jeux de paramètres
d’une même méthode, on est amené à considérer 3 ensembles : l’ensemble A
d’apprentissage, l’ensemble T de test, et l’ensemble V de validation. 160
La matrice de confusion : mesure globale de la performance de la classification en
toutes les classes de l'ensemble de validation

161
La courbe ROC (Receiver Operating Characteristics -> voir radar/World War))
Dans un contexte de prise de décision, la performance intrinsèque en terme de taux
d’erreur indifférencié n’est pas suffisante.
Les taux de “faux positifs” et de “faux négatifs” sont des estimateurs précieux : faire
une erreur sur la prédiction d’une maladie grave n’est pas équivalent selon qu’on la
laisse passer (faux négatif) ou qu’on la détecte (“faux positif”).
Ces taux sont disponibles à partir de la matrice de confusion.
La courbe ROC est utilisée dans le cadre de classification à 2 classes.
Remarque : classe = hypothèse = test

‘+’ ‘-‘

Vrais positifs Faux positifs

‘+’

Faux négatifs Vrais négatifs

‘-‘

162
Mesures de la qualité de prédiction
d'une classe par rapport à toutes les autres Ensemble des N éléments
déclarés roses en phase de
décision (test), c'est-à-dire
qui répondent positivement
au test (hypothèse) de la
classe rose après
apprentissage.

6 roses dans cercle noir

Précision=
62 non roses dans cercle noir

6 roses dans cercle noir 

Recall=
63 roses hors du cercle noir  163
Sensibilité = taux de détection ou reconnaissance = Recall =TP/(TP+FN)=TP/{Exemples positifs}
Spécificité = 1-taux de fausses alarmes = TN/(TN+FP)= TN/{Exemples négatifs)
Taux de fausses alarmes = FP/(TN+FP)=1-spécificité
Précision = TP/(TP+FP) (utilisée en médecine essentiellement)
sensibilité

1-spécificité
164
165
166
Mesures de la qualité de prédiction
d'une classe par rapport à toutes les autres Ensemble des N éléments
déclarés roses en phase de
décision (test), c'est-à-dire
qui répondent positivement
au test (hypothèse) de la
classe rose après
apprentissage.

FP TP

TN FN

167
Chapitre II. Apprentissage a
posteriori par Induction
Arbres de Décision

168
Principe : Construire des règles Si Age > 65 ans
Et Sexe Feminin
Alors Pas d’achat (à 87 %)

…à partir d’un arbre

Algorithme ID3 ou C4.5, Algorithme CART

En théorie,
Principe de diminution du désordre
et lien avec la théorie de l’information

Un pont vers les Systèmes Experts

169
 On veut classer les pièces anciennes et modernes en fonction de
critères explicites et pertinents : Pièces anciennes Pièces modernes

Si on tire au hasard une pièce de ce sac de petites

pièces, la probabilité de tomber sur une pièce ancienne
est de 1/4 et moderne de 3/4
Désordre estimable à = -1/4log(1/4)-3/4log(3/4) = 0,24

Critère de taille
Si on tire au hasard une pièce de ce sac de grandes
pièces, la probabilité de tomber sur une pièce ancienne
est de 2/3 et moderne de 1/3 :
Désordre estimable à = -1/3log(1/3)-2/3log(2/3) = 0,27

Et en prenant le critère de forme ?

170
Modélisation dans le cas binaire

E1 E2 E3 E4 E5 E6 dH Pm
Connaît l’école Oui Oui Non Oui Non Non 2 2
Q1
A eu un stagiaire Oui Non Non Non Non Non 2 2
Q2
A embauché un étudiant Non Oui Non Oui Non Oui 4 2
Q3
Verse la taxe Non Oui Oui Non Non Non 1 1
Q4
A participé à un Oui Oui Oui Oui Oui Oui 3 3
Q5 évènement

Rendez-vous Oui Oui Oui Non Non Non

R
171
But : Trouver le facteur question Qi le plus pertinent pour
classer les exemples Ei par rapport à une mesure du
désordre.

On utilisera par exemple, comme mesure de désordre

dans le cas binaire, Pm(Qi) définie à partir de la distance
de Hamming dH(R,Qi):
Pm : Pseudo-Métrique de Hamming
=
min(nb_exemples – dH, dH)

172
Arbre de décision correspondant :
oui Verse la taxe
non
à l’école

non
oui A eu un
Rendez- stagiaire
vous
accepté

Rendez- Rendez-
vous vous refusé
accepté

Simplicité
Lisibilité
Multiplicité des arbres possible

Taille de l’arbre libre 173

Mais pour des Variables qualitatives, comment faire ?

Revenu
client Age Résidence Etudes Internet

1 moyen moyen village oui oui

2 élevé moyen bourg non non

3 faible âgé bourg non non

4 faible moyen bourg oui oui

5 moyen jeune ville oui oui

6 élevé âgé ville oui non

7 moyen âgé ville oui non

8 faible moyen village non non

174
Pour chaque nœud, on répartit les différentes classes.

Un nœud est terminal s’il ne contient que des individus

appartenant à une seule classe (en l’occurrence ici, qui
consulte ses comptes sur internet).

Ainsi le nœud racine de notre arbre n’est pas terminal.

Racine
(3,5)

Racine
(3,5)
Quel test choisir ?
Revenu

(1,2) Faible Moyen

Elevé
(0,2) 175
(2,1)
 C
• Entropie (nœud p) = −∑ p(k / p)log p(k / p)
k =1

Avec p(k/p) = N(k/p) / N(p)

= proportion d’éléments de classe k à la position p

Entropie(Racine) = -3/8log(3/8) –5/8log(5/8) = 0.954

Entropie(Etudes/oui) = -3/5log(3/5) –2/5log(2/5) = 0.970
Entropie(Etudes/non) = 0

Ainsi le gain au niveau du désordre entre le noeud courant p de l’arbre

et l’embranchement de test choisi t vaut : Racine
(3,5)
n
• Gain(p,t) = Entropie(p) - ∑P Entropie(p )
k =1
j j Revenu

Avec (1,2) Faible Moyen

Elevé
(0,2)
(2,1)
pj = jème nœud créé
et Pj = proportion d’éléments 176
pour ce noeud
Gain(Racine,Revenu) = Entropie(Racine) – 0.620 Racine
(3,5)

= Entropie(Racine) - 3/8[-1/3log(1/3)-2/3log(2/3)]
Revenu
-3/8[[-2/3log(2/3)-1/3log(1/3)]
-2/8[[-0/2log(0/2)-2/2log(2/2)] (1,2) Faible Moyen
Elevé
(0,2)
(2,1)

Gain(Racine,Age) = Entropie(Racine) – 0.5

Gain(Racine,Etudes) = Entropie(Racine) – 0.607
Gain(Racine,Résidence) = Entropie(Racine) – 0.870
Le meilleur gain est obtenu pour le test sur l’âge
Racine
(3,5)

Age

(1,0) Jeune Moyen

Agé
(0,3)
(2,2)
L’arbre se construit ainsi
incrémentalement en
? poursuivant 177
Variables quantitatives : méthode des grappes

client Revenu Age Résidence Etudes Internet

1 2000 30 1000 4 oui

2 4500 34 500 0 non

3 600 56 300 1 non

4 1000 41 350 3 oui

5 1500 20 10000 2 oui

6 3000 65 5000 3 non

7 1800 59 4000 3 non

8 600 32 5600 1 non

178
Toujours la même chose : compromis entre généralisation et complexité :
-> Elagage a posteriori d'un arbre de décision par algorithme glouton
(équivalent du pruning pour le réseau neuronal)

179
180
Partie élaguée
après l'algo

181
Boosting ou dopage : théorème du classifieur faible
ADABOOST Algorithm ou la combinaisons des classifieurs faibles
Technique du Bagging

182
Chapitre III. Algorithmes
évolutionnaires

183
Le problème de l’optimisation en général

184
185
• Optimiser une fonction de coût ou d’erreur J(W) : maximiser ou minimiser !!

• Descente de gradient (voir Réseau de Neurones), qui donne

vectoriellement :
Wt+1 = Wt - c * GradientW(J)

Pour sortir de minima locaux, on peut par exemple faire varier c avec les
iitérations : un des principes du “recuit simulé” ‘simulated annealing”
Wt+1 = Wt + c(t) * ∆W

En général, le calcul du gradient n’est pas toujours possible facilement

notamment quand la fonction de coût n’est pas la classique erreur aux
moindres carrés -> solution par processus stochastique type Monte Carlo.

Enfin, l’espoir d’arriver en un temps raisonnable à un minimum correct

s’efface quand le nombre de ces minima locaux augmente.

186
 Simulated annealing search
• Idea: escape local maxima by allowing some "bad"
moves but gradually decrease their frequency

187
188
 Les Algorithmes génétiques
L'évolution dans la nature survient quand des entités ont la capacité de se
reproduire, qu'il existe une population de ces entités, qu'il existe une
variété (diversité) à travers ces entités, et que la survie des entités dépend
des différences entre elles. Toute entité vivante possède un génotype et le
phénotype
Le génotype.
Le génotype est constitué de gènes situés sur des chromosomes stockés dans le noyau des cellules sous la
forme d'une longue chaine d'acide déoxyribonucléique (ADN). Dans la nature, l'ADN est un polymère
constitué par l'enchaînement de quatres molécules, les nucléotides adénime (A), cytosime (C), guanine (G) et
la thymine (T). On peut donc décrire l'ADN par des chaînes de quatre caractères ACGT. L'ADN constitue
l'ensemble des chromosomes, ou le génome d'un individu.
Exemple : la suite ACCTGAGGGTA
Informatique : le codage binaire d’une solution
Le phénotype.
Le phénotype est l'ensemble des protéines et des enzymes qui peuvent être fabriqués à partir de l'ADN. En fait,
l'ADN est copiée par un messager (ARN) qui au niveau du ribosome, se traduit en chaînes d'acides aminés
formant les protéines et les enzymes. En général, on compte une protéine (un enzyme) par gène. Ce sont les
protéines et les enzymes qui dictent la structure et le comportement des cellules qui définissent les
caractéristiques physiques d’un individu et permettent à un individu de réaliser des tâches dans son
environnement, de survivre et de se reproduire à des taux différents. Ensemble des manifestations observables
du génotype.
Exemple : le gène AGTAGT code les yeux verts. 189
Informatique : une solution du problème dans une représentation « naturelle » obtenue après décodage du
génotype
 La reproduction se traduit par la transmission du génome aux
individus de la progéniture ce qui permet de préserver les gènes
menant à des performances supérieures. Occasionnellement, un
processus naturel, la mutation génétique, introduit une variation dans
les chromosomes.

Or les individus les mieux adaptés, c'est-à-dire capables de mieux effectuer

les tâches nécessaires à leur survie, se reproduisent à des taux les plus
élevés, alors que les individus les moins adaptés se reproduisent à des taux
plus faibles. Ce sont les principes de survie et reproduction décrit par
Charles Darwin dans « On the Origin of Species By Means of Natural
Selection » en 1859. Il s'avère alors qu'une population ayant une grande
variété va, de génération en génération, contenir des individus dont le
génotype se traduit par une meilleure adaptation, et ceci à cause de la
contrainte de la sélection naturelle. 190
L'algorithme génétique ne fait que transposer ce que fait la nature à des
systèmes artificiels. Il simule les processus évolutifs Darwiniens et
génétiques s'appliquant aux chromosomes. Il transforme une population
d'individus souvent représentés par des chaînes de caractères pour imiter les
chaînes d'ADN, chacun ayant une valeur d'adaptation, en une nouvelle
population. L'algorithme fait donc appel à quatres opérateurs de base :

–l'évaluation du niveau d'adaptation d'un individu.

–la sélection : c'est le choix des individus en fonction du niveau
d'adaptation.
–le croisement : c'est le mélange des bagages génétiques et c’est
l’opérateur de recherche essentiel.
–la mutation : le bagage génétique est modifié abruptement (utilisé à
un faible taux et pour assurer un certain degré de diversité dans la
population).

Auxquels il faut ajouter le codec génotype<->phénotype approprié au

191
problème.
192
193
194
195
196
Etape 3 : Création de la génération t+1

197
Maximisation de C(x) = 256-x2

198
Optimisation de réseaux UMTS

L’optimisation d’un réseau radio mobile

est un problème difficile qui met en jeu
des centaines de paramètres.

199
200
Opérateurs de variation

201
Une fonction de coût aggrégeant les objectifs pertinents est utilisée :
•Couverture
•Capacité
•Continuité et qualité de service
•Coût d’implémentation

Un algorithme génétique guide une génération de réseaux vers une solution globale
correspondante à un optimum global ou à un bon optimum local.

A chaque itération, un évaluateur rapide de réseau UMTS calcule les différents critères
de qualité qui permettent de “noter” les paramétrages des réseaux proposés.

Ensuite, l’AG utilise ces “notes” et propose un nouveau jeu de paramètres pour le
réseau.

202
203
[Link] 204
205
 Réf. Biblio. pour la partie appliquée du cours :
Data mining :
Gestion de la relation client,
Personnalisation de Sites Web.
par René Lefébure et Gilles Venturi.
Edition Eyrolles

Chapitre IV. Systèmes et

Processus de Data Mining
Exemples d’applications

206
Par arbres de décision Une entreprise de télécommunications

Comprendre les facteurs explicatifs d’un niveau d’appel.

Variable expliquée : durée mensuelle de consommation.

La base de données :
Département
Type de client

Profession
Revenu
Situation matrimoniale
Âge des enfants
Options : renvoi, double appel, etc.
Heure d’appel
207
Code destination : étranger, local
Par arbres de décision Une entreprise de télécommunications

4 étapes :

1. Préparation des données :

Définir la nature catégorique ou numérique des variables

2. Enrichissement des données :

Organiser en taxonomie, typologie, combiner les variables

3. Création de l’arborescence
Manuel, Semi-automatique ou automatique

4. Validation de l’arborescence
Soit sur un mode statistique, soit sur un mode opérationnel

208
Par arbres de décision Une entreprise de télécommunications
Moy = 245.72
Type = 203.06
n = 10000

Revenu
0-5000 +5000

Moy = 241.02 Moy = 319.76

Type = 137.51 Type = 622.6
N=9403(94%) n=597(6%)

pc
Non oui

Moy = 234.94 Moy = 524.31

Type = 150.85 Type = 1101.43
209
N=422(4.2%) n=175(1.8%)
Par arbres de décision Une entreprise de télécommunications

REGLE_17 : SI
Pc = Oui
Revenu = 0 or 30 000 +
ALORS
durée_appel : moyenne 524.309, écart type : 1101,43

REGLE_10 : SI
Marié(e) = Oui
Propriétaire_maison = Oui
Membres5-18 = 2 or 3
Console_jeux = Oui
Satellite = Oui
Revenu = 10-20 000, 0- 10 000 or 20-30 000
ALORS
durée_appel : moyenne 376.478, écart type : 131,73
210
Par arbres de décision Une entreprise de télécommunications

Simplicité

Lisibilité

Multiplicité des arbres possibles

Taille de l'arbre
211
Data Mining has been identified as one of the ten emergent technologies of the
21st century (MIT Technology Review, 2001). This discipline aims at discovering
knowledge relevant to decision making from large amounts of data. After some
knowledge has been discovered, the final user (a decision-maker or a data-
analyst) is unfortunately confronted with a major difficulty in the validation stage:
he/she must cope with the typically numerous extracted pieces of knowledge in
order to select the most interesting ones according to his/her preferences. For
this reason, during the last decade, the designing of quality measures (or
interestingness measures) has become an important challenge in Data Mining.

Alchimie de la transformation des données en connaissances

Nécessité et Proposition d'un cadre méthodologique pour la

KDD : Knowledge Discovery in Database
212
 Phase 1 / POSER LE PROBLEME

Phase 2 / LA RECHERCHE DES DONNEES

Phase 3 / LA SELECTION DES DONNEES PERTINENTES

Phase 4 / LE NETTOYAGE DES DONNEES

Phase 5 / LES ACTIONS SUR LES VARIABLES

Phase 6 / LA RECHERCHE DU MODELE (tout ce qui précède dans le cours)

Phase 7 / L'EVALUATION DU RESULTAT

Phase 8 / L'INTEGRATION DE LA CONNAISSANCE

213
 Phase 1 / POSER LE PROBLEME

Cas de marketing classique : identification de profils de clients et

organisation d'une campagne de marketing direct
Il s'agit d'un voyagiste organisant des circuits touristiques avec 5 types de
prestation (A,B,C,D et E). Son directeur de marketing souhaite mettre en
place une politique de fidélisation.

Décomposition en sous-problèmes précis :

Fidéliser la clientèle ?
Clientèle ?

Typologie de problèmes à résoudre :

Structuration : qui sont mes clients ?
Affectation : quels sont les clients à contacter ?

Objectifs :
1. Connaître les clients pour revoir les offres et la politique marketing.
2. Fournir à la cellule marketing opérationnelle et aux réseaux de
distribution une liste ciblée de clients par requête SQL, ce qui implique
214
des critères compréhensibles
 Phase 2 / LA RECHERCHE DES DONNEES
La base d'informations à disposition

Informations sur le client : Informations sur le produit acheté :

-âge; -produit A avec la date de 1er achat;
-sexe; -produit B avec la date de 1er achat;
-situation matrimoniale : marié ou non; -produit C avec la date de 1er achat;
-nombre d'enfants à charge; -produit D avec la date de 1er achat;
-catégorie socioprofessionnelle; -produit E avec la date de 1er achat;
-nombre d'année dans son emploi;
SGBD Entreprise
Informations comptables :
-montant des achats;
-date du dernier achat;
-type de paiement; INSEE
-statut financier du client : bon, moyen ou Informations géographiques :
mauvais; -code commune;
-taille de la commune;
Informations collectées par questionnaires et enquêtes : -type d'habitat;
-centre d'intérêts;

215
Relier toutes ces bases d'information ? Jointures ? Manuelles ou Automatiques ?
 Phase 3 / LA SELECTION DES DONNEES PERTINENTES

Procédure d'extraction des échantillons représentatifs des enjeux marketing :

accroître le CA :

•Si le client n'a effectué aucun achat au cours des 5 dernières années,
alors pas d'extraction;

•Si le client a acheté pour plus de 3000 Euros ,

alors on tire aléatoirement un enregistrement sur 3;

•Sinon, on tire aléatoirement un enregistrement sur 10

216
 Phase 4 / LE NETTOYAGE DES DONNEES

Pour l'heure, après extraction et sélection, environ un fichier de 1400 clients à

analyser.
Les données sont forcément "gâtées" par le cheminement qui a conduit à leur
stockage et notamment par la saisie manuelle par des opérateurs différents. Les
erreurs, oublis, approximations ponctuels ou systématiques doivent être détectés et
corrigés le mieux possible.

Choix de traitement automatique des :

•Valeurs aberrantes;
•Analyse des valeurs min et max au 2e et 98e centiles;
•Analyse de la distribution afin de vérifier son homogénéité;
•Contrôle de cohérence de certaines informations;
•Valeurs manquantes;
•Valeurs nulles.

217
 Phase 5 / LES ACTIONS SUR LES VARIABLES

Adaptation aux contraintes de la modélisation par :

•Enrichissement :
• le croisement de la Date du premier achat et de la Date du dernier achat permet de
déterminer la longévité du client dans la compagnie de voyages;
•Le croisement des variables Type d'habitat et Taille de la commune permet de caractériser
le style d'habitat :
oPetite ville + individuel = rural;
oGrande ville + individuel = banlieue chic;
oGrande ville + collectif = forte concentration, etc.

•Normalisation des distributions

218
 Phase 6 / LA RECHERCHE DU MODELE (tout ce qui précède dans le cours)
Le fichier est nettoyé et complété.
Il reste à trouver les critères de structuration et d'affectation.
• La recherche des facteurs pertinents :
Recherche des typologie de clients par :
•Analyse factorielle pour la compréhension des principaux facteurs
de différenciation des clients
-> représentation sur 3 dimensions expliquant 84 % de la variance totale
C.A. important
CA (19%) S4
Age (27%) S6 S1

S5

âgés S2
Détention (38%) S3
jeunes
S9
•Classification automatique dans cet espace S8

-> représentation en 9 groupes de clients S7

types de comportements regroupés en 3
familles C.A. faible 219
multi mono
Phase 6 / LA RECHERCHE DU MODELE (tout ce qui précède dans le cours)

• La recherche des modèles de ventes croisées :

Il faut construire trois approches, différenciées par la notion d'âge des clients :
quels sont les facteurs comportementaux qui permettent de caractériser les gros
chiffres d'affaires parmi les clients jeunes, middle age, et âgés. Exemple, sur les
clients jeunes par :
•La préparation par réseau de neurones qui répartit notre population en 4
classes :
•Les multi : les multiacheteurs prédits multiacheteurs (45 %);
•Les mono : les monoacheteurs prédits monoacheteurs (30 %). Ces
deux catégories expliquent notre modèle à 75 %;
•Les prospects : les monoacheteurs prédits multiacheteurs (15 %);
•Les erreurs : les multiacheteurs prédits monoacheteurs (10 %).

Conclusion : les prospects représentent une part importante des

monoacheteurs ce qui constitue un point positif en terme de CA.
•La formalisation de la connaissance par arbre de décision.
•La synthèse.
220
 Phase 7 / L'EVALUATION DU RESULTAT

•Analyse statistique et écart entre taux de classification constaté sur la base

d'apprentissage et sur la base de test.

•Croisement avec les connaissance des experts : ici, commerciaux et spécialistes

du marketing : être prêt à répondre à tous les résultats qui vont à l'encontre des
intuitions de ces derniers -> nécessite une vrai expertise dans le domaine du Data
Mining.

Phase 8 / L'INTEGRATION DE LA CONNAISSANCE

•Dans sa fonction de communication;

•Dans sa fonction de production-logistique;

Le tout, permet de juger sa capacité à s'adapter aux différents

types de clients révélés par le processus de Data Mining.
221
Les logiciels du marché

Intelligent Miner, d’IBM

Clementine, de SPSS

SAS Enterprise Miner, de SAS

TeraMiner, de NCR

KXEN Components, de KXEN

SPAD, Start Miner, Alice d’Isoft, NeuroText de Grimmer

222
Bibliographie :

• Data mining : Gestion de la relation client, Personnalisation de Sites Web, par René Lefébure et
Gilles Venturi, Edition Eyrolles (pour la partie appliquée surtout)

• Mastering Data Mining : the art and the science of customer relationship management, par M. J.A.
Berry et G. S. Linoff, Edition Wiley (ouvrage très complet)

•Apprentissage artificiel : concepts et algorithmes, par A. Cornuéjols et L. Miclet, Edition Eyrolles

(pour la partie théorique du cours)

223
###################
##########
####### Appel à soumissions pour un
##### numéro spécial de la Revue RNTI
###
## FOUILLE DES DONNEES D'OPINIONS
# [Link]
Objectifs de ce numéro spécial :
------------------------------
Pour faire suite à l'atelier FODOP'08
([Link] sur la problématique de la fouille
des données d'opinions, un numéro spécial est proposé sur cette même
thématique. De plus en plus de documents contenant des informations
exprimant des opinions ou des sentiments apparaissent sur le Web (i.e.
commentaires ou évaluations de produits par des clients, forums, groupe de
discussion, blogs). Aujourd’hui, la détection ou l'extraction automatique
d'opinions devient un domaine de recherche particulièrement prometteur
notamment avec le développement du Web 2.0. Elle devient essentielle pour
de très nombreux domaines d'applications. Nous pouvons citer, par exemple,
le développement de tâches de veille (technologique, marketing,
concurrentielle, sociétale), l'évaluation d'un produit par la communauté
avant un achat, l'image que les clients peuvent se faire d'une entreprise,
la détection de rumeurs (buzz) sur le web, détection d'opinions émergentes
et/ou significatives dans les forums, etc. Ainsi, les approches
traditionnelles de fouille de données doivent être adaptées à un contexte
dans lequel il faut appréhender de gros volumes de données
particulièrement hétérogènes. L'objectif principal de ce numéro spécial
est alors de décrire les différents traitements des données d'opinions.
Thèmes développés (liste non exhaustive) :
----------------------------------------
– Catégorisation automatique de textes d'opinion
– Ontologies et données d'opinion
– Aide à la décision pour les données d'opinion
– Visualisation pour une analyse des données d'opinion
– Interrogation des données d'opinion
– Acquisition de bases de données d'opinion
– Veille technologique pour l'analyse des opinions
– Détection de tendances dans les opinions
– Fouille du Web pour acquérir et/ou analyser des textes d'opinion
– TAL à partir de textes d'opinion
- Analyse de discours

224