Monografia-Joilma Souza Algoritmos Genéticos

Universidade Federal da Bahia Instituto de Matemtica

Departamento de Cincia da Computao

Minerao de Dados Utilizando Algoritmos Genticos

Joilma Souza Santos Orientadora: Prof. Daniela Barreiro Claro

Salvador Bahia

2008

Joilma Souza Santos

Minerao de Dados Utilizando Algoritmos Genticos

Monografia apresentada ao Curso de Graduao

em Cincia da Computao da Universidade

Federal da Bahia como requisito parcial

obteno do diploma de Bacharel em Cincia da

Computao.

Orientadora: Prof. Daniela Barreiro Claro

Salvador Bahia 2008

AGRADECIMENTOS

Agradeo a Deus por tudo que tem feito por mim e por nunca ter me deixado

sucumbir diante das dificuldades que enfrentei para chegar at aqui.

Agradeo a meu pai pelos sacrifcios que fez por mim e pelo amor que sempre me

deu e a quem eu sempre serei grata, e a minha irm Joelma.

A meu namorado Tadeu que me ajudou nos momentos mais difceis, e que todo dia

me oferece suporte.

A Eric Sobral, pela interface grfica da ferramenta deste projeto, e por sua amizade.

A meus colegas de trabalho, que para mim j so como parte de minha famlia e que

me ajudaram nesse projeto.

A todos os meus amigos e amigas, que me apoiaram com uma palavra de incentivo,

com um sorriso quando estava desanimada. Vocs so tesouros em minha vida, e fica aqui o

meu mais sincero agradecimento.

Joilma Souza Santos

Estamos nos afogando em dados, mas sedentos por conhecimento.

John Naisbitt

RESUMO

A produo crescente de dados por organizaes privadas e pblicas produz enormes

bases de dados. Conseqentemente, as tarefas de anlise e extrao de informaes

tornam-se extremamente custosas para um analista humano. No processo de Minerao de

Dados ou Data Mining, a anlise e extrao do conhecimento realizada procurando-se

padres consistentes e/ou relacionamentos sistemticos entre as instncias destes dados.

Para implementao dessa tcnica, mtodos automticos baseados na Inteligncia Artificial

so usados a fim de aperfeioar o processo de anlise. Este projeto visa determinar padres

atravs dos algoritmos genticos com o intuito de minerar os dados. Os padres obtidos

atravs dos algoritmos genticos so comparados com padres determinados atravs do uso

de um outra tcnica de Inteligncia Artificial, a Lgica Fuzzy e uma ferramenta com o intuito

de integrar estas duas tcnicas foi desenvolvida.

Palavras-Chave: Minerao de Dados, KDD, Inteligncia Artificial, Algoritmos Genticos,

Banco de Dados.

ABSTRACT

The growing volume of information by public and private organizations produces

huge databases. Therefore, the tasks of analysis and extraction of information becomes

extremely costly for analysts. In the process of Data Mining, these tasks require consistent

standards and / or systematic relationships between different instances of these data. To

implement and optimize the analysis process, automation methods based on artificial

intelligence are used. This project aims to determine patterns through genetic algorithms

with a view to mine the data. The patterns obtained from the Genetic algorithms are

compared with standards set by use a different technique of artificial intelligence, fuzzy logic

and a tool with the aim of integrating these two techniques was developed.

Keywords: Data Mining, KDD, Artificial Intelligence, Genetics Algorithms, Data Bases

LISTA DE FIGURAS

Figura 2.1: Fases do Processo de KDD (PAPPA, 2002 apud LIU; MOTODA, 1998) ................... 17

Figura 2.2: Exemplo de Classificao (CARVALHO, 2005) ........................................................ 19

Figura 2.3: Exemplo de dados organizados em clusters (CARVALHO, 2005) ........................... 21

Figura 2.4: Exemplo de interao de atributos em problema de classificao do tipo XOR

(PAPPA, 2002) ........................................................................................................................... 23

Figura 3.1: Funo hipottica com um mximo local e outro global (LINDEN, 2006). ............ 27

Figura 3.2: Modelo da Tcnica de Gerao e Teste ................................................................. 28

Figura 3.3: Esquema de um algoritmo gentico (LINDEN, 2006) ............................................. 29

Figura 3.5: Roleta Viciada para a populao exemplo da tabela 3.1 (LINDEN, 2006) .............. 34

Figura 3.6: Tipos de cruzamento (crossover) (CARVALHO, 2005) ............................................ 36

Figura 4.1: Matriz de Confuso para uma Regra de Classificao (FREITAS, 2001). ............... 44

Figura 4.2: Exemplo de crossover de generalizao/especializao (FREITAS, 2001).............. 48

Figura 5.1: Diagrama de Classe da Funo de Seeding ............................................................ 52

Figura 5.2: Diagrama de Classe da Funo do Operador de Sufrgio Universal ...................... 53

Figura 5.3: Diagrama de Classe da Funo do Operador de Mutao .................................... 54

Figura 5.4: Diagrama de Classe da Funo do Operador de Cruzamento Uniforme ............... 55

Figura 5.5: Diagrama de Classe da Funo de Fitness .............................................................. 56

Figura 5.6: Execuo de experimento utilizando lgica nebulosa. .......................................... 57

Figura 5.7: Execuo de experimento utilizando o algoritmo gentico implementado. ........ 58

Figura 5.8: Execuo de experimento utilizando o algoritmo gentico implementado e

comparando o resultado com a rvore fuzzy escolhida. .......................................................... 59

Figura 6.1: Acurcia X nmero de geraes ............................................................................. 64

Figura A.1: Formato de arquivo de dados a ser lido pelo Explorer Patterns Tool (SOUZA, 2008)

.................................................................................................................................................. 71

Figura A.2: Mensagem de erro gerada caso um arquivo no tenha sido carregado. .............. 71

Figura A.3: Tela principal do EPT .............................................................................................. 72

Figura A.4: Tela para experimentos utilizando rvores de deciso nebulosas ........................ 74

Figura A.5: Mensagem de erro gerada caso algum item requerido no seja informado. ....... 75

Figura A.6: Janela para gravao de arquivo de resultados para experimentos utilizando

Lgica Nebulosa. ....................................................................................................................... 76

Figura A.7: Tela para experimentos utilizando um algoritmo evolucionrio ........................... 77

Figura A.8: Janela para gravao de arquivo de resultados para experimentos utilizando AG.

.................................................................................................................................................. 78

Figura A.9: Janela para realizao de experimentos comparativos entre algoritmos nebulosos

e genticos ................................................................................................................................ 79

Figura A.10: Janela para gravao de arquivo de resultados dos testes comparativos. ......... 80

LISTA DE TABELAS

Tabela 3.1: Grupo de indivduos, seus respectivos fitness e parcela na roleta (LINDEN, 2006)

................................................................................................................................................ 34

Tabela 6.1: Informaes sobre os conjuntos de dados (SOUZA, 2008) ................................... 61

Tabela 6.2: Resultados das Comparaes entre as Taxas de Acurcia Obtidas pelo Algoritmo

Gentico Implementado e as rvores Fuzzy Implementadas no EFT ...................................... 63

LISTA DE ABREVIATURAS E SIGLAS

KDD Knowledge Data Discovery p.13 WEKA Waikato Environment for Knowledge Analysis p.13 EFT Explorer Fuzzy Tree p.13 AG Algoritmo Gentico p.24 COGIN Covered-based Genetic Induction p.39 REGAL Relational Genetic Algorithm Learner p.40 VP Verdadeiro Positivo p.44 VN Verdadeiro Negativo p.44 FP Falso Positivo p.44 FN Falso Negativo p.44 EPT Explorer Patterns Tool p.49

SUMRIO

1 INTRODUO ............................................................................................................. 13

2 MINERAO DE DADOS .............................................................................................. 16

2.1 AS FASES DO PROCESSO DE DESCOBERTA DE CONHECIMENTO ........................................................ 17

2.2 TAREFAS DA MINERAO DE DADOS ......................................................................................... 19

2.1.1 REGRAS DE CLASSIFICAO .................................................................................................. 19

2.1.2 CLUSTERIZAO (AGRUPAMENTO) ........................................................................................ 20

2.1.3 REGRAS DE ASSOCIAO ..................................................................................................... 21

2.3 UTILIZAO DE ALGORITMOS GENTICOS (AGS) NO PROCESSO DE KDD .......................................... 22

3 ALGORITMOS GENTICOS (AG) ................................................................................... 25

3.1 FUNCIONAMENTO DE UM ALGORITMO GENTICO ........................................................................ 28

3.2 REPRESENTAO CROMOSSOMIAL (CODIFICAO DO INDIVDUO) ................................................... 29

3.3 FUNO DE AVALIAO (FITNESS) ............................................................................................ 31

3.4 ESQUEMAS ........................................................................................................................... 31

3.5 OPERADORES GENTICOS ........................................................................................................ 33

3.4.1 SELEO DE PAIS ................................................................................................................ 33

3.4.2 RECOMBINAO OU CRUZAMENTO (CROSSOVER) .................................................................... 35

3.4.3 MUTAO ........................................................................................................................ 37

3.6 ELITISMO ............................................................................................................................. 37

3.7 NICHOS BIOLGICOS .............................................................................................................. 38

3.6.1 FITNESS SHARING ............................................................................................................... 38

3.6.2 COGIN (COVERED-BASED GENETIC INDUCTION) .................................................................... 39

3.6.3 REGAL (RELATIONAL GENETIC ALGORITHM LEARNER) ............................................................ 40

4 DESCOBERTA DE REGRAS USANDO AGS ...................................................................... 41

4.1 CODIFICAO DO INDIVDUO ................................................................................................... 41

4.2 OPERADOR DE INTRODUO DE NOVOS INDIVDUOS (SEEDING) ..................................................... 42

4.3 FUNO DE AVALIAO PARA DESCOBERTA DE REGRAS DE CLASSIFICAO ....................................... 43

4.4 MTODOS PARA MANTER A DIVERSIDADE DE REGRAS .................................................................. 45

4.5 OPERADOR DE CRUZAMENTO (CROSSOVER) ................................................................................ 47

4.6 OPERADOR DE GENERALIZAO E ESPECIALIZAO....................................................................... 48

5 IMPLEMENTAO ...................................................................................................... 49

5.1 ARQUITETURA DA FERRAMENTA ............................................................................................... 49

5.2 ALGORITMO IMPLEMENTADO................................................................................................... 50

5.2.1 INICIALIZAO DA POPULAO ............................................................................................. 51

5.2.2 SELEO DE PAIS ................................................................................................................ 52

5.2.3 CRUZAMENTO, MUTAO E ELITISMO: EVOLUO DOS INDIVDUOS ........................................... 53

5.2.4 CLCULO DA FUNO DE AVALIAO .................................................................................... 55

5.3 EXPERIMENTOS ..................................................................................................................... 56

5.3.1 RELATRIO DE RESULTADOS ................................................................................................. 59

6 EXPERIMENTOS REALIZADOS ...................................................................................... 60

6.1 BASES DE DADOS UTILIZADAS .................................................................................................. 60

6.2 MTODOS DE EXPERIMENTAO .............................................................................................. 61

6.2.1 CONJUNTO DE TREINO (TRAINING SET) .................................................................................. 61

6.2.2 VALIDAO CRUZADA (CROSS-VALIDATION) ........................................................................... 61

6.2.3 PERCENTAGEM DE TREINO (PERCENTAGE SPLIT) ...................................................................... 62

6.3 PROCEDIMENTOS EXPERIMENTAIS ............................................................................................. 62

6.4 RESULTADOS E DISCUSSES ..................................................................................................... 63

7 CONCLUSO ............................................................................................................... 66

REFERNCIAS BIBLIOGRFICAS ........................................................................................ 68

APNDICE A MANUAL PARA UTILIZAO DO EXPLORER PATTERNS TOOL ...................... 70

A.1 TELA PRINCIPAL .................................................................................................................... 72

A.2 TELA PARA EXPERIMENTOS UTILIZANDO LGICA NEBULOSA .......................................................... 73

A.3 TELA PARA EXPERIMENTOS UTILIZANDO ALGORITMOS GENTICOS .................................................. 76

A.4 TELA PARA EXPERIMENTOS UTILIZANDO ALGORITMOS GENTICOS E LGICA NEBULOSA ..................... 79

13

1 INTRODUO

O advento do desenvolvimento da tecnologia tornou a captao e armazenamento

de dados uma tarefa mais simples e barata (FIGUEIRA, 2008 apud FERNANDES, 2003a), o que

contribuiu para o aparecimento de bases de dados cada vez mais complexas e maiores.

Com a crescente valorizao da informao nas ltimas dcadas, a extrao de

conhecimento desses dados brutos torna-se um diferencial no desenvolvimento de

estratgias de investimento de empresas pblicas ou privadas. Experincias como a relatada

no lendrio exemplo das fraldas e cerveja mostram como decises baseadas na anlise de

dados podem aumentar o volume de vendas de determinado produto (FUCHS, 2004).

O modo mais tradicional para extrair informao de uma base de dados baseia-se na

anlise e interpretao manuais; este modo de anlise, alm de lento,

computacionalmente custoso e subjetivo (FAYYAD et al., 1996). Visando a extrao mais

rpida e confivel de conhecimento, surgem mtodos automticos denominados Knowledge

Data Discovery, ou simplesmente KDD. O KDD aplica mtodos interdisciplinares

especialmente mtodos estatsticos e de aprendizado de mquina para extrair

conhecimento de alto nvel a partir de bases de dados reais (FREITAS, 2001) e tem a

Minerao de Dados como principal tarefa.

O processo de Minerao de Dados ou Data Mining analisa e extrai informaes teis

a partir de dados. A captao de conhecimento de alto nvel atravs deste processo se d a

partir da procura de padres consistentes e/ou relacionamentos sistemticos entre

instncias de dados, classificando-os em subconjuntos de informaes baseados em regras

estatsticas e da teoria da informao.

Algoritmos de aprendizado de mquina so amplamente utilizados na tarefa de

Minerao de Dados. Estes algoritmos so baseados na construo de rvores de deciso,

utilizando-se como matria prima os dados de treinamento. Atravs do percurso destas

14

rvores, da raiz at um n folha1 possvel inferir classes a dados baseados em

determinados valores para cada atributo.

Para uma classificao com maior percentual de acerto (acurcia2), mtodos de

aprendizado de mquina baseados em Lgica Fuzzy tm-se mostrado mais eficientes que

mtodos clssicos (SOUZA, 2008). Apesar da perceptvel contribuio que a Lgica Fuzzy

proporciona acurcia das rvores de classificao utilizadas na Minerao de Dados, o

WEKA (Waikato Environment for Knowledge Analysis) (FRANK; TRIGG, 1993), principal

ferramenta gratuita para Minerao de Dados, baseada em algoritmos de aprendizado de

mquina, no implementa tcnicas com algoritmos baseados na lgica nebulosa.

Outra abordagem para realizao da Minerao de Dados utiliza algoritmos de

aprendizado de mquina baseados na Computao Evolutiva os Algoritmos Genticos.

Estes algoritmos realizam buscas globais e permitem uma melhor interao entre atributos

que os algoritmos baseados na estratgia gulosa que so geralmente utilizados para a tarefa

de Minerao de Dados e por isso so extremamente teis na procura de padres relevantes

em dados (FREITAS, 2001 apud DHAR V; PROVOST, 2000). Os Algoritmos Genticos tambm

no foram implementados no WEKA.

Para disponibilizar a Minerao de Dados utilizando rvores de classificao fuzzy e

testar a acurcia dessas rvores em relao a rvores de classificao clssicas, foi

desenvolvido o EFT (Explorer Fuzzy Tree) (SOUZA, 2008). Para determinar a acurcia das

rvores fuzzy implementadas pelo EFT, foram feitos testes utilizando quatro bases de dados

de complexidades diferentes: Iris (FISHER, 1988), Segment-challenge (GROUP, 1990a),

Segment-test (GROUP, 1990b) e SPAMBASE (HOPKINS et al., 2001).

Assim, o presente trabalho aplica Algoritmos Genticos tarefa de Minerao de

Dados e incorpora o algoritmo implementado ferramenta Explorer Fuzzy Tree (EFT). Com o

intuito de avaliar o algoritmo implementado, novos experimentos foram realizados sobre

estes algoritmos utilizando as mesmas quatro bases de dados utilizadas para o teste dos

1 N folha n terminal de uma rvore, que no caso de uma rvore de classificao, corresponde a classe que

caracteriza um dado objeto com os valores de atributos; 2 Acurcia exatido de uma operao;

15

algoritmos de construo de rvores fuzzy. Os resultados obtidos mostraram uma igualdade

de desempenho entre as duas tcnicas para bases de dados mdias,

Esta monografia est dividida em seis captulos, dispostos da seguinte forma: o

captulo 2 apresenta e detalha os conceitos de Minerao de Dados; o captulo 3 apresenta

os Algoritmos Genticos e a Computao Evolutiva; o captulo 4 detalha a implementao do

algoritmo gentico usado para extrao de conhecimento de alto nvel de bases de dados; o

captulo 5 apresenta os experimentos realizados e discute seus resultados; e por fim,

captulo 6 apresenta a concluso e trabalhos futuros.

16

2 MINERAO DE DADOS

Conhecimento a informao devidamente organizada e que pode ser aplicada a

resoluo de problemas. Em uma base de dados, encontra-se a matria-prima para a

obteno de conhecimento, que pode ser realizada utilizando o processo de descoberta de

conhecimento em bases de dados, ou KDD.

Atualmente, as bases de dados vm crescendo em alta velocidade, abrigando milhes

de registros com dezenas de atributos. Essas bases de dados crescem de suas maneiras: o

nmero N de registros ou objetos na base aumenta ou ainda o nmero d de campos ou

atributos deste objeto aumenta, de modo que bases de dados que possuem em mdia N =

109 objetos ou d = 10 2 ou at mesmo d = 103 tm-se tornado comum (FAYYAD et al., 1996).

A anlise manual dessas bases de dados com grandes nmeros de atributos ou registros

pode ser um processo demorado.

Os resultados da anlise destes dados armazenados podem ser utilizados para

atribuir maior competitividade s empresas, que, baseadas nestes resultados, podem

desenvolver estratgias mais efetivas para obteno de sucesso em suas respectivas reas

de atuao, assim como tambm pode ser utilizada no campo cientfico, para promover a

melhor interpretao dos dados coletados atravs das pesquisas cientficas.

O KDD um processo no trivial de identificao de padres vlidos, potencialmente

teis e compreensveis a partir de dados3 (FAYYAD et al., 1996). Para a identificao destes

padres, o processo de KDD realiza operaes em dados brutos que vo desde a seleo dos

dados a serem utilizados at a anlise dos padres encontrados para a obteno de

conhecimento til. A busca destes padres possui algumas etapas baseadas em estratgicas

3 Segundo Fayyad, dado um conjunto de fatos e padro uma expresso em alguma linguagem que descreve

um subconjunto de dados ou um modelo aplicvel a este subconjunto; o termo processo denota que o KDD envolve vrios passos; no trivial denota que o processo de KDD demanda alguma busca ou inferncia.

computacionais, o que permite que enormes volumes de dad

rapidamente e de forma no subjetiva. A figura 2.1 apresen

Figura 2.1: Fases do Processo de KDD (PAPPA

H ainda confuso em relao aos

so esporadicamente tratados como sinnimos. Porm, como mostrado na figura acima, a

Minerao de Dados apenas

A Minerao de Dados

descoberta de dados e na

informao (FAYYAD et al., 1996), enquanto que o termo KDD refere

aplicados a dados brutos para a obteno de

1999). As fases do processo de KDD so discutidas a seguir.

2.1 As Fases do Processo de Descoberta de Conhecimento

O processo de KDD interativo e iterativo e envolve vrios passos onde decises so

feitas pelo usurio (FAYYAD

Data Warehouse, que coleta e reuni informaes de vrias bases de dados

integrao entre eles. No pr

Warehouse so filtradas e selecionado apenas o contedo relevante para a tarefa que ser

realizada. Este processo de filtragem

correo de erros e preenchimento de valores nulos

dados a serem utilizados.

computacionais, o que permite que enormes volumes de dad

rapidamente e de forma no subjetiva. A figura 2.1 apresenta as etapas do processo de KDD.

: Fases do Processo de KDD (PAPPA, 2002 apud LIU; MOTODA, 1998)

H ainda confuso em relao aos termos Minerao de Dados e KDD


apenas uma das etapas do processo de KDD.

A Minerao de Dados consiste na aplicao de algoritmos para a

na produo de padres ou modelos a partir

et al., 1996), enquanto que o termo KDD refere

aplicados a dados brutos para a obteno de dados de alto nvel (GOEBEL; GRUENWALD,

As fases do processo de KDD so discutidas a seguir.

As Fases do Processo de Descoberta de Conhecimento


FAYYAD et al., 1996). A primeira etapa do processo de KDD a etapa de

que coleta e reuni informaes de vrias bases de dados

. No pr-processamento, as informaes coletadas na fase d

das e selecionado apenas o contedo relevante para a tarefa que ser

realizada. Este processo de filtragem reforado por mtodos de reduo de rudos

correo de erros e preenchimento de valores nulos, para garantir a confiabilidade dos

17

computacionais, o que permite que enormes volumes de dados sejam analisados

ta as etapas do processo de KDD.

apud LIU; MOTODA, 1998)

termos Minerao de Dados e KDD. Esses termos


algoritmos para a anlise e

padres ou modelos a partir de grandes bases de

et al., 1996), enquanto que o termo KDD refere-se a todos os passos

alto nvel (GOEBEL; GRUENWALD,

As Fases do Processo de Descoberta de Conhecimento


A primeira etapa do processo de KDD a etapa de

que coleta e reuni informaes de vrias bases de dados, realizando a

processamento, as informaes coletadas na fase de Data

das e selecionado apenas o contedo relevante para a tarefa que ser

reforado por mtodos de reduo de rudos,

para garantir a confiabilidade dos

18

geralmente desejvel a interveno de um analista humano nas etapas citadas

anteriormente, a fim de que seu conhecimento sobre as informaes relevantes que devem

ser extradas pelo processo de KDD seja utilizado (FREITAS, 2001).

Aps o refinamento dos dados a serem utilizados, a discretizao pode ser utilizada

para transformar um atributo com valores contnuos em um atributo categrico

(categorical) ou nominal, formando intervalos discretos (FREITAS, 2001).

A etapa de seleo de atributos encontra atributos que possuem relevncia para o

objetivo que deve ser satisfeito pelo processo de KDD, encontrando um subconjunto de

atributos relevantes (atributos capazes de distinguir exemplos pertencentes a classes

diferentes (PAPPA, 2002)) entre os atributos originais do registro para ser utilizado no

processo de minerao de dados. A motivao para a realizao desta etapa baseada nos

seguintes fatores: algoritmos de minerao de dados que utilizam mtodos de induo tem

seu tempo de execuo aumentado caso haja muitos atributos presentes (PAPPA, 2002); a

presena de atributos irrelevantes ou redundantes pode de alguma maneira levar o

algoritmo a uma classificao equivocada dos dados, levando o processo a produzir dados

pouco relevantes ou no confiveis (FREITAS, 2001); experimentos comprovam que o

nmero de exemplos para garantir certa taxa de classificao cresce de maneira exponencial

baseada no nmero de atributos irrelevantes presentes (PAPPA, 2002 apud LANGLEY; IBA,

1993). Outra motivao encontrada para a seleo de atributos est na melhora da

performance do algoritmo de minerao de dados, com melhores taxas de aprendizado ou

regras mais simples (PAPPA, 2002).

A prxima etapa do processo de KDD a Minerao de Dados. Nesta etapa aplicado

um algoritmo baseado na estratgia computacional escolhida para minerao de dados, e

extrado conhecimento dessa base de dados. A ltima etapa do processo, o ps-

processamento, visa validar, interpretar e organizar o conhecimento encontrado, obtendo

conhecimento realmente til (PAPPA, 2002).

interessante salientar que o conhecimento resultante do processo de KDD deve

possuir as seguintes propriedades: ser confivel (conhecimento com alta acurcia),

compreensvel e interessante (FREITAS, 2001). Conhecimento com alta taxa de acurcia nos

permite seu uso para prever o valor que alguns atributos podero possuir no futuro,

baseado nos dados observados. Este conhecimento deve tambm ser compreensvel para o

usurio, j que ele deve utilizar o conheci

vrias reas. Alm disso, esses dados devem ser interessantes

ser medida pelo seu carter

2.2 Tarefas da Minerao de Dados

Essa sesso discute

classificao, a clusterizao e

2.1.1 Regras de Classifica

Alvo de estudo das comunidades da rea estatstica e de aprendizado de mquina, a

classificao tem como objetivo

por uma referncia externa, baseado no valor dos demais atributos de um exemplo

pertencente a uma base de dados

aplicado a uma base de dados.

Figura 2.

Um algoritmo de classificao

(a parte conseqente da regra) representa



usurio, j que ele deve utilizar o conhecimento adquirido no processo como diferencial em

vrias reas. Alm disso, esses dados devem ser interessantes propriedade mais difcil de

pelo seu carter subjetivo

Tarefas da Minerao de Dados

a sesso discute algumas tcnicas utilizadas pela Minerao de Dado

classificao, a clusterizao e as regras de associao.

Classificao


classificao tem como objetivo prever o valor de um atributo objetivo, a ser

por uma referncia externa, baseado no valor dos demais atributos de um exemplo

pertencente a uma base de dados B. A figura 2.2 demonstra o processo de classificao

dados.

Figura 2.2: Exemplo de Classificao (CARVALHO, 2005)

Um algoritmo de classificao gera regras do tipo (l-se:

(a parte conseqente da regra) representa o atributo objetivo (classe) e

19



mento adquirido no processo como diferencial em

propriedade mais difcil de

Minerao de Dados: regras de


objetivo, a ser determinado

por uma referncia externa, baseado no valor dos demais atributos de um exemplo E

demonstra o processo de classificao

se: Se X ento Y), onde Y

atributo objetivo (classe) e X (a parte

20

antecedente da regra) representa um conjunto de valores tomados por atributos,

geralmente representados por uma conjuno. A seguinte regra poderia ser uma regra

gerada por um algoritmo de classificao: > 35 > $ 2.500,00

! = #$, onde > 35 > $ 2.500,00 seria a parte

antecedente da regra e ! = #$ seria a parte conseqente da regra

(classe).

Este trabalho utiliza algoritmos genticos para gerar regras que tero o formato

descrito acima. Este formato foi escolhido por ser intuitivo e facilmente compreendido pelo

usurio. Abaixo outros exemplos de regras de classificao:

%&' = ( 25 < %&'%* < 30 +, = &.

&%(% = ( (-& %'./*0.($ = $*%0 '( = &

Para a gerao das regras de classificao, a base de dados dividida em dois

conjuntos de exemplos: C1 e C2, que possuem todos os seus exemplos j previamente

classificados. O algoritmo de classificao recebe o conjunto de exemplos C1 (o conjunto de

treinamento), aplica tcnicas de estatsticas e/ou de aprendizado de mquina e gera as

regras de classificao, baseado nos valores encontrados nos atributos de cada um dos

exemplos. Posteriormente, o algoritmo aplica as regras de classificao geradas no conjunto

de exemplos C2 (o conjunto de teste), e mede o quo confiveis so as regras geradas no

processo anterior. A propriedade que mede o quo confivel uma regra , ou seja, quantos

exemplos do conjunto de teste foram corretamente classificados por esta regra, a

acurcia. importante que o algoritmo de classificao no tenha acesso ao conjunto de

teste na etapa de gerao de regras, ou ento, a medio da acurcia das regras ficaria

comprometida e a fase de testes no apresentaria resultados confiveis.

2.1.2 Clusterizao (Agrupamento)

A clusterizao visa classificar a informao a ser minerada em clusters ou classes.

Cada um desses clusters formado por exemplos que possuem caractersticas similares em

seus atributos. Essa classificao feita de modo a maximizar as diferenas encontradas

entre clusters diferentes e minimizar as diferenas entre exemplos pertencentes ao mesmo

cluster.

Por realizar a classificao dos exemplos baseado nos valores dos atributos dos

prprios exemplos, ou seja, descobrir classes para os exemplos e agrup

sem que seja informada nenhuma referncia externa, a clusterizao considerada uma

forma de aprendizado no supervisionado (FREITAS, 2001).

A clusterizao prepara os dados para a aplicao de um algoritmo de classificao,

uma vez que divide estes dados em classes, que sero usadas posteriormente

de classificao (CARVALHO,

Por exemplo, numa base como a Iris (FISHER, 1988), cada exemplo possui

determinado valor para os comprimentos e larguras da ptala e da spala de uma

determinada flor. Baseado

clusters: o cluster Iris-setosa, o cluster Iris

Figura 2.3

2.1.3 Regras de Associao

As regras de associao

E do tipo (Se X ento



prprios exemplos, ou seja, descobrir classes para os exemplos e agrup


aprendizado no supervisionado (FREITAS, 2001).


uma vez que divide estes dados em classes, que sero usadas posteriormente

de classificao (CARVALHO, 2005).



o nesses atributos, um algoritmo de clusterizao

setosa, o cluster Iris-versicolor e o cluster Iris-virginica.

3: Exemplo de dados organizados em clusters (CARVALHO, 2005)

Associao

associao so regras encontradas a partir de um conjunto de exemplos

ento Y), onde X e Y so conjuntos de itens, tal que

21



prprios exemplos, ou seja, descobrir classes para os exemplos e agrup-los em classes



uma vez que divide estes dados em classes, que sero usadas posteriormente pelo algoritmo



nesses atributos, um algoritmo de clusterizao encontraria trs

virginica.

(CARVALHO, 2005)

a partir de um conjunto de exemplos

conjuntos de itens, tal que 1 Y = 2. Cada

22

regra encontrada sinaliza que os conjuntos de itens X e Y so freqentemente encontrados

em um mesmo exemplo.

O uso de regras de associao pode ser ilustrado usando-se o exemplo das fraldas e

das cervejas (FUCHS, 2004). Estas regras aplicadas a um conjunto de exemplos E, onde cada

exemplo representa uma transao de compra de um cliente, permitiram a descoberta do

produto cerveja como sendo o mais vendido junto ao produto fraldas, ou seja, foram

encontrados muitos exemplos onde os itens fraldas e cervejas faziam parte da compra dos

consumidores do supermercado e assim pde ser comprovada a associao entre a compra

das fraldas e a compra das cervejas, ou seja: 3 40+.

Apesar de possurem a mesma estrutura , as regras de associao e regras de

classificao possuem diferenas decisivas: regras de associao podem possuir mais de um

item na parte conseqente da regra (Y), enquanto regras de classificao s podem possuir

um atributo objetivo. Alm disso, em regras de classificao, os atributos previsores (X) s

podem ocorrer na parte antecedente da regra e o atributo objetivo (Y) somente ocorre na

parte conseqente da regra, o que no uma constante em regras de associao. Abaixo

alguns exemplos de regras de associao:

5 7(%,, 8*+ (clientes que compram po, geralmente compram

manteiga e queijo)

9%% 3% -,(% (clientes que compram batatas fritas

geralmente compram refrigerante).

2.3 Utilizao de Algoritmos Genticos (AGs) no Processo de KDD

Os algoritmos genticos podem ser aplicados s etapas do processo de KDD, desde o

pr-processamento dos dados brutos para aplicao da minerao de dados por exemplo,

na seleo de atributos, podendo ser aplicados tambm minerao de dados. Esta tcnica

pode tambm ser aplicada a etapa de ps-processamento do conhecimento encontrado.

O uso dos AGs na etapa de seleo de atributos motivado pela interao de

atributos. Os algoritmos baseados em outras tcnicas desenvolvidos para esta tarefa, como

23

por exemplo, algoritmos baseados na estratgia gulosa, podem no ser confiveis, levando a

no seleo de atributos relevantes para a correta classificao dos dados, como demonstra

o exemplo a seguir, ilustrado na figura 2.4.

Figura 2.4: Exemplo de interao de atributos em problema de classificao do tipo XOR (PAPPA, 2002)

Na figura 2.4 ilustrado um exemplo utilizando a funo XOR. Esta funo classifica

os dados em 0 ou 1, baseado no valores de todos os seus atributos previsores. Nesta funo,

dados com valores de atributos previsores (A1 e A2) iguais pertencem a classe 0 (B = 0) e

dados com valores de atributos diferentes pertencem a classe 1 (B = 1). Caso um mtodo de

seleo de atributos guloso fosse aplicado a este exemplo, encontraria uma distribuio

igual de classes ao selecionar qualquer um dos atributos previsores, tendo 50% dos

resultados igual a 1 e os outros 50% dos resultados iguais a 0 e chegaria a concluso que

nenhum dos atributos previsores so relevantes para a tarefa de classificao, chegando

ento a uma concluso equivocada, j que o resultado da funo XOR depende de todos os

atributos previsores (PAPPA, 2002).

A principal motivao para o uso de algoritmos genticos para descoberta de regras

de classificao tambm est na melhor interao entre atributos proporcionada pelos AGs

se comparados com algoritmos baseados na estratgica gulosa para induo de regras de

classificao, e que so geralmente mais utilizados para minerao de dados (FREITAS,

2001). Outra vantagem importante do uso de AGs para esta tarefa a busca global realizada

por esta tcnica, aumentando a probabilidade de se obter um conjunto de regras com alta

acurcia preditiva.

Duas caractersticas dos AGs so decisivas para a sua utilizao no processo de KDD, e

seu sucesso diante de algumas das tcnicas tradicionais de busca: a) algoritmos genticos

24

so mtodos de busca globais AGs no utilizam apenas informao local e por isso no

necessariamente prendem-se a solues timas locais, como certos mtodos de busca

(LINDEN, 2006); b) AGs utilizam informao da populao corrente para determinar o

prximo estado da busca (LINDEN, 2006), e atravs de uma funo objetivo e dos

operadores genticos de cruzamento (crossover) e mutao (mutation) promovem a

interao entre os atributos de um objeto.

Vale salientar que os algoritmos genticos no garantem que a soluo encontrada

seja a soluo tima para o problema proposto, todavia estes algoritmos tendem a

encontrar boas solues ou solues muito prximas da soluo tima. Os operadores

genticos e demais aspectos dos AGs so descritos no captulo 3 deste trabalho.

25

3 ALGORITMOS GENTICOS (AG)

Algoritmos Evolucionrios so basicamente algoritmos inspirados nos princpios da

seleo natural e da gentica natural (FREITAS, 2007). Existe uma grande variedade de

modelos computacionais propostos dentro deste paradigma, mas todos simulam os

mecanismos de evoluo natural das espcies, onde, a partir de operadores genticos

seleo, cruzamento e mutao novas espcies so criadas novas geraes utilizando

indivduos que so avaliados segundo seu desempenho dentro de um ambiente (LINDEN,

2006).

Durante os anos de 1950 e 1960 alguns cientistas computacionais estudaram as

tcnicas evolucionrias, para que se tornassem uma alternativa de ferramenta de otimizao

para a resoluo de problemas de engenharia, criando um conjunto de solues candidatas

a resoluo do problema proposto, e utilizando operadores inspirados na gentica e soluo

natural para a busca das melhores solues (MITCHELL, 1996). Os operadores genticos so

aproximaes computacionais de fenmenos naturais como a reproduo sexuada

(crossover ou cruzamento) e a mutao gentica (mutao ou mutation) (LINDEN, 2006)

O conceito da evoluo natural aplicado computao para a resoluo de

problemas computacionais, pois os mecanismos de evoluo parecem se adequar a estes

problemas nas mais variadas reas (MITCHELL, 1996). Problemas que envolvem buscas em

um espao muito grande de soluo como a busca de um conjunto de regras de

classificao a partir de uma base de dados, dentre outros problemas que requerem

solues difceis de serem projetadas, podem utilizar-se do conceito da seleo e evoluo

natural para criarem e melhorarem solues adaptadas a esses problemas complexos.

O comportamento padro dos algoritmos evolucionrios representado pela

listagem 3.1.

26

Listagem 3.1: Pseudocdigo de um Algoritmo Evolucionrio (LINDEN, 2006)

Como ilustrado na listagem 3.1, os algoritmos evolucionrios so mtodos

fortemente probabilsticos, visto que a gerao da populao inicial e a seleo feita para a

escolha dos indivduos que sero recombinados e submetidos mutao raramente gera

indivduos iguais a cada execuo do algoritmo, o que faz com que os resultados

encontrados por um algoritmo evolucionrios sejam raramente reprodutveis, e por isso so

heursticas4 que no asseguram a obteno do melhor resultado possvel em todas as suas

execues (LINDEN, 2006)

Em 1975, John Holland no livro Adaptive in Natural and Artificial Systems,

formalizou e fundamentou matematicamente os algoritmos genticos. Mesmo no tendo

sido o primeiro a aplicar os conceitos da evoluo natural programao, John Holland foi o

primeiro a provar matematicamente a eficcia da estratgia evolucionria em problemas de

busca. Em seu trabalho, Holland apresenta os algoritmos genticos como uma abstrao dos

processos evolutivos, que permitiriam importar os conceitos de adaptao, evoluo e

seleo natural da vida real para o mundo computacional, a fim de resolver problemas que

envolvem a busca por uma soluo tima (LINDEN, 2006).

4 Heursticas so algoritmos polinomiais que no podem garantir que a soluo encontrada para o problema

proposto a melhor soluo, mas que usualmente tentem a encontrar a soluo tima ou prxima da tima (Linden, 2006).

T:=0 //Inicializamos o contador de tempo Inicializa_Populao P(0) //Inicializamos a populao aleatoriamente Enquanto no terminar faa //Condio de trmino: por tempo, por avaliao, etc.

Avalie_Populao P(t) //Avalie a populao neste instante P:= Selecione_Pais P(t) //Selecionamos sub-populao que gerar nova gerao P = Recombinao_e_mutao P //Aplicamos os operadores genticos Avalie_Populao P //Avalie esta nova populao P(t+1)=Selecione_sobreviventes P(t), P //Selecione sobreviventes desta gerao t:= t+1 //Incrementamos o contador de tempo

Fim enquanto

27

Os algoritmos genticos so uma tcnica heurstica de otimizao global baseada no

processo biolgico da evoluo natural (LINDEN, 2006). O grande diferencial desta tcnica

a sua capacidade de no se restringir a mximos locais, como outros mtodos de otimizao,

explorando o espao de busca como um todo.

A maioria dos algoritmos que tratam problemas de otimizao no so capazes de

encontrar uma soluo tima global, e se restringem a timos locais, como o hill climbing,

que seguem a derivada de uma funo e facilmente se prende a mximos locais,

desprezando o mximo global, como mostrado na figura abaixo. Note que a figura ilustra

que numa tcnica de hill climbing se inicia em qualquer um dos pontos de incio marcados,

seguir a direo de maior crescimento e acabar presa no ponto de mximo local, onde a

derivada zero.

Figura 3.1: Funo hipottica com um mximo local e outro global (LINDEN, 2006).

Um algoritmo gentico fundamentado na tcnica de gerao e teste. Nesta tcnica,

representada pela figura 3.2, uma soluo gerada; testada sua eficcia na resoluo do

problema proposto, considerando limitaes impostas, e se por acaso esta soluo for

adequada resoluo deste problema e obedece s limitaes previamente determinadas,

ela adotada. Se por acaso ela no se adqe as limitaes ou no solucione de maneira

satisfatria o problema proposto, ela desprezada e o processo recomea gerando uma

nova soluo a ser testada.

Figura 3.

A abordagem supracitada

por isso chamada de busca dirigida. Um algoritmo gentico a utilizao da mecnica da

gentica e da seleo natural busca dirigida, encontrando os melhores conjuntos de

parmetros que descrevem uma funo de adaptao (

A fundamentao para a utilizao de algoritmos genticos a problemas de

otimizao est nos conceitos da seleo natural e evoluo das espcies. Segundo esses

conceitos, os indivduos mais adaptados

reproduzirem, enquanto os indivduos menos adaptados morrem antes da reproduo.

Operadores genticos da seleo natural como cruzamento

(crossover), mutao (mutation

sucessivas geraes de solues, so aplicados para se chegar soluo que, se no a tima,

a soluo prxima da tima. Este processo de gerao de populaes atravs de

algoritmos genticos para chegar soluo mais

proposto, utilizando o fitness

Cada um destes operadores gentico

3.1 Funcionamento de um Algoritmo Gentico

Figura 3.2: Modelo da Tcnica de Gerao e Teste

supracitada utiliza sempre um critrio na avaliao destas solues,

de busca dirigida. Um algoritmo gentico a utilizao da mecnica da

seleo natural busca dirigida, encontrando os melhores conjuntos de

em uma funo de adaptao (fitness) (FREITAS, 2001)



conceitos, os indivduos mais adaptados ao seu ambiente vivem tempo o suficiente para se


peradores genticos da seleo natural como cruzamento

mutation) e o uso de uma funo de adaptao

geraes de solues, so aplicados para se chegar soluo que, se no a tima,


algoritmos genticos para chegar soluo mais adequada na resoluo do problema

fitness de um cromossomo, chamado convergncia

ada um destes operadores genticos descrito mais profundamente na subseo seguinte.

Funcionamento de um Algoritmo Gentico

28

utiliza sempre um critrio na avaliao destas solues, e

de busca dirigida. Um algoritmo gentico a utilizao da mecnica da

seleo natural busca dirigida, encontrando os melhores conjuntos de

) (FREITAS, 2001).



ao seu ambiente vivem tempo o suficiente para se


peradores genticos da seleo natural como cruzamento ou recombinao

de adaptao (fitness) para gerar

geraes de solues, so aplicados para se chegar soluo que, se no a tima,


adequada na resoluo do problema

, chamado convergncia (COX, 2005).

s descrito mais profundamente na subseo seguinte.

29

Figura 3.3: Esquema de um algoritmo gentico (LINDEN, 2006)

Como ilustrado no esquema 3.3, um algoritmo gentico gera uma populao inicial

P(N) com N indivduos (cromossomos), que representam possveis solues para o problema

a ser atacado. Cada um desses indivduos P(n) avaliado por uma funo que recebe o nome

de funo de avaliao ou fitness. Quanto mais prximo da soluo tima, ou seja, o quanto

mais adaptado for o indivduo, melhor a avaliao calculada por essa funo para este

indivduo. Aps a anlise de cada um dos indivduos, a populao analisada e verifica-se se

a condio de parada foi satisfeita. Caso a condio de parada no tenha sido satisfeita, K

indivduos da populao so escolhidos para o processo de reproduo, onde so aplicados

os operadores genticos de recombinao (crossover), que gera a partir da combinao de

dois indivduos, como uma analogia a reproduo sexuada, novos indivduos e/ou a mutao

desses indivduos, e os N-K indivduos so descartados. Aps a gerao da nova populao

P(N) o processo refeito. Nas sees seguintes so descritos os aspectos de um algoritmo

gentico.

3.2 Representao Cromossomial (Codificao do Indivduo)

30

Em um algoritmo gentico, cada soluo candidata representada por um indivduo

(cromossomo), que um ponto do espao de busca dentre todas as solues possveis de

um problema (CARVALHO, 2005).

Um cromossomo uma coleo de genomas5 formado por vrios genes (analogia

com um cromossomo biolgico). Cada gene representa um pedao indivisvel da

representao cromossomial (LINDEN, 2006).

Um cromossomo representa uma soluo potencial para o problema a ser abordado

(COX, 2005). A representao cromossomial deve representar adequadamente o problema

em questo, traduzindo suas informaes para pra uma maneira vivel a ser tratada por um

computador. A adaptao destas informaes est fortemente ligada qualidade das

solues obtidas (LINDEN, 2006).

Existem vrias maneiras de representao de cromossomos em um algoritmo

gentico. A escolha de uma representao arbitrria, e deve ser feita a fim de ser a mais

adequada possvel a soluo do problema, e no o contrrio.

A representao mais comumente usada, que tambm a representao proposta

por Holland a representao binria de tamanho fixo, onde cada indivduo formado por

uma cadeia de bits que podem assumir os valores 0 ou 1 (PAPPA, 2002 apud Hinterding

2000). Esta representao possui algumas vantagens: alm de ser uma representao

compacta, facilita os operadores genticos crossover e mutao (COX, 2005). Por outro lado

possui alguns problemas, dentre os quais a dificuldade encontrada para a representao de

valores contnuos a principal. Para representar valores contnuos utilizando a

representao binria, necessria a introduo de transformaes ou discretizaes no

algoritmo gentico, representando um maior custo a sua execuo.

Para a Minerao de Dados a representao cromossomial geralmente uma

seqncia linear de condies de regras, onde usualmente cada condio um par atributo-

valor (CARVALHO, 2005).

5 Um genoma representa uma caracterstica particular em um cromossomo, e sua natureza depende da

representao cromossomial escolhida para o algoritmo gentico.

31

3.3 Funo de Avaliao (Fitness)

A funo de avaliao a maneira utilizada pelos algoritmos genticos para

determinar a qualidade de um indivduo como soluo do problema em questo (LINDEN,

2006). A funo de avaliao e a representao cromossomial esto diretamente ligadas ao

problema a ser abordado caso esses elementos no sejam boas representaes deste

problema a soluo encontrada pode no ser a soluo esperada.

Um AG uma busca dirigida controlada pela funo de avaliao (COX, 2005). Cada

indivduo da populao de solues avaliado segundo esta funo e recebe uma nota. Esta

nota utilizada para a escolha dos indivduos que se reproduziro, atravs de um mtodo de

seleo que favorece a escolha de indivduos melhor avaliados (LINDEN, 2006). O fitness de

um cromossomo depende do quo aquele cromossomo est apto para solucionar o

problema em questo (MITCHELL, 1996).

3.4 Esquemas

Introduzidos por Holland, os esquemas formalizam a existncia de blocos

construtivos (building blocks) em um AG e justificam o seu funcionamento. Esquemas

podem ser descritos como um modelo de 0 e 1 e asteriscos, onde os asteriscos representam

as posies deste modelo onde o valor ali representado no possui relevncia para a soluo

(dont cares) (MITCHELL, 1996). O esquema H = 1 * * * * 1, por exemplo, representa um

modelo de todos os cromossomos que se iniciam e terminam com 1, e possuem tamanho de

6 bits. Indivduos como 1 0 1 0 0 1 ou 1 0 1 1 1 1 so chamados de instncias do esquema H.

Cada esquema representa 2m

cromossomos, onde m o nmero de posies sem

relevncia, os dont care deste esquema. Vale salientar que o valore de 2m cromossomos

representados por um esquema de m posies dont care vlido apenas para um

esquema baseado na representao binria. Para uma populao que possui indivduos de

tamanho k, possui-se apenas 3k esquemas possveis.

Em um AG, um esquema pode ser avaliado utilizando-se a mdia dos fitness dos

indivduos pertencentes ao esquema em questo. O operador de seleo tende a favorecer

32

esquemas que possuem avaliaes acima da mdia, de maneira que a quantidade desses

esquemas cresa de forma exponencial (CASTRO; ZUBEN, 2002 apud MICHALEWICZ, 1996).

Esta afirmao provada pela equao do crescimento reprodutivo do esquema,

representada na figura 3.4.

Figura 3.4: Equao do crescimento reprodutivo do esquema (CASTRO; ZUBEN, 2002).

Seja o esquema Si. representa o nmero de cromossomos representados

pelo esquema Si na gerao t. representa o fitness mdio da populao na gerao t.

As variveis pc e pm representam as probabilidades de ocorrncia de cruzamento e mutao

para o AG em questo, respectivamente e m o tamanho de cada indivduo (tamanho da

cadeia de genes). Nesta equao, considera-se que o AG produz indivduos que possuem

avaliaes positivas (CASTRO; ZUBEN, 2002).

Apenas a seleo no introduz novos esquemas na populao esta uma atribuio

do operador de cruzamento (crossover), que habilita a troca de informao estruturada,

ainda que aleatria (CASTRO; ZUBEN, 2002).

O operador de cruzamento combinado com o operador de seleo pode destruir ou

criar esquemas, porm a probabilidade de um esquema sobreviver ao crossover maior se

esse esquema for pequeno (MITCHELL, 1996). Esse aspecto foi formalizado pelo Teorema

dos Esquemas. Todavia, acredita-se que o operador de cruzamento o principal operador de

um algoritmo gentico, j que recombina instncias de bons esquemas para formar

instncias de esquemas melhores ou igualmente bons aos esquemas anteriores (MITCHELL,

1996). Baseado na afirmao anterior introduz-se outro Teorema o Teorema dos Blocos

Construtivos: um algoritmo gentico busca desempenho quase-timo atravs da

33

justaposio de esquemas curtos, de baixa ordem e alto desempenho, chamados de blocos

construtivos (MITCHELL, 1996 apud GOLDBERG, 1989).

O Teorema dos Esquemas e o Teorema dos Blocos Construtivos tratam dos

operadores de seleo e cruzamento (MITCHELL, 1996). O operador de mutao foi

proposto por Holland, em 1975, para prevenir a baixa diversidade de uma posio de um

esquema, ou seja, evitar casos onde, por exemplo, inicialmente todos os indivduos

comeassem com 1 na primeira posio de sua cadeia de bits a mutao seria o nico meio

de se obter indivduos que possussem o 0 no incio de sua cadeia.

3.5 Operadores Genticos

3.4.1 Seleo de Pais

Este operador seleciona cromossomos da populao para reproduo e favorece os

cromossomos com maior fitness, ou seja, quanto melhor a avaliao do cromossomo, feita

pela a funo de avaliao, mais vezes este cromossomo pode ser selecionado para se

reproduzir (MITCHELL, 1996).

Este mtodo simula o mecanismo de seleo natural, onde os pais mais capazes

geram mais filhos e pais menos aptos podem gerar menos descendentes (LINDEN, 2006).

importante notar que os indivduos menos aptos no podem ser totalmente descartados, a

fim de evitar a convergncia gentica onde os indivduos se tornam cada vez mais

semelhantes, o que destri a diversidade da populao, comprometendo a evoluo.

Existem vrias maneiras de se implementar este mtodo, algumas das quais so

descritas a seguir.

ROLETA

Neste mtodo criada uma roleta, onde cada cromossomo recebe uma parte

proporcional ao seu fitness em relao soma total dos fitness de todos os cromossomos da

populao.

34

Como exemplo, mostrado a seguir uma tabela com alguns indivduos fictcios e a

representao da roleta para estes indivduos:

Tabela 3.1: Grupo de indivduos, seus respectivos fitness e parcela na roleta (LINDEN, 2006)

Indivduo Fitness Pedao da Roleta (%) Pedao da roleta ()

0001 1 1.61 5.8

0011 9 14.51 52.2

0100 16 25.81 92.9

0110 36 58.07 209.1

Total 62 100 360.0

Figura 3.5: Roleta Viciada para a populao exemplo da tabela 3.1 (LINDEN, 2006)

A representao computacional da roleta ilustrada acima dada por um algoritmo

que no permite que haja indivduos com avaliao negativa ou igual a zero, j que nunca

seriam selecionados, pois no possuiriam parcela alguma da roleta. A lgica do algoritmo de

implementao da roleta descrito pela listagem 3.2.

35

Listagem 3.2: Pseudocdigo do mtodo de seleo da roleta (LINDEN, 2006)

TORNEIO

Neste mtodo so selecionados N indivduos da populao. Dentre os indivduos

selecionados, o mais apto selecionado para a reproduo. A quantidade N chamada de

tamanho do torneio, e um parmetro definido pelo usurio. Geralmente quanto maior o

valor de N maior a probabilidade de convergncia gentica, resultante da extino dos

indivduos menos aptos da populao (CARVALHO, 2005).

3.4.2 Recombinao ou Cruzamento (Crossover)

O processo de criao de um novo cromossomo atravs da combinao de um ou

mais cromossomos de alta performance (cromossomo que obteve uma alta nota da funo

de avaliao) conhecido como recombinao ou cruzamento (COX, 2005). A principal

funo deste operador assegurar a troca de material gentico entre dois indivduos

chamados pais, combinando informaes de maneira que haja uma probabilidade razovel

dos indivduos resultantes deste cruzamento sejam melhores que os pais (PAPPA, 2002).

Graas ao operador de recombinao e a funo de avaliao os algoritmos genticos

so classificados como uma busca dirigida, j que utiliza a seleo para determinar as reas

mais promissoras de pesquisa e a recombinao para combin-las de modo a gerar solues

mais aptas para resoluo do problema em questo (LINDEN, 2006).

No cruzamento de um ponto, so selecionados dois pais utilizando um mtodo de

seleo. escolhido, randomicamente, um ponto de corte uma posio entre dois genes

(a) Some todas as avaliaes para uma varivel soma

(b) Ordene todos os indivduos em ordem crescente de avaliao (opcional)

(c) Selecione um nmero s entre 0 e soma (no includos)

(d) i = 1

(e) aux = avaliao do indivduo

(f) enquanto aux < s

(g) i = i + 1

(h) aux = aux + avaliao do indivduo i

(i) fim enquanto

36

de um cromossomo. Ento os pais so separados em duas partes, uma direita e outra

esquerda do ponto de corte. O primeiro filho obtido concatenando-se a parte que se

encontra esquerda do ponto de corte do primeiro pai parte que se encontra direita do

segundo pai. O segundo filho, obtido concatenando-se a parte que se encontra esquerda

do segundo pai parte que se encontra direita do ponto de corte do primeiro pai.

J em outra forma de recombinao chamada crossover uniforme cada gene possui

igual probabilidade P de ser trocado independente de sua posio. O crossover uniforme d

origem a apenas um novo indivduo, enquanto que o crossover de um ponto resulta em dois

novos indivduos.

A recombinao uniforme mais poderosa para algoritmos genticos que utilizam a

representao cromossomial binria, j que criam solues que os outros tipos de

recombinao, como o de um ponto, podem criar, alm de criar combinaes que seriam

impossveis em outros tipos de recombinao. Porm este o tipo de crossover que mais

facilmente quebra esquemas interessantes (LINDEN, 2006). A figura 3.5 ilustra o cruzamento

de um ponto e o cruzamento uniforme.

Figura 3.6: Tipos de cruzamento (crossover) (CARVALHO, 2005)

37

3.4.3 Mutao

Este operador troca randomicamente alguns bits de um cromossomo. Por exemplo, a

seqncia 00000100 poderia ser modificada em sua segunda posio, transformando-se na

seqncia 01000100. A mutao pode ocorrer em cada gene de um cromossomo com uma

probabilidade informada pelo usurio, ou baseada em algum critrio previamente definido.

(MITCHELL, 1996).

O propsito do operador de mutao manter a diversidade da populao e

assegurar que o cromossomo sempre cobrir uma parte suficientemente grande do espao

de busca (PAPPA, 2002 apud Hinterding 2000), introduzindo material gentico que no est

presente em nenhum outro indivduo da populao, ao contrrio do operador de crossover

(CARVALHO, 2005).

A mutao diversifica a populao e combate as regies de mnimos e mximos

locais, assegurando o surgimento de novas solues potenciais, independentes dos

cromossomos j existentes (COX, 2005).

3.6 Elitismo

A cada gerao G de um AG, os indivduos resultantes da gerao G-1 so todos

descartados, dando lugar a novos indivduos resultantes da aplicao dos operadores de

seleo, cruzamento e/ou mutao aos indivduos da gerao G-1.

A estratgia elitista visa preservar indivduos com altos valores de fitness, ou seja, as

melhores solues encontradas na gerao corrente, por mais de uma gerao, copiando-os

para a gerao seguinte (PAPPA, 2002). Seja uma populao com N indivduos. So

escolhidos Nelit indivduos com os melhores fitness. Estes indivduos so copiados

integralmente para a populao da prxima gerao do AG. Os outros N- Nelit indivduos da

nova populao so gerados a partir da aplicao dos operadores genticos citados acima. O

nmero Nelit chamado de fator de elitismo, e um nmero, definido pelo usurio e

geralmente pequeno (CARVALHO, 2005).

38

3.7 Nichos Biolgicos

Simulando o processo evolutivo natural, onde cada espcie evolui em nichos

ecologicamente separados e consomem os recursos oferecidos neste nicho, os mtodos de

niching so utilizados para evitar a convergncia do algoritmo gentico para uma populao

uniforme, com indivduos semelhantes a um super indivduo (uma soluo de alta qualidade)

(CARVALHO; FREITAS, 2002).

A formao de espcies permite primeiramente que vrios disjuntos e diversos

conceitos sejam aprendidos simultaneamente, alm de permitir que os recursos

computacionais sejam efetivamente explorados, evitando replicaes desnecessrias e

redundncias (GIORDANA; NERI, 1995)

Os mtodos de nicho (niching) no permitem que a populao perca a sua

diversidade, habilitando os AGs a localizar diferentes solues com boa qualidade e mant-

las numa mesma subpopulao (CARVALHO, 2005). A fundamentao para a introduo

deste mtodo no AG vem da observao dos ecossistemas biolgicos na natureza, se uma

determinada espcie satura um determinado ambiente, os indivduos daquela espcie so

forados a compartilhar os recursos disponveis, o que nos faz concluir que a necessidade de

compartilhamento uma conseqncia natural de ambiente contendo superpopulaes e

conflitos (CARVALHO, 2005).

As tcnicas de niching so importantes para o sucesso dos AGs aplicados a tarefas

como a classificao, o aprendizado de mquina, a otimizao de funes multimodais, a

otimizao de funes multiobjetivos e simulao de sistemas adaptativos e complexos

(CARVALHO; FREITAS, 2002). A seguir so descritos alguns mtodos de niching, a fim de

ilustrar como esta tcnica introduzida aos algoritmos genticos.

3.6.1 Fitness Sharing

Neste mtodo, a funo de avaliao utilizada para forar a diversidade dos

indivduos. No Fitness Sharing, na avaliao de um indivduo, no considerado apenas o

seu fitness individual, tambm utilizado o fitness de todos os indivduos que esto

prximos no espao de busca (CARVALHO, 2005). O clculo do fitness de um indivduo I para

39

o mtodo de fitness sharing realizado dividindo-se o fitness de I pelo valor de sua

contagem de nicho (niche count). Esta funo de nicho, para cada indivduo I o valor da

soma dos valores da funo de sharing entre ele e cada outro indivduo na populao

(incluindo ele mesmo). A funo de sharing avalia a igualdade entre dois indivduos,

retornando 1 se estes forem idnticos e 0 se eles ultrapassam um limiar de diferena

previamente definido. Os clculos demandados para a implementao deste mtodo o

tornam computacionalmente caro, j que em uma populao com N indivduos, N2 clculos

devem ser feitos para determinar o fitness de um individuo (CARVALHO, 2005). Uma

vantagem deste mtodo a sua capacidade de espalhar a populao em mltiplos nichos.

3.6.2 COGIN (COvered-based Genetic INduction)

O COGIN um sistema de aprendizado que utiliza um mtodo de niching implcito

(CARVALHO; FREITAS, 2002), utilizando um algoritmo de induo de regras baseado na

competio (CARVALHO, 2005).

O COGIN funciona criando novos indivduos (regras) candidatos atravs de

cruzamentos utilizando os indivduos presentes na prpria populao. Este cruzamento

feito utilizando cruzamento de um ponto. Aps a etapa do cruzamento os indivduos so

ordenados de maneira crescente pelo valor p retornado pela funo de avaliao para este

indivduo. Ento tomada a primeira regra (indivduo de maior fitness) e os exemplos do

conjunto de treinamento que atendem a esta regra so escolhidos e eliminados. Este

processo se repete at que o conjunto de treinamento no possua mais nenhum exemplo a

ser coberto, ento as regras restantes so descartadas, j que sua presena na populao de

indivduos desnecessria j que todos os exemplos j foram cobertos pelas regras geradas,

que substituem as regras existentes. Pode-se notar que o tamanho da populao de

indivduos varivel, dependendo exclusivamente da quantidade de regras necessrias para

cobrir todo o espao do conjunto de treinamento, e esta uma grande vantagem deste

mtodo, pois o nmero de regras se adapta dinamicamente aos dados (CARVALHO, 2005

apud GREENE, D.P.; SMITH, S, 1993). A desvantagem deste mtodo a difcil compreenso

do conjunto de regras, pois estas se apresentam a partir de um conjunto de regras

ordenadas (CARVALHO; FREITAS, 2002).

40

3.6.3 REGAL (RElational Genetic Algorithm Learner)

O REGAL um sistema distribudo, baseado em algoritmos genticos, desenvolvido

para aprendizagem de conceitos representados em lgica de primeira ordem a partir de

exemplos (GIORDANA; NERI, 1995). Este sistema baseado num operador de seleo

chamado sufrgio universal (universal suffrage), que tem como funo promover a

coexistncia de diferentes espcies.

O sufrgio universal utiliza uma metfora poltica (FREITAS, 2007) onde os exemplos

da base de treinamento podem votar apenas num indivduo (regra) que os representa. Cada

exemplo pode votar apenas uma vez. Os indivduos mais votados so selecionados para o

cruzamento. Este mtodo descrito com mais detalhes na seo 4.4.

41

4 DESCOBERTA DE REGRAS UTILIZANDO AGs

A utilizao dos algoritmos genticos para a tarefa de descoberta de regras de

previso se deve a busca global realizada por esta abordagem. Outro fator determinante

para a obteno de bons resultados na aplicao de algoritmos genticos a esta tarefa a

boa interatividade com os atributos, que inerente aos processos de seleo e cruzamento

providos pelos algoritmos genticos. Essa interatividade maior que a interatividade

oferecida pelos algoritmos freqentemente utilizados para Data Mining, geralmente

baseados na estratgia gulosa (FREITAS, 2001 apud DHAR V; PROVOST, 2000).

Neste captulo sero discutidos os aspectos e as ferramentas utilizadas no uso de

algoritmos genticos para descoberta de regras de previso no processo de Minerao de

Dados.

4.1 Codificao do Indivduo

Algoritmos genticos para descoberta de regras podem ser divididos em duas

grandes abordagens, que diferem entre si na maneira como elas representam as regras em

um indivduo da populao de solues.

Em geral, existem duas abordagens para a representao de indivduos em um

algoritmo gentico para descoberta de regras: a abordagem de Michigan e a abordagem de

Pittsburgh.

Na abordagem de Michigan, cada indivduo representa uma nica regra, enquanto

que para a abordagem de Pittsburgh, cada individuo representa um conjunto de regras

(FREITAS, 2001). Cada abordagem tem sua aplicao em uma etapa diferente do processo de

Minerao de Dados. A abordagem de Michigan aplicada descoberta de regras de

previso de uma maneira mais natural, pois nesta tarefa a avaliao de cada regra mais

interessante para o sucesso no alcance do objetivo. Se for avaliada cada regra

42

individualmente, ao final do algoritmo gentico as regras que possuem os melhores ndices

de previso sero conhecidas.

Para a tarefa de classificao de dados, a abordagem mais adequada dentre as duas

a de Pittsburgh, j que nesta abordagem, so avaliados os conjuntos de regras. Os melhores

conjuntos avaliados classificaro os dados de maneira mais satisfatria, o que o objetivo

neste momento.

Enquanto a abordagem de Pittsburgh oferece interao entre as regras, a abordagem

de Michigan oferece interao entre os atributos, o que justifica que cada abordagem seja

mais bem aplicada em tarefas diferentes. Os indivduos gerados pela abordagem de

Pittsburgh tendem a terem mais informao e a serem mais complexos (FREITAS, 2001), o

que aumenta o custo computacional para o clculo do fitness. Por outro lado, os indivduos

baseados na abordagem de Michigan so mais simples e menores, o que acelera o

desempenho da funo de avaliao.

Para este trabalho, foi escolhida a representao binria seguindo a abordagem de

Michigan por facilitar a representao das regras e atributos, alm da interao entre cada

um deles durante o processo de execuo do algoritmo.

4.2 Operador de Introduo de Novos Indivduos (Seeding)

O operador de seeding introduz na populao um novo indivduo. O diferencial deste

operador que o novo indivduo gerado cobre um exemplo pertencente a base de

treinamento. Este operador age como uma funo, que, dado um exemplo pertencente a

base de treinamento retorna um indivduo que cobre este exemplo (GIORDANA; NERI,

1995). A listagem 4.1 Descreve o funcionamento deste operador.

Listagem 4.1: Pseudocdigo do operador de seeding (GIORDANA; NERI, 1995).

Seja e um exemplo pertencente ao conjunto de treinamento E Gere uma cadeia aleatria de bits definindo um indivduo K Transforme em 1 o menor nmero de bits em K para que K cubra e Retorne (K)

43

4.3 Funo de Avaliao para Descoberta de Regras de

Classificao

A funo de avaliao deve traduzir o problema a ser resolvido para que possa ser

compreendido e tratado por um computador (LINDEN, 2006). Para a descoberta de regras de

classificao, a funo de avaliao deve ser capaz de medir as seguintes caractersticas: a

acurcia preditiva da regra, ou seja, o poder desta regra de prever comportamentos baseada

nas informaes cedidas pelo conjunto de treinamento; o quanto esta regra compreensvel

ao usurio, pois regras que no so claras ou que so muito complexas sero sumariamente

descartadas pelo usurio; e o quanto esta regra interessante, sendo esta a caracterstica

mais difcil de ser medida, por ser extremamente subjetiva (FREITAS, 2001).

Para um AG que segue a abordagem de Michigan, onde cada indivduo representa

apenas uma regra, seja esta regra representada pela forma SE A ENTO C, onde A

representa a parte antecedente da regra e C a parte conseqente da regra o atributo

objetivo. Uma maneira simples de medir a acurcia preditiva (AC) de uma regra definida

por:

.4 =| ; & =|

| ; | , (4.1)

onde | . | o nmero de exemplos da base de dados que satisfazem todas as condies

antecedentes representadas por A e | . & 4| representada todos os exemplos que

atendem a parte antecedente e conseqente da regra (exemplos que atendem a A e a C)

(FREITAS, 2001). Por exemplo, se uma regra cobre 10 exemplos (| . | = 10), dos quais

apenas 8 possuem o mesmo valor de atributo objetivo (classe) que esta regra (| . & 4| =

8), tem-se que a acurcia preditiva desta regra igual a @

AB= 80 %.

A acurcia preditiva de uma regra de classificao pode ser resumida a uma matriz

2x2 chamada de matriz de confuso. Seu contedo representado a partir de quatro

conceitos que so observados ao utilizarmos uma regra para classificar um exemplo da base

44

de dados a partir da classe que foi prevista pela regra e da classe efetiva deste exemplo, e

so apresentados a seguir:

Verdadeiros Positivos (VP) denota o nmero de exemplos que atendem a

parte antecedente da regra (a parte A) e a parte conseqente da regra (a

parte representada por C);

Falsos Positivos (FP) denota o nmero de exemplos que atendem a parte

antecedente da regra (a parte A) e no atendem a parte conseqente da

regra (a parte representada por C);

Falsos Negativos (FN) denota o nmero de exemplos que no atendem a

parte antecedente da regra (a parte A), porm atendem a parte conseqente

da regra (a parte representada por C);

Verdadeiros Negativos (VN) denota o nmero de exemplos que no

atendem a parte antecedente da regra (a parte A) e no atendem a parte

conseqente da regra (a parte representada por C);

Assim, a forma de uma matriz de confuso apresentada a seguir:

Figura 4.1: Matriz de Confuso para uma Regra de Classificao (FREITAS, 2001).

Outra frmula para medir a acurcia preditiva de cada regra, baseando-se nos

conceitos apresentados acima representada pela frmula:

.4 =| DE|

| DEFGE | , (4.2)

45

Outro conceito importante para a avaliao de regras de classificao o conceito da

completude, que representa o nmero de exemplos da base de dados que possuem o

mesmo valor do atributo objetivo que a regra a ser avaliada e que so cobertos pela regra

antecedente. A completude Comp de uma regra pode ser avaliada atravs da frmula:

4&' =| DE|

| DEFGH | . (4.3)

Tendo em vista que as caractersticas citadas acima, acurcia preditiva e completude,

so as caractersticas desejveis a regras de classificao, podemos ento utilizar a seguinte

funo de avaliao, onde o valor do fitness obtido da seguinte forma:

3%( = .4 $ 4&' , (4.4)

e que foi utilizada para a avaliao das regras neste trabalho.

Vale salientar que, durante a execuo do algoritmo gentico para extrao de regras

de classificao, indivduos que possuem acurcia preditiva de 100% no so interessantes,

por representarem idiossincrasias particulares ao conjunto de dados utilizado para

treinamento das regras. A funo de fitness utilizada neste trabalho no avalia a

simplicidade de uma regra.

4.4 Mtodos para Manter a Diversidade de Regras

Como discutido na seo 3.5, existem alguns mtodos de criao de nichos que visam

manuteno da diversidade entre os indivduos de uma populao em um algoritmo

gentico.

Para a manuteno da diversidade de indivduos em um algoritmo gentico para a

descoberta de regras de classificao, existe ainda outra maneira para se manter a

diversidade das regras, evitando a convergncia para um indivduo: a Cobertura Seqencial

(Sequential Covering). Neste mtodo, a cada execuo do AG apenas uma regra

selecionada a regra com melhor adaptao. Aps a execuo do AG, a regra mais apta

armazenada e todos os exemplos do conjunto de treinamento que so cobertos por esta

regra so descartados. O AG executado n vezes, onde n a quantidade de vezes

46

necessrias para que haja regras suficientes para cobrir todo o conjunto de treinamento, ou

seja, at que o conjunto de treinamento esteja vazio. Portanto, o uso deste mtodo de

seleo implementa uma forma de niching, fomentando a evoluo de diferentes regras que

cobrem diferentes partes da base de dados (FREITAS, 2007). No sufrgio universal, o mtodo

de seleo favorece os indivduos que cobrem mais exemplos, pois eles ocorrem vrias vezes

na roleta, e os indivduos mais adaptados (maior fitness total), pois possuem maior

probabilidade de serem selecionados pela roleta.

Para este trabalho foi utilizado um mtodo baseado em nichos para a manuteno da

diversidade das regras: o sufrgio universal. Este mtodo foi escolhido por evitar a

convergncia da populao em torno de um super-indivduo que foi obtida quando foi

utilizado apenas o mtodo de seleo da roleta. A listagem 4.1 exibe o pseudocdigo do

funcionamento do sufrgio universal.

Listagem 4.2: Pseudocdigo do mtodo de sufrgio universal (GIORDANA; NERI, 1995).

A cada gerao do algoritmo gentico selecionado, de maneira aleatria, um

subconjunto de exemplos do conjunto de treinamento E. Este conjunto de treinamento um

subconjunto da base de dados utilizada para se obter as regras de predio. Esta seleo

realizada com reposio dos exemplos para que, casos onde o nmero de exemplos seja

menor que o nmero de indivduos M da populao (E < M) no haja mais exemplos a serem

escolhidos (GIORDANA; NERI, 1995). Para cada exemplo selecionado, so escolhidos os

candidatos a receberem o voto deste exemplo, ou seja, as regras que cobrem este exemplo

B(t) = 2 Selecione aleatoriamente, com reposio g * M exemplos de E Para cada exemplo K selecionado faa Para cada individuo I da populao faa

Se existe um indivduo que cobre o K ento armazene este indivduo como um candidato Seno crie um novo indivduo que cubra este exemplo e adicione a B(t) Fim Utilize o mtodo da roleta para escolher apenas um indivduo que receber o voto deste exemplo e o adicione a B(t)

Fim

47

e que so agora passveis de serem votados por este exemplo, esses candidatos so

armazenados. Depois de se conhecer e armazenar todos os candidatos, o indivduo votado

escolhido utilizando o mtodo de seleo da roleta, onde selecionado um indivduo a

partir de um subconjunto de indivduos com probabilidade diretamente proporcional a seu

fitness, assim a probabilidade de ser escolhido um indivduo de alto fitness grande, porm

indivduos de baixo fitness no esto totalmente descartados, o que importante para a

manuteno da diversidade da populao de um AG. Apenas os exemplos pertencentes ao

conjunto B(t) so selecionados para cruzamento, e esse aspecto que garante que apenas

formulas que cobrem o mesmo exemplo sejam competidoras entre si. A introduo do

mtodo de seleo da roleta, que escolhe o indivduo que ser votado pelo exemplo, faz

com que a probabilidade de que os exemplos votem nos melhores indivduos seja

proporcional ao fitness dos indivduos que cobrem estes exemplos. A funo de fitness a ser

utilizada no precisa necessariamente levar em considerao a completude de cada regra, j

que apenas indivduos que cobrem pelo menos um exemplo so selecionados quando

utilizado o operador de seleo sufrgio universal (RAS; ZEMANKOVA, 1994), j que estes

indivduos devem ser votados por pelo menos um exemplo. Porm, para este trabalho foi

considerada a completude de uma regra na funo de fitness para que regras que cubram

mais exemplos que outras tenham maior probabilidade de serem votadas.

4.5 Operador de Cruzamento (Crossover)

O operador de cruzamento utilizado para este trabalho foi o crossover uniforme. Este

tipo de crossover foi escolhido por ser capaz de combinar todo e qualquer esquema

existente na populao (LINDEN, 2006).

Existe tambm outro tipo de crossover especfico para a tarefa de descoberta de

regras de classificao: o crossover de generalizao/especializao

(generalizing/specializing crossover). A idia bsica deste operador generalizar ou

especializar uma dada regra, ou seja, aumentar o nmero de exemplos que so cobertos

pela regra se este nmero for considerado pequeno, ou aumentar o nmero de exemplos

que so cobertos por esta regra se este for considerado grande.

Como exemplo, consideremos que um algoritmo evolucionrio, seguindo a

codificao de Michigan. Ento, o

implementado como o OU lgico ou o E lgico (FREITAS, 2001), respectivamente, como

mostrado na figura 4.2.

Figura 4.2: Exemplo de

4.6 Operador de Generalizao e Especializao

A generalizao ou especializao de regras pode tambm ser realizada por um

operador independente do operador de cruzamento, chamado operador de

generalizao/especializao.

Para ilustrar o uso deste operador, consideremos a seguinte regra

so ligadas por um E lgico (FREITAS, 2001)

Esta regra pode ser

25, assim em 4.5 haver uma cobertura de mais exemplos. Um exemplo pode ser ilustrado

atravs em 4.6 (FREITAS, 2001):

Outra maneira de generaliza

Para realizar a especializao de uma regra, pode

diminuiria o intervalo coberto e assim o nmero de exemplos cobertos por este indivduo.

Para este trabalho este o

garantida pela funo de avaliao e pelo mtodo de sufrgio universal.


. Ento, o crossover de generalizao/especializao pode ser


Exemplo de crossover de generalizao/especializao (FREITAS, 2001)

Generalizao e Especializao



generalizao/especializao.

ilustrar o uso deste operador, consideremos a seguinte regra

so ligadas por um E lgico (FREITAS, 2001):

> 25 %I J K = %

Esta regra pode ser generalizada, utilizando a mutao para subtrair certo valor de


atravs em 4.6 (FREITAS, 2001):

> 21 %I J K = %

Outra maneira de generalizar uma regra apagar alguma das condies desta regra.

Para realizar a especializao de uma regra, pode-se adicionar certo valor a 25, assim


Para este trabalho este operador no foi utilizado e a cobertura dos exemplos


48


de generalizao/especializao pode ser


(FREITAS, 2001)



ilustrar o uso deste operador, consideremos a seguinte regra, onde as condies

(4.5)

subtrair certo valor de


(4.6)

r uma regra apagar alguma das condies desta regra.

se adicionar certo valor a 25, assim


perador no foi utilizado e a cobertura dos exemplos


49

5 IMPLEMENTAO

O presente captulo descreve e discute o algoritmo implementado, baseado em

tcnicas da Programao Gentica, para a ferramenta EPT - Explorer Patterns Tool,

ferramenta de Minerao de Dados desenvolvida neste trabalho. Esta ferramenta a

resultante da incorporao de algoritmos genticos para extrao de regras de predio

ferramenta EFT (Explorer Fuzzy Tree). A ferramenta EFT foi desenvolvida em SOUZA, 2008

para oferecer ao seu usurio parmetros de experimentao que permitam aumentar o

poder preditivo da rvore clssica atravs da sua fuzzyficao (SOUZA, 2008).

O EPT oferece um ambiente de experimentos com algoritmos de classificao

baseados em rvores de deciso nebulosas e clssicas sobre qualquer base de dados com

atributos contnuos (SOUZA, 2008) assim como experimentos com algoritmos genticos para

extrao de regras de predio sobre qualquer base de dados com atributos contnuos ou

categricos, alm de um ambiente onde possvel comparar esses dois paradigmas

utilizados

Documents

Monografia-Joilma Souza Algoritmos Genéticos