Découverte de connaissances à partir des bases de données Flashcards
Qu’est-ce que la découverte de connaissances?
We are drowning in data, but starving for knowledge
Necessity is the mother of invention
Découverte de connaissances à partir des BD (DCBD)
- Recherche de la structure cachée des données sous forme de motifs (patterns), associations, classes/concepts
- Objectifs
* Aide à la prise de décision pour une meilleure gestion stratégique et opérationnelle
* Meilleure connaissance de la sémantique des données
Découverte de connaissances à partir des BD
- Processus non trivial d’identification, à partir des données, de motifs
* Valides (pour de nouvelles données avec un bon degré de certitude)
* Nouveaux
* Potentiellement utiles (c.-à-d., devraient conduire vers des décisions utiles)
* Ultimement compréhensibles (par des humains).
Quelles sont les étapes de la découverte de connaissances à partir des bases de données?
Sélection
- Choix d’un échantillon représentatif, sélection des attributs et des enregistrements les plus pertinents après avoir bien compris les objectifs de l’application
Traitement des données
- Vérification de la cohérence, réduction de la redondance et de l’ambiguïté, ajout de données, prise en compte de connaissances a priori, traitement des valeurs
manquantes
Transformation
- Recodification, agrégation, …
Fouille de données
- choix des techniques (ex. classification) et des algorithmes (ex. arbre de décision) à appliquer
- Exécution des algorithmes et filtrage des résultats en utilisant des mesures de qualité (ex. confiance)
Interprétation et évaluation des résultats
Qu’est-ce que la fouille de données?
Confluence de plusieurs disciplines
- Technologie des bases de données
- Algorithmique
- Statistique
- Visualisation
- Apprentissage machine
- Reconnaissance de formes
- Autres disciplines
Données d’entrée
- Bases de données relationnelles
- Entrepôts de données
- Bases de données avancées
* Orientées objet
* Multimédia (texte, image, vidéo)
* Documents Web (ex. fichiers de journalisation)
- Graphes (ex. réseaux sociaux)
Deux types de démarches
- Validation d’hypothèses et exploration
* Ex. Existe-t-il une corrélation entre la diversification d’un portefeuille d’investissement d’une entreprise et le risque financier qu’elle encourt?
* Qu’est-ce qui caractérise les employés détenant une prime annuelle supérieure à 40,000$ ?
- Recherche exhaustive des liens, règles et concepts
* Opération coûteuse
* L’usager n’est pas nécessairement intéressé à obtenir l’ensemble des connaissances extraites
* Plusieurs connaissances peuvent être non pertinentes
Prise en compte de connaissances a priori
- Connaissance basée sur les instances (faits)
* Ex. la physique est une science
- Connaissance exprimée sous forme opératoire
* Ex. Si l’employé est analyste, alors son salaire annuel dépasse 50,000$
Quelles sont les différentes formes de fouille de données?
Trois principales formes
- Prédiction
* Apprentissage supervisé
* Prédiction de la valeur d’une variable (régression) ou de la classe d’appartenance (classification)
* Réseaux bayésiens, arbres de décision, réseaux de neurones
* Ex. identification des fraudeurs et des clients à haut risque
- Découverte
* Apprentissage non supervisé, analyse exploratoire
* Règles d’association. Ex. Achat du lait -> achat du beurre [sup. =50%, conf.= 75%]
* Motifs séquentiels. Ex. Si le client acquiert un magnétoscope, alors il y a une probabilité de 75% qu’il achète un caméscope dans un délai de 4 mois
* Formation de grappes (cluster Analysis). Ex. segmentation de la clientèle par genre et âge
- Détection de déviation
* Valeurs exceptionnelles (outliers), analyse de tendances
Quelles sont les méthodes et techniques de fouille de données?
- Arbres de décision
- Formation de grappes
- Séries temporelles
- Associations
- Réseaux bayésiens
- Réseaux de neurones
Association et sommarisation
- Règles d’association, résumés statistiques
Classification
- Arbres de décision, réseaux de neurones, réseaux bayésiens, K-nearest neighbor
Formation de grappes (Clustering)
- Regroupement conceptuel de Michalski
- Treillis de concepts de Wille
- Classification hiérarchique en statistique
Prédiction
- réseaux de neurones
- modèles de régression
Modèles de dépendance
- réseaux bayésiens, …
Analyse de tendances et déviations
- Techniques statistiques
- Motifs séquentiels
Quelles sont les différentes catégories de connaissances?
- Règles d’association et d’implication
- Règles de classification
- Règles de discrimination (ou caractérisation)
- Groupes et concepts obtenus par formation de grappes
- Modèles de prédiction
- Modèles de régression, etc.
Qu’est-ce qu’une implication?
Implications
- Représentation des implications entre des propriétés (ex. genre = masculin) des entités (ex. clients)
- Exemple : Si l’employé est âgé entre 30 et 39 ans, alors il est marié et possède 2 voitures
Qu’est-ce qu’une règle d’association?
Règles d’association
- Objectif : trouver des associations, corrélations, ou structures causales entre des ensembles d’items.
- Travaux d’Agrawal et al. (IBM) sur l’algorithme Apriori
- Applications : analyse du panier du consommateur, analyses médicales, gestion de la clientèle
- Exemple : Si un employé est responsable des comptes clients depuis plus de 2 ans et s’il a bénéficié d’une formation, alors il a 50% de chance de quitter l’entreprise.
Qu’est-ce que la classification?
Classification
- Constitution de classes d’objets similaires en se basant sur un ensemble de valeurs d’attributs et sur un attribut de classification
- Applications : approbation de crédit, marketing ciblé, diagnostic médical, analyse de l’efficacité d’un traitement, etc.
- Ex. Faire une classification de maladies et établir des règles pour fournir les symptômes qui décrivent chaque classe de maladie
- Les classes formées permettent de
* Générer des règles de classification
* Repérer la classe où devrait se trouver un nouvel objet
* Comprendre la signification de chaque classe
* Prédire la valeur de certains attributs
- Règle de classification : règle qui permet d’inférer qu’un objet répondant à une description D appartient à la classe C (modalité de l’attribut de classification)
* Si description D, alors classe C
* Ex. Si 30 <= âge < 40 ans ET genre = … … ET …, alors grand fraudeur
Qu’est-ce qu’une règle de discrimination?
Règle de discrimination
- Règle qui permet d’inférer que tout objet appartenant à la classe C (modalité de l’attribut de classification) répond à la description D
Si classe C, alors description D
- Discrimination entre classes d’individus ou d’objets
(ex. les habitants de diverses régions)
Ex. Si grand fraudeur, alors revenu < … ET âge … ET genre … ET …
Qu’est-ce que la formation de grappes (clustering)?
Formation de grappes (clustering)
- Constitution de grappes d’objets similaires sur la base d’un ensemble de valeurs d’attributs (sans spécification d’un attribut de classification)
- Découverte de concepts (ensemble d’objets avec leurs propriétés communes)
- Méthodes
* Technique de classification hiérarchique en statistique
* Conceptual clustering de Michalski en intelligence artificielle
* Treillis de concepts de Wille
Qu’est-ce que le regroupement?
Regroupement
- Ex. regroupement des logements selon divers attributs (prix, localisation, type de logement, nombre de chambres, ..)
- Ex. de concept : ({L1, L5, L8}, {lieu = Westmount, prix >= 600K, type=unifamiliale, chambres= 5})
Qu’est-ce qu’un treillis de concepts?
Treillis de concepts
- Technique de regroupement de type conceptuel
- Treillis : ensemble de nœuds reliés par une relation d’ordre partiel
- Chaque nœud est un concept formel (X, Y), avec X= extension et Y= intention
Qu’est-ce que les modèles de prédiction?
Modèles de prédiction
- Estimation de la valeur manquante ou inconnue d’une variable à partir d’autres variables.
Exemple : prédiction de la demande de consommation d’un nouveau produit à partir des dépenses de publicité pour ce produit
- Les réseaux de neurones servent à la classification, la prédiction, et même le
regroupement
- Détermination des facteurs majeurs influençant la valeur d’une variable donnée
* Jugement d’un expert, modèles de régression, etc.
Qu’est-ce que la prédiction par régression?
Prédiction par régression
- Régression linéaire, quadratique, exponentielle, ..
- Si régression linéaire, estimation des paramètres a et b de la fonction linéaire Y = a*X + b à partir de la connaissance des valeurs de la variable X (explicative) et de la variable Y (expliquée) pour un ensemble d’objets ou d’individus
- Ex. L’épargne Y est-elle une fonction linéaire du revenu X ? Si oui, quelle est la qualité de la régression et quelles sont les valeurs des paramètres a et b ?
Quelle est la différence entre la classification et la régression?
- Les deux techniques font de la prédiction et concernent l’apprentissage supervisé
- La classification prédit l’appartenance d’une observation (objet, individu, …) à une classe
- La régression prédit une valeur spécifique d’un attribut (ex. épargne)
Quelles sont les applications de la découverte de connaissances?
CRM (Customer Relationship Management)
- offre de produits et services
- connaissance des produits déjà acquis par les clients, ciblage des clients susceptibles de répondre à une campagne publicitaire
- prédiction de la probabilité d’un défaut de paiement par un client
Domaine médical
- Prédiction de la probabilité qu’un patient atteint d’une maladie puisse guérir à la suite d’une thérapie donnée, etc.
Analyse et gestion du marché
- Marketing ciblé
- Analyse du panier du consommateur
- Analyse du profil et des besoins de la clientèle: détection des produits les plus appréciés, identification des facteurs permettant d’attirer de nouveaux clients, etc.
- Segmentation du marché
- Sources de données : transactions bancaires et par cartes de crédit, plaintes des consommateurs, dépenses de la clientèle, etc.
Analyse et gestion du risque
- Prévision
- Analyse de la compétitivité : tendances du marché, comportement des compétiteurs
- Contrôle de la qualité
Détection de fraudes
- Assurances médicales, assurances de biens
- Appels téléphoniques
- Cartes de crédit
- Vente au détail
Domaine financier
- Analyse de tendances (clientèle, dépôts)
- Prédiction du paiement d’hypothèques et prêts
- Analyse de la politique d’octroi de prêts
- Regroupement et classification de clients
- Détection de patrons de comportement des clients (ex. séquences d’opérations)
- Détection de fraudes par intégration de données sur les transactions bancaires et sur le dossier criminel de certains clients
Commerce de détail
- Identification du comportement (ex. achats) des clients
- Amélioration des services à la clientèle (satisfaction, loyauté, rétention, etc.)
- Identification des produits qui se vendent le plus
- Analyse des politiques de transport et de livraison de produits
- Analyse de l’impact de campagnes publicitaires
Analyse de réseaux sociaux
- Détection de communautés par des techniques de regroupement (clustering)
- Analyse dynamique de réseaux et prédiction de leur structure
- Identification de nœuds influents (ou au contraire marginaux) et découverte de rôles
- Prédiction de liens
- Fouille intégrée de réseaux interconnectés
Text Mining : extraction de connaissances à partir de textes
- Extraction de termes
- Formation de résumés
- Organisation de documents par sujet
- Recherche de thèmes prédominants
- Construction de réseaux de concepts
- Quelques produits
* SAS Text Miner, IBM Watson AlchemyAPI
* IBM SPSS Text Analytics
* Lexalytics, etc.
Web Mining
- Fouille des résultats obtenus par les moteurs de recherche (ex. Google, Yahoo)
- Fouille de documents Web
- Découverte des pages les plus influentes sur le Web, découverte de l’organisation d’un site Web et des liens entre les pages
- Découverte du profil d’usagers sur le Web
Business Internet Analytics (BIA)
- Processus d’analyse de la séquence de déclics réalisés ou de pages consultées par un usager du Web.
Conclusion de la découverte de connaissances.
Plusieurs applications possibles
Aide à la prise de décision et à la prédiction
Meilleure compréhension de la sémantique des données
Dangers
- « While mining, beware of mines! »
- Atteinte à la vie privée et risque de poursuites
De grands défis
- Qualité des données et des connaissances
- Données massives : volume, vélocité, variété, véracité et valeur
- Performance et capacité d’expansion
- Répartition et parallélisme
- Intégration avec d’autres systèmes
Exigences envers les méthodes de FD
- Performance
- Capacité d’expansion (Scalability)
- Mise à jour incrémentale des résultats
- Fouille “à la demande” ou guidée par des contraintes
Fouille de données dans les applications
- Développement de solutions taillées sur mesure pour les besoins de l’organisation
- Fouille invisible : fonction encastrée (built-in) dans les applications (ex. Amazon.com)