Détection des associations fréquentes en C++ - deuxième partie

Un billet de stendhal666

Dans le billet précédent, vous avez vu comment construire l'arbre des associations fréquentes, ou fptree. Vous verrez dans celui-ci comment utiliser l'arbre pour déduire les associations fréquentes, sans plus retourner à la base de données initiale. Vous terminerez ainsi de découvrir cette première implémentation naïve et "pythonesque" de l'algorithme. Dans les prochains billets, il sera temps de la raffiner pour arriver à un résultat plus conforme à l'esprit du C++ et de ses standards récents.

Extraction des associations fréquentes, le principe
Comme je le mentionnais en introduction, l'extraction des associations fréquentes, quoique facile à encoder, est plus difficile à concevoir. Elle repose sur le principe suivant:

• on commence par placer les éléments fréquents de l'arbre, qui sont contenus dans la table des éléments, parmi les associations fréquentes. En effet, ils constituent trivialement des associations fréquentes;
  
• pour chacun de ces éléments, en commençant par le moins fréquent, on va construire récursivement un arbre de fréquence conditionnel. Comment est-ce que cela fonctionne?
  

L'arbre de fréquence conditionnel
L'arbre de fréquence conditionnel d'un élément de l'arbre initial est généré à partir des séquences qui partent de chaque noeud contenant cet élément. La séquence commence à partir du parent de ce noeud et s'arrête au dernier noeud avant la racine. Voici la fonction qui recherche, pour un noeud, la séquence ascendante en question:

template
std::vector fptree::ascendTree(fpnode* bottom) { // bottom est un des noeuds contenant l'élément
std::vector res; // dont on veut créer l'arbre conditionnel
while (bottom->parent != root) {
res.push_back(bottom->parent->label);
bottom = bottom->parent;
}
return res;
}

Voici maintenant la fonction qui produit l'ensemble des séquences ascendantes. Une fréquence est attribuée à chacune des séquences: elle correspond à la fréquence du noeud dont on part.

template
std::vector, int>> fptree::getConditionalPatterns(const Item& i) {
std::vector, int>> res; // un vector de paires
auto bnode = headerTable.cousins; // à partir de la table des éléments
for (;;) { // on parcourt tous les noeuds cousins
if (!bnode) break;
res.push_back(std::make_pair(ascendTree(bnode), bnode->count));
bnode = bnode->cousins;
}
return res;
}

Redondance, redondance...
La construction de l'arbre conditionnel est désormais semblable à la construction de l'arbre initial, à la nuance près que les séquences sont annotées d'une fréquence:
template
bool fptree::buildTree(const std::vector, int>>& input) {
for (auto& kv : input)
scanSequenceForFrequency(kv.first, kv.second);
for (auto kv : input)
scanSequenceIntoTree(kv.first, kv.second);
return root->children;
}

Malgré les similitudes, on ne peut pas échapper à l'écriture d'une surcharge, à cause de mauvais choix initiaux; comparez la fonction au-dessus et la fonction en-dessous, utilisée pour créer l'arbre initial:
template
bool fptree::buildTree(const std::vector>& input) {
for (auto& vi : input)
scanSequenceForFrequency(vi);
for (auto vi : input)
scanSequenceIntoTree(vi);
return root->children; // si la racine a un enfant, l'arbre n'est pas vide
}

On dirait du copier-coller, hein? Le père de tous les anti-patterns? hé bien oui.

Des arbres conditionnels aux associations fréquentes
Vous passerez des arbres conditionnels aux associations fréquentes en construisant des préfixes. Lors du premier passage dans l'arbre, le préfixe est vide. Au deuxième passage, le préfixe est constitué de l'élément fréquent dont vous avez construit l'arbre conditionnel. Au troisième passage, on ajoute l'élément fréquent de l'arbre conditionnel dont vous construisez l'arbre conditionnel, et ainsi de suite, jusqu'à ce que l'arbre conditionnel soit vide. Le préfixe constitue une association fréquente: en effet, l'élément n du préfixe est fréquent dans l'arbre conditionnel de l'élément n-1 du préfixe.

Pour explorer correctement l'ensemble de l'arbre, vous commencez l'extraction par l'élément le moins fréquent, dont les noeuds se trouvent le plus loin de la racine. Voici la fonction mineTree, qui extraie les associations fréquentes, et que vous pouvez désormais comprendre sans encombre:
template
void fptree::mineTree(std::vector, int>>& patterns, const std::vector& prefix) {

// retrieve items with mininum support
deleteInfrequentItems(); // retire de la headerTable (table des éléments) les éléments qui ne sont pas assez fréquents
std::vector keys;
for (auto& kv : headerTable) keys.push_back(kv.first);

// sort keys in increasing order of frequency
std::sort(std::begin(keys), std::end(keys), [&](const Item& a, const Item& b) {
return headerTable.count < headerTable.count;
});

// get conditional patterns and create their fptrees
for (auto& k : keys) {
std::vector nprefix = prefix;
nprefix.push_back(k); // augment prefix with new key
patterns.push_back(std::make_pair(nprefix, headerTable.count));

fptree cfpt(minsup); // recursively build new fptree
bool items_left = cfpt.buildTree(getConditionalPatterns(k));
if (items_left)
cfpt.mineTree(patterns, nprefix); // recursively mine the new fptree
}
}

Ouf!
Nous en avons terminé avec l'implémentation naïve. Maintenant nous allons pouvoir commencer le vrai travail, raffiner l'implémentation jusqu'à ce qu'elle soit agréable à utiliser et aussi performante et extensible que possible! Nous nous y attellerons dans le prochain billet!

A vous de jouer

• Quels sont, à votre avis, les fonctions indispensables qui constitueront l'interface minimale de notre structure de données?
  
• Faut-il réduire une interface au minimum de fonctions requises pour exploiter la structure de données?
  

Pour expérimenter, voici in extenso les fichiers source:
- fptree.h
#ifndef __FP_FPTREE_H
#define __FP_TREE_H

#include "fpnode.hpp"
#include
#include
#include

template
class fptree {
public:
// les données de l'arbre
std::unordered_map> headerTable;
fpnode* root;
int minsup; // la fréquence minimale à respecter

//constructeur / destructeur
fptree(int sup) : root(new fpnode()), minsup(sup) {}
~fptree() { deleteNode(root); }

// les fonctions pour construire la fp-tree
bool buildTree(const std::vector>& input);
bool buildTree(const std::vector, int>>& input);
void scanSequenceForFrequency(const std::vector& input, int freq = 1);
void deleteInfrequentItems();
void scanSequenceIntoTree(std::vector& input, int freq = 1);

//les fonctions pour chercher les associations fréquentes
void mineTree(std::vector, int>>& patterns, const std::vector& prefix);
std::vector ascendTree(fpnode* bottom);
std::vector, int>> getConditionalPatterns(const Item& i);

void show();
};

template
void fptree::scanSequenceForFrequency(const std::vector& input, int freq) {
for (auto& item : input) {
auto kv = headerTable.find(item);
if (kv != headerTable.end()) {
kv->second.count += freq;
}
else headerTable.count = freq;
}
}

template
void fptree::deleteInfrequentItems() {
std::vector to_erase;
for (auto& kv : headerTable) {
if (kv.second.count < minsup) to_erase.push_back(kv.first);
}
for (auto& i : to_erase) {
headerTable.erase(i);
}
}

template
void fptree::scanSequenceIntoTree(std::vector& input, int freq) {
input.erase(std::remove_if(std::begin(input),
std::end(input),
[&](const Item& i) { return headerTable.count < minsup; }),
std::end(input)); // delete elements under minimal freq support
std::sort(std::begin(input),
std::end(input),
[&](const Item& a, const Item& b) {
return headerTable.count == headerTable.count ?
std::less()(a, b) :
headerTable.count > headerTable.count;
}); // most frequent elements first
fpnode* n = root;
for (auto& i : input) {
auto pair = n->addChild(i, freq);
n = pair.first;
if (pair.second) {
n->cousins = headerTable.cousins;
headerTable.cousins = n;
}
}
}

template
std::vector fptree::ascendTree(fpnode* bottom) {
std::vector res;
while (bottom->parent != root) {
res.push_back(bottom->parent->label);
bottom = bottom->parent;
}
return res;
}

template
std::vector, int>> fptree::getConditionalPatterns(const Item& i) {
std::vector, int>> res;
auto bnode = headerTable.cousins;
for (;;) {
if (!bnode) break;
res.push_back(std::make_pair(ascendTree(bnode), bnode->count));
bnode = bnode->cousins;
}
return res;
}

template
bool fptree::buildTree(const std::vector, int>>& input) {
for (auto& kv : input)
scanSequenceForFrequency(kv.first, kv.second);
for (auto kv : input)
scanSequenceIntoTree(kv.first, kv.second);
return root->children;
}

template
bool fptree::buildTree(const std::vector>& input) {
for (auto& vi : input)
scanSequenceForFrequency(vi);
for (auto vi : input)
scanSequenceIntoTree(vi);
return root->children;
}

template
void fptree::mineTree(std::vector, int>>& patterns, const std::vector& prefix) {

// retrieve items with mininum support
deleteInfrequentItems();
std::vector keys;
for (auto& kv : headerTable) keys.push_back(kv.first);

// sort in increasing order of frequency
std::sort(std::begin(keys), std::end(keys), [&](const Item& a, const Item& b) {
return headerTable.count < headerTable.count;
});

// get conditional patterns and create their fptrees
for (auto& k : keys) {
std::vector nprefix = prefix;
nprefix.push_back(k); // augment prefix with new key
patterns.push_back(std::make_pair(nprefix, headerTable.count));

fptree cfpt(minsup); // recursively build new fptree
bool items_left = cfpt.buildTree(getConditionalPatterns(k));
if (items_left)
cfpt.mineTree(patterns, nprefix);
}
}

template
void fptree::show() {
root->show(0);
}

#endif

-fpnode.h
#ifndef __FP_NODE_H
#define __FP_NODE_H

#include

template
struct fpnode {
Item label;
int count;
fpnode *parent, *brothers, *children, *cousins;

fpnode() : label{}, count(0), parent(nullptr), brothers(nullptr), children(nullptr), cousins(nullptr) {};
fpnode(fpnode* father, const Item& name, int freq, fpnode* bro) : label(name), count(freq), parent(father), brothers(bro), children(nullptr), cousins(nullptr) {}

fpnode* hasChild(const Item& name) { // return the name named child if found, nullptr otherwise
fpnode* n = children;
while (n) {
if (n->label == name) break;
n = n->brothers;
}
return n;
}

std::pair addChild(const Item& name, int freq=0) {
fpnode* n = hasChild(name);
if (!n) {
children = new fpnode(this, name, freq, children);
return std::make_pair(children, true);
}
else n->count += freq;
return std::make_pair(n, false);
}

void show(int offset) {
std::cout << std::string(offset, ' ') << label << " - " << count << std::endl;
for (fpnode* n = children; n; n=n->brothers) {
n->show(offset+2);
}
}

};

template
void deleteNode(fpnode* n) {
if (n->children) {
for (fpnode* ch = n->children; ch; ch = ch->brothers) {
deleteNode(ch);
}
}
delete n;
}

#endif

Vous avez lu gratuitement 651 articles depuis plus d'un an.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.