Loïck Lhôte (Greyc)

En Fouille de Données, l’objectif est d’extraire des informations intéressantes dans de grandes bases de données. Une manière de faire est d’extraire les motifs fréquents qui sont très utiles pour construire des règles d’associations.

Une base de données est composée de transactions dont chacune contient une liste d’items. En pratique, les transactions représentent les objets observés (des patients, des champignons, etc…) alors que les items représentent les caractéristiques des objets (grand, petit, blond, etc…).

Un motif g-fréquent est un ensemble d’items qui apparait en même temps dans au moins g transaction(s).

La difficulté théorique pour énumérer les g-fréquents est bien connue. Dans le pire des cas, il y en a un nombre exponentiel. A contrario dans le meilleur des cas, on en compte un nombre constant. Le saut théorique entre le pire et le meilleur des cas est immense et pourtant, on ne dispose d’aucune autre information sur le nombre de fréquents. Les expériences montrent que pour de petites valeurs du seuil g, ce nombre explose. En revanche lorsque le seuil augmente, l’énumération de tous les g-fréquents devient accessible.

Afin d’expliquer (partiellement) ces phénomènes, François Rioult, Arnaud Soulet et moi-même avons effectué la première analyse en moyenne du nombre de g-fréquents. L’analyse en moyenne fournit des résultats plus proches de la réalité que le pire des cas et met en évidence l’influence des différents paramètres.

Nous avons utilisé deux modèles théoriques de bases de données pour notre analyse: un modèle de Bernoulli et un modèle markovien. Bien que très éloignés de la réalité, ces modèles ont révélé des comportements nouveaux. En particulier, nous avons montré que le nombre de g-fréquents est exponentiel pour un petit seuil alors qu’il est d’ordre polynomial pour un seuil non négligeable.

Dans ce séminaire, je vous présenterai les grandes lignes de cette première analyse en moyenne issue d’une collaboration entre l’équipe DoDoLa et l’équipe Algorithmique.