Les fondements du machine learning

S'initier à la méthode A priori

TESTEZ LINKEDIN LEARNING GRATUITEMENT ET SANS ENGAGEMENT

Tester maintenant Afficher tous les abonnements
Assimilez la définition du vocabulaire relatif à l'algorithme a priori et voyez un exemple détaillé des itérations qu'il effectue.
09:37

Transcription

Dans ce chapitre concernant les algorithmes non supervisés de type règles d'association, on va étudier que l'algorithme d'a priori. Avant d'aborder cet algorithme qui est l'algorithme le plus populaire de l'association rules, du moins en ce tout début de 21ème siècle, il est important de définir quelques concepts-clés propres à ces méthodes particulières d'apprentissage. Voici quelques définitions de vocabulaire et également un tableau qui va nous aider à illustrer ces concepts. Déjà remarquez que ce tableau a les compositions d'un panier qui potentiellement, on va imaginer, peut contenir maximum quatre articles et on a numéroté les numéros de transaction, c'est-à-dire le numéro de panier qui est passé à la caisse. Alors voici quelques définitions de vocabulaire qui sont importantes pour comprendre ce qui va suivre. D'abord on définit par transaction le panier ou le caddie d'un ou ou plusieurs articles achetés par les consommateurs. Dans notre tableau on a donc cinq transactions. Ensuite on définit par item, c'est-à-dire par élément, c'est le terme anglais qui désigne aussi un article dans les magasins, comme étant un élément du panier, c'est-à-dire jus, le pain, le lait et ainsi de suite par rapport à tous nos paniers. Ensuite, et c'est là que ça commence peut-être à se compliquer, on définit le concept d'Itemset. Un itemset c'est quoi ? C'est une collection d'items ou d'articles. Un itemset contenant K items ou ce qu'on appelle également un K itemset, c'est un ensemble de K articles, par exemple un 1 itemset, ce serait le pain ou le lait ou le yaourt etc. Un 2 item set, ce serait le couple pain-lait, pain-beurre, lait- sucre ou jus-pain etc. Un 3 itemset, ce serait une combinaison de trois articles, peu importe lesquels. Maintenant qu'est-ce qu'un support ? Etant donné un item set, le support d'un item set, c'est le pourcentage de transaction contenant l'itemset. J'explique. Par exemple considérez le 2 item set, je vous rappelle que par exemple pain-lait c'est un 2 item set si on les prend ensemble. Si on considère l'item set pain-lait, alors le support de cet item set, si on le dénote par exemple par S, est égal à 2 sur 5, c'est-à-dire à 0,4 ou 40 %. Alors vous allez me dire mais d'où je sors ça ? Regardez. Sur les cinq paniers, combien de fois on a le couple pain-lait qui apparaît ? Si vous observez bien le tableau à l'écran et que vous prenez le temps de lire chaque ligne, sur les cinq paniers donc les cinq transactions, on a deux fois lait et pain qui sont ensemble dans le même panier. Ils sont ensemble dans le panier 2 et dans le panier 3, ce qui fait qu'on dit qu'ils ont un support, le 2 itemset pain-lait, de 2 sur 5, c'est-à-dire de 40 %. Après, par exemple si on prend le 1 itemset pain, alors son support est égal à 4/5, pourquoi ? Parce que pain tout seul, si on regarde, il est dans la transaction 1, 2, 3 et 5 donc il est sur 4/5 transactions. Il a un indice de fiabilité plus grand, c'est en quelque sorte ça que mesure le support, un indice de fiabilité dans le sens d'être dans une transaction. Maintenant on a ce qu'on appelle le minimum support, c'est la valeur de seuil minimum d'un support à partir duquel on qualifie un itemset de fréquent, c'est subjectif. Par exemple pour le pain, si on met 20 % comme minimum support, comme actuellement il est à 80 % dans notre tableau, il sera considéré comme fréquent parce que 80 % est plus grand que 20 %. Ensuite on définit par itemset fréquent un itemset dont le support est supérieur ou égal au support minimum. Si le minimum support vaut 0,5 par exemple, on peut dire que L, si on dit qu'on dénote par exemple L un 1 item set, est un item set fréquent, par exemple l'itemset pain est donc fréquent puisqu'il a un minimum support de 0,5 de base mais dans notre panier il est a 0,8. Mais par exemple l'item set qui serait donc le 2 itemset pain-lait, vaut 0,4 mais comme on a choisi un minimum support de 0,5, il sera considéré comme étant un itemset pas fréquent. L'algorithme a priori se fonde sur la probabilité dite a priori qui s'énonce comme suit : Si un item set est jugé fréquent, alors tout autre sous-itemset découlant des item sets de cet item set est également fréquent. Par exemple si on définit le support minimum à 0,35, l'itemset pain-lait ayant un support de S de 40 % sera qualifié de fréquent. Maintenant si on considère le sous-item set pain donc sous-item set de l'item set pain-lait, alors son support à lui, à ce sous-item set, est égal à 4/5. À ce niveau-là, étant donné qu'on a un sous-item set qui est pain et qui vaut 80 %, on le considérera a priori également comme fréquent parce que l'itemset parent dont on avait fixé le support minimum à 0,35 était donc lui-même qualifié de fréquent. Et si on considère un autre item set, par exemple le lait, si on regarde le tableau d'origine, je vous laisse vous y référer, son support est de 3/5 puisqu'il apparaît dans trois transactions sur cinq. Son support est de 0,6, il est plus grand que 0,35 donc il est aussi fréquent mais de toute façon il sera considéré a priori comme fréquent. Ainsi le nombre d'itemsets à analyser peut se réduire considérablement suite à l'élagage des itemsets non fréquents. Etant donné un support minimum qui, souvent d'ailleurs, est noté δ, l'algorithme d'a priori adopte une approche itérative ascendante qui détermine d'abord tous les item sets possibles de type 1 item sets et ensuite ceux dont le support est inférieur à δ font l'objet d'élagage ou pruning, c'est-à-dire qu'on les élimine et le reste, ceux qui sont fréquents, sont stockés dans une collection d'item sets que l'on notera L1. Par exemple, pour nos cinq transactions initiales, si on extrait tous les types d'articles que l'on avait, à ce niveau-là, parmi les dix item sets qu'il y avait donc les dix 1 item sets. Si on filtre ou on élague un δ de 0,35, seuls les cinq 1 item sets pain, sucre, lait, confiture et fromage resteront et feront partie de L1. Ensuite l'étape suivante constitue tous les itemsets possibles de type 2 item sets à partir des items contenus dans L1. Ça veut dire qu'on va obtenir la chose suivante, le tableau avec les paires qui restent par rapport au support minimum qu'on avait fixé à l'état des 1 item sets. A nouveau les 2 item sets sont testés et ceux dont le support est inférieur à δ feront aussi l'objet d'un élagage ou de pruning et seuls les 2 item sets fréquents sont conservés dans la collection d'itemsets L2 que vous avez sur votre écran. Ce processus d'agrégation et d'élagage est répété pour une collection LK contenant les itemsets possibles de type K itemsets ayant validé le test du support minimum δ. En général ça ressemble à la chose suivante : on a une table qui est vide, on a les 1 item sets, par exemple B, C et D, vous voyez qu'on a éliminé A par élagage. Ensuite on monte d'un niveau, on a les paires d'item sets donc les 2 itemsets, les BC, BD et CD et ensuite on a les 3 itemsets donc les item sets ternaires qui nous resteraient. Et on continue comme ça jusqu'à ne conserver que les éléments qui satisfont à certains δ. Cet algorithme je pense que vous comprenez qu'il s'arrête si, pour une nouvelle collection d'itemsets, de niveau K + 1, aucun K + 1 item set ne valide le test du support minimum δ. En d'autres termes, plus aucun K item set n'a un support qui dépasse notre support minimum. Optionnellement on peut définir un entier K qui spécifie soit le nombre maximum d'items qu'un item set peut contenir ou le nombre maximum d'itérations à effectuer par l'algorithme et, là encore, vous allez me dire oui mais il y a une intervention humaine puisqu'il faut fixer K ! Non parce qu'à nouveau les algorithmes peuvent apprendre, sur la base, des bases de données existantes. De toute façon l'humain n'est pas nécessaire dans cette intervention. Voilà concernant la première approche, les premières informations qu'il faut savoir sur l'algorithme d'a priori.

Les fondements du machine learning

Acquérez les bases du vocabulaire lié au machine learning. Découvrez les outils fondamentaux avec les idées, applications et concepts mathématiques sous-jacents à chacun.

3h04 (33 vidéos)
Aucun commentaire n´est disponible actuellement
Spécial abonnés
Date de parution :21 déc. 2017

Votre formation est disponible en ligne avec option de téléchargement. Bonne nouvelle : vous ne devez pas choisir entre les deux. Dès que vous achetez une formation, vous disposez des deux options de consultation !

Le téléchargement vous permet de consulter la formation hors ligne et offre une interface plus conviviale. Si vous travaillez sur différents ordinateurs ou que vous ne voulez pas regarder la formation en une seule fois, connectez-vous sur cette page pour consulter en ligne les vidéos de la formation. Nous vous souhaitons un excellent apprentissage avec cette formation vidéo.

N'hésitez pas à nous contacter si vous avez des questions !