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.

Transcript

1. Extraindo regras de associação com PHP 1
2. 2 Raphael de Almeida
3. DojoRio PHPRio RubyOnRio Mestrando Computação UFF
4. https://t.me/archDesignOO Arquitetura de sistemas e Design OO
5. • Mineração de Dados • Regras de Associação • Algoritmos • Ferramentas em PHP • Demo Sumário 5
6. Mineração de Dados 6
7. Mineração de dados 7
8. Mineração de dados 8
9. Mineração de dados 9
10. Mineração de dados 10
11. Mineração de dados 11 Técnicas
12. Mineração de dados 12 Técnicas
13. Regras de Associação 13
14. 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.
15. Regras de Associação 15 Antecedente Consequente
16. Regras de Associação 16 As regras devem satisfazer o limite mínimo de suporte e confiança.
17. 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;
18. 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.
19. Regras de Associação 19 Conjunto frequente (frequent pattern) é o conjunto de itens satisfaz o suporte mínimo
20. 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.
21. 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
22. Algoritmos 22
23. Apriori FP-Growth Algoritmos 23
24. 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
25. 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.
26. 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.
27. 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
28. 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
29. FP-Growth 29 Necessita de apenas duas consultas ao banco de dados
30. 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.
31. 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
32. 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.
33. 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
34. 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
35. 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
36. 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)
37. 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é
38. 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
39. 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
40. 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
41. 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
42. 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
43. 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
44. 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
45. 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
46. 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 - -
47. 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 - - -
48. Vantagens (comparado com Apriori): • Estrutura em árvore é mais compacta, consumindo menos memória • Sem geração de candidatos FP-Growth 48
49. 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
50. 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
51. 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
52. Ferramentas em PHP 52
53. 53 Ferramentas em PHP Rubix ML :) Desenvolvimento ativo Várias algoritmos :( Não tem Regras de Associação https://rubixml.com/
54. 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. 55 Ferramentas em PHP adryanev/php-fpgrowth :) FP-Growth :( Sem documentação Baixo desempenho https://github.com/adryanev/php-fpgrowth
56. 56 Chega de falar...
57. 57 Demo Transações Regras obtidas
58. 58 Referências Dataset http://www.philippe-fournier-viger.com/spmf/datasets/OnlineRetailZZ.txt http://www.philippe-fournier-viger.com/spmf/datasets/OnlineRetailZZAtrributes.xlsx
59. 59 Referências
60. OBRIGADO @raph_almeida