CHAPITRE III :

FOUILLES DE DONNÉES
2. Technique de structuration

Dr EL FAR Mohamed
Sommaire

A. Rappel
B. Introduction
C. Méthodes utilisées
D. Conclusion
A. Rappel
A. Rappel
 Structuration / Classification
A. Rappel

1. 2.

4. 3.
Techniques du Datamining
• Présentation des techniques
• Description de chaque technique :
 Mesures de Simularitées &Types Variables
 Classification/Structuration /Clustering
 Association
 Estimation & Segmentation & Prévision
Techniques du Datamining
• Présentation des techniques
• Description de chaque technique :
 Mesures de Simularitées & Types Variables
 Classification/Structuration /Clustering
 Association
 Estimation & Segmentation & Prévision
B. Mésures de Simularitées & Types
Variables
 Intervalles:
 Binaires:
 catégories, ordinales, ratio:
 Différents types:
 Intervalle (discrètes)
 Standardiser les données
 Calculer l’écart absolu moyen:

s1
fn
1

(|
x m|
|
x
f f 2
m|
f f

...
|
x
nf
m
|)
f

où m1
(x
f n1
x
f 2
f
 x

...)
nf
.

 Calculer la mesure standardisée (z-score)

xifm
zif s f
f
 Intervalle (discrètes)
Age Salaire M 60 SAge  5
Age

Personne1 50 11000
Personne2 70 11100 M 
1107
S 1
salaire salair

Personne3 60 11122
Personne4 60 11074

Age Salaire
Personne1 -2 -0,5
Personne2 2 0,175
Personne3 0 0,324
Personne4 0 2
 Similarité entre objets
 Les distances expriment une similarité
 Ex: la distance de Minkowski :
d
(
i
,
j
)
q 
(|
xxq
|
|
xx
q
| 
...
|
x xq
|
)
i
1j
1i 2j
2 ipj
p

où i = (xi1, xi2, …, xip) et j = (xj1, xj2, …, xjp) sont deux objets

p-dimensionnels et q un entier positif
 Si q = 1, d est la distance de Manhattan
d
(
i
,
j
)
|
xx
||
xx
|
 
...
|
x x
|
i
1j
1 i2j
2 ipj
p
 Similarité entre objets
 Si q = 2, d est la distance Euclidienne :
d
(
i
,
j
) 
(|
xx
2
||
xx
2
| 
...
|
x x2
|
)
i
1j
1i 2j
2 ipj
p

 Propriétés
 d(i,j)  0
 d(i,i) = 0
 d(i,j) = d(j,i)
 d(i,j)  d(i,k) + d(k,j)
 Exemple: distance de Manhattan
Age Salaire
d(p1,p2)=120
Personne1 50 11000
Personne2 70 11100 d(p1,p3)=132
Personne3 60 11122 Conclusion: p1 ressemble plus à
Personne4 60 11074 p2 qu’à p3 

Age Salaire
Personne1 -2 -0,5 d(p1,p2)=4,675
Personne2 2 0,175 d(p1,p3)=2,324
Personne3 0 0,324
Conclusion: p1 ressemble
Personne4 0 0 plus à p3 qu’à p2 
 Variables binaires
 Une table de contingence pour données binaires
Objet j
a= nombre de positions
1 0 sum
où i a 1 et j a 1
1 a b ab
Objet i 0 c d cd
suma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
 Variables binaires
 Coefficient d’appariement (matching) simple (invariant
pour variables symétriques):
d
(
i,
j)bc

a
b
cd

Exemple oi=(1,1,0,1,0) et oj=(1,0,0,0,1)

d(oi, oj)=3/5 
d
(i
,jb
) c
 Coefficient de Jaccard 
ab
c

d(oi, oj)=3/4
Variables binaires
 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

 Variables binaires
 Exemple
N om Sexe Fièvre Toux Test-1 Test-2 Test-3 Test-4
Jack M Y N P N N N
M ary 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
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

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

 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

d
(i
,jp
) 
pm
 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)
 Variables Ordinales
 Une variable ordinale peut être discrète ou continue
 L’ordre peut être important, ex: classement
 Peuvent être traitées comme les variables intervalles
 remplacer xif par son rang rif
 { 1,...,
M f
}
 Remplacer le rang de chaque variable par une valeur dans
[0, 1] en remplaçant la variable f dans l’objet I par
r 1
zif  if
M f
1
 Utiliser une distance pour calculer la similarité
Techniques du Datamining
• Présentation des techniques
• Description de chaque technique :
 Mesures de Simularitées & Types Variables

 Classification/Structuration /Clustering
 Association
 Estimation & Segmentation & Prévision
C. Introduction

 Classification/Structuration /Clustering
 C. Introduction
 Problématique :
 Par exemple, on souhaite regrouper une clientèle (14 clients)
en 4 classes
 Probabilité : 10 millions de partitions possibles en 4 classes

 Avec un gros calculateur :

 examiner toutes les possibilités (10 millions)
Impossible !
 et ne retenir que la meilleure

 D’où le besoin d’algorithmes

 C. Introduction
 Structuration = Classification = “Clustering”

 Définition :
 Consiste à créer des classes (≈sous-ensembles) de données:
 similairesentre elles
 et différentes des données d’une autre classe

L’intersection des classes entre elles doit toujours être vide

------------------------------------------------------------------
 Définit les grands types de regroupement et de
distinction: on parle de métatypologie (type de type)
 Partitionnement logique de la base de données en
clusters
 Clusters : groupes d’instances ayant les mêmes
caractéristiques
 ƒClasses inconnues (Apprentissage non supervisé)
C. Introduction
 Intérêts :
 Favoriser la compréhension et la prédiction
 Fixer des segments qui serviront d’ensemble de départ pour des
analyses approfondies.
 Réduire les dimensions, c’est-à-dire le nombre d’attributs/variables,
quand il y en a trop au départ

 Applications :
 Economie (segmentation de marchés)
 Médecine (localisation de tumeurs dans le cerveau)
 etc.

 Exemple : Métatypologie d’une clientèle en fonction de :

l’âge, les revenus, le caractère urbain ou rural,
la taille des villes, etc.
D. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centres mobiles (KMeans)
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
C. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centres mobiles (K-Means/K-
moyennes)
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
C. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centre mobiles (K-Means/K-
moyennes)
 Définition
 Etapes
 L’algorithme de “K-Means”
 Synthèse
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
C. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centre mobiles (K-Means/K-
moyennes)
 Définition
 Etapes
 L’algorithme de “K-Means”
 Synthèse
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
 Algorithme k voisins
30

 Paramètre : le nombre k de voisins

 Donnée : un échantillon de m exemples et leurs
classes
 La classe d’un exemple X est c(X)
 Entrée : un enregistrement Y
 1. Déterminer les k plus proches exemples de Y en
calculant les distances
 2. Combiner les classes de ces k exemples en une
classe c
 Sortie : la classe de Y est c(Y)=c
 Exemple
31
 Exemple
32

K=3
Définition de l’algorithme “K-Means”

 C'est la méthode la mieux adaptée aux très grands

tableaux de données.
 On choisit une métrique pour calculer la distance
entre individus.
 On définit à priori un nombre de classes (k).
 On choisit de façon arbitraire k centres de classes.
C'est souvent k individus tirés au hasard.
 Les individus seront affectés au centre de classe le
plus proche.
D. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centre mobiles (K-Means/K-
moyennes)
 Définition
 Etapes
 L’algorithme de “K-Means”
 Synthèse
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
Etapes de l’algorithme “K-Means”
 Exemple :
 On désire un regroupement en 2 classes.
Etapes de l’algorithme “K-Means”
 Etape 1:
 On choisit au hasard 2 centres de classe
Etapes de l’algorithme “K-Means”
 Étape 2 :
 Lesindividus sont affectés au centre de classe le plus
proche  Constitution des 2 premières classes.

• : Classe 1
• : Classe 2
Etapes de l’algorithme “K-Means”
 Étape 3 :
 Calcul des nouveaux centres de classes
Etapes de l’algorithme “K-Means”
 Étape 4 :
 Affectation des individus aux nouveaux centres de classes
Etapes de l’algorithme “K-Means”
 Étape 5 :
 Calcul des nouveaux centres de classes
Etapes de l’algorithme “K-Means”
 Étape 6 : (dernière étape)
 Affectation des individus aux nouveaux centres de classe
Etapes de l’algorithme “K-Means”
 L'algorithme s'arrête quand :
 La variance intra classe cesse de décroître ou,
 La variance inter classe cesse d'augmenter ou,

 L'affectation des individus aux classes ne change plus ou,

 On a atteint un nombre maximum d'itérations

D. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centre mobiles (K-Means/K-
moyennes)
 Définition
 Etapes
 L’algorithme de “K-Means”
 Synthèse
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
L’algorithme de “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
ƒ
D. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centre mobiles (K-Means/K-
moyennes)
 Définition
 Etapes
 L’algorithme de “K-Means”
 Exemple
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
 Exemple

 A={1,2,3,6,7,8,13,15,17}. Créer 3 clusters à partir de A

 On prend 3 objets au hasard. Supposons que c’est 1, 2 et 3. Ca

donne C1={1}, M1=1, C2={2}, M2=2, C3={3} et M3=3

 Chaque objet O est affecté au cluster au milieu duquel, O est le

plus proche. 6 est affecté à C3 car dist(M3,6)<dist(M2,6) et
dist(M3,6)<dist(M1,6)
On a C1={1}, M1=1,
C2={2}, M2=2
C3={3, 6,7,8,13,15,17}, M3=69/7=9.86
 Exemple

 dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent pas. C1={1},
M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

 dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent pas. C1={1},
M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

 dist(2,M1)<dist(2,M2)2 passe en C1. dist(7,M2)<dist(7,M3) 7 passe en C2. Les autres ne

bougent pas. C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34, C3= {8,13,15,17}, M3=13.25

 dist(3,M1)<dist(3,M2)3 passe en 1. dist(8,M2)<dist(8,M3)8 passe en 2

C1={1,2,3}, M1=2, C2={6,7,8}, M2=7, C3={13,15,17}, M3=15

Plus rien ne bouge

Synthèse

 Avantages :
 Relativementextensible : dans le traitement
d’ensembles de taille importante (BD volumineuse)

 Relativement efficace

 Produit généralement un optimum : local ; un optimum

globalpeut être obtenuen utilisant d’autres techniques
telles que: algorithmes génétiques, …
Synthèse
 Inconvénients :
 Applicable seulement dans le cas où la moyenne des
objets est définie
 Besoin de spécifier k, le nombre de clusters/groupes/classes,
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
C. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centres mobiles (KMeans)
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
 Exemple simple
 Exemple complexe & ses étapes
 Algorithme
 Synthèse
Exemple simple
 Enoncé :
Nom Age Enfants Pointure Taille
Alain 45 3 45 182
Martine 28 1 36 165
Pierre 22 0 43 172

 Questions :
 Comment mesurer la distance entre deux individus ?
 De qui Martine est-elle la plus proche ?
Exemple simple
 Distance :
 On utilisera la distance euclidienne.
 Distance entre Alain et Martine :

 Distance entre Martine et Pierre :

 Distance entre Alain et Pierre :

Exemple simple
 Tableau des distances :
 De ces distances euclédiennes, on obtient le tableau
des distances :
Alain Martin Pierre
Alain 0
Martin 25,74 0
Pierre 25,33 11,61 0
Exemple simple
 Remarque :
 Les deux variables Pointure et Enfants n'ont que peu de
poids dans le calcul de la distance.
 C'est pour remédier à ça, qu'on doit centrer et réduire
les données. (On verra plus tard)

Id Age Enfants Pointure Taille

1 45 3 45 182
2 28 1 36 165
3 22 0 43 172
C. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centres mobiles (KMeans)
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
 Exemple simple
 Exemple complexe & ses étapes
 Algorithme
 Synthèse
Exemple complexe & ses étapes
 Enoncé :
1 tableau de données : V1 V2
 Variables : V1, V2 A 2 5
 Individus : A, B, C, D, E B 7 8
C 3 3
D 8 9
E 4 5

 Questions :
A partir des variables V1& V2, “Qui est proche de qui” ?
Exemple complexe & ses étapes
 Étape 1 :
 On calcule les distances euclédiennes




 …
 Exemple complexe & ses étapes
 Étape 1 : (suite)
 De ces distances euclédiennes, on obtient le tableau
des distances :
A B C D E
A 0
B 5,83 0
A la main 
C 2,23 6,40 0
D 7,21 1,41 7,81 0
E 2,00 4,24 2,23 5,65 0

A l’aide d’1
Logiciel 
Exemple complexe & ses étapes
 Étape 2 :
 On regroupe les individus les plus proches
 B et D sont les individus les plus proches

Pourquoi ?

 Car la distance minimum est dB*D (indice de niveau 1.41)

 On se retrouve avec les 4 groupes suivants :

 A
 BD
C
E
Exemple complexe & ses étapes
 Étape 3 :
 On calcule la :
 distance Euclidienne : dA*C dA*E dC*E
 distance moyenne : dA*BD dBD*C dBD*E

 …..
 Étape 3 : (suite)
 De ces distances, on obtient le tableau des distances :

A BD C E
A 0
BD 6,52 0
C 2,23 7,05 0
E 2,00 4,94 2,23 0
 Étape 4 :
 On regroupe les individus les plus proches
 A et E sont les individus les plus proches

Pourquoi ?

 Car la distance minimum est dA*E (indice de niveau 2,00)

 On se retrouve avec les 3 groupes suivants :

 AE
 BD
C
 Étape 5 :
 On calcule la distance moyenne : dAE*C dAE*BD dBD*C

 …..

 On obtient le tableau des distances

AE BD C
AE 0
BD 5,73 0
C 2,23 7,05 0
Exemple complexe & ses étapes
 Étape 6 :
 On regroupe les individus les plus proches
 AE et C sont les individus les plus proches

Pourquoi ?

 Car la distance minimum est dC*AE (indice de niveau 2,23)

 On se retrouve avec les 3 groupes suivants :

 CAE
 BD
Exemple complexe & ses étapes
 Étape 7 :
 On calcule la distance moyenne : dAEC*BD


 On obtient le tableau des distances

AEC BD
AE 0
BD 6,39 0
Exemple complexe & ses étapes
 Étape 8 :
 On regroupe les individus AEC et BD
 Exemple complexe & ses étapes
 Résumé des 8 étapes précédentes :
 Etape 1&2 : B et D sont regroupés à l'indice de niveau 1,41

 Etape 3&4 : A et E sont regroupés à l'indice de niveau 2,00

 Etape 5&6 : AE et C sont regroupés à l'indice de niveau 2,23

 Etape 7&8 : AEC et BD sont regroupés à l'indice de niveau 6,39

 Pour y voir plus clair, il reste à faire un graphique

Dendrogramme ≈ Arbre hiérarchique
Exemple complexe & ses étapes
A la main A l’aide d’1 Logiciel
Paramètres :
• calcul des distances : distance euclidienne
• critère d'agrégation : distance moyenne (average)
C. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centres mobiles (KMeans)
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
 Exemple simple
 Exemple complexe & ses étapes
 Algorithme
 Synthèse
Algorithme de la classif. hiérarchique ascendante

 1ère phase : Initialisation de l’algorithme

 Les classes initiales = n singletons individus.
 Calcul de la matrice des distances des individus 2 à 2

 2ème phase : Itération des étapes suivantes.

 Regrouper les 2 éléments (individus ou groupes) les plus
proches au sens d’un critère choisi
 Mise à jour du tableau des distances en remplaçant les
deux éléments regroupés par le nouveau et en recalculant
sa distance avec les autres classes

 Fin de l’itération :
 agrégation de tous les individus en une seule classe
C. Méthodes utilisées
I. Classification Non hiérarchique
1. Agrégation autour de centres mobiles (KMeans)
2. Nuées Dynamiques (Self organizing map)

II. Classification Hiérarchique

1. Ascendante (agglomerative)
 Exemple simple
 Exemple complexe & ses étapes
 Algorithme
 Synthèse
 Synthèse
 Objectif :
 Fournirun ensemble de partitions de moins en moins fines
obtenus par regroupement successifs de parties.
 Obtenir une hiérarchie, une collection de groupes d’observations
 Les feuilles de l’arbre
= objets/observation
 ƒLes noeuds intermédiaires
de l’arbre =clusters
Une fois cet algorithme terminé, on ne
récupère donc pas directement une
partition, mais une hiérarchie de
partitions en n,...1 classes, avec
diminution de l’inertie inter-classes à
chaque agrégation
Synthèse
 Lectures des arbres
on coupe l'arbre et on
regarde les branches qui
tombent Le nb de classes
correspond aux nb de
lignes coupées

La hauteur d’une branche

est proportionnelle à la
distance entre les deux
objets regroupés

On coupe l’arbre avant une perte trop

importante de de distance
Synthèse
 Lectures des arbres
 Il existe deux formes d'arbre très reconnaissables

Données classifiables Données non classifiables

En 2 ou 3 classes Continuum !!
Synthèse
 Lectures des arbres
Données non classifiables

 Données non classifiables : Inutile d'insister. On peut

tester d'autres critères d'agrégation
 Synthèse
 Interprétation
 Les programmes fournissent souvent des aides pour
interpréter les classes.
 Elles ne sont pas forcément utiles…

 2 méthodes générales d'aide à l'interprétation :

 1ère méthode :
 Projeter les numéros de classes (à la place des codes des
individus) sur un plan issu d'une analyse en composantes
principales ou d'une analyse factorielle des correspondances
 2ème méthode :
 Affecter à chaque individu le numéro de classe auquel il
appartient
 Puis, dessiner des histogrammes des variables pour chaque classe
 Calculer des moyennes par classe
 Croiser les variables qualitatives avec les classes (tableaux de
fréquences)
 ..
Synthèse
 Avantages :
 Conceptuellement simple
ƒ
Les 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
 Inconvénients :
 Groupement de clusters est définitif => décisions
erronées sont impossibles à modifier ultérieurement
 Méthodes non extensibles pour des ensembles de
données de grandes tailles
Techniques du Datamining
• Présentation des techniques
• Description de chaque technique :
 Mesures de Simularitées & Types Variables
 Classification/Structuration /Clustering

 Association
 Estimation & Segmentation & Prévision
E. Méthodes utilisées

Regles D’associations
 Introduction
 Indicateurs d’evaluatuions
 Algorithme Apriori
 règles d’associations
 Règles d’association :
Une règle d’association a la forme logique générale suivante
si Conditions alors Résultats
CR
 motifs de la forme : Corps  Tête
 Exemple : achète(x, “fraises”) achète(x, “Pommes”)
 Etant donnés: (1) une base de transactions, (2) chaque transaction est décrite
par un identifiant et une liste d’items
 Trouver: toutes les règles qui expriment une corrélation entre la présence
d’un item avec la présence d’un ensemble d’items
 Ex., 98% des personnes qui achètent des fraises achètent des pommes
 règles d’associations
 Mesures: Support et Confiance pour une règle du type : C  R
 Indice de confiance
Clients achetant les deux
Clients achetant IC = p(C,R) / p(C)
Lait Avec:
p(C,R) = nb (C = vrai et R = vrai) / nb total
p(C) = nb (C = vrai ) / nb total
On arrive à :
IC = nb (C = vrai et R = vrai) / nb (C = vrai )
 Indice de Support
Clients achetant fromage IS = probabilité (condition)
IS = p(C)
ID Transaction Items Ou encore :
IS = nb (C = vrai ) / nb total
2000 A,B,C
1000 A,C Soit support minimum 50%, et confiance
minimum 50%,
4000 A,D A  C (50%, 66.6%)
5000 B,E,F C  A (50%, 100%)
 règles d’associations
 Extraction de règles
Transaction ID Items Min. support 50%
2000 A,B,C Min. confiance 50%
1000 A,C
4000 A,D Itemsets fréquentsSupport
{A} 75%
5000 B,E,F
{B} 50%
{C} 50%
{A,C} 50%
Pour A  C:
support = support({A, C}) = 50%
confiance = support({A, C})/support({A}) = 66.6%
 règles d’associations
 Exemple
Le tableau suivant présente 10 tickets de caisse pour lesquels il y a eu, ou pas, achat de
pomme et de fraises.

 Calcul de l’indice de support :

IS = p(pomme) = 5/10 = 50%.
Donc, 50% des individus sont concernés par cette règle.
 Calcul de l’indice de confiance de la règle « pomme  fraise » :
p(pomme) = 5/10
p(pomme, fraise) = 4/10
IC = (4/10) / (5/10) = 4 / 5 = 80%.
Dans 80% des cas où il y a « pomme », il y a aussi « fraise ».
 règles d’associations
Les indicateurs d’évaluation d’une règle
 IC * IS ou p(C,R
Le pourcentage de réussite de la règle dans la population totale est un indicateur de
la valeur d’une règle.
IC * IS donne cette mesure :
IC * IS = p(C,R)
L’exemple précédent donne :
IC * IS = 80% * 50% = 40%
Cet indicateur montre le taux d’individus (40%) concernés par la règle.
 règles d’associations
Les indicateurs d’évaluation d’une règle
 Le « lift »
Pour qu’une règle soit intéressante, l’indice de confiance de la règle doit être supérieur
à la probabilité absolue du résultat.
Pour qu’une règle soit intéressante, il faut donc que :
indice de confiance > probabilité (résultat)
IC > p(R)
Le « lift », c’est le taux de progression de la probabilité du résultat grâce à la règle :
lift = IC / p(R)
Un lift intéressant est > 1
 On peut aussi calculer la progression brute :

PB = IC - p(R)
Une progression brute intéressante est > 0
 règles d’associations
Les indicateurs d’évaluation d’une règle
 Exemple

L’indice de confiance de la règle « pomme  fraise » vaut : (4/10) / (5/10) soit 80%.
Donc, dans 80% des cas où il y a « pomme », on trouve aussi « fraise ».
Mais la probabilité des fraises vaut : (9/10) soit 90 %.
Le lift vaut : 80 / 90 = 8/9.
La progression brute vaut : 80 – 90 = -10%.
Lift < 1 et progression brute < 0 : la règle « pomme ® fraise » est donc sans
intérêt.
 règles d’associations
Les indicateurs d’évaluation d’une règle
 Règle inverse
Si une règle est inutile (le lift est < 1) alors, la règle inverse est utile :
si C  R est inutile alors C  non(R) est utile
 Exemple

Dans l’exemple précédent, la règle « pomme  non(fraise) » est utile.

L’indice de confiance de la règle « pomme  non(fraise) » vaut : (1/10) / (5/10)
soit 20%.
La probabilité des non(fraise) vaut : (1/10) soit 10%.
Le lift vaut : 20% / 10% = 2.
De 10% de chances on passe à 20 % de chance.
On a 100% (10 +X*10 = 20) de chance en plus de ne pas avoir des fraises quand
on a pris des pommes que dans tous les cas.
 règles d’associations

 La capacité de déploiement
La capacité de déploiement, c’est le pourcentage de ceux qui vérifient les conditions mais
pas encore les résultats.
Autrement dit, c’est le pourcentage de la population qui est potentiellement concerné par
l’application de la règle.
Capacité de déploiement = p(C, non R)
 Exemple :
On reprend le tableau précédent :

La capacité de déploiement de la règle « pomme ® fraise » vaut : (1/10) soit 10%.

 règles d’associations
 Type des variables
On a vu dans les exemples que la recherche d’associations se fait sur des variables
booléennes.
Cependant, les types continus (numériques) et catégoriels peuvent aussi être pris en
compte.
Les types continus doivent d’abord être discrétisés, c’est-à-dire transformés en types
catégoriels.
Les types catégoriels sont traités en transformant chaque catégorie (chaque valeur
possible pour la variable) en une nouvelle variable qui est donc booléenne.
 règles d’associations
 Exemple
Soit le tableau suivant :
 règles d’associations
On va le transformer en matrice creuse :
 règles d’associations
règle d’association et modèle entité-association
La recherche d’associations traite surtout d’associations entre les produits dans un
magasin : son premier domaine d’application est l’analyse du ticket de caisse.
Les variables en jeu sont des variables qui identifient le produit. Dans nos exemples, la
variable, c’est le produit lui-même.
On utilise aussi la taxinomie du produit, c’est-à-dire les différents genres dans lesquels
on peut classer le produit (par exemple : tel produit est un yaourt, un produit laitier,
un dessert, etc.).
Cette situation est différente de celle de la classification et de l’analyse des données
car les attributs avec lesquels on travaille sont souvent des clés étrangères, dans la
terminologie du modèle entité-association (MEA).
 règles d’associations
 Exemple :
La table du fichier d’analyse des règles d’association du ticket de caisse correspond au MEA
suivant :

Les règles d’association du data mining s’appliquent à l’association non-hiérarchique « ticket ».

Cette association correspond à la table suivante :
Ticket (#numAchat, #numProd, quantité, prix unitaire)
En considérant chaque valeur possible de la variable numProd comme une variable booléenne, on
va fabriquer la matrice creuse qui va servir pour la recherche des associations.
 règles d’associations
Dans la table ticket, on trouve par exemple (en considérant nomFruit comme l’équivalent de
numProd) :

La transformation en matrice creuse donne le résultat

suivant :

A la place des catégories de produit (nom des fruits), on pourrait s’intéresser à des types : fruits
exotiques, agrumes, etc.
 règles d’associations
Algorithme a priori
Principe de l’algorithme
Pour trouver des règles d’association :
1. On commence par fixer une fréquence minimum pour la recherche : un seuil de fréquence.
2. On calcule la fréquence de chaque n-uplet de variables en partant des n-uplets à une seule
variable (singleton), puis en passant à 2, puis à 3, etc.
3. On réduit le problème en utilisant la propriété suivante :
Quel que soit le n-uplet de variables N et quelle que soit la variable V, la fréquence de N est
inférieure à celle de N U V (N union V).
On peut donc commencer par éliminer tous les singletons de fréquence inférieure au seuil, et
donc tous les n-uplets contenant ces singletons, puis tous les doublons de fréquence inférieure
au seuil, et donc tous les n-uplets contenant ces doublons, etc.
Cette technique permet de réduire considérablement l’ensemble des n-uplets de variables
pouvant être la condition d’une règle d’association.
 règles d’associations
Algorithme a priori
Exemple
Matrice creuse de départ
On reprend le tableau des ventes de fruits en le complétant :

Tableau n°1 : matrice creuse des transactions

 règles d’associations
Algorithme a priori
Détermination des n-uplet candidats pour générer des règles d’association
 Première réduction du nombre de variables : choix d’un seuil de fréquence
On fixe un seuil de fréquence : on choisit 4. Ce choix est arbitraire. On considère qu’à moins
de 4 / 14 = 29 %, on ne s’intéressera pas au associations.
 Calcul de la fréquence pour chaque variable
Ensuite, on somme les colonnes pour avoir la fréquence par fruit :

Tableau n°2 : fréquence et %age de fréquence par fruit. Singleton candidat pour les règles
d’association.

Toutes les variables sont sélectionnées, sauf la Poire.

 règles d’associations
Algorithme a priori
 Calcul de la fréquence pour chaque couple de variables
Ensuite on croise toutes les variables sélectionnées entre elles et on compte le nombre
d’occurrences :

Tableau n°3 : couples candidats pour les règles d’association.

On peut supprimer la première ligne (fraise) et la dernière colonne (orange) du tableau.
Il n’y a que 6 couples qui ont une fréquence suffisante.
A noter le rôle prépondérant des oranges.
 règles d’associations
Algorithme a priori
Calcul de la fréquence pour chaque triplet de variables
On croise tous les couples trouvés avec tous les singletons.
Toutefois, il n’est pas nécessaire de croiser tous les couples trouvés avec tous les singletons.
En effet, on constate que tous les couples avec fraise sont éliminés : on peut donc retirer la fraise
des singletons.
Ensuite, pour une variable donnée, le secondes variables intervenant dans les couples éliminés
seront éliminées des singletons. Dans le tableau, pour passer tous les couples en revue, on
prend toutes les variables « en ligne et en colonne » (banane-fraise, banane-banane,
bananecitron, banane pomme, etc.)

Il n’y a qu’un triplet qui ait la fréquence suffisante. C’est la condition d’arrêt de la fabrication des n-uplet candidats : quand on trouve 0 ou 1 n-uplet, on peut s’arrêter.
 règles d’associations
Algorithme a priori
Principe de la constitution des règles
Rappelons que, pour la règle C R:
 IC = p(C,R) / p(C) = f(C,R) / f(C)
 IS = p(C) = f(C) / nb total
 p( ) étant la probabilité et f( ) la fréquences ou nombre d’occurrences.
 lift = IC / p(R) (un lift intéressant est > 1)
 Progression Brute = IC - p(R) (une progression brute intéressante est > 0)
 Capacité de déploiement = p(C, non R),

Le prochain tableau a été construit avec les données des tableaux n° 1 et 2.

Dans les colonnes « lift », on trouve
 Le « lift » : IC / p(R)
 La progression brute : IC – p(R )
 Dans les colonnes « déploiement », on trouve
 f(C, nR) : fréquence des conditions avec la négation du résultat
 p(C, nR) : probabilité des conditions avec la négation du résultat
règles d’associations
Algorithme a priori
 règles d’associations
Algorithme a priori
Interprétation des règles d’association
Classifications
Pour l’interprétation, on va classer le tableau des règles selon les 3 indicateurs de qualité : par
 IC * IS : réussite de la règle dans la population totale
 lift : taux de progression de la probabilité du résultat
 déploiement : pourcentage de la population concerné par l’application de la règle

On commence par le lift car cet indicateur permet d’éliminer des règles.
 règles d’associations
Algorithme a priori
 Classement par lift

Les « lift » < 1 (ce qui équivaut à une progression brute négative) sont des règles sans intérêt.
Les 7 premières règles se résument à l’association : Citron – Pomme –
Orange. Il ne reste qu’une seule autre association : Raisin – Banane.
 règles d’associations
Algorithme a priori
 Classement par IC * IS

 On obtient les mêmes résultat qu’avec le lift.

 règles d’associations
Algorithme a priori
 Classement par capacité de déploiement

L’observation des capacités de développement montre que le triplet Citron – Pomme – Orange
est intéressant à déployer, tandis que le couple Raisin – Banane l’est moins.
 règles d’associations
Algorithme a priori
 Support et confiance ne sont pas toujours suffisants
 Ex : Soient les 3 articles A, B et C

 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
 règles d’associations
Algorithme a priori
 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 : Si A alors B ; support=25% ; confiance=55% ;

Amélioration = 1.31 donc Meilleure règle
règles d’associations
Algorithme a priori
règles d’associations
Algorithme a priori
règles d’associations
Algorithme a priori