Employing nonlinear time series analysis tools with stable clustering algorithms for detecting concept drift on data streams (2017)
- Authors:
- Autor USP: COSTA, FAUSTO GUZZO DA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: ANÁLISE DE SÉRIES TEMPORAIS; APRENDIZADO COMPUTACIONAL; SISTEMAS DINÂMICOS
- Keywords: Agrupamento; Clustering; Concept drift; Data streams; Fluxos de dados; Machine learning; Mudanças de conceito; Nonlinear time series
- Language: Inglês
- Abstract: Diversos processos industriais, científicos e comerciais produzem sequências de observações continuamente, teoricamente infinitas, denominadas fluxos de dados. Pela análise das recorrências e das mudanças de comportamento desses fluxos, é possível obter informações sobre o fenômeno que os produziu. A inferência de modelos estáveis para tais fluxos é suportada pelo estudo das recorrências dos dados, enquanto é prejudicada pelas mudanças de comportamento. Essas mudanças são produzidas principalmente por influências externas ainda desconhecidas pelos modelos vigentes, tal como ocorre quando novas estratégias de investimento surgem na bolsa de valores, ou quando há intervenções humanas no clima, etc. No contexto de Aprendizado de Máquina (AM), várias pesquisas têm sido realizadas para investigar essas variações nos fluxos de dados, referidas como mudanças de conceito. Sua detecção permite que os modelos possam ser atualizados a fim de apurar a predição, a compreensão e, eventualmente, controlar as influências que governam o fluxo de dados em estudo. Nesse cenário, algoritmos supervisionados sofrem com a limitação para rotular os dados quando esses são gerados em alta frequência e grandes volumes, e algoritmos não supervisionados carecem de fundamentação teórica para prover garantias na detecção de mudanças. Além disso, algoritmos de ambos paradigmas não representam adequadamente as dependências temporais entre observações dos fluxos. Nesse contexto, esta tese de doutoradointroduz uma nova metodologia para detectar mudanças de conceito, na qual duas deficiências de ambos paradigmas de AM são confrontados: i) a instabilidade envolvida na modelagem dos dados, e ii) a representação das dependências temporais. Essa metodologia é motivada pelo arcabouço teórico de Carlsson e Memoli, que provê uma propriedade de estabilidade para algoritmos de agrupamento hierárquico com relação à permutação dos dados. Para usufruir desse arcabouço, as observações são embutidas pelo teorema de imersão de Takens, transformando-as em independentes. Esses dados são então agrupados pelo algoritmo Single-Linkage Invariante à Permutação (PISL), o qual respeita a propriedade de estabilidade de Carlsson e Memoli. A partir dos dados de entrada, esse algoritmo gera dendrogramas (ou modelos), que são equivalentes a espaços ultramétricos. Modelos sucessivos são comparados pela distância de Gromov-Hausdorff a fim de detectar mudanças de conceito no fluxo. Como resultado, as divergências dos modelos são de fato associadas a mudanças nos dados. Experimentos foram realizados, um considerando mudanças abruptas e o outro mudanças graduais. Os resultados confirmam que a metodologia proposta é capaz de detectar mudanças de conceito, tanto abruptas quanto graduais, no entanto ela é mais adequada para cenários mais complicados. As contribuições principais desta tese são: i) o uso do teorema de imersão de Takens para transformar os dados de entrada em independentes; ii) a implementaçãodo algoritmo PISL em combinação com a distância de Gromov-Hausdorff (chamado PISLGH); iii) a comparação da metodologia proposta com outras da literatura em diferentes cenários; e, finalmente, iv) a disponibilização de um pacote em R (chamado streamChaos) que provê tanto ferramentas para processar fluxos de dados não lineares quanto diversos algoritmos para detectar mudanças de conceito.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2017
- Data da defesa: 17.08.2017
-
ABNT
COSTA, Fausto Guzzo da. Employing nonlinear time series analysis tools with stable clustering algorithms for detecting concept drift on data streams. 2017. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2017. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-13112017-105506/. Acesso em: 19 set. 2024. -
APA
Costa, F. G. da. (2017). Employing nonlinear time series analysis tools with stable clustering algorithms for detecting concept drift on data streams (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-13112017-105506/ -
NLM
Costa FG da. Employing nonlinear time series analysis tools with stable clustering algorithms for detecting concept drift on data streams [Internet]. 2017 ;[citado 2024 set. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-13112017-105506/ -
Vancouver
Costa FG da. Employing nonlinear time series analysis tools with stable clustering algorithms for detecting concept drift on data streams [Internet]. 2017 ;[citado 2024 set. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-13112017-105506/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
