08 FDON 1 - LIPNbennani/tmpc/FDON/08_FDON_1.pdf · Trevor Hastie, Robert Tibshirani, Jerome Friedman –The elements of statistical learning. Data mining, Inference and Prediction

08_FDON_1 Copyright KXEN 1

Data Mining1 - Introduction au data mining

Françoise Soulié [email protected]

Master MI2 Pro EID - Université Paris 13Data mining et Business IntelligenceFDONJanvier – Février 2008

2

Plan du cours

3

Références générales

Cours en ligne

1. Andrew Moore – Statistical Data Mining Tutorials. http://www.autonlab.org/tutorials/2. Carlos Guestrin – Machine Learning. School of Computer Science, Carnegie Mellon

University. http://www.cs.cmu.edu/~guestrin/Class/10701/schedule.html#basics3. Isabelle Guyon and André Elisseeff – Feature Extraction. ETH Zürich.

http://clopinet.com/isabelle/Projects/ETH/4. Tommi S. Jaakkola – Machine learning. MIT AI Lab.

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-867Machine-LearningFall2002/CourseHome/index.htm

5. Jeffrey D. Ullman – Data Mining. Computer Science. Stanford University. http://www.stanford.edu/class/cs345a/

6. Yann LeCun – Introduction to Machine Learning and Pattern Recognition. Courant Institute. New York University. http://www.cs.nyu.edu/~yann/2007s-V22-0480-002/schedule.html

7. Andreas Weigend – Data Mining and Electronic Business. Stanford University.http://www.weigend.com/Teaching/Stanford/

4

Références générales

Livres / articles

1. Christopher Bishop. Neural Networks for Pattern Recognition. Oxford University Press. 1995.

2. Gilbert Saporta – Probabilités, Analyse des données et statistique. Editions Technip. 1990.3. David Hand, Heikki Manila & Padhraic Smyth – Principles of Data Mining. MIT Press. 2001.

4. Trevor Hastie, Robert Tibshirani, Jerome Friedman – The elements of statistical learning. Data mining, Inference and Prediction. Springer Series in Statistics. 2001.

5. Sylvie Thiria, Y. Lechevallier, O. Gascuel, S. Canu Ed. Statistiques et méthodes neuronales. Dunod. 1997.

6. Vladimir Vapnik – Estimation of Dependences based on empirical data. Springer. Information sciences and Statistics. Reprint of 1982 Edition with afterword. 2006.

7. Vladimir Vapnik – Statistical Learning Theory, Wiley-Interscience, 1998.

8. Vladimir Vapnik – The Nature of Statistical Learning Theory, Springer-Verlag, 1999.9. Françoise Fogelman Soulié – CRM Analytique - L’apport du Data Mining. In «Apprentissage

Artificiel & Fouille de Données », Y. Bennani, E. Viennet eds, Revue des Nouvelles Technologies de l'Information. 2007. A paraître.

Ressources en ligne

1. Wikipedia http://en.wikipedia.org/wiki/Data_mining

2. Videos Machine learning. http://videolectures.net/

3. Site de références Data Mining. http://www.kdnuggets.com/

5

Agenda

1. Qu’est ce que le data mining

2. Les principaux types de modèles

3. Statistique & data mining

4. Le data mining dans l’industrie

5. Les nouvelles sources de données

6. Conclusion

6

Qu’est ce que le data mining

Un ensemble de méthodes permettant l’exploitation des données pour

� Décrire

� Comprendre

� Agir


7

Qu’est ce que le data mining

Le data mining repose sur des techniques nombreuses

� Statistiques

� Machine learning

� Intelligence Artificielle

� Reconnaissance des formes

� Informatique …

« The scary thing is that when you scratch the surface, you find you need all these new sciences that don't exist yet, combining machine learning, artificial intelligence and microeconomics with traditional

computer and data sciences »U. Fayyad (Yahoo !)

8

Données

9

Données

� Sources nombreuses ■ Production

■ Sources externes

� Types variés■ Structuré

■ Non structuré

• Texte

• Image

• Video

• Audio …

� Volumes croissants■ Le Web domine !

Russom, TDWI 2007

10

ResearchResearchResearchResearch

Yahoo! Data – A league of its own…

Terrabytes of Warehoused Data

25 49 94 100500

1,000

5,000

Am

azon

Kor

ea

Teleco

m

AT&T

Y! L

iveS

tor

Y! P

anam

a

Ware

hou

se

Walm

art

Y! M

ain

war

eho

use

GRAND CHALLENGE PROBLEMS OF DATA PROCESSING

TRAVEL, CREDIT CARD PROCESSING, STOCK EXCHANGE, RETAIL, INTERNET

Y! PROBLEM EXCEEDS OTHERS BY 2 ORDERS OF MAGNITUDE

Millions of Events Processed Per Day

50 120 2252,000

14,000

SABRE VISA NYSE Y! Panama Y! DataHighway

Fayyad, KDD 2007

11

Fonctions d’exploitation des données

� Requêtes■ Requête : données structurées

■ Search : données non structurées

� Reporting■ Présentation des données dans des tableaux de bord■ Statistiques descriptives

� Extraction d’information■ Data mining

• Modèles descriptifs : segments, associations

• Modèles prédictifs : scores, séries temporelles …

■ Text mining

• Catégorisation, résumé …

� Pour fournir des services à valeur ajoutée■ Campagnes marketing, e-commerce, publicités et mots clés, …

� Tout en gérant les risques■ Fraude, spam, intrusion, money laundering …

� Dans tous les secteurs industriels■ Banque & Assurance, Télécom, Grande distribution, Web, …

Informatique

Informatique décisionnelle

Data mining

Text mining

12

Le contexte

Le data mining est un domaine où

� La recherche est active depuis très longtemps■ Recherche universitaire

• Communauté du Machine Learning

■ Labos mixtes

• Google, Microsoft et Sun créent le RAD Lab de l’UC de Berkeley– Reliable, Adaptive and Distributed Systems, ou RAD

– Financement de 7,5 millions de dollars

� L’exploitation industrielle explose■ Les entreprises de pointe (Microsoft, Yahoo !, Google, Amazon …)

• Yahoo ! « manages many of the largest and richest data repositories in the world, and researchers mine insights from these giant collections »

■ Les banques et les opérateurs téléphoniques ont tous mis en œuvre

• Des bases de données / data warehouses pour recueillir les données clients

• Des méthodes data mining pour exploiter ces données– Score d’octroi de crédit, ciblage des campagnes …

■ Les industries de production manipulent

• Des gros volumes de données

• Utilisent la méthodologie SixSigma, qui s’appuie sur données et statistiques

L’exploitation industrielle impose des contraintes particulières


13

Applications

� Campagnes marketing

14

Applications

� Crédit

Ce crédit est refusé

15

Applications

� Recommandations

Recommandation

Ratings

Recommandation

16

Applications

� Bannières & Mots clés

Requête

Résultats Bannières

Research AreasResearch Areas

Paid SearchPaid SearchRelevanceRelevance

•• Relevance verificationRelevance verification•• Relevance measurementRelevance measurement

Keywords TechnologiesKeywords Technologies•• CategorizationCategorization•• Mutation/Group detectionMutation/Group detection•• ForecastingForecasting•• ……

Content AdsContent AdsText MiningText MiningConcept hierarchyConcept hierarchyTerm extractionTerm extractionSensitive Content detectionSensitive Content detection……

Behavior TargetingBehavior TargetingAge and Gender predictionAge and Gender predictionOnline Commercial Intention Online Commercial Intention detectiondetectionAudience SegmentationAudience SegmentationSocial networkingSocial networking……

Emerging MarketEmerging MarketVideo adsVideo adsLarge displayLarge displayLocal adsLocal adsMobile adsMobile ads……

http://adlab.msn.com/

18

Applications

Sécurité

� Détection de la fraude http://mmdss.jrc.it/Presentations/Docs/MMDSS_Hand_PUBLIC.pdf� « Intelligence » http://mmdss.jrc.it/Presentations/Docs/MMDSS_Best.pdf

http://press.jrc.it/NewsBrief/clusteredition/en/latest.html


19

Agenda






6. Conclusion

20

Qu’est ce qu’un modèle ?

« Data mining is the analysis of (often large) observational data sets to find unsuspected relationships and to summarize the data in novel ways that are both understandable and useful to the data owner »

Hand, 2001

Un modèle est l’objet mathématique qui décrit ces relations

� On peut considérer un modèle comme un processus qui fournit un résultat sur la base des informations qu’on lui présente

� Les données d’entrée peuvent être nombreuses

� Elles proviennent, en général, d’une base de données

21

Les différents types de variables

� Variables quantitativesVariables sur lesquelles les opérations arithmétiques ont un sens■ Variables numériques réelles

• 0,3256

■ Variables discrètes

• 1, 2, 27

� Variables qualitatives

Variables dont les valeurs sont des catégories ou des modalités■ Variables ordinales (numérique ou texte) dont l’ordre a un sens, mais pas les

opérations arithmétiques

• A, B, C

• Un peu, beaucoup, passionnément

• Dates : 22112007, 23 novembre 2007

■ Variables nominales dont l’ordre n’a pas de sens

• Numérique : variables numériques discrètes– Codes postaux (75 013, 92 125 …)

– Binaire : 0 ou 1

• Texte : chaînes de caractères sans ordre significatif– CC –carte crédit, CH –chèque, RA –retrait automatique

– Bleu, blanc, rouge

22

Les principaux types de modèles

Il y a deux grandes familles de modèles

Les modèles descriptifs

� Description■ Représentation des données dans des graphiques synthétiques

� Visualisation■ Représenter visuellement les données

� Clustering / Segmentation■ Déterminer des regroupements des items

� Associations■ Déterminer les groupes d’items qui se présentent souvent ensemble

Les modèles prédictifs

� Régression■ Prévoir une valeur continue

� Classification■ Prévoir dans laquelle des classes pré-définies se trouve un item

23


Modèles descriptifs

� Visualisation

24


Modèles descriptifs

� Le modèle est une description / simplification du phénomène■ Statistiques descriptives

■ Importance des variables

■ Segments

■ Associations …


25


Modèles prédictifs

� Classification ■ La cible est nominale

• Binaire : il y a 2 classes (0 et 1)

• Multi-modale : il y a n classes (1, 2, …, n)

26


Modèles prédictifs

� Régression■ Le modèle donne une estimation de la classe ou de la valeur

• La cible est continue– Score

– Série temporelle …

■ Des modèles différents donnent des prévisions différentes

• Quelle est la “bonne” prévision ?

• Existe-t-il un moyen de garantir qu’on obtient une bonne prévision ?

PasséFutur

Données Modèle

27

Agenda






6. Conclusion

28

Historique

� 1900-1990 : statistiques■ Fisher, Cramer, Bayes, Kolmogorov-Smirnoff …

� 1985-1995 : réseaux de neurones■ En 1982, réseau de Hopfield

■ En 1985-86 : Perceptron Multi-couche(Rumelhart, LeCun)

■ En 1984 : Cartes Topologiques & Learning Vector Quantization (Kohonen)

� En 1991 Vapnik quitte la Russie et rejoint les Bell Labs■ Sa « Statistical Learning Theory » est appliquée aux réseaux de neurones

■ Il développe les SVM

� 1992-2007 : le data mining émerge des divers domaines ■ Statistique

■ Machine learning

■ Intelligence Artificielle

■ Reconnaissance des Formes

■ Informatique (bases de données) …

� Les fondations théoriques du data mining proviennent essentiellement des statistiques

29

Historique (personnel)

� En 1985 nous commençons à travailler sur les réseaux de neurones■ Gradient Back Propagation

� En 1991, nous mettions au point des techniques opérationnelles ■ Early stopping, Optimal Brain Damage, Weight Decay, TDNN, LVQ …

� En février 1991, start-up Mimetics■ Réseaux de neurones, OCR

■ Échec après rachat par Adaptive Solutions

� En avril 1991 (Snowbird Learning Workshop)■ Exposé de Vapnik

■ Un « beau » cadre mathématique

■ Très opérationnel

• Nos « trucs » MLP sont expliqués

� En 1998, start-up KXEN■ Le software de data mining de KXEN est basé sur la théorie de Vapnik

■ La société croît régulièrement

■ http://www.kxen.com/

30

Statistiques

Le domaine des statistiques est très vaste. Il comprend (notamment ! )Voir Saporta

La statistique exploratoire

� Statistiques descriptives■ Représentations graphiques

■ Représentations numériques

• Moyenne, variance, médiane …

� Statistiques croisées■ Représentations graphiques

■ Représentations numériques

• Coefficient de corrélation

� Descriptions multi-dimensionnelles■ Analyse en Composantes Principales

• Variables numériques

■ Analyse factorielle • Variables catégoriques

http://fr.wikipedia.org/wiki/Analyse_en_composantes_principaleshttp://rb.ec-lille.fr/l/Analyse_de_donnees/Methodologie_L_AFC_pour_les_nuls.pdf


31

Statistiques

La statistique inférentielle

� L’estimation■ Biais

■ Maximum de vraisemblance

■ Intervalles de confiance

� Les tests■ Tests d’hypothèses

■ Tests d’ajustement

■ Tests de comparaison d’échantillons

� La régression

� L’analyse discriminante

La statistique mathématique

� La théorie des probabilités

� Les divers théorèmes de statistiques

� La « Statistical Learning Theory » de V. Vapnik32

Statistique & data mining

Ce que disent les statisticiens

� « Le Data Mining est une discipline née en dehors de la statistique, dans la communauté des bases de données et de l’IA dans le but de valoriser les bases de données. Le Data Mining offre des perspectives nouvelles pour la statistique et répond au défi du traitement des gigabasesde données. »

G. Saporta� « La statistique … est attachée à la notion de preuve pour valider une

méthode … En revanche, … le data mining… vise à l’efficacité opérationnelle en admettant une approche empirique. … Une caricature de la démarche conduit … [en statistique] à des méthodes théoriquement performantes mais inutilisables … ne répondant pas aux besoins des praticiens … [edn data mining] on assiste à un foisonnement de … variantes incrémentales des

algorithmes censées en améliorer la vitesse ou la précision » P. Besse

� « We are ceding some of the most interesting of current statistical problems to computer scientists and engineers allied to the machine learning area …Young statisticians need to learn about algorithmic modeling and how it

applies to a large variety of statistical problems » L. Breiman in Bolton & Hand

� « Data mining is more than statistics writ large » D. Hand

� « Statistics is the science of learning from data » J. Kettenring in Saporta

� « Data mining is the set of engineering techniques for learning from data »Moi

33

Agenda






6. Conclusion

34

Le data mining … hier

Andrew Moore, KDD’06

35

Le data mining … aujourd’hui

Andrew Moore, KDD’06

36

Le data mining … aujourd’hui ?

Deux jours après

5 000 colonnes


37

Le data mining … aujourd’hui

� Ce qu’on voit déjà■ Masses de données

• Milliers de variables, 10-100 millions de lignes

■ Beaucoup de modèles

• 100 – 1000 modèles / an / semaine / jour

■ Ressources limitées

• Quelques utilisateurs (10 – 30 ?)

… généralement dans un secteur de l’entreprise■ Marketing, Risque …

� Ce qu’on commence à voir■ Des initiatives à l’échelle de l’entreprise

• Conception, production, vente, maintenance, service client, marketing

■ Des ressources à l’échelle de l’entreprise

• Beaucoup d’utilisateurs (100 – 1000 )

… ce qui va donner une nouvelle dimension au data mining

38

Le contexte industriel

� Des sources de données nombreuses ■ Volume des données : double chaque année

■ Sources : hétérogènes, incohérentes

� Le nombre de décisions prises augmente sans cesse■ Qualité des décisions prises : dépend des analyses menées

■ Coût / bénéfice d’une seule décision : peut être très grand

■ Décision en temps réel « au fil de l’eau » : nécessaire

� Le nombre de modèles à produire augmente aussi■ Capacité à produire des modèles : réduite

■ Disponibilité des experts : goulet d’étranglement

� Des utilisateurs – et des besoins – variés■ Utilisateurs : veulent répondre par eux-mêmes à leurs questions, sans dépendre

d’experts ni être obligés d’en devenir eux-mêmes

� Le process data mining doit être intégré au SI■ Méthodologie de mise en œuvre : globale

■ Industrialisation / déploiement : facile

■ Contrôle et suivi des performances : automatisé

39


Ce qui est central : les algorithmes & la théorie ?

� Non■ Dans le monde industriel : $$$$

� Oui ■ Il faut s’appuyer sur une théorie solide pour

obtenir $$$

■ À condition qu’elle soit opérationnelle !

20


Researcher view

Algorithms andTheory

Database

Systems

22


Practitioner view

Systems and integration

Database

Algorithms

Customer

23


Business view

Systems

Database

Algorithms

Customer

$$$’s

Fayyad, KDD 2007

40


� Le data mining fournit des moyens de définir des actions■ Un modèle non utilisé pour une action n’est qu’un coût inutile

� Le volume de données croît exponentiellement ■ Le nombre de modèles doit suivre

Herschel, Gartner 2006

41


Le Data mining est utilisé surtout dans des applications CRM

� Les utilisateurs ne sont pas des data minersPour être productifs, il faut être simple

■ Les utilisateurs comprennent les modèles

■ Les utilisateurs produisent les modèles

Eckerson, TDWI, 2007

21


Business

Challenges

Conversion

Retention

Acquisition

Loyalty

Average Order

TechnologiesSpecialists

Statisticians

DBAs

Consultants

Data Mining PhDsSegmentation

Logistic

Regressions

Genetic

Algorithms

Decision

Trees

Chaid

CART

OLAP

Bayesian

Networks

Neural

Networks

Business Results Gap

Business

Challenges

Conversion

Retention

Acquisition

Loyalty

Average Order

Technical Tools

Business users are unable to apply the power of

existing data mining tools to achieve results

Fayyad, KDD 2007

42


Le processus data mining comprend 4 étapes


43


44


Le processus data mining n’est pas très efficace

� On n’utilise pas toutes les variables

� La manipulation des données est très lourde

� La construction d’un modèle prend très longtemps■ Des semaines, voire des mois

Time to build a model

Project breakdown

Number of variables used

Eckerson, TDWI, 2007

45


1. Intégration

Le Data mining n’est pas LA solution, mais une partie

2. Productivité

Le Data mining doit apporter de la valeur à l’entreprise

3. Scalabilité

Le Data mining doit pouvoir produire de nombreux modèles sur de grands volumes de données

4. Automatisation

Le Data mining doit être aussi automatique que possible

46

Le Data mining fait partie du Système d’Information

CRM AnalytiqueBack-Office

Base deDonnéesClients

Data Mining

ERP

BasesLegacy

CRMOpérationnel

Marketing

Ventes

ServiceClients

Reporting Olap

Canaux decontactClient

ClientsSMSCourrier E-mail Question-

nairesFax InternetTéléphone

Fichiersexternes

Production

Fabrication

Conditionnement

Informatique

SAV

Distribution

R&D

Expédition

47

Agenda






6. Conclusion

48

Les nouvelles sources de données

� De plus en plus de données non structurées■ Texte

■ Mais aussi video, audio, parole, …

� L’arrivée des réseaux sociaux …

Russom, TDWI, 2007

Provost, NATO 2007

http://mmdss.jrc.it/index.html


49

Agenda






6. Conclusion

50

Un exemple à méditer

On construit un modèle pour expliquer l’index S&P 500

� Avec 3 variables1. La production de beurre au Bangladesh & aux USA

2. La production de fromage aux USA

3. La population de moutons au Bangladesh & aux USA

Les modèles obtenus sont quasiment « parfaits »

Leinweber

Variable 1R2=0,75

Variables 1 & 2R2=0,95

Variables 1, 2 & 3R2=0,99

51


Un modèle polynomial

� De degré 9 pour la période 1983-92• .25*1016-.26*1013x+.12*1010x2-

320000.x3+56.x4-.0064x5+.49*10-6x6-.24*10-10x7+.69*10-15x8-.88*10-20x9

■ Le modèle obtenu est absolument « parfait » : 100%

� À l’arrivée de la donnée 1993, un polynôme de degré 10■ .77*1017-.88*1014x+.45*1011x2-

.14*108x3+2700.x4-.37x5

+.000035x6-.23*10-8x7+.99*10-13x8-.25*10-17x9+.28*10-22x10

■ Le modèle obtenu est absolument « parfait » : 100%

Leinweber

52


Un modèle polynomial

� Que se passe-t-il ?■ In-sample: 100% parfait

■ Out-of-sample: 100% non-sens

Leinweber

Polynôme de degree 9

Polynôme de degree 10

53

References

� Usama Fayyad, A Data Miner’s Story – Getting to Know the Grand Challenges, KDD’07. http://videolectures.net/kdd07_fayyad_dms/

� Usama Fayyad, From Data Mining to Data Strategy -- towards the New Sciences Underlying the Internet, adma'06 http://www.itee.uq.edu.au/~adma06/usama-ADMA-Xian-China-08-06.pdf

� Gareth Herschel, Gartner Customer Relationship Management Summit 2006.� Andrew Moore, New Cached-Sufficient Statistics Algorithms for quickly answering

statistical questions, KDD’07, http://www.sigkdd.org/kdd/2006/docs/presentations/andrewMoore06Keynote.pdf

� Wayne W. Eckerson, Predictive Analytics. Extending the Value of Your Data Warehousing Investment. TDWI Best Practices Report. Q1 2007. https://www.tdwi.org/Publications/WhatWorks/display.aspx?id=8452

� Philip Russom, BI Search & Text Analytics. TDWI Best Practices Report. Q2-2007. https://www.tdwi.org/Publications/WhatWorks/display.aspx?id=8449

� Besse, P.; Le Gall, C.; Raimbault, N.; Sarpy, S. Data Mining & Statistique, avec discussion, Journal de la Société Française de Statistique, 142, 5-35 (2001). http://www.lsp.ups-tlse.fr/Besse/prepublications.html

� David J. Hand : Why data mining is more than statistics writ large. Institut International de Statistique. http://www.stat.fi/isi99/proceedings.html

� Gilbert Saporta : Data mining: une nouvelle façon de faire de la statistique ? Exposéhttp://cedric.cnam.fr/~saporta/DM.pdf

� David J. Leinweber, Stupide data miner tricks : overfitting the S&P 500.http://nerdsonwallstreet.typepad.com/my_weblog/files/dataminejune_2000.pdf

� Richard J. Bolton and David J. Hand : Statistical Fraud Detection: A Review. Statistical Science. Vol. 17, No. 3, 235–255, (2002)

� Usama Fayyad, A Data Miner’s Story – Getting to Know the Grand Challenges, KDD’07. http://videolectures.net/kdd07_fayyad_dms/

� Usama Fayyad, From Data Mining to Data Strategy -- towards the New Sciences Underlying the Internet, adma'06 http://www.itee.uq.edu.au/~adma06/usama-ADMA-Xian-China-08-06.pdf

� Gareth Herschel, Gartner Customer Relationship Management Summit 2006.� Andrew Moore, New Cached-Sufficient Statistics Algorithms for quickly answering

statistical questions, KDD’07, http://www.sigkdd.org/kdd/2006/docs/presentations/andrewMoore06Keynote.pdf

� Wayne W. Eckerson, Predictive Analytics. Extending the Value of Your Data Warehousing Investment. TDWI Best Practices Report. Q1 2007. https://www.tdwi.org/Publications/WhatWorks/display.aspx?id=8452

� Philip Russom, BI Search & Text Analytics. TDWI Best Practices Report. Q2-2007. https://www.tdwi.org/Publications/WhatWorks/display.aspx?id=8449

� Besse, P.; Le Gall, C.; Raimbault, N.; Sarpy, S. Data Mining & Statistique, avec discussion, Journal de la Société Française de Statistique, 142, 5-35 (2001). http://www.lsp.ups-tlse.fr/Besse/prepublications.html

� David J. Hand : Why data mining is more than statistics writ large. Institut International de Statistique. http://www.stat.fi/isi99/proceedings.html

� Gilbert Saporta : Data mining: une nouvelle façon de faire de la statistique ? Exposéhttp://cedric.cnam.fr/~saporta/DM.pdf

� David J. Leinweber, Stupide data miner tricks : overfitting the S&P 500.http://nerdsonwallstreet.typepad.com/my_weblog/files/dataminejune_2000.pdf

� Richard J. Bolton and David J. Hand : Statistical Fraud Detection: A Review. Statistical Science. Vol. 17, No. 3, 235–255, (2002)

Documents

08 FDON 1 - LIPNbennani/tmpc/FDON/08_FDON_1.pdf · Trevor Hastie, Robert Tibshirani, Jerome Friedman –The elements of statistical learning. Data mining, Inference and Prediction