Algorithme: Comprendre quand un graphique à deux lignes est similaire

Question

J'essaie de développer un script capable de comprendre quand deux graphiques à lignes sont similaires (ils ont une direction similaire ou des valeurs similaires).

Par exemple suppose que j'ai deux tableaux:

array1 = [0,1,2,3,4,5,6,7,8,9,10]; 

array2 = [2,3,4,5,6,7,8,8,10,11,12]; 

Comme vous pouvez le voir, ils la croissance et leurs valeurs sont tout à fait semblables. J'ai actuellement trouvé une solution qui fonctionne parfaitement en utilisant un algorithme DTW. Le problème est que le DTW a un "partie de formation" très rapide (je dois juste stocker beaucoup de lignes de graphique), mais il a une partie de prédiction lourde car il compare le dernier graphique linéaire avec tous les autres dans Mémoire. Donc, ma question est la suivante: est-il possible de déplacer le temps de complexité de calcul pendant la partie d'entraînement afin d'avoir une prédiction plus rapide? Par exemple créer un arbre de recherche ou quelque chose comme ça? Et s'il est possible, en conséquence, à quelle valeur spécifique puis-je regrouper l'information?

Avez-vous des conseils ou des liens utiles?

Answer 1

Il est souvent possible de mapper les objets de votre domaine vers un espace linéaire. Par exemple, vous pouvez voir comment cela fonctionne pour les plongées de mots dans les langues naturelles (word2vec tutorial, passez à "Visualisation des incorporations apprises"). Dans ce cas, la similarité entre les objets est définie par une distance dans l'espace linéaire, qui est très rapide à calculer.

La complexité du mappage dépend beaucoup de vos données: la diversité des graphiques et le type de similarité que vous souhaitez capturer.

Dans votre exemple avec deux vecteurs, il est possible de calculer une seule valeur: la pente du regression line. Cela fonctionnera probablement parce que vos graphiques sont "quelque peu linéaires" dans la nature. Si vous souhaitez également capturer des motifs sinusoïdaux, vous pouvez essayer de normaliser la série chronologique en soustrayant la première valeur. Encore une fois, dans votre exemple, ça va montrer un ajustement parfait.

Conclusion: la complexité du mappage est déterminée par la complexité des données.

Answer 2

Si elles ont toujours la même longueur, corrélation de Pearson devrait être beaucoup plus approprié, et beaucoup plus rapide. Si vous normalisez vos vecteurs, Pearson est euclidien et vous pouvez utiliser n'importe quel arbre de recherche multidimensionnel pour une accélération plus poussée.