Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos Autores: Pontifícia Universidade Católica do Rio de Janeiro Marco A. C. Pacheco Marley M. R. Vellasco Carlos H. P. Lopes Emmanuel P. L. Passos Apresentação: Universidade Federal do Pará Luiz Daniel Creão Augusto Priscila Corrêa Saboia Dezembro de 2004 Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos Roteiro 1. Introdução 2. Algoritmos Genéticos em Mineração de Dados 3. O modelo de AG 4. A ferramenta Rule-Evolver 5. Estudo de Caso: Iris Plant DB 6. Estudo de Caso: Tic-Tac-Toe Endgame DB 7. Considerações Finais Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 1. Introdução Proposta do artigo Apresentar um modelo genético e uma ferramenta (Rule-Evolver) para a geração de regras de classificação de registros em Bancos de Dados (BD). Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 1. Introdução – AG’s Algoritmos Genéticos: Idéia Algoritmos de busca e otimização baseados nos princípios biológicos da seleção natural e da recombinação gênica. O funcionamento é baseado na sobrevivência e recombinação dos indivíduos mais aptos no decorrer de uma série de gerações. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 1. Introdução – AG’s Funcionamento básico 1. Inicialmente é gerada uma população formada por um conjunto aleatório de indivíduos que podem ser vistos como possíveis soluções do problema. 2. Durante o processo evolutivo, a população é avaliada. Para cada indivíduo é dada uma nota, ou índice, refletindo sua habilidade de adaptação a determinado ambiente. 3. Uma porcentagem dos mais adaptados é mantida, enquanto os outros são descartados. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 1. Introdução – AG’s Funcionamento básico 1. Os membros mantidos pela seleção podem sofrer modificações em suas características fundamentais por meio de mutações e cruzamento ou recombinação genética gerando descendentes para a próxima geração. 2. Esse processo é repetido até que uma solução satisfatória seja encontrada (normalmente número máximo de gerações ou solução satisfatória). Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 1. Introdução – AG’s Fluxo básico de um AG Início t = 0; Iniciar P(t); Avaliar P(t); Enquanto (Condição de parada não for satisfeita) Faça Início Selecionar P(t +1) de P(t); Aplicar Cruzamento em P(t +1); Aplicar Mutação em P(t +1); Avaliar P(t +1); t = t +1; Fim Fim Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 2. AG’s em Mineração de Dados Classificação com AG’s A classificação no contexto de Algoritmos Genéticos consiste na evolução de regras de associação da forma SE-ENTÃO, de alta acurácia e abrangência. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 2. AG’s em Mineração de Dados Medição de qualidade das soluções encontradas Para medir a qualidade das soluções encontradas defini-se acurária e abrangência de uma regra. Considere C um conjunto de atributos preditivos (condição da regra) e P, a previsão, ou classe do registro. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 2. AG’s em Mineração de Dados Qualidade das soluções encontradas A acurácia de uma regra de associação da forma SE C ENTÃO P mede o grau de confiança da regra. A abrangência de uma regra pode ser interpretada como a cobertura de registros da classe P que satisfazem a regra. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 3. O Modelo de AG A modelagem de um algoritmo genético consiste da definição de 4 componentes principais: • Representação do cromossoma – estrutura de dados que representa uma solução do problema; • Avaliação – medida da qualidade de uma determinada solução; • Operadores genéticos – atuam no processo de reprodução criando e/ou alterando indivíduos; • Inicialização da população – método que determina a população inicial. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 3. O Modelo de AG Representação do cromossomo Um cromossomo deve ser capaz de representar uma regra de associação através da faixa de valores dos atributos preditivos, categóricos ou quantitativos. No cromossomo proposto, um gene representa um atributo preditivo. Cada gene tem uma faixa de valores por atributo: os números reais, os valores mínimo e máximo Vantagem: Fácil interpretação da regra através da visualização na forma de intervalo. Desvantagem: Requer evolução de dois valoresnúmeros reais para a faixa de cada atributo. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 3. O Modelo de AG Representação do cromossomo Onde mín X e máx X indicam os valores mínimos e máximos da faixa de valores de cada atributo preditivo definido como quantitativo (para atributos categóricos, somente mín é usado); P é o valor do Atributo Objetivo, informado como meta no início do processo, não fazendo parte do cromossomo SE [ (Atributo 1 >= mín 1) e (Atributo 1 <= máx 1) e (Atributo 2 >= mín 2) e (Atributo 2 <= máx 2) e ... e (Atributo N >= mín N) e (Atributo N <= máx N) ] ENTÃO Atributo Objetivo = P Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 3. O Modelo de AG Avaliação Cálculo da Avaliação Geral da Regra • Não é baseada somente na avaliação da regra • Prevê 3 tipos de recompensas: acurácia, abrangência ou ambas. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 3. O Modelo de AG Avaliação Cbayesianos • Uma possível função de avaliação f(i) • É inspirada em classificadores bayesianos, representa o produto das probabilidades dos valores dos atributos de uma regra pertencerem a um intervalo, dado que a classe do registro corrente é a especificada como objetivo. P(A1 = a1|C = c) * P(A2 = a2|C = c) *...* P(Ak = ak|C = c) Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 3. O Modelo de AG Operadores Genéticos – Cruzamento crossover de 1 e 2 pontos crossover de média aritmética crossover uniforme Operadores Genéticos – Mutação Mutação simples (troca aleatória de informação) Um novo operador de mutação denominado don’t care. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 3. O Modelo de AG Inicialização da população Estudo de formas de inicializar o AG com restrições de espaço de busca ou com soluções promissoras Métodos de inicialização sem sementes: – consistem em estabelecer os limites mín e máx na faixa relevante à classe, incluindo o valor médio ou mediano desses atributos. Métodos de inicialização com sementes: – utilizam material genético já evoluído em experimentos anteriores ou informações da própria base de dados. – Desse modo o modelo já inicia a busca por regras em áreas mais promissoras. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 4. O Rule-Evolver O Rule Evolver foi a ferramenta desenvolvida para avaliação do modelo proposto, sendo capaz de extrair regras de associação para a base dada. Módulos do Rule-Evolver – – – – Seleção de Atributos do BD Interpretação Visualização Gráfica Parametrização do Ambiente Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 4. O Rule-Evolver: Módulos Seleção de Atributos do BD permite ao usuário a escolha dos atributos da base que serão considerados pelas regras geradas; Interpretação apresenta as melhores regras na forma: SE (A1 e A2 e ... An) ENTÃO P; Visualização Gráfica apresenta gráficos de acurácia, abrangência e aptidão durante a evolução genética; Parametrização do Ambiente permite o usuário a customização de taxas, parâmetros, função de avaliação, operadores e técnicas evolucionárias. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 5. Estudo de Caso: Iris Plant DB 150 registros em 3 classes: Setosa, Versicolour e Virginica Atributos: largura e comprimento da pétala e da sépala Dois grupos: 25 registros/classe para teste e treinamento Erros: 3 classificados errados e 7 não classificados Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 6. Estudo de Caso: Tic-Tac-Toe Configurações do jogo para 'x' ganhar, tendo começado 958 registros (x ganha 626) com diferentes 'tabuleiros' 70% treinamento, 30% teste (dos 626 – vencer ou não) Erros: 4 classificações erradas e 3 não classificados Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 7. Considerações Finais A Classificação de Registros através da evolução de regras de associação por Algoritmos Genéticos, ainda que tenham apresentado erros acima de outros métodos, é um técnica bastante promissora. A grande vantagem de se extrair regras por AG é que elas são facilmente entendidas, mesmo para um usuário. O modelo genético é capaz de gerar regras de alta precisão e abrangência, e sem conflitos para os intervalos presentes no treinamento. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia Extração de Regras de Associação em Bases de Dados por Algoritmos Genéticos 7. Considerações Finais O modelo ainda é um pouco deficiente na geração de regras suficientemente genéricas durante a fase de treinamento que sejam altamente precisas nos testes. Possível solução: variação de mutação (Creep) que estenda a faixa de valores de um atributo até antes de valores que o classificariam como outra classe. Tempo de Execução do Rule-Evolver: 6 minutos em um Pentium II 350MHz para avaliar 80 gerações de 100 indivíduos. Luiz Daniel Creão Augusto e Priscila Corrêa Saboia