Boosting e estratégias evolucionárias na tarefa de regressão para a mineração de dados temporais

Abstract

Resumo: O aumento no volume de dados armazenados contribui para o crescimento da expectativa de obter informações implícitas que possam auxiliar em decisões futuras. A extração de padrão nos dados que possuem alguma dimensão de tempo é tarefa da Mineração de Dados Temporais. Quando os atributos têm características numéricas, os padrões podem ser descobertos por meio da regressão, a qual constrói modelos que mapeiam variáveis de entrada x = {x1...xn} para uma variável de saída y. Para determinar modelos (equações) lineares na regressão, convém que a técnica utilizada seja capaz de manipular variáveis contínuas. Diferentes técnicas podem ser utilizadas na Mineração de Dados, como Redes Neurais e algoritmos de Computação Evolucionária (Programação Genética, Algoritmos Genéticos, etc). A Computação Evolucionária (EC – Evolutionary Computation) é uma das áreas do aprendizado de máquina onde a solução de problemas baseia-se na teoria da evolução natural das espécies, proposta por Darwin. Entre as técnicas de Computação Evolucionária, as Estratégias Evolucionárias (ESs – Evolution Strategies) são apropriadas para a manipulação de variáveis contínuas. ESs codificam indivíduos (soluções) na forma de variáveis reais (contínuas) e evoluem essas soluções ao longo das gerações. Assim sendo, Estratégia Evolucionária pode ser utilizada na tarefa de regressão. Para aperfeiçoar as hipóteses obtidas por meio de ES, pode-se utilizar o Boosting, um método de aprendizado de máquina que visa gerar uma única solução precisa, combinando hipóteses fracas. Um algoritmo de Boosting é o AdaBoost, o qual fornece um conjunto de exemplos de treinamento com uma distribuição de pesos a um programa que gera hipóteses fracas. Isso força o programa a focar em exemplos de maior peso. O objetivo deste trabalho foi utilizar AdaBoost e ESs na tarefa de regressão para a Mineração de Dados Temporais. O algoritmo exposto nessa dissertação, denominado ESboost, foi implementado em C++ e utilizou a biblioteca EO. Realizaram-se diferentes experimentos com séries temporais univariadas, com séries temporais multivariadas e com bases de dados de regressão. Em relação às execuções da ES sem Boosting, observou-se que na maioria dos casos houve uma melhora pelo menos com uma das funções de perdas. Em muitos casos, houve melhora em relação à regressão linear e às model trees do software Weka, o qual é uma ferramenta para Mineração de Dados. Os resultados do ESboost nas séries temporais univariadas superaram o modelo ARMA em quase todas as séries. Trabalhos futuros poderão constituir-se da aplicação de outras técnicas de aprendizado de máquina no lugar de ES, de experimentos com outras funções de fitness e de estudos comparativos com outras metodologias para a predição de eventos

Abstract: The increase in the volume of stored data contributes to the growth of the expectationof obtaining implicit information that can aid in future decisions. The patterndiscovery in data presenting some time dimension represents a Temporal Data Miningtask. The patterns can be discovered through the regression method when the attributeshave numeric characteristics. Regression methods builds models that map inputvariables x = {x1 ...xn} for an output variable y. In order to determine linear models(equations) in regression, we need a technique that is able to manipulate continuousvariables. Different techniques can be used in Data Mining as, for example, NeuralNetworks and algorithms of Evolutionary Computation (Genetic Programming,Genetic Algorithms, etc). The Evolutionary Computation (EC) is one of the machinelearning areas that defines the solution of problems based on the theory of the naturalevolution of the species, proposed by Darwin. Among Evolutionary Computationtechniques, the Evolution Strategies (ESs) are appropriated for manipulation ofcontinuous variables. ESs codify individuals (solutions) in the form of real variables(continuous) and those solutions develop along the generations. Then, EvolutionStrategies can be used in the regression task. In order to improve the hypothesesobtained by means of Evolution Strategies, it is possible the use of Boosting, a methodof machine learning that seeks to generate a more precision solution combining weakhypotheses. An example of Boosting algorithm is the AdaBoost, which supplies agroup of training examples with a distribution of weights to a program that generatesweak hypotheses. That procedure forces the program in the examples with largerweight. The goal of this work was to use AdaBoost and ESs in the regression task forTemporal Data Mining. The algorithm showed in this dissertation, denominatedESboost, was implemented in C++ and used the EO library. Different experimentswere accomplished using univariate time series, multivariate time series and regressiondataset. Related to the executions without Boosting, it was observed an improvementin most of the cases at least with one of the loss functions. In many cases, it gets betterin relation to the methods implemented in Weka software, a Data Mining tool. Theresults of ESboost in the univariate time series outperform the ARMA model in almostall the series. Some future works can be constituted of the application of other machinelearning techniques in the place of ES, of experiments with other fitness functions andof comparative studies with other methodologies for the events prediction.