Explicando o algoritmo de Regra de Associação

Regra de Associação

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:

Suporte

e o cálculo da confiança é:

Confianca

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 que é bastante raro de encontrar para vender hoje em dia. Mas também usei Introdução à mineração de dados: com Aplicações em R que ainda é facilmente encontrado. Porém, uma outra referência que usei (mas que não é de livro) é do artigo Interestingness measures for data mining: A survey.

 

Sobre Diego Nogare 322 Artigos
Diego Nogare é CDO - Chief Data Officer - na Lambda3. Também é professor em programas de pós graduação no Mackenzie e na FIAP, em São Paulo. Foi nomeado como Microsoft MVP por 11 anos seguidos, e hoje faz parte do programa Microsoft Regional Director.