Máximo y cerrado frecuente - Respuesta incluida

1 : A , B , C , E 2 : A , C , D , E 3 : B , C , E 4 : A , C , D , E 5 : C , D , E 6 : A , D ,

Quiero descubrir los conjuntos de elementos frecuentes máximos y los conjuntos de elementos frecuentes cerrados .

• El conjunto de elementos frecuentes es máximo si no tiene superconjuntos frecuentes.$X ∈ F$
• El conjunto de elementos frecuentes X ∈ F está cerrado si no tiene un superconjunto con la misma frecuencia

Así que conté la aparición de cada conjunto de elementos.

{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 establecido en // Muy importante. Gracias steffen por recordar eso.$50%$

¿ Maximal = ?$\{{A,B,C,E\}}$

¿ Cerrado = ?$\{{A,B,C,D\}} \ and \ \{{B,C,D,E\}}$

Encontré una definición ligeramente extendida en esta fuente (que incluye una buena explicación). Aquí hay una fuente más confiable (publicada): CHARM: Un algoritmo eficiente para la minería de conjuntos cerrados por Mohammed J. Zaki y Ching-jui Hsiao .

Según esta fuente:

• Un conjunto de elementos está cerrado si ninguno de sus superconjuntos inmediatos tiene el mismo soporte que el conjunto de elementos
• Un conjunto de elementos es máximo frecuente si ninguno de sus superconjuntos inmediatos es frecuente


Algunas observaciones:

• Es necesario establecer un min_support (soporte = el número de conjuntos de elementos que contienen el subconjunto de interés dividido por el número de todos los conjuntos de elementos) que define qué conjunto de elementos es frecuente . Un conjunto de elementos es frecuente si su soporte> = min_support.
• En lo que respecta al algoritmo, solo se consideran conjuntos de elementos con min_support cuando se intenta encontrar los conjuntos de elementos máximos frecuentes y cerrados.
• El aspecto importante en la definición de cerrado es que no importa si existe un superconjunto inmediato con más soporte, solo importan los superconjuntos inmediatos con exactamente el mismo soporte.
• máximo frecuente => cerrado => frecuente, pero no al revés.

Aplicación al ejemplo del OP

Nota:

• No verificó los recuentos de soporte
• Digamos min_support = 0.5. Esto se cumple si min_support_count> = 3

{A} = 4; no cerrado debido a {A, E}
{B} = 2; no frecuente => ignorar
{C} = 5; no cerrado debido a {C, E}
{D} = 4; no cerrado debido a {D, E}, pero no máximo debido a, por ejemplo, {A, D}
{E} = 6; cerrado, pero no máximo debido a, por ejemplo, {D, E}

{A, B} = 1; no frecuente => ignorar
{A, C} = 3; no cerrado debido a {A, C, E}
{A, D} = 3; no cerrado debido a {A, D, E}
{A, E} = 4; cerrado, pero no máximo debido a {A, D, E}
{B, C} = 2; no frecuente => ignorar
{B, D} = 0; no frecuente => ignorar
{B, E} = 2; no frecuente => ignorar
{C, D} = 3; no cerrado debido a {C, D, E}
{C, E} = 5; cerrado, pero no máximo debido a {C, D, E}
{D, E} = 4; cerrado, pero no máximo debido a {A, D, E}

{A, B, C} = 1; no frecuente => ignorar
{A, B, D} = 0; no frecuente => ignorar
{A, B, E} = 1; no frecuente => ignorar
{A, C, D} = 2; no frecuente => ignorar
{A, C, E} = 3; máxima frecuente
{A, D, E} = 3; máxima frecuente
{B, C, D} = 0; no frecuente => ignorar
{B, C, E} = 2; no frecuente => ignorar
{C, D, E} = 3; máxima frecuente

{A, B, C, D} = 0; no frecuente => ignorar
{A, B, C, E} = 1; no frecuente => ignorar
{B, C, D, E} = 0; no frecuente => ignorar

Es posible que desee leer sobre el algoritmo APRIORI. Evita conjuntos de elementos innecesarios mediante una poda inteligente.

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

B no es frecuente, eliminar.

Construye y cuenta conjuntos de dos elementos (aún no hay magia, excepto que Bya está fuera)

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

Todos estos son frecuentes (¡ Btenga en cuenta que todo lo que tenía no puede ser frecuente!)

Ahora usa la regla de prefijo. SOLO combine conjuntos de elementos que comiencen con los mismos elementos n-1. Eliminar todo, donde cualquier subconjunto no es frecuente. Cuente los conjuntos de elementos restantes.

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

Tenga en cuenta que {A,C,D}no es frecuente. Como no hay un prefijo compartido, ¡no puede haber un conjunto de elementos frecuente más grande!

¡Observe cuánto menos trabajo hice!

Para conjuntos de elementos máximos / cerrados, verifique subconjuntos / supersets.

Tenga en cuenta que {E}=6, por ejemplo , y {A,E}=4. {E}es un subconjunto, pero tiene mayor soporte, es decir, está cerrado pero no es máximo. {A}tampoco lo es, ya que no tiene mayor soporte que {A,E}, es decir, es redundante .