Data Mining (Fouille de données)

Iskandar KESKES
iskandarkeskes@[Link]

Assistant en informatique de gestion à ISGG

Membre du laboratoire MIRACL

Membre du laboratoire IRIT

Université de Gabès
Institut supérieur de Gestion de Gabès

Cours data mining - Iskandar KESKES 1

 Plan du Cours

1. Introduction au Data Mining

2. Processus ECD
3. Techniques de Data Mining
4. Découverte de règles d’association
5. Classification automatique
6. Arbres de décision
7. Réseaux de neurones
8. Manipulation d’outils logiciels de DataMining.

Cours data mining - Iskandar KESKES 2

 3. Classification
automatique

Cours data mining - Iskandar KESKES 3

 Avant-propos
Classification ou clustering?

Cours data mining - Iskandar KESKES 4

 Définition
L’objet du clustering : le groupent automatique d'objets en classes de
telle manière à :
 Maximiser la ressemblance intra-groupes
 Minimiser la ressemblance inter-groupes =>
Maximiser la dissemblance inter-groupes
Résultats du clustering :
 les objets soient les plus similaires possibles au sein d'un groupe
(critère de compacité)
 les groupes soient aussi dissemblables que possible (critère de
séparabilité)
Utilité du clustering : réduction de la complexité dans certains
problème selon le postulat qui stipule que :
 Deux objets de la même classe se ressemblent ont donc le même
comportement
 Tout élément d’une classe peut-être remplacé par un représentant
de la classe (Choix du représentant?)
Cours data mining - Iskandar KESKES 5
Le point de départ

Regrouper est donc une histoire

d'évaluation de la ressemblance entre individus

=> Une bonne clustérisation regroupe des individus

ressemblant

d'évaluation de la dissemblance (ou ressemblance) entre

deux classes (ensembles d'individus)

=> Une bonne clustérisation sépare des groupes

dissemblables

Cours data mining - Iskandar KESKES 6

Le point de départ

Évaluation de la ressemblance (comparaison)

Comment procède-t-on?
Exemple : parmi les dix objets suivants quels sont les
deux les plus ressemblants?

Cours data mining - Iskandar KESKES 7

Le point de départ

Exemples d’application :
Identifier des groupes d’individus ou de
ménages ayant un comportement homogène
vis-à-vis de :
la consommation de différents produits,
la consommation de différentes marques ou
variétés,
l’attitude par rapport à un produit,
...

 Il s’agit de problèmes souvent traités avec les

méthodes de classification automatique.

Cours data mining - Iskandar KESKES 8

Le point de départ

Données analysées :
 Un tableau individus-variables :
n individus (objets) décrits par p variables
(descripteurs) ;
un tableau à valeurs numériques
continues (valeur de la variable j pour
l’individu i) ;
un tableau de contingence (croisant deux
partitions d’une même population) ;
un tableau de présence–absence (valeur
0 ou 1).
 Un tableau carré symétrique de
similarités ou de distances.

Cours data mining - Iskandar KESKES 9

Le point de départ

Objectifs :
Constituer des groupes d’objets
homogènes et différenciés tels que :
 les objets soient les plus similaires possibles
au sein d’un groupe (critère de compacité) ;
 les groupes soient aussi dissemblables que
possible (critère de séparabilité).

La ressemblance ou la dissemblance

étant mesurée sur l’ensemble des
variables descriptives.

Cours data mining - Iskandar KESKES 10

Le point de départ

Hypothèse :
On suppose qu’une structure de
classes existe au sein de la
population étudiée.

Le but de la classification est de la

mettre à jour ou de l’identifier.

 On suppose que la population étudiée

est séparable.

Cours data mining - Iskandar KESKES 11

Le point de départ

Représentations :
La représentation synthétique peut
être :
une typologie ;
une partition ;
une hiérarchie de partitions (arbre
hiérarchique) ;
une hiérarchie de recouvrements
(pyramide).

Cours data mining - Iskandar KESKES 12

Le point de départ

Une classification automatique obtenue sur un ensemble n’est

jamais la classification de cet ensemble . . .

 C’est une classification parmi beaucoup d’autres.

La classification fait appel à une démarche algorithmique et

non aux calculs formalisés usuels en statistique.

La définition des classes se fait à partir d’une formulation

algorithmique.
Une série d’opérations définies de façon récursive et répétitive.
La mise en oeuvre de la plupart des techniques de classification
ne nécessite que des notions mathématiques relativement
élémentaires.

Cours data mining - Iskandar KESKES 13

Le point de départ

Les étapes de la classification

automatique :
1. Choix des données.

2. Calcul des dissimilarités entre les n

individus à partir du tableau initial.
3. Choix d’un algorithme de classification et
exécution.
4. L’interprétation des résultats :
évaluation de la qualité de la classification,
description des classes obtenues.

Cours data mining - Iskandar KESKES 14

Le point de départ

Calcul des ressemblances :

 Variables quantitatives
 La distance euclidienne est une mesure
possible de la ressemblance.
 Dans le cas de variables hétérogènes, il
faut travailler sur les données centrées
réduites.
 Variables qualitatives
 De nombreux indices de ressemblance ont
été proposés.
 Dans le cas d’objets décrits par des
variables binaires, indice de Jaccard, indice
de Russel et Rao.

Cours data mining - Iskandar KESKES 15

Le point de départ

Il existe plusieurs familles d’algorithme

de classification.
On s’intéresse d'abord aux algorithmes
hiérarchiques
 Les algorithmes ascendants (ou encore
agglomératifs) qui procèdent à la construction
des classes par agglomérations successives
des objets deux à deux, et qui fournissent une
hiérarchie de partitions des objets.
 Les algorithmes descendants (ou encore
divisifs) qui procèdent par dichotomies
successives de l’ensemble des objets, et qui
peuvent encore fournir une hiérarchie de
partitions.

Cours data mining - Iskandar KESKES 16

Le point de départ

Les algorithmes ascendants (ou encore agglomératifs)

 Les algorithmes descendants (ou encore divisifs)

Cours data mining - Iskandar KESKES 17
Le point de départ

Une hiérarchie de partitions (arbre hiérarchique)

Cours data mining - Iskandar KESKES 18

Le point de départ

Évaluation de la ressemblance

Modèle pour la comparaison

Pour des approches pour l’évaluation de la ressemblance, les
modèles comprennent:
Référentiel => modèle de représentation
Une fonction de similarité => évaluation du degrés de
ressemblance dans le référentiel
Une fonction de similarité entre groupes d'objets
 Remarque
Ces composantes sont autant d'occasions/risques de s'éloigner de la
réalité

Cours data mining - Iskandar KESKES 19

Le point de départ

En résumé:

Un algorithme de classification commence par le choix des

paramètres pour la comparaison (features selection / référentiel)

Un algorithme de classification définit une mesure de

ressemblance/dissemblance
•Entre objets
•Entre groupes d’objet
Dans l’espace des paramètres choisis

Cours data mining - Iskandar KESKES 20

Vocabulaire de base

Cours data mining - Iskandar KESKES 21

 Distances

Cours data mining - Iskandar KESKES 22

 Distances

Cours data mining - Iskandar KESKES 23

 Similarité

Cours data mining - Iskandar KESKES 24

 Similarité

Cours data mining - Iskandar KESKES 25

 Similarité

Cours data mining - Iskandar KESKES 26

 Similarité

Cours data mining - Iskandar KESKES 27

 Méthodes

Cours data mining - Iskandar KESKES 28

 CAH

Cours data mining - Iskandar KESKES 29

 CAH

Cours data mining - Iskandar KESKES 30

 CAH

Cours data mining - Iskandar KESKES 31

 CAH

Un dendrogramme

Cours data mining - Iskandar KESKES 32

 CAH

Cours data mining - Iskandar KESKES 33

 CAH

Cours data mining - Iskandar KESKES 34

 CAH

Cours data mining - Iskandar KESKES 35

 CAH

Cours data mining - Iskandar KESKES 36

 CAH

Cours data mining - Iskandar KESKES 37

 CAH

Première observation :
 La stratégie intuitive utilisé pour passer d’une partition
Pi à la suivante Pi+1 ne remet pas en cause les
regroupements.
 Si deux individus sont réunis dans une classe, ils
restent ensemble tout le temps.
 Les partitions ainsi construites sont emboîtées de la
plus fine à la plus grossière.
 On obtient une hiérarchie de partitions qu’on peut
représenter par un dendrogramme.

Cours data mining - Iskandar KESKES 38

 CAH

Deuxième observation :

Cours data mining - Iskandar KESKES 39

K-Means (Supervisé)

Cours data mining - Iskandar KESKES 40

K-Means (Supervisé)

Cours data mining - Iskandar KESKES 41

 Stratégies Mixtes

Cours data mining - Iskandar KESKES 42

 Dissimilarité entre deux points

Mesures de distance :
La plupart des techniques de classification font appel à des
mesures de distance, appelé aussi métrique.

 Evaluer les degrés de dissemblance ou de ressemblance entre

deux individus ou deux groupes d’individus.

 La dissemblance entre deux d’individus est évaluée par la

notion de dissimilarité dont le sens mathématique peut se
traduire par divers critères de mesure quantitative.

Cours data mining - Iskandar KESKES 43

 Dissimilarité entre deux points

Types de dissimilarité :
 Selon la nature des données, on distinguent quatre
groupes de critères de dissimilarité entre individus :

1. la dissimilarité définie sur les données quantitatives ;

2. la dissimilarité définie sur les données qualitatives,
fréquentielles, ou les données d’occurrences ;
3. la dissimilarité définie sur les données ordinales ;
4. la dissimilarité définie sur les données logiques.

Cours data mining - Iskandar KESKES 44

 Dissimilarité entre deux points

Cours data mining - Iskandar KESKES 45

 Dissimilarité entre deux points

Cours data mining - Iskandar KESKES 46

 Dissimilarité entre deux points

Cours data mining - Iskandar KESKES 47

 Dissimilarité entre deux points

Cours data mining - Iskandar KESKES 48

 Dissimilarité entre deux points

Cours data mining - Iskandar KESKES 49

 Dissimilarité entre deux points

Cours data mining - Iskandar KESKES 50

 Dissimilarité entre deux points

En utilisant la distance de Manhattan

Calculer les distances entre p1et p2
Calculer les distances entre p1et p3

Intuitivement on sait que p3 est plus proche à p1 que p2

 Il faut normaliser les données

Cours data mining - Iskandar KESKES 51

 Dissimilarité entre deux points

Lorsque les données sont des réels

Il faut calculer des valeurs standardisées pour ces données

Les xji standardisées (z-score)

Cours data mining - Iskandar KESKES 52

 Dissimilarité entre deux points

6,7
5,29

Cours data mining - Iskandar KESKES 53

 Dissimilarité entre deux points

Lorsqu’il s’agit de données binaires, il faut tout

d’abord tracer la table de contingence (table de
dissimilarité) de ces données

Cours data mining - Iskandar KESKES 54

 Dissimilarité entre deux points

Les distances utilisées

Le coefficient de correspondance simple

Le coefficient de Jaccard

Exemple : Oi=(1,1,0,1,0) et Oj=(1,0,0,0,1)

a= 1 b=2 c=1 d=1
dcs(Oi,Oj)=3/5
djc(Oi,Oj)=3/4

Cours data mining - Iskandar KESKES 55

 Algorithme de CAH

Lance et William (1967)

Etape 0 : il y a n éléments à classer (n objets) ;

Etape 1 : on construit la matrice de distances entre les n éléments et

l’on cherche les deux plus proches, que l’on agrège en un nouvel
élément. On obtient une première partition à (n−1) classes ;
Etape 2 : on construit une nouvelle matrice des distances qui résultent
de l’agrégation, en calculant les distances entre le nouvel élément et les
éléments restants (mêmes conditions qu’à l’étape 1 avec (n−1)
éléments). On cherche les deux éléments les plus proches, que l’on
agrège. On obtient une deuxième partition avec (n−2) classes et qui
englobe la première ;
Etape m : on calcule les nouvelles distances, et l’on réitère le processus
jusqu’à n’avoir plus qu’un seul élément regroupant tous les objets et qui
constitue la dernière partition.

Cours data mining - Iskandar KESKES 56

 Algorithme de CAH (Exemple)

Cours data mining - Iskandar KESKES 57

 Algorithme de CAH (Exemple)

Cours data mining - Iskandar KESKES 58

 Algorithme de CAH (Exemple)

Cours data mining - Iskandar KESKES 59

 Algorithme de CAH (Exemple)

Cours data mining - Iskandar KESKES 60

 Algorithme de CAH (Exemple)

Cours data mining - Iskandar KESKES 61

 Exercice
Soit Le tableau de dissimilarités suivant:

En utilisant CAH, construire le dendrogramme en

utilisant la méthode d’agrégation suivante:
 Lien minimum (saut minimal)
 Lien maximum (saut maximal)
 Lien moyen
Cours data mining - Iskandar KESKES 62
 Réponse

Cours data mining - Iskandar KESKES 63

 Réponse

Cours data mining - Iskandar KESKES 64