Remerciez-le!

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

Projet 1 : Règles d’Association Professeur Maurice TCHUENTE Avril 2018 On consi

Projet 1 : Règles d’Association Professeur Maurice TCHUENTE Avril 2018 On considère un ensemble d'items I = {i1, i2, … , in}. Un sous-ensemble de I est appelé itemset. On considère un ensemble d'itemsets ou base de transactions T = {t1, t2, … , tm}. Un itemset A est dit fréquent dans T, s'il est contenu dans un nombre de transactions de T supérieur ou égal à un seuil s. 1 –Donner des exemples d'application des itemsets fréquents pour : o le rangement de produits dans un entrepôt de vente par correspondance pour minimiser les déplacements lors de la collecte des articles correspondant aux commandes des clients o le rangement de produits dans les rayons d'un supermarché pour obliger les clients consommant certains produits à voir d’autres produits o la conception de catalogues. 2 - Une règle d'association ‘’certaine’’ X ⇒ Y entre deux itemsets X et Y, signifie que toute transaction qui contient X contient aussi Y (Toute personne qui achète X achète aussi Y).  Donner des exemples d'application des règles d'association certaines pour la recommandation sur un site de vente en ligne. 3 – Règles d’association ‘’canoniques’’ 3.1 Si X ⇒ Y et X ⊂ Z, que peut-on déduire comme relation entre Z et Y ? 3.2 Donner une propriété analogue basée sur la partie droite Y de la règle X ⇒ Y. 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. 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. 4 - Que peut-on dire des règles X ⇒ Y et Xa ⇒ Ya 5 - Déduire des questions 3 et 4, deux contraintes qu’on peut imposer aux règles d'association. Dire pourquoi les règles vérifiant ces contraintes peuvent être qualifiées de canoniques. Le calcul des règles d’association entraîne des frais liés à :  la mobilisation d’un informaticien pour la conception du logiciel de découverte des règles  l’utilisation des ressources informatiques pour la mise en œuvre du logiciel. 6 - Pour que ce calcul vaille la peine, il faut que ces coûts puissent être amortis. Proposer un critère qui modélise la valeur économique d’une règle d’association certaine. 7 – Sémantique des règles d’association 7.1 Dire pourquoi la définition d’une règle d’association qui utilise l'expression « toute transaction qui contient X » n’est pas raisonnable dans un contexte applicatif ? Indication : Donner un exemple où cette définition n’est pas vraie alors que le fait de savoir qu’un client achète ensemble les articles de X permet de le prospecter avantageusement pour acheter les articles de Y. Dans la suite, on dira que XY, XY = , est une règle d’association de support s (entier naturel) et confiance c (comprise entre 0 et 1), si  Freq(X  Y)  s  Freq(X  Y)/Freq(X)  c Freq(A) désigne le nombre de transactions contenant un itemset A. Dire pourquoi ces critères permettent de mesurer la qualité, d’une règle d’association. 7.2 Expliquer cette définition Approche pour le calcul des règles de support au moins s et de confiance au moins c Etape 1 : On calcule les itemsets fréquents L, c-à-d dont le support (ou fréquence) dépasse le seuil s. Etape 2 : Pour chaque itemset fréquent L, on calcule les règles de la forme XY, telles que = X  Y = L, XY =  et Freq(L)/Freq(X)  c. On s'intéresse maintenant à l’étape 1 consacrée au calcul de tous les itemsets ayant une fréquence au moins égale à s. On note Lk les itemsets fréquents de taille k. On considère pour l'étape 1, l'approche “brute force” qui consiste à examiner systématiquement l'ensemble des parties de I (noté 2I ), et à comparer ces parties aux éléments de T pour déterminer les itemsets fréquents: 8 - Décrire une méthode très simple pour l’énumération des parties de I (sans vous soucier de l’efficacité). 9 - Sachant que l’ensemble T des transactions ne peut pas tenir en mémoire centrale, lequel des deux schémas ci-dessous est le plus efficace ? (Schéma 1) (Schéma 2) Initialisation Initialisation Pour A ∈ 2I faire Pour t ∈T faire Pour t ∈T faire Pour A ∈2I faire début début … … fin ; fin ; 10 - On suppose que X n’est pas fréquent, et X  Z. Que peut-on dire de Z. N.B. : Cette propriété est appelée anti monotonie. 11 – Déduire qu’il n'est pas nécessaire de balayer toutes les parties de I pour déterminer les itemsets fréquents. On suppose connu l‘ensemble Lk-1 des itemsets fréquents de taille k-1. On remarque que tout sous-ensemble d’un itemset fréquent Lk est aussi fréquent. Cette propriété appelée anti-monotonie se formule aussi en disant que si X n’est pas fréquent, alors tout sous- ensemble Y contenant X n’est pas fréquent. Projet1_Règles_Association_Avril2018 12 - Donner une condition nécessaire (mais non suffisante) basée sur k tests d’appartenance à Lk-1, pour qu’un itemset X de taille k, soit fréquent. 13 - Montrer que, par utilisation de l’anti monotonie, on peut pour le calcul de Lk, générer par jointure à partir de Lk-1, un ensemble PCk de pré-candidats de taille k et donc réduire l’ensemble des itemsets de taille k à examiner. Indication : tout pré-candidat les k conditions mises en évidence dans la question 12. 14 – Intérêt des prétraitements 14.a Dire comment filtrer les candidats PCk pour obtenir un ensemble de candidats Ck plus petit que PCk, dont les itemsets vérifient les k conditions de la question 12. Le calcul des pré-candidats et des candidats a évidemment un coût qu’il faut comparer aux parcours de T qu’on économise. 14.b Faire une analyse pour faire ressortir l’intérêt de passer par PCk et Ck pour calculer Lk. 15 – Dire comment procéder pour le calcul des pré-candidats lorsque Lk-1 est organisé en liste chaînée. 16 - Proposer une structure de données en arbre (trie) qui facilite le calcul des pré-candidats. 17 – Donner la complexité en nombre d’opérations, du calcul de l’ensemble PCk des pré-candidats de taille k. N.B. On précisera le choix des paramètres utilisés pour cette évaluation. 18 – Dire pourquoi il est avantageux d’organiser Lk-1 dans une table de hachage pour faciliter le filtrage des pré-candidats en vue d’obtenir les candidats ? 19 - Donner la complexité en nombre d’opérations, du calcul de l’ensemble Ck des candidats de taille k. Les deux astuces introduites plus haut sont à la base de l'algorithme Apriori. 20 - Expliquer les algorithmes ci-dessous pour le calcul des itemsets fréquents et des règles d’association (R. Agrawal et R. Srikant). Projet1_Règles_Association_Avril2018 21 - 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. 22 - On désire réduire le nombre d’itemsets à traiter tout en maintenant intacte la capacité à détecter tous les itemsets fréquents. Pour cela on considère deux itemsets X et Y fréquents et de même fréquence, tels que X  Y. De ces deux itemsets, lequel faut-il conserver ? 23 - On appelle itemset fermé un itemset maximal pour l’inclusion, parmi les itemsets de même fréquence. Montrer que le plus petit itemset fermé contenant X est l’intersection de toutes les transactions contenant X. 24 - Montrer que les itemsets fréquents fermés permettent de déduire tous les itemsets fréquents, avec leurs fréquences. 25 - Comment pourrait-on définir la notion d’itemset fréquent maximal ? 26 - Montrer que les itemsets fréquents maximaux permettent de déduire tous les itemsets fréquents, mais sans leurs fréquences. 27 - Donner un algorithme pour le calcul des itemsets fréquents maximaux 28 - Donner pour l'exemple ci-dessous (on prendra le seuil s = 2) tiré de l’article de Uno et al. : o le treillis des parties de I o les itemsets fréquents, les itemsets fréquents maximaux, les itemsets fréquents fermés. Calcul des règles d’association On s’intéresse au calcul des règles d’association XY telles que X  Y = L, L étant un itemset fréquent. Il est clair que plus X est grand (plus le client achète d’articles) plus L – X est petit, et il y a de chances d’acheter Y = L – X. 29 – Donner une règle d’association triviale (mais sans intérêt). 30 – Expliquer comment on peut à partir de la règle XY, générer de manière récursive toutes les règles de partie gauche incluse dans X, en diminuant au fur et à mesure la partie gauche au profit de la partie droite. N.B. On pourra illustrer par un arbre 31 – Donner la procédure récursive correspondante 32 – Comment s’obtient alors la génération de toutes les règles d’association associées à L ? 33 – Expliquer comment on peut à partir de la règle XY, générer de manière récursive toutes les règles dont la partie droite contient Y, en augmentant au uploads/Finance/ projet-regles-association-nov2019.pdf