Data Mining: Concepts et Techniques

Plan du Cours

Introduction
Rgles dassociation Classification et prdiction

Regroupement (Clustering)
Extraction de types complexes Applications du Datamining et tendances actuelles (gnomique)

Chapitre 1. Introduction

Motivation: Pourquoi le Data mining?

Ce quest le Data mining? Data Mining: Sur quels types de donnes? Fonctionnalits du Data mining Intrt des motifs (patterns)

Classification des systmes de Data mining

Problmes rencontrs
3

Motivation: Le besoin cre linvention

Problme de lexplosion de donnes

Les outils automatiques de collecte de donnes font que les Bases de Donnes (BDs) contiennent normment de donnes (Ex: La base de donnes des transactions dun super march)

Beaucoup de donnes mais peu de connaissances ! Solution: Data warehousing et data mining

Data warehousing et OLAP (On Line Analytical Processing)

Extraction de connaissances intressantes (rgles, rgularits,

patterns, contraintes) partir de donnes

Evolution des Bases de Donnes

1960s:

Collecte des donnes, cration des BDs, IMS et le modle rseau Modle et SGBDs relationnels, SQL, transactions, OLTP Modles de donnes et SGBDs avancs (relationnel tendu, OO, dductifs, etc.) et SGBDs ddis (spatial, gnomique, engineering, etc.) Data mining et data warehousing, BDs multimdia, BDs sur le WEB
5

1970s:

1980s:

1990s2000s:

Ce quest le Data Mining

Data mining :

Extraction dinformations intressantes (non triviales, implicites, pralablement inconnues et potentiellement utiles) partir de grandes bases de donnes. ECD (Extraction de Connaissances partir de Donnes) KDD (Knowledge Discovery from Databases) Analyse de donnes/patterns, business intelligence, fouille de donnes, etc

Autres appellations:

Pourquoi faire ? Applications potentielles

Analyse de donnes et aide la dcision

Analyse de march

Marketing cibl, gestion des relations client, analyse des achats des clients, ventes croises, segmentation du march

Analyse de risque Dtection de fraudes Text mining : news groups, emails, documents Web. Optimisation des requtes
7

Autres Applications

Analyse de march et management (1)

Les sources de donnes analyser ?

Transactions avec carte de crdit, carte de fidlit, sondages Trouver un modle pour regrouper les clients partageant les mmes caractristiques. Pour chaque groupe, adopter une dmarche marketing particulire Associations/co-relations entre ventes de produits Prdiction base sur ces associations

Marketing cibl

Analyse croise

Applications

Lanalyse dune BD de transactions dun supermarch permet dtudier le comportement des clients :

rorganiser les rayons Ajuster les promotions Cibler les mailings Support pour la recherche Prdire lvolution des actions Organismes de crdit (dresser des profils de clients)
9

En VPC, regrouper les clients selon certains critres :

Lanalyse de donnes mdicales :

Lanalyse de donnes financires :

Applications

Dtection de fraudes

en sant, services de cartes de crdit, tlcommunications, etc.

Utiliser les donnes historiques pour construire des modles de comportements frauduleux puis utiliser les techniques de datamining pour retrouver des instances similaires Assurances auto: dtecter les personnes qui collectionnent les accidents et les remboursements Blanchiment dargent: dtecter les transactions suspectes (US Treasury's Financial Crimes Enforcement Network)

Approche

Exemples

10

Applications

Astronomie

Le laboratoire JPL a dcouvert 22 quasars en utilisant les techniques de datamining IBM a appliqu des algorithmes de data mining pour rorganiser leurs sites WEB afin de faciliter la navigation. Amliorer le WEB marketing

Web

11

Datamining: Un processus dans lECD

Data mining: tape cl dans lextraction de connaissances
Donnes intressantes Data Warehouse Slection Evaluation de patterns

Data Mining

Nettoyage de donnes
Intgration Bases de donnes ou fichiers
12

Etapes du processus dECD

Comprendre le domaine dapplication Cration dun ensemble de donnes (slection) Nettoyage et pr-traitement des donnes (peut prendre 60% de leffort) Choix des fonctionnalits du data mining

classification, consolidation, rgression, association, clustering.

Choix de(s) lalgorithme(s) dextraction Datamining: Recherche des motifs (patterns) intressants Evaluation des Patterns et prsentation

visualisation, transformation, suppression des patterns redondants, etc.

Utilisation de la connaissance extraite

13

Architecture typique dun systme de Data mining

Interface graphique Evaluation des motifs

Module Data mining

BD ou Datawarehouse
Nettoyage & intgration Filtrage

Base de connaissances

BDs

Data Warehouse
14

Datamining: sur quels types de donnes

BDs relationnelles Data warehouses BDs transactionnelles BDs avances

BDs objet et objet-relationnelles BDs spatiales Sries temporelles BDs Textes et multimedia BDs Htrognes WWW

15

Fonctionnalits du Data Mining

On distingue deux grandes familles de tches
ralises en datamining

Description : consiste trouver les caractristiques gnrales relatives aux donnes fouilles Prdiction : consiste faire de linfrence partir des donnes actuelles pour prdire des volutions futures

16

Quels types de motifs extraire ? (1)

Description de concepts: Caractrisation et discrimination

Caractrisation : Il sagit de trouver des descriptions

concises et prcises de certains concepts. Ex: On a une

table dcrivant les clients dune entreprise.

Contraster (rgions sches vs humides)

17

Quels types de motifs extraire ? (2)

Association (corrlation et causalit)

age(X, 20..29) & revenu(X, 200..300KF) achte(X, PC) [support = 2%, confiance = 60%] contient(T, ordinateur) contient(T, logiciel) [1%, 75%]

18

Quels types de motifs extraire ? (3)

Classification et Prdiction

Trouver des modles (fonctions) qui dcrivent et distinguent des concepts pour de futures prdictions
Ex : classifier les pays en se basant sur leurs climats, les voitures selon leurs carburants

Prsentation: Arbres de dcision, rgles de classification, rseaux neuronaux

Prdiction: Prdire des valeurs inconnues Dmarche:

On prend un chantillon (jeu dessai) dans lequel chaque objet est associ une classe
Analyser chaque classe (son contenu) pour pouvoir ensuite affecter chaque objet nouveau une classe particulire
19

Quels types de motifs extraire ? (4)

Analyse de groupes (clusters)

Appele aussi classification non supervise Le regroupement est bas sur le principe: maximiser la similarit intra-groupe et la minimiser entre groupes distincts Le nom de chaque groupe est inconnu

20

Quels types de motifs extraire ? (5)

Analyse dexceptions

Les objets non conformes la tendance gnrale Une exception peut tre considre comme du bruit mais aussi comme indice de fraude

Analyse de tendances

Tendance et dviation: analyse de rgression

Extraction de squences squentiels, analyse de

priodicits

21

Est-ce que tous les motifs dcouverts sont utiles?

Un systme de data mining peut gnrer des milliers de motifs pas tous intressants. Cest quoi un motif intressant ? Mesure dintrt : Un motif est intressant sil est facilement comprhensible, a un degr de certitude, nouveau, peut servir

valider (ou invalider) une hypothse utilisateur

Mesure Objective vs. Subjective :

Objective: base sur des mesures statistiques : support, confiance, etc. Subjective: base sur le point de vue de lutilisateur sur les donnes, ex: le fait que cela soit inattendu, nouveaut, actionnabilit, etc.
22

Peut-on trouver tous et que les motifs intressants?

Trouver tous les patterns intressants: Compltude

Association vs. classification vs. regroupement Approches

Trouver que les patterns intressants: Optimisation

Dabord les trouver tous puis filtrer Ne gnrer que les motifs intressants

23

Data Mining: Confluence de plusieurs Disciplines

Technologie BD

Statistique

Apprentissage

Data Mining

Visualisation

Thorie de linformation

Autres Disciplines
24

Classification des systmes (1)

Fonctionnalit gnrale

Data mining descriptif Data mining prdictif

Diffrentes vues, diffrentes classifications

Types de BDs fouiller Types de connaissances dcouvrir

Types de techniques utilises

Application cible

25

Classification des systmes (2)

BD fouille

Relationnelle, transactionnelle, orient-objet, objectrelationnelle, active, spatiale, sries temporelles, texte, multimedia, htrognes, WWW, etc. Association, classification, clustering, tendance, analyse de dviation, etc. Multiples fonctions aux diffrents niveaux

Connaissance recherche

Techniques utilises

BD, data warehouse (OLAP), apprentissage, statistiques, visualisation, rseaux de neurones, etc.
tlcommunication, banque, analyse de fraude, ADN, finance, Web,
26

Applications

Problmatiques

Mthodologie et interaction

Diffrents types de connaissances extraire

Prise en compte des connaissances des experts

Langages de requte et data mining ad-hoc Expression et visualisation des rsultats Prise en compte des donnes incompltes ou avec bruit

valuation des motifs: notion dintrt

Efficacit des algorithmes Mthodes Parallles, distribues et incrmentales Relationnels, objets complexes, texte,
27

Performance et mise en chelle

Diversit des types de donnes

Rsum

Data mining: Dcouverte de motifs intressants partir de grandes quantits de donnes

Une volution naturelle de la technologie des SGBD, trs demande par diverses applications

Un processus dECD inclut les tapes: nettoyage, intgration, slection, transformation, data mining, valuation des patterns, prsentation de la connaissance
La fouille peut se faire sur diffrents types dentrepts de donnes

Fonctionnalits: discrimination, association, classification, clustering, analyse de tendances, etc.

Classification de SDM Problmatiques du data mining
28

Quelques systmes

Intelligent miner dIBM (coupl avec le SGBD DB2)

Entreprise miner de SAS

Classification, association, rgression, analyse de squences, regroupement

Mine set de Silicon graphics.

Multiples outils danalyse statistique, classification,

Clmentine de SPSS

Classification, association et divers outils statistiques. Trs puissant en terme de visualisation

En plus des fonctionnalits classiques, lutilisateur peut y rajouter ses propres algorithmes Il se distingue par le fait quil incorpore les fonctionnalits dOLAP
29

DBMiner de DBMiner technologie.

Bibliographie
Titre: Datamining : Concepts and techniques.
Auteurs : Jiawei Han & Micheline Kamber Editeur : Morgan Kaufmann 2000

30