Algoritmo Apriori Fp-growth 6w606v

Introdução a Análise de Associação Utilizando Algoritmo Apriori e WEKA José Cavalcante Reis Neto Apresentação IFAL 23/07/2014

Quem sou eu ? 

Bacharel em Ciência da Computação 2012;  Mestrando no Programa de pós-graduação em Informática da UFAL (Mestrado em Informática)  Colaborador do Laboratório de Computação Pervasiva da UFAL ( COMPE)  Pesquisando atualmente em M-Health, HealthCare, Cyber-Physical Systems e Verificação Formal (Petri Nets), Segurança na especificação de dispositivos médicos baseado na ISO 14971;

Roteiro  Introdução  Motivação  Contador

de e  Algoritmo Apriori  WEKA  Conclusão

Introdução – O que é mineração É

a transformação de grandes quantidades de dados em padrões e regras significativas.  Empresas como Google e Yahoo - o que eles planejam fazer com com todas as suas informações?  A Walmart é uma das mais avançadas empresas em mineração de dados e na aplicação de seus resultados ao negócio.

Introdução – Análise de Associação  Está

sendo largamente utilizada no mercado;  Descobrir relacionamentos contidos de forma implícita em grandes conjuntos de dados;  Representar padrões, sempre relacionando dois conjuntos distintos para obter informação.

Introdução – Análise de Associação 

Uma regra de associação é uma expressão de implicação que segue a forma X  Y , onde X e Y são conjuntos disjuntos de itens ou seja X Y  

Motivação 

Apresentar relacionamentos entre itens que a principio são desconhecidos;



Descobrir padrões a partir de um conjunto grande de dados de transações pode ser computacionalmente custoso.



Agregar novos valores a um determinado produto;



Organização estratégica de objetos em um supermercado;

Fonte : Livro - Introdução ao Data Mining: Mineração de Dados - Pang-Ning Tan, Michael Steinbach e Vipin Kumar , editora : Editora Ciência Moderna

Regra de Associação 

Contador de e : Consiste no somatório da frequência de um determinado conjunto X considerando o conjunto de dados.



Uma regra de associação é uma expressão de implicação que segue a forma X  Y , onde X e Y são conjuntos disjuntos de itens ou seja X Y  

Conjunto de Itens e Contador de e  e

: Determina a freqüência na qual uma regra é aplicável a um determinado conjunto de dados; (geralmente usado para eliminar regras de baixo interesse)

 Confiança:

Determina a frequência na qual os itens de um determinado conjunto Y aparecem em transações que contenham X ;

 e

s( X  Y ) 

 (X Y ) N

 Confiança

 (X Y ) c( X  Y )   (X )

e ( Fraldas -> Cerveja) = 60% Confiança (Fraldas-> Cerveja) = 75%

Problemas de Mineração de Regras de Associação 

   

A descoberta de regra de associação é um processo muito custoso.  e >= minsup  Confiança >= minconf • Onde o Minisup e o Miniconf são os limites mínimos de e e confiança correspondentes. Geração de Conjuntos de Itens Frequentes;  e X -> Y > minsup; Geração de Regras;  Confiança X->Y > minconf Conjunto de Itens Frequentes (minsup); Geração de Regras;(regras fortes)

Conjunto de itens Candidatos

Contando e para o conjunto de itens candidatos O

conjunto de itens candidatos é formado pela quantidade em que cada candidato aparece em uma determinada transação.

 Por

exemplo o candidato “a“ parece nas transações a,ab,abc a cada uma das transações acrescenta-se 1 ao valor do contador de e de “a”;

Conjunto de itens frequentes

Transactions

N

TID 1 2 3 4 5

Items Bread, Milk Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke

w

List of Candidates

M

Apriori O

principio Apriori é uma forma efetiva de se eliminar alguns dos conjuntos de itens sem contar seus valores de e  Principio Apriori – Se um conjunto de itens é frequente então todos os seus subconjuntos também devem ser frequentes.  Obs.: Itens frequentes são que observam a lei de ser superior ao minsup.

Poda Por intens infrequentes ( Anti-Monotonica) – Define-se que a medida do e para um determinado conjunto Y de itens nunca excede o e de seus subconjuntos X.

 Definição

Exemplificando o Funcionamento Do algoritmo Apriori

60%; -> 3

Geração dos itens Candidatos (Força Bruta)

Geração dos itens Candidatos (Fusão de intes frequentes)

Geração de Regras baseado em confiança  

 

Para uma regra gerada a partir de um mesmo conjunto de item frequente Y temos que; Sempre que uma regra for gerada a partir de um subconjunto X´ de X, onde, o contador de e de X´ é maior ou igual ao do X, então, a regra de confiança de X´ nunca poderá ser maior do que a confiança de X. Com isso se X for menor do que minconf então as subsequentes regras podem ser eliminadas; X -> Y - X || X´ -> Y – X´ onde X´ está contido em X;

 ( X  (Y  X ))  (Y ) c( X ´ Y  X ´)   ( X ´Y  X ´)   (Y ) c( X  Y  X )    ( X ´)  ( X ´)  (X )  (X )

      

 



Suponha o conjunto Y do itens frequentes composto por ( Pão,Cerveja,Fralda) Suponha um subconjunto de Y denomiado X composto por (Pão e Cerveja); Suponha um subconjunto de X denomiado X´ composto por (Pão); Logo, X->Y-X = (Pão,Cerveja)-> Fralda; Assim X´->Y-X´ = (Pão)-> Fralda,Cerveja; Temos, confiança X = Y/(Pão,Cerveja); Confiança de X´ = Y/(Pão); Então temos que X > X´ ; 2/2 >= 2/4 ; Se confiança de X é maior e tem baixa confiança logo X´ obrigatoriamente também terá confiança baixa; -I -N 100 -T 0 -C 0.5 -D 0.06 -U 1.0 -M 0.4 -S -1.0 -c -1

ABC =>{}

AB =>C

AC =>B

BC =>A

A =>BC

B =>AC

C =>BA

Uma Introdução à ferramenta Weka

WEKA  Significa

(Waikato Environment for Knowledge Analysis ) criado pela Universidade de Waikato;  Possui licença GPL;  É uma coleção de algoritmos de aprendizagem de máquina para resolver problemas de mineração de dados.  http://www.cs.waikato.ac.nz/ml/weka/index.ht ml

Os dados que foram utilizados                    

@RELATION compras @attribute leite {sim, não} @attribute ovos {sim, não} @attribute café {sim, não} @attribute açúcar {sim, não} @attribute fraldas {sim, não} @attribute manteiga {sim, não} @attribute farinha {sim, não} @attribute cerveja {sim, não} @data sim, sim, sim, sim, sim, sim, não, não sim, não, sim, não, não, não, sim, não sim, sim, não, sim, não, não, não, não não, não, sim, sim, não, não, não, não não, não, não, não, sim, não, não, não sim, sim, não, não, não, sim, não, não sim, sim, sim, sim, não, não, não, não não, sim, não, não, não, sim, sim, não sim, sim, sim, sim, não, sim, não, não não, não, sim, não, sim, não, não, sim

Scheme: weka.associations.Apriori -N 10 -T 1 -C 1.5 -D 0.05 -U 1.0 -M 0.5 -S -1.0 -c -1 Relation: compras Instances: 10 Attributes: 8 leite ovos café açúcar fraldas manteiga farinha cerveja Apriori Minimum : 0.55 (6 instances) Minimum metric : 1.5 Number of cycles performed: 9 Best rules found: 1. leite=sim 6 ==> ovos=sim farinha=não 5 conf:(0.83) < lift:(1.67)> lev:(0.2) [2] conv:(1.5) 2. ovos=sim 6 ==> leite=sim farinha=não 5 conf:(0.83) < lift:(1.67)> lev:(0.2) [2] conv:(1.5) 3. leite=sim farinha=não 5 ==> ovos=sim 5 conf:(1) < lift:(1.67)> lev:(0.2) [2] conv:(2) 4. ovos=sim farinha=não 5 ==> leite=sim 5 conf:(1) < lift:(1.67)> lev:(0.2) [2] conv:(2) 5. leite=sim 6 ==> ovos=sim farinha=não cerveja=não 5 conf:(0.83) < lift:(1.67)> lev:(0.2) [2] conv:(1.5) 6. ovos=sim 6 ==> leite=sim farinha=não cerveja=não 5 conf:(0.83) < lift:(1.67)> lev:(0.2) [2] conv:(1.5) 7. leite=sim farinha=não 5 ==> ovos=sim cerveja=não 5 conf:(1) < lift:(1.67)> lev:(0.2) [2] conv:(2) 8. ovos=sim farinha=não 5 ==> leite=sim cerveja=não 5 conf:(1) < lift:(1.67)> lev:(0.2) [2] conv:(2) 9. leite=sim cerveja=não 6 ==> ovos=sim farinha=não 5 conf:(0.83) < lift:(1.67)> lev:(0.2) [2] conv:(1.5) 10. ovos=sim cerveja=não 6 ==> leite=sim farinha=não 5 conf:(0.83) < lift:(1.67)> lev:(0.2) [2] conv:(1.5)

    

  

Os parâmetros mais interessantes para a implementação são: -N indica o número de regras que será listado. -M indica o valor mínimo para e para consideração da regra. -T indica a métrica de ordenação (e Filtragem) das regras: -T 0 ordena pela métrica confidence, igual à confiança explicada anteriormente. -T 1 ordena pela métrica lift. -T 2 ordena pela métrica leverage. -T 3 ordena pela métrica conviction.

Medidas de interesse  Medidas

de interesse no Weka

 Lift;  Leverage;  Conviction;

Fatores de interesse 

O lift é calculado pela divisão da confiança de uma determinada regra c(A->B) pelo e do consequente s(B);



Dada uma regra de associação A -> B, esta medida indica o quanto mais freqüente torna-se B quando A ocorre.

LIFT 

Quando o lift obtido é maior que 1, pode-se dizer que o lado direito da regra ocorre com mais freqüência nas transações em que o lado esquerdo ocorre.



Quando o lift é menor que 1, o lado direito ocorre com mais freqüência nas transações em que o lado esquerdo não ocorre.



Dessa forma, as regras que possuem lift maior que 1 são mais interessantes que as demais, sendo o lift diretamente proporcional à relação entre os dois lados da regra.

Leverage 

Dada uma regra L -> R, leverage mede a diferença entre a freqüência de co-ocorrência de L e R e as freqüências de L e R separadamente, ou seja, (Pr(L;R) ) − (Pr(L) × Pr(R)). Valores acima de zero são desejáveis. Esta métrica é semelhante à lift.



É a diferença entre a Frequência de co-ocorrencia entre dois conjuntos e a frequencia desses dois conjuntos acontecerem separadamente.



mede o número de casos extra obtidos em relação ao esperado (à independência)

Leverage 

Quando o leverage obtido é maior que zero, há a indicação de que os dois lados da regra ocorreram juntos, em número de transações maior que o esperado, caso os itens analisados sejam completamente independentes.



Se o leverage for menor que zero, os dois lados ocorrem juntos em número menor que o esperado.



Para leverage igual a zero, os dois lados da regra ocorrem juntos, exatamente o esperado. Isso significa que ambos provavelmente são independentes.

Conviction 

Dada uma regra L -> R, conviction é a freqüência com que L ocorre sem R, dividida pela frequência com que as duas ocorrem juntas, ou seja:

(Pr( L)  Pr(! R)) Pr( L, R) 

Tenta capturar o grau de implicação entre A e C  valor 1 indica independência  Assimétrico

Conviction  Quando

a convicção de uma regra é igual a 1, pode-se dizer que os itemsets não possuem relação. Quanto maior a convicção, maior a relação entre X e Y. Uma convicção menor que 1 implica em relação negativa entre os itemsets, ou seja, quando X ocorre, Y tende a não ocorrer.

Conclusão  Importância

dos dados;  Importante saber o que buscar;  Ter conhecimento prévio do domínio do problema para poder eliminar as associações que não agregam informações.

Dúvidas ?

OBRIGADO PELA ATENÇÃO

Introdução ao Fp-growth

Fp-Growth  Possui

uma abordagem radicalmente diferente para descobrir conjuntos de itens frequentes.  O Algoritmo não concorda com o paradigma gerar e testar do Apriori, em vez disso usa uma estrutura de árvore chamada de FP extraindo o conjunto de itens frequentes diretamente desta árvore.

Analisando item frequentes  Trata-se

de uma abordagem de leitura bottom up da árvore.  Começa a ler do item mais infrequente para o mais frequente.  Para encontrar os itens frequentes devese analisar primeiro o mais baixo de todos os subconjunto se este é frequente, sendo este frequente, deve-se analisar gradativamente os seus superconjuntos.

O Algoritmo FP-Growth  Não

geram conjuntos de itens frequentes duplicados;  Gera de modo eficiente o conjunto de itens frequentes;  Para determinados conjuntos de dados o Fp-growth tem melhor desempenho do que o Apriori.  Salvo quando existe um problema com o fator de compactação.

Padrões de Associação  Mesmos

os bancos de dados pequenos podem gerar até centenas de regras de associação em determinados limites de e e confiança.  Muito desses padrões não são interessantes para se extrair informações  “ O lixo de uma pessoa pode ser o tesouro de outra”

Padrões de Associação 

Padrões de associação podem ser encontrados através de métodos estatísticos;  Utilizar a medida de interesse objetivo que utiliza estatística derivada de dados para determinar se um padrão é interessante.  Utilizar medida subjetiva de interesse, relevância subjetiva : manteiga -> pão em detrimento a fraldas -> cerveja;  Incorporar conhecimento subjetivo na avaliação de padrões é uma tarefa difícil porque requer conhecimento prévio de especialista o domínio.

Medidas Objetivas de Interesse É

uma abordagem orientada a dados para se avaliar a qualidade de padrões de associação.  É independente de domínio e requer o mínimo de informação do usuário além da especificação de um limite para filtragem de padrões de baixa qualidade.  Utilização da tabela de Contigência.

Tabela de Contigência

Exemplo Chá, Café

Fatores de interesse  Lift

-> Regras com alta confiaça podem ser enganosas por que a medida de confiança ignora o e do conjunto de intens que aprece no consequente da regra.  O lift é calculado pela divisão da confiança de uma determinada regra c(A->B) pelo e do consequente s(B);

Fator de interesse 

Medida do fator de interesse : esta medida foca na independência estatística dos conjuntos de interesse. I(A,B) ;

s( A, B) Nf 11 I ( A, B)   . s( A)  s( B) f 1  f  1 

I(A,B) : = 1, Se A e B forem independentes;  I(A,B) > 1, Se A e B forem relacionados positivamente  I(A,B) < 1, Se A e B forem relacionados negativamente.  Ex chá -> café tem correlação negativa entre pessoas que bebem chá e as que bebem café;

FpGrowth com o Exemplo do Livro

40%; -> 2