100
  FUNDAÇÃO EDUCACIONAL DE FERNANDÓPOLIS FACULDADES INTEGRADAS DE FERNANDÓPOLIS LUCAS ADÃO ZANARDI ESTUDO E APLICAÇÃO DE ALGORITMO DE DATA MINING

Data Mining

Embed Size (px)

Citation preview

Page 1: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 1/100

 

FUNDAÇÃO EDUCACIONAL DE FERNANDÓPOLISFACULDADES INTEGRADAS DE FERNANDÓPOLIS

LUCAS ADÃO ZANARDI

ESTUDO E APLICAÇÃO DE ALGORITMO DE DATA MINING

Page 2: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 2/100

 

FERNANDÓPOLIS 2007

FUNDAÇÃO EDUCACIONAL DE FERNANDÓPOLISFACULDADES INTEGRADAS DE FERNANDÓPOLIS

LUCAS ADÃO ZANARDI

ESTUDO E APLICAÇÃO DE ALGORITMO DE DATA MINING

Page 3: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 3/100

 

FERNANDÓPOLIS 2007

LUCAS ADÃO ZANARDI

ESTUDO E APLICAÇÃO DE ALGORITMO DE DATA MINING

Monografia apresentada às Faculdades Integradas deFernandópolis, Fundação Educacional de Fernandópolis,como requisito para a obtenção do título de Bacharel emSistemas de Informação.

Orientador: Prof. Dr. Evandro Araújo Jardini

FERNANDÓPOLIS

2007

Page 4: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 4/100

 

Autorizo a reprodução e divulgação total ou parcial deste trabalho, por qualquer meioconvencional ou eletrônico, para fins de estudo e pesquisa, desde que citada a fonte.

Catalogação na publicaçãoServiço de Documentação Universitária

Fundação Educacional de Fernandópolis

Zanardi, Lucas Adão.

Data mining : estudo e aplicação de algoritmos de data mining ;orientador: Prof. Dr. Evandro de Araújo Jardini. Fernandópolis, 2007. 100f.

Monografia (Graduação em Sistemas de Informação) -Faculdades Integradas de Fernandópolis, Fundação Educacional deFernandópolis.

1. Dados. 2. Preparação, mineração. 3. Estudo de caso. I. Título.

Page 5: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 5/100

 

FOLHA DE APROVAÇÃO 

LUCAS ADÃO ZANARDI

Estudo e aplicação de algoritmos de data mining

Monografia apresentada às Faculdades Integradas deFernandópolis, Fundação Educacional de Fernandópolis,como requisito para a obtenção do título de Bacharel emSistemas de Informação.

Examinadores:

 ___________________________________________ Prof.Instituição: Faculdades Integradas de FernandópolisCurso: Sistemas de Informação

 ___________________________________________ Prof.Instituição: Faculdades Integradas de FernandópolisCurso: Sistemas de Informação

Aprovada em: ___/___/2007

Page 6: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 6/100

 

Dedicatória

A minha família, por tudo quanto me pôde proporcionar,principalmente carinho e afeto, dedicação e desprendimento, proteção e amor.

Page 7: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 7/100

 

Agradecimentos

Primeiramente, agradeço a Deus por estar aqui realizando o sonho da minha vida com saúde e força de vontade.Um agradecimento especial a toda a minha família, em especial aos meus pais, pela forma como me criaram e a educação que me deram, fatores fundamentais que fizeram de mim a pessoa que hoje sou.

 Aos professores do curso de “Sistemas de Informação” que,com seus ensinamentos, forneceram os estímulos e as orientações necessárias para a elaboração deste trabalho.Ao amor da minha vida, Simone, que tive o privilégio de conhecer durante a faculdade e que se tornou papel principal na minha história de vida.

Page 8: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 8/100

 

Epígrafe

A maior parte das dificuldades que nos aparecem não provém das decisões que tomamos, mas das que deixamos de tomar. Quase sempre deixamos em segundo plano muitas decisões que ficaram sem solução porque não nos atrevemos a resolvê-las definitivamente. Desconfiamos de nós mesmos, dos nossos pensamentos e, quase sempre achamos mais conveniência ou comodidade em deixar de fazer transferindo o ato “Para Amanhã”. 

(Chamfort).

Page 9: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 9/100

 

RESUMO

ZANARDI, L. A. Estudo e aplicação de algoritmos de data mining. 2007. 100 f.

Monografia (Graduação em Sistemas de Informação) - Faculdades Integradas deFernandópolis, Fundação Educacional de Fernandópolis, Fernandópolis-SP, 2007.

A informática, apesar dos grandes feitos que já realizou, ainda tem muito a contribuir à

humanidade. Além disso, sua crescente inserção em tarefas comuns do cotidiano leva

o ser humano a uma dependência sem fronteiras, pois, a cada ano, companhias

acumulam mais e mais informações em seus bancos de dados. Como conseqüência,

esses bancos de dados passam a conter verdadeiros tesouros de informação sobre

vários dos procedimentos dessas companhias. Desse modo, toda essa informação

pode ser usada em vários procedimentos, permitindo que a empresa detecte

tendências e características disfarçadas e reaja rapidamente a um evento que ainda

pode estar por vir. No entanto, apesar do enorme valor desses dados, a maioria das

organizações é incapaz de aproveitar totalmente o que está armazenado em seus

arquivos. Essa informação preciosa está na verdade escondida sob uma montanha de

dados e não pode ser descoberta utilizando-se sistemas de gerenciamento de banco de

dados convencionais. Felizmente, recursos e técnicas computacionais foram

desenvolvidos para analisar os dados, ou mesmo ajudar o analista a encontrar ordem

no caos: conhecimento. A utilização desses recursos e técnicas para a exploração em

bases de dados possibilitou o surgimento do que se chama mineração de dados (Data 

Mining ). Portanto, data mining  constitui-se de uma tecnologia capaz de automatizar

processos de busca por informações predictivas que podem estar ocultas dentro de um

amontoado de banco de dados ou relatórios gerenciais. Questões que tradicionalmente

Page 10: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 10/100

 

exigem um extensivo trabalho de análise podem agora ser resolvidas nos dados, direta

e instantaneamente, pois as ferramentas de mineração de dados são implementadas

em sistemas de processamento de alta performance e podem analisar grandes bancosde dados em questões de minutos. Através de um processamento mais rápido, iremos

executar simulações com diferentes modelos, compreendendo dados ainda mais

complexos, obtendo predições mais aperfeiçoadas.

Palavras chave: mineração de dados, algoritmos, tomada de decisão.

Page 11: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 11/100

 

ABSTRACT 

ZANARDI, L. A. STUDY AND APPLICATION OF ALGORITHMS OF DATA MINING2007. 100 f. Monograph (Graduation in Information Systems) - “Fundação Educationalde Fernandópolis (FEF)”, Fernandópolis, SP, 2007.

Although Informatics has already done great deeds in the world, it still has a lot to

contribute to humanity. Moreover, its increasing insertion in common everyday tasks

make the human being dependent on it. This dependence is without limits because each

and every year companies accumulate more and more information in their databases.As a consequence, these databases start to contain veritable treasures of information

on several procedures of those companies. Thus, all information can be used in several

procedures, allowing the company to detect tendencies and disguised characteristics as

well as react quickly to any event to come. However, in spite of the enormous value of

those data, most of the organizations are unable to take full advantage of what is stored

in their files. Such precious information is actually hidden under a mountain of data and

it cannot be discovered using conventional database management systems. Fortunately,

computer techniques and resources were developed to analyze the data or even to help

the analyst to find order in the chaos: knowledge. The use of those resources and

techniques for the exploration in bases of data made possible the appearance of the so-

called mining of data (Data Mining ). Therefore, data mining is a key technology in order

to automate search processes for predictive information which can be occult on medium

or large-scale databases or managerial reports. Issues, which traditionally require

extensive analysis work, can be direct and instantly resolved in the data now since the

data mining tools are implemented in high-performance processing systems and they

Page 12: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 12/100

 

can analyze big databases in a few minutes. Through faster processing, we will execute

simulations using different models, understanding even more complex data and

obtaining more improved predictions.

keywords: Data Mining, algorithms, decision taking.

Page 13: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 13/100

 

LISTA DE ILUSTRAÇÕES 

Figura 1 – Visão geral dos passos que compõem o processo KDD ............... 26

Figura 2 – Detectando outliers com a técnica da análise de agrupamentos... 33

Figura 3 – Conversão de dados nominais para booleanos.............................. 37

Figura 4 – Conversão de dados numéricos para booleanos........................... 37

Figura 5 – Conversão de dados numéricos para booleanos(usando faixas de valores).............................................................. 37

Figura 6 – Conversão de dados ordinais para booleanos(usando faixas de valores)............................................................. 38

Figura 7 – Conversão de dados de ocorrência para booleanos...................... 39

Figura 8 – Classificação como identificação do que é “parecido”no espaço de atributos................................................................... 48

Figura 9 – Algumas formas de calcular distâncias.......................................... 49

Figura 10 – Exemplos de classificação com paralelepípedos......................... 51

Figura 11 – Exemplos de classificação com paralelepípedos(com problemas potenciais de classificação)............................... 54

Figura 12 – Exemplos de classificação com menor distância a protótipo........ 55

Figura 13 – Arquivo ARFF com os resultados da mega senaconfigurado para ser usado em técnicas de associação............. 81

Figura 14 – Regras de associação utilizando o algoritmo APRIORI,

verificando o atributo “NÃO”....................................................... 85

Figura 15 – Regras de associação com valor de mínima métricaalterado para 0.93........................................................................ 86

Figura 16 – Regras de associação com valor de mínima métricaalterado para 0.04........................................................................ 87

Page 14: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 14/100

 

Figura 17 – Arquivo ARFF com os resultados da mega sena configuradopara ser usado em técnicas de clusterização ..............................

89

Figura 18 – Atributos utilizados na técnica de clusterização .......................... 91

Figura 19 – Atributos utilizados na clusterização com a adiçãodo cluster como atributo............................................................... 91

Figura 20 – Dados exibidos de forma gráfica incluindo os clusteresadicionados ................................................................................ 92

Figura 21 – Apresentação do grupos com seus respectivos cálculos............. 94

Figura 22 – Apresentação dos clusters gerados utilizandoo atributo “ganhadores_sena”...................................................... 96

Figura 23 – Apresentação dos clusters gerados utilizando o atributo“dezena 1”.................................................................................... 96

Figura 24 – Apresentação dos clusters gerados utilizandoos atributos “ganhadores_sena” e “mês” com coresrepresentando os clusteres ......................................................... 97

Page 15: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 15/100

 

LISTA DE TABELAS

Tabela 1 – Exemplo da base de dados com as transações de comprasdos clientes e conjunto de itens (produtos).................................... 67

Tabela 2 – Conjunto de itens tamanho1.......................................................... 70

Tabela 3 – Conjuntos candidatos formados a partir dos conjuntos

freqüentes de tamanho 1.............................................................. 71

Tabela 4 – Candidatos de tamanho 3, gerados a partir dos conjuntos

freqüentes de tamanho 2............................................................... 72 

Tabela 5 – Candidatos formados a partir dos conjuntos freqüentesde tamanho 2................................................................................. 73 

Tabela 6 – Regras possíveis para cada um dos conjuntos freqüentes........... 74

Tabela 7 – Exemplo da base de dados com os respectivos concursos

e seu conjunto de itens (dezenas)................................................. 83

Tabela 8 – Regras de associação e seus significados literais......................... 84

Page 16: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 16/100

 

SUMÁRIO 

INTRODUÇÃO..................................................................................................... 18CAPÍTULO I: PREPARAÇÃO DOS DADOS...................................................... 21

1.1 Conceito da mineração de dados................................................................... 211.2 Data warehouse ............................................................................................. 221.3 Processo KDD................................................................................................ 241.3.1 Modelagem da descoberta de conhecimento

de dados...................................................................................................... 251.3.2 As fases e os processos do processo KDD................................................ 251.3.2.1 A Preparação dos dados.......................................................................... 291.3.2.2 Limpeza dos dados (data cleaning )......................................................... 301.4 Integração de dados....................................................................................... 341.4.1 integração de diversas fontes de dados...................................................... 341.5 Transformação dos dados.............................................................................. 361.6 Seleção de dados........................................................................................... 391.6.1 Redução de dados...................................................................................... 41

CAPÍTULO II: MINERAÇÃO DE DADOS............................................................ 43 

2.1 Objetivos primários da mineração de dados.................................................. 452.2 Tarefas primárias da mineração de dados ................................................... 462.2.1 Classificação............................................................................................... 462.2.1.1 Classificação supervisionada................................................................... 472.2.1.2 Medidas de distância................................................................................ 482.2.1.3 Conceitos adicionais................................................................................ 502.2.1.4 Métodos da classificação supervisionada................................................ 502.2.1.4.1 Método do paralelepípedo..................................................................... 502.2.1.4.2 Fase de classificação supervisionada................................................... 512.2.1.4.3 Características...................................................................................... 532.2.1.5 Menor distância a protótipo...................................................................... 542.2.1.5.1 Fase de treinamento............................................................................. 552.2.1.5.2 Fase de classificação............................................................................ 562.2.1.5.3 Características...................................................................................... 572.2.2 Agrupamento (clustering )............................................................................ 582.2.2.1 Medidas de distância................................................................................ 602.2.2.1.1 Métricas................................................................................................. 612.2.2.1.2 Tipos de agrupamentos......................................................................... 612.2.3 Associação.................................................................................................. 622.2.3.1 Exemplo de aplicação de técnicas de associação................................... 642.2.3.2 Regras de associação.............................................................................. 652.2.3.3 Algoritmo.................................................................................................. 69

Page 17: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 17/100

 

2.2.3.3.1 APRIORI – obtenção dos conjuntosFreqüentes........................................................................................... 69

2.2.3.3.2 Geração de regras a partir dos conjuntosde itens freqüentes............................................................................... 73

CAPÍTULO III: ESTUDO DE CASO....................................................................  77

3.1 Técnica de associação................................................................................... 783.1.1 Dados.......................................................................................................... 793.1.2 Metodologia (associação)........................................................................... 813.1.3 Descoberta de regras de associação.......................................................... 843.2 Técnica de clusterização................................................................................ 883.2.1 Dados.......................................................................................................... 883.2.2 Metodologia (clusterização)........................................................................ 89

CONCLUSÃO......................................................................................................  99

REFERÊNCIAS BIBLIOGRÁFICAS....................................................................  100

Page 18: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 18/100

 

INTRODUÇÃO 

A informática, apesar dos grandes feitos de que já é capaz, ainda tem muito a

apresentar e a acrescentar à humanidade. E sua crescente inserção em tarefas comuns

do cotidiano leva o ser humano a uma dependência sem fronteiras, pois, a cada ano,

companhias acumulam mais e mais informações em seus bancos de dados.

A quantidade de informações armazenadas em banco de dados é muito grande

e ultrapassa a habilidade técnica e a capacidade humana na sua interpretação. Bancos

de dados são medidos hoje em gigabytes ou até mesmo em terabytes . A necessidade

de transformarem esses terabytes de dados em informações significativas é óbvia.

Como conseqüência, esses bancos de dados passam a conter verdadeiros

tesouros de informação sobre vários dos procedimentos dessas companhias. Toda

essa informação pode ser usada em vários procedimentos, permitindo que a empresadetecte tendências e características disfarçadas e reaja rapidamente a um evento que

ainda pode estar por vir.

A necessidade de se obter lucro em sua atividade leva o homem a uma busca

incansável de informações que podem ser utilizadas como diferencial, ou até mesmo

representadas como aspectos decisivos na tomada de decisões bem sucedidas e

lucrativas.

O acesso privilegiado a algumas informações pode ser o ponto chave de um

negócio sólido e rentável e, provavelmente, com um índice mínimo de erros que

eventualmente seria um entrave na sua realização. Devido a tais aspectos, é dada uma

ênfase muito significativa à busca e ao manuseio correto da informação.

Page 19: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 19/100

 

No entanto, apesar do enorme valor desses dados, a maioria das organizações

é incapaz de aproveitar totalmente o que está armazenado em seus arquivos. Essa

informação preciosa está na verdade escondida sob uma montanha de dados e nãopode ser descoberta utilizando-se sistemas de gerenciamento de banco de dados

convencionais (AMARAL, 2001).

Felizmente, recursos e técnicas computacionais foram desenvolvidos para

analisar os dados, ou mesmo ajudar o analista a encontrar ordem no caos:

conhecimento.

A utilização desses recursos e técnicas para a exploração em bases de dados

possibilitou o surgimento do que se chama mineração de dados (Data Mining ).

Data Mining pode ser definido como um processo não-trivial de identificar, em

dados, padrões válidos, novos, potencialmente úteis e ultimamente compreensíveis.

Esse processo vale-se de diversos algoritmos (muitos deles desenvolvidos

recentemente) que processam os dados e encontram esses "padrões válidos, novos evaliosos".

Os dados são extraídos dos sistemas operacionais e após limpeza e

transformação, são carregados no Data Warehouse . É importante ressaltar que nunca

se deve alterar no Data Warehouse as informações contidas nos sistemas operacionais

sob o pretexto de que ficarão mais corretas no Data Warehouse . Quaisquer alterações

de erros e processos devem ser feitas nos sistemas operacionais. O Data Warehouse  

tem que refletir o sistema operacional e deve ser único, pois precisa ser a única versão

da verdade e não pode estar em conflito com o sistema operacional. O Data 

Warehouse  deve conter o máximo de detalhes possível e ser desenvolvido em

ferramentas especiais para isso, ou seja, banco de dados relacionais ou

Page 20: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 20/100

 

multidimensionais. Não se confunda transformação com alteração de dados:

transformar significa somente alinhar os dados entre vários sistemas ou mesmo

aprontá-los para que sejam mais bem utilizados no Data Warehouse .Os processos de limpeza, transformação e carga são interativos, pois os dados

são modelados, transformados, limpos e analisados até que possam ser carregados em

definitivo.

Page 21: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 21/100

21

CAPÍTULO I

PREPARAÇÃO DOS DADOS

1.1 Conceito da mineração de dados

A crescente inserção da informática em tarefas comuns do cotidiano leva os

seres humanos a uma dependência sem fronteiras. A utilização de seus recursos para

a exploração em bases de dados possibilitou o surgimento do que se chama mineração

de dados (Data Mining ).

Data Mining constitui-se, segundo Amaral (2001) de uma tecnologia capaz de

automatizar processos de busca por informações predictivas que podem estar ocultas

dentro de um amontoado de banco de dados ou relatórios gerenciais. Questões que

tradicionalmente exigem um extensivo trabalho de análise podem agora ser resolvidas

nos dados, direta e instantaneamente, pois as ferramentas do Data Mining  são

implementadas em sistemas de processamento de alta performance e podem analisarmassivos bancos de dados em questões de minutos. Através de um processamento

mais rápido, os usuários podem executar simulações com diferentes modelos,

compreendendo dados ainda mais complexos, obtendo predições mais aperfeiçoadas. 

Page 22: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 22/100

22

1.2 Data Warehouse

No seu nível mais fundamental, Data Warehouse  é um repositório deinformações para suportar decisões. Ele coleta dados a partir de diversas aplicações de

uma organização, integra os dados em áreas lógicas de assuntos de negócios,

armazena a informação de forma que ela fique acessível e compreensível a pessoas

não técnicas responsáveis pela tomada de decisão através da organização e de várias

ferramentas.

O desenvolvimento do Data Warehouse  segue uma metodologia própria,

distinta da que é normalmente aplicada ao projeto de bancos de dados para fins

transacionais. Seu objetivo é casar as expectativas dos usuários em termos de análise

e tomada de decisão com os dados disponíveis. A modelagem adotada prioriza o

desempenho nas consultas, adotando modelos mais simples, a chamada modelagem

dimensional, ou esquema estrela. Sua construção inclui ainda a limpeza de dados, queleva a um estado mais consistente dos dados utilizados para a tomada de decisão.

Por definição, um projeto de Data Warehouse  tem por objetivo organizar os

dados operacionais de uma empresa em um local onde o ambiente operacional não

seja afetado, da melhor forma possível, para que possam ser aplicadas técnicas de

análise e extração de dados.

Devido à característica de se armazenarem dados operacionais, pode-se dizer

que um Data Warehouse é, na verdade, uma coleção de dados derivados dos dados

operacionais para sistemas de suporte a decisão. Tais dados derivados são, muitas

vezes, referidos como dados “gerenciais”, “informacionais” ou “analíticos”. 

Page 23: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 23/100

23

Um Data Warehouse armazena dados analíticos, destinados ás necessidades

da gerência no processo de tomada de decisões. Isso pode envolver consultas

complexas que necessitam acessar um grande número de registros, por isso éimportante a existência de muitos índices criados para acessar as informações da

maneira mais rápida possível. Um Data Warehouse armazena informações de maneira

histórica de muito anos e por isso deve ter uma grande capacidade de processamento e

armazenamento dos dados que se encontram de duas maneiras, detalhados e

resumidos.

Com base nesses conceitos, o Data Warehouse é um conjunto de técnicas e

bancos de dados integrados, projetados para suportar as funções do sistemas de apoio

a decisão, onde cada unidade de dados está relacionada a um determinado assunto, ou

fato (SANTOS, 2007). Esses bancos são os que darão subsídio de informações aos

gerentes e diretores da empresa, para analisarem tendências históricas dos seus

clientes e, com isso melhorarem os processos que aumentem a satisfação e fidelidadedos mesmos.

Data Warehouses  são construídos para que tais dados possam ser

armazenados e acessados de forma que não sejam limitados por tabelas e linhas

estritamente relacionadas. Os dados de um Data Warehouse podem ser compostos por

um ou mais sistemas distintos e sempre estarão separados de qualquer outro sistema

transacional, ou seja, deve existir um local físico onde os dados desses sistemas serão

armazenados.

Além disso, considera que os analistas precisam de informações para montar

seus planos táticos e estratégicos. Por exemplo, um sistema operacional, para

funcionamento, não precisa da taxa do dólar do ano passado; o analítico, porém, pode

Page 24: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 24/100

24

querer avaliar a evolução do dólar diante do volume de compras de seus produtos e,

portanto, precisará uma informação (taxa do dólar) para a tomada de decisão.

1.3 Processo KDD

A mineração de dados pode ser considerada como uma parte do processo de

descoberta de conhecimento em banco de dados (KDD  – Knowledge Discovery in

Databases). O termo KDD é usado para representar o processo de tornar dados de

baixo nível em conhecimento de alto nível, enquanto mineração de dados pode ser

definida como a extração de padrões ou modelos de dados observados, ou seja,

mineração de dados é a exploração e a análise, por meio automático ou semi-

automático, de grandes quantidades de dados, a fim de descobrir padrões e regras

significativas.

Os principais objetivos da mineração de dados são descobrir relacionamentosentre dados e fornecer subsídios para que possa ser feita uma previsão de tendências

futuras baseadas no passado.

Os resultados obtidos com a mineração dos dados podem ser usados no

gerenciamento da informação, processamento de pedidos de informação, tomada de

decisão, controle de processo e muitas outras aplicações.

A mineração de dados pode ser aplicada de duas formas: como um processo

de verificação e como um processo de descoberta. No processo de verificação, o

usuário sugere uma hipótese acerca da relação entre os dados e tenta prová-la

aplicando técnicas como análise estatística e multidimensional sobre um banco de

Page 25: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 25/100

25

dados contendo informações passadas. No processo de descoberta não é feita

nenhuma suposição antecipada.

1.3.1 Modelagem da descoberta de conhecimento de dados  – KDD

Pode-se dizer que o processo KDD é a descoberta de novos conhecimentos,

sejam padrões, tendências, associações, probabilidades ou fatos, que são óbvios ou de

fácil identificação.

O KDD é o processo de uso dos métodos de mineração de dados para extrair

conhecimento de acordo com a especificação de medidas e limites, aplicados à base de

dados com o pré-processamento exigido.

1.3.2 As fases e os passos do processo KDD

O processo KDD envolve duas grandes fases: preparação de dados e

mineração de dados. Essas fases possuem inúmeros passos, os quais envolvem umnúmero elevado de decisões a serem tomadas pelo usuário, ou seja, é um processo

interativo. É também um processo iterativo, pois, ao longo do processo KDD, um passo

será repetido tantas vezes quantas se fizerem necessárias para que se chegue a um

resultado satisfatório.

O processo KDD é também um processo multi-step (AMARAL, 2001), cujos

passos serão apresentados na figura 1:

Page 26: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 26/100

26

Figura 1 Visão geral dos passos que compõem o processo KDD.Fonte: Amaral, 2001, p. 14.

A fase de preparação de dados envolve os seguintes passos (AMARAL,

2001):

1. O primeiro é a definição do objetivo do problema, que é o conhecimento

desejado pelo usuário final, ou seja, é definido o tipo de conhecimento que se

deseja extrair do banco de dados. Nessa fase, é feito um reconhecimento da

aplicação e a verificação do conhecimento anterior;

2. O segundo passo é a criação de um conjunto de dados-alvo. Nessa fase,

seleciona-se um conjunto de dados ou focaliza-se um subconjunto de atributos

ou de instâncias de dados, em que a descoberta deverá ser efetuada. Muitas

vezes, o sucesso desse processo depende da correta escolha dos dados que

formam o conjunto de dados-alvo. Para isso, são usadas técnicas, linguagens,

ferramentas e comandos convencionais de banco de dados, como o SQL

(Structured Query Language );

3. O terceiro passo é a limpeza e o pré-processamento dos dados. Nesse caso,

deve-se fazer a limpeza dos dados, de maneira que os incorretos ou incompletos

Page 27: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 27/100

27

sejam desprezados. Com isso, é feita uma purificação dos dados usando

operações básicas, como as de eliminação de ruído. Nela são coletadas as

informações necessárias para a modelagem e correção do ruído e paraestratégias de manipulação de campos de dados perdidos, considerando as

seqüências de informações de tempo e as mudanças de conhecimento;

4. O quarto passo é a redução e projeção de dados. Esse processo consiste em

encontrar as características úteis que representam as dependências dos dados

no objetivo do processo. Muitas vezes, pode não ser necessário representar

todas as faixas de valores de um determinado problema. Assim, podem-se

reagrupar esses valores em faixas mais abrangentes, de modo a diminuir o

número de faixas de valores e, conseqüentemente, a complexidade do problema.

Dando continuidade ao processo KDD a fase de mineração de dados envolve

os seguintes passos:

5. O quinto passo é a escolha das tarefas de mineração de dados. Nesse passo,decide-se qual o objetivo do processo de mineração de dados. Os objetivos são

diversificados, tais como: classificação, regressão, clusterização etc.;

6. O sexto passo é a escolha dos algoritmos de mineração de dados. Nele, são

selecionados os métodos para serem usados na busca de padrões dos dados.

Isso inclui decidir que modelos e parâmetros são mais apropriados para a

aquisição do tipo de conhecimento desejado. Por meio da submissão dos dados

aos algoritmos de mineração de dados selecionados, chega-se ao conhecimento.

Esses passos, se usados corretamente, serão de grande ajuda para a etapa

seguinte;

Page 28: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 28/100

28

7. O sétimo passo é a mineração de dados, que é caracterizada pela busca de

padrões de interesse em uma forma particularmente representativa ou em um

conjunto dessas representações. Como exemplos, podem-se citar: regras declassificação, árvores de decisão, regressão, clusterização. Nesse passo, é

realizada a extração de informação dos dados até então processados;

8. O oitavo passo é a interpretação de padrões da exploração. Os dados de saída

definidos no passo anterior são analisados e interpretados pelos especialistas do

domínio. Caso seja necessário, pode-se repetir qualquer um dos sete passos

anteriores para se obter a correta interpretação dos padrões;

9. O nono passo é a consolidação do conhecimento descoberto. Trata-se,

portanto, da incorporação desse conhecimento no desempenho do sistema, na

documentação do conhecimento e no relatório para as partes interessadas.

Nesse passo, fazem-se também a verificação e a resolução de conflitos

potenciais com o prévio conhecimento extraído.O processo KDD pode envolver interações significativas e retornar a qualquer

dos passos, independentemente da fase a que ele pertença. Apesar da seqüência

apresentada na figura 1 ser a mais comum, ela pode ser alterada. O maior trabalho esta

situado entre os processos um e quatro, pois nessas etapas os dados estão sendo

preparados para o processo de exploração, embora as demais sejam também

importantes para o sucesso da aplicação como um todo.

Com relação à eficiência desse processo, ela não deve sem medida em termos

de rapidez do processamento das conclusões. Para um processo KDD ser considerado

eficiente, o valor da informação encontrada deverá exceder o alto custo de sua

implementação e do processamento dos dados. Pode-se dizer que a eficiência do

Page 29: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 29/100

29

processo tem uma relação custo beneficio elevada. Geralmente, os resultados de um

processo KDD têm alto valor estratégico.

1.3.2.1 A preparação dos dados

A fase de preparação dos dados (AMARAL, 2001) capta uma boa parte do

tempo do processo KDD, consumindo aproximadamente 70 por cento desse trabalho,

além de ser de grande importância. Nela são identificados os dados relevantes para a

solução satisfatória do problema. Na verdade, apenas ter os dados não é suficiente,

pois é necessário que eles estejam suficientemente corretos, adequados e tenham sido

corretamente selecionados para que preencham todas as características desejadas.

Mesmo assim, sempre existirá a pergunta: os dados existentes preenchem essas

características?

Outra característica importante é o tipo de armazenamento de dados usado. No

caso de processos informatizados, o armazenamento deve ser feito em arquivos ou

bancos de dados; no caso de processos não informatizados, em fichas ou anotações.

Independentemente do tipo de armazenamento dos dados utilizados, sua importância

continua sendo a mesma. Para que o processo KDD obtenha sucesso, é necessário

que os dados estejam disponíveis para o processamento e em condições de uso.

A quantidade de informações disponíveis deverá, sempre que possível, ser

excedente e não estar em falta, pois uma solução satisfatória exige todas as

informações importantes para a solução de um determinado problema. A falta de

informação pode dificultar e, em alguns casos, até mesmo impedir que se chegue a um

resultado confiável.

Page 30: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 30/100

30

Somente a posse dos dados permite avaliar de forma confiável aqueles que

são realmente relevantes para a solução do problema proposto.

A quantidade de dados será definida de acordo com os métodos utilizadosdurante o processo KDD.

Outro ponto a ser observado está relacionado à quantidade de dados para o

teste. Na totalidade dos dados, deve-se separar um terço para ser usado como dados

de teste. Esses dados devem ser cuidadosamente escolhidos para representar todas as

situações possíveis de serem encontradas. Em alguns casos, deve-se também separar

um terceiro conjunto de dados para a validação. Estes são utilizados para a realização

de um teste preliminar de verificação do desempenho do método de mineração de

dados antes de submetê-lo ao teste final.

1.3.2.2 Limpeza dos dados (data cleaning )

Os dados no mundo real tendem a ser incompletos, fora de padrões e

inconsistentes. As rotinas de limpeza de dados empreendem esforços no sentido de

preencher os valores ausentes, aplainar dados enquanto identificam valores fora de

padrões e corrigem inconsistências nos dados.

Na realidade, os dados fornecidos pelo cliente sempre têm problemas. Uma

vez que a procedência dos dados não é muito confiável, trazendo campos não

preenchidos em registros, erros de entrada de dados, entre outros, o processo KDD

não pode ter sucesso sem um esforço para purificá-los. Portanto, o trabalho necessário

para colocar esses dados de forma a serem usados deve ser considerado.

A limpeza dos dados é, na realidade, um processo ambíguo. Devido à baixa

qualidade dos dados, um cuidado especial deve ser tomado para não confundir um

Page 31: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 31/100

31

fenômeno interessante do domínio com uma anomalia ocasional. Em outras palavras, o

que parece ser uma anomalia ocasional dispensável pode vir a ser a chave dos pontos

centrais.Por exemplo, enquanto os pagamentos das parcelas do empréstimo são

analisados, pode-se eliminar a loja recebedora que nada recebeu, pois as outras lojas

receberam muito, desde que se atribua um valor zero ao problema da qualidade dos

dados. Por outro lado, não se pode esquecer que, em algumas instâncias, a loja com

recebimento zero pode conduzir a um conhecimento sobre determinadas condições que

a tornem não funcional, embora isso possa ser uma limpeza correta dos dados. Podem-

se remover todas as transações vazias de uma base de dados. Entretanto, registros

vazios são cruciais para medir a produtividade do encarregado do caixa e, algumas

vezes, ajudam a localizar as fraudes.

Valores ausentes

Valores ausentes se caracterizam (SANTOS, 2007) por existirem em diversastuplas (ou registros) atributos (campos) que não possuem valores armazenados, os

quais podem ser importantes para o processo de mineração de dados. Como exemplo,

o atributo rendimento em uma instância de uma entidade cliente. A seguir serão

apresentados alguns métodos que podem ser utilizados para preencher valores a esses

atributos:

1. Ignorar o registro   – usualmente utilizada quando o conteúdo da variável está

ausente. Não é muito efetivo, a menos que a tupla possua muitos atributos com

valores ausentes. É especialmente pobre quando o percentual de valores

ausentes varia consideravelmente;

Page 32: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 32/100

32

2. Preencher o valor manualmente   – em geral essa abordagem consome muito

tempo e pode não ser possível em grandes bases de dados com muitos valores

ausentes;3. Usar uma constante global para preencher os valores ausentes   – atualizar todos

os valores ausentes com um único valor constante. Embora simples, não é muito

recomendado;

4. Utilizar um atributo médio pertencente à mesma classe à qual a tupla pertença  -

utilizado quando o atributo é do tipo numérico e seu significado é passível de

utilização de um valor médio. Calcular valores médios do atributo em estudo

segundo os valores (classificação) de um outro atributo (por exemplo, profissão

do cliente) e atribuir esse valor a todos os valores ausentes do atributo (por

exemplo, rendimento do cliente), segundo a classificação do atributo;

5. Utilizar o valor de maior probabilidade para preencher os valores ausentes - este

valor pode ser determinado através da aplicação de uma técnica de regressão,ferramentas de inferência básica, utilizando um formalismo bayesiano ou indução

por árvores de decisão. Por exemplo, utilizar outros atributos do conjunto de

dados de clientes para construir uma árvore de decisão para predizer seu

rendimento.

A utilização de outros atributos na estimação dos valores ausentes, nos dá

uma grande chance de preservar o relacionamento entre o atributo estimado e os

demais atributos utilizados no processo de estimação.

Valores fora de padrão

Noisy data  (valores extremos) são um erro aleatório ou uma variação

acentuada na medição de uma variável. Ocorrem em varáveis numéricas do tipo

Page 33: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 33/100

33

rendimento, faturamento etc., que precisam ser aplainadas, retirando-se erro de

medição. A seguir são apresentados alguns métodos que podem ser utilizados para

corrigir esses valores:1. Binning   – esse método ordena os valores do atributo para utilizar o conceito de

vizinhança entre os dados. Após a ordenação os valores são distribuídos por

grupos, e cada grupo deverá ter o mesmo número de elementos (valores). Em

cada grupo aplica-se um critério na escolha de uma medida para ajustar os

valores dos grupos, tais como as medidas aritméticas, a mediana ou um valor de

limite. Assim, substituem-se os valores pelas medidas calculadas em cada grupo,

ajustando, assim, os valores da série. Diversos métodos podem ser utilizados

para ajustar os valores dos grupos.

2. Agrupamento (clustering ) - Outliers  podem ser detectados quando valores

similares são organizados em grupos ou clusters . Intuitivamente, valores que

estão fora dos clusters podem ser considerados como outliers . A figura 2 mostraa aplicação da técnica de agrupamento para detecção de outliers.

Figura 2 Detectando outliers com a técnica da análise de agrupamentos. Seleção doautor.

Fonte: WECA, 2007.

Page 34: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 34/100

34

3. Combinação de inspeção humana e computador - outliers  podem ser

identificados através da combinação de inspeção humana e do uso do

computador. Em uma aplicação, uma medida teórica pode ser utilizada paraajudar a identificar padrões de outliers. Uma vez identificados os padrões de

outliers e sendo considerados lixo, podem ser excluídos da utilização na etapa

de mineração de dados;

4. Regressão  – dados podem ser ajustados por funções de ajustamentos de dados,

tais como funções de regressão. Regressão linear busca encontrar a melhor

linha de ajustamento para duas variáveis, desde que uma possa ser estimada

(predita) pela outra. Regressão linear múltipla é uma extensão da regressão

linear, onde duas ou mais variáveis são envolvidas e os dados combinados numa

superfície (plano) multidimensional.

Dados inconsistentes

Pode haver inúmeras inconsistências nos dados armazenados. Alguns dosdados inconsistentes são corrigidos manualmente utilizando referências externas, como

erros causados por entrada de dados manual. Ferramentas de software de engenharia

de conhecimento podem também ser utilizadas para detectar violações nas restrições

de integridades dos dados, tais como funções de dependência entre atributos. Podem,

também, existir inconsistências causadas por integrações de dados, onde um atributo

pode possui nomes diferentes em seus bancos de dados. Podemos ter redundância

dos dados.

1.4 Integração de dados

Page 35: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 35/100

35

O processo de mineração de dados freqüentemente requer a integração (união,

consolidação, fusão) de várias bases de dados. Nesse processo, provavelmente,

também existirá a necessidade de transformar os dados integrados em um formatoapropriado para o processo de mineração de dados.

1.4.1 Integração de diversas fontes de dados

A integração de dados geralmente envolve a combinação de várias fontes de

dados em um único armazenamento coerente, semelhante as bases de dados

geradas no processo de construção de um data warehouse. Essas fontes de dados

podem incluir vários bancos de dados, arquivos textos, flat files entre outros tipos de

armazenamento. Existem, segundo Santos (2007), três pontos importantes na

integração de esquemas:

  Integração de esquemas internos  – diversas entidades do mundo real podem

ser semelhantes e estarem definidas em diversos esquemas com nomes eatributos diferentes, recaindo num problema típico de identificação de

entidades. Quando se têm apenas bancos de dados operacionais e/ou data 

warehouses para integração, essa atividade se torna mais fácil, uma vez que

esses armazenamentos devem possuir metadados, os quais ajudam a evitar

esse tipo de problema.

  Redundância de dados  - um atributo pode ser redundante se ele puder ser

derivado de outro armazenamento (tabela), tal como o atributo agregado

salário anual. Inconsistências em atributos ou nome de dimensões (salário,

salário anual etc.) podem ser a causa de redundância em conjunto de dados.

Uma técnica muito interessante para verificar redundância em conjunto de

Page 36: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 36/100

36

dados é a utilização da análise de correlação, a qual medirá o quanto dois

atributos são correlatos. A redundância no atributo também pode ser

identificada através da geração de registros (tuplas) idênticos gerados numamesma entrada de dados.

  Detecção e resolução de valores conflitantes - para as mesmas entidades do

mundo real, os valores dos atributos podem diferir em diversas fontes de

dados. Preços de produtos, diárias de hotéis, salários de empregados etc.,

numa mesma empresa, podem ser registrados em unidades e moedas

diferentes, incluindo ou não parcelas de valores tais quais impostos ou taxas.

A heterogeneidade semântica dos dados pode causar grandes desafios na

integração dos dados.

Outros fatores como os vários formatos de armazenamento dos dados, tais

como armazenamentos e bancos de dados relacionais, de rede e hierárquico, arquivos

textos, campos fixos e variáveis, entre outros formatos irão afetar a forma como serecuperam e integram os dados. A variedade dos sistemas operacionais e plataformas

de hardware também são fatores que dificultam o acesso aos inúmeros protocolos para

a recuperação e integração dos dados.

Os cuidados na integração dos dados oriundos de várias fontes podem ajudar

a reduzir e evitar redundâncias e inconsistências no resultado do conjunto de dados

gerado na integração.

Certamente irá melhorar a precisão dos resultados e a velocidade das fases

subseqüentes dos processos de garimpagem.

1.5 Transformação dos dados

Page 37: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 37/100

37

Se houver atributos cuja representação deva ser modificada, podem-se fazer

algumas manipulações nos dados para o melhor processamento (SANTOS, 2007).Têm-se, como exemplo, os dados do problema “jogar golfe”: 

Figura 3 Conversão de dados nominais para booleanos.Fonte: Santos, 2007, p. 4 (dm02).

Um outro exemplo de transformação ilustra a “normalização” de uma base de

dados de ocorrência de eventos:

Figura 4 Conversão de dados numéricos para booleanos.Fonte: Santos, 2007, p. 5 (dm02).

Figura 5 Conversão de dados numéricos para booleanos (usando faixas de valores).Fonte: Santos, 2007, p. 5 (dm02).

Page 38: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 38/100

38

Figura 6 Conversão de dados ordinais para booleanos (usando faixas de valores).Fonte: Santos, 2007, p. 6 (dm02).

Loja Caixa Transação Compras03 05 011672 ‘Pão francês’ 

03 05 011673 ‘Pão francês’ 

03 06 010169 ‘Pão francês’ 

03 05 011674 ‘Pão francês’,‘Pimentão’,’leitePasteurizado’,‘Danone’,’adoçante’ 

01 14 003752 ‘Pão francês’,’Leite pasteurizado’ 

01 14 003758 ‘Coca-cola’,‘Pão francês’,’Leite pasteurizado’ 

01 13 003001 ‘Leite pasteurizado’,‘Pão francês’ 

03 05 011685 ‘Pão francês’,‘Pão francês’ 

01 14 003764 ‘Açúcar União’,’Feijão Taruma’,‘Pão francês’ 

03 05 011688 ‘Pão francês’ 

01 14 003765 ‘Biscoito triunfo’,’Bisc. Bauducco’,‘Pão

francês’,’açúcar refinado’,’Mortadela Marba’ 

03 06 010188 ‘Pão francês’,‘açúcar refinado’ 

Page 39: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 39/100

39

Loja Caixa Trans. PF FLVPV LPSS DDC ADML RFCC1 LPPT ARU FPT1 ...03 05 001672 T F F F F F F F F

03 05 011673 T F F F F F F F F

03 06 010169 T F F F F F F F F

03 05 011674 T T T T T F F F F

01 14 003752 T F T F F F F F F

01 14 003758 T F F F F T T F F

01 13 003001 T F F F F F T F F

03 05 011685 T F F F F F F T T

01 14 003764 T F F F F F F F F

03 05 011688 T F F F F F F F F

01 14 003765 T F F F F F F F F

Figura 7 Conversão de dados de ocorrência para booleanos.Fonte: Santos, 2007, p. 6 (dm02).

A segunda parte da tabela 7 mostra que ocorrências existiam como booleanos.

Outra possível forma de transformar a primeira parte da tabela seria contar o número de

itens ao invés de simplesmente indicar a existência.

É importante observar que transformações em dados devem ser feitas

considerando que tipo de dados podem ser entrados em um determinado algoritmo e

qual é o significado da mudança do tipo de dado. Quem deve responder essa segunda

pergunta é quem conhece os dados e pode estimar o impacto da transformação.

1.6 Seleção de dados

Nesta etapa serão identificados todos os dados necessários para o processo

de mineração de dados. Vale a pena ressaltar que esta etapa, acorrendo após a etapa

de integração, possibilita a seleção somente do conjunto de dados que possa ser

Page 40: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 40/100

40

efetivamente utilizado e cuja integração já garantiu a coerência entre as diversas fontes

de dados utilizados.

Uma vez preparados e transformados os dados para um formato padrão, aexpectativa para a mineração de dados é muito grande. Para uma quantidade de dados

moderada, a tabela já está pronta para que se faça a exploração, mas para uma grande

amostra existe um passo intermediário, a redução de dados , que deve ser seguido

antes da aplicação de programas de pré-elaboração (SANTOS, 2007).

Muitas vezes a tabela usada tem mais de cem campos, mas apenas 10 deles

são usados para uma decisão. A seleção dos dados a serem utilizados no processo

KDD deve ser feita de forma que somente os dados não relevantes sejam retirados. É

muito importante a identificação correta dos dados relevantes. No caso de uma análise

incorreta no decorrer do processo, os dados descartados podem ser necessários

posteriormente.

O objetivo da seleção de atributos é encontrar um subconjunto de atributoscom desempenho editável comparável ao conjunto original. Dado um conjunto de

atributos m, o número de subconjuntos a serem analisados é finito, e o procedimento

que procura encontrar a solução é feito sempre com base no conjunto original. Os

resultados são avaliados, e o subconjunto de atributos com o melhor desempenho é

selecionado. Entretanto, há dificuldades óbvias nessa abordagem:

Para uma quantidade grande de atributos, o número de subconjuntos que

pode ser enumerado é algo impossível de ser manipulado;

O padrão de uma avaliação é o erro encontrado. Para uma vasta amostra, a

maioria dos métodos editáveis gasta muito tempo para encontrar uma

solução e estimar o erro.

Page 41: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 41/100

41

Diversas abordagens têm sido descritas para filtrar ou transformar atributos em

um conjunto menor. A idéia de separar seleção de atributos de pré-elaboração foi

criada pelo fato de o espaço de busca e o tempo computacional gasto serem bastante

diferentes de uma tarefa para outra. Os métodos lógicos apresentam uma perspectiva

inovadora para a seleção de atributos, constituindo-se em um processo dinâmico e

coordenado pela busca de soluções. Esses particionam os dados em grupos de casos

menores, examinando os valores dos atributos, porém em ordem não randômica. Têm-

se duas tarefas essenciais para o desempenho desses métodos:

Ordenar os valores;

Analisar o erro para cada valor.

Com uma quantidade de dados moderada, a ordenação de valores não é um

processo complexo. Já com o uso de uma amostra maior, a ordenação desses valores

torna-se uma tarefa árdua. Os outros métodos, entretanto, são estatísticos, pois o

aprendizado é feito separadamente da seleção.

1.6.1 Redução de dados

Redução de dados é uma técnica que pode ser aplicada para obtenção de uma

representação reduzida (compactada) de um conjunto de dados, muito menor em

volume, mantendo a integridade do conjunto de dados original. Garimpar nesseconjunto de dados reduzidos pode produzir resultados mais eficientes do que no

conjunto de dados originais. Podem-se aplicar, conforme propõe Santos (2007) as

seguintes técnicas para a redução de dados:

Page 42: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 42/100

42

  Agregação de dados em cubo -  operações de agregação de dados são

aplicadas para a construção de cubos de dados (estrutura multidimensional

para análise de dados);  Redução de dimensão  – atributos ou dimensões irrelevantes, fracos ou

redundantes são identificados e retirados;

  Compressão de dados  – mecanismos de codificação são aplicados para

reduzir o tamanho do conjunto de dados;

  Redução de numerosidade  – dados são alterados ou estimados por valores

alternativos, menores representações de dados tal como modelos

paramétricos ou métodos não paramétricos tais como clustering , amostras e

uso de histogramas;

  Discretização e geração de conceitos hierárquicos  – valores de atributos em

linhas ou registros são alterados por intervalos ou níveis de conceitos mais

elevados. Conceitos hierárquicos permitem a garimpagem de dados em

vários níveis de abstração e são fortemente utilizados em ferramentas de

mineração de dados.

Page 43: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 43/100

43

CAPÍTULO II

MINERAÇÃO DE DADOS

A etapa de mineração de dados envolve as fases de identificação dos objetivos

da mineração (sua funcionalidade), a identificação da melhor técnica e da abordagem

da aplicação de seus processos, ou seja, mineração de dados é o processo de busca

de relacionamentos e padrões globais existentes nas bases de dados (CARVALHO,

2005).

Devido à grande quantidade de dados dos sistemas de bancos de dados

atuais, esses relacionamentos estão escondidos, mas representam o valioso

conhecimento e seus objetos nos bancos de dados existentes.Os bancos de dados devem representar um espelho sincero do mundo real

registrado.

A definição de mineração de dados aceita por diversos pesquisadores foi

elaborada como sendo: “Extração de conhecimento de base de dados é o processo de

identificações válidas, potencialmente úteis e compreensíveis embutidos nos dados”

(SANTOS, 2007).

Para se compreender melhor o conteúdo dessa definição, ainda referindo

Santos (2007), deve-se olhar individualmente cada componente seu:

Page 44: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 44/100

44

  Dados   – conjunto de fatos ou casos em que há um repositório de

dados. Por exemplo, os dados correspondem aos valores dos campos

de um registro de vendas em uma base de dados qualquer;  Padrões  – denotam alguma abstração de um subconjunto dos dados

em alguma linguagem descritiva de conceitos;

  Processo  – a extração de conhecimento da base de dados envolve

diversas etapas como a preparação dos dados, busca por padrões e

avaliação do conhecimento;

  Válidos -  os padrões descobertos devem possuir algum grau de

certeza, ou seja, devem satisfazer funções ou limiares que garantam

que os exemplos cobertos e os casos relacionados ao padrão

encontrado sejam aceitáveis;

  Novos  – um padrão encontrado deve fornecer novas informações

sobre os dados. O grau de novidade serve para determinar quão novo

ou inédito é um padrão. Pode ser medido por meio de comparações

entre as mudanças ocorridas nos dados ou no conhecimento anterior;

  Úteis  – os padrões descobertos devem ser incorporados para serem

utilizados;

  Compreensíveis -  um dos objetivos de se realizar a mineração dos

dados é encontrar padrões descritos em alguma linguagem que pode

ser compreendida pelos usuários, permitindo uma análise mais

profunda nos dados;

Page 45: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 45/100

45

  Conhecimento   –  é definido em termos dependentes do domínio

relacionados fortemente com medidas de utilidade, originalidade e

compreensão.O processo de extração de conhecimento tem o objetivo de encontrá-lo a partir

de um conjunto de dados para ser utilizado em um processo decisório. Portanto, um

requisito importante é que esse conhecimento descoberto seja compreensível a

humanos, além de útil e interessante para os usuários finais do processo, que

geralmente são tomadores de decisão, de forma que ele forneça um suporte a esses

usuários no processo de decisão.

2.1 Objetivos primários da mineração de dados

Os objetivos primários da mineração de dados, na prática, são: a descrição e a

pré-elaboração .Na descrição, encontram-se os padrões de interpretação humana a partir da

descrição dos dados. Como exemplo, a produção de determinado cereal na última

colheita pode ser apontada a partir de um conjunto de dados armazenados. Nesse

caso, o valor da produção pode ou não ser confinado prontamente.

Por pré-elaboração entende-se a utilização de algumas variáveis ou campos na

base de dados para predizer o desconhecido ou valores futuros em variáveis de

interesse. Como exemplo, tem-se a previsão da produção do mesmo cereal na próxima

colheita a partir do conjunto de dados usado na descrição. Como a produção só será

determinada no final da colheita, esse dado não pode ser confirmado de imediato.

Page 46: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 46/100

46

A importância de cada uma dessas definições varia consideravelmente com a

aplicação em questão.

Independentemente dos objetivos primários da mineração de dados, as tarefasprimárias são as mesmas.

2.2 Tarefas primárias da mineração de dados

A mineração de dados necessita basicamente de técnicas (tarefas) para a sua

realização. Essas tarefas são de caráter genérico e podem ser implementadas através

de ferramentas diferentes como redes neuronais artificiais, estatística ou inteligência

artificial simbolista. São apresentadas muitas técnicas básicas, mas cinco delas

abraçam didaticamente todas as outras formas de apresentação e permitem uma visão

mais global e aproximada para uma introdução ao assunto.

2.2.1 Classificação

Para Carvalho (2005), a classificação é uma das mais utilizadas técnicas do

data mining, simplesmente porque é uma das mais realizadas tarefas cognitivas

humanas no auxílio à compreensão da ambiente em que vivemos. O ser humano está

sempre classificando o que percebe à sua volta: criando classes de relações humanas

diferentes (colegas de trabalho, amigos, familiares etc.) e dando a cada classe uma

forma diferente de tratamento, formada de protocolos de comportamento em diferentes

ambientes, definindo as classes sociais, estabelecendo preconceitos e tratando as

pessoas segundo esses estereótipos, entre outras formas de classificação. O homem,

ao receber qualquer estímulo do meio-ambiente e preparando-se para uma resposta a

Page 47: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 47/100

47

ele, busca, por analogia, classificar esse estímulo em categorias de outros estímulos já

recebidos no passado e para os quais possui uma resposta pronta e imediata. Assim,

não precisa produzir laboriosamente cada resposta aos estímulos do ambiente a cadainstante, pois possui classes de estímulos com suas respostas estereotipadas

construídas no passado e prontas para o uso. Como o mundo físico nada é exatamente

igual, por mais semelhante que pareça, para se criarem classes, é preciso afrouxar as

exigências de igualdade e permitir que detalhes sejam desprezados, e somente as

características principais sejam observadas. A tarefa de classificar normalmente exige a

comparação de um objeto ou dado com outros dados ou objetos, que supostamente

pertençam a classes anteriormente definidas. Para comparar dados ou objetos, utiliza-

se uma métrica ou forma de medidas de diferenças entre eles.

No data mining são comuns às tarefas de classificação de clientes em baixo,

médio ou alto risco de empréstimos bancários, de clientes potencialmente

consumidores de um determinado produto a julgar pelo seu perfil, de transaçõesfinanceiras como legais, ilegais ou suspeitas em sistemas de proteção e fiscalização do

mercado financeiro internacional, de ações de bolsas de valores com lucros potenciais

baixos, médios e altos, entre outras.

2.2.1.1 Classificação supervisionada

Na classificação supervisionada, já se sabem quantas classes se têm no

problema, com amostras rotuladas que permitem o treinamento do classificador.

Nessa fase, já se tem uma idéia de como a diferença entre as classes pode ser

modelada, por exemplo, através da análise do espaço de atributos.

Page 48: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 48/100

48

Essa classificação conta com algoritmos que podem criar funções

discriminantes ou métodos que permitem indicar, para os dados de uma instância, à

qual classe eles devem pertencer. Os modelos, classificadores, atributos, parâmetros aserem usados dependem da tarefa em questão, pois, dependendo da complexidade de

espaço de atributos, têm-se algoritmos simples e rápidos, e complexos e lentos.

2.2.1.2 Medidas de distância

Algoritmos para treinamento e classificação envolvem o cálculo de uma

distância entre dois ou mais pontos no espaço de atributos (com isso, identifica-se o

que é “parecido” no espaço de atributos). 

Algumas medidas de distância (entre a origem e o ponto em questão), segundo

Santos (2007), são:

  Distância manhattan ou City block - soma das distâncias, calculadas no

espaço de atributos, entre cada atributo da origem e do ponto emquestão. Simples e rápida para calcular, pode ter pouca precisão;

Figura 8 Classificação como identificação do que é “parecido” no espaço de atributos.Fonte: Santos, 2007, p. 4 (dm03).

Page 49: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 49/100

49

  Distância euclidiana   –  distância mínima entre os dois pontos

considerando todas as coordenadas do espaço de atributos. Simples de

calcular, pode ser acelerada se o cálculo for somente para comparação;

  Distância de Mahalanobis ou máxima verossimilhança   – distância

calculada considerando o espalhamento dos dados, inclusive orientação

de amostras de uma determinada classe. Deve ser calculada entre um

ponto e um conjunto de amostras.

Figura 9 Algumas formas de calcular distâncias.Fonte: Santos, 2007, p. 4 (dm03).

As medidas de distância são simples. Podem-se considerar algumas extensões

e exceções:

Se todos os atributos forem numéricos e da mesma dimensão/magnitude,

podem-se usar as medidas da forma como estão;

Se alguns atributos forem nominais ou ordinais, o pré-processamento poderá ser

necessário. Ainda como alternativa, regras de cálculo de distâncias

(condicionais, pesos etc.) podem ser usadas;

Page 50: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 50/100

50

Pesos para diferentes atributos podem ser usados.

2.2.1.3 Conceitos adicionaisO treinamento de um classificador supervisionado pode gerar assinaturas 

(conjunto de valores que caracterizam uma classe no espaço de atributos), regras  

(conjunto de condições para determinar se uma instância pertence a uma classe),

protótipos (exemplos de instâncias, reais ou não, que representam uma classe).

Vale a pena lembrar que as instâncias serão usadas no treinamento e para a

classificação em si. As instâncias usadas devem conter rótulos das classes conhecidas,

e as classes usadas para a classificação terão seus rótulos de classes determinados

pelo algoritmo.

Para se obterem resultados mais precisos, uma instância pode ser rejeitada

pelo classificador se o resultado não for satisfatório (depende do algoritmo e da

implementação).

2.2.1.4 Métodos da classificação supervisionada 

2.2.1.4.1 Método do paralelepípedo

Santos (2007) refere que o método de classificação supervisionada precisa de

amostras ou instâncias com classes ou rótulos.Usa limiares ou extremos dessas como

assinaturas, compara atributos de uma instância para ver se estão dentro dos limiares e

resolve as classes.

A figura 10 ilustra a classificação pelo método paralelepípedo. Usando os

dados da figura, pode-se considerar que a instância pertence à classe lilás se o seu

atributo 1 está entre a  e b  e o seu atributo 2 está entre c  e d, e que uma instância

Page 51: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 51/100

51

pertence à classe verde se o atributo 1 está entre e e f e o seu atributo 2 está entre g e

h .

Figura 10 Exemplos de classificação com paralelepípedos.Fonte: Santos, 2007, p. 6 (apostila 03).

Verifica-se, então, quais são os valores extremos para cada classe e para cada

atributo.

Armazenam-se como assinaturas os valores extremos por classe e atributos,

para se verificar a qualidade, reclassificam-se os dados usados para criar as

assinaturas com os extremos criados.

2.2.1.4.2 Fase de classificação supervisionada

Para essa fase, consideram-se os seguintes critérios:

Para cada instância com classe desconhecida, verifica-se se os valores

dos atributos estão contidos nos extremos para a classe, marcando a

classe como sendo selecionável;

Page 52: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 52/100

52

Se somente uma classe for selecionável, ela será escolhida; caso

contrário, usa-se um critério de desempate ou rejeição.

Assinaturas:

IRÍS-SETOSA:

Comprimento da sépala entre 4.3 e 5.8

Largura da sépala entre 2.3 e 4.4

Comprimento da pétala entre 1.0 e 1.9

Largura da pétala entre 0.1 e 0.6

IRÍS-VERSICOLOR:

Comprimento da sépala entre 4.9 e 7.0

Largura da sépala entre 2.0 e 3.4

Comprimento da pétala entre 3.0 e 5.1

Largura da pétala entre 1.0 e 1.8

IRÍS-VIRGINICA:

Comprimento da sépala entre 4.9 e 7.9

Largura da sépala entre 2.2 e 3.8

Comprimento da pétala entre 4.5 e 6.9Largura da pétala entre 1.4 e 2.5

Classificação:

Amostra 1: classe original é Iris-setosa Iris-setosa

Amostra 2: classe original é Iris-setosa Iris-setosa

Amostra 3: classe original é Iris-setosa Iris-setosa...Amostra 49: classe original é Iris-setosa Iris-setosa

Amostra 50: classe original é Iris-setosa Iris-setosa

Amostra 51: classe original é Iris-versicolor: múltiplas classes:Iris-versicolor Iris-virginica

Page 53: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 53/100

53

Amostra 52: classe original é Iris-versicolor: múltiplas classes:Iris-versicolor Iris-virginica

Amostra 53: classe original é Iris-versicolor: múltiplas classes:Iris-versicolor Iris-virginica

Amostra 54: classe original é Iris-versicolor Iris-versicolor...Amostra 98: classe original é Iris-versicolor Iris-versicolor

Amostra 99: classe original é Iris-versicolor Iris-versicolor

Amostra 100: classe original é Iris-versicolor Iris-versicolor

Amostra 101: classe original é Iris-virginica Iris-virginica...Amostra 148: classe original é Iris-virginica Iris-virginica

Amostra 149: classe original é Iris-virginica Iris-virginica

Amostra 150: classe original é Iris-virginica: múltiplas classes:Iris-versicolor Iris-virginica

Classificações corretas: 124Classificações incorretas: 0

Classificações múltiplas: 26Classificações que não puderam ser feitas: 0

2.2.1.4.3 Características

Entre elas destacam-se:

Método simples e rápido;

Usa cortes ortogonais no espaço de atributos para determinar regiões para

classificação. As regiões são hiperparalepípedas;

As assinaturas geradas são facilmente compreensíveis, semelhantes a um

sistema especialista;

Page 54: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 54/100

54

Rejeição pode ocorrer se a instância não pertencer a nenhum dos

hiperparalepípedos correspondentes às classes;

Atributos nominais e ordinais podem ser usados diretamente (comparação deordinais e numéricos com > , >= , < , <=, e de nominais categóricos como = e ≠ ); 

Pesos na comparação são facilmente implementados;

Interoperabilidade com sistemas especialistas e árvores de decisão;

Pode causar problemas de classificação, pois é possível que instâncias sejam

pertencentes a mais de um hiperparalelepípedo. Na figura 11, tem-se uma classe

cujo paralelepípedo está praticamente dentro do de outra classe.

Figura 11 Exemplos de classificação com paralelepípedos (com problemas potenciais declassificação).Fonte: Santos, 2007, p. 8 (apostila 3).

2.2.1.5 Menor distância a protótipo

Outro método simples de classificação supervisionada que usa a mínima

distância euclidiana é o protótipo de uma classe como assinatura.

Page 55: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 55/100

55

Comparando-se atributos de uma instância com o protótipo mais próximo

(considerando a distância euclidiana), indica-se a classe.

A figura 12 ilustra a classificação pelo método da menor distância a protótipo.Para cada classe tem-se um protótipo (neste exemplo, o ponto central ou médio das

instâncias reconhecidas como sendo de cada classe). Considera-se que uma instância

pertence a uma classe X se a distância euclidiana entre a instância e o protótipo da

classe X for menor que as distâncias entre a instância e os protótipos das outras

classes.

Figura 12 Exemplos de classificação com menor distância a protótipo.Fonte: Santos, 2007, p. 9 (apostila 3).

2.2.1.5.1 Fase de treinamento

Para se caracterizar tal fase:

Calcula-se a média (e/ou outras informações) para cada classe, usando-se as

amostras rotuladas de instâncias para as respectivas classes;

Page 56: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 56/100

56

Armazenam-se como assinaturas as médias (e/ou outras informações) como

protótipos das classes.

2.2.1.5.2 Fase de classificação

Nesta fase, pode-se referir que:

Para cada instância com classe desconhecida, verifica-se a menor distância

entre instâncias e os protótipos das classes;

Atribuem-se a instâncias as classes cujo protótipo tiver menor distância;

Raramente se tem empate, mas se pode estabelecer distância máxima para

criar rejeição.

Como exemplo, usa-se novamente a classificação das flores íris:

Assinaturas:

IRÍS-SETOSA:

Comprimento médio da sépala médio: 5.0059996

Largura média da sépala: 3.4180002

Comprimento médio da pétala: 1.464

Largura média da pétala: 0.24399997

IRÍS-VERSICOLOR:

Comprimento médio da sépala médio: 5.936002

Largura média da sépala: 2.77

Comprimento médio da pétala: 4.26Largura média da pétala: 1.3259999

Page 57: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 57/100

57

IRÍS-VIRGINICA:

Comprimento médio da sépala média: 6.5879993

Largura média da sépala: 2.9740002

Comprimento médio da pétala: 5.5520005Largura média da pétala: 2.0260003

Classificação:

Amostra 1: (Iris-setosa) dist: 0.15 3.27 4.80 = Iris-setosa

Amostra 2: (Iris-setosa) dist: 0.44 3.25 4.84 = Iris-setosa

Amostra 3: (Iris-setosa) dist: 0.41 3.43 5.00 = Iris-setosa...Amostra 49: (Iris-setosa) dist: 0.41 3.19 4.68 = Iris-setosa

Amostra 50: (Iris-setosa) dist: 0.14 3.26 4.82 = Iris-setosa

Amostra 51: (Iris-versicolor) dist: 3.98 1.23 1.16 = Iris-virginica...Rafael Santos - www.lac.inpe.br/~rafael.santosAmostra 52: (Iris-versicolor) dist: 3.58 0.70 1.21 = Iris-versicolor

Amostra 53: (Iris-versicolor) dist: 4.13 1.22 0.90 = Iris-virginica...Amostra 99: (Iris-versicolor) dist: 1.99 1.55 3.13 = Iris-versicolor

Amostra 100: (Iris-versicolor) dist: 2.99 0.29 1.86 = Iris-versicolor...Amostra 149: (Iris-virginica) dist: 4.60 1.65 0.66 = Iris-virginica

Amostra 150: (Iris-virginica) dist: 4.08 0.99 0.85 = Iris-virginica

Classificações corretas: 139

Classificações incorretas: 11

2.2.1.5.3 Características

São elas:

Método simples e rápido, assinaturas compactas, facilmente compreensíveis;

Page 58: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 58/100

58

Possibilita rejeição com parâmetro adicional (máxima distância tolerada);

Intuito: qual protótipo é o mais próximo, ou seja, qual classe é a mais próxima

no espaço de atributos;

Considera que as classes têm distribuição hiperesférica no espaço de atributos;

Assume-se que o empate (duas classes cujos protótipos tem distâncias iguais

a uma instância) é raro.

2.2.2 Agrupamento (clustering )

A análise de agrupamento possui vários algoritmos diferentes e métodos por se

agruparem objetos de tipo semelhante em categorias respectivas. Uma pergunta geral

de investigadores em muitas áreas de investigação é como organizar dados

observados em estruturas significantes, quer dizer, desenvolver taxonomias. Em outras

palavras, a análise de agrupamento é uma ferramenta de análise de dados exploratória

que busca ordenar objetos diferentes (de certo modo) em grupos requerindo o grau de

associação entre dois objetos: no máximo se eles pertencerem ao mesmo grupo e

mínimo caso contrário. Dado o anterior, a análise de agrupamento pode ser usada para

descobrir estruturas em dados sem prover uma interpretação da explicação.

Lida-se com “crescer em cachos” em quase todos os aspectos de vida diária.

Por exemplo, um grupo de pessoas que compartilham a mesma mesa em um

restaurante pode ser considerado como um agrupamento das pessoas. Em comida,

armazena artigos de natureza semelhante, como tipos diferentes de carne ou legumes;

é exibido nos mesmos ou em locais. Próximo exemplo: biólogos têm que organizar as

espécies diferentes de animais antes de uma descrição significante das diferenças

Page 59: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 59/100

59

entre animais. De acordo com o sistema moderno empregado em biologia, homem

pertence aos primatas, os mamíferos, os vertebrados e os animais. Nesta classificação

se te: o mais alto, o nível de agregação; o menos semelhante são os sócios na classerespectiva. Homem tem mais em comum com todos os outros primatas (por exemplo,

macacos), o que faz com os sócios mais distantes dos mamíferos (por exemplo,

cachorros). Em resumo, qualquer que seja a natureza de um negócio, cedo ou tarde se

terá um problema agrupando de uma forma ou outra.

Essa funcionalidade visa segmentar um conjunto de dados num número de

subgrupos homogêneos ou clustering . Seu objetivo é formar grupos baseados nos

princípios de que esses grupos devem ser o mais homogêneos em si e mais

heterogêneos entre si. A diferença fundamental entre a formação de agrupamento e a

classificação é que, no agrupamento, não existem classes predefinidas para classificar

os registros em estudo. Os registros são agrupados em função de suas similaridades

básicas, ou seja, quando se desejam formar agrupamentos, seleciona-se um conjuntode atributos (variáveis) e, em função da similaridade desses atributos, são formados os

grupos.

A tarefa consiste em identificar agrupamentos de objetos, que identificam uma

classe. Por exemplo, pode-se aplicar análise de clusters sobre o banco de dados de um

supermercado a fim de se identificarem grupos homogêneos de clientes, por exemplo:

clientes aglutinados em determinados pontos da cidade costumam vir ao supermercado

aos domingos, enquanto clientes aglutinados em outros pontos da cidade costumam

fazer suas compras às segundas-feiras.

Os algoritmos não-supervisionados criam grupos de dados onde:

  Cada instância pertence a um grupo; 

Page 60: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 60/100

60

  Instâncias em um grupo são semelhantes entre si; 

  Instâncias em grupos diferentes são diferentes entre si. 

Esses algoritmos são conhecidos também como algoritmos de classificaçãonão-supervisionada ou de aprendizado auto-organizado.

2.2.2.1 Medidas de distâncias 

A ligação ou árvore que agrupam métodos usam, seguindo Santos (2007),

dessemelhanças (semelhanças) ou distâncias entre objetos ao formar os

agrupamentos. Semelhanças são um jogo de regras que servem como critérios por se

agruparem ou separarem artigos. Por exemplo, usa-se uma regra para se agruparem

vários jantares e ver se eles compartilharam a mesma mesa ou não. Essas distâncias

(semelhanças) podem estar baseadas em uma única dimensão ou dimensões múltiplas,

com cada dimensão que representa uma regra ou condiciona por se agruparem

objetos. Por exemplo, se agruparem comidas rápidas, pode-se levar em conta o númerode calorias que elas contêm, o preço deles/delas, avaliações subjetivas de gosto etc. O

modo mais direto de computar distâncias entre objetos em um espaço multi-dimensional

é computar distâncias euclidianas. Se houvesse dois objetos, ou espaço tridimensional,

essa medida é a distância geométrica atual entre objetos no espaço (como se medido

como uma regra). O algoritmo de ligação, porém, não se preocupa se as distâncias

alimentadas são reais distâncias atuais, ou alguma outra medida derivada de distância

que é mais significante ao investigador.

Os métodos de clustering normalmente utilizam uma medida de dissimilaridade

para avaliar o grau de semelhança entre dois objetos durante o processo de

agrupamento. Muitas vezes, essa media é apresentada como sendo a distância entre

Page 61: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 61/100

61

dois objetos. A combinação entre a escolha das variáveis, transformações das variáveis

(homogeneização) e as medidas de dissimilaridade escolhidas é que traduz

operacionalmente o termo “associação natural” entre objetos (Santos 2007).

2.2.2.1.1 Métricas

As métricas mais utilizadas são:

Distância euclidiana;

Distância quarteirão.

Os algoritmos de clustering  podem ser classificados em duas categorias

principais: método hierárquico e método de particionamento ou relocação interariva.

2.2.2.1.2 Tipos de agrupamentos

As técnicas de agrupamento mais conhecidas são: o agrupamento por

particionamento e o agrupamento hierárquico.  Agrupamento por particionamento  – o algoritmo das K-means  é o

mais utilizado e divide o grupo total de itens em subgrupos. O dataset é

tratado como um vetor e, cada informação é considerada uma

componente vetorial. Se o banco de dados não for numérico, a técnica

não funciona, portanto os dados qualitativos devem ser transformados

em variáveis numéricas, pois o algoritmo trabalha com distâncias entre

os pontos. Pontos próximos formam um grupo. Para plotagem dos

dados, lança-se mão de uma função de distância, e a mais utilizada é a

função euclidiana e a função Manhattan. Faz-se necessário definir

Page 62: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 62/100

62

previamente o número de grupos a ser criado, e esse número é

denominado de K, daí o nome de K-médias. Inicia-se, então, com o

algoritmo dividindo o dataset  em K grupos e plotando um pontochamado centróide (mean ) no meio de cada grupo. Na seqüência,

reposicionam-se os centróides de acordo com a sua distância em

relação aos outros pontos do grupo. Com o centróide reposicionado, os

grupos são novamente plotados. Em seguida, os centróides são

novamente recalculados e o processo se repete até que os grupos

estejam bem definidos.

  Agrupamento hierárquico  – nesse tipo de agrupamento, o algoritmo

mais utilizado é o HAC. Essa técnica trabalha de duas formas:

1. Processo divisivo: começa com um cluster  único e vai

particionando-o em clusters menores, em processos iterativos;

2. Processo aglomerativo: faz o processo ao contrário: inicia emcluster pequeno e vai-se agrupando em clusters maiores.

Após o processo de agrupamento, o analista deve estudar os padrões

identificados procurando verificar se esses podem ser transformados em conhecimento

estratégico. O agrupamento não responde porque os padrões existem, apenas os

identifica.

2.2.3 Associação

As associações visam determinar relacionamentos entre conjuntos de itens,

tais como “90% de pessoas que compram pão também levam leite”. Exemplos de uso

de regras de associação são projetos de catálogos, projeto de layout  de

Page 63: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 63/100

63

lojas/prateleiras, segmentação de clientela baseada em padrões de compra, etc., onde

itens podem ser agrupados, por exemplo, em catálogos ou espaços físicos, de modo a

induzir a venda de artigos relacionados.As seqüências visam determinar padrões de ordenação entre dados, tais como

ordenações temporais, ou ordenação de classificação, por exemplo, “42% das pessoas

que viram De Volta para o Futuro: Parte I” voltaram ao cinema para assistir “De Volta

para o Futuro: Parte II”. As seqüências são um tipo especial de associação, onde os

itens associados são resultantes de transações diferentes. As seqüências podem ser

amplamente empregadas em mala direta, sistemas médicos, sistemas meteorológicos.

A classificação de séries de tempo visa definir grupos com séries de tempo

similares, ou seja, mesmo padrão de comportamento numa dada fatia de tempo, com

inúmeras possibilidades de aplicação prática, tais como identificação de produtos com

mesmos padrões de vendas, detecção de comportamento similar de instrumentos

financeiros.O algoritmo de descoberta de regra de associação identifica afinidades entre

itens de um subconjunto de dados. Essas afinidades dão expressas em forma de

regras: “72% de todos os registros que contêm os itens A, B e C também contém D e

E”. A por centagem de ocorrência (72, no caso) representa o fator de confiança da regra

e costuma ser usado para eliminar tendências fracas, mantendo apenas as regras mais

fortes. Dependências funcionais podem ser vistas como regra de associação com fator

de confiança igual a 100%.

Trata-se de um algoritmo tipicamente endereçado à análise de mercado, em

que o objetivo é encontrar tendências dentro de um grande número de registros de

compras, por exemplo, expressas como transações. Essas tendências podem ajudar a

Page 64: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 64/100

64

entender e a explorar padrões de compras naturais e podem ser usadas para ajudar

mostruários, modificar prateleiras ou propagandas e introduzir atividades promocionais

específicas.Um exemplo distinto, em que a mesma técnica pode ser utilizada, é o caso de

um banco de dados escolar, relacionando alunos e disciplinas. Uma regra do tipo “84%

dos alunos inscritos em „Introdução a Linux‟ também estão inscritos em „Programação

em Java‟” pode ser usada pela direção ou secretaria para planejar o currículo anual, ou

alocar recursos como salas de aula e professores.

Uma variante do problema de regras de associação é a análise de seqüências,

onde as regras encontradas entre as relações podem ser usadas para identificar

seqüências interessantes, que serão utilizadas para predizer acontecimentos

subseqüentes. Nesse caso, não apenas a coexistência de itens dentro de cada

transação é importante, mas também a ordem em que aparecem e o intervalo entre

elas. As seqüências podem ser úteis para identificar padrões temporais, por exemplo,entre compras em uma loja, ou utilização de cartões de crédito, ou ainda tratamentos

médicos.

2.2.3.1 Exemplo de aplicação de técnicas de associação

Quando determinados padrões de comportamento, como associação de

produtos durante um processo de compras, por exemplo, começam a se repetir com

freqüência, as ferramentas data mining  indicam a presença de oportunidades em

relação àquele público consumidor.

Um exemplo clássico de data mining  foi desenvolvido pela Wal-Mart. A

empresa descobriu que o perfil do consumidor de cervejas era semelhante ao de

Page 65: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 65/100

65

fraldas. Eram homens casados, entre 25 e 30 anos, que compravam fraldas e/ou

cervejas às sextas-feiras à tarde no caminho do trabalho para a casa. Com base na

verificação dessas hipóteses, a Wal-Mart optou por uma otimização das atividades juntoàs gôndolas nos pontos de vendas, colocando as fraldas ao lado das cervejas.

Resultado: o consumo cresceu 30% às sextas-feiras com a redefinição de

layout baseada na conexão de hipóteses desenvolvidas pelo data mining .

2.2.3.2 Regras de associação

O grande problema da descoberta de associações é que elas podem ter

ocorrido ao acaso. Como exemplo, considere-se a hipótese de que mais cegonhas

determinam um maior número de nascimento de crianças. Isso pode ser confirmado ao

serem analisadas correlações nos dados sobre ninhos de cegonhas e taxa de

natalidade de algumas regiões. Existe, porém, uma terceira variável que foi

desconsiderada na análise: a quantidade de chaminés. As áreas urbanas têm taxas denascimento 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 é valida 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.

Para Graça, Semaan e Dias, a partir dos conceitos apresentados, a extração

da regra de associação corresponde à obtenção de regra do tipo “se X ocorre então Y

Page 66: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 66/100

66

ocorre”, ou seja, X → Y, onde X e Y correspondem a conjuntos de eventos que ocorrem

com certa freqüência na base de dados. O algoritmo mais usado é o APRIORI, que foi

desenvolvido com o objetivo de tratar o problema de encontrar padrões referentes aprodutos que são comprados juntos com certa freqüência (a análise da cesta de

compras). A resolução desse 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 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 deitens de um subconjunto de dados, que é expressa na forma das regras de associação.

Considera-se 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 no conjunto {A,L,M}.

Page 67: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 67/100

67

Tabela 1 - Exemplo da base de dados com as transações de compras dos clientes e conjuntosde itens (produtos)

Transações (Compras)

Número da transação Conjuntos de itens (produtos)1 {A,L,M}

2 {D,L}

3 {D,L}

4 {A,L,M}

5 {A,D,L,M}

6 {A,D,M}

7 {A,D}8 {A,D,L,M}

9 {A,P}

10 {A,D,L,M}

Fonte: Graça; Semaan; Dias, p. 26.

Como foi dito, após a execução do algoritmo de associação sobre a base de

dados, serão obtidas regras do tipo X → Y. É importante observar que X, chamado de

antecedente da regra, corresponde a um conjunto de itens que pode variar de “um” a

vários itens. O mesmo vale para o conjunto Y, chamado de conseqüente da regra. Vale

ressaltar que nenhum item poderá pertencer, em uma mesma regra, aos conjuntos X e

Y.

Assim, a partir da base de dados do exemplo, podem ser encontradas regras

diferentes a padrões de comportamento de compras dos clientes como as

apresentadas no quadro 1. Nessa tabela, são apresentadas apenas algumas regras

dentre várias possíveis.

Page 68: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 68/100

68

Quadro 1 - Regras de associação e seus significados literais

Número Regra obtida Significado

1 M → L SE compra macarrão ENTÃO compra lasanha

congelada

2 A,D → M SE compra arroz E detergente ENTÃO compra macarrão

3 A → M,L SE compra arroz ENTÃO compra macarrão E lasanha

congelada

4 A,L →M,D SE compra arroz E lasanha congelada ENTÃO compra

macarrão E detergente

Fonte: Graça; Semaan; Dias, p. 26.

Cada uma das regras obtidas só poderá ser considerada como sendo um

padrão caso obtenha alguns critérios. O primeiro critério é o número de transações em

que o padrão obtido pode ser confirmado na base de dados. Esse critério, conhecido

como suporte da regra, corresponde à freqüência com que todos os itens presentes na

regra aparecem juntos em uma mesma transação da base de dados, mesmo que eles

apareçam com outros itens não presentes na regra. Assim, se o conjunto de itens de

uma regra ocorre em 50% das transações, seu suporte é igual a 0,5. Na base de dados

do exemplo, o suporte da regra A → L,M é igual a 0,5 (ou 50%), pois o conjunto de

itens da regra, ou seja {A,L,M} está presente nas transações 1, 4, 5, 8 e 10. Assim, para

que sejam obtidas regras que correspondam a padrões de comportamento, devem ser

obtidas apenas as regras que possuam o valor de suporte igual ou acima de um valor

mínimo, um que será referida como suporte mínimo ou SupMin.

É comum, ao utilizar um algoritmo de regras de associação em grandes bases

de dados, que o valor para suporte mínimo seja próximo a 3% (ou 0,03). Vale observar

que, quanto menor o valor escolhido para o suporte, mais conjuntos diferentes de itens

Page 69: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 69/100

69

irão satisfazê-lo e, conseqüentemente, mais regras poderão ser geradas; por outro

lado, quanto menor o valor do suporte, menos relevantes se tornarão as regras obtidas.

Esses conjuntos de itens são chamados de conjuntos freqüentes de itens(itensets). A partir dos conjuntos freqüentes, as regras poderão ser obtidas. Como

exemplo, verifica-se que, a partir do conjunto freqüente {A,L,M}, podem ser obtidas as

regras indicadas no quadro 2.

Quadro 2 - Regras possíveis a partir do conjunto freqüente {A,L,M}

A → L,M  L → A,M  M → A,L 

A,L → M  A,M → L  M,A → M Fonte: Graça; Semaan; Dias, p. 26.

2.2.3.3 Algoritmo

2.2.3.3.1 APRIORI - Obtenção dos conjuntos freqüentes 

O problema de se obterem os conjuntos freqüentes de itens de uma base de

dados de transações vem sendo tratado com bastante interesse pela comunidade

acadêmica nos últimos anos (GRAÇA; SEMAAN; DIAS).

O interesse é grande porque, a cada dia, as bases de dados se tornam maiores

e é necessário reduzir o tempo gasto pelo algoritmo para realizar o processamento das

transações durante a mineração. Apesar de os diferentes algoritmos fornecerem

tempos de execução diferentes para uma mesma base de dados, principalmente devido

à otimização nas estruturas de dados manipuladas internamente, as idéias principais do

algoritmo APRIORI ainda são utilizadas.

Quando o algoritmo APRIORI foi proposto, foi apresentada uma importante

propriedade dos conjuntos no contexto da obtenção de conjuntos freqüentes. Essa

Page 70: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 70/100

70

propriedade diz que “todo subconjunto de um conjunto freqüente também é freqüente” 

(GRAÇA; SEMAAN; DIAS).

Com essa propriedade, o problema de encontrar um conjunto freqüentecontendo n itens (referenciando também como conjunto freqüente de tamanho n ) passa

a ser o problema de encontrar primeiro os seus subconjuntos freqüentes. Como o

menor subconjunto com algum item é o subconjunto de tamanho 1 (contendo apenas 1

produto), então o primeiro passo é encontrar todos os produtos que ocorrem na base de

dados com freqüência igual ou superior ao valor do SupMin. A partir daqui, considere-

se a base de dados da tabela 1 e o valor SupMin como sendo igual a 0,5 (50%), que

corresponde a cinco transações da base da dados em questão, ou seja, deseja-se

encontrar os conjuntos freqüentes com suporte maior ou igual a 0,5.

Assim, para se obterem os conjuntos freqüentes será necessário varrer toda a

base de dados contando o número de transações em que cada item aparece. O

resultado desta contagem é apresentado na tabela 2:

Tabela 2 - Conjunto de itens tamanho 1

Conjunto de itens (ns) Nº de transações Suporte %

{A} 8 0,8 80

{D} 7 0,7 70

{L} 7 0,7 70

{M} 6 0,6 60

{P} 1 0,1 10

Fonte: Graça; Semaan; Dias, p. 27.

Pode, então, ser verificado que os itens A, D, L e M atendem ao suporte

mínimo definido, portanto, esses são os conjuntos freqüentes de tamanho 1. Nesse

Page 71: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 71/100

71

caso, qualquer conjunto freqüente maior do que 1 não poderá conter algum item

diferente desses quatro itens.

De forma geral, a partir dos conjuntos freqüentes de tamanho K, no APRIORI opróximo passo é a geração dos possíveis conjuntos de tamanho K + 1 (chamados de

“conjuntos candidatos”), para que, em seguida, seja verificado se eles são freqüentes

ou não. Os conjuntos candidatos são todos os conjuntos de tamanho K + 1 que podem

ser formados com os itens presentes nos conjuntos freqüentes de tamanho K. No

exemplo, K = 1 e os candidatos de tamanho K + 1 são as combinações dois a dois dos

quatros itens freqüentes obtidos. Após a geração desses candidatos, deve-se contar o

número de transações em que cada um dos pares de itens está presente. Para a base

de dados do exemplo, os pares obtidos e os respectivos valores de suporte após a

contagem são apresentados na tabela 3.

Tabela 3 - Conjuntos candidatos formados a partir dos conjuntos freqüentes de tamanho 1

Conjunto de itens Número de transações Suporte %

{A,M} 6 0,6 60

{A,D} 5 0,5 50

{A,L} 5 0,5 50

{D,L} 5 0,5 50

{D,M} 4 0,4 40

{L,M} 5 0,5 50

Fonte: Graça; Semaan; Dias, p. 27.

Conforme apresentado na tabela 3, considerando o SupMin igual a 0,5, os

conjuntos freqüentes de tamanho dois são {A,M}, {A,D}, {A,L}, {D,L} e {L,M}. Como visto

anteriormente, o próximo passo do algoritmo APRIORI será obter os conjuntos

Page 72: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 72/100

72

candidatos de tamanho 3. Como os itens presentes nos conjuntos freqüentes de

tamanho 2 são A, D, L e M, as combinações 3 a 3 desses itens formam os conjuntos

candidatos apresentados na tabela 4.

Tabela 4 - Candidatos de tamanho 3, gerados a partir dos conjuntos freqüentes de tamanho 2

Conjuntos de itens

{A,D,L}

{A,D,M}

{A,L,M}

{D,L.M}

Fonte: Graça; Semaan; Dias, p. 27.

Observando-se a tabela 4, verifica-se que existem conjuntos candidatos nos

quais estão contidos subconjuntos de tamanho 2 que não foram considerados

freqüentes. Esses conjuntos candidatos são o conjunto {A, D, M}, que possui o

subconjunto não freqüente {D, M} e o subconjunto {D, M, L} que também possui osubconjunto não freqüente {D, M}. Portanto, esses conjuntos candidatos também

podem ser considerados não freqüentes sem a necessidade de realizar a contagem de

ocorrências na base de dados. Tal procedimento de eliminação de candidatos que

possuam subconjuntos não freqüentes é chamado de “poda” e evita consumir recursos

computacionais com a contagem de conjuntos que já se sabe, em princípio, não serem

freqüentes.

Em seguida, através de contagem na base de dados, deve ser determinado o

suporte de cada um dos conjuntos candidatos que não foram podados. Os conjuntos

Page 73: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 73/100

73

candidatos não podados e seus valores de suporte, referentes à base de dados do

exemplo, são apresentados na tabela 5.

Tabela 5 - Candidatos formados a partir dos conjuntos freqüentes de tamanho 2

Conjunto de itens Número de transações Suporte %

{A, D, L} 3 0,3 30

{A, L, M} 5 0,5 50

Fonte: Graça; Semaan; Dias, p. 27.

No algoritmo APRIORI, com os conjuntos freqüentes de tamanho 3, devem-se

gerar candidatos de tamanho 4, realizar a poda e calcular os seus valores de suporte.

Em seguida, com os conjuntos freqüentes de tamanho 5, e assim por diante,

até que não seja possível gerar candidatos K a partir dos conjuntos freqüentes de

tamanho K – 1.

Voltando ao exemplo, após a contagem do suporte dos conjuntos candidatos

de tamanho 3 (Tabela 5), verifica-se que apenas o conjunto {A, L, M} é freqüente (com

o valor do suporte igual ao SupMin). Assim, a elaboração dos conjuntos freqüentes se

encerra aqui, tendo-se em vista que, com apenas os itens A, L e M, não é possível

obter conjuntos candidatos de tamanho 4.

2.2.3.3.2 Geração de regras a partir dos conjuntos de itens freqüentesApós a conclusão da etapa de obtenção dos conjuntos de itens freqüentes na

base de dados, devem ser geradas as regras de associação. Essa nova etapa é critica,

tendo-se em vista que podem ter sido obtidos muitos conjuntos freqüentes e, para cada

Page 74: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 74/100

74

um deles, podem-se obter várias regras através das combinações de seus itens no

antecedente e conseqüente de cada regra.

No exemplo, foram obtidos os conjuntos freqüentes apresentados na tabela 6,a partir dos quais podem ser geradas as regras de associação. Deve-se observar que,

para a geração de regras, só são utilizados os conjuntos freqüentes de tamanho maior

ou igual a 2. Na segunda coluna da tabela 6 são apresentados as possíveis regras para

cada um dos conjuntos freqüentes de itens.

Tabela 6 - Regras possíveis para cada um dos conjuntos freqüentes

Conjuntosfreqüentes

Regras

{A, M} A M; M A

{A, D} A D; D A

{A, L} A L; L A

{L, M} L M; M L

{D, L} D L; L D

{A, L, M} A L, M; L A, M; M A, L; A, L M; A,M L; L, M A

Fonte: Graça; Semaan; Dias, p. 27.

É fácil concluir que o número de regras possíveis pode tornar- se muito grande,

principalmente quando se têm muitos conjuntos freqüentes de tamanho superior a dois,

inviabilizando qualquer análise por parte dos usuários de mineração de dados. Assim,

são necessários critérios, ou medidas, que possam identificar, das possíveis regras de

associação, quais são as mais interessantes.

Com esse intuito, várias medidas de interesse vêm sendo pesquisadas e

algumas são muito utilizadas na literatura do que as outras. Segundo Graça, Semaan e

Dias, a partir da escolha de uma medida de interesse, cada regra de associação

Page 75: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 75/100

75

possível de ser gerada é avaliada e aquelas que não atendam a um valor mínimo

definido serão descartadas. Outra alternativa é o algoritmo apresentar as regras

geradas em ordem de valor para a medida de interesse utilizada, o que permitirá aousuário verificar as regras geradas por ordem de relevância.

Dada uma regra X → Y, onde X é o conjunto de itens do antecedente da regra,

Y é o conjunto de itens do seu conseqüente e X U Y é o conjunto de todos os itens

presentes no antecedente e no conseqüente, têm-se as seguintes medidas de interesse

sobre a regra, considerando P(X) igual ao número de transações contendo os itens de

X, dividindo pelo número total de transações da base de dados.

Dentre as medidas de interesse, serão mostradas as 4 mais utilizadas:

confiança, lift, coverage e leverage :

a) Confiança: através dessa medida, verifica-se a ocorrência de

transações em que todos os itens da regra aparecem, sobre as

transações em que os itens do antecedente estão presentes;b) Lift: foi chamada inicialmente de interest e é utilizada para avaliar o grau

de dependência do conseqüente em relação ao antecedente de uma

regra. A lift  indica quão mais freqüente torna-se B quando A ocorre. Se

lift  (X → Y) = 1, a ocorrência dos itens do conseqüente é estatisticamente

independente da ocorrência dos itens do antecedente, e vice-versa. Se

lift   (X → Y) > 1, então os itens do antecedente e conseqüente são

positivamente dependentes. Se lift  (X → Y) < 1, os itens do antecedente

e conseqüente são negativamente dependentes;

c) Coverage: indica a proporção de transações em que estão presentes os

itens que compõem o antecedente da regra;

Page 76: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 76/100

76

d) Leverage: corresponde à diferença entre as ocorrências dos itens do

antecessor X e do conseqüente Y, juntos em uma mesma transação, e a

ocorrência esperada dos itens de X e Y, caso esses sejamestatisticamente independentes.

No exemplo apresentado, será considerada apenas a medida “confiança”. A

medida confiança é a mais utilizada na aplicação do algoritmo APRIORI. Entretanto, a

maioria das ferramentas de mineração de dados que utilizam o APRIORI permitem

também a escolha de outras medidas para a geração das regras.

Page 77: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 77/100

77

CAPÍTULO III

ESTUDO DE CASO

Apresentados alguns resultados de técnicas aplicadas à mineração de dados

(data mining ), serão usadas, em especial, a visualização e obtenção de regras de

associação e clusterização, aplicadas à análise dos sorteios da mega sena.

A mega sena é uma das loterias mais populares no Brasil, onde são sorteadas

6 dezenas semanalmente, e os valores dos prêmios podem chegar à casa dos milhares

ou milhões.

Com todos os dados dos sorteios que ocorreram de março de 1996 a julho de

2007, totalizando 888 concursos, será feita uma análise para extrair todas as

informações interessantes, tentando demonstrar a viabilidade e aplicabilidade de

técnicas de mineração de dados à análise dos resultados dos sorteios teoricamente

equiprováveis, ou seja, não se assume a possibilidade de obtenção de qualquer

informação realmente aplicável para a seleção das dezenas.

Este estudo visa apenas revelar informações que possam guiar os apostadores

para a escolha das dezenas.

Será utilizado o software WECA, onde serão apresentadas as técnicas que

podem ser usadas e também os seus respectivos resultados; para que aconteça a

mineração, os dados coletados devem ser pré-processados, ou seja, os dados originais

são transformados para o formato .arff para que possam ser processados pelos

algoritmos de data mining .

Page 78: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 78/100

78

Em seguida, serão aplicadas algumas metodologias e os algoritmos utilizados

para a técnica da associação e clusterização, fornecendo seus respectivos resultados.

3.1 Técnica de associação

As associações visam determinar relacionamentos entre conjuntos de itens,

tais como “94% de confiança de que, quando a dezena 26 não saiu, a dezena 54

também não saiu”.

As seqüências visam determinar padrões de ordenação entre dados, onde os

itens associados são resultantes de transações diferentes. A técnica de associação visa

definir grupos similares, ou seja, mesmo padrão de comportamento numa dada fatia de

tempo, problema igual com inúmeras possibilidades de aplicação prática, tais como

identificação de dezenas que acontecem com a mesma freqüência dentro do banco de

dados, detecção do comportamento das dezenas sorteadas.O algoritmo de descoberta de regra de associação identifica afinidades entre

itens de um subconjunto de dados. Essas afinidades dão expressas as formas de

regras: “94% dos registros que contêm as dezenas 48 e 54, também contêm a dezena

26”. A porcentagem de ocorrência (94, no caso) representa o fator de confiança da

regra, e costuma ser usado para eliminar tendências fracas, mantendo apenas as

regras mais fortes. Dependências funcionais podem ser vistas como regra de

associação com fator de confiança igual a 100%.

Trata-se de um algoritmo tipicamente endereçado à análise da base de dados,

onde o objetivo é encontrar tendências dentro de um grande número de registros, por

exemplo, expressas como os concursos e suas dezenas. Essas tendências podem,

Page 79: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 79/100

79

também, ajudar a entender e a explorar padrões de compras naturais, e ser usadas

para ajustar mostruários, modificar prateleiras ou propagandas e introduzir atividades

promocionais específicas.Um exemplo distinto, onde a mesma técnica pode ser utilizada, é o caso de um

banco de dados escolar, relacionando alunos e disciplinas. Uma regra como “84% dos

alunos inscritos em „Introdução a Linux‟ também estão inscritos em „Programação em

Java‟” pode ser usada pela direção ou secretaria para planejar o currículo anual, ou

alocar recursos como salas de aula e professores.

Uma variante do problema de regras de associação é a análise de seqüências,

onde as regras encontradas entre as relações podem ser usadas para identificar

seqüências interessantes, a serem utilizadas para predizer acontecimentos

subseqüentes. Nesse caso, não apenas a coexistência de itens dentro de cada

transação é importante, mas também a ordem em que aparecem e o intervalo entre

elas. Seqüências podem ser úteis para identificar padrões temporais, por exemplo,entre compras em uma loja, ou utilização de cartões de crédito, ou tratamentos médicos

e também, no caso, as dezenas sorteadas da mega sena.

3.1.1 Dados

Antes de executar a aplicação, precisa-se formatar os dados para o formato

.ARFF (attribute-Relation File Format), que é o formato esperado pelos componentes do

software WECA.

O arquivo no formato ARFF é um arquivo de texto puro, composto de três

partes:

Page 80: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 80/100

80

 Relação  –  a primeira linha do arquivo, que deve ser igual a @relation, 

seguida de uma palavra-chave que identifique a relação ou a tarefa

estudada;  Atributos  – um conjunto de linhas onde cada uma inicia com @attribute 

seguida do nome do atributo e do seu tipo, que pode ser nominal ou

numérico; 

 Dados  –  depois de uma linha contendo @data. Cada linha deve

corresponder a uma instância e ter valores separados por vírgula

correspondente (e na mesma ordem) dos atributos da seção Atributos. 

Os dados foram coletados no site da Caixa Econômica Federal, com

possibilidade de download  no formato HTML, e foram reformatados para o formato

ARFF.

O arquivo formatado será apresentado na figura 13:

Page 81: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 81/100

81

Figura 13 Arquivo ARFF com os resultados da mega sena configurado para ser usado emtécnicas de associação.Fonte: WECA, 2007.

3.1.2 Metodologia (associação)

Com os dados coletados e armazenados no formato correto, fai-se-á uma

primeira análise usando as técnicas de associação para verificar que tipo de regras se

encontrará.

Como as associações visam determinar relacionamentos entre os conjuntos de

dezenas sorteadas, serão indicados quais elementos ocorrem nos registros com

freqüência e, para o estudo em questão, podem indicar que dezenas não são

freqüentemente sorteadas, tais como “com 94% de certeza de que, das 736 vezes em

que a dezena 26 não saiu, a dezena 54 também não saiu em 787 vezes”.

Page 82: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 82/100

82

Uma variante do problema de regras de associação á a análise de seqüencias,

onde as regras encontradas entre as relações podem ser usadas para identificar

seqüências interessantes, a serem utilizadas para predizer acontecimentossubseqüentes.

A extração da regra de associação corresponde à obtenção de regra 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 certa freqüência na base de dados. É importante observar

que X, chamado de antecedente da regra, corresponde a um conjunto de itens que

pode variar de “um” a vários itens. O mesmo vale para o conjunto Y, chamado de

conseqüente da regra, ressaltando que nenhum item poderá pertencer, em uma mesma

regra, aos conjuntos X e Y.

Para essa técnica, o algoritmo mais usado é o APRIORI, que foi desenvolvido

com o objetivo de tratar o problema de encontrar padrões referentes a dezenas que são

 jogadas junto com certa freqüência.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 é valida 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.

Considere-se uma base de dados dos sorteios da mega sena com 888

concursos, como apresentada na tabela 7. As dezenas sorteadas nos concursos

correspondem às dezenas de 01 a 60. Para cada concurso são indicadas as dezenas

Page 83: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 83/100

83

sorteadas. Como exemplo, no concurso 1, foram sorteadas as dezenas 04, 05, 30, 33,

41, 52, o que é representado no conjunto {04, 05, 30 33, 41, 52}.

Tabela 7 - Exemplo da base de dados com os respectivos concursos e seu conjunto de itens(dezenas)

Concursos mega sena

Concursos Conjunto de itens (dezenas)

01 {04, 05, 30 33, 41, 52}

02 {09, 37, 39, 41, 43, 49}

03 {10, 11, 29, 30, 36, 47}04 {01, 05, 06, 27, 42, 59}

05 {01, 02, 06, 16, 19, 46}

06 {07, 13, 19, 22, 40, 47}

... 

886 {17, 33, 37, 50, 55, 59}

887 {01, 12, 21, 32, 34, 44}

888 {24, 40, 50, 52, 54, 60}

Fonte: WECA, 2007.

Assim, a partir da base de dados do exemplo podem ser encontradas regras

diferentes a padrões de comportamento das dezenas sorteadas como apresentadas na

tabela 8. Nessa tabela, são apresentadas apenas algumas regras dentre várias

possíveis.

Cada uma das regras obtidas só poderá ser considerada como sendo um

padrão caso obedeça a alguns critérios. Um dos critérios é o número de transações em

que o padrão obtido pode ser confirmado na base de dados. Esse critério, conhecido

como suporte da regra, corresponde à freqüência com que todos os itens presentes na

Page 84: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 84/100

84

regra aparecem juntos em uma mesma transação da base de dados, mesmo que eles

apareçam com outros itens não presentes na regra. Assim, se o conjunto de itens de

uma regra ocorre em 50% das transações, seu suporte é igual a 0,5.

Tabela 8 - Regras de associação e seus significados literais

R R. obtida Significado

1 54 → 26 Se não sorteou a dezena 26, então não sorteou a dezena 54.

2 17 → 39 Se não sorteou a dezena 39, então não sorteou a dezena 17.

3 48, 54 → 26  Se não sorteou a dezena 26, então não sorteou as dezenas 48 e

54.4 52, 54 → 26  Se não sorteou a dezena 26, então não sorteou as dezenas 52 e

54Fonte: WECA, 2007.

Para que sejam obtidas regras que correspondem a padrões de

comportamento, devem ser obtidas apenas as regras que possuam o valor de suporte

igual ou acima de um valor mínimo, onde será referenciado como suporte mínimo. 

3.1.3 Descobertas de regras de associação

Essa técnica pode mostrar informações sobre as dezenas sorteadas, pois

indicam as dezenas que ocorrem com maior freqüência na base de dados.

Para indicar as dezenas que ocorreram com menor freqüência, será usado oalgoritmo APRIORI e os seguintes parâmetros: -N 10 –T 0 –C 0.9  –D 0.05  –U 1.0  –M

0.1 -S 1.0, onde foi solicitado que fossem geradas 10 regras (-N 10), em que a medida

de interesse seja a de confiança (-T 0), pois, através de tal medida de interesse,

verifica-se a ocorrência de transações em que todos os itens da regra aparecem. Sobre

Page 85: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 85/100

85

as transações em que os itens do antecedente estão presentes, no valor da mínima

métrica (-C 0.9) estipula-se que o valor de suporte mínino seja de 90%, ou seja, devem

ser obtidas regras cujo valor de suporte seja igual ou acima de 90%. No valor de delta,utiliza-se 0.05 (-D 0.05), que reduz o apoio até que o suporte mínimo ou o número de

regras seja alcançado; já o valor de lowerBoundMinSupport (-U 1.0) diminui o limite do

suporte mínimo, o valor do mínimo suporte (-M 0.1) considera só regras com contagens

mais altas que este valor de 0.1 e, por fim, o valor do nível de significação (-S 1.0),

medindo somente a confiança.

Para que se consiga visualizar as relações que menos ocorreram, serão usados

valores mais altos para os parâmetros  –D (delta), -M (mínimo suporte), -C (mínima

métrica), pois se espera muitas associações com o valor “NÃO”. 

O resultado dessa experiência é mostrado na figura 14:

Figura 14 Regras de associação utilizando o algoritmo APRIORI, verificando o atributo “NÃO”. Fonte: WECA, 2007.

As regras de associação listadas na figura 14 mostram as dezenas que saíram

com menor freqüência e se pode dizer, com 94 % de confiança, que, dos 888

Page 86: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 86/100

86

concursos da mega sena, em 736 concursos a dezena 26 não saiu, assim como a

dezena 54.

Usando-se como valores de parâmetro: -N 10 -T 0 -C 0.93 -D 0.05 -U 1.0 -M 0.1-S -1.0, onde se altera apenas o valor de mínima métrica, troca-se o -C 0.9 para  –C

0.93; com isso, solicita-se para o algoritmo que ele mostre apenas as regras que

possuem valor de confiança igual ou maior que 93%.

Os resultados dessa mudança de parâmetros serão mostrados na figura 15:

Figura 15 Regras de associação com valor de mínima métrica alterado para 0.93.

Fonte: WECA, 2007.

As regras encontradas na figura 15 mostram regras que foram geradas a partir

de conjuntos freqüentes devido ao fato de que a mínima métrica força a gerar apenas

regras em que o valor de confiança seja igual ou maior que o valor da mínima métrica.

Obtiveram-se muitos conjuntos freqüentes e, para cada um deles, podem-se

obter várias regras através das combinações de seus itens no antecedente econseqüente de cada regra.

Pode-se afirmar, então, que, com 94% de confiança, a dezena 26 não saiu em

674 concursos e que as dezenas 48 e 54 também não saíram.

Page 87: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 87/100

87

É comum, ao utilizar um algoritmo de regras de associação em grandes bases

de dados, que o valor para suporte mínimo seja próximo a 3% (ou 0,03). Vale observar

que, quanto menor o valor escolhido para o suporte, mais conjuntos diferentes de itensirão satisfazê-lo e, conseqüentemente, mais regras poderão ser geradas; por outro

lado, quanto menor o valor do suporte, menos relevantes se tornarão as regras obtidas.  

Altera-se então, os parâmetros para -N 10 -T 0 -C 0.04 -D 0.01 -U 0.2 -M 1.0E-4

-S -1.0, trocando-se valor de mínima métrica para 0.04 (-C 0.04), o valor de delta para

0.01 (-D 0.01), o valor de lowerBoundMinSupport para 0.2 (-U 0.2), o valor do mínimo

suporte para 0.0001 (-M 1.0E-4), geram-se as regras que serão apresentadas a figura

16.

As regras de associação listadas na figura 16 mostram quais dezenas

apareceram em conjunto com outras. Somente associações de duas dezenas foram

encontradas entre as dez regras mais relevantes e dentre essas regras, a primeira

regra pode ser interpretada como “25% de confiança, a dezena 54 foi sorteada em 17concursos e a dezena 26 também foi sorteada”. 

Figura 16 Regras de associação com valor de mínima métrica alterado para 0.04. Fonte: WECA, 2007.

Page 88: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 88/100

88

3.2 Técnica de clusterização 

De uma forma geral, obter a solução para um algoritmo de clusterizaçãocorresponde ao processo de agrupar os elementos (objetos) de uma base de dados

(conjunto) de tal forma que os grupos formados, ou clusters, representem uma

configuração em que cada elemento possua uma maior similaridade com qualquer

elemento do mesmo cluster do que os elementos de outros clusters. 

As técnicas de clusterização vêm sendo tratadas com freqüência na literatura

para a solução de vários problemas de aplicações práticas em diversas áreas do

conhecimento.

O objetivo principal do clustering  é separar os objetos ou observações em

classes naturais, de forma que os elementos pertencentes a um mesmo grupo tenham

um alto grau de semelhança ou similaridade, enquanto quaisquer elementos

pertencentes a grupos distintos tenham pouca semelhança entre si.Os critérios mais comuns adotados em clustering  são homogeneidade e

separação:

Homogeneidade refere-se a objetos pertencentes a um mesmo cluster,

que devem ser tão similares quanto possível;

Separação está relacionada a objetos de diferentes clusters, que devem

ser distintos entre si, tanto quanto possível.

3.2.1 Dados

Explorando a base de dados da mega sena, será agora, utilizada a técnica de

clusterização para se extraírem novos conhecimentos. Para se utilizar o software Weca,

Page 89: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 89/100

89

precisa-se que a base de dados esteja também com as configurações necessárias no

formato .ARFF, como mostra a figura 17:

Figura 17 Arquivo ARFF com os resultados da mega sena configurado para ser usado emtécnicas de clusterização .Fonte: WECA, 2007.

3.2.2 Metodologia (clusterização)

Com os dados coletados e armazenados no formato correto, procede-se a uma

primeira análise usando a técnica de clusterização  para se verificar quais são osagrupamentos formados.

Quando se faz clusterização de dados numéricos, normalmente isso é realizado

assumindo que os pesos de um vetor de características definem um ponto no espaço e

Page 90: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 90/100

90

encontrado a distância entre os pontos (número de pontos é medido pelo número de

clusters solicitados).

No estudo preliminar realizado, as etapas iniciais de seleção, pré-processamento e transformação já fornecerem informações relevantes.

Como o objetivo deste estudo é identificar qual é o melhor algoritmo a ser

utilizado para determinadas técnicas, devem-se atribuir ao item atributos dois clusters  

para que haja uma melhor visualização dos agrupamentos formados, utilizando o

algoritmo Simple K-means, que cria um conjunto de K clusters e distribui o conjunto de

dados entre esses clusters  usando a similaridade entre os vetores e os centróides

desses clusters ( um centróide é um vetor médio de todos os vetores no respectivo

cluster).

Considerando ainda a base dos concursos da mega sena, têm-se os seguintes

atributos: concurso, data do sorteio, dezena 1, dezena 2, dezena 3, dezena 4, dezena

5, dezena 6, ganhadores da sena, rateio da sena, ganhadores da quina, rateio daquina, ganhadores da quadra, rateio da quadra, mega sena acumulou, valor

acumulado, os dados são apresentados como mostra a figura 18:

Figura 18 Atributos utilizados na técnica de clusterização.Fonte: WECA, 2007.

Page 91: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 91/100

91

Para que se consigam visualizar, graficamente, os clusteres criados, devem-se

adicioná-los a essa lista de atributos, como mostra a figura 19:

Figura 19 Atributos utilizados na clusterização com a adição do cluster como atributo.Fonte: WECA, 2007.

Na inserção dos clusters, eles devem ser previamente configurados, indicando

que o algoritmo utilizado será o Simple K-Means e, também, o número de clusteres que

deverão ser criados. O cluster foi configurado para se criar dois clusteres. 

Criado o atributo cluster,   já se pode visualizá-lo graficamente de uma forma

bem simplificada, mas já mostrando valores relevantes para que se consigam obter

informações, como mostra a figura 20:

Page 92: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 92/100

92

Figura 20 Dados exibidos de forma gráfica incluindo os clusteres adicionados.Fonte: WECA, 2007.

As cores solicitadas para a plotagem do gráfico é a do atributo “mega sena

acumulou”, onde a cor azul informa que a mega sena acumulou e a cor vermelha

informa que a mega sena não acumulou.

Analisando-se superficialmente a figura 20, podem-se visualizar algumas

informações interessantes como: as dezenas que mais foram sorteadas, quantas vezes

a mega sena acumulou ou não, e observa-se também o atributo cluster que gerou dois

grupos (objetos) onde os elementos desses grupos possuem maior semelhança ou

similaridade entre si.

Executando a técnica de clusterização, calcula-se a métrica para a

separabilidade e compactação dos grupos.

Page 93: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 93/100

93

Têm-se, como saída, os grupos (centróide, desvio padrão), medidas (contagem

de dados, erro quadrático total), e o objetivo principal é minimizar o erro quadrático, pois

para cada grupo calcula-se a distância entre todos os pontos pertencentes a um grupoe aos seus centróides, divide-se pelo número de dados para aquele grupo e somam-se

as distâncias para todos os agrupamentos gerados.

Cada grupo identificado é caracterizado por todos os dados numéricos

presentes na base de dados.

Utilizando o algoritmo Simple K-means, o software  WECA executa todos os

cálculos necessários para que os dados sejam agrupados, como se vê na figura 21.

A figura 21 informa alguns pontos de interesse, tais como:

Nas linhas 31 e 32, são mostrados alguns resultados do processo de

agrupamento: número de iterações até convergência e medida objetivo

minimizadas (soma dos erros quadráticos entre clusters );

Nas linhas 34 até a 48, são mostrados os centróides e os desviospadrões de cada cluster;  

Finalmente, a partir da linha 50, mostra-se o número de instâncias que

foram atribuídas para cada cluster. 

1. === Run information ===2.3. Scheme: weka.clusterers.SimpleKMeans -N 2 -S 104. Relation: megasena-weka.filters.unsupervised.attribute.AddCluster-Wweka.clusterers.SimpleKMeans -N 2 -S 10

5. Instances: 8886. Attributes: 177. concurso8. mes9. dezena110. dezena211. dezena312. dezena413. dezena514. dezena615. ganhadores_sena16. rateio_sena17. ganhadores_quina

Page 94: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 94/100

94

18. rateio_quina19. ganhadores_quadra20. rateio_quadra21. megasena_acumulou22. valor_acumulado23. cluster

24. Test mode: evaluate on training data25.26. === Model and evaluation on training set ===27.28. kMeans29. ======30.31. Number of iterations: 232. Within cluster sum of squared errors: 1209.992399559346733.34. Cluster centroids:35.36. Cluster 0 37. Mean/Mode: 623.4263 Dezembro 8.5201 16.3036 25.6942 34.5402 42.97138. 52.3772 0.2656 2925472.869 89.6049 17046.0506 6035.1295 222.1696 SIM 10331153.635839.40. Std Devs: 182.4736 N/A 6.8142 8.7092 10.0932 9.984 9.1025 6.655341. 0.6192 8849724.5517 78.8103 8535.3345 4500.1602 72.3929 N/A 10029684.0415 N/A42.43. Cluster 1 44. Mean/Mode: 262.3205 Janeiro 9.1114 18.6818 27.675 36.4318 44.9545 52.981845. 0.2977 2263665.3256 104.8864 16991.5439 6560.1364 231.8595 SIM 6075128.638246.47. Std Devs: 181.8828 N/A 6.7957 8.879 9.8185 8.944 8.3836 6.092748.0.9304 7758338.2809 182.1007 29339.438 6484.4269 627.5157 N/A 7591867.185 N/A49.50. Clustered Instances51.52. 0 448 ( 50%)

53. 1 440 ( 50%)

Figura 21 Apresentação dos grupos com seus respectivos cálculos.Fonte: WECA, 2007.

O funcionamento do algoritmo Simple K-Means  exige a definição prévia do

número de clusters e o posicionamento do centro dos clusters, chamado de centróide,

que é o ponto médio do cluster é calculado pelo algoritmo.

Esse algoritmo é sensível ao ruído, mas em termos de desempenho, é

relativamente eficiente para grandes bases de dados.

Os passos básicos do algoritmo Simple K-Means são:

Passo 1: seleção de n  objetos para serem centros iniciais dos K clusters;  

Page 95: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 95/100

95

Passo 2: cada objeto é associado a um cluster, para o qual a

dissimilaridade entre o objeto e o centro do cluster  é menor que as

demais; Passo 3: os centros dos clusteres são recalculados, redefinindo cada um

em função dos atributos de todos os objetos pertencentes ao cluster;  

Passo 4: retorna ao passo 2 até que os centros dos clusters  se

estabilizem. 

A cada interação os objetos são agrupados em função do centro do cluster mais

próximo e, por conseqüência, os centros dos clusters são reavaliados (passo 3). Isso

provoca, no espaço, o deslocamento dos centros médios. O algoritmo é interrompido

quando as médias não mais são deslocadas, ou há uma insignificante realocação de

objetos entre os clusters, e o cluster gerado pelo algoritmo na base da mega sena é

mostrado na figura 22.

A figura 22 mostra os clusters gerados, utilizando o atributo “ganhadores_sena”

e através desse, pode-se visualizar que o maior agrupamento de ganhadores acontece

entre os números 1 e 2 ganhadores; o mesmo pode ser feito para todos os outros

atributos; podem-se visualizar os agrupamentos dos outros atributos como mostra a

figura 23:

Page 96: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 96/100

96

Figura 22 Apresentação dos clusters gerados utilizando o atributo “ganhadores_sena”. Fonte: WECA, 2007.

Figura 23 Apresentação dos clusters gerados utilizando o atributo “dezena 1”. Fonte: WECA, 2007.

A figura 23 mostra os clusters  gerados, utilizando o atributo “dezena 1” e

através deste, pode-se visualizar a maior incidência de números sorteados na primeira

dezena acontece entre as dezenas 1 e 20; nota-se, também, que, em todos os

concursos, nunca foi mostrada alguma dezena maior que o número 39.

Page 97: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 97/100

97

Aplicando a técnica de clusterização, pode-se analisar toda a base de dados

procurando os dados que obtiveram maior semelhança entre si, ou seja, agrupar é

simplesmente classificar uma massa de dados em classes desconhecidas a priori emnúmero ou forma.

Uma tarefa é, dadas várias categorias ou classes conhecidas, dizer a qual delas

um certo dado pertence; outra tarefa semelhante em objetivo, porém muito mais

complexa, é, de posse de uma massa de dados, dizer em quantas classes esses dados

se distribuem e como são essas classes.

A dificuldade reside inclusive no fato de que pode não haver tais classes, ou

seja, os dados se distribuem eqüitativamente por todo o espaço possível não

caracterizando nenhuma categoria, como mostra a figura 24. Na análise dos clusteres,

os grupos ou classes são construídos com base na semelhança entre os elementos,

cabendo ao analisador das classes resultantes avaliar se essas significam algo de útil.

Figura 24 Apresentação dos clusters  gerados utilizando os atributos “ganhadores_sena” e“mês” com cores representando os clusteres .Fonte: WECA, 2007.

Page 98: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 98/100

98

A análise dos clusters normalmente é uma técnica preliminar utilizada quando

nada ou pouco se sabe sobre os dados, como na metodologia da descoberta não-

supervisionada de relações.

CONCLUSÃO

Page 99: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 99/100

99

Todas as etapas do processo de mineração de dados, desde a preparação dosdados até a exploração em si, são de extrema importância e exigem que a mesma

atenção seja dispensada para cada uma delas.

O sucesso de uma etapa depende exclusivamente do bom desenvolvimento

das etapas anteriores, daí a importância de uma disciplina evidente na realização de

um processo KDD.

No mundo atual, um sistema de descoberta de conhecimento que funciona

sozinho pode não ser muito útil; é necessário que ele seja integrado a outros sistemas

para que, em conjunto, explorem todas as fases do processo e as conclua com

sucesso.

O objetivo é encontrar padrões que possam ser facilmente entendidos pelos

analistas dos dados e pelos usuários, extraindo dos dados informações relevantes paraa geração do conhecimento, auxiliando assim a tomada de decisão.

Page 100: Data Mining

5/13/2018 Data Mining - slidepdf.com

http://slidepdf.com/reader/full/data-mining-55a74de8ed301 100/100

100

REFERÊNCIAS BIBLIOGRÁFICAS

AMARAL, Fernanda. Data Mining  – Técnicas e aplicações para o marketing direto. SãoPaulo: Berkeley, 2001. 

CARVALHO, Luís. Data Mining  –  A mineração de dados no marketing, medicina,economia, engenharia e administração. Rio de Janeiro: Ciência Moderna, 2005.

SANTOS, Rafael (2007). Princípios e aplicações de mineração de dados. Disponívelem: <http://www.lac.inpe.br/~rafael.santos>. Acesso em: 15 jan. 2007.

GRAÇA, A. A.; SEMAAN, G. S.; DIAS, C. R. Data mining  e a descoberta deassociações em dados. SQL Magazine, ed. 26, ano 2, p. 22-30.