Share
Embed
Extraindo regras de associação com PHP
Palestra apresentada no Darkmira Tour PHP 2020
https://php.darkmiratour.rocks/2020/
Mineração de dados, regras de associação e como aplicar isso em PHP.
raphaeldealmeida
December 13, 2020
Transcript
60 slides
-
• Mineração de Dados • Regras de Associação • Algoritmos
• Ferramentas em PHP • Demo Sumário 5 -
Regras de Associação 14 A mineração de regras de associação
procura encontrar relacionamentos de correlação entre um grande conjunto de itens de dados, normalmente transações. -
Regras de Associação 16 As regras devem satisfazer o limite
mínimo de suporte e confiança. -
Regras de Associação 17 O suporte de uma regra A
⇒ B, é o total das transações que contêm A ∪ B em relação ao número total de transações analisadas; -
Regras de Associação 18 Já a confiança calcula a força
da regra. Sendo A ⇒ B, C é o total de transações que contêm A ∪ B em relação a todas as transações que contêm A. -
Regras de Associação 19 Conjunto frequente (frequent pattern) é o
conjunto de itens satisfaz o suporte mínimo -
Regras de Associação 20 Abordagem padrão: 1. Encontrar todos os
conjuntos de itens frequentes que satisfazem o suporte mínimo; 2. Gerar regras de associação a partir dos conjuntos de itens frequentes que satisfazem suporte e confiança mínimos. -
Regras de Associação 21 Abordagem padrão: 1. Encontrar todos os
conjuntos de itens frequentes que satisfazem o suporte mínimo; 2. Gerar regras de associação a partir dos conjuntos de itens frequentes que satisfazem suporte e confiança mínimos. Maior custo -
Junção: geração de conjuntos com k-itens. Poda: os conjuntos que
não atingem o suporte mínimo não são considerados conjuntos frequentes, e não passam para próxima iteração. Apriori 24 -
Apriori 25 S Nasreen, MA Azam, K Shehzad, U Naeem.
“Frequent Pattern Mining Algorithms for Finding Associated Frequent Patterns for Data Streams: A Survey”. Procedia Computer Science 37:109, 2014. -
Para 104 conjuntos de apenas 1 item frequente, o algoritmo
a priori precisará gerar mais de 107 candidatos de comprimento 2, acumular e testar suas frequências. Apriori 26 C Győrödi, R Győrödi, S Holban. “A comparative study of association rules mining algorithms”. SACI 2004. -
Para 104 conjuntos de apenas 1 item frequente, o algoritmo
a priori precisará gerar mais de 107 candidatos de comprimento 2, acumular e testar suas frequências. Apriori 27 C Győrödi, R Győrödi, S Holban. “A comparative study of association rules mining algorithms”. SACI 2004. Consulta ao banco de dados -
O algoritmo utiliza-se da estrutura de árvore para representar o
banco de dados, essa representação é chamada de frequent-pattern tree ou FP-Tree. FP-Growth 28 JCB Nandi, RM Pereira, G Felippe; “O Algoritmo de Associação Frequent Pattern-Growth na Shell Orion Data Mining Engine”; Anais SULCOMP, 2015 -
FP-Growth 30 1º Etapa Os dados são verificados e a
contagem de suporte para cada item é calculada, os padrões raros são excluídos da lista e os padrões restantes são classificados em ordem decrescente. -
FP-Growth 31 1º Etapa Os dados são verificados e a
contagem de suporte para cada item é calculada, os padrões raros são excluídos da lista e os padrões restantes são classificados em ordem decrescente. Não gera candidatos -
FP-Growth 32 2º Etapa FP-Tree é construída, usando o algoritmo
de FP-Growth em seguida os padrões frequentes são extraídos. -
Utiliza uma abordagem de dividir para conquistar que, consequentemente, reduz
o espaço de busca. FP-Growth 33 JCB Nandi, RM Pereira, G Felippe; “O Algoritmo de Associação Frequent Pattern-Growth na Shell Orion Data Mining Engine”; Anais SULCOMP, 2015 -
FP-Growth 34 TID TRANSAÇÃO 1 pão, manteiga, leite 2 manteiga,
leite, café 3 café, adoçante 4 pão, manteiga, café, adoçante 5 pão, manteiga, leite, adoçante 6 pão, manteiga, leite, café suporte mínimo: 50% 3 transações -
FP-Growth 35 Item Frequência manteiga 5 pão 4 leite 4
café 4 adoçante 2 Criar tabela ordenada com a frequência de cada item -
FP-Growth 36 Item Frequência manteiga 5 pão 4 leite 4
café 4 adoçante 2 Remover itens abaixo do suporte mínimo (3) -
FP-Growth 37 TID TRANSAÇÃO Itens ordenados 1 pão, manteiga, leite
manteiga, pão, leite 2 manteiga, leite, café manteiga, leite, café 3 café, adoçante café 4 pão, manteiga, café, adoçante manteiga, pão, café 5 pão, manteiga, leite, adoçante manteiga, pão, leite 6 pão, manteiga, leite, café manteiga, pão, leite, café -
FP-Growth 38 NULL TID Itens ordenados 1 manteiga, pão, leite
2 manteiga, leite, café 3 café 4 manteiga, pão, café 5 manteiga, pão, leite 6 manteiga, pão, leite, café FP-Tree -
FP-Growth 39 NULL TID Itens ordenados 1 manteiga, pão, leite
2 manteiga, leite, café 3 café 4 manteiga, pão, café 5 manteiga, pão, leite 6 manteiga, pão, leite, café manteiga: 1 pão: 1 leite: 1 -
FP-Growth 40 NULL TID Itens ordenados 1 manteiga, pão, leite
2 manteiga, leite, café 3 café 4 manteiga, pão, café 5 manteiga, pão, leite 6 manteiga, pão, leite, café manteiga: 2 pão: 1 leite: 1 leite: 1 café: 1 -
FP-Growth 41 NULL TID Itens ordenados 1 manteiga, pão, leite
2 manteiga, leite, café 3 café 4 manteiga, pão, café 5 manteiga, pão, leite 6 manteiga, pão, leite, café manteiga: 2 pão: 1 leite: 1 leite: 1 café: 1 café: 1 -
FP-Growth 42 NULL TID Itens ordenados 1 manteiga, pão, leite
2 manteiga, leite, café 3 café 4 manteiga, pão, café 5 manteiga, pão, leite 6 manteiga, pão, leite, café manteiga: 3 pão: 2 leite: 1 leite: 1 café: 1 café: 1 café: 1 -
FP-Growth 43 NULL TID Itens ordenados 1 manteiga, pão, leite
2 manteiga, leite, café 3 café 4 manteiga, pão, café 5 manteiga, pão, leite 6 manteiga, pão, leite, café manteiga: 4 pão: 3 leite: 1 leite: 2 café: 1 café: 1 café: 1 -
FP-Growth 44 NULL TID Itens ordenados 1 manteiga, pão, leite
2 manteiga, leite, café 3 café 4 manteiga, pão, café 5 manteiga, pão, leite 6 manteiga, pão, leite, café manteiga: 5 pão: 4 leite: 1 leite: 3 café: 1 café: 1 café: 1 café: 1 -
FP-Growth 45 Frequência inversa Conditional base pattern café {manteiga, pão,
leite: 1} {manteiga, pão: 1} {manteiga, leite: 1} leite {manteiga, pão: 3} {manteiga: 1} pão {manteiga: 4} manteiga - NULL manteiga: 5 pão: 4 leite: 1 leite: 3 café: 1 café: 1 café: 1 café: 1 -
FP-Growth 46 Frequência inversa Conditional base pattern Conditional FP tree
café {manteiga, pão, leite: 1} {manteiga, pão: 1} {manteiga, leite: 1} {manteiga: 3} leite {manteiga, pão: 3} {manteiga: 1} {manteiga: 4, pão: 3} pão {manteiga: 4} {manteiga: 4} manteiga - - -
FP-Growth 47 Frequência inversa Conditional base pattern Conditional FP tree
FP Generated café {manteiga, pão, leite: 1} {manteiga, pão: 1} {manteiga, leite: 1} {manteiga: 3} {manteiga, café} leite {manteiga, pão: 3} {manteiga: 1} {manteiga: 4, pão: 3} {manteiga, leite} {pão, leite} {manteiga, pão, leite} pão {manteiga: 4} {manteiga: 4} {manteiga, pão} manteiga - - - -
Vantagens (comparado com Apriori): • Estrutura em árvore é mais
compacta, consumindo menos memória • Sem geração de candidatos FP-Growth 48 -
FP-Growth 49 NULL TID TRANSAÇÕES 1 café, pão, manteiga 2
leite, cerveja, pão, manteiga 3 café, pão, manteiga 4 leite, café, pão, manteiga 5 cerveja 6 manteiga 7 pão 8 feijão 9 arroz, feijão 10 arroz manteiga: 5 pão: 4 café: 3 café: 1 Exemplo de árvore compacta -
FP-Growth 50 Desvantagens: • Algoritmo mais complexo • 80% do
processamento usado na navegação da FP-Tree • Refaz toda estrutura quando novas transações são adicionadas à base de dados -
FP-Growth 51 Frequência inversa Conditional base pattern café {manteiga, pão,
leite: 1} {manteiga, pão: 1} {manteiga, leite: 1} leite {manteiga, pão: 3} {manteiga: 1} pão {manteiga: 4} manteiga - NULL manteiga: 5 pão: 4 leite: 1 leite: 3 café: 1 café: 1 café: 1 café: 1 Navegação da raiz => folha, folha=>raiz -
53 Ferramentas em PHP Rubix ML :) Desenvolvimento ativo Várias
algoritmos :( Não tem Regras de Associação https://rubixml.com/ -
54 Ferramentas em PHP PHP-ML :) Regras de associação :(
Não tem FP-Growth Pouca atividade https://php-ml.readthedocs.io/en/latest/ -
55 Ferramentas em PHP adryanev/php-fpgrowth :) FP-Growth :( Sem documentação
Baixo desempenho https://github.com/adryanev/php-fpgrowth