Je fais des recherches sur des méthodes de comparaison des données de la série chronologique. L'un des algorithmes que j'ai trouvés utilisés pour correspondre à ce type de données est l'algorithme DTW (dynamique de gauchissement du temps).
Les données que j'ai, ressemblent à la structure suivante (cela peut être un chemin): P>
Path Event Time Location (x,y) 1 1 2:30:02 1,5 1 2 2:30:04 2,7 1 3 2:30:06 4,4 ... ...
3 Réponses :
Si deux chemins ont la même longueur, disons n , ils sont vraiment des points dans un espace 2n -dimensionnel. Le premier emplacement détermine les deux premières dimensions, le deuxième emplacement détermine les deux dimensions suivantes, etc. Par exemple, si nous prenons simplement les trois points de votre exemple, le chemin peut être représenté comme le point 6 dimensions (1, 5, 2, 7, 4, 4). Si nous voulons la comparer à cela à un autre chemin de trois points, nous pouvons calculer la distance euclidienne (racine carrée de la somme des carrés de distances de la dimension entre les deux points) ou la distance de Manhattan (somme des différences par dimensions ). Par exemple, le chemin ennuyeux qui reste à (0, 0) pendant les trois fois devient le point 6 dimensions (0, 0, 0, 0, 0, 0). Ensuite, la distance euclidienne entre ce point et votre exemple de chemin est Bien sûr, un problème avec cette approche est que tous les chemins ne seront pas de la même longueur. Cependant, vous pouvez facilement couper le chemin plus long sur la même longueur que le chemin plus court, ou considérez la plus courte des deux chemins pour rester au même endroit ou en déplaçant dans la même direction après la fin des mesures, jusqu'à ce que les deux chemins soient de la même longueur. . L'une ou l'autre approche présentera des inexactitudes, mais peu importe ce que vous devez faire face au fait que vous manquez des données sur le chemin court et que vous devez le compenser en quelque sorte. supposant que alors, vous pouvez utiliser le code suivant pour trouver la distance de Manhattan: avec les mêmes hypothèses que pour la distance de Manhattan, nous pouvons générer la distance euclidienne comme suit: sqrt ((1-0) ^ 2 + (5-0) ^ 2 + (2-0) ^ 2 + (7-0) ^ 2 + ( 4-0) ^ 2 + (4-0) ^ 2) = sqrt (111) = 10.54 . La distance de Manhattan est ABS (1-0) + ABS (5-0) + ABS (2-0) + ABS (7-0) + ABS (4-0) + ABS (4-0) = 23 . Ce genre de différence entre les métriques n'est pas inhabituel, car la distance de Manhattan est prouvante au moins aussi grande que la distance euclidienne. chemin1 et chemin2 sont les deux Liste
J'ai aussi eu cette idée, mais je ne pouvais pas l'appliquer, principalement du fait que les chemins ne sont jamais égaux (certains chemins peuvent être 10x la longueur d'autres chemins), une fonction de fenêtrage prendrait donc du temps le temps.
Pas nécessairement. Comme je l'ai mentionné ci-dessus, vous pourriez couper le chemin plus long pour correspondre à la longueur du chemin plus court, puis calculer simplement la distance de là. Pas besoin d'une fonction de fenêtrage.
Est-ce que cela considère l'ordre des points? Si je marche un chemin dans une direction, il ne faut pas correspondre au même chemin dans l'autre sens (retour)
Cela considère que l'ordre des points, car l'appel enumérable.zip (utilisé pour créer des points de correspondance) correspond au premier point de chemin1 avec le premier point de chemin2, le deuxième point de chemin1 avec le deuxième point de chemin2, etc.
J'ai testé cela, désolé pour la réponse tardive. Cela fonctionne correctement. Merci.
Il y a une autre question ici qui pourrait être de l'aide. Si vous avez déjà un chemin donné, vous pouvez trouver la correspondance la plus proche en utilisant l'algorithme de distance croisée; D'autre part, si vous voulez réellement résoudre le problème de reconnaissance de modèle, vous voudrez peut-être en savoir plus sur la distance de LevenShtein et la correspondance élastique (de Wikipedia: «La correspondance élastique peut être définie comme un problème d'optimisation du gauchissement bidimensionnel spécifiant pixels correspondants entre des images soumises ".
Le mot clé que vous recherchez est "(Dis) Mesures de similarité".
Distance Euclidienne (ED) telle que mentionnée par Adam Mihalcin (première réponse) est facilement calculable et reflète en quelque sorte la compréhension naturelle de la distance de mot en langage naturel. Pourtant, lors de la comparaison de deux séries chronologiques, DTW doit être préféré - en particulier lorsqu'il est appliqué aux données du monde réel.
1) ED ne peut être appliqué qu'à une série de longueur égale. Par conséquent, lorsque des points sont manquants, ED n'est simplement pas calculable (sauf coupant également l'autre séquence, ne perd ainsi plus d'informations).
2) ED ne permet pas de changer de temps ou de déformation temporelle opposée à tous les algorithmes basés sur DTW.
Ainsi, ed n'est pas une véritable alternative à la DTW, car les exigences et les restrictions sont beaucoup plus élevées. Mais pour répondre à votre question, je souhaite vous recommander cette conférence:
Clustering série horaire - Revue d'une décennie Saeed Aghabozorgi, Ali Seyed Shirkhorshidi, Teh Ying Wah http://www.sciencepeirect.com/science/article/pii/s0306437915000733
Ce document donne une vue d'ensemble des mesures de similarité (dis) utilisées dans la série de séries chronologiques. Ici un petit extrait pour motiver votre lecture réellement sur le papier:
Cette réponse ne répond pas à la question réelle, mais cela fonctionne parfaitement comme une réaction à la réponse acceptée. Vous avez complètement raison, ed n'est pas du tout une alternative à DTW. Merci beaucoup, +1 pour explication.
Vous devez fournir plus d'informations ici. Quelle logique est en train de décider d'un "match"? Si j'utilise le cas de reconnaissance de geste et que l'exemple d'un chemin d'accès, tel que le dessin du nombre "6", une correspondance requise en fonction de la forme du chemin (c'est-à-dire: un grand 6 devraient "faire correspondre" un petit "6" - mise à l'échelle uniquement), la topologie du chemin (c.-à-d.: correspond aux matchs "6" "6" "B '" B', etc.), la vitesse du trajet (c.-à-d .: une tirée rapide 6 ne correspond pas à une tirée lentement) - Qu'est-ce que vous essayez d'accomplir? À quelle précision? Avec quels poids? Un problème comme celui-ci a besoin de plus de paramètres.