Fréquence maximale et fermée - Réponse incluse

Je souhaite connaître les ensembles d'éléments fréquents maximaux et les ensembles d'éléments fréquents fermés .

• L'ensemble d'éléments fréquents $X ∈ F$ est maximal s'il n'a pas de sur-ensembles fréquents.
• L'ensemble d'éléments fréquents X ∈ F est fermé s'il n'a pas de sur-ensemble avec la même fréquence

J'ai donc compté l'occurrence de chaque ensemble d'éléments.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

{A,B} = 1; {A,C} = 3; {A,D} = 3; {A,E} = 4; {B,C} = 2; 
{B,D} = 0; {B,E} = 2; {C,D} = 3; {C,E} = 5; {D,E} = 3

{A,B,C} = 1; {A,B,D} = 0; {A,B,E} = 1; {A,C,D} = 2; {A,C,E} = 3; 
{A,D,E} = 3; {B,C,D} = 0; {B,C,E} = 2; {C,D,E} = 3

{A,B,C,D} = 0; {A,B,C,E} = 1; {B,C,D,E} = 0

Min_Support réglé à $50%$ // Très important. Merci steffen de l'avoir rappelé.

Est-ce que maximal = $\{{A,B,C,E\}}$ ?

Est-ce que fermé = $\{{A,B,C,D\}} \ and \ \{{B,C,D,E\}}$ ?

J'ai trouvé une définition légèrement étendue dans cette source (qui comprend une bonne explication). Voici une source plus fiable (publiée): CHARM: Un algorithme efficace pour l'extraction d'éléments fermés par Mohammed J. Zaki et Ching-jui Hsiao .

Selon cette source:

• Un ensemble d'éléments est fermé si aucun de ses sur-ensembles immédiats n'a le même support que l'ensemble d'éléments
• Un ensemble d'éléments est maximal fréquent si aucun de ses sur-ensembles immédiats n'est fréquent


Quelques remarques:

• Il est nécessaire de définir un min_support (support = le nombre d'ensembles d'éléments contenant le sous-ensemble d'intérêt divisé par le nombre de tous les ensembles d'éléments) qui définit quel ensemble d'éléments est fréquent . Un jeu d'éléments est fréquent si son support> = min_support.
• En ce qui concerne l'algorithme, seuls les ensembles d'éléments avec min_support sont considérés lorsque l'on essaie de trouver les ensembles d'éléments fréquents et fermés maximaux.
• L'aspect important dans la définition de fermé est que peu importe si un surensemble immédiat existe avec plus de support, seuls les surensemble immédiats avec exactement le même support sont importants.
• fréquence maximale => fermé => fréquent, mais pas l'inverse.

Application à l'exemple de l'OP

Remarque:

• N'a pas vérifié le nombre de soutiens
• Disons que min_support = 0,5. Ceci est rempli si min_support_count> = 3

{A} = 4; non fermé en raison de {A, E}
{B} = 2; peu fréquent => ignorer
{C} = 5; non fermé en raison de {C, E}
{D} = 4; non fermé en raison de {D, E}, mais pas maximal en raison par exemple de {A, D}
{E} = 6; fermé, mais pas maximal en raison par exemple de {D, E}

{A, B} = 1; peu fréquent => ignorer
{A, C} = 3; non fermé en raison de {A, C, E}
{A, D} = 3; non fermé en raison de {A, D, E}
{A, E} = 4; fermé, mais pas maximal en raison de {A, D, E}
{B, C} = 2; peu fréquent => ignorer
{B, D} = 0; peu fréquent => ignorer
{B, E} = 2; peu fréquent => ignorer
{C, D} = 3; non fermé en raison de {C, D, E}
{C, E} = 5; fermé, mais pas maximal en raison de {C, D, E}
{D, E} = 4; fermé, mais pas maximal en raison de {A, D, E}

{A, B, C} = 1; peu fréquent => ignorer
{A, B, D} = 0; peu fréquent => ignorer
{A, B, E} = 1; peu fréquent => ignorer
{A, C, D} = 2; peu fréquent => ignorer
{A, C, E} = 3; fréquence maximale
{A, D, E} = 3; fréquence maximale
{B, C, D} = 0; peu fréquent => ignorer
{B, C, E} = 2; peu fréquent => ignorer
{C, D, E} = 3; fréquence maximale

{A, B, C, D} = 0; peu fréquent => ignorer
{A, B, C, E} = 1; peu fréquent => ignorer
{B, C, D, E} = 0; peu fréquent => ignorer

Vous voudrez peut-être lire sur l'algorithme APRIORI. Il évite les ensembles d'éléments inutiles par une taille intelligente.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

B n'est pas fréquent, supprimez.

Construisez et comptez deux ensembles d'éléments (pas encore de magie, sauf que Bc'est déjà sorti)

{A,C} = 3; {A,D} = 3; {A,E} = 4; 
{C,D} = 3; {C,E} = 5; {D,E} = 3

Tout cela est fréquent (notez que tout ce qui avait Bne peut pas être fréquent!)

Utilisez maintenant la règle de préfixe. Combinez UNIQUEMENT les ensembles d'éléments commençant par les mêmes n-1 éléments. Supprimez tout, là où un sous-ensemble n'est pas fréquent. Comptez les ensembles d'éléments restants.

{A,C,D} = 2; {A,C,E} = 3; {A,D,E} = 3; 
{C,D,E} = 3

Notez que ce {A,C,D}n'est pas fréquent. Comme il n'y a pas de préfixe partagé, il ne peut pas y avoir un plus grand nombre d'éléments fréquents!

Remarquez combien moins de travail que j'ai fait!

Pour les ensembles d'éléments maximaux / fermés, vérifiez les sous-ensembles / sur-ensembles.

Notez que par exemple {E}=6, et {A,E}=4. {E}est un sous-ensemble, mais a un support plus élevé, c'est-à-dire qu'il est fermé mais pas maximal. {A}n'est pas non plus, car il n'a pas un support plus élevé que {A,E}, c'est-à-dire qu'il est redondant .