Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Modèle de règles d’association dans les bases de données 2 Règles d’associati

1 Modèle de règles d’association dans les bases de données 2 Règles d’association L’idée principale: la recherche des régularités dans les BD Objectifs : Transcrire la connaissance sous forme de règle d’association Utiles : Aide à la décision Efficaces : Algorithmes de recherche Utilité des règles et exemple - Dans une base de données découvrir des règles de la forme: “95% des étudiants qui ont suivi un cours de géographie et un cours d’histoire économique ont également suivi un cours de droit” - Détection de corrélations entre descripteurs dans des ensembles de données Exemple: Découverte d’associations et de corrélations entre les articles achetés par les clients en analysant les achats effectués (panier) 3 La règle utile contenant des informations de qualité qui peuvent être mises en pratique Exemples : - le samedi, les clients des épiceries achètent en même temps de la bière et des couches - SI achat de riz + vin blanc ALORS achat de poisson (avec une grande probabilité) Résultats inexplicables difficiles à situer et donc à expliquer Exemple : lors de l'ouverture d'une quincaillerie, parmi les articles les plus vendus on trouve les abattants de toilette. Application typique: Analyser les transactions d’achats des utilisateurs pour dégager les habitudes d’achat des clients - Disposition des produits dans le magasin - Quels produits mettre en promotion, gestion de stock, … Très utile pour développer des stratégies de Marketing 4 Approche applicable dans d’autres domaines •Cartes de crédit, e-commerce, … •Services des compagnies de télécommunication •Services bancaires •Traitements médicaux Les serveurs Web stockent les sessions de visite des internautes - IP, navigateur, pages visitées, ordre de la visite, durée, ... 5 Exemple : Analyse du panier de la ménagère Découverte d’associations et de corrélations entre les articles achetés par les clients en analysant les achats effectués (panier) Etant donnée : •Une base de données de transactions de clients, où chaque transaction est représentée par un ensemble d’articles -set of items- (ex., produits) Trouver : •Groupes d’articles (itemset) achetés fréquemment (ensemble) 6 Données de transaction Analyse des tickets de caisse Commentaires: >> Une observation = Un caddie >> Ne tenir compte que de la présence des produits (pas de leur quantité) >> Nombre variable de produits dans un caddie >> La liste des produits est immense ! Autre représentation des données de transactions Selon la granularité choisie, le nombre de colonnes peut être immense. Type de données traitées 7 Tableau individus x variables Tableau binaire 0/1 On cherche des relations entre les mots d'un corpus sous forme de règles : si les mots x1; : : : ; xm apparaissent dans un texte alors les mots xm+1; : : : ; xn apparaissent aussi dans le texte Type de données traitées 8 Données transactionnelles Une représentation de la base de données D • Les données transactionnelles peuvent être représentées par une matrice • Une ligne = une transaction • Les attributs sont binaires • Chaque transaction (enregistrement) fait intervenir un ensemble d’items • Existe dans d’autres situations : visites d’un site web, ensemble d’amis d’un réseau social, les mots d’un documents, … 9 Données transactionnelles Notation ou formalisation du problème Etant donnés : (1) une liste d’items I(Ex: item = produit) (2) une base D de transactions où chaque transaction T est un ensemble d’items • I = {I1, I2, …, In} désigne un ensemble d’objets ensemble de produits (ex. {p1,p3}) • D = {T1, T2, …, Tm} est un ensemble de transactions tel que • On note par k-ensemble tout ensemble de taille k (contenant k objets) 3-itemset : {Café, Moutarde, Saucisse} . • Une transaction T est dite contenir un ensemble • La fréquence d’un ensemble A est le nombre de transactions dans D contenant A 10 Exemple1: Données transactionnelles 11 Associations de Documents - Trouver des associations parmi des documents dans une collection - Les documents correspondent aux items et les mots correspondent aux transactions -Les itemsets fréquents sont des groupes de docs dans lesquels plusieurs mots apparaissent en commun -support(E) = pourcentage de textes dans lesquels apparaissent tous les mots Règles d’association pour le web content mining Associations de T ermes - Trouver les associations parmi les mots basée sur leurs occurrences dans les documents -Intervertir la table (termes comme items, et docs comme transactions) Doc1 Doc2 Doc3 … Docn Mot1 5 4 2 … 1 Mot2 2 0 3 … 5 … … … … … … Motm 6 0 0 … 3 12 Règles d’association pour le web usage mining Règles d’association dans les Transactions Web - Découvrir les affinités parmi les ensembles de page Web à travers les sessions d’un utilisateur - Exemple: 60% des clients qui ont accédé /products/, ont aussi accédé /products/software/webminer.html 13 Recherche de règles d’association Formats de représentation des règles d’association de la forme : motifs de la forme : Corps Tête Exemple: couches =>bière [0.5%, 60%] (support et confiance sont des mesures d’intérêt définies par l’utilisateur) achète:couches =>achète:bière [0.5%, 60%] achète(x, “couches”) achète(x, “bière”) •“SI achète couches ALORS achète bière dans 60% de cas. Les couches et la bière sont tous deux achetés dans 0.5% des transactions de la base de données." 14 Evaluation des règles d’association R1 : Si p1 alors p2 1: 2: 3: 4: “SI achète couche, ALORS achète bière, dans 60% de cas, dans 0.5% de la base" Recherche de règles d’association 15 Critères d’évaluation des règles d’association Pour mesurer la qualité d’une règle d’association, on va utiliser deux indices: Support et confiance RQ:« Bonne » règle = règle avec un support et une confiance élevée 16 Exemple: Règle: A=>B? Soit A={I1,I2}, B={I3} 17 Constructions des règles d’association Schéma algorithmique de base La plupart des approches utilise le même schéma algorithmique - Pour construire les règles d ’association, le support de tous les itemsets fréquents dans la base doit être calculé - L ’algorithme procède en deux phases : 1) Génération de tous les ensembles fréquents 2) Génération des règles d ’association 18 Une première approche 1) Comptage des itemsets Soit I = {A, B,C} - Génération de tous les cas possibles : {∅},{A}, {B}, {C},{A,B}, {A,C}, {B,C},{A,B,C} - Comptage du support 2)Les règles d ’association -Le nombre d ’ensemble fréquent potentiel est égal à la taille du produit cartésien de tous les items - qui croit exponentiellement en fonction du nombre d ’items considérés. -Approche naïve : recherche exhaustive et test de tous les ensemble du produit cartésien pour savoir s ’ils sont fréquents -Exemple: 1000 items => 2^1000 ensembles à considérer Constructions des règles d’association Schéma algorithmique de base 19 Vers un algorithme générique But : minimiser les candidats L’algorithme APRIORI Principe : générer seulement les candidats pour lesquels tous les sous-ensembles ont été déterminés fréquents - Génération des candidats réalisée avant et de manière séparée de l'étape de comptage Constructions des règles d’association 20 L’idée est surtout de contrôler (limiter) le nombre de règles produites Démarche: Construction en deux temps Constructions des règles d’association 21 Quelques définitions - item = produit - itemset = ensemble de produits (ex. {p1,p3}) - Un ensemble d’items (itemset) - k = |X| est appelé un k-itemset. 3-itemset : {Café, Moutarde, Saucisse} - sup(itemset) = nombre de transactions d’apparition simultanée des produits (ex. sup{p1,p3} = 4) - X : cardinalité card(itemset) = nombre de produits dans l’ensemble (ex. card{p1,p3} = 2) - itemset fréquent= itemset dont le support est ≥ à support min Constructions des règles d’association Phase 1: Algorithme Apriori 23 Extraction des itemsets fréquents Exemple: Données Il s’agit de parcourir un treillis et de calculer les supports associés à chaque combinaison Phase 1: Algorithme Apriori 24 Itemset fréquent : itemset dont le support>= sup_min Exemple: Donne la représentation la plus compacte possible de la liste des itemsets. Ex. si on sait que {p1,p2,p3} est fréquent, on sait que {p1,p2}, {p1,p3} et {p2,p3} le sont également (mais on ne connaît pas leur support) Démonstration: Propriété 1 : support pour les sous- ensembles Si A ⊆B pour les itemsets A, B alors supp(A) >= supp(B) car toutes les transactions dans D qui supportent B supportent aussi nécessairement A. A={Café, Moutarde}, B ={Café, Moutarde, Saucisse} Propriété 2 : les sous-ensembles d’ensembles fréquents sont fréquents Propriétés des ensembles fréquents Phase élagage: 25 Propriétés des ensembles fréquents 26 Exemple: Extraction des itemsets fréquents Min_sup=2/9 (min_freq=2) Propriétés des ensembles fréquents 27 Constat : génération d ’un trop grand nombre de candidats s ’il y a 10^4 (1-itemset) => génération de 10^7 candidats 2-itemsets Pour un fréquent de 100, il faut générer plus de 10^30 candidats au total Est-il possible de proposer une méthode qui évite de générer des candidats ? Génération des candidats 28 Problèmes d’Apriori Le principe de l’algorithme: ◦Utiliser les (k – 1)-itemsets fréquents pour générer les k-itemsets candidats ◦Scanner la base pour tester le support des candidats Là où l’algo pèche : génération des candidats ◦Beaucoup: 104 1-itemsets fréquents générant 107 2-itemsets candidats Pour trouver les 100-itemsets on doit générer 2100 1030 candidats. ◦Plusieurs scans de la base: 29 Principe de base • Apriori utilise l’approche : uploads/Management/ chap2-fouilledonnees.pdf