Func' programming - un blog homéopathique

Comme je l'indiquais dans le billet précédent, je propose maintenant une implémentation naïve, reprise presqu'exactement d'une implémentation en Python, de l'algorithme de détection des associations fréquentes centré autour d'une structure de donnée appelée frequent pattern tree, ou arbre des associations fréquentes. Il peut être utile de relire la présentation de l'algorithme

Une implémentation naïve
Une implémentation en Python se ressent souvent de l'utilisation de ce langage pour créer des prototypes: plutôt que de chercher d'emblée à écrire une librairie bien finie qu'on pourra utiliser sans risque dans des programmes plus vastes, on cherche à mettre au point rapidement quelques briques logicielles à confronter à des données de test. Ni la performance, ni la sûreté ne sont recherchées prioritairement mais plutôt la simplicité et la réutilisation de la vaste librairie standard de ce langage "piles incluses".

Pour générer quelques données d'associations fréquentes, on fera donc une liste de listes; en C++ il faut ajouter un type mais grâce aux nouvelles std::initializer_list de C++11, on a des possibilités semblables:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
  std::vector<std::vector<std::string>> bseq = // nos données de test
    {
      {"r", "z", "h", "j", "p" },
      {"z", "y", "x", "w", "v", "u", "t", "s" },
      {"z"},
      {"r", "x", "n", "o", "s"},
      {"y", "r", "x", "z", "q", "t", "p"},
      {"y", "z", "x", "e", "q", "s", "t", "m"}
    };

Une interface naïve
L'interface de notre classe FP-Tree, naïvement, est conçue pour épouser la forme des données de test; pour pousser la ressemblance avec Python, l'encapsulation des données est laissée de côté...

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class Item>
class fptree {
public:
  // les données de l'arbre
  std::unordered_map<Item, fpnode<Item>> headerTable;
  fpnode<Item>* root; // la classe fpnode sera définie plus loin
  int minsup; // la fréquence minimale à respecter
 
  //constructeur / destructeur
  fptree(int sup) : root(new fpnode<Item>()), minsup(sup) {}
  ~fptree() { deleteNode(root);  }
 
  // les fonctions pour construire la fp-tree
  bool buildTree(const std::vector<std::vector<Item>>& input);
  bool buildTree(const std::vector<std::pair<std::vector<Item>, int>>& input);
  void scanSequenceForFrequency(const std::vector<Item>& input, int freq = 1);
  void deleteInfrequentItems();
  void scanSequenceIntoTree(std::vector<Item>& input, int freq = 1);
 
  //les fonctions pour chercher les associations fréquentes
  void mineTree(std::vector<std::pair<std::vector<Item>, int>>& patterns, const std::vector<Item>& prefix);
  std::vector<Item> ascendTree(fpnode<Item>* bottom);
  std::vector<std::pair<std::vector<Item>, int>> getConditionalPatterns(const Item& i);
 
  void show();   
};

Sans analyser trop précisément cette interfacte "pythonesque", plusieurs choses sautent aux yeux:
- pas d'encapsulation des données, impossible de changer quoique ce soit une fois la librairie offerte au vaste monde...
- une interface beaucoup trop grosse. Impossible de s'y repérer aisément, de la comprendre facilement
- beaucoup de structures de données figées; même s'il est devenu beaucoup plus facile en C++11 d'itérer sur un conteneur et donc de construire un conteneur d'un autre type avec, on sent que l'interface sera contraignante dès que le scénario retenu pour prototyper la librairie ne sera pas respecté

Pour l'instant, tout va bien
Malgré tous ces défauts, pour chercher les associations fréquentes dans notre scénario idéal, il suffit de faire:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
fptree<std::string> fpt(3); // fréquent = au moins trois occurrences
fpt.buildTree(bseq); // bseq = les données définies à l'instant
std::vector<std::pair<std::vector<std::string>, int>> fpatterns; // la structure pour accueillir les résultats
fpt.mineTree(fpatterns, std::vector<std::string>()); // on lance l'analyse des associations fréquentes

Le résultat est le suivant:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
// toutes les associations apparaissant plus de trois fois, avec leur nombre d'occurrences
s : 3 // pour être précis, c'est l'association d'un élément et de l'élément nul
s x : 3
t : 3
t z : 3
t z x : 3
t x : 3
y : 3
y z : 3
y z t : 3
y z x : 3
y z x t : 3
y x : 3
y x t : 3
y t : 3
r : 3
x : 4
x z : 3
z : 5

La fonction show permet de visualiser l'arbre, même si d'évidence il faudrait faire mieux:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 - 0 // la racine
  x - 1 // plus la ligne est indentée, plus l'élément est loin de la racine
    r - 1
      s - 1
  z - 5
    x - 3
      r - 1
        t - 1
          y - 1
      s - 2
        t - 2
          y - 2
    r - 1

Un arbre familial
Pour rentrer un peu plus avant dans l'implémentation, il faut présenter les noeuds de l'arbre. Comme l'arbre s'appelle fptree, les noeuds s'appellent fpnode:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template <class Item>
struct fpnode {
  Item label;
  int count; // la fréquence
  fpnode *parent, *brothers, *children, *cousins; // toute la famille
(...)
};

Chaque noeud a:
- un parent;
- des enfants (children): en fait le pointeur pointe sur l'aîné des enfants; pour retrouver les autres enfants, il faut suivre le pointeur qui part de l'aîné vers ses frères (brothers);
- des frères, donc;
- des cousins: ce sont les autres éléments de l'arbre qui ont le même label.

Ajouter une séquence d'éléments à l'arbre
Comme je l'expliquais dans le billet précédent, il y a deux grandes étapes dans la construction d'une FP-Tree. La première consiste à parcourir tous les éléments de toutes les séquences pour déterminer leur fréquence. Il n'y a pas de difficulté particulière:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
template <class Item>
void fptree<Item>::scanSequenceForFrequency(const std::vector<Item>& input, int freq) {
  for (auto& item : input) {
    auto kv = headerTable.find(item);
    if (kv != headerTable.end()) { // si l'élément est déjà connu
      kv->second.count += freq; // on augmente sa fréquence
    }
    else headerTable[item].count = freq; // sinon on l'ajoute à la table
  }
}

Lorsque la fréquence de tous les éléments est connue, on peut ajouter des séquences à l'arbre proprement dit, à partir de la racine. C'est le rôle de la fonction:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
template <class Item>
void fptree<Item>::scanSequenceIntoTree(std::vector<Item>& input, int freq)

Ne seront ajoutés que les éléments fréquents; pour que l'arbre soit le plus compressé possible, il faut ajouter les éléments de la séquence en commençant par les plus fréquents:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
  input.erase(std::remove_if(std::begin(input), 
			     std::end(input), 
			     [&](const Item& i) { return headerTable[i].count < minsup; }),
	      std::end(input)); // enlever éléments non fréquents
  std::sort(std::begin(input), 
	    std::end(input), 
	    [&](const Item& a, const Item& b) {
	      return headerTable[a].count == headerTable[b].count ? 
		std::less<Item>()(a, b) : 
		headerTable[a].count > headerTable[b].count;
	    }); // les plus fréquents d'abord + clé secondaire

NB: j'ai utilisé de fonctions lambda, qui permettent de tirer parti des algorithmes de la bibliothèque standard de façon agréable. Ce sont des petites fonctions, familières dans un langage comme Python, définies localement et que l'on passe facilement en argument à d'autres fonctions.

On peut alors ajouter la séquence à l'arbre. L'ajout se fait à la racine, élément par élément, de façon récursive: si la racine a un enfant nommé comme le premier élément, on en augmente la fréquence; sinon, on crée un nouvel enfant pour la racine. Et on recommence l'opération sur le noeud obtenu.

Dès qu'on crée un nouveau noeud il faut l'indexer dans la headerTable: cette liste des cousins permettra de retrouver tous les chemins partant d'un des éléments vers la racine lorsque nous rechercherons les associations fréquentes.

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
  fpnode<Item>* n = root;
  for (auto& i : input) {
    auto pair = n->addChild(i, freq);
    n = pair.first;
    if (pair.second) { // pair second == true <=> un nouveau noeud a été créé
      n->cousins = headerTable[i].cousins; // on met à jour la table des éléments
      headerTable[i].cousins = n;

NB: deux "features" nouvelles de C++11 sont utilisées ici: auto pour déduire le type d'une variable à initialiser et la construction (for element : conteneur) { ... } qui équivaut à:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for (std::conteneur::iterator it = std::begin(conteneur); it != std::end(conteneur); ++it) {
  conteneur::value_type element = *it; 
  ... }

Pensez à utiliser auto& si vous voulez éviter de copier les élément du conteneur.

Une fois l'arbre construit, il devient possible de chercher les associations fréquentes sans plus retourner à la base de données. Nous verrons cela dans la prochain billet mais en attendant, joyeux Noël!

A suivre...