TCC Mineração de Dados

HELIO MOREIRA DA SILVA

MINERAÇÃO DE DADOS EM GRANDES BASES DE DADOS: UM ESTUDO DE AGRUPAMENTOS (CLUSTERING)

Centro Universitário Salesiano – U. E. Lorena

Lorena, 2006

2

Folha de Aprovação

HELIO MOREIRA DA SILVA

MINERAÇÃO DE DADOS EM GRANDES BASES DE DADOS:

UM ESTUDO DE AGRUPAMENTOS (CLUSTERING)

Centro Universitário Salesiano – U. E. Lorena

Lorena, 2006

Trabalho de Conclusão de Curso desenvolvido como requisito parcial para obtenção do grau de Bacharel em Ciência da Computação do Centro Universitário Salesiano de São Paulo – U.E. Lorena, sob a orientação do Prof. Ms. José Walmir Gonçalves Duque

3

Dedico à minha esposa Cláudia e minha filha Júlia Mariana, que

estiveram ao meu lado sempre, acreditaram em mim, apoiando-me nas

horas difíceis. A todas as pessoas que de uma forma ou de outra

contribuíram para que eu pudesse realizar este trabalho e me formar.

4

AGRADECIMENTOS

Gostaria de agradecer primeiramente à Deus, pois através dele tudo

é possível, à minha esposa Cláudia e filha Júlia Mariana, por terem me ajudado

acreditar que seria capaz fazer este trabalho, por terem paciência comigo nas

horas que me ausentei, por terem me dado apoio para não desistir nas horas

difíceis, aos meus familiares: pais, irmãos, sogro e sogra, com os quais pude

contar sempre, aos meus professores que, de uma forma ou de outra,

ajudaram na realização deste trabalho. Em especial, agradeço ao meu

orientador, Professor Ms. José Walmir Gonçalves Duque, pela oportunidade de

realizar este trabalho e por suas orientações, à Professora Giana Raquel Rosa

Gouvêa pela atenção e ajuda no desenvolvimento metodológico deste trabalho.

E, finalmente, quero agradecer aos meus colegas de classe, com os

quais pude conviver por quatro anos, criando um fraterno laço de amizade.

A todos, muito obrigado!

5

RESUMO

A evolução tecnológica tem propiciado a possibilidade de geração de inúmeras informações (registros) a cada momento, formando gigantescas bases de dados nas organizações (empresas, governo, universidades, hospitais, etc). Questões como “O que fazer com todos os dados armazenados?", "Como utilizar o patrimônio digital em benefício das instituições?", "Como analisar e utilizar, de maneira útil, todo o volume de dados disponível?", entre outras, surgem naturalmente. Porém a análise de toda essa informação a olho nu pelo homem não é simples, necessitando, portanto de técnicas e ferramentas que permitam adquirir, de forma automática, conhecimentos que estão implícitos nestas bases de dados. Neste contexto, surge uma nova área denominada Descoberta de Conhecimento em Bases de Dados (Knowledge Discovery in Databases - KDD), mais conhecida como “Mineração de Dados”, a qual é, na realidade, uma das etapas do processo de KDD. Essa nova área procura minerar as bases de dados em busca de conhecimentos úteis, valiosos para as organizações, que podem a partir destes tomar decisões importantes, fazer marketing, ser, portanto, mais competitivas no mercado. Este trabalho tem como objetivo descrever algumas técnicas e algoritmos de agrupamentos (clustering) para, a partir daí, escolher um algoritmo e aplicá-lo em uma base de dados de uma locadora de vídeo, descrevendo e interpretando os resultados com observações, conclusões e gráficos. Para esse intento, foi necessário conhecer o processo de KDD, aplicando as etapas: o “Pré-processamento”, que tem a função de captação, organização e tratamento dos dados, preparando-os para a mineração; a “Mineração de Dados”, também conhecida como “Data Mining”, a qual consiste em definir as tarefas, técnicas e algoritmos que podem ser aplicados sobre os dados para a descoberta de conhecimento – neste trabalho foi empregado o algoritmo “SimpleK-Means”; por fim, a etapa “Pós-processamento”, na qual o tratamento do conhecimento obtido na Mineração de Dados permite facilitar, para o homem, a interpretação e a avaliação da utilidade dos resultados. Nesta pesquisa, utilizou-se o WEKA, software gratuito, para a aplicação da Mineração de Dados, que gerou vários resultados interessantes, como por exemplo, gêneros mais alugados por bairro, gêneros menos alugados, preferência de gênero por sexo, clientes que mais e menos alugam, filmes que mais e menos alugam, entre outros. Conclui-se que este trabalho permite um grande aprendizado na área de Mineração de Dados, sobretudo em Agrupamentos, conhecendo melhor alguns algoritmos, em especial “K-Means”, “K-Modes”, “K-Medoids” e “SimpleK-Means”, nos quais constatou-se a desvantagem de ter que especificar o número de clusters; a sensibilidade destes algoritmos em relação a ruídos; as dificuldades em minerar bases de dados com grandes dimensões (muitos atributos), alterando significativamente os resultados e a vantagem que em quanto uns, como “K-Means”, trabalham com atributos numéricos, outros, como “K-Modes”, permitem trabalhar com dados categóricos (textos), e outros ainda, como “SimpleK-Means”, podem manipular os dois tipos de dados. Por fim, cabe ressaltar que é necessário muita pesquisa para obter-se um algoritmo que seja capaz de atender a todos os requisitos necessários à uma boa Mineração de Dados.

6

Palavras-chave: KDD; Tarefas de KDD; Técnicas e Algoritmos de Mineração de Dados; Métodos; Agrupamentos (Clustering); Weka.

ABSTRACT

The technological evolution has afforded the possibility of generating a great amount of information (registers) each moment, forming enormous quantity of databases in organizations (companies, government, universities hospitals, etc). Questions such as "What to make with all the stored data", "How to use the digital patrimony in benefit of the institutions", "How to analyze and to use, in useful way, all the available volume of data", among others, appear naturally. However, the analysis of all this information with the naked eye by man is not simple. He needs, therefore, techniques and tools that allow him to acquire, in an automatic form, knowledge that are implicit in these databases. In this context, there is a new area called “Knowledge Discovery in Databases – KDD”, known as "Data Mining ", which is, in reality, one of the stages of the KDD process. This new area tries to mine the databases searching valuable and useful knowledge for the organizations that can, from these, to take important decisions, to make marketing and, therefore, to be more competitive in the market. This work aims to describe some techniques and algorithms of groupings (clustering) and, from there, to choose an algorithm and to apply it in a database of a video rental shop, describing and interpreting the results with comments, conclusions and graphics. For this reason, it was necessary to know the KDD process, applying the stages: the “Pre processing”, that has the function of capitation, organization and treatment of the data, preparing them for the mining; the " Data Mining ", also known as " Date Mining ", which consists of defining the tasks, techniques and algorithms that can be applied on the data to discover knowledge - in this work the algorithm "SimpleK-Means" was used; finally, the stage "After-processing", in which the treatment of knowledge got during the process of Data Mining allows to facilitate, for man, the interpretation and the evaluation of the utility of results. This research generated some interesting results, for example, sorts more rented by quarter, sorts less rented, sort preference for gender, customers who rent more and who rent less, films that rent more and that rent less, among others. It is concluded that this work allows a great learning in Data Mining area, mainly in Groupings, some algorithms, specially "K-Means", "K-Modes", "K-Medoids" and "SimpleK-Means", in which the disadvantage of having to specify the number of clusters was evidenced; the sensitivity of these algorithms in relation to noise; the difficulties in mine databases with great dimensions (many attributes), significantly modifying the results and the advantage to notice that while some work with numerical attributes, others allow to work with categorical data (texts) and others still can manipulate these two types of data. Finally, it was possible to notice that much research is still necessary to get an algorithm that is able to pay attention to all the necessary requirements to a good Data Mining.

Key-words: KDD, Technicians and algorithms of Data Mining, Methods; Clustering; Weka.

7

LISTAS DE FIGURAS

Figura 1: Grandes quantidades de dados transformadas em conhecimentos. .......................... 24

Figura 2: Etapas do processo de KDD. ........................................................................................ 29

Figura 3: Análise de crédito........................................................................................................ 35

Figura 4: Uma árvore de decisão. .............................................................................................. 40

Figura 5: Classificação do dados. .............................................................................................. 43

Figura 6: Neurônio Artificial. ........................................................................................................ 48

Figura 7: Rede Neural Artificial. .................................................................................................. 49

Figura 8: Conjunto nebuloso construído em função da variável "Idade". ................................... 54

Figura 9: Matriz de dados........................................................................................................... 58

Figura 10: Matriz de similaridade. ............................................................................................... 59

Figura 11: Fluxograma do funcionamento do Algoritmo K-Means. .............................................. 65

Figura 12: Passos subseqüentes do Algoritmo K-Means. ........................................................... 66

Figura 13: Dendograma. ............................................................................................................. 70

Figura 14: Como os Métodos Hierárquicos trabalham. ................................................................ 71

Figura 15: Representação de clusters e ruídos. .......................................................................... 73

Figura 16: Alcance por Densidade e Conectividade por Densidade. ............................................ 74

Figura 17: Aprendizado competitivo. ........................................................................................... 79

Figura 18: Mapa de Kohonen. .................................................................................................... 80

Figura 19: Tabela de registros de Clientes................................................................................. 84

Figura 20: Tabela de registros de Filmes. .................................................................................. 84

Figura 21: Tabela de registros de locações de Filmes. .............................................................. 85

Figura 22: Registros com ruídos. ............................................................................................... 86

Figura 23: Registros excluídos da base de dados. .................................................................... 86

Figura 24: Base de dados codificada. ........................................................................................ 88

Figura 25: Atributo DATAMOV inconsistente. ............................................................................ 91

Figura 26: Base de dados com atributo BAIRRO com “__” e SEXO preenchido. ...................... 92

Figura 27: Arquivo no formato “CSV” antes das alterações. ...................................................... 95

Figura 28: Arquivo no formato “ARFF” após as alterações. ....................................................... 96

Figura 29: Janela exibindo um erro carregando o arquivo LOCACAO.ARFF. ........................... 96

Figura 30: Carregando o arquivo LOCACAO.ARFF. .................................................................. 97

Figura 31: Escolhendo o número de clusters e o número de sementes. .................................. 99

Figura 32: Exemplo de como o software WEKA representa o Modelo de Conhecimento. ....... 100

Figura 33: Os 15 Filmes mais alugados com base nos testes realizados no Weka. ................ 116

Figura 34: Alguns Filmes menos alugados com base nos testes realizados no Weka. ........... 117

Figura 35: Gêneros de filmes apresentado pelo WEKA. .......................................................... 117

Figura 36: Gêneros de filmes mais alugados, apresentado pelo WEKA. ................................. 120

Figura 37: Gêneros de filmes menos alugados, apresentado pelo WEKA. .............................. 120

Figura 38: Filmes alugados por bairro. ..................................................................................... 121

Figura 39: Filmes mais alugados por Sexo. ............................................................................. 121

Figura 40: Bairros que alugam filmes. ...................................................................................... 122

Figura 41: Separabilidade dos clientes pelo atributo Sexo. ..................................................... 124

Figura 42: Separabilidade dos clientes pelo atributo Bairro. .................................................... 124

8

LISTAS DE TABELAS Tabela 1: Resumo das tarefas de KDD........................................................................................ 55

Tabela 2: Ferramentas de KDD. .................................................................................................. 56

Tabela 3: A tabelas escolhidas e seus atributos. ....................................................................... 85

Tabela 4: Novos atributos após aplicar a função “ Construção de Atributos” . ........................ 89

Tabela 5: Atributos rejeitados por inconsistência do atributo DATAMOV. ................................. 91

Tabela 6: Tabela LOCACAO.DBF normalizada. ........................................................................ 92

Tabela 7: Testes realizados com N Clusters e N Seeds. ......................................................... 101

Tabela 8: Resultado do teste T1 apresentado pelo WEKA. ..................................................... 102

Tabela 9: Resultado do teste T2 apresentado pelo WEKA. ..................................................... 102

Tabela 10: Resultado do teste T3 apresentado pelo WEKA. ................................................... 103







Tabela 17: Resultado do teste T10 apresentado pelo WEKA. ................................................. 110





Tabela 22: Colocação dos clientes que mais alugam filmes, segundo WEKA. ........................ 118

Tabela 23: Colocação dos com clientes que menos alugam filmes, segundo WEKA. ............. 119

Tabela 24: Gêneros mais assistidos por clientes que menos alugam filmes. .......................... 123

9

SUMÁRIO

INTRODUÇÃO .................................................................................................................................... 10

1. UMA VISÃO GERAL SOBRE MINERAÇÃO DE DADOS .......................................................... 22

1.1 APRESENTAÇÃO .................................................................................................................... 22 1.2 O PROCESSO DE KDD ........................................................................................................... 25

1.2.1 O problema em que será aplicado o processo de KDD ......................................................... 25 1.2.2 Os Recursos Disponíveis ................................................................................................... 26 1.2.3 Os Resultados Obtidos ....................................................................................................... 28

1.3 ETAPAS DO PROCESSO KDD ................................................................................................. 29 1.3.1 Etapa de Pré-processamento ............................................................................................ 29 1.3.2 Etapa de Mineração de Dados .......................................................................................... 34

1.3.2.1 Medida de Interesse ................................................................................................................. 35 1.3.2.2 Similaridade ............................................................................................................................... 36 1.3.2.3 Aprendizado ............................................................................................................................... 38

1.3.3 Etapa de Pós-processamento ............................................................................................ 39 1.4 APRENDIZADO DE MÁQUINA ................................................................................................. 41 1.5 TAREFAS DO PROCESSO DE KDD ........................................................................................... 42 1.6 MÉTODOS DE MINERAÇÃO DE DADOS ................................................................................... 47

1.6.1 Algoritmos de Redes Neurais .......................................................................................... 48 1.6.2 Algoritmos Genéticos ...................................................................................................... 50 1.6.3 Algoritmos Baseados em Instâncias ................................................................................. 50 1.6.4 Algoritmos Estatísticos .................................................................................................... 51 1.6.5 Algoritmos Específicos .................................................................................................... 52 1.6.6 Algoritmos de Árvores de Decisão .................................................................................. 52 1.6.7 Algoritmos Baseados em Lógica Nebulosa ...................................................................... 53

1.7 RESUMO DAS TAREFAS DE KDD ........................................................................................... 55 1.8 FERRAMENTAS DE KDD ....................................................................................................... 56

2 CLUSTERIZAÇÃO (CLUSTERING).............................................................................................. 57

2.1 APRESENTAÇÃO .................................................................................................................... 57 2.1.1 Estrutura de Dados .......................................................................................................... 58 2.1.2 Requisitos para os Algoritmos de Clusterização ............................................................... 60

2.2 MÉTODOS DE CLUSTERIZAÇÃO ............................................................................................. 62 2.2.1 Métodos por Particionamento .......................................................................................... 63 2.2.2 Métodos Hierárquicos...................................................................................................... 70 2.2.3 Métodos Baseados em Densidade .................................................................................... 72 2.2.4 Métodos Baseados em Grades ......................................................................................... 74 2.2.5 Métodos Baseados em Modelos ....................................................................................... 76

2.2.5.1 Abordagem Estatística ................................................................................................................. 77 2.2.5.2 Abordagem por Rede Neural ...................................................................................................... 78

3 APLICAÇÃO DO PROCESSO DE KDD......................................................................................... 81

3.1 APRESENTAÇÃO .................................................................................................................... 81 3.2 PROGRAMAS UTILIZADOS ...................................................................................................... 81 3.3 APLICAÇÃO DAS ETAPAS DO KDD ........................................................................................ 82

3.3.1 Etapa de Pré-Processamento ............................................................................................ 83 3.3.1.1 Hipóteses .................................................................................................................................... 89

3.3.2 Etapa de Mineração de Dados .......................................................................................... 93 3.3.2.1 Testes realizados sobre a Base de Dados ........................................................................ 101

3.3.3 Etapa de Pós-processamento .......................................................................................... 116 3.3.3.1 Respondendo as Hipóteses e Explicando os Resultados .............................................. 116

CONSIDERAÇÕES FINAIS ........................................................................................................... 125 REFERÊNCIAS BIBLIOGRÁFICAS E BIBLIOGRAFIAS ............................................................ 130

10

INTRODUÇÃO

A visão é a mais sofisticada modalidade sensorial do ser humano.

Porém, quando se trata de grandes quantidades de dados armazenados, à

espera de especialistas em descobrir informações interessantes e úteis, é

humanamente impossível visualizar essas informações, uma vez que elas

podem estar implícitas e desagrupadas dentro dos bancos de dados. Por isso,

métodos e técnicas de análise precisam ser aplicados sobre esses dados para

que relações novas e úteis possam ser descobertas, ou seja, os dados devem

ser “Minerados” (Data Mining).

A Mineração de Dados consiste na busca pela descoberta

conhecimento em bases de dados, também chamado de KDD - (Knowledge

Discovery in Databases), um processo dividido em etapas como Pré-

processamento, Mineração de Dados e Pós-processamento.

A Mineração de Dados permite, por exemplo, adquirir conhecimentos

úteis, descobrir relações entre produtos, classificar consumidores, prever

vendas, localizar áreas geográficas com perfis específicos, perceber

necessidades de consumidores ou de uma região, entre outras.

Também pode ser definida como o uso de técnicas automáticas de

exploração de grandes quantidades de dados, para descobrir novos padrões e

relações, que devido ao volume de dados, não seriam facilmente descobertos a

olho nu pelo ser humano. Pode ser aplicado a qualquer massa de dados, sejam

eles de medicina, economia, astronomia, geologia, entre outras.

11

MOTIVAÇÃO

Diante de incalculáveis quantidades de dados disponíveis e esses dados aumentando a cada momento, é extremamente atraente o uso da tecnologia Data Mining para exploração de dados por vários motivos:

1. O volume de dados é enorme: Data Mining só se aplica às grandes

massas de dados. Empresas de telefonia, cartões de credito, bancos, televisão

por assinatura, comércio eletrônico, entre outras, geram grandes quantidade de

dados sobre seus clientes e serviços. Esses dados são passíveis de análise

por mineração;

2. Os dados estão sendo organizados: Com a tecnologia Data

Warehouse, os dados estão sendo organizados e padronizados para a tomada

de decisão através de ferramentas de análises. Data Mining necessita de

banco de dados “limpos”, padronizados e organizados;

3. Disponibilidade de Recursos Computacionais: Data Mining necessita

de muitos recursos computacionais para operar seus algoritmos sobre grandes

bases de dados e a queda dos preços dos computadores possibilita o uso de

Data Mining hoje;

4. Bancos de Dados Distribuídos: A construção de bancos de dados

distribuídos e avanços nesta área também contribuem para a mineração de

dados;

5. As empresas exigem técnicas mais modernas de decisão:

Inicialmente empresas das áreas de finanças, telecomunicações e seguros

sentiram essa necessidade e hoje outras empresas também buscam adquirir

dados para analisar melhor seus caminhos futuros por meios de sistemas de

apoio à decisão; e

12

6. A Informação é o Produto: Para empresas de serviços, é importante

saber o que oferecer e a quem. Para outras empresas, até a venda das

informações pode ser um produto.

Em particular, dentro do escopo de Data Mining, perceber

“Agrupamentos” pode ser importante para organizações, pois podem

demonstrar comportamentos de suas atividades tais como vendas, compras,

gerências de decisões, locações, entre outras.

O estágio de desenvolvimento da tecnologia atual tornou

relativamente fácil o acúmulo de dados nas empresas, cuja a conseqüência é a

ampliação dos Bancos de Dados. Ao mesmo tempo a informação passa a ser

valorizada como nunca antes na história e os dados armazenados podem ser

vasculhados por profissionais especializados à procura de tendências e

padrões. Entretanto, a análise desses dados ainda é demorada, dispendiosa,

pouco automatizada, e sujeita a erros, mal-entendidos e falta de atenção, ou

seja, informações passam despercebidas a olho nu, pois geralmente estão

implícitas (CARVALHO, 2001).

Na tentativa de minimizar essas carências é que o problema de

pesquisa se apresenta:

PROBLEMA DE PESQUISA

Quais técnicas de Data Mining devem ser utilizadas para descobrir

novos conhecimentos (Knowledge Discovery in Databases - KDD), sob o

prisma de “Agrupamento” (Clustering), no domínio de aplicação de uma

Locadora de Vídeo?

13

MINERAÇÃO DE DADOS EM UMA LOCADORA DE VÍDEO

A Mineração de Dados em uma Locadora de Vídeo pode oferecer

subsídios para sua melhor gestão, tais como novas relações, classes, padrões,

grupos de usuários com características comuns e grupos com perfis

heterogêneos (exceções). Para isso, serão aplicadas todas as etapas do KDD

numa base de dados de uma locadora, a qual será minerada pelo algoritmo de

Clusterização SimpleK-Means, por se tratar de um algoritmo clássico de

Mineração de Dados e por estar implementado em um software gratuito WEKA,

permitindo usar esse algoritmo e explorar todas as suas características sem a

necessidade de implementação.

OBJETIVO

Estudar as técnicas de Mineração de Dados, ou seja, os métodos,

as tarefas e os algoritmos, escolher um algoritmo, aplicá-los sobre uma base

de dados e mostrar os resultados, permitindo a realização de análise para que

se possa interpretá-los, oferecendo apoio nas tomadas de decisões, sob o

prisma da tarefa de “Agrupamento” (Clustering).

JUSTIFICATIVA

Mineração de Dados tornou-se uma necessidade, já que permite

transformar grandes quantidades de dados em conhecimentos úteis que

podem ser utilizados como auxílio nas tomadas de decisões, permitindo

avanços sem paralelo na história do desenvolvimento dos bancos de dados.

14

Algumas áreas com interesse na utilização de mineração de dados:

- Marketing: Técnicas de Mineração de Dados são aplicadas para

descobrir preferências do consumidor e padrões de compra ou locação, com o

objetivo de realizar marketing direto de produtos e ofertas promocionais, de

acordo com o perfil do consumidor.

- Detecção de fraudes: Muitas fraudes óbvias (tais como, a

compensação de cheque por pessoas falecidas) podem ser encontradas sem

Mineração de Dados, mas padrões mais sutis de fraude podem ser difíceis de

ser detectados, por exemplo, o desenvolvimento de modelos que predizem

quem será um bom cliente ou aquele que poderá se tornar inadimplente em

seus pagamentos.

- Medicina: Caracterizar comportamento de paciente para prever

visitas, identificar terapias médicas de sucesso para diferentes doenças, buscar

por padrões de novas doenças.

- Instituições governamentais: Descoberta de padrões para

melhorar as coletas de taxas ou descobrir fraudes.

- Ciência: Técnicas de Mineração de Dados podem ajudar cientistas

em suas pesquisas, por exemplo, encontrar padrões em estruturas

moleculares, dados genéticos, mudanças globais de clima, oferecendo

conclusões valiosas rapidamente.

15

DELIMITAÇÃO DO PROBLEMA

Os bancos de dados atuais são muito grandes (muitos registros) e,

na maioria das vezes, dispersos (divididos em tabelas). A busca por

conhecimento que possa oferecer apoio às tomadas de decisões em

empresas, instituições e organizações tem se tornado de vital importância para

a sua existência. Dentro desse contexto, surgiu nos anos 90, um ramo da

Ciência da Computação que tinha esse tipo de preocupação: Descobri

Conhecimento em Bases de Dados (Knowledge Discovery in Databases- KDD).

A Mineração de Dados (Data Mining) pode ser considerada como

uma parte do KDD, onde é geralmente usado para representar o processo de

tornar dados de baixo nível em conhecimento de alto nível por meio da

extração de padrões ou modelos de dados observados, exploração e a análise,

por meio automático ou semi-automático (BERRY; LINOFF, 2004).

Segundo Berry e Linoff (2004), os principais objetivos da Mineração

de Dados são de descobrir relacionamentos entre 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 de Dados podem ser usados

no gerenciamento de informação, processamento de pedidos de informação,

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

Uma das tarefas possíveis de emprego de Data Mining é o

Agrupamento, que consiste na partição de uma “população heterogênea” de

dados em vários subgrupos, ou grupos (clusters), mais homogêneos. Alguns

possíveis exemplos são agrupar clientes por regiões do país, agrupar clientes

com preferências por determinados gêneros de filmes, agrupar clientes com

16

comportamento de compra similar, agrupar seções de usuários para prever

comportamentos futuros.

Por fim, interessa o estudo de técnicas de Agrupamento em

aplicações das mais diversas, tais como a utilizada por esta pesquisa – um

Banco de Dados de uma Vídeo Locadora.

Em específico, na aplicação realizada nesse estudo, pretende-se

encontrar novas relações, classes, padrões, grupos de usuários com

características comuns e grupos com perfis heterogêneos (exceções).

REFERENCIAL TEÓRICO

Segundo Pedrycz (2005), padrões e dados são partes integradas na

cultura de nossa sociedade de informação. O desafio que nós estamos

enfrentando todos os dias é manipular o fluxo de dados gerados pelas

transações bancárias, pelos milhões de sensores, os registros de log da WWW

(World Wide Web), o tráfego de comunicações das chamadas de celulares,

coleções de sistemas de imagens de satélites, para mencionar apenas alguns

exemplos evidentes.

De acordo com Carvalho (2001) e Fayyad (1996), Descoberta de

Conhecimento em Bases de Dados (Knowledge Discovery in Databases -

KDD) é um processo que envolve a automação da identificação e do

reconhecimento de padrões em um banco de dados. Sua principal

característica é a extração não-trivial de informações a partir de uma base de

dados de grande porte. Essas informações são necessariamente implícitas,

previamente desconhecidas e potencialmente úteis.

17

O processo de KDD é um conjunto de atividades contínuas que

compartilham o conhecimento descoberto a partir de bases de dados. Esse

conjunto é composto de etapas, que são: Pré-processamento, Mineração de

Dados (Data Mining) e Pós-processamento (FAYYAD, 1996).

Para Goldschmidt e Passos (2005), dentro das etapas do KDD, Data

Mining se destaca oferecendo as técnicas para extração de algum tipo de

conhecimento para posterior análise e interpretação. As técnicas de Data

Mining são utilizadas para delinear o perfil dos clientes e estreitar a relação

com consumidores. A tecnologia de Data Mining faz uso de algoritmos

matemáticos e estatísticos para pesquisar padrões em grandes volumes de

dados que se relacionem com questões comerciais. Companhias se voltam a

essa tecnologia para identificar novos clientes, diminuir os custos e descobrir

novas hipóteses. Várias tarefas podem ser consideradas na etapa de Data

Mining, tais como Descrição, Associação, Classificação, Previsão, grupamento,

Análise de série temporal. No entanto, interessa neste estudo a tarefa de

Agrupamento (Clustering).

Segundo Carlantonio (2001), para a tarefa de Agrupamento, também

denominada Classificação Não-Supervisionada, existem diversos métodos ou

algoritmos que foram ou estão sendo desenvolvidos, tais como alguns

exemplos a seguir:

18

– K-MEANS;

– K-MODES

– K-MEDOIDS;

– SIMPLEK-MEANS

– FUZZY C-MÉDIAS;

– FUZZY K-MEANS;

– CLARANS;

– PAM;

– CURE;

– EM;

– BIRCH;

– ROCK;

– STING;

– CLICK;

– K-PROTOTYPES;

– OPTIC;

– WAVECLUSTER;

– ISODATA;

– COBWEB;

– KOHONEN.

METODOLOGIA

Este trabalho iniciou-se com pesquisas sobre o termo Mineração de

Dados, chegando à conclusão de que o mesmo é uma etapa do processo de

KDD, que por sua vez subentende-se “Descoberta de Conhecimento em Bases

de Dados (Knowledge Discovery in Data Bases – KDD)” e que é preciso passar

por todas as fases deste processo para se chegar ao resultado desejado, o

conhecimento.

Dentro do processo de KDD, conhecer as etapas Pré-

processamento, Mineração de Dados e Pós-processamento foi de fundamental

importância para o desenvolvimento deste trabalho.

Como o objetivo deste trabalho é conhecer e aplicar técnicas e

algoritmos de Clusterização sobre uma base de dados e mostrar os resultados,

foi preciso estudar o processo de KDD e suas aplicações, estudar os

19

algoritmos de agrupamentos, seus pontos fortes e fracos, suas características

e suas diferenças para poder escolher um e aplicá-lo no processo de KDD.

Após ter definido qual algoritmo seria utilizado, o próximo passo foi

obter a base de dados a ser aplicado no processo de KDD. Uma base de

dados de uma locadora de vídeo foi conseguida para ser utilizada neste

trabalho.

Com a base de dados, aplicou-se a etapa de Pré-processamento no

sentido de modelar os dados para sua posterior aplicação na etapa de

Mineração de Dados. Utilizou-se para isso os softwares DBF View, Microsoft

Excel e o Bloco de Notas.

Na etapa de Mineração de Dados, aplicou-se o algoritmo escolhido

sobre a base de dados para descobrir conhecimentos, novos padrões ou

relações interessantes e úteis. Utilizou-se para isso a linguagem de

programação JAVA através do Software WEKA.

Aplicou-se o conhecimento em JAVA, após o estudo dessa

linguagem de programação, a qual foi muito importante como base para

entender o funcionamento dos algoritmos e do software WEKA feito em JAVA,

usado na Mineração de Dados e, portanto, precisa dessa linguagem instalada

para funcionar.

Aplicou-se o software WEKA, após seu estudo, conhecendo sua

interface, os tipos de arquivos e seus formatos aceitáveis, seus algoritmos de

Clusterização, seus parâmetros de entradas, seus pré-requisitos e suas

respostas em forma de Mineração de Dados, permitindo chegar ao objetivo

desta pesquisa.

20

Por último, na etapa de Pós-processamento, após a aplicação do

algoritmo selecionado sobre o banco de dados de uma Vídeo Locadora,

analisou-se os resultados, bem como fez-se uma apresentação de forma que o

especialista no Domínio da Aplicação pudesse ver, ler e interpretar os

resultados obtidos. Utilizou-se, para isso, o software Microsoft Excel para gerar

gráficos.

SÍNTESE DOS CAPÍTULOS

Capítulo 1:

UMA VISÃO GERAL SOBRE MINERAÇÃO DE DADOS

Neste capítulo é apresentado uma visão panorâmica do termo “Data

Mining” ou Mineração de Dados como é mais conhecido, mostrando, no

entanto, que este termo é na realidade uma etapa de um processo muito maior

que é o KDD (Knowledge Discovery in Databases), ou seja, o processo de

“Descoberta de Conhecimento em Bases de Dados“. Neste capítulo também

são mostrados detalhes de cada parte do processo KDD, dando uma visão

bem clara dos conceitos e onde pode ser utilizado no mercado, tendo como

referência os seguintes autores: Carvalho (2001); Goldschmidt e Passos (2005);

Resende (2003); Fayyad et al. (1996) e Elmasri e Navathe (2000); Pedrycz

(2005), Carlantonio (2001); Braga, Carvalho e Ludermir (2000).

21

Capítulo 2:

CLUSTERIZAÇÃO (CLUSTERING)

Neste capítulo é apresentada a tarefa de Agrupamento (Clustering),

as técnicas mais conhecidas e usadas e principalmente, vários algoritmos

voltados para esta tarefa, com o objetivo de escolher um para aplicar na etapa

de Mineração de Dados, tendo como referência os seguintes autores: Fayyad

et al. (1996); Carlantonio (2001); Goldschmidt e Passos (2005); Braga, Carvalho

e Ludermir (2000).

Capítulo 3:

APLICAÇÃO DO PROCESSO DE KDD

Neste capítulo são expostos o modo teórico e prático de como

preparar a base de dados, passando pela etapa de Pré-processamento,

aplicando suas funções até chegar ao arquivo ideal para ser, então, usado na

etapa de Mineração de Dados, onde também são descritos os passos para

carregar o arquivo em formato “.ARFF” no software WEKA, escolher a tarefa de

Cluster, configurar os parâmetros necessários, iniciar a Mineração de Dados,

colher os resultados e finalmente aplicá-los à etapa de Pós-processamento,

gerando explicações e gráficos sobre o conhecimento encontrado, tendo como

referência os seguintes autores: Carlantonio (2001); Fayyad et al. (1996);

Goldschmidt e Passos (2005); Souto (2005); Witten e Frank (2000).

22

1. UMA VISÃO GERAL SOBRE MINERAÇÃO DE DADOS

1.1 Apresentação

Segundo Elmasri e Navathe (2000), Mineração de Dados (Data

Mining) é o uso de métodos e técnicas automáticas de exploração de grandes

Bancos de Dados, para descobrir novos padrões, tendências e relações que

possam significar conhecimentos, que devido a grande quantidade de dados,

não seriam facilmente vistos a olho nu pelo ser humano. Portanto, a Mineração

de Dados consiste em extrair informações de grandes bases de dados de

empresas, organizações e instituições, permitindo a realização de análises que

possam oferecer apoios nas tomadas de decisões.

Para Carvalho (2001); Goldschmidt e Passos (2005); Resende (2003)

e FAYYAD et al. (1996), os constantes avanços na área da Tecnologia da

Informação têm permitido o armazenamento de grandes e múltiplas bases de

dados. Tecnologias como a Internet, sistemas gerenciadores de banco de

dados, leitores de códigos de barras, dispositivos de memória secundária de

maior capacidade de armazenamento, de menor custo como HDs e sistemas

de informação em geral são alguns exemplos de recursos que têm viabilizado a

proliferação e o aumento gigantesco de inúmeras bases de dados de natureza

comercial, administrativa, governamental e científica.

23

Atualmente, dados científicos em projetos de pesquisa, tais como

missões espaciais da NASA e o Projeto do Genoma Humano, têm alcançado

proporções gigantescas. Empresas como FedEx, Wal-Mart, UPS, Banco do

Brasil, Caixa Econômica Federal, Sendas e outros possuem bases de dados

da ordem de centenas de Terabytes de informações (GOLDSCHMIDT e

PASSOS, 2005).

A cada dia dados estão sendo gerados. Quando se realiza uma

compra por telefone, por exemplo, o número telefônico, a duração da chamada,

o número do cartão de crédito, o endereço da entrega, o produto escolhido e

outros dados, como nível sociocultural, preferências e hobbies, podem ser

facilmente armazenados em bancos de dados.

A filosofia empresarial dirigida ao cliente considera cada item de

informação sobre o cliente, cada interação em pontos de venda, cada chamada

ao serviço de atendimento ao cliente e cada visita a uma página da world wide

web (www), como uma oportunidade de obter dados sobre o cliente. Certamente

que obter dados não significa aprender sobre o cliente!

De fato, muitas empresas armazenam Gigabytes de dados ocupando

espaço e sem aprender nada acerca dos seus clientes e produtos. Nestes

casos, os dados são armazenados para fins operacionais, como controle de

estoque e cobrança, e após seu uso são simplesmente descartados sem a

consideração de que podem representar uma fonte de informação valiosa para a

empresa (CARVALHO, 2001).

24

Diante desse cenário, naturalmente surgem algumas questões

como: "O que fazer com todos os dados armazenados?", "Como utilizar o

patrimônio digital em benefício das instituições?", "Como analisar e utilizar de

maneira útil todo o volume de dados disponível?", entre outras. A análise de

grandes quantidades de dados pelo homem não é trivial sem o auxílio de

ferramentas computacionais apropriadas. Portanto, torna-se imprescindível o

desenvolvimento de ferramentas que auxiliem o homem, de forma automática e

inteligente, na tarefa de analisar, interpretar e relacionar esses dados para que

se possa desenvolver estratégias de tomadas de decisões (FAYYAD et al.,

1996).

É necessário conseguir transformar grandes quantidades de dados

em conhecimentos úteis, conforme mostra a figura 1.

Figura 1: Grandes quantidades de dados transformadas em conhecimentos.

GOLDSCHMIDT e PASSOS (2005)

É neste contexto que surge uma nova área denominada Descoberta

de Conhecimento em Bases de Dados (Knowledge Discovery in Databases -

KDD), mais popularmente conhecida como “Mineração de Dados ou Data Mining”,

a qual é, na realidade, uma das etapas do processo de KDD (GOLDSCHMIDT e

PASSOS, 2005).

25

1.2 O processo de KDD

Numa visão geral, o processo de KDD é a busca pela descoberta de

conhecimento em base de dados. Basicamente, um processo de KDD é composto

por três de componentes:

O Problema em que será aplicado o processo de KDD;

Os recursos disponíveis para a solução do problema ; e

Os resultados obtidos a partir da aplicação dos recursos disponíveis

em busca da solução do problema (GOLDSCHMIDT e PASSOS, 2005).

A seguir estão detalhamentos e comentários sobre cada um dos

componentes.

1.2.1 O problema em que será aplicado o processo de KDD

Segundo Elmasri e Navathe (2000), o problema em que será

aplicado o processo de KDD pode ser caracterizado por três elementos:

a) O conjunto de dados;

b) O especialista do Domínio da Aplicação; e

c) Os objetivos da aplicação.

a) Todo conjunto de dados pode ser observado sob os aspectos intencional

e extensional. O aspecto intencional se refere à estrutura ou ao esquema do

conjunto de dados. Neste contexto encontram-se os atributos (campos) do

conjunto de dados. Os registros compõem o aspecto extensional do conjunto

de dados, ou seja, seu tamanho. Mesmo não sendo obrigatório, o processo de

KDD pressupõe que os dados sejam organizados em uma única estrutura

26

tabular bidimensional chamado “Data Warehouse” (Banco de Dados

Multidimensional), contendo casos e atributos do problema a ser analisado.

b) O especialista no Domínio da Aplicação representa a pessoa ou o grupo de

pessoas que conhece o assunto em que deverá ser realizada a aplicação de KDD.

Em geral, pertencem a esta classe analistas de negócios interessados em

identificar novos conhecimentos que possam ser utilizados em sua área de

atuação. Costumam deter o chamado conhecimento prévio sobre o problema

(background knowledge). As informações prestadas pelas pessoas deste grupo

são de fundamental importância no processo de KDD, pois influenciam desde a

definição dos objetivos do processo até a avaliação dos resultados

(GOLDSCHMIDT e PASSOS, 2005).

c) Para Engels (1996); Engels et al. (1997); Wirth et al. (1997); Verdenius e

Engels (1997) apud Goldschmidt e Passos (2005), os objetivos da aplicação

compreendem os resultados a serem produzidos ao final do processo, chamados,

a partir de agora, de “Modelo de Conhecimento”. Tais objetivos diminuem

restrições e expectativas dos especialistas no domínio da aplicação acerca do

modelo de conhecimento a ser gerado.

1.2.2 Os Recursos Disponíveis

Os Recursos Disponíveis para solução do problema podem ser

(GOLDSCHMIDT e PASSOS, 2005):

a) O especialista em KDD;

b) As ferramentas de KDD; e

27

c) A plataforma computacional disponível (Hardware e Software).

a) O especialista em KDD representa a pessoa ou o grupo de pessoas que

possui experiência na execução de processos de KDD. Ele Interage com o

especialista no Domínio da Aplicação e direciona a condução do processo de KDD,

definindo o que, como e quando deve ser realizada cada ação do processo. Suas

atribuições variam desde a identificação e a utilização do conhecimento prévio

existente sobre o problema até o direcionamento das ações do processo, que

englobam a seleção e a aplicação das ferramentas disponíveis, além da avaliação

dos resultados obtidos (GOLDSCHMIDT e PASSOS, 2005).

b) A expressão ferramenta de KDD está sendo empregada para designar

qualquer recurso computacional que possa ser utilizado no processo de análise de

dados. Pode ser desde um ambiente de software que integre diversas

funcionalidades de tratamento e análise de dados até algoritmos isolados que

possam ser adaptados ao processo de KDD (GOLDSCHMIDT e PASSOS,

2005).

c) A plataforma computacional, conforme o próprio nome sugere, indica os

recursos computacionais de hardware (processadores e memória) disponíveis

para a execução da aplicação de KDD. São os equipamentos disponibilizados

para o processo. Podem ser desde máquinas isoladas até mesmo ambientes

computacionais paralelos. Quanto maior a capacidade de processamento e

memória da plataforma computacional, maior a agilidade em obter resultados,

proporcionando uma maior dinâmica ao processo de KDD (FAYYAD et al.,

28

1996).

1.2.3 Os Resultados Obtidos

Segundo Fayyad et al. (1996), os resultados obtidos a partir da

aplicação dos recursos no problema compreendem, fundamentalmente:

a) Os modelos de conhecimento descobertos ao longo da aplicação de KDD;

b) O histórico das ações realizadas.

a) Fayyad et al. (1996) explicam que a expressão “modelo de conhecimento”

indica qualquer abstração de conhecimento, expresso em alguma linguagem, que

descreva algum conjunto de dados. Todo modelo de conhecimento deve ser

avaliado com relação ao cumprimento das expectativas definidas nos objetivos da

aplicação. É muito comum que, durante o processo de KDD, sejam realizadas

comparações entre os modelos de conhecimento obtidos. Por exemplo. se no caso

dos empréstimos da financeira fossem obtidos diversos modelos e todas as

características desses modelos fossem iguais, menos a acurácia (precisão).

Considerando ainda, que todos os modelos tenham acurácia superior à mínima

desejada. O modelo de conhecimento com maior precisão na classificação dos

clientes possui maiores chances de ser eleito como principal resultado (produto

final) gerado pelo processo de KDD.

b) Os históricos sobre como os modelos de conhecimento foram gerados

também se enquadram como resultados do processo de KDD. São de fundamental

importância no controle do processo, pois permitem uma análise crítica e uma

revisão das ações realizadas.

29

1.3 Etapas do Processo KDD

A Descoberta de Conhecimento em Bases de Dados é caracterizada

como um processo composto por três etapas operacionais básicas

(GOLDSCHMIDT e PASSOS, 2005):

Pré-processamento;

Mineração de Dados; e

Pós-processamento.

Figura 2: Etapas do processo de KDD.


1.3.1 Etapa de Pré-processamento

Segundo Goldschmidt e Passos (2005), a etapa de Pré-processamento

compreende todas as funções relacionadas à captação, à organização e ao

tratamento dos dados. Essa etapa tem como objetivo a preparação dos dados para

os algoritmos da etapa da Mineração de Dados.

Dados Conhecimento

30

As principais funções do Pré-processamento dos dados são:

a) Seleção de Dados;

b) Limpeza dos Dados;

c) Codificação dos Dados;

d) Enriquecimento dos Dados;

e) Normalização de Dados; e

f) Construção de Atributos.

a) Seleção de Dados

Para Goldschmidt e Passos (2005), essa função compreende, em

essência, a identificação de quais informações, dentre as bases de dados

existentes, devem ser efetivamente consideradas durante o processo de KDD. A

seleção dos dados pode ter dois enfoques distintos: a escolha de atributos ou a es-

colha de registros que devem ser considerados no processo de KDD. Em geral, os

dados encontram-se organizados em bases de dados transacionais que sofrem

constantes atualizações ao longo do tempo. Assim sendo, recomenda-se que seja

sempre feita uma cópia dos dados a fim de que o processo de KDD não interfira

nas rotinas operacionais relacionadas à base de dados.

Nos casos em que já exista uma estrutura de Data Warehouse, deve-se

verificar a possibilidade de que esta seja utilizada no processo de KDD. Nos

demais casos, é comum a congregação dos dados em uma única tabela, pois a

31

maioria dos algoritmos de Mineração de Dados assim exige. O processo de KDD

pode ocorrer independente da disponibilidade ou não de um Data Warehouse.

A junção dos dados em uma única tabela pode ocorrer de duas

formas:

I) Junção Direta

Todos os atributos (campos) e registros da base de dados transacional

são incluídos na nova tabela, sem uma análise crítica quanto a que variáveis e que

casos podem realmente contribuir para o processo de KDD.

II) Junção Orientada

O especialista no Domínio da Aplicação, em parceria com o especialista

em KDD, escolhe os atributos e os registros com algum potencial para influenciar

no processo de KDD. Recomenda-se que sejam desconsiderados somente

atributos e registros sobre os quais se tenha uma visão clara quanto à existência

de potencial de contribuição para o processo de KDD.

b) Limpeza dos Dados

Abrange qualquer tratamento realizado sobre os dados selecionados de

forma a assegurar a qualidade (completude, veracidade e integridade) dos fatos

por eles representados. Informações ausentes, errôneas ou inconsistentes nas

bases de dados devem ser corrigidas de forma a não comprometer a qualidade

dos resultados (modelos de conhecimento) a serem extraídos do processo de

KDD.

A execução dessa fase tem como objetivo, corrigir a base de dados,

eliminando consultas desnecessárias que poderiam ser executadas futuramente

pelos algoritmos de Mineração de Dados, afetando o seu desempenho.

32

A melhor maneira de evitar a poluição dos dados é organizando a

entrada dos dados. Rotinas de crítica nas interfaces de entrada de dados dos

sistemas de informação são de grande valor para evitar a poluição dos dados. No

entanto, nem sempre tais rotinas estão disponíveis. Assim sendo, a participação

dos especialistas em KDD e dos especialistas na área da aplicação é essencial

nesta operação (GOLDSCHMIDT e PASSOS, 2005).

c) Codificação dos Dados

Nessa função, os dados devem ser codificados para ficarem numa

forma que possam ser usados como entrada dos algoritmos de Mineração de

Dados. É importante compreender que os dados devem ser codificados de forma a

atender às necessidades específicas dos algoritmos de Mineração de Dados. Por

exemplo, uma rede neural requer que os dados estejam em uma representação

numérica. Assim sendo, caso a base de dados a ser processada apresente valores

nominais (texto), estes devem ser codificados antes de serem submetidos à rede,

pois a maneira como a informação é codificada tem forte influência sobre o tipo de

conhecimento a ser encontrado (GOLDSCHMIDT e PASSOS, 2005).

Segundo eles, a codificação pode ser:

I) Numérica - Categórica que transforma valores reais em categorias

ou intervalos;

II) Categórica - Numérica que representa numericamente valores de

atributos categóricos.

33

d) Enriquecimento dos Dados

A fase de enriquecimento consiste em conseguir de alguma forma mais

informação que possa ser agregada aos registros existentes, enriquecendo os

dados, para que estes forneçam mais informações para o processo de descoberta

de conhecimento (GOLDSCHMIDT e PASSOS, 2005).

e) Normalização de Dados

Para Goldschmidt e Passos (2005), essa operação consiste em ajustar

a escala dos valores de cada atributo de forma que os valores fiquem em

pequenos intervalos, tais como -1 a 1, ou de 0 a 1. Tal ajuste faz-se necessário

para evitar que alguns atributos, por apresentarem uma escala de valores maior

que outras, influenciem de forma tendenciosa em determinados métodos de

Mineração de Dados.

f) Construção de Atributos

Essa operação consiste em gerar novos atributos a partir de atributos

existentes. Os novos atributos são denominados atributos derivados. Como

exemplo, é citado a criação de um atributo "Idade" a partir do atributo "DT_NC"

(data de nascimento) e da data corrente do sistema (SYSDATE).

A importância desse tipo de operação é justificada pois novos

atributos, além de expressarem relacionamentos conhecidos entre atributos

existentes, podem reduzir o conjunto de dados, simplificando o processamento

dos algoritmos de Mineração de Dados (GOLDSCHMIDT e PASSOS 2005).

34

1.3.2 Etapa de Mineração de Dados

Segundo Elmasri e Navathe (2000), a Mineração de Dados, também

conhecida como “Data Mining”, consiste em descobrir relações entre produtos,

classificar consumidores, prever vendas, localizar áreas geográficas com perfis

específicos, perceber necessidades, entre outras.

Para Goldschmidt e Passos (2005), na Mineração de Dados, são

definidos as técnicas e os algoritmos a serem utilizados na base de dados (no

problema em questão). Redes Neurais Artificiais, algoritmos Genéticos, Modelos

Estatísticos e Probabilísticos são exemplos de técnicas que podem ser utilizadas

na etapa de Mineração de Dados. A escolha da técnica depende, muitas vezes,

do tipo de tarefa de KDD a ser realizada. A etapa de Mineração de Dados é a

principal etapa do processo de KDD. Envolve a aplicação de algoritmos sobre os

dados em busca de conhecimentos implícitos e úteis, denominado “Modelo de

conhecimento”.

Goldschmidt e Passos (2005), explicam que todo conjunto de dados no

processo de KDD corresponde a uma base de fatos ocorridos que devem ser

interpretados como um conjunto de pontos em um hiper-espaço de K dimensões.

A dimensão da base de fatos é determinada pelo número de atributos do conjunto

de dados em análise. A figura 3 mostra o exemplo no contexto da análise de

crédito nas quais três informações estão representadas em um plano cartesiano.

Os eixos correspondem aos atributos Renda e Despesa. Cada ponto representa

um caso. O símbolo associado a cada caso ("círculo" ou "xis") fornece a terceira

informação, que corresponde ao comportamento do cliente quanto ao pagamento

do crédito concedido.

35

Neste exemplo a financeira responsável pelos dados deseja obter

um modelo de conhecimento que preveja o comportamento de futuros clientes

quanto ao pagamento de suas dívidas com uma taxa máxima tolerável de erro

de 5%. Esta intenção aliada à base de dados disponível conduz à tarefa de

classificação dos clientes. Esta classificação consiste em gerar um modelo de

conhecimento a partir do histórico de casos disponível. E a partir dos dados de

novos clientes, prever em qual classe de comportamento o novo cliente deverá

se enquadrar.

Figura 3: Análise de crédito.


1.3.2.1 Medida de Interesse

O conceito de medida de interesse é essencial ao processo de KDD

por dois motivos principais:

a) Podem ser usadas após a etapa de Mineração de Dados (etapa

de Pós-processamento) a fim de ordenar ou filtrar os padrões descobertos de

acordo com o grau de interesse associado a estes padrões;

b) Podem ser usadas para guiar ou restringir o espaço de busca da

Mineração de Dados, melhorando a eficiência da busca ao eliminar conjuntos de

padrões que não satisfaçam a condições predeterminadas.

Despesa

Renda - Negligente - Não Negligente

36

Existem basicamente dois tipos de medidas de interesse que podem

ser associadas aos modelos de conhecimento em Mineração de Dados: objetivas

e subjetivas (GOLDSCHMIDT e PASSOS, 2005).

As medidas de interesses objetivas são baseadas na estrutura dos

padrões descobertos e nas estatísticas a eles relacionados.

As medidas de interesses subjetivas são baseadas em crenças que os

especialistas no domínio da aplicação tenham com relação aos dados e aos

modelos de conhecimento gerados.

Padrões esperados podem ser considerados interessantes caso

confirmem suspeitas dos especialistas em determinados temas. A avaliação

envolvendo este tipo de medida depende, muitas vezes, da visualização e da

interpretação dos resultados obtidos, normalmente realizadas na etapa de Pós-

processamento. Algoritmos tais como “C4.5” e “Rough Seis” podem ser

utilizados. Por outro lado, algoritmos tais corno “Back-propagation” e “K-NN”

devem ser descartados diante deste tipo de expectativa (GOLDSCHMIDT e

PASSOS, 2005).

1.3.2.2 Similaridade

Segundo Pedrycz (2005), Carlantonio (2001) e Goldschmidt e

Passos (2005), um conceito muito importante e muito utilizado em Mineração

de Dados é a medida de similaridade. Uma vez que o conjunto de dados pode

ser interpretado como um conjunto de pontos em um espaço k-dimensional, o

conceito de similaridade entre dois pontos pode ser traduzido como a

distância entre estes pontos. Quanto maior a similaridade, menor a

distância entre os pontos.

37

Quanto menor o valor desta, mais semelhantes serão os objetos e

deverão estes ficar no mesmo cluster. Por outro lado, quanto maior a

distância, menos similares serão os objetos e, em conseqüência, eles

deverão estar em grupos distintos.

Cole (1998) apud Carlantonio (2001), resume que para

clusterização de objetos de acordo com sua similaridade, deve-se definir

uma medida de distância entre dois objetos. Uma pequena distância entre os

objetos deve indicar uma alta similaridade. Assim, uma medida de distância

pode ser usada para quantificar dissimilaridade.

Não há uma medida de similaridade que sirva para todos os tipos

de variáveis que podem existir numa base de dados.

Segundo Pedrycz (2005); Goldschmidt e Passos (2005), os

exemplos mais comuns de distância são:

Distância Euclideana: d(X,Y)=

Distância Mahalanobis:

Distância de Hamming (City-Block): d(X, Y) =

n

i

ii YX1

2)(

n

i

ii YX1

||

38

Distância de Minkowski: d(X, Y) =

Distância de Tchebyschev d(X, Y) =

Distância de Canberra d(X, Y) =

Distância de Angular d(X, Y) =

1.3.2.3 Aprendizado

Um outro conceito muito importante envolvido no processo de KDD,

mais especificamente na etapa da Mineração de Dados, refere-se à capacidade

que determinados algoritmos têm de aprender a partir de exemplos existentes

entre os dados, retratando o resultado deste aprendizado nos modelos de

conhecimento gerados (GOLDSCHMIDT e PASSOS, 2005).

Pn

i

P

ii YX

/1

1

||

39

Segundo Resende (2003), as principais abordagens de aprendizado

normalmente aplicadas em Mineração de Dados são:

O aprendizado supervisionado compreende a abstração de um

modelo de conhecimento a partir dos dados apresentados na forma de pares

ordenados (entrada, saída desejada). Por “entrada” entenda-se o conjunto de

valores das variáveis (registros) de entrada do algoritmo para um determinado

caso. A “saída desejada” corresponde ao valor que se espera que o algoritmo

possa produzir sempre que receber os valores especificados em entrada.

Segundo Braga, Carvalho e Ludermir (2000), no aprendizado não

supervisionado não existe a informação da saída desejada, nem um supervisor

para acompanhar o processo de aprendizagem. Os algoritmos partem dos

dados, procurando estabelecer relacionamentos entre eles e desenvolvendo

uma habilidade de formar representações internas para codificar

características do dados e criar novas classes ou grupos automaticamente.

1.3.3 Etapa de Pós-processamento

Segundo Fayyad et al. (1996), a etapa de Pós-processamento abrange

o tratamento do conhecimento obtido na Mineração de Dados e tem como

objetivo facilitar, para o homem, a interpretação e a avaliação da utilidade do

conhecimento descoberto. Em geral é nesta etapa que o especialista em KDD e o

especialista no Domínio da Aplicação avaliam os resultados obtidos e definem

novas alternativas de investigação dos dados.

A seguir algumas operações de Pós-processamento.

40

I) Simplificações de Modelo de Conhecimento

Segundo Han e Kember (2001) apud Goldschmidt e Passos (2005), a

simplificação de um modelo de conhecimento, conforme o próprio nome sugere,

consiste em remover detalhes deste modelo de conhecimento de forma a torná-

lo menos complexo, sem perda de informação relevante.

II) Transformações de Modelo de Conhecimento

Muitas vezes, de forma a facilitar a análise de modelos de

conhecimento, podem ser utilizados métodos de transformação sobre estes

modelos. A Figura 4 ilustra uma árvore de decisão e o conjunto de regras

correspondente.

Sexo

Pais

Idade

Compra M

França

25

Sim M

Inglaterra

21

Sim F

França

23

Sim F

Inglaterra

34

Sim F

França

30

Não M

Alemanha

21

Não M

Alemanha

20

Não F

Alemanha

18

Não F

França

34

Não

Figura 4: Uma árvore de decisão.

GOLDSCHMIDT e PASSOS (2005).

41

Se País=Alemanha Então Compra=Não

Se País=lnglaterra Então Compra=Sim

Se País=França e Idade < 25 Então Compra=Sim

Se País=França e Idade > 25 Então Compra=Não

III) Organização e Apresentação dos Resultados

Os modelos de conhecimento podem ser representados de diversas

formas. Árvores, regras, gráficos em duas ou três dimensões, planilhas, tabelas

e cubos de dados são muito úteis na representação de conhecimento. Em

geral, as técnicas de visualização de dados estimulam percepção e a

inteligência humana, aumentando a capacidade de entendimento e associação

de novos padrões. Oferecem, portanto, subsídios para a escolha dos passos

seguintes a serem realizados no processo de KDD (GOLDSCHMIDT e

PASSOS, 2005).

1.4 Aprendizado de Máquina

Segundo Resende (2003), Aprendizado de Máquina (Machine

Learning) é uma área da Inteligência Artificial (IA) cujo objetivo é o

desenvolvimento de técnicas computacionais capazes de adquirir

conhecimento de forma automática. Essas técnicas são transformadas em

programas de computador (Algoritmos/Sistemas) que tomam decisões

baseadas em experiências acumuladas por meio de soluções bem sucedidas

de problemas anteriores.

Existem diversos paradigmas de Aprendizado de Máquina, tais

como:

42

Simbólico

Estatístico

Baseados em Exemplos

Conexionista

Evolutivo

1.5 Tarefas do processo de KDD

Segundo Goldschmidt e Passos (2005), tarefas de KDD são técnicas

computacionais (Aprendizado de Máquina) a serem utilizadas sobre a base de

dados em busca de novos padrões, tendências, conhecimentos implícitos e úteis.

A escolha da tarefa depende, muitas vezes, do tipo de problema a ser realizado

e envolve a escolha e aplicação de algoritmos específicos para cada tarefa.

A seguir algumas tarefas de KDD mais comuns na realização de

processos de descoberta de conhecimento em bases de dados.

a) Descoberta de Associações

Para Agrawal et al. (1993) apud Goldschmidt e Passos (2005),

Descoberta de Associações, também conhecida como “Regras de Associação”,

consiste em encontrar conjuntos de itens que ocorram simultaneamente e de

forma freqüente em um banco de dados, por exemplo, produtos que sejam

freqüentemente vendidos de forma conjunta. Um exemplo clássico da aplicação

desta tarefa é na área de marketing: durante um processo de descoberta de

associações em sua vasta base de dados, uma grande rede de mercados

norte-americana descobriu que um número razoável de compradores de fralda

43

também comprava cerveja na véspera de finais de semana com jogos

transmitidos pela televisão.

Existem diversos algoritmos desenvolvidos especificamente para

aplicação na tarefa de descoberta de associações, dentre eles: Apriori, DHP

(Direct Hashing and Pruning), Partition, DIC (Dynamic Itemset Counting), Eclat,

MaxE-ctat, Clique, MaxClique, Cumulate e EstMerge. Existem versões destes

algoritmos para funcionamento em ambientes paralelos e distribuídos.

b) Classificação

Classificação é uma das tarefas de KDD mais importantes e mais

populares, pois permite associar corretamente cada registro de um banco de

dados à um único rótulo categórico denominado “classe”. Pode ser aplicada a

novos registros de forma a prever a classe em que tais registros se

enquadram. Essa tarefa pode ser incorporada a um sistema de apoio à decisão

que auxilie na filtragem e concessão de empréstimos somente a clientes

classificados como bons pagadores. Redes Neurais, Algoritmos Genéticos,

Lógica Indutiva são exemplos de técnicas (algoritmos) que podem ser

aplicadas na tarefa de classificação (GOLDSCHMIDT e PASSOS, 2005).

Figura 5: Classificação do dados. GOLDSCHMIDT e PASSOS (2005)

Conj. de Dados Conj. de Classes

f(?)

44

c) Regressão

Compreende a busca por uma função que mapeie os registros de um

banco de dados em valores reais. Esta tarefa é similar à tarefa de classificação,

sendo restrita apenas a atributos numéricos. Estatística, Redes Neurais, e outras

áreas, oferecem ferramentas para implementação da tarefa de regressão, de

acordo com Michie et al. (1994) apud Goldschmidt e Passos (2005).

d) Sumarização

Segundo Weiss e Indurkhya (1998) citados por Goldschmidt e Passos

(2005), a tarefa de Sumarização, muito comum em KDD, consiste em procurar,

identificar e apresentar de forma concisa e compreensível, as principais

características dos dados contidos em um conjunto de dados, características que

sejam comuns à boa parte dos clientes.

Por exemplo: são assinantes da revista X, homens na faixa etária de

25 a 45 anos, que residem na região sudeste do Brasil, são em grande maioria,

assinantes com faixa salarial de X reais, nível superior completo, que possuem

residência própria e que trabalham na área de finanças. ". Tais informações

poderiam ser utilizadas pela equipe de marketing da revista para direcionar a

oferta para novos assinantes.

É muito comum aplicar a tarefa de Sumarização a cada um dos

agrupamentos obtidos pela tarefa de Clusterização. Lógica Indutiva e

algoritmos Genéticos são alguns exemplos de técnicas que podem ser aplicadas

na implementação da tarefa de Sumarização.

45

e) Clusterização

Segundo Fayyad et al. (1996), a tarefa de Clusterização, também

chamada de Agrupamento, é utilizada para separar os registros de uma base de

dados em subconjuntos (clusters) de tal forma que os elementos de um cluster

compartilhem de propriedades comuns que os distingam de elementos em outros

clusters. Diferente da tarefa de classificação, que tem rótulos predefinidos, a

Clusterização precisa automaticamente identificar os grupos de dados aos quais

o usuário deverá atribuir rótulos. Por esta razão, a Clusterização é também

denominada “Aprendizado não supervisionado”.

A Clusterização pode ser considerada como uma das tarefas básicas

da Mineração de Dados que auxilia o usuário a realizar agrupamentos naturais

de registros em um conjunto de dados.

Por exemplo: uma empresa do ramo de telecomunicações pode

realizar um processo de Clusterização de sua base de clientes de forma obter

grupos de clientes que compartilhem o mesmo perfil de compra de serviços. Na

implementação desta tarefa podem ser utilizados algoritmos tais como: K-Means,

K-Modes, K-Medoids, Kohonen, dentre outros.

Esta tarefa é assunto do capítulo 2 deste trabalho, onde será mais

aprofundado.

f) Detecção de Desvios

Para Weiss e Indurkhya (1998) apud Goldschmidt e Passos (2005),

essa tarefa consiste em procurar e identificar registros do banco de dados cujas

características não atendam aos padrões considerados normais. Sua aplicação

vem crescendo de forma significativa nos últimos anos, sendo muito utilizada para

46

detecção de fraudes em cartões de crédito, planos de saúde, arrecadação,

dentre outras.

Diferentemente das demais tarefas de KDD em que a repetição de

padrões é uma característica fundamental na busca por conhecimento, a

detecção de desvios procura identificar padrões com pouca incidência e que

sejam suficientemente distintos dos valores normalmente registrados. A

tecnologia de Agentes Inteligentes é muito utilizada na detecção de desvios.

g) Descoberta de Seqüências

Segundo Srikant et al. (1997) citados por Goldschmidt e Passos

(2005), é uma extensão da tarefa de descoberta de associações, que são

buscados itens freqüentes considerando-se várias transações ocorridas ao

longo de um período (GOLDSCHMIDT e PASSOS, 2005).

h) Previsão de Séries Temporais

Segundo Goldschmidt e Passos (2005), uma série temporal é um

conjunto de observações de um fenômeno ordenadas no tempo. São exemplos

de séries temporais, o consumo mensal de energia elétrica de uma casa,

registrado durante um ano, as vendas diárias de um produto no decorrer de um

mês, dentre muitos outros. Dentre os diversos objetivos da análise de séries

temporais, o maior deles é a geração de modelos voltados à previsão de valores

futuros (Bolsa de Valores).

47

Há quatro principais tipos de movimentos utilizados na

caracterização de séries temporais:

I. Movimentos de Tendência;

II. Movimentos Cíclicos;

III. Movimentos Sazonais; e

IV. Movimentos Irregulares ou Randômicos.

1.6 Métodos de Mineração de Dados

Segundo Elmasri e Navathe (2000), Mineração de Dados é o uso de

métodos e técnicas automáticas de exploração de grandes quantidades de dados,

para descobrir novos padrões, tendências e relações, que devido ao grande

volume de dados, não seriam facilmente descobertos a olho nu pelo ser humano.

Por isso, métodos (algoritmos) e técnicas de análise precisam ser aplicados sobre

esses dados para que relações novas e úteis possam ser descobertas, ou seja, os

dados devem ser “minerados” (Data Mining).

Portanto, a Mineração de Dados consiste em extrair informações de

grandes bases de dados de empresas, organizações e instituições, permitindo a

realização de análise para que se possa interpretá-los e oferecer apoio nas

tomadas de decisões.

A seguir estão sucintamente descritos diversos métodos (algoritmos) e

suas aplicações em Mineração de Dados. É importante destacar que vários deles

são utilizados em muitos outros tipos de aplicações. Além disso estes algoritmos

apenas ilustram, mas não esgotam o universo de métodos de Mineração de

48

Dados. A compreensão de determinados algoritmos requer um conhecimento

prévio sobre algumas técnicas tais como Redes Neurais, Lógica Nebulosa e

algoritmos Genéticos (GOLDSCHMIDT e PASSOS, 2005).

1.6.1 Algoritmos de Redes Neurais

Segundo Braga, Carvalho e Ludermir (2000), o final dos anos 80

marcou o ressurgimento da área de Redes Neurais Artificiais (RNAs),

consideradas sistemas compostos por unidades de processamento simples

(nodos ou neurônios) que calculam funções matemáticas e estão dispostos em

uma ou mais camadas interligadas por conexões.

Estas conexões estão associadas a pesos que representam o

conhecimento do modelo e servem para ponderar a entrada de cada neurônio.

Conceito de um Neurônio Artificial

Figura 6: Neurônio Artificial. BRAGA, LUDERMIR e CARVALHO (2000)

X1

X2

Xn

W1

W2

Wn

F(NET) y

Saída

Entradas

Pesos

Unidade de

Processamento

Função de

Ativação

UB UB=Limiar

49

A figura 7 representa uma Rede Neural com vários Neurônios e três

camadas.

Figura 7: Rede Neural Artificial. GOLDSCHMIDT e PASSOS (2005)

A capacidade de aprender através de exemplos é sem dúvida é o

maior atrativo das (RNAs), consideradas ferramentas computacionais

extremamente poderosas para soluções de problemas complexos.

Segundo Goldschmidt e Passos (2005), diversos algoritmos de

Redes Neurais podem ser utilizados na Mineração de Dados.

Classificação, Regressão, Previsão de Séries Temporais e

Clusterização são exemplos de tarefas de Mineração de Dados que podem ser

implementadas por algoritmos de Redes Neurais. Alguns algoritmos de Redes

Neurais podem ser aplicados em mais de um tipo de tarefa de Mineração.

...

... ...

50

Back-propagation

O algoritmo Back-propagation, também conhecido como algoritmo de

retro-propagação do erro, é um algoritmo de aprendizado supervisionado, cuja

aplicação é adequada a tarefas de Mineração de Dados tais como Classificação,

Regressão ou Previsão de Séries Temporais (GOLDSCHMIDT e PASSOS,

2005).

Kohonen

Segundo Braga, Carvalho e Ludermir (2000), o algoritmo Kohonen

pertence à classe das Redes Neurais Auto-organizáveis (Mapas Auto-

organizáveis também denominados “Self-Organizing Maps –SOM”).

Esse algoritmo será mais detalhado no capítulo 2, por se tratar de

um algoritmo de Clusterização, um assunto específico daquele capítulo.

1.6.2 Algoritmos Genéticos

Segundo Goldschmidt e Passos (2005), os algoritmos Genéticos são

extremamente úteis em problemas complexos que envolvam otimizações. Em

particular, podem ser aplicados a diversas tarefas de Mineração de Dados

Rule Evolver

O Rule Evolver é um algoritmo genético.

1.6.3 Algoritmos Baseados em Instâncias

Segundo Goldschmidt e Passos (2005), a expressão "Métodos

baseado em instância" indica que o algoritmo, ao processar um novo registro, leva

51

em consideração as instâncias ou os registros existentes na base de dados. Um

dos principais métodos de Mineração de Dados baseados em instâncias é

denominado K-NN (K-Nearest Neighbors ou, em português, K-Vizinhos mais

Próximos).

Algoritmo K-NN

O método K-NN é muito utilizado em aplicações envolvendo a tarefa de

classificação. Trata-se de um método de fácil entendimento e implementação e

que não requer treinamento prévio para ser aplicado.

1.6.4 Algoritmos Estatísticos

Diversos algoritmos de Mineração de Dados são fundamentados em

princípios e teorias da Estatística (GOLDSCHMIDT e PASSOS, 2005).

Classificador Bayesiano Ingênuo

O Classificador Bayesiano Ingênuo baseia-se no Teorema de

Bayes, estando relacionado ao cálculo de probabilidades condicionais. É

aplicável, conforme o próprio nome sugere, em tarefas de classificação.

Outros algoritmos estatísticos como K-Means, K-Modes, K-Medoids ,

SimpleK-Means, PAM e Clarans serão detalhados no capítulo 2, por se

tratarem de algoritmos de Clusterização, assunto específico daquele capítulo


52

1.6.5 Algoritmos Específicos

Segundo Agrawal (1993) apud Goldschmidt e Passos (2005), alguns

algoritmos, tais como: GSP, DHP, Partition, DIC, Eclat, MaxEclat, Clique e

MaxClique foram inspirados no funcionamento do Apriori, um algoritmo

desenvolvidos especificamente para tarefa de Mineração de Dados, voltados à

Descoberta de Associações .

Apriori

O algoritmo Apriori consiste em encontrar conjuntos de itens que

ocorram simultaneamente e de forma freqüente em um banco de dados,

produtos que sejam freqüentemente vendidos de forma conjunta, por exemplo.

1.6.6 Algoritmos de Árvores de Decisão

Segundo Goldschmidt e Passos (2005), alguns dos principais

algoritmos de Mineração de Dados são baseados na construção de árvores de

decisão. Em geral a construção de uma árvore de decisão é realizada segundo

alguma abordagem recursiva de particionamento da base de dados.

C4.5

O algoritmo C4.5 é um exemplo clássico de método baseado na indução

de árvores de decisão, bastante aceito e utilizado pela comunidade científica

mundial.

53

1.6.7 Algoritmos Baseados em Lógica Nebulosa

Segundo Goldschmidt e Passos (2005), diversos métodos de

Mineração de Dados foram adaptados de forma a incorporar a flexibilidade

proporcionada pela Lógica Nebulosa. Entre eles podem ser citadas as versões

nebulosas do K-Means (Fuzzy K-Means) e do C4.5. Nessas versões, os

registros da base de dados podem pertencer a diversos clusters e classes

simultaneamente, com diferentes graus de pertinência.

Wang-Mendel

O algoritmo Wang-Mendel foi concebido para aplicação em tarefas de

Previsão de Séries Temporais utilizando Lógica Nebulosa. Esse método consiste

em abstrair regras nebulosas a partir de conjuntos de dados históricos, para definir

os antecedentes e os conseqüentes de tais regras. Com conceitos da Lógica

Nebulosa, podem-se construir sistemas inteligentes de controle e suporte à

decisão que lidem com informações imprecisas e subjetivas, tais como:

Investimento de alto risco; Pressão média; Fluxo muito intenso; Temperatura alta

e Muito jovem, são todas as expressões lingüísticas cuja interpretação pode variar

de um indivíduo para outro, sendo, portanto, expressões nebulosas. Como

exemplos de aplicações industriais e comerciais da Lógica Nebulosa, podem ser

citados:

• Aparelhos de Refrigeração;

• Filmadoras;

• Freios Antiderrapantes (ABS);

• Sistema de Análise de Crédito;

• Detecção de Fraude em Seguradoras;

• Sistema de Análise de Investimentos;

• Dentre muitos outros...

54

A figura 8 mostra quatro exemplos de conjunto nebulosos

construídos em função da variável "Idade". Todos os conjuntos apresentam o

formato de trapézios.

Figura 8: Conjunto nebuloso construído em função da variável "Idade".


Pode-se perceber pelo exemplo que uma pessoa que possua 40

anos, pertence ao mesmo tempo aos conjuntos jovem e velho, com graus de

pertinência 0,65 e 0,45, respectivamente. Isso é Lógica Nebulosa.

55

1.7 Resumo das Tarefas de KDD

A seguir é apresentado um resumo das principais tarefas de KDD e

algumas alternativas de métodos (algoritmos) que podem ser utilizados, porém

ressaltando, mais uma vez, que a tabela a seguir não esgota o universo de

métodos de Mineração de Dados que pode ser aplicado em cada tarefa de KDD


Tarefas de KDD

Métodos de Mineração de Dados

Descoberta de Associações

Basic, Apriori, DHP, Partition, DIC, ASCX-2P

Descoberta de Seqüências

GSP, MSDD, SPADE

Classificação

Redes Neurais (Ex: Back-Propagation, RBF), C4.5,

Rough Sets, Algoritmos Genéticos (Ex: Rule Evolver),

CART, K-NN, Classificadores Bayesianos

Regressão

Redes Neurais (Ex: Back-Propagation), Lógica Nebulosa

Sumarização

C4.S, algoritmos Genéticos (Ex: Rule Evolver)

Clusterização K-Means, K-Modes, K-Prototypes, Fuzzy

algoritmos Genéticos, Redes Neurais (Ex: Kohonen)

Previsão de Séries Temporais Redes Neurais (Ex: Back-Propagation), Lógica Nebulosa

(Ex: Wang-Mendel)

Tabela 1: Resumo das tarefas de KDD. GOLDSCHMIDT e PASSOS (2005).

56

1.8 Ferramentas de KDD

Atualmente, existem diversas ferramentas que implementam

ambientes integrados para facilitar a execução das etapas operacionais de KDD.

Abaixo apresentam-se algumas destas ferramentas (GOLDSCHMIDT e

PASSOS, 2005):

Nome Tarefas de KDD Fabricante

SPSS/Clementine

Classificação, Regras de

Associação, Clusterização,

Seqüências, Detecção de

Desvios.

SPSS Inc.

www.spss.com

PolyAnalyst

Classificação, Regressão,

Regras de Associação,

Clusterização, Sumarização,

Detecção de Desvios.

Megaputer Intelligence

www.megaputer.com

Weka

Classificação, Regressão,

Regras de Associação e

Clusterização.

University of Waikato

www.cs.waikato.ac.nz/ml/weka

Darwin Classificação Thinking Machines

http://en.wikipedia.org/wiki/thinking_machines

Intelligent Miner


Associação, Seqüências,

Clusterização, Sumarização.

IBM Corp.

www.ibm.com

WizRule Sumarização, Classificação,

Detecção de Desvios.

WizSoft Inc.

www.wizsoft.com

Bramining


Associação, Regressão,

Sumarização.

Graal Corp.

www.graal-corp.com . br

SAS Enterprise

Miner


Associação, Regressão,

Sumarização.

SAS Inc.

www.sas.com

Oracle Data Mining

classificação, regressão,

associação, clusterização, e

mineração de textos

Oracle

www.oracle.com

Tabela 2: Ferramentas de KDD.


http://www.ibm.com/

http://www.wizsoft.com/

http://www.oracle.com/

57

2 CLUSTERIZAÇÃO (CLUSTERING)

2.1 Apresentação

Neste capítulo é apresentado o conceito de Clusterização, tema de

estudo proposto neste trabalho e uma descrição de alguns algoritmos da tarefa de

Clusterização mais conhecidos, utilizados em diversas ferramentas citadas na

tabela 2.

Segundo Fayyad et al. (1996), Clusterização é uma tarefa do processo

de KDD, também chamada de Agrupamento, que separa os registros de uma

base de dados em subconjuntos (clusters), de tal forma que os elementos de um

cluster tenham características comuns que os distingam de elementos em outros

clusters. A Clusterização pode ser considerada como uma das tarefas básicas da

Mineração de Dados que auxilia o usuário a realizar agrupamentos naturais de

registros em um conjunto de dados.

Em geral, o processo de Clusterização requer que o usuário determine

qual o número de cluster a ser considerado. Com base neste número, os

registros de dados são então separados nos grupos de forma que os registros

similares fiquem nos mesmos grupos e registros diferentes fiquem em grupos

distintos. Tendo esses grupos, torna-se possível fazer uma análise dos elementos

58

que compõem cada um deles, identificando as características comuns aos seus

elementos e, desta forma, podendo criar um rótulo que represente cada grupo.

2.1.1 Estrutura de Dados

Para que os algoritmos de Clusterização possam efetuar sua tarefa faz-

se necessário utilizar estruturas de dados capazes de armazenar os objetos

(registros) a serem processados. Algoritmos de Clusterização que trabalham com

dados armazenados na memória principal, normalmente, utilizam uma das

seguintes estruturas de dados no seu processamento (GOLDSCHMIDT e

PASSOS, 2005):

Matriz de dados - As linhas representam cada um dos objetos a

serem clusterizados e as colunas, os atributos ou características de cada objeto.

Considerando n objetos cada qual com p atributos, obtém-se uma matriz

n x p como a matriz abaixo:

Figura 9: Matriz de dados. (GOLDSCHMIDT e PASSOS, 2005)

59

Matriz de similaridade - Cada elemento da matriz representa a

distância entre pares de objetos. Visto que a distância entre o objeto i e o objeto j

é igual à distância entre o objeto j e o objeto i, não é necessário armazenar

todas as distâncias entre os objetos. Portanto, considerando n objetos à serem

clusterizados, obtém-se uma matriz quadrada de tamanho n x n como a que

segue:

Figura 10: Matriz de similaridade.

(GOLDSCHMIDT e PASSOS, 2005)

O ponto d(i, j) representa a distância ou similaridade entre o objeto i e

o j. Como as medidas de similaridade expressam o conceito de distância, estas

são sempre números positivos. Quanto mais próximo de zero for d(i, j), mais

similares serão os objetos.

Quando um algoritmo que trabalha com matrizes de similaridade

recebe uma matriz de dados, ele primeiro a transforma em uma matriz de

similaridade antes de iniciar o processo de Clusterização (HAN e KEMBER,

2001) citado por Carlantonio (2001).

60

2.1.2 Requisitos para os Algoritmos de Clusterização

Segundo Carlantonio (2001), cabe ressaltar que, para se obter uma

melhor Clusterização dos dados, alguns requisitos devem ser atendidos pelos

algoritmos que implementam essa tarefa, como segue:

• Descobrir clusters de forma arbitrária - A forma dos clusters,

considerando o espaço euclideano, pode ser esférica, linear, alongada, elíptica,

cilíndrica, espiralada, etc. Os métodos de Clusterização baseados na medida de

distância Euclideana tendem a encontrar clusters esféricos de tamanho e

densidade similares;

• Identificar clusters de tamanhos variados - Além da forma, alguns

métodos tendem a fazer os clusters com tamanho homogêneo;

• Aceitar os diversos tipos de variáveis possíveis - Os métodos têm

que ser capazes de lidar com variáveis contínuas, discretas e nominais;

• Ser insensível à ordem de apresentação dos objetos - Um mesmo

conjunto de objetos quando apresentado em diferentes ordenamentos deve

conduzir aos mesmos resultados;

• Trabalhar com objetos com qualquer número de atributos

(dimensões) - Os olhos humanos são bons para julgar a qualidade de clusters

com até três dimensões. Os métodos devem manejar, com eficiência, objetos

com altas dimensões e fornecer resultados compreensíveis;

• Ser escalável para lidar com qualquer quantidade de objetos - Uma

base de dados de grande porte pode conter milhões de registros. Os métodos

devem ser rápidos e escalonáveis em função do número de dimensões e da

quantidade de registros a serem clusterizados;

61

• Fornecer resultados interpretáveis e utilizáveis - As descrições dos

clusters devem ser facilmente assimiladas. Em geral, os usuários esperam que os

resultados dos clusters sejam interpretáveis, compreensíveis e utilizáveis.

Assim, é importante que os algoritmos utilizem representações simples;

• Ser robusto na presença de ruídos - A maioria das bases de dados

do mundo real contém ruídos, dados desconhecidos ou errôneos. A existência

deles não deve afetar a qualidade dos clusters obtidos;

• Exigir o mínimo de conhecimento para determinar os parâmetros de

entrada - Os valores apropriados são frequentemente, desconhecidos e difíceis

de determinar, especialmente, para conjuntos de objetos de alta

dimensionalidade e de grande número de registros. Em alguns métodos, os

resultados do processo de Clusterização são bastante sensíveis aos parâmetros de

entrada;

• Aceitar restrições - Aplicações reais podem necessitar agrupar

objetos de acordo com vários tipos de restrições. Assim sendo, os métodos

devem encontrar grupos de dados cujas estruturas satisfaçam às restrições

especificadas; e

• Encontrar o número adequado de clusters - Encontrar o número

natural de clusters de um conjunto de objetos é uma tarefa difícil. Muitos

métodos precisam de um valor de referência, especificado pelo usuário.

Como dito por Agrawal et al. (1998) apud Carlantonio (2001), nenhuma

técnica de Clusterização existente atende a todos estes requisitos de forma

adequada, embora um trabalho considerável seja feito para atender a cada ponto

separadamente. Assim, há métodos apropriados para grandes quantidades de

62

registros e outros para pequenas quantidades; métodos em que o número de

clusters tem que ser fornecido pelo usuário e outros em que não há essa

exigência; métodos capazes de identificar clusters que tenham tamanhos diversos

e outros que necessitam que os clusters tenham tamanhos semelhantes; métodos

para dados categóricos; métodos que sofrem a influência de “ruídos” e outros

insensíveis a estes; etc.

2.2 Métodos de Clusterização

Segundo Han e Kamber (2001) apud Carlantonio (2001), em geral a

classificação dos algoritmos de Clusterização é dividida em:

• Métodos por particionamento;

• Métodos hierárquicos;

• Métodos baseados em densidade;

• Métodos baseados em grades;

• Métodos baseados em modelos.

Os métodos mais tradicionais de Clusterização são os métodos por

particionamento e os métodos hierárquicos. Os primeiros métodos por

particionamento foram: o método K-MEANS, que é de 1967, e os métodos PAM

e CLARA, que são de 1990. Já para os métodos hierárquicos, os primeiros

foram os métodos AGNES e DIANA, que são de 1990 (HAN e KAMBER, 2001)

apud Carlantonio (2001).

63

2.2.1 Métodos por Particionamento

Carlantonio (2001) explica que os algoritmos de Clusterização por

particionamento dividem a base de dados em k grupos, onde o usuário escolhe o

número k. A partir daí, estes algoritmos escolhem k objetos (registros) que farão

parte de cada clusters.

Os objetos são divididos entre os k clusters de acordo com a medida

de similaridade adotada, de modo que cada objeto fique no cluster que forneça o

menor valor de distância entre o objeto e o centro do mesmo. Os algoritmos

utilizam, então, uma estratégia iterativa, que determina se os objetos devem

mudar de cluster, fazendo com que cada cluster contenha somente elementos

similares entre si.

Após a divisão inicial, há duas possibilidades na escolha do

"elemento" que vai representar o centro do cluster, e que será a referência para o

cálculo da medida de similaridade:

• Pode-se utilizar a média dos objetos que pertencem ao cluster em

questão, também chamada de “centro de gravidade” do cluster. Essa é a

abordagem conhecida como K-Means, nome de um dos mais importantes

algoritmos de Clusterização;

• Pode-se também escolher como representante do cluster o objeto

que se encontra mais próximo ao centro de gravidade do cluster. Essa

abordagem é conhecida como k-medoids, e o elemento mais próximo ao centro

é chamado de medoid.

64

Algoritmo K-Means

Carlantonio (2001), Goldschmidt e Passos (2005), apresentam o

algoritmo K-Means como um método popular da tarefa de Clusterização, que

toma, randomicamente, k pontos de dados (dados numéricos) como sendo os

centróides (elementos centrais) dos clusters.

Em seguida, cada ponto (registro da base de dados) é atribuído ao

cluster cuja distância deste ponto em relação ao centróide de cada cluster é a

menor dentre todas as distâncias calculadas.

Um novo centróide para cada cluster é computado pela média dos

pontos do cluster, caracterizando a configuração dos clusters para a iteração

seguinte. O processo termina quando os centróides dos clusters param de se

modificar, ou após um número limitado de iterações que tenha sido especificado

pelo usuário.

A execução do algoritmo K-Means consiste em, primeiro, selecionar

aleatoriamente k objetos que inicialmente representam cada um, a média de um

cluster. Para cada um dos objetos remanescentes, é feita a atribuição ao cluster

ao qual o objeto é mais similar, baseado na distância entre o objeto e a média

do cluster.

A partir de então, o algoritmo computa as novas médias para cada

cluster. Este processo se repete até que uma condição de parada seja atingida.

O algoritmo tenta determinar partições que minimizem a função do

erro quadrado, mas apresenta bom desempenho quando os clusters são

densos, compactos e bem separados uns dos outros.

65

O funcionamento do algoritmo K-Means encontra-se resumido na

Figura 11.

Figura 11: Fluxograma do funcionamento do Algoritmo K-Means.

Fonte: GOLDSCHMIDT e PASSOS (2005).

A necessidade de o usuário ter que especificar k (o número clusters),

com antecedência pode ser visto como uma desvantagem. Em geral, diversos

experimentos variando o valor de k devem ser realizados. Objetos, que são

diferentes ou inconsistentes em relação ao conjunto de dados, são chamados de

ruídos (outliers). O método K-Means é sensível a ruídos visto que pequeno

número de dados ruidosos pode influenciar, substancialmente, os valores médios

dos clusters. A figura 12 ilustra a aplicação do algoritmo K-Means em um arquivo

com 20 registros de dados, considerando-se k = 3.

O algoritmo K-Means é inicializado com os centros (médias)

colocados em posições aleatórias. A busca pelo centro comum se faz de forma

iterativa. Após essa inicialização, os objetos restantes são agrupados conforme

a distância em que se encontram dessas médias (GOLDSCHMIDT E PASSOS,

2005).

Houve Mudança na

configuração do cluster

66

Figura 12: Passos subseqüentes do Algoritmo K-Means.

GOLDSCHMIDT; PASSOS (2005)

Algoritmo K-Modes

Para Carlantonio (2001) e Goldschmidt e Passos (2005), outra

variante do k-means é o método K-Modes, que estende o paradigma k-means

para clusterizar dados categóricos, trocando a média de clusters com a moda

(valor que aparece com maior freqüência). Os métodos k-means e K-Modes

podem ser combinados para clusterizar dados com misturas de valores

numéricos e categóricos, resultando no método K-Prototypes.

c) d)

a) b)

67

Algoritmo K-Medoids

O algoritmo k-means é sensível a ruídos visto que um objeto com

um valor extremamente grande pode, substancialmente, distorcer a distribuição

de dados. Para diminuir essa sensibilidade no algoritmo K-Medoids, ao invés

de utilizar o valor médio dos objetos em um cluster como um ponto de

referência, usa o objeto mais centralmente localizado em um cluster. Assim, o

método de particionamento pode ainda ser desempenhado no intuito de

minimizar a soma das dissimilaridades entre cada objeto e seu ponto de

referência correspondente. Isto forma a base do método K-Medoids.

O algoritmo K-Medoids baseia-se, primeiramente, em encontrar o

medoid (objeto mais centralmente localizado em um cluster). Os objetos

restantes são então clusterizados com o medoid ao qual ele é mais similar. Há

então uma troca iterativa, de um medoid por um não medoid, visando à

melhoria da Clusterização. A diferença básica entre o K-Means e K-Medoids

está em o primeiro elemento representar de cada cluster pela média dos registros

que pertencem ao cluster e no segundo em representar o cluster por um dos

registros pertencentes ao cluster.

Segundo Han e Kamber (2001) apud Carlantonio (2001), o método

k-Medoids é mais robusto do que o k-means na presença de ruídos porque um

medoid pode ser menos influenciado pelos ruídos do que a média. Entretanto,

seu processamento pode ser mais custoso do que o do método k-means.

Ambos os métodos requerem que o usuário especifique k, o número de

clusters.

68

Algoritmo PAM

Segundo Carlantonio (2001), PAM (Partitioning Around Medoids) foi

um dos primeiros algoritmos k-medoids apresentados.

NG e Han (1994) apud Carlantonio (2001), comentam que uma vez

que os medoids tenham sido selecionados, cada objeto não selecionado é

agrupado com o medoid ao qual ele é mais similar. Todos os valores de

dissimilaridade são dados como entradas para o algoritmo PAM. Finalmente, a

qualidade de uma Clusterização é medida pela dissimilaridade média entre um

objeto e o medoid de seu cluster.

Han e Kamber (2001) e NG e HAN (1994) apud Carlantonio (2001),

escrevem que um algoritmo típico de particionamento k-medoids como o

algoritmo PAM é eficiente para pequenos conjuntos de dados, mas não é

escalável para grandes conjuntos de dados.

Algoritmo CLARA

Para tratar com grandes conjuntos de dados, um método baseado

em amostragem, chamado CLARA (Clustering Large Applications) pode ser

usado. A idéia por trás deste método é a seguinte: Ao invés de tomar todo o

conjunto de dados em consideração, uma pequena porção dos dados é

escolhida como uma amostra representativa. Medoids são então escolhidos da

amostra usando o algoritmo PAM (CARLANTONIO, 2001).

69

Algoritmo CLARANS

Han e Kamber (2001) apud Carlantonio (2001), lembram que um

algoritmo tipo k-medoids chamado CLARANS (Clustering Large Applications

based upon Randomize Search) foi proposto, procurando combinar a técnica

de amostragem (CLARA) com o algoritmo PAM.

Entretanto, diferente do algoritmo CLARA, o algoritmo CLARANS

não se restringe a alguma amostra em um dado tempo. Enquanto o algoritmo

CLARA tem uma amostra fixa a cada estágio de busca, o algoritmo CLARANS

executa uma amostra com algum grau de aleatoriedade em cada etapa da

busca.

Ester et al. (1995) apud Carlantonio (2001), escrevem que o

algoritmo CLARANS é um método de Clusterização baseado no algoritmo PAM

com uma nova estratégia de busca heurística. Esta estratégia não tenta todos

os possíveis Clusters, mas somente um pequeno número deles, que são

selecionados de uma forma aleatória.

Carlantonio (2001) explica que o algoritmo CLARANS tem se

mostrado, experimentalmente, mais efetivo do que ambos os algoritmos PAM e

CLARA. Ele pode ser usado para encontrar o número de clusters mais "natural"

usando um coeficiente de silhueta (uma propriedade de um objeto que

especifica quanto o objeto verdadeiramente pertence ao cluster). O algoritmo

CLARANS também permite a detecção de ruídos.

70

2.2.2 Métodos Hierárquicos

Segundo Goldschmidt e Passos (2005) e Ester et al. (1998) apud

Carlantonio (2001), os algoritmos de Clusterização Hierárquicos criam uma

decomposição hierárquica da base de dados. A decomposição hierárquica é

representada por um dendograma, uma árvore que iterativamente divide a base

de dados em subconjuntos menores até que cada subconjunto consista de

somente um objeto. Em tais hierarquias, cada nó da árvore representa um cluster

da base de dados.

O dendograma pode ser criado de duas formas:

• Abordagem Aglomerativa (bottom-up): Parte-se das folhas para a

raiz. Coloca-se, inicialmente, cada objeto (registro) em seu próprio cluster, ou

seja, todos os objetos estão separados, totalizando n clusters.

• Abordagem Divisiva (top-down): Parte-se da raiz para as folhas.

Inverte-se o processo por começar com todos os objetos em um único cluster.

Em cada etapa, um cluster é escolhido e dividido em dois clusters menores. Esse

processo continua até que se tenha n clusters ou até que uma condição de

término aconteça (NG e HAN, 1994; HAN e KAMBER, 2001) apud Carlantonio

(2001).

Figura 13: Dendograma.

Top-Down

Botton-Up

1 2

3

4

5

71

Cole (1998) apud Carlantonio (2001) comenta que os métodos

aglomerativos são mais populares do que os métodos divisivos.

Algoritmos AGNES e DIANA

De acordo com Carlantonio (2001), o método AGNES (AGglomerative

NESting) é um exemplo de método hierárquico aglomerativo e o método DIANA

(DIvisive ANAlysis) é um método hierárquico divisivo.

Na Figura 14 apresenta-se um exemplo de como os métodos

hierárquicos trabalham.

Figura 14: Como os Métodos Hierárquicos trabalham.

(CARLANTONIO, 2001).

Algoritmo BIRCH

Guha et al. (1998) apud Carlantonio (2001) comentam que o método

BIRCH representa o estado da arte para Clusters de conjuntos de dados

grandes.

72

Algoritmo CURE

O método CURE é um algoritmo hierárquico, que interrompe a criação

de uma hierarquia de cluster se um nível consiste de k clusters, onde k é um dos

vários parâmetros de entrada (ANKERST et al., 1999) apud Carlantonio (2001).

Segundo Carlantonio (2001), o método CURE emprega um novo

algoritmo hierárquico de Clusterização que adota um meio termo entre as

abordagens baseadas em centróide e baseadas em objetos representativos. Ao

invés de usar um centróide único ou objeto para representar um cluster, um

número fixo de pontos representantes do espaço é escolhido.

Algoritmo ROCK

O método ROCK (RObust Clustering using linKs) é um algoritmo de

Clusterização hierárquico aglomerativo alternativo que é adequado para

Clusterização de atributos categóricos.

Como destacado por Guha et al. (1999) apud Carlantonio (2001),

algoritmos tradicionais que usam distância entre pontos para Clusterização não

são apropriados para atributos categóricos e booleanos (binários).

2.2.3 Métodos Baseados em Densidade

Segundo Carlantonio (2001), a maioria dos métodos por

particionamento agrupa objetos baseado na distância entre objetos. Tais métodos

podem encontrar dificuldades para descobrir clusters de formas arbitrárias.

Ester et al. (1996) apud Carlantonio (2001), colocam que quando

olhamos para conjuntos de objetos tais como os da figura 15, nós podemos,

73

facilmente detectar clusters de objetos e ruídos não pertencentes a qualquer dos

clusters.

Figura 15: Representação de clusters e ruídos.

CARLANTONIO (2001).

Carlantonio (2001) e Ester et al. (1996) afirmam que a razão principal

porque nós reconhecemos os clusters é que dentro de cada cluster tem uma

densidade de objetos típica que é consideravelmente maior do que fora dos

clusters.

Além disso, a densidade de áreas de ruído é menor do que a

densidade em qualquer dos clusters. Um método baseado em densidade

clusteriza objetos baseado na noção de densidade.

Algoritmo DBSCAN

Segundo Ankerst et al. (1999); Sheikholeslami et al. (1998); Han e

Kamber (2001) apud Carlantonio (2001), o método DBSCAN (Density-Based

Spatial Clustering on Applications with Noise) é um algoritmo de Clusterização

baseado em densidade que não é baseado em grade, que cresce em regiões

com densidade alta o suficiente nos clusters e descobre clusters de forma

arbitrária em bases de dados espaciais com ruído, podendo separá-lo.

74

O método DBSCAN encontra regiões densas que são separadas por

regiões de baixa densidade (regiões de ruídos), define um cluster como um

conjunto máximo de pontos conectados densamente e agrupa os objetos na

mesma região densa.

Figura 16: Alcance por Densidade e Conectividade por Densidade.

CARLANTONIO (2001).

2.2.4 Métodos Baseados em Grades

Segundo Han e Kamber (2001) apud Carlantonio (2001), os métodos

de Clusterização baseados em grades usam uma estrutura de dados em grade

de multi-resolução. Ele divide o espaço de objetos em um número finito de

células que formam uma estrutura de grade nas quais todas as operações de

Clusterização são efetuadas. A principal vantagem desta abordagem é seu

tempo de processamento rápido, que é tipicamente independente do número de

objetos de dados, contudo dependente, somente, do número de células em cada

dimensão no espaço discretizado (dividido).

75

Algoritmo STING

O método STING é uma técnica de Clusterização de multi-resolução

baseada em grade na qual a área espacial é dividida em células retangulares.

Existem, geralmente, vários níveis de tais células retangulares correspondendo a

diferentes níveis de resolução, e estas células formam uma estrutura hierárquica,

onde cada célula no nível mais alto é particionada para formar um número de

células no próximo nível mais baixo. São pré-computadas e armazenadas

Informações estatísticas considerando os atributos numéricos dos objetos em

cada célula da grade (tais como os valores: média, máximo, mínimo, variância e

tipo de distribuição). Estes parâmetros estatísticos são úteis para processamento

de consultas (HAN e KAMBER, 2001; SHEIKHOLESLAMI et al., 1998) apud

Carlantonio (2001).

Algoritmo WaveCluster

WaveCluster é um algoritmo de Clusterização multi-resolução que

primeiro resume os dados impondo uma estrutura de grade multidimensional ao

espaço de dados. Ele, então, usa a transformação Wavelet para transformar o

espaço característico original, encontrando regiões densas no espaço

transformado, que são os clusters.

Nesta abordagem, cada célula da grade resume a informação de um

grupo de pontos que mapeia a célula. Esta informação resumida se ajusta à

memória principal. Ela é usada pela transformação wavelet de multi-resolução e

na análise de cluster subseqüente (HAN e KAMBER, 2001) apud Carlantonio

(2001).

76

Algoritmo CLIQUE

Segundo Ankerst et al. (1999) apud Carlantonio (2001), o algoritmo de

Clusterização (Clustering In QUEst) integra os métodos de Clusterização

baseados em grade e em densidade. Ele é útil para clusterizar dados de alta

dimensão em grandes bases de dados.

Agrawal et al. (1999) apud Carlantonio (2001) afirmam que CLIQUE

esforça-se em descobrir correlações interessantes entre os dados em vários

subespaços do espaço de alta dimensão original. Os parâmetros de entrada são

o tamanho da grade e um limiar de densidade global para clusters.

Ankerst et al. (1999) apud Carlantonio (2001) colocam que a maior

diferença de CLIQUE para outras abordagens de Clusterização é que este

método também detecta automaticamente subespaços de dimensionalidade mais

alta tal que clusters de alta densidade existam nesses subespaços.

2.2.5 Métodos Baseados em Modelos

De acordo com Carlantonio (2001), os métodos baseados em modelos

usam um modelo para cada cluster que tentam otimizar a curva entre os objetos

de dados e algum modelo matemático. Este tipo de modelo pode descobrir

clusters construindo uma função de densidade que reflete a distribuição espacial

dos pontos de dados. Ele também conduz a um modo de determinar

automaticamente o número de clusters baseado na estatística padrão,

identificando ruídos no relatório e assim produzindo métodos para Clusterização

mais robustos. Tais modelos são, freqüentemente, baseados na suposição que

os dados são gerados por uma mistura de distribuições de probabilidades.

77

Os métodos de Clusterização baseados em Modelos seguem uma das

duas principais abordagens (HAN e KAMBER, 2001) apud Carlantonio (2001):

- Abordagem Estatística;

- Abordagem por Rede Neural.

2.2.5.1 Abordagem Estatística

Para Carlantonio (2001), a Clusterização conceitual é uma forma de

Clusterização em aprendizado de máquina que, dado um conjunto de objetos não

rotulados, produz um esquema de classificação sobre os objetos. Ao contrário

das Clusterização convencional, que primariamente identificam grupos de

objetos, a Clusterização conceitual realiza uma etapa adicional para encontrar

descrições características para cada grupo, onde cada grupo representa um

conceito ou classe. Muitos métodos de Clusterização adotam uma abordagem

estatística que usa medidas de probabilidade na determinação dos conceitos ou

clusters. Descrições probabilísticas são, tipicamente, usadas para representar

cada conceito derivado (CARLANTONIO, 2001).

Algoritmo COBWEB

De acordo com Carlantonio (2001), o método COBWEB cria uma

Clusterização hierárquica na forma de uma árvore de classificação que é uma

árvore de decisão, onde cada nó da árvore refere-se a um conceito e contém

uma descrição probabilística daqueles conceitos que resumem os objetos

classificados abaixo do nó.

78

Algoritmo CLASSIT

O método CLASSIT é uma extensão do algoritmo COBWEB. Ele

armazena uma distribuição normal contínua (isto é, média e desvio padrão) para

cada atributo individual em cada nó e usa uma medida de utilidade categórica

modificada, que é uma integral sobre os atributos contínuos, ao invés de uma

soma sobre atributos discretos como no método COBWEB. Entretanto, ele sofre

de problemas similares aos do algoritmo COBWEB e assim não é adequado para

clusterizar bases de dados grandes (CARLANTONIO, 2001).

2.2.5.2 Abordagem por Rede Neural

Para Carlantonio (2001), a abordagem por rede neural para

Clusterização tende a representar cada cluster como um exemplar que serve de

protótipo do cluster e não necessariamente corresponde a um exemplo de dado

particular ou objeto. São apresentados aqui dois métodos importantes da

abordagem de Rede Neural para Clusterização.

O primeiro é o aprendizado Competitivo, e o segundo é o mapa de

auto-organização (Self-Organizing Maps - SOM) de características, ambos

envolvem unidades neurais competindo (CARLANTONIO, 2001).

Aprendizado competitivo: envolve uma arquitetura hierárquica de

várias unidades (ou neurônios artificiais) que competem de forma que o

"vencedor leva tudo" para o objeto que está correntemente sendo apresentado ao

sistema. A figura 17 mostra um exemplo de um sistema de aprendizado

competitivo. Onde cada círculo representa uma unidade.

79

Figura 17: Aprendizado competitivo. (CARLANTONIO, 2001).

No final da Clusterização, cada cluster pode ser pensado como uma

nova característica que detecta alguma regularidade nos objetos. Assim, os

clusters resultantes podem ser vistos como um mapeamento das características

dos níveis mais baixos para as características dos níveis mais altos

(CARLANTONIO, 2001).

Mapas Auto-Organizáveis

Para Carlantonio (2001), com auto-organização de mapas

característicos (SOMs), o vetor de peso é mais próximo ao objeto corrente torna-

se uma unidade vencedora ou uma unidade ativa. Os pesos da unidade

vencedora são ajustados e também de seus vizinhos mais próximos de forma

que elas fiquem mais próximas do objeto de entrada (CARLANTONIO, 2001).

80

Algoritmo Kohonen

Segundo Braga, Carvalho e Ludermir (2000), o algoritmo Kohonen

pertence à classe das Redes Neurais de Mapas Auto (Self-Organizing Maps –

SOMs). Essas Redes foram desenvolvidas por Teuvo Kohonen na década de

80. Em uma Rede Neural Auto-organizável o treinamento é não supervisionado,

geralmente baseado em uma forma de competição entre os elementos

processadores.

Entre as principais aplicações do Algoritmo Kohonen estão:

• Tarefa de Clusterização - Tarefa na qual os dados de entrada

devem ser agrupados em conjuntos que agreguem padrões semelhantes;

• Detecção de Regularidades - Modelo em que o sistema deve extrair

as características relevantes dos padrões de entrada.

Figura 18: Mapa de Kohonen. GOLDSCHMIDT e PASSOS (2005).

81

3 APLICAÇÃO DO PROCESSO DE KDD

3.1 Apresentação

Neste capítulo é exposto o modo teórico e prático de como preparar

a base de dados, passando pela etapa de Pré-processamento, aplicando suas

funções até chegar ao arquivo ideal para ser, então, usado na etapa de

Mineração de Dados, onde também é descrito de modo teórico e prático de

todos os passos para carregar o arquivo em formato “.ARFF” no software

WEKA, escolher a tarefa de Cluster, configurar os parâmetros necessários,

iniciar a Mineração de Dados, colher os resultados e finalmente aplicá-los à

etapa de Pós-processamento, gerando explicações e gráficos sobre o

conhecimento encontrado.

3.2 Programas utilizados

- JAVA: linguagem de programação, versão j2sdk1.4.2_12,

disponível gratuitamente no site www.sun.com, a qual foi baixada e instalada,

pois a mesma é necessária para utilização do software WEKA;

- WEKA: software de mineração de dados usado para aplicação de

tarefas de KDD, das quais interessa neste trabalho a tarefa de Clusterização,

http://www.sun.com/

82

em especial o algoritmo SimpleK-Means, adaptado para trabalhar tanto com

dados categóricos quanto com dados numéricos.

Este software foi desenvolvido pela universidade de Waikato da

Nova Zelândia e foi obtido no site http://www.cs.waikato.ac.nz/ml/weka/

gratuitamente. Usou-se a versão weka-3-4-8a.exe;

- DBF View: software shareware que oferece uma GUI (Graphic

User Interface) para manipular Banco de Dados, disponível para ser baixado no

site www.superdownloads.com.br.

- Base de Dados: um conjunto de arquivos, no formato “.DBF”,

representando tabelas de dados de uma locadora de filmes, a qual será usada

em todo o processo de KDD e principalmente na etapa de Mineração de

Dados;

- Microsoft Excel: software de planilha de cálculos para conversão

do formato “.DBF” para “.CSV”. (podendo ser utilizado outro software de

planilha); e

- Editor de texto: para trocar os símbolos ponto_e_vírgila “ ; ” por

vírgula “ , ” e depois, para converter o arquivo “.CSV” em “.ARFF”.

3.3 Aplicação das Etapas do KDD

- Pré-processamento;

- Mineração de Dados; e

- Pós-processamento.

http://www.cs.waikato.ac.nz/ml/weka/

http://www.superdownloads.com.br/

83

3.3.1 Etapa de Pré-Processamento

Nesta seção será estudado a etapa de Pré-processamento sobre a

base de dados (conjunto de arquivos em formato “.DBF”).

Conforme descrito no capítulo 1, as principais funções do Pré-

processamento são:

a) Seleção de Dados;

b) Limpeza dos Dados;

c) Codificação dos Dados;

d) Enriquecimento dos Dados;

e) Normalização de Dados; e

f) Construção de Atributos.

Primeiramente usou-se a função de “Seleção de Dados” para

selecionar quais tabelas (ARQUIVOS.DBF) e seus respectivos atributos

(registros) serão utilizados na aplicação do processo de KDD.

Inicialmente haviam as seguintes tabelas:

- CLIENTES.DBF;

- PRODUTOS.DBF;

- MOVPROD.DBF;

- DOLAR.DBF;

- IMPCOD.DBF;

- NFISCAL.DBF;

- PACOTE.DBF;

- PAGTO.DBF; e

- CONFIG1.DBF.

84

Selecionou-se as seguintes tabelas:

Tabela CLIENTES.DBF com 3.810 registros;

Figura 19: Tabela de registros de Clientes.

Tabela PRODUTO.DBF com 5.029 registros; e

Figura 20: Tabela de registros de Filmes.

85

Tabela MOVPROD.DBF com 71.861 registros.

Figura 21: Tabela de registros de locações de Filmes.

Portanto, para esse processo de KDD, considerou-se relevantes as

seguintes tabelas e seus respectivos atributos:

Tabela 3: A tabelas escolhidas e seus atributos.

Os demais atributos destas tabelas forão descartados, como

também as demais tabelas da base de dados, pois neste momento não

representam expectativas de “Descoberta de Conhecimento na Base de

Dados” (Knowledge, Discovery in Data Base - KDD).

MOVPROD.DBF

CODCLI

CODPRO

CLIENTES.DBF

CODCLI

NOME

Bairro

Cidade

PRODUTOS.DBF

CODPRO

NOME (filme)

GENERO

86

Notou-se que as tabelas “MOVPROD.DBF, CLIENTE.DBF e

PRODUTO.DBF” contêm ruídos (outliers), ou seja, registros danificados ou

inconsistentes, conforme mostra a figura 24, o que pode influenciar nos

resultados apresentados pelos algoritmos de Clusterização.

Por outro lado, o que pode parecer ruídos para alguns, pode ser

dados relevantes para outros. Por exemplo: ruído pode ser uma forma dos

bancos verificarem fraudes em transações.

Figura 22: Registros com ruídos.

Neste caso aplicou-se a “Limpeza dos Dados”, uma função do Pré-

processamento, utilizando-se de uma planilha.

Figura 23: Registros excluídos da base de dados.

87

Os registros mostrados na figura 23 foram excluídos.

Notou-se também que alguns atributos estão na forma “Categórica”,

ou seja, em formato texto/alfanumérico. Dependendo do atributo é interessante

codificá-lo, necessitando, portanto que se aplique a próxima função do Pré-

processamento, que é a “Codificação dos Dados”. Os dados precisam ser

transformados para que fiquem numa forma que possam ser usados como

entrada pelo algoritmo de Clusterização escolhido.

Os dados devem atender às necessidades do algoritmo em questão.

Por exemplo, o algoritmo K-Means requer que os dados de entrada estejam em

uma representação numérica. Já o K-Modes, uma variação do K-Means,

trabalha com atributos categóricos para achar a “Moda”, ou seja, a freqüência

da ocorrência dos atributos (CARLANTONIO, 2001).

No entanto, ao usar o software WEKA, percebeu-se que o mesmo

aceitou e trabalhou tanto com dados numéricos quanto categóricos (formato

texto/alfanumérico), na utilização do algoritmo SimpleK-Means, aumentando as

possibilidades de hipóteses e expectativas em relação a base de dados.

A figura 26 mostra os atributos codificados da seguinte forma:

A coluna “A” foi codificada a partir da coluna original para seguir um

padrão e posteriormente foi codificada de categórica para numérica;

A coluna “D” foi codificada para seguir um padrão. Por exemplo,

onde era AV, foi padronizado para AVENTURA;

A coluna “E” em azul também foi codificada de categórica para

numérica;

88

Figura 24: Base de dados codificada.

Percebeu-se a necessidade de aplicar a “Construção de Atributos”,

“Enriquecimento dos Dados” e “Normalização”, outras funções de Pré-

processamento.

Na “Construção de Atributos”, houve a adição de novos atributos

como ID_Genero, Sexo, Dubla-Legendado, Lançamento, Em_Promoção e

Final_Semana.

89

Após a construção de alguns atributos, as tabelas “MOVPROD.DBF,

CLIENTE.DBF e PRODUTO.DBF” ficaram alteradas para:

Tabela 4: Novos atributos após aplicar a função “ Construção de Atributos” .

3.3.1.1 Hipóteses

A tabela 4 mostra novos atributos criados para responder algumas

hipóteses levantadas e algumas expectativas, como:

Quais os filmes que mais são alugados?

Quais os filmes que menos são alugados?

Quais os clientes que mais alugam?

Quais os clientes que menos alugam?

Quais os tipos de filmes (Gênero) são mais alugados?

Quais os tipos de filmes (Gênero) são menos alugados?

PRODUTO.DBF

ID_Filme

Filme

ID_Genero

Genero

Dubla-Legendado

{DUBLADO, LEGENDADO}

Lançamento {SIM,NÃO}

Em_Promoção {SIM, NÃO}

Final_Semana{SIM, NÃO}

CLIENTE.DBF

ID_Cliente

NOME

Bairro

Cidade

Sexo

MOVPROD.DBF

ID_Cliente

ID_Filme

90

Quais os tipos de filmes são mais assistidos por aqueles que mais

alugam? Eram dublados ou legendados? Eram lançamentos? Estavam na

promoção? Eram finais de semanas quando foram alugados?

Quais os tipos de filmes são mais assistidos por aqueles que menos

alugam? Eram dublados ou legendados? Eram lançamentos? Estavam na

promoção? Eram finais de semanas quando foram alugados?

Quais os bairros que mais alugam filmes?

Quais os bairros que menos alugam filmes?

Em que épocas do ano se alugam mais filmes?

Em que dias da semana se alugam mais filmes?

Em que épocas do ano determinados gêneros são mais alugados?

Quem assiste mais filmes? Homem ou mulher?

Qual a faixa etária do clientes que mais alugam?

Após ter-se levantado essas hipóteses, foi preciso manipular os

novos atributos construídos, enriquecendo-os com informações inerentes.

Porém, ao tentar utilizar e preencher os atributos mostrados na

tabela 5 com informações que pudessem gerar novos conhecimentos,

expectativas e responder algumas hipóteses acima, percebeu-se que não seria

possível por vários motivos.

O principal deles é que o atributo DATAMOV (data da locação do

filme) está totalmente inconsistente, conforme mostra a figura 25, não

permitindo, por exemplo, saber se um filme alugado era lançamento, se estava

em promoção ou se era final de semana, na data de locação, sendo, portanto,

esse atributo, inutilizado por este trabalho de pesquisa, impedindo-se assim,

91

que algumas hipóteses, que dependiam deste atributo, pudessem ser também

respondidas.

ATRIBUTOS REJEITADOS Dubla-Legendado {DUBLADO, LEGENDADO}

Lançamento {SIM,NÃO}

Em_Promoção {SIM, NÃO}

Final_Semana{SIM, NÃO}

Tabela 5: Atributos rejeitados por inconsistência do atributo DATAMOV.

Figura 25: Atributo DATAMOV inconsistente.

Na função de “Enriquecimento dos Dados” foram preenchidos

alguns atributos como SEXO {Masculino, Feminino}, ID_Genero. Foi preciso

trocar todos os espaços “ “ dentro dos atributos por underlines “_”, tirar os

apóstrofe “ „ “ , virgulas “ , ” e outros caracteres indesejados.

92

Figura 26: Base de dados com atributo BAIRRO com “__” e SEXO preenchido.

E por último foi aplicada a “Normalização”, função do Pré-

processamento, para unir os atributos interessantes numa única tabela, a qual

será utilizada no processo de Mineração de dados, após ter passado pela

etapa de Pré-processamento.

Tabela 6: Tabela LOCACAO.DBF normalizada.

ID_Filme

Filme

Genero

ID_Cliente

Bairro

Cidade

Sexo

93

Escolheu-se os atributos na tabela 6 para serem “Minerados” pelo

software WEKA, através da tarefa de Clusterização (cluster), utilizando-se do

algoritmo SimpleK-Means, para tentar responder as hipóteses e expectativas

criadas e principalmente para tentar descobrir novas relações, novos padrões

de comportamentos e novas tendências de locações dentro dos dados.

Conseguindo-se chegar a esses conhecimentos, poder-se-á utilizá-

los em favor da organização, desenvolvendo-se estratégias de marketing ou

mesmo em apoio nas tomadas decisões.

3.3.2 Etapa de Mineração de Dados

Neste trabalho usou-se uma base de dados dividida em vários

arquivos no formato “.DBF”.

Após ter concluído a etapa de Pré-processamento, chegando-se a

base de dados LOCACAO.DBF. Aplica-se a próxima etapa do processo de

KDD que é a Mineração de Dados.

Em várias ocasiões os dados a serem minerados estão disponíveis

em arquivos textos, banco de dados, planilhas, etc.

Como o software WEKA, usado para a etapa de Mineração de

Dados, tem vários algoritmos para a tarefa de Clusterização, dentre eles o

algoritmo SimpleK-Means, precisou-se transformar essa base de dados em um

arquivo no formato “.ARFF”, que é o formato aceito pelo software WEKA.

Segundo Souto (2005), o pacote WEKA (Waikato Environment for

Knowledge Analysis) é formado por um conjunto de implementações de

algoritmos de diversas técnicas de Mineração de Dados. WEKA está

94

implementado na linguagem Java, que tem como principal característica ser

portável. Desta forma pode rodar nas mais variadas plataformas e aproveitando

os benefícios de uma linguagem orientada a objetos como: modularidade,

polimorfismo, encapsulamento, reutilização de código dentre outros, além

disso, é um software de domínio público estando disponível em

http://www.cs.waikato.ac.nz/ml/weka/ .

Segundo Witten e Frank (1999, 2000), os arquivos de entrada de

dados do Weka possui um formato próprio, o “ARFF”, o qual necessita que se

descreva o domínio do atributo, pois o mesmo não pode ser obtido

automaticamente pelo seu valor. Antes de aplicar os dados a qualquer

algoritmo do pacote Weka, estes devem ser convertidos para o formato

“ARFF”, que consiste basicamente de duas partes:

A primeira parte contém uma lista de todos os atributos, onde deve-

se definir o tipo do atributo ou os valores que ele pode representar, quando

utiliza-se os valores, estes devem estar entre “{ }” separados por vírgulas.

A segunda parte consiste nas instâncias, ou seja, os registros a

serem minerados com o valor dos atributos para cada instancia separado por

vírgula, a ausência de um item em um registro deve ser atribuída pelo símbolo

“?”.

Para isso podem-se usar programas de planilhas eletrônicas os

quais permitem exportar os dados em um arquivo onde as vírgulas são os

separadores.

http://www.cs.waikato.ac.nz/ml/weka/

95

Uma vez feito isso, é necessário apenas carregar o arquivo em um

editor de texto e adicionar o nome do conjunto de dados usando “@relation”,

os atributos usando “@attribute” e “@data” com os dados em si, salvando o

arquivo como texto puro com extensão “.ARFF”.

Usou-se um software de planilha eletrônica para abrir arquivo no

formato “.DBF” e em seguida salvá-lo em um formato “.CSV” que possa ser

convertido em ARFF.

A figura 27 é um exemplo de um arquivo no formato “ separado por

vírgula .csv”.

Figura 27: Arquivo no formato “CSV” antes das alterações.

96

A figura 28 é um exemplo de um arquivo no formato “.ARFF”.

Figura 28: Arquivo no formato “ARFF” após as alterações.

O arquivo com extensão “.ARFF” será carregado pelo software

WEKA se seu formato estiver correto, sem nenhum problema interno, seja no

cabeçalho, seja nos dados.

Caso contrário será exibido uma janela de diálogo de erro pedindo

para que se verifique e arrume os erros.

Figura 29: Janela exibindo um erro carregando o arquivo LOCACAO.ARFF.

97

Esta etapa geralmente é bastante trabalhosa, pois se houver um

erro no formato do arquivo ARFF, não será possível prosseguir.

Algumas causas são:

- Ausência de parte do cabeçalho;

- Tipos de dados não aceitos pelo WEKA;

- Um valor ausente entre as chaves “{ }”, mensagem na figura 29;

- Espaços entre os valores de atributos;

- Se os valores forem String, devem vir entre “{ }”

- Valores duplicados entre “{ }”

- Presença de ruído (outliers) como apóstrofos ” „ “ , virgulas “ , “

entre os valores, sinal de porcentagem “ % “, e outros.

Após solucionar todos os problemas, o WEKA finalmente carrega o

arquivo.

Figura 30: Carregando o arquivo LOCACAO.ARFF.

98

Na janela principal do WEKA deve-se verificar se o arquivo foi

carregado corretamente. Para isso confere-se os valores que aparecem na

página principal do WEKA correspondem aos valores da planilha original.

Observe a opção Current relation, temos o nome da relação,

quantidade de instâncias (registros) e quantidade de atributos (campos),

No lado esquerdo abaixo se encontra a lista de atributos que

carregamos.

No lado direito encontra-se o atributo selecionado e abaixo um

gráfico.

Depois de lidos os dados pelo software é preciso escolher qual

tarefa usar e qual algoritmo será aplicado na tarefa.

Clique na guia Cluster;

Em seguida clique no botão Choose;

Estão disponíveis os seguintes algoritmos de Clusterização:

- COBWEB;

- EM;

- FARTHERSTFIRST

- MAKEDENSITYBASEDCLUSTER; e

- SMPLEKMEANS

Na lista de opções, clique em SimpleK-Means. Este é o algoritmo a

ser aplicado na Mineração de Dados.

99

Clique na frente do botão Choose, sobre o nome do algoritmo

escolhido e especifique o número de clusters (N – o número de clusters) e o

número de sementes (seed), conforme figura 31;

Em seguida clique Ok.

Figura 31: Escolhendo o número de clusters e o número de sementes.

Segundo Witten e Frank (2000), é necessário especificar um número

de clusters que o algoritmo deverá encontrar na Mineração de Dados e Seed

(semente), que corresponde ao número de registros que o algoritmo escolherá

aleatoriamente para iniciar o processo de Clusterização. Eles serão os

centróides iniciais, a partir dos quais serão realizados cálculos de distância e

similaridade que permitirão ao algoritmo agrupar (clustering) um registro em um

determinado cluster.

Na área de “Cluster Mode” clique em “Use training set” para que o

WEKA use o arquivo ARFF no treinar do algoritmo, ou seja, na mineração de

dados ou Clusterização (Clustering);

A opção Ignore Attributes pode ser usada para selecionar atributos e

estes não participarão da Clusterização;

Clica-se no botão Start para iniciar a Clusterização. O resultado

aparecerá em seguida do lado direito da tela, conforme mostra a figura 32.

100

A figura 32 representa um exemplo do resultado da Mineração de

Dados em sua forma natural, ou seja, do jeito que o software WEKA o

representa.

Percebe-se que o resultado não é tão fácil de ser interpretado.

Cabe ao especialista de KDD transformá-lo, usando a etapa de Pós-

processamento, que abrange o tratamento do conhecimento obtido, alterando a

forma de exibição para que fique mais claro e que tenha melhor leitura,

gerando gráficos se necessário, tendo como objetivo facilitar para o

especialista no Domínio da Aplicação, a interpretação e a avaliação da utilidade

do conhecimento descoberto. É nesta etapa que o especialista em KDD e o

especialista no Domínio da Aplicação avaliam os resultados obtidos e fazem

suas interpretações.

Figura 32: Exemplo de como o software WEKA representa o Modelo de Conhecimento.

101

3.3.2.1 Testes realizados sobre a Base de Dados

Utilizando-se do algoritmo SimpleK-Means através do Software

WEKA, uma base de dados chamada LOCACAO.ARFF e os atributos

(ID_Filme, Gênero, ID_Cliente, Bairro, Cidade, Sexo), com

suas instâncias (64.518 Registros), realizou-se os seguintes testes:

Nº DO TESTE Nº DE CLUSTERS Nº DE SEEDS

T1 2 10

T2 2 10

T3 10 10

T4 10 20

T5 4 10

T6 20 50

T7 10 5

T8 13 30

T9 30 100

T10 30 200

T11 5 100

T12 30 50

T13 5 200

T14 100 500

Tabela 7: Testes realizados com N Clusters e N Seeds.

Após aplicar várias vezes o algoritmo SimpleK-Means sobre a base

de dados LOCACAO.ARFF, utilizando-se de combinações de N clusters e de N

sementes (Seed), conforme mostra a tabela 7, e após o tratamento do Modelos

de conhecimentos pelo especialista de KDD, obteve-se os seguintes

resultados:

OBS.: Cluster é o grupo formado na Mineração de

Dados.

102

TESTE T1 Neste teste 2 clusters foram gerados e observa-se que: o gênero AÇÃO e

DESENHO são mais alugados por quem mora no CENTRO e seja do sexo

MASCULINO.

Atributos: 6

Usados: Genero

Bairro

Cidade

Sexo

Ignorados:

ID_Filme

ID_Cliente

CLUSTERIZAÇÃO GENERO, BAIRRO, CIDADE, SEXO, Nº LOCAÇÕES (%)

Cluster 0

Mean/Mode: ACAO CENTRO POTIM MASCULINO, 57758 ( 90%)

Cluster 1

Mean/Mode: DESENHO CENTRO POTIM MASCULINO, 6760 ( 10%)

Tabela 8: Resultado do teste T1 apresentado pelo WEKA.

TESTE T2 Neste teste há 2 clusters e descobriu-se quantos filmes foram alugados por

SEXO e as respectivas porcentagens .

CLUSTERIZAÇÃO SEXO, Nº LOCAÇÕES (%)

Cluster 0 Mean/Mode: MASCULINO 46081 ( 71%)

Cluster 1 Mean/Mode: FEMININO 18437 ( 29%)


103

TESTE T3 Neste teste 10 clusters foram gerados, conclui-se que:

Os gêneros suspense e ação são mais alugados por quem mora no centro e

seja do sexo masculino.

Attributos Ignorados:

ID_Filme

ID_Cliente

CLUSTERIZAÇÃO OBTIDA GENERO, BAIRRO, CIDADE, SEXO, Nº LOCAÇÕES (%)

Cluster 0 Mean/Mode: SUSPENSE CENTRO POTIM MASCULINO, 14847 ( 23%)

Cluster 1 Mean/Mode: DESENHO CENTRO POTIM MASCULINO, 6648 ( 10%)

Cluster 2 Mean/Mode: COMEDIA CENTRO POTIM MASCULINO, 7411 ( 11%)

Cluster 3 Mean/Mode: AVENTURA CENTRO POTIM MASCULINO, 7584 ( 12%)

Cluster 4 Mean/Mode: ACAO VISTA_ALEGRE POTIM MASCULINO, 5479 ( 8%)

Cluster 5 Mean/Mode: ACAO CENTRO POTIM MASCULINO, 12672 ( 20%)

Cluster 6 Mean/Mode: DRAMA CENTRO POTIM MASCULINO, 1566 ( 2%)

Cluster 7 Mean/Mode: TERROR CENTRO POTIM MASCULINO, 3362 ( 5%)

Cluster 8 Mean/Mode: PORNO CENTRO POTIM FEMININO, 3229 ( 5%)

Cluster 9 Mean/Mode: PORNO M_DOS_MARQUES POTIM MASCULINO, 1720 ( 3%)


Teste T4

Neste: 2 cluster indicam que quem mora na cidade de Aparecida aluga o

gênero TERROR e AÇÃO, e a maioria são Homem.

Quem mora no CENTRO de Potim assistem mais filmes AÇÃO.

104


Cluster 0 Mean/Mode: TERROR CENTRO APARECIDA MASCULINO, 4321 ( 7%)


Cluster 2 Mean/Mode: JOGO CENTRO POTIM MASCULINO, 494 ( 1%)

Cluster 3 Mean/Mode: BIBLICO CENTRO POTIM MASCULINO, 191 ( 0%)

Cluster 4 Mean/Mode: ACAO M_DOS_MARQUES POTIM MASCULINO, 3449 ( 5%)

Cluster 5 Mean/Mode: PORNO CENTRO POTIM MASCULINO, 5567 ( 9%)


Cluster 7 Mean/Mode: ACAO CENTRO POTIM FEMININO, 13558 ( 21%)


Cluster 9 Mean/Mode: ACAO JD_PARAIBA APARECIDA MASCULINO, 1883 (3%)


TESTE T5

A cidade onde tem a locadora, obviamente tem mais clientes, porém cidades

vizinhas costumam alugar filmes. Por quê? É um perfil a ser explorado.

Uma provável resposta seria: o bairro destes clientes de outra cidade não tem

locadora e é mais próximo. Outra resposta seria: a locadora fica no caminho de

transição destes clientes.

CLUSTERIZAÇÃO OBTIDA CIDADE, Nº LOCAÇÕES (%)

Cluster 0 Mean/Mode: POTIM, 59953 ( 93%)

Cluster 1 Mean/Mode: APARECIDA, 4108 ( 6%)

Cluster 2 Mean/Mode: GUARATINGUETA, 452 ( 1%)

Cluster 3 Mean/Mode: ROSEIRA, 5 ( 0%)


105

TESTE T6 Neste teste, o bairro que mais aluga filmes é o CENTRO com (47%), onde o

gênero mais alugado é AÇÃO, sendo (31%) Homens e (16%) Mulheres.

Alguns gêneros são pouco procurados. Pode-se incentivar o aluguel de filmes

de GUERRA, ROMANCE, POLICIAL e outros através de promoções, por

exemplo.




Cluster 2 Mean/Mode: ACAO CENTRO POTIM FEMININO10106 ( 16%)

Cluster 3 Mean/Mode: TERROR CENTRO POTIM MASCULINO, 2374 ( 4%)

Cluster 4 Mean/Mode: PORNO M_DOS_MARQUES POTIM MASCULINO, 2538 ( 4%)

Cluster 5 Mean/Mode: PORNO CENTRO POTIM MASCULINO, 3429 ( 5%)

Cluster 6 Mean/Mode: DESENHO M_DOS_MARQUES POTIM MASCULINO, 1070 ( 2%)

Cluster 7 Mean/Mode: DESENHO CENTRO POTIM FEMININO, 2231 ( 3%)

Cluster 8 Mean/Mode: PORNO CENTRO POTIM FEMININO, 1362 ( 2%)

Cluster 9 Mean/Mode: SUSPENSE M_DOS_MARQUES POTIM MASCULINO, 1574 ( 2%)

Cluster 10 Mean/Mode: GUERRA CENTRO POTIM MASCULINO, 661 ( 1%)

Cluster 11 Mean/Mode: COMEDIA CENTRO POTIM FEMININO, 2227 ( 3%)

Cluster 12 Mean/Mode: AVENTURA ALVORADA POTIM MASCULINO, 1504 ( 2%)



Cluster 15 Mean/Mode: DESENHO BARRANCO_ALTO POTIM MASCULINO, 248 ( 0%)

Cluster 16 Mean/Mode: ROMANCE ALVORADA POTIM MASCULINO, 167 ( 0%)

Cluster 17 Mean/Mode: POLICIAL CENTRO POTIM MASCULINO, 241 ( 0%)

Cluster 18 Mode: COMEDIA CHACARA_TROPICAL POTIM MASCULINO, 102 (0%)

Cluster 19 Mean/Mode: SUSPENSE CENTRO POTIM FEMININO, 2180 ( 3%)


106

TESTE T7 Mulheres de POTIM alugam mais SUSPENSE e Homens, mais AÇÃO.

Atributos Ignorados:

ID_Filme

ID_Cliente

CLUSTERIZAÇÃO OBTIDA GENERO, BAIRRO, CIDADE, SEXO, Nº LOCAÇÕES(%)


Cluster 1 Mean/Mode: ACAO ALVORADA POTIM MASCULINO 2308 ( 4%)

Cluster 2 Mode: DESENHO PONTE_ALTA APARECIDA FEMININO, 1674 (3%)

Cluster 3 Mean/Mode: SUSPENSE CENTRO POTIM FEMININO, 7507 ( 13%)

Cluster 4 Mean/Mode: AVENTURA CENTRO POTIM FEMININO, 1891 ( 3%)

Cluster 5 Mean/Mode: DRAMA CENTRO POTIM MASCULINO, 963 ( 2%)

Cluster 6 Mode: COMEDIA VILA_SAO_JOSE POTIM FEMININO, 558 ( 1%)


Cluster 8 Mean/Mode: COMEDIA CENTRO POTIM FEMININO, 1579 ( 3%)



TESTE T8 Os gêneros de filmes mais alugados por clientes que mais alugam são: AÇÃO

(26%), SUSPENSE (18%), AVENTURA (12%), COMÉDIA (12%) e DESENHO

(11%).

Atributos: Ignorados:

ID_Filme

Bairro

Cidade

Sexo

107

CLUSTERIZAÇÃO OBTIDA GENERO, ID_CLIENTE, Nº LOCAÇÕES (%)

Cluster 0 Mean/Mode: SUSPENSE 2004, 11900 ( 18%)

Cluster 1 Mean/Mode: DESENHO 2362, 6809 ( 11%)

Cluster 2 Mean/Mode: COMEDIA 1643, 7575 ( 12%)

Cluster 3 Mean/Mode: AVENTURA 497, 7603 ( 12%)

Cluster 4 Mean/Mode: ACAO 84 , 17074 ( 26%)

Cluster 5 Mean/Mode: ACAO 2004, 121 ( 0%)

Cluster 6 Mean/Mode: DRAMA 2318, 1588 ( 2%)

Cluster 7 Mean/Mode: RELIGIOSO 1253, 190 ( 0%)

Cluster 8 Mean/Mode: TERROR 2423, 3446 ( 5%)

Cluster 9 Mean/Mode: PORNO 1068, 6330 ( 10%)



Cluster 12 Mean/Mode: AVENTURA 855, 55 ( 0%)


Após vários experimentos de Mineração de dados sobre a base de

dados de uma Locadora de Vídeo, passou-se a ter mais atenção nos

resultados onde as porcentagens (%) são menos significativas, pois podem

sugerir pontos fracos de uma locadora à serem estudados e melhorados ou

talvez nichos à serem explorados, já que as porcentagens (%) mais

expressivas, ao serem observadas, representam o óbvio e muitas vezes

repetitivas, não acrescentando nenhum novo conhecimento.

Por isso, deste ponto de teste em diante as menores porcentagens

(%) são observadas com mais atenção, não descartando as maiores.

108

TESTE T9

Nesta mineração de dados observou-se que:

Homens alugam pouco gênero COMÉDIA= 65 vezes (0%).

Mulheres alugam pouco gênero TERROR =1167 vezes (2%).

Homens alugam pouco gênero INFANTIL = 151 vezes (0%).

Mulheres alugam pouco gênero ERÓTICO= 150 vezes (0%).

Homens alugam pouco gênero SUSPENSE = 411 vezes (1%).

Homens alugam pouco gênero DESENHO = 299 vezes (0%).

Mulheres alugam pouco gênero AÇÃO= 121 vezes (0%).

CLUSTERIZAÇÃO ID_FILME, GENERO, ID_CLIENTE, BAIRRO, CIDADE, SEXO,NºLOCAÇÕES(%)

Cluster 0

Mode: 668 SUSPENSE 2207 M_DOS_MARQUES POTIM MASCULINO, 2952 (5%)

Cluster 1

Mean/Mode: 2153 ACAO 2202 CENTRO POTIM FEMININO, 10325 ( 18%)

Cluster 2

Mean/Mode: 2956 COMEDIA 2512 CENTRO POTIM MASCULINO, 7800 ( 13%)

Cluster 3

Mean/Mode: 2930 ACAO 1309 M_DOS_MARQUES POTIM MASCULINO, 2173 ( 4%)

Cluster 4


Cluster 5

Mean/Mode: 431 ACAO 900 JD_PARAIBA APARECIDA MASCULINO, 2445 ( 4%)

Cluster 6

Mean/Mode: 2235 TERROR 1030 CENTRO POTIM FEMININO, 1167 ( 2%)

Cluster 7

Mode: 49 ACAO 1672 BAIRRO_DOS_VIEIRAS POTIM MASCULINO, 393 ( 1%)

Cluster 8

Mean/Mode: 211 DESENHO 1919 CENTRO POTIM FEMININO, 2043 ( 4%)

Cluster 9

Mean/Mode: 1244 AVENTURA 379 CENTRO POTIM MASCULINO, 4206 ( 7%)

Cluster 10

Mean/Mode: 1188 AVENTURA 183 ALVORADA POTIM MASCULINO, 921 ( 2%)

Cluster 11

Mean/Mode: 2945 ACAO 1187 ALVORADA POTIM MASCULINO, 500 ( 1%)

Cluster 12

Mean/Mode: 400 SUSPENSE 1940 CENTRO POTIM MASCULINO, 3184 ( 5%)

Cluster 13

Mean/Mode: 211 AÇÃO 1340 CENTRO POTIM MASCULINO, 3252 ( 6%)

Cluster 14

Mean/Mode: 2013 INFANTIL 2755 ALVORADA POTIM MASCULINO, 151 ( 0%)

Cluster 15

Mean/Mode: 422 EROTICO 2189 CENTRO POTIM FEMININO, 150 ( 0%)

Cluster 16

Mean/Mode: 2945 ACAO 546 CENTRO POTIM MASCULINO, 7300 ( 13%)

Cluster 17

Mean/Mode: 1188 AVENTURA 99 CENTRO POTIM FEMININO, 1754 ( 3%)

Cluster 18

Mean/Mode: 1 PORNO 1225 VISTA_ALEGRE POTIM MASCULINO, 773 ( 1%)

Cluster 19

Mode: 264 SUSPENSE 2093 SANTA_RITA APARECIDA MASCULINO, 411 ( 1%)

Cluster 20


Cluster 21

Mean/Mode: 706 PORNO 788 M_DOS_MARQUES POTIM MASCULINO, 623 ( 1%)

Cluster 22

Mode: 2318 ACAO 1561 BAIRRO_DOS_VIEIRAS POTIM FEMININO, 121 ( 0%)

109

Cluster 24

Mean/Mode: 2285 DESENHO 2561 CENTRO POTIM MASCULINO, 89 ( 0%)

Cluster 25

Mean/Mode: 6030 TERROR 2506 CENTRO POTIM MASCULINO, 4 ( 0%)

Cluster 26

Mode: 2899 DESENHO 2622 M_DOS_MARQUES POTIM MASCULINO, 210 ( 0%)

Cluster 27


Cluster 28

1484 PORNO 2197 PQ_SAO_FRANCISCO GUARATINGUETA MASCULINO, 205 ( 0%)

Cluster 29

Mean/Mode: 2386 PORNO 1068 CENTRO POTIM MASCULINO, 2965 ( 5%)


TESTE 10

Nesta mineração de dados observou-se que alguns bairros fazem poucas

locações, necessitando, portanto que se intensifique o Market nestes bairros.

Observou-se também que alguns gêneros são pouco alugados como, por

exemplo: INFANTIL, DRAMA, FAROESTE, BÍBLICO, CLIPES, ROMANCE,

FICÇÃO.

Sugestão: poderia ser feito uma grande promoção com esses tipos de filmes e

diminuir a compra destes gêneros.


Cluster 0

Mean/Mode: SUSPENSE M_DOS_MARQUES POTIM MASCULINO, 2347 ( 4%)

Cluster 1

Mean/Mode: ACAO CENTRO POTIM FEMININO, 10358 ( 18%)

Cluster 2

Mean/Mode: COMEDIA CENTRO POTIM MASCULINO, 7501 ( 13%)

Cluster 3

Mean/Mode: ACAO M_DOS_MARQUES POTIM MASCULINO, 1811 ( 3%)

Cluster 4

Mean/Mode: ACAO JD_PARAIBA APARECIDA MASCULINO, 1892 ( 3%)

Cluster 5

Mean/Mode: TERROR CENTRO POTIM FEMININO, 975 ( 2%)

Cluster 6

Mean/Mode: ACAO BAIRRO_DOS_VIEIRAS POTIM MASCULINO, 384 ( 1%)

Cluster 7

Mean/Mode: DESENHO CENTRO POTIM FEMININO, 2021 ( 3%)

Cluster 8

Mean/Mode: AVENTURA CENTRO POTIM MASCULINO, 3964 ( 7%)

Cluster 9

Mean/Mode: AVENTURA ALVORADA POTIM MASCULINO, 952 ( 2%)

Cluster 10

Mean/Mode: ACAO ALVORADA POTIM MASCULINO, 471 ( 1%)

Cluster 11

Mean/Mode: SUSPENSE CENTRO POTIM MASCULINO, 3106 ( 5%)

Cluster 12


110

Cluster 13

Mean/Mode: INFANTIL ALVORADA POTIM MASCULINO, 94 ( 0%)

Cluster 14

Mean/Mode: EROTICO CENTRO POTIM FEMININO, 107 ( 0%)

Cluster 15

Mean/Mode: AVENTURA CENTRO POTIM FEMININO, 1871 ( 3%)

Cluster 16

Mean/Mode: PORNO VISTA_ALEGRE POTIM MASCULINO, 764 ( 1%)

Cluster 17

Mean/Mode: SUSPENSE SANTA_RITA APARECIDA MASCULINO, 374 ( 1%)

Cluster 18


Cluster 19

Mean/Mode: PORNO M_DOS_MARQUES POTIM MASCULINO, 487 ( 1%)

Cluster 20

Mean/Mode: ACAO BAIRRO_DOS_VIEIRAS POTIM FEMININO, 103 ( 0%)

Cluster 21

Mean/Mode: TERROR CENTRO POTIM MASCULINO, 1650 ( 3%)

Cluster 22

Mode: PORNO PARQUE_SAO_FRANCISCO GUARATINGUETA MASCULINO, 206 (0%)

Cluster 23

Mean/Mode: PORNO CENTRO POTIM MASCULINO, 3068 ( 5%)

Cluster 24

Mean/Mode: PORNO JD_PARAIBA APARECIDA MASCULINO, 403 ( 1%)

Cluster 25

Mean/Mode: AVENTURA M_DOS_MARQUES POTIM MASCULINO, 316 ( 1%)

Cluster 26

Mean/Mode: COMEDIA ALVORADA POTIM MASCULINO, 287 ( 0%)

Cluster 27

Mean/Mode: ACAO CHACARA_TROPICAL POTIM MASCULINO, 229 ( 0%)

Cluster 28

Mean/Mode: COMEDIA PONTE_ALTA APARECIDA MASCULINO, 550 ( 1%)

Cluster 29

Mean/Mode: COMEDIA M_DOS_MARQUES POTIM MASCULINO, 364 ( 1%)


TESTE T11 Nesta mineração de dados observou-se que:

Mulheres alugam pouco TERROR= 1096 vezes (2%) e pouco COMÉDIA =

2227 vezes (3%), em relação à outros gêneros.

CLUSTERIZAÇÃO GENERO, SEXO, Nº LOCAÇÕES (%)

Cluster 0

Mean/Mode: ACAO FEMININO, 15114 ( 23%)

Cluster 1

Mean/Mode: ACAO MASCULINO, 40920 ( 63%)

Cluster 2

Mean/Mode: TERROR FEMININO, 1096 ( 2%)

Cluster 3

Mean/Mode: COMEDIA FEMININO, 2227 ( 3%)

Cluster 4

Mean/Mode: PORNO MASCULINO, 5161 ( 8%)


111

TESTE 12

Aparecida é a cidade vizinha com clientes que mais alugam filmes. Talvez pelo

fato de que o bairro JD_PARAIBA ser mais próximo de Potim.

Verificou-se quais gêneros mais e menos alugados por bairros periféricos, ou

seja, excluindo-se o bairro centro desta pesquisa.

Observou-se que nos bairros periféricos o gênero AVENTURA é o mais

alugado, diferente do bairro CENTRO, onde AÇÃO é o mais alugado, mostrado

nos clusters 0 e 4. Outro fato interessante é que o gênero COMÉDIA não tem

locações nos bairros periféricos, mas somente num bairro de outra cidade.

O gênero DRAMA e outros nem aparecem nos bairros periféricos.


Cluster 0


Cluster 1

Mean/Mode: TERROR CENTRO POTIM MASCULINO, 2742 ( 5%)

Cluster 2

Mean/Mode: COMEDIA CENTRO POTIM MASCULINO, 6133 ( 11%)

Cluster 3

Mean/Mode: AVENTURA ALVORADA POTIM MASCULINO, 2468 ( 4%)

Cluster 4

Mean/Mode: ACAO CENTRO POTIM FEMININO, 10448 ( 18%)

Cluster 5

Mean/Mode: PORNO CENTRO POTIM MASCULINO, 4359 ( 8%)

Cluster 6


Cluster 7

Mean/Mode: SUSPENSE M_DOS_MARQUES POTIM MASCULINO, 1342 ( 2%)

Cluster 8

Mean/Mode: ACAO BARRANCO_ALTO POTIM MASCULINO, 338 ( 1%)

Cluster 9

Mean/Mode: ACAO VISTA_ALEGRE POTIM FEMININO, 347 ( 1%)

Cluster 10

Mean/Mode: ROMANCE CENTRO POTIM MASCULINO, 463 ( 1%)

Cluster 11

Mean/Mode: DESENHO CENTRO POTIM FEMININO, 2048 ( 4%)

Cluster 12

Mean/Mode: POLICIAL VISTA_ALEGRE POTIM FEMININO, 29 ( 0%)

Cluster 13

Mean/Mode: AVENTURA CENTRO POTIM MASCULINO, 3433 ( 6%)

Cluster 14

Mean/Mode: EROTICO CENTRO POTIM MASCULINO, 336 ( 1%)

Cluster 15

Mean/Mode: INFANTIL M_DOS_MARQUES POTIM MASCULINO, 87 ( 0%)

Cluster 16

Mean/Mode: TERROR ALVORADA POTIM FEMININO, 638 ( 1%)

112

Cluster 17

Mean/Mode: ACAO BAIRRO_DOS_VIEIRAS POTIM MASCULINO, 160 ( 0%)

Cluster 18

Mean/Mode: DESENHO VISTA_ALEGRE POTIM MASCULINO, 250 ( 0%)

Cluster 19

Mean/Mode: ACAO VILA_SAO_JOSE POTIM MASCULINO, 243 ( 0%)

Cluster 20

Mean/Mode: DESENHO BARRANCO_ALTO POTIM MASCULINO, 136 ( 0%)

Cluster 21

Mean/Mode: SUSPENSE CENTRO POTIM MASCULINO, 3106 ( 5%)

Cluster 22

Mean/Mode: ROMANCE VISTA_ALEGRE POTIM MASCULINO, 20 ( 0%)

Cluster 23

Mean/Mode: DRAMA CENTRO POTIM MASCULINO, 842 ( 1%)

Cluster 24

Mean/Mode: TERROR BARRANCO_ALTO POTIM MASCULINO, 41 ( 0%)

Cluster 25

Mean/Mode: CLIPES CENTRO POTIM MASCULINO, 162 ( 0%)

Cluster 26

Mean/Mode: ACAO CHACARA_TROPICAL POTIM MASCULINO, 211 ( 0%)

Cluster 27

Mean/Mode: COMEDIA JD_PARAIBA APARECIDA MASCULINO, 1415 ( 2%)

Cluster 28

Mean/Mode: JOGO FREI_GALVAO POTIM MASCULINO, 50 ( 0%)

Cluster 29

Mean/Mode: SUSPENSE FAZENDA POTIM MASCULINO, 29 ( 0%)


TESTE T13 Nesta mineração de dados observou-se que: o gênero RELIGIOSO é muito

pouco alugado por Homens.

Sugestão: comprar menos gêneros RELIGIOSOS.

CLUSTERIZAÇÃO GENERO, SEXO, Nº LOCAÇÕES (%)

Cluster 0

Mean/Mode: ACAO MASCULINO, 40405 ( 63%)

Cluster 1

Mean/Mode: COMEDIA MASCULINO, 7411 ( 11%)

Cluster 2

Mean/Mode: RELIGIOSO MASCULINO, 177 ( 0%)

Cluster 3

Mean/Mode: DESENHO FEMININO, 11547 ( 18%)

Cluster 4

Mean/Mode: SUSPENSE MASCULINO, 4978 ( 8%)


113

Teste T14

Observou-se que o gênero DRAMA só foi assistido por quem mora no Centro,

sendo que Mulheres alugaram 1773 vezes o gênero DRAMA, (3%) das locações e

Homens alugaram 792 vezes o gênero DRAMA, (1%) das locações.

Confirmando-se o que alguns autores afirmaram, observou-se que o algoritmo

SimpleK-Means, usado nesta pesquisa, apresentou-se sensível a grande dimensões,

ou seja, muitos atributos sendo utilizados ao mesmo tempo na Mineração de Dados.

Isto pode ser observado no Teste T14, onde o cluster 65 com o cliente 788, da coluna

três, indica ter 503 locações, sendo que na realidade ele fez 340, conforme Tabela 22.

Sendo assim não é confiável fazer mais observações neste Teste T14.

Constata-se, portanto que é imprescindível a presença de um especialista no

Domínio da Aplicação para escolher os atributos ideais para cada mineração de

dados.

CLUSTERIZAÇÃO ID_FILME, GENERO, ID_CLIENTE, BAIRRO, CIDADE, SEXO,NºLOCAÇÕES(%)

Cluster 0

Mode: 2863 ACAO 1616 VISTA_ALEGRE POTIM MASCULINO, 3294 ( 5%)

Cluster 1


Cluster 2


Cluster 3

Mean/Mode: 61 RELIGIOSO 866 CENTRO POTIM MASCULINO, 204 ( 0%)

Cluster 4

Mode: 2876 DESENHO 900 JD_PARAIBA APARECIDA FEMININO, 1106 ( 2%)

Cluster 5

Mode: 668 SUSPENSE 2349 M_DOS_MARQUES POTIM MASCULINO, 1519 ( 2%)

Cluster 6

Mean/Mode: 1383 DRAMA 2169 CENTRO POTIM FEMININO, 1773 ( 3%)

Cluster 7

Mode: 1933 AVENTURA 1577 M_DOS_MARQUES POTIM MASCULINO, 1102 ( 2%)

Cluster 8

Mode: 1272 TERROR 2487 M_DOS_MARQUES POTIM MASCULINO, 655 ( 1%)

Cluster 9


Cluster 10


Cluster 11

Mode: 2235 TERROR 2423 CHACARA_TROPICAL POTIM FEMININO, 402 ( 1%)

Cluster 12


Cluster 13


Cluster 14


Cluster 15


Cluster 16

114


Cluster 17


Cluster 18

Mode: 1207 PORNO 715 PONTE_ALTA APARECIDA MASCULINO, 1115 ( 2%)

Cluster 19

Mode: 483 COMEDIA 2652 FREI_GALVAO POTIM MASCULINO, 182 ( 0%)

Cluster 20


Cluster 21


Cluster 22

Mode: 2220 COMEDIA 1610 VILA_SAO_JOSE POTIM FEMININO, 484 ( 1%)

Cluster 23

Mode: 2930 ACAO 2093 PONTE_ALTA APARECIDA MASCULINO, 869 (1%)

Cluster 24


Cluster 25


Cluster 26

Mode: 1188 AVENTURA 2155 SANTA_RITA APARECIDA FEMININO, 127 ( 0%)

Cluster 27


Cluster 28


Cluster 29

Mean/Mode: 2220 COMEDIA 2102 CENTRO POTIM FEMININO, 1710 ( 3%)

Cluster 30


Cluster 31

Mean/Mode: 2930 ACAO 33 ALVORADA POTIM MASCULINO, 783 ( 1%)

Cluster 32


Cluster 33


Cluster 34


Cluster 35


Cluster 36


Cluster 37

Mean/Mode: 133 PORNO 484 CENTRO POTIM FEMININO, 1190 ( 2%)

Cluster 38

Mean/Mode: 3009 SUSPENSE 2379 ALVORADA POTIM MASCULINO, 292 ( 0%)

Cluster 39


Cluster 40

Mode: 400 SUSPENSE 1714 BARRANCO_ALTO POTIM FEMININO, 338 ( 1%)

Cluster 41


Cluster 42


Cluster 43


Cluster 44


Cluster 45

Mean/Mode: 1383 POLICIAL 1850 CENTRO POTIM MASCULINO, 254 ( 0%)

Cluster 46

Mean/Mode: 2967 ACAO 2202 ALVORADA POTIM FEMININO, 789 ( 1%)

Cluster 47


Cluster 48


Cluster 49


Cluster 50


Cluster 51


Cluster 52


Cluster 53


Cluster 54


115

Cluster 55

Mean/Mode: 1073 SUSPENSE 1000 ALVORADA POTIM FEMININO, 120 ( 0%)

Cluster 56


Cluster 57


Cluster 58

Mean/Mode: 668 SUSPENSE 1030 CENTRO POTIM FEMININO, 1486 ( 2%)

Cluster 59


Cluster 60


Cluster 61

Mean/Mode: 2008 AVENTURA 1229 ALVORADA POTIM FEMININO, 87 ( 0%)

Cluster 62

Mean/Mode: 2981 ACAO 1618 SANTA_CRUZ POTIM MASCULINO, 79 ( 0%)

Cluster 63

Mode: 2859 GUERRA 2111 VILA_SAO_JOSE POTIM FEMININO, 89 ( 0%)

Cluster 64


Cluster 65

Mode: 2567 PORNO 788 M_DOS_MARQUES POTIM MASCULINO, 503 ( 1%)

Cluster 66


Cluster 67


Cluster 68


Cluster 69

Mode: 197 COMEDIA 1577 BARRANCO_ALTO POTIM MASCULINO, 308 ( 0%)

Cluster 70

Mean/Mode: 10031 JOGO 1065 CENTRO POTIM MASCULINO, 249 ( 0%)

Cluster 71


Cluster 72


Cluster 73

Mean/Mode: 1001 CLIPES 916 CENTRO POTIM FEMININO, 103 ( 0%)

Cluster 74

Mean/Mode: 587 ACAO 2024 BARRANCO_ALTO POTIM MASCULINO, 268 ( 0%)

Cluster 75


Cluster 76

Mean/Mode: 1207 DRAMA 118 CENTRO POTIM MASCULINO, 792 ( 1%)

Cluster 77


Cluster 78


Cluster 79


Cluster 80

Mean/Mode: 1197 TERROR 1813 ALVORADA POTIM FEMININO, 70 ( 0%)

Cluster 81


Cluster 82


Cluster 83


Cluster 84


Cluster 85


Cluster 86

Mean/Mode: 1929 INFANTIL 809 CENTRO POTIM MASCULINO, 398 ( 1%)

Cluster 87


Cluster 88


Cluster 89


Cluster 90


Cluster 91


Cluster 92


Cluster 93

116


Cluster 94


Cluster 95

Mean/Mode: 174 CLIPES 307 CENTRO POTIM MASCULINO, 170 ( 0%)

Cluster 96


Cluster 97


Cluster 98


Cluster 99

Mode: 760 COMEDIA 2093 SANTA_RITA APARECIDA MASCULINO, 292 ( 0%) Tabela 21: Resultado do teste T14 apresentado pelo WEKA.

3.3.3 Etapa de Pós-processamento

Segundo Fayyad et al. (1996); Goldschmidt e Passos (2005) é nesta

etapa que abrange o tratamento do conhecimento obtido na Mineração de Dados

e tem como objetivo explicar os resultados e facilitar, para o homem, a

interpretação e a avaliação da utilidade do conhecimento descoberto . Em geral é

nesta etapa que o especialista em KDD e o especialista no Domínio da Aplicação

avaliam os resultados obtidos e definem novas alternativas de investigação dos

dados.

3.3.3.1 Respondendo as Hipóteses e Explicando os Resultados

Quais Filmes foram mais alugados? Quantas vezes?

Figura 33: Os 15 Filmes mais alugados com base nos testes realizados no Weka.

Filmes mais alugados

590

489

378

325

321

309307304

288

287

282

277

271

265 265

HOMEM ARANHA

O SENHOR DOS ANEIS

HARRY POTTER E A PEDRA

FILOSOFAL

O ESCORPIAÃO REI

BLADE 2

VELOZES E FURIOSOS

TRIPLO X

BEIJO DO DRAGÃO

A INTERPRETE

XUXA E OS DUENDES

SCOOBY DOO

EFEITO COLATERAL

JASON

HOMEM ARANHA II

A ERA DO GELO

117

Quais Filmes foram menos alugados? Quantas vezes?

Figura 34: Alguns Filmes menos alugados com base nos testes realizados no Weka.

O WEKA apresenta a relação dos gêneros e o nº de vezes que

foram alugados.

Figura 35: Gêneros de filmes apresentado pelo WEKA.

Filmes menos alugados

3

9

1

19

12

4 2

A BATALHA DE RIDD

TERRORISMO EMATLANTA

A PRINCESA

NAPOLEÃO

FILADELPHIA

MARIO WORLDSUPER

MAKING OF SEXY

118

Quais os clientes que mais alugam filmes?

Colocação ID_Cliente Nº de Locações

1 788 340

2 2004 336

3 1643 334

4 497 315

5 1361 304

6 638 286

7 1612 282

8 1340 269

9 2202 262

10 855 259

11 1125 252

12 2362 252

13 2169 251

14 84 244

15 1616 240

16 2349 234

17 355 225

18 2487 219

19 1030 216

20 2333 216

21 1614 215

22 1935 214

23 1740 211

24 379 208

25 226 207

26 1577 207

27 484 206

28 917 203

29 1068 202

30 2423 202

31 1542 198

32 2093 198

33 2288 191

34 1750 190

35 1777 187

36 83 185

37 900 183

38 630 182

39 799 180

40 347 177

41 2267 176

42 2400 176

43 753 172

44 616 169

45 1919 169

46 87 168

47 732 166

48 809 166

49 1539 165

50 2281 165

Tabela 22: Colocação dos clientes que mais alugam filmes, segundo WEKA.

119

Quais os clientes que menos alugam filmes?

Colocação ID_Cliente Nº de Locações

1 3831 1

2 73 2

3 420 3

4 409 4

5 29 5

6 3146 5

7 97 6

8 3051 6

9 62 7

10 247 8

11 333 9

12 1983 9

13 39 10

14 36 11

15 861 12

16 2434 12

17 70 13

18 2786 13

19 536 14

20 1510 14

21 265 15

22 2710 15

23 2439 16

24 2380 17

25 1203 18

26 136 19

27 2464 19

28 1378 20

29 2467 20

30 253 21

31 802 21

32 2624 21

33 977 22

34 234 23

35 1408 23

36 843 24

36 794 25

38 448 26

39 2521 26

40 2734 27

41 2165 28

42 1513 29

43 1802 30

44 889 31

45 1470 32

46 771 33

47 906 34

48 1398 35

49 88 36

50 322 37

Tabela 23: Colocação dos clientes que menos alugam filmes, segundo WEKA.

Sugestão: Para os que menos alugam poderia ser enviada uma

mala direta com promoções de filmes.

120

Generos mais alugados

17494; 27%

7584; 11%

7411; 11%7209; 12%

6648; 11%

6648; 11%

3470; 6%1615; 3%

966; 2%

939; 2%718; 1%

669; 1%547; 1%

514; 1%

ACAO

AVENTURA

COMEDIA

SUSPENSE

DESENHO

PORNO

TERROR

DRAMA

ROMANCE

GUERRA

INFANTIL

FICCAO

EROTICO

JOGO

Quais os tipos de filmes (GÊNERO) são mais alugados?

Figura 36: Gêneros de filmes mais alugados, apresentado pelo WEKA.

Quais os tipos de filmes (Gênero) são menos alugados?

Figura 37: Gêneros de filmes menos alugados, apresentado pelo WEKA.

0 100 200 300 400 500 600

nº de Vezes que foram alugadas

JOGO

POLICIAL

CLIPES

WESTERN

BIBLICO

MUSICAL

RELIGIOSO

FAROESTE

FUTEBOL

DOCUMENTARIO

EPICO

RODEIO

BANDA

EVANGELICO

BANG_BANG

CLASSICO

LUTA

ESPORTE

LIVRO

ROCK_NACIONAL

SHOW

LUTA_LIVRE

PRESIDIO

RACING

SERTANEJO

TORCIDA

Gen

ero

s

Generos menos alugados

121

Sugestão : Podem-se colocar os gêneros mais alugados próximos uns dos

outros e os gêneros menos alugados, numa área separada com promoções

com o objetivo de ter uma maior rotatividade de locações entre os gêneros

menos alugados.

Quais os bairros que mais alugam filmes?

Resposta: Em 1º lugar o bairro onde se encontra a locadora, logo

após os bairros mais próximos, conforme mostra a figura 49.

Figura 38: Bairros que mais alugam filmes.

Quem assiste mais filmes? O homem ou a mulher?

Figura 39: Filmes mais alugados por Sexo.

Filmes alugados por Bairro

3475; 6%

2842; 5%

2066; 3%1371; 2%

1361; 2%1264; 2%

895; 1%

786; 1%

661; 1%

46726; 77%

CENTRO

M_DOS_MARQUES

ALVORADA

VISTA_ALEGRE

JD_PARAIBA

BARRANCO_ALTO

PONTE_ALTA

VILA_SAO_JOSE

CHACARA_TROPICAL

BAIRRO_DOS_VIEIRAS

MASCULINO;

46081; 71%

FEMININO;

18437; 29%

MASCULINO

FEMININO

122

Quais os bairros alugam menos filmes?

Figura 40: Bairros que menos alugam filmes.

Quais os gêneros de filmes são mais assistidos por clientes que

mais alugam?

Resposta: Conforme TESTE na tabela 15, com base nos clientes

mapeados na tabela 22, os gêneros de filmes mais alugados por clientes que

mais alugam são: AÇÃO (26%), SUSPENSE (18%), AVENTURA (12%) e

COMÉDIA (12%) e DESENHO (11%).

647

464

0

100

200

300

400

500

600

700

1

Bairros que menos alugam filmes.FREI_GALVAO

SANTA_RITA

ITAGUAÇÚ

FAZENDA

VILA_SAO_PEDRO

JOAO_NOGUEIRA

SANTA_LUZIA

PARQUE_SAO_FRANCISCO

SANTA_CRUZ

SAO_GERALDO

MANTO_AZUL

SAO_SEBASTIAO

TIGRAO

PEDREGULHO

PARQUE_DAS_ARVORES

JOAO_DANIEL

ROSA_DE_OURO

VILA_MARIANA

SANTO_AFONSO

VILA_MUNICIPAL_2

SAO_BENEDITO

TAMANDARE

AGUA_BRANCA

PARQUE_SANTA_CLARA

AROEIRA

SANTA_TEREZINHA

CAMPO_DO_GALVAO

V_ALEGRE

JD_PRIMAVERA

RES_PALMEIRAS

SAO_ROQUE

VILA_OLIVIA

JD_DO_VALE

PARQUE_DAS_GARÇAS

123

Quais os gêneros de filmes são mais assistidos por clientes que

menos alugam?

Resposta: Com base nos clientes mapeados na tabela 23, fez-se

uma amostragem de alguns clientes que menos alugam filmes e os gêneros

que eles mais assistem, considerando os clientes que alugaram mais de 9

filmes, tem-se:

ID_Cliente

Nº de Fitas

Alugadas Gêneros mais alugados

39 10 ACAO

36 11 COMEDIA

70 13 ACAO, COMEDIA

536 14 DESENHO

265 15 SUSPENSE, DESENHO

136 19 AVENTURA, SUSPENSE

253 21 ACAO, SUSPENSE

234 23 ACAO, AVENTURA

1408 23 DESENHO


794 25 AVENTURA, COMEDIA

448 26 AVENTURA, SUSPENSE

2521 26 CLIPES, AVENTURA

2734 27 DESENHO

2165 28 ACAO, SUSPENSE

1470 32 ACAO, DESENHO

771 33 ACAO, COMEDIA


88 36 COMEDIA, SUSPENSE

322 37 ACAO, COMEDIA

Tabela 24: Gêneros mais assistidos por clientes que menos alugam filmes.

Na figura 41 nota-se que o atributo SEXO tem uma ótima

separabilidade e visualização em relação aos atributos ID_FILME, GÊNERO,

ID_CLIENTE, BAIRRO e CIDADE, enquanto na figura 42 os outros atributos

estão mais misturado, dificultando suas visualizações.

124

Figura 41: Separabilidade dos clientes pelo atributo Sexo.

Figura 42: Separabilidade dos clientes pelo atributo Bairro.

125

CONSIDERAÇÕES FINAIS

Após o desenvolvimento deste trabalho, podem ser feitas algumas

considerações:

É necessária muita pesquisa para obter-se um método ideal para

resolver um determinado problema e que seja capaz de atender a todos os

requisitos desejáveis para a tarefa de Clusterização, principalmente com

respeito aos requisitos relacionados à escalabilidade, ao conhecimento prévio

necessário, à robustez na presença de ruídos e à identificação do número

apropriado de clusters.

Nesta pesquisa foi possível responder algumas hipóteses e

expectativas, como por exemplo, conseguiu-se saber quais os filmes mais e

menos alugados, os clientes que mais e menos alugam por bairro, sexo e

cidade, os gêneros mais e menos alugados e quais os gêneros preferidos dos

clientes que mais e menos alugam.

Em todas as minerações realizadas, notou-se a ausência, ou pouca

freqüência, de locações de alguns gêneros como DRAMA, FAROESTE,

BÍBLICO, CLIPES, ROMANCE, FICÇÃO entre outros. Com base nesta

informação, a Locadora pode diminuir o número de compras deste tipo de

filme.

Após ter-se levantado várias hipóteses, construído alguns atributos e

ao tentar manipular esses novos atributos construídos, mostrados na tabela 5,

enriquecendo-os com informações que pudessem gerar novos conhecimentos,

expectativas e responder algumas hipóteses, percebeu-se que não seria

126

possível, pois o atributo DATAMOV (data da locação do filme) está totalmente

inconsistente, conforme mostra a figura 25.

Apesar da maioria das hipóteses terem sido respondidas, algumas

não puderam ser respondidas, tais como:

- Em que épocas do ano alugam-se mais filmes?

- Em que dias da semana se alugam mais filmes?

- Em que épocas do ano determinados gêneros são mais alugados?

- Os filmes mais alugados eram dublados ou legendados?

- Os filmes eram lançamentos quando foram alugados?

- Os filmes estavam na promoção ou eram finais de semanas

quando foram alugados?

As respostas não foram possíveis devido ao fato do atributo

DATAMOV (data da locação) ter sido desprezado por inconsistência, fato

comentado anteriormente.

O método K-Means é sensível a clusters de tamanhos muito

diferentes. Talvez isso explique a ausência, ou pouca freqüência, de locações

de alguns gêneros.

A necessidade de o usuário ter que especificar k número de clusters,

com antecedência pode ser vista como uma desvantagem, pois o usuário terá

que fazer várias minerações para achar o k número de clusters ideal para

retornar a melhor Mineração de Dados, ou seja, que retorne o melhor “Modelo

de Conhecimento” possível.

O método K-Means é sensível a ruídos, visto que um pequeno

número de tais dados (ruídos) podem influenciar, substancialmente, os

resultados. Porém, o que pode parecer ruídos para alguns, pode ser de grande

127

relevância para outros. Por exemplo: ruídos pode ser uma forma dos bancos

verificarem fraudes nas transações.

Com base nesta pesquisa um especialista no Domínio da Aplicação

pode fazer uma análise detalhada dos resultados (conhecimentos

descobertos), conhecer o perfil dos clientes, suas preferências e preparar um

plano de ação para aumentar o faturamento da Vídeo Locadora.

DIFICULDADES ENCONTRADAS

Uma grande dificuldade encontrada foi durante a fase de Pré-

processamento, onde percebeu-se a necessidade de uma política para que os

desenvolvedores criem uma Interface nos sistemas de armazenamento de dados

que permitam rotinas de crítica nas interfaces de entrada. Esta seria a melhor

maneira de evitar a “poluição” dos dados, organizando a entrada dos dados de

forma consistente para futuras utilizações em Mineração de Dados, pois essas

informações são de grande valor para as organizações. No entanto, nem sempre

tais rotinas estão disponíveis nos sistemas de armazenamento, o que dificulta

bastante o Pré-processamento.

Com a ausência de um especialista no Domínio da Aplicação no

processo de Mineração de Dados, principalmente na etapa de Pós-

processamento, percebeu-se uma dificuldade em interpretar os modelos de

conhecimentos (resultados da mineração), dificultando também as conclusões

e, principalmente, deixando talvez de enxergar alguns conhecimentos não

explícitos, que para ele talvez fizesse sentido.

128

Um exemplo dessa dificuldade está na figura 32 que representa um

resultado da Mineração de Dados em sua forma natural, ou seja, o formato que

o software WEKA apresenta, cabendo ao especialista de KDD transformá-lo,

tendo como objetivo facilitar para o especialista no Domínio da Aplicação, a

interpretação e a avaliação da utilidade do conhecimento descoberto.

É nesta etapa que o especialista em KDD e o especialista no

Domínio da Aplicação avaliam juntos os resultados obtidos e fazem

considerações ou conclusões.

Durante vários experimentos de Minerações de dados sobre a base

de dados, percebeu-se uma dificuldade em enxergar e interpretar os

resultados, pois os mesmos parecem ser repetitivos, confirmando-se a

necessidade da presença de um especialista no Domínio da Aplicação.

Por isso passou-se então a ter mais atenção nos resultados onde as

porcentagens (%) são menos significativas, pois podem sugerir pontos fracos à

serem estudados e melhorados ou talvez nichos à serem explorados, já que as

porcentagens (%) mais expressivas, ao serem observadas, representam o

óbvio e muitas vezes repetitivas, parecendo não acrescentar nenhum novo

conhecimento.

Observou-se uma dificuldade do algoritmo de Clusterização em

conseguir formar clusters (grupos) com clientes que tenham feito poucas

locações. Essa afirmação foi constatada quando se fez uma Mineração de

129

Dados com parâmetros de N= 100 para clusters e S=100 para Seed, onde só

foi encontrado um cliente da relação de clientes que menos alugam filmes,

mapeados na tabela 23.

Observou-se também uma dificuldade do algoritmo de Clusterização

em conseguir formar clusters com gêneros poucos alugados. Essa afirmação é

constatada em todas as Minerações de Dados feitas, mostradas nas tabelas de

testes, onde raramente se encontra, por exemplo, os gêneros DRAMA,

FAROESTE, BÍBLICO, CLIPES, ROMANCE, FICÇÃO, entre outros.

E por fim, terminar este trabalho com a certeza de que muitos

conceitos foram aprendidos e os objetivos de conhecer várias técnicas, tarefas,

métodos e algoritmos de Clusterização, escolher um e aplicar um sobre uma

base de dados, interpretar os resultados e apresentá-los de forma clara, foram

alcançados.

TRABALHOS FUTUROS

Esse trabalho pode ser continuado para melhor estudar as técnicas

de KDD, as tarefas de Mineração de Dados e os algoritmos voltados à estas

tarefas, suas características, diferenças e principalmente suas utilidades,

conhecer mais profundamente outros Algoritmo de Clusterização, e tentar

definir quais são mais apropriados para um determinado segmento do

mercado, testando-os através de ferramentas disponíveis no mercado,

mostradas na tabela 2, e se possível implementá-los, melhorando seus pontos

fracos.

130

REFERÊNCIAS BIBLIOGRÁFICAS E BIBLIOGRAFIAS

APTE, Chidanand; GROSSMAN, Edna et al. Probabilistc Estimation-based Data Mining for Discovering Insurance Risks IEEE Intelligent Systems & their aplications, Los Alamitos/CA, p. 49-58, nov./dec. 1999.

ARNOLD, Ken. Programando em Java. São Paulo/SP: Makron Books, 1997. BERRY, Michael J. A.; LINOFF, Gordon. Data Mining Techniques 2nd Edition: Wiley, 2004.

BRAGA, Antonio de Padua; CARVALHO, André Ponce de Leon; LUDERMIR, Teresa Bernardes. Redes Neurais Artificiais: Teoria e Aplicações. Rio de Janeiro: Ed. LTC, 2000.

CARLANTONIO, Lando Mendonça Di. Novas Metodologias para Clusterização de Dados. 2001. 157 f. Dissertação (Mestrado em Ciências em Engenharia Civil) – Universidade Federal do Rio de Janeiro: COPPE/UFRJ, Rio de Janeiro, 2001.

CARVALHO, Luís Alfredo Vidal de. Data Mining: a mineração de dados no marketing, medicina, economia, engenharia e administração. São Paulo: Erica, 2001.

CHAN, Philip K.; FAN, Wei et al. Distributed Data Mining in Credit Card Fraud detection. IEEE Intelligent Systems & their applications, Los Alamitos/CA, p. 67-74, nov./dec. 1999.

DEITEL, H. M. Java: Como Programar. São Paulo/SP: Printice Hall, 2005.

ELMASRI, Ramez; NAVATHE, Shankant B. Fundamentals of Database Systems: Addison Wesley, 2000.

FAYYAD, Usama M. et al. Advances in knowledge Discovery and Data Mining. Menlo Park /CA: AAAI Press, 1996.

131

FREEMAN, James A.; SKAPURA, David M. Neural Networks: algorithm application and programming techniques. California: Ed. CNS, 1991.

GOLDSCHMIDT, Ronaldo; PASSOS, Emmanuel. Data Mining: um guia prático. Rio de Janeiro/RJ: Campus, 2005.

LEMAY, Laura. Aprenda Java em 21 dias. Rio de Janeiro/RJ: Campus, 1998.

PEDRYCZ, Witold. Kowledge-based clustering: from data to information granules. Edmonton /Canada: Wiley, 2005.

RESENDE, Solange Oliveira. Sistemas Inteligentes: Fundamentos e Aplicações. Barueri/SP: Manole, 2003.

SMITH, Elmi; ELOFF, Jan. Cognitive Fuzzy Modeling for Enhanced Risk Assessment in Health Care Institution. IEEE Intelligent Systems & their applications, Los Alamitos/CA, p. 69-75, mar./abr. 2000.

Souto, M. C. P. Weka: Aprendizado de Máquina. Site da faculdade UFRN. Disponível em <http://www.dimap.ufrn.br/~marcilio/AM/course-AM.htm>. Acesso em 07 ago. 2006.

WITTEN, Ian H.; Frank, Eibe. Data Mining: practical machine learning tools and techniques with Java Implementations. San Francisco: Morgan Kaufmann Publishers, 1999.

WITTEN, Ian H.; FRANK, Eibe. Data Mining: practical machine learning tools and techniques with Java Implementations. San Francisco: Morgan Kaufmann Publishers, 2000.

Documents

TCC Mineração de Dados