Uma abordagem baseada em minerac~ao de dados para aquisic~ao autom atica de ... · 2013. 6. 27. · minerac~ao de dados para aquisic~ao autom atica de conhecimento sobre o processo

Universidade Federal do Rio Grande

Engenharia de Computacao

Uma abordagem baseada emmineracao de dados para aquisicao

automatica de conhecimento sobre oprocesso seletivo da Universidade

Federal do Rio Grande

Guilherme Vaz Pereira e Roger Sa da Silva

Rio Grande, 11 de Janeiro de 2010

Universidade Federal do Rio Grande


Uma abordagem baseada emmineracao de dados para aquisicao

automatica de conhecimento sobre oprocesso seletivo da Universidade

Federal do Rio Grande

Guilherme Vaz Pereira e Roger Sa da Silva

Trabalho de Conclusao do Curso de Gradu-

acao em Engenharia de Computacao subme-

tido a avaliacao, como requisito parcial a ob-

tencao do tıtulo de Engenheiro de Computa-

cao.

Orientador: Prof. Dr. Adriano Velasque Werhli

Co-orientador: Prof. Dr. Leonardo Ramos Emmendorfer

Rio Grande, 11 de Janeiro de 2010

Este trabalho foi analisado e julgado adequado para a obtencao do tıtulo de Engenheiro

de Computacao e aprovado em sua forma final pelo orientador.

——————————————————–

Prof. Dr. Adriano Velasque Werhli

Banca Examinadora:

Prof. Dr. Adriano Velasque Werhli

Centro de Ciencias Computacionais – FURG (Orientador)

Prof. Dr. Leonardo Ramos Emmendorfer

Centro de Ciencias Computacionais – FURG

Prof. Dr. Andre Luis Castro de Freitas

Centro de Ciencias Computacionais – FURG

Agradecimentos

Gostarıamos de agradecer algumas pessoas e instituicoes que foram importan-

tes na realizacao deste trabalho:

Ao nosso orientador, Prof. Dr. Adriano Velasque Werhli, e nosso co-

orientador, Prof. Dr. Leonardo Ramos Emmendorfer, pelas ideias, pela dis-

ponibilidade em esclarecer duvidas e por dividirem seu conhecimento conosco.

Ao Nucleo de Tecnologia da Informacao (NTI) e a Comissao Permanente de

Vestibular (COPERVE) da Universidade Federal do Rio Grande, por disponi-

bilizarem e permitirem a utilizacao da base de dados dos processos seletivos

da universidade.

Ao Analista de T.I. do NTI-FURG Carlos Alberto Madsen e ao Prof. An-

dre Prisco Vargas (na epoca, tambem Analista de T.I. do NTI-FURG), pelo

interesse e por estarem sempre dispostos a ajudar.

A todos nossos amigos, em especial os amigos e colegas Diogo, Gabriel, Igor,

Leonardo, Tiago, Wesley e Bruno pelos estudos e trabalhos realizados em con-

junto, pelas boas risadas proporcionadas e inumeras situacoes compartilhadas.

Eu, Guilherme, particularmente gostaria de agradecer:

A todos que contribuıram, direta ou indiretamente, para a conclusao deste

trabalho e deste curso, e a todos que torceram para que estas etapas fossem

cumpridas.

Aos meus pais Gilberto e Gilce, que nunca pouparam esforcos para que eu

alcancasse meus objetivos, e disseram sempre palavras de apoio e incentivo ao

longo do curso. A minha irma e amiga, Gabriela.

A Jessica. Com muito amor, carinho, e paciencia, dividiu comigo alegrias

e tristezas, foi ouvinte de muitos desabafos, e suportou a distancia e minha

ausencia em alguns momentos, alem de ser fonte constante de apoio, incentivo

e confianca na realizacao deste sonho.

A todos os meus amigos que torceram por mim, os de longa data, e aqueles

que fiz durante a faculdade.

Eu, Roger, particularmente gostaria de agradecer:

A minha famılia, especialmente meus pais Zalmir e Dora, por apoiarem minhas

decisoes, estarem sempre presentes e incentivarem esta jornada academica.

A minha namorada Laura, por ser minha companheira, parceira e amiga. Por

estar sempre disposta a ajudar, incondicionalmente me apoiar em todos os

momentos e ser tao compreensiva em situacoes difıceis. Em especial, por ser

a alegria e o amor da minha vida.

A minha segunda famılia, especialmente meus sogros Pedro e Sandra, por

permitirem que eu faca parte da famılia e incentivarem meu trabalho, e pela

amizade construıda ao longo da nossa convivencia; e a minha cunhada/irma

Marina, pelo constante interesse, pelas dicas e por me aturar.

Aos meus amigos e a todos que, de alguma forma, contribuıram para a reali-

zacao do curso e deste trabalho.

Sumario

Lista de Figuras iii

Lista de Tabelas v

Lista de Codigos vi

Lista de Abreviaturas vii

Resumo viii

Abstract ix

1 Introducao 1

2 Descoberta de Conhecimento em Bases de Dados 3

2.1 Etapas do KDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Pre-Processamento 6

3.1 Selecao de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2 Limpeza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.3 Codificacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.4 Enriquecimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.5 Construcao de Atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.6 Correcao de Prevalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Data Mining 13

4.1 Tarefas Desempenhadas por Tecnicas de Mineracao de Dados . . . . . . . 14

i

SUMARIO ii

4.1.1 Classificacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.2 Metodos e Algoritmos de Classificacao . . . . . . . . . . . . . . . . . . . . 16

4.2.1 Classificacao por Inducao de Arvores de Decisao . . . . . . . . . . . 17

4.3 Classes Desbalanceadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5 Pos-Processamento 24

6 Ferramenta WEKA 26

6.1 Caracterısticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

6.2 Selecao de Atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6.3 Algoritmo de Classificacao J4.8 . . . . . . . . . . . . . . . . . . . . . . . . 30

7 Estudo de Caso 35

7.1 Base de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

7.2 Coleta e Pre-Processamento dos Dados . . . . . . . . . . . . . . . . . . . . 36

7.3 Data Mining na ferramenta WEKA . . . . . . . . . . . . . . . . . . . . . . 39

7.3.1 Arquivo no formato ARFF . . . . . . . . . . . . . . . . . . . . . . . 39

7.3.2 Selecao de Atributos . . . . . . . . . . . . . . . . . . . . . . . . . . 40

7.3.3 Algoritmo de Classificacao . . . . . . . . . . . . . . . . . . . . . . . 41

7.4 Demonstracao dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 41

7.4.1 Medicina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

7.4.2 Direito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

7.4.3 Engenharia de Computacao . . . . . . . . . . . . . . . . . . . . . . 46

7.4.4 Engenharia Mecanica . . . . . . . . . . . . . . . . . . . . . . . . . . 48

7.5 Obtencao do Conhecimento . . . . . . . . . . . . . . . . . . . . . . . . . . 51

7.5.1 Regras de Classificacao . . . . . . . . . . . . . . . . . . . . . . . . . 52

8 Consideracoes Finais 55

A Questionario Socio-Economico 57

B Consulta SQL 62

Bibliografia 70

Lista de Figuras

2.1 Visao geral das etapas do processo de Descoberta de Conhecimento em

Base de Dados - KDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Agrupamento das etapas de KDD em tres grandes etapas, destacando a

participacao do especialista . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4.1 Representacao da natureza interdisciplinar da mineracao de dados, envol-

vendo as areas de Inteligencia Artificial, Banco de Dados e Estatıstica . . . 13

4.2 Associacoes entre registros de dados e classes - figura reproduzida de Golds-

chmidt and Passos (2005) . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.3 Atividades de classificacao - figura reproduzida de Han and Kamber (2001) 16

4.4 Atributos disponıveis para a construcao da arvore de decisao para o pro-

blema de esperar ou nao uma mesa em um restaurante . . . . . . . . . . . 17

4.5 Exemplo de arvore de decisao para o problema de esperar ou nao uma mesa

em um restaurante - figura reproduzida de Russell and Norvig (2003) . . . 18

4.6 Representacao do algoritmo de aprendizagem de arvode de decisao . . . . . 19

4.7 Divisao dos exemplos por meio de testes em atributos, baseado no conjunto

de exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6.1 Exemplo de arquivo no formato ARFF utilizado como entrada na ferra-

menta WEKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

6.2 Janela para configuracao dos parametros do algoritmo J4.8 . . . . . . . . . 30

6.3 Exemplo de resultado da execucao do algoritmo de classificacao por arvore

de decisao J4.8 na ferramenta WEKA - Arvore de decisao e porcentagens

de instancias classificadas correta e incorretamente . . . . . . . . . . . . . 32

iii

LISTA DE FIGURAS iv

6.4 Exemplo de resultado da execucao do algoritmo de classificacao por arvore

de decisao J4.8 na ferramenta WEKA - Matriz de confusao . . . . . . . . . 33

6.5 Arvore de decisao gerada pela execucao do algoritmo de classificacao J4.8 . 33

6.6 Matriz de confusao gerada pela execucao do algoritmo de classificacao J4.8 34

6.7 Exemplo grafico da arvore de decisao gerada como resultado da execucao

do algoritmo de classificacao J4.8 na ferramenta WEKA . . . . . . . . . . 34

7.1 Diagrama Entidade-Relacionamento que representa a base de dados original

utilizada para a coleta dos dados utilizados neste estudo de caso . . . . . . 36

7.2 Arquivo no formato ARFF, contendo somente um registro para exemplifi-

cacao, para o curso de Medicina . . . . . . . . . . . . . . . . . . . . . . . . 40

7.3 Arvore de decisao gerada pela ferramenta WEKA para o curso de Medicina 43

7.4 Ilustracao da arvore de decisao gerada pela ferramenta WEKA para o curso

de Medicina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7.5 Arvore de decisao gerada pela ferramenta WEKA para o curso de Direito . 45


de Direito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

7.7 Arvore de decisao gerada pela ferramenta WEKA para o curso de Enge-

nharia de Computacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47


de Engenharia de Computacao . . . . . . . . . . . . . . . . . . . . . . . . . 47

7.9 Arvore de decisao gerada pela ferramenta WEKA para o curso de Enge-

nharia Mecanica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49


de Engenharia Mecanica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Lista de Tabelas

6.1 Algumas caracterısticas da ferramenta WEKA . . . . . . . . . . . . . . . . 29

7.1 Indices de instancias classificadas correta e incorretamente na execucao do

algoritmo de classificacao J4.8 na ferramenta WEKA para os cursos em

analise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7.2 Atributos selecionados na ferramenta WEKA para o curso de Medicina . . 42

7.3 Matriz de confusao do algoritmo de classificacao gerada pela ferramenta

WEKA para o curso de Medicina . . . . . . . . . . . . . . . . . . . . . . . 42

7.4 Atributos selecionados na ferramenta WEKA para o curso de Direito . . . 43


WEKA para o curso de Direito . . . . . . . . . . . . . . . . . . . . . . . . 46

7.6 Atributos selecionados na ferramenta WEKA para o curso de Engenharia

de Computacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46


WEKA para o curso de Engenharia de Computacao . . . . . . . . . . . . . 48

7.8 Atributos selecionados na ferramenta WEKA para o curso de Engenharia

Mecanica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48


WEKA para o curso de Engenharia Mecanica . . . . . . . . . . . . . . . . 49

7.10 Atributos mais relevantes para a classificacao de cada curso analisado . . . 52

v

Lista de Codigos

7.1 Trecho de codigo que representa um resumo da query utilizada para formar

a tabela unica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.2 Trecho de codigo SQL que representa a fracao da query que realiza a redu-

cao horizontal dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.3 Trecho de codigo SQL que representa a fracao da query que realiza a amos-

tragem estratificada do curso de Direito, para o vestibular de codigo ‘2007VN’ 37

7.4 Trecho de codigo SQL que representa a fracao da query que realiza a redu-

cao de valores para o atributo cidade, para o vestibular de codigo ‘2009VN’ 38

7.5 Trecho de codigo SQL que representa a fracao da query que realiza a criacao

do atributo idade, para o vestibular de codigo ‘2009VN’ . . . . . . . . . . 38

B.1 Codigo que representa a query utilizada para formar a tabela unica . . . . 62

vi

Lista de Abreviaturas

FURG Universidade Federal do Rio Grande

ECOMP Engenharia de Computacao

KDD Knowledge Discovery in Databases

NFL No Free Lunch

WEKA Waikato Environment for Knowledge Analysis

GNU GNU is Not Unix

ARFF Attribute-Relation File Format

NTI Nucleo de Tecnologia da Informacao

COPERVE Comissao Permanente de Vestibular

SQL Structured Query Language

SGBD Sistema Gerenciador de Bando de Dados

ER Entidade-Relacionamento

vii

Resumo

Atualmente, ha um crescimento constante do volume de dados produzidos e armazena-

dos, amparado pelo avanco dos recursos computacionais com cada vez mais capacidade

de armazenamento e processamento de dados. Com isto, e inevitavel que informacoes

fundamentais para que empresas, corporacoes, e governos tenham suporte a tomada de

decisao e obtenham vantagem competitiva, fiquem implıcitas. Em resposta a necessidade

de analisar de forma inteligente e automatica os imensos repositorios de dados surgiu o

campo da Descoberta de Conhecimento em Bases de Dados (Knowlege Discovery in Data

Bases - KDD) que se refere ao processo de extracao de conhecimento a partir de uma

grande base de dados. Data Mining, tambem chamado de Mineracao de dados e a prin-

cipal etapa, que forma o nucleo do processo de KDD. Neste contexto, este trabalho visa

fazer um estudo detalhado sobre Data Mining atraves da analise de conceitos e tecnicas,

e realizar aplicacoes praticas utilizando a ferramenta WEKA (Weikato Enviroment for

Knowledge Analysis) na base de dados do vestibular da FURG (Universidade Federal do

Rio Grande) dos anos 2007, 2008 e 2009. Espera-se obter domınio sobre a base de dados

e os algoritmos que serao executados sobre ela, assim como dos processos de KDD e Data

Mining como um todo. Alem disso, e esperada a identificacao dos principais atributos e

a extracao de regras para as diferentes populacoes existente nos dados.

Palavras-chave: Data Mining, Mineracao de Dados, Descoberta de Conhecimento,

Vestibular FURG, WEKA.

viii

Abstract

Nowadays there is a growth in volume of data produced and stored, supported by advan-

ces in computational resources and increasing capacity from data storage and processing.

Is inevitable that fundamental information for corporations and governments to support

decision and get competitive advantage remain implicit. In response to need to analyze

intelligently and automatically the vast repositories of data emerged the Knowledge Dis-

covery in Database, the process of extracting knowledge from a large database. Data

Mining is the main stage of KDD process. In this context, this work aims to make a

detailed study of Data Mining through the analysis of concepts and techniques, and prac-

tical applications using tool WEKA (Weikato Enviroment for Knowledge Analysis) in the

database of selection process of FURG (Federal University of Rio Grande) for 2007, 2008

and 2009. Intended to know the database and Data Mining algorithms, as well as the

processes of KDD and Data Mining as a whole. Furthermore, is expected to identify the

main attributes and extraction of rules for different samples.

Keywords: Data Mining, Knowlege Discovery, FURG, WEKA.

ix

Capıtulo 1

Introducao

Com o crescimento do volume de dados produzidos e armazenados em ambientes compu-

tacionais, aumenta a dificuldade do homem de analisar, interpretar e extrair informacoes

destes, e surge a necessidade do uso de ferramentas computacionais que auxiliem nestas

tarefas. Neste contexto surgiu o processo de Descoberta de Conhecimento em Banco de

Dados (Knowledge Discovery in Data Bases - KDD).

Segundo Goldschmidt and Passos (2005), descobrir conhecimento e extrair significados

dos dados para evitar riscos e aproveitar oportunidades, nao apenas na hora de tomar

decisoes, mas tambem para planejamento de atividades. Fayyad et al. (1996) destaca que

KDD e um processo interativo e iterativo, nao trivial, para identificar padroes validos,

novos, potencialmente uteis e compreensıveis nos dados. O processo e dividido em etapas,

sendo a principal delas a etapa de Data Mining, ou Mineracao de Dados, onde ocorre

efetivamente a busca por conhecimentos uteis a aplicacao. A etapa de pre-processamento,

segundo Goldschmidt and Passos (2005), trata da captacao, organizacao, tratamento e

preparacao dos dados para a etapa de Data Mining. Segundo os mesmos autores, a

etapa de pos-processamento trata de analisar e interpretar os resultados da etapa de Data

Mining.

Este trabalho apresenta um estudo detalhado sobre o processo de KDD, principal-

mente sobre Data Mining e suas tecnicas e algoritmos, com destaque para algoritmos de

classificacao por inducao de arvores de decisao.

Alem do estudo teorico, evidencia aplicacoes praticas de Data Mining atraves de al-

goritmos implementados pela ferramenta WEKA, e um estudo de caso realizado sobre a

1

CAPITULO 1. INTRODUCAO 2

base de dados dos processos seletivos da Universidade Federal do Rio Grande dos anos

de 2007, 2008 e 2009, visando obter, de forma automatica, conhecimentos, ate entao

implıcitos, atraves da Mineracao de Dados.

A estrutura deste trabalho e formada por oito capıtulos. Este capıtulo de introdu-

cao mostra uma visao geral do trabalho. O capıtulo dois trata sobre o conceito e as

etapas do processo de descoberta de conhecimento em base de dados. O capıtulo tres

apresenta conceitos e tecnicas da etapa de pre-processamento. O capıtulo quatro aborda

a etapa de Data Mining, principal etapa do processo de KDD, apresentando tecnicas,

metodos e algoritmos para realizacao desta etapa. O capıtulo cinco trata sobre a etapa

de pos-processamento. O capıtulo seis apresenta a ferramenta WEKA, suas caracterısti-

cas, funcionalidades e algoritmos disponibilizados que foram utilizados neste trabalho. O

capıtulo sete aborda o estudo de caso realizado, desde a caracterizacao e coleta dos dados

utilizados ate a demonstracao e interpretacao dos resultados obtidos apos execucao dos

algoritmos de Data Mining. O capıtulo oito apresenta as consideracoes finais e sugestoes

para trabalhos futuros.

Capıtulo 2

Descoberta de Conhecimento em

Bases de Dados

Diante de um cenario de constante crescimento do volume de dados disponıveis em am-

bientes computacionais, surge nas organizacoes, de qualquer natureza, a necessidade de

analisar e utilizar do melhor modo possıvel todo o volume de dados disponıveis obtendo

informacoes ate entao implıcitas nesta grande quantidade de dados. Como os volumes de

dados crescem dramaticamente, este tipo de analise, manual, torna-se impraticavel em

varios domınios, segundo Fayyad et al. (1996).

De acordo com Goldschmidt and Passos (2005), a analise de grandes quantidades de

dados pelo homem e inviavel sem o auxılio de ferramentas computacionais apropriadas.

Portanto, torna-se imprescindıvel o desenvolvimento de ferramentas que auxiliem o ho-

mem, de forma automatica e inteligente, na tarefa de analisar, interpretar e relacionar

esses dados para que se possa desenvolver e selecionar estrategias de acao em cada con-

texto de aplicacao.

Segundo Fayyad et al. (1996), Descoberta de Conhecimento em Banco de Dados (Kno-

wledge Discovery in Databases - KDD) e o processo que surgiu junto com este contexto. O

termo Knowledge Discovery in Databases foi formalizado em 1989, no primeiro workshop

de KDD.

A definicao classica do processo de KDD foi apresentada por um grupo de pesquisa-

dores, Fayyad, Piatetsky-Shapiro e Smyth, e diz que KDD e um processo nao trivial para

identificar padroes validos, novos, potencialmente uteis e compreensıveis nos dados. O

3

CAPITULO 2. DESCOBERTA DE CONHECIMENTO EM BASES DE DADOS 4

autor acrescenta que o termo processo implica que KDD compreende varias etapas e que

o processo e interativo e iterativo.

De acordo com a definicao apresentada, Goldschmidt and Passos (2005) diz que o

termo interativo indica a atuacao do homem como no controle do processo. O termo

iterativo faz referencia a possibilidade de repeticoes, seja de todo o processo ou apenas de

algumas etapas, em busca de resultados satisfatorios. Um padrao compreensıvel refere-se

a uma representacao do conhecimento que possa ser interpretada pelo homem, enquanto

um padrao valido indica que o conhecimento deve ser verdadeiro e estar contextualizado

com a aplicacao de KDD. Finalmente um padrao, ou conhecimento util, e aquele que pode

ser aplicado e trazer benefıcios a aplicacao.

Segundo Fayyad et al. (1996), o processo possui duas classes de objetivos: Verificacao

e Descoberta. Na verificacao ocorre a confirmacao ou nao de uma hipotese formulada

pelo usuario, enquanto na descoberta ocorre a busca por novos conhecimentos, de forma

automatica. Alem disso, o objetivo de Descoberta pode ser subdividido em Predicao, onde

se busca padroes para prever o comportamento futuro de algumas entidades, a partir de

casos anteriores, ou Descricao, onde se busca um modelo para descrever um conhecimento

existente, em um conjunto de dados, de uma maneira compreensıvel pelo homem. Elmasri

and Navathe (2003) cita como exemplo de Predicao a analise de transacoes de compra

para prever o comportamento dos consumidores diante de determinadas promocoes, ou

outras acoes estrategicas de uma organizacao. Como exemplo de Descricao, o autor cita

a busca por intrusos, tentado danificar um sistema, atraves da analise dos programas

executados e arquivos acessados durante uma fatia de tempo.

Entre as areas de aplicacao do processo de KDD estao marketing, gestao de qualidade,

medicina, mercado financeiro, transporte e logıstica.

2.1 Etapas do KDD

A figura, 2.1 reproduzida de Fayyad et al. (1996) fornece uma visao geral das etapas do

processo de KDD.

Goldschmidt and Passos (2005) traz um agrupamento das etapas de KDD em tres

etapas, como mostra a figura 2.2, adaptada de Goldschmidt and Passos (2005). O autor

CAPITULO 2. DESCOBERTA DE CONHECIMENTO EM BASES DE DADOS 5

Figura 2.1: Visao geral das etapas do processo de Descoberta de Conhecimento em Basede Dados - KDD

Figura 2.2: Agrupamento das etapas de KDD em tres grandes etapas, destacando aparticipacao do especialista

destaca a participacao do homem, que deve ser especializada, ou seja, deve possuir conhe-

cimento sobre a natureza dos dados. Cabe ao analista a tarefa de conduzir e orientar a

execucao do processo, de forma a escolher as estrategias a serem adotadas. E fundamental

ter entendimento do domınio da aplicacao e objetivos bem definidos.

De acordo com este agrupamento, a etapa de Pre-processamento esta relacionada as

atividades de captacao, organizacao e tratamento dos dados. Estas atividades preparam

os dados para os algoritmos da etapa de Mineracao de Dados. A etapa de Mineracao de

Dados e a principal do processo de KDD, pois e onde ocorre efetivamente a busca por

conhecimentos uteis a aplicacao. Ja a etapa de Pos-processamento refere-se ao tratamento

do conhecimento obtido de modos a torna-lo compreensıvel.

Capıtulo 3

Pre-Processamento

Segundo Goldschmidt and Passos (2005), a etapa de Pre-processamento e formada por

atividades que tratam da captacao, organizacao, tratamento e preparacao dos dados para

a proxima etapa, a Mineracao de Dados.

Algumas das mais importantes atividades da etapa de pre-processamento de dados, de

acordo com Goldschmidt and Passos (2005) e Zhang et al. (2003) sao expostas a seguir.

3.1 Selecao de Dados

Esta etapa busca, de acordo com o contexto da aplicacao e objetivos tracados, o conjunto

de dados apropriado nas bases existentes, quais informacoes devem ser consideradas du-

rante o processo, sejam estas bases internas ou externas. Segundo Jubran et al. (2004),

bases internas sao repositorios que ja estao incorporados ao sistema de aplicacao do domı-

nio, como por exemplo Data Warehouse e base de dados operacionais. Ja bases externas

vem de repositorios de outras localidades que nao estao no sistema de aplicacao, como

por exemplo, documentos do especialista do domınio.

Segundo Goldschmidt and Passos (2005), a maioria dos metodos de Mineracao de

Dados parte do princıpio que os dados estao organizados em uma unica, e possivelmente

grande, estrutura. Duas formas de agrupar as informacoes sao propostas pelo autor,

na primeira, chamada juncao direta, nao ha analise crıtica quanto a contribuicao dos

atributos ou variaveis para o processo de KDD, pois todos os atributos e registros da

base de dados sao incluıdos na nova tabela. Outra forma e chamada juncao orientada, na

6

CAPITULO 3. PRE-PROCESSAMENTO 7

qual sao escolhidos os atributos e registros que tem maior potencial para colaborar com

o processo atraves de analise feita pelo especialista do domınio da aplicacao.

Para Soares (2007), a selecao de dados pode ocorrer em dois momentos, sendo que

primeiro ocorre a extracao dos dados de diversas fontes para formar o conjunto de dados

a ser analisado. Esta atividade e denominada Coleta de Dados por Zhang et al. (2003).

O segundo momento, e de escolha dos atributos que serao considerados efetivamente na

analise e ocorre imediatamente antes do processo de mineracao de dados. Este segundo

momento e chamado de Reducao de Dados e e importante porque alguns atributos po-

dem contribuir muito pouco ou nada com o processo, por nao estarem de acordo com a

semantica da aplicacao ou possuırem forte restricao de unicidade, por exemplo.

Considerando que os dados estejam em uma estrutura unica, segundo Goldschmidt and

Passos (2005) a Relacao de Dados pode ser obtida sob dois enfoques distintos, Reducao

de Dados Horizontal ou Reducao de Dados Vertical.

1. Reducao Horizontal de Dados

Segundo Goldschmidt and Passos (2005), na Reducao Horizontal ocorre a escolha

de casos, ou seja, de registros. Pode ser feita escolhendo um ou mais atributos

para guiar o processo, sendo que de acordo com estes atributos e possıvel escolher

casos para fazer parte ou nao do conjunto. Tais operacoes poderiam ser feitas por

instrucoes da linguagem SQL.

Outra maneira de fazer este tipo de selecao, colocada por Han and Kamber (2006),

e por Amostragem, na qual se seleciona registros, de forma randomica, para formar

um conjunto menor que o original. O autor classifica os tipos de amostragem como

Amostragem Aleatoria Simples Com ou Sem Repeticao, Amostragem em Clusters

e Amostragem Estratificada. Na Amostragem Aleatoria Simples, todos os registros

possuem a mesma probabilidade de selecao, podendo ser permitida a possibilidade

de repeticao do registro selecionado ou nao. Na Amostragem em Clusters, as tuplas

sao agrupadas em diferentes clusters e em seguida e realizada uma amostra aleatoria

dentre os clusters. Na Amostragem Estratificada, um conjunto de dados e segmen-

tado em grupos disjuntos e, a partir daı, sao selecionadas amostras aleatorias de

cada grupo.


O autor destaca a importancia da Amostragem Estratificada em contextos em que

sao apresentados dados tendenciosos, pois ela facilita a obtencao de amostras repre-

sentativas.

Segundo Goldschmidt and Passos (2005), uma simples agregacao de informacoes,

quando isso for possıvel, pode reduzir horizontalmente os dados, sob pena de perda

de detalhes. O autor traz como exemplo, registros de diferentes compras de um

mesmo cliente, sendo possıvel agregar os registros com valores de cada compra em

um unico, com o valor total das compras.

2. Reducao Vertical de Dados

Segundo Goldschmidt and Passos (2005), esta tecnica trata da selecao de atributos.

A Reducao Vertical de Dados procura qual combinacao, com o mınimo de atributos,

deve ser considerada no processo de KDD. De acordo com Merschmann (2007), a

selecao de atributos visa identificar e excluir o maximo de informacoes irrelevantes

ou redundantes do conjunto de dados.

De acordo com Soares (2007), uma boa selecao de atributos pode levar, atraves de

um conjunto bem selecionado, a modelos de conhecimento mais precisos e confiaveis.

Segundo este autor, a eliminacao de um atributo e muito mais significativa do que

a eliminacao de um registro no conjunto de dados, e por isso, mais importante.

Segundo Merschmann (2007), de acordo com a abordagem usada para avaliacao de

atributos, as tecnicas de selecao de atributos podem ser classificadas como filter ou

wrapper. No caso dos wrappers, a avaliacao dos atributos e feita por um algoritmo

de Mineracao de Dados especıfico e o desempenho do subconjunto de atributos e

medida de acordo com o desempenho do algoritmo. Por outro lado, filters trabalham

de forma que os atributos sao selecionados levando em conta apenas as caracterısticas

gerais dos dados, tal como a capacidade de discriminacao dos atributos com relacao

a classe, pois operam independentemente de qualquer algoritmo de Mineracao de

Dados. Segundo Soares (2007), o metodo wrapper tem a vantagem de gerar um

subconjunto de atributos que pode aumentar o desempenho e precisao do algoritmo

de mineracao de dados, porem e mais lento que o metodo filter e, ainda, o melhor

subconjunto para um classificador pode nao ser tao boa para outro.


Segundo Merschmann (2007), pode-se usar tres abordagens diferentes para selecio-

nar atributos, no que diz respeito ao ponto de partida do subconjunto de atributos

selecionados.

• Forward Selection - chamada de Selecao para Frente, o subconjunto dos atribu-

tos selecionados comeca vazio, e vao sendo adicionados atributos pelo processo

iterativo. Cada atributo por vez e adicionado ao subconjunto, e este sofre uma

avaliacao. No fim de cada iteracao, e incluıdo definitivamente no subconjunto

aquele atributo que tenha maximizado a medida de qualidade considerada.

• Backward Selection - chamada de Selecao para Tras, esta estrategia funciona

de maneira contraria a primeira. O subconjunto comeca preenchido por todos

os atributos do problema, e cada atributo e excluıdo a cada iteracao. O subcon-

junto vai sendo avaliado e, ao final de cada iteracao, e excluıdo definitivamente

do subconjunto o atributo que tenha minimizado a medida de qualidade.

Outros autores, como Han and Kamber (2006) incluem a abordagem bidirecional.

• Bidirectional Selection - e a combinacao das outras duas estrategias. A cada

passo, o algoritmo seleciona o melhor atributo e o inclui no subconjunto dos

atributos selecionados, e remove o pior atributo entre os que continuam no

conjunto de atributos do problema.

Segundo Merschmann (2007), ha tecnicas de selecao de atributos que consideram

cada atributo individualmente, selecionando os melhores atributos para fazer parte

do subconjunto no qual sera aplicado o algoritmo de Mineracao de Dados, atraves da

sua capacidade preditiva, e outras que avaliam subconjuntos de atributos, a procura

daquele que maximize a acuracia preditiva do classificador.

Segundo Goldschmidt and Passos (2005), se a reducao vertical de atributos for feita

com a tecnica da Eliminacao Direta, manual, deve-se ter conhecimento previo e

especializado do problema para saber quais atributos realmente nao sao relevantes

para o processo de KDD. Este tipo de operacao pode ser feita atraves de instrucoes

SQL. Por exemplo, podem-se eliminar atributos com valores constantes ou que sejam

elementos identificadores.


Freitas (2002) ressaltam que existem tecnicas interessantes para reducao de atribu-

tos, com o uso de algoritmos geneticos ou algoritmos para inducao de arvores de

decisao.

A reducao de valores, segundo Goldschmidt and Passos (2005), e uma alternativa

a reducao de dados vertical. Este tipo de operacao consiste em reduzir o numero

de valores distintos de cada atributo, nao excluindo o atributo. Pode melhorar o

desempenho do algoritmo de Mineracao de Dados e diminuir o tempo de processa-

mento, pois com menos valores distintos, menos comparacoes sao feitas. Pode ser

usado para valores discretos ou nominais.

3.2 Limpeza

Segundo Goldschmidt and Passos (2005), o objetivo desta fase e corrigir a base de dados.

Esta etapa envolve uma avaliacao da consistencia das informacoes, correcao de possıveis

erros, tratamento de valores ausentes ou redundantes, e ainda a eliminacao de valores nao

pertencentes ao domınio.

De acordo com Goldschmidt and Passos (2005), valores inconsistentes sao aqueles que

contem alguma discrepancia semantica entre si. Ja valores nao pertencentes ao domınio

sao os valores que nao estao entre os valores possıveis de um atributo. A limpeza de

dados com estas caracterısticas pode ocorrer com a exclusao dos casos ou pela correcao

dos erros.

Segundo Soares (2007), nao existe consenso sobre a classificacao das tecnicas para

preenchimento de valores ausentes. Goldschmidt and Passos (2005) apresenta, alem da

exclusao de casos para limpar valores ausentes, opcoes para o preenchimento de valores

ausentes. Os valores podem ser preenchidos de forma manual, com valores globais cons-

tantes, com medidas estatısticas como media ou moda, e ainda atraves de metodos de

Mineracao de Dados para predizer valores proporcionando que eventuais relacionamentos

entre atributos possam ser mantidos, pois atributos sao usados para prever valores de

outro atributo. Este ultimo metodo citado e muito usado na pratica.


3.3 Codificacao

Segundo Soares (2007), Codificar significa transformar a natureza dos valores de um atri-

buto. De acordo com Goldschmidt and Passos (2005), esta etapa e responsavel pela forma

como os dados serao representados durante o processo de KDD, e os dados devem ser co-

dificados de maneira a atender as necessidades especıficas dos algoritmos de mineracao

de dados, pois assim facilitam o seu uso por esses algoritmos. O mesmo autor classifica a

codificacao como Numerica - Categorica, que divide valores de atributos contınuos em va-

lores categoricos ou intervalos codificados, e Categorica - Numerica que representa valores

categoricos em codigos numericos.

Goldschmidt and Passos (2005) destaca que a tecnica muito usada da Discretizacao,

que e a representacao de valores por intervalos, e um tipo de Codificacao Numerica -

Categorica, mas ressalva que alguns autores consideram esta tecnica como Reducao de

Valores.

3.4 Enriquecimento

De acordo com Elmasri and Navathe (2003), a etapa de enriquecimento serve para au-

mentar a base de dados atraves de outras fontes de informacao.

Segundo Soares (2007) as informacoes adicionais podem ser adquiridas por meio de

duas operacoes mais usualmente utilizadas: pesquisas e consultas a bases de dados ex-

ternas. O papel do especialista e importante para que sejam agregadas informacoes que

aumentem o significado dos dados.

3.5 Construcao de Atributos

Segundo Goldschmidt and Passos (2005), consiste em gerar atributos derivados de outros

ja existentes na estrutura. Soares (2007) simplifica este conceito, citando que esta etapa

somente cria novas colunas na tabela.

Goldschmidt and Passos (2005) destaca a importancia deste tipo de operacao, pois

novos atributos podem reduzir o conjunto de dados e, alem disso, expressam relaciona-

mentos conhecidos entre atributos existentes e podem incorporar informacoes importantes


para o processo.

3.6 Correcao de Prevalencia

Segundo Goldschmidt and Passos (2005), esta atividade e necessaria, muitas vezes, em

tarefas de classificacao. Consiste em corrigir um desequilıbrio na distribuicao de registros

com determinadas caracterısticas, para evitar que a classificacao seja prejudicada pela

pouca ocorrencia de um atributo e muita ocorrencia de outro.

Segundo este mesmo autor esta correcao e feita, com frequencia, selecionando quan-

tidades iguais de registros para as classes envolvidas, usando o metodo de Amostragem

Estratificada descrita na secao 3.1 . Alternativamente pode-se usar um metodo de Re-

plicacao Aleatoria de Registros, selecionando aleatoriamente e com reposicao registros da

classe com menor quantidade para equilibrar o volume de casos associados das cada classe.

Capıtulo 4

Data Mining

De acordo com Fayyad et al. (1996), Data Mining e uma etapa do processo de KDD

que consiste em aplicar algoritmos especıficos, de analise e descoberta, para extracao de

padroes sobre dados. Envolve aplicacao repetida e iterativa de metodos destes algoritmos,

seja para construcao de modelos de conhecimento ou para determinacao de padroes sobre

os dados observados. Segundo Goldschmidt and Passos (2005), esta e a principal etapa

do processo de KDD, pois e onde ocorre a busca efetiva por conhecimentos novos e uteis,

surgindo assim o uso de Data Mining e KDD como sinonimos por parte de alguns autores.

Segundo Fayyad et al. (1996), Data Mining possui uma natureza interdisciplinar, en-

volvendo areas como Inteligencia Artificial, Banco de Dados, Estatıstica, como ilustrado

na Figura 4.1, adaptada de Han and Kamber (2006).

Neste contexto, o mesmo autor destaca a importancia do conceito que se refere a

Figura 4.1: Representacao da natureza interdisciplinar da mineracao de dados, envolvendoas areas de Inteligencia Artificial, Banco de Dados e Estatıstica

13

CAPITULO 4. DATA MINING 14

capacidade que os algoritmos possuem de aprender a partir de exemplos.

Segundo Fayyad et al. (1996), o aprendizado supervisionado trata-se da abstracao de

um modelo de conhecimento a partir dos dados disponıveis. De acordo com Russell and

Norvig (2004), explica-se este tipo de aprendizagem como a aprendizagem de uma funcao

a partir de exemplos de entrada e saıda. Um algoritmo de aprendizado supervisionado

recebe como entrada o valor correto de uma funcao desconhecida para as entradas de

exemplo e, assim, tenta encontrar esta funcao, chamada de hipotese. No aprendizado

nao supervisionado nao sao fornecidos valores de saıdas desejados para a aprendizagem

de padroes, ou seja, nao ha informacoes sobre o que e uma acao correta ou resultado

desejavel.

4.1 Tarefas Desempenhadas por Tecnicas de Mine-

racao de Dados

Segundo Dias (2001), as tecnicas de Data Mining podem ser aplicadas a diferentes tarefas

ou tipos de problemas de conhecimento a serem resolvidos, como Classificacao, Associ-

acao, Regressao, Clustering e Sumarizacao. Neste trabalho sera abordada a tecnica de

Classificacao.

4.1.1 Classificacao

Segundo Fayyad et al. (1996), a tarefa de classificacao consiste em buscar uma funcao

que mapeie os dados, ou seja, classifique corretamente registros de dados em uma, dentre

diferentes classes de dados.

Segundo Witten and Frank (2005), o esquema de aprendizagem e apresentado com

um conjunto de exemplos classificados, a partir do qual se espera aprender a classifi-

car exemplos ainda nao-vistos. Segundo o autor, os algoritmos de classificacao podem

ser chamados de supervisionados, pois e fornecida uma classe na qual cada exemplo do

treinamento pertence.

Goldschmidt and Passos (2005) apresenta uma formalizacao para a tarefa de classi-

ficacao, considerando um par (x, f(x)) como um exemplo, onde x e a entrada e f(x) a


Figura 4.2: Associacoes entre registros de dados e classes - figura reproduzida de Golds-chmidt and Passos (2005)

funcao aplicada a x. A tarefa deve obter uma funcao h que se aproxime de f , dada uma

colecao de exemplos de f . Segundo o autor, a funcao h obtida e uma hipotese, e toda a

hipotese encontrada e chamada de classificador.

Segundo Goldschmidt and Passos (2005), a acuracia da funcao, ou hipotese h, retrata

a precisao da hipotese em classificar as entradas ainda nao vistas, ou seja, as entradas que

formam o conjunto de testes. O conjunto de entradas utilizadas para encontrar a melhor

hipotese h e chamado de conjunto de treinamento. Depois de conhecido este conjunto, o

classificador pode ser aplicado a novos registros para rotula-los de acordo com as classes

existentes.

De acordo com Goldschmidt and Passos (2005), cada algoritmo de aprendizado possui

um bias, que afeta o processo de aprendizado restringindo o espaco de hipoteses e impoe

ordem de preferencia sobre as hipoteses. Segundo o teorema NFL - No Free Lunch Theo-

rem - Wolpert (1996), nao ha um algoritmo de classificacao que seja superior a todos os

outros em qualquer problema de classificacao.

Segundo Goldschmidt and Passos (2005), ao induzir um classificador podem ocorrer os

fenomenos Overfitting ou Underfitting. O primeiro fenomeno ocorre quando o classificador

e muito especıfico para o conjunto de treinamento utilizado, ou seja, quando se ajusta

excessivamente ao conjunto de treinamento e nao consegue obter bom desempenho para

o conjunto de testes. Por outro lado, o segundo fenomeno ocorre quando o classificador

se ajusta muito pouco ao conjunto de treinamento. O autor afirma que o detalhamento

do desempenho do modelo de classificacao e mostrado atraves da matriz de confusao.


Figura 4.3: Atividades de classificacao - figura reproduzida de Han and Kamber (2001)

Segundo Witten and Frank (2005), a matriz de confusao e uma matriz bidimensional

com uma linha e uma coluna para cada classe. Cada elemento da matriz mostra o numero

de exemplos de teste para o qual a classe representada na linha e a classe real e a classe

representada na coluna e a classe na qual o exemplo foi classificado.

Fayyad et al. (1996) traz como exemplos de aplicacao de metodos de classificacao a

verificacao de tendencias em mercados financeiros e a identificacao de objetos de interesse

em dados de imagens. Han and Kamber (2001) utilizam como exemplo de aplicacao desta

tarefa a aprovacao de credito, o diagnostico medico e as campanhas de marketing.

Ainda existem outros tipos de tarefas desempenhadas por tecnicas de Mineracao de

Dados como a Associacao, a Regressao, a Clusterizacao e a Sumarizacao.

4.2 Metodos e Algoritmos de Classificacao

Como citado anteriormente, o processo de classificacao envolve a construcao de um mo-

delo, realizada por um algoritmo de aprendizado a partir de uma analise sobre um conjunto

de treinamento.


Figura 4.4: Atributos disponıveis para a construcao da arvore de decisao para o problemade esperar ou nao uma mesa em um restaurante

4.2.1 Classificacao por Inducao de Arvores de Decisao

Segundo Russell and Norvig (2004), inducao de arvores de decisao e um dos algoritmos

de aprendizado de maior sucesso mesmo sendo um dos mais simples, porem nao existe

algum tipo de representacao que seja eficiente para todos os tipos de funcoes. Uma arvore

de decisao recebe como entrada um conjunto de atributos e retorna uma decisao (valor

previsto de acordo com a entrada) como saıda. Esta decisao e alcancada com a execucao

de uma sequencia de testes.

De acordo com Merschmann (2007), os nos internos da arvore representam testes sobre

atributos, os ramos representam resultados possıveis do teste e os nos folha representam

valores a serem retornados.

Segundo Merschmann (2007), o processo de construcao de uma arvore de decisao e

chamado inducao. Russell and Norvig (2004) traz um exemplo de arvore de decisao

caracterizado pelo problema de esperar ou nao uma mesa em um restaurante. Para

entender este exemplo como um problema de aprendizagem e preciso declarar os atributos

disponıveis.

A figura 4.4, reproduzida de Russell and Norvig (2003), apresenta os atributos dispo-

nıveis.

Segundo os autores, os atributos Preco e Tipo nao sao utilizados na arvore porque

foram considerados irrelevantes por ela. Este exemplo apresentado trata de uma arvore


Figura 4.5: Exemplo de arvore de decisao para o problema de esperar ou nao uma mesaem um restaurante - figura reproduzida de Russell and Norvig (2003)

de decisao booleana, na qual cada exemplo e classificado como verdadeiro ou falso, ou seja,

espera-se a mesa ou nao. Cada exemplo consiste em um vetor de atributos de entrada e

um unico valor de saıda, e o conjunto completo de exemplos e o conjunto de treinamento.

De acordo com Russell and Norvig (2004), a arvore deve ser capaz de extrair padroes

e informacoes de exemplos que ela ainda nao viu, ou seja, nao deve memorizar apenas os

exemplos de treinamento. Para isso, aplicando a lamina de Ockham, deve-se encontrar a

menor arvore de decisao que seja consistente com os exemplos.

Segundo Merschmann (2007), a maioria dos algoritmos de inducao de arvores de deci-

sao constroi a arvore recursivamente, de cima para baixo, ou seja, do no raiz em direcao

aos nos folha. A partir da base de dados de treinamento, os algoritmos procuram pelo

atributo que melhor separa as classes para realizar a ramificacao da arvore e, recursiva-

mente, processa os subproblemas resultantes. Segundo Russell and Norvig (2004), a ideia

basica e testar primeiro o atributo mais importante, ou seja, aquele considerado mais

relevante na classificacao de uma entrada, para obter uma arvore com o mınimo numero

de testes realizados.

A figura 4.6, reproduzida de Russell and Norvig (2003), apresenta o algoritmo de

aprendizagem de arvore de decisao.

Segundo Russell and Norvig (2004), ha quatro casos a serem considerados:


Figura 4.6: Representacao do algoritmo de aprendizagem de arvode de decisao

• Se existem exemplos positivos e negativos, o melhor atributo para dividi-los deve

ser escolhido.

• Se todos os exemplos restantes forem positivos ou negativos, entao ja e possıvel

obter a resposta.

• Se nao resta nenhum exemplo, significa que nenhum exemplo deste tipo foi observado

durante o treinamento, entao um valor padrao deve ser retornado.

• Se ainda restam exemplos, mas nao restam atributos, quer dizer que os exemplos

tem a mesma descricao, mas classificacao diferente. Isso ocorre quando ha dados

incorretos, ou seja, quando os dados possuem ruıdo. Pode ocorrer tambem quando

os atributos nao apresentam informacoes suficientes para descrever a situacao ou

quando o domınio e nao determinıstico.

Como ja foi exposta, a ideia basica do algoritmo e testar primeiramente o atributo

mais importante. Segundo Russell and Norvig (2004), esta ideia e escolher o atributo que

tenha maior alcance na tentativa de fornecer uma classificacao exata para os exemplos, de

modo a minimizar a profundidade da arvore. Um atributo perfeito e aquele que divide os

exemplos em conjuntos de tal forma que os exemplos do conjunto sejam todos positivos

ou todos negativos.


Figura 4.7: Divisao dos exemplos por meio de testes em atributos, baseado no conjuntode exemplos

A figura 4.7, reproduzida de Russell and Norvig (2003), ilustra a divisao de exemplos

atraves de testes em atributos, baseado no conjunto de exemplos apresentado na figura

4.4.

A figura 4.7 mostra que Tipo nao e um bom atributo, pois apresenta quatro resultados

possıveis, cada um com o mesmo numero de exemplos positivos e negativos. O atributo

Cliente nao chega a ser um atributo perfeito, mas e um bom atributo, pois dos tres

resultados possıveis, apenas um deles conta com exemplos mistos.

Segundo Russell and Norvig (2004), o melhor atributo e escolhido de acordo com o

ganho de informacao obtido a partir dele. A teoria da informacao mede o conteudo de

informacao em bits, sendo que um bit de informacao e suficiente para responder uma

pergunta com resposta sim/nao. Se vi sao as respostas possıveis com probabilidade P (vi),

entao a quantidade de informacao necessaria para chegar a resposta e:

I(P (v1), ..., P (vn)) =n∑

i=1

−P (vi) log2 P (vi) (4.1)

Supondo que o conjunto de treinamento possua p exemplos positivos e n exemplos

negativos, uma estimativa das informacoes contidas em uma resposta correta e:

I(p

p + n,

n

p + n) = − p

p + nlog2

p

p + n− n

p + nlog2

n

p + n(4.2)

O conjunto de treinamento apresentado na figura 4.4 tem p = 6 e n = 6, assim, de

acordo com a equacao citada anteriormente precisamos de um bit de informacao.

De acordo com Russell and Norvig (2004), o ganho de informacao a partir de um

atributo A e a diferenca entre o requisito de informacoes original e o novo requisito.

Entenda-se por novo requisito a quantidade de informacoes ainda necessaria para chegar


a resposta, apos o teste do atributo A. A equacao para calcular o ganho de informacao,

sendo que Restante representa o novo requisito de informacao, e:

Ganho(A) = I(p

p + n,

n

p + n) −Restante (4.3)

Qualquer atributo A testado divide o conjunto de treinamento em subconjuntos de

acordo com os valores possıveis para A, sendo que A tem v valores possıveis e cada

subconjunto tem pi exemplos positivos e ni exemplos negativos, deste modo, seguindo ao

longo desta ramificacao sera necessario I(pi/(pi + ni)), ni/(pi + ni)) bits de informacoes

para obter uma resposta. Segundo o autor, um exemplo qualquer escolhido a partir

de um conjunto de treinamento tem o i-esimo valor para o atributo com probabilidade

(pi + ni)/(p + n). Desta forma e possıvel conhecer o valor de Restante(A) da seguinte

forma:

Restante(A) =v∑

i=1

pi + ni

p + nI(

pipi + ni

,ni

pi + ni

) (4.4)

De acordo com Russell and Norvig (2004), o ganho de informacao para os atributos

utilizados como exemplo na figura 4.7, comprovando que o atributo Cliente e melhor que

o atributo Tipo, e:

Ganho(Clientes) = 1 − [2

12I(0, 1) +

4

12I(1, 0) +

6

12I(

2

6,4

6)] ≈ 0, 541bits (4.5)

Ganho(Tipo) = 1 − [2

12I(

1

2,1

2) +

2

12I(

1

2,1

2) +

4

12I(

1

2,1

2) +

4

12I(

2

6,4

6)] = 0 (4.6)

Segundo Russell and Norvig (2004), o desempenho de um algoritmo de aprendizado

e considerado bom quando resulta em hipoteses que classifiquem exemplos nao vistos

durante o treinamento de maneira correta. A qualidade de uma hipotese pode ser avaliada

comparando-se as suas previsoes com as classificacoes reais, atraves de um conjunto de

testes aplicado a hipotese, que deve ser um conjunto que nao tenha nenhum elemento em

comum com o conjunto de treinamento.


De acordo com Russell and Norvig (2004), a poda de arvore de decisao e uma tecnica

usada para selecionar uma arvore com melhor desempenho de classificacao. A poda tem

por objetivo impedir a divisao recursiva feita pelo algoritmo de aprendizado sobre atribu-

tos que nao sejam claramente relevantes, sendo que o ganho de informacao e considerado

uma boa medida de relevancia. Segundo os autores, as arvores com poda funcionam

significantemente melhor que as sem poda quando ha grande quantidade de ruıdo nos

dados, e complementam, ressaltando que as arvores com poda sao menores e de mais facil

compreensao.

Segundo os mesmos autores, a validacao cruzada e outra tecnica utilizada, inclusive

em conjuntos com outras tecnicas, para selecionar uma arvore com bom desempenho de

previsao. Segundo Witten and Frank (2005), esta tecnica reserva uma porcentagem de

exemplos para teste e usa o restante para o treinamento da arvore. Na validacao cruzada

e decidido um numero fixo de fold, ou particoes de dados. Na pratica, o numero padrao

de folds, aceito apos inumeros testes com diferentes tecnicas de aprendizagem, e dez. Os

dados sao divididos aleatoriamente em 10 partes, nas quais a classe e representada nas

mesmas proporcoes que no conjunto de dados completo. Segundo Russell and Norvig

(2004), em uma validacao cruzada de K folds sao executados k experimentos, reservando,

em cada experimento, uma fracao 1/k diferente dos dados para testes e, ao final, calcula-se

a media dos resultados.

4.3 Classes Desbalanceadas

Segundo Prati (2006), um dos aspectos que pode influenciar o desempenho de um mo-

delo de classificacao ocorre quando uma classe e representada por um grande numero de

exemplos, enquanto que a outra classe e representada por poucos exemplos. A classe com

muitos exemplos e chamada de classe majoritaria e a com poucos exemplos e chamada de

classe minoritaria.

De acordo com Batista (2003), a maioria dos sistemas de aprendizado assume que

as classes encontram-se balanceadas, o que explica o fato desses sistemas falharem ao

induzir um classificador que seja capaz de predizer com precisao a classe minoritaria na

ocorrencia de dados desbalanceados. Tal situacao deve ser considerada, pois geralmente


a classe minoritaria e a de maior interesse.

Prati (2006) e Batista (2003) destacam que diversos pesquisadores - Fawcett and Pro-

vost (1997); Kubat et al. (1998); Weiss and Provost (2003); Han et al. (2005); Tang and

Liu (2005) - tem analisado o problema do aprendizado a partir de dados com classes

desbalanceadas e elaborado alguns metodos para a sua solucao.

Segundo Prati (2006), existem duas abordagens utilizadas com maior frequencia que

tratam diretamente do problema, buscando balancear artificialmente a distribuicao de

exemplo nas classes: a Under-sampling e a Over-Sampling. A primeira abordagem visa

balancear o conjunto de dados atraves da remocao de exemplos da classe majoritaria,

enquanto que a outra abordagem visa o balanceamento atraves da replicacao de exemplos

da classe minoritaria. Metodos baseados nestas abordagens sao realizados pela tecnica de

Amostragem Estratificada presente na etapa de Selecao de Dados (capıtulo 3, secao 3.1).

Capıtulo 5

Pos-Processamento

Segundo Goldschmidt and Passos (2005), nesta ultima etapa do processo de descoberta de

conhecimento, considerada uma das mais importantes, o objetivo e analisar e interpretar

os padroes obtidos na etapa de data mining para identificar quais destes padroes pode

ser considerado um novo conhecimento referente ao domınio da aplicacao. De acordo com

Fayyad et al. (1996), o proximo passo e consolidar o conhecimento gerado incorporando-

o dentro de outros sistemas, documentando-o ou utilizando-o no auxılio a tomada de

decisao.

Fayyad et al. (1996) ainda afirma que, nesta etapa, o analista de KDD avalia a necessi-

dade de reiniciar ou nao a execucao de qualquer uma das etapas ou sub-etapas anteriores

na tentativa de buscar melhores resultados.

Goldschmidt and Passos (2005) considera as seguintes tarefas pertencentes a esta etapa

do processo:

• Simplificacoes do Modelo de Conhecimento

Nesta tarefa o objetivo e reduzir o volume de padroes gerados, a fim de facilitar o

entendimento do modelo gerado.

• Transformacoes do Modelo de Conhecimento

Esta tarefa tem por objetivo converter um modelo de conhecimento em outro modelo

existente, de forma a tornar mais facil o seu entendimento.

• Organizacao e Apresentacao dos Resultados

24

CAPITULO 5. POS-PROCESSAMENTO 25

O objetivo desta tarefa e visualizar em duas ou tres dimensoes o modelo de conhe-

cimento gerado, atraves do uso de tabelas, arvores, graficos, planilhas, entre outros,

visando a facilidade no entendimento do modelo.

Capıtulo 6

Ferramenta WEKA

6.1 Caracterısticas

Segundo Witten and Frank (2005), experiencias mostram que nao ha um unico esquema

de aprendizado de maquina que seja apropriado para todos os problemas de Mineracao

de Dados.

De acordo com Waikato (2008), WEKA e uma colecao de algoritmos de aprendizagem

de maquina e ferramentas de pre-processamento de dados desenvolvida pela University

of Waikato, Nova Zelandia. O nome da ferramenta e uma sigla para Waikato Environ-

ment for Knowledge Analysis. O sistema da ferramenta foi implementado em Java, e

multiplataforma e e distribuıdo sob os termos da GNU.

O programa fornece implementacoes de algoritmos de aprendizagem, com uma inter-

face uniforme para eles, juntamente com metodos para pre e pos-processamento de dados

e para avaliacao de resultados. Inclui metodos para classificacao, regressao, clusterizacao,

regras de associacao e selecao de atributos.

Para todos os algoritmos, a entrada e representada na forma de uma tabela relacional

incluıda em um arquivo no formato ARFF. Segundo Goldschmidt and Passos (2005), o

WEKA suporta a abertura direta de arquivos nos formatos ARFF, CSV, C45, porem,

manipula apenas o formato ARFF. A figura 6.1 mostra uma representacao de um arquivo

de exemplo no formato ARFF.

De acordo com o mesmo autor, um arquivo no formato ARFF e constituıdo da seguinte

maneira: as linhas do arquivo iniciadas pelo caractere “%”sao consideradas comentarios.

26

CAPITULO 6. FERRAMENTA WEKA 27

Figura 6.1: Exemplo de arquivo no formato ARFF utilizado como entrada na ferramentaWEKA


Em seguida, e mostrado o nome da relacao em questao (@relation) e um bloco de infor-

macoes indicando os atributos da relacao (@attribute) e os valores possıveis que podem

assumir (se for numerico apenas e indicado o tipo numeric). O ultimo bloco de informa-

coes representa o conjunto de dados em si (@data).

De acordo com Goldschmidt and Passos (2005), o WEKA permite a visualizacao gra-

fica de dados em forma de histogramas, a apresentacao de resultados em arvores de decisao

e diagramas de dispersao e modelos graficos para montagem de redes neurais. As figu-

ras exemplificam o resultado da execucao de um algoritmo de classificacao por arvore de

decisao do WEKA, o J4.8.

Segundo Goldschmidt and Passos (2005), quatro implementacoes de interface podem

ser utilizadas, sendo que estas podem ser executadas diretamente via codigo Java. Sao

elas:

• Simple Cient - a interacao com o usuario ocorre por linhas de comando, por isso,

exige conhecimento profundo do programa.

• Explorer - e a interface mais comum, que disponibiliza separadamente as etapas

de pre-processamento, mineracao de dados e pos-processamento.

• Experimenter - ambiente em podem ser avaliados os desempenhos dos algoritmos

de aprendizagem atraves de avaliacoes estatısticas.

• KnowledgeFlow - ferramenta grafica, ainda em desenvolvimento, que permite

criacao de um fluxo de processos de KDD.

Mais algumas informacoes e caracterısticas da ferramenta podem ser encontradas na

tabela 6.1, reproduzida de Goldschmidt and Passos (2005).

6.2 Selecao de Atributos

A tecnica de selecao de atributos utilizada neste trabalho e conhecida como Correlation-

based Feature, implementada no WEKA com o nome de CfsSubsetEval, sendo que este

metodo e utilizado juntamente com uma heurıstica de busca, tambem implementada no

WEKA. Neste caso, a heurıstica de busca escolhida foi a BestFirst.


Tabela 6.1: Algumas caracterısticas da ferramenta WEKA

Caracterısticas Valores

Acesso a Fontes de Dados Heterogeneas Sim

Integracao de Conjuntos de Dados Nao

Facilidade para Inclusao de Novas Operacoes Sim

Facilidade para Inclusao de Novos Metodos Sim

Recursos para Planejamento de Acoes Sim

Processamento Paralelo/Distribuıdo Nao

Visualizacao Distribuicao deFrequencias; Medi-das de Dispersao;Histogramas

Reducao de Dados AmostragemLimpeza de Dados Substituicao

Operacoes/Metodos Codificacao de Dados Discretizacao automa-tica e manual

Disponıveis Classificacao Arvores de Deci-sao, Bayes, RedesNeurais...

Clusterizacao Simple-KMeans,Cobweb, Farthest-First...

Simplificacao de Resultados N/DOrganizacao de Resultados Agrupamento de Pa-

droes; Ordenamentode Padroes

Apresentacao de Resultados Conjunto de Regras;Arvores de Decisao

Estruturas para Armazenamento de Modelos de Conhecimento Sim

Estruturas para Armazenamento de Historicos de Acoes Sim

Segundo Merschmann (2007), os metodos Cfs avaliam subconjuntos de atributos, le-

vando em consideracao a capacidade de discriminacao dos atributos em relacao a classe

e em relacao aos proprios atributos. Quanto maior for a correlacao dos atributos com

a classe e menor a correlacao entre eles, maior e a pontuacao do subconjunto, ou seja,

melhor e o subconjunto.

De acordo com o mesmo autor, atraves da heurıstica de busca, o Cfs percorre o espaco

de solucoes para encontrar o subconjunto adequado. A estrategia BestFirst trabalha de

forma que, a cada iteracao, a solucao corrente e expandida, gerando solucoes vizinhas e

movendo-se para a melhor solucao gerada ate o momento e que ainda nao tenha sido ex-

pandida. Segundo o autor, solucoes geradas em iteracoes anteriores podem ser escolhidas,


Figura 6.2: Janela para configuracao dos parametros do algoritmo J4.8

desde que ainda nao tenham sido expandidas.

6.3 Algoritmo de Classificacao J4.8

O algoritmo para classificacao atraves de inducao de arvores de decisao disponibilizado

pelo WEKA e utilizado neste trabalho e o J4.8. Segundo Witten and Frank (2005), o

J4.8 e uma versao melhorada do popular algoritmo C4.5, tambem conhecido como C4.5

revision 8. Segundo o autor, este algoritmo deu origem ao C5.0, que e um algoritmo de

grande sucesso comercial na area de machine learning.

O WEKA permite a configuracao de alguns parametros antes da execucao do algo-

ritmo. A figura, 6.2, apresenta a janela para configuracao dos parametros de execucao do

algoritmo J4.8.

De acordo com Witten and Frank (2005) e Waikato (2008), tais parametros represen-


tam:

• binarySplits: relevancia para usar divisao binaria sobre atributos nominais para

construir arvores;

• confidenceFactor : fator de confianca para a poda, sendo que valores menores

indicam maior poda;

• minNumObj : determina o numero mınimo de instancias por folha;

• numFolds: determina o tamanho do conjunto para poda, os dados sao divididos

em folds, um e usado para a poda e os outros continuam na construcao da arvore;

• saveInstanceData : determina se os dados originais devem estar disponıveis para

posterior consulta;

• reducedErrorPruning : em substituicao a poda padrao do algoritmo, e possıvel

escolher a reducao do erro da poda;

• seed : parametro que informa o numero de sementes que serao selecionadas aleato-

riamente quando for utilizado o parametro reducedErrorPruning ;

• subtreeRaising : operacao para substituir o no interno da arvore por um dos nos

que estao abaixo;

• unpruned : determina a nao utilizacao da operacao de poda;

• useLaplace: determina a utilizacao do nivelamento de Laplace para predicao pro-

babilıstica.

Alem destes parametros, tambem e possıvel escolher um conjunto de treinamento e

ativar a validacao cruzada.

As figuras, 6.3 e 6.4, mostram o modelo de resultado da execucao do algoritmo J4.8

na ferramenta WEKA.

A figura 6.5, contida na figura 6.3, representa, em detalhe, a arvore de decisao gerada

pelo algoritmo J4.8 da ferramenta WEKA.


Figura 6.3: Exemplo de resultado da execucao do algoritmo de classificacao por arvorede decisao J4.8 na ferramenta WEKA - Arvore de decisao e porcentagens de instanciasclassificadas correta e incorretamente


Figura 6.4: Exemplo de resultado da execucao do algoritmo de classificacao por arvore dedecisao J4.8 na ferramenta WEKA - Matriz de confusao

Figura 6.5: Arvore de decisao gerada pela execucao do algoritmo de classificacao J4.8


Figura 6.6: Matriz de confusao gerada pela execucao do algoritmo de classificacao J4.8

Figura 6.7: Exemplo grafico da arvore de decisao gerada como resultado da execucao doalgoritmo de classificacao J4.8 na ferramenta WEKA

Segundo Witten and Frank (2005), os numeros entre parenteses indicam o numero

de instancias que atingiram cada folha. Se esta representacao estiver no formato, por

exemplo, (4.0/1.0) significa que quatro instancias chegaram ate a folha, sendo que, destas

quatro, uma foi classificada incorretamente.

A figura 6.6, contida na figura 6.4, representa, em detalhe, a matriz de confusao (secao

4.1.1) gerada pelo algoritmo de classificacao J4.8 da ferramenta WEKA.

A figura 6.7 mostra uma representacao grafica, gerada pela ferramenta WEKA, para

a arvore de decisao encontrada.

Capıtulo 7

Estudo de Caso

7.1 Base de Dados

Os dados utilizados para este estudo foram os dados dos processos seletivos de verao dos

anos de 2007, 2008 e 2009 da Universidade Federal do Rio Grande (FURG), dados estes

que nunca haviam sido explorados para atividades de data mining. Os dados encontram-se

armazenados nos servidores do Nucleo de Tecnologia da Informacao (NTI) da FURG, e fo-

ram disponibilizados sob autorizacao da Comissao Permanente de Vestibular (COPERVE)

da Universidade.

Foram utilizados dados de diferentes fontes:

• Ficha de inscricao dos candidatos, excluindo dados de identificacao pessoal;

• Questionario socio economico preenchido no momento da inscricao (Apendice A);

• Dados referentes ao desempenho do candidato.

Os dados sao armazenados, manipulados, e gerenciados atraves do SGBD PostgreSql

8.2.

A figura 7.1 apresenta um diagrama Entidade-Relacionamento (ER) do banco de dados

em questao.

35

CAPITULO 7. ESTUDO DE CASO 36

Figura 7.1: Diagrama Entidade-Relacionamento que representa a base de dados originalutilizada para a coleta dos dados utilizados neste estudo de caso

7.2 Coleta e Pre-Processamento dos Dados

Para formar o conjunto de dados a ser analisado, os dados foram coletados das diferentes

fontes citadas e organizados em uma unica estrutura atraves de uma juncao orientada,

utilizando a linguagem SQL. Esta tecnica foi escolhida para facilitar o pre-processamento

dos dados e, posteriormente, a geracao dos arquivos no formato ARFF.

Para formar a tabela unica foi feita uma consulta - query - SQL. O trecho de codigo,

7.1, representa um resumo da query utilizada.

Codigo 7.1: Trecho de codigo que representa um resumo da query utilizada para formar

a tabela unica

1 select <<dados>> from f i c h a s f

2

3 join cur so s on ( cur so s . cd curso = f . cd curso and cur so s . c d v e s t i b u l a r = f .

c d v e s t i b u l a r )

4

5 where f . c d v e s t i b u l a r = ’2007VN’ or f . c d v e s t i b u l a r = ’2008VN’ or f .

c d v e s t i b u l a r = ’2009VN’

6


7 order by n r i n s c r i c a o

Nesta mesma query, foram executadas tecnicas de reducao horizontal dos dados.

Os dados foram segmentados utilizando, como atributo guia, o atributo correspondente

ao codigo do vestibular, que especifica o processo seletivo em questao. Por exemplo,

cd vestibular = ‘2009VN’ identifica o processo seletivo de verao para ingresso em 2009.

Alem disso, para tratar o problema das classes desbalanceadas, foram usadas amostras

estratificadas de cada curso de modo a igualar o numero de candidatos aprovados e repro-

vados - situacao = ‘A’ e situacao = ‘R’ respectivamente - para cada curso. Os trechos

de codigo 7.2 e 7.3 fazem referencia a estas acoes.

Codigo 7.2: Trecho de codigo SQL que representa a fracao da query que realiza a reducao

horizontal dos dados

1 where f . c d v e s t i b u l a r = ’2007VN’ or f . c d v e s t i b u l a r = ’2008VN’ or f .


Codigo 7.3: Trecho de codigo SQL que representa a fracao da query que realiza a amos-

tragem estratificada do curso de Direito, para o vestibular de codigo ‘2007VN’

1 ( select c d v e s t i b u l a r , c idade , idade , sexo , s i tuacao , r e spo s ta

2 from t c c v e s t i b u l a r where cd curso = 51 and s i tuacao = ’A’ and

c d v e s t i b u l a r = ’2007VN’ and r e spo s ta i s not null )

3 union

4 (

5 select c d v e s t i b u l a r , c idade , idade , sexo , s i tuacao , r e spo s ta

6 from

7 ( select ∗ , random ( ) as r

8 FROM t c c v e s t i b u l a r where cd curso = 51 and s i tuacao = ’R’

9 order by r ) as t r ep

10 where cd curso = 51 and s i tuacao = ’R’ and c d v e s t i b u l a r = ’2007VN’ and

r e spo s ta i s not null order by t r ep . r l imit 65

11 )

Alem da reducao horizontal, foi realizada a reducao vertical do dados, ja que foram

eliminados atributos diretamente atraves da query, ou seja, nao foram especificados no

comando de selecao da consulta SQL. Estes atributos apresentaram inconsistencias, ou

foram julgados desnecessarios ou inapropriados para os objetivos deste trabalho.


Os atributos referentes a identificacao pessoal dos candidatos sao um bom exemplo de

dados inapropriados. Um outro exemplo, referente a dados desnecessarios, sao os atributos

relativos as provas do processo seletivo (local de prova, pontuacoes e desempenho do

candidato) e algumas questoes socio-economicas, como a profissao dos pais e o tipo de

curso fundamental e medio, o ano de conclusao do ensino medio, e a escola que o candidato

concluiu os estudos.

A tecnica de reducao de valores foi utilizada para diminuir o numero de valores pos-

sıveis para cada atributo. Neste caso especıfico, foi usada para reduzir o numero de

alternativas de respostas tanto para dados da ficha de inscricao, quanto para questoes do

questionario socio economico. Por exemplo, o atributo estado civil passou de cinco alter-

nativas possıveis, para tres. Outro bom exemplo e o do atributo cidade (cidade de origem

do candidato), que passou de todas as cidades possıveis para os valores ‘Rio Grande’ e

‘Outras’. O trecho de codigo 7.4 em linguagem SQL referencia esta tecnica.

Codigo 7.4: Trecho de codigo SQL que representa a fracao da query que realiza a reducao

de valores para o atributo cidade, para o vestibular de codigo ‘2009VN’

1 CASE WHEN trim ( t o a s c i i (upper ( nm cidade ) ) ) in

2 ( select

3 trim ( t o a s c i i (upper ( nm cidade ) ) )

4

5 FROM f i c h a s where c d v e s t i b u l a r = ’2009VN’

6

7 AND trim ( t o a s c i i (upper ( nm cidade ) ) ) i l i k e ’R%DE%’

8 AND nm cidade != ’RIO DE JANEIRO’

9

10 order by trim ( t o a s c i i (upper ( nm cidade ) ) ) desc

11 ) THEN ’RIO_GRANDE’

12 ELSE ’OUTRAS’

13 END as c idade

O unico atributo criado foi o atributo idade, cujos valores possıveis foram mapeados

em faixas etarias, ou seja, em intervalos especıficos. A criacao deste atributo foi feita na

consulta SQL, sendo que a idade e conhecida atraves da data de nascimento do candidato.

O trecho de codigo, 7.5, representa a criacao do atributo idade.


Codigo 7.5: Trecho de codigo SQL que representa a fracao da query que realiza a criacao

do atributo idade, para o vestibular de codigo ‘2009VN’

1 CASE

2 WHEN to number ( to char ( dt nasc , ’YYYY’ ) , ’9999’ ) >= ’1990’ THEN ’

menor20’

3 WHEN to number ( to char ( dt nasc , ’YYYY’ ) , ’9999’ ) < ’1990’ AND

to number ( to char ( dt nasc , ’YYYY’ ) , ’9999’ ) >= ’1984’ THEN ’20_25’

4 ELSE ’maior26’

5 END as idade

A limpeza de dados ruidosos ou inconsistentes foi feita utilizando a tecnica de exclusao

de casos ou atributos. Por exemplo, apos analise quantitativa de respostas isoladas, foi

verificada no questionario socio economico uma quantidade discrepante (mais de 50% do

total) de pessoas residindo atualmente no Acre (primeira opcao para escolha no questi-

onario), entao, apos comparacao com os enderecos nas fichas de inscricao, foi excluıdo o

atributo referente a residencia atual. A exclusao de atributos e de casos referida e feita

apenas nao selecionando tais dados na query.

Ressaltamos que todas estas acoes foram executadas na mesma query SQL e esta esta

em anexo (Apendice B).

Durante a execucao do pre-processamento dos dados foi possıvel confirmar o consenso

existente na bibliografia de que esta etapa e fundamental para o sucesso dos algoritmos de

mineracao de dados e e a etapa do processo de KDD que demanda mais tempo e esforco

de quem esta conduzindo o processo.

7.3 Data Mining na ferramenta WEKA

7.3.1 Arquivo no formato ARFF

Apos a coleta e pre-processamento dos dados, e gerado o arquivo no formato ARFF

para execucao no WEKA, utilizando a interface Explorer (secao 6.1). O PgAdmin III,

aplicativo utilizado para gerenciar o SGBD Postgresql 8.2, permite que o resultado da

execucao de uma query seja escrito em arquivo. Assim, apos algumas formatacoes no

resultado da consulta escrito em arquivo, e gerado um arquivo no formato ARFF para


Figura 7.2: Arquivo no formato ARFF, contendo somente um registro para exemplificacao,para o curso de Medicina

cada curso a ser analisado.

A figura, 7.2, ilustra um exemplo do arquivo no formato ARFF, contendo somente um

registro, para o curso de Medicina.

7.3.2 Selecao de Atributos

Antes do conjunto de dados ser submetido ao algoritmo de mineracao de dados propria-

mente dito, neste caso o algoritmo de classificacao, e executado sobre este conjunto um

algoritmo de selecao de atributos implementado no WEKA. Neste trabalho, foi utilizado

o algoritmo CfsSubsetEval, associado com a heurıstica de busca BestFirst, que executa

uma busca bidirecional no conjunto de dados (secao 6.2).


7.3.3 Algoritmo de Classificacao

Depois de selecionados os atributos pelo algoritmo do WEKA, e executado o algoritmo

de classificacao J4.8 do WEKA sobre o conjunto de dados. Este e um algoritmo para

classificacao por inducao de arvores de decisao (secoes 4.2.1 e 6.3).

Nos testes realizados, foram utilizados os parametros padroes do algoritmo J4.8, com

excecao do parametro confidenceFactor, alterado para 0.2 para aumentar a poda em busca

de um melhor desempenho e de uma arvore menor e, portanto, mais compreensıvel. Tam-

bem foi usada validacao cruzada com 10 folds, ou seja, sao realizados 10 experimentos,

reservando a cada experimento, uma fracao 110

dos dados para teste e, ao final, e calculada

a media de resultados (secao 4.2.1).

O atributo classe escolhido, tanto para selecao de atributos do WEKA, quanto para

o algoritmo de classificacao foi o atributo situacao, que apresenta os seguintes valores

possiveis: ‘A’ (para aprovado) ou ‘R’ (para reprovado).

7.4 Demonstracao dos Resultados

Para demonstracao dos resultados deste trabalho foram escolhidos quatro cursos especı-

ficos, sao eles: Medicina, Direito, Engenharia de Computacao e Engenharia Mecanica.

Apos execucao dos algoritmos citados na secao 7.3, utilizando um arquivo no formato

ARFF para cada curso, foram obtidos os seguintes resultados para os diferentes cursos

analisados.

Em media, o ındice de instancias classificadas corretamente pelo algoritmo J4.8 da

ferramenta WEKA, para os 4 cursos analisados, foi de 63.1720%, o que representa um bom

nıvel de acerto segundo a literatura consultada. Consequentemente, a porcentagem de

instancias classificadas incorretamente pelo mesmo algoritmo foi de, em media, 37.0781%,

como pode ser visto na tabela 7.1.

7.4.1 Medicina

Na tabela 7.2 encontram-se os atributos selecionados para o curso de Medicina pela fer-

ramenta WEKA e os respectivos dados reais a que eles se referem.


Tabela 7.1: Indices de instancias classificadas correta e incorretamente na execucao doalgoritmo de classificacao J4.8 na ferramenta WEKA para os cursos em analise

Curso Acerto Erro

Medicina 65.1089 % 35.8911 %

Direito 61.6915 % 38.3085 %

Eng. Computacao 61.2000 % 38.8000 %

Eng. Mecanica 64.6875 % 35.3125 %

Media 63.1720 % 37.0781 %

Tabela 7.2: Atributos selecionados na ferramenta WEKA para o curso de Medicina

Atributo Referencia

idade Ficha de Inscricao: Idade do candidato no ano em que participou doProcesso Seletivo

cursinho Questionario: “Voce frequentou/frequenta curso-pre vestibular?”

tentativas Questionario: “Ha quantos anos voce esta tentando ingressar na suaopcao de curso?”

salarios Questionario: “Qual a renda que compoe o orcamento de sua resi-dencia? (Soma dos salarios brutos de todos os residentes).”

Apos a selecao de atributos, foi executada a etapa de data mining na ferramenta

WEKA somente com os atributos anteriormente selecionados. A figura 7.3 representa a

arvore de decisao gerada pela ferramenta para o curso de Medicina.

A figura 7.4 ilustra a arvore de decisao gerada pela ferramenta WEKA.

De acordo com a matriz de confusao, representada na tabela 7.3, encontrada apos a

geracao da arvore de decisao para o curso de Medicina, nota-se que o algoritmo apren-

deu com mais eficiencia a classificar as instancias relacionadas a condicao “Aprovado” do

atributo classe situacao, visto que a proporcao de instancias com condicao “Aprovado”

classificadas corretamente e de aproximadamente 76.23% (154 instancias corretas de 202

com condicao “Aprovado”) ante a porcentagem de classificacoes corretas para instancias

com condicao “Reprovado” que foi de aproximadamente 51.98% (105 instancias corretas

de 202 com condicao “Reprovado”).

Tabela 7.3: Matriz de confusao do algoritmo de classificacao gerada pela ferramentaWEKA para o curso de Medicina

a b <= classificado como

154 48 a = A

97 105 b = R


Figura 7.3: Arvore de decisao gerada pela ferramenta WEKA para o curso de Medicina

7.4.2 Direito

Na tabela 7.4 encontram-se os atributos selecionados pela ferramenta WEKA e os respec-

tivos dados reais a que eles se referem, para o curso de Direito.

Tabela 7.4: Atributos selecionados na ferramenta WEKA para o curso de Direito

Atributo Referencia

turno Questionario: “Em que turno voce cursou o ensino medio?”


outro curso Questionario: “Voce ja iniciou algum curso superior?”




arvore de decisao gerada pela ferramenta para o curso de Direito.



geracao da arvore de decisao para o curso de Direito, nota-se que o algoritmo aprendeu com

mais eficiencia a classificar as instancias relacionadas a condicao “Aprovado” do atributo

classe situacao, visto que a proporcao de instancias com condicao “Aprovado” classificadas

corretamente e de aproximadamente 64.67% (130 instancias corretas de 201 com condicao


Figura 7.4: Ilustracao da arvore de decisao gerada pela ferramenta WEKA para o cursode Medicina


Figura 7.5: Arvore de decisao gerada pela ferramenta WEKA para o curso de Direito

Figura 7.6: Ilustracao da arvore de decisao gerada pela ferramenta WEKA para o cursode Direito


“Aprovado”) ante a porcentagem de classificacoes corretas para instancias com condicao

“Reprovado” que foi de aproximadamente 58.70% (118 instancias corretas de 201 com

condicao “Reprovado”).

Tabela 7.5: Matriz de confusao do algoritmo de classificacao gerada pela ferramentaWEKA para o curso de Direito


130 71 a = A

83 118 b = R

7.4.3 Engenharia de Computacao


tivos dados reais a que eles se referem, para o curso de Engenharia de Computacao.

Tabela 7.6: Atributos selecionados na ferramenta WEKA para o curso de Engenharia deComputacao

Atributo Referencia

ens fund Questionario: “Em que tipo de estabelecimento de ensino voce cursouseus estudos do ensino fundamental?”


escolha Questionario: “Qual o principal motivo na escolha do curso para quevoce esta se inscrevendo?”

atividade Questionario: “Qual a sua ocupacao?”

pessoa renda Questionario: “Qual o numero de pessoas com atividade remuneradaem sua residencia?”


tem internet Questionario: “Voce tem computador em sua residencia?”



arvore de decisao gerada pela ferramenta para o curso de Engenharia de Computacao.



geracao da arvore de decisao para o curso de Engenharia de Computacao, nota-se que o

algoritmo aprendeu com mais eficiencia a classificar as instancias relacionadas a condicao


Figura 7.7: Arvore de decisao gerada pela ferramenta WEKA para o curso de Engenhariade Computacao

Figura 7.8: Ilustracao da arvore de decisao gerada pela ferramenta WEKA para o cursode Engenharia de Computacao


“Reprovado” do atributo classe situacao, visto que a proporcao de instancias com condicao

“Reprovado” classificadas corretamente e de 63.20% (79 instancias corretas de 125 com

condicao “Reprovado”) ante a porcentagem de classificacoes corretas para instancias com

condicao “Aprovado” que foi de aproximadamente 59.20% (74 instancias corretas de 125

com condicao “Aprovado”).

Tabela 7.7: Matriz de confusao do algoritmo de classificacao gerada pela ferramentaWEKA para o curso de Engenharia de Computacao


74 51 a = A

46 79 b = R

7.4.4 Engenharia Mecanica


tivos dados reais a que eles se referem, para o curso de Engenharia Mecanica.

Tabela 7.8: Atributos selecionados na ferramenta WEKA para o curso de EngenhariaMecanica

Atributo Referencia

ens fund Questionario: “Em que tipo de estabelecimento de ensino voce cursouseus estudos do ensino fundamental?”

turno Questionario: “Em que turno voce cursou o ensino medio?”

esc pai Questionario: “Qual o nıvel de instrucao de seu pai?”


tentativas Questionario: “Ha quantos anos voce esta tentando ingressar na suaopcao de curso?”

atividade Questionario: “Qual a sua ocupacao?”

sustento Questionario: “Quem e a principal pessoa responsavel pelo seu sus-tento?”



arvore de decisao gerada pela ferramenta para o curso de Engenharia Mecanica.


De acordo com a matriz de confusao, representada na tabela 7.5, encontrada apos

a geracao da arvore de decisao para o curso de Engenharia Mecanica, nota-se que o


Figura 7.9: Arvore de decisao gerada pela ferramenta WEKA para o curso de EngenhariaMecanica

algoritmo aprendeu com mais eficiencia a classificar as instancias relacionadas a condicao

“Aprovado” do atributo classe situacao, visto que a proporcao de instancias com condicao

“Aprovado” classificadas corretamente e de 66.25% (106 instancias corretas de 160 com

condicao “Aprovado”) ante a porcentagem de classificacoes corretas para instancias com

condicao “Reprovado” que foi de aproximadamente 63.12% (101 instancias corretas de 160

com condicao “Reprovado”).

Tabela 7.9: Matriz de confusao do algoritmo de classificacao gerada pela ferramentaWEKA para o curso de Engenharia Mecanica


106 54 a = A

59 101 b = R


Figura 7.10: Ilustracao da arvore de decisao gerada pela ferramenta WEKA para o cursode Engenharia Mecanica


7.5 Obtencao do Conhecimento

As amostras das populacoes, neste caso, dos cursos, foram submetidas aos mesmos algo-

ritmos implementados no WEKA, tanto de selecao de atributos, quanto de classificacao

por inferencia de arvore de decisao.

Primeiramente, foi executado o algoritmo CfsSubset Eval associado a heurıstica de

busca BestFirst sobre a base de dados, formatada no arquivo ARFF de entrada (secao

7.3.2). Assim, e escolhido um conjunto de atributos do qual fazem parte os atributos que

possuem maior correlacao com o atributo classe situacao e menor correlacao entre eles

(secao 6.2).

Ao analisar os atributos escolhidos pelo algoritmo de selecao, para cada curso, e pos-

sıvel perceber que para cursos diferentes o conjunto de atributos de maior correlacao com

a classe situacao nao e o mesmo, assim, podemos dizer que os exemplos de teste dos

diferentes cursos apresentam caracterısticas distintas uns dos outros. No entanto, alguns

atributos sao relevantes para mais de um curso ou para a maioria dos analisados: o atri-

buto cursinho possui alta correlacao com o atributo classe situacao em todos os cursos

analisados; o atributo salario e um atributo relevante em relacao a classe em todos os cur-

sos analisados, com excecao de Eng. Mecanica. O atributo ens fund tem alta correlacao

com a classe para os cursos de Engenharia analisados.

Tambem e possıvel perceber que, em todos os cursos analisados, ha pelo menos um

atributo diretamente relacionado a renda dos candidatos e de suas famılias entre os atri-

butos selecionados, como por exemplo: sustento, salarios e pessoa renda.

Apenas analisando o resultado da selecao de atributos do WEKA sobre as populacoes

podemos confirmar que, para diferentes cursos, os atributos relevantes em relacao a classe

situacao mudam. Embora possam existir algumas semelhancas entre as populacoes, e

improvavel que o conjunto dos atributos mais relevantes seja exatamente o mesmo para

elas, ou seja, e possıvel confirmar a heterogeneidade entre os candidatos para os diferentes

cursos disponibilizados pela Universidade.

Apos a selecao de atributos, foi executado o algoritmo J4.8 sobre o subconjunto de

atributos previamente selecionado, mantendo o atributo classe situacao. Nosso interesse

esta centralizado na matriz de confusao e na arvore de decisao apresentadas como resul-


tado. Atraves da matriz de confusao, temos conhecimento do desempenho quantitativo do

algoritmo de classificacao, ou seja, sabemos quantos exemplos de teste foram classificados

de maneira correta e quantos de forma incorreta, para cada valor possıvel do atributo

classe situacao. Pela arvore de decisao tambem podemos fazer uma analise quantitativa

do algoritmo de classificacao, pois ela fornece a informacao de quantos exemplos atingi-

ram cada no folha e, destes, quantos foram classificados incorretamente. Este resultado

quantitativo, expresso pela arvore de decisao, nao e tao explıcito quanto o apresentado

pela matriz de confusao.

Interpretando a arvore de decisao gerada para o conjunto de entradas chegamos a ou-

tras conclusoes sobre a amostra, alem dos resultados quantitativos. A arvore e construıda

recursivamente do no raiz em direcao aos nos folha testando primeiro os atributos mais

importantes, ou seja, aqueles atributos mais relevantes para classificacao de uma entrada

(secao 4.2.1). Assim, podemos estabelecer a ordem de importancia de cada atributo para

a classificacao do conjunto de dados, sendo que o atributo raiz e o mais importante para

a classificacao.

Seguindo esta interpretacao, a tabela 7.10 apresenta o atributo mais relevante para a

classificacao de cada curso analisado.

Tabela 7.10: Atributos mais relevantes para a classificacao de cada curso analisado

Curso Atributo

Medicina tentativas

Direito salarios

Engenharia de Computacao cursinho

Engenharia Mecanica ens fund

7.5.1 Regras de Classificacao

Atraves da arvore de decisao gerada e possıvel tambem extrair regras de classificacao para

o conjunto de entrada, a partir dos nos da arvore e do ındice de acerto de classificacao

em cada no folha. Sendo assim, foi determinado um fator mınimo de confianca de 63.17%

(media do ındice de classificacoes corretas para os 4 cursos calculada a partir das matrizes

de confusao - Tabela 7.1) para extracao de regras de classificacao para cada conjunto de

dados, a partir do resultado da inducao de arvores de decisao.


E necessaria a utilizacao das tabelas 7.2, 7.4, 7.6 e 7.8 para interpretacao dos rotulos

dos atributos (tentativas, cursinho, salarios, atividade, outro curso, ens fund, etc). A

leitura das regras de classificacao e feita como segue, tendo como exemplo a segunda

regra encontrada para o curso de Medicina.

• Regra: tentativas (Mais Anos) -> salarios (Entre 1 5) -> cursinho (Sim 1ano) ->

Reprovado (86.36%)

• Leitura: Candidatos do curso de Medicina que tem numero de tentativas no vesti-

bular igual a mais de um ano, renda familiar entre 1 e 5 salarios mınimos e tempo

de cursinho preparatorio igual a um ano possui situacao Reprovado no processo

seletivo, com um fator de confianca de 86.36%.

Nos itens subsequentes encontram-se, para cada curso, todas as regras extraıdas que

possuem fator mınimo de confianca de 63.17%.

Medicina

• tentativas (Primeiro Ano) -> Reprovado (80.45%)

• tentativas (Mais Anos) -> salarios (Entre 1 5) -> cursinho (Sim 1ano) -> Repro-

vado (86.36%)

• tentativas (Mais Anos) -> salarios (Entre 5 10) -> Aprovado (64.34%)

• tentativas (Mais Anos) -> salarios (Acima 10) -> Aprovado (66.05%)

Direito

• salarios (Entre 5 10) -> outro curso (Sim) -> Aprovado (70.21%)

• salarios (Entre 5 10) -> outro curso (Nao) -> cursinho (Nao) -> Reprovado

(88.88%)

• salarios (Entre 5 10) -> outro curso (Nao) -> cursinho (Sim Mais 1ano) -> Apro-

vado (71.42%)

• salarios (Acima 10) -> Aprovado (69.33%)



• cursinho (Sim Mais 1ano) -> Aprovado (90.90%)

• cursinho (Sim 1ano) -> atividade (Estudante) -> Aprovado (64.70%)

• cursinho (Nao) -> tem internet (Nao) -> Reprovado (93.33%)

• cursinho (Nao) -> tem internet (Sim) -> ens fund (Fund Particular) -> Aprovado

(76.92%)

• cursinho (Nao) -> tem internet (Sim) -> ens fund (Fund Publica) -> escolha (Mo-

tivo Econ) -> Reprovado (92.85%)

Engenharia Mecanica

• ens fund (Fund Publica) -> tentativas (Primeiro Ano) -> Reprovado (73.78%)

• ens fund (Fund Publica) -> tentativas (Mais Anos) -> atividade (Outra) -> Re-

provado (70.58%)

• ens fund (Fund Publica) -> tentativas (Mais Anos) -> atividade (Estudante) ->

sustento (Pai) -> Aprovado (72.00%)

• ens fund (Fund Particular) -> Aprovado (69.69%)

• ens fund (Fund Misto) -> cursinho (Nao) -> Reprovado (85.71%)

Capıtulo 8

Consideracoes Finais

A ideia central deste trabalho foi a de apresentar conceitos e tecnicas do processo de KDD,

com destaque para os metodos de Data Mining. Com apoio de um software especıfico

para Mineracao de Dados, o WEKA, foi possıvel realizar experimentos sobre os dados

selecionados, com foco nos algoritmos de classificacao por inducao de arvores de decisao.

Foram realizadas atividades, desde a coleta dos dados, atraves de consultas SQL, ate a

extracao de regras de classificacao.

Sendo KDD um grande processo dividido em etapas, durante a pesquisa e estudo de

caso foi possıvel confirmar que o sucesso no desenvolvimento de uma etapa esta intima-

mente ligado ao bom desenvolvimento das etapas anteriores.

O software WEKA foi de extrema importancia, pois fornece uma interface visual que

facilita a manipulacao e visualizacao dos dados, construcao de modelos de Data Mining,

bem como a analise e interpretacao destes, e proporciona meios para encontrar informacoes

implıcitas na base de dados que seriam quase impossıveis de serem descobertas por analise

humana ou por metodos estatısticos convencionais.

Atraves dos algoritmos de selecao de atributos e de classificacao por inducao de arvores

de decisao foi possıvel conhecer as variaveis mais importantes para cada curso na relacao

com o atributo situacao (‘Aprovado’ ou ‘Reprovado’), alem disso, foi possıvel extrair regras

de classificacao para cada curso em relacao a este mesmo atributo a partir dos modelos de

arvores de decisao gerados. Assim, adquirimos novos conhecimentos sobre a base de dados

e sobre a relacao entre as variaveis em questao para cada curso, ou seja, sobre algumas

caracterısticas dos candidatos participantes do processo seletivo.

55

CAPITULO 8. CONSIDERACOES FINAIS 56

Destacamos que o software especıfico para Data Mining nao trabalha sozinho. E

necessaria a compreensao dos dados e conhecimento do domınio da pesquisa, ou seja, e

necessaria a participacao no processo de analistas ou pesquisadores da area para que toda

a atividade seja guiada com qualidade.

Como sugestoes para trabalhos futuros, citamos o uso de outras tecnicas e algoritmos

de classificacao, como por exemplo, redes Bayesianas e redes Neurais. Alem disso, pode-

se realizar a Mineracao de Dados utilizando outras tecnicas como associacao a priori,

clusterizacao, e regressao. Atraves do uso de outras tecnicas e algoritmos sera possıvel,

alem de uma comparacao de desempenho computacional, uma comparacao de resultados

e conhecimentos extraıdos no que diz respeito a relacao entre atributos e regras extraıdas.

Apendice A

Questionario Socio-Economico

Pergunta : Qual seu estado civil?

Solteiro; Casado; Viuvo; Separado, desquitado ou divorciado; Unido consensualmente;

Pergunta : Onde voce reside atualmente?

Acre Alagoas Amapa Amazonas Bahia Ceara Distrito Federal Espırito Santo Fernando

de Noronha Goias Maranhao Mato Grosso Mato Grosso do Sul Minas Gerais Para Pa-

raıba Parana Pernambuco Piauı Rio Grande do Norte Rio Grande do Sul Rio de Janeiro

Rondonia Roraima Santa Catarina Sao Paulo Sergipe Tocantins Outros paıses

Pergunta : Que tipo de curso fundamental (1o. grau) voce concluiu?

Ensino fundamental regular; Antigo ginasio secundario; Antigo ginasio profissional;

Supletivo; Outro;

Pergunta : Em que tipo de estabelecimento de ensino voce cursou seus

estudos do ensino fundamental?

Todo em escola publica; Todo em escola particular; Maior parte em escola publica;

Maior parte em escola particular; Metade em escola publica e metade em escola particular;

Outro;

Pergunta : Que tipo de curso medio (2o. grau) voce concluiu ou concluira?

Ensino medio; Tecnico de nıvel medio; Normal ou Magisterio; Supletivo; Outro;

Pergunta : Em que tipo de estabelecimento de ensino voce cursou seus

estudos do ensino medio?

Todo em escola publica; Todo em escola particular; Maior parte em escola publica;

Maior parte em escola particular; Metade em escola publica e metade em escola particular;

57

APENDICE A. QUESTIONARIO SOCIO-ECONOMICO 58

Outro;

Pergunta : Em que turno voce cursou o ensino medio?

Diurno; Noturno; Parte diurno / parte noturno;

Pergunta : Em que ano voce concluiu ou concluira o ensino medio?

[2008,1900]

Pergunta : Em qual escola voce concluiu ou concluira seus estudos do

Ensino Medio?

Rio Grande - Col. Est. Getulio Vargas; Rio Grande - Col. Est. Lemos Junior; Rio

Grande - Col. Santa Joana D’Arc; Rio Grande - Col. Sao Francisco; Rio Grande - Col.

Tec. Ind. Prof. Mario Alquati; Rio Grande - Esc. Est. Lılia Neves; Rio Grande - Esc.

Est. Roberto Bastos Tellechea; Rio Grande - Esc. Est. Silva Gama; Rio Grande - Inst.

Educ. Juvenal Miller; Rio Grande - Liceu Salesiano Leao XIII; Rio Grande - Esc. Est.

Bıbiano de Almeida; Rio Grande - ASSPE; Rio Grande - Albert Einstein; Rio Grande

- E. E. E. M. Brigadeiro Jose da Silva Paes; Rio Grande - E. E. E. M. Alfredo Ferreira

Rodrigues; Rio Grande - E. E. E. M. Professor Carlos Lorea Pinto; Rio Grande - Colegio

Alternativo; Sao Jose do Norte - Instituto Sao Jose; Santa Vitoria do Palmar - Col. Est.

Santa Vitoria do Palmar; Santa Vitoria do Palmar - Esc. Normal Sao Carlos; Santa

Vitoria do Palmar - Esc. Est. Manuel Vicente do Amaral; Chuı - Esc. Est. Marechal

Soares de Andrea; Outra;

Pergunta : Qual o nıvel de instrucao de seu pai?

Nao frequentou escola; 1o. grau incompleto; 1o. grau completo; 2o. grau incompleto;

2o. grau completo; Curso superior incompleto; Curso superior completo; Pos-graduacao;

Nao sei informar;

Pergunta : Qual o nıvel de instrucao de sua mae?

Nao frequentou escola; 1o. grau incompleto; 1o. grau completo; 2o. grau incompleto;

2o. grau completo; Curso superior incompleto; Curso superior completo; Pos-graduacao;

Nao sei informar;

Pergunta : Voce frequentou/frequenta curso-pre vestibular?

Nao; Sim, por menos de um ano; Sim, por um ano; Sim, por mais de um ano;

Pergunta : Ha quantos anos voce esta tentando ingressar na sua opcao de

curso?


Este e o primeiro ano; Um ano; Dois anos; Tres anos; Quatro anos ou mais;

Pergunta : Voce ja iniciou algum curso superior?

Nao; Sim, mas abandonei; Sim, estou cursando; Sim, ja concluı; Sim, ja concluı um e

estou cursando outro; Sim, ja concluı um e abandonei outro;

Pergunta : Qual o motivo que fez/faria com que voce abandonasse um

curso superior?

Por nao ter sido classificado(a) no curso desejado; Por ter me decepcionado com o

curso; Por ter mudado a minha opcao profissional; Por motivo financeiros; Outros motivos;

Pergunta : Qual o principal motivo na escolha do curso para que voce esta

se inscrevendo?

Mercado de trabalho; Prestıgio social e economico da profissao; Conceito do curso; Re-

alizacao pessoal; Influencia da famılia e/ou amigos; Orientacao vocacional; Menor relacao

candidato/vaga; Compatibilidade entre o turno do curso e trabalho; Outro motivo;

Pergunta : Como voce se considera em relacao a sua opcao de curso?

Decidido; Indeciso;

Pergunta : Como tomou conhecimento do Processo Seletivo da FURG?

Jornal; Televisao; Radio; Escola e/ou cursinho; Internet; Revistas; Folhetos e/ou car-

tazes; Parentes ou amigos; Outro;

Pergunta : Qual o principal motivo pelo qual voce escolheu a FURG para

prestar o seu Processo Seletivo?

Oferece o curso pretendido; Pelo conceito dos seus cursos; Oferece horario adequado;

Prestıgio conferido a Instituicao; E publica e gratuita; Por tradicao familiar; Por residir

em Rio Grande; Outro;

Pergunta : Qual a sua ocupacao?

Profissional liberal; Professor do ensino superior; Professor do ensino medio e funda-

mental; Tecnico de nıvel superior; Tecnico de nıvel medio; Trabalhador ligado a ativi-

dades artısticas e a pratica desportiva; Trabalhador ligado as atividades de navegacao

aerea, marıtima e interior; Membro do poder legislativo, do executivo ou do judiciario;

Servidor publico civil de nıvel superior; Servidor publico civil de nıvel intermediario ou de

apoio; Oficial das forcas armadas ou das forcas auxiliares; Militar (nao oficial) das forcas

armadas ou das forcas auxiliares; Diretor ou gerente de empresa publica ou privada; Tra-


balhador administrativo de empresa publica ou privada; Trabalhador do comercio ou as-

semelhado; Trabalhador do setor de prestacao de servicos; Trabalhador do setor primario;

Trabalhador da producao industrial; Proprietario de estabelecimento agrıcola; Proprieta-

rio de estabelecimento comercial; Proprietario de estabelecimento industrial; Proprietario

de estabelecimento de prestacao de servicos; Do lar; Trabalhador em situacao informal;

Estudante; Aposentado; Desempregado; Nao sei informar;

Pergunta : Qual a ocupacao de seu pai?













Estudante; Aposentado; Desempregado; Falecido; Nao sei informar;

Pergunta : Qual a ocupacao de sua mae?














Estudante; Aposentada; Desempregada; Falecida; Nao sei informar;

Pergunta : Qual o numero de pessoas que moram na sua residencia?

Uma; Duas; Tres; Quatro; Cinco ou mais;

Pergunta : Qual o numero de pessoas com atividade remunerada em sua

residencia?

Nenhuma; Uma; Duas; Tres; Quatro; Cinco ou mais;

Pergunta : Quem e a principal pessoa responsavel pelo seu sustento?

Pai; Mae; Pai e Mae; Conjuge; Avos; Eu mesmo(a); Outra pessoa;

Pergunta : Qual a renda que compoe o orcamento de sua residencia? (Soma

dos salarios brutos de todos os residentes).

Ate 1 (inclusive) salario mınimo; De 1 a 5 (inclusive) salarios mınimos; De 5 a 10

(inclusive) salarios mınimos; De 10 a 20 (inclusive) salarios mınimos; Acima de 20 salarios

mınimos;

Pergunta : Qual o seu principal meio de informacao?

Jornal; Televisao; Radio; Revista; Internet; Nao tenho me mantido informado;

Pergunta : Voce tem computador em sua residencia?

Sim, com acesso a internet; Sim, sem acesso a internet; Nao;

Apendice B

Consulta SQL

Codigo B.1: Codigo que representa a query utilizada para formar a tabela unica

1 insert into t c c v e s t i b u l a r (

2

3 select

4

5 f . n r i n s c r i c a o ,

6

7 −−− separa as c idades em RIO GRANDE E OUTRAS

8 CASE WHEN trim ( t o a s c i i (upper ( nm cidade ) ) ) in

9 ( select

10

11 trim ( t o a s c i i (upper ( nm cidade ) ) )

12

13 FROM f i c h a s where c d v e s t i b u l a r = ’2007VN’ or c d v e s t i b u l a r

= ’2008VN’ or c d v e s t i b u l a r = ’2009VN’

14

15 AND trim ( t o a s c i i (upper ( nm cidade ) ) ) i l i k e ’R%DE%’

16 AND nm cidade != ’RIO DE JANEIRO’

17

18 order by trim ( t o a s c i i (upper ( nm cidade ) ) ) desc

19 ) THEN ’RIO_GRANDE’

20 ELSE ’OUTRAS’

21 END as cidade ,

22

23 −−− separa as idades em <20 20<>25 >26

62

APENDICE B. CONSULTA SQL 63

24 CASE

25 WHEN to number ( to char ( dt nasc , ’YYYY’ ) , ’9999’ ) >= ’1990’ THEN ’

menor20’

26 WHEN to number ( to char ( dt nasc , ’YYYY’ ) , ’9999’ ) < ’1990’ AND

to number ( to char ( dt nasc , ’YYYY’ ) , ’9999’ ) >= ’1984’ THEN ’20_25’

27 ELSE ’maior26’

28 END as idade ,

29

30 f . cd sexo as sexo ,

31

32 f . cd curso ,

33

34 cur so s . nm curso ,

35

36 cur so s . nr vaga ,

37

38 f . n r ace r to s ,

39

40 f . n r c l a s s i f i c a c a o ,

41

42 f . vl media harmonica ,

43

44 case when f . n r c l a s s i f i c a c a o <= curso s . nr vaga then ’A’ else ’R’ END as

s i tuacao ,

45

46 array (

47

48 SELECT

49

50 CASE

51 −− t i p o es tado c i v i l

52 WHEN q u e s t i o n a r i o a l t e r n a t i v a s . id = 2127 THEN ’

Solteiro’


Casado’

54 WHEN q u e s t i o n a r i o a l t e r n a t i v a s . id between 2129 and

2131 THEN ’Outros’


55

56 −− t i p o de e s co l a ensino fundamental


Fund_Publica’


Fund_Particular’


2171 THEN ’Fund_Misto’

60

61 −− t i p o de e s co l a ensino medio


Med_Publica’


Med_Particular’


2182 THEN ’Med_Misto’

65

66 −− formacao pai


2318 THEN ’Pai_Min’


2320 THEN ’Pai_Fund’


2322 THEN ’Pai_Medio’


Pai_Sup’


Pai_Pos’


Pai_NSI’

73

74 −− formacao mae


2327 THEN ’Mae_Min’


2329 THEN ’Mae_Fund’



2331 THEN ’Mae_Medio’


Mae_Sup’


Mae_Pos’


Mae_NSI’

81

82 −− anos tentando in g r e s s a r no curso


Primeiro_Ano’


2343 THEN ’Mais_Anos’

85

86 −− j a i n i c i o u curso super i o r

87 WHEN q u e s t i o n a r i o a l t e r n a t i v a s . id = 2344 THEN ’Nao’


2349 THEN ’Sim’

89

90 −− t i p o de ensino medio


Turno_Misto’

92

93 −− curso pre−v e s t i b u l a r

94 WHEN q u e s t i o n a r i o a l t e r n a t i v a s . id = 2335 THEN ’Nao’


Sim_Menos_1ano’


Sim_1ano’


Sim_Mais_1ano’

98

99 −− motivo abandonar curso


2351 THEN ’Motivo_Curso’



Motivo_Outros’


Motivo_Outros’


Motivo_Finan’

104

105 −− motivo e s c o l h e r curso


2356 THEN ’Motivo_Econ’


Motivo_Curso’


2362 THEN ’Motivo_Curso’


2360 THEN ’Motivo_Pessoal’


Motivo_Outro’

111

112 −− tomou conhecimento do Vest . da FURG


Impresso’


2372 THEN ’Impresso’


2368 THEN ’Radio_TV’


Escola_Cursinho’


Outro_Meio’


Parente_Amigo’

119

120 −− motivo e s c o l h e r a FURG


2378 THEN ’Motivo_Outro’



Motivo_Outro’


Motivo_Outro’


Oferece_Curso’


Conceito_Curso’


Publica_Gratuita’


Residir_RG’

128

129 −− ocupacao v e s t i b u l ando


2406 THEN ’Outra’



132

133 −− numero de pessoas que moram


Cinco_mais’

135

136 −− numero de pessoas com remuneracao


2479 THEN ’Tres_mais’

138

139 −− pessoa re sponsave l pe l o su s t en t o

140 WHEN q u e s t i o n a r i o a l t e r n a t i v a s . id = 2480 THEN ’Pai’

141 WHEN q u e s t i o n a r i o a l t e r n a t i v a s . id = 2481 THEN ’Mae’


Pai_Mae’



144

145 −− orcamento f am i l i a r



Ate_1’


Entre_1_5’


Entre_5_10’


2491 THEN ’Acima_10’

150

151 −− t e r i n t e r n e t


2500 THEN ’Nao’

153 WHEN q u e s t i o n a r i o a l t e r n a t i v a s . id = 2498 THEN ’Sim’

154

155 −− meios de informacao


Outro_Meio’


2495 THEN ’Outro_Meio’


Outro_Meio’


Televisao’


Internet’

161 ELSE r e p l a c e ( q u e s t i o n a r i o a l t e r n a t i v a s . a l t e r n a t i v a

, ’ú’ , ’u’ )

162

163 END as r e spo s ta

164

165 FROM q u e s t i o n a r i o a l t e r n a t i v a s

166

167 JOIN q u e s t i o n a r i o r e s p o s t a s ON( q u e s t i o n a r i o r e s p o s t a s .

i d a l t e r n a t i v a = q u e s t i o n a r i o a l t e r n a t i v a s . id )

168

169 JOIN q u e s t i o n a r i o p e r g u n ta s ON ( q u e s t i o n a r i o a l t e r n a t i v a s .

i d q u e s t i o n a r i o p e r g u n t a = q u e s t i o n a r i o p e r g u n ta s . id )


170

171 JOIN f i c h a s ON ( f i c h a s . n r f i c h a = q u e s t i o n a r i o r e s p o s t a s .

n r f i c h a AND f i c h a s . c d v e s t i b u l a r =

q u e s t i o n a r i o p e r g u n ta s . c d v e s t i b u l a r )

172

173 WHERE f i c h a s . c d v e s t i b u l a r = ’2007VN’ or f i c h a s .

c d v e s t i b u l a r = ’2008VN’ or f i c h a s . c d v e s t i b u l a r = ’2009

VN’ and f i c h a s . n r i n s c r i c a o = f . n r i n s c r i c a o

174

175 AND q u e s t i o n a r i o p e r g u n ta s . id != 88







182

183

184 ) as r e spo s ta

185

186

187 FROM f i c h a s f

188

189 JOIN cur so s ON ( cur so s . cd curso = f . cd curso AND cur so s . c d v e s t i b u l a r = f .

c d v e s t i b u l a r )

190

191 WHERE f . c d v e s t i b u l a r = ’2007VN’ or f . c d v e s t i b u l a r = ’2008VN’ or f .


192

193 ORDER BY n r i n s c r i c a o

194

195 )

Referencias Bibliograficas

Batista, G. E. A. P. A. (2003). Pre-processamento de Dados em Aprendizado de Maquina

Supervisionado. PhD thesis, Universidade de Sao Paulo.

Dias, M. M. (2001). Um modelo de formalizacao do processo de desenvolvimento de siste-

mas de descoberta de conhecimento em banco de dados. Master’s thesis, Universidade

Federal de Santa Catarina.

Elmasri, R. E. and Navathe, S. B. (2003). Fundamentals of Database Systems. Addison

Wesley, 4 edition.

Fawcett, T. and Provost, F. (1997). Adaptive fraud detection. Data Mining and Knowledge

Discovery, 1(3):291–316.

Fayyad, U. M., Piatetsky-Shapiro, G., and Smyth, P. (1996). From data mining to kno-

wledge discovery in databases. AI Magazine, 17(3):37–54.

Freitas, A. A. (2002). Data Mining and Knowledge Discovery with Evolutionary Algo-

rithms. Natural Computing Series. Springer-Verlag Berlin Heidelberg.

Goldschmidt, R. and Passos, E. (2005). Data Mining: um Guia Pratico. Campus.

Han, H., Wang, W.-Y., and Mao, B.-H. (2005). Borderline-smote: A new over-sampling

method in imbalanced data sets learning. pages 878–887.

Han, J. and Kamber, M. (2001). Data Mining: Concepts and Techniques. Morgan Kauf-

mann, 1 edition.

Han, J. and Kamber, M. (2006). Data Mining: Concepts and Techniques. Morgan Kauf-

mann, 2 edition.

70

REFERENCIAS BIBLIOGRAFICAS 71

Jubran, A. J., Jubran, L. M. P., de Magalhaes Cipparrone, F. A., and de Almeida Ju-

nior, J. R. (2004). Data mining na web. In Anais do I Workcomp-Sul, Palhoca, SC.

Universidade do Sul de Santa Catarina.

Kubat, M., Holte, R. C., and Matwin, S. (1998). Machine learning for the detection of oil

spills in satellite radar images. Machine Learning, 30(2-3):195–215.

Merschmann, L. H. C. (2007). Classificacao probabilıstica baseasa em analise de padroes.

PhD thesis, Universidade Federal Fluminense.

Prati, R. C. (2006). Novas abordagens em aprendizado de maquina para a geracao de

regras, classes desbalanceadas e ordenacao de casos. Master’s thesis, Universidade de

Sao Paulo.

Russell, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Prentice

Hall, 2 edition.

Russell, S. and Norvig, P. (2004). Inteligencia Artificial. Campus, 1 edition.

Soares, J. A. (2007). Pre-processamento em mineracao de dados: Um estudo comparativo

em complementacao. PhD thesis, Universidade Federal do Rio de Janeiro,COPPE.

Tang, L. and Liu, H. (2005). Bias analysis in text classification for highly skewed data.

Data Mining, IEEE International Conference on, 0:781–784.

Waikato, U. (2008). WEKA 3: Data Mining Software in Java. Nova Zelandia.

Weiss, G. M. and Provost, F. (2003). Learning when training data are costly: the ef-

fect of class distribution on tree induction. Journal of Artificial Intelligence Research,

19(1):315–354.

Witten, I. H. and Frank, E. (2005). Data Mining - Practical Machine Learning Tools and

Techniques. Morgan Kaufmann Series. Elsevier, 2 edition.

Wolpert, D. H. (1996). The lack of a priori distinctions between learning algorithms.

Neural Computation, 8:1341–1390.

REFERENCIAS BIBLIOGRAFICAS 72

Zhang, S., Zhang, C., and Yang, Q. (2003). Data preparation for data mining. Applied

Artificial Intelligence, 17:375–381.

Documents

Uma abordagem baseada em minerac~ao de dados para aquisic~ao autom atica de ... · 2013. 6. 27. · minerac~ao de dados para aquisic~ao autom atica de conhecimento sobre o processo