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

Un billet de stendhal666

Le 11 janvier 2016, par stendhal666

0PARTAGES

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:

Code C++ :

Sélectionner tout

1
2
3
4
5
6
7
8
9
template <class Item> 
std::vector<Item> fptree<Item>::ascendTree(fpnode<Item>* bottom) { // bottom est un des noeuds contenant l'élément 
  std::vector<Item> 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.

Code C++ :

Sélectionner tout

1
2
3
4
5
6
7
8
9
10
11
template <class Item> 
std::vector<std::pair<std::vector<Item>, int>> fptree<Item>::getConditionalPatterns(const Item& i) { 
  std::vector<std::pair<std::vector<Item>, int>> res; // un vector de paires <séquence, fréquence> 
  auto bnode = headerTable[i].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:

Code C++ :

Sélectionner tout

1
2
3
4
5
6
7
8
template <class Item> 
bool fptree<Item>::buildTree(const std::vector<std::pair<std::vector<Item>, 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:

Code C++ :

Sélectionner tout

1
2
3
4
5
6
7
8
template <class Item> 
bool fptree<Item>::buildTree(const std::vector<std::vector<Item>>& 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:

Code C++ :

Sélectionner tout

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
template <class Item> 
void fptree<Item>::mineTree(std::vector<std::pair<std::vector<Item>, int>>& patterns, const std::vector<Item>& 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<Item> 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[a].count < headerTable[b].count;  
    }); 
  
  // get conditional patterns and create their fptrees 
  for (auto& k : keys) { 
    std::vector<Item> nprefix = prefix; 
    nprefix.push_back(k); // augment prefix with new key 
    patterns.push_back(std::make_pair(nprefix, headerTable[k].count)); 
  
    fptree<Item> 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

Code C++ :

Sélectionner tout

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#ifndef __FP_FPTREE_H 
#define __FP_TREE_H 
  
#include "fpnode.hpp" 
#include <algorithm> 
#include <unordered_map> 
#include <vector> 
  
template <class Item> 
class fptree { 
public: 
  // les données de l'arbre 
  std::unordered_map<Item, fpnode<Item>> headerTable; 
  fpnode<Item>* root; 
  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();    
}; 
  
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()) { 
      kv->second.count += freq; 
    } 
    else headerTable[item].count = freq; 
  } 
} 
  
template <class Item> 
void fptree<Item>::deleteInfrequentItems() { 
  std::vector<Item> 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 <class Item> 
void fptree<Item>::scanSequenceIntoTree(std::vector<Item>& input, int freq) { 
  input.erase(std::remove_if(std::begin(input),  
			     std::end(input),  
			     [&](const Item& i) { return headerTable[i].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[a].count == headerTable[b].count ?  
		std::less<Item>()(a, b) :  
		headerTable[a].count > headerTable[b].count; 
	    }); // most frequent elements first 
  fpnode<Item>* n = root; 
  for (auto& i : input) { 
    auto pair = n->addChild(i, freq); 
    n = pair.first; 
    if (pair.second) { 
      n->cousins = headerTable[i].cousins; 
      headerTable[i].cousins = n; 
    } 
  } 
} 
  
template <class Item> 
std::vector<Item> fptree<Item>::ascendTree(fpnode<Item>* bottom) { 
  std::vector<Item> res; 
  while (bottom->parent != root) { 
    res.push_back(bottom->parent->label); 
    bottom = bottom->parent; 
  } 
  return res; 
} 
  
template <class Item> 
std::vector<std::pair<std::vector<Item>, int>> fptree<Item>::getConditionalPatterns(const Item& i) { 
  std::vector<std::pair<std::vector<Item>, int>> res; 
  auto bnode = headerTable[i].cousins; 
  for (;;) { 
    if (!bnode) break; 
    res.push_back(std::make_pair(ascendTree(bnode), bnode->count)); 
    bnode = bnode->cousins; 
  } 
  return res; 
} 
  
template <class Item> 
bool fptree<Item>::buildTree(const std::vector<std::pair<std::vector<Item>, int>>& input) { 
  for (auto& kv : input) 
    scanSequenceForFrequency(kv.first, kv.second); 
  for (auto kv : input) 
    scanSequenceIntoTree(kv.first, kv.second); 
  return root->children; 
} 
  
template <class Item> 
bool fptree<Item>::buildTree(const std::vector<std::vector<Item>>& input) { 
  for (auto& vi : input) 
    scanSequenceForFrequency(vi); 
  for (auto vi : input)  
    scanSequenceIntoTree(vi); 
  return root->children; 
} 
  
template <class Item> 
void fptree<Item>::mineTree(std::vector<std::pair<std::vector<Item>, int>>& patterns, const std::vector<Item>& prefix) { 
  
  // retrieve items with mininum support  
  deleteInfrequentItems(); 
  std::vector<Item> 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[a].count < headerTable[b].count;  
    }); 
  
  // get conditional patterns and create their fptrees 
  for (auto& k : keys) { 
    std::vector<Item> nprefix = prefix; 
    nprefix.push_back(k); // augment prefix with new key 
    patterns.push_back(std::make_pair(nprefix, headerTable[k].count)); 
  
    fptree<Item> cfpt(minsup); // recursively build new fptree 
    bool items_left = cfpt.buildTree(getConditionalPatterns(k)); 
    if (items_left) 
      cfpt.mineTree(patterns, nprefix); 
  } 
} 
  
template <class Item> 
void fptree<Item>::show() { 
  root->show(0); 
} 
  
#endif

-fpnode.h

Code C++ :

Sélectionner tout

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#ifndef __FP_NODE_H 
#define __FP_NODE_H 
  
#include <iostream> 
  
template <class Item> 
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<fpnode*, bool> 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<Item>* n = children; n; n=n->brothers) { 
      n->show(offset+2); 
    } 
  } 
  
}; 
  
template <class Item> 
void deleteNode(fpnode<Item>* n) { 
  if (n->children) { 
    for (fpnode<Item>* ch = n->children; ch; ch = ch->brothers) { 
      deleteNode(ch); 
    } 
  } 
  delete n; 
} 
  
#endif

Une erreur dans cette actualité ? Signalez-nous-la !

Votre nom : Votre e-mail :

Décrivez l'erreur que vous souhaitez porter à notre connaissance :

Identifiez-vous

Créer un compte

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

Un billet de stendhal666

Identifiant
Mot de passe

Mot de passe oublié ?

Identifiez-vous

Créer un compte

Détection des associations fréquentes en C++ - deuxième partie Un billet de stendhal666

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

Un billet de stendhal666