Clustering dinâmico de distorção do tempo

Qual seria a abordagem para usar o Dynamic Time Warping (DTW) para executar o agrupamento de séries temporais?

Eu li sobre o DTW como uma maneira de encontrar semelhança entre duas séries temporais, enquanto elas poderiam ser alteradas no tempo. Posso usar esse método como uma medida de similaridade para algoritmos de cluster como k-means?

Você não usar k-médias para timeseries.

DTW não é minimizado pela média; O k-means pode não convergir e, mesmo se convergir, não produzirá um resultado muito bom. A média é um estimador de mínimos quadrados nas coordenadas. Minimiza a variação, não distâncias arbitrárias, e o k-means é projetado para minimizar a variação, não distâncias arbitrárias .

Suponha que você tenha duas séries temporais. Duas ondas senoidais, da mesma frequência, e um período de amostragem bastante longo; mas eles são deslocados por . Como o DTW distorce o tempo, ele pode alinhá-los para que correspondam perfeitamente, exceto o começo e o fim. A DTW atribuirá uma distância bastante pequena a essas duas séries. No entanto, se você calcular a média das duas séries, será um 0 simples - elas serão canceladas. A média não faz distorção dinâmica do tempo e perde todo o valor que a DTW recebeu. Nesses dados, o k-means pode não convergir e os resultados serão sem sentido. Os meios K realmente devem ser usados ​​apenas com variância (= euclidiana ao quadrado) ou em alguns casos equivalentes (como cosseno, em dados normalizados de L2, onde a semelhança de cosseno é$\pi$o mesmo que distância euclidiana ao quadrado)$2 -$

Em vez disso, calcule uma matriz de distância usando o DTW e execute o cluster hierárquico, como o link único. Em contraste com o k-mean, a série pode até ter um comprimento diferente.

Sim, você pode usar a abordagem DTW para classificação e agrupamento de séries temporais . Compilei os seguintes recursos , focados nesse mesmo tópico (recentemente respondi a uma pergunta semelhante, mas não neste site, por isso estou copiando o conteúdo aqui para conveniência de todos):

• Classificação / agrupamento de séries temporais UCR : página principal , página do software e papel correspondente
• Classificação e agrupamento de séries temporais com Python : uma postagem no blog
• Capital Bikeshare: Cluster de séries temporais : outro post do blog
• Classificação e agrupamento de séries temporais : notebook ipython
• Dynamic Time Warping usando rpy e Python : outra postagem no blog
• Mineração de séries temporais com trilhões de pontos: distorção dinâmica do tempo em escala : outra postagem no blog
• Análise de séries temporais e mineração em R (para adicionar R à mistura): mais uma postagem no blog
• E, finalmente, duas ferramentas implementando / dando suporte ao DTW , ainda por cima: pacote R e módulo Python

Um método recente DTW Barycenter Averaging (DBA) foi proposto por Petitjean et al. para séries temporais médias. Em outro artigo, eles provaram empiricamente e teoricamente como ele pode ser usado para agrupar séries temporais com k-médias. Uma implementação é fornecida no GitHub pelos autores ( link para código ).

1 F. Petitjean, G. Forestier, GI Webb, AE Nicholson, Y. Chen e E. Keogh, "A média dinâmica de distorção temporal das séries temporais permite uma classificação mais rápida e precisa", Conferência Internacional IEEE de 2014 sobre mineração de dados, Shenzhen, 2014 .

2 F. Petitjean, P. Gançarski, Resumindo um conjunto de séries temporais calculando a média: Da sequência de Steiner ao compacto alinhamento múltiplo, Ciência da Computação Teórica, Volume 414, Edição 1, 2012

O Dynamic Time Warp compara os pontos de dados realizados, que podem ou não funcionar. Uma abordagem mais rigorosa é comparar a distribuição das séries temporais por meio de uma métrica chamada distância do telescópio .

O interessante dessa métrica é que o cálculo empírico é feito ajustando uma série de classificadores binários como o SVM.

Para uma breve explicação, veja isso .

Para cluster de séries temporais, foi demonstrado que supera o DTW; veja a Tabela 1 no documento original [1].

[1] Ryabko, D. & Mary, J. (2013). Uma métrica baseada em classificação binária entre distribuições de séries temporais e seu uso em problemas estatísticos e de aprendizado. O Journal of Machine Learning Research, 14 (1), 2837-2856.

Sim. Uma abordagem ingênua e potencialmente lenta pode ser,

1. Crie todas as suas combinações de cluster. k é para contagem de cluster en é para número de séries. O número de itens retornados deve ser n! / k! / (n-k)!. Seriam algo como centros em potencial.
2. Para cada série, calcule as distâncias via DTW para cada centro em cada grupo de clusters e atribua-o ao mínimo.
3. Para cada grupo de clusters, calcule a distância total em clusters individuais.
4. Escolha o mínimo.

Eu usei isso para um pequeno projeto. Aqui está o meu repositório sobre o cluster de séries temporais e minha outra resposta sobre isso.