Pré-processamento de dados em aprendizado de máquina supervisionado por Gustavo Enrique de Almeida Prado Alves Batista - Versão HTML

ATENÇÃO: Esta é apenas uma visualização em HTML e alguns elementos como links e números de página podem estar incorretos.
Faça o download do livro em PDF, ePub, Kindle para obter uma versão completa.

Pré-processamento de Dados em Aprendizado de

Máquina Supervisionado

Gustavo Enrique de Almeida Prado Alves Batista

SERVI ÇO DE P ÓS-GRADUA Ç ˜

AO DO ICMC-USP

Data de Depósito: 11/03/2003

Assinatura:

Pré-processamento de Dados em Aprendizado

de Máquina Supervisionado

Gustavo Enrique de Almeida Prado Alves Batista

Orientadora: Profa. Dra. Maria Carolina Monard

Tese apresentada ao Instituto de Ciências Matemáticas e de

Computaç˜

ao — ICMC-USP, como parte dos requisitos para ob-

tenç˜

ao do t´ıtulo de Doutor em Ciências — Ciências de Compu-

taç˜

ao e Matemática Computacional.

USP - S˜

ao Carlos

Março/2003

Resumo

A qualidade de dados é uma das principais preocupaç˜

oes em Aprendizado de Máquina — AM — cujos

algoritmos s˜

ao freqüentemente utilizados para extrair conhecimento durante a fase de Mineraç˜

ao de Dados

— MD — da nova área de pesquisa chamada Descoberta de Conhecimento de Bancos de Dados. Uma

vez que a maioria dos algoritmos de aprendizado induz conhecimento estritamente a partir de dados, a

qualidade do conhecimento extra´ıdo é amplamente determinada pela qualidade dos dados de entrada.

Diversos aspectos podem influenciar no desempenho de um sistema de aprendizado devido à qua-

lidade dos dados. Em bases de dados reais, dois desses aspectos est˜

ao relacionados com (i) a presença de

valores desconhecidos, os quais s˜

ao tratados de uma forma bastante simplista por diversos algoritmos de

AM, e; (ii) a diferença entre o número de exemplos, ou registros de um banco de dados, que pertencem

a diferentes classes, uma vez que quando essa diferença é expressiva, sistemas de aprendizado podem ter

dificuldades em aprender o conceito relacionado com a classe minoritária.

O problema de tratamento de valores desconhecidos é de grande interesse prático e teórico. Em

diversas aplicaç˜

oes é importante saber como proceder quando as informaç˜

oes dispon´ıveis est˜

ao incompletas

ou quando as fontes de informaç˜

oes se tornam indispon´ıveis. O tratamento de valores desconhecidos

deve ser cuidadosamente planejado, caso contrário, distorç˜

oes podem ser introduzidas no conhecimento

induzido. Neste trabalho é proposta a utilizaç˜

ao do algoritmo k-vizinhos mais próximos como método

de imputaç˜

ao. Imputaç˜

ao é um termo que denota um procedimento que substitui os valores desconhecidos

de um conjunto de dados por valores plaus´ıveis. As análises conduzidas neste trabalho indicam que a

imputaç˜

ao de valores desconhecidos com base no algoritmo k-vizinhos mais próximos pode superar o

desempenho das estratégias internas utilizadas para tratar valores desconhecidos pelos sistemas C4.5 e

CN2, bem como a imputaç˜

ao pela média ou moda, um método amplamente utilizado para tratar

valores desconhecidos.

O problema de aprender a partir de conjuntos de dados com classes desbalanceadas é de crucial

importância, um vez que esses conjuntos de dados podem ser encontrados em diversos dom´ınios. Classes

com distribuiç˜

oes desbalanceadas podem se constituir em um gargalo significante no desempenho obtido

por sistemas de aprendizado que assumem uma distribuiç˜

ao balanceada das classes. Uma soluç˜

ao para

o problema de aprendizado com distribuiç˜

oes desbalanceadas de classes é balancear artificialmente o

conjunto de dados. Neste trabalho é avaliado o uso do método de seleç˜

ao unilateral, o qual realiza uma

remoç˜

ao cuidadosa dos casos que pertencem à classe majoritária, mantendo os casos da classe minoritária.

Essa remoç˜

ao cuidadosa consiste em detectar e remover casos considerados menos confiáveis, por meio

do uso de algumas heur´ısticas.

Uma vez que n˜

ao existe uma análise matemática capaz de predizer se o desempenho de um método

é superior aos demais, análises experimentais possuem um papel importante na avaliaç˜

ao de sistema de

aprendizado. Neste trabalho é proposto e implementado o ambiente computacional Discover Learning

Environmnet — DLE — o qual é um framework para desenvolver e avaliar novos métodos de pré-

processamento de dados. O ambiente DLE é integrado ao projeto Discover, um projeto de pesquisa em

desenvolvimento em nosso laboratório para planejamento e execuç˜

ao de experimentos relacionados com

o uso de sistemas de aprendizado durante a fase de Mineraç˜

ao de dados do processo de KDD.

iii

Abstract

Data quality is a major concern in Machine Learning, which is frequently used to extract knowledge during

the Data Mining phase of the relatively new research area called Knowledge Discovery from Databases —

KDD. As most Machine Learning algorithms induce knowledge strictly from data, the quality of the

knowledge extracted is largely determined by the quality of the underlying data.

Several aspects may influence the performance of a learning system due to data quality. In real

world databases, two of these aspects are related to (i) the presence of missing data, which is handled

in a rather naive way by many Machine Learning algorithms; (ii) the difference between the number of

examples, or database records, that belong to different classes since, when this difference is large, learning

systems may have difficulties to learn the concept related to the minority class.

The problem of missing data is of great practical and theoretical interest. In many applications

it is important to know how to react if the available information is incomplete or if sources of informa-

tion become unavailable. Missing data treatment should be carefully thought, otherwise bias might be

introduced into the knowledge induced. In this work, we propose the use of the k-nearest neighbour

algorithm as an imputation method. Imputation is a term that denotes a procedure that replaces the

missing values in a data set by some plausible values. Our analysis indicates that missing data imputation

based on the k-nearest neighbour algorithm can outperform the internal missing data treatment stra-

tegies used by C4.5 and CN2, and the mean or mode imputation, a widely used method for treating

missing values.

The problem of learning from imbalanced data sets is of crucial importance since it is encountered

in a large number of domains. Imbalanced class distributions might cause a significant bottleneck in the

performance obtained by standard learning methods, which assume a balanced distribution of the classes.

One solution to the problem of learning with skewed class distributions is to artificially balance the data

set. In this work we propose the use of the one-sided selection method, which performs a careful removal

of cases belonging to the majority class while leaving untouched all cases from the minority class. Such

careful removal consists of detecting and removing cases considered less reliable, using some heuristics.

An experimental application confirmed the efficiency of the proposed method.

As there is not a mathematical analysis able to predict whether the performance of a learning

system is better than others, experimentation plays an important role for evaluating learning systems.

In this work we propose and implement a computational environment, the Discover Learning Envi-

ronment — DLE — which is a framework to develop and evaluate new data pre-processing methods.

The DLE is integrated into the Discover project, a major research project under development in our

laboratory for planning and execution of experiments related to the use of learning systems during the

Data Mining phase of the KDD process.

v

Aos meus pais,

Joselito e Margarida,

Às minhas irm˜

as,

Anapaula e Analúcia,

À Maria Carolina Monard.

Agradecimentos

Ainda me lembro do dia que conheci a professora Carolina. Parece até mesmo que n˜

ao

faz muito tempo. Eu ainda estava cursando o segundo grau e estava passeando de férias

pela USP. Um dos meus primos, José Pacheco, que sempre me incentivou a ingressar

na carreira acadêmica e que na época era aluno de mestrado da profa. Carolina, disse-

me que iria me apresentar à sua orientadora. Chegando à sala da profa. Carolina, ele

me apresentou. Ela me cumprimentou, foi extremamente gentil, como sempre, e os dois

começaram a tratar dos assuntos da dissertaç˜

ao de mestrado dele.

Naquela época, eu jamais poderia imaginar o quanto aquela senhora, de sotaque

espanhol carregado, poderia representar na minha vida. Nos últimos oito anos ela n˜

ao foi

somente a minha orientadora de mestrado e doutorado, mas também a minha orientadora

na vida. Ela me ensinou grande parte do que eu sei sobre Aprendizado de Máquina.

Inúmeras foram as nossas discuss˜

oes sobre o tema, e inúmeras vezes eu ouvi um doce

“n˜

ao é bem assim, filhinho” quando eu estava errado. Mas a profa. Carolina também

me ensinou outras coisas t˜

ao valiosas quanto o conhecimento acadêmico. Uma delas, eu

pretendo carregar comigo para sempre: a postura ética no trabalho e na vida.

Carolina esteve comigo nos bons momentos, como nas festas de aniversário do Labic.

Nos momentos chatos do trabalho quando nos reun´ıamos à noite e aos finais de semana

para escrever artigos, e nos momentos dif´ıceis, como no falecimento de minha avó.

Minha avó, Margarida, da qual nunca posso esquecer, sempre acolhedora, ensinou-

me muito nos anos em que morei com ela na graduaç˜

ao.

Importante, também, foi o apoio que sempre recebi da minha fam´ılia. Agradeço aos

meus pais por sempre terem me apoiado a estudar. À minha m˜

ae por sempre me apoiar

nas decis˜

oes que tomei em minha carreira. E, em especial, ao meu pai por freqüentemente

me dizer que fazer uma pós-graduaç˜

ao era o caminho certo.

Agradeço, também, à Claudia, minha namorada e ao mesmo tempo minha colega de

doutorado. Esses anos de doutorado teriam sido muito mais dif´ıceis se você n˜

ao estivesse

comigo todos os dias. Obrigado por me apoiar sempre, seja qual for a coisa que eu resolva

fazer.

Durante esses anos, dois amigos me ajudaram muito com o meu trabalho. Primeiro,

José Augusto pelas diversas conversas sobre Mineraç˜

ao de Dados, KDD e a criaç˜

ao do

ix

projeto Discover. Eu tenho utilizado como referência de qualidade muitos trabalhos

desenvolvidos por você. E o Ronaldo, um pesquisador com uma capacidade incr´ıvel, com

quem tenho desenvolvido muitas das idéias que têm dado vida ao Discover.

Agradeço, também aos amigos Daniel, Kaminski, Valmir e Rodrigo pelos momentos

de bagunça nas viagens e nas reuni˜

oes de confraternizaç˜

ao. Um obrigado especial ao

Valmir por suportar as nossas brincadeiras. E aos amigos Huei e Wu pelas viagens que

fizemos juntos.

Aos amigos do Labic: Jaque, Claudinha, Patr´ıcia, Gedson, José Flávio, Cris, Walter,

Adriano, Marcos Geromini e Marcos Paula. Obrigado também à Talita por nos ajudar

na parte de Engenharia de Software do projeto Discover.

Agradeço ao pessoal da pós-graduaç˜

ao do ICMC, e em especial à Beth, à Laura,

à Mar´ılia e à Ana Paula, por terem respondido às minhas inúmeras perguntas sobre o

funcionamento da pós. Ao pessoal da biblioteca por serem todos sempre prestativos.

Gostaria de lembrar também da Alice e da Sofia por estarem comigo nas madrugadas

que estive redigindo esta tese.

Um agradecimento especial a dois professores do ICMC que me ajudaram muito

durante esses anos. Ao André que sempre me impressionou com o seu dinamismo, capa-

cidade, bom humor e cordialidade. À Solange, por ter me ajudado diversas vezes com os

meus problemas na pós, e por ter me ajudado em várias oportunidades. Muito do que eu

aprendi em contato com outros pesquisadores externos ao ICMC eu devo à você, Solange.

Sumário

Resumo

iii

Abstract

v

Dedicat´

oria

vii

Agradecimentos

ix

Sum´

ario

xi

Lista de Figuras

xvii

Lista de Tabelas

xxi

Lista de Algoritmos

xxiii

Lista de Abreviaturas

xxv

1

Introdu¸

ao

1

1.1

Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Qualidade de Dados

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3

Pr´

e-processamento de Dados . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Objetivos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.5

Principais Contribuiç˜

oes desta Tese . . . . . . . . . . . . . . . . . . . . . .

6

1.6

Organizaç˜

ao deste Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . .

9

xi

xii

SUMÁRIO

2

Aprendizado de M´

aquina

11

2.1

Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2

O Aprendizado em Inteligˆ

encia Artificial . . . . . . . . . . . . . . . . . . .

11

2.3

Aprendizado Indutivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.4

Aprendizado Indutivo por Exemplos . . . . . . . . . . . . . . . . . . . . . .

14

2.5

Aprendizado de M´

aquina Indutivo por Exemplos . . . . . . . . . . . . . . .

18

2.5.1

Os Paradigmas de Aprendizado de M´

aquina Supervisionado . . . .

21

2.5.1.1

Paradigma Simb´

olico . . . . . . . . . . . . . . . . . . . . .

21

2.5.1.2

Paradigma Estat´ıstico . . . . . . . . . . . . . . . . . . . .

22

2.5.1.3

Paradigma Instance-based . . . . . . . . . . . . . . . . . .

22

2.5.1.4

Paradigma Conexionista . . . . . . . . . . . . . . . . . . .

23

2.6

Descoberta de Conhecimento em Bancos de Dados . . . . . . . . . . . . . .

24

2.7

O Projeto Discover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.7.1

O Ambiente Discover . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.7.2

Outros Trabalhos Realizados e em Desenvolvimento . . . . . . . . .

29

2.8

Consideraç˜

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

3

Pr´

e-processamento de Dados

31

3.1

Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2

O Processo de Descoberta de Conhecimento em Bancos de Dados . . . . .

31

3.3

Coleta de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.4

Pr´

e-processamento de Dados . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.5

Transformaç˜

ao de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.6

Consideraç˜

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4

O Ambiente Discover Learning Environment — DLE

49

4.1

Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4.2

Os M´

odulos do Ambiente DLE . . . . . . . . . . . . . . . . . . . . . . . . 49

4.3

A Biblioteca de Classes Discover Object Library — DOL . . . . . . 51

SUMÁRIO

xiii

4.3.1

O Desenvolvimento da Biblioteca de Classes DOL . . . . . . . . . . 55

4.3.2

A Arquitetura da Biblioteca DOL . . . . . . . . . . . . . . . . . . 56

4.3.3

O Projeto da Biblioteca DOL . . . . . . . . . . . . . . . . . . . . . 61

4.3.3.1

O M´

odulo Core . . . . . . . . . . . . . . . . . . . . . . . .

62

4.3.3.2

Os M´

odulos ResaplingkFoldCV e ResamplingStratKFoldCV .

66

4.3.3.3

Os M´

odulos DistanceHEOM e DistanceHVDM

. . . . . . .

68

4.3.3.4

Os M´

odulos NormalizeLinear, NormalizeSimpleSD e Norma-

lizeScalledSD

. . . . . . . . . . . . . . . . . . . . . . . . .

69

4.3.3.5

Os M´

odulos kNNMTree, kNNLinear, MTreeRandom e MTre-

eMST . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

4.3.4

Outras Soluç˜

oes para a Implementaç˜

ao da Biblioteca DOL . . . . . 72

4.4

O Ambiente Computacional Sniffer . . . . . . . . . . . . . . . . . . . . . 75

4.4.1

O Funcionamento do Ambiente Computacional Sniffer . . . . . . 77

4.4.2

A Arquitetura do Ambiente Computacional Sniffer . . . . . . . . 82

4.4.3

O Projeto do Ambiente Computacional Sniffer . . . . . . . . . . 84

4.5

Consideraç˜

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

5

Tratamento de Valores Desconhecidos

89

5.1

Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89

5.2

A Aleatoriedade dos Valores Desconhecidos . . . . . . . . . . . . . . . . . .

90

5.3

etodos para Tratamento de Valores Desconhecidos . . . . . . . . . . . . .

93

5.4

etodos de Imputaç˜

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

5.5

Imputaç˜

ao com o Algoritmo k-Vizinhos mais Pr´

oximos . . . . . . . . .

96

5.5.1

O Algoritmo k-Vizinhos mais Pr´

oximos . . . . . . . . . . . . . .

97

5.5.1.1

O Algoritmo k-Vizinhos mais Pr´

oximos B´

asico . . . .

98

5.5.1.2

O Algoritmo k-Vizinhos mais Pr´

oximos com Pesos . . 100

5.5.1.3

As Funç˜

oes de Distˆ

ancia VDM, HEOM e HVDM . . . . . . 101

5.5.1.4

Acelerando as Consultas com M-trees . . . . . . . . . . . . 105

xiv

SUMÁRIO

5.6

Como os Sistemas de Aprendizado C4.5 e CN2 Tratam Valores Desconhe-

cidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.7

An´

alise Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.7.1

Identificaç˜

ao de Atributos Relevantes . . . . . . . . . . . . . . . . . 115

5.7.2

Estimando um Bom Valor para o Parˆ

ametro k . . . . . . . . . . . . 117

5.7.3

Resultados Experimentais . . . . . . . . . . . . . . . . . . . . . . . 119

5.7.3.1

O Conjunto de Dados Bupa . . . . . . . . . . . . . . . . . 121

5.7.3.2

Conjunto de Dados CMC . . . . . . . . . . . . . . . . . . 122

5.7.3.3

Conjunto de Dados Pima . . . . . . . . . . . . . . . . . . 122

5.7.3.4

Conjunto de Dados CRX . . . . . . . . . . . . . . . . . . 129

5.7.3.5

Conjunto de Dados Breast . . . . . . . . . . . . . . . . . 129

5.7.3.6

Conjunto de Dados Sonar . . . . . . . . . . . . . . . . . . 135

5.8

Consideraç˜

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

6

Aprendizado com Classes Desbalanceadas

141

6.1

Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

6.2

etodos para Solucionar o Problema de Classes Desbalanceadas . . . . . . 143

6.3

Precis˜

ao, Taxa de Erro e Classes Desbalanceadas

. . . . . . . . . . . . . . 144

6.4

Conjuntos Desbalanceados e Aprendizado Sens´ıvel ao Custo

. . . . . . . . 148

6.5

Qual Proporç˜

ao de Classes ´

e Melhor para Aprender?

. . . . . . . . . . . . 149

6.6

Como Descartar ou Duplicar Exemplos?

. . . . . . . . . . . . . . . . . . . 150

6.7

Under-sampling, Over-sampling e os Atuais Sistemas de Aprendizado . . . 154

6.8

An´

alise Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

6.9

Consideraç˜

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

7

Conclus˜

ao

159

7.1

Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

7.2

Principais Contribuiç˜

oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

7.2.1

Tratamento de Valores Desconhecidos . . . . . . . . . . . . . . . . . 162

SUMÁRIO

xv

7.2.2

Tratamento de Conjuntos com Classes Desbalanceadas . . . . . . . 163

7.3

Limitaç˜

oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

7.3.1

Tratamento de Valores Desconhecidos . . . . . . . . . . . . . . . . . 164

7.3.2

Tratamento de Conjuntos com Classes Desbalanceadas . . . . . . . 165

7.4

Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

A A Sintaxe Discover Dataset Sintax — DSX

169

A.1 Consideraç˜

oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

A.2 Uma Vis˜

ao Geral da Sintaxe DSX . . . . . . . . . . . . . . . . . . . . . . 171

A.3 Os Tipos de Dado da Sintaxe DSX . . . . . . . . . . . . . . . . . . . . . . 173

A.3.1 O Tipo de Dado Nominal

. . . . . . . . . . . . . . . . . . . . . . . 173

A.3.2 O Tipo de Dado Enumerated

. . . . . . . . . . . . . . . . . . . . . 174

A.3.3 O Tipo de Dado Integer

. . . . . . . . . . . . . . . . . . . . . . . 174

A.3.4 O Tipo de Dado Real

. . . . . . . . . . . . . . . . . . . . . . . . . 175

A.3.5 O Tipo de Dado String . . . . . . . . . . . . . . . . . . . . . . . . 175

A.3.6 O Tipo de Dado Date

. . . . . . . . . . . . . . . . . . . . . . . . . 175

A.3.7 O Tipo de Dado Time

. . . . . . . . . . . . . . . . . . . . . . . . . 176

A.4 Atributos Virtuais

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

A.5 Declaraç˜

oes Estendidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

A.6 Gram´

atica da Sintaxe DSX . . . . . . . . . . . . . . . . . . . . . . . . . . 178

B Relat´

orios do Ambiente Sniffer

181

B.1 Exemplo de Relat´

orio Resumido . . . . . . . . . . . . . . . . . . . . . . . . 181

B.2 Exemplo de Relat´

orio Detalhado . . . . . . . . . . . . . . . . . . . . . . . . 184

B.3 Exemplo de Relat´

orio com Testes Hip´

otese . . . . . . . . . . . . . . . . . . 188

Referˆ

encias

191

xvi

SUMÁRIO

Lista de Figuras

2.1

Representaç˜

ao gr´

afica de um conjunto de exemplos (a) e uma poss´ıvel hi-

otese para o conceito representado por esses exemplos (b). . . . . . . . . .

15

2.2

Atualizaç˜

ao de uma hip´

otese. Hip´

otese consistente (a). Falso negativo (b).

Hip´

otese generalizada (c). Falso positivo (d). Hip´

otese especializada (e). .

16

2.3

A hierarquia do aprendizado.

. . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1

Principais fases do processo de KDD. . . . . . . . . . . . . . . . . . . . . .

34

4.1

Exemplo de interaç˜

ao entre m´

odulos da biblioteca DOL. . . . . . . . . . . 60

4.2

Arquitetura do mecanismo de envio de mensagens da biblioteca DOL. . . . 61

4.3

Diagrama de classes em UML do projeto do m´

odulo Core. . . . . . . . . . .

65

4.4

Diagrama de classes em UML do projeto dos m´

odulos ResaplingkFoldCV e

ResamplingStratKFoldCV. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

4.5

Diagrama de classes em UML do projeto dos m´

odulos DistanceHEOM e

DistanceHVDM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.6

Diagrama de classes em UML do projeto dos m´

odulos NormalizeLinear, Nor-

malizeSimpleSD e NormalizeScalledSD. . . . . . . . . . . . . . . . . . . . . .

71

4.7

Diagrama de classes em UML do projeto dos m´

odulos kNNMTree, kNNLi-

near, MTreeRandom e MTreeMST. . . . . . . . . . . . . . . . . . . . . . . .

72

4.8

Exemplo de experimento organizado em diret´

orios para o ambiente Sniffer. 78

4.9

Arquitetura do ambiente computacional Sniffer. . . . . . . . . . . . . . . 83

4.10 Projeto do m´

odulo SearchandRun do ambiente computacional Sniffer. . . 85

xvii

xviii

LISTA DE FIGURAS

4.11 Projeto dos m´

odulos Report e HypothesisTest do ambiente computacional

Sniffer.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.1

Exemplo de valores desconhecidos n˜

ao aleatoriamente distribu´ıdos. . . . . .

92

5.2

Exemplo de uma estrutura M-tree.

. . . . . . . . . . . . . . . . . . . . . . 107

5.3

Representaç˜

ao gr´

afica da M-tree apresentada na Figura 5.2. . . . . . . . . . 108

5.4

Representaç˜

ao gr´

afica da metodologia utilizada nos experimentos. . . . . . 114

5.5

Conjunto de dados Bupa. Erro mse medido sobre o atributo 4 para diver-

sos valores do parˆ

ametro k do m´

etodo de imputaç˜

ao baseado no algoritmo

k-vizinhos mais pr´

oximos. Valores desconhecidos inseridos no atributo

4. Imputa¸

ao pela m´

edia ou moda obteve erros mse no intervalo

[1616.44 ± 56.69, 1704.55 ± 118.03]. . . . . . . . . . . . . . . . . . . . . . . 119

5.6

Conjunto de dados Pima. Erro mse medido sobre o atributo 1 para diver-

sos valores do parˆ

ametro k do m´

etodo de imputaç˜

ao baseado no algoritmo

k-vizinhos mais pr´

oximos. Valores desconhecidos inseridos no atributo

1. Imputa¸

ao pela m´

edia ou moda obteve erros mse no intervalo

[989.81 ± 29.45, 1044.24 ± 50.58].

. . . . . . . . . . . . . . . . . . . . . . . 120

5.7

Conjunto de dados Breast. Erro mse medido sobre o atributo 1 para diver-

sos valores do parˆ

ametro k do m´

etodo de imputaç˜

ao baseado no algoritmo

k-vizinhos mais pr´

oximos. Valores desconhecidos inseridos no atributo

1. Imputa¸

ao pela m´

edia ou moda obteve erros mse no intervalo

[8.98 ± 0.33, 9.39 ± 0.12]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.8

Comparaç˜

ao do m´

etodo 10-NNI com as estratégias internas utilizada pelos

indutores C4.5 e CN2 e com a imputa¸

ao pela m´

edia ou moda para

o conjunto de dados Bupa. Na Tabela 5.3 s˜

ao apresentados os resultados

na forma num´

erica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

5.9

Comparaç˜

ao do m´

etodo 10-NNI com as estratégias internas utilizada pelos

indutores C4.5 e CN2 e com a imputa¸

ao pela m´

edia ou moda para

o conjunto de dados CMC. Na Tabela 5.4 s˜

ao apresentados os resultados

na forma num´

erica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

LISTA DE FIGURAS

xix

5.10 Comparaç˜

ao do m´

etodo 10-NNI com as estratégias internas utilizada pelos

indutores C4.5 e CN2 e com a imputa¸

ao pela m´

edia ou moda para

o conjunto de dados Pima. Na Tabela 5.5 s˜

ao apresentados os resultados

na forma num´

erica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

5.11 Comparaç˜

ao do m´

etodo 10-NNI com as estratégias internas utilizada pelos

indutores C4.5 e CN2 e com a imputa¸

ao pela m´

edia ou moda para

o conjunto de dados CRX. Na Tabela 5.6 s˜

ao apresentados os resultados

na forma num´

erica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

5.12 Comparaç˜

ao do m´

etodo 10-NNI com as estratégias internas utilizada pelos

indutores C4.5 e CN2 e com a imputa¸

ao pela m´

edia ou moda para

o conjunto de dados Breast. Na Tabela 5.7 s˜

ao apresentados os resultados

na forma num´

erica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

5.13 Comparaç˜

ao do m´

etodo 10-NNI com as estratégias internas utilizada pelos

indutores C4.5 e CN2 e com a imputa¸

ao pela m´

edia ou moda para o

conjunto de dados Sonar. Na Tabela 5.11 s˜

ao apresentados os resultados

na forma num´

erica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

6.1

Erro no conjunto de teste para diversas distribuiç˜

oes de classes no conjunto

de treinamento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

6.2

Um exemplo de gr´

afico ROC para trˆ

es classificadores. . . . . . . . . . . . . 147

6.3

Exemplo de conjunto de dados com duas classes desbalanceadas. . . . . . . 151

6.4

A aplicaç˜

ao de ligaç˜

oes Tomek em um conjunto de dados. O conjunto

de dados original (a), Ligaç˜

oes Tomek identificadas (b), e ligaç˜

oes Tomek

removidas (c). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

6.5

Conjunto de dados ap´

os a remoç˜

ao de casos da classe majorit´

aria por meio

da criaç˜

ao de um subconjunto consistente. . . . . . . . . . . . . . . . . . . 153

xx

LISTA DE FIGURAS

Lista de Tabelas

2.1

Conjunto de exemplos no formato atributo-valor.

. . . . . . . . . . . . . .

20

4.1

Sistemas de aprendizado cujas sintaxes s˜

ao suportadas atualmente pela

biblioteca DOL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.2

Os identificadores especiais para diret´

orios utilizados atualmente pelo am-

biente Sniffer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.1

Descriç˜

ao resumida dos conjuntos de dados.

. . . . . . . . . . . . . . . . . 113

5.2

Atributos selecionados como os mais representativos de cada conjunto de

dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5.3

Resultados experimentais na forma num´

erica para o conjunto de dados Bupa.124

5.4

Resultados experimentais na forma num´

erica para o conjunto de dados CMC.126

5.5

Resultados experimentais na forma num´

erica para o conjunto de dados Pima.128

5.6

Resultados experimentais na forma num´

erica para o conjunto de dados CRX.131

5.7

Resultados experimentais na forma num´

erica para o conjunto de dados

Breast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

5.8

Erro m´

edio quadr´

atico (mse) entre os valores preditos e os valores reais para

os m´

etodos 10-NNI e imputa¸

ao pela m´

edia ou moda — conjunto de

dados Breast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

5.9

N´ıvel da ´

arvore de decis˜

ao no qual os atributos 1, 5 e 0 do conjunto de

dados Breast foram incorporados pelo indutor C4.5. “-” significa que o

atributo n˜

ao foi incorporadò

a ´

arvore de decis˜

ao. N´ıvel 1 representa a raiz

da ´

arvore. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

xxi

xxii

LISTA DE TABELAS

5.10 Índice de correlaç˜

ao linear r entre os atributos selecionados como mais

representativos e os atributos de maior correlaç˜

ao — conjunto de dados

Sonar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

5.11 Resultados experimentais na forma num´

erica para o conjunto de dados

Sonar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.1

Diferentes tipos de erros e acertos para um problema com duas classes. . . 144

6.2

Resultados dos experimentos para o conjunto de dados Hepatitis. . . . . . 156

A.1 Exemplo de arquivo de declaraç˜

ao de atributos: voyage.names. . . . . . . 171

A.2 Exemplo de arquivo de declaraç˜

ao de dados: voyage.data. . . . . . . . . . 172

A.3 Tipos de dado suportados pela sintaxe DSX. . . . . . . . . . . . . . . . . . 173

A.4 Exemplo de arquivo de declaraç˜

ao de atributos, voyage.names, com decla-

raç˜

ao de atributo virtual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

A.5 As l´ınguas aceitas pela definiç˜

ao estendida date_language. . . . . . . . . . 178

Lista de Algoritmos

2.1

Algoritmo que procura por uma hip´

otese consistente com os exemplos por

meio de operaç˜

oes de generalizaç˜

ao e especializaç˜

ao. . . . . . . . . . . . . .

18

4.1

Algoritmo que divide um conjunto de exemplos em k pares de conjuntos

de treinamento e teste segundo o m´

etodo de reamostragem k-fold cross-

validation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.1

Vers˜

ao b´

asica do algoritmo k-vizinhos mais pr´

oximos para problemas

com classes qualitativas. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

6.1

Algoritmo para encontrar um subconjunto consistente.

. . . . . . . . . . . 153

xxiii

xxiv

LISTA DE ALGORITMOS

Lista de Abreviaturas

10-NNI

. . . . . . . . . . . . . . . . . . . . . . . . . 10-Nearest Neighbour Imputation

AM

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Aprendizado de Máquina

API

. . . . . . . . . . . . . . . . . . . . . . . . . . Application Programming Interface

ARFF

. . . . . . . . . . . . . . . . . . . . . . . . . . . . Attribute Relation Format File