Data Mining de Regras de Associação

A descoberta de regras de associação em bancos de dados relacionais ou data warehouses é uma das tarefas de mineração de dados (data mining) que possui o maior número de aplicações práticas. Este artigo inicia uma série de trabalhos que terão o objetivo principal de demonstrar como esta nova tecnologia pode ser aplicada em diferentes áreas de conhecimento.

Data Mining

A Mineração de Dados (Data Mining) é uma linha de pesquisa pertencente ao campo da Ciência da Computação que tem por objetivo oferecer estratégias automatizadas para a análise de grandes bases de dados de empresas, procurando extrair das mesmas informações que estejam implícitas, que sejam previamente desconhecidas e potencialmente úteis. A Mineração de Dados surgiu no início dos anos 90, a partir da reunião de ideias provenientes de diferentes áreas como Inteligência Artificial, Banco de Dados, Estatística, e Visualização de Dados. A principal motivação para o surgimento da Mineração de Dados encontra-se no fato de as organizações estarem armazenando de forma contínua uma enorme quantidade de dados a respeito de seus negócios nas últimas décadas. O conhecimento obtido pelas técnicas de Mineração de Dados é geralmente expresso na forma de regras e padrões.

Devido a sua grande aplicabilidade, as regras de associação encontram-se entre um dos mais importantes tipos de conhecimento que podem ser minerados em bases de dados. Estas regras representam padrões de relacionamento entre itens de uma base de dados. Uma de suas típicas aplicações é a análise de transações de compras (market basket analysis), um processo que examina padrões de compras de consumidores para determinar produtos que costumam ser adquiridos em conjunto. Um exemplo de regra de associação, obtida a partir da análise de uma base de dados real, que registra os produtos adquiridos por famílias cariocas em suas compras mensais, é dado por: {mini-pizza semi-pronta} Þ {suco de fruta em pó}. Esta regra de associação indica que as famílias que compram o produto {mini-pizza semi-pronta} tem maior chance de também adquirir o produto {suco de fruta em pó}.

Introdução às Regras de Associação

O problema da mineração de regras de associação foi primeiramente apresentado no ano de 1993. Nesta época, as regras eram mineradas a partir de bases de dados de transações (ou bases transacionais). As definições formais de regra de associação e base de dados transacional são apresentadas a seguir.

Seja I = {I1,I2,...In} um conjunto de itens. Seja D uma base de dados de transações, em que cada transação T é formada por um conjunto de itens onde T Í I. Cada transação possui um identificador chamado TID. Uma regra de associação é uma implicação da forma A Þ B, onde A e B podem ser conjuntos compostos por um ou mais itens, A Ì I, B Ì I, e A Ç B = Æ. A é chamado de antecedente da regra e B é chamado de consequente.

Dada uma regra A Þ B, a sua medida de suporte (Sup) representa a porcentagem de transações da base de dados que contêm os itens de A e B, indicando a relevância da mesma. Já a sua medida de confiança (Conf) representa, dentre as transações que possuem os itens de A, a porcentagem de transações que possuem também os itens de B, indicando a validade da regra. O problema da mineração de regras de associação, conforme definido originalmente em 1993, consiste em encontrar todas as regras de associação que possuam suporte e confiança maiores ou iguais, respectivamente, a um suporte mínimo (SupMin) e uma confiança mínima (ConfMin), especificados pelo usuário.

Para explicar o funcionamento deste processo, será apresentado um exemplo baseado numa pequena base de dados que armazena as compras efetuadas por clientes de um supermercado hipotético, como mostra a Tabela 1.

Observe que cada registro da base de dados armazena a relação de produtos adquiridos por um cliente específico. Um exemplo de regra de associação que poderia ser minerada nesta base de dados, através da utilização de uma ferramenta de data mining, é dado por: {cerveja} Þ {salaminho}. Note que duas das seis transações que compõem a base contêm os produtos {cerveja} e {salaminho}. Desta maneira, o suporte da regra {cerveja} Þ {salaminho} pode ser calculado da seguinte forma: 2 ¸ 6 = 33,33%. Observe agora que na base de dados, existem duas transações que contêm os produtos {cerveja} e {salaminho} juntos e três transações que contêm o produto {cerveja}. A confiança da regra {cerveja} Þ {salaminho} pode então ser calculada da seguinte maneira: 2 ¸ 3 = 66,67%. Este valor indica que 66,67% dos consumidores que compraram {cerveja} também compraram {salaminho}.

Outro índice estatístico comumente utilizado para definir o grau de interesse de uma regra de associação é denominado lift. O lift de uma regra de associação A Þ B indica o quanto mais freqüente torna-se B, quando A ocorre. Esta medida é computada por: Lift(A Þ B) = Conf(A Þ B) ÷ Sup(B). O lift da regra hipotética {cerveja} Þ {salaminho} é dado por: Conf({cerveja} Þ {salaminho}) ÷ Sup({salaminho}) = 66.67% ÷ 33.33% = 2. O resultado deste cálculo indica que os clientes que compram {cerveja} têm uma chance duas vezes maior de comprar {salaminho}.

Os primeiros softwares para mineração de regras de associação começaram a ser desenvolvidos em meados da década de 90, ainda em ambiente acadêmico. Hoje em dia já existem algumas dezenas de ferramentas comerciais capazes de minerar este tipo de padrão, desenvolvidas por grandes empresas. As ferramentas para mineração de regras de associação funcionam, tipicamente, da seguinte maneira. O usuário especifica a base de dados que deseja minerar e estabelece valores mínimos para as medidas de interesse como o suporte, a confiança e o lift (muitas ferramentas utilizam ainda outras medidas de interesse para avaliar as regras de associação). Em seguida, a ferramenta executa um algoritmo que analisa a base de dados e gera como saída um conjunto de regras de associação com valores de suporte e confiança superiores aos valores mínimos especificados pelo usuário. Note que este processo é diferente do utilizado pelas aplicações OLAP e pelo métodos estatísticos tradicionais, onde o especialista testa a sua hipótese contra a base de dados. No caso da mineração de dados, as hipóteses e os padrões são automaticamente extraídos da base de dados pelas ferramentas.

Regras de Associação Transacionais

As regras de associação mineradas a partir de bases de dados de transações (como a ilustrada na Figura 1) foram apresentadas no artigo anterior. Elas são conhecidas na literatura como regras de associação transacionais ou regras de associação convencionais.

A partir da base de dados acima, tem-se que a seguinte regra transacional poderia ser minerada: {couve}Þ {brócolis}. Esta regra é interessante porque possui suporte de 50% (metade dos consumidores comprou os dois produtos em conjunto) e confiança de 60% (o que indica que 60% dos consumidores que compraram couve também compraram brócolis).

A grande maioria das ferramentas de mineração de dados oferece a capacidade de minerar regras de associação a partir de bases de dados que contêm atributos numéricos e categóricos, como data warehouses e bancos de dados relacionais. Neste caso, as regras de associação extraídas envolvem múltiplos atributos (ou dimensões - terminologia empregada na área de data warehouses). Este tipo de regra é denominado regra de associação multidimensional.

Considere uma base de dados de um supermercado que possui, além dos produtos comprados por seus clientes, outros atributos que informam os dados pessoais destes. Um exemplo de regra multidimensional que poderia ser minerada a partir desta base é dado por:

(Sexo = “F”) Ù (30 £ Idade £ 35) Þ (Forma de Pagamento = “cartão de crédito”)

Esta regra hipotética indica que clientes do sexo feminino, com idade entre 30 e 35 anos, costumam pagar por suas compras utilizando cartão de crédito. Note que esta regra envolve três atributos (dimensões), sendo um deles numérico (Idade) e dois deles categóricos (Sexo e Forma de Pagamento).

Regras de Associação Híbridas

Uma regra de associação híbrida é um tipo especial de regra multidimensional onde uma das dimensões pode aparecer repetidas vezes no corpo da regra. Um exemplo deste tipo de regra é dado por:

(Sexo = “M”) Ù (Casado = “N”) Ù (Produto = “cerveja”) Þ (Produto = “salaminho”)

Esta regra hipotética indica que clientes solteiros, do sexo masculino, que compram cerveja têm maior chance de também comprar salaminho. Este exemplo envolve três dimensões, sendo que uma delas ocorre mais de uma vez (Produto). Observe que este tipo de regra é extremamente útil, pois envolve tanto os dados pessoais dos clientes, quanto os produtos adquiridos pelos mesmos.

Regras de Associação Multinível

Em alguns casos, os itens em uma base de dados podem estar organizados em diferentes níveis, que os classificam hierarquicamente (Figura 2).

Algumas ferramentas de mineração de dados oferecem a capacidade de minerar regras de associação definidas não somente a partir de itens básicos, mas também a partir de itens que representam classificações (ou generalizações) destes itens básicos. Este tipo de regra é denominado regra de associação multinível. Desta maneira, seria possível minerar a regra genérica {arroz} Þ {feijão} na base de dados, sem a necessidade da mineração de regras mais específicas como {arroz integral} Þ {feijão preto} e {arroz parboilizado} Þ {feijão fradinho}.

Regras de Associação Negativas

Usuários também podem estar interessados em minerar regras de associação negativas (também chamadas de exceções) em bases de dados. Esta abordagem é direcionada para a descoberta de regras inesperadas ou com suporte e confiança com valores baixos. Para ilustrar esta idéia, considere, por exemplo, a regra {couve} Þ {brócolis}, minerada a partir da base de dados hipotética apresentada na Figura 1. Esta regra é forte na base de dados em questão, uma vez que possui confiança de 60%. Note que dentre os cinco clientes que compraram {couve}, três também compraram {brócolis}.

Na prática, pode ser interessante descobrir se esta regra continua forte quando avaliada contra outros produtos da base de dados. Desta forma, uma ferramenta para a mineração de regras negativas poderia descobrir o seguinte padrão apresentado na Figura 3.

O significado intuitivo desta notação é o de indicar que o valor da confiança (ou do suporte) da regra de associação {couve} Þ {brócolis} é significativamente inferior ao esperado entre os consumidores que compram {lingüiça}. A regra negativa foi inferida a partir de uma avaliação da regra de associação {couve} Þ {brócolis} contra o item {lingüiça}, pelo fato da confiança da regra {couve} Ù {lingüiça} Þ {brócolis} ser inferior a uma determinada expectativa. Observando a base de dados da Figura 1, é possível identificar que nenhum dos consumidores que comprou {couve} e {lingüiça} comprou {brócolis} (ou seja a confiança e o suporte de {couve} Ù {lingüiça} Þ {brócolis} possuem valor igual a 0%).

Uma regra negativa pode ser útil para identificar clientes com diferentes perfis de compra. Um especialista pode concluir, por exemplo, que a regra de associação {couve} Þ {brócolis} é válida entre os clientes adeptos de refeições que priorizam o consumo de verduras e legumes, mas que a mesma torna-se inválida entre os clientes que consomem carne de boi ou de porco.

Mineração de Uso da Web

Para demonstrar que a técnica para a mineração de regras de associação possui grande utilidade prática, será apresentado um exemplo de aplicação na mineração de uso da Web (MUW). A abordagem utilizada constitui-se na avaliação dos resultados obtidos através da utilização de uma ferramenta de mineração de dados sobre bases de dados reais.

A MUW possui o objetivo de investigar a seqüência de visitas a páginas feitas por usuários de um determinado site ou portal da Internet. Desta forma, torna-se possível reconstituir os passos seguidos pelos usuários e também descobrir quais padrões de correlação entre as diferentes páginas.

A base de dados escolhida para o teste foi a base de acessos ao site da Microsoft. Trata-se de uma base transacional que está disponibilizada no repositório da Universidade da Califórnia. Nesta base, cada transação contém a lista de páginas visitadas por um determinado usuário durante o tempo (sessão) em que ele manteve acesso ao portal da Microsoft. A base é composta por cerca de 33.000 transações, referentes ao ano de 1998.

Para esta avaliação, utilizou-se o programa minerador de regras de associação transacionais denominado RATRANS, que foi desenvolvido em C++ . O software para mineração de regras de associação foi configurado com os seguintes parâmetros: suporte mínimo de 0,1%, confiança mínima de 30% e interesse mínimo de 1,30. A tabela 2 apresenta algumas das regras obtidas neste experimento, ordenadas de maneira decrescente de acordo com o valor da medida do lift.

Observe, por exemplo, a regra {International IE content} Þ {Free Downloads}. O valor da medida de suporte indica que 1,29% das pessoas que visitaram o portal da Microsoft consultaram ambas as páginas durante o tempo de permanência da visita: {International IE content} e {Free Downloads}.

O valor da medida de confiança indica que a probabilidade de um usuário ter visitados a página {Free Downloads}, dado que ela também visitou {International IE content} é de 46,59%. E, por fim, o valor da medida de interesse da regra indica que a visita à página {Free Downloads} é nada menos do que 72,70 vezes maior entre os usuários que visitam {International IE content}.

Resultados como este demonstram que as regras de associação podem servir como ferramenta de apoio ao processo de tomada de decisões gerenciais. No exemplo em questão, observe que é possível tirar proveito das informações descobertas para identificar os diferentes perfis de usuários que acessam o portal da Microsoft.

Conclusões

Neste trabalho foram apresentados e discutidos os diferentes tipos de regras de associação que podem ser minerados a partir de bases de dados. Inicialmente foram descritas as regras de associação transacionais. A seguir discorreu-se sobre as regras multidimensionais, híbridas, multinível e negativas. Além de definições teóricas, foram utilizados exemplos ilustrativos para melhor caracterizar cada uma das diferentes formas que estas regras podem assumir.

O trabalho demonstrou a aplicabilidade da técnica para mineração de regras de associação, através da análise dos resultados obtidos através da mineração de uma base de dados real. A partir da análise dos resultados, foi possível demonstrar que as informações contidas nas regras de associação são capazes de auxiliar na identificação do perfil dos usuários de um portal Internet.