Remerciez-le!

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

INF2033, Méthodes Algorithmiques et Structures de Données TP règles d’associati

INF2033, Méthodes Algorithmiques et Structures de Données TP règles d’association, Novembre 2020 Membres du groupe matricules et pourcentage de participation : - NZOUETENG TCHUENTE MICAELLE GRACE ; 19M2193 30% - EKOH FOUAPON NJIKAM YVAN ; 19M2198 30% - FOTIE NGNIPIBEO DERRICK JUNIOR ; 19M2390 25% - OBAMA MEVOUNGOU DRYSTAN GODGIFT ; 19M2132 15% Exercice 1 :  Le rangement de produits dans un entrepôt est dépendant des préférences des clients. Si l’ensemble d’itemsets I={I1,I2,I3} correspondant respectivement au itemset du pain, du chocolat et du beur. En ayant remarquer que un client qui achète du pain achète aussi du chocolat et du beur (I1I2I3), alors dans l’entrepôt ils seront rangés cote à cote pour faciliter les livraisons.  Le rangement des produits dans un super marché est fait de tel sorte que puisqu’on sait qu’un client qui achète du pain doit forcement chercher du chocolat et du beur, alors, ces articles sont placés les loin des autres pour permettre aux clients de parcourir l’ensemble des articles du super marché tout t’en cherchant ses priorités.  Dans la conception des catalogues les itemsets permettent de classer les articles de façon à ce les articles dont les clients n’ont pas encore découvert soient en premier plan et les articles populaires en second plan. Exercice 2 : application des règles d’association certaines pour la recommandation sur un site web de vente en ligne. Les sites de vente en ligne collectent le données sur les achats des consommateurs ; Ces informations servent à mieux mener les campagnes de marketing, mieux gérer les inventaires ou améliorer la relation client-serveur ; a approprier/mieux organiser la présentation des produit sur les sites. Exercice 3 : Règles d’association ‘’canoniques’’ 3.1- Nous pouvons dire que Y est contenu dans Z. 3.2- propriété analogue basée sur la partie droite Y de la règle X Y ⇒ X Y où Y ⇒ X ⊂ 3.3- Déduire, par rapport aux parties gauches X, les règles X Y qui sont les ⇒ noyaux à partir desquels on peut obtenir toutes les règles d'association. X Y, Y Z. ⇒ ⇒ 3.4- Déduire, par rapport aux parties droites Y, les règles X Y qui sont les ⇒ noyaux à partir desquels on peut obtenir toutes les règles d'association. Exercice 4 : Règles X Y et Xa Ya ⇒ ⇒ nous pouvons dire de ces règles d’association ne sont pas équivalentes. Exercice 5 : ° X Y et Xa Ya sont équivalent si a appartient à un itemsets. ⇒ ⇒ ° Exercice 6 : pour que ce calcul vaille la peine, il faut que ces coûts puissent être amortis. Proposer un critère pui modélise la valeur économique d’une règle d’association certaine. Pour amortir les coûts du calcul des règles d’association, un critère qu’on peut utiliser est la réduction du nombre d’itemsets candidat ; ce qui diminue du coup le nombre de comparaisons. Exercice 7 : 1)  La définition d’une règle d’association qui utilise l’expression « toute transaction qui contient X » n’est pas raisonnable dans le contexte applicatif car dans le cas que ce n’est pas pour X que le client est là ou que tous les articles soient cote à cote l’ensemble d’itemsets ne pourra être parcouru parce que soit le client ne va pas prendre tous les articles qui vont avec X soit il ne découvrira pas les autres articles proposés.  Ces critères permettent de mesurer la qualité d’une règle d’association car ils prennent en compte le support et la confiance par rapport à X ꓴY qui est une association fréquente. 2) Cette définition des règles d’associations elle une modélisation d’une bases de données non conventionnelle qui se base sur la fréquence d’achat en association de certains articles ; cela dans l’optique d’accroitre la vente des articles moins prisés tout en maintenant celle des articles prisés. Exercice 8 : Décrire une méthode très simple pour l’élimination des parties de I (sans vous soucier de l’efficacité). Pour énumérer les itemsets, il suffit de parcourir un treillis et de calculer les supports associés à chaque combinaison. On part des différents items initialement énoncé, et on en déduit les différent itemsets possible ( en utilisant un principe similaire au principe des arbres). Exercice 9 : C’est le schéma 2 qui est le plus efficace. Exercice 10 : On peut dire que Z n’est pas fréquent. Exercice 11 : On désigne par I un ensemble d’items. Un sous ensemble de I est appelé itemset. D’après la question de l’exercice précédent, (propriété de l’anti-monotoni), si X n’est pas fréquente alors tous sous ensemble contenant X n’est pas fréquent. Pour déterminer les itemsets fréquent, on entre dans I et on détermine si ses items sont fréquent. Si le premier l’est on passe au suivant et si il ne l’est pas, on élimine de la recherche toutes les parties de I auxquelles cet item appartient, et on passe a l’item qui suit. Les itemsets fréquent seront (qui ne seront pas éliminé). Ainsi, les parties de I ne seront pas parcouru. Exercice 12 : Pour qu’un itemset X de taille k soit fréquent, il faut que chacun des k éléments contenue dans X soit fréquent. (les k terst doivent être positif). E XERCICE 15: Pour le calcul des pré-candidats lorsque Lk-1 est organise en liste chaînée il faut vérifier tout d'abord que ces itemsets sont fréquents dans ce cas nous obtiendrons les K- pré-candidats si ce n'est pas le cas alors nous regrouperons les itemsets par affinité puis on parcours chacun et on somme a la fin. EXERCICE 17: la complexite est log2K EXERCICE 18 : Il est avantageux d’organiser Lk-1 dans une table de hachage pour le filtrage des pré-candidats car une table de hachage nous permet d’accéder à une valeur grâce à sa clé or comme les transactions sont associés à des identifiant unique, il serait donc avantageux d’utiliser une table de hachage pour organiser les Lk-1. EXERCICE 19 : La complexité en nombre d’opérations, du calcul de l’ensemble Ck des candidats de taille k est de : O(2n) EXERCICE 2 0 : Explications des algorithmes pour le calcul des itemsets fréquents et des règles d’association (R. Agrawal et R. Srikant) : Explication : - la recherche des itemsets fréquents : les itemsets fréquents sont les groupes d'items (attributs) dont le support est supérieur à minSup, - l'extraction des règles parmi l'ensemble des itemsets fréquents : les règles dont la confiance est supérieure à minConf • Premier Algorithme : Recherche des itemsets fréquents L'ensemble des itemsets fréquents se produit dans cette partie. L'algorithme construit des ensembles de plus en plus grands d'itemsets fréquents. Elle consiste à parcourir la base de données de manière itérative, pour calculer les itemsets fréquents de taille k (k-itemsets noté Lk) à partir des itemsets fréquents de taille k-1 (k-itemsets notés Lk-l). Le procédé est le suivant : - construire un ensemble candidat Ck • - jointure des itemsets de taille k avec ceux de taille k-l, en éliminant les itemsets de taille k qui contient un sous-itemset non fréquent. En effet tout sous-itemset d'un k-itemset fréquent est fréquent (Si i1 i2 i3 est fréquent, alors il, i2, i3, il i2, il i3, i2 i3 le sont nécessairement). - calcul du support de chaque itemset candidat, et ne garder que ceux dont le support est supérieur à minSup. • Deuxième Algorithme : extraction de règles L’algorithme sauvegarde à chaque passage, le support des k-itemsets fréquents. Ces derniers sont utilisés dans la deuxième partie pour calculer les confiances des k-itemsets fréquents, car la confiance est définie par une relation simple avec le support EXERCICE 2 1 : Donner la complexité en nombre d’opérations de Apriori avec les structures de données de votre choix, en fonction des tailles de |Lk-1|, |PCk|, |Ck|, M = ||T|| (taille de T), m = |T|, n = |I| :  Nombre d’itemset généré : Le nombre d’itemset possible est de 2m Le principe de l’algorithme itératif permet de ne pas générer la totalité des itemsets, on n’examine donc pas 2m itemsets mais beaucoup moins. Pour chaque niveau k on ne génère donc pas les k-itemsets mais seulement un sous-ensemble, basé sur le nombre de (k-1) itemsets fréquents identifier au niveau précédent. Pour m itemsets, on identifie m 1-itemsets candidats. Le calcul des supports de ces candidats via un examen de l’ensemble des données permet d’identifier m’ 1-itemsets fréquents (avec m’< m). Le nombre de 2-itemset possibles est C2 = m! /(2! * (m-2)!) = m*(m-1) / 2. Or, on ne génère qu’un sous-ensemble des 2-itemsets en ce basant sur la propriété : tous les sous itemsets d’un itemset fréquent sont fréquents. Ainsi on génère les candidats de taille 2 à partir des m’ 1-itemsets fréquents, soit m’*(m’-1) / 2 2-itemsets candidats.  Nombre de scan de données : m Le nombre de scans nécessaires des données dépends de l’implémentation réaliser. Pour calculer le support des 2k-itemsets possibles, on doit réaliser : 2k scans de base, un pour chacun des itemsets, dans la version de base de l’algorithme (on effectue un scan uploads/Marketing/ projet-tp-inf2033.pdf