Regroupement temporel dynamique

40

Quelle serait l'approche d'utiliser Dynamic Time Warping (DTW) pour regrouper des séries chronologiques?

J'ai lu que DTW était un moyen de trouver des similitudes entre deux séries chronologiques, alors qu'elles pouvaient être décalées dans le temps. Puis-je utiliser cette méthode comme mesure de similarité pour un algorithme de classification tel que k-means?

Marko
la source
2
oui, vous pouvez utiliser une mesure de similarité en tant qu'entrée. k signifie regroupement, puis déterminer des groupes dans vos données.
prévisionniste
Merci pour votre réponse Monsieur. Je suppose que pour chaque itération, je devrais former la matrice de distance pour chaque couple (centroïde, point de regroupement) et recalculer les centroïdes de manière standard, en tant que moyenne de toutes les séries appartenant à un cluster?
Marko
1
Aleksandr Blekh dans la réponse ci-dessous a un article de blog qui fournit un exemple détaillé sur la façon de procéder dans R.
prévisionniste
2
@forecaster n'utilise pas k-means avec DTW. k-moyennes minimise la variance, pas les distances. La variance est au carré euclidienne, mais cela ne signifie pas que k-means pourrait optimiser d'autres distances. La moyenne non, et en DTW, il devrait être assez facile de construire des contre-exemples, comme une onde sinusoïdale décalée de : les deux sont très similaires en DTW, mais leur moyenne est constante zéro - très différente des deux. π
Anony-Mousse
1
K-means n'est pas un algorithme approprié pour le regroupement de séries chronologiques. Les modèles de markov cachés pour les données discrètes et longitudinales sont appropriés. Il existe actuellement plusieurs ouvrages sur ce sujet, ainsi que des contributions clés de Oded Netzer (Columbia) et Steve Scott (Google). Une autre approche serait la méthode de la théorie de l'information mise au point par Andreas Brandmaier chez Max Planck, appelée groupement par distribution de permutation. Il a également écrit un module R. La comparaison des solutions de cluster est un problème différent. L'article de Marina Meila, Comparing Clusterings, Rapport technique 418 de l'Université de Washington, est le meilleur.
Mike Hunter

Réponses:

33

N'utilisez pas k-means pour les séries chronologiques.

DTW n'est pas minimisé par la moyenne; Les k-moyennes peuvent ne pas converger et même si elles convergent, cela ne donnera pas un très bon résultat. La moyenne est un estimateur des moindres carrés sur les coordonnées. Il minimise la variance, pas les distances arbitraires, et k-moyennes est conçu pour minimiser la variance, pas les distances arbitraires .

Supposons que vous avez deux séries chronologiques. Deux ondes sinusoïdales de même fréquence et d’une période d’échantillonnage assez longue; mais ils sont compensés par . Depuis que DTW réduit le temps, il peut les aligner afin qu’ils correspondent parfaitement, à l’exception du début et de la fin. DTW attribuera une distance relativement petite à ces deux séries. Cependant, si vous calculezπ moyenne des deux séries, ce sera un 0 - elles s’annulent. La moyenne ne fait pas de décalage temporel dynamique et perd toute la valeur obtenue par DTW. Sur de telles données, les k-moyennes risquent de ne pas converger et les résultats n'auront aucun sens. Les K-moyennes ne doivent en réalité être utilisées qu'avec variance (= carré euclidien), ou dans certains cas équivalents (comme le cosinus, données normalisées L2, où la similarité cosinus estla même chose que distance euclidienne au carré)2

Au lieu de cela, calculez une matrice de distance à l'aide de DTW, puis exécutez un clustering hiérarchique tel qu'un lien simple. Contrairement aux k-moyennes, la série peut même avoir une longueur différente.

Anony-Mousse
la source
4
Eh bien, il y a bien sûr PAM (K-medoids) qui fonctionne avec des distances arbitraires. Un des nombreux algorithmes qui supportent des distances arbitraires - k-means ne le fait pas. Autres choix possibles: DBSCAN, OPTICS, CLARANS, HAC, ...
Anony-Mousse
1
Probablement. Parce que k-medoids utilise DTW-medoid pour trouver le centre du cluster, pas la moyenne de L2. Je ne connais pas de regroupement réussi de séries chronologiques dans le monde réel. Je crois avoir déjà vu des journaux, mais aucun n'utilisait vraiment le résultat. Seulement des preuves de concepts.
Anony-Mousse
1
@Aleksandr Blekh a cité cet exemple parmi ses exemples: nbviewer.ipython.org/github/alexminnaar/… Quelle est votre opinion à ce sujet?
Marko
1
Problèmes de jouets. Inutile dans le monde réel. Les données réelles ont beaucoup de bruit, ce qui va faire beaucoup plus mal que les courbes sinusoïdales lisses et les modèles présentés dans ces données.
Anony-Mousse
1
Je pense que le regroupement hiérarchique est le meilleur choix. De toute façon, vous ne pourrez pas traiter un très grand nombre de séries.
Anony-Mousse
49

Oui, vous pouvez utiliser l' approche DTW pour la classification et le regroupement de séries chronologiques . J'ai compilé les ressources suivantes , qui traitent de ce sujet particulier (j'ai récemment répondu à une question similaire, mais pas sur ce site, je copie donc le contenu ici pour la commodité de tous):

Aleksandr Blekh
la source
3
+1 excellente collection d'articles et de blogs. Très bonnes références.
prévisionniste
@forecaster: Merci pour votre vote et vos gentils mots! Content que la collection vous plaise. Il est trop regrettable qu’à l’heure actuelle, je n’ai pas le temps d’apprendre plus sérieusement aux prévisions et à de nombreux autres domaines de la statistique et de la science des données, mais j’utilise chaque occasion pour apprendre quelque chose de nouveau.
Aleksandr Blekh
1
@AleksandrBlekh Merci beaucoup pour votre réponse. J'ai discuté de cette approche avec Anony-Mousse, car je m'intéresse particulièrement à DTW en tant que mesure de similarité pour K-moyennes, afin de pouvoir obtenir des centroïdes en sortie. Quelle est votre opinion et expérience avec cela? Comme vous pouvez le constater, Anony-Mousse a avancé des arguments selon lesquels les résultats pourraient ne pas être aussi bons dans ce cas ... Peut-être une expérience personnelle sur le plan pratique?
Marko le
1
Ok, merci encore. Vous avez +1 de moi et il obtient la réponse acceptée, car ma question est plus orientée vers k-means et DTW.
Marko
1
@pera: mon plaisir. Merci d'avoir voté. Totalement comprendre et être d'accord sur l'acceptation, pas de problème du tout.
Aleksandr Blekh
1

Une méthode récente DTW Barycenter Averaging (DBA) a été proposée par Petitjean et al. à des séries chronologiques moyennes. Dans un autre article, ils ont prouvé empiriquement et théoriquement comment utiliser cette méthode pour regrouper des séries chronologiques avec des k-moyennes. Une implémentation est fournie sur GitHub par les auteurs ( lien vers code ).

1 F. Petitjean, G. Forestier, GI Webb, AE Nicholson, Y. Chen et E. Keogh, «La mise en moyenne temporelle dynamique de la série chronologique permet une classification plus rapide et plus précise», conférence internationale de l'IEEE sur l'exploration de données, 2014, Shenzhen, 2014 .

2 F. Petitjean, P. Gançarski, Synthèse d'un ensemble de séries chronologiques en faisant la moyenne: de la séquence de Steiner à l'alignement multiple compact, Informatique théorique, Volume 414, numéro 1, 2012

Hassan ISMAIL FAWAZ
la source
2
veuillez fournir des références complètes au lieu de liens. Les liens peuvent mourir
Antoine
1

Dynamic Time Warp compare les points de données réalisés, qui peuvent ou non fonctionner. Une approche plus rigoureuse consiste à comparer la distribution de la série chronologique au moyen d’une métrique appelée distance du télescope. .

La bonne chose à propos de cette métrique est que le calcul empirique est effectué en ajustant une série de classificateurs binaires tels que SVM.

Pour une brève explication, voir ceci .

Pour les séries chronologiques de regroupement, il a été démontré que ses performances étaient supérieures à celles de DTW; voir le tableau 1 dans le document d'origine [1].

[1] Ryabko, D. et Mary, J. (2013). Métrique basée sur une classification binaire entre les distributions de séries chronologiques et son utilisation dans les problèmes statistiques et d'apprentissage. Le journal de la recherche en apprentissage machine, 14 (1), 2837-2856.

horaceT
la source
2
Une tentative de rédacteur en chef note: "Jérémie Mary (co-auteur) a une page Web traitant de l’algorithme avec une implémentation de R.
gung - Reinstate Monica
@gung Wow, excellent! J'ai eu une correspondance avec le premier auteur et il ne l'a pas mentionné.
HoraceT
En fait, je ne fais que copier quelqu'un qui a tenté de l'éditer dans votre réponse, @horaceT. Je ne sais pas trop à ce sujet.
gung - Réintégrer Monica
0

Oui. Une approche naïve et potentiellement lente pourrait être,

  1. Créez vos combinaisons de toutes les grappes. k correspond au nombre de groupes et n au nombre de séries. Le nombre d'articles retournés devrait être n! / k! / (n-k)!. Ce serait quelque chose comme des centres potentiels.
  2. Pour chaque série, calculez les distances via DTW pour chaque centre de chaque groupe et attribuez-les au minimum.
  3. Pour chaque groupe de clusters, calculez la distance totale au sein de chaque cluster.
  4. Choisissez le minimum.

Je l'ai utilisé pour un petit projet. Voici le mon référentiel sur le clustering de séries chronologiques et mon autre réponse à ce sujet.

Dogan Askan
la source