• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
Documento
Autor
Nome completo
Diego Furtado Silva
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2017
Orientador
Banca examinadora
Batista, Gustavo Enrique de Almeida Prado Alves (Presidente)
Meira Junior, Wagner
Prati, Ronaldo Cristiano
Rezende, Solange Oliveira
Título em inglês
Large scale similarity-based time series mining
Palavras-chave em inglês
Data mining
Dynamic Time Warping
Similarity measures
Time series
Resumo em inglês
Time series are ubiquitous in the day-by-day of human beings. A diversity of application domains generate data arranged in time, such as medicine, biology, economics, and signal processing. Due to the great interest in time series, a large variety of methods for mining temporal data has been proposed in recent decades. Several of these methods have one characteristic in common: in their cores, there is a (dis)similarity function used to compare the time series. Dynamic Time Warping (DTW) is arguably the most relevant, studied and applied distance measure for time series analysis. The main drawback of DTW is its computational complexity. At the same time, there are a significant number of data mining tasks, such as motif discovery, which requires a quadratic number of distance computations. These tasks are time intensive even for less expensive distance measures, like the Euclidean Distance. This thesis focus on developing fast algorithms that allow large-scale analysis of temporal data, using similarity-based methods for time series data mining. The contributions of this work have implications in several data mining tasks, such as classification, clustering and motif discovery. Specifically, the main contributions of this thesis are the following: (i) an algorithm to speed up the exact DTW calculation and its embedding into the similarity search procedure; (ii) a novel DTW-based spurious prefix and suffix invariant distance; (iii) a music similarity representation with implications on several music mining tasks, and a fast algorithm to compute it, and; (iv) an efficient and anytime method to find motifs and discords under the proposed prefix and suffix invariant DTW.
Título em português
Mineração de séries temporais por similaridade em larga escala
Palavras-chave em português
Dynamic Time Warping
Medidas de similaridade
Mineração de dados
Séries temporais
Resumo em português
Séries temporais são ubíquas no dia-a-dia do ser humano. Dados organizados no tempo são gerados em uma infinidade de domínios de aplicação, como medicina, biologia, economia e processamento de sinais. Devido ao grande interesse nesse tipo de dados, diversos métodos de mineração de dados temporais foram propostos nas últimas décadas. Muitos desses métodos possuem uma característica em comum: em seu núcleo, há uma função de (dis)similaridade utilizada para comparar as séries. Dynamic Time Warping (DTW) é indiscutivelmente a medida de distância mais relevante na análise de séries temporais. A principal dificuldade em se utilizar a DTW é seu alto custo computacional. Ao mesmo tempo, algumas tarefas de mineração de séries temporais, como descoberta de motifs, requerem um alto número de cálculos de distância. Essas tarefas despendem um grande tempo de execução, mesmo utilizando-se medidas de distância menos custosas, como a distância Euclidiana. Esta tese se concentra no desenvolvimento de algoritmos eficientes que permitem a análise de dados temporais em larga escala, utilizando métodos baseados em similaridade. As contribuições desta tese têm implicações em variadas tarefas de mineração de dados, como classificação, agrupamento e descoberta de padrões frequentes. Especificamente, as principais contribuições desta tese são: (i) um algoritmo para acelerar o cálculo exato da distância DTW e sua incorporação ao processo de busca por similaridade; (ii) um novo algoritmo baseado em DTW para prover invariância a prefixos e sufixos espúrios no cálculo da distância; (iii) uma representação de similaridade musical com implicações em diferentes tarefas de mineração de dados musicais e um algoritmo eficiente para computá-la; (iv) um método eficiente e anytime para encontrar motifs e discords baseado na medida DTW invariante a prefixos e sufixos.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2017-12-07
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2014. Todos os direitos reservados.