Nesta coluna vamos continuar nosso estudo sobre algoritmos de Data Mining.

Desta vez estudaremos um algoritmo que permite a geração de regras de associação a partir de um conjunto de transações com itens em um banco de dados. Como veremos, este algoritmo trabalha baseado em dois parâmetros iniciais que controlam a geração das regras de associação.

Regras de associação

A motivação por traz de um algoritmo que gera regras de associação relaciona-se com a grande quantidade de aplicações possíveis para estas regras. Questões a respeito das características de consumo sempre foram analisadas com o objetivo de maximizar não apenas a quantidade de vendas, mas também a quantidade de vendas de certos produtos. Na mineração de regras de associação é comum encontrar questões como:

O que caracteriza quem compra o produto X?

O que é tipicamente comprado juntamente com o produto Y?

Que pares de produtos são comprados em conjunto?

Quem compra isso e aquilo, compra a seguir o quê?

Talvez o exemplo mais comum relacionado ao estudo de regras de associação seja a famosa história das fraldas e cerveja. Esta história conta que um determinado supermercado aumentou a venda de cervejas colocando-as próximas ao local onde as fraldas eram vendidas. De acordo com esta história, as regras de associação analisadas indicaram que quem compra fraldas também compra cervejas, com uma margem de erro, e colocar estes dois produtos em conjunto iria aumentar as vendas.

Notem que o algoritmo apenas indicou a correlação dos produtos e, a partir do conhecimento deste fato, uma ação foi tomada. Como exemplo de regra, podemos obter a seguinte frase abaixo:

Se o cliente comprou o produto A1 e o produto A4, então ele também comprou o produto A6 em 74% dos casos. Esta regra aplica-se a 20% dos casos estudados.

Sendo um pouco mais formal, podemos definir as regras de associação da seguinte forma:

A => B, onde A e B são conjuntos que podem conter um ou mais elementos. O conjunto total de transações é chamado de conjunto T. É importante lembrar também que cada regra de associação gerada por esta técnica possui dois parâmetros.

O primeiro parâmetro é o suporte, ou seja, o percentual de vezes que o conjunto A aparece no conjunto de transações. Na regra apresentada acima, o valor 20% indica o suporte, pois é dito que a regra aplica-e a 20% dos casos estudados.

O segundo parâmetro, a confiança, indica o percentual de ocorrência da regra. Na regra de exemplo apresentada anteriormente, o valor 74% indica a confiança pois, dos 20% casos onde os produtos A1 e A4 são encontrados, em 74% também se encontra o produto A6.

Os parâmetros confiança e suporte são essenciais para o funcionamento do algoritmo. Eles vão determinar diretamente tanto a quantidade como a qualidade das regras geradas e saber trabalhar com estes parâmetros são fundamentais para a geração de regras de associação significativas para a análise.

É importante lembra que o algoritmo não se limita apenas a análise de produtos vendidos. Na verdade esta análise de produtos na transação (também chamado de carrinho de compras, tíquete ou mesmo cesta de produtos) é denominada Market Basket Analysis. Outra aplicação relacionada com compras de produtos chama-se Cross-selling, que funciona assim:

1. Cliente inclui o produto A no cesto;
2. A loja conhece a regra A => B;
3. A regra tem uma certa confiança (geralmente acima de 20%);
4. Como ação, a loja informa que o artigo B pode interessar ao cliente. Dependendo da situação, pode-se inclusive oferecer um desconto no preço do artigo B;
5. O cliente decide comprar o artigo ou não.

Um último exemplo do uso de regras de associação está ligada à análise de navegação dos usuários em um site da Web. Esta análise se é baseada nos dados coletados pelo servidor Web onde cada link que o usuário clicou é armazenado. Este análise, chamada de ClickStream Analisys, funciona da seguinte maneira:

1. O usuário visita páginas A, B e C de um site por meio de links;
2. Conhecemos a regras como, por exemplo: {A,B,C} => {D}
3. A regra tem uma certa confiança (geralmente acima de 20%)
4. Como ação, após o usuário clicar na página C, sabendo que ele veio da página A e B, o site inclui dinamicamente uma referência para a página D.

Existem diversos outros exemplos. Contudo, é importante analisar se a ação que está sendo tomada a partir do conhecimento obtido pela regra de associação vale a pena. Ou seja, se não houver nenhum ganho a partir da ação que está sendo tomada isso não quer dizer, necessariamente, que o conhecimento obtido é inválido, mas sim que a ação tomada pode não ser a mais adequada.

O algoritmo

Para fazer a geração das regras de associação é necessário analisar um conjunto de dados com as transações. Neste contexto, a transação é considerada uma compra, onde o consumidor recebe um identificador da transação (tíquete) e este identificador relaciona os produtos comprados na transação. Em termos de bancos de dados, a transação é representada pelo o clássico relacionamento entre produtos, pedidos e itens de pedidos, como mostrado no MER da Figura 1.

Figura 1. Relacionamento clássico entre as tabelas de Pedidos, Itens de Pedidos e Produtos.

No diagrama apresentado na Figura 1, a tabela ITENSPEDIDOS possui uma chave primária composta pelas colunas PED_COD e PROD_COD. Existem duas chaves estrangeiras na tabela ITENSPEDIDOS. A primeira chave estrangeira relaciona a coluna PROD_COD da tabela ITENSPEDIDOS com a coluna PROD_COD, que é a chave primária da tabela PRODUTOS. A segunda chave estrangeira relaciona a coluna PED_COD, da tabela ITENSPEDIDOS, com a coluna PED_COD da tabela PEDIDOS, que é a chave primária da tabela PEDIDOS.

Existem alguns algoritmos para a geração de regras de associação. Talvez o mais popular seja o algoritmo APRIORI, implementado em diversas ferramentas de Data Mining (mineração de dados), como o Weka. Este algoritmo recebe como parâmetro um conjunto de transações T, o valor percentual S como o suporte e um valor percentual C para a confiança. O algoritmo gera um conjunto de regras no formato A => B [suporte, confiança], onde o conjunto A é chamado de antecedente da regra e o conjunto B é chamado de conseqüente. Cara regra gerada deve ser seu suporte e sua confiança maior ou igual ao suporte e confiança mínimo passado para o algoritmo, respectivamente.

O algoritmo APRIORI é dividido em duas partes. Na primeira parte são selecionados todos os subconjuntos de T que podem ser utilizados em alguma regra, ou seja, que contenham o suporte acima do suporte mínimo S. A segunda parte do algoritmo faz a geração das regras a partir dos subconjuntos gerados na primeira parte, sendo que estas regras devem ter uma confiança maior que a confiança mínima C.

Sem entrar em detalhes muito técnicos de como o algoritmo funciona, basta pensar que os quatro passos abaixo devem ser seguidos para a primeira parte do algoritmo:

PASSO 1: Inicializações.

Neste passo são iniciadas as estruturas de memória que conterão os dados trabalhados no algoritmo. É gerado uma estrutura que conterá os conjuntos com 1 elemento, isto é todos os elementos da base T são colocados neste conjunto. Chamaremos este conjunto de L1, pois ele contém apenas os conjuntos com um elemento, ou seja, todos os conjuntos unitários com os produtos. Inicia-se também um variável chamada K com o valor 2, pois ela será o indexador da estrutura que armazena os conjuntos.

PASSO 2: Gerar os subconjuntos

Neste passo é necessário gerar todos os subconjuntos possíveis de Lk-1 que tenham o tamanho K, pois é a partir destes subconjutos de Lk-1 que o algoritmo vai determinar quais podem ou não ser utilizados. Chamaremos todos os subconjuntos com tamanho K que podem ser gerados a partir de Lk-1 de Ck. Esta geração de subconjuntos é muito importante e, muitas vezes, é neste passo que o algoritmo demora.

PASSO 3: Filtrar os subconjuntos.

Neste passo vamos analisar cada elemento do conjunto Ck, que foi gerado no passo anterior. Calcula-se qual o suporte de cada elemento de Ck e selecionam-se apenas os elementos de Ck cujo suporte seja maior do que o suporte mínimo especificado como parâmetro e chamado de S.Todos os elementos de Ck cujo suporte seja maior do que o suporte mínimo são jogados dentro do conjunto Lk.

PASSO 4: Seleção do conjunto.

Todos os elementos de Ck cujo suporte seja maior do que o suporte mínimo especificado são armazenados em uma estrutura indexada por K chamada Uk. Em seguida, o algoritmo incrementa o contador K e verifica se existe algum elemento em Lk-1. Se existir, o algoritmo volta para o PASSO 2. Caso contrário, o algoritmo termina retornado a união de todos os elementos dos conjuntos Uk. É importante lembrar os elementos de Uk podem ser conjuntos de elementos como, por exemplo, o conjunto {A1, A4}, utilizado como antecedente da regra apresentada no começo deste artigo.

A segunda parte do algoritmo gera as regras a partir de todos os elementos retornados pelo primeiro passo. Este parte do algoritmo é bem simples: basta verificar para cada um dos elementos retornados pela primeira parte do algoritmo qual é o suporte deste conjunto em relação aos elementos de todos os conjuntos Lk.

Para fazer o download do algoritmo implementado em T-SQL basta clicar aqui.

Referências:

Paper original contendo a definição do algoritmo Apriori:

Agrawal R, Srikant R. “Fast Algorithms for Mining Association Rules”, VLDB. Sep 12-15 1994, Chile, 487-99, ISBN 1-55860-153-8.

http://www.acm.org/sigmod/vldb/conf/1994/P487.PDF

O que cerveja tem a ver com fraldas?

por Helio Gurovitz – Revista Info – 1997

http://www.datawarehouse.inf.br/artigos/cervejaefraldas.asp