Dm Fouille Donnees + Etl Biblio

Module Master Recherche

Fouille de Données et Apprentissage Michèle Sebag, Antoine Cornuejols, Céline Rouveirol Laboratoire de Recherche en Informatique, Université Paris-Sud http://tao.lri.fr Orsay, 6 décembre 2004

MIT Technology Review, Jan-Feb 2001 Parmi les 10 technologies émergentes du 21e siècle,

Data Mining – Fouille de Données

Fouille de Données – Motivations L’idéal le siècle des connaissances La réalité des expertises spécialisées des pratiques à l’état de traces dans les données Le besoin la gestion humaine des connaissances ne passe pas à l’échelle L’opportunité les données sont accessibles

OBJECTIF restituer à l’expert des connaissances nouvelles, utiles, valides

Plan du Module • Introduction – Etude de cas, SKICAT – Pré-traitement des données

• Apprentissage statistique (Antoine Cornuéjols) • Apprentissage relationnel (Céline Rouveirol) • Optimisation – Evolution artificielle (MS)

Bonnes adresses • SIGKDD Explorations //www.acm.org/sigs/sigkdd/explorations

• CACM Special Issues on Data Mining (Nov 96): //www.digimine.com/usama/datamine/acm-contents.htm

• Kdnuggets: //www.kdnuggets.com/

• SIGMOD //www.acm.org/sigmod/

• VLDB //www.vldb.org

• SIGMOD Record: //www.acm.org/sigmod/record

• IEEE Data Engingeering Bulletin: //www.research.microsoft.com/research/db/debull

Plan de ce cours 1. Discussion des objectifs 2. Un exemple : SKICAT 3. Discussion des tâches 4. Pré-traitement

Introduction Fouille de données, une définition...

Fayyad et al. 1996

Automatic extraction of novel, useful and valid knowledge from large sets of data.

des connaissances

...faisant une large part à l’implicite...   nouvelles % au sens commun



utiles valides

pour qui un pb multi-critères

Domaines d’application

Domaine

But : Modélisation

Phénomènes physiques

modélisation et contrôle de process

Applications industrielles, sciences expérimentales, calcul numérique

+ confidentialité

Phénomènes sociaux Hôpitaux, Assurances, Banques, ...

+ dynamique rapide

Phénomènes individuels Consumer Relationship Management User Modelling

PASCAL : http://www.pascal-netwwork.org

Vocabulaires / Approches • Statistiques, identification de modèles • Analyse de données exploratoire • Réseaux neuronaux, Neural nets • Apprentissage supervisé, Supervised Machine Learning • Apprentissage relationel, Inductive Logic Programming • Fouille de données, Data Mining,

Découverte de pépites, nuggets

• Extraction de connaissances à partir de données, Knowledge Discovery from Databases

• Apprentissage statistique, Statistical learning • Algorithmes d’évolution, Evolutionary computation

Lignes de partage Etat d’esprit

No Free Lunch Thm. Wolpert & McReady, 1995

→ Pas de killer algorithm Input grandes dimensions (nb exemples ou nb attributs) flots (streaming) séquentiel, spatial, spatio-temporel structuré (DB relationnelles) semi-structuré (texte, Web, parole, SMS,...) hybride (eg séquences annotées) multi-media

Lignes de partage, 2 Output / critères paramétrique / hypothèses de forme connue (eg coeffs d’un polynome discriminant) non paramétrique : sélection de modèle combinatoire, NP-difficile (eg sélection d’attributs) Qualité d’approximation Rapidité d’exploitation Intelligibilité Stabilité Adaptativité Approches PASSE A L’ECHELLE Ascendant / Descendant Discrimination / Description INTERACTIVE

Inspirations Disciplines voisines

• Bases de Données

Passage à l’échelle ; au plus près des données

• Statistiques et analyse de données

Modèles prédéfinis ; évaluation

• Apprentissage artificiel Connaissances du domaine ; représentations complexes

• Optimisation • Interface Homme Machine • Calcul hautes performances

problèmes bien ou mal posés

Pas de solution finale : un dialogue

Données réparties, confidentialité

Dilemme H. Simon, 1958: In complex real-world situations, optimization becomes approximate optimization since the description of the real-world is radically simplified until reduced to a degree of complication that the decision maker can handle. Satisficing seeks simplification in a somewhat different direction, retaining more of the detail of the real-world situation, but settling for a satisfactory, rather than approximate-best, decision. Any-time algorithms http://anytime.cs.umass.edu/∼shlomo/

Data Mining: A KDD Process – Data mining: the core of knowledge discovery process.

Pattern Evaluation

Data Mining Task-relevant Data Data Warehouse

Selection

Data Cleaning Data Integration Databases

CMPT884, Introduction

12

Les étapes

1. Collecte des données

expert, DB

2. Nettoyage

stat, BK

3. Sélection

stat, BK

4. Extraction

Fouille

5. Visualisation

chm

6. Evaluation

stat, chm

7. Recherche de nouvelles données un processus itératif

expert, stat

Data Mining and Business Intelligence Increasing potential to support business decisions

Making Decisions Data Presentation Visualization Techniques Data Mining Information Discovery

End User

Business Analyst Data Analyst

Data Exploration Statistical Analysis, Querying and Reporting Data Warehouses / Data Marts OLAP, MDA Data Sources Paper, Files, Information Providers, Database Systems, OLTP CMPT884, Introduction

DBA

14

Données / Applications • Données propositionnelles • Données spatiales, temporelles

80% alarmes, gisements, accidents

• Données relationnelles

e.g. chimie

• Données semi-structurées

texte, Web

• Données multi-media

images, sons, films,..

En resumé Objectif

• Description • Prédiction • Agrégation

Qu’y a-t-il ds les données ? Décider sur un cas Prendre une décision globale

Ca dépend

• des attentes • des données initiales • des connaissances a priori. Encore un art, mais des lois se dégagent: Choix des biais pour un problème

Champ de la fouille de données Méthodes prédictives descriptives Recherche de clusters • Catégorisation X Prédiction discrète • Classification X Prédiction continue • Régression X • Détection de déviations X Recherche de motifs • Règles d’association X X • Patterns séquentiels X X Evaluation • Sélection d’attributs X X • Détection de tendances X X

Défis • Les données telles qu’elles sont : bruitées, incomplètes, confidentielles...

• Evaluation : quelle fonction d’intérêt ? • Différents types de connaissance visés pas d’approche universelle

• Un jeu à information incomplète : la connaissance du domaine. • Interaction : l’utilisateur au centre de la boucle validation, visualisation, oracle Existence de Benchmarks Question : Distance entre une preuve de principe et un outil

Défis, 2 Performances

• Passage à l’échelle • Calcul parallèle, distribué, incrémental... • Tout utiliser : semi-supervised learning, active learning • Le dilemme intelligibilité / efficacité • Intelligence analytique / diagrammatique

Bref historique • 1989 IJCAI Workshop on KDD Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991)

• 1991-1994 Workshops on KDD Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)

• International Conference on KDD, 1995-1998 Journal of Data Mining and Knowledge Discovery (1997)

• 1998— ACM SIGKDD conference • 2001— IEEE Conference ICDM

Partie 2 : Un exemple

Application scientifique

U. M. Fayyad, S. G. Djorgovski, and N. Weir. 1996

• Quel secteur du ciel regarder ? • Térabytes de données • Classification : étoiles, étoiles radiantes, galaxies, artefacts • Arbres de décision • Nb étoiles découvertes/nuit d’observation

Gain d’un facteur 40

http://www-aig.jpl.nasa.gov/public/mls/skicat/skicat_home.html

SKICAT, 2 Objectif final catalogue du ciel objets d’un ordre de grandeur moins brillants

Caltech, release 93 ≈ 40,000 volumes

Le problème trop nombreux candidats : artefacts ?

3 Téra bytes.

tera Terrorbytes

SKICAT, 3 L’opportunité existence de photos étiquetées existence de photos de mise au point label : contient O/N une étoile Variabilité entre géologistes pour un même géologiste Critère non pas la vérité absolue des performances de même ordre

floues.

Sample Volcanoes Category 1:

Category 2:

Category 3:

Category 4:

SKICAT, 4 Mise en œuvre apprentissage % photos de mise au point. pré-traitement

• brillance, surface, voisinage,... • extraction d’un échantillon • analyse en composantes principales • recodage

Volcanoes used for Training

Principal Components

Skicat, fin Impact Automate a task ≈ tens of man years. Provide a consistent and objective means for a comprehensive analysis of a scientifically important data set. Achievements 94% classification accuracy Classified objects: one magnitude fainter than previously 200% increase in size of data usable in analysis. Exceeds human ability in classifying faint objects, solution achieved automatically using learning algorithms on astronomer-provided training data.

Skicat, fin, 2 The classification rules produced by the inductive learning techniques form an objective, repeatable, examinable basis for classifying sky objects. Since the automated approach allows us to classify faint sky objects that cannot be processed visually or by traditional computational techniques, the content of the catalog produced from the survey is increased by three-fold, since the majority of objects in each image are faint. The training data for faint sky objects was obtained by examining a limited set of higher resolution CCD images covering minute portions of the survey. The learning algorithms are trained to predict the class (only obtainable by humans from higher resolution images) based on measurements from the survey. We thus classify objects that have to date not been classifiable by known techniques.

http://www-aig.jpl.nasa.gov/public/mls/skicat/skicat_home.html

A posteriori

Fayyad, nov. 2003 Personne ne connaissait les données mieux que les astronomes (30 ans).

Mais le concept (une fois résolu) fait intervenir 8 variables (attributs) parmi 40.

Exemple, domaine des assurances

• Détection de régularités certaines triviales: les jeunes ont plus d’accidents

• Segmentation des clients identification d’individus prototypes Clients des assurances sur la vie (Ace Insurance): single females aged 35-45 living in cities with incomes of 60-80k, married males aged 40-55 living in suburbs with incomes of 35-40k, divorced men over 65 with net worths over 2M. Any time you make broad, generalized statements about data, you’re liable to miss specific cases.

Exemple, domaine du CRM

• Détection de fraudes

Leo Carbonara et al., British Telecom

• Détection de “churners” • Détection des mauvais payeurs

Michel Jambu et al., France Telecom

Leçons Le but de la collecte Les données sont-elles collectées pour l’analyse ? Usage dérivé, reformulation des données. Passage à l’échelle efficacité quand les données ne tiennent pas en mémoire données (même aléatoires) de grande taille ⇒ contiennent des motifs réguliers. critères statistiques → comportement asymptotique besoin de mesures de qualité

Avec du recul Vision DM elevates the way we interact with DB like to see three buttons: What’s new What’s interesting Predict for me Myth DM pervasive; Large datawarehouses; Companies know how Integrated view Success means invisibility Maps findings to actions Integrating domain knowledge: no AI-hard: deep and narrow.

Technical challenges • How does the data grow ? Not iid. specially with time. • Explain how, when, why, a model fails. • Tuning: complex/understandable • Interestingness (common sense) • Scalability/integration DBMS / sampling / abstractions • Interaction / Visualisation • A theory of what we do