Extraction des itemsets fermés fréquents sur un cluster de PCs

Extraction parallèle des itemsets fermés fréquents L’algorithme EXPERT utilise une structure de données appelée Itemset-Trie proposée par Slimani et al [39]. Le Itemset-Trie est particulièrement adapté au contexte de datamining interactif dans la mesure sa construction est indépendante du support. De plus, il a l’avantage, par rapport à FP-Tree d’offrir un meilleur taux de compression pour les données denses. L’extraction des itemsets fermés fréquents se fait selon l’approche Diviserpour-Régner en utilisant les optimisations apportées à l’algorithme Closet .

Notions de base

Dans ce qui suit, nous donnons quelques définitions et des résultats provenant de la théorie des concepts formels qui ont été utilisés dans notre algorithme [32, 39]. Definition 1 (Itemset fermés fréquents) : Un itemset X est dit fermé si et seulement si il n’existe aucun itemset Y tel que support(X)=support(Y) et Y ⊂ X. Autrement dit un Extraction des itemsets fermés fréquents sur un cluster de PCs  itemset est fermé si tous ses sur-ensembles ont un support inférieur au sien. Les itemets fermés dont le support est supérieur au support minimal sont dits fermés fréquents. Definition 2 (Trie conditionnel) : Le Trie conditionnel d’un k-itemset Y est l’ensemble des transactions de la base de données contenant Y. De manière formelle, une transaction t = (T ID,X) appartient a un Trie conditionnel de Y si et seulement Y ⊆ X. Definition 3 (liste globale et liste conditionnelle) : La liste globale est constituée de l’ensemble des items ayant un support supérieur ou égal au support minimal. La liste conditionnelle d’un k-itemset est constituée des items de son Trie conditionnel ayant un support supérieur ou égal au support minimal. Dans ces listes, les items sont classés par ordre lexicographique et accompagnés chacun de son support. Propriétés 1 (Fusion d’items [32]) : Soit X un itemset fréquent. Si chaque transaction contenant X contient aussi Y mais pas un sur-ensemble de Y, alors X ∪ Y forme un ensemble fermé fréquent et il n’est pas nécessaire de chercher un itemset contenant X et non Y. Propriétés 2 (Elagage de sous-ensembles d’itemsets [32]) : Soit X un itemset fréquent. Si X est un sous-ensemble d’un itemset fermé fréquent Y déja trouvé et support(X)=support(Y), alors X et tous ses descendants (itemset dont X est le préfixe) ne peuvent pas être des itemsets fermés fréquents et doivent être omis de l’arbre d’énumération. FIG. 4.1 – Exemple d’un contexte d’extraction avec l’itemset-Trie associé

L’algorithme

EXPERT (EXtraction Parallèle d’itEmsets feRmés fréquenTs) Dans l’algorithme EXPERT les processeurs utilisent un itemset-Trie commun qui contient toutes les transactions de la base de données. Ainsi, il n’est pas nécessaire que les processeurs communiquent pour échanger des informations concernant un item de la base. Puisque les listes peuvent être traitées de manière indépendante, une fois que le Trie est construit, la liste globale sera partitionnée et chaque processeur traitera la liste qui lui est affectée. Considérons le contexte d’extraction a droite de la figure 4.1. Chaque processeur construit à partir de ce contexte un itemset-Trie représenté à gauche de la figure 4.1. Si nous disposons de deux nœuds, l’extraction des itemsets fermés fréquents avec minsup=1 se fait de la manière suivante sur le nœud 1 : Après la construction du Trie, la liste des 1-itemsets obtenue est L = ha/3;b/3; c/4; f /4;m/3; p/3i. Le partitionnement de cette liste selon l’algorithme Round Robin donne une nouvelle liste L1 = ha/3; c/4;m/3i qui sera traitée au niveau du nœud 1. En appliquant le paradigme Diviser-pour-Régner, nous cherchons d’abord tous les itemsets fermés fréquents contenant a puis ceux contenant c mais ne contenant ni a ni b et enfin ceux contenant m mais ne contenant ni a, ni b, ni f . 1. Recherche des itemsets fermés fréquents contenant a : Elle commence par la construction du Trie conditionnel de a et de sa liste conditionnelle La = hb/1; c/3; f /3;m/3; p/2i. nous constatons que c, f et m ont le même support que a. D’aprés le principe de la fusion d’items ac f m/3 constitue un itemset fermé fréquent et les autres itemsets fermés fréquents de La seront des surensembles de celui-ci. Les items c, f et m sont ensuite supprimés de La et puisque celle-ci n’est pas vide on continue en construisant respectivement le Trie conditionnel de l’itemset ac f mp et celui de ac f mb ainsi que les listes conditionnelles associées. Finalement nous obtenons Lac f mp = h0/i, Lac f mb = h0/i d’ou l’on extrait les itemsets fermés fréquents ac f mp/2 et ac f mb/1. 2. Recherche des itemsets fermés fréquents contenant c mais ne contenant ni a, ni b : On constate que dans la liste conditionnelle de Lc = ha/3;b/2; f /3;m/3; p/3i aucun item4 n’a un support égal à celui de c d’ou c/3 est un itemset fermé fréquent. Puisque Lc n’est pas vide, nous continuons avec les listes Lcp, Lcm et Lc f .