|
extraction de motifs fréquents , aussi connu comme l'extraction de motifs fréquents , est une technique pour découvrir des groupes d'éléments qui se produisent fréquemment ensemble dans une base de données . Selon le Dr Christian Borgelt , chercheur principal au Centre européen pour Soft Computing , extraction de motifs fréquents a été l'un des sujets les plus activement recherchées dans l'extraction de données depuis le début des années 1990 et de nombreux algorithmes mathématiques ont été développés. Motif fréquent Mining
fréquente extraction de motifs est un problème élémentaire dans de nombreuses applications . Une base de données transactionnelle typique - comme une base de données qui décrit le comportement des acheteurs sur la rue Main , par commande postale ou en ligne - contient un grand nombre de jeux d'éléments et présente un défi en termes de développement efficaces , les algorithmes évolutifs. Fréquents algorithmes d'extraction de motifs connus comme Apriori , Eclat et FP- croissance sont parmi les plus connus .
Apriori algorithme
L'algorithme Apriori , d'abord proposé par Rakesh Agrawal et Ramkrishnan Srikant du Centre de recherche Almaden d'IBM en 1994, fonctionne sur le principe que les jeux d'éléments sont comptabilisés quand ils se produisent dans les transactions. La base de données est analysé pour trouver fréquente 1- itemsets , les 1- itemsets sont utilisés pour générer 2- itemsets et ainsi de suite jusqu'à k- itemsets . Un k- itemset est dit fréquent si et seulement si tous ses subitemsets sont fréquents . Depuis qu'il a été proposé , de nombreuses améliorations à l'algorithme Apriori ont été suggérées
FP- croissance algorithme
L'algorithme FP- croissance - . FP se pour " Frequent Pattern" - utilise une technique connue sous le nom l'algorithme scanne la base de données pour créer une liste d'éléments fréquents dans l'ordre décroissant , qu'il utilise pour compresser la base de données dans un FP -tree " diviser pour mieux régner . ». Le FP- arbre lui-même est miné , à partir de chaque fréquente length-1 modèle - également connu comme un motif de suffixe - pour créer une condition FP -tree , qui contient des préfixes correspondant à des éléments qui co- produire avec le motif de suffixe initial. Le motif de suffixe initial est concaténée avec les motifs fréquents trouvés dans la FP -tree conditionnel à réaliser une croissance du motif.
Eclat algorithme
Apriori et algorithmes FP- croissance mien motifs fréquents à partir d'un ensemble de transactions disposés horizontalement . La transformation ( Eclat ) algorithme de Equivalence Class - proposé par Mohammed J. Zaki , un professeur de sciences informatiques à l'Institut polytechnique Rensselaer , en 2000 - d'autre part , les mines motifs fréquents dans une série de transactions disposés verticalement . L'algorithme Eclat commence avec un seul point et utilise un jeu d'intersection pour déterminer itemsets fréquents et répète jusqu'à ce que des motifs fréquents peuvent être trouvés.
|
