Détection des associations fréquentes en C++ - Introduction
Un billet de stendhal666

Le , par stendhal666, Membre chevronné
Pour ceux qui ont suivi ce blog dans une vie antérieure, ce billet n'a aucun rapport avec les précédents. J'ai échoué à susciter le débat autour de la programmation fonctionnelle, dont acte. La série de billets que je prépare portera sur l'élaboration d'une petite bibliothèque d'apprentissage machine en C++ moderne en essayant de faire ressortir la singularité de ce langage. Il serait peut-être plus avisé de créer un autre blog mais la règle de developpez.net semble être: un utilisateur, un blog, et je m'y plie bien volontiers. Cela dit, commençons.

Les associations fréquentes, ou frequent patterns
Le premier algorithme que nous développerons devra permettre, dans un ensemble de séquences, de détecter les associations d'éléments les plus fréquentes. Imaginez que vous êtes embauchés par votre libraire: il veut pouvoir suggérer d'autres lectures à ses clients lorsqu'ils passent à la caisse et vous demande donc le moyen de savoir quels sont les livres fréquemment achetés ensemble... Et vous voilà à chercher des associations! Voici deux autres exemples de l'utilisation qu'on peut en faire:

- proposer une saisie dans un moteur de recherche: lorsque vous tapez votre recherche, le moteur propose souvent de la compléter; ses propositions sont tirées des associations les plus fréquentes dans les recherches précédentes. Donc, si vous voulez vous faire une idée de ce que pense le sexe opposé à votre sujet, tapez: "Pourquoi les hommes" ou "Pourquoi les femmes" et le moteur vous proposera des recherches avisées, comme: "Pourquoi les hommes adorent les chieuses", "Pourquoi les hommes mentent", etc. Ce n'est pas que le moteur a un avis sur la question, c'est juste que c'est une question fréquemment posée.

- fixer la disposition des rayons et les prix dans un magasin: en prenant la liste des achats de vos clients, et en détectant les associations fréquentes, vous pouvez décider de rapprocher -ou d'éloigner- des produits, voire d'en fixer les prix. L'exemple le plus célèbre est celui des bières et des couches: un magasin américain avait remarqué, par cette méthode, que ses clients achetaient souvent ensemble bières et couches; ils en avaient déduit que les maris envoyés faire les courses pour les enfants se dédommageaient de leur peine en prenant quelques bières. Moralité, les bières -plein tarif- ont été placées à côté des couches, pour encourager à la consommation.

On pourrait réfléchir à bien d'autres façons d'utiliser les associations fréquentes: faire le menu d'un restaurant, améliorer l'interface d'un logiciel, etc.

Qu'est-ce qu'un association fréquente?
Essayons de donner une définition plus rigoureuse des associations fréquentes: soit un ensemble d'éléments que nous appellerons E. Soit des séquences, ou transactions, qui sont des sous-ensembles de E. Une association fréquente est un sous-ensemble de E qui est également un sous-ensemble d'un nombre déterminé (fréquent) de séquences.
Il y a deux façons de définir le caractère fréquent d'une association: on peut fixer un seuil d'apparition, 10 apparitions, par exemple, ou bien un pourcentage: si l'élément apparaît dans au moins 5% des séquences analysées, on considérera qu'il est fréquent. Néanmoins, une fois que l'on connaît le nombre de séquences à analyser, la deuxième définition est réductible à la première.

Quels sont les algorithmes utilisés?
La force brute
ne convient que pour les petites bases de données. On génère d'abord l'ensemble des éléments apparaissant dans la base de données, puis tous ses sous-ensembles, et on vérifie la fréquence de chacun des sous-ensembles dans la base de données. Mettons que vous ayez 99 articles dans votre magasin, vous aurez 2100 sous-ensembles à vérifier. C'est long. Si vous êtes un moteur de recherche, et même si vous avez la puissance de calcul de Google, imaginez le nombre de sous-ensembles et reconnaissez que vous êtes foutus.

L'algorithme a priori
L'algorithme appelé a priori repose sur une propriété évidente des associations fréquentes: si un élément, ou un sous-ensemble, n'est pas fréquent, aucun des ensembles qui le contient ne le sera. Si le sous-ensemble { "femme", "simple" } n'est pas fréquent, alors { "femme", "simple", "caractère", "égal" } ne le sera pas non plus.

Que peut-on en tirer d'un point de vue algorithmique (je vous laisse en tirer les conclusions que vous voulez pour votre vie sentimentale)? Si un sous-ensemble n'est pas fréquent, il n'est pas nécessaire de vérifier les sous-ensembles qui le contiennent; c'est ce que fait l'algorithme a priori: on commence par générer tous les sous-ensembles d'un seul élément - on raye les sous-ensembles qui n'atteignent pas le seuil requis - on combine les sous-ensembles restant pour former des sous-ensembles de deux éléments - on raye ceux qui n'ont pas la fréquence requise - on combine pour obtenir des ensembles à trois éléments, et ainsi de suite, jusqu'à épuisement.

Quoiqu'il réduise le nombre de passage dans la base de données, il reste nécessaire de scanner la base de données pour chaque combinaison, ce qui peut être un gros désavantage dès que la connexion/la lecture est lente.

L'arbre des associations fréquentes, ou frequent pattern tree
C'est l'algorithme que nous implémenterons ensemble et longuement. C'est un algorithme nettement plus compliqué mais nettement plus efficace. Vous pouvez jeter un oeil à l'article original ici (c'est un pdf dans une archive), ou taper "frequent pattern tree" dans votre moteur de recherche favori, vous le trouverez facilement. Il promet d'être, pour la plupart des données à analyser, plus rapide de plusieurs ordres de grandeur. Son premier avantage est de ne demander que deux passages dans la base de données: le premier pour déterminer les éléments fréquents, le deuxième pour construire l'arbre lui-même. Toutes les opérations suivantes sont effectuées sur l'arbre, qui est une version réduite et pratique de la base de données

L'AAF est composé de deux élements principaux:
- un arbre qui contient les séquences de la base de données triées et condensées
- une table qui permet de retrouver dans l'arbre tous les noeuds qui renvoient au même élément.

En voici un exemple (avec une fréquence minimum de 1, ce qui n'est pas très représentatif, certes), illustrant mes capacités en dessin. Il est extrait de la base de données suivante:

s1: { eau }
s2: { eau, bière, couches }
s3: { eau, bière, chips}
s4: { eau }
s5: { bière, vodka }
s6: { eau, bière, couches }

Les grandes étapes de la construction de l'AAF
1. scannez la base de données pour obtenir, pour chaque élément présent, sa fréquence et construisez partiellement la table avec.
2. scannez à nouveau la base de données, et pour chaque séquence:
2.1: retirer les éléments qui ne sont pas assez fréquents
2.2: triez-les dans l'ordre décroissant de fréquence
2.3: ajoutez-les à l'arbre: ne créez un nouveau noeud que si la séquence ajoutée ne se confond pas avec une séquence précédente; sinon augmentez simplement la fréquence du noeud: dans l'exemple que j'ai donné, { eau } crée un nouveau noeud car l'arbre était vide; { eau, bière, couches } crée deux noeuds puisque son premier élément était déjà à la bonne place dans l'arbre; { eau, bière, chips } crée un seul nouveau noeud puisque les deux premiers éléments étaient à la bonne place, etc.
Voilà, votre arbre est prêt.

Trouver les associations fréquentes
C'est à la fois plus simple à faire et plus compliqué à concevoir; la détection tire partie des propriétés de l'AAF.
1. On reprend les éléments fréquents dans la table et on les trie dans l'ordre croissant de fréquence
2. Pour chacun de ces éléments:
2.1: on ajoute l'élément, avec un préfixe initialement vide, à la liste des associations fréquentes // le sens du préfixe se comprend en 2.3
2.2 on prend l'ensemble des chemins qui partent des noeuds contenant cet élément et vont vers la racine de l'arbre
2.3 on crée une nouvelle AAF avec ces chemins et on recommence en ajoutant l'élément au préfixe utilisé en 2.1
Voilà, vos associations sont trouvées

Le programme pour la suite
Mon projet n'est pas seulement d'implémenter l'algorithme en C++. Je proposerai dans le prochain billet une interprétation naïve, qui est la transcription en C++ d'une implémentation en Python que j'ai trouvé dans l'excellent Machine learning in Action de Peter Harrington. En partant de ce prototype grossier, nous raffinerons ensemble -j'espère avoir en commentaire des propositions- la conception et l'implémentation de l'algorithme dans un esprit C++.


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster un commentaire

Avatar de SpiceGuid SpiceGuid - Membre émérite https://www.developpez.com
le 26/12/2015 à 21:38
Pour le débat ouvert sur la programmation fonctionnelle, je dirais que ça n'est pas une question de lieu, de format ou de style de présentation, c'est une simple question de part de marché. Peu de parts de marché égale peu d'emplois, peu de logiciels. Et soyons honnête, une techno sans killer-app a du mal à justifier son existence sur un marché déjà saturé par l'offre. Et non, un assistant de preuve n'est pas une killer-app. La seule fois où j'ai réussi à arracher une réaction à un programmeur mainstream c'était à l'évocation de Raincat. J'ai eu droit à "je croyais que Haskell ça n'était que pour les abstractions mathématiques". Le comble de la gratification.
Ensuite je crois que Nikki and the robots n'a pas été un succès commercial et là ça a été le coup de grâce, plus aucun curieux ne s'est intéressé à Haskell.

Mais revenons à nos moutons.
Le C++ moderne c'est à partir de quand ? Quand je remplace struct par class ? Ou plutôt quand je privilégie les récents ajouts dans la norme ?

Les associations. C'est vague. Si c'était juste des listes on utiliserait un Trie. Si c'était juste des paires on utiliserait un 2D-tree. Si c'était des n-uplets on utiliserait un kD-tree. Si c'était des partitions on utiliserait un Union-Find. Mais comme ça n'est rien de tout ça on va crafter un algorithme original. Ça ressemble assez à des inventaires, un peu comme ce que j'avais fait il y a longtemps en OCaml avec les briques lego.
Au niveau des données la similitude est frappante, par contre comme la finalité n'est pas la même au niveau des traitements ça n'aura aucun rapport.
Avatar de stendhal666 stendhal666 - Membre chevronné https://www.developpez.com
le 26/12/2015 à 23:35
Citation Envoyé par SpiceGuid;bt1654
Pour le débat ouvert sur la programmation fonctionnelle, je dirais que ça n'est pas une question de lieu, de format ou de style de présentation, c'est une simple question de part de marché.


J'espère ne pas être tout à fait à côté de la plaque quand je dis qu'on programme aussi par plaisir? Et j'ai pour ma part trouvé beaucoup de plaisir à découvrir et utiliser la programmation fonctionnelle. J'espérais partager ça dans le blog avec d'autres... J'ai vu qu'il y avait quand même un certain nombre d'affichages pour chaque post, il y a eu très peu de commentaires mais les billets ont tout de même été lus.

Citation Envoyé par SpiceGuid;bt1654
Mais revenons à nos moutons.
Le C++ moderne c'est à partir de quand ? Quand je remplace struct par class ? Ou plutôt quand je privilégie les récents ajouts dans la norme ?

Les récents ajouts de la norme: on arrive presqu'à l'expressivité des langages de script avec toujours la rigueur et la performance C++

Citation Envoyé par SpiceGuid;bt1654
Les associations. C'est vague. Si c'était juste des listes on utiliserait un Trie. Si c'était juste des paires on utiliserait un 2D-tree. Si c'était des n-uplets on utiliserait un kD-tree. Si c'était des partitions on utiliserait un Union-Find. Mais comme ça n'est rien de tout ça on va crafter un algorithme original. Ça ressemble assez à des inventaires, un peu comme ce que j'avais fait il y a longtemps en OCaml avec les briques lego.
Au niveau des données la similitude est frappante, par contre comme la finalité n'est pas la même au niveau des traitements ça n'aura aucun rapport.

J'ai jeté un oeil à ton article qui est très intéressant. Le vaisseau logo est incroyable! En revanche sur la question des associations fréquentes je vais éditer mon article pour le rendre moins vague. Ce à quoi je pense est:
- soit E un ensemble d'éléments
- soit S un ensemble de séquences, ou transactions, qui sont des sous-ensembles de E
on veut trouver tous les sous-ensembles de E qui sont également des sous-ensembles d'un nombre déterminé de transactions présentes dans S
Avatar de SpiceGuid SpiceGuid - Membre émérite https://www.developpez.com
le 27/12/2015 à 16:21
J'ai envie d'une formulation un peu plus générale.

Par exemple:
  • soit C un ensemble et soit P=℘(C).
  • soit T un multi-ensemble d'éléments de P.
  • on veut trier P selon le nombre d’occurrences de ses éléments dans T, par ordre décroissant.


Après, pour paramétrer l'algorithme, on peut introduire des bornes, par exemple le nombre d'occurrences minimales.

Est-ce qu'en procédant ainsi on s'éloigne du problème concret ? Ou bien au contraire on a explicité la question cachée derrière la motivation matérielle ?
Avec le décodage évident :
  • C pour catalogue
  • P pour paniers
  • T pour transactions
Avatar de stendhal666 stendhal666 - Membre chevronné https://www.developpez.com
le 27/12/2015 à 17:12
Citation Envoyé par SpiceGuid;bt1666
J'ai envie d'une formulation un peu plus générale.

Par exemple:
  • soit C un ensemble et soit P=℘(C).
  • soit T un multi-ensemble d'éléments P.
  • on veut trier P selon le nombre d’occurrences de ses éléments dans T, par ordre décroissant.


Après, pour paramétrer l'algorithme, on peut introduire des bornes, par exemple le nombre d'occurrences minimales.

Est-ce qu'en procédant ainsi on s'éloigne du problème concret ? Ou bien au contraire on a explicité la question cachée derrière la motivation matérielle ?
Avec le décodage évident :
  • C pour catalogue
  • P pour paniers
  • T pour transactions

Merci pour ce commentaire judicieux qui m'oblige à éclaircir la notion!
  • soit C un ensemble: le catalogue, pourquoi pas!
  • soit P=℘(C): là nous divergeons; l'ensemble des parties de l'ensemble est nécessaire lors d'une approche "force brute" pour générer des candidats au titre d'association fréquente, mais il n'est pas nécessaire pour définir le problème.
  • soit T un multi-ensemble de P: nous divergeons encore; les transactions dans la recherche d'associations fréquentes ne sont pas un multi-ensemble mais un ensemble simple et de plus un sous-ensemble de C.


Je comprends l'intérêt de proposer une définition plus générale mais on y perd en l'occurrence toutes les possibilités d'optimisation présentes dans les algorithmes a priori et fp-growth (ce dernier étant celui que je présente) dont l'heuristique permet d'éviter la génération de ℘(C).

La succession tri de ℘(C) - borne de fréquence minimale a une complexité assez terrible: 2|C|+1 pour la génération de ℘(C), |C|log|C| pour le tri et encore |C| pour la borne...
Contacter le responsable de la rubrique C++