Artigo da SQL Magazine 26 - Data mining e a descoberta de associações em dados

Data mining e a descoberta de associações em dados

Andrei Alencastro, Gustavo Semaan e Carlos Rodrigo Dias

Data mining, ou mineração de dados, corresponde à extração automática ou semi-automática de padrões ou modelos a partir dos dados armazenados em uma base de dados. Nesse contexto, um padrão é um evento, ou conjunto de eventos, que ocorre com uma certa freqüência na base de dados e um modelo corresponde à estrutura que descreve, de forma resumida, estes dados. Para que a mineração de dados obtenha sucesso, os padrões e modelos obtidos, além de serem úteis, devem trazer alguma novidade, ou seja, devem ser interessantes para o usuário. E na prática, como a mineração de dados pode ser útil?

Para responder a esta pergunta, deve-se considerar que a realidade atual das empresas está inserida no contexto da globalização. Assim, é importante que cada empresa busque, a cada instante, estratégias para conseguir alcançar vantagem competitiva em relação às demais. Vantagem competitiva deve ser entendida como qualquer diferencial que uma empresa possa ter em relação às outras. Entretanto, nem toda vantagem competitiva é sustentável, pois, em alguns casos, é possível que ela seja copiada por outras empresas. Portanto, uma vantagem competitiva é considerada sustentável se ela for valiosa, rara, difícil de imitar ou insubstituível.

Para incrementar a vantagem competitiva de uma empresa em um ambiente de constantes mudanças, os seus gestores devem tomar as decisões corretas nos momentos certos, utilizando as informações disponíveis. Desta forma, o sucesso poderá ser alcançado a partir das decisões tomadas desde que seja realizada uma exploração eficaz do relacionamento existente entre os diferentes elementos que compõem a realidade de atuação da empresa.

Com o avanço das tecnologias de informação e o aumento da capacidade de armazenamento e de processamento dos sistemas computacionais, cada vez mais as empresas armazenam em suas bases de dados informações referentes às várias formas de interação com seus clientes e fornecedores. Como exemplo pode-se citar as transações de compras em uma empresa de varejo, em que cada compra de cada cliente envolve um ou mais produtos. A partir do banco de dados criado e alimentado durante um período de tempo, imagina-se que estes dados possam conter informações valiosas. Algumas destas informações podem ser obtidas através da execução de consultas SQL, em que o desenvolvedor cria suas próprias hipóteses, ou de seus usuários, gerando, em seguida, uma série de relatórios gerenciais. Um relatório deste tipo informaria, por exemplo, os produtos mais vendidos durante o período de um mês.

Entretanto, nestes dados armazenados sobre as transações existe muito mais informações do que se percebe em um primeiro momento. Estas informações normalmente ficam ocultas devido ao volume de dados disponível. Na busca destas informações ocultas pode-se querer, por exemplo, identificar os produtos que são comprados juntos em um certo número de compras, o que corresponde ao problema conhecido como “análise da cesta de compras”. Outro exemplo é a busca pela identificação dos perfis de clientes a partir dos produtos adquiridos por eles. Observa-se facilmente que estes tipos de demandas não podem ser atendidos com simples consultas SQL. Assim, é necessário recorrer a outras ferramentas de análise.

A cada dia novos investimentos estão sendo realizados em pesquisa para o desenvolvimento de técnicas computacionais e algoritmos para explorar as bases de dados disponíveis. Isto permite um suporte cada vez maior aos tomadores de decisões das empresas. Um grupo de técnicas desenvolvidas para este fim recebe a denominação de mineração de dados (data mining), que corresponde a uma analogia ao processo tradicional de mineração, em que ocorre a extração de minérios valiosos da Terra. No caso da mineração de dados, os “minérios valiosos” são os padrões escondidos nos dados que, de alguma forma, podem ser extraídos.

É importante mencionar que, neste artigo, estamos tratando da aplicação da mineração de dados em bases de dados comerciais. Entretanto, a mineração de dados vem sendo utilizada nas mais diversas áreas, como bioinformática, medicina, astronomia, análise de logs da web, pesquisa operacional, dentre outras.

Estima-se que o volume de dados armazenados em bancos de dados espalhados pelo mundo dobre a cada 20 meses. Assim, a dificuldade em encontrar padrões e modelos nestes dados é cada vez maior, tornando-se ainda mais complexa pelo fato destes dados estarem normalmente espalhados em diferentes sistemas em diversos setores de uma empresa. A integração destes dados espalhados pode ser necessária se, no processo de tomada de decisão, for necessária uma visão mais ampla da empresa. Esta integração pode ocorrer, por exemplo, com a implantação de um ERP ou um data warehouse. Em alguns casos esta integração pode não ser necessária, como no caso do escopo ser apenas vendas, o que exigirá apenas os dados referentes às transações de vendas.

Independente do escopo para a geração dos padrões desejados, para realizar a mineração de dados são necessárias ferramentas automatizadas ou semi-automatizadas. Atualmente existem diversas ferramentas de análise disponíveis que não contemplam as técnicas de mineração de dados. Estas ferramentas normalmente utilizam métodos baseados na verificação, isto é, o usuário (analista de negócio) constrói hipóteses sobre relações entre os dados para extrair algum tipo de padrão implícito a partir do banco de dados. Um exemplo de hipótese que pode ser tratada por este tipo de ferramenta é saber se os clientes com determinada faixa de renda familiar são mais propensos a solicitar financiamento em suas compras do que os demais clientes. Neste contexto de ferramentas estão os geradores de relatórios e as ferramentas de análise OLAP (On-Line Analytical Processing). Estes métodos de verificação dependem da intuição, visão e experiência do analista de negócio em propor hipóteses interessantes para extrair informações do banco de dados, de tal forma que possam ser aplicadas estrategicamente na empresa. Diferentemente, na mineração de dados o objetivo é encontrar relações entre os dados que ainda não sejam conhecidas. É importante mencionar que a mineração de dados não precisa ser aplicada apenas a grandes bases de dados, sendo também possível obter conhecimento valioso a partir de bases de dados modestas.

Para muitos autores, a mineração de dados é considerada uma etapa de um processo maior, denominado KDD (Knowledge Discovery in Databases, traduzido como descoberta de conhecimento em bases de dados). O termo KDD foi utilizado pela primeira vez em 1989 e, desde então, o interesse neste assunto aumenta a cada dia. O processo de KDD e a mineração de dados utilizam técnicas herdadas de áreas como aprendizado de máquina, estatística, reconhecimento de padrões, inteligência artificial, banco de dados e visualização de dados.

O KDD prevê várias etapas como a seleção, pré-processamento, transformação e mineração dos dados, bem como a interpretação dos resultados obtidos. Estas etapas foram apresentadas e explicadas na edição 10 da SQL Magazine. Outros autores apresentam variações destas etapas, que podem ser agrupadas em pré-processamento, mineração e pós-processamento dos dados.

Pré-processamento dos dados

Nessa etapa devem ser definidos os objetivos da análise. A definição dos objetivos necessita de um conhecimento prévio das possibilidades que a mineração de dados oferece, além de um profundo conhecimento das necessidades do negócio da empresa.

Em seguida deve-se buscar conhecimento sobre as fontes dos dados, conhecendo sua estrutura e verificando como estes dados podem ser utilizados na mineração. É então realizada a seleção dos dados conforme os objetivos definidos, ou seja, caso o objetivo seja identificar o comportamento de compras dos clientes em um período de um ano, por exemplo, os dados referentes ao ano desejado devem ser selecionados. A partir da seleção dos dados, estes deverão ser organizados e armazenados em uma nova base de dados para análise, que pode ser mantida por um SGBD ou ser apenas um único arquivo texto. Durante a carga dos dados na nova base de dados, estes podem sofrer algum tratamento prévio para evitar resultados inesperados na mineração de dados. É necessário tratar os dados quando existem distorções, como valores discrepantes gerados devido a erro na entrada dos dados, ou falta de valores para alguns campos importantes para a mineração e que não eram tão importantes na entrada de dados, como o CEP, por exemplo. Existem formas de amenizar os efeitos de problemas como falta de valores ou dados inconsistentes, o que não faz parte do escopo deste artigo e por isto não será discutido aqui.

Ainda faz parte do pré-processamento a realização de uma análise prévia dos dados, através de alguns métodos estatísticos, para tentar identificar atributos mais relevantes ou dependências que possam facilitar ou dificultar a etapa de mineração de dados. Após a análise, pode ser necessário realizar a transformação dos valores de alguns atributos para melhorar os resultados obtidos com a mineração de dados. Um exemplo deste caso seria realizar a transformação dos valores do campo de data de nascimento dos clientes, substituindo-o pela idade correspondente. Outro seria substituir valores contínuos por rótulos de faixas de valores. Após a transformação dos dados a base já está pronta para ser minerada.

Durante a etapa de pré-processamento também deverá ser definida a tarefa de mineração de dados a ser utilizada.

Mineração de dados

Existem diferentes tarefas de mineração que podem ser executadas sobre uma base de dados. As tarefas correspondem aos problemas que podem ser tratados pela mineração de dados de uma forma mais ampla. As tarefas mais comuns são:

·         Classificação: corresponde à descoberta de um conjunto de regras de decisão que permitem classificar novas instâncias a partir de modelos obtidos dos dados já existentes. Para a classificação é necessário um prévio conhecimento das classes das instâncias disponíveis para que possa ser obtido um modelo que seja capaz de classificar novas instâncias.

·         Agregação: também conhecida como “clusterização”, refere-se ao procedimento de agrupar as instâncias de acordo com suas características, ou atributos. Assim, deseja-se que instâncias com valores similares para os atributos fiquem em um mesmo grupo e instâncias com atributos muito diferentes sejam colocadas em grupos diferentes.

·         Associação: procura-se, com esta tarefa, identificar associações entre valores de atributos de instâncias na base de dados. A aplicação mais conhecida para a tarefa de associação é a obtenção de regras de associação a partir de uma base de dados de vendas para tratar o problema da “análise da cesta de compras”. As regras de associação obtidas identificam os produtos que são comprados juntos com uma certa freqüência. Devido a seu grande apelo prático, esta tarefa foi escolhida como tema principal deste artigo.

Depois de escolher a tarefa a ser utilizada, deve-se também escolher o algoritmo que será utilizado na mineração de dados. Para cada tarefa existem diferentes algoritmos que trabalham com diferentes tipos de dados e que fornecem resultados diferentes. Alguns algoritmos são mais simples e outros mais sofisticados, como os algoritmos que utilizam lógica difusa e redes neurais. Assim, é necessário um conhecimento do resultado que cada algoritmo pode fornecer, e como funciona internamente, para que a escolha possa ser acertada.

Dependendo do algoritmo escolhido, pode ser necessário também fornecer alguns parâmetros para a sua execução. Estes parâmetros normalmente dependem do conhecimento do usuário em relação ao negócio que está sendo considerado.

Finalmente, esta etapa é concluída com a execução do algoritmo de mineração de dados sobre a base de dados pré-processada, utilizando os parâmetros definidos. O resultado será um conjunto de padrões, ou modelo, que descreve os dados, devendo ser analisado na etapa de pós-processamento.

Pós-processamento

Normalmente, o modelo obtido na etapa anterior, além de descrever os dados minerados, poderá tornar possível a realização de previsões sobre fatos futuros. Para isto é necessário que alguém com conhecimento do negócio possa realizar a sua interpretação. Após a interpretação, o próximo passo é o seu uso nos processos decisórios da empresa. A principal meta dessa etapa é melhorar a compreensão do conhecimento obtido, em forma de relatórios demonstrativos, com a documentação e explicação das informações relevantes descobertas.

No pós-processamento pode-se também chegar à conclusão de que o modelo obtido não atende às expectativas, ou seja, ao objetivo definido inicialmente. Neste caso, é necessário analisar todo o processo de KDD e identificar qual passo deve ser revisto e refeito. Dessa forma, os passos subseqüentes ao passo refeito também devem ser refeitos para que um novo modelo seja obtido e também avaliado. Existe ainda a possibilidade do usuário intervir em qualquer momento do processo e retornar a um passo anterior quando for detectado algum problema durante o seu desenvolvimento.

Como pode ser observado, o processo de KDD é iterativo, uma vez que pode ser executado várias vezes até a obtenção do resultado desejado, e interativo, por permitir a interferência do usuário a qualquer momento e o retorno a passos anteriores.

Extração de regras de associação

O grande problema da descoberta de associações é que elas podem ter ocorrido ao acaso. Como exemplo, considere a hipótese de que mais cegonhas determinam um maior número de nascimento de crianças. Isto pode ser confirmado ao serem analisadas correlações nos dados sobre ninhos de cegonhas e taxa de natalidade de algumas regiões da Suécia (através de métodos estatísticos). Temos então a confirmação da hipótese. Porém, existe uma terceira variável que foi desconsiderada na análise: a quantidade de chaminés. As áreas urbanas da Suécia têm taxa de nascimento mais altas e também mais chaminés, onde as cegonhas fazem seus ninhos, daí, o grande número de cegonhas. Logo, é necessário estudar corretamente a teoria da associação antes de tentar medir, ou provar alguma coisa.

Na estatística trabalha-se dessa forma, ou seja, a partir de uma hipótese busca-se verificar se ela é válida ou não. Na mineração de dados, apesar de ser necessária a definição da tarefa a ser realizada e dos dados a serem analisados, normalmente não existe uma hipótese prévia a ser verificada.

A partir dos conceitos apresentados, neste artigo será tratada apenas a extração de regras de associação, que corresponde à obtenção de regras do tipo “se X ocorre então Y ocorre”, ou seja, X Þ Y, onde X e Y correspondem a conjuntos de eventos que ocorrem com uma certa freqüência na base de dados. O algoritmo mais conhecido utilizado para este fim é o algoritmo chamado APRIORI, que foi desenvolvido com o objetivo de tratar o problema de encontrar padrões referentes a produtos que são comprados juntos com uma certa freqüência (a análise da cesta de compras). A resolução deste problema pode ser aplicada a qualquer base de dados de transações de vendas de uma empresa. Um exemplo clássico, e sempre lembrado quando se fala em mineração de dados, é o de uma grande empresa varejista que, a partir da utilização de um algoritmo de extração de regras de associação, obteve a regra “às sextas-feiras no horário noturno, jovens do sexo masculino que compram fraldas também compram cerveja”. A partir da regra obtida, a empresa pode tomar decisões estratégicas, como ajustar mostruários, modificar prateleiras ou propagandas, e introduzir atividades promocionais específicas, na tentativa de melhorar o foco do negócio. Dessa forma, o algoritmo APRIORI identifica dependências na ocorrência de itens de um subconjunto de dados, que é expressa na forma das regras de associação. O algoritmo APRIORI será explicado a seguir através de um exemplo.

Considere uma base de dados de um supermercado com apenas dez transações, como apresentada na Tabela 1. Os itens comprados nas transações correspondem aos produtos arroz (A), detergente (D), lasanha congelada (L), macarrão (M) e pasta de dente (P). Para cada transação são indicados os itens comprados naquela transação. Como exemplo, na transação 1 foram comprados os itens arroz, lasanha congelada e macarrão, o que é representado pelo conjunto {A, L, M}.