Faire face à l'explosion combinatoire

Étant donné un ensemble de transactions, comment trouver toutes les règles ayant un support >= minSup et une confiance >= minConf
Problème : il est impossible de calculer toutes les règles. Pour un ensemble de d items, le nombre de règles possibles est nbRègles(d)= 3^d-2^d+1+1, soit 74 pour d=4 et 602 pour d=6...
Pour améliorer la performance d'un algorithme de recherche de règles, on peut tenir compte d'une propriété du support : le support d'une règle X → Y ne dépend que du support de son ensemble d'items (X ∪ Y)
Exemple : Les règles (bière,couches)→(lait), (biere,lait)→(couches), (bière)→(lait,couches) (lait)→(bière,couches) ont toutes le même support car elles sont construites sur le même ensemble {bière, couches, lait}.
Par conséquent, si un ensemble d'items est rare alors toutes les règles associées sont rares et peuvent être éliminées sans calculer leur confiance.