Chapitre1 DM Rebbah
Chapitre1 DM Rebbah
Chapitre1 DM Rebbah
Polycopié de Cours
Techniques de Fouille de
données
Présenté par :
M. REBBAH Mohammed
Présentation du Datamining
2 Application du Datamining
Les applications de Datamining sont diverses. Il est utilisé par les entreprises pour la
création des prols clients, ciblage des clients potentiels et nouveaux marchés. En nance,
il est exploité pour la minimisation des risques. En bioinformatique, pour l'analyse du
génome, mise au point de médicaments. En Internet, pour la détection des spams, e-
1
CHAPITRE 1. PRÉSENTATION DU DATAMINING
Il est très important de comprendre que le datamining n'est pas seulement le problème
de découverte de modèles dans un ensemble de donnée. Ce n'est qu'une seule étape dans
tout un processus suivi par les scientiques, les ingénieurs ou toute autre personne qui
cherche à extraire les Connaissances à Partir des Données (ECD) ou Knowledge Data
Discovery (KDD). En 1996, un groupe d'analystes dénit le datamining comme étant un
processus composé de cinq étapes sous le standard CRISP-DM (Cross-Industry Standard
Process for Data Mning ) comme schématisé ci-dessous [4].
Ce processus, composé de cinq étapes, n'est pas linéaire, on peut avoir besoin de reve-
nir à des étapes précédentes pour corriger ou ajouter des données. Par exemple, on peut
2 3. MISE EN ×UVRE D'UN PROJET DE DATAMINING
CHAPITRE 1. PRÉSENTATION DU DATAMINING
découvrir à l'étape d'exploration (5) de nouvelles données qui nécessitent d'être ajoutées
aux données initiales à l'étape de collection (2).
Décrivons maintenant ces étapes :
prend par exemple une partie importante (susante pour l'analyse) des données (70
à 80 %) à partir de laquelle on construit un modèle qui prédit les données futures.
Pour valider ce modèle, on le teste sur la partie restante (20 à 30 %) dont on connaît
le comportement.
3. Prétraitement : Les données collectées doivent être "préparées". Avant tout, elles
doivent être nettoyées puisqu'elles peuvent contenir plusieurs types d'anomalies : des
données peuvent être omises à cause des erreurs de frappe ou à causes des erreurs
dues au système lui-même, dans ce cas il faut remplacer ces données ou éliminer
complètement leurs enregistrements. Des données peuvent être incohérentes c.-à-d.
qui sortent des intervalles permis, on doit les écarter où les normaliser. Parfois on est
obligé à faire des transformations sur les données pour unier leur poids. Un exemple
de ces transformations est la normalisation des données qui consiste à la projection
des données dans un intervalle bien précis [0,1] ou [0,100] par exemple. Un autre
exemple est le lissage des données qui considère les échantillons très proches comme
étant le même échantillon. Le prétraitement comporte aussi la réduction des données
qui permet de réduire le nombre d'attributs pour accélérer les calculs et représenter les
données sous un format optimal pour l'exploration. Une méthode largement utilisée
dans ce contexte, est l'analyse en composantes principales (ACP). Une autre méthode
de réduction est celle de la sélection et la suppression des attributs dont l'importance
dans la caractérisation des données est faible, en mesurant leurs variances. On peut
même réduire le nombre de données utilisées par le Datamining en écartant les moins
importantes. Dans la majorité des cas, le prétraitement doit préparer des informations
globales sur les données pour les étapes qui suivent tel que la tendance centrale
des données (moyenne, médiane, mode), le maximum et le minimum, le rang, les
quartiles, la variance, ... etc. Plusieurs techniques de visualisation des données telles
que les courbes, les diagrammes, les graphes,... etc., peuvent aider à la sélection et le
nettoyage des données.
4. Estimation du modèle : Dans cette étape, on doit choisir la bonne technique pour
extraire les connaissances (exploration) des données. Des techniques telles que les
réseaux de neurones, les arbres de décision, les réseaux bayésiens, le clustering, etc.
sont utilisées. Généralement, l'implémentation se base sur plusieurs de ces techniques,
puis on choisit le bon résultat.
5. Interprétation du modèle et établissement des conclusions : généralement,
l'objectif du datamining est d'aider à la prise de décision en fournissant des modèles
compréhensibles aux utilisateurs. En eet, les utilisateurs ne demandent pas des pages
et des pages de chires, mais des interprétations des modèles obtenus. Les expériences
montrent que les modèles simples sont plus compréhensibles mais moins précis, alors
que ceux complexes sont plus précis mais diciles à interpréter.
Les données extraites ne sont pas nécessairement toutes exploitables par des techniques
de datamining. En eet, la plus part des techniques que nous utilisons ne traitent que des
tableaux de données numériques rangées sous forme lignes/colonnes. Certaines méthodes
sont plus contraignantes que d'autres. Elles peuvent par exemple exiger des données bi-
naires, comme c'est le cas des premières techniques de recherche de règles d'association.
Les données acquises depuis l'entrepôt peuvent être de types diérents. On peut y
trouver des textes de longueur variables, des images, des enregistrements quantitatifs ou
des séquences vidéo.
4 4. PRÉTRAITEMENT DES DONNÉES
CHAPITRE 1. PRÉSENTATION DU DATAMINING
5 Logiciels de datamining
Il existe de nombreux logiciels de Datamining qui sont faciles à installer. On trouve des
logiciels libres et/ou gratuits et d'autres commerciaux, on peut citer [7] :
TANAGRA : une grande partie de la panoplie des méthodes de Datamining in-
tégrées dans une seule structure. Le mode d'utilisation du logiciel est au standard
logiciels du domaine, avec notamment la dénition des opérations à réaliser sur les
données à l'aide d'une représentation visuelle. A voir absolument, la section didacti-
ciels de ce site. (site : http ://eric.univ-lyon2.fr/ ricco/tanagra/)
SIPINA : du même auteur que TANAGRA, il se distingue surtout par sa large
palette de méthodes d'induction par arbres de décision, avec la possibilité d'inter-
agir directement avec les modèles construits. Distribué depuis une dizaine d'années,
ce logiciel est très connu dans le monde de la recherche. (site : http ://eric.univ-
lyon2.fr/ ricco/sipina.html)
R-project : Un logiciel gratuit que l'on associe souvent aux statisticiens mais qui
en réalité convient très bien pour le Datamining. La bibliothèque des fonctions est
impressionnante et s'enrichit chaque jour grâce au système des packages. Seul in-
convénient, il fonctionne à l'aide d'un interpréteur de commandes. Il faut un peu de
pratique pour en tirer véritablement parti. Le lien indiqué nous dirige vers mon site de
cours de programmation sous R, vous y trouverez tous les liens idoines pour l'appren-
tissage du logiciel R. (site : http ://eric.univ-lyon2.fr/ ricco/cours/cours_programmation_R.html).
6 5. LOGICIELS DE DATAMINING
CHAPITRE 1. PRÉSENTATION DU DATAMINING
6 Etude de cas
Nous présentons maintenant l'exemple qui nous servira pour illustrer chaque étape du
processus. Cet exemple est issu du livre de P. Adriaans et D. Zantige [1].
Un éditeur vend 5 sortes de magazines : sport, voiture, maison, musique et BD. Il souhaite
mieux étudier ses clients pour découvrir de nouveaux marchés ou vendre plus de magazines
à ses clients habituels. Les questions qu'il se pose sont :
1. Combien de personnes ont pris un abonnement a un magazine de sport cette année ?
2. A-t-on vendu plus d'abonnements de magazines de sport cette année que l'année
dernière ?
3. Est-ce que les acheteurs de magazines de BD sont aussi amateurs de sport ?
4. Quelles sont les caractéristiques principales de mes lecteurs de magazines de voiture ?
5. Peut-on prévoir les pertes de clients et prévoir des mesures pour les diminuer ?
Les questions qui sont proposées sont de natures diérentes et mettent en jeu des processus
diérents. De simples requêtes SQL sont susantes pour répondre aux deux premières
questions. Les données recherchées dans ce cas ne sont que le résultat d'un calcul simple sur
un ou des groupes d'enregistrements. Ce qui distingue ces deux premières questions, c'est
la notion de temps et la comparaison. Pour établir cette comparaison, les données doivent
être présentes dans la base, ce qui n'est pas toujours le cas pour les bases opérationnelles.
Nous pouvons donc supposer que la requête 1 est réalisable sans technique particu-
lière à partir des données opérationnelles sous réserve d'indexations susantes des tables
concernées.
La requête 2 nécessite de conserver toutes les dates de souscription même pour les
abonnements résiliés. Nous pouvons imaginer aussi que l'utilisateur émettra une grande
variété de requêtes de ce type. Nous supposons alors que ces questions seront résolues à
l'aide d'outils de création de requêtes multidimensionnelles.
La question 3 est un exemple simplié de problème où l'on demande si les données
vérient une règle. La réponse pourrait se formuler par une valeur estimant la probabilité
que la règle soit vraie. Souvent, des outils statistiques sont utilisés. Cette question peut être
généralisée. On pourrait chercher des associations fréquentes entre acheteurs de magazine
6. ETUDE DE CAS 7
CHAPITRE 1. PRÉSENTATION DU DATAMINING
pour eectuer des actions promotionnelles. On pourrait également introduire une compo-
sante temporelle pour chercher si le fait d'être lecteur d'un magazine implique d'être, plus
tard, lecteur d'un autre magazine.
La question 4 est beaucoup plus ouverte. La problématique ici est de trouver une règle
et non plus de la vérier ou de l'utiliser. C'est pour ce type de question que l'on met en
÷uvre des outils de fouille de données.
La question 5 est également une question ouverte. Il faut pour la résoudre disposer
d'indicateurs qui pourraient sur notre exemple être : les durées d'abonnement, les délais
de paiement. Ce type de question a une forte composante temporelle et nécessite des
données historiques. Le processus de KDD utilise des outils de création de requêtes, des
outils statistiques et des outils de fouille de données. Là encore, nous nous apercevons
qu'une très grande partie des problèmes de décision se traite avec des outils simples. La
fouille de données quand elle est nécessaire, suit souvent une analyse des données simple
ou statistique.
Phase de préparation des données Dans notre exemple, nous avons identié quelques
objectifs précis, exprimés sous forme de questions. La préparation des données consiste dans
un premier temps à obtenir des données en accord avec les objectifs que l'on s'impose. Ces
données proviennent le plus souvent de bases de production ou d'entrepôts. Pour illustrer
cette phase, nous partons d'une liste des souscriptions d'abonnements avec cinq champs
(voir Tableau 1.1).
accompagner le chargement des données (par exemple sommer les ventes pour obtenir et
enregistrer un total par jour et non pas toutes les transactions).
Uniformisation d'échelle
Pour éviter de trop grandes dispersions dans les valeurs numériques, une homogénéisation
des échelles de valeurs est utile. Ne pas la réaliser peut pénaliser les outils d'analyse et de
visualisation et peut-être simplement remplir inutilement les supports de stockage.
Doublons, erreurs de saisie
Les doublons peuvent se révéler gênants parce qu'ils vont donner plus d'importance aux
valeurs répétées. Une erreur de saisie pourra à l'inverse occulter une répétition. Dans notre
exemple, les clients numéro 23134 et 23130 sont certainement un seul et même client,
malgré la légère diérence d'orthographe.
Intégrité de domaine
Un contrôle sur les domaines des valeurs permet de retrouver des valeurs aberrantes. Dans
notre exemple, la date de naissance du client 23130 (11/11/11) semble plutôt correspondre
à une erreur de saisie ou encore à une valeur par défaut en remplacement d'une valeur
manquante.
Informations manquantes
C'est le terme utilisé pour désigner le cas où des champs ne contiennent aucune donnée.
Parfois, il est intéressant de conserver ces enregistrements car l'absence d'information peut
être une information (ex : détection de fraudes). D'autre part, les valeurs contenues dans
les autres champs peuvent être utiles. Dans notre exemple, nous n'avons pas le type de
magazine pour le client 25312. Il sera écarté de notre ensemble. L'enregistrement du client
43241 sera conservé bien que l'adresse ne soit pas connue. Pré traitement des données
Attributs discrets
Les attributs discrets prennent leurs valeurs (souvent textuelles) dans un ensemble ni
donné. C'est le cas de la colonne magazine dans notre exemple qui peut prendre les valeurs
Sport, BD, Voiture, Maison, Musique. Deux représentations sont possibles pour ces don-
nées : une représentation verticale telle qu'elle est présentée en table 1 ou une représentation
horizontale ou éclatée (voit Tableau 1.4).
N0 Sport BD Voit. Mais. Musique Age Reven. Prop. Voit. Paris ? Dur'ee
abon.
23134 0 1 1 0 1 50 20 Oui Oui 1 4
31435 0 1 0 0 0 30 12 Non Oui 0 NULL
43342 1 0 0 0 0 37 9 Non Non 0 5
43241 1 0 0 0 0 53 15 Non Oui NULL 4
10 6. ETUDE DE CAS
CHAPITRE 1. PRÉSENTATION DU DATAMINING
7 Exercice
Un chef d'un grand groupe regroupant plusieurs compagnies situées dans plusieurs pays
souhaite réaliser une étude sur ses employés. Pour cela il a à sa disposition les données du
service des ressources humaines sur les employés.
Voici quelles sont les données à sa disposition et comment est organisée l'entreprise :
Pour chaque employé on mémorise dans le SI son nom, sa date de naissance, son sexe
et sa situation familiale (marié, concubinage, pacs, célibataire, veuf, divorcé). Lorsqu'il
est engagé dans le groupe chaque employé se voit attribuer un numéro d'employé, il est
aecté dans un service d'une compagnie du groupe. On enregistre sa date d'engagement.
Un employé est engagé avec un type de contrat particulier qui peut être un CDD (contrat à
durée déterminée) ou un CDI (contrat à durée indéterminée). Chaque employé est engagé
à un grade particulier qui caractérise son niveau d'avancement dans l'entreprise ; ce grade
peut évoluer au cours de sa carrière. Les grades vont de 1 à 25. Un employé devient cadre
lorsque son grade est supérieur à 20. Chaque année les employés peuvent recevoir une prime
de performance plus ou moins importante selon le travail qu'ils ont eectué.
Le décideur de ce groupe souhaite analyser un certain nombre de variables de l'entre-
prise :
Le nombre d'employés.
Le % d'employés (nombre d'employé considéré / nombre total d'employé).
Le salaire moyen
Le taux d'occupation moyen
Le nombre de jours d'absence
Les primes de performance moyennes
Il souhaite analyser ces variables en fonction de plusieurs paramètres : le numéro d'employé,
le type de contrat, le sexe, l'âge, le grade, la situation familiale, l'ancienneté.
Il souhaite pouvoir répondre aux questions suivantes :
Quels pays et quelles compagnies ont le plus d'employés, les plus haut salaires ?
Quel était le nombre d'employé de la compagnie X au premier trimestre de 2004 ?
Quels sont les mois de l'année où les employés sont les plus absents ?
Quel était le taux d'occupation moyen par service en 2003 ?
Quel est le prol (sexe, âge, grade) des employés les plus "dynamiques" ?
Y a-t-il un rapport entre l'ancienneté des employés et leur performance ?
8 Travaux pratiques
8. TRAVAUX PRATIQUES 13
CHAPITRE 1. PRÉSENTATION DU DATAMINING
14 8. TRAVAUX PRATIQUES
Bibliographie
[1] P. Adriaans and D. Zantinge. Data Mining. Addison-Wesley, dunod edition, 1996.
[2] Imielinski T. Agrawal R. Fast algorithms for mining association rules. 20th Int. Conf.
Very Large Data Bases, pages 487499, 1993.
[3] Imielinski T. et Swami A. N. Agrawal R. Mining association rules between sets of items
in large databases. ACM SIGMOD 1993, pages 207216, 1994.
[4] A. DJEFFAL. Cours fouille de données avancée. Technical report, Université Mohamed
Khider - Biskra, 2014.
[5] Ronen Feldman and James Sanger. Text Mining Handbook : Advanced Approaches in
Analyzing Unstructured Data. Cambridge University Press, New York, NY, USA., 2006.
[6] P. A FOUR. Des données au savoir : big data et data mining. Technical report, Rapport
technique, Lyon, 2013.
[7] R. RAKOTOMALALA. Support de cours data mining et data science.
http ://eric.univ-lyon2.fr/ ricco/cours/supports_data_mining.html, 2015.
[8] Claude TOUZET. Les réseaux de neurones articiels : Introduction au connexionnisme,
Cours, Exercices et Travaux pratiques. 1992.
15
BIBLIOGRAPHIE
16 BIBLIOGRAPHIE
Autres références
1. Les données, puissance du futur : http ://www.lemonde.fr/idees/article/2013/01/07/les-
donnees-puissance-du-futur_1813693_3232.html
2. Guillaume CALAS Études des principaux algorithmes de data mining, EPITA 2009
3. FAYYAD, U. and R. UTHURUSAMY, Data Mining and Knowledge Discovery in
Databases. Data Mining and Knowledge Discovery. 1996.
4. Ph. PREUX, Fouille de données Notes de cours, Université de Lille 3, 2011
5. Djamel Abdelkader ZIGHED & Ricco RAKOTOMALALA, Extraction des Connais-
sances à partir des Données (ECD) in Techniques de l'Ingénieur, 2002.
6. G. Holmes, A. Donkin and I.H. Witten, Weka : A machine learning workbench, Proc
Second Australia and New Zealand Conference on Intelligent Information Systems,
Brisbane, Australia, 1994
7. Adriaans P. and D. Zantinge (1996). Data Mining. Syllogic.
8. Bertrand LIAUDET, Cours de Data Mining, École d'ingénieurs, Septembre 2008
9. J. Ross Quinlan, "C4.5 : Programs for Machine Learning", Morgan Kaufmann Pu-
blishers, 1993.
10. Michael Berry and Gordon Lino, "Data Mining Techniques (For Marketing, Sales,
and Customer Support), John Wiley & Sons, 1997.
11. Sholom M. Weiss and Nitin Indurkhya, "Predictive Data Mining : A Practical Guide",
Morgan Kaufmann Publishers, 1998.
12. Alex Freitas and Simon Lavington, "Mining Very Large Databases with Parallel
Processing", Kluwer Academic Publishers, 1998.
13. K. Jain and R. C. Dubes, "Algorithms for Clustering Data", Prentice Hall, 1988.
14. V. Cherkassky and F. Mulier, "Learning From Data", John Wiley & Sons, 1998.
15. Usama Fayyad, "Mining Databases : Towards Algorithms for Knowledge Discovery",
Bulletin of the IEEE Computer Society Technical Committee on Data Engineering,
vol. 21, no. 1, March 1998.
16. Bertrand LIAUDET : COURS DE DATA MINING
17. Guillaume CALAS Études des principaux algorithmes de data mining
18. Ph. PREUX Fouille de données : Notes de cours Université de Lille 3, 2011.
19. D. Chessel, J. Thioulouse & A.B. Dufour Introduction à la classication hiérarchique,
université Lyon1, 2004
20. Maurice ROUX ALGORITHMES DE CLASSIFICATION Université Paul Cézanne
Marseille, France.
21. Camille Dutrey, Anne Peradotto, Chloé Clavel Analyse de forums de discussion pour
la relation clients : du Text Mining au Web Content Mining
17
AUTRES RÉFÉRENCES
22. Actes de l'atelier : Fouille du Web, des 6èmes journées francophones " Extraction et
Gestion des Connaissances "
23. Tellier, Introduction à la fouille de textes, Université de Paris 3 - Sorbonne Nouvelle
24. Adriaans P. and D. Zantinge (1996). Data Mining. Syllogic.
18 AUTRES RÉFÉRENCES