Sampling strategies for finding frequent sets
Jaume Baixeries, Gemma Casas-Garriga · 2003
Les plusieurs algorithmes pour faire la quete d'itemsets frequents dans une base de donees dependent de la grandeur de la base de donees. L'echantillonage est une facon de resoudre ce probleme. L'aproximation classique d'echantillonage a ete basee dans les limites de Chernoff et similaires. Une des alternatives proposees est celle de l'echantillonage on-line, qui calcule la grandeur de l'echantillon de facon adaptative pour chaque itemset. Mais cette technique est tres dificile d'etre implementee si on utilise les algorithmes actuels. Dans cet article on presente differents implementations de le scheme on-line utilisant notre algorithme meilleur-d'abord (deja presente), qui peut implementer l'echantillonage on-line. On compare aussi cet algorithme avec l'alternative batch. L'algorithme final agit de maniere stable dans diferents situations.