Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-03-02T13:31:20Z No. of bitstreams: 2 Dissertação_Albert F. J. Costa.pdf: 4215192 bytes, checksum: 995a811676e714bffa60b5d73a387cfa (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-03-02T13:31:36Z (GMT) No. of bitstreams: 2 Dissertação_Albert F. J. Costa.pdf: 4215192 bytes, checksum: 995a811676e714bffa60b5d73a387cfa (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-02T13:31:36Z (GMT). No. of bitstreams: 2 Dissertação_Albert F. J. Costa.pdf: 4215192 bytes, checksum: 995a811676e714bffa60b5d73a387cfa (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-12-11 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Current machine learning techniques used for prediction tasks rely on the assumption that the environment where data is generated is static and supervised. However, most of the real-world problems present dynamic and semi-supervised environments, which invalidate this assumed assumption. In these environments, it is possible the occurrence of a phenomenon known in the literature as concept drift. The main characteristic of such a phenomenon is that the relationship between instances’ features and their true classes changes over time. The primary effect of the concept drift occurrence is the decrease on classifier performance, which leads the classifier to be obsolete for the task. There are methods in the literature that deal with concept drift implicitly or explicitly. The main drawback to blind (implicit) methods is the cost on retraining the classifier constantly, even with no concept drift occurrence, while the informed (explicit) methods generally work based on classifier performance decrease, or based on assumptions about the samples distribution. In order to try to overcome these drawbacks, in this work we propose to use density variation of the most significant instances as an explicit trigger for concept drift detection. Density variation measurement is based on Active Learning, and is calculated from virtual margins projected onto the input space according to the classifier confidence. Focusing on demonstrating the validity of the proposed method, called Concept Drift Detection Method Based on Active Learning (DMAA), were have carried out experiments divided into two series. In the first series, DMAA was investigated on six databases, which represent four synthetic and two real problems. The obtained results show that the proposed method achieved 95.45% of drift detection rate on synthetic databases, and 16.5% as mean error rate in both synthetic and real databases. In the second series of experiments, DMAA was compared to three baselines, including two supervised drift detectors and one Active Learning-based method. The obtained results show that DMAA reached statistically significant better recognition rates in the majority of databases. Besides, it reduced the amount of labeled instances needed to keep the system updated. / As atuais técnicas de aprendizado de máquina aplicadas na tarefa de predição são baseadas na premissa de que o ambiente em que os dados são gerados apresenta um comportamento estacionário e supervisionado. Porém, os ambientes, na maioria dos problemas do mundo real, são considerados dinâmicos e semi-supervisionados, fatos que invalidam as premissas normalmente utilizadas. Nesses ambientes há a possibilidade da ocorrência do fenômeno conhecido na literatura por mudança de conceito (do inglês concept drift), que caracteriza-se pela alteração na relação entre as características das instâncias e a sua verdadeira classe com a passagem do tempo. Como efeito primário da ocorrência desse fenômeno tem-se a degradação significativa na taxa de desempenho do classificador, tornando-o obsoleto para a tarefa. Encontram-se na literatura métodos que lidam implicitamente ou explicitamente com a mudança de conceito, sendo que os métodos cegos (implícitos) arcam com os custos de retreinar o classificador de forma constante, enquanto que os métodos informados (explícitos) atuam normalmente baseados no monitoramento da degradação do desempenho do classificador, ou na realização de suposições sobre a distribuição das instâncias. Para contornar essas dificuldades, esta dissertação propõe o uso da variação da densidade das instâncias mais significativas, calculada com base em Aprendizado Ativo, como sinalizador explícito da ocorrência de mudança de conceito. A densidade é mensurada a partir do conceito de margens virtuais projetadas no espaço de entrada, sendo que as margens virtuais são obtidas com base na incerteza do classificador. Objetivando-se demonstrar a validade do método proposto, denominado de Método de Detecção de Mudança de Conceito Baseada em Aprendizado Ativo (DMAA), experimentos foram realizados em duas etapas. A primeira consistiu na aplicação do DMAA em seis bases de dados, sendo quatro sintéticas e duas reais. Os resultados obtidos demonstram que o método proposto identificou em média 95,45% das mudanças existentes nas bases sintéticas, e alcançou uma média geral de erro de 16,5%. Na segunda etapa de experimentos, foi feita uma comparação entre o DMAA e três baselines, incluindo dois métodos supervisionados e um método baseado em aprendizado ativo. Os resultados indicam que o DMAA alcançou resultados estatisticamente superiores em mais da metade das bases de dados investigadas, além de reduzir significativamente a quantidade de instâncias rotuladas necessárias para manter o sistema atualizado.

Apesar do grau relativamente alto de maturidade existente na área de pesquisa de aprendizado supervisionado em lote, na qual são utilizados dados originários de problemas estacionários, muitas aplicações reais lidam com fluxos de dados cujas distribuições de probabilidade se alteram com o tempo, ocasionando mudanças de conceito. Diversas pesquisas vêm sendo realizadas nos últimos anos com o objetivo de criar modelos precisos mesmo na presença de mudanças de conceito. A maioria delas, no entanto, assume que tão logo um evento seja classificado pelo algoritmo de aprendizado, seu rótulo verdadeiro se torna conhecido. Este trabalho explora as situações complementares, com revisão dos trabalhos mais importantes publicados e análise do impacto de atraso na disponibilidade dos rótulos verdadeiros ou sua não disponibilização. Ainda, propõe um novo algoritmo que reduz drasticamente a complexidade de aplicação do teste de hipótese não-paramétrico Kolmogorov-Smirnov, tornado eficiente seu uso em algoritmos que analisem fluxos de dados. A exemplo, mostramos sua potencial aplicação em um método de detecção de mudança de conceito não-supervisionado que, em conjunto com técnicas de Aprendizado Ativo e Aprendizado por Transferência, reduz a necessidade de rótulos verdadeiros para manter boa performance de um classificador ao longo do tempo, mesmo com a ocorrência de mudanças de conceito. / Despite the relatively maturity of batch-mode supervised learning research, in which the data typifies stationary problems, many real world applications deal with data streams whose statistical distribution changes over time, causing what is known as concept drift. A large body of research has been done in the last years, with the objective of creating new models that are accurate even in the presence of concept drifts. However, most of them assume that, once the classification algorithm labels an event, its actual label become readily available. This work explores the complementary situations, with a review of the most important published works and an analysis over the impact of delayed true labeling, including no true label availability at all. Furthermore, this work proposes a new algorithm that heavily reduces the complexity of applying Kolmogorov- Smirnov non-parametric hypotheis test, turning it into an uselful tool for analysis on data streams. As an instantiation of its usefulness, we present an unsupervised drift-detection method that, along with Active Learning and Transfer Learning approaches, decreases the number of true labels that are required to keep good classification performance over time, even in the presence of concept drifts.

Aprender conceitos provenientes de fluxos de dados é uma tarefa significamente diferente do aprendizado tradicional em lote. No aprendizado em lote, existe uma premissa implicita que os conceitos a serem aprendidos são estáticos e não evoluem significamente com o tempo. Por outro lado, em fluxos de dados os conceitos a serem aprendidos podem evoluir ao longo do tempo. Esta evolução é chamada de mudança de conceito, e torna a criação de um conjunto fixo de treinamento inaplicável neste cenário. O aprendizado incremental é uma abordagem promissora para trabalhar com fluxos de dados. Contudo, na presença de mudanças de conceito, conceitos desatualizados podem causar erros na classificação de eventos. Apesar de alguns métodos incrementais baseados no modelo de misturas gaussianas terem sido propostos na literatura, nota-se que tais algoritmos não possuem uma política explicita de descarte de conceitos obsoletos. Nesse trabalho um novo algoritmo incremental para fluxos de dados com mudanças de conceito baseado no modelo de misturas gaussianas é proposto. O método proposto é comparado com vários algoritmos amplamente utilizados na literatura, e os resultados mostram que o algoritmo proposto é competitivo com os demais em vários cenários, superando-os em alguns casos. / Learning concepts from data streams differs significantly from traditional batch learning. In batch learning there is an implicit assumption that the concept to be learned is static and does not evolve significantly over time. On the other hand, in data stream learning the concepts to be learned may evolve over time. This evolution is called concept drift, and makes the creation of a fixed training set be no longer applicable. Incremental learning paradigm is a promising approach for learning in a data stream setting. However, in the presence of concept drifts, out dated concepts can cause misclassifications. Several incremental Gaussian mixture models methods have been proposed in the literature, but these algorithms lack an explicit policy to discard outdated concepts. In this work, a new incremental algorithm for data stream with concept drifts based on Gaussian Mixture Models is proposed. The proposed methodis compared to various algorithms widely used in the literature, and the results show that it is competitive with them invarious scenarios, overcoming them in some cases.

Apesar do grau relativamente alto de maturidade existente na área de pesquisa de aprendizado supervisionado em lote, na qual são utilizados dados originários de problemas estacionários, muitas aplicações reais lidam com fluxos de dados cujas distribuições de probabilidade se alteram com o tempo, ocasionando mudanças de conceito. Diversas pesquisas vêm sendo realizadas nos últimos anos com o objetivo de criar modelos precisos mesmo na presença de mudanças de conceito. A maioria delas, no entanto, assume que tão logo um evento seja classificado pelo algoritmo de aprendizado, seu rótulo verdadeiro se torna conhecido. Este trabalho explora as situações complementares, com revisão dos trabalhos mais importantes publicados e análise do impacto de atraso na disponibilidade dos rótulos verdadeiros ou sua não disponibilização. Ainda, propõe um novo algoritmo que reduz drasticamente a complexidade de aplicação do teste de hipótese não-paramétrico Kolmogorov-Smirnov, tornado eficiente seu uso em algoritmos que analisem fluxos de dados. A exemplo, mostramos sua potencial aplicação em um método de detecção de mudança de conceito não-supervisionado que, em conjunto com técnicas de Aprendizado Ativo e Aprendizado por Transferência, reduz a necessidade de rótulos verdadeiros para manter boa performance de um classificador ao longo do tempo, mesmo com a ocorrência de mudanças de conceito. / Despite the relatively maturity of batch-mode supervised learning research, in which the data typifies stationary problems, many real world applications deal with data streams whose statistical distribution changes over time, causing what is known as concept drift. A large body of research has been done in the last years, with the objective of creating new models that are accurate even in the presence of concept drifts. However, most of them assume that, once the classification algorithm labels an event, its actual label become readily available. This work explores the complementary situations, with a review of the most important published works and an analysis over the impact of delayed true labeling, including no true label availability at all. Furthermore, this work proposes a new algorithm that heavily reduces the complexity of applying Kolmogorov- Smirnov non-parametric hypotheis test, turning it into an uselful tool for analysis on data streams. As an instantiation of its usefulness, we present an unsupervised drift-detection method that, along with Active Learning and Transfer Learning approaches, decreases the number of true labels that are required to keep good classification performance over time, even in the presence of concept drifts.

Submitted by Haroudo Xavier Filho (haroudo.xavierfo@ufpe.br) on 2016-01-22T14:22:26Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_Mestrado_Victor_Lorena.pdf: 1644188 bytes, checksum: 4a53bf1f4dc89599b68bd29f20b7fd59 (MD5) / Made available in DSpace on 2016-01-22T14:22:26Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_Mestrado_Victor_Lorena.pdf: 1644188 bytes, checksum: 4a53bf1f4dc89599b68bd29f20b7fd59 (MD5) Previous issue date: 2015-10-19 / FACEPE / Uma série temporal financeira representa as cotações dos preços das ações e apresenta comportamento similar a um fluxo de dados. Para a descoberta de padrões presentes em seus dados alguns trabalhos utilizam técnicas de mineração de dados que são fundamentadas na ideia de que os dados históricos guardam a memória essencial para prever a direção futura dos preços. Métodos tradicionais propostos na literatura consideram que o ambiente é estático, ou seja, que o mecanismo gerador da série financeira é o mesmo durante todo o intervalo de tempo de interesse. Porém, no caso de séries temporais financeiras, isso pode não ocorrer. Para resolver este problema, esta dissertação propõe a abordagem PAA-IDPSO-CD (Aproximação por Valor Agregado de Segmento - Otimização por Enxame de Partículas Auto Adaptativa com detecção de mudança de conceito) para descoberta de padrões em séries temporais financeiras. A abordagem proposta objetiva lidar explicitamente com mudanças de conceito na série e descobrir os melhores padrões representativos dos dados das séries temporais que serão utilizados junto a uma estratégia de investimento formulada para automatizar as operações a serem feitas no mercado de ações. Isso possibilitará a redução das incertezas e dos riscos envolvidos nas compras e vendas de ações e auxiliará os investidores a maximizar o lucro nas suas operações feitas no mercado de ações. A fim de alcançar melhores resultados são propostas diferentes estruturas de partículas, utilizadas pelo IDPSO, junto a diferentes regras de decisão. Primeiramente, é utilizada uma estrutura básica para a partícula, em que se opera apenas na posição comprado no mercado financeiro. É proposto também uma segunda estrutura que é capaz de operar tanto na posição comprado quanto na posição vendido. Os experimentos do presente estudo comparam os resultados das versões do método proposto entre si e com os resultados obtidos pelas abordagens Buy and Hold (B&H) e SAX-GA (Aproximação por Valor Agregado Simbólico - Algoritmos Genéticos). Para isso, foram realizados Teste t Pareado com nível de confiança de 95% em vinte ações. O presente estudo conclui que o PAA-IDPSO-CD apresentou resultados estatisticamente melhores que o B&H e o SAX-GA para todas as vinte ações em que os testes foram executados (pvalor <0;05). Além disso, a estratégia que opera nas posições comprado e vendido é melhor quando comparada àquela que opera apenas na posição comprado. No estudo comparativo em onze ações não houve diferença estatística e em outras sete a estratégia comprado e vendido obteve melhores resultados (pvalor < 0; 05). / Financial time series represents the prices of stock over time and presents similar behavior to a data stream. Mining techniques, which are based on the idea that the historical data retain the essential memory to predict the future direction, are used to make the patterns discovery in the time series data. In this context, this study proposes the PAA-IDPSO-CD (Piecewise Aggregate Approximation - Improved self-adaptive particle swarm optimization with Concept Drift) approach aiming to find patterns in financial time series. The purpose of this study is the discovery of the best representative patterns of the time series data to be used by a designed investment strategy to automate the operations to be made in the stock market. Thus, reducing the uncertainties and risks involved in buying and selling operations of stocks and help investors maximize the profit in their operations made in the stock market. In order to achieve best results, different particle structures, used by IDPSO, along with different decision rules are proposed. First, a basic structure to the particle is employed, it operates only in the Long position in the financial market. Subsequently, this structure develops to be able to operate both in Long and Short position. The experiments of this study comparing the results of the various versions of the proposed approach with each other and with those obtained by the Buy and Hold (B&H) and SAX-GA techniques, for that, were performed Paired t test with a confidence level of 95% in twenty stocks. The achieved results show that the PAA-IDPSO-CD outperforms B&H and SAX-GA for all twenty stocks in which the tests were performed (pvalue < 0:05). Furthermore, the long-short operating strategy is better than that operating only in the long position. In the comparative study in eleven actions there was no statistical difference and in other seven long-short strategy outperforms (pvalue < 0:05).

Submitted by Regis Albuquerque (regis.albuquerque1@gmail.com) on 2018-06-20T21:40:28Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) dissertacao_regis_corrigida_final.pdf: 2557634 bytes, checksum: b48eb7c37fd9dd633c4489a7f0f041a4 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-06-20T21:52:37Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) dissertacao_regis_corrigida_final.pdf: 2557634 bytes, checksum: b48eb7c37fd9dd633c4489a7f0f041a4 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-06-21T13:29:00Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) dissertacao_regis_corrigida_final.pdf: 2557634 bytes, checksum: b48eb7c37fd9dd633c4489a7f0f041a4 (MD5) / Made available in DSpace on 2018-06-21T13:29:01Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) dissertacao_regis_corrigida_final.pdf: 2557634 bytes, checksum: b48eb7c37fd9dd633c4489a7f0f041a4 (MD5) Previous issue date: 2018-06-08 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Many machine learning applications have to deal with classification problems in dynamic environments. This type of environment may be affected by concept drift, which may reduce the accuracy of classification systems significantly. In this context, methods using ensemble of classifiers are interesting due to the fact that ensembles of classifiers allow the design of strategies for drift detection and reaction more accurate and robust to changes. A classification system based on ensemble of classifiers may be divided into three main phases: classifier generation; single classifier or subset of classifier selection; and classifier fusion. The selection phase may be performed as a dynamic process. In this case, for each unknown sample, the individual classifier or classifier ensemble most likely to be correct is chosen to assign a label to the sample. In this work, it is proposed a method for concept drift detection and reaction based on dynamic classifier ensemble selection. The proposed method choses the expert classifier ensemble according to diversity and accuracy values. Focusing on evaluating the impact of dynamic ensemble selection guided by diversity and accuracy in terms of concept drift detection and reaction, four series of experiments were carried in this work using both synthetic and real datasets. In addition, since the proposed method is broken down into four phases: pool of ensemble classifiers generation; dynamic ensemble selection; drift detection; and drift reaction, different versions of the proposed method were investigated by varying the parameters of each phase. The results show that, in general, all these different versions attain very similar accuracy values. Besides, when compared to two baselines: (1) DDM - single classifier-based; and (2) Leveraging Bagging - classifier ensemble-based, our method outperforms both baselines since it achieved higher accuracy, lower detection delay and false detection rates, and it did not present missing detection. However, both baselines present lower time complexity. Therefore, this work shows that dynamic classifier ensemble selection guided by diversity and accuracy helps to improve detection precision and the general accuracy of classification systems employed in problems with concept drift. / Muitas aplicações de aprendizado de máquina estão relacionadas com problemas de classificação em ambientes dinâmicos. Mudança de conceito figura nesse tipo de ambiente e pode prejudicar muito a acurácia de sistemas de classificação. Nesse contexto, a utilização de comitês de classificadores é interessante porque possibilita a implementação de processos de detecção e de reação à mudança mais acurados e robustos. Sistemas de classificação que utilizam comitês podem possuir três grandes fases: geração; seleção; e integração de classificadores. A etapa de seleção pode ser feita de forma dinâmica, isto é, para cada instância desconhecida, o classificador ou comitê de classificadores com maior probabilidade de acerto é escolhido para atribuir uma classe à essa instância. Neste trabalho, é proposto um método para detecção e reação à mudança de conceito que utiliza seleção dinâmica de comitês de classificadores. O método proposto escolhe o comitê especialista com base nos valores de diversidade e de acurácia de cada comitê candidato. A fim de avaliar o impacto do uso de seleção dinâmica guiada por diversidade e acurácia nas tarefas de detecção e reação a mudança de conceito, foram realizadas quatro séries de experimentos com bases sintéticas e reais. Além disso, como o método proposto é dividido em quatro fases: geração da população de comitês; seleção dinâmica do comitê especialista; detecção de mudanças; e reação à mudança, diferentes versões desse método foram investigadas em função da definição de parâmetros de cada fase. Os resultados dos experimentos mostraram que, de maneira geral, as versões estudadas são bem equivalentes em termos de acurácia média final. Adicionalmente, quando comparado a dois baselines: (1) DDM - que utiliza um único classificador; e (2) Leveraging Bagging - que utiliza um comitê de classificadores, o método proposto alcançou melhores taxas de acurácia, menores taxas de atraso de detecção, não deixou de detectar as mudanças conhecidas nas bases e produziu reduzidas taxas de falsa detecção, apesar de apresentar maior complexidade computacional. Portanto, o trabalho mostra que o uso de seleção dinâmica guiada por diversidade e acurácia melhora a precisão de detecção, bem como a acurácia geral de sistemas de classificação utilizados em problemas que apresentam mudança de conceitos.

Aprender conceitos provenientes de fluxos de dados é uma tarefa significamente diferente do aprendizado tradicional em lote. No aprendizado em lote, existe uma premissa implicita que os conceitos a serem aprendidos são estáticos e não evoluem significamente com o tempo. Por outro lado, em fluxos de dados os conceitos a serem aprendidos podem evoluir ao longo do tempo. Esta evolução é chamada de mudança de conceito, e torna a criação de um conjunto fixo de treinamento inaplicável neste cenário. O aprendizado incremental é uma abordagem promissora para trabalhar com fluxos de dados. Contudo, na presença de mudanças de conceito, conceitos desatualizados podem causar erros na classificação de eventos. Apesar de alguns métodos incrementais baseados no modelo de misturas gaussianas terem sido propostos na literatura, nota-se que tais algoritmos não possuem uma política explicita de descarte de conceitos obsoletos. Nesse trabalho um novo algoritmo incremental para fluxos de dados com mudanças de conceito baseado no modelo de misturas gaussianas é proposto. O método proposto é comparado com vários algoritmos amplamente utilizados na literatura, e os resultados mostram que o algoritmo proposto é competitivo com os demais em vários cenários, superando-os em alguns casos. / Learning concepts from data streams differs significantly from traditional batch learning. In batch learning there is an implicit assumption that the concept to be learned is static and does not evolve significantly over time. On the other hand, in data stream learning the concepts to be learned may evolve over time. This evolution is called concept drift, and makes the creation of a fixed training set be no longer applicable. Incremental learning paradigm is a promising approach for learning in a data stream setting. However, in the presence of concept drifts, out dated concepts can cause misclassifications. Several incremental Gaussian mixture models methods have been proposed in the literature, but these algorithms lack an explicit policy to discard outdated concepts. In this work, a new incremental algorithm for data stream with concept drifts based on Gaussian Mixture Models is proposed. The proposed methodis compared to various algorithms widely used in the literature, and the results show that it is competitive with them invarious scenarios, overcoming them in some cases.

Aprendizado em fluxo de dados é uma área de pesquisa importante e que vem crescendo nos últimos tempos. Em muitas aplicações reais os dados são gerados em uma sequência temporal potencialmente infinita. O processamento em fluxo possui como principal característica a necessidade por respostas que atendam restrições severas de tempo e memória. Por exemplo, um classificador aplicado a um fluxo de dados deve prover uma resposta a um determinado evento antes que o próximo evento ocorra. Caso isso não ocorra, alguns eventos do fluxo podem ficar sem classificação. Muitos fluxos geram eventos em uma taxa de chegada com grande variabilidade, ou seja, o intervalo de tempo de ocorrência entre dois eventos sucessivos pode variar muito. Para que um sistema de aprendizado obtenha sucesso na aquisição de conhecimento é preciso que ele apresente duas características principais: (i) ser capaz de prover uma classificação para um novo exemplo em tempo hábil e (ii) ser capaz de adaptar o modelo de classificação de maneira a tratar mudanças de conceito, uma vez que os dados podem não apresentar uma distribuição estacionária. Algoritmos de aprendizado de máquina em lote não possuem essas propriedades, pois assumem que as distribuições são estacionárias e não estão preparados para atender restrições de memória e processamento. Para atender essas necessidades, esses algoritmos devem ser adaptados ao contexto de fluxo de dados. Uma possível adaptação é tornar o algoritmo de classificação anytime. Algoritmos anytime são capazes de serem interrompidos e prover uma resposta (classificação) aproximada a qualquer instante. Outra adaptação é tornar o algoritmo incremental, de maneira que seu modelo possa ser atualizado para novos exemplos do fluxo de dados. Neste trabalho é realizada a investigação de dois métodos capazes de realizar o aprendizado em um fluxo de dados. O primeiro é baseado no algoritmo k-vizinhos mais próximo anytime estado-da-arte, onde foi proposto um novo método de desempate para ser utilizado neste algoritmo. Os experimentos mostraram uma melhora consistente no desempenho deste algoritmo em várias bases de dados de benchmark. O segundo método proposto possui as características dos algoritmos anytime e é capaz de tratar a mudança de conceito nos dados. Este método foi chamado de Algoritmo Anytime Incremental e possui duas versões, uma baseado no algoritmo Space Saving e outra em uma Janela Deslizante. Os experimentos mostraram que em cada fluxo cada versão deste método proposto possui suas vantagens e desvantagens. Mas no geral, comparado com outros métodos baselines, ambas as versões apresentaram melhor desempenho. / Data stream learning is a very important research field that has received much attention from the scientific community. In many real-world applications, data is generated as potentially infinite temporal sequences. The main characteristic of stream processing is to provide answers observing stringent restrictions of time and memory. For example, a data stream classifier must provide an answer for each event before the next one arrives. If this does not occur, some events from the data stream may be left unclassified. Many streams generate events with highly variable output rate, i.e. the time interval between two consecutive events may vary greatly. For a learning system to be successful, two properties must be satisfied: (i) it must be able to provide a classification for a new example in a short time and (ii) it must be able to adapt the classification model to treat concept change, since the data may not follow a stationary distribution. Batch machine learning algorithms do not satisfy those properties because they assume that the distribution is stationary and they are not prepared to operate with severe memory and processing constraints. To satisfy these requirements, these algorithms must be adapted to the data stream context. One possible adaptation is to turn the algorithm into an anytime classifier. Anytime algorithms may be interrupted and still provide an approximated answer (classification) at any time. Another adaptation is to turn the algorithm into an incremental classifier so that its model may be updated with new examples from the data stream. In this work, it is performed an evaluation of two approaches for data stream learning. The first one is based on a state-of-the-art k-nearest neighbor anytime classifier. A new tiebreak approach is proposed to be used with this algorithm. Experiments show consistently better results in the performance of this algorithm in many benchmark data sets. The second proposed approach is to adapt the anytime algorithm for concept change. This approach was called Incremental Anytime Algorithm, and it was designed with two versions. One version is based on the Space Saving algorithm and the other is based in a Sliding Window. Experiments show that both versions are significantly better than baseline approaches.

Aprendizado em fluxo de dados é uma área de pesquisa importante e que vem crescendo nos últimos tempos. Em muitas aplicações reais os dados são gerados em uma sequência temporal potencialmente infinita. O processamento em fluxo possui como principal característica a necessidade por respostas que atendam restrições severas de tempo e memória. Por exemplo, um classificador aplicado a um fluxo de dados deve prover uma resposta a um determinado evento antes que o próximo evento ocorra. Caso isso não ocorra, alguns eventos do fluxo podem ficar sem classificação. Muitos fluxos geram eventos em uma taxa de chegada com grande variabilidade, ou seja, o intervalo de tempo de ocorrência entre dois eventos sucessivos pode variar muito. Para que um sistema de aprendizado obtenha sucesso na aquisição de conhecimento é preciso que ele apresente duas características principais: (i) ser capaz de prover uma classificação para um novo exemplo em tempo hábil e (ii) ser capaz de adaptar o modelo de classificação de maneira a tratar mudanças de conceito, uma vez que os dados podem não apresentar uma distribuição estacionária. Algoritmos de aprendizado de máquina em lote não possuem essas propriedades, pois assumem que as distribuições são estacionárias e não estão preparados para atender restrições de memória e processamento. Para atender essas necessidades, esses algoritmos devem ser adaptados ao contexto de fluxo de dados. Uma possível adaptação é tornar o algoritmo de classificação anytime. Algoritmos anytime são capazes de serem interrompidos e prover uma resposta (classificação) aproximada a qualquer instante. Outra adaptação é tornar o algoritmo incremental, de maneira que seu modelo possa ser atualizado para novos exemplos do fluxo de dados. Neste trabalho é realizada a investigação de dois métodos capazes de realizar o aprendizado em um fluxo de dados. O primeiro é baseado no algoritmo k-vizinhos mais próximo anytime estado-da-arte, onde foi proposto um novo método de desempate para ser utilizado neste algoritmo. Os experimentos mostraram uma melhora consistente no desempenho deste algoritmo em várias bases de dados de benchmark. O segundo método proposto possui as características dos algoritmos anytime e é capaz de tratar a mudança de conceito nos dados. Este método foi chamado de Algoritmo Anytime Incremental e possui duas versões, uma baseado no algoritmo Space Saving e outra em uma Janela Deslizante. Os experimentos mostraram que em cada fluxo cada versão deste método proposto possui suas vantagens e desvantagens. Mas no geral, comparado com outros métodos baselines, ambas as versões apresentaram melhor desempenho. / Data stream learning is a very important research field that has received much attention from the scientific community. In many real-world applications, data is generated as potentially infinite temporal sequences. The main characteristic of stream processing is to provide answers observing stringent restrictions of time and memory. For example, a data stream classifier must provide an answer for each event before the next one arrives. If this does not occur, some events from the data stream may be left unclassified. Many streams generate events with highly variable output rate, i.e. the time interval between two consecutive events may vary greatly. For a learning system to be successful, two properties must be satisfied: (i) it must be able to provide a classification for a new example in a short time and (ii) it must be able to adapt the classification model to treat concept change, since the data may not follow a stationary distribution. Batch machine learning algorithms do not satisfy those properties because they assume that the distribution is stationary and they are not prepared to operate with severe memory and processing constraints. To satisfy these requirements, these algorithms must be adapted to the data stream context. One possible adaptation is to turn the algorithm into an anytime classifier. Anytime algorithms may be interrupted and still provide an approximated answer (classification) at any time. Another adaptation is to turn the algorithm into an incremental classifier so that its model may be updated with new examples from the data stream. In this work, it is performed an evaluation of two approaches for data stream learning. The first one is based on a state-of-the-art k-nearest neighbor anytime classifier. A new tiebreak approach is proposed to be used with this algorithm. Experiments show consistently better results in the performance of this algorithm in many benchmark data sets. The second proposed approach is to adapt the anytime algorithm for concept change. This approach was called Incremental Anytime Algorithm, and it was designed with two versions. One version is based on the Space Saving algorithm and the other is based in a Sliding Window. Experiments show that both versions are significantly better than baseline approaches.

Métodos baseados em grafos consistem em uma poderosa forma de representação e abstração de dados que proporcionam, dentre outras vantagens, representar relações topológicas, visualizar estruturas, representar grupos de dados com formatos distintos, bem como, fornecer medidas alternativas para caracterizar os dados. Esse tipo de abordagem tem sido cada vez mais considerada para solucionar problemas de aprendizado de máquina, principalmente no aprendizado não supervisionado, como agrupamento de dados, e mais recentemente, no aprendizado semissupervisionado. No aprendizado supervisionado, por outro lado, o uso de algoritmos baseados em grafos ainda tem sido pouco explorado na literatura. Este trabalho apresenta um algoritmo não paramétrico baseado em grafos para problemas de classificação com distribuição estacionária, bem como sua extensão para problemas que apresentam distribuição não estacionária. O algoritmo desenvolvido baseia-se em dois conceitos, a saber, 1) em uma estrutura chamada grafo K-associado ótimo, que representa o conjunto de treinamento como um grafo esparso e dividido em componentes; e 2) na medida de pureza de cada componente, que utiliza a estrutura do grafo para determinar o nível de mistura local dos dados em relação às suas classes. O trabalho também considera problemas de classificação que apresentam alteração na distribuição de novos dados. Este problema caracteriza a mudança de conceito e degrada o desempenho do classificador. De modo que, para manter bom desempenho, é necessário que o classificador continue aprendendo durante a fase de aplicação, por exemplo, por meio de aprendizado incremental. Resultados experimentais sugerem que ambas as abordagens apresentam vantagens na classificação de dados em relação aos algoritmos testados / Graph-based methods consist in a powerful form for data representation and abstraction which provides, among others advantages, representing topological relations, visualizing structures, representing groups of data with distinct formats, as well as, supplying alternative measures to characterize data. Such approach has been each time more considered to solve machine learning related problems, mainly concerning unsupervised learning, like clustering, and recently, semi-supervised learning. However, graph-based solutions for supervised learning tasks still remain underexplored in literature. This work presents a non-parametric graph-based algorithm suitable for classification problems with stationary distribution, as well as its extension to cope with problems of non-stationary distributed data. The developed algorithm relies on the following concepts, 1) a graph structure called optimal K-associated graph, which represents the training set as a sparse graph separated into components; and 2) the purity measure for each component, which uses the graph structure to determine local data mixture level in relation to their classes. This work also considers classification problems that exhibit modification on distribution of data flow. This problem qualifies concept drift and worsens any static classifier performance. Hence, in order to maintain accuracy performance, it is necessary for the classifier to keep learning during application phase, for example, by implementing incremental learning. Experimental results, concerning both algorithms, suggest that they had presented advantages over the tested algorithms on data classification tasks