approches efficaces de fouille de motifs fréquents sur big data

Abstract

La fouille de motifs fréquents est un domaine de recherche important dans la fouille de données ou Data Mining. Depuis son introduction, elle a attiré l’attention de nombreux chercheurs, et de nombreux algorithmes ont été proposés. Bien que ces algorithmes soient populaires et performants en raison de leurs intéressantes pro priétés, ils présentent également des inconvénients , tels que les analyses multiples de bases de données et les constructions récursives d’arbres. Dans l’ère actuelle du Big Data, des volumes importants d’une grande variété de données de grande valeur sur les différentes véracités peuvent être facilement re cueillis ou générés à grande vitesse dans diverses applications de la vie réelle. Parmi ces 5V de grandes données, on se concentre dans cette thèse sur le traitement de gros volumes de données. Récemment, de nombreux algorithmes parallèles basés sur des frameworks mo dernes (comme Apache Hadoop, Apache Spark) ont été développés, et qui sont capables d’exploiter le calcul distribué dans des clusters de machines. Cependant, la parallélisation des algorithmes d’extraction de motifs fréquents est loin d’être triviale, et même l’exploration de l’espace de recherche, sur laquelle toutes les tech niques sont basées, n’est pas facilement partageable. Par conséquent, la fouille de motifs fréquents distribués est un problème difficile et devient alors un sujet de recherche intéressant. Dans ce contexte, nos principales contributions consistent : Premièrement, en une analyse théorique et expérimentale exhaustive des approches les plus performantes, dont nous avons mené plusieurs expériences afin d’évaluer et de discuter les performances des algorithmes par rapport aux différents cas d’utilisation réelle et à différentes distributions de données. Les résultats de cette analyse ont montré qu’aucun algorithme n’est universellement supérieur et que les performances sont fortement affectées par la distribution des données. De plus, elle nous permet d’identifier un manque de fiabilité en ce qui concerne l’extraction fréquente de motifs dans des cas d’utilisation des données massives ou Big Data. Deuxièmement, les résultats et les questions en suspens ont motivé le développe ment d’une première approche distribuée appelée HFIMH, basée sur le fameux algorithme Apriori, qui utilise les deux dispositions horizontales et verticales pour représenter efficacement la base des transactions, et une méthode d’intersection des ensembles pour accélérer le calcul des supports. Troisièmement, en une implémentation d’un nouvel algorithme distribué appelé 3 HPrePostPlus basé sur la structure des listes, et adoptant la structure HashMap pour accélérer la construction d’une arborescence de recherche, l’algorithme HPre PostPlus utilise aussi une méthode d’intersection des listes afin d’accélérer le calcul des supports. Enfin, l’évaluation expérimentale nous permet d’obtenir de meilleures performances de nos approches par rapport aux algorithmes existants de l’état de l’art, et montrent leurs performances, leurs efficacités et leurs extensibilités.