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++.