Mineração de Dados: Descoberta de regras de associação

A descoberta de regras de associação, proposta por Rakesh Agrawal (AGRAWAL et. al., 1993), a partir da observações dos itens presentes em uma compra de supermercado, com o objetivo de descobrir relações do tipo: “Um cliente que compra o item A frequentemente compra também o item B”. Esta tarefa busca caracterizar o quanto a presença de um conjunto de itens nos registros de uma base de dados implica na presença de algum outro conjunto distinto de itens no mesmo registro.

Deste então, a mineração de regras de associação tem atraído grande interesse de pesquisadores de diversas áreas como no comércio eletrônico, navegação WEB, na medicina, em serviços bancários, detecção de fraudes em cartões de crédito, gerenciamento de projetos, entre outras (PAIDI, 2012).

A terminologia básica utilizada na análise de associações é dada como: Seja I = {i1,i2,i3,…im} um conjunto de atributos e seja D uma base de dados composta por um conjunto de transações T = {t1,…,tm}, na qual cada transação ti ∈ T é composta por um conjunto de itens A tal que A ⊆ I. Um conjunto de itens A é denominado itemset e um itemset com k itens é denominado um k-item set. O conjunto X = a; b; c é um 3-itemset. A frequência de ocorrência de um conjunto de itens é o número de transações que o contêm (AGRAWAL e SRIKANT, 1994).

Uma regra de associação é uma representação da forma A ⇒ B, em que A e B são respectivamente o antecedente e o consequente da regra. Tais conjuntos devem atender as seguintes propriedades A ⊆ I, B ⊆ I e A ∩ B =Ø. Uma regra de associação A ⇒ B não implica que há uma relação de causa-efeito entre os conjuntos A e B mas que os mesmos co-ocorrem numa mesma transação (SCHONHORST, 2010).

Podemos definir que uma regra é dita forte se atende a um suporte e confiança mínimo. E uma regra é frequente se atende a um suporte mínimo (SCHONHORST, 2010).

O suporte s de uma regra de associação A ⇒ B sobre um conjunto de transações D é a porcentagem de transações em D que contém A ∪ B, ou seja, P(A ∪ B). A confiança c da mesma regra é dada pelo conjunto de transações em D contendo A que também contém B, ou seja, é a probabilidade condicional P(B|A) (HAN et.al., 2012). Em resumo, o suporte pode ser definido como (SCHONHORST, 2010):

Função de Suporte em Descoberta de Associações

onde, P(A ⇒ B): é o número de transações em que A e B ocorrem juntos; e N é o número total de transações.

A confiança pode ser definido como:

Função de confiança na descoberta de associações

onde, σ(A) é o número de transações em que A ocorre.

Problemas e Desafios da Aplicação de Regras de Associação

O problema de mineração de regras de associação pode ser descomposto em dois passo (TAN et.al., 2009):

  1. Encontrar todos os conjuntos de itens frequentes, ou seja, encontrar todos os conjuntos de itens que satisfação o limite mínimo do suporte.
  2. Gerar fortes regras de associação a partir dos conjuntos de itens frequentes, ou seja, extrair todas as regras que satisfaça o suporte mínimo e a confiança mínima.

O maior desafio nas regras de associação é determinar o conjuntos de itens frequentes de um grande conjunto de dados é o processo de geração de conjuntos de itens frequentes pela quantidade ser muito grande especialmente se o suporte mínimo for muito pequeno.Deste modo, a performance de um algoritmo de mineração é dados pelo passo 1 . O tempo de processamento com certeza é um desafio presente na aplicação de regras de associação, mas pode-se dizer que este desafio se caracteriza mais como uma limitação presente em qualquer processo de mineração de dados (SCHONHORST, 2010).

Um outro problema está no fato de o modelo suporte-confiança não ser capaz de mensurar a dependência entre dois itemsets. Por exemplo, este modelo não é capaz de identificar implicações negativas do tipo: “Um cliente que compra o item A geralmente não compra o item B” (SCHONHORST, 2010).

Desde a introdução de regras de associação, muitos esforços têm sido concentrados no desenvolvimento de algoritmos eficientes para a geração de regras. E o algoritmo mais utilizado para geração dos itemset é o algoritmo Apriori, que satisfaz o suporte mínimo definido pelo usuário (SCHONHORST, 2010).

Há vários algoritmos que extraem regras de associação que surgiram a partir das ideias apresentadas no algoritmo Apriori tais como: PARTITION, FP-Growth, ECLAT e entre outros (AGRAWAL e SRIKANT, 1994).

Conclusão

A descoberta de regras de associação pode ser dita como uma das melhoras forma de encontrar relações simples e em alguns casos complexos. A aplicação de regras de associação é variada e comumente descobre regras que não são vistas facilmente por experientes analistas de dados.

Espero ter contribuído para a melhoria do seu conhecimento. Até o próximo artigo.

Prof. Norton Guimarães
@nortoncg

Referências

AGRAWAL, R.; IMIELIN´ SKI, T.; SWAMI, A. Mining association rules between sets of items in large databases. SIGMOD Rec., 22(2):207–216, June 1993.

AGRAWAL, R.; SRIKANT, R. Fast algorithms for mining association rules. In: Proc. of 20th Intl. Conf. on VLDB, p. 487–499, 1994.

HAN, J.; .; KAMBER, M.; PEI, J. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 3th edition, 2012.

PAIDI, A. N. Data mining: Future trends and applications. IJMER, 2(6):4657–4663, 2012.

SCHONHORST, G. B. Mineração de regras de associação aplicada à modelagem dos dados transacionais de um supermercado, 2010. Dissertação (Mestrado em Engenharia da Produção), Universidade Federal de Itajubá, Itajubá, Minas Gerais, Brasil. Disponível em: <http://saturno.unifei.edu.br/bim/0036319.pdf>. Acesso em: 07 jun. 2016.

TAN, P.-N.; STEINBACH, M.; KUMAR, V. Introdução à Mineração de Dados. Editora Ciência Moderna, Rio de Janeiro, 2009.

Facebooktwittergoogle_plusredditpinterestlinkedinmail

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *