MINERAÇÃO DE DADOS UTILIZANDO ALGORITMOS GENÉTICOS Joilma Souza Santos Orientadora: Profª....

MINERAÇÃO DE DADOS UTILIZANDO ALGORITMOS

GENÉTICOSJoilma Souza Santos

Orientadora: Profª. Daniela Barreiro Claro Salvador – Bahia

2008

1

ROTEIRO DA APRESENTAÇÃO

IntroduçãoMineração de DadosAlgoritmos GenéticosO Explorer Patterns ToolsExperimentos e ResultadosConclusão e Trabalhos Futuros

2

INTRODUÇÃO

3

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

Utilização prática de bases de dados Fases do Processo de KDD

Aplicação de algoritmos para extração de conhecimento a partir de bases de dados

Utilização de algoritmos genéticos no processo de KDD

Motivação para utilização desta técnica

4

INTRODUÇÃO

MINERAÇÃO DE DADOS - ROTEIRO Introdução Mineração de Dados

o Técnicas de Mineração de Dadoso Utilização de Algoritmos Genéticos no processo de KDD

Algoritmos Genéticos O Explorer Patterns Tools Experimentos e Resultados Conclusão e Trabalhos Futuros

5

TÉCNICAS PARA MINERAÇÃO DE DADOS - REGRAS DE CLASSIFICAÇÃO

6Exemplo de Classificação (CARVALHO, 2005)

7

TÉCNICAS PARA MINERAÇÃO DE DADOS - CLUSTERIZAÇÃO

Exemplo de dados organizados em clusters (CARVALHO, 2005)

8

TÉCNICAS PARA MINERAÇÃO DE DADOS – REGRAS DE ASSOCIAÇÃO

ALGORITMOS GENÉTICOS - ROTEIRO Introdução Mineração de Dados

Técnicas de Mineração de Dados Utilização de Algoritmos Genéticos no processo de KDD

Algoritmos Genéticoso Aspectos de um Algoritmo Genético

O Explorer Patterns Tools Experimentos e Resultados Conclusão e Trabalhos Futuros

9

ASPECTOS DE UM ALGORITMO GENÉTICO

Método baseado nos princípios da seleção natural e evolução das espécies;

Heurística de otimização global; Baseado na técnica de geração e teste;

10

ASPECTOS DE UM ALGORITMO GENÉTICO

11

Esquema de um algoritmo genético (LINDEN, 2006)

ASPECTOS DE UM ALGORITMO GENÉTICO Representação Cromossomial

Diversas maneiras de representação: Binária: (1 0 1 0 0 1 0) Números Reais: (4.6 5.9 2.0 8.6) Lista de Regras: (R1 R2 R3 ... Rn)

Nichos Biológicos Elitismo Função de Avaliação (Função de Fitness)

Determina a qualidade de um indivíduo como solução do problema em questão (LINDEN, 2006)

Um Algoritmo Genético é uma busca dirigida controlada pela função de avaliação 12

OPERADORES GENÉTICOS - SELEÇÃO Torneio Roleta

É criada uma roleta, onde cada cromossomo recebe uma parte proporcional ao seu fitness em relação à soma total dos fitness de todos os cromossomos da população.

13

Grupo de indivíduos e seus respectivos fitness e parcela na roleta (LINDEN, 2006)

Indivíd

uo

Fitn

ess

Pedaço da

Roleta (%)

Pedaço 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.0Roleta Viciada para a população exemplo da tabela 3.1 (LINDEN, 2006)

OPERADORES GENÉTICOS - RECOMBINAÇÃO OU CRUZAMENTO (CROSSOVER)

14 Tipos de cruzamento (crossover) (CARVALHO, 2005)

1 0 0 1 1 0 1 1

15

OPERADORES GENÉTICOS - MUTAÇÃO

1 0 0 1 1 0 1 1

16

OPERADORES GENÉTICOS - MUTAÇÃO

1 0 0 0 1 0 1 1

17

OPERADORES GENÉTICOS - MUTAÇÃO

ALGORITMOS GENÉTICOS - ROTEIRO Introdução Mineração de Dados

Técnicas de Mineração de Dados Utilização de Algoritmos Genéticos no processo de

KDD Algoritmos Genéticos

Operadores Genéticos O Explorer Patterns Tools

Aspectos da Implementação Experimentos e Resultados Conclusão e Trabalhos Futuros

18

ALGORITMO DESENVOLVIDO Inicialização da População

Operador de Seeding Elitismo Seleção de Pais

Criação de nichos utilizando o operador sufrágio universal (universal suffrage)

Cruzamento Cruzamento Uniforme (universal crossover)

Mutação Probabilidade de mutação utilizada: 1/(tam. cadeia

cromossômica) Função de Avaliação (Cálculo do Fitness do Indivíduo)

19

INICIALIZAÇÃO DA POPULAÇÃO

Seja e um exemplo pertencente ao conjunto de treinamento EGere uma cadeia aleatória de bits definindo um indivíduo KTransforme em 1 o menor número de bits em K para que K cubra eRetorne (K)

20

ELITISMO

Nelit = 1 (o cromossomo de maior fitness é integralmente copiado para a próxima população)

21

B(t) = Selecione aleatoriamente, com reposição g * M exemplos de EPara cada exemplo K selecionado faça

Para cada individuo I da população faça Se existe um indivíduo que cobre o K então armazene este indivíduo como um candidato Senão crie um novo indivíduo que cubra este exemplo e adicione a B(t)FimUtilize o método da roleta para escolher apenas um indivíduo que receberá o voto deste exemplo e o adicione a B(t)

Fim

SELEÇÃO DE PAIS Sufrágio Universal (Universal Suffrage)

22

Verdadeiros Positivos (VP) Falsos Positivos (FP) Falsos Negativos (FN) Verdadeiros Negativos (VN) Acurácia

23

Figura 4.1 - Matriz de Confusão para uma Regra de Classificação (FREITAS, 2001).

FUNÇÃO DE AVALIAÇÃO

FUNÇÃO DE AVALIAÇÃO Função de Fitness

onde,

e

24

ALGORITMOS GENÉTICOS - ROTEIRO Introdução Mineração de Dados

Técnicas de Mineração de Dados Utilização de Algoritmos Genéticos no processo de KDD

Algoritmos Genéticos Aspectos de um Algoritmo Genético;

O Explorer Patterns Tools Aspectos da Implementação;

Experimentos e Resultados Bases de Dados Utilizadas Aspectos dos Experimentos Resultados

Conclusão e Trabalhos Futuros 25

BASES DE DADOS UTILIZADAS

26

Informações sobre os conjuntos de dados (SOUZA, 2008)

Conjuntos de Dados Domínio Classes Atributos de entrada Qtde. de instâncias

SPAMBASE Comercial 2 57 4601

Segment-challenge Comercial 7 19 1500

Segment-test Comercial 7 19 810

Iris Biológico 3 4 150

ALGORITMOS GENÉTICOS - ROTEIRO Introdução Mineração de Dados

Técnicas de Mineração de Dados Utilização de Algoritmos Genéticos no processo de KDD

Algoritmos Genéticos Operadores Genéticos

O Explorer Patterns Tools Aspectos da Implementação

Experimentos e Resultados Bases de Dados Utilizadas Aspectos dos Experimentos Resultados

Conclusão e Trabalhos Futuros 27

DESCRIÇÃO DOS EXPERIMENTOS

Experimento 1 – Comparação entre as acurácias do algoritmo implementado e das árvores clássicas/fuzzy

300 execuções do algoritmo; 60% da base de dados utilizada para treinar o algoritmo

utilizando o método de divisão por porcentagem; 10 folds quando utilizada a validação cruzada;

Experimento 2 – Estudo do aumento de gerações X taxas de acurácia

Validação cruzada com 10 folds;28

RESULTADOS – EXPERIMENTO 1

Resultados Obtidos para o Algoritmo Genético Implementado – Média Aritmética dos Resultados Obtidos

Conjuntos de Dados Precisão das Regras Taxa de VP Acurácia

SPAMBASE 0,629 0,260 0,520

Segment-challenge 0,369 0,397 0,820

Segment-test 0,383 0,408 0,830

Iris 0,611 0,596 0,726

29

RESULTADOS – EXPERIMENTO 2

ALGORITMOS GENÉTICOS - ROTEIRO Introdução Mineração de Dados

Técnicas de Mineração de Dados Utilização de Algoritmos Genéticos no processo de KDD

Algoritmos Genéticos Aspectos de um Algoritmo Genético;

O Explorer Patterns Tools Aspectos da Implementação;

Experimentos e Resultados Bases de Dados; Aspectos dos Experimentos;

Conclusão e Trabalhos Futuros31

CONCLUSÃO

32

Visão Geral

O algoritmo implementado

Resultados Obtidos

TRABALHOS FUTUROS

33

A implementação de um outro algoritmo genético que utilize operadores diferentes dos utilizados pelo algoritmo desenvolvido neste trabalho;

A Implementação de métodos de seleção de atributos para diminuir o tempo de execução dos algoritmos implementados;

Utilização de outras técnicas de mineração de dados diferentes da classificação.

MINERAÇÃO DE DADOS UTILIZANDO ALGORITMOS

GENÉTICOSJoilma Souza Santos

E-mail: joilma@dcc.ufba.br

Salvador – Bahia2008

34