English

CIn - Centro de Informática UFPE




Eventos Relacionados

Defesa de Tese de Doutorado Nº 187: "Multivariate non-parametric statistical tests to reuse classifiers in recurring concept drifting environments"

O aluno Paulo Mauricio Gonçalves Júnior irá defender seu trabalho dia 23 de abril, às 13h, na sala D218 Início: 23/04/2013 às 13:00 Término: 23/04/2013 às 15:00 Local: Sala D218

Pós-Graduação em Ciência da Computação – UFPE
Defesa de Tese de Doutorado Nº 187
 
Aluno: Paulo Mauricio Gonçalves Júnior
Orientador: Prof. Roberto Souto Maior de Barros
Título: MULTIVARIATE NON-PARAMETRIC STATISTICAL TESTS TO REUSE CLASSIFIERS IN RECURRING CONCEPT DRIFTING ENVIRONMENTS
Data: 23/04/2013
Hora/Local: 13:00h – Sala D218
 
Banca Examinadora:
Prof. Paulo Jorge Leitão Adeodato (UFPE / Centro de Informática)
Prof. Geber Lisboa Ramalho (UFPE / Centro de Informática)
Prof. Sergio Ricardo de Melo Queiroz (UFPE / Centro de Informática)
Prof. José Alfredo Ferreira Costa (UFRN / Departamento de Engenharia Elétrica)
Prof. Marco Antonio de Oliveira Domingues (IFPE / DASE)
 
RESUMO:
 
Data streams are a recent processing model where data arrives continuously, in large quantities, and at high speeds that must be processed on-line. Besides that, several private and public institutions store large amounts of data that also must be processed. Traditional batch classifiers are not well suited to handle huge amounts of data for basically two reasons. First, they usually read the available data several times until converge, which is impractical in this scenario. Second, they imply that the context represented by data is stable in time, which may not be true. In fact, the context change is a common situation in data streams, and is named concept drift.
This thesis presents rcd, a framework that offers an alternative approach to handle data streams that suffer from recurring concept drifts. It creates a new classifier to each context found and stores a sample of the data used to build it. When a new concept drift occurs, RCD compares the new context to old ones using a non-parametric multivariate statistical test to verify if both contexts come from the same distribution. If so, the corresponding classifier is reused. If not, a new classifier is generated and stored.
Three kinds of tests were performed. One compares the RCD framework with several adaptive algorithms (among single and ensemble approaches) in artificial and real data sets, among the most used in the concept drift research area, with abrupt and gradual concept drifts. It is observed the ability of the classifiers in representing each context, how they handle concept drift, and training and testing times needed to evaluate the data sets. Results shown that RCD had better statistical results compared to the other classifiers when abrupt concept drifts occurred. With gradual concept drifts, it also had better performance, but in fewer cases. In the real-world data sets, RCD presented accuracies close to the best classifier in each data set.
Another test compares two statistical tests (knn and Cramer) in their capability in representing and identifying contexts. Tests were performed using adaptive and batch classifiers as base learners of RCD in artificial and real-world data sets, with several rates-of-change. Results shown that, in average, knn had better results compared to the Cramer test, and was also faster. Independently of the test used, RCD had higher accuracy values compared to their respective base learners.
It is also presented an improvement in the RCD framework where the statistical tests are performed in parallel through the use of a thread pool. Tests were performed in three processors with different numbers of cores. Better results were obtained when there was a high number of detected concept drifts, the buffer size used to represent each data distribution was large, and there was a high test frequency. Even if none of these conditions apply, parallel and sequential execution still have very similar performances.
Finally, a comparison between five different drift detection methods were also performed, comparing the predictive accuracies, evaluation times, and drift handling, including false alarm and miss detection rates, and average distance to the drift point and its standard deviation.
 
Palavras-chave: Data streams, concept drifts, multivariate non-parametric statistical test,
recurring contexts
 
===================================================================
Título: Testes estatísticos não-paramétricos multivariados para reutilização de classificadores em ambientes com mudanças de conceito recorrentes
Resumo:
 
Fluxos de dados são um modelo de processamento de dados recente, onde os dados chegam continuamente, em grandes quantidades, a altas velocidades, de modo que eles devem ser processados em tempo real. Além disso, várias instituições públicas e privadas armazenam grandes quantidades de dados que também devem ser processadas. Classificadores tradicionais não são adequados para lidar com grandes quantidades de dados por basicamente duas razões. Primeiro, eles costumam ler os dados disponíveis várias vezes até convergirem, o que é impraticável neste cenário. Em segundo lugar, eles assumem que o contexto representado por dados é estável no tempo, o que pode não ser verdadeiro. Na verdade, a mudança de contexto é uma situação comum em fluxos de dados, e é chamado de mudança de conceito.
Esta tese apresenta o RCD, uma estrutura que oferece uma abordagem alternativa para lidar com os fluxos de dados que sofrem de mudanças de conceito recorrentes. Ele cria um novo classificador para cada contexto encontrado e armazena uma amostra dos dados usados para construí-lo. Quando uma nova mudança de conceito ocorre, RCD compara o novo contexto com os antigos, utilizando um teste estatístico não paramétrico multivariado para verificar se ambos os contextos provêm da mesma distribuição. Se assim for, o classificador correspondente é reutilizado. Se não, um novo classificador é gerado e armazenado.
Três tipos de testes foram realizados. Um compara o RCD com vários algoritmos adaptativos (entre as abordagens individuais e de agrupamento) em conjuntos de dados artificiais e reais, entre os mais utilizados na área de pesquisa de mudança de conceito, com mudanças bruscas e graduais. É observada a capacidade dos classificadores em representar cada contexto, como eles lidam com as mudanças de conceito e os tempos de treinamento e teste necessários para avaliar os conjuntos de dados. Os resultados indicam que RCD teve resultados estatísticos semelhantes ou melhores, em comparação com os outros classificadores. Nos conjuntos de dados do mundo real, RCD apresentou precisões próximas do melhor classificador em cada conjunto de dados.
Outro teste compara dois testes estatísticos (KNN e Cramer) em suas capacidades de representar e identificar contextos. Os testes foram realizados utilizando classificadores tradicionais e adaptativos como base do RCD, em conjuntos de dados artificiais e do mundo real, com várias taxas de variação. Os resultados indicam que, em média, KNN obteve melhores resultados em comparação com o teste de Cramer, além de ser mais rápido. Independentemente do critério utilizado, RCD apresentou valores mais elevados de precisão em comparação com seus respectivos classificadores base.
Também é apresentada uma melhoria do RCD onde os testes estatísticos são executadas em paralelo por meio do uso de um pool de threads. Os testes foram realizados em três processadores com diferentes números de núcleos. Melhores resultados foram obtidos quando houve um elevado número de mudanças de conceito detectadas, o tamanho das amostras utilizadas para representar cada distribuição de dados era grande, e havia uma alta freqüência de testes. Mesmo que nenhuma destas condições se aplicam, a execução paralela e seqüencial ainda têm performances muito semelhantes.
Finalmente, uma comparação entre seis diferentes métodos de detecção de mudança de conceito também foi realizada, comparando a precisão, os tempos de avaliação, manipulação das mudanças de conceito, incluindo as taxas de falsos positivos e negativos, bem como a média da distância ao ponto de mudança e o seu desvio padrão.
 
Palavras-chaves: Fluxos de dados, mudanças de conceito, teste estatístico não-paramétrico multivariado, contextos recorrentes, aprendizado em tempo real 
  • © Centro de Informática UFPE - Todos os direitos reservados
    Tel +55 81 2126.8430 - Cidade Universitária - 50740-560 - Recife/PE
Plano4 Consultoria Web