Governo Federal

Dados do Trabalhos de Conclusão

UNIVERSIDADE FEDERAL DO PARANÁ
MÉTODOS NUMÉRICOS EM ENGENHARIA (40001016030P0)
Extração de Regras de Classificação de Bases de Dados por meio de Procedimentos Meta-Heurísticos Baseados em GRASP
GENIVAL PAVANELLI
TESE
28/05/2014

O processo de gestão do conhecimento nas mais diversas áreas – seja em indústrias, hospitais, escolas, bancos, dentre outros – exige constante atenção à multiplicidade de decisões a serem tomadas acerca de suas atividades. Para a tomada de decisões, faz-se necessária a utilização de técnicas científicas que lhes garantam a máxima acurácia. O presente trabalho faz o uso de ferramentas matemáticas que cumpram a finalidade de extração de conhecimento de base de dados. O objetivo é a proposição de uma nova meta-heurística, baseada no procedimento GRASP (Greedy Randomized Adaptive Search Procedure) como ferramenta de Data Mining (DM), no contexto do processo denominado Knowledge Discovery in Databases (KDD) para a tarefa de extração de regras de classificação em bases de dados. Assim, a metodologia aqui proposta possui três grandes blocos segundo o processo KDD: pré-processamento dos dados, no qual todos os atributos previsores são codificados de maneira a corresponder a uma ou mais coordenadas binárias; aplicação da meta-heurística propriamente dita para extração de regras de classificação; construção do classificador, momento em que as regras extraídas são ordenadas segundo critérios baseados no “fator de suporte” e na “confiança”. A fim de validar esta proposta, a metodologia foi implementada e aplicada a sete bases de dados distintas, com um número variável de instâncias, de atributos e de classes. Os resultados obtidos apresentam elevada precisão preditiva, atingindo, por exemplo, 98% de acurácia para a base de dados zoo, 97% para a base íris e 94% para a base wine. Buscando ratificar os resultados obtidos, foram estabelecidas comparações entre a meta-heurística aqui proposta e os algoritmos BFTree, RepTree e J4.8, todos de árvore de decisão. A partir destas comparações, observa-se que em seis das sete bases analisadas a proposta implementada é superior, em termos de acurácia, aos algoritmos de árvore de decisão utilizados. Desta forma, conclui-se que a metaheurística proposta atende os pré-requisitos para a tarefa de extração de conhecimento de base de dados.

Greedy Randomized Adaptive Search Procedure. Data Mining. Extração de Regras
The process of knowledge management in several areas – existing in industries, hospitals, schools, banks, among others - requires constant attention to the multiplicity of decisions to be made about their activities. In order to make decisions, it is necessary to use scientific techniques that will ensure their maximum accuracy. This study makes use of mathematical tools that meet the purpose of extracting knowledge from a database. The aim is to propose a new metaheuristic based on GRASP (Greedy Randomized Adaptive Search Procedure) procedure as a tool of Data Mining (DM) within the context of the process called Knowledge Discovery in Databases (KDD) for the task of extracting classification rules in databases. Thus, the methodology proposed herein has three large blocks according to the KDD process: data pre-processing, in which all predictor attributes are encoded to correspond to one or more binary coordinates; application of the metaheuristic itself for extracting classification rules; construction of the classifier, when the extracted rules are ordered in accordance with criteria based on "support factor" and "trust." In order to validate this proposal, the methodology has been implemented and applied to seven different databases, with a variable number of instances, attributes and classes. The results show high predictive accuracy, reaching, for example, 98% accuracy in the zoo database, 97% for the iris base and 94% for the wine base. Seeking to ratify the results, comparisons between the metaheuristic proposed herein and BFTree, RepTree and J4.8 decision tree algorithms were established. Based on these comparisons, it is observed that in six out of seven analyzed bases the implemented proposal is superior, in terms of accuracy, to the used decision tree algorithms. In this way, it is concluded that the meta-heuristic proposed meets the prerequisites for the task of extracting knowledge from a database.
Greedy Randomized Adaptive Search Procedure. Data Mining. Rule Extraction
1
132
PORTUGUES
UNIVERSIDADE FEDERAL DO PARANÁ

Contexto

PROGRAMAÇÃO MATEMÁTICA
ABORDAGEM DE PROBLEMAS DE OTIMIZAÇÃO E DE ANÁLISE NUMÉRICA
-

Banca Examinadora

MARIA TERESINHA ARNS STEINER
Sim
Nome Categoria
ANDERSON ROGES TEIXEIRA GOES Participante Externo
CASSIUS TADEU SCARPIN Docente
JULIO CESAR NIEVOLA Participante Externo
DEISE MARIA BERTHOLDI COSTA Docente

Vínculo

Servidor Público
Empresa Pública ou Estatal
Ensino e Pesquisa
Não