Etudes des principaux algorithmes de data mining PITA. Guillaume CaLas [email protected] 14-16 tue Voltaire 94270 Le Kremlin-Bi Spécialisation Sciences Cognitives et Informatique Avancée France Mots clés data mining, arbres de décision, clustering, Table des matiéres 1 Introduction Apprentissage supervisé 13 LL 112 Apprentissage non supervisé . . 121 122 123 Les arbres de décision Les réseaux de neurones Clustering Les regles associatives Sequence mining Apprentissage inerémental 2 Présentation des algorithmes 2.1 Induction d’arbres de décision 21.1 CART 2.12 IDB 23 CAS 214 OCL 215 SLIQ 2.1.6 SPRINT 2.2 Les réseaux de neurones 2.2.1 AdaBoost 2.2.2 Leams+ 2.3. Induction de regles associatives . . 2.3.1 Apriori 2.3.2. FP-Growth 2.3.3. Belat 2.34 SSDM 2.3.5 KDCI 24 Sequence mining 24.1 GSP 2.42 SPADE Algorithmes Références gles associatives, sequence mining, classification. Bue RYU RD exe ewwidlas 10 »Etudes des principaux algorithmes de data mining {Scta] Eprra 2009 1 Introduction Le Data mining est un domaine pluridisciplinaire permettant, & partir d'une trés importante quantité de données brutes, d’en extraite de fagon automatique ou semi-automatique des informations cachées, per- tinentes et inconnues auparavant en vue dune util sation industrielle ow opérationnelle de ce savoir, I peut également mettre en avant les associations et les tendances et done servir d’outil de prévisions au service de l’organe décisionnel. (On distingue le data mining supervisé qui sert essentiellement a la classification des données et Ie data mining non supervisé qui est utilisé dans la recherche d’associations ou de groupes d’individus. Le champ d’action du data mining s’étend du chargement et du nettoyage des données (ETL") dans, les bases de données, a la mise en forme des résultats, cen passant par le plus important : la classification et la mise en relation de différentes données 1.1 Apprentissage supervisé En sciences cognitives, 'apprentissage super- visé est une technique d'apprentissage automatique — plus connu sous le terme anglais de machine- Tearning — qui permet & une machine d’apprendre & réaliser des tiches & partir dune base d’apprentissage contenant des exemples déja traités. Chague élément (item) de Vensemble d'apprentissage (training set) tant un couple entrée-sortie. De part sa nature, ’apprentissage supervisé concerne essentiellement les méthodes de classification de don- nées (on connait lentrée et l'on veut déterminer la sortie) et de régression (on connait la sortie et 'on veut retrouver l’entrée). 1.1.1 Les arbres de décision Un arbre de décision est, comme son nom le suggére, un outil d'aide & la décision qui permet de répartir une population d’individus en groupes homo- génes selon des attributs discriminants en fonction Pun objectif fixés et connu. II permet d’émetire des ‘Extract, Transform and Load prédictions & partir des données connues sur le pro- bléme par réduction, niveau par niveau, du domaine des solutions CChaque nud inteme d'un arbre de décision porte sur un attribut discriminant des éléments a classifier qui permet de répartir ces éléments de fagon homogene entre les différents fils de ce naeud, Les branches liant tun neeud a ses fils représentent les valeurs discrimi- nantes de Pattribut du noeud. Et enfin, les feuilles dun arbre de décision sont ses prédictions concernant les, données a classifier. Crest une méthode qui a lavantage d’étre lisible pour les analystes et permet de déterminer les couples discriminants & partir d'un tres grand nombre 4 attributs et de valeurs. Les algorithmes d’apprentissage automatique que nous éndierons d la section 2.1 permettent Vinduction de ces arbres de décision. 1.1.2 Les réseaux de neurones Un réseau de neurones est un modéle de cal- cul dont le fonctionnement schématique est inspiré du fonctionnement des neurones biologique. Chaque neurone fait une somme pondérée de ses entrées (ou synapses) et retourne une valeur en fonction de sa fonction d’activation?. Cette valeur peut étre utilisée soit comme une des entrées d’une nouvelle couche de neurones, soit comme un résultat qu’il appartient & utilisateur d'interpréter (classe, résultat d'un calcul, ete) wh eon oO sonme pondise LP ein 3 ‘onctan ae Oy sity] fa —fon} 4 way seat Fic. | — Structure d'un neurone antficie. La phase d apprentissage d’un réseau de neurones 7Une fonction dactivation permet de déterminer l'état activation d’un neurone formel, BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 permet de régler le poids associé & chaque synapse entrée (on parle également de coefficient synap- tique). C'est un processus long qui doit étre réitéré & chaque modification structurelle de la base de données, traitée, 1.2 Apprentissage non supervisé ‘On parle d’apprentissage non supervisé lorsque Von cherche & extraire des informations nouvelles et originales d’un ensemble de données dont aucun attribut n'est plus important qu'un autre, Le résultat des algorithmes de data mining non supervisé doit étre analysé afin d’étre retenu pour un usage ou tout simplement rejeté. 1.2.1 Clustering Le clustering est une méthode statistique dana- lyse de données qui a pour but de regrouper un en- semble de données en différents groupes homogenes. Chaque sous-ensemble regroupe des éléments ayant des caractéristiques communes qui correspondent & des critéres de proximité Le but des algorithmes de clustering est done de minimiser la distance intra-classe (grappes d’éléments homogenes) et de maximiser la distance inter-classe afin dobtenir des sous-ensembles le plus di possible La mesure des distances est un élément prépondé~ rant pour la qualité de l'algorithme de clustering Cette classe dalgorithmes ne sera pas traitée dans le présent document. 1.2.2 Les régles associatives Les régles associatives sont des régles qui sont ex- traites dune base de données transactionnelles (item- set) et qui décrivent des associations entre certains éléments. Cette technique permet de faire ressortir les, associations entre les produits de base (les produits essentiels, ceux pour lesquels le client se déplace) et les produits complémentaires, ce qui permet de mettre en place des stratégies commerciales visant & accroitre les profits en favorisant, par exemple, les ventes com- plémentaires. Ces algorithmes permettent de résoudre des problémes dits de Frequemt Set Counting (FSC). 1.2.3 Sequence mining Le sequence mining conceme la détection de motifs dans les flux de données dont les valeurs sont délivrées par séquences, Cette technique est particuligrement utilisé en bio- logie pour l'analyse de genes et des protéines mais Egalement afin de faire du text mining, les phrases étant considérées comme des séquences ordonnées de mots. 1.3. Apprentissage incrémental Liapprentissage incrémental permet a une ma- chine d’ apprendre par ajout successif d’informations. Pour étre considéré comme tel, un systéme d’appren- tissage doit €tre capable @’apprentre de nouvelles informa- tions & partir de nouvelles données: — étre capable de se passer des données dorigine pour entrainer le nouveau classifieu — préscrver le savoir précédemment acq| €tre capable de reconnaitre de nouvelles classes indroduites dans les nouvelles données. 2. Présentation des algorithmes 2.1 Induction d’arbres de décision 2.1.1 CART Référence : [4] Date de publication : 1984 Auteur : Breiman Incrémental : non Description : CART (Classification And Regression Tree) construit un arbre de décision strictement binaire avec exactement deux branches pour chaque navud de décision. Lalgorithme partitionne l'ensemble d’en- trainement de fagon récursive selon la méthode diviser pour mieux régner’ 3Du latin Divide ut imperes, méthode de conception consistant a diviser un probleme de grande taille en plusieurs sous-problemes analogues, 'étape de subdivision BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 Pour chaque neeud de décision, CART fait une recherche exhaustive sur tous les attributs et valeurs de séparation disponibles et sélectionne la séparation s qui maximise le critére suivant au nocud ¢ Cant Chass O(s|1)=2P:Pe YP |PIte)— PUte)) (1) ot S = ensemble d’entrainement it, = fils gauche du noeud ¢ te = fils droit du nceud r _ Card(t1) % = Cara\S) _ Card(te) Pe = Card(S) ' _ Card( PU.) = Cardi Card (classe j € 4 Phim) = eretcasse Ste) Card(0) Dans le cas oi Iattribut testé porte sur des valeurs continues, CART peut identifier un ensemble fini de valeurs possibles. Cependant, il est préférable que Putilisateur diserétise les variables continues afin de mieux controler la génération de I'arbre et de le rendre plus robuste. Lalgorithme s’arréte lorsque un des cas darrét suivant est rencontré = le nceud est pur, ie. tous les éléments du neeud appartiennent a la méme classe ; tous les attributs ont été utilisés précédemment ; la profondeur de l’arbre & atteint la valeur maxi- ‘male définie par l'utilisateur la taille du noeud est inférieure a la taille mini- male définie par l'utilisateur a taille d'un des fils qui résulterait de la sépara- tion optimale est inféricure & la taille minimale définie par Mutilisateur. CART n'est pas adapté pour travailler sur de rds grandes quantités denregistrements (@ cause de Vexhaustivité de ses recherches de valeurs de sépa- ration optimales) et bien qu’ayant des performances ‘ant appliqué récursivement honorables, il est sujet au sur-apprentissage. Le post Glagage de l'arbre de décision généré est donc forte- ment conseillée. 2.1.2 ID3 Référence : [11] Date de publication : 1986 Auteur : Quinlan Incrémental ; par extension (cf. ID4[13], IDS et IDSR{16]) Algorithme : figure I page 10 Description : 1D3 construit un arbre de décision de facon récursive en choisissant Fattribut qui maxime Ie gain (3) d'information selon l’entropie de Shannon (2). Cet algorithme fonctionne exclusivement avec des attributs catégoriques et un neud est eréé pour chaque valeur des attributs sélectionnés. IDB est un algorithme basique facile & implémen- ter dont la premigre fonction est de remplacer les experts dans la construction d’un arbre de décision. Cependant, les arbres de décisions ne sont ni robustes, ni compacts ce qui les rends inadaptés aux grosses bases de données. Entropie de Shannon S| E(S) =— Y pli)log: pli) @ oi p() est la probabilité d’avoir un élément de earac- téristique j dans l'ensemble S Gain(s,a) = (8) (5! isi *E(Sy)) @) oi S est un ensemble d’entrainement, A est l'atribut cible, S; le sous-ensemble des éléments dont la valeur de Pattribut A est v, [S,| = nombre d’éléments de S, et || =nombre d’ éléments de 5. 243 C45 Référence : [12] Date de publication : 1993 Auteur : Quinlan Inerémental : non Description : C4.5 est une amélioration d'1D3 qui permet de travailler la fois avec des données diserétes BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 et des données continues. I permet également de travailler avec des valeurs d'attribut absentes, Enfin, C4.5 élague l'arbre construit afin de suppri- mer les regles inutiles et de rendre arbre plus com- pact. L’algorithme C5, qui est une solution commer- ciale, est une amélioration supplémentaire de C4.5, 214 OC1 Référence : [8] Date de publication : 1993, Auteurs : Murphy, Kasi Incrémental : non Algorithme : figures 5 et 6 page 12 Description : OCI (Oblique Classifier 1) est une ex- tension de CART-LC (CART avec des Combinaisons, Linéaires). Mais contrairement & CART, dune part, OCI utilise le hasard pour trouver le meilleur hyper- plan de séparation de ensemble dentrainement, et autre part, Vhyperplan de séparation peut ne pas, etre parallele aux axes, De ce fait, Valgorithme peut générer une multitude d'arbres de décision ce qui peut permettre de réaliser un k-decision-tree classifieur dont le résultat de la classification résulte de la majo- Tité des votes des k arbres de décision. izberg, Beigel Afin de ne pas perdre de performance par rapport Aun classifieur classique a arbre de décision, OCI utilise une séparation oblique uniquement quand cela améliore les performances par rapport a la meilleure séparation paralléle a un axe, Pour trouver le meilleur hyperplan Valgorithme travaille attribut par attribut. Il considére (d-1) attributs comme des constantes et va émettre m (le nombre cexemples) contraintes sur V'attribut restant et dé- terminer la valeur qui en respecte le plus, Pour cela Palgorithme utilise les équations suivantes : I) «4 Xin ott xjq est la valeur de Tattribut m de exemple j, dm est le coefficient réel de attribut m de Phyperplan recherché et V; est détinit par 4 Llary) saa vi «) Pour mesurer Pimpureté de la séparation, OC1 peut utiliser n’importe quelle mesure d’impureté mais e Gain (3), Gini Index (7), et Twoing Rule (6) ob- tiennent les meilleures performances. mo (8-08) (El Enfin, en ce qui conceme I’élagage de I'arbre de décision obtenu, nimporte quel algorithme prévu a cet effet est utilisable et obtient de bons résultats R TT O} 2.1.5 SLIQ Référence : [1] Date de publication : 1996 Auteurs : Metha, Agrawal, Rissanen Incrémental : oui, par extension Algorithme : figures 2,3 et 4 page 10 Description : SLIQ (Supervised Learning In Quest) est un algorithme performant capable de traiter des at- tributs numériques et catégoriques. L’algorithme construit un arbre binaire de décision de fagon récursive en uti- lisant le coefficient de Gini (7) comme critére pour la sélection du meilleur attribut et de la valeur associée Coefficient de Gini sini(S) o ot pe est la fréquence relative de la classe c dans ensemble 5 contenant m classes. Si S est pure, gini(S) = 0. Le coefficient de Gini pour une partition de $ en deux ensembles Sp et Se selon le critéte de séparation + est défini par la relation [Srl is} Sel Bini(S. Das = Fey Bin S) + Ge gintSe) (8) Afin de gagner en performances, Valgorithme tri les attributs sur leurs valeurs (quand c*est possible) et utilise une liste triée par attribut associée A un histo- gramme pour chaque neeud ce qui lui permet de calcu ler trés rapidement le coefficient de Gini, cependant, ces listes doivent étre stockés dans la mémoire vive et Icur taille dépend directement du nombre éléments, BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 dans la base de données ce qui peut constituer une limitation physique Pour les attributs catégoriques & large cardina- 1ité on utilise un algorithme glouton pour trouver La meilleure séparation. Enfin, SLIQ utilise un algorithme basé sur le principe de la Longueur Minimale de Description (Mi- rnimum Description Length, MDL) pour faite I’élagage final 2.16 SPRINT Référence : [14] Date de publication : 1996 Auteurs : Shafer, Mehta, Agrawal Incrémental : non Description : SPRINT est un algorithme basé que SLIQ qui a été coneu afin de remédier au principal probleme de SLIQ : son utilisation excessive de la mémoire, Il peut également étre facilement sérial afin d’augmenter ses performances. La différence entre les deux algorithmes réside dans le fait que SPRINT ne conserve en mémoire que la pattie utilisée des listes triges alors que SLIQ conserve la liste entitre en mémoire, 2.2 Les réseaux de neurones 2.2.1 AdaBoost Référence : [6] Date de publication : 1997 Auteurs : Freund, Schapire Incrémental : oui Algorithme : figure 7 page 13 Description ; AdaBoost est un méta-algorithme qui permet de booster les performances d'un classifieur A base de réseau de neurones. L’algorithme regroupe des hypothéses faibles émises par un classiffieur faible centrainés sur un sous-ensemble d’entrainement dont la distribution des éléments est renforcée, itération apres inération, afin que l’apprentissage puisse étre concentré sur les exemples qui posent le plus de difficultés au classifieur ainsi entrainé La distribution est modifige selon I’équation sui- vante In(xi) =i ny o Ala fin des 7 itérations, les T hypothéses faibles — pondérées en fonction de leurs performances — sont combinées afin de donner naissance 2 une hypo- these finale H()iX>Y¥ AdaBoost est rapide et simple & implémenter, il permet d'avoir de bons résultats et d’améliorer les performances d'autres classifieurs. 2.2.2 Learn++ Référence : [10] Date de publication : 2001 Auteurs : Polikar, Udpa, 8. Udpa, Honovar Incrémental : oui Algorithme : figure 8 page 14 Description : Learn++ s’inspire de l'algorithme Ada- Boost. Il géntre un certain nombre de classifieurs faibles & partir d’un ensemble de données dont on connait le label. En fonetion des erreurs du classi- fieur faible généré, 'algorithme modifie la distribution des éléments dans le sous-ensemble suivant afin de renforcer la présence des éléments les plus difficile a classifier. Cette procédure est ensuite répétée avec un ensemble différent de données du méme dataset et des nouveaux classificurs sont générés. En combinant leurs sorties selon le schéma de majorité de votes de Littlestone on obtient la régle finale de classification. Les classifieurs faibles sont des classifieuts: qui fournissent une estimation grossiére — de l'ordre de 50% ou plus de bonne classification — d'une regle de décision car ils doivent étre trés rapide & générer, Un classifier fort passant la majorité de son temps entrainement & affiner ses critéres de décision. La recherche d'un classifieur faible n’est pas un probleme trivial et la complexité de Ia tiche croft avec le nombre de classes différentes, cependant, l'utilisation d’algo- rithmes NN correctement réglés permet efficacement de contourner le probleme. BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 Leerreur est calculée selon équation Lr & = Ls Yuta) Ay intadens F oy avec hy :X — ¥ une hypothese et S; = TR, UTE; ott TR, est le sous-ensemble d’entrainement et TE, le sous-ensemble de test. Les coefficients synaptiques sont mi Péquation suivante : vot mat fr Hs) =H 1 sinon jour selon ‘ ay or est le numéro d’itération, B; erreur composite normalisée et H; Phypothése composite. Contrairement & AdaBoost qui est orienté vers V'amélioration des performances tout en permettant de part sa structure — Mapprentissage incrémental, Learn++ est essentiellement orienté sur l'apprentis- sage inerémental 2.3 Induction de régles associatives ers Jace + 8 (baer « Prone nig FIG. 2 ~ Algorithmes de Frequent Set Counting (FSC). Les algorithmes suivants utilisent les notions de support et de confidence pour déterminer la pert des associations, Le support d’une régle est défini par count(A) Support(A) = ipport(: i} «aay ot A est item (un produit) et T une base de données transactionnelle dont est issu A. La confidence d'une régle est définie par Support(A = B) Confidence a BT (3) Les regles associatives générées sont retenues si elles ont un support supérieur & minSupp et une conti- dence supérieure & minConf. Ces deux constantes — dépendantes de la base de données — sont définies par utilisateur du systéme de fagon empirique. 2.3.1 Référence : (2) Date de publication : 1993, Auteurs : Agrawall, Imielinski, Swami Algorithme : figure 9 page 15 Description : Apriori est un algorithme classique de recherche de régles d’association. Comme tous les algorithmes de découvertes «associations, il travaille sur des bases de données transactionnelles (des enre- gistrements de transactions). Apriori Pour révéler la pertinence d'une regle on utilise deux concepts qui sont le support (12) et la confidence (13). Afin d’étre retenue, chaque régle devra avoir tun support supérieur & minSupp et une confidence supérieure a minCon f. Ces deux valeurs étant définies empiriquement par l'utilisateur du systéme Lalgorithme démarre avec la liste des produits les plus fréquents dans la base de données respectant les seuils de support. Un ensemble de régles (des candi- dats) est généré partir de cette liste. Les candidats sont testés sur la base de données (ie. on recherche les instances des régles générées et leurs occurrences) et, les candidats ne respectant pas minSupp et minCon f sont retirées. Lialgorithme réitére ce processus en augmentant & chaque fois la dimension des candidats, dune unité tant que des régles pertinentes sont décou- vertes. A la fin, les ensembles de régles découvertes sont fusionnés, <énération des candidats se fait en deux étapes : 1) la jointure ; 2) ’élagage. La jointure consiste en une jointure d'un ensemble de régles a k-1 éléments sur Jui méme qui aboutit a la génération d’un ensemble de candidats a k éléments. Enfin, I'élagage supprime BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 les candidats dont au moins une des sous-chaine 8 k-1 éléments n'est pas présente dans l'ensemble des regles, ade éléments. Cet algorithme est trés performant, mais soutre si les ensembles d’éléments fréquents sont trop grands. De plus, scanner la base données a la recherche d’un motif de fagon répété devient rapidement un frein aux performances sur de grosses bases de donnée: 2.3.2 FP-Growth Référence : {7] Date de publication : 2000 Auteurs : Han, Pei, Yin, Mao Description : FP-Growth (Frequent-Pattern Growth) est un algorithme complétement innovant par rapport AUX autres algorithmes de recherche de régles associa tives presque tous basés sur Apriori Lalgorithme utilise une structure de données com- pacte appelé Frequent-Pattern tree et qui apporte une solution au probléme de la fouille de motifs fréquents dans une grande base de données transactionnelle. En stockant ensemble des éléments fréquents de la base de transactions dans une structure compacte, on supprimer la nécessiter de devoir scanner de fagon répétée la base de transactions. De plus, en triant les éléments dans la structure compacte, on accélére la recherche des moti Un FP-tree est composé dune racine nulle et d’un ensemble de naeuds préfixé par I'élément représemté. Un neeud est composé par : le nom de I'élément, le nombre d'occurrence de transaction oi figure la portion de chemin jusqu’a ce neeud, un lien inter-noeud vers les autres occurrences du méme élément figurant dans d'autres séquences de transactions. Une table «en-téte pointe sur la premiére occurrence de chaque élément. Lravantage de cette représentation des données est qu’il suffit de suivre les liens inter-noeuds pour connaitre toutes les associations fréquentes oit figure Pélément fréquent. 2.3.3 Eclat Référence : (17] Date de publication : 2000 Auteur : Zaki Algorithme : figures 10 et 11 page 15 Description : Eclat est le fondateur de la seconde grande famille dalgorithmes de recherche de regles associations avec l'algorithme Apriori. L’algorithme démarre avec la liste des éléments fréquents puis Valgorithme est réitéré en rajoutant les ensembles fréquents a l'ensemble des candidats C jusqu’a ce que cet ensemble soit vide Lensemble des transactions de D qui contiennent élément X est définit par D(X) ={T DIX CT} 4) Les relations sont filtrées selon M'équation sui- vante freq(Co, { (x, Dy) |(x.De) € Cp, |De| > minsup} as) 2 Référence : [5] Date de publication : 2005 Auteurs : Escovat, Biajiz, Vieira Algorithme : figures 9 et 12 pages 15 et 16 Deseription : SSDM (Semantically Similar Data Mi- ner) est un algorithme de la famille de algorithme Apriori auquel est rajouté des notions d’ensembles flous afin de renforcer la recherche d’associations sur des bases plus robustes. 4 SSDM Comme le nom de 'algorithme Pindique, SSDM s‘appuie sur les similarité sémantique des éléments pour effectuer ses recherches, L’algorithme utilise des matrices de similarité — remplie par Mutilisateur du systtme — pour chaque domaine de produits afin d'effectuer ses recherches. C’est le principal incon- vénient de cette méthode basée sur des critéres hu- mains, des études sont aujourd’hui menées afin de trouver des méthodes pour remplir ces matrices de fagon automatique. L’algorithme nécessite de fixer une valeur minimale de similarité minSim qui détermine si Palgorithme doit confondre deux éléments — ’un méme domaine — en une seule entité Lalgorithme recherche les cycles de similarité entre les éléments et ces cycles sont utilisés lors de la génération des candidats (identique & Apriori. On se retrouve alors avec un ensemble de candidats purs BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 contenant éventuellement des candidats flous. Le cas, éhéant, le support du candidat flou est évalué selon le poids de ses similarités par la formule suivante [poids(a) + poids()|[1 2 poidse sinlesb) 6) ot poidse est le poids du candidat C contenant les éléments a et b et ob poids(a) correspond au nombre occurrence de a dans la base de données transaction- elles, La formule générale pour n éléments est donnée par I’équation suivante : = fit poids = [Eroistm “4 ay a l olf est le plus petit degré de similarité contenu dans, les associations considérées. La génération des regles est également identique & celle de 'Apriori. 2.3.5 KDCI Référence : [9] Date de publication : 2003 Auteurs : Orlando, Lucchese, Palmerini, Algorithme : figures 10 et I page 15 Description : KDCI (k Direct Count & Intersect) est un algorithme hybride multi-stratégies basé sur l'algo- rithme DCI. L’algorithme recueille des informations sur Ia base de données durant exécution afin de déterminer la meilleure stratégie & adopter selon que les données sont denses ou éparses. ilvestri KDCI est optimisé pour les grandes bases de don- nées et utilise des structures de données compactes ainsi gu’une représentation des données minimale en mémoire. Lorsque la base de données élaguée peut tenir en mémoire, DCI construit une ridtist d’intersee- tions a la volée. Ce vecteur binaire & deux dimensions comprend les identifiants des éléments en ordonnée et ceux des transactions en abscisse, la présence dun élément dans une transaction étant marqué d'un 1 et absence d'un 0. La technique utilisée pour les bases de données parses se résume a tine projection suivie d'un élagage (uniquement si le gain de ce dernier est supérieur a son cot). Pour les bases de données denses oit le nombre intersection est important, I'heuristique de DCI est utilisé. II consiste en une réorganisation de la base de données yerticale en réordonnant les colonnes en plagant les segments identiques associés aux éléments, les plus fréquents aux premiéres positions, ce qui permet de réduire le nombre d’intersections en évitant a répétition de segments identiques. 2.4 Sequence mining Afin de facilité explication des algorithmes étu- diés ci-dessus, nous utiliserons le formalisme suivant : soit 1 sim} un ensemble de m éléments distinets. Un événement est une collection non vide non ordonnée de m éléments notée (i) ,i9,-.-, in). Une séquence & est une liste ordonnée d’événements 0 notée (0) > G2 >... > Gy). Une séquence avec k Elements (k = ¥,,ot)|) est appelée une k—séquence. Enfin, o£ (de cardinal n) est une sous-séquence de B ssi . ie. il existe des entiers i) < ip <... < iy tels que ey C By, 09 C B,..- 0% C Bj,» Une sous-séquence ¢ de s est dite contigue si elle résulte d’une suppression ala fois du premier et du dernier élément de s, ou de la suppression dune des éléments de s contenu dans un EvEnement ayant au moins 2 éléments, ou si ¢ est une sous-séquence contigué de c’ laquelle est une sous- séquence contigué de s. tsi 2.4.1 GSP Référence : [15] Date de publication : 1996 Auteurs : Srikant, Agrawal Algorithme : figure 14 page 17 Deseription : GSP (Generalized Sequential Patterns) est un algorithme multipasse. La premiére passe déter- mine le support (ie, le nombre de séquence contenant cet élément) de chaque élément et permet de ne tra- vailler que sur les éléments ayant le support minimum, et générer les séquences candidates. Le support de ces candidats étant déterminé lors des passages suivants. La génération des candidats se fait en 2 phases : Ja jointure et élagage. La jointure se fait en joignant ensemble des (k-1)-séquences fréquentes Ly avec luieméme, ce qui consiste — en considérant les sé- quences 51,52 € Lx) — a rajouter le demier élément de sy & sy, Si élément constituait un événement a BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 ui tout seul dans 52 alors il constituera un événement dans sj, De la méme manidre s'il faisait parti dun événement dans s2 alors il sera rajouter au dernier évé- nement de 51. La jointure est valable uniquement si en enlevant le premier élément de 5; on obtient la méme sous-séquences qu’en retirant le dernier élément des Enfin, I'élagage consiste & retirer les candidats ayant des sous-séquences ou des sous-séquences contiguiés dont le support serait inférieur au minSupp. Une fois ensemble des k—séquences candidates ‘2énéré, chaque candidat est dénombré dans la base de données. Afin d’optimiser le dénombrement, une table de hachage est utilisée ainsi que la mise en place d’une urge maximale entre éléments d’une squence ce qui permet de limiter les recherches. Pour plus de détails sur l'implémentation de ces techniques, merci de vous referer & [15]. Enfin, algorithme GSP permet également d’uti- liser les informations contenues dans une hiérarchi- sation des données de type est-un. Dans ce cas, on ‘généralise la recherche aux descendants des éléments recherchés 24.2 SPADE Référence : [18] Date de publication : 2001 Auteurs : Zaki Algorithme : figures 15, 16 et 17 page 17 Description : SPADE (Sequential PAttern Discovery using Equivalence classes) est un algorithme qui lise la théorie des Treillis afin de limiter son espace de recherche, ie. il utilise pour chaque ensemble une borne supérieure et une borne inféricure. SPADE utilise des ID-listes verticales, id est une liste de couple ($1D!,E1D*) par atome. Concernant la recherche des séquences fréquentes, deux stratégies sont proposées : Breadth-First Search (BFS) et Depth- First Search (DFS). BFS correspond & la stratégie utilisge par GSP, elle procéde niveau par niveau ce qui a Vavantage de permettre un élagage beaucoup plus intéressant que via DPS, cependant, DPS prend beau- coup moins de place en mémoire et cette technique — qui consiste a effectuer des recherches branche par branche — est la seule utilisable dans le cas oit les SID = Séquence IDentifiant SEID = Evénement IDentifiant. ensembles de séquences fréquentes seraient amener 8 &tre beaucoup trop importants. Lors de la génération des séquences candidates, les Jjointures se font de la fagon suivante 1, Elément contre élément : PB jointe avec PD en PBD. 2. Elément contre séquence : PB jointe avec P— Aen PBA 3. Séquence contre séquence : ? — A jointe avec P=FenPAF,P+A>FaP>F A Le principal avantage de SPADE par rapport & GSP est utilisation de listes verticales temporaires pour les jointures. Ces listes, bornées, sont beaucoup plus petites et rapides a générer que celles utilisées par GSP ce qui permet d’améliorer grandement le temps de calcul nécessaire ainsi que de réduire les besoins de mémoire. Enfin, utilisation d’ensembles de treillis permet de restreindre le domaine de recherche autour des éléments fréquents ce qui occasion un important gain de temps BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 Algorithmes Algorithme 1 1D3 ENTRE Exemples, attributCible, AttributsNonCible si estVide(Exemples) alors retourner un nceud Erreur sinon si estVide(AttributsNonCible) alors retourner un nceud ayant la valeur la plus représenté pour attributCible sinon si tous les éléments de Exemples ont la méme valeur pour attributCible alors retourner un noeud ayant cette valeur sinon AttributSélectionne attribut maximisant le gain d’information parmi AttributsNonCible AttributsNonCibleRestants = AtributsNonCible —{AtributSélectionné} nouveauNeeud = neeud étiqueté avec AttributSélectionné pour chaque valeur de AttributSélectionné faire ExemplesFiltrés= exempleAyantValeurPourAttribut(Exemples, AttributSélectionné, va- leur) nouveauNovud.fils(valeur)=1D3(ExemplesFiltrés, AttibutSélectionné, AttributsNonCi- bleRestants) fin pour retourner nouveauNoeud fin si fin si fin si Algorithme 2 SLIQ-Pariition ENTRE Dataset S si (tous les points de S appartiennent & a méme classe) alors Sortir de Palgorithme fin si Evaluer les partitionnements pour chaque attribut A Utiliser le meilleur partitionnement de $ aboutissant sur la eréation de Sy et S2 Pattition(S;) /* Appel récursif & gauche */ Partition(S.) /* Appel récursif A droite * 1, 4-16 ue Volare, 93290 Le Kremlin Bice, France 10Etudes des principaux algorithmes de data mining {Scta] Eprra 2009 Algorithme 3 SLIQ-EvaluateSphits pour chaque attribut A faire pour chaque valeur v de la liste d’attribut faire = feuille contenant I’élément courrant mettre & jour I’histogramme de la feuille / si A est un attribut continu alors tester la séparation pour le critére A < v de la feuille 1 fin si fin pour si A est un attribut discret alors pour chaque feuille de l’arbre faire trouver le sous-ensemble de A qui réalise la meilleure séparation fin pour fin si fin pour Algorithme 4 SLIQ-UpdateLabels pour chaque attribut A utiliser comme critére de séparation faire création des nouveaux noeuds et histogrammes associés pour chaque valeur v de la liste de attribut A faire soit ¢ la classe correspondant 2 I"élément courrant trouver la nouvelle classe ¢ de A correspondant a la nouvelle séparation modifier la référence de classe de I’ lément de e vers ¢ fin pour fin pour BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, France uEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 Algorithme 5 OCT ENTREES: T/* Lensemble d'entrainement *7 H = bestAxis-Parallel(7) /* Meilleur hyperplan de séparation paralléle un axe "/ 1 = impurity(H) /* Impureté de cette séparation */ pour j= | jusqu’a & faire sii> 1 alors H = randomisedHyperplan() /* Hyperplan aléatoire */ fin si label Etape_1 répéter pour j= 1 jusqu’a d faire Perturb(H, j) /* Perturber le coefficient j de H */ fin pour jusqu’a / soit améliorée label Etape_2 pour i= 1 jusqu’a J faire Choisir aléatoirement une direction et tenter de perturber Hf dans cette direction. si impurity(H) <1 alors aller & Etape_1 fin si fin pour 1, = impurity(H) sil) - un algorithme d'apprentissage faible WeakLearn, - un entier 7, pour spécifier le nombre d’itérations. pour k = 1 jusqu’a K faire Ke wi(i) = D(i) = 1, /* A moins que Yon ai des connaissances pour faire autrement */ pour; = | jusqu’a 7; faire label we/ EPs weld) (* D, est une distribution */ label 2 : TR, = RandomSubset(S,D,) /* Ensemble d’entrainement choisi aléatoirement dans S selon D, */ TE, = RandomSubset(S,D,) * Ensemble de test choisi aléatoirement dans S selon D, */ label 3 : hy = WeakLearn(T'R,) /* Hypothtse de X — ¥ label ComputeE rror(hy,S;) /* Calcul de l'erreur de hy selon l’équation (10) * sie, > 1/2 alors t=1-1 Supprimer(h,) goto label 2 sinon By = normalise(e,) * Enreur normalisée : £5 */ fin si Tabel 5 : H, = argmar¥,()-yl08(1/B:) /* Hypothese composée */ E, = ComputeError(H;,S;) si E; > 1/2 alors t=t-1 ‘Supprimer(#,) goto label 2 fin si label normalise(E;) /* Erreur composite normalisée */ UpdateWeight(t) /* Mise a jour des poids des instances selon l’équation (11) */ fin pour fin pour retourner K Hina =argm 1 ju aromas oe 1, 4-16 ue Volare, 93290 Le Kremlin Bice, France 4Etudes des principaux algorithmes de data mining {Scta] Eprra 2009 Algorithme 9 Apriori ENTREES: T,€ Ly = {ensemble de I-item qui apparaissent dans au moins e transactions} k=2 tant que Lj; 4 2 faire Cy = Generate( Ly) /* Génere l'ensemble de candidats */ pour €T faire G, = SousEnsemble(C;,t) M Sélection des candidats de Cy, présents dans t pour c € C; faire count{e] = count|e] +1 fin pour fin pour ¢ € Cylcount{c] > e} k+l fin tant que retourner UL, i Algorithme 10 Eclat ENTREES: Liste des arguments = -A/* Liste des éléments ordonnée en ordre croissant */ - DC P(A) /* La base de données transactionnelles issue de A */ ~ minSup € N /* Le support minimum définit par l'utilisateur */ F = {(2,|D))} /* initialisation de ensemble des fréquent et de leur support */ Co = {(x, D({x}) |x € A} /* Ensemble des transactions contenant un élément de A */ Ch = freg(Co) /* Co est filtrée selon (15) */ {2} F = addFrequentSupersets(F,Cj) * Appel recursit */ retourner F /* Ensemble d’éléments fréquents et leur support */ Algorithme 11 Eclat-addFrequentSupersets ENTREES: Liste des arguments ~ p< P(A) /* Préfixe * - C/* Matrice des motifs fréquents de p */ - F /* Ensemble des motifs fréquents et de leur support */ pour (x,D,) € C faire putt} Cy = {0D.NDy)|(y.Dy) € Cy > a} %, = freq(C,) /* Cy est filtrée selon (15) */ siC, # @ alors F = addFrequentSupersets(q.C,) fin si P=FU{(g|Ds))} fin pour retourner BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 Algorithme 12 SSDM-CyclesDeSimilarité ‘Az = ensemble «associations floues de taille 2 pour (k =3;k < size(D,);k+) faire comparer chaque paire 4 association floues dans Ay_1 si (prefixe(a;) = prefixe(a,),i 4 j) alors // Si Vunion des suffixes est suffisament similaire si ((suffix(a;) U suffix(a;)) € Ap) alors ay = aj Usuffix(a;) fin si fin si fincomparer Aj, = ensemble de tous les ax fin pour Sy = groupe de tous les Ay Algorithme 13 KDCT ENTREES: D.minSupp remierScan(D,minSupp) /* Obtenir les figures d optimisation durant le premier sean */ = secondScan(D',minSupp) /* A partir du second scan on utilise une base de données Df temporaire */ k=2 tant que D/ taille_verticale() > memoire_disponible() faire ket Fi, = DCP(D! minSupp.k) fin tant que ka Fy = DCP(D!, VD, minSupp,k) /* Création dune base de données verticale */ dense =VD.est_dense() tant que F; 4 2 faire ket useclefyyotif() alors si dense alors Fi = DCI_dense_keyp(VD.minSupp.k) sinon Fj = DCI_sparse_keyp(VD.minSupp.k) fin si sinon si dense alors Fi = DCI_dense(VD,minSupp.k) sinon Fj, = DCL_sparse(VD,minSupp,k) fin si fin si fin tant que 1, 4-16 ue Volare, 93290 Le Kremlin Bice, France 16Etudes des principaux algorithmes de data mining {Scta] Eprra 2009 Algorithme 14 GSP T-séquence fréquentes} pour k= 1 jusqu’a Fi, 4 2 faire Cy = Ensemble de k—séquences candidates pour Ve < DB faire pour 0 € C; faire sie Caalors Incrémenter le compteur de 0. fin si fin pour fin pour Fy ={a€ Gla.sup > minSupp} fin pour retourner U, Fi / Ensemble des séquences fréquentes */ Algorithme 15 SPADE ENTREES: minSupp,D /* Support minimal et base de données */ F, =( élements fréquents ou 1-séquences fréquentes } "y =(2-séquences fréquentes} © ={classes équivalentes [X']o, }} pour V(X] €¢ faire EnumerateF requentSeq(|X]) fin pour BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, France 7Etudes des principaux algorithmes de data mining {Scta] Eprra 2009 ‘Algorithme 16 SPADE. EnumerateFrequentSeq ENTRE S/* Un sous-treillis et son ID-liste */ pour VA; € S faire =o pour VA; € S avec j > i faire R=A)VAj si Prune(R) = FAUX alors L(R) = L(A) NL(Aj) sio(R) > minSupp alors TU{R} Fini AR} fin si fin pour si DepthFirstSearch alors Enumerate requenteSeq(T) fin si fin pour si BreadthFirstSearch alors pour V7; 4 2 faire EnumerateFrequenteSeq(T)) fin pour fin si Algorithme 17 SPADE-Prune ENTREES: B pour ¥/(k-1)-sous-séquence, a ~ f faire si [o1] a été caleulé et a ¢ Fi. alors retourner Vrai fin si fin pour retourner Faux BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, FranceEtudes des principaux algorithmes de data mining {Scta] Eprra 2009 Références [1] Manish Mehta 0002, Rakesh Agrawal, and Jorma Rissanen, SLIQ : A fast scalable classifier for data mining. In Apers et al. (3], pages 18-32. [2] Rakesh Agrawal, Tomasz Imielinski, and Arun N, Swami. Mining association rules between sets of items in large databases. In Peter Buneman and Sushil Jajodia, editors, SIGMOD Conference, pages 207-216. ACM Press, 1993. [3] Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin, editors. Advances in Database ‘Technology - EDBT’96, Sth Intemational Conference on Extending Database Technology, Avignon, France, March 25-29, 1996, Proceedings, volume 1057 of Lecture Notes in Computer Science. Springer, 1996. [4] Leo Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone, Classification and Regression Trees. Wadsworth, 1984. [5] Eduardo L. G. Escovar, Mauro Biajiz, and Marina Teresa Pires Vieira. SSDM : A semantically similar data mining algorithm. In Carlos A. Heuser, editor, SBBD, pages 265-279. UFU, 2005, [6] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1) :119-139, 1997. [7] Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation : A frequent-pattern tree approach. Data Min. Knowl. Discov., 8(1) :53-87, 2004, [8] Sreerama K. Murthy, Simon Kasif, Steven Salzberg, and Richard Beigel. Ocl : A randomized induction of oblique decision trees. In AAAI, pages 322-327, 1993 Salvatore Orlando, Claudio Lucchese, Paolo Palmerini, Raffaele Perego, and Fabrizio multi-strategy algorithm for mining frequent sets. In FIMI, 2003. 19 ilvestri. kdci : a [10] Robi Polikar, L. Upda, S. S. Upda, and Vasant Honavar. Learn+ : an incremental learning algorithm for supervised neural networks, IEEE Transactions on Systems, Man, and Cybernetics, Part C, 31(4) :497— 508, 2001. [11] J. Ross Quinlan. Induction of decision trees. Machine Learning, 1(1) :81-106, 1986. [12] Ross R. Quinlan, C4.5 : programs for machine learning. Morgan Kaufmann Publishers Inc., 1993. [13] Jeffrey C. Schtimmer and Douglas H. Fisher. A case study of incremental concept induction. In AAAI, pages 496-501, 1986, [14] John C, Shafer, Rakesh Agrawal, and Manish Mehta 0002. SPRINT : A scalable parallel classifier for data mining. In T. M. Vijayaraman, Alejandro P, Buchmann, C, Mohan, and Nandlal L. Sarda, editors, VLDB, pages 544-555. Morgan Kaufmann, 1996, [15] Ramakrishnan Srikant and Rakesh Agrawal. Mining sequential patterns : Generalizations and performance improvements, In Apers et al. (3], pages 3-17. [16] Paul E, Utgoff. Incremental induction of decision trees. Machine Learning, 4 :161~186, 1989. [17] Mohammed J. Zaki. Scalable algorithms for association mining. IBEE. Transactions on Knowledge and Data Engineering, 12 :372-390, 2000. [18] Mohammed Javed Zaki, SPADE : An efficient algorithm for mining frequent sequences, Machine Learning. 42(1/2) :31-60, 2001 BPA, 1-16 He Volare, 93290 Le Kremlin- Bice, France 9