Unioeste - Universidade Estadual do Oeste do ParanáCENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICASColegiado de InformáticaCurso de Bacharelado em Informática

DATA MINING

Fabiany LamboiaLuciano Machado Pereira

CASCAVEL2005

Fabiany LamboiaLuciano Machado Pereira

DATA MINING

Trabalho apresentado como nota parcial da disci-plina de Banco de Dados II do Curso de Bacha-rel em Informática, do Centro de Ciências Exatase Tecnológicas da Universidade Estadual do Oestedo Paraná - Campus de Cascavel

Professor: Carlos José Maria Olguín

CASCAVEL2005

Lista de Figuras

2.1 Estratégias e Algoritmos utilizados . . . . . . . . . . . . . . . . . . . . . . . . 8

3.1 Exemplo de um conjunto de dados . . . . . . . . . . . . . . . . . . . . . . . . 14

iii

Lista de Abreviaturas e Siglas

DM Data MiningIBM International Business MachinesKDD Knowledge Discovery in DatabasesOLAP Online Analytical ProcessingCAD Computer Aided DesignCAM Computer Aided Manufacturing

iv

Sumário

Lista de Figuras iii

Lista de Abreviaturas e Siglas iv

Sumário v

1 Introdução 1

2 Data Mining 3

2.1 Principais Tarefas de Data Mining . . . . . . . . . . . . . . . . . . . . . . . . 4

2.1.1 Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.2 Estimativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.3 Segmentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.4 Regressão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1.5 Agregação (clustering) . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1.6 Sumarização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1.7 Modelo de Dependência . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.8 Associação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.9 Análise de Sequência . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.10 Predição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Técnicas de Data Mining 9

3.1 Estatística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2 Métodos Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.3 Indução de Regras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.3.1 Regras de Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.3.2 Regras de Associação . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3.3 Apriori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

v

3.3.4 Regras de Caracterização . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3.5 Regras de Discriminação . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.4 Alguns Algoritmos utilizados em Data Mining . . . . . . . . . . . . . . . . . . 13

3.4.1 Árvores de decisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.4.2 Cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.4.3 Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.4.4 Adaptive Bayes Network . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.5 Aplicações para Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.5.1 Marketing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.5.2 Vendas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.5.3 Finanças . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.5.4 Manufatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.5.5 Saúde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.5.6 Energia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.6 Tecnologias que Implementam Data Mining . . . . . . . . . . . . . . . . . . . 20

3.7 Exemplos de Empresas que utilizam Data Mining . . . . . . . . . . . . . . . . 20

4 Conclusão 22

5 Bibliografia 23

vi

Capítulo 1

Introdução

O grande volume de dados disponíveis cresce a cada dia e desafia a capacidade de arma-

zenamento, seleção e uso dos mesmos. Assim surge a necessidade de uso de tecnologias que

permitem a obtenção (mineração) de dados afim de gerar informações e conhecimento a partir

dos dados.

A tecnologia de Data Mining com suas ferramentas permite a "mineração"destes dados. Esta

tecnologia é formada por um conjunto de ferramentas que são capazes de explorar um grande

conjunto de dados, extraindo destes conhecimentos na forma de hipóteses e de regras.

Diariamente as empresas acumulam diversos dados em seus bancos de dados, tornando-os

em informação sobre os vários processos e procedimentos das funções da empresa, inclusive

com dados e hábitos de seus clientes, suas histórias de sucesso e fracassos. Todos estes dados

podem contribuir com a empresa, sugerindo tendências e particularidades pertinentes a ela e seu

meio ambiente interno e externo, visando uma rápida ação de seus gestores.

Com a geração de informações e conhecimentos úteis para as empresas, os seus negócios

podem se tornar mais lucrativos. Os recursos da Tecnologia da Informação, mais precisamente

a capacidade do hardware e software disponíveis podem efetuar atividades em horas o que

tradicionalmente as pessoas levariam meses.

Os sistemas tradicionais são ferramentas capazes de manipular dados de forma rápida, se-

gura e efetiva em bancos de dados, mas apresentam restrições para gerar informações com

análises significativas. Estas restrições são melhores trabalhadas quando as empresas utilizam-

se da tecnologia de Data Mining aliada a outras tecnologias, tais como, Knowledge Discovery

in Databases (KDD).

No ambiente comercial atual, data mining está começando a ganhar mais atenção. Como

esse recurso trata de exploração e análise, de forma automática ou semi-automática, quantida-

des de dados podem ajudar a descobrir padrões e regras significativas. Esses padrões e regras

ajudam as empresas a aprimorar áreas de marketing, vendas e de operações de suporte ao cliente

para entendê-los melhor.

2

Capítulo 2

Data Mining

Data mining (DM), é o processo de seleção, exploração de dados e criação de modelos que

utiliza um grande volume de armazenamento de dados para identificar padrões previamente des-

conhecidos. Consiste na construção de modelos computacionais para a descoberta automática

de novos fatos e relacionamentos entre dados, produzindo novos conhecimentos.

Tais conhecimentos são utilizados para informar melhor os tomadores de decisão antes de

eles agirem. O DM Pode criar um modelo do mundo real com base nos dados coletados de

várias fontes, incluindo transações corporativas, dados históricos e demográficos de clientes,

e mesmo de fontes externas, como empresas de análise de crédito. Depois, pode utilizar esse

modelo para produzir padrões a partir de informações, os quais podem dar suporte às tomadas

de decisão e prever novas oportunidades de negócios. O data mining está presente em vários

setores e atividades de negócio, como por exemplo:

• Empresas de telecomunicações, seguros, cartões de crédito e do mercado de ações utili-

zam o data mining para detectar fraudes, otimizar campanhas de marketing e identificar

as estratégias mais lucrativas.

• A área médica utiliza o data mining para prever a eficácia de procedimentos cirúrgicos,

exames médicos e medicações.

• O setor de varejo utiliza o data mining para avaliar a eficácia de promoções e eventos

especiais, e prever que ofertas são mais apropriadas para os diferentes consumidores.

É importante não confundir data mining com complexas estruturas de consulta a bases de

dados, onde o usuário já possua alguma hipótese e deseja apenas extrair material para manu-

almente verificar e confirmar a validade de sua hipótese. A idéia central em data mining é a

de que seus algoritmos atuem como extratores de dados e sejam capazes de automaticamente

identificar a existência de padrões e relacionamentos desconhecidos, que ao serem analisados

posteriormente, possam mostrar e induzir a geração de hipóteses úteis e relevantes para o usuá-

rio.

O Data Mining representa uma forma de capitalizar o investimento necessário para o arma-

zenamento de grandes volumes de dados, tentando, por exemplo, descobrir padrões de compor-

tamento de clientes para fins de concessão de crédito, ou identificando estilos de ações fraudu-

lentas em administradoras de cartão de créditos.

Um problema nesta abordagem é que além da possibilidade de criar relacionamentos inúteis,

o número de correlações possíveis de serem obtidas tende a ser muito grande, o que impede a

análise exaustiva de cada uma. A solução é usar algoritmos e técnicas inteligentes que possam

identificar e selecionar automaticamente os casos mais relevantes para cada aplicação.

O processo de data mining difere das técnicas de OLAP já bastante difundidas na literatura,

enquanto estas oferecem meios para consolidar os dados em vários níveis, trabalhando-os em

múltiplas dimensões, a técnica de data mining busca mais do que a interpretação dos dados exis-

tentes, visa fundamentalmente inferir e generalizar possíveis fatos e correlações não percebidas

nem facilmente deduzidas.

2.1 Principais Tarefas de Data Mining

O termo ”minerar” pressupõe o garimpo por alguma preciosidade, ”minerar dados” pres-

supõe o ”garimpo” entre bases de dados por algo que possa trazer algum valor ou vantagem

competitiva para a empresa. Em geral este ”garimpo” tem como objetivo descrever ou prever o

comportamento futuro de algum fenômeno. Descrever tem como foco encontrar algo que faça

sentido e que consiga explicar os resultados ou valores obtidos em determinados dados ou ne-

gócios. Prever, por outro lado, tem como foco antecipar o comportamento ou o valor futuro de

algum fenômeno ou variável de interesse, com base no conhecimento de valores do passado.

Na busca de tais objetivos diferentes estratégias podem ser utilizadas para ”garimpar” as

bases de dados disponíveis na busca por indícios que possam relacionar dados ou fatos. As

principais estratégias empregadas nesta tarefa incluem a classificação, a agregação, a associa-

4

ção, a regressão e a predição. Em todas estratégias, o objetivo maior é o de poder generalizar o

conhecimento adquirido para novas ocorrências do fenômeno ou para outros contextos ou situ-

ações parecidas com a utilizada na construção do modelo computacional. Em cada uma destas

estratégias diferentes técnicas e algoritmos podem ser aplicados.

2.1.1 Classificação

É a estratégia que consiste na busca por uma função que consiga mapear (classificar) uma

determinada ocorrência em uma dentre um conjunto finito e pré-definido de classes. A constru-

ção do modelo segundo esta estratégia pressupõe o conhecimento prévio das possíveis classes e

a correta classificação dos exemplos usados na modelagem. Várias são as aplicações para este

tipo de abordagem, em análise de risco, por exemplo, o objetivo pode ser o de classificar um

potencial cliente entre as classes de excelente, bom ou mau pagador.

2.1.2 Estimativa

Os algoritmos de estimativa são uma variação do problema de classificação, que determina

um valor mais provável para um índice diante dos dados do passado ou de dados de outros

índices semelhantes sobre os quais tem-se conhecimento.

A classificação lida com valores discretos, já a estimativa trabalha com valores númericos

contínuos. Dadas informações de entrada, busca-se estimar um valor númerico para uma variá-

vel contínua, ou seja, preencher um valor perdido em um campo em particular de um registro

como uma função de outros campos no registro. Redes Neurais, algoritmos genéticos e as

técnicas usuais de regressão estatística são algumas ferramentas muito utilizadas para estimar

grandezas.

Exemplos de tarefas de estimativa incluem estimar a renda total de uma família e estimar o

valor de um empréstimo que pode ser concedido a uma empresa.

2.1.3 Segmentação

Busca realizar a separação, em uma grande população, de sub-populações com comporta-

mentos semelhantes. Dentro dessas sub-populações, vários tipos de previsões são possíveis.

5

Várias técnicas de detecção de clusters, agrupamento por afinidades e análises de ligações

podem ser aplicadas à tarefas de segmentação.

Um exemplo de aplicação pode ser a segmentação de clientes através da descoberta de gru-

pos de clientes com características de comportamento semelhantes.

2.1.4 Regressão

Consiste na busca por uma função que represente, de forma aproximada, o comportamento

apresentado pelo fenômeno em estudo. A forma mais conhecida de regressão é a linear, por

exemplo, uma reta que minimiza o erro médio entre todos os valores considerados, mas também

pode ser não linear.

2.1.5 Agregação (clustering)

Consiste na busca de similaridades entre os dados tal que permita definir um conjunto finito

de classes ou categorias que os contenha e os descreva. A principal diferença entre esta abor-

dagem e classificação é que em agregação não se tem conhecimento prévio sobre o número de

classes possíveis nem a possível pertinência dos exemplos usados na modelagem.

Esta tarefa agrupa informações homegêneas de grupos heterogêneos entre os demais e

aponta o item que melhor representa cada grupo, também conhecido como clusters. Os grupos

identificados podem ser mutuamente exclusivos ou exaustivos ou consistir de uma representa-

ção mais rica tais como categorias hierárquicas ou sobrepostas. Assim, todos os elementos de

um mesmo grupo são similares segunda uma medida. Os elementos descobertos são as classes

ou as hipóteses.

Exemplos de tarefas de clusterização incluem agrupar clientes em conjuntos homogêneos de

acordo com seus hábitos de consumo e colocar em um mesmo conjunto de bactérias semelhan-

tes. Outro exemplo é o segmentação demográfica que serve de início para uma determinação

das características de um grupo social, visando desde hábitos de compras até utilização de meios

de transporte.

2.1.6 Sumarização

Envolve métodos que encontram uma descrição compacta para um subconjunto de dados.

6

Aplicações podem ser de tabular o resultado e o desvio padrão para todos os atributos de

conjunto de dados, descobrir dependência funcional entre as variáveis, realizar a derivação de

um sumário de regras, etc.

As técnicas de sumarização são frequentemente aplicadas à análise exploratória interativa

de dados e geração automatizada de relatórios.

2.1.7 Modelo de Dependência

Encontra um modelo que descreve as dependências significativas entre as variáveis. Os mo-

delos de dependência existem em dois níveis: estruturais, cujas variáveis são localmente depen-

dentes entre si; quantitativos os quais especificam a solidez da dependência usando uma escala

númerica. Geralmente um modelo utiliza os dois tipos de dependências, um para encontrar a

relação e outra para quantificá-la.

Estes modelos são utilizados em áreas como desenvolvimento de probabilidades em siste-

mas especialistas da área médica, recuperaçaõ de informação e modelagem de genes humanos.

2.1.8 Associação

Consiste em identificar fatos que possam ser direta ou indiretamente associados. Esta es-

tratégia é geralmente usada em aplicações onde se busca identificar itens que possam ser colo-

cados juntos em um mesmo pacote de negociação. Por exemplo, a constatação de que vendas

de cerveja e de fraldas descartáveis aumentam às sextas-feiras pode levar à construção de uma

hipótese que associe ambos os itens a um tipo especial de cliente. Associação também pode ser

usada para avaliar a existência de algum tipo de relação temporal entre os itens constantes de

uma base de dados.

2.1.9 Análise de Sequência

Uma variante de problema de regras de associação é a Análise de Sequências, onde as regras

encontradas entre as relações podem ser usadas para identificar sequências interessantes, que

serão utilizadas para predizer acontecimentos subsequentes. Nesse caso, não apenas a coexis-

tência de itens dentro da cada transação é importante, mas também a ordem em que aparecem e

o intervalo entre elas. Sequências podem ser úteis para identificar padrões temporais, utilização

7

de cartões de crédito ou ainda tratamentos médicos.

2.1.10 Predição

Envolve uma componente temporal, isto é, representa aquela classe de problemas nos quais

estamos interessados em prever o comportamento ou valor futuro de uma determinada variável

com base em valores anteriores desta mesma variável (mono-variável) ou em valores anteriores

da variável de interesse e de outras variáveis (multi-variável).

Existem várias técnicas que podem ser utilizadas na implementação destas estratégias, onde

as principais podemos ver na figura 2.1.

Figura 2.1: Estratégias e Algoritmos utilizados

8

Capítulo 3

Técnicas de Data Mining

As técnicas de DM fornecem a estrutura necessária para que se possam acessar os dados e

extrair conhecimento a partir dos mesmos. A escolha da técnica mais adequada depende do tipo

de aplicação, do tipo dos dados armazenados e da tarefa ou função escolhida.

3.1 Estatística

É utilizada em problemas em que o interessa está centrado em uma simples variável de saída

y e uma coleção pré-editada. Todos os modelos assumem a viabilidade dos dados treinados e

tem como objetivo encontrar um modelo para prever o valor y a partir de x, que seja executado

e produza bons resultados a partir de novos dados.

Estatísticas envolvem computação matemática e, portanto, requerem uso de dados quantita-

tivos. Testes estatítiscos podem ser usados para comparar valores entres vários grupos amostra-

dos num conjunto de dados.

3.2 Métodos Lineares

Métodos Lineares englobam modelos clássicos de elaboração e classificação, sendo estes

respectivamente regressões lineares e análise linear de discriminante. O termo linear, nesses

modelos, é derivado do fato da superfície de regressão ou classificação ser um plano.

A flexibilidade e a computação direta envolvidas na regressão linear são feitas sem o uso

de outras técnicas associadas. Exemplificando, as funções radiais básicas de redes neurais são

meras regressões lineares de um conjunto de características do núcleo.

3.3 Indução de Regras

Os sistemas baseados em regras buscam extrair conhecimento por meio de regras do tipo:

Se premissa então conclusão.

Uma regra indutiva é um processo de percorrer uma série de dados e, a partir destes, gerar

padrões. Pelo fato de explorar automaticamente uma série de dados, o sistema indutivo cria

hipóteses que conduzem padrões.

O processo é em sua essência semelhante aquilo que um especialista humano parece fazer

quando em análise exploratória. Por exemplo, dado um banco de dado de informação demográ-

fica, o sistema de indução pode primeiramente examinar como as idades são distribuídas e pode

perceber uma interessante variação áquelas pessoas cujas profissões são listadas como atletas

profissionais.

Os sistemas baseados em regras dividem-se em regras de de classificação, regras de associ-

ação, regras de caracterização e regras de discriminação.

3.3.1 Regras de Classificação

São obtidas pelo processo de classificação que consiste em analisar uma base de exemplos

e de construir um modelo para cada classe a partir das características dos atributos. Geralmente

a descrição dos atributos está em uma base de dados, na forma de registros. Uma regra de

classificação tem a seguinte forma:

Valor -> Classe

onde os valores dos atributos são as premissas e a classe a conclusão. Essas regras podem

ser utilizadas para categorizar outros elementos de dados com o objetivo de melhorar a compre-

ensão do conteúdo da base.

Alguns exemplos de utilização de regras de classificação:

• Classificar um lote de pedras preciosas;

• Classificar solicitações de cartões de crédito como sendo baixo, médio ou alto risco;

• Discriminar solicitações de cobertura de seguros fraudulentas das não fraudulentas.

Em todos esses exemplos existe um número limitado de classes e a cada um dos registros

do banco de dados uma determinada classe deve ser atribuída.

10

3.3.2 Regras de Associação

A tarefa de associação, que envolve a descoberta de regras de associação, é uma das tecno-

logias predominantes em mineração de dados. O banco de dados é tratado como uma coleção

de transações, sendo que cada uma envolve um conjunto de itens.

Uma regra de associação é uma expressão da forma X− > Y , onde X e Y são conjuntos

de itens. O significado de tal regra é que transações da base de dados que contém X tendem

a conter Y também. O conjunto de itens que aparece à esquerda da seta (representado por

X) é chamado de antecedente da regra. Já o conjunto de itens que aparece à direita da seta

(representado por Y ) é o conseqüente da regra. Assim, uma regra de associação tem o seguinte

formato:

Antecedente − > Conseqüente

A cada regra são associados dois fatores: suporte e confiança. Para uma regra de associação

X− > Y , o suporte indica a porcentagem de registros em que aparecem X e Y simultanea-

mente, sobre o total de registros. Já a confiança indica a porcentagem de registros que contém

X e Y , sobre o total de registros que possuem X. Um conjunto de itens é chamado de itemset e

seu suporte é a porcentagem das transações que contêm todos os itens do itemset. Um itemset

é dito freqüente quando o seu suporte é maior ou igual a um valor de suporte mínimo definido

pelo usuário.

A tarefa de mineração de regras de associação consiste em duas etapas:

1. Encontrar todos os itemsets freqüentes.

2. Gerar regras de associação a partir dos itemsets freqüentes.

Se na base de dados de transações existir m itens diferentes, o número de possíveis itemsets

distintos é 2m. Desta maneira, a maior dificuldade na mineração de regras de associação está

em determinar todos os itemsets freqüentes.

Seja, por exemplo, I = {1, 2, 3, 4} o conjunto de todos os possíveis itens em uma base de

dados. Dessa maneira tem-se 24 = 16 possíveis itemsets.

Um dos algoritmos mais utilizados para a extração de regras de associção é o Apriori.

11

3.3.3 Apriori

Entre os diversos algoritmos para realizar a mineração de dados buscando regras de associ-

ação, um dos mais famosos e utilizados é o Apriori.

Ele foi proposto pela equipe de pesquisa QUEST da IBM que deu origem ao Software Intel-

ligent Miner. Esse algoritmo faz recursivas buscas no Banco de Dados à procura dos conjuntos

frequentes (conjuntos que satisfazem um suporte mínimo estabelecido).

Sua criação representou um grande diferencial em relação aos algoritmos anteriores a ele,

principalmente no que se refere ao desempenho e à estratégia de solução do problema de mine-

ração de regras de associação. Por esse motivo, o algoritmo Apriori é considerado um algoritmo

clássico, e a partir dele muitos algoritmos foram posteriormente criados, formando o que muitos

chamam de ”família Apriori”.

O objetivo do algoritmo pode ser descrito dessa forma:

• um conjunto de transações D, D = {T |Tumconjuntodeitens};

• um suporte mínimo minsup;

• uma confiança mínima minconf.

obter todas as regras de associação que possuam

• confiança ≥ minconf;

• suporte ≥ minsup.

Assim, a estratégia do Apriori é identificar os conjuntos de itemsets freqüentes (cujo suporte

seja maior ou igual a minsup) e construir regras a partir desses conjuntos, que possuam confiança

maior ou igual a minconf. A idéia inovadora desse algoritmo é a de que se um conjunto está

abaixo do suporte mínimo, pode-se ignorar todos os seus superconjuntos.

Com isso, o algoritmo ganha em desempenho, já que não perde tempo analisando esses

superconjuntos que não são freqüentes. Essa otimização é possível porque a busca em largura

garante que os valores dos suportes de todos os subconjuntos de um candidato são conhecidos

antecipadamente. Em uma varredura da base de dados, o Apriori realiza simultaneamente a

contagem de todos os candidatos de tamanho k.

12

A parte crítica do algoritmo é procurar pelos candidatos em cada transação. Para esse pro-

pósito, foi introduzida uma estrutura de dados chamada hash-tree. Os itens em cada transação

são utilizados para percorrer a hash-tree. Quando é alcançada uma de suas folhas, é encontrado

um conjunto de candidatos que possui um prefixo comum. Esses candidatos são procurados na

transação e, se encontrados, o contador deles na hash-tree é incrementado.

3.3.4 Regras de Caracterização

Regras de Caracterização possibilitam generalizar e comparar as características dos dados.

Sua forma geral é a seguinte:

[Valor] + Classe -> Valor

onde [Valor] é opcional. A caracterização de uma cidade, é um exemplo dessa regra:

Se nome = Paris e tamanho = grande e população = grande então prédios = antigos No exem-

plo, a classe é o nome da cidade os valores das premissas são os atributos tamanho e população

e o atributo prédio é a conclusão.

3.3.5 Regras de Discriminação

Assemelham-se às regras de caracterização, exceto pelo fato de que a extração pode ser feita

a partir da conclusão. Comparam dois conjuntos de objetos e sua forma é:

Valor1 = Valor2 -> Classe1 = Classe2

3.4 Alguns Algoritmos utilizados em Data Mining

Em data mining existem vários algoritmos que podem ser utilizados para a obtenção de

informaçãoes ou criação de hipóteses, tais como, Árvore de decisão, redes neurais, indução de

regras, vizinho mais próximo, algoritmos genéticos. Nas seções seguintes é descrito uma breve

explanação de alguns desses algoritmos.

3.4.1 Árvores de decisão

O algoritmo de árvores de decisão foi desenvolvido por estatísticos para automatizar a deter-

minação de quais campos eram importantes e se relacionavam com o problema. Este algoritmo

13

encontra relacionamentos entre os atributos da previsão, através da classificação. É um dos

melhores algoritmos de mineração de dados.

• Árvore de decisão é um modelo de previsão onde cada ramo da árvore representa um

questionamento da classificação e as folhas representam os valores dos atributos alvo da

previsão. Se um atributo está relacionado com alguma folha da árvore, então este atributo

tem influência na previsão.

• A seleção dos atributos que compõe a árvore é realizada através de um processo de clas-

sificação, neste caso somente os atributos mais importantes são adicionados à árvore.

A árvore de decisão é provavelmente a técnica mais popular para a modelagem de prognós-

tico. Um exemplo explica alguns conceitos básicos do algoritmo de árvore de decisão. A figura

3.1 mostra um conjunto de dados de treinamento que podem ser usados para prever o risco do

crédito. Neste exemplo, informações fictícias sobre clientes foram geradas, incluindo o nível de

débito, o nível de receita, o tipo de emprego e se há risco de crédito bom ou ruim.

Figura 3.1: Exemplo de um conjunto de dados

Neste exemplo, o algoritmo de árvore de decisão pode determinar que o atributo mais sig-

nificante para prever o risco de crédito é o nível de débito. Dessa forma, a primeira divisão na

árvore de decisão é feita no nível de débito. Um dos dois novos nós (Débito = Alto) é um nó

14

folha, que contém três casos com créditos ruins e nenhum caso com crédito bom. Neste exem-

plo, um nível de débito alto é um prognóstico perfeito para um risco de crédito ruim. O outro

nó (Débito = Baixo) ainda é misturado, tendo três créditos bons e um ruim.

O algoritmo de árvore de decisão escolhe o tipo de emprego como o prognóstico mais sig-

nificante de risco de crédito. A divisão no tipo de emprego tem dois nós de folha que indicam

que os autônomos têm uma probabilidade de crédito ruim maior. Isso é, claramente, um pe-

queno exemplo baseado em dados sintéticos, mas ilustra como a árvore de decisão pode usar

atributos conhecidos de pessoas que desejam obter crédito para prever o risco. Na realidade, há

normalmente mais atributos para cada candidato ao crédito, e os números de candidatos podem

ser muito grande. Quando a escala do problema aumenta, é difícil para uma pessoa extrair ma-

nualmente as regras para identificar riscos de crédito bons e ruins. O algoritmo de classificação

pode considerar vários atributos e milhões de registros para chegar a uma árvore de decisão que

descreva as regras para a previsão do risco de crédito.

Há muitas variações de algoritmos que constroem árvores de decisão e que usam diferentes

métodos de divisão: formas de árvore, técnicas de remoção e assim por diante.

3.4.2 Cluster

O algoritmo de cluster aqui abordado é baseado no algoritmo de expectativa e maximização

(EM). Esse algoritmo se itera entre duas etapas. Na primeira etapa, chamada E ou ”expecta-

tiva”, a participação no cluster de cada caso é calculada. Na segunda etapa, chamada M ou

”maximização”, os parâmetros dos modelos são reestimados usando as participações no cluster.

EM é semelhante tem as seguintes etapas principais:

1. Atribuir médias iniciais.

2. Atribuir casos para cada média usando alguma medida de distância.

3. Calcular novas médias com base nos participantes de cada cluster.

4. Atribuir novos limites com base nas novas médias.

5. Circular até obter a convergência.

15

EM não tem limite restrito entre os clusters. Um caso é atribuído a cada cluster com uma

determinada probabilidade. Os dados em cada cluster têm uma distribuição gaussiana. A média

de cada cluster é alternada, depois de cada iteração.

A maioria dos algoritmos de cluster deve carregar todos os pontos de dados na memória, o

que pode acarretar sérios problemas de escalonabilidade quando você estiver processando um

conjunto de dados maior. O algoritmo de cluster pode utilizar uma estrutura escalonável, que

armazena seletivamente importantes partes do banco de dados e resume outras partes. A idéia

básica é carregar os dados nos buffers de memória em blocos, e com base no modelo de data

mining atualizado, resumir os casos próximos à distribuição gaussiana, compactando-os.

3.4.3 Naive Bayes

Este algorítmo constroi modelos para predizer a probabilidade de resultados específicos,

utilizando dados históricos para encontrar padrões e relacionamentos e então fazer predições.

Utiliza o teorema de Bayes que define a fórmula:

P (h|D) =P (D|h)P (h)

P (D)

Sendo:

P (h|D) a probabilidade a posteriori da hipótese h, dado que o conjunto D acon-

tece;

P (D|h) a probabilidade de observar o conjunto de dados D, dada a hipótese h;

P (h) a probabilidade a priori da hipótese h;

P (D) a probabilidade a priori sobre conjunto de dados D.

Calcula explicitamente probabilidades para cada hipótese. É útil para obter uma boa estima-

tiva de qualquer modelo preditivo. Possui uma validação cruzada que permite ao analista testar

a acurácia do modelo no mesmo conjunto de dados utilizado para construir o modelo.

Pode prever resultados binários ou multi classes. Exemplos:

Modelo Binário:

-Pergunta: O cliente pode se tornar um investiodor em ações ?

-Resposta: Sim, com 65% de probabilidade.

Modelo de multi classes:

16

-Pergunta: Em qual dos cinco grupos: crescimento, estável, rejeição, defeito ou

insignificante, o cliente se enquadra ?

-Resposta: Estável, com 55% de probabilidade.

3.4.4 Adaptive Bayes Network

É um algorítmo proprietário da Oracle para dar suporte a árvores de decisão. O resultado é

fornecido na forma de regras de fácil compreensão, como por exemplo: ”Se salário é 5000-7000

R$ e número de dependentes é 3-4, então a possibilidade de comprar o último modelo de Van é

SIM”.

Possui boa performance e escalabilidade, devido a possibilidade do analista informar pa-

râmetros que definem o nível de precisão e o tempo de construção. É utilizado quando existe

um volume grande de atributos, o analista precisa de regras que explicam o modelo e definir

parâmetros para controlar o tempo de construção do modelo. Considera custos no caso de uma

previsão incorreta, baseada em uma matriz de custos informada para modificar o modelo de

previsão.

3.5 Aplicações para Data Mining

Não há na prática limite ou área específica para aplicação dos conceitos até aqui apresenta-

dos, tudo depende da capacidade de modelar o problema para a aplicação de uma das estratégias

listadas e da criatividade em analisar e utilizar os resultados alcançados. Dentre as que mais têm

explorado o uso de data mining encontramos as áreas de marketing, vendas, finanças, manufa-

tura, saúde e energia.

3.5.1 Marketing

Database marketing é um segmento emergente que vem revolucionando a forma de encarar

e fazer a divulgação dos produtos de uma empresa. Quando aliado às técnicas de data mining

amplia suas potencialidades abrindo novas e diferentes formas de avaliar e alavancar a relação

entre o cliente e o faturamento da empresa.

O esforço de marketing geralmente é elevado, nem sempre é efetivo, mas fatalmente influi

no preço final de venda. Qualquer tecnologia que seja capaz de tornar mais efetivo o resultado

17

da propaganda ou de reduzir seus custos, tem impacto direto no faturamento e no sucesso do

empreendimento.

A manutenção de grandes bancos de dados onde são armazenadas as transações de vendas,

operações de crédito ao cliente, de compra a prazo e de pagamento, tem feito do database

marketing uma das áreas mais ricas e promissoras para aplicação dos conceitos de data mining .

As principais aplicações estão na seleção de candidatos para propaganda seletiva ou na seleção

de produtos a serem oferecidos num mesmo pacote.

Numa campanha de marketing a possibilidade de identificar antecipadamente aqueles clien-

tes que apresentam maiores chances de responder positivamente a abordagem reduz os custos

da propaganda, o mesmo ocorre quando a cesta de produtos a ser oferecida é otimizada para

cada cliente em potencial.

3.5.2 Vendas

No setor de vendas a aplicação provavelmente de maior interesse seja a de identificar produ-

tos que possam ser colocados em uma mesma cesta ou pacote. Isto envolve a ”garimpagem” por

associação entre produtos, que pode revelar afinidades ou aversões nunca imaginadas e como

conseqüência, sugerir estratégias para maximizar o lucro.

A descoberta de que dois ou mais produtos têm suas vendas fortemente associadas pode, por

exemplo, ser usada no sentido de não colocá-los em promoção ao mesmo tempo, de organizá-

los de uma forma que facilite o cliente a encontrá-los ou de organizá-los de maneira que no

caminho entre eles o cliente seja exposto a outros produtos para que a venda desses outros seja

estimulada.

Outra aplicação é a busca por associações que envolvam uma componente temporal, isto é,

aquela que revela, por exemplo, que a compra de um produto hoje induz, com alta probabilidade,

a compra de outro algum tempo depois. Tal descoberta pode sugerir uma estratégia de venda

que busque efetivar a venda de ambos logo na primeira oportunidade.

3.5.3 Finanças

Em finanças as aplicações têm sido várias envolvendo associação, classificação, agregação

e também predição. Análise de crédito, potencial transações fraudulentas em cartões de crédito,

18

avaliação de risco, constituição de bolsa de ações, previsão de transferência de numerário entre

agencias bancárias, previsão de flutuações nos mercados de ações e de commodities e previsão

de falências, são algumas das aplicações mais comumente encontradas.

Nesta área as transações podem envolver volumes financeiros efetivamente elevados, os

riscos e a concorrência também são altos e neste cenário, qualquer oportunidade de ganho é

considerada e pode representar um diferencial, por menor que seja a margem de ganho.

3.5.4 Manufatura

A complexidade dos modernos parques de produção e a pressão pela eficiência e pela qua-

lidade tem possibilitado o uso de data mining e de automação em diversas áreas. CAD/CAM

(Computer Aided Design/Computer Aided Manufacturing) e robôs são algumas das aplicações

de maior demanda na área.

3.5.5 Saúde

São basicamente duas frentes distintas de trabalho nesta área: administração e diagnóstico.

Na administração os sistemas lidam com os serviços oferecidos aos pacientes, com os seguros,

com as ações potencialmente fraudulentas, etc.

Em termos de diagnóstico o emprego de data mining visa o desenvolvimento de sistemas

capazes de realizar diagnósticos (classificações) automaticamente, com base em dados obtidos

de exames laboratoriais. Sistemas de diagnóstico apresentam a vantagem de atender rapida-

mente grandes volumes de pacientes, o que facilita a ação pública em epidemias ou campanhas

sanitárias.

3.5.6 Energia

Previsão de consumo e previsão de falhas em sistemas de transmissão ou de distribuição são

as duas aplicações mais comuns, embora muitas outras tenham sido pesquisadas e difundidas

na literatura.

Conforme visto na figura 3.1, a tecnologia de maior emprego atualmente em data mining é a

de redes neurais, assunto ao qual dedicamos o próximo capítulo. Nele tentaremos proporcionar

ao leitor uma visão geral sobre o paradigma das redes neurais e capacitá-lo a utilizá-las na

19

resolução de alguns problemas reais.

3.6 Tecnologias que Implementam Data Mining

• IBM DB2 Enterprise Edition 8.2: suporta técnicas de árvore de decisão, regressão, asso-

ciação e técnicas de agrupamento;

• Oracle Database 10g: Naive Bayes, redes Adaptive Bayes e Support Vector Machines

(SVM);

• Microsoft SQL Server 2000 Analisys Services: suporta árvores de decisão.

3.7 Exemplos de Empresas que utilizam Data Mining

• A rede americana Wall-Mart, pioneira no uso de Data Mining, descobriu ao explorar seus

números que 60% das mães que compram boneca Barbie, levam também uma barra de

chocolate.

• O banco Itaú conseguiu aumentar sua taxa de retorno nas malas diretas para 30%. Re-

duzindo a conta do correio a um quinto. Armazenando e analisando a movimentação

financeira de seus 3 milhões de correntistas nos últimos 18 meses.

• A Sprint, um dos líderes no mercado de americano de telefone de longa distância, de-

senvolveu, com a análise de Data Mining em seu Data Warehouse, um método capaz de

prever com 61% de segurança se um consumidor trocaria de companhia telefônica dentro

de um período de dois meses. Com um marketing agressivo, conseguiu evitar a deserção

de 120.000 clientes e uma perda de 35 milhões de dólares em faturamento.

• O governo de Massachusetts, no Estados Unidos, compilava informações financeiras im-

primindo telas e mais telas nos terminais de grande porte. Só com papel foram economi-

zados U$ 250.000,00 por ano. Além de permitir que o orçamento anual fosse assinado e

analisado, antes do início do ano fiscal.

• O SERPRO no Brasil, implantando o seu Data Warehouse e Data Mining, já consegue

hoje cruzar e analisar informações em cinco minutos, o que antes demandavam quinze

20

dias de trabalho.

• E o clássico exemplo da grande rede varejista americana (Wal-Mart) que descobriu, atra-

vés de seu Data Mining , que as vendas de fraldas estavam intimamente ligadas às vendas

de cerveja. Explicação, os pais que saiam à noite para comprar fraldas, compravam cer-

veja também.

21

Capítulo 4

Conclusão

O data mining está se tornando rapidamente uma técnica analítica amplamente utilizada,

pois possibilita a obtenção de conhecimento e relações que podem passar despercebidas. Tais

conhecimentos são extraídos de uma base de dados e posteriormente poderão ser utilizados para

informar melhor os gerentes e executivos (tomadores de decisão).

Para a extração das informações o data mining utiliza-se de algoritmos ”mineradores”, que

criam relações e extraem informações dos dados. A tendência é que todo desenvolvedor de

banco de dados deverá ser capaz de criar e treinar os modelos de data mining para incorporar

esses recursos avançados nos aplicativos do consumidor, ou seja, os bancos de dados deverão

oferecer o recurso de data mining, pois tal recurso está se tornando extremamente necessário

para o crescimento e estabilidade de empresas.

Capítulo 5

Bibliografia

AGRAWAL, R. e SRIKANT, R. Fast Algorithms for Mining Association Rules. In: 20th

Conference on Very Large Data Bases (VLDB’94), 1994, Santiago, Chile. Anais. Santiago,

Chile, 1994. p. 487-499.

AMARAL, F. C. N. do. Data Mining: técnicas e aplicações para o marketing. São

Paulo: Berkeley Brasil.2001.

CONTI, A. L. Estado de Arte - Data Mining. Trabalho de Conclusão de Curso. Universi-

dade Estadual do Oeste do Paraná, 2000.

ELMASRI, R. e NAVATHE, S. B. Data Mining Concepts. In: Fundamentals of Database

Systems. Addison-Wesley, 2004, p. 867-897.

LOSS, L e RABELO, R. J. Sistemas de Data Mining. Relatório Técnico GSIGMA

001/2004. Universidade Federal de Santa Catarina - UFSC.2004.

NAVEGA, S. Princípios Essenciais do Data Mining. Infoimagem 2002.

ORLANDO, S., PALMERINI, P. e PEREGO, R. Enhancing the Apriori Algorithm for

Frequent Set Counting. Lecture Notes in Computer Science - Springer-Verlag, v. 2114, p.

71+, 2001.

REATEGUI, E. Data Mining e Personalização Dinâmica. X Escola de Informática da

SBC - Sul, 2002.

THOMÉ, A. C. G. Redes Neurais : uma ferramento para KDD e Data Mining. Dispo-

nível em: http://equipe.nce.ufrj.br/thome/grad/nn/mat_didatico. Acessado em 15/08/2005.

WOJCIECHOWSKI, M. e ZAKRZEWICZ, M. On Efficiency of Dataset Filtering

Implementations in Constraint-Based Discovery of Frequent Itemsets. In: 2002 JCKBSE

Conference, 2002, Maribor, Slovenia. Anais. Maribor, Slovenia, 2002.

24