LE2I – Laboratoire Electronique, Informatique et Image

Unité Mixte de Recherche CNRS 5158

Université de Bourgogne

Rapport technique
Janvier 2012
Pré-stage Master Recherche 3I

Data Mining

Yoan Chabot
Rapport Technique Jan. 12 Data Mining 2

CONTENU

Introduction.............................................................................................................................. 4

Qu’est-ce que le Data Mining ?.................................................................................................4

Histoire et Applications.............................................................................................................4

Principe général du Data Mining...............................................................................................5

Méthodologie........................................................................................................................... 6

Compréhension du métier.....................................................................................................6

Compréhension et préparation des données.......................................................................6

Modélisation......................................................................................................................... 7

Evaluation de la modélisation............................................................................................... 9

Déploiement des résultats.................................................................................................. 10

Techniques de Data Mining.....................................................................................................10

Méthodes de classification..................................................................................................10

Classification par partitionnement...................................................................................12

Classification hiérarchique...............................................................................................16

Classification mixte.......................................................................................................... 17

Classification neuronale...................................................................................................17

Classification relationnelle...............................................................................................22

Méthodes d’association...................................................................................................... 22

Algorithme a priori...........................................................................................................24

Méthodes d’estimation....................................................................................................... 27

Régression Lineaire..........................................................................................................27

Méthodes de Segmentation................................................................................................28

Méthodes de Prévision........................................................................................................29

Références.............................................................................................................................. 29

FIGURES
Figure 1 Distance entre clusters............................................................................................................................12
Figure 2 Méthodes des K-Moyennes.....................................................................................................................13

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 3

Figure 3 Méthodes des K-Moyennes.....................................................................................................................14

Figure 4 Méthode des voisinages denses..............................................................................................................15
Figure 5 Méthode des voisinages denses..............................................................................................................16
Figure 6 Neurone biologique................................................................................................................................18
Figure 7 Fonction de Heaviside et fonction Sigmoïde...........................................................................................19
Figure 8 Réseau entièrement bouclé, sans feedback et avec feedback.................................................................19
Figure 9 Perceptron..............................................................................................................................................20
Figure 10 Perceptron multicouche........................................................................................................................20
Figure 11 Carte de Kohonen.................................................................................................................................21
Figure 12 Régression linéaire simple....................................................................................................................28

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 4

INTRODUCTION

Ce dossier constitue un état de l’art du domaine du Data Mining. Ce document ne se veut

toutefois pas exhaustif et la priorité sera placée sur les éléments susceptibles d’être
pertinent dans le contexte nous intéressant : la construction automatique d’ontologies.

Dans un premier temps, nous donnerons une définition générale du Data Mining puis nous
présenterons l’histoire de ce domaine de recherche puis ces principes fondateurs. Dans la
suite de ce rapport, nous étudierons des méthodologies utilisées pour mener à bien des
projets de Data Mining puis nous présenterons ensuite les différentes familles de techniques
utilisées dans ce domaine.

QU’EST-CE QUE LE DATA MINING ?

Le Data Mining (ou exploration de données, fouille de données, extraction de connaissances

ou encore knowledge discovery in databases (KDD)) est un domaine de l’informatique dont
le but est de proposer des méthodes et des techniques permettant d’extraire des
connaissances à partir de quantités de données importantes. Extraire des connaissances
peut signifier mettre en évidence des données cachées, découvrir des corrélations
significatives entre des connaissances ou encore prédire de nouvelles connaissances. Pour
résumer, le Data Mining est le procédé permettant de convertir les données en
connaissances (« extraire les pépites d’informations de la gangue des données »).

Le Data Mining utilise des techniques variés issues de l’Intelligence Artificielle ou encore des
statistiques. Grâce à des capacités de calculs toujours plus importantes et pour traiter des
informations toujours plus nombreuses (augmentation de la capacité des supports de
stockage, optimisation des moyens de productions de l’information et plus grand nombre de
producteurs…) et interconnectées, de nombreuses entreprises sont amenés à utiliser les
algorithmes issus de ce domaine. Parmi les exemples d’utilisation les plus courants, on
trouve notamment des applications dans le marketing, la détection de fraude ou encore
certaines expériences scientifiques. L’attrait du monde industriel pour le Data Mining a
permis de faire de ce domaine l’un des plus actifs de la communauté scientifique
informatique. D’après le MIT (Massachusetts Institue of Technology), le Data Mining pourrait
faire partie des technologies qui auront un impact important sur le monde au XXIème siècle.

HISTOIRE ET APPLICATIONS

La problématique d’extraction de connaissances à partir de volumes de données importants

est une problématique intéressant l’homme depuis de nombreux siècles. Les premières
collectes importantes de données (ou recensement) remonte à 2238 avant Jésus Christ en
Chine où l’empereur Tang Yao avait souhaité recenser les récoltes produites. Toutefois,
l’homme s’intéressera réellement à l’analyse des volumes de données collectées seulement
à partir du 17ème siècle. John Graunt, en 1662, publie un livre ayant pour sujet l’analyse de la
mortalité dans le but de prévoir l’apparition de la peste bubonique. Par la suite, Thomas
Bayes, Pierre-Simon de Laplace et Adrien-Marie Legendre contribue à la mise en place du
socle mathématiques du futur domaine du Data Mining en proposant le théorème de Bayes
ou encore la méthode des moindres carrés. De nombreuses techniques aujourd’hui utilisées
en Data Mining voient ensuite le jour en même temps que les premiers calculateurs dans les

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 5

années 1950-1960: les réseaux neuronaux, les algorithmes génétiques, les arbres de
décisions ou encore les techniques de segmentation.

Le terme Data Mining voit le jour durant les années 1960. D’abord employé péjorativement
pour désigner le mépris des statisticiens pour les démarches de déduction sans fondement,
le nom de Data Mining a définitivement était adopté durant les années 1990.

De nos jours, de nombreuses entreprises utilisent les techniques de Data Mining. Parmi les
applications les plus courantes, on trouve tout d’abord les systèmes de prospection. Les
entreprises de publicité, pour vendre des produits, utilisent des supports tels que des e-mails
ou des publicités papiers. Les techniques de Data Mining sont utilisées pour réduire le coût
des campagnes publicitaires en permettant de cibler les clients offrant une probabilité de
réponse aux offres importantes.

Le Data Mining est également abondamment utilisé par les sociétés de ventes. Ces outils
sont ici utilisés pour analyser le profil des utilisateurs afin de produire des offres
personnalisés. Parmi ces sociétés de vente, on trouve notamment l’entreprise Amazon qui
utilisent ce type d’outils pour suggérer des produits à ces clients.

Les sociétés de vente (mais également les banques ou encore les opérateurs en
communication) utilisent également le Data Mining pour lutter contre l’attrition
(phénomène entraînant la perte de clients) en partant du principe qu’il est plus aisé de
conserver un client (en lui proposant des promotions par exemple) que d’en acquérir un
nouveau.

Le Data Mining est aussi employé par les assurances et les banques pour identifier des profils
de clients. Dans le cas des banques, les techniques d’extraction peuvent par exemple
permettre d’évaluer un taux de risque pour un client demandant un prêt ou de fixer les tarifs
d’assurance en fonction du risque d’accident.

Les forces de l’ordre ont également recours au Data Mining pour la prévention des crimes.
Enfin, ce domaine de recherche joue également un rôle de premier plan dans les recherches
sur le génome humain.

PRINCIPE GÉNÉRAL DU DATA MINING

Pour produire des connaissances, le Data Mining se repose sur quelques principes simples.
Lors de l’étude d’un ensemble de données, il est possible d’identifier des ensembles de
caractéristiques souvent associé avec un comportement en particulier. Il s’agit ici d’étude le
« synchronisme de l’implication ». Si l’on constate que cet ensemble de caractéristiques est
toujours lié au même comportement, on peut alors déduire que les caractéristiques sont la
cause du phénomène. On parle ici de «diachronisme de la relation causale ».

Par exemple, si nous constatons que tous les matins où le sol est mouillé, un phénomène
pluvieux a été observé durant la nuit (synchronisme de l’implication), on peut en déduire
une relation causale qui dit que « si il pleut, le sol est mouillé » (diachronisme de la relation
causale). Il est important de noter que la déduction de relation causale ne peut se faire que
sur des jeux de données suffisamment volumineux. En effet, il est difficile de définir ce qu’est
une maison (par exemple) après en avoir vu une seule. C’est en voyant un certain nombre de

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 6

maisons que l’on peut tirer des généralités comme la présence d’une porte, d’un toit ou
encore de murs permettant de définir ce qu’est le concept de maison.

Il est également important de préciser que cette méthode de déduction présente plusieurs
limites. Tout d’abord, ce type de déduction se base sur les statistiques. Les interprétations
qui en découlent ne sont donc pas nécessairement valables pour chacun des individus de la
population. Dans le cas d’une banque par exemple qui utilise le Data Mining pour identifier
les caractéristiques des mauvais payeurs, il est tout à fait possible qu’un client présentant les
caractéristiques identifiées paie toujours ses dettes. La corrélation statistique n’est donc pas
équivalente à la causalité physique.

MÉTHODOLOGIE

Afin d’augmenter la réussite des projets utilisant le Data Mining, de nombreuses

recommandations ont émergé au fil du temps. Plusieurs méthodologies ont ainsi vu le jour
parmi lesquelles on trouve notamment CRISP-DM (Cross Industry Standard Process for Data
Mining), SEMMA (Sample, Explore, Modify, Model, Assess) ou encore la méthode des Six
Sigma. Nous traiterons ici de la première méthode qui semble être la plus reconnue et
utilisée actuellement dans le milieu du Data Mining.

Cette méthode se compose de la manière suivante :

Acteurs Etapes Phases

Objectifs Compréhension du métier
Données Compréhension des données
Maître d’oeuvre Préparation des données
Traitements Modélisation
Evaluation de la modélisation
Maître d’ouvrage Déploiement Déploiement des résultats

COMPRÉHENSION DU MÉTIER

La première phase, réalisée par le maitre d’œuvre, consiste le plus souvent à rédiger un
cahier des charges. Ce dernier a pour objectif de lister les objectifs du projet et les
contraintes inhérentes à ce dernier (contraintes en temps, contraintes budgétaires…) et de
traduire ces objectifs en un problème de Data Mining.

L’exemple suivant permet d’illustrer la phase de compréhension du métier. Un constructeur

de véhicules veut étudier les plaintes de ces clients suite à des achats de voitures.
L’entreprise fait appel à une entreprise spécialisée en Data Mining pour étudier les plaintes
concernant plus de 10 millions de véhicules. Pour chaque plainte, les caractéristiques de la
voiture, de sa fabrication et du garage ayant réalisé la vente sont conservées. Le maître
d’œuvre, après concertation avec le maître d’ouvrage, fixe les objectifs. Ici, il peut s’agir par
exemple de réduire les coûts associés aux plaintes en réduisant le nombre de ces dernières.
Un objectif sous-jacent est d’augmenter la satisfaction générale des clients vis-à-vis du
constructeur. A partir de ces objectifs, le maître d’œuvre peut poser le ou les problèmes de
Data Mining. Dans le cas présent, il peut s’agir de savoir si l’on peut établir une relation entre

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 7

certaines caractéristiques des voitures et certains types de plaintes ou encore certains

garages et certains types de plaintes.

COMPRÉHENSION ET PRÉPARATION DES DONNÉES

Ces deux phases sont les plus importantes et les plus coûteuses d’un projet de Data Mining.
La phase nommée « compréhension des données » a pour but de collecter, de comprendre
(entrevoir les connaissances contenues dans les données) et d’évaluer la qualité des
données qui seront utilisées pour le minage.

Pour comprendre cette phase, il est tout d’abord nécessaire d’introduire un vocabulaire
propre au Data Mining. Dans ce domaine, les données utilisées sont généralement sous la
forme de tableaux. Ces tableaux représentent les concepts observés par l’étude (tableaux de
voiture, de plaintes…). Chaque ligne de ce tableau est appelée « individu ». L’ensemble des
individus est appelé « population », Chaque colonne d’un tableau correspond à une
propriété/un attribut. Ces propriétés sont aussi appelées « variables ». Pour chaque objet,
une valeur est donnée à cette variable. Cette valeur est appelée « donnée ». Une sélection
de quelques valeurs pour des propriétés d’un tableau donne en résultat un « segment »/une
« classe ».

Il existe ensuite plusieurs types de variables. On distingue tout d’abord les variables
numériques des variables catégorielles. Ce second type correspond à des variables pouvant
prendre un nombre de valeurs restreint. La variable poids pouvant prendre pour valeur
« mince », « normal » et « gros » est un exemple de variable catégorielle.

Lorsque le Data Mining est utilisé pour faire de la prévision (nous verrons de quoi il s’agit
plus loin dans ce rapport), on distingue alors deux types de variables : la variable cible d’une
part qui est la variable à prédire et les prédicteurs d’une autre part qui sont les variables
utilisées pour la prédiction.

La compréhension des données comprend plusieurs étapes :

 Inventorier les données existantes et les stocker dans des tableaux.

 Etablir un dictionnaire des données en identifiant notamment le nom, le type et la

signification de chacune des variables.

 Réaliser des études statistiques basiques sur les données afin de prendre
connaissance de la physionomie du jeu de données.

 Nettoyer les données en supprimant, le cas échéant, la ou les clefs primaires,

identifier et renseigner les données manquantes, identifier les données aberrantes à
l’aide de méthodes graphiques ou numériques et corriger l’aberration (suppression,
remplacement par la valeur moyenne…), corriger les incohérences.

La phase de préparation des données doit permettre, quant à elle, de transformer les
données brutes en données exploitables par les algorithmes de Data Mining. Cette phase
doit notamment permettre d’identifier les variables à analyser pour répondre au problème
posé par la première phase. La phase de préparation permet de réaliser les transformations
nécessaires sur les données pour permettre de faciliter la recherche de la solution au

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 8

problème et en s’appuyant sur les connaissances des données acquises lors de la phase
précédente.

MODÉLISATION

La quatrième phase est une des plus importantes. Elle a pour objectif de choisir et
paramétrer la technique d’extraction la plus appropriée au problème.

On distingue deux grands types de méthodes d’extraction de connaissances : les méthodes

descriptives et les méthodes prédictives.

Les méthodes descriptives sont utilisées pour mettre au jour des connaissances présentes
(mais cachées) dans un volume de données. Il s’agit ici de produire un jugement sur les
données en présence. Un exemple connu de méthodes descriptives est l’étude du caddy de
la ménagère. Dans cette application, il s’agit d’étudier les articles les plus couramment
acheté ensemble. Il est ensuite possible de déduire des règles permettant de placer de
manière stratégique des produits dans un magasin. Les techniques descriptives visent à
résumer, synthétiser ou encore classer les données. Il n’y a pas de variables cibles à prédire
dans ce type de techniques. Les méthodes descriptives sont non supervisées. Elle ne requiert
donc pas (ou peu) d’interventions humaines pour fonctionner.

Les méthodes prédictives ont pur but de déduire de nouvelles informations par
extrapolation à partir d’un volume de données. Il s’agit ici de produire des règles de
raisonnements afin de déduire de nouvelles connaissances à partir de celles existantes. Ces
méthodes cherchent à généraliser des règles présentes dans l’ensemble partielle de données
observées. Le but des méthodes prédictives est de prévoir la valeur d’une variable cible.
Généralement, les techniques prédictives sont supervisées.

Une distinction est également faite entre les méthodes utilisant des variables numériques et
les méthodes utilisant des variables catégorielles.

Il existe six familles de techniques de Data Mining. Trois d’entre elles sont des méthodes
appartenant à la famille des méthodes descriptives :

 Les méthodes de description : Cette famille de méthodes consiste à mettre en avant

la physionomie de la répartition des valeurs d’une variable (histogramme, écart-type,
moyenne…) ou les liens liant la répartition des valeurs de plusieurs variables (étude
des tendances). L’intérêt principal de ces méthodes est de permettre une meilleure
compréhension des données. L’étude de la répartition des achats de voiture par
tranches d’âge peut être une application possible des méthodes de description.
Parmi les techniques les plus connues, on trouve notamment l’ensemble des
méthodes graphiques tel que les histogrammes ou encore les nuages de points.

 Les méthodes de classification : Autrement appelé « clustering », ces méthodes

permettent de créer des sous-ensembles (aussi appelés « cluster »). Tout l’enjeu de
la classification se trouve dans les caractéristiques de ces clusters : les éléments
composant un même groupe doivent être le plus similaires possible tandis que les
données de deux groupes distincts doivent être différentes (de manière à ce que
l’intersection des clusters soit égale à l’ensemble vide). On parle ici de
« métatypologie » car il s’agit de créer de nouveaux types dans un ensemble. Le

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 9

clustering peut être utilisé pour segmenter un ensemble de clients en fonction de

leurs revenus par exemple. Cela permet de créer des groupes distincts d’individus
ayant des caractéristiques de revenus similaires. Parmi les techniques de clustering
les plus connues, on trouve notamment l’algorithme des K moyennes (« k means »)
ou les cartes de Kohonen.

 Les méthodes d’association : Ces méthodes permettent, comme leurs noms

l’indiquent, de créer des associations entre les valeurs des différentes variables. A
l’instar de certaines méthodes prédictives, il s’agit ici de mettre en évidence des
règles du type « si une variable a pour valeur x, alors la variable y aura la valeur z ».
Cependant, les méthodes d’association se différencient des méthodes prédictives
par le fait qu’il n’y a pas de variables cibles particulières à prédire. En effet, les
algorithmes d’association recherchent des corrélations sur l’ensemble des données.
Ces méthodes peuvent être utilisées sur des problèmes comme l’analyse du panier
de la ménagère (évoqué un peu plus tôt dans ce rapport) par exemple. Parmi les
techniques d’association les plus connues, on trouve notamment l’algorithme à
priori ou l’algorithme du GRI.

Les trois autres sont des méthodes appartenant à la famille des méthodes prédictives :

 Les méthodes d’estimation : Il s’agit ici d’identifier comment un ensemble de

prédicteurs et une variable cible numérique sont liés. Après avoir identifié ce lien, il
est alors possible d’estimer la valeur d’une variable cible dont la valeur est inconnue
à partir des prédicteurs qui lui sont associés. Grâce à ces méthodes, il est par
exemple possible d’estimer le pourcentage de risque d’accident vasculaire cérébral à
partir de l’âge, de l’activité physique et constantes physiques d’un patient. Parmi les
méthodes les plus utilisées dans cette famille ont trouve notamment la régression
linéaire simple ou multiple ou les réseaux de neurones.
 Les méthodes de segmentation : Les méthodes par segmentation ont le même
fonctionnement et les mêmes objectifs que les méthodes d’estimation. La principale
différence se situe dans le fait que la variable cible est ici une variable catégorielle.
On parle donc de segmentation car chaque valeur possible de la variable cible
entraînera la création d’un groupe d’individus. Il est par exemple possible d’utiliser
ces méthodes pour permettre l’affectation d’un nouvel individu dans une population
de patients divisée en trois groupes représentatifs du niveau de risques d’accident
vasculaire cérébral : aucun risque, à surveiller, risque important. Parmi les techniques
les plus courantes en segmentation, on trouve les méthodes graphiques comme les
nuages de points, la méthode des K plus proches voisins, les arbres de décisions et les
réseaux de neurones.
 Les méthodes de prévision : La principale différence entre les deux types de
méthodes précédentes et les méthodes de prévisions se situent dans le temps utilisé
pour la prédiction. Dans le cas des deux premières méthodes, les prédictions
concernent le présent. En effet, la segmentation et l’estimation prédisent la valeur
d’une variable à l’instant présent. Les méthodes de prévisions permettant quant à
elle d’estimer la valeur d’une variable dans le futur. Il est ainsi possible de répondre à
des problèmes comme la prévision du prix d’un bien dans une ou plusieurs années ou
encore de prédire le vainqueur d’un tournoi de tennis au regard des résultats
précédents et des caractéristiques des joueurs par exemple. Les techniques utilisées

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 10

pour la prévision sont les mêmes que celles utilisées pour faire de l’estimation et de
la segmentation.

EVALUATION DE LA MODÉLISATION

L’évaluation de la modélisation intervient après que les premiers résultats, produits par la
technique choisie lors de la phase précédente, soient donnés. Cette phase a pour but de
déterminer si la modélisation utilisée donne des résultats de qualité (résultats pertinents) et
si elle permet d’atteindre les objectifs fixés par le projet.

DÉPLOIEMENT DES RÉSULTATS

La dernière phase est réalisée par le maître d’ouvrage (le client et utilisateur principal de
l’application de Data Mining). Elle a pour but de prendre des décisions au regard des
résultats fournis par l’application.

TECHNIQUES DE DATA MINING

Dans cette partie, nous allons présenter plus en détails les techniques les plus courantes
utilisées dans la phase de modélisation.

MÉTHODES DE CLASSIFICATION

Comme nous l’avons dis précédemment, les méthodes de classification permettent de créer
des sous-ensembles dans une population. Contrairement aux techniques de classement, les
critères de classification ne sont pas déterminés au préalable. En effet, les critères dissociant
les différents clusters sont déterminés en fonction des valeurs rencontrées parmi les
individus de la population.

La classification est souvent utilisée pour préparer les données à l’utilisation d’autres
techniques de Data Mining. La classification permet en effet d’étudier les sous-ensembles en
tenant compte d’un nombre de variables réduits car les variables peu discriminantes (ce qui
est souvent le cas car les individus d’un même cluster se ressemblent) peuvent être
supprimées.

Avant d’étudier plus précisément les techniques courantes de clustering, nous allons tout
d’abord introduire quelques notions inhérentes à ce type de méthodes.

On distingue tout d’abord les techniques avec à priori des techniques sans à priori. Les
premières demandent à l’utilisateur de donner une estimation du nombre de classes à
chercher tandis que les secondes fonctionnent automatiquement.

Une distinction est également faite à partir de la configuration des groupes obtenue en
résultat. En règle générale, les algorithmes de classification donnent des sous-ensembles
disjoints en résultat. Toutefois, des techniques dites « mixtes » produisent des sous-
ensembles disjoints avec quelques sous-ensembles inclus. Enfin, les techniques d’analyse

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 11

floue (logique floue) donnent en résultat des sous-ensembles non disjoints mais sans
inclusion.

Plusieurs paramètres numériques peuvent être utilisés pour tester la qualité de la

classification :

 L’inertie totale est une mesure correspondant à la moyenne des carrés des distances
des individus par rapport au barycentre (centre de gravité). L’inertie totale est
indépendante des groupes formés lors de la classification et donne des informations
sur la répartition de la population dans l’espace.
 L’inertie intra-classe, dépendante des groupes formés, correspond à l’inertie totale
de chacune des classes. Lors de la classification, il s’agit de minimiser cette inertie
afin d’obtenir des groupes les plus homogènes possibles.
 L’inertie inter-classe, également dépendante des groupes formés, correspond à la
moyenne pondérée des carrées des distances des centres de gravité de chaque classe
au centre de gravité de la population. Lors de la classification, il s’agit de maximiser
cette inertie afin d’obtenir des clusters très différents.

Enfin, la formule de Huygens définie comme la somme de l’inertie intra-classe et de l’inertie

inter-classe permet de qualifier une classification plus simplement. De nombreuses autres
mesures de qualité ont été créées pour mesurer la qualité d’une classification : proportion
de la variance expliquée par les classes (ou R²), mesure de la séparation entre toutes les
classes (ou Pseudo F), mesure CCC (Cubic Clustering Criterion), mesure de la perte d’inertie
inter-classe provoquée en regroupant deux classes (ou R² semi-partiel).

Dans la plupart des algorithmes de classification, il est nécessaire de mesurer la distance

entre deux groupes d’individus. Plusieurs calculs de distances sont disponibles :

 La distance minimale (ou « saut minimum » ou « single linkage ») mesure la distance

entre les deux individus les plus proches des deux groupes.
 La distance maximale (ou « saut maximum » ou « complete linkage ») mesure la
distance entre les deux individus les plus éloignés des deux groupes.
 La distance moyenne (ou « saut moyen » ou « average linkage ») mesure la distance
moyenne entre tous les individus des deux groupes.
 La distance entre les barycentres (ou « centroid method ») calcule la distance entre
les barycentres des groupes.
 Le critère de Ward est fonction de la distance des barycentres et permet de
maximiser l’inertie inter-classe.

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 12

Figure 1 Distance entre clusters

Il est possible de séparer les méthodes de classification en cinq types :

 La classification par partitionnement

 La classification hiérarchique
 La classification mixte
 La classification neuronale
 La classification relationnelle

CLASSIFICATION PAR PARTITIONNEMENT

La classification par partitionnement consiste à découper l’espace en plusieurs sections. Les

individus situés dans une même section appartiennent à une même classe.

La méthode par partitionnement la plus célèbre est celle des K-Moyennes (et ses variantes
comme la méthode des centres mobiles ou les nuées dynamiques). Le réseau de neurone
nommé « Cartes de Kohonen » permet également de produire une classification par
partitionnement.

MÉTHODE DES K-MOYENNES

Les figures suivantes présentent le fonctionnement de la méthode des K-Moyennes :

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 13

Figure 2 Méthodes des K-Moyennes

Le point de départ de la méthode des K-Moyennes est une population à scinder en n

groupes. Cette technique étant une méthode avec à priori, la valeur n est donc donnée par
l’utilisateur (dans la figure, n est égal à 3). Dans la deuxième étape, l’algorithme sélectionne
n individus au hasard afin de servir de graines. Les individus de la population sont ensuite
reliés à la graine la plus proche dans l’étape 3. Les groupes reliés à la même graine sont alors
regroupés au sein d’un même cluster dans l’étape 4. L’étape suivante calcule les barycentres
de chacun des clusters ainsi créés. On recherche ensuite les individus les plus proches des
barycentres précédemment calculés. Ces derniers deviennent alors les nouvelles graines à
l’étape 6.

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 14

Figure 3 Méthodes des K-Moyennes

Dans l’étape 7, les individus sont à nouveau reliés à la graine la plus proche et des nouveaux
clusters sont formés à l’étape 8 de la même manière que précédemment. On recalcule alors
les barycentres et l’on forme des groupes à nouveau dans les étapes 10, 11 et 12. Dans
l’étape 13, on constate que les groupes formés sont identiques à ceux de l’étape 9. Le
processus de classification est donc terminé.

Parmi les avantages de cette technique, on peut citer sa rapidité et la possibilité d’identifier
facilement les individus isolés (un individu isolé formera une classe). En revanche, cette
méthode présente de nombreux inconvénients parmi lesquels l’obligation de donner un
nombre de groupes à priori avant l’exécution ou encore le caractère aléatoire des groupes
qui dépendent fortement des choix aléatoires des graines. Des variantes permettant
d’améliorer les résultats (au détriment de la vitesse de calcul) ont été proposées : Méthode
des k-medoids ou des k-modes par exemple.

MÉTHODE DES VOISINAGES DENSES

Les figures suivantes présentent le fonctionnement de la méthode des voisinages denses :

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 15

Figure 4 Méthode des voisinages denses

Le principe de l’algorithme des voisinages denses est le suivant. Avant l’exécution de

l’algorithme, l’utilisateur donne au système une valeur d représentant une taille de boule
utilisée pour les calculs de voisinage et une valeur n représentant la densité des groupes
souhaitée (le nombre d’éléments minimum par groupe).

Dans la première étape, le système sélectionne un individu aléatoirement pour devenir la

graine. Dans l’étape 2, une boule virtuelle de rayon d et centrée sur l’individu est tracée et
les individus inclus dans cette boule sont ajoutés au groupe en cours de composition.
L’opération de traçage de boule est ensuite répétée sur chaque nouvel élément du groupe à
l’étape 3. Dans l’étape suivante, de nouveaux individus, contenus dans les boules
précédemment tracées, sont ajoutés à l’agrégat. Ces opérations sont répétées à l’étape 5 et
6 jusqu’à l’arrivée d’un point n’ayant pas d’individus étrangers dans sa boule. Le groupe est
alors stable.

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 16

Figure 5 Méthode des voisinages denses

Dans le cas où tous les individus n’ont pas été classifiés, une nouvelle graine est choisie et les
opérations sont alors renouvelées avec cette nouvelle graine. Lorsque tous les individus de la
population ont été classés, l’algorithme s’arrête.

Bien que cette méthode ne puisse pas être réellement considéré comme une méthode à
priori (puisque le nombre de groupes n’ai pas demandé avant l’exécution de l’algorithme).
Le choix d’une taille de boules et d’une densité rend malgré tout cette méthode assez
complexe à utiliser. La question du choix de ces deux valeurs est un problème difficile.

CLASSIFICATION HIÉRARCHIQUE

Ce type de classifications repose sur deux opérations que sont la réunion d’ensembles et la
scission d’un ensemble. Dans les classifications hiérarchiques par réunion de classes (ou
classification ascendante hiérarchique), on créé tout d’abord autant de classes qu’il y a
d’individus dans la population puis on regroupe les classes les plus proches de manière
décroissante. A chaque étape, les deux classes sujettes à la fusion sont les deux classes les
plus proches de l’ensemble (la formule de distance étant choisie parmi celles données un
peu plus tôt dans ce dossier). A la fin du processus, une seule classe subsiste. A l’inverse, les
méthodes hiérarchiques par division de classes (ou classification descendante hiérarchique)
débutent en considérant une seule classe regroupant l’ensemble des individus puis divise
successivement celle-ci afin d’obtenir des sous classes les plus éloignées possibles de

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 17

manière décroissante. Dans les deux approches, la succession de fusion ou de réunion peut
être représentée par un dendrogramme. Ce type de figures, ayant la forme d’arbres, permet
d’obtenir un visuel sur l’évolution des clusters.

Pour des raisons de complexité, les approches ascendantes sont souvent préférées aux
approches descendantes. Dans les premières, il est nécessaire de maintenir à jour après
chaque étape une structure de données contenant les distances entre les clusters afin de
réaliser lors de l’étape suivante une union entre les deux clusters les plus proches. La mise à
jour des distances, bien que coûteuse, peut être effectué en un temps raisonnable. En
revanche, dans le cas des méthodes descendantes, il est nécessaire, lors d’une tentative de
scission d’un cluster, d’étudier toutes les possibilités de partitionnement en deux parties.
Même sur un cluster de taille réduite, le calcul des nombreuses distances, dû au grand
nombre de possibilités de partitionnement, rend le travail de scission relativement coûteux
en temps. En revanche, les approches descendantes ne sont toutefois pas totalement
délaissées car elle propose malgré tout une vision du problème plus intuitive (le cerveau
humain a tendance à procéder de cette manière).

Un des principaux avantages des méthodes hiérarchiques est qu’il s’agit de méthodes sans à
priori. Le nombre de clusters n’est donc pas fixé à l’avance. En revanche, ce type de
méthodes nécessite de nombreux calculs de distances qui sont autant de coûts
supplémentaires en temps.

CLASSIFICATION MIXTE

Les méthodes de classifications mixtes combinent les caractéristiques des classifications par
partitionnement et hiérarchiques. En général, il s’agit d’utiliser au préalable une méthode de
classification par partitionnement comme les K-Moyennes pour permettre une exécution
plus efficace d’une méthode hiérarchique par la suite.

CLASSIFICATION NEURONALE

Les méthodes de cette famille se basent sur le domaine des réseaux neuronaux pour
classifier des populations. Il est à noter que les classifications neuronales peuvent tout à fait
produire un résultat identique aux classifications par partitionnement par exemple. Enfin,
tous les réseaux de neurones ne sont pas utilisés en classification. L’un des réseaux de
neurones les plus utilisés dans ce domaine reste le réseau de Kohonen. Les autres types de
réseaux de neurones sont plutôt utilisés dans les techniques de segmentation ou
d’estimation (techniques prédictives). Bien que l’ensemble des réseaux de neurones ne soit
pas utilisé dans les techniques de classification, nous présenterons ici quelques généralités
sur les réseaux de neurones afin de faciliter la compréhension des cartes de Kohonen.

RÉSEAUX DE NEURONES

Les réseaux de neurones « formels » notamment utilisés dans le domaine de l’informatique

sont directement inspirés du fonctionnement du cerveau humain et plus précisément de ses
neurones :

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 18

Figure 6 Neurone biologique

Un neurone biologique fonctionne en recevant des impulsions électriques par le biais de

long filament nommés dendrites et en envoyant des impulsions par le biais d’un axone. Les
quelques 100 milliards de neurones du cerveau humain sont connectés entre eux via des
contacts entre un axone d’un neurone et une dendrite d’un second neurone. Ces connexions
sont nommées synapse. Lorsqu’une impulsion électrique atteint la jonction synaptique, des
neuromédiateurs sont produits pour exciter ou inhiber les effets du signal.

La composition et le fonctionnement des neurones ont été formalisés par des chercheurs
pour former un neurone formel. Chaque neurone est caractérisé par un seuil et par des
poids synaptiques portés par chacun des synapses en entrée. Le neurone, lorsque sa
fonction d’activation renvoie un 1 (indiquant que la somme des produits des entrées par les
poids synaptiques (à laquelle on retranche le seuil) a atteint une valeur admise), envoie un
signal sur le canal de sortie (l’équivalent de l’axone en biologie). Il est important de préciser
que la valeur de sortie est souvent comprise dans l’intervalle [0,1].

X1 W1
xa

Entrée X2
W2
Sortie
W3

X3

Sur la figure ci-dessus, les signaux reçus par le neurone sont contenus dans les variables xi
tandis que les poids synaptiques sont contenus dans les variables wi. Comme nous l’avons
dis plus tôt, chaque neurone est doté d’une fonction d’activation f et d’un seuilθ . Ainsi, la
valeur de sortie d’un neurone ayant M entrées peut être déterminée à l’aide de la formule
suivante :

Sortie= f ¿

Lorsque la valeur de sortie est proche de 1, le neurone est actif. Lorsque la valeur est proche
de 0, le neurone est inactif. En règle générale, la fonction d’activation choisie n’est pas
linéaire afin de rendre le réseau de neurones plus intéressant. En effet, lorsqu’une fonction
d’activation linéaire est utilisée, le réseau de neurones devient équivalent à une régression
multi-linéaire.

Deux fonctions non-linéaires sont fréquemment utilisées :

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 19

 La fonction de Heaviside : g ( x )=1 si x ≥ 0 et g ( x )=0 sinon

1
 La fonction sigmoïde : g ( x )= −x
1+ e

Figure 7 Fonction de Heaviside et fonction Sigmoïde

Trois caractéristiques sont nécessaires pour définir intégralement un réseau de neurones :

 Son architecture : comment connecter les neurones entre eux ? Parmi les
architectures les plus couramment utilisées, on trouve notamment les réseaux de
type « Un pour tous, tous pour un » où la connectivité est totale entre les neurones.
Chaque neurone est ainsi relié à tous les autres neurones. Un autre type
d’architecture est le modèle « Sans retours, ni consignes » (ou feed-forward) où le
réseau est orienté dans une direction. Un troisième type de réseau est le modèle
avec feedback (ou retour arrière).

Figure 8 Réseau entièrement bouclé, sans feedback et avec feedback

 Sa dynamique : comment se propage les signaux dans le réseau ? Le réseau peut

notamment être synchrone ou asynchrone. Dans le cas d’un réseau synchrone, les
neurones composant le réseau émette leur signal simultanèment à l’inverse d’un
réseau asynchrone ou un seul neurone émet un signal à la fois. Dans un réseau
asynchrone, l’ordonnancement entre les neurones peut être aléatoire ou non.
 Sa méthode d’apprentissage : comment le réseau apprend afin d’atteindre l’objectif
fixé ?

Dans la suite, nous allons étudier les deux types de réseaux de neurones principaux que sont
les perceptrons et les perceptrons multicouches (les réseaux booléens ou les réseaux
cellulaires ne seront pas étudiés ici). Nous terminerons par l’étude des réseaux de Kohonen,
un réseau de neurones couramment utilisé en classification.

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 20

PERCEPTRON

Un perceptron est un réseau de neurones monocouche caractérisé par la présence d’une

couche de neurones en entrée nommée « rétine » et d’une couche de neurones en sortie. Il
s’agit d’un réseau de type feed-forward. Les perceptrons sont principalement utilisés pour
des tâches de classification simple.

Figure 9 Perceptron

Pour réaliser l’apprentissage d’un perceptron, on débute en utilisant des valeurs de poids
synaptiques aléatoires. Après une phase de tests, ces poids sont modifiés afin de corriger les
sorties du réseau de neurones en fonction de ce que l’on attend de lui. Lorsqu’un neurone
de la couche de sortie est actif alors qu’on attend de lui qu’il soit inactif, les poids
synaptiques relatifs à ce neurone sont diminués d’une valeur donnée. Lorsqu’un neurone de
la couche de sortie est inactif alors qu’on attend de lui qu’il soit actif, les poids synaptiques
relatifs à ce neurone sont augmentés. Lorsque le réseau de neurones donne les résultats
attendus en sortie, on dit que le réseau a convergé. Il est à noter que le réseau ne converge
pas toujours. Lorsque les catégories utilisées pour la classification ne sont pas linéairement
séparable, la convergence ne peut être atteinte.

Ce type de perceptron peut par exemple être utilisé pour reconnaître des caractères sur un
support (lecture de code postal pour la poste…), identifier des visages, apprendre une
langue…

PERCEPTRON MULTICOUCHES

Le perceptron multicouches a été conçu pour être utilisé dans les applications où les
perceptrons monocouches divergent.

Figure 10 Perceptron multicouche

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 21

Un perceptron multicouches est un réseau de neurones caractérisé par la présence d’une

couche de neurones en entrée nommée « rétine », d’une couche de neurones intermédiaire
nommée « couche cachée » et d’une couche de neurones en sortie. Il s’agit d’un réseau de
type feed-forward.

Une particularité des perceptrons multicouches se situe au niveau du choix de la

configuration de la couche cachée et de l’étalonnage de ses poids synaptiques. Le nombre de
neurones présent sur la couche en entrée dépend des données en entrée tandis que le
nombre de réseaux en sortie dépend du nombre de classes utilisées pour la classification. Il
est par contre impossible de connaître le nombre de neurones à placer sur la couche cachée.
De nombreux tests sont donc souvent nécessaires pour découvrir une taille de couche
cachée adéquate. De la même manière, il est impossible de connaître le traitement à
appliquer aux poids synaptiques de la couche cachée pour faire converger le réseau. Des
algorithmes d’apprentissage ont donc été créés pour combler le manque de méthodes
d’apprentissage. L’algorithme de rétropropagation (il s’agit en réalité d’une heuristique)
notamment propose une méthode permettant de modifier les poids synaptiques d’un réseau
multicouches.

RÉSEAUX DE KOHONEN

Les réseaux de Kohonen (ou cartes auto-organisatrices (SOM)) s’inspirent de la constatation

biologique suivante : deux zones proches dans le cortex visuel correspondent à deux zones
proches dans la rétine.

Une carte (ou réseau) de Kohonen est composée de deux dimensions que sont la couche
compétitive et la couche d’entrée.

Figure 11 Carte de Kohonen

Les individus à classer sont représentés par une combinaison de valeurs placés sur la couche
d’entrée. Les neurones de la couche compétitive sont en concurrence et permettent, après
l’apprentissage, d’identifier la classe de chacun des individus. Lorsqu’un nouvel individu est
placé en entrée, un neurone vainqueur est désigné parmi ceux de la couche compétitive en
calculant une distance basée sur les pondérations entre les deux couches du réseau.

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 22

Lorsqu’un nouvel individu est présenté sur la couche d’entrée, chaque nœud de la couche
compétitive envoie en réponse une distance (euclidienne par exemple). La réponse d’un
nœud de coordonnées (i,j) sur la carte à un individu x composé des attributs x1, x2…, x n est
égale à :
n
dist ij ( x )=∑ (x k − pijk )²
k=1

Le nœud de la couche compétitive déclaré vainqueur est celui pour lequel la distance est
minimum. Une étape d’apprentissage démarre ensuite afin de mettre à jour les poids relatifs
aux nœuds voisins (le voisinage peut être 4-connexe, 6-connexe ou 8-connexe par exemple)
dans le but de les rapprocher du nœud vainqueur. Le rapprochement des voisins de la carte
permet de garantir, au terme de l’apprentissage, que deux individus similaires
correspondront à deux nœuds de la carte proches. Lorsque tous les individus ont été
présentés, l’apprentissage est terminé et les clusters apparaissent sur la carte.

CLASSIFICATION RELATIONNELLE

La classification relationnelle peut se résumer par la présentation de la méthode de

Condorcet. Cette méthode se base sur la définition d’un critère de similarité nommé critère
de Condorcet :

 Critère de Condorcet pour deux individus A et B : c(A,B)=(nombre de variables de

même valeur entre les deux individus)-(nombre de variables de valeurs différentes
entre les deux individus)
 Critère de Condorcet pour un individu A et un groupe C de n individus : c(A,C)=
i=n

∑ c (A ,C i )
i=1

L’algorithme de la méthode de Condorcet se déroule de la manière suivante :

 La constitution des groupes débute en plaçant chacun des individus A dans la classe C
pour laquelle le critère de Condorcet c(A,C) est maximum et supérieur à 0. Si pour
tous les groupes en présence, c(A,C) est inférieur à zéro, l’individu devient le premier
élément d’un nouveau groupe.
 Après avoir assigné tous les individus à un groupe, une série d’itérations est ensuite
lancer pour réaffecter, le cas échéant et selon les mêmes critères que
précédemment, les individus à un nouveau groupe plus proche de leurs
caractéristiques. On répète cette étape jusqu’à ce que le nombre de classes souhaité
soit atteint (ou jusqu’à un nombre d’itérations limites).

La méthode de Condorcet est très adaptée aux cas où les individus sont composés de
variables qualitatives. En revanche, elle présente plusieurs limites lorsque les variables sont
de type quantitatif. Le critère de Condorcet produit parfois des aberrations dans ce type de
cas. Si deux individus a et b ont une variable très proche et une autre très éloignée et si les
variables de l’individu a sont toutes les deux assez proches (moins proche que dans le cas de
la première variable avec b) d’un individu c, la méthode de Condorcet aura tendance à
grouper les individus a et b et pas les individus a et c.

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 23

MÉTHODES D’ASSOCIATION

Le but des méthodes d’association est de permettre d’identifier des corrélations entre les
valeurs des différentes variables. Des règles d’association de la forme « si antécédent, alors
conséquence » peuvent ainsi être mises au jour par les algorithmes d’association. Il est
important de voir que dans ce type de méthodes, aucune variable cible n’est défini (c’est ce
qui en fait une méthode descriptive et pas prédictive). Toutes les variables peuvent ainsi être
actrice d’une règle d’association découverte. La nécessité d’explorer l’ensemble des données
couplées à la nature souvent volumineuse des données utilisées pour ce type de techniques
(millions de tickets de caisse de supermarché, centaines de milliers de produits…) font qu’il
est nécessaire d’utiliser d’importants moyens calculatoires pour utiliser ces méthodes.
L’analyse des associations entre les valeurs des variables et également appelée l’analyse des
affinités (également célèbre sous le nom d’analyse du panier de la ménagère).

La plupart des algorithmes utilisés en recherche d’associations utilisent deux indicateurs :

 La confiance d’une règle : une règle d’association n’est pas valable pour tous les cas.
L’indice de confiance d’une règle permet donc de quantifier la capacité de
généralisation d’une règle donnée (si antécédent alors conséquence dans X% des
cas). Une règle d’association ayant une confiance faible est moins intéressante
qu’une règle ayant une confiance importante. La confiance notée C d’une règle P -> V
est donnée par les formules suivantes :

probabilité ( conditionet résultat)

C=
probabilité ( condition)

probabilité ( P , V )
C=
probabilité (P)

cardinalité (P=vrai ET V =vrai) cardinalité (P=vrai)

Où p ( P ,V ) = et p ( P )=
cardinalité totale cardinalité totale

La confiance d’une règle est donc donnée par la formule suivante:

cardinalité ( P=vrai ET V =vrai)

C=
cardinalité (P=vrai)

 Le support d’une règle : cette caractéristique permet de quantifier la proportion

d’individus concernés par la règle (les individus vérifiant les antécédents de la règle).
Le support noté S d’une règle P -> V est donné par la formule suivante :

S= probabilité (condition)

cardinalité (P=vrai)
S=
cardinalité totale

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 24

L’exemple suivant est issu de 10 tickets de caisse. Pour chacun d’eux, la présence ou non de
chips et de limonade a été notée :

Chips 1 1 1 0 0 0 1 0 1 0
Limonad 0 1 1 1 0 0 1 1 0 0
e

L’indice de confiance de la règle Chips->Limonade est égale à :

cardinalité (Chip s , Limonade) 3

C= = =60 %
cardinalité (Chips) 5

Dans 60% des cas où le client a acheté des Chips, il a également acheté de la limonade.

Le support de la règle Chips->Limonade est égale à :

cardinalité (Chips) 5
S= = =50 %
cardinalité totale 10

Seulement 50% des clients sont concernés par la règle.

A partir du support et de la confiance, trois indicateurs supplémentaires ont été créés :

 Un indicateur de réussite de la règle dans la population totale noté R:

R=S∗C

 L’indice de Lift : cet indicateur s’appuie sur le principe qu’une règle, pour être
intéressante, doit avoir une confiance supérieure à la probabilité absolue du résultat.
Si un résultat a 80% de chances d’arriver dans l’absolu, une règle où le même résultat
a 40% de chances de se produire (confiance de 40%) n’est pas intéressante. Cet
indicateur est noté L :
C
L=
probabilité (V )

Un lift jugé intéressant est donc supérieur à 1. Un indicateur équivalent nommé

progression brute peut être calculé en soustrayant la probabilité du résultat à la
confiance. Une règle pertinente a une progression brute supérieure à 0. Il est à noter
que lorsqu’une règle est jugée inutile car elle a un lift et une progression brute trop
faible, la règle inverse P->non(V) est nécessairement intéressante.

 La capacité de déploiement : cet indicateur permet de donner la proportion des

individus vérifiant les conditions mais ne satisfaisant pas encore le résultat. Cet
indicateur est noté D :

D= probabilité ( P , non ( V ) )

Pour finir cette présentation générale des techniques d’association, il est important de noter
que le nombre de règles possibles dans un ensemble est très important. Pour un problème
avec n variables, le nombre de règles possibles est donné par la formule n∗( 2( n−1 )−1 ) .
Devant ce nombre de possibilités important, des moyens peuvent être mis en place pour

LE2I – UMR CNRS 5158 – Université de Bourgogne

 Rapport Technique Jan. 12 Data Mining 25

limiter l’exploration à un certain type de règles. Par exemple, si la fréquence d’une variable
(égale au nombre de fois où la variable vaut vraie ou 1) est trop faible, la variable ne sera pas
utilisée comme condition d’une règle d’association. Un seuil de fréquence peut donc être
fixé pour les variables utilisées comme conditions d’une règle.

ALGORITHME A PRIORI

L’algorithme à priori est une méthode couramment utilisée pour la recherche d’associations.
Cet algorithme se compose des étapes suivantes :

 On fixe tout d’abord un seul de fréquence qui sera utilisé tout au long du
déroulement de l’algorithme.
 On calcule ensuite la fréquence de chaque combinaison de variables en démarrant
par les singletons (combinaisons comprenant une seule variable), puis les
combinaisons à deux variables, puis trois…
 Lors de chacune des étapes, on cherche à réduire le nombre de règles éligibles en
éliminant les combinaisons dont la fréquence est inférieure au seuil. Les
combinaisons de variables sont ensuite éliminées en cascade. Par exemple, si une
combinaison de deux variables n’a pas une fréquence suffisante, cette combinaison
ainsi que toutes les combinaisons contenant cette combinaison sont supprimées.

Il est à noter qu’un autre algorithme nommé « algorithme du GRI (induction de règles
généralisée) est également utilisé en recherche d’associations. Son fonctionnement est
similaire à celui de l’algorithme à priori.

Nous allons maintenant présenter le déroulement de l’algorithme à priori sur un exemple. Le

tableau ci-dessous contient les produits figurant sur une dizaine de tickets de caisse et leurs
répartitions dans ces derniers :

Numéro Limonade Chips Carottes Jambon Fromage Céréales

ticket/Produit
Ticket n°1 0 0 0 1 1 0
Ticket n°2 1 1 0 0 0 0
Ticket n°3 0 0 0 0 0 0
Ticket n°4 0 0 0 0 1 0
Ticket n°5 0 0 0 0 1 1
Ticket n°6 0 1 0 0 1 0
Ticket n°7 0 0 1 0 1 1
Ticket n°8 0 1 0 0 0 1
Ticket n°9 0 1 0 0 0 0
Ticket n°10 1 0 1 0 1 1

D’après la formule donnée précédemment, la présence de six variables entraîne un nombre

de règles d’associations possibles égale à 6∗( 25−1 )=186

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 26

On fixe un seuil de fréquence de 3. On considère donc que lorsque la fréquence est

inférieure à 30%, l’association n’est pas intéressante.

On poursuit ensuite en calculant la fréquence de chaque singleton :

Produit Limonade Chips Carottes Jambon Fromage Céréales

Fréquence 2 4 2 1 6 4
Proportion 20% 40% 20% 10% 60% 40%

Les singletons Limonade, Carottes et Jambon sont éliminés car leurs fréquences est
inférieure à 30%.

On calcule ensuite la fréquence pour chaque combinaison de deux variables. Il est à noter
que les singletons éliminés ne sont pas utilisés pour le tableau ci-dessous :

Produit/Produit Chips Fromage Céréales

Chips
Fromage 1
Céréales 1 3

Le seule couple ayant une fréquence suffisante est (Fromage, Céréales) avec une fréquence
de 30%. Il n’est pas utile d’essayer des combinaisons à trois variables car la fréquence serait
nécessairement inférieure à 30%.

A ce stade de l’algorithme, nous avons seulement obtenu une combinaison candidate pour
former des associations. A partir de cette combinaison, il est possible de définir deux règles
d’associations Fromage->Céréales et Céréales->Fromage.

Il nous faut maintenant déterminer les règles d’association réellement pertinentes. Pour
cela, nous calculons tout d’abord la confiance et le support de chacune d’elles :

cardinalité (Fromage ,Céréales) 3

C ( Fromage → Céréales )= = =50 %
cardinalité (Fromage) 6

cardinalité (Céréales , Fromage) 3

C ( Céréales → Fromage )= = =75 %
cardinalité (Céréales) 4

cardinalité (Fromage) 6
S ( Fromage →Céréales )= = =60 %
cardinalité totale 10
cardinalité (Céréales) 4
S ( Céréales → Fromage )= = =40 %
cardinalité totale 10

On calcule ensuite l’indicateur de réussite de la règle dans la population, le taux de lift et la

capacité de déploiement de chaque association :

R ( Fromage →Céréales )=50∗60=30 %

R¿

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 27

50
L ( Fromage → Céréales ) = =1.25
40
75
L ( Céréales→ Fromage ) = =1.25
60
D ( Fromage →Céréales )=30 %

D ( Céréales → Fromage )=10 %

On remarque tout d’abord que, très logiquement, les deux premiers indicateurs sont égaux
pour une règle et son inverse. Les deux règles d’association ci-dessus présente un indicateur
de réussite de la règle correcte (30%) et un lift supérieure à 1. Cette règle est donc à priori
éligible (c’est relatif). L’association Fromage->Céréales présente une meilleure capacité de
déploiement que son inverse. Il est donc plus intéressant de travailler avec l’association
Fromage->Céréales.

MÉTHODES D’ESTIMATION

Les techniques d’estimation, membre de la famille des méthodes prédictives, permettent

d’identifier des liens entre des prédicteurs et une variable cible puis d’utiliser ce lien pour
déduire des valeurs inconnues de la variable.

Parmi les techniques couramment utilisées en estimation, on trouve notamment les

méthodes de régression linéaire.

RÉGRESSION LINEAIRE

Les techniques de régression permettent de mettre en lien des prédicteurs avec des
variables cibles. On distingue deux types de régressions :

 La régression simple : une variable explicative est mise en relation avec une variable
cible.
 La régression multiple : plusieurs variables explicatives sont mises en relation avec
une variable cible.

RÉGRESSION LINÉAIRE SIMPLE

Soit des individus composés de deux variables X et Y, on souhaite définir un modèle

permettant de déduire la variable cible Y à partir de la variable X (prédicteur).

Pour aider la définition de ce modèle, il est possible de représenter la relation liant les
valeurs de X et les valeurs de Y pour les individus déjà connus à l’aide d’un nuage de points.
La technique de régression linéaire consiste ensuite à définir une droite approximant la
répartition des points du nuage : on dit que la droite « ajuste » le nuage. L’équation du
modèle (de la droite) est donnée par la formule suivante :

Yi=a∗Xi +b+ Ri

Où Yi est égale à la valeur de Y pour l’individu i, Xi est égale à la valeur de X pour l’individu i,
a et b sont les coefficients du modèle de régression linéaire et Ri est le résidu pour l’individu

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 28

i. L’équation du modèle est constitué d’une composante déterministe a∗Xi +b

correspondant à la droite sur la figure ci-dessous et d’une composante stochastique
(également appelée « résidu ») Ri correspondant à l’écart entre les points du graphique et le
modèle.

Figure 12 Régression linéaire simple

Après avoir défini le modèle, il est possible d’estimer la valeur Yi d’un individu en
connaissant la valeur Xi de ce même individu.

RÉGRESSION LINÉAIRE MULTIPLE

Soit des individus composés d’une variable Y et d’un ensemble de n variables Xk , k ∈[1 , n],
on souhaite définir un modèle permettant de déduire la variable cible Y à partir des variables
Xk.

L’équation du modèle (de la droite) est donnée par la formule suivante :

Yi=a 1∗X 1+ a 2∗X 2+ a3∗X 3+ a 4∗X 4+…+ an∗Xn+b+ Ri

A l’instar de la régression linéaire, l’équation du modèle est constitué d’une composante

déterministe a 1∗X 1+ a 2∗X 2+ a 3∗X 3+ a 4∗X 4+ …+an∗Xnet d’une composante
stochastique (également appelée « résidu ») Ri.

QUALIFICATION DE LA RÉGRESSION

Lors de la recherche du modèle de régression, le but est d’essayer de réduire au maximum la

distance séparant les individus de la droite de régression. Plusieurs indicateurs sont
disponibles pour guider la recherche dans ce sens :

 L’indicateur SRes défini comme la somme des résidus au carré.

 L’indicateur SReg défini comme la somme des carrés des différences entre les Yi
estimés et la moyenne des Y.
 L’indicateur SDom défini comme la somme des carrés des différences entre les Yi
d’origine et la moyenne des Y (Sdom=SRes+Sreg).

LE2I – UMR CNRS 5158 – Université de Bourgogne

Rapport Technique Jan. 12 Data Mining 29

MÉTHODES DE SEGMENTATION

Les méthodes de segmentation sont souvent utilisées en aval des méthodes de classification.
Comme nous avons pu le voir plus tôt dans ce dossier, les méthodes de classification
permettent de créer des groupes d’individus dans une population. Les techniques de
segmentation permettent quant à elle de déterminer quel groupe est le plus approprié (le
plus similaire) pour un nouvel individu. La variable cible à prédire ici est donc le groupe
d’appartenance du nouvel individu.

Parmi les techniques les plus utilisées en segmentation, on trouve notamment les arbres de
décisions, les réseaux de neurones ou encore l’algorithme des k plus proches voisins.

MÉTHODES DE PRÉVISION

Comme cela a été dit un peu plus tôt dans ce dossier, les méthodes utilisées en prévision
sont les mêmes que celles utilisées pour l’estimation et la segmentation.

CONCLUSION

En conclusion, nous avons pu étudier dans ce dossier un large panel de techniques de Data
Mining.

A FAIRE

RÉFÉRENCES

1. Jiawei Han et Micheline Kamber, 2006, Data Mining Concept and Techniques.
2. Massachusetts Institue of Technology, Data Mining: Lecture Notes,
[Link]
3. Bing Liu, Department of Computer Science, University of Illinois Chicago, Data Mining and Text Mining,
[Link]
4. Bertrand Liaudet, Cours de Data Mining, [Link]
5. Stéphane Tuffery, Paris Dauphine, Cours de Data Mining, [Link]
6. Ricco Rakotomalala, Cours de Data Mining,
[Link]
7. Joël Savelli, Université de Bourgogne, Cours de Data Mining.
8. Jia Li, Pennsylvania State University Cours de Data Mining,
[Link]
9. Jean-Marc Saglio, Ecole Nationale Supérieure des Télécommunications, Data Mining et Systèmes d’aide à
la décision,
[Link]
10. Philippe Leray et Alain Rakotomamonjy, INSA de Rouen, Cours de Data Mining,
[Link]
11. Thair Nu Phyu, 2009, Survey of Classification Techniques in Data Mining, International MultiConference of
Engineers and Computer Scientists.

LE2I – UMR CNRS 5158 – Université de Bourgogne