Máximo e fechado frequentemente - resposta incluída

10

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 , E

My  dumatumaset:
1:UMA,B,C,E
2:UMA,C,D,E
3:     B,C,E
4:UMA,C,D,E
5:    C,D,E
6:    UMA,D,E

Quero descobrir o máximo de conjuntos de itens frequentes e os conjuntos de itens frequentes fechados .

  • O conjunto de itens frequentes XF é máximo se não tiver nenhum superconjunto frequente.
  • O conjunto de itens frequentes X ∈ F é fechado se não houver um superconjunto com a mesma frequência

Então contei a ocorrência de cada conjunto de itens.

{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 definido como 50. // Muito importante. Obrigado, Steffen, por lembrar isso.

Faz máximas = {UMA,B,C,E} ?

Faz fechado = {UMA,B,C,D} umand {B,C,D,E} ?

Mike John
fonte

Respostas:

5

Encontrei uma definição um pouco estendida nesta fonte (que inclui uma boa explicação). Aqui está uma fonte mais confiável (publicada): CHARM: Um algoritmo eficiente para mineração de conjuntos de itens fechados por Mohammed J. Zaki e Ching-jui Hsiao .

Segundo esta fonte:

  • Um conjunto de itens é fechado se nenhum dos seus superconjuntos imediatos tiver o mesmo suporte que o conjunto de itens
  • Um conjunto de itens é máximo frequente se nenhum de seus superconjuntos imediatos for frequente


Algumas observações:

  • É necessário definir um min_suporte (suporte = o número de conjuntos de itens que contém o subconjunto de interesse dividido pelo número de todos os conjuntos de itens) que define qual conjunto de itens é frequente . Um conjunto de itens é frequente se o seu suporte> = min_support.
  • Em relação ao algoritmo, apenas conjuntos de itens com min_support são considerados quando se tenta encontrar o máximo de conjuntos de itens frequentes e fechados.
  • O aspecto importante na definição de fechado é que não importa se um superconjunto imediato existe com mais suporte, apenas os superconjuntos imediatos com exatamente o mesmo suporte importam.
  • máximo frequente => fechado => frequente, mas não vice-versa.

Aplicação ao exemplo do OP

Nota:

  • Não verificou as contagens de suporte
  • Digamos min_support = 0.5. Isso será cumprido se min_support_count> = 3
{A} = 4; não foi fechado devido a {A, E}
{B} = 2; não frequente => ignorar
{C} = 5; não foi fechado devido a {C, E}
{D} = 4; não fechado devido a {D, E}, mas não máximo devido, por exemplo, {A, D}
{E} = 6; fechado, mas não máximo devido a, por exemplo, {D, E}

{A, B} = 1; não frequente => ignorar
{A, C} = 3; não foi fechado devido a {A, C, E}
{A, D} = 3; não foi fechado devido a {A, D, E}
{A, E} = 4; fechado, mas não máximo devido a {A, D, E}
{B, C} = 2; não frequente => ignorar
{B, D} = 0; não frequente => ignorar
{B, E} = 2; não frequente => ignorar
{C, D} = 3; não foi fechado devido a {C, D, E}
{C, E} = 5; fechado, mas não máximo devido a {C, D, E}
{D, E} = 4; fechado, mas não máximo devido a {A, D, E}

{A, B, C} = 1; não frequente => ignorar
{A, B, D} = 0; não frequente => ignorar
{A, B, E} = 1; não frequente => ignorar
{A, C, D} = 2; não frequente => ignorar
{A, C, E} = 3; máximo frequente
{A, D, E} = 3; máximo frequente
{B, C, D} = 0; não frequente => ignorar
{B, C, E} = 2; não frequente => ignorar
{C, D, E} = 3; máximo frequente

{A, B, C, D} = 0; não frequente => ignorar
{A, B, C, E} = 1; não frequente => ignorar
{B, C, D, E} = 0; não frequente => ignorar
Steffen
fonte
O link de origem está quebrado, apenas informando. E sim, o min_support é muito importante, estou usando .50
Mike John
1
Desculpe por isso, consertado.
Steffen
1
mudou min_support = 0,5 <=> min_support_count = 3 e alterou o aplicativo para o exemplo de acordo.
Steffen
Use APRIORI, e você pode economizar muito contando e construindo conjuntos de itens ...
Possui QUIT - Anony-Mousse 28/13/13
@ Anony-Mousse, eu sei APRIORI ... Passei por cima dos conjuntos de itens manualmente para explicar o conceito de conjuntos de itens freqüentes fechados e máximos da maneira mais detalhada possível, já que essa era a fonte de confusão do OP (IMHO).
Steffen
1

Você pode querer ler o algoritmo APRIORI. Evita itens desnecessários por poda inteligente.

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

B não é frequente, remova.

Construa e conte conjuntos de dois itens (nenhuma mágica ainda, exceto que Bjá está fora)

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

Tudo isso é frequente (observe que tudo o que tinha Bnão pode ser frequente!)

Agora use a regra de prefixo. SOMENTE combine conjuntos de itens começando com os mesmos itens n-1. Remova tudo, onde qualquer subconjunto não for frequente. Conte os conjuntos de itens restantes.

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

Observe que isso {A,C,D}não é frequente. Como não há prefixo compartilhado, não pode haver um conjunto maior de itens frequentes!

Observe quanto menos trabalho eu fiz!

Para conjuntos de itens máximos / fechados, verifique subconjuntos / superconjuntos.

Observe que {E}=6, por exemplo , e {A,E}=4. {E}é um subconjunto, mas possui um suporte mais alto, ou seja, está fechado, mas não é o máximo. {A}não é nenhum, pois não possui suporte mais alto que {A,E}, isto é, é redundante .

Possui QUIT - Anony-Mousse
fonte