Como recomendar algo
a partir de experiências passadas
Como acontece com refatoração no desenvolvimento de software, ví a importância de escrever um outro texto explicando o algoritmo de Regra de Associação. Por exemplo, em 2014, eu já havia postado sobre este assunto, porém foi com uma implementação no SQL Server 2014. Ao re-ler o texto, contudo, senti falta de algumas coisas importantes.
Regras de Associação
As regras de associação permitem que elementos em um conjunto de dados sejam expressos como 𝑋→𝑌, e lê-se 𝑋 implica em 𝑌, desde que 𝑋 e 𝑌 sejam sub-conjuntos da base de dados em questão e os conjuntos de itens não tenham intereceptação entre si 𝑋∩𝑌.
Como exemplo, {𝑙𝑒𝑖𝑡𝑒,𝑝ã𝑜}→{𝑜𝑣𝑜𝑠} é uma associação que diz que quando se encontra os itens 𝑙𝑒𝑖𝑡𝑒 e 𝑝ã𝑜 em uma ocorrência, é esperado que o 𝑜𝑣𝑜𝑠 também apareça na transação.
A regra de associação pode ser feita através de um processo exaustivo computacionalmente, e que resulta em um conjunto de regras bastante expressivo mesmo com um conjunto de dados pequeno. Uma alternativa elegante para esse cálculo é já definir o suporte e confiança na parametrização do algoritmo para que haja a poda de regras que não atendam esse valor mínimo aceitável.
Seguindo essa abordagem, para avaliar a qualidade de associação do algoritmo, os termos de suporte e confiança devem ser utilizados. O suporte implica na frequência de vezes que uma determinada regra é aplicável ao conjunto de dados, e a confiança é a frequência na qual os elementos de 𝑌 aparecem no conjunto de dados com transações que possuem 𝑋.
Formalização matemática
A equação do suporte é dada por:
e o cálculo da confiança é:
Formalmente pode-se definir que uma regra de associação possui um conjunto de dados, representado por 𝐼={𝑖1,𝑖2,…,𝑖𝑛}. Também possui um conjunto de transações, onde cada transação 𝑇 é um sub-conjunto de 𝑇⊆𝐶, e que a implicação dos subitens 𝑋→𝑌, sendo que 𝑋⊂𝐼, 𝑌⊂𝐼, 𝑋∩𝑌=𝜙.
Exemplo 1
Para exemplificar a aplicação de suporte e confiança na geração de regras de associação, imagine esta base de dados com transações. Onde Zero significa que não havia o item na compra, e Um significa que o item estava na compra. Cada linha é uma transação e a coluna é o item no pedido.
| ID | Leite | Pão | Ovos |
| 1 | 1 | 0 | 1 |
| 2 | 1 | 1 | 0 |
| 3 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 |
| 5 | 0 | 0 | 1 |
Ao se observar a base de dados, são encontradas cinco transações (linhas) e três produtos (colunas). A regra gerada que explica 𝑙𝑒𝑖𝑡𝑒→𝑝ã𝑜 tem o suporte de 0.60, porque ela aparece em três das cinco transações encontradas na base de dados ( 3/5=0.6 ).
Já a confiança desta regra é de 0.75 porque o 𝑝ã𝑜 aparece em três transações, das quatro vezes que existe 𝑙𝑒𝑖𝑡𝑒 na base de dados ( 3/4=0.75 ).
Exemplo 2
Uma nova base de dados, mas seguindo a mesma ideia de Zeros onde aquele item não estava presente na transação e o Um estava.
| ID | Pão | Leite | Fralda | Cerveja | Ovo | Café |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 1 | 1 | 0 |
| 3 | 0 | 1 | 1 | 1 | 0 | 1 |
| 4 | 1 | 1 | 1 | 1 | 0 | 0 |
| 5 | 1 | 1 | 1 | 0 | 0 | 1 |
Ao analisar a regra {Leite, Fralda} → Cerveja é possível ver que existem estes três itens (Leite, Fralda e Cerveja) comprados em conjunto apenas duas vezes nas cinco transações, gerando um suporte de 0.4 (2/5=0.4). E, então, a confiança é calculada a partir do resultado do suporte para os itens totais (Leite, Fralda e Cerveja) que é encontrado duas vezes, divididos pelo suporte dos itens predecessores (Leite e Fralda), que foram encontrados três veses. Gerando a confiança de 0.66 (2/3 = 0.66).
Para esse conjunto de dados, utilizando o processo de força bruta, seriam criadas 602 regras. Esse número se dá pela formalização da equação 𝑅𝑒𝑔𝑟𝑎𝑠=3𝑑−2𝑑+1+1. Sendo que D é o numero de itens (no caso, os 6 produtos possíveis). Ao encontrar estas 602 regras, mais de 80% delas seriam inúteis ao utilizar os métodos de avaliação de suporte = 20% e confiança = 50%, sendo então apropriado evitar o processo de força bruta para não desperdiçar poder computacional e tempo.
Melhorando a abordagem
Uma definição formal aceita para o algoritmo de regras de associação diz que a regra 𝑋→𝑌 é válida para o conjunto de dados 𝐷 com suporte 𝑆 e confiança 𝐶. Se o % do 𝑆 das transações em 𝐷 contiverem 𝑋∪𝑌 e % mínimo de 𝐶 das transações em 𝐷 que contêm 𝑋 também conter 𝑌.
Uma abordagem para melhorar o poder computacional do algoritmo sugere que o processo seja dividido em duas fases, sendo:
- Geração de itens frequentes: Todos os itens que forem definidos como frequentes, por satisfazer o mínimo de suporte definido no início do algoritmo.
- Geração das regras: Extrair todas as regras que satisfaçam a confiança, a partir dos dados gerados pelos itens frequentes.
E esta abordagem deixa o gancho para a próxima publicação, que vou falar sobre o algoritmo Apriori, que é importante para seguir explicando o algoritmo de Regra de Associação.
Material de referência
Para trabalhar com Regra de Associação na minha dissertação do mestrado, usei referências de Introdução ao Data Mining. Mineração de Dados
