Dm Prez Pwt

Convergence de produits logiciels et d’information en Fouille de Données (Data Mining) et Extraction de Connaissance à partir de Bases de Données (Knowledge Discovery in Databases) Xavier Polanco URI-INIST-CNRS [email protected] Séminaire ADEST - 15 février 2000 X. Polanco

Séminaire ADEST - 15/02/2000

1

Plan ●

●

● ●

Distinction et concept: Fouille de données (DM) et Extraction de Connaissance à partir de BD (KDD) Fouille de textes (Text Mining) – Données factuelles versus bibliographiques et textuelles Applications et produits Références utiles

X. Polanco

Séminaire ADEST - 15/02/2000

2

Emergence du domaine ●

●

●

●

Workshops – 1991, 1993, 1994 International Conf. on KDD and DM – 1995, 1996, 1997, 1998, 1999 European Symposiums – 1997, 1998, 1999 Data Mining and Knowledge Discovery Journal (1997)

X. Polanco

Séminaire ADEST - 15/02/2000

3

SIGKDD est créé en 1999 ●

●

●

Special Interest Group Knowledge Discovery in Databases (1999) de l’Association for Computing Machinery (ACM) SIGMOD (Database Research), SIGIR (Information Retrieval), and SIGART (artificial intelligence) http://www.acm.org/sigkdd/charter.html

X. Polanco

Séminaire ADEST - 15/02/2000

4

Distinction et concept

1 X. Polanco

Séminaire ADEST - 15/02/2000

5

Expressions synonymes «Knowledge Discovery in Databases (KDD), also known as Data Mining, has emerged in the last decade ● «in reponse to the challenge of turning large and ubiquitous databases into knowledge that can be used in practice» ●

– (Second European Symposium, PKDD’98) X. Polanco

Séminaire ADEST - 15/02/2000

6

Tâche commune ●

A partir de données brutes (raw data), il s’agit de produire de la connaissance utile (useful knowledge) – «The notion of finding useful patterns (or nuggest of knowledge) in raw data has been given various names, including knowledge discovery in data bases, data mining, knowledge extraction, information discovery, information harvesting, data archaeology, and data pattern processing» ● (Fayyad et al., 1996, p. 3)

X. Polanco

Séminaire ADEST - 15/02/2000

7

Extraction de Connaissances à partir de Bases de Données (KDD) ●

●

●

Le terme knowledge discovery in databases, (KDD), est utilisé depuis 1989 pour signifier le processus d’extraire de la connaissance à partir des données, et pour souligner le «high-level» dans l’application de méthodes de fouille de données (data mining) – (Fayyad et al., 1996, p. 1-34)

X. Polanco

Séminaire ADEST - 15/02/2000

8

Distinction ●

●

Le terme «data mining», ou «fouille de données», a été habituellement utilisé par les statisticiens, les analystes de données, et la communauté de systèmes de gestion de l’information Tandis que KDD a été principalement utilisé par les chercheurs en intelligence artificielle et apprentissage automatique

X. Polanco

Séminaire ADEST - 15/02/2000

9

Pour signifier l’ensemble du processus ●

●

Le point de vue adopté (en Fayyad et al., 1996) est que «KDD» désigne l’ensemble du processus d’extraction de connaissances utiles à partir des données Tandis que «data mining» se réfère – à l’application d’algorithmes pour l’extraction de formes à partir des données, – sans considérer les étapes où il est question d’incorporer la connaissance du domaine et – de l’interprétation des résultats

X. Polanco

Séminaire ADEST - 15/02/2000

10

Concept ●

Le processus total de trouver et d’interpréter des formes (patterns) à partir des données, est reconnu sous le nom de ECBD (KDD) – un processus homme-machine interactif et itératif, basé sur des algorithmes de «data mining», – et qui suppose l’interprétation des formes générées par ces algorithmes

X. Polanco

Séminaire ADEST - 15/02/2000

11

Convergence de domaines ●

ECBD est le résultat de la convergence de recherches en :

●

– apprentissage automatique – reconnaissance de formes – bases de données – statistique – intelligence artificielle – visualisation de données

X. Polanco

●

Les systèmes de ECBD sont donc basés sur de – méthodes – algorithmes – techniques provenant de ces différents domaines

Séminaire ADEST - 15/02/2000

12

Etapes du processus ● ● ● ● ● ● ● ● ●

1. Compréhension du domaine d’application 2. Création du fichier cible (target data set) 3. Traitement des données brutes (data cleaning and preprocessing) 4. Réduction des données (data reduction and projection) 5. Définition des tâches de fouille de données 6. Choix des algorithmes appropriés de fouille de données 7. Fouille de données (data mining) 8. Interprétation des formes extraites (mined patterns) 9. Validation des connaissances extraites – (source : Fayyat et al., 1996, p. 1-34)

X. Polanco

Séminaire ADEST - 15/02/2000

13

Text-Mining : Fouille de textes et/ou données textuelles

2 X. Polanco

Séminaire ADEST - 15/02/2000

14

«Data Mining» et «Text Mining» ●

●

●

L’expression «Data Mining» est en général utilisée quand on travaille sur des données structurées dans des bases relationnelles On parle de «Text Mining» lorsqu’il s’agit de données textuelles (textual data) «Text Mining» est l’extraction d’information utile à partir des formes non manifestes (hidden patterns) dans des grands corpus de textes – (Feldman et al. 1998)

X. Polanco

Séminaire ADEST - 15/02/2000

15

Fouille de données textuelles ●

●

●

«Text Mining» est un nouveau domaine de recherche qui essaye de résoudre le problème de la surabondance d’information textuelle utilisant des techniques de :«data mining», «machine learning», «information retrieval», «natural-language understanding», «case-based reasoning», «statistics», and «knowledge management» le but est d’aider les personnes à gagner de la connaissance à partir de grandes quantités de textes semi-structurés ou non-structurés – (source : IJCAI’99 - Text Mining Workshop)

X. Polanco

Séminaire ADEST - 15/02/2000

16

Processus de la fouille de textes (IJCAI’99 Text Mining Workshop)

Les processus que la fouille de textes implique sont : ● Pré-traitements de la collection de documents – (p. ex. catégorisation des textes ou extraction de termes) ● ●

Stockage et Indexation des documents Analyse des représentations intermédiaires – (via p. ex. analyse de distribution, classification automatique (clustering), analyse de tendances, découverte de règles d’association)

●

Visualisation des résultats.

X. Polanco

Séminaire ADEST - 15/02/2000

17

Etapes de la fouille de textes ● ●

●

● ●

1. Sélection du corpus (data selection) 2. Extraction terminologique – extraction des termes – filtrage des termes extraits 3. Classification – automatique (clustering) – taxonomie (classement) 4. Visualisation des données : cartographie (graphes, ...) 5. Interprétation des résultats

X. Polanco

Séminaire ADEST - 15/02/2000

18

Au niveau inter-document Les opérations de «Text mining» ont pour objet la distribution de concepts au niveau inter-document ● Le but est de découvrir les concepts et leurs rapports tels qu’ils se trouvent dans la collection considérée comme un tout ●

– (Feldman et al. 1998) X. Polanco

Séminaire ADEST - 15/02/2000

19

Relations conceptuelles ●

Un instrument central de la fouille de données textuelles est l’analyse des relations conceptuelles (concept relationships) – Une collection d’éléments séparés (documents) – Chaque document représente un ensemble de concepts (termes)

X. Polanco

Séminaire ADEST - 15/02/2000

20

Analyse des relations conceptuelles ●

L’analyse des relations conceptuelles cherche à découvrir les rapports entre concepts, tels que nous pouvons les dégager de la totalité du corpus disponible

X. Polanco

Séminaire ADEST - 15/02/2000

21

Exemple Un nombre croissant de documents (articles, brevets) à propos de la société Y et le produit Z peut indiquer un changement d’orientation concernant les intérêts de la firme ● Il faut voir que l’information n’est pas fournie par un seul document isolé, mais par l’ensemble de la collection ●

X. Polanco

Séminaire ADEST - 15/02/2000

22

Marché et Produits

3 X. Polanco

Séminaire ADEST - 15/02/2000

23

Evaluation de l’ACM (1) ●

●

Le domaine de l’Extraction de Connaissances et de la Fouille de Données se trouve aujourd’hui au niveau où était 15 ans auparavant le domaine des bases de données Il y a plus d’une centaine de sociétés fournissant des outils de fouille de données, des applications, de conseil (consulting), de la formation et des séminaires, et même de «hardware» spécialisé

X. Polanco

Séminaire ADEST - 15/02/2000

24

Evaluation de l’ACM (2) ●

●

Le domaine se trouve au début de la phase d’adoption par le marché, et l’on prévoit que dans 3 à 5 ans, la phase de produits commerciaux passera à l’état de maturité Dans les prochains 10 ans, la technologie de la Fouille de Données et de l’Extraction de Connaissance à partir de Données deviendra une partie intégrante des technologies de l’information dans le monde des entreprises

X. Polanco

Séminaire ADEST - 15/02/2000

25

Produits et Sociétés ●

109 produits logiciels (12 européens) – http://www.kdnuggets.com/companies/products.html

●

67 sociétés consultant et formation – http://www.kdnuggets.com/companies/consulting.html – voir aussi «Yahoo List of Data Mining Companies»

X. Polanco

Séminaire ADEST - 15/02/2000

26

Exemples de produits d’information ●

IST – space : sur des données de l’observatoire Palomar (SKICAT), et sur des images des volcans de Venus (clustering)

– chimie : fouille de données sur des articles et des brevets en chimie (CLARIT, IBM)

– biologie : sur la séquence des protéines X. Polanco

Séminaire ADEST - 15/02/2000

27

Exemples de produits d’information ●

Santé – sur des données de santé (KEFIR), pour la détection de fraudes dans l’assurance maladie (arbres de décisions)

●

Marchés financiers – prédiction de risques en crédit (arbres de décisions)

●

Marketing – pour l’analyse de consommateurs (facturation, code barre)

X. Polanco

Séminaire ADEST - 15/02/2000

28

Références utiles

4 X. Polanco

Séminaire ADEST - 15/02/2000

29

Sites dans la Toile ●

Knowledge Discovery Nuggets Directory: Data Mining and Knowledge Discovery Ressources – http://www.kdnuggets.com/index_kdm.htm

●

ACM Special Interest Group (SIGKDD) home page – http://www.acm.org/sigkdd

●

Data Mining and Knowledge Discovery Journal – http://www.wkap.nl/jrnltoc.htm

●

Pour les deux derniers symposiums européens – http://www.sciences.univ-nantes.fr/pkdd98/ – http://lisp.vse.cz/pkdd99/

X. Polanco

Séminaire ADEST - 15/02/2000

30

Définitions et Terminologie ●

Data Mining Glossary – http://www.twocrows.com/glossary.htm

●

Glossary of Data Mining Terms – http://www.pilotsw.com/r_and_t/whtpaper/datamine/dmglos.htm

●

Glossary of Machine Learning and KDD Terms – http://orgwis.gmd.de/projects/explora/terms.html

●

Data Warehouse Terminology – http://www.credata.com/research/terminology.html

X. Polanco

Séminaire ADEST - 15/02/2000

31

Bibliographie ●

●

●

Fayyad et al., Advances in Knowledge Discovery and Data Maning. Menlo Park, Calif., AAAI Press / The MIT Press, 1996 (611 p.) IEEE Expert, 1996, vol. 11, n° 5, numéro consacré au «data mining» Y. Kodratoff «L’Extraction de Connaissances à partir de Données», Reveu Electronique sur l’Apprentissage par les Données, vol. 1, n° 1, juin 1997, p. 1-28 – http://chirouble.univ-lyon2.fr/gtra/numero1/Kodratoff_Mai97_fr.htm

X. Polanco

Séminaire ADEST - 15/02/2000

32

Bibliographie (suite) ●

●

Principles of Data Mining and Knowledge Discovery (J.M. Zytkow et M. Quafafou, eds). Berlin, Springer Verlag, 1998 (482 p.) – Sur «text mining», voir Feldman et al. in Principles (cidessus) – Sur «visualisation», voir Polanco et al. in Principles (ci-dessus) Carla E. Brodley et al. «Knowledge Discovery and Data Mining», American Scientist, vol. 87, January-February 1999, p. 54-61

X. Polanco

Séminaire ADEST - 15/02/2000

33

Bibliographie (suite) ●

IEEE Computer, Special Issue on Data Mining, vol. 32, n° 8, 1999

X. Polanco

Séminaire ADEST - 15/02/2000

34