[pt] Esta dissertação investiga a utilização de Algoritmos
Genéticos (AG) no processo de descoberta de conhecimento
implícito em Banco de Dados (KDD - Knowledge Discovery
Database). O objetivo do trabalho foi avaliar o desempenho
de Algoritmos Genéticos no processo de classificação de
registros em Bancos de Dados (BD). O processo de
classificação no contexto de Algoritmos Genéticos consiste
na evolução de regras de associação que melhor
caracterizem, através de sua acurácia e abrangência, um
determinado grupo de registros do BD. O trabalho consistiu
de 4 etapas principais: um estudo sobre a área de
Knowledge Discovery Database (KDD); a definição de um
modelo de AG aplicado à Mineração de Dados (Data Mining);
a implementação de uma ferramenta (Rule-Evolver) de
Mineração de Dados; e o estudo de casos.
O estudo sobre a área de KDD envolveu todo o processo de
descoberta de conhecimento útil em banco de dados:
definição do problema; seleção dos dados; limpeza dos
dados; pré-processamento dos dados; codificação dos dados;
enriquecimento dos dados; mineração dos dados e a
interpretação dos resultados. Em particular, o estudo
destacou a fase de Mineração de Dados e os algoritmos e
técnicas empregadas (Redes Neurais, Indução de regras,
Modelos Estatísticos e Algoritmos Genéticos). Deste estudo
resultou um survey sobre os principais projetos de
pesquisa na área.
A modelagem do Algoritmo Genético consistiu
fundamentalmente na definição de uma representação dos
cromossomas, da função de avaliação e dos operadores
genéticos. Em mineração de dados por regras de associação
é necessário considerar-se atributos quantitativos e
categóricos. Atributos quantitativos representam variáveis
contínuas (faixa de valores) e atributos categóricos
variáveis discretas. Na representação definida, cada
cromossoma representa uma regra e cada gene corresponde a
um atributo do BD, que pode ser quantitativo ou categórico
conforme a aplicação. A função de avaliação associa um
valor numérico à regra encontrada, refletindo assim uma
medida da qualidade desta solução. A Mineração de Dados
por AG é um problema de otimização onde a função de
avaliação deve apontar para as melhores regras de
associação. A acurácia e a abrangência são medidas de
desempenho e, em alguns casos, se mantém nulas durante
parte da evolução. Assim, a função de avaliação deve ser
uma medida que destaca cromossomas contendo regras
promissoras em apresentar acurácia e abrangência
diferentes de zero. Foram implementadas 10 funções de
avaliação. Os operadores genéticos utilizados (crossover e
mutação) buscam recombinar as cláusulas das regras, de
modo a procurar obter novas regras com maior acurácia e
abrangência dentre as já encontradas. Foram implementados
e testados 4 operadores de cruzamento e 2 de mutação.
A implementação de uma ferramenta de modelagem de AG
aplicada à Mineração de Dados, denominada Rule-Evolver,
avaliou o modelo proposto para o problema de classificação
de registros. O Rule-Evolver analisa um Banco de Dados e
extrai as regras de associação que melhor diferenciem um
grupo de registros em relação a todos os registros do
Banco de Dados. Suas características principais são:
seleção de atributos do BD; informações estatísticas dos
atributos; escolha de uma função de avaliação entre as 10
implementadas; escolha dos operadores genéticos;
visualização gráfica de desempenho do sistema; e
interpretação de regras. Um operador genético é escolhido
a cada reprodução em função de uma taxa preestabelecida
pelo usuário. Esta taxa pode permanecer fixa ou variar
durante o processo evolutivo. As funções de avaliação
também podem ser alteradas (acrescidas de uma recompensa)
em função da abrangência e da acurácia da regra. O Rule-
Evolver possui uma interface entre o BD e o AG, necessária
para tor / [en] This dissertation investigates the application of Genetic
Algorithms (GAs) to the process of implicit knowledge
discovery over databases (KDD - Knowledge Discovery
Database). The objective of the work has been the
assessment of the Genetic Algorithms (GA) performance in
the classification process of database registers. In the
context of Genetic Algorithms, this classification process
consists in the evolution of association rules that
characterise, through its accuracy and range, a particular
group of database registers. This work has encompassed
four main steps: a study over the area of Knowledge
Discovery Databases; the GA model definition applied to
Data Mining; the implementation of the Data Mining Rule
Evolver; and the case studies.
The study over the KDD area included the overall process
of useful knowledge discovery; the problem definition;
data organisation; data pre-processing; data encoding;
data improvement; data mining; and results´
interpretation. Particularly, the investigation emphasied
the data mining procedure, techniques and algorithms
(neural Networks, rule Induction, Statistics Models and
Genetic Algorithms). A survey over the mais research
projects in this area was developed from this work.
The Genetic Algorithm modelling encompassed fundamentally,
the definition of the chromosome representation, the
fitness evaluation function and the genetic operators.
Quantitative and categorical attributes must be taken into
account within data mining through association rules.
Quantitative attribites represent continuous variables
(range of values), whereas categorical attributes are
discrete variable. In the representation employed in this
work, each chromosome represents a rule and each gene
corresponds to a database attribute, which can be
quantitative or categorical, depending on the application.
The evaluation function associates a numerical value to
the discovered rule, reflecting, therefore, the fitness
evaluation function should drive the process towards the
best association rules. The accuracy and range are
performance statistics and, in some cases, their values
stay nil during part of the evolutionary process.
Therefore, the fitness evaluation function should reward
chromosomes containing promising rules, which present
accuracy and range different of zero. Ten fitness
evaluation functions have been implemented. The genetic
operators used in this work, crossover and mutation, seek
to recombine rules´clauses in such a way to achieve rules
of more accuracy and broader range when comparing the ones
already sampled. Four splicing operators and two mutation
operators have been experimented.
The GA modeling tool implementation applied to Data Mining
called Rule Evolever, evaluated the proposed model to the
problem of register classification. The Rule Evolver
analyses the database and extracts association rules that
can better differentiate a group of registers comparing to
the overall database registers. Its main features are:
database attributes selection; attributes statistical
information; evaluation function selection among ten
implemented ones; genetic operators selection; graphical
visualization of the system performance; and rules
interpretation. A particular genetic operator is selected
at each reproduction step, according to a previously
defined rate set by the user. This rate may be kept fix or
may very along the evolutionary process. The evolutionary
process. The evaluation functions may also be changed (a
rewarding may be included) according to the rule´s range
and accuracy. The Rule Evolver implements as interface
between the database and the GA, endowing the KDD process
and the Data Mining phase with flexibility. In order to
optimise the rules´ search process and to achieve better
quality rules, some evolutionary techniques have been
implemented (linear rank and elitism), and different
random initialisation methods have been used as well;
global averag
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:7297 |
| Date | 19 October 2005 |
| Creators | CARLOS HENRIQUE PEREIRA LOPES |
| Contributors | MARLEY MARIA BERNARDES REBUZZI VELLASCO, MARCO AURÉLIO CAVALCANTI PACHECO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0031 seconds